aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-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
-rw-r--r--tools/syz-query-subsystems/generator.go31
-rw-r--r--tools/syz-query-subsystems/query_subsystems.go19
9 files changed, 125 insertions, 43 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"},
diff --git a/tools/syz-query-subsystems/generator.go b/tools/syz-query-subsystems/generator.go
index a7db17d3f..3e2251747 100644
--- a/tools/syz-query-subsystems/generator.go
+++ b/tools/syz-query-subsystems/generator.go
@@ -8,6 +8,7 @@ import (
"fmt"
"go/format"
"regexp"
+ "slices"
"sort"
"strings"
"text/template"
@@ -18,7 +19,8 @@ import (
"github.com/google/syzkaller/pkg/vcs"
)
-func generateSubsystemsFile(name string, list []*subsystem.Subsystem, commit *vcs.Commit) ([]byte, error) {
+func generateSubsystemsFile(name string, list []*subsystem.Subsystem, commit *vcs.Commit,
+ debugInfo *subsystem.DebugInfo) ([]byte, error) {
// Set names first -- we'll need them for filling in the Parents array.
objToName := map[*subsystem.Subsystem]string{}
for _, entry := range list {
@@ -41,11 +43,16 @@ func generateSubsystemsFile(name string, list []*subsystem.Subsystem, commit *vc
// The serializer does not understand parent references and just prints all the
// nested structures.
// Therefore we call it separately for the fields it can understand.
- parents := []string{}
+ parents := []parentInfo{}
for _, p := range entry.Parents {
- parents = append(parents, objToName[p])
+ parents = append(parents, parentInfo{
+ Name: objToName[p],
+ Comment: debugInfo.ParentChildComment[p][entry],
+ })
}
- sort.Strings(parents)
+ slices.SortFunc(parents, func(a, b parentInfo) int {
+ return strings.Compare(a.Name, b.Name)
+ })
subsystem := &templateSubsystem{
VarName: varName,
Name: serializer.WriteString(entry.Name),
@@ -121,11 +128,16 @@ type templateSubsystem struct {
PathRules string
Lists string
Maintainers string
- Parents []string
+ Parents []parentInfo
NoReminders bool
NoIndirectCc bool
}
+type parentInfo struct {
+ Name string
+ Comment string
+}
+
type templateVars struct {
Name string
Version int
@@ -171,7 +183,14 @@ var {{range $i, $item := .List}}
Maintainers: {{.Maintainers}},
{{- end}}
{{- if .Parents}}
- Parents: []*Subsystem{ {{range .Parents}} &{{.}}, {{end}} },
+ Parents: []*Subsystem{
+ {{- range .Parents}}
+ {{- if .Comment}}
+ // {{.Comment}}
+ {{- end}}
+ &{{.Name}},
+ {{end -}}
+},
{{- end}}
PathRules: {{.PathRules}},
{{- if .NoReminders}}
diff --git a/tools/syz-query-subsystems/query_subsystems.go b/tools/syz-query-subsystems/query_subsystems.go
index 8f0fbae76..74da8ee8d 100644
--- a/tools/syz-query-subsystems/query_subsystems.go
+++ b/tools/syz-query-subsystems/query_subsystems.go
@@ -28,6 +28,7 @@ var (
flagName = flag.String("name", "", "the name under which the list should be saved")
flagFilter = flag.String("filter", "", "comma-separated list of subsystems to keep")
flagEmails = flag.Bool("emails", true, "save lists and maintainer fields")
+ flagDebug = flag.Bool("debug", false, "print the debugging information")
)
var nameRe = regexp.MustCompile(`^[a-z]\w*$`)
@@ -48,10 +49,11 @@ func main() {
tool.Failf("the name is not acceptable")
}
// Query the subsystems.
- list, err := linux.ListFromRepo(*flagKernelRepo)
+ list, debugInfo, err := linux.ListFromRepo(*flagKernelRepo)
if err != nil {
tool.Failf("failed to query subsystems: %v", err)
}
+ printDebugInfo(debugInfo)
list = postProcessList(list)
// Save the list.
folder := filepath.Join(*flagSyzkallerRepo, "pkg", "subsystem", "lists")
@@ -62,7 +64,7 @@ func main() {
if err != nil {
tool.Failf("failed to fetch commit info: %v", err)
}
- code, err := generateSubsystemsFile(*flagName, list, commitInfo)
+ code, err := generateSubsystemsFile(*flagName, list, commitInfo, debugInfo)
if err != nil {
tool.Failf("failed to generate code: %s", err)
}
@@ -72,6 +74,19 @@ func main() {
}
}
+func printDebugInfo(info *subsystem.DebugInfo) {
+ if !*flagDebug {
+ return
+ }
+ for item, list := range info.FileLists {
+ fmt.Printf("****\n")
+ fmt.Printf("Subsystem %q (%d paths)\n", item.Name, len(list))
+ for _, path := range list {
+ fmt.Printf("%s\n", path)
+ }
+ }
+}
+
func postProcessList(list []*subsystem.Subsystem) []*subsystem.Subsystem {
if *flagFilter != "" {
list = subsystem.FilterList(list, prepareFilter())
generated by ggit (джигит) mrf-deployment (git 2.46.0) at 2026-03-11 16:00:54 +0000