1// Copyright 2015 syzkaller project authors. All rights reserved.
2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
3
4package main
5
6import (
7	"bufio"
8	"bytes"
9	"fmt"
10	"html/template"
11	"io"
12	"io/ioutil"
13	"path/filepath"
14	"sort"
15	"strconv"
16	"strings"
17	"sync"
18	"time"
19
20	"github.com/google/syzkaller/pkg/cover"
21	"github.com/google/syzkaller/pkg/hash"
22	"github.com/google/syzkaller/pkg/osutil"
23	"github.com/google/syzkaller/pkg/symbolizer"
24)
25
26type symbol struct {
27	start uint64
28	end   uint64
29	name  string
30}
31
32type coverage struct {
33	line    int
34	covered bool
35}
36
37var (
38	initCoverOnce     sync.Once
39	initCoverError    error
40	initCoverSymbols  []symbol
41	initCoverPCs      []uint64
42	initCoverVMOffset uint32
43)
44
45func initCover(kernelObj, arch string) error {
46	if kernelObj == "" {
47		return fmt.Errorf("kernel_obj is not specified")
48	}
49	vmlinux := filepath.Join(kernelObj, "vmlinux")
50	symbols, err := symbolizer.ReadSymbols(vmlinux)
51	if err != nil {
52		return fmt.Errorf("failed to run nm on %v: %v", vmlinux, err)
53	}
54	for name, ss := range symbols {
55		for _, s := range ss {
56			initCoverSymbols = append(initCoverSymbols, symbol{s.Addr, s.Addr + uint64(s.Size), name})
57		}
58	}
59	sort.Slice(initCoverSymbols, func(i, j int) bool {
60		return initCoverSymbols[i].start < initCoverSymbols[j].start
61	})
62	initCoverPCs, err = coveredPCs(arch, vmlinux)
63	if err != nil {
64		return fmt.Errorf("failed to run objdump on %v: %v", vmlinux, err)
65	}
66	sort.Slice(initCoverPCs, func(i, j int) bool {
67		return initCoverPCs[i] < initCoverPCs[j]
68	})
69	initCoverVMOffset, err = getVMOffset(vmlinux)
70	return err
71}
72
73func generateCoverHTML(w io.Writer, kernelObj, kernelSrc, arch string, cov cover.Cover) error {
74	if len(cov) == 0 {
75		return fmt.Errorf("no coverage data available")
76	}
77	initCoverOnce.Do(func() { initCoverError = initCover(kernelObj, arch) })
78	if initCoverError != nil {
79		return initCoverError
80	}
81
82	pcs := make([]uint64, 0, len(cov))
83	for pc := range cov {
84		fullPC := cover.RestorePC(pc, initCoverVMOffset)
85		prevPC := previousInstructionPC(arch, fullPC)
86		pcs = append(pcs, prevPC)
87	}
88	vmlinux := filepath.Join(kernelObj, "vmlinux")
89	uncovered, err := uncoveredPcsInFuncs(vmlinux, pcs)
90	if err != nil {
91		return err
92	}
93
94	coveredFrames, _, err := symbolize(vmlinux, pcs)
95	if err != nil {
96		return err
97	}
98	if len(coveredFrames) == 0 {
99		return fmt.Errorf("'%s' does not have debug info (set CONFIG_DEBUG_INFO=y)", vmlinux)
100	}
101
102	uncoveredFrames, prefix, err := symbolize(vmlinux, uncovered)
103	if err != nil {
104		return err
105	}
106
107	var d templateData
108	for f, covered := range fileSet(coveredFrames, uncoveredFrames) {
109		remain := strings.TrimPrefix(f, prefix)
110		if kernelSrc != "" {
111			f = filepath.Join(kernelSrc, remain)
112		}
113		lines, err := parseFile(f)
114		if err != nil {
115			return err
116		}
117		coverage := 0
118		var buf bytes.Buffer
119		for i, ln := range lines {
120			if len(covered) > 0 && covered[0].line == i+1 {
121				if covered[0].covered {
122					buf.Write([]byte("<span id='covered'>"))
123					buf.Write(ln)
124					buf.Write([]byte("</span> /*covered*/\n"))
125					coverage++
126				} else {
127					buf.Write([]byte("<span id='uncovered'>"))
128					buf.Write(ln)
129					buf.Write([]byte("</span>\n"))
130				}
131				covered = covered[1:]
132			} else {
133				buf.Write(ln)
134				buf.Write([]byte{'\n'})
135			}
136		}
137		f = filepath.Clean(remain)
138		d.Files = append(d.Files, &templateFile{
139			ID:       hash.String([]byte(f)),
140			Name:     f,
141			Body:     template.HTML(buf.String()),
142			Coverage: coverage,
143		})
144	}
145
146	sort.Sort(templateFileArray(d.Files))
147	return coverTemplate.Execute(w, d)
148}
149
150func fileSet(covered, uncovered []symbolizer.Frame) map[string][]coverage {
151	files := make(map[string]map[int]bool)
152	funcs := make(map[string]bool)
153	for _, frame := range covered {
154		if files[frame.File] == nil {
155			files[frame.File] = make(map[int]bool)
156		}
157		files[frame.File][frame.Line] = true
158		funcs[frame.Func] = true
159	}
160	for _, frame := range uncovered {
161		if !funcs[frame.Func] {
162			continue
163		}
164		if files[frame.File] == nil {
165			files[frame.File] = make(map[int]bool)
166		}
167		if !files[frame.File][frame.Line] {
168			files[frame.File][frame.Line] = false
169		}
170	}
171	res := make(map[string][]coverage)
172	for f, lines := range files {
173		sorted := make([]coverage, 0, len(lines))
174		for ln, covered := range lines {
175			sorted = append(sorted, coverage{ln, covered})
176		}
177		sort.Slice(sorted, func(i, j int) bool {
178			return sorted[i].line < sorted[j].line
179		})
180		res[f] = sorted
181	}
182	return res
183}
184
185func parseFile(fn string) ([][]byte, error) {
186	data, err := ioutil.ReadFile(fn)
187	if err != nil {
188		return nil, err
189	}
190	htmlReplacer := strings.NewReplacer(">", "&gt;", "<", "&lt;", "&", "&amp;", "\t", "        ")
191	var lines [][]byte
192	for {
193		idx := bytes.IndexByte(data, '\n')
194		if idx == -1 {
195			break
196		}
197		lines = append(lines, []byte(htmlReplacer.Replace(string(data[:idx]))))
198		data = data[idx+1:]
199	}
200	if len(data) != 0 {
201		lines = append(lines, data)
202	}
203	return lines, nil
204}
205
206func getVMOffset(vmlinux string) (uint32, error) {
207	out, err := osutil.RunCmd(time.Hour, "", "readelf", "-SW", vmlinux)
208	if err != nil {
209		return 0, err
210	}
211	s := bufio.NewScanner(bytes.NewReader(out))
212	var addr uint32
213	for s.Scan() {
214		ln := s.Text()
215		pieces := strings.Fields(ln)
216		for i := 0; i < len(pieces); i++ {
217			if pieces[i] != "PROGBITS" {
218				continue
219			}
220			v, err := strconv.ParseUint("0x"+pieces[i+1], 0, 64)
221			if err != nil {
222				return 0, fmt.Errorf("failed to parse addr in readelf output: %v", err)
223			}
224			if v == 0 {
225				continue
226			}
227			v32 := (uint32)(v >> 32)
228			if addr == 0 {
229				addr = v32
230			}
231			if addr != v32 {
232				return 0, fmt.Errorf("different section offsets in a single binary")
233			}
234		}
235	}
236	return addr, nil
237}
238
239// uncoveredPcsInFuncs returns uncovered PCs with __sanitizer_cov_trace_pc calls in functions containing pcs.
240func uncoveredPcsInFuncs(vmlinux string, pcs []uint64) ([]uint64, error) {
241	handledFuncs := make(map[uint64]bool)
242	uncovered := make(map[uint64]bool)
243	for _, pc := range pcs {
244		idx := sort.Search(len(initCoverSymbols), func(i int) bool {
245			return pc < initCoverSymbols[i].end
246		})
247		if idx == len(initCoverSymbols) {
248			continue
249		}
250		s := initCoverSymbols[idx]
251		if pc < s.start || pc > s.end {
252			continue
253		}
254		if !handledFuncs[s.start] {
255			handledFuncs[s.start] = true
256			startPC := sort.Search(len(initCoverPCs), func(i int) bool {
257				return s.start <= initCoverPCs[i]
258			})
259			endPC := sort.Search(len(initCoverPCs), func(i int) bool {
260				return s.end < initCoverPCs[i]
261			})
262			for _, pc1 := range initCoverPCs[startPC:endPC] {
263				uncovered[pc1] = true
264			}
265		}
266		delete(uncovered, pc)
267	}
268	uncoveredPCs := make([]uint64, 0, len(uncovered))
269	for pc := range uncovered {
270		uncoveredPCs = append(uncoveredPCs, pc)
271	}
272	return uncoveredPCs, nil
273}
274
275// coveredPCs returns list of PCs of __sanitizer_cov_trace_pc calls in binary bin.
276func coveredPCs(arch, bin string) ([]uint64, error) {
277	cmd := osutil.Command("objdump", "-d", "--no-show-raw-insn", bin)
278	stdout, err := cmd.StdoutPipe()
279	if err != nil {
280		return nil, err
281	}
282	defer stdout.Close()
283	if err := cmd.Start(); err != nil {
284		return nil, err
285	}
286	defer cmd.Wait()
287	var pcs []uint64
288	s := bufio.NewScanner(stdout)
289	traceFunc := []byte(" <__sanitizer_cov_trace_pc>")
290	var callInsn []byte
291	switch arch {
292	case "amd64":
293		// ffffffff8100206a:       callq  ffffffff815cc1d0 <__sanitizer_cov_trace_pc>
294		callInsn = []byte("\tcallq ")
295	case "386":
296		// c1000102:       call   c10001f0 <__sanitizer_cov_trace_pc>
297		callInsn = []byte("\tcall ")
298	case "arm64":
299		// ffff0000080d9cc0:       bl      ffff00000820f478 <__sanitizer_cov_trace_pc>
300		callInsn = []byte("\tbl\t")
301	case "arm":
302		// 8010252c:       bl      801c3280 <__sanitizer_cov_trace_pc>
303		callInsn = []byte("\tbl\t")
304	case "ppc64le":
305		// c00000000006d904:       bl      c000000000350780 <.__sanitizer_cov_trace_pc>
306		callInsn = []byte("\tbl ")
307		traceFunc = []byte(" <.__sanitizer_cov_trace_pc>")
308	default:
309		panic("unknown arch")
310	}
311	for s.Scan() {
312		ln := s.Bytes()
313		if pos := bytes.Index(ln, callInsn); pos == -1 {
314			continue
315		} else if !bytes.Contains(ln[pos:], traceFunc) {
316			continue
317		}
318		colon := bytes.IndexByte(ln, ':')
319		if colon == -1 {
320			continue
321		}
322		pc, err := strconv.ParseUint(string(ln[:colon]), 16, 64)
323		if err != nil {
324			continue
325		}
326		pcs = append(pcs, pc)
327	}
328	if err := s.Err(); err != nil {
329		return nil, err
330	}
331	return pcs, nil
332}
333
334func symbolize(vmlinux string, pcs []uint64) ([]symbolizer.Frame, string, error) {
335	symb := symbolizer.NewSymbolizer()
336	defer symb.Close()
337
338	frames, err := symb.SymbolizeArray(vmlinux, pcs)
339	if err != nil {
340		return nil, "", err
341	}
342
343	prefix := ""
344	for i := range frames {
345		frame := &frames[i]
346		frame.PC--
347		if prefix == "" {
348			prefix = frame.File
349		} else {
350			i := 0
351			for ; i < len(prefix) && i < len(frame.File); i++ {
352				if prefix[i] != frame.File[i] {
353					break
354				}
355			}
356			prefix = prefix[:i]
357		}
358
359	}
360	return frames, prefix, nil
361}
362
363func previousInstructionPC(arch string, pc uint64) uint64 {
364	switch arch {
365	case "amd64":
366		return pc - 5
367	case "386":
368		return pc - 1
369	case "arm64":
370		return pc - 4
371	case "arm":
372		// THUMB instructions are 2 or 4 bytes with low bit set.
373		// ARM instructions are always 4 bytes.
374		return (pc - 3) & ^uint64(1)
375	case "ppc64le":
376		return pc - 4
377	default:
378		panic("unknown arch")
379	}
380}
381
382type templateData struct {
383	Files []*templateFile
384}
385
386type templateFile struct {
387	ID       string
388	Name     string
389	Body     template.HTML
390	Coverage int
391}
392
393type templateFileArray []*templateFile
394
395func (a templateFileArray) Len() int { return len(a) }
396func (a templateFileArray) Less(i, j int) bool {
397	n1 := a[i].Name
398	n2 := a[j].Name
399	// Move include files to the bottom.
400	if len(n1) != 0 && len(n2) != 0 {
401		if n1[0] != '.' && n2[0] == '.' {
402			return true
403		}
404		if n1[0] == '.' && n2[0] != '.' {
405			return false
406		}
407	}
408	return n1 < n2
409}
410func (a templateFileArray) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
411
412var coverTemplate = template.Must(template.New("").Parse(`
413<!DOCTYPE html>
414<html>
415	<head>
416		<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
417		<style>
418			body {
419				background: white;
420			}
421			#topbar {
422				background: black;
423				position: fixed;
424				top: 0; left: 0; right: 0;
425				height: 42px;
426				border-bottom: 1px solid rgb(70, 70, 70);
427			}
428			#nav {
429				float: left;
430				margin-left: 10px;
431				margin-top: 10px;
432			}
433			#content {
434				font-family: 'Courier New', Courier, monospace;
435				color: rgb(70, 70, 70);
436				margin-top: 50px;
437			}
438			#covered {
439				color: rgb(0, 0, 0);
440				font-weight: bold;
441			}
442			#uncovered {
443				color: rgb(255, 0, 0);
444				font-weight: bold;
445			}
446		</style>
447	</head>
448	<body>
449		<div id="topbar">
450			<div id="nav">
451				<select id="files">
452				{{range $f := .Files}}
453				<option value="{{$f.ID}}">{{$f.Name}} ({{$f.Coverage}})</option>
454				{{end}}
455				</select>
456			</div>
457		</div>
458		<div id="content">
459		{{range $i, $f := .Files}}
460		<pre class="file" id="{{$f.ID}}" {{if $i}}style="display: none;"{{end}}>{{$f.Body}}</pre>{{end}}
461		</div>
462	</body>
463	<script>
464	(function() {
465		var files = document.getElementById('files');
466		var visible = document.getElementById(files.value);
467		if (window.location.hash) {
468			var hash = window.location.hash.substring(1);
469			for (var i = 0; i < files.options.length; i++) {
470				if (files.options[i].value === hash) {
471					files.selectedIndex = i;
472					visible.style.display = 'none';
473					visible = document.getElementById(files.value);
474					visible.style.display = 'block';
475					break;
476				}
477			}
478		}
479		files.addEventListener('change', onChange, false);
480		function onChange() {
481			visible.style.display = 'none';
482			visible = document.getElementById(files.value);
483			visible.style.display = 'block';
484			window.scrollTo(0, 0);
485			window.location.hash = files.value;
486		}
487	})();
488	</script>
489</html>
490`))
491