pkg/subsystem: export debug info

Make it possible to print more debugging information when (re)generating
a subsystem list.

Include parent inference details to the source code itself and add a
-debug flag to list the source files assigned to each subsystem.

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())