diff options
21 files changed, 398 insertions, 12 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] +} diff --git a/tools/syz-declextract/clangtool/declextract.cpp b/tools/syz-declextract/clangtool/declextract.cpp index 68ca91d32..d2b2133b9 100644 --- a/tools/syz-declextract/clangtool/declextract.cpp +++ b/tools/syz-declextract/clangtool/declextract.cpp @@ -52,6 +52,8 @@ using MacroMap = std::unordered_map<std::string, MacroDef>; class Extractor : public MatchFinder, public tooling::SourceFileCallbacks { public: Extractor() { + match(&Extractor::matchFunctionDef, functionDecl(isDefinition()).bind("function")); + match(&Extractor::matchSyscall, functionDecl(isExpandedFromMacro("SYSCALL_DEFINEx"), matchesName("__do_sys_.*")).bind("syscall")); @@ -99,6 +101,7 @@ private: std::unordered_map<std::string, bool> StructDedup; std::unordered_map<std::string, int> FileOpsDedup; + void matchFunctionDef(); void matchSyscall(); void matchIouring(); void matchNetlinkPolicy(); @@ -549,6 +552,40 @@ void Extractor::matchNetlinkFamily() { std::string Extractor::policyName(const ValueDecl* Decl) { return Decl->getNameAsString() + "_" + getDeclFileID(Decl); } +void Extractor::matchFunctionDef() { + const auto* Func = getResult<FunctionDecl>("function"); + const auto Range = Func->getSourceRange(); + const std::string& SourceFile = + std::filesystem::relative(SourceManager->getFilename(SourceManager->getExpansionLoc(Range.getBegin())).str()); + const int LOC = std::max<int>(0, SourceManager->getExpansionLineNumber(Range.getEnd()) - + SourceManager->getExpansionLineNumber(Range.getBegin()) - 1); + std::vector<std::string> Callees; + std::unordered_set<std::string> CalleesDedup; + const auto& Calls = findAllMatches<CallExpr>(Func->getBody(), stmt(forEachDescendant(callExpr().bind("res")))); + for (auto* Call : Calls) { + if (auto* CalleeDecl = Call->getDirectCallee()) { + // Builtins are not interesting and won't have a body. + if (CalleeDecl->getBuiltinID() != Builtin::ID::NotBuiltin) + continue; + const std::string& Callee = CalleeDecl->getNameAsString(); + // There are too many of these and they should only be called at runtime in broken builds. + if (Callee.rfind("__compiletime_assert", 0) == 0 || Callee == "____wrong_branch_error" || + Callee == "__bad_size_call_parameter") + continue; + if (!CalleesDedup.insert(Callee).second) + continue; + Callees.push_back(Callee); + } + } + Output.emit(Function{ + .Name = Func->getNameAsString(), + .File = SourceFile, + .IsStatic = Func->isStatic(), + .LOC = LOC, + .Calls = std::move(Callees), + }); +} + void Extractor::matchSyscall() { const auto* Func = getResult<FunctionDecl>("syscall"); std::vector<Field> Args; diff --git a/tools/syz-declextract/clangtool/output.h b/tools/syz-declextract/clangtool/output.h index c8e9741fd..d09881aee 100644 --- a/tools/syz-declextract/clangtool/output.h +++ b/tools/syz-declextract/clangtool/output.h @@ -108,6 +108,14 @@ struct FileOps { std::vector<IoctlCmd> IoctlCmds; }; +struct Function { + std::string Name; + std::string File; + bool IsStatic = false; + int LOC = 0; + std::vector<std::string> Calls; +}; + struct Syscall { std::string Func; std::vector<Field> Args; @@ -237,6 +245,15 @@ inline void print(JSONPrinter& Printer, const FileOps& V) { Printer.Field("ioctl_cmds", V.IoctlCmds, true); } +inline void print(JSONPrinter& Printer, const Function& V) { + JSONPrinter::Scope Scope(Printer); + Printer.Field("name", V.Name); + Printer.Field("file", V.File); + Printer.Field("is_static", V.IsStatic); + Printer.Field("loc", V.LOC); + Printer.Field("calls", V.Calls, true); +} + inline void print(JSONPrinter& Printer, const Syscall& V) { JSONPrinter::Scope Scope(Printer); Printer.Field("func", V.Func); @@ -295,6 +312,7 @@ public: Includes.push_back(Inc.Filename); } + void emit(Function&& V) { Functions.push_back(std::move(V)); } void emit(Define&& V) { Defines.push_back(std::move(V)); } void emit(Struct&& V) { Structs.push_back(std::move(V)); } void emit(Enum&& V) { Enums.push_back(std::move(V)); } @@ -306,6 +324,7 @@ public: void print() const { JSONPrinter Printer; + Printer.Field("functions", Functions); Printer.Field("includes", Includes); Printer.Field("defines", Defines); Printer.Field("enums", Enums); @@ -318,6 +337,7 @@ public: } private: + std::vector<Function> Functions; std::vector<std::string> Includes; std::unordered_set<std::string> IncludesDedup; std::vector<Define> Defines; diff --git a/tools/syz-declextract/declextract.go b/tools/syz-declextract/declextract.go index 63e6089ac..62008d8ad 100644 --- a/tools/syz-declextract/declextract.go +++ b/tools/syz-declextract/declextract.go @@ -181,8 +181,8 @@ func errorHandler() (func(pos ast.Pos, msg string), *bytes.Buffer) { func serialize(interfaces []*declextract.Interface) []byte { w := new(bytes.Buffer) for _, iface := range interfaces { - fmt.Fprintf(w, "%v\t%v\tfunc:%v\taccess:%v\tmanual_desc:%v\tauto_desc:%v", - iface.Type, iface.Name, iface.Func, iface.Access, + fmt.Fprintf(w, "%v\t%v\tfunc:%v\tloc:%v\taccess:%v\tmanual_desc:%v\tauto_desc:%v", + iface.Type, iface.Name, iface.Func, iface.ReachableLOC, iface.Access, iface.ManualDescriptions, iface.AutoDescriptions) for _, file := range iface.Files { fmt.Fprintf(w, "\tfile:%v", file) diff --git a/tools/syz-declextract/testdata/arch/x86/syscalls.tbl b/tools/syz-declextract/testdata/arch/x86/syscalls.tbl index 19309c4ef..d79726fdf 100644 --- a/tools/syz-declextract/testdata/arch/x86/syscalls.tbl +++ b/tools/syz-declextract/testdata/arch/x86/syscalls.tbl @@ -4,3 +4,4 @@ 1 64 open sys_open 2 64 chmod sys_chmod 3 64 types_syscall sys_types_syscall +4 64 functions sys_functions diff --git a/tools/syz-declextract/testdata/file_operations.c.json b/tools/syz-declextract/testdata/file_operations.c.json index e5ddad2b2..94ad7bef5 100644 --- a/tools/syz-declextract/testdata/file_operations.c.json +++ b/tools/syz-declextract/testdata/file_operations.c.json @@ -1,4 +1,52 @@ { + "functions": [ + { + "name": "foo_ioctl", + "file": "file_operations.c", + "is_static": true, + "loc": 7 + }, + { + "name": "foo_mmap", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "foo_open", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "foo_read", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "foo_write", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "proc_ioctl", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "proc_open", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "proc_read", + "file": "file_operations.c", + "is_static": true + }, + { + "name": "proc_write", + "file": "file_operations.c", + "is_static": true + } + ], "includes": [ "include/uapi/file_operations.h" ], diff --git a/tools/syz-declextract/testdata/functions.c b/tools/syz-declextract/testdata/functions.c new file mode 100644 index 000000000..675489432 --- /dev/null +++ b/tools/syz-declextract/testdata/functions.c @@ -0,0 +1,25 @@ +// Copyright 2024 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. + +#include "include/types.h" +#include "include/syscall.h" + +static void func_foo() { +} + +static void func_bar() { + func_foo(); +} + +void func_baz(int f) { + func_foo(); + if (f) + func_bar(); + if (__builtin_constant_p(f)) + func_bar(); +} + +SYSCALL_DEFINE1(functions) { + func_baz(1); + return 0; +} diff --git a/tools/syz-declextract/testdata/functions.c.info b/tools/syz-declextract/testdata/functions.c.info new file mode 100644 index 000000000..0101daf12 --- /dev/null +++ b/tools/syz-declextract/testdata/functions.c.info @@ -0,0 +1 @@ +SYSCALL functions func:__do_sys_functions loc:8 access:unknown manual_desc:false auto_desc:true file:functions.c subsystem:kernel diff --git a/tools/syz-declextract/testdata/functions.c.json b/tools/syz-declextract/testdata/functions.c.json new file mode 100644 index 000000000..8a1fd4ee1 --- /dev/null +++ b/tools/syz-declextract/testdata/functions.c.json @@ -0,0 +1,52 @@ +{ + "functions": [ + { + "name": "__do_sys_functions", + "file": "functions.c", + "loc": 2, + "calls": [ + "func_baz" + ] + }, + { + "name": "atomic_load32", + "file": "include/types.h", + "is_static": true, + "loc": 1 + }, + { + "name": "atomic_load64", + "file": "include/types.h", + "loc": 1 + }, + { + "name": "func_bar", + "file": "functions.c", + "is_static": true, + "loc": 1, + "calls": [ + "func_foo" + ] + }, + { + "name": "func_baz", + "file": "functions.c", + "loc": 5, + "calls": [ + "func_foo", + "func_bar" + ] + }, + { + "name": "func_foo", + "file": "functions.c", + "is_static": true + } + ], + "syscalls": [ + { + "func": "__do_sys_functions", + "source_file": "functions.c" + } + ] +}
\ No newline at end of file diff --git a/tools/syz-declextract/testdata/functions.c.txt b/tools/syz-declextract/testdata/functions.c.txt new file mode 100644 index 000000000..998d5fb72 --- /dev/null +++ b/tools/syz-declextract/testdata/functions.c.txt @@ -0,0 +1,11 @@ +# Code generated by syz-declextract. DO NOT EDIT. + +meta automatic + +type auto_todo intptr + +include <vdso/bits.h> +include <linux/types.h> +include <net/netlink.h> + +functions$auto() diff --git a/tools/syz-declextract/testdata/include/types.h b/tools/syz-declextract/testdata/include/types.h index 5b1d6303c..2e6a7d853 100644 --- a/tools/syz-declextract/testdata/include/types.h +++ b/tools/syz-declextract/testdata/include/types.h @@ -11,3 +11,11 @@ typedef unsigned int u32; typedef unsigned long long u64; #define ARRAY_SIZE(x) (sizeof(x)/sizeof((x)[0])) + +static inline u32 atomic_load32(u32* p) { + return __atomic_load_n(p, __ATOMIC_RELAXED); +} + +inline u64 atomic_load64(u64* p) { + return __atomic_load_n(p, __ATOMIC_RELAXED); +} diff --git a/tools/syz-declextract/testdata/io_uring.c.info b/tools/syz-declextract/testdata/io_uring.c.info index 6757eca74..89ede5685 100644 --- a/tools/syz-declextract/testdata/io_uring.c.info +++ b/tools/syz-declextract/testdata/io_uring.c.info @@ -1,3 +1,3 @@ -IOURING IORING_OP_NOP func:io_nop access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel -IOURING IORING_OP_READV func:io_read access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel -IOURING IORING_OP_WRITEV func:io_write access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel +IOURING IORING_OP_NOP func:io_nop loc:0 access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel +IOURING IORING_OP_READV func:io_read loc:0 access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel +IOURING IORING_OP_WRITEV func:io_write loc:0 access:user manual_desc:false auto_desc:false file:io_uring.c subsystem:kernel diff --git a/tools/syz-declextract/testdata/io_uring.c.json b/tools/syz-declextract/testdata/io_uring.c.json index 927adfe26..3f0a74a95 100644 --- a/tools/syz-declextract/testdata/io_uring.c.json +++ b/tools/syz-declextract/testdata/io_uring.c.json @@ -1,4 +1,34 @@ { + "functions": [ + { + "name": "io_eopnotsupp_prep", + "file": "io_uring.c" + }, + { + "name": "io_nop", + "file": "io_uring.c" + }, + { + "name": "io_nop_prep", + "file": "io_uring.c" + }, + { + "name": "io_read", + "file": "io_uring.c" + }, + { + "name": "io_readv_prep", + "file": "io_uring.c" + }, + { + "name": "io_write", + "file": "io_uring.c" + }, + { + "name": "io_writev_prep", + "file": "io_uring.c" + } + ], "includes": [ "include/uapi/io_uring.h" ], diff --git a/tools/syz-declextract/testdata/netlink.c.info b/tools/syz-declextract/testdata/netlink.c.info index e57a57c73..c2a57f448 100644 --- a/tools/syz-declextract/testdata/netlink.c.info +++ b/tools/syz-declextract/testdata/netlink.c.info @@ -1,4 +1,4 @@ -NETLINK NETLINK_BAR_CMD_FOO func:NETLINK_BAR_CMD_FOO access:user manual_desc:false auto_desc:true file:netlink.c subsystem:kernel -NETLINK NETLINK_FOO_CMD_BAR func:bar_cmd access:ns_admin manual_desc:false auto_desc:true file:netlink.c subsystem:kernel -NETLINK NETLINK_FOO_CMD_FOO func:foo_cmd access:admin manual_desc:false auto_desc:true file:netlink.c subsystem:kernel -NETLINK NETLINK_NOPOLICY_CMD func:foo_cmd access:user manual_desc:false auto_desc:true file:netlink.c subsystem:kernel +NETLINK NETLINK_BAR_CMD_FOO func:NETLINK_BAR_CMD_FOO loc:0 access:user manual_desc:false auto_desc:true file:netlink.c subsystem:kernel +NETLINK NETLINK_FOO_CMD_BAR func:bar_cmd loc:0 access:ns_admin manual_desc:false auto_desc:true file:netlink.c subsystem:kernel +NETLINK NETLINK_FOO_CMD_FOO func:foo_cmd loc:0 access:admin manual_desc:false auto_desc:true file:netlink.c subsystem:kernel +NETLINK NETLINK_NOPOLICY_CMD func:foo_cmd loc:0 access:user manual_desc:false auto_desc:true file:netlink.c subsystem:kernel diff --git a/tools/syz-declextract/testdata/netlink.c.json b/tools/syz-declextract/testdata/netlink.c.json index ed3a04b79..4233eab7d 100644 --- a/tools/syz-declextract/testdata/netlink.c.json +++ b/tools/syz-declextract/testdata/netlink.c.json @@ -1,4 +1,42 @@ { + "functions": [ + { + "name": "atomic_load32", + "file": "include/types.h", + "is_static": true, + "loc": 1 + }, + { + "name": "atomic_load64", + "file": "include/types.h", + "loc": 1 + }, + { + "name": "bar_cmd", + "file": "netlink.c", + "is_static": true + }, + { + "name": "bar_doit", + "file": "netlink.c", + "is_static": true + }, + { + "name": "bar_post_doit", + "file": "netlink.c", + "is_static": true + }, + { + "name": "bar_pre_doit", + "file": "netlink.c", + "is_static": true + }, + { + "name": "foo_cmd", + "file": "netlink.c", + "is_static": true + } + ], "includes": [ "include/uapi/netlink_family.h" ], diff --git a/tools/syz-declextract/testdata/syscall.c.info b/tools/syz-declextract/testdata/syscall.c.info index 5d204a68e..9b5c4c969 100644 --- a/tools/syz-declextract/testdata/syscall.c.info +++ b/tools/syz-declextract/testdata/syscall.c.info @@ -1,2 +1,2 @@ -SYSCALL chmod func:__do_sys_chmod access:unknown manual_desc:false auto_desc:true file:syscall.c subsystem:kernel -SYSCALL open func:__do_sys_open access:unknown manual_desc:false auto_desc:true file:syscall.c subsystem:kernel +SYSCALL chmod func:__do_sys_chmod loc:1 access:unknown manual_desc:false auto_desc:true file:syscall.c subsystem:kernel +SYSCALL open func:__do_sys_open loc:1 access:unknown manual_desc:false auto_desc:true file:syscall.c subsystem:kernel diff --git a/tools/syz-declextract/testdata/syscall.c.json b/tools/syz-declextract/testdata/syscall.c.json index 6e52fd57e..735ac7dc9 100644 --- a/tools/syz-declextract/testdata/syscall.c.json +++ b/tools/syz-declextract/testdata/syscall.c.json @@ -1,4 +1,16 @@ { + "functions": [ + { + "name": "__do_sys_chmod", + "file": "syscall.c", + "loc": 1 + }, + { + "name": "__do_sys_open", + "file": "syscall.c", + "loc": 1 + } + ], "syscalls": [ { "func": "__do_sys_chmod", diff --git a/tools/syz-declextract/testdata/types.c.info b/tools/syz-declextract/testdata/types.c.info index 4e1bdf314..cf7001874 100644 --- a/tools/syz-declextract/testdata/types.c.info +++ b/tools/syz-declextract/testdata/types.c.info @@ -1 +1 @@ -SYSCALL types_syscall func:__do_sys_types_syscall access:unknown manual_desc:false auto_desc:true file:types.c subsystem:kernel +SYSCALL types_syscall func:__do_sys_types_syscall loc:2 access:unknown manual_desc:false auto_desc:true file:types.c subsystem:kernel diff --git a/tools/syz-declextract/testdata/types.c.json b/tools/syz-declextract/testdata/types.c.json index df19ab4a4..944346502 100644 --- a/tools/syz-declextract/testdata/types.c.json +++ b/tools/syz-declextract/testdata/types.c.json @@ -1,4 +1,11 @@ { + "functions": [ + { + "name": "__do_sys_types_syscall", + "file": "types.c", + "loc": 2 + } + ], "defines": [ { "name": "a", |