3 files changed, 96 insertions, 0 deletions
diff --git a/pkg/declextract/declextract.go b/pkg/declextract/declextract.go
index 30caeaa2d..4edb6c867 100644
--- a/pkg/declextract/declextract.go
+++ b/pkg/declextract/declextract.go
@@ -7,6 +7,7 @@ import (
 	"bytes"
 	"errors"
 	"fmt"
+	"os"
 	"slices"
 	"strings"
 
@@ -19,8 +20,10 @@ func Run(out *Output, probe *ifaceprobe.Info, syscallRename map[string][]string)
 		probe:         probe,
 		syscallRename: syscallRename,
 		structs:       make(map[string]*Struct),
+		funcs:         make(map[string]*Function),
 		uniqualizer:   make(map[string]int),
 	}
+	ctx.processFunctions()
 	ctx.processIncludes()
 	ctx.processEnums()
 	ctx.processStructs()
@@ -37,6 +40,7 @@ type context struct {
 	probe         *ifaceprobe.Info
 	syscallRename map[string][]string // syscall function -> syscall names
 	structs       map[string]*Struct
+	funcs         map[string]*Function
 	uniqualizer   map[string]int
 	interfaces    []*Interface
 	descriptions  *bytes.Buffer
@@ -47,6 +51,10 @@ func (ctx *context) error(msg string, args ...any) {
 	ctx.errs = append(ctx.errs, fmt.Errorf(msg, args...))
 }
 
+func (ctx *context) warn(msg string, args ...any) {
+	fmt.Fprintf(os.Stderr, msg+"\n", args...)
+}
+
 func (ctx *context) processIncludes() {
 	// These additional includes must be at the top, because other kernel headers
 	// are broken and won't compile without these additional ones included first.
diff --git a/pkg/declextract/entity.go b/pkg/declextract/entity.go
index 7cdd5a73a..ba45cc51c 100644
--- a/pkg/declextract/entity.go
+++ b/pkg/declextract/entity.go
@@ -11,6 +11,7 @@ import (
 )
 
 type Output struct {
+	Functions       []*Function      `json:"functions,omitempty"`
 	Includes        []string         `json:"includes,omitempty"`
 	Defines         []*Define        `json:"defines,omitempty"`
 	Enums           []*Enum          `json:"enums,omitempty"`
@@ -22,6 +23,17 @@ type Output struct {
 	NetlinkPolicies []*NetlinkPolicy `json:"netlink_policies,omitempty"`
 }
 
+type Function struct {
+	Name     string   `json:"name,omitempty"`
+	File     string   `json:"file,omitempty"`
+	IsStatic bool     `json:"is_static,omitempty"`
+	LOC      int      `json:"loc,omitempty"`
+	Calls    []string `json:"calls,omitempty"`
+
+	callers int
+	calls   []*Function
+}
+
 type Define struct {
 	Name  string `json:"name,omitempty"`
 	Value string `json:"value,omitempty"`
@@ -147,6 +159,7 @@ type BufferType struct {
 }
 
 func (out *Output) Merge(other *Output) {
+	out.Functions = append(out.Functions, other.Functions...)
 	out.Includes = append(out.Includes, other.Includes...)
 	out.Defines = append(out.Defines, other.Defines...)
 	out.Enums = append(out.Enums, other.Enums...)
@@ -159,6 +172,7 @@ func (out *Output) Merge(other *Output) {
 }
 
 func (out *Output) SortAndDedup() {
+	out.Functions = sortAndDedupSlice(out.Functions)
 	out.Includes = sortAndDedupSlice(out.Includes)
 	out.Defines = sortAndDedupSlice(out.Defines)
 	out.Enums = sortAndDedupSlice(out.Enums)
@@ -173,6 +187,9 @@ func (out *Output) SortAndDedup() {
 // SetSoureFile attaches the source file to the entities that need it.
 // The clang tool could do it, but it looks easier to do it here.
 func (out *Output) SetSourceFile(file string, updatePath func(string) string) {
+	for _, fn := range out.Functions {
+		fn.File = updatePath(fn.File)
+	}
 	for i, inc := range out.Includes {
 		out.Includes[i] = updatePath(inc)
 	}
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]
+}