pkg/subsystem/match: add coincidence matrix

We'll need it for determining overlapping subsystems and for the
inferece of parent-child relationships.

Add the code to calculate a coincidence matrix from a filesystem.

4 files changed, 212 insertions, 0 deletions

diff --git a/pkg/subsystem/match/coincidence.go b/pkg/subsystem/match/coincidence.go
new file mode 100644
index 000000000..45bd98884
--- /dev/null
+++ b/pkg/subsystem/match/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 match
+
+import "github.com/google/syzkaller/pkg/subsystem/entity"
+
+// 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 entity.Subsystem, so its interface is tailored to it.
+type CoincidenceMatrix struct {
+	matrix map[*entity.Subsystem]map[*entity.Subsystem]int
+}
+
+func MakeCoincidenceMatrix() *CoincidenceMatrix {
+	return &CoincidenceMatrix{
+		matrix: make(map[*entity.Subsystem]map[*entity.Subsystem]int),
+	}
+}
+
+func (cm *CoincidenceMatrix) Record(items ...*entity.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 *entity.Subsystem) int {
+	return cm.Get(a, a)
+}
+
+func (cm *CoincidenceMatrix) Get(a, b *entity.Subsystem) int {
+	return cm.matrix[a][b]
+}
+
+func (cm *CoincidenceMatrix) NonEmptyPairs(cb func(a, b *entity.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 *entity.Subsystem) {
+	subMatrix, ok := cm.matrix[a]
+	if !ok {
+		subMatrix = make(map[*entity.Subsystem]int)
+		cm.matrix[a] = subMatrix
+	}
+	subMatrix[b]++
+}
diff --git a/pkg/subsystem/match/coincidence_test.go b/pkg/subsystem/match/coincidence_test.go
new file mode 100644
index 000000000..15f0dd241
--- /dev/null
+++ b/pkg/subsystem/match/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 match
+
+import (
+	"testing"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+	"github.com/stretchr/testify/assert"
+)
+
+func TestCoincidenceMatrix(t *testing.T) {
+	cm := MakeCoincidenceMatrix()
+	a, b, c := &entity.Subsystem{}, &entity.Subsystem{}, &entity.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 *entity.Subsystem
+		b *entity.Subsystem
+	}
+	expected := []pair{{a, b}, {b, a}, {b, c}, {c, b}}
+	got := []pair{}
+	cm.NonEmptyPairs(func(a, b *entity.Subsystem, _ int) {
+		got = append(got, pair{a, b})
+	})
+	assert.ElementsMatch(t, expected, got)
+}
diff --git a/pkg/subsystem/match/path_coincidence.go b/pkg/subsystem/match/path_coincidence.go
new file mode 100644
index 000000000..944546490
--- /dev/null
+++ b/pkg/subsystem/match/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 match
+
+import (
+	"io/fs"
+	"regexp"
+	"runtime"
+	"sync"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+)
+
+func BuildCoincidenceMatrix(root fs.FS, list []*entity.Subsystem,
+	excludeRe *regexp.Regexp) (*CoincidenceMatrix, error) {
+	// Create a matcher.
+	matcher := 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 *PathMatcher) (chan<- string, <-chan []*entity.Subsystem) {
+	procs := runtime.NumCPU()
+	paths, output := make(chan string, procs), make(chan []*entity.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/match/path_coincidence_test.go b/pkg/subsystem/match/path_coincidence_test.go
new file mode 100644
index 000000000..2d1969d7f
--- /dev/null
+++ b/pkg/subsystem/match/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 match
+
+import (
+	"testing"
+	"testing/fstest"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+	"github.com/stretchr/testify/assert"
+)
+
+func TestBuildCoincidenceMatrix(t *testing.T) {
+	vfs := &entity.Subsystem{PathRules: []entity.PathRule{
+		{IncludeRegexp: `^fs/`},
+	}}
+	ext4 := &entity.Subsystem{PathRules: []entity.PathRule{
+		{IncludeRegexp: `^fs/ext4/`},
+	}}
+	ntfs := &entity.Subsystem{PathRules: []entity.PathRule{
+		{IncludeRegexp: `^fs/ntfs/`},
+	}}
+	kernel := &entity.Subsystem{PathRules: []entity.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, []*entity.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))
+}