tools/syz-check: add description checking utility

syz-check parses vmlinux dwarf, extracts struct descriptions,
compares them with what we have (size, fields, alignment, etc)
and produces .warn files.
This is first raw version, it can be improved in a number of ways.
But it already helped to identify a critical issue #1542
and shows some wrong struct descriptions.

Update #590

2 files changed, 430 insertions, 0 deletions

diff --git a/tools/syz-check/check.go b/tools/syz-check/check.go
new file mode 100644
index 000000000..bde088a78
--- /dev/null
+++ b/tools/syz-check/check.go
@@ -0,0 +1,228 @@
+// Copyright 2019 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.
+
+// syz-check does best-effort static correctness checking of the syscall descriptions in sys/os/*.txt.
+// Use:
+//	$ go install ./tools/syz-check
+//	$ syz-check -obj /linux/vmlinux
+// Currently it works only for linux and only for one arch at a time.
+// The vmlinux files should include debug info and enable all relevant configs (since we parse dwarf).
+// The results are produced in sys/os/*.warn files.
+// On implementation level syz-check parses vmlinux dwarf, extracts struct descriptions
+// and compares them with what we have (size, fields, alignment, etc).
+package main
+
+import (
+	"bytes"
+	"debug/dwarf"
+	"flag"
+	"fmt"
+	"os"
+	"path/filepath"
+	"runtime"
+	"runtime/pprof"
+	"sort"
+
+	"github.com/google/syzkaller/pkg/ast"
+	"github.com/google/syzkaller/pkg/compiler"
+	"github.com/google/syzkaller/pkg/osutil"
+	"github.com/google/syzkaller/prog"
+	"github.com/google/syzkaller/sys/targets"
+)
+
+func main() {
+	var (
+		flagOS           = flag.String("os", runtime.GOOS, "OS")
+		flagArch         = flag.String("arch", runtime.GOARCH, "arch")
+		flagKernelObject = flag.String("obj", "", "kernel object file")
+		flagCPUProfile   = flag.String("cpuprofile", "", "write CPU profile to this file")
+		flagMEMProfile   = flag.String("memprofile", "", "write memory profile to this file")
+	)
+	flag.Parse()
+	if *flagCPUProfile != "" {
+		f, err := os.Create(*flagCPUProfile)
+		if err != nil {
+			fmt.Fprintf(os.Stderr, "failed to create cpuprofile file: %v\n", err)
+			os.Exit(1)
+		}
+		defer f.Close()
+		if err := pprof.StartCPUProfile(f); err != nil {
+			fmt.Fprintf(os.Stderr, "failed to start cpu profile: %v\n", err)
+			os.Exit(1)
+		}
+		defer pprof.StopCPUProfile()
+	}
+	if *flagMEMProfile != "" {
+		defer func() {
+			f, err := os.Create(*flagMEMProfile)
+			if err != nil {
+				fmt.Fprintf(os.Stderr, "failed to create memprofile file: %v\n", err)
+				os.Exit(1)
+			}
+			defer f.Close()
+			runtime.GC()
+			if err := pprof.WriteHeapProfile(f); err != nil {
+				fmt.Fprintf(os.Stderr, "failed to write mem profile: %v\n", err)
+				os.Exit(1)
+			}
+		}()
+	}
+	if err := check(*flagOS, *flagArch, *flagKernelObject); err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+}
+
+func check(OS, arch, obj string) error {
+	structs, err := parseKernelObject(obj)
+	if err != nil {
+		return err
+	}
+	structDescs, locs, err := parseDescriptions(OS, arch)
+	if err != nil {
+		return err
+	}
+	warnings, err := checkImpl(structs, structDescs, locs)
+	if err != nil {
+		return err
+	}
+	return writeWarnings(OS, arch, warnings)
+}
+
+func writeWarnings(OS, arch string, warnings map[string][]string) error {
+	allFiles, err := filepath.Glob(filepath.Join("sys", OS, "*.warn"))
+	if err != nil {
+		return err
+	}
+	toRemove := make(map[string]bool)
+	for _, file := range allFiles {
+		toRemove[file] = true
+	}
+	for file, warns := range warnings {
+		sort.Strings(warns)
+		buf := new(bytes.Buffer)
+		for _, warn := range warns {
+			fmt.Fprintf(buf, "%v\n", warn)
+		}
+		warnFile := filepath.Join("sys", OS, file+".warn")
+		if err := osutil.WriteFile(warnFile, buf.Bytes()); err != nil {
+			return err
+		}
+		delete(toRemove, warnFile)
+	}
+	for file := range toRemove {
+		os.Remove(file)
+	}
+	return nil
+}
+
+func checkImpl(structs map[string]*dwarf.StructType, structDescs []*prog.KeyedStruct,
+	locs map[string]*ast.Struct) (map[string][]string, error) {
+	warnings := make(map[string][]string)
+	checked := make(map[string]bool)
+	for _, str := range structDescs {
+		typ := str.Desc
+		if typ.Varlen() {
+			continue
+		}
+		astStruct := locs[typ.Name()]
+		if astStruct == nil {
+			// TODO: that's a template. Handle templates.
+			continue
+		}
+		if checked[typ.Name()] {
+			continue
+		}
+		checked[typ.Name()] = true
+
+		if err := checkStruct(warnings, typ, astStruct, structs[typ.Name()]); err != nil {
+			return nil, err
+		}
+
+	}
+	return warnings, nil
+}
+
+func checkStruct(warnings map[string][]string, typ *prog.StructDesc, astStruct *ast.Struct,
+	str *dwarf.StructType) error {
+	warn := func(pos ast.Pos, msg string, args ...interface{}) {
+		warnings[pos.File] = append(warnings[pos.File],
+			fmt.Sprintf("%04v: ", pos.Line)+fmt.Sprintf(msg, args...))
+	}
+	if str == nil {
+		warn(astStruct.Pos, "struct %v: no corresponding struct in kernel", typ.Name())
+		return nil
+	}
+	if typ.Size() != uint64(str.ByteSize) {
+		warn(astStruct.Pos, "struct %v: bad size: syz=%v kernel=%v", typ.Name(), typ.Size(), str.ByteSize)
+	}
+	// TODO: handle unions, currently we should report some false errors.
+	ai := 0
+	offset := uint64(0)
+	for _, field := range typ.Fields {
+		if prog.IsPad(field) {
+			offset += field.Size()
+			continue
+		}
+		if ai < len(str.Field) {
+			fld := str.Field[ai]
+			if field.Size() != uint64(fld.Type.Size()) {
+				warn(astStruct.Fields[ai].Pos, "field %v.%v/%v: bad size: syz=%v kernel=%v",
+					typ.Name(), field.FieldName(), fld.Name, field.Size(), fld.Type.Size())
+			}
+			if offset != uint64(fld.ByteOffset) {
+				warn(astStruct.Fields[ai].Pos, "field %v.%v/%v: bad offset: syz=%v kernel=%v",
+					typ.Name(), field.FieldName(), fld.Name, offset, fld.ByteOffset)
+			}
+			// How would you define bitfield offset?
+			// Offset of the beginning of the field from the beginning of the memory location, right?
+			// No, DWARF defines it as offset of the end of the field from the end of the memory location.
+			offset := fld.Type.Size()*8 - fld.BitOffset - fld.BitSize
+			if fld.BitSize == 0 {
+				// And to make things even more interesting this calculation
+				// does not work for normal variables.
+				offset = 0
+			}
+			if field.BitfieldLength() != uint64(fld.BitSize) ||
+				field.BitfieldOffset() != uint64(offset) {
+				warn(astStruct.Fields[ai].Pos, "field %v.%v/%v: bad bit size/offset: syz=%v/%v kernel=%v/%v",
+					typ.Name(), field.FieldName(), fld.Name,
+					field.BitfieldLength(), field.BitfieldOffset(),
+					fld.BitSize, offset)
+			}
+		}
+		ai++
+		if !field.BitfieldMiddle() {
+			offset += field.Size()
+		}
+	}
+	if ai != len(str.Field) {
+		warn(astStruct.Pos, "struct %v: bad number of fields: syz=%v kernel=%v", typ.Name(), ai, len(str.Field))
+	}
+	return nil
+}
+
+func parseDescriptions(OS, arch string) ([]*prog.KeyedStruct, map[string]*ast.Struct, error) {
+	eh := func(pos ast.Pos, msg string) {}
+	top := ast.ParseGlob(filepath.Join("sys", OS, "*.txt"), eh)
+	if top == nil {
+		return nil, nil, fmt.Errorf("failed to parse txt files")
+	}
+	consts := compiler.DeserializeConstsGlob(filepath.Join("sys", OS, "*_"+arch+".const"), eh)
+	if consts == nil {
+		return nil, nil, fmt.Errorf("failed to parse const files")
+	}
+	prg := compiler.Compile(top, consts, targets.Get(OS, arch), eh)
+	if prg == nil {
+		return nil, nil, fmt.Errorf("failed to compile descriptions")
+	}
+	prog.RestoreLinks(prg.Syscalls, prg.Resources, prg.StructDescs)
+	locs := make(map[string]*ast.Struct)
+	for _, decl := range top.Nodes {
+		switch n := decl.(type) {
+		case *ast.Struct:
+			locs[n.Name.Name] = n
+		}
+	}
+	return prg.StructDescs, locs, nil
+}
diff --git a/tools/syz-check/dwarf.go b/tools/syz-check/dwarf.go
new file mode 100644
index 000000000..adda98173
--- /dev/null
+++ b/tools/syz-check/dwarf.go
@@ -0,0 +1,202 @@
+// Copyright 2019 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 main
+
+import (
+	"debug/dwarf"
+	"debug/elf"
+	"fmt"
+	"runtime"
+	"strings"
+)
+
+func parseKernelObject(obj string) (map[string]*dwarf.StructType, error) {
+	file, err := elf.Open(obj)
+	if err != nil {
+		return nil, err
+	}
+	var sections []*elf.Section
+	for _, sec := range file.Sections {
+		// We don't need these for our purposes and dropping them speeds up parsing a lot.
+		//nolint:misspell
+		if sec.Name == ".debug_line" || strings.HasPrefix(sec.Name, ".rela.") {
+			continue
+		}
+		sections = append(sections, sec)
+	}
+	file.Sections = sections
+	debugInfo, err := file.DWARF()
+	if err != nil {
+		return nil, err
+	}
+	// DWARF parsing in Go is slow, so we parallelize it as much as possible.
+	// First stage extracts top-level compilation units and sends them over unitc.
+	// Next parallel stage consumes units, extracts struct offsets and sends them over offsetc.
+	// Next parallel stage consumes offsets, extracts struct types and sends them over structc.
+	// Last stage consumes structs, deduplicates them and builds the resulting map.
+	numProcs := runtime.GOMAXPROCS(0)
+	numTypes := numProcs/8 + 1
+	buffer := 100 * numProcs
+	unitc := make(chan Unit, buffer)
+	offsetc := make(chan []dwarf.Offset, buffer)
+	structc := make(chan []*dwarf.StructType, buffer)
+	errc := make(chan error)
+
+	go extractCompilationUnits(debugInfo, unitc, errc)
+
+	uniterrc := make(chan error, numProcs)
+	for p := 0; p < numProcs; p++ {
+		go extractOffsets(debugInfo, unitc, offsetc, uniterrc)
+	}
+	go func() {
+		var err error
+		for p := 0; p < numProcs; p++ {
+			if err1 := <-uniterrc; err1 != nil {
+				err = err1
+			}
+		}
+		close(offsetc)
+		errc <- err
+	}()
+
+	structerrc := make(chan error, numTypes)
+	for p := 0; p < numTypes; p++ {
+		// Only parallel extraction of types races with each other,
+		// so we can reuse debugInfo for one of the goroutines.
+		debugInfo1 := debugInfo
+		if p != 0 {
+			debugInfo1 = nil
+		}
+		go extractStructs(file, debugInfo1, offsetc, structc, structerrc)
+	}
+	go func() {
+		var err error
+		for p := 0; p < numTypes; p++ {
+			if err1 := <-structerrc; err1 != nil {
+				err = err1
+			}
+		}
+		close(structc)
+		errc <- err
+	}()
+
+	result := make(map[string]*dwarf.StructType)
+	go func() {
+		for structs := range structc {
+			for _, str := range structs {
+				result[str.StructName] = str
+			}
+		}
+		errc <- nil
+	}()
+
+	for i := 0; i < 4; i++ {
+		if err := <-errc; err != nil {
+			return nil, err
+		}
+	}
+	return result, nil
+}
+
+type Unit struct {
+	start dwarf.Offset
+	end   dwarf.Offset
+}
+
+func extractCompilationUnits(debugInfo *dwarf.Data, unitc chan Unit, errc chan error) {
+	defer close(unitc)
+	const sentinel = ^dwarf.Offset(0)
+	prev := sentinel
+	for r := debugInfo.Reader(); ; {
+		ent, err := r.Next()
+		if err != nil {
+			errc <- err
+			return
+		}
+		if ent == nil {
+			if prev != sentinel {
+				unitc <- Unit{prev, sentinel}
+			}
+			errc <- nil
+			break
+		}
+		if ent.Tag != dwarf.TagCompileUnit {
+			errc <- fmt.Errorf("found unexpected tag %v on top level", ent.Tag)
+			return
+		}
+		if prev != sentinel {
+			unitc <- Unit{prev, ent.Offset}
+		}
+		prev = ent.Offset
+		r.SkipChildren()
+	}
+}
+
+func extractOffsets(debugInfo *dwarf.Data, unitc chan Unit, offsetc chan []dwarf.Offset, errc chan error) {
+	r := debugInfo.Reader()
+	var offsets []dwarf.Offset
+	for unit := range unitc {
+		r.Seek(unit.start)
+		for {
+			ent, err := r.Next()
+			if err != nil {
+				errc <- err
+				return
+			}
+			if ent == nil || ent.Offset >= unit.end {
+				break
+			}
+			if ent.Tag == dwarf.TagStructType || ent.Tag == dwarf.TagTypedef {
+				offsets = append(offsets, ent.Offset)
+			}
+			if ent.Tag != dwarf.TagCompileUnit {
+				r.SkipChildren()
+			}
+		}
+		offsetc <- offsets
+		offsets = make([]dwarf.Offset, 0, len(offsets))
+	}
+	errc <- nil
+}
+
+func extractStructs(file *elf.File, debugInfo *dwarf.Data, offsetc chan []dwarf.Offset,
+	structc chan []*dwarf.StructType, errc chan error) {
+	if debugInfo == nil {
+		var err error
+		debugInfo, err = file.DWARF()
+		if err != nil {
+			errc <- err
+			return
+		}
+	}
+	var structs []*dwarf.StructType
+	appendStruct := func(str *dwarf.StructType) {
+		if str.StructName != "" && str.ByteSize > 0 {
+			structs = append(structs, str)
+		}
+	}
+	for offsets := range offsetc {
+		for _, off := range offsets {
+			typ1, err := debugInfo.Type(off)
+			if err != nil {
+				errc <- err
+				return
+			}
+			switch typ := typ1.(type) {
+			case *dwarf.StructType:
+				appendStruct(typ)
+			case *dwarf.TypedefType:
+				if str, ok := typ.Type.(*dwarf.StructType); ok {
+					str.StructName = typ.Name
+					appendStruct(str)
+				}
+			default:
+				errc <- fmt.Errorf("got not struct/typedef")
+			}
+		}
+		structc <- structs
+		structs = make([]*dwarf.StructType, 0, len(structs))
+	}
+	errc <- nil
+}