aboutsummaryrefslogtreecommitdiffstats
path: root/pkg/subsystem/linux
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/subsystem/linux')
-rw-r--r--pkg/subsystem/linux/coincidence.go55
-rw-r--r--pkg/subsystem/linux/coincidence_test.go40
-rw-r--r--pkg/subsystem/linux/maintainers.go6
-rw-r--r--pkg/subsystem/linux/maintainers_test.go7
-rw-r--r--pkg/subsystem/linux/names.go4
-rw-r--r--pkg/subsystem/linux/names_test.go8
-rw-r--r--pkg/subsystem/linux/parents.go35
-rw-r--r--pkg/subsystem/linux/parents_test.go69
-rw-r--r--pkg/subsystem/linux/path_coincidence.go68
-rw-r--r--pkg/subsystem/linux/path_coincidence_test.go49
-rw-r--r--pkg/subsystem/linux/subsystems.go19
-rw-r--r--pkg/subsystem/linux/subsystems_test.go7
12 files changed, 286 insertions, 81 deletions
diff --git a/pkg/subsystem/linux/coincidence.go b/pkg/subsystem/linux/coincidence.go
new file mode 100644
index 000000000..86ee0794f
--- /dev/null
+++ b/pkg/subsystem/linux/coincidence.go
@@ -0,0 +1,55 @@
+// 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 linux
+
+import "github.com/google/syzkaller/pkg/subsystem"
+
+// 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 subsystem.Subsystem, so its interface is tailored to it.
+type CoincidenceMatrix struct {
+ matrix map[*subsystem.Subsystem]map[*subsystem.Subsystem]int
+}
+
+func MakeCoincidenceMatrix() *CoincidenceMatrix {
+ return &CoincidenceMatrix{
+ matrix: make(map[*subsystem.Subsystem]map[*subsystem.Subsystem]int),
+ }
+}
+
+func (cm *CoincidenceMatrix) Record(items ...*subsystem.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 *subsystem.Subsystem) int {
+ return cm.Get(a, a)
+}
+
+func (cm *CoincidenceMatrix) Get(a, b *subsystem.Subsystem) int {
+ return cm.matrix[a][b]
+}
+
+func (cm *CoincidenceMatrix) NonEmptyPairs(cb func(a, b *subsystem.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 *subsystem.Subsystem) {
+ subMatrix, ok := cm.matrix[a]
+ if !ok {
+ subMatrix = make(map[*subsystem.Subsystem]int)
+ cm.matrix[a] = subMatrix
+ }
+ subMatrix[b]++
+}
diff --git a/pkg/subsystem/linux/coincidence_test.go b/pkg/subsystem/linux/coincidence_test.go
new file mode 100644
index 000000000..8aaf5ed0a
--- /dev/null
+++ b/pkg/subsystem/linux/coincidence_test.go
@@ -0,0 +1,40 @@
+// 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 linux
+
+import (
+ "testing"
+
+ "github.com/google/syzkaller/pkg/subsystem"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestCoincidenceMatrix(t *testing.T) {
+ cm := MakeCoincidenceMatrix()
+ a, b, c := &subsystem.Subsystem{}, &subsystem.Subsystem{}, &subsystem.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 *subsystem.Subsystem
+ b *subsystem.Subsystem
+ }
+ expected := []pair{{a, b}, {b, a}, {b, c}, {c, b}}
+ got := []pair{}
+ cm.NonEmptyPairs(func(a, b *subsystem.Subsystem, _ int) {
+ got = append(got, pair{a, b})
+ })
+ assert.ElementsMatch(t, expected, got)
+}
diff --git a/pkg/subsystem/linux/maintainers.go b/pkg/subsystem/linux/maintainers.go
index 7c60a840a..2f4d63003 100644
--- a/pkg/subsystem/linux/maintainers.go
+++ b/pkg/subsystem/linux/maintainers.go
@@ -13,7 +13,7 @@ import (
"strings"
"unicode"
- "github.com/google/syzkaller/pkg/subsystem/entity"
+ "github.com/google/syzkaller/pkg/subsystem"
)
// maintainersRecord represents a single raw record in the MAINTAINERS file.
@@ -146,7 +146,7 @@ func parseEmail(value string) (string, error) {
return addr.Address, nil
}
-func (r maintainersRecord) ToPathRule() entity.PathRule {
+func (r maintainersRecord) ToPathRule() subsystem.PathRule {
inclRe := strings.Builder{}
for i, wildcard := range r.includePatterns {
if i > 0 {
@@ -167,7 +167,7 @@ func (r maintainersRecord) ToPathRule() entity.PathRule {
}
wildcardToRegexp(wildcard, &exclRe)
}
- return entity.PathRule{
+ return subsystem.PathRule{
IncludeRegexp: inclRe.String(),
ExcludeRegexp: exclRe.String(),
}
diff --git a/pkg/subsystem/linux/maintainers_test.go b/pkg/subsystem/linux/maintainers_test.go
index dc3299dbf..676bbcda1 100644
--- a/pkg/subsystem/linux/maintainers_test.go
+++ b/pkg/subsystem/linux/maintainers_test.go
@@ -8,8 +8,7 @@ import (
"testing"
"github.com/google/go-cmp/cmp"
- "github.com/google/syzkaller/pkg/subsystem/entity"
- "github.com/google/syzkaller/pkg/subsystem/match"
+ "github.com/google/syzkaller/pkg/subsystem"
)
func TestRecordToPathRule(t *testing.T) {
@@ -127,8 +126,8 @@ func TestRecordToPathRule(t *testing.T) {
for _, loopTest := range tests {
test := loopTest
t.Run(test.name, func(t *testing.T) {
- pm := match.MakePathMatcher([]*entity.Subsystem{
- {PathRules: []entity.PathRule{test.record.ToPathRule()}},
+ pm := subsystem.MakePathMatcher([]*subsystem.Subsystem{
+ {PathRules: []subsystem.PathRule{test.record.ToPathRule()}},
})
for _, path := range test.match {
if len(pm.Match(path)) != 1 {
diff --git a/pkg/subsystem/linux/names.go b/pkg/subsystem/linux/names.go
index be57a5ab3..3dcc2deed 100644
--- a/pkg/subsystem/linux/names.go
+++ b/pkg/subsystem/linux/names.go
@@ -7,12 +7,12 @@ import (
"fmt"
"regexp"
- "github.com/google/syzkaller/pkg/subsystem/entity"
+ "github.com/google/syzkaller/pkg/subsystem"
)
// setSubsystemNames assigns unique names to the presented subsystems.
// If it failed to assign a name to a subsystem, the Name field remains empty.
-func setSubsystemNames(list []*entity.Subsystem) error {
+func setSubsystemNames(list []*subsystem.Subsystem) error {
dups := map[string]bool{}
for _, item := range list {
// For now, we can only infer name from the list email.
diff --git a/pkg/subsystem/linux/names_test.go b/pkg/subsystem/linux/names_test.go
index 0b2352411..03f9a86d3 100644
--- a/pkg/subsystem/linux/names_test.go
+++ b/pkg/subsystem/linux/names_test.go
@@ -6,7 +6,7 @@ package linux
import (
"testing"
- "github.com/google/syzkaller/pkg/subsystem/entity"
+ "github.com/google/syzkaller/pkg/subsystem"
)
func TestEmailToName(t *testing.T) {
@@ -33,8 +33,8 @@ type subsystemTestInput struct {
outName string
}
-func (sti subsystemTestInput) ToSubsystem() *entity.Subsystem {
- s := &entity.Subsystem{}
+func (sti subsystemTestInput) ToSubsystem() *subsystem.Subsystem {
+ s := &subsystem.Subsystem{}
if sti.email != "" {
s.Lists = append(s.Lists, sti.email)
}
@@ -92,7 +92,7 @@ func TestSetSubsystemNames(t *testing.T) {
for _, test := range tests {
curr := test
t.Run(curr.name, func(t *testing.T) {
- list := []*entity.Subsystem{}
+ list := []*subsystem.Subsystem{}
for _, i := range curr.inputs {
list = append(list, i.ToSubsystem())
}
diff --git a/pkg/subsystem/linux/parents.go b/pkg/subsystem/linux/parents.go
index fdea4a62f..344bc0db2 100644
--- a/pkg/subsystem/linux/parents.go
+++ b/pkg/subsystem/linux/parents.go
@@ -3,14 +3,11 @@
package linux
-import (
- "github.com/google/syzkaller/pkg/subsystem/entity"
- "github.com/google/syzkaller/pkg/subsystem/match"
-)
+import "github.com/google/syzkaller/pkg/subsystem"
// parentTransformations applies all subsystem list transformations that have been implemented.
-func parentTransformations(matrix *match.CoincidenceMatrix,
- list []*entity.Subsystem) ([]*entity.Subsystem, error) {
+func parentTransformations(matrix *CoincidenceMatrix,
+ list []*subsystem.Subsystem) ([]*subsystem.Subsystem, error) {
list = dropSmallSubsystems(matrix, list)
list = dropDuplicateSubsystems(matrix, list)
err := setParents(matrix, list)
@@ -24,13 +21,13 @@ func parentTransformations(matrix *match.CoincidenceMatrix,
// We assume A is a child of B if:
// 1) B covers more paths than A.
// 2) Most of the paths that relate to A also relate to B.
-func setParents(matrix *match.CoincidenceMatrix, list []*entity.Subsystem) error {
+func setParents(matrix *CoincidenceMatrix, list []*subsystem.Subsystem) error {
// Some subsystems might have already been dropeed.
- inInput := map[*entity.Subsystem]bool{}
+ inInput := map[*subsystem.Subsystem]bool{}
for _, item := range list {
inInput[item] = true
}
- matrix.NonEmptyPairs(func(a, b *entity.Subsystem, count int) {
+ matrix.NonEmptyPairs(func(a, b *subsystem.Subsystem, count int) {
if !inInput[a] || !inInput[b] {
return
}
@@ -45,10 +42,10 @@ func setParents(matrix *match.CoincidenceMatrix, list []*entity.Subsystem) error
}
// dropSmallSubsystems removes subsystems for which we have found only a few matches in the filesystem tree.
-func dropSmallSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Subsystem) []*entity.Subsystem {
+func dropSmallSubsystems(matrix *CoincidenceMatrix, list []*subsystem.Subsystem) []*subsystem.Subsystem {
const cutOffCount = 2
- newList := []*entity.Subsystem{}
+ newList := []*subsystem.Subsystem{}
for _, item := range list {
if matrix.Count(item) > cutOffCount || len(item.Syscalls) > 0 {
newList = append(newList, item)
@@ -61,9 +58,9 @@ func dropSmallSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Subsyst
// First, if subsystems A and B 100% overlap, we prefer the one that's alphabetically first.
// Second, if subsystem A is fully enclosed in subsystem B and constitutes more than 75% of B,
// we drop A, since it brings little value.
-func dropDuplicateSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Subsystem) []*entity.Subsystem {
- drop := map[*entity.Subsystem]struct{}{}
- firstIsBetter := func(first, second *entity.Subsystem) bool {
+func dropDuplicateSubsystems(matrix *CoincidenceMatrix, list []*subsystem.Subsystem) []*subsystem.Subsystem {
+ drop := map[*subsystem.Subsystem]struct{}{}
+ firstIsBetter := func(first, second *subsystem.Subsystem) bool {
firstEmail, secondEmail := "", ""
if len(first.Lists) > 0 {
firstEmail = first.Lists[0]
@@ -73,7 +70,7 @@ func dropDuplicateSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Sub
}
return firstEmail < secondEmail
}
- matrix.NonEmptyPairs(func(a, b *entity.Subsystem, count int) {
+ matrix.NonEmptyPairs(func(a, b *subsystem.Subsystem, count int) {
// Only consider cases when A is fully enclosed in B, i.e. M[A][B] == M[A][A].
if count != matrix.Count(a) {
return
@@ -91,7 +88,7 @@ func dropDuplicateSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Sub
drop[a] = struct{}{}
}
})
- newList := []*entity.Subsystem{}
+ newList := []*subsystem.Subsystem{}
for _, item := range list {
if _, exists := drop[item]; !exists {
newList = append(newList, item)
@@ -102,15 +99,15 @@ func dropDuplicateSubsystems(matrix *match.CoincidenceMatrix, list []*entity.Sub
// The algorithm runs in O(E * (E + V)).
// We expect that E is quite low here, so it should be fine.
-func transitiveReduction(list []*entity.Subsystem) {
+func transitiveReduction(list []*subsystem.Subsystem) {
for _, s := range list {
- removeParents := map[*entity.Subsystem]bool{}
+ removeParents := map[*subsystem.Subsystem]bool{}
for _, p := range s.Parents {
for otherP := range p.ReachableParents() {
removeParents[otherP] = true
}
}
- newParents := []*entity.Subsystem{}
+ newParents := []*subsystem.Subsystem{}
for _, p := range s.Parents {
if !removeParents[p] {
newParents = append(newParents, p)
diff --git a/pkg/subsystem/linux/parents_test.go b/pkg/subsystem/linux/parents_test.go
index dde13177d..444e4ff33 100644
--- a/pkg/subsystem/linux/parents_test.go
+++ b/pkg/subsystem/linux/parents_test.go
@@ -7,40 +7,39 @@ import (
"testing"
"testing/fstest"
- "github.com/google/syzkaller/pkg/subsystem/entity"
- "github.com/google/syzkaller/pkg/subsystem/match"
+ "github.com/google/syzkaller/pkg/subsystem"
"github.com/stretchr/testify/assert"
)
func TestDropSmallSubsystems(t *testing.T) {
- kernel := &entity.Subsystem{}
- net := &entity.Subsystem{}
- fs := &entity.Subsystem{}
- legal := &entity.Subsystem{}
+ kernel := &subsystem.Subsystem{}
+ net := &subsystem.Subsystem{}
+ fs := &subsystem.Subsystem{}
+ legal := &subsystem.Subsystem{}
- matrix := match.MakeCoincidenceMatrix()
+ matrix := MakeCoincidenceMatrix()
matrix.Record(kernel, net)
matrix.Record(kernel, fs)
matrix.Record(kernel, net, fs)
matrix.Record(kernel, net, fs)
matrix.Record(kernel, net, fs)
- ret := dropSmallSubsystems(matrix, []*entity.Subsystem{kernel, net, fs, legal})
- assert.ElementsMatch(t, []*entity.Subsystem{kernel, net, fs}, ret)
+ ret := dropSmallSubsystems(matrix, []*subsystem.Subsystem{kernel, net, fs, legal})
+ assert.ElementsMatch(t, []*subsystem.Subsystem{kernel, net, fs}, ret)
}
func TestDropDuplicateSubsystems(t *testing.T) {
- input, expected := []*entity.Subsystem{}, []*entity.Subsystem{}
- matrix := match.MakeCoincidenceMatrix()
+ input, expected := []*subsystem.Subsystem{}, []*subsystem.Subsystem{}
+ matrix := MakeCoincidenceMatrix()
// Always present.
- kernel := &entity.Subsystem{Name: "kernel"}
+ kernel := &subsystem.Subsystem{Name: "kernel"}
input = append(input, kernel)
expected = append(expected, kernel)
// Fully overlap.
- sameA := &entity.Subsystem{Lists: []string{"SameA@gmail.com"}}
- sameB := &entity.Subsystem{Lists: []string{"SameB@gmail.com"}}
+ sameA := &subsystem.Subsystem{Lists: []string{"SameA@gmail.com"}}
+ sameB := &subsystem.Subsystem{Lists: []string{"SameB@gmail.com"}}
matrix.Record(kernel, sameA, sameB)
matrix.Record(kernel, sameA, sameB)
matrix.Record(kernel, sameA, sameB)
@@ -48,7 +47,7 @@ func TestDropDuplicateSubsystems(t *testing.T) {
expected = append(expected, sameA)
// Overlap, but the smaller one is not so significant.
- ext4, fs := &entity.Subsystem{Name: "ext4"}, &entity.Subsystem{Name: "fs"}
+ ext4, fs := &subsystem.Subsystem{Name: "ext4"}, &subsystem.Subsystem{Name: "fs"}
matrix.Record(kernel, ext4, fs)
matrix.Record(kernel, ext4, fs)
matrix.Record(kernel, fs) // 66%.
@@ -56,7 +55,7 @@ func TestDropDuplicateSubsystems(t *testing.T) {
expected = append(expected, ext4, fs)
// Overlap, and the smaller one takes a big part.
- toDrop, stays := &entity.Subsystem{Name: "to-drop"}, &entity.Subsystem{Name: "stays"}
+ toDrop, stays := &subsystem.Subsystem{Name: "to-drop"}, &subsystem.Subsystem{Name: "stays"}
for i := 0; i < 5; i++ {
matrix.Record(kernel, toDrop, stays)
}
@@ -75,31 +74,31 @@ func TestTransitiveReduction(t *testing.T) {
// (d, b)
// (d, e)
// (c, a)
- a := &entity.Subsystem{}
- b := &entity.Subsystem{Parents: []*entity.Subsystem{a}}
- c := &entity.Subsystem{Parents: []*entity.Subsystem{a, b}}
- e := &entity.Subsystem{}
- d := &entity.Subsystem{Parents: []*entity.Subsystem{a, b, c, e}}
- transitiveReduction([]*entity.Subsystem{a, b, c, d, e})
+ a := &subsystem.Subsystem{}
+ b := &subsystem.Subsystem{Parents: []*subsystem.Subsystem{a}}
+ c := &subsystem.Subsystem{Parents: []*subsystem.Subsystem{a, b}}
+ e := &subsystem.Subsystem{}
+ d := &subsystem.Subsystem{Parents: []*subsystem.Subsystem{a, b, c, e}}
+ transitiveReduction([]*subsystem.Subsystem{a, b, c, d, e})
// The result should be:
// (d, c), (c, b), (b, a)
// (d, e)
- assert.ElementsMatch(t, d.Parents, []*entity.Subsystem{c, e})
- assert.ElementsMatch(t, c.Parents, []*entity.Subsystem{b})
+ assert.ElementsMatch(t, d.Parents, []*subsystem.Subsystem{c, e})
+ assert.ElementsMatch(t, c.Parents, []*subsystem.Subsystem{b})
}
func TestSetParents(t *testing.T) {
- kernel := &entity.Subsystem{PathRules: []entity.PathRule{{
+ kernel := &subsystem.Subsystem{PathRules: []subsystem.PathRule{{
IncludeRegexp: `.*`,
}}}
- net := &entity.Subsystem{PathRules: []entity.PathRule{{
+ net := &subsystem.Subsystem{PathRules: []subsystem.PathRule{{
IncludeRegexp: `^net/`,
}}}
- wireless := &entity.Subsystem{PathRules: []entity.PathRule{{
+ wireless := &subsystem.Subsystem{PathRules: []subsystem.PathRule{{
IncludeRegexp: `^net/wireless`,
}}}
- drivers := &entity.Subsystem{PathRules: []entity.PathRule{{
+ drivers := &subsystem.Subsystem{PathRules: []subsystem.PathRule{{
IncludeRegexp: `^drivers/`,
}}}
@@ -114,20 +113,20 @@ func TestSetParents(t *testing.T) {
"drivers/android/binder.c": {},
}
- matrix, err := match.BuildCoincidenceMatrix(tree,
- []*entity.Subsystem{kernel, net, wireless, drivers}, nil)
+ matrix, err := BuildCoincidenceMatrix(tree,
+ []*subsystem.Subsystem{kernel, net, wireless, drivers}, nil)
assert.NoError(t, err)
// Calculate parents.
- err = setParents(matrix, []*entity.Subsystem{kernel, net, wireless, drivers})
+ err = setParents(matrix, []*subsystem.Subsystem{kernel, net, wireless, drivers})
if err != nil {
t.Fatal(err)
}
// Verify parents.
- assert.ElementsMatch(t, net.Parents, []*entity.Subsystem{kernel})
- assert.ElementsMatch(t, wireless.Parents, []*entity.Subsystem{net})
- assert.ElementsMatch(t, drivers.Parents, []*entity.Subsystem{kernel})
- assert.ElementsMatch(t, kernel.Parents, []*entity.Subsystem{})
+ assert.ElementsMatch(t, net.Parents, []*subsystem.Subsystem{kernel})
+ assert.ElementsMatch(t, wireless.Parents, []*subsystem.Subsystem{net})
+ assert.ElementsMatch(t, drivers.Parents, []*subsystem.Subsystem{kernel})
+ assert.ElementsMatch(t, kernel.Parents, []*subsystem.Subsystem{})
}
diff --git a/pkg/subsystem/linux/path_coincidence.go b/pkg/subsystem/linux/path_coincidence.go
new file mode 100644
index 000000000..44182bd6a
--- /dev/null
+++ b/pkg/subsystem/linux/path_coincidence.go
@@ -0,0 +1,68 @@
+// 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 linux
+
+import (
+ "io/fs"
+ "regexp"
+ "runtime"
+ "sync"
+
+ "github.com/google/syzkaller/pkg/subsystem"
+)
+
+func BuildCoincidenceMatrix(root fs.FS, list []*subsystem.Subsystem,
+ excludeRe *regexp.Regexp) (*CoincidenceMatrix, error) {
+ // Create a matcher.
+ matcher := subsystem.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 *subsystem.PathMatcher) (chan<- string, <-chan []*subsystem.Subsystem) {
+ procs := runtime.NumCPU()
+ paths, output := make(chan string, procs), make(chan []*subsystem.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/linux/path_coincidence_test.go b/pkg/subsystem/linux/path_coincidence_test.go
new file mode 100644
index 000000000..ac32dcd31
--- /dev/null
+++ b/pkg/subsystem/linux/path_coincidence_test.go
@@ -0,0 +1,49 @@
+// 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 linux
+
+import (
+ "testing"
+ "testing/fstest"
+
+ "github.com/google/syzkaller/pkg/subsystem"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestBuildCoincidenceMatrix(t *testing.T) {
+ vfs := &subsystem.Subsystem{PathRules: []subsystem.PathRule{
+ {IncludeRegexp: `^fs/`},
+ }}
+ ext4 := &subsystem.Subsystem{PathRules: []subsystem.PathRule{
+ {IncludeRegexp: `^fs/ext4/`},
+ }}
+ ntfs := &subsystem.Subsystem{PathRules: []subsystem.PathRule{
+ {IncludeRegexp: `^fs/ntfs/`},
+ }}
+ kernel := &subsystem.Subsystem{PathRules: []subsystem.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, []*subsystem.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))
+}
diff --git a/pkg/subsystem/linux/subsystems.go b/pkg/subsystem/linux/subsystems.go
index 5ca57a1be..18ac3864e 100644
--- a/pkg/subsystem/linux/subsystems.go
+++ b/pkg/subsystem/linux/subsystems.go
@@ -10,16 +10,15 @@ import (
"regexp"
"sort"
- "github.com/google/syzkaller/pkg/subsystem/entity"
- "github.com/google/syzkaller/pkg/subsystem/match"
+ "github.com/google/syzkaller/pkg/subsystem"
)
-func ListFromRepo(repo string) ([]*entity.Subsystem, error) {
+func ListFromRepo(repo string) ([]*subsystem.Subsystem, error) {
return listFromRepoInner(os.DirFS(repo), linuxSubsystemRules)
}
// listFromRepoInner allows for better testing.
-func listFromRepoInner(root fs.FS, rules *customRules) ([]*entity.Subsystem, error) {
+func listFromRepoInner(root fs.FS, rules *customRules) ([]*subsystem.Subsystem, error) {
records, err := getMaintainers(root)
if err != nil {
return nil, err
@@ -31,7 +30,7 @@ func listFromRepoInner(root fs.FS, rules *customRules) ([]*entity.Subsystem, err
extraRules: rules,
}
list := ctx.groupByList()
- matrix, err := match.BuildCoincidenceMatrix(root, list, dropPatterns)
+ matrix, err := BuildCoincidenceMatrix(root, list, dropPatterns)
if err != nil {
return nil, err
}
@@ -71,7 +70,7 @@ var (
dropPatterns = regexp.MustCompile(`^(Documentation|scripts|samples|tools)|Makefile`)
)
-func (ctx *linuxCtx) groupByList() []*entity.Subsystem {
+func (ctx *linuxCtx) groupByList() []*subsystem.Subsystem {
perList := make(map[string][]*maintainersRecord)
for _, record := range ctx.rawRecords {
for _, list := range record.lists {
@@ -82,7 +81,7 @@ func (ctx *linuxCtx) groupByList() []*entity.Subsystem {
if ctx.extraRules != nil {
exclude = ctx.extraRules.notSubsystemEmails
}
- ret := []*entity.Subsystem{}
+ ret := []*subsystem.Subsystem{}
for email, list := range perList {
if _, skip := exclude[email]; skip {
continue
@@ -96,7 +95,7 @@ func (ctx *linuxCtx) groupByList() []*entity.Subsystem {
return ret
}
-func (ctx *linuxCtx) applyExtraRules(list []*entity.Subsystem) {
+func (ctx *linuxCtx) applyExtraRules(list []*subsystem.Subsystem) {
if ctx.extraRules == nil {
return
}
@@ -105,7 +104,7 @@ func (ctx *linuxCtx) applyExtraRules(list []*entity.Subsystem) {
}
}
-func mergeRawRecords(email string, records []*maintainersRecord) *entity.Subsystem {
+func mergeRawRecords(email string, records []*maintainersRecord) *subsystem.Subsystem {
unique := func(list []string) []string {
m := make(map[string]struct{})
for _, s := range list {
@@ -119,7 +118,7 @@ func mergeRawRecords(email string, records []*maintainersRecord) *entity.Subsyst
return ret
}
var maintainers []string
- subsystem := &entity.Subsystem{Lists: []string{email}}
+ subsystem := &subsystem.Subsystem{Lists: []string{email}}
for _, record := range records {
rule := record.ToPathRule()
if !rule.IsEmpty() {
diff --git a/pkg/subsystem/linux/subsystems_test.go b/pkg/subsystem/linux/subsystems_test.go
index f13009fad..cbc4b9699 100644
--- a/pkg/subsystem/linux/subsystems_test.go
+++ b/pkg/subsystem/linux/subsystems_test.go
@@ -8,8 +8,7 @@ import (
"testing"
"testing/fstest"
- "github.com/google/syzkaller/pkg/subsystem/entity"
- "github.com/google/syzkaller/pkg/subsystem/match"
+ "github.com/google/syzkaller/pkg/subsystem"
"github.com/stretchr/testify/assert"
)
@@ -26,7 +25,7 @@ func TestGroupLinuxSubsystems(t *testing.T) {
// It complicates the test, so let's skip it here.
s.Parents = nil
}
- expected := []*entity.Subsystem{
+ expected := []*subsystem.Subsystem{
{
Name: "fs",
Lists: []string{"linux-fsdevel@vger.kernel.org"},
@@ -88,7 +87,7 @@ func TestLinuxSubsystemPaths(t *testing.T) {
if err != nil {
t.Fatal(err)
}
- matcher := match.MakePathMatcher(subsystems)
+ matcher := subsystem.MakePathMatcher(subsystems)
tests := []struct {
path string
list []string
generated by ggit (джигит) mrf-deployment (git 2.46.0) at 2026-03-11 21:23:10 +0000