From 5dd495422eafefcc3e74450aadd68756cbca7eb1 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Sun, 9 Dec 2018 15:32:10 +0100 Subject: syz-manager: move coverage report code to pkg/cover This will allow better testing and make it possible to reuse this code. --- pkg/cover/report.go | 454 +++++++++++++++++++++++++++++++++++++++++++++++++++ syz-manager/cover.go | 418 +---------------------------------------------- syz-manager/html.go | 5 +- 3 files changed, 465 insertions(+), 412 deletions(-) create mode 100644 pkg/cover/report.go diff --git a/pkg/cover/report.go b/pkg/cover/report.go new file mode 100644 index 000000000..a4878dba4 --- /dev/null +++ b/pkg/cover/report.go @@ -0,0 +1,454 @@ +// Copyright 2018 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 cover + +import ( + "bufio" + "bytes" + "fmt" + "html/template" + "io" + "io/ioutil" + "path/filepath" + "sort" + "strconv" + "strings" + + "github.com/google/syzkaller/pkg/hash" + "github.com/google/syzkaller/pkg/osutil" + "github.com/google/syzkaller/pkg/symbolizer" +) + +type ReportGenerator struct { + vmlinux string + srcDir string + arch string + symbols []symbol + coverPCs []uint64 +} + +type symbol struct { + start uint64 + end uint64 + name string +} + +type coverage struct { + line int + covered bool +} + +func MakeReportGenerator(vmlinux, srcDir, arch string) (*ReportGenerator, error) { + rg := &ReportGenerator{ + vmlinux: vmlinux, + srcDir: srcDir, + arch: arch, + } + if err := rg.readSymbols(); err != nil { + return nil, err + } + if err := rg.readPCs(); err != nil { + return nil, err + } + return rg, nil +} + +func (rg *ReportGenerator) Do(w io.Writer, pcs []uint64) error { + if len(pcs) == 0 { + return fmt.Errorf("no coverage data available") + } + for i, pc := range pcs { + pcs[i] = PreviousInstructionPC(rg.arch, pc) + } + covered, _, err := rg.symbolize(pcs) + if err != nil { + return err + } + if len(covered) == 0 { + return fmt.Errorf("'%s' does not have debug info (set CONFIG_DEBUG_INFO=y)", rg.vmlinux) + } + uncoveredPCs := rg.uncoveredPcsInFuncs(pcs) + uncovered, prefix, err := rg.symbolize(uncoveredPCs) + if err != nil { + return err + } + return rg.generate(w, prefix, covered, uncovered) +} + +func (rg *ReportGenerator) generate(w io.Writer, prefix string, covered, uncovered []symbolizer.Frame) error { + var d templateData + for f, covered := range fileSet(covered, uncovered) { + remain := filepath.Clean(strings.TrimPrefix(f, prefix)) + if rg.srcDir != "" && !strings.HasPrefix(remain, rg.srcDir) { + f = filepath.Join(rg.srcDir, remain) + } + lines, err := parseFile(f) + if err != nil { + return err + } + coverage := 0 + var buf bytes.Buffer + for i, ln := range lines { + if len(covered) > 0 && covered[0].line == i+1 { + if covered[0].covered { + buf.Write([]byte("")) + buf.Write(ln) + buf.Write([]byte(" /*covered*/\n")) + coverage++ + } else { + buf.Write([]byte("")) + buf.Write(ln) + buf.Write([]byte("\n")) + } + covered = covered[1:] + } else { + buf.Write(ln) + buf.Write([]byte{'\n'}) + } + } + f = filepath.Clean(remain) + d.Files = append(d.Files, &templateFile{ + ID: hash.String([]byte(f)), + Name: f, + Body: template.HTML(buf.String()), + Coverage: coverage, + }) + } + sort.Sort(templateFileArray(d.Files)) + return coverTemplate.Execute(w, d) +} + +func (rg *ReportGenerator) readSymbols() error { + symbols, err := symbolizer.ReadSymbols(rg.vmlinux) + if err != nil { + return fmt.Errorf("failed to run nm on %v: %v", rg.vmlinux, err) + } + for name, ss := range symbols { + for _, s := range ss { + rg.symbols = append(rg.symbols, symbol{ + start: s.Addr, + end: s.Addr + uint64(s.Size), + name: name, + }) + } + } + sort.Slice(rg.symbols, func(i, j int) bool { + return rg.symbols[i].start < rg.symbols[j].start + }) + return nil +} + +// readPCs collects list of PCs of __sanitizer_cov_trace_pc calls in the kernel. +func (rg *ReportGenerator) readPCs() error { + cmd := osutil.Command("objdump", "-d", "--no-show-raw-insn", rg.vmlinux) + stdout, err := cmd.StdoutPipe() + if err != nil { + return err + } + defer stdout.Close() + if err := cmd.Start(); err != nil { + return fmt.Errorf("failed to run objdump on %v: %v", rg.vmlinux, err) + } + defer cmd.Wait() + s := bufio.NewScanner(stdout) + callInsnS, traceFuncS := archCallInsn(rg.arch) + callInsn, traceFunc := []byte(callInsnS), []byte(traceFuncS) + for s.Scan() { + ln := s.Bytes() + if pos := bytes.Index(ln, callInsn); pos == -1 { + continue + } else if !bytes.Contains(ln[pos:], traceFunc) { + continue + } + colon := bytes.IndexByte(ln, ':') + if colon == -1 { + continue + } + pc, err := strconv.ParseUint(string(ln[:colon]), 16, 64) + if err != nil { + continue + } + rg.coverPCs = append(rg.coverPCs, pc) + } + if err := s.Err(); err != nil { + return fmt.Errorf("failed to run objdump output: %v", err) + } + sort.Slice(rg.coverPCs, func(i, j int) bool { + return rg.coverPCs[i] < rg.coverPCs[j] + }) + return nil +} + +// uncoveredPcsInFuncs returns uncovered PCs with __sanitizer_cov_trace_pc calls in functions containing pcs. +func (rg *ReportGenerator) uncoveredPcsInFuncs(pcs []uint64) []uint64 { + handledFuncs := make(map[uint64]bool) + uncovered := make(map[uint64]bool) + for _, pc := range pcs { + idx := sort.Search(len(rg.symbols), func(i int) bool { + return pc < rg.symbols[i].end + }) + if idx == len(rg.symbols) { + continue + } + s := rg.symbols[idx] + if pc < s.start || pc > s.end { + continue + } + if !handledFuncs[s.start] { + handledFuncs[s.start] = true + startPC := sort.Search(len(rg.coverPCs), func(i int) bool { + return s.start <= rg.coverPCs[i] + }) + endPC := sort.Search(len(rg.coverPCs), func(i int) bool { + return s.end < rg.coverPCs[i] + }) + for _, pc1 := range rg.coverPCs[startPC:endPC] { + uncovered[pc1] = true + } + } + delete(uncovered, pc) + } + uncoveredPCs := make([]uint64, 0, len(uncovered)) + for pc := range uncovered { + uncoveredPCs = append(uncoveredPCs, pc) + } + return uncoveredPCs +} + +func (rg *ReportGenerator) symbolize(pcs []uint64) ([]symbolizer.Frame, string, error) { + symb := symbolizer.NewSymbolizer() + defer symb.Close() + + frames, err := symb.SymbolizeArray(rg.vmlinux, pcs) + if err != nil { + return nil, "", err + } + + prefix := "" + for i := range frames { + frame := &frames[i] + frame.PC-- + if prefix == "" { + prefix = frame.File + } else { + i := 0 + for ; i < len(prefix) && i < len(frame.File); i++ { + if prefix[i] != frame.File[i] { + break + } + } + prefix = prefix[:i] + } + + } + return frames, prefix, nil +} + +func parseFile(fn string) ([][]byte, error) { + data, err := ioutil.ReadFile(fn) + if err != nil { + return nil, err + } + htmlReplacer := strings.NewReplacer(">", ">", "<", "<", "&", "&", "\t", " ") + var lines [][]byte + for { + idx := bytes.IndexByte(data, '\n') + if idx == -1 { + break + } + lines = append(lines, []byte(htmlReplacer.Replace(string(data[:idx])))) + data = data[idx+1:] + } + if len(data) != 0 { + lines = append(lines, data) + } + return lines, nil +} + +func fileSet(covered, uncovered []symbolizer.Frame) map[string][]coverage { + files := make(map[string]map[int]bool) + funcs := make(map[string]bool) + for _, frame := range covered { + if files[frame.File] == nil { + files[frame.File] = make(map[int]bool) + } + files[frame.File][frame.Line] = true + funcs[frame.Func] = true + } + for _, frame := range uncovered { + if !funcs[frame.Func] { + continue + } + if files[frame.File] == nil { + files[frame.File] = make(map[int]bool) + } + if !files[frame.File][frame.Line] { + files[frame.File][frame.Line] = false + } + } + res := make(map[string][]coverage) + for f, lines := range files { + sorted := make([]coverage, 0, len(lines)) + for ln, covered := range lines { + sorted = append(sorted, coverage{ln, covered}) + } + sort.Slice(sorted, func(i, j int) bool { + return sorted[i].line < sorted[j].line + }) + res[f] = sorted + } + return res +} + +func PreviousInstructionPC(arch string, pc uint64) uint64 { + switch arch { + case "amd64": + return pc - 5 + case "386": + return pc - 1 + case "arm64": + return pc - 4 + case "arm": + // THUMB instructions are 2 or 4 bytes with low bit set. + // ARM instructions are always 4 bytes. + return (pc - 3) & ^uint64(1) + case "ppc64le": + return pc - 4 + default: + panic("unknown arch") + } +} + +func archCallInsn(arch string) (string, string) { + const callName = " <__sanitizer_cov_trace_pc>" + switch arch { + case "amd64": + // ffffffff8100206a: callq ffffffff815cc1d0 <__sanitizer_cov_trace_pc> + return "\tcallq ", callName + case "386": + // c1000102: call c10001f0 <__sanitizer_cov_trace_pc> + return "\tcall ", callName + case "arm64": + // ffff0000080d9cc0: bl ffff00000820f478 <__sanitizer_cov_trace_pc> + return "\tbl\t", callName + case "arm": + // 8010252c: bl 801c3280 <__sanitizer_cov_trace_pc> + return "\tbl\t", callName + case "ppc64le": + // c00000000006d904: bl c000000000350780 <.__sanitizer_cov_trace_pc> + return "\tbl ", " <.__sanitizer_cov_trace_pc>" + default: + panic("unknown arch") + } +} + +type templateData struct { + Files []*templateFile +} + +type templateFile struct { + ID string + Name string + Body template.HTML + Coverage int +} + +type templateFileArray []*templateFile + +func (a templateFileArray) Len() int { return len(a) } +func (a templateFileArray) Less(i, j int) bool { + n1 := a[i].Name + n2 := a[j].Name + // Move include files to the bottom. + if len(n1) != 0 && len(n2) != 0 { + if n1[0] != '.' && n2[0] == '.' { + return true + } + if n1[0] == '.' && n2[0] != '.' { + return false + } + } + return n1 < n2 +} +func (a templateFileArray) Swap(i, j int) { a[i], a[j] = a[j], a[i] } + +var coverTemplate = template.Must(template.New("").Parse(` + + + + + + + +
+ +
+
+ {{range $i, $f := .Files}} +
{{$f.Body}}
{{end}} +
+ + + +`)) diff --git a/syz-manager/cover.go b/syz-manager/cover.go index 11993b537..6c05df174 100644 --- a/syz-manager/cover.go +++ b/syz-manager/cover.go @@ -7,65 +7,34 @@ import ( "bufio" "bytes" "fmt" - "html/template" "io" - "io/ioutil" "path/filepath" - "sort" "strconv" "strings" "sync" "time" "github.com/google/syzkaller/pkg/cover" - "github.com/google/syzkaller/pkg/hash" "github.com/google/syzkaller/pkg/osutil" - "github.com/google/syzkaller/pkg/symbolizer" ) -type symbol struct { - start uint64 - end uint64 - name string -} - -type coverage struct { - line int - covered bool -} - var ( initCoverOnce sync.Once initCoverError error - initCoverSymbols []symbol - initCoverPCs []uint64 initCoverVMOffset uint32 + reportGenerator *cover.ReportGenerator ) -func initCover(kernelObj, kernelObjName, arch string) error { +func initCover(kernelObj, kernelObjName, kernelSrc, arch string) error { if kernelObj == "" { return fmt.Errorf("kernel_obj is not specified") } vmlinux := filepath.Join(kernelObj, kernelObjName) - symbols, err := symbolizer.ReadSymbols(vmlinux) + var err error + reportGenerator, err = cover.MakeReportGenerator(vmlinux, kernelSrc, arch) if err != nil { - return fmt.Errorf("failed to run nm on %v: %v", vmlinux, err) - } - for name, ss := range symbols { - for _, s := range ss { - initCoverSymbols = append(initCoverSymbols, symbol{s.Addr, s.Addr + uint64(s.Size), name}) - } - } - sort.Slice(initCoverSymbols, func(i, j int) bool { - return initCoverSymbols[i].start < initCoverSymbols[j].start - }) - initCoverPCs, err = coveredPCs(arch, vmlinux) - if err != nil { - return fmt.Errorf("failed to run objdump on %v: %v", vmlinux, err) + return err } - sort.Slice(initCoverPCs, func(i, j int) bool { - return initCoverPCs[i] < initCoverPCs[j] - }) initCoverVMOffset, err = getVMOffset(vmlinux) return err } @@ -74,133 +43,15 @@ func generateCoverHTML(w io.Writer, kernelObj, kernelObjName, kernelSrc, arch st if len(cov) == 0 { return fmt.Errorf("no coverage data available") } - initCoverOnce.Do(func() { initCoverError = initCover(kernelObj, kernelObjName, arch) }) + initCoverOnce.Do(func() { initCoverError = initCover(kernelObj, kernelObjName, kernelSrc, arch) }) if initCoverError != nil { return initCoverError } - pcs := make([]uint64, 0, len(cov)) for pc := range cov { - fullPC := cover.RestorePC(pc, initCoverVMOffset) - prevPC := previousInstructionPC(arch, fullPC) - pcs = append(pcs, prevPC) - } - vmlinux := filepath.Join(kernelObj, kernelObjName) - uncovered, err := uncoveredPcsInFuncs(vmlinux, pcs) - if err != nil { - return err - } - - coveredFrames, _, err := symbolize(vmlinux, pcs) - if err != nil { - return err - } - if len(coveredFrames) == 0 { - return fmt.Errorf("'%s' does not have debug info (set CONFIG_DEBUG_INFO=y)", vmlinux) - } - - uncoveredFrames, prefix, err := symbolize(vmlinux, uncovered) - if err != nil { - return err - } - - var d templateData - for f, covered := range fileSet(coveredFrames, uncoveredFrames) { - remain := filepath.Clean(strings.TrimPrefix(f, prefix)) - if kernelSrc != "" && !strings.HasPrefix(remain, kernelSrc) { - f = filepath.Join(kernelSrc, remain) - } - lines, err := parseFile(f) - if err != nil { - return err - } - coverage := 0 - var buf bytes.Buffer - for i, ln := range lines { - if len(covered) > 0 && covered[0].line == i+1 { - if covered[0].covered { - buf.Write([]byte("")) - buf.Write(ln) - buf.Write([]byte(" /*covered*/\n")) - coverage++ - } else { - buf.Write([]byte("")) - buf.Write(ln) - buf.Write([]byte("\n")) - } - covered = covered[1:] - } else { - buf.Write(ln) - buf.Write([]byte{'\n'}) - } - } - f = filepath.Clean(remain) - d.Files = append(d.Files, &templateFile{ - ID: hash.String([]byte(f)), - Name: f, - Body: template.HTML(buf.String()), - Coverage: coverage, - }) + pcs = append(pcs, cover.RestorePC(pc, initCoverVMOffset)) } - - sort.Sort(templateFileArray(d.Files)) - return coverTemplate.Execute(w, d) -} - -func fileSet(covered, uncovered []symbolizer.Frame) map[string][]coverage { - files := make(map[string]map[int]bool) - funcs := make(map[string]bool) - for _, frame := range covered { - if files[frame.File] == nil { - files[frame.File] = make(map[int]bool) - } - files[frame.File][frame.Line] = true - funcs[frame.Func] = true - } - for _, frame := range uncovered { - if !funcs[frame.Func] { - continue - } - if files[frame.File] == nil { - files[frame.File] = make(map[int]bool) - } - if !files[frame.File][frame.Line] { - files[frame.File][frame.Line] = false - } - } - res := make(map[string][]coverage) - for f, lines := range files { - sorted := make([]coverage, 0, len(lines)) - for ln, covered := range lines { - sorted = append(sorted, coverage{ln, covered}) - } - sort.Slice(sorted, func(i, j int) bool { - return sorted[i].line < sorted[j].line - }) - res[f] = sorted - } - return res -} - -func parseFile(fn string) ([][]byte, error) { - data, err := ioutil.ReadFile(fn) - if err != nil { - return nil, err - } - htmlReplacer := strings.NewReplacer(">", ">", "<", "<", "&", "&", "\t", " ") - var lines [][]byte - for { - idx := bytes.IndexByte(data, '\n') - if idx == -1 { - break - } - lines = append(lines, []byte(htmlReplacer.Replace(string(data[:idx])))) - data = data[idx+1:] - } - if len(data) != 0 { - lines = append(lines, data) - } - return lines, nil + return reportGenerator.Do(w, pcs) } func getVMOffset(vmlinux string) (uint32, error) { @@ -235,256 +86,3 @@ func getVMOffset(vmlinux string) (uint32, error) { } return addr, nil } - -// uncoveredPcsInFuncs returns uncovered PCs with __sanitizer_cov_trace_pc calls in functions containing pcs. -func uncoveredPcsInFuncs(vmlinux string, pcs []uint64) ([]uint64, error) { - handledFuncs := make(map[uint64]bool) - uncovered := make(map[uint64]bool) - for _, pc := range pcs { - idx := sort.Search(len(initCoverSymbols), func(i int) bool { - return pc < initCoverSymbols[i].end - }) - if idx == len(initCoverSymbols) { - continue - } - s := initCoverSymbols[idx] - if pc < s.start || pc > s.end { - continue - } - if !handledFuncs[s.start] { - handledFuncs[s.start] = true - startPC := sort.Search(len(initCoverPCs), func(i int) bool { - return s.start <= initCoverPCs[i] - }) - endPC := sort.Search(len(initCoverPCs), func(i int) bool { - return s.end < initCoverPCs[i] - }) - for _, pc1 := range initCoverPCs[startPC:endPC] { - uncovered[pc1] = true - } - } - delete(uncovered, pc) - } - uncoveredPCs := make([]uint64, 0, len(uncovered)) - for pc := range uncovered { - uncoveredPCs = append(uncoveredPCs, pc) - } - return uncoveredPCs, nil -} - -// coveredPCs returns list of PCs of __sanitizer_cov_trace_pc calls in binary bin. -func coveredPCs(arch, bin string) ([]uint64, error) { - cmd := osutil.Command("objdump", "-d", "--no-show-raw-insn", bin) - stdout, err := cmd.StdoutPipe() - if err != nil { - return nil, err - } - defer stdout.Close() - if err := cmd.Start(); err != nil { - return nil, err - } - defer cmd.Wait() - var pcs []uint64 - s := bufio.NewScanner(stdout) - traceFunc := []byte(" <__sanitizer_cov_trace_pc>") - var callInsn []byte - switch arch { - case "amd64": - // ffffffff8100206a: callq ffffffff815cc1d0 <__sanitizer_cov_trace_pc> - callInsn = []byte("\tcallq ") - case "386": - // c1000102: call c10001f0 <__sanitizer_cov_trace_pc> - callInsn = []byte("\tcall ") - case "arm64": - // ffff0000080d9cc0: bl ffff00000820f478 <__sanitizer_cov_trace_pc> - callInsn = []byte("\tbl\t") - case "arm": - // 8010252c: bl 801c3280 <__sanitizer_cov_trace_pc> - callInsn = []byte("\tbl\t") - case "ppc64le": - // c00000000006d904: bl c000000000350780 <.__sanitizer_cov_trace_pc> - callInsn = []byte("\tbl ") - traceFunc = []byte(" <.__sanitizer_cov_trace_pc>") - default: - panic("unknown arch") - } - for s.Scan() { - ln := s.Bytes() - if pos := bytes.Index(ln, callInsn); pos == -1 { - continue - } else if !bytes.Contains(ln[pos:], traceFunc) { - continue - } - colon := bytes.IndexByte(ln, ':') - if colon == -1 { - continue - } - pc, err := strconv.ParseUint(string(ln[:colon]), 16, 64) - if err != nil { - continue - } - pcs = append(pcs, pc) - } - if err := s.Err(); err != nil { - return nil, err - } - return pcs, nil -} - -func symbolize(vmlinux string, pcs []uint64) ([]symbolizer.Frame, string, error) { - symb := symbolizer.NewSymbolizer() - defer symb.Close() - - frames, err := symb.SymbolizeArray(vmlinux, pcs) - if err != nil { - return nil, "", err - } - - prefix := "" - for i := range frames { - frame := &frames[i] - frame.PC-- - if prefix == "" { - prefix = frame.File - } else { - i := 0 - for ; i < len(prefix) && i < len(frame.File); i++ { - if prefix[i] != frame.File[i] { - break - } - } - prefix = prefix[:i] - } - - } - return frames, prefix, nil -} - -func previousInstructionPC(arch string, pc uint64) uint64 { - switch arch { - case "amd64": - return pc - 5 - case "386": - return pc - 1 - case "arm64": - return pc - 4 - case "arm": - // THUMB instructions are 2 or 4 bytes with low bit set. - // ARM instructions are always 4 bytes. - return (pc - 3) & ^uint64(1) - case "ppc64le": - return pc - 4 - default: - panic("unknown arch") - } -} - -type templateData struct { - Files []*templateFile -} - -type templateFile struct { - ID string - Name string - Body template.HTML - Coverage int -} - -type templateFileArray []*templateFile - -func (a templateFileArray) Len() int { return len(a) } -func (a templateFileArray) Less(i, j int) bool { - n1 := a[i].Name - n2 := a[j].Name - // Move include files to the bottom. - if len(n1) != 0 && len(n2) != 0 { - if n1[0] != '.' && n2[0] == '.' { - return true - } - if n1[0] == '.' && n2[0] != '.' { - return false - } - } - return n1 < n2 -} -func (a templateFileArray) Swap(i, j int) { a[i], a[j] = a[j], a[i] } - -var coverTemplate = template.Must(template.New("").Parse(` - - - - - - - -
- -
-
- {{range $i, $f := .Files}} -
{{$f.Body}}
{{end}} -
- - - -`)) diff --git a/syz-manager/html.go b/syz-manager/html.go index 777dcd39b..22c568340 100644 --- a/syz-manager/html.go +++ b/syz-manager/html.go @@ -393,7 +393,8 @@ func (mgr *Manager) httpRawCover(w http.ResponseWriter, r *http.Request) { defer mgr.mu.Unlock() initCoverOnce.Do(func() { - initCoverError = initCover(mgr.cfg.KernelObj, mgr.sysTarget.KernelObject, mgr.cfg.TargetArch) + initCoverError = initCover(mgr.cfg.KernelObj, mgr.sysTarget.KernelObject, + mgr.cfg.KernelSrc, mgr.cfg.TargetArch) }) if initCoverError != nil { http.Error(w, initCoverError.Error(), http.StatusInternalServerError) @@ -407,7 +408,7 @@ func (mgr *Manager) httpRawCover(w http.ResponseWriter, r *http.Request) { pcs := make([]uint64, 0, len(cov)) for pc := range cov { fullPC := cover.RestorePC(pc, initCoverVMOffset) - prevPC := previousInstructionPC(mgr.cfg.TargetVMArch, fullPC) + prevPC := cover.PreviousInstructionPC(mgr.cfg.TargetVMArch, fullPC) pcs = append(pcs, prevPC) } sort.Slice(pcs, func(i, j int) bool { -- cgit mrf-deployment