tools/syz-declextract: support function scopes

Extract info about function scopes formed by switch'es on function arguments.
For example if we have:

void foo(..., int cmd, ...)
{
  ...
  switch (cmd) {
  case FOO:
    ... block 1 ...
  case BAR:
    ... block 2 ...
  }
  ...
}

We record that any data flow within block 1 is only relevant
when foo's arg cmd has value FOO, similarly for block 2 and BAR.

This allows to do 3 things:
1. Locate ioctl commands that are switched on within transitively
   called functions.
2. Infer return value for each ioctl command.
3. Infer argument type when it's not specified in _IO macro.

This will also allow to infer other multiplexed syscalls.

Descriptions generated on Linux commit c4b9570cfb63501.

5 files changed, 135 insertions, 45 deletions

diff --git a/pkg/declextract/declextract.go b/pkg/declextract/declextract.go
index 16b2d6cca..fbd585389 100644
--- a/pkg/declextract/declextract.go
+++ b/pkg/declextract/declextract.go
@@ -34,6 +34,7 @@ func Run(out *Output, probe *ifaceprobe.Info, syscallRename map[string][]string,
 		syscallRename: syscallRename,
 		structs:       make(map[string]*Struct),
 		funcs:         make(map[string]*Function),
+		ioctls:        make(map[string]*Type),
 		facts:         make(map[string]*typingNode),
 		uniqualizer:   make(map[string]int),
 		debugTrace:    trace,
@@ -65,6 +66,7 @@ type context struct {
 	syscallRename map[string][]string // syscall function -> syscall names
 	structs       map[string]*Struct
 	funcs         map[string]*Function
+	ioctls        map[string]*Type
 	facts         map[string]*typingNode
 	includes      []string
 	defines       []define
@@ -137,11 +139,13 @@ func (ctx *context) processConsts() map[string]string {
 	ctx.includes = append([]string{
 		"vdso/bits.h",
 		"linux/types.h",
+		"linux/usbdevice_fs.h", // to fix broken include/uapi/linux/usbdevice_fs.h
 		"net/netlink.h",
 	}, ctx.includes...)
 	// Also pretend they are used.
 	includeUse["__NR_read"] = "vdso/bits.h"
 	includeUse["__NR_write"] = "linux/types.h"
+	includeUse["__NR_openat"] = "linux/usbdevice_fs.h"
 	includeUse["__NR_close"] = "net/netlink.h"
 	return includeUse
 }
diff --git a/pkg/declextract/entity.go b/pkg/declextract/entity.go
index 83f56ba52..5562ff570 100644
--- a/pkg/declextract/entity.go
+++ b/pkg/declextract/entity.go
@@ -17,24 +17,36 @@ type Output struct {
 	Structs         []*Struct        `json:"structs,omitempty"`
 	Syscalls        []*Syscall       `json:"syscalls,omitempty"`
 	FileOps         []*FileOps       `json:"file_ops,omitempty"`
+	Ioctls          []*Ioctl         `json:"ioctls,omitempty"`
 	IouringOps      []*IouringOp     `json:"iouring_ops,omitempty"`
 	NetlinkFamilies []*NetlinkFamily `json:"netlink_families,omitempty"`
 	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"`
-	Facts    []*TypingFact `json:"facts,omitempty"`
+	Name     string `json:"name,omitempty"`
+	File     string `json:"file,omitempty"`
+	IsStatic bool   `json:"is_static,omitempty"`
+	// Information about function scopes. There is a global scope (with Arg=-1),
+	// and scope for each switch case on the function argument.
+	Scopes []*FunctionScope `json:"scopes,omitempty"`
 
 	callers int
 	calls   []*Function
 	facts   map[string]*typingNode
 }
 
+type FunctionScope struct {
+	// The function argument index that is switched on (-1 for the global scope).
+	Arg int `json:"arg"`
+	// The set of case values for this scope.
+	// It's empt for the global scope for the default case scope.
+	Values []string      `json:"values,omitempty"`
+	LOC    int           `json:"loc,omitempty"`
+	Calls  []string      `json:"calls,omitempty"`
+	Facts  []*TypingFact `json:"facts,omitempty"`
+}
+
 type ConstInfo struct {
 	Name     string `json:"name"`
 	Filename string `json:"filename"`
@@ -63,16 +75,15 @@ type Syscall struct {
 type FileOps struct {
 	Name string `json:"name,omitempty"`
 	// Names of callback functions.
-	Open       string      `json:"open,omitempty"`
-	Read       string      `json:"read,omitempty"`
-	Write      string      `json:"write,omitempty"`
-	Mmap       string      `json:"mmap,omitempty"`
-	Ioctl      string      `json:"ioctl,omitempty"`
-	IoctlCmds  []*IoctlCmd `json:"ioctl_cmds,omitempty"`
-	SourceFile string      `json:"source_file,omitempty"`
+	Open       string `json:"open,omitempty"`
+	Read       string `json:"read,omitempty"`
+	Write      string `json:"write,omitempty"`
+	Mmap       string `json:"mmap,omitempty"`
+	Ioctl      string `json:"ioctl,omitempty"`
+	SourceFile string `json:"source_file,omitempty"`
 }
 
-type IoctlCmd struct {
+type Ioctl struct {
 	// Literal name of the command (e.g. KCOV_REMOTE_ENABLE).
 	Name string `json:"name,omitempty"`
 	Type *Type  `json:"type,omitempty"`
@@ -207,6 +218,7 @@ func (out *Output) Merge(other *Output) {
 	out.Structs = append(out.Structs, other.Structs...)
 	out.Syscalls = append(out.Syscalls, other.Syscalls...)
 	out.FileOps = append(out.FileOps, other.FileOps...)
+	out.Ioctls = append(out.Ioctls, other.Ioctls...)
 	out.IouringOps = append(out.IouringOps, other.IouringOps...)
 	out.NetlinkFamilies = append(out.NetlinkFamilies, other.NetlinkFamilies...)
 	out.NetlinkPolicies = append(out.NetlinkPolicies, other.NetlinkPolicies...)
@@ -219,6 +231,7 @@ func (out *Output) SortAndDedup() {
 	out.Structs = sortAndDedupSlice(out.Structs)
 	out.Syscalls = sortAndDedupSlice(out.Syscalls)
 	out.FileOps = sortAndDedupSlice(out.FileOps)
+	out.Ioctls = sortAndDedupSlice(out.Ioctls)
 	out.IouringOps = sortAndDedupSlice(out.IouringOps)
 	out.NetlinkFamilies = sortAndDedupSlice(out.NetlinkFamilies)
 	out.NetlinkPolicies = sortAndDedupSlice(out.NetlinkPolicies)
diff --git a/pkg/declextract/fileops.go b/pkg/declextract/fileops.go
index d28c48337..cacdcaa9e 100644
--- a/pkg/declextract/fileops.go
+++ b/pkg/declextract/fileops.go
@@ -12,6 +12,9 @@ import (
 // TODO: also emit interface entry for file_operations.
 
 func (ctx *context) serializeFileOps() {
+	for _, ioctl := range ctx.Ioctls {
+		ctx.ioctls[ioctl.Name] = ioctl.Type
+	}
 	fopsToFiles := ctx.mapFopsToFiles()
 	for _, fops := range ctx.FileOps {
 		files := fopsToFiles[fops]
@@ -52,22 +55,36 @@ func (ctx *context) createFops(fops *FileOps, files []string) {
 			" flags flags[mmap_flags], fd %v, offset fileoff)\n", suffix, fdt)
 	}
 	if fops.Ioctl != "" {
-		if len(fops.IoctlCmds) == 0 {
-			ctx.fmt("ioctl%v(fd %v, cmd intptr, arg ptr[in, array[int8]])\n", suffix, fdt)
-		} else {
-			for _, cmd := range sortAndDedupSlice(fops.IoctlCmds) {
-				name := ctx.uniqualize("ioctl cmd", cmd.Name)
-				f := &Field{
-					Name: strings.ToLower(cmd.Name),
-					Type: cmd.Type,
-				}
-				typ := ctx.fieldType(f, nil, "", false)
-				ctx.fmt("ioctl%v_%v(fd %v, cmd const[%v], arg %v)\n",
-					autoSuffix, name, fdt, cmd.Name, typ)
+		ctx.createIoctls(fops, suffix, fdt)
+	}
+	ctx.fmt("\n")
+}
+
+func (ctx *context) createIoctls(fops *FileOps, suffix, fdt string) {
+	const defaultArgType = "ptr[in, array[int8]]"
+	cmds := ctx.inferCommandVariants(fops.Ioctl, fops.SourceFile, 1)
+	if len(cmds) == 0 {
+		retType := ctx.inferReturnType(fops.Ioctl, fops.SourceFile)
+		argType := ctx.inferArgType(fops.Ioctl, fops.SourceFile, 2)
+		if argType == "" {
+			argType = defaultArgType
+		}
+		ctx.fmt("ioctl%v(fd %v, cmd intptr, arg %v) %v\n", suffix, fdt, argType, retType)
+		return
+	}
+	for _, cmd := range cmds {
+		argType := defaultArgType
+		if typ := ctx.ioctls[cmd]; typ != nil {
+			f := &Field{
+				Name: strings.ToLower(cmd),
+				Type: typ,
 			}
+			argType = ctx.fieldType(f, nil, "", false)
 		}
+		name := ctx.uniqualize("ioctl cmd", cmd)
+		ctx.fmt("ioctl%v_%v(fd %v, cmd const[%v], arg %v)\n",
+			autoSuffix, name, fdt, cmd, argType)
 	}
-	ctx.fmt("\n")
 }
 
 // mapFopsToFiles maps file_operations to actual file names.
@@ -176,14 +193,14 @@ func (ctx *context) mapFileToFops(funcs map[string]bool, funcToFops map[string][
 	// An example of an excessive case is if we have 2 file_operations with just read+write,
 	// currently we emit generic read/write operations, so we would emit completly equal
 	// descriptions for both. Ioctl commands is the only non-generic descriptions we emit now,
-	// so if a file_operations has any commands, it won't be considered excessive.
+	// so if a file_operations has an ioctl handler, it won't be considered excessive.
 	// Note that if we generate specialized descriptions for read/write/mmap in future,
 	// then these won't be considered excessive as well.
 	excessive := make(map[*FileOps]bool)
 	for i := 0; i < len(best); i++ {
 		for j := i + 1; j < len(best); j++ {
 			a, b := best[i], best[j]
-			if (a.Ioctl == b.Ioctl || len(a.IoctlCmds)+len(b.IoctlCmds) == 0) &&
+			if (a.Ioctl == b.Ioctl) &&
 				(a.Read == "") == (b.Read == "") &&
 				(a.Write == "") == (b.Write == "") &&
 				(a.Mmap == "") == (b.Mmap == "") &&
diff --git a/pkg/declextract/interface.go b/pkg/declextract/interface.go
index b5c8ea5ac..d891b4899 100644
--- a/pkg/declextract/interface.go
+++ b/pkg/declextract/interface.go
@@ -59,15 +59,16 @@ func (ctx *context) processFunctions() {
 	}
 	nocallers := 0
 	for _, fn := range ctx.Functions {
-		for _, callee := range fn.Calls {
-			called := ctx.findFunc(callee, fn.File)
-			if called == nil || called == fn {
-				continue
+		for _, scope := range fn.Scopes {
+			for _, callee := range scope.Calls {
+				called := ctx.findFunc(callee, fn.File)
+				if called == nil || called == fn {
+					continue
+				}
+				fn.calls = append(fn.calls, called)
+				called.callers++
 			}
-			fn.calls = append(fn.calls, called)
-			called.callers++
 		}
-		fn.Calls = nil
 		if len(fn.calls) == 0 {
 			nocallers++
 		}
@@ -84,7 +85,9 @@ func (ctx *context) reachableLOC(name, file string) int {
 	ctx.collectRachable(fn, reachable)
 	loc := 0
 	for fn := range reachable {
-		loc += fn.LOC
+		for _, scope := range fn.Scopes {
+			loc += scope.LOC
+		}
 	}
 	return loc
 }
diff --git a/pkg/declextract/typing.go b/pkg/declextract/typing.go
index 7de22474d..f29f8e950 100644
--- a/pkg/declextract/typing.go
+++ b/pkg/declextract/typing.go
@@ -94,6 +94,8 @@ const maxTraversalDepth = 18
 
 type typingNode struct {
 	id    string
+	fn    *Function
+	arg   int
 	flows [2]map[*typingNode]bool
 }
 
@@ -104,14 +106,16 @@ const (
 
 func (ctx *context) processTypingFacts() {
 	for _, fn := range ctx.Functions {
-		for _, fact := range fn.Facts {
-			src := ctx.canonicalNode(fn, fact.Src)
-			dst := ctx.canonicalNode(fn, fact.Dst)
-			if src == nil || dst == nil {
-				continue
+		for _, scope := range fn.Scopes {
+			for _, fact := range scope.Facts {
+				src := ctx.canonicalNode(fn, fact.Src)
+				dst := ctx.canonicalNode(fn, fact.Dst)
+				if src == nil || dst == nil {
+					continue
+				}
+				src.flows[flowTo][dst] = true
+				dst.flows[flowFrom][src] = true
 			}
-			src.flows[flowTo][dst] = true
-			dst.flows[flowFrom][src] = true
 		}
 	}
 }
@@ -142,8 +146,14 @@ func (ctx *context) canonicalNode(fn *Function, ent *TypingEntity) *typingNode {
 	if n != nil {
 		return n
 	}
+	arg := -1
+	if ent.Argument != nil {
+		arg = ent.Argument.Arg
+	}
 	n = &typingNode{
-		id: fullID,
+		id:  fullID,
+		fn:  fn,
+		arg: arg,
 	}
 	for i := range n.flows {
 		n.flows[i] = make(map[*typingNode]bool)
@@ -266,3 +276,46 @@ func flowString(path []*typingNode, flowType int) string {
 	}
 	return w.String()
 }
+
+func (ctx *context) inferCommandVariants(name, file string, arg int) []string {
+	ctx.trace("inferring %v:arg%v variants", name, arg)
+	fn := ctx.findFunc(name, file)
+	if fn == nil {
+		return nil
+	}
+	var variants []string
+	n := fn.facts[fmt.Sprintf("arg%v", arg)]
+	if n == nil {
+		ctx.collectCommandVariants(fn, arg, &variants)
+	} else {
+		visited := make(map[*typingNode]bool)
+		ctx.walkCommandVariants(n, &variants, visited, 0)
+	}
+	return sortAndDedupSlice(variants)
+}
+
+func (ctx *context) collectCommandVariants(fn *Function, arg int, variants *[]string) {
+	var values []string
+	for _, scope := range fn.Scopes {
+		if scope.Arg == arg {
+			values = append(values, scope.Values...)
+		}
+	}
+	if len(values) != 0 {
+		ctx.trace("  function %v:arg%v implements: %v", fn.Name, arg, values)
+		*variants = append(*variants, values...)
+	}
+}
+
+func (ctx *context) walkCommandVariants(n *typingNode, variants *[]string, visited map[*typingNode]bool, depth int) {
+	if visited[n] || depth >= 10 {
+		return
+	}
+	visited[n] = true
+	if n.arg >= 0 {
+		ctx.collectCommandVariants(n.fn, n.arg, variants)
+	}
+	for e := range n.flows[flowTo] {
+		ctx.walkCommandVariants(e, variants, visited, depth+1)
+	}
+}