blob: 6bf7e0a6ffd96735b502ec2ef55c94f7009f0b45 [file] [log] [blame]
// 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 (
"fmt"
"sort"
"github.com/google/syzkaller/pkg/cover/backend"
"github.com/google/syzkaller/pkg/host"
"github.com/google/syzkaller/pkg/mgrconfig"
"github.com/google/syzkaller/sys/targets"
)
type ReportGenerator struct {
target *targets.Target
srcDir string
buildDir string
subsystem []mgrconfig.Subsystem
rawCoverEnabled bool
*backend.Impl
}
type Prog struct {
Sig string
Data string
PCs []uint64
}
var RestorePC = backend.RestorePC
func MakeReportGenerator(cfg *mgrconfig.Config, subsystem []mgrconfig.Subsystem,
modules []host.KernelModule, rawCover bool) (*ReportGenerator, error) {
impl, err := backend.Make(cfg.SysTarget, cfg.Type, cfg.KernelObj,
cfg.KernelSrc, cfg.KernelBuildSrc, cfg.AndroidSplitBuild, cfg.ModuleObj, modules)
if err != nil {
return nil, err
}
subsystem = append(subsystem, mgrconfig.Subsystem{
Name: "all",
Paths: []string{""},
})
rg := &ReportGenerator{
target: cfg.SysTarget,
srcDir: cfg.KernelSrc,
buildDir: cfg.KernelBuildSrc,
subsystem: subsystem,
rawCoverEnabled: rawCover,
Impl: impl,
}
return rg, nil
}
type file struct {
module string
filename string
lines map[int]line
functions []*function
covered []backend.Range
uncovered []backend.Range
totalPCs int
coveredPCs int
}
type function struct {
name string
pcs int
covered int
}
type line struct {
progCount map[int]bool // program indices that cover this line
progIndex int // example program index that covers this line
}
func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error) {
if err := rg.lazySymbolize(progs); err != nil {
return nil, err
}
files := make(map[string]*file)
for _, unit := range rg.Units {
files[unit.Name] = &file{
module: unit.Module.Name,
filename: unit.Path,
lines: make(map[int]line),
totalPCs: len(unit.PCs),
}
}
progPCs := make(map[uint64]map[int]bool)
unmatchedProgPCs := make(map[uint64]bool)
verifyCoverPoints := (len(rg.CoverPoints) > 0)
for i, prog := range progs {
for _, pc := range prog.PCs {
if progPCs[pc] == nil {
progPCs[pc] = make(map[int]bool)
}
progPCs[pc][i] = true
if verifyCoverPoints && !rg.CoverPoints[pc] {
unmatchedProgPCs[pc] = true
}
}
}
matchedPC := false
for _, frame := range rg.Frames {
f := getFile(files, frame.Name, frame.Path, frame.Module.Name)
ln := f.lines[frame.StartLine]
coveredBy := progPCs[frame.PC]
if len(coveredBy) == 0 {
f.uncovered = append(f.uncovered, frame.Range)
continue
}
// Covered frame.
f.covered = append(f.covered, frame.Range)
matchedPC = true
if ln.progCount == nil {
ln.progCount = make(map[int]bool)
ln.progIndex = -1
}
for progIndex := range coveredBy {
ln.progCount[progIndex] = true
if ln.progIndex == -1 || len(progs[progIndex].Data) < len(progs[ln.progIndex].Data) {
ln.progIndex = progIndex
}
}
f.lines[frame.StartLine] = ln
}
if !matchedPC {
return nil, fmt.Errorf("coverage doesn't match any coverage callbacks")
}
// If the backend provided coverage callback locations for the binaries, use them to
// verify data returned by kcov.
if verifyCoverPoints && (len(unmatchedProgPCs) > 0) {
return nil, fmt.Errorf("%d out of %d PCs returned by kcov do not have matching "+
"coverage callbacks. Check the discoverModules() code",
len(unmatchedProgPCs), len(progPCs))
}
for _, unit := range rg.Units {
f := files[unit.Name]
for _, pc := range unit.PCs {
if progPCs[pc] != nil {
f.coveredPCs++
}
}
}
for _, s := range rg.Symbols {
fun := &function{
name: s.Name,
pcs: len(s.PCs),
}
for _, pc := range s.PCs {
if progPCs[pc] != nil {
fun.covered++
}
}
f := files[s.Unit.Name]
f.functions = append(f.functions, fun)
}
for _, f := range files {
sort.Slice(f.functions, func(i, j int) bool {
return f.functions[i].name < f.functions[j].name
})
}
return files, nil
}
func (rg *ReportGenerator) lazySymbolize(progs []Prog) error {
if len(rg.Symbols) == 0 {
return nil
}
symbolize := make(map[*backend.Symbol]bool)
uniquePCs := make(map[uint64]bool)
pcs := make(map[*backend.Module][]uint64)
for _, prog := range progs {
for _, pc := range prog.PCs {
if uniquePCs[pc] {
continue
}
uniquePCs[pc] = true
sym := rg.findSymbol(pc)
if sym == nil || (sym.Symbolized || symbolize[sym]) {
continue
}
symbolize[sym] = true
pcs[sym.Module] = append(pcs[sym.Module], sym.PCs...)
}
}
if len(uniquePCs) == 0 {
return fmt.Errorf("no coverage collected so far")
}
frames, err := rg.Symbolize(pcs)
if err != nil {
return err
}
rg.Frames = append(rg.Frames, frames...)
for sym := range symbolize {
sym.Symbolized = true
}
return nil
}
func getFile(files map[string]*file, name, path, module string) *file {
f := files[name]
if f == nil {
f = &file{
module: module,
filename: path,
lines: make(map[int]line),
// Special mark for header files, if a file does not have coverage at all it is not shown.
totalPCs: 1,
coveredPCs: 1,
}
files[name] = f
}
return f
}
func (rg *ReportGenerator) findSymbol(pc uint64) *backend.Symbol {
idx := sort.Search(len(rg.Symbols), func(i int) bool {
return pc < rg.Symbols[i].End
})
if idx == len(rg.Symbols) {
return nil
}
s := rg.Symbols[idx]
if pc < s.Start || pc > s.End {
return nil
}
return s
}