pkg/subsystem: restructure the package

Remove the entity and match subpackages.

Regenerate the linux.go file.

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