aboutsummaryrefslogtreecommitdiffstats
path: root/pkg/subsystem
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/subsystem')
-rw-r--r--pkg/subsystem/entities.go5
-rw-r--r--pkg/subsystem/linux/parents.go37
-rw-r--r--pkg/subsystem/linux/parents_test.go4
-rw-r--r--pkg/subsystem/linux/path_coincidence.go34
-rw-r--r--pkg/subsystem/linux/path_coincidence_test.go2
-rw-r--r--pkg/subsystem/linux/subsystems.go26
-rw-r--r--pkg/subsystem/linux/subsystems_test.go10
7 files changed, 83 insertions, 35 deletions
diff --git a/pkg/subsystem/entities.go b/pkg/subsystem/entities.go
index 493f2fe67..f7c364299 100644
--- a/pkg/subsystem/entities.go
+++ b/pkg/subsystem/entities.go
@@ -82,3 +82,8 @@ type PathRule struct {
func (pr *PathRule) IsEmpty() bool {
return pr.IncludeRegexp == "" && pr.ExcludeRegexp == ""
}
+
+type DebugInfo struct {
+ ParentChildComment map[*Subsystem]map[*Subsystem]string
+ FileLists map[*Subsystem][]string
+}
diff --git a/pkg/subsystem/linux/parents.go b/pkg/subsystem/linux/parents.go
index 344bc0db2..846f2b2b1 100644
--- a/pkg/subsystem/linux/parents.go
+++ b/pkg/subsystem/linux/parents.go
@@ -3,42 +3,61 @@
package linux
-import "github.com/google/syzkaller/pkg/subsystem"
+import (
+ "fmt"
+
+ "github.com/google/syzkaller/pkg/subsystem"
+)
// parentTransformations applies all subsystem list transformations that have been implemented.
func parentTransformations(matrix *CoincidenceMatrix,
- list []*subsystem.Subsystem) ([]*subsystem.Subsystem, error) {
+ list []*subsystem.Subsystem) ([]*subsystem.Subsystem, parentInfo, error) {
list = dropSmallSubsystems(matrix, list)
list = dropDuplicateSubsystems(matrix, list)
- err := setParents(matrix, list)
+ info, err := setParents(matrix, list)
if err != nil {
- return nil, err
+ return nil, nil, err
+ }
+ return list, info, nil
+}
+
+type parentInfo map[*subsystem.Subsystem]map[*subsystem.Subsystem]string
+
+func (pi parentInfo) Save(parent, child *subsystem.Subsystem, info string) {
+ if pi[parent] == nil {
+ pi[parent] = map[*subsystem.Subsystem]string{}
}
- return list, nil
+ pi[parent][child] = info
}
// setParents attempts to determine the parent-child relations among the extracted subsystems.
// 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 *CoincidenceMatrix, list []*subsystem.Subsystem) error {
+func setParents(matrix *CoincidenceMatrix, list []*subsystem.Subsystem) (parentInfo, error) {
// Some subsystems might have already been dropeed.
inInput := map[*subsystem.Subsystem]bool{}
for _, item := range list {
inInput[item] = true
}
- matrix.NonEmptyPairs(func(a, b *subsystem.Subsystem, count int) {
+ info := parentInfo{}
+ matrix.NonEmptyPairs(func(a, b *subsystem.Subsystem, common int) {
if !inInput[a] || !inInput[b] {
return
}
+ childFiles := matrix.Count(a)
+ parentFiles := matrix.Count(b)
// Demand that >= 50% paths are related.
- if 2*count/matrix.Count(a) >= 1 && matrix.Count(a) < matrix.Count(b) {
+ if 2*common/childFiles >= 1 && childFiles < parentFiles {
a.Parents = append(a.Parents, b)
+ info.Save(b, a,
+ fmt.Sprintf("Auto-inferred: %d common files among %d/%d.",
+ common, childFiles, parentFiles))
a.ReachableParents() // make sure we haven't created a loop
}
})
transitiveReduction(list)
- return nil
+ return info, nil
}
// dropSmallSubsystems removes subsystems for which we have found only a few matches in the filesystem tree.
diff --git a/pkg/subsystem/linux/parents_test.go b/pkg/subsystem/linux/parents_test.go
index 444e4ff33..0881daeae 100644
--- a/pkg/subsystem/linux/parents_test.go
+++ b/pkg/subsystem/linux/parents_test.go
@@ -113,13 +113,13 @@ func TestSetParents(t *testing.T) {
"drivers/android/binder.c": {},
}
- matrix, err := BuildCoincidenceMatrix(tree,
+ matrix, _, err := BuildCoincidenceMatrix(tree,
[]*subsystem.Subsystem{kernel, net, wireless, drivers}, nil)
assert.NoError(t, err)
// Calculate parents.
- err = setParents(matrix, []*subsystem.Subsystem{kernel, net, wireless, drivers})
+ _, err = setParents(matrix, []*subsystem.Subsystem{kernel, net, wireless, drivers})
if err != nil {
t.Fatal(err)
}
diff --git a/pkg/subsystem/linux/path_coincidence.go b/pkg/subsystem/linux/path_coincidence.go
index 44182bd6a..8dab14f28 100644
--- a/pkg/subsystem/linux/path_coincidence.go
+++ b/pkg/subsystem/linux/path_coincidence.go
@@ -7,22 +7,27 @@ import (
"io/fs"
"regexp"
"runtime"
+ "sort"
"sync"
"github.com/google/syzkaller/pkg/subsystem"
)
func BuildCoincidenceMatrix(root fs.FS, list []*subsystem.Subsystem,
- excludeRe *regexp.Regexp) (*CoincidenceMatrix, error) {
+ excludeRe *regexp.Regexp) (*CoincidenceMatrix, *matrixDebugInfo, error) {
// Create a matcher.
matcher := subsystem.MakePathMatcher(list)
chPaths, chResult := extractSubsystems(matcher)
// The final consumer goroutine.
cm := MakeCoincidenceMatrix()
ready := make(chan struct{})
+ debug := &matrixDebugInfo{files: map[*subsystem.Subsystem][]string{}}
go func() {
- for items := range chResult {
- cm.Record(items...)
+ for item := range chResult {
+ cm.Record(item.list...)
+ for _, entity := range item.list {
+ debug.files[entity] = append(debug.files[entity], item.path)
+ }
}
ready <- struct{}{}
}()
@@ -40,23 +45,38 @@ func BuildCoincidenceMatrix(root fs.FS, list []*subsystem.Subsystem,
})
close(chPaths)
<-ready
- return cm, err
+ for _, list := range debug.files {
+ sort.Strings(list)
+ }
+ return cm, debug, err
+}
+
+type matrixDebugInfo struct {
+ files map[*subsystem.Subsystem][]string
}
var (
includePathRe = regexp.MustCompile(`(?:/|\.(?:c|h|S))$`)
)
-func extractSubsystems(matcher *subsystem.PathMatcher) (chan<- string, <-chan []*subsystem.Subsystem) {
+type extracted struct {
+ path string
+ list []*subsystem.Subsystem
+}
+
+func extractSubsystems(matcher *subsystem.PathMatcher) (chan<- string, <-chan extracted) {
procs := runtime.NumCPU()
- paths, output := make(chan string, procs), make(chan []*subsystem.Subsystem, procs)
+ paths, output := make(chan string, procs), make(chan extracted, 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)
+ output <- extracted{
+ path: path,
+ list: matcher.Match(path),
+ }
}
}()
}
diff --git a/pkg/subsystem/linux/path_coincidence_test.go b/pkg/subsystem/linux/path_coincidence_test.go
index ac32dcd31..cc6f81d6a 100644
--- a/pkg/subsystem/linux/path_coincidence_test.go
+++ b/pkg/subsystem/linux/path_coincidence_test.go
@@ -33,7 +33,7 @@ func TestBuildCoincidenceMatrix(t *testing.T) {
"fs/fat/file.c": {},
"net/socket.c": {},
}
- matrix, err := BuildCoincidenceMatrix(fs, []*subsystem.Subsystem{vfs, ntfs, ext4, kernel}, nil)
+ matrix, _, err := BuildCoincidenceMatrix(fs, []*subsystem.Subsystem{vfs, ntfs, ext4, kernel}, nil)
assert.NoError(t, err)
// Test total counts.
diff --git a/pkg/subsystem/linux/subsystems.go b/pkg/subsystem/linux/subsystems.go
index ae2c61556..d63ad879e 100644
--- a/pkg/subsystem/linux/subsystems.go
+++ b/pkg/subsystem/linux/subsystems.go
@@ -13,15 +13,16 @@ import (
"github.com/google/syzkaller/pkg/subsystem"
)
-func ListFromRepo(repo string) ([]*subsystem.Subsystem, error) {
+func ListFromRepo(repo string) ([]*subsystem.Subsystem, *subsystem.DebugInfo, error) {
return listFromRepoInner(os.DirFS(repo), linuxSubsystemRules)
}
// listFromRepoInner allows for better testing.
-func listFromRepoInner(root fs.FS, rules *customRules) ([]*subsystem.Subsystem, error) {
+func listFromRepoInner(root fs.FS, rules *customRules) ([]*subsystem.Subsystem,
+ *subsystem.DebugInfo, error) {
records, err := getMaintainers(root)
if err != nil {
- return nil, err
+ return nil, nil, err
}
removeMatchingPatterns(records, dropPatterns)
ctx := &linuxCtx{
@@ -31,22 +32,22 @@ func listFromRepoInner(root fs.FS, rules *customRules) ([]*subsystem.Subsystem,
}
extraList, err := ctx.groupByRules()
if err != nil {
- return nil, err
+ return nil, nil, err
}
list := append(ctx.groupByList(), extraList...)
- matrix, err := BuildCoincidenceMatrix(root, list, dropPatterns)
+ matrix, matrixDebug, err := BuildCoincidenceMatrix(root, list, dropPatterns)
if err != nil {
- return nil, err
+ return nil, nil, err
}
- list, err = parentTransformations(matrix, list)
+ list, parentDebug, err := parentTransformations(matrix, list)
if err != nil {
- return nil, err
+ return nil, nil, err
}
if err := setSubsystemNames(list); err != nil {
- return nil, fmt.Errorf("failed to set names: %w", err)
+ return nil, nil, fmt.Errorf("failed to set names: %w", err)
}
if err := ctx.applyExtraRules(list); err != nil {
- return nil, fmt.Errorf("failed to apply extra rules: %w", err)
+ return nil, nil, fmt.Errorf("failed to apply extra rules: %w", err)
}
// Sort subsystems by name to keep output consistent.
@@ -61,7 +62,10 @@ func listFromRepoInner(root fs.FS, rules *customRules) ([]*subsystem.Subsystem,
return a.ExcludeRegexp < b.ExcludeRegexp
})
}
- return list, nil
+ return list, &subsystem.DebugInfo{
+ ParentChildComment: parentDebug,
+ FileLists: matrixDebug.files,
+ }, nil
}
type linuxCtx struct {
diff --git a/pkg/subsystem/linux/subsystems_test.go b/pkg/subsystem/linux/subsystems_test.go
index a411155ad..44cf5ac21 100644
--- a/pkg/subsystem/linux/subsystems_test.go
+++ b/pkg/subsystem/linux/subsystems_test.go
@@ -13,7 +13,7 @@ import (
)
func TestGroupLinuxSubsystems(t *testing.T) {
- subsystems, err := listFromRepoInner(
+ subsystems, _, err := listFromRepoInner(
prepareTestLinuxRepo(t, []byte(testMaintainers)),
nil)
if err != nil {
@@ -57,7 +57,7 @@ func TestGroupLinuxSubsystems(t *testing.T) {
}
func TestCustomCallRules(t *testing.T) {
- subsystems, err := listFromRepoInner(
+ subsystems, _, err := listFromRepoInner(
prepareTestLinuxRepo(t, []byte(testMaintainers)),
testRules,
)
@@ -103,7 +103,7 @@ func TestLinuxSubsystemPaths(t *testing.T) {
// For the list of subsystems, see TestLinuxSubsystemsList.
// Here we rely on the same ones.
repo := prepareTestLinuxRepo(t, []byte(testMaintainers))
- subsystems, err := listFromRepoInner(repo, nil)
+ subsystems, _, err := listFromRepoInner(repo, nil)
if err != nil {
t.Fatal(err)
}
@@ -164,7 +164,7 @@ func TestLinuxSubsystemParents(t *testing.T) {
// For the list of subsystems, see TestLinuxSubsystemsList.
// Here we rely on the same ones.
repo := prepareTestLinuxRepo(t, []byte(testMaintainers))
- subsystems, err := listFromRepoInner(repo, nil)
+ subsystems, _, err := listFromRepoInner(repo, nil)
if err != nil {
t.Fatal(err)
}
@@ -177,7 +177,7 @@ func TestLinuxSubsystemParents(t *testing.T) {
})
// Now check that our custom parent rules work.
- subsystems2, err := listFromRepoInner(repo, &customRules{
+ subsystems2, _, err := listFromRepoInner(repo, &customRules{
addParents: map[string][]string{
// Just for the sake of testing.
"fs": {"mm"},
generated by ggit (джигит) mrf-deployment (git 2.46.0) at 2026-03-11 17:41:17 +0000