From 95871dcc45f6531b4c692ff892aad56bdd95e16f Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Fri, 10 Feb 2023 12:14:36 +0100 Subject: pkg/subsystem: restructure the package Remove the entity and match subpackages. Regenerate the linux.go file. --- pkg/subsystem/match/coincidence.go | 55 -------------------- pkg/subsystem/match/coincidence_test.go | 40 --------------- pkg/subsystem/match/match.go | 75 ---------------------------- pkg/subsystem/match/match_test.go | 52 ------------------- pkg/subsystem/match/path_coincidence.go | 68 ------------------------- pkg/subsystem/match/path_coincidence_test.go | 49 ------------------ 6 files changed, 339 deletions(-) delete mode 100644 pkg/subsystem/match/coincidence.go delete mode 100644 pkg/subsystem/match/coincidence_test.go delete mode 100644 pkg/subsystem/match/match.go delete mode 100644 pkg/subsystem/match/match_test.go delete mode 100644 pkg/subsystem/match/path_coincidence.go delete mode 100644 pkg/subsystem/match/path_coincidence_test.go (limited to 'pkg/subsystem/match') diff --git a/pkg/subsystem/match/coincidence.go b/pkg/subsystem/match/coincidence.go deleted file mode 100644 index 45bd98884..000000000 --- a/pkg/subsystem/match/coincidence.go +++ /dev/null @@ -1,55 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import "github.com/google/syzkaller/pkg/subsystem/entity" - -// CoincidenceMatrix represents a matrix that, for every pair of subsystems -// A and B, stores the number of times A and B have coincided in the input data. -// So far we only need it for entity.Subsystem, so its interface is tailored to it. -type CoincidenceMatrix struct { - matrix map[*entity.Subsystem]map[*entity.Subsystem]int -} - -func MakeCoincidenceMatrix() *CoincidenceMatrix { - return &CoincidenceMatrix{ - matrix: make(map[*entity.Subsystem]map[*entity.Subsystem]int), - } -} - -func (cm *CoincidenceMatrix) Record(items ...*entity.Subsystem) { - for i := 0; i < len(items); i++ { - for j := 0; j < len(items); j++ { - cm.inc(items[i], items[j]) - } - } -} - -func (cm *CoincidenceMatrix) Count(a *entity.Subsystem) int { - return cm.Get(a, a) -} - -func (cm *CoincidenceMatrix) Get(a, b *entity.Subsystem) int { - return cm.matrix[a][b] -} - -func (cm *CoincidenceMatrix) NonEmptyPairs(cb func(a, b *entity.Subsystem, val int)) { - for a, sub := range cm.matrix { - for b, val := range sub { - if a == b { - continue - } - cb(a, b, val) - } - } -} - -func (cm *CoincidenceMatrix) inc(a, b *entity.Subsystem) { - subMatrix, ok := cm.matrix[a] - if !ok { - subMatrix = make(map[*entity.Subsystem]int) - cm.matrix[a] = subMatrix - } - subMatrix[b]++ -} diff --git a/pkg/subsystem/match/coincidence_test.go b/pkg/subsystem/match/coincidence_test.go deleted file mode 100644 index 15f0dd241..000000000 --- a/pkg/subsystem/match/coincidence_test.go +++ /dev/null @@ -1,40 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import ( - "testing" - - "github.com/google/syzkaller/pkg/subsystem/entity" - "github.com/stretchr/testify/assert" -) - -func TestCoincidenceMatrix(t *testing.T) { - cm := MakeCoincidenceMatrix() - a, b, c := &entity.Subsystem{}, &entity.Subsystem{}, &entity.Subsystem{} - cm.Record(a, b) - cm.Record(b, c) - - // Test counts. - assert.Equal(t, cm.Count(a), 1) - assert.Equal(t, cm.Count(b), 2) - assert.Equal(t, cm.Count(c), 1) - - // Test pairwise counts. - assert.Equal(t, cm.Get(a, b), 1) - assert.Equal(t, cm.Get(b, c), 1) - assert.Equal(t, cm.Get(a, c), 0) - - // Test the iterator. - type pair struct { - a *entity.Subsystem - b *entity.Subsystem - } - expected := []pair{{a, b}, {b, a}, {b, c}, {c, b}} - got := []pair{} - cm.NonEmptyPairs(func(a, b *entity.Subsystem, _ int) { - got = append(got, pair{a, b}) - }) - assert.ElementsMatch(t, expected, got) -} diff --git a/pkg/subsystem/match/match.go b/pkg/subsystem/match/match.go deleted file mode 100644 index 31874f978..000000000 --- a/pkg/subsystem/match/match.go +++ /dev/null @@ -1,75 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import ( - "regexp" - "strings" - - "github.com/google/syzkaller/pkg/subsystem/entity" -) - -type PathMatcher struct { - matches []*match -} - -type match struct { - include *regexp.Regexp - exclude *regexp.Regexp - object *entity.Subsystem -} - -func MakePathMatcher(list []*entity.Subsystem) *PathMatcher { - m := &PathMatcher{} - for _, item := range list { - m.register(item) - } - return m -} - -func (p *PathMatcher) register(item *entity.Subsystem) { - onlyInclude := []string{} - list := []entity.PathRule{} - for _, r := range item.PathRules { - if r.ExcludeRegexp == "" { - // It's expected that almost everything will go to this branch. - onlyInclude = append(onlyInclude, r.IncludeRegexp) - } else { - list = append(list, r) - } - } - if len(onlyInclude) > 0 { - list = append(list, entity.PathRule{ - IncludeRegexp: strings.Join(onlyInclude, "|"), - }) - } - for _, rule := range list { - p.matches = append(p.matches, buildMatch(rule, item)) - } -} - -func (p *PathMatcher) Match(path string) []*entity.Subsystem { - ret := []*entity.Subsystem{} - for _, m := range p.matches { - if m.exclude != nil && m.exclude.MatchString(path) { - continue - } - if m.include != nil && !m.include.MatchString(path) { - continue - } - ret = append(ret, m.object) - } - return ret -} - -func buildMatch(rule entity.PathRule, item *entity.Subsystem) *match { - m := &match{object: item} - if rule.IncludeRegexp != "" { - m.include = regexp.MustCompile(rule.IncludeRegexp) - } - if rule.ExcludeRegexp != "" { - m.exclude = regexp.MustCompile(rule.ExcludeRegexp) - } - return m -} diff --git a/pkg/subsystem/match/match_test.go b/pkg/subsystem/match/match_test.go deleted file mode 100644 index 2f7440e19..000000000 --- a/pkg/subsystem/match/match_test.go +++ /dev/null @@ -1,52 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import ( - "testing" - - "github.com/google/syzkaller/pkg/subsystem/entity" - "github.com/stretchr/testify/assert" -) - -func TestPathMatcher(t *testing.T) { - arm := &entity.Subsystem{ - PathRules: []entity.PathRule{ - { - IncludeRegexp: `^arch/arm/.*$`, - ExcludeRegexp: `^arch/arm/boot/dts/.*$`, - }, - {IncludeRegexp: `^drivers/spi/spi-pl022\.c$`}, - { - // nolint:lll - IncludeRegexp: `^drivers/irqchip/irq-vic\.c$|^Documentation/devicetree/bindings/interrupt-controller/arm,vic\.yaml$`, - }, - }, - } - docs := &entity.Subsystem{ - PathRules: []entity.PathRule{ - {IncludeRegexp: `^Documentation/.*$`}, - }, - } - m := MakePathMatcher([]*entity.Subsystem{arm, docs}) - assert.ElementsMatch(t, []*entity.Subsystem{arm, docs}, - m.Match(`Documentation/devicetree/bindings/interrupt-controller/arm,vic.yaml`)) - assert.ElementsMatch(t, []*entity.Subsystem{arm}, m.Match(`arch/arm/a.c`)) - assert.ElementsMatch(t, []*entity.Subsystem{docs}, m.Match(`Documentation/a/b/c.md`)) - assert.Empty(t, m.Match(`arch/boot/dts/a.c`)) -} - -func TestPathMatchOrder(t *testing.T) { - s := &entity.Subsystem{ - PathRules: []entity.PathRule{ - { - IncludeRegexp: `^a/b/.*$`, - ExcludeRegexp: `^a/.*$`, - }, - }, - } - m := MakePathMatcher([]*entity.Subsystem{s}) - // If we first exclude a/, then a/b/c never matches. - assert.Empty(t, m.Match("a/b/c")) -} diff --git a/pkg/subsystem/match/path_coincidence.go b/pkg/subsystem/match/path_coincidence.go deleted file mode 100644 index 944546490..000000000 --- a/pkg/subsystem/match/path_coincidence.go +++ /dev/null @@ -1,68 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import ( - "io/fs" - "regexp" - "runtime" - "sync" - - "github.com/google/syzkaller/pkg/subsystem/entity" -) - -func BuildCoincidenceMatrix(root fs.FS, list []*entity.Subsystem, - excludeRe *regexp.Regexp) (*CoincidenceMatrix, error) { - // Create a matcher. - matcher := MakePathMatcher(list) - chPaths, chResult := extractSubsystems(matcher) - // The final consumer goroutine. - cm := MakeCoincidenceMatrix() - ready := make(chan struct{}) - go func() { - for items := range chResult { - cm.Record(items...) - } - ready <- struct{}{} - }() - // Source of data. - err := fs.WalkDir(root, ".", func(path string, info fs.DirEntry, err error) error { - if err != nil || info.IsDir() { - return err - } - if !includePathRe.MatchString(path) || - (excludeRe != nil && excludeRe.MatchString(path)) { - return nil - } - chPaths <- path - return nil - }) - close(chPaths) - <-ready - return cm, err -} - -var ( - includePathRe = regexp.MustCompile(`(?:/|\.(?:c|h|S))$`) -) - -func extractSubsystems(matcher *PathMatcher) (chan<- string, <-chan []*entity.Subsystem) { - procs := runtime.NumCPU() - paths, output := make(chan string, procs), make(chan []*entity.Subsystem, procs) - var wg sync.WaitGroup - for i := 0; i < procs; i++ { - wg.Add(1) - go func() { - defer wg.Done() - for path := range paths { - output <- matcher.Match(path) - } - }() - } - go func() { - wg.Wait() - close(output) - }() - return paths, output -} diff --git a/pkg/subsystem/match/path_coincidence_test.go b/pkg/subsystem/match/path_coincidence_test.go deleted file mode 100644 index 2d1969d7f..000000000 --- a/pkg/subsystem/match/path_coincidence_test.go +++ /dev/null @@ -1,49 +0,0 @@ -// Copyright 2023 syzkaller project authors. All rights reserved. -// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. - -package match - -import ( - "testing" - "testing/fstest" - - "github.com/google/syzkaller/pkg/subsystem/entity" - "github.com/stretchr/testify/assert" -) - -func TestBuildCoincidenceMatrix(t *testing.T) { - vfs := &entity.Subsystem{PathRules: []entity.PathRule{ - {IncludeRegexp: `^fs/`}, - }} - ext4 := &entity.Subsystem{PathRules: []entity.PathRule{ - {IncludeRegexp: `^fs/ext4/`}, - }} - ntfs := &entity.Subsystem{PathRules: []entity.PathRule{ - {IncludeRegexp: `^fs/ntfs/`}, - }} - kernel := &entity.Subsystem{PathRules: []entity.PathRule{ - {IncludeRegexp: `.*`}, - }} - - fs := fstest.MapFS{ - ".git/obj/12345": {}, - "fs/inode.c": {}, - "fs/ext4/file.c": {}, - "fs/ntfs/file.c": {}, - "fs/fat/file.c": {}, - "net/socket.c": {}, - } - matrix, err := BuildCoincidenceMatrix(fs, []*entity.Subsystem{vfs, ntfs, ext4, kernel}, nil) - assert.NoError(t, err) - - // Test total counts. - assert.Equal(t, 5, matrix.Count(kernel)) - assert.Equal(t, 4, matrix.Count(vfs)) - assert.Equal(t, 1, matrix.Count(ext4)) - - // Test pairwise counts. - assert.Equal(t, 1, matrix.Get(vfs, ext4)) - assert.Equal(t, 1, matrix.Get(vfs, ntfs)) - assert.Equal(t, 0, matrix.Get(ext4, ntfs)) - assert.Equal(t, 4, matrix.Get(kernel, vfs)) -} -- cgit mrf-deployment