tools/syz-declextract: extract info about all functions

Extract info about all functions, and compute total LOC for each interface.
For now only static calls are considered, this doesn't handle indirect calls yet.
This is just a groundwork for more complex callgraph/dataflow analysis.

1 files changed, 71 insertions, 0 deletions

diff --git a/pkg/declextract/interface.go b/pkg/declextract/interface.go
index dfb223d16..7abce44fb 100644
--- a/pkg/declextract/interface.go
+++ b/pkg/declextract/interface.go
@@ -5,6 +5,7 @@ package declextract
 
 import (
 	"slices"
+	"strings"
 )
 
 type Interface struct {
@@ -17,6 +18,7 @@ type Interface struct {
 	Subsystems         []string
 	ManualDescriptions bool
 	AutoDescriptions   bool
+	ReachableLOC       int
 }
 
 const (
@@ -36,6 +38,7 @@ func (ctx *context) noteInterface(iface *Interface) {
 
 func (ctx *context) finishInterfaces() {
 	for _, iface := range ctx.interfaces {
+		iface.ReachableLOC = ctx.reachableLOC(iface.Func, iface.Files[0])
 		slices.Sort(iface.Files)
 		iface.Files = slices.Compact(iface.Files)
 		if iface.Access == "" {
@@ -44,3 +47,71 @@ func (ctx *context) finishInterfaces() {
 	}
 	ctx.interfaces = sortAndDedupSlice(ctx.interfaces)
 }
+
+func (ctx *context) processFunctions() {
+	for _, fn := range ctx.Functions {
+		ctx.funcs[fn.File+fn.Name] = fn
+		// Strictly speaking there may be several different static functions in different headers,
+		// but we ignore such possibility for now.
+		if !fn.IsStatic || strings.HasSuffix(fn.File, "*.h") {
+			ctx.funcs[fn.Name] = fn
+		}
+	}
+	nocallers := 0
+	for _, fn := range ctx.Functions {
+		for _, callee := range fn.Calls {
+			called := ctx.findFunc(callee, fn.File)
+			if called == nil || called == fn {
+				continue
+			}
+			fn.calls = append(fn.calls, called)
+			called.callers++
+		}
+		fn.Calls = nil
+		if len(fn.calls) == 0 {
+			nocallers++
+		}
+	}
+}
+
+func (ctx *context) reachableLOC(name, file string) int {
+	fn := ctx.findFunc(name, file)
+	if fn == nil {
+		ctx.warn("can't find function %v in called in %v", name, file)
+		return 0
+	}
+	reachable := make(map[*Function]bool)
+	ctx.collectRachable(fn, reachable)
+	loc := 0
+	for fn := range reachable {
+		loc += fn.LOC
+	}
+	return loc
+}
+
+func (ctx *context) collectRachable(fn *Function, reachable map[*Function]bool) {
+	// Ignore very common functions when computing reachability for complexity analysis.
+	// Counting kmalloc/printk against each caller is not useful (they have ~10K calls).
+	// There are also subsystem common functions (e.g. functions called in some parts of fs/net).
+	// The current threshold is somewhat arbitrary and is based on the number of callers in syzbot kernel:
+	// 6 callers - 2272 functions
+	// 5 callers - 3468 functions
+	// 4 callers - 6295 functions
+	// 3 callers - 16527 functions
+	const commonFuncThreshold = 5
+
+	reachable[fn] = true
+	for _, callee := range fn.calls {
+		if reachable[callee] || callee.callers >= commonFuncThreshold {
+			continue
+		}
+		ctx.collectRachable(callee, reachable)
+	}
+}
+
+func (ctx *context) findFunc(name, file string) *Function {
+	if fn := ctx.funcs[file+name]; fn != nil {
+		return fn
+	}
+	return ctx.funcs[name]
+}