1/*	$OpenBSD: db_dwarf.c,v 1.7 2017/10/27 08:40:15 mpi Exp $	 */
2/*
3 * Copyright (c) 2014 Matthew Dempsky <matthew@dempsky.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18#ifdef _KERNEL
19#include <sys/param.h>
20#include <sys/systm.h>
21#include <machine/db_machdep.h>
22#include <ddb/db_sym.h>
23#ifdef DIAGNOSTIC
24#define DWARN(fmt, ...) printf("ddb: " fmt "\n", __VA_ARGS__)
25#else
26#define DWARN(fmt, ...) ((void)0)
27#endif
28#else /* _KERNEL */
29#include <err.h>
30#include <stdbool.h>
31#include <stdint.h>
32#include <string.h>
33#define DWARN warnx
34#endif /* _KERNEL */
35
36enum {
37	DW_LNS_copy			= 1,
38	DW_LNS_advance_pc		= 2,
39	DW_LNS_advance_line		= 3,
40	DW_LNS_set_file			= 4,
41	DW_LNS_set_column		= 5,
42	DW_LNS_negate_stmt		= 6,
43	DW_LNS_set_basic_block		= 7,
44	DW_LNS_const_add_pc		= 8,
45	DW_LNS_fixed_advance_pc		= 9,
46	DW_LNS_set_prologue_end		= 10,
47	DW_LNS_set_epilogue_begin	= 11,
48};
49
50enum {
51	DW_LNE_end_sequence		= 1,
52	DW_LNE_set_address		= 2,
53	DW_LNE_define_file		= 3,
54};
55
56struct dwbuf {
57	const char *buf;
58	size_t len;
59};
60
61static inline bool
62read_bytes(struct dwbuf *d, void *v, size_t n)
63{
64	if (d->len < n)
65		return (false);
66	memcpy(v, d->buf, n);
67	d->buf += n;
68	d->len -= n;
69	return (true);
70}
71
72static bool
73read_s8(struct dwbuf *d, int8_t *v)
74{
75	return (read_bytes(d, v, sizeof(*v)));
76}
77
78static bool
79read_u8(struct dwbuf *d, uint8_t *v)
80{
81	return (read_bytes(d, v, sizeof(*v)));
82}
83
84static bool
85read_u16(struct dwbuf *d, uint16_t *v)
86{
87	return (read_bytes(d, v, sizeof(*v)));
88}
89
90static bool
91read_u32(struct dwbuf *d, uint32_t *v)
92{
93	return (read_bytes(d, v, sizeof(*v)));
94}
95
96static bool
97read_u64(struct dwbuf *d, uint64_t *v)
98{
99	return (read_bytes(d, v, sizeof(*v)));
100}
101
102/* Read a DWARF LEB128 (little-endian base-128) value. */
103static bool
104read_leb128(struct dwbuf *d, uint64_t *v, bool signextend)
105{
106	unsigned int shift = 0;
107	uint64_t res = 0;
108	uint8_t x;
109	while (shift < 64 && read_u8(d, &x)) {
110		res |= (uint64_t)(x & 0x7f) << shift;
111		shift += 7;
112		if ((x & 0x80) == 0) {
113			if (signextend && shift < 64 && (x & 0x40) != 0)
114				res |= ~(uint64_t)0 << shift;
115			*v = res;
116			return (true);
117		}
118	}
119	return (false);
120}
121
122static bool
123read_sleb128(struct dwbuf *d, int64_t *v)
124{
125	return (read_leb128(d, (uint64_t *)v, true));
126}
127
128static bool
129read_uleb128(struct dwbuf *d, uint64_t *v)
130{
131	return (read_leb128(d, v, false));
132}
133
134/* Read a NUL terminated string. */
135static bool
136read_string(struct dwbuf *d, const char **s)
137{
138	const char *end = memchr(d->buf, '\0', d->len);
139	if (end == NULL)
140		return (false);
141	size_t n = end - d->buf + 1;
142	*s = d->buf;
143	d->buf += n;
144	d->len -= n;
145	return (true);
146}
147
148static bool
149read_buf(struct dwbuf *d, struct dwbuf *v, size_t n)
150{
151	if (d->len < n)
152		return (false);
153	v->buf = d->buf;
154	v->len = n;
155	d->buf += n;
156	d->len -= n;
157	return (true);
158}
159
160static bool
161skip_bytes(struct dwbuf *d, size_t n)
162{
163	if (d->len < n)
164		return (false);
165	d->buf += n;
166	d->len -= n;
167	return (true);
168}
169
170static bool
171read_filename(struct dwbuf *names, const char **outdirname,
172    const char **outbasename, uint8_t opcode_base, uint64_t file)
173{
174	if (file == 0)
175		return (false);
176
177	/* Skip over opcode table. */
178	size_t i;
179	for (i = 1; i < opcode_base; i++) {
180		uint64_t dummy;
181		if (!read_uleb128(names, &dummy))
182			return (false);
183	}
184
185	/* Skip over directory name table for now. */
186	struct dwbuf dirnames = *names;
187	for (;;) {
188		const char *name;
189		if (!read_string(names, &name))
190			return (false);
191		if (*name == '\0')
192			break;
193	}
194
195	/* Locate file entry. */
196	const char *basename = NULL;
197	uint64_t dir = 0;
198	for (i = 0; i < file; i++) {
199		uint64_t mtime, size;
200		if (!read_string(names, &basename) || *basename == '\0' ||
201		    !read_uleb128(names, &dir) ||
202		    !read_uleb128(names, &mtime) ||
203		    !read_uleb128(names, &size))
204			return (false);
205	}
206
207	const char *dirname = NULL;
208	for (i = 0; i < dir; i++) {
209		if (!read_string(&dirnames, &dirname) || *dirname == '\0')
210			return (false);
211	}
212
213	*outdirname = dirname;
214	*outbasename = basename;
215	return (true);
216}
217
218bool
219db_dwarf_line_at_pc(const char *linetab, size_t linetabsize, uintptr_t pc,
220    const char **outdirname, const char **outbasename, int *outline)
221{
222	struct dwbuf table = { .buf = linetab, .len = linetabsize };
223
224	/*
225	 * For simplicity, we simply brute force search through the entire
226	 * line table each time.
227	 */
228	uint32_t unitsize;
229	struct dwbuf unit;
230next:
231	/* Line tables are a sequence of compilation unit entries. */
232	if (!read_u32(&table, &unitsize) || unitsize >= 0xfffffff0 ||
233	    !read_buf(&table, &unit, unitsize))
234		return (false);
235
236	uint16_t version;
237	uint32_t header_size;
238	if (!read_u16(&unit, &version) || version > 2 ||
239	    !read_u32(&unit, &header_size))
240		goto next;
241
242	struct dwbuf headerstart = unit;
243	uint8_t min_insn_length, default_is_stmt, line_range, opcode_base;
244	int8_t line_base;
245	if (!read_u8(&unit, &min_insn_length) ||
246	    !read_u8(&unit, &default_is_stmt) ||
247	    !read_s8(&unit, &line_base) ||
248	    !read_u8(&unit, &line_range) ||
249	    !read_u8(&unit, &opcode_base))
250		goto next;
251
252	/*
253	 * Directory and file names are next in the header, but for now we
254	 * skip directly to the line number program.
255	 */
256	struct dwbuf names = unit;
257	unit = headerstart;
258	if (!skip_bytes(&unit, header_size))
259		return (false);
260
261	/* VM registers. */
262	uint64_t address = 0, file = 1, line = 1, column = 0;
263	uint8_t is_stmt = default_is_stmt;
264	bool basic_block = false, end_sequence = false;
265	bool prologue_end = false, epilogue_begin = false;
266
267	/* Last line table entry emitted, if any. */
268	bool have_last = false;
269	uint64_t last_line = 0, last_file = 0;
270
271	/* Time to run the line program. */
272	uint8_t opcode;
273	while (read_u8(&unit, &opcode)) {
274		bool emit = false, reset_basic_block = false;
275
276		if (opcode >= opcode_base) {
277			/* "Special" opcodes. */
278			uint8_t diff = opcode - opcode_base;
279			address += diff / line_range;
280			line += line_base + diff % line_range;
281			emit = true;
282		} else if (opcode == 0) {
283			/* "Extended" opcodes. */
284			uint64_t extsize;
285			struct dwbuf extra;
286			if (!read_uleb128(&unit, &extsize) ||
287			    !read_buf(&unit, &extra, extsize) ||
288			    !read_u8(&extra, &opcode))
289				goto next;
290			switch (opcode) {
291			case DW_LNE_end_sequence:
292				emit = true;
293				end_sequence = true;
294				break;
295			case DW_LNE_set_address:
296				switch (extra.len) {
297				case 4: {
298					uint32_t address32;
299					if (!read_u32(&extra, &address32))
300						goto next;
301					address = address32;
302					break;
303				}
304				case 8:
305					if (!read_u64(&extra, &address))
306						goto next;
307					break;
308				default:
309					DWARN("unexpected address length: %zu",
310					    extra.len);
311					goto next;
312				}
313				break;
314			case DW_LNE_define_file:
315				/* XXX: hope this isn't needed */
316			default:
317				DWARN("unknown extended opcode: %d", opcode);
318				goto next;
319			}
320		} else {
321			/* "Standard" opcodes. */
322			switch (opcode) {
323			case DW_LNS_copy:
324				emit = true;
325				reset_basic_block = true;
326				break;
327			case DW_LNS_advance_pc: {
328				uint64_t delta;
329				if (!read_uleb128(&unit, &delta))
330					goto next;
331				address += delta * min_insn_length;
332				break;
333			}
334			case DW_LNS_advance_line: {
335				int64_t delta;
336				if (!read_sleb128(&unit, &delta))
337					goto next;
338				line += delta;
339				break;
340			}
341			case DW_LNS_set_file:
342				if (!read_uleb128(&unit, &file))
343					goto next;
344				break;
345			case DW_LNS_set_column:
346				if (!read_uleb128(&unit, &column))
347					goto next;
348				break;
349			case DW_LNS_negate_stmt:
350				is_stmt = !is_stmt;
351				break;
352			case DW_LNS_set_basic_block:
353				basic_block = true;
354				break;
355			case DW_LNS_const_add_pc:
356				address += (255 - opcode_base) / line_range;
357				break;
358			case DW_LNS_set_prologue_end:
359				prologue_end = true;
360				break;
361			case DW_LNS_set_epilogue_begin:
362				epilogue_begin = true;
363				break;
364			default:
365				DWARN("unknown standard opcode: %d", opcode);
366				goto next;
367			}
368		}
369
370		if (emit) {
371			if (address > pc) {
372				/* Found an entry after our target PC. */
373				if (!have_last) {
374					/* Give up on this program. */
375					break;
376				}
377				/* Return the last entry. */
378				*outline = last_line;
379				return (read_filename(&names, outdirname,
380				    outbasename, opcode_base, last_file));
381			}
382
383			last_file = file;
384			last_line = line;
385			have_last = true;
386		}
387
388		if (reset_basic_block)
389			basic_block = false;
390	}
391
392	goto next;
393}
394
395#ifndef _KERNEL
396#include <sys/endian.h>
397#include <sys/mman.h>
398#include <sys/stat.h>
399#include <elf.h>
400#include <fcntl.h>
401#include <stdio.h>
402#include <stdlib.h>
403#include <unistd.h>
404
405#ifndef ELFDATA
406#if BYTE_ORDER == LITTLE_ENDIAN
407#define ELFDATA ELFDATA2LSB
408#elif BYTE_ORDER == BIG_ENDIAN
409#define ELFDATA ELFDATA2MSB
410#else
411#error Unsupported byte order
412#endif
413#endif /* !ELFDATA */
414
415static void
416usage(void)
417{
418	extern const char *__progname;
419	errx(1, "usage: %s [-s] [-e filename] [addr addr ...]", __progname);
420}
421
422/*
423 * Basic addr2line clone for stand-alone testing.
424 */
425int
426main(int argc, char *argv[])
427{
428	const char *filename = "a.out";
429
430	int ch;
431	bool showdir = true;
432	while ((ch = getopt(argc, argv, "e:s")) != EOF) {
433		switch (ch) {
434		case 'e':
435			filename = optarg;
436			break;
437		case 's':
438			showdir = false;
439			break;
440		default:
441			usage();
442		}
443	}
444
445	argc -= optind;
446	argv += optind;
447
448	/* Start by mapping the full file into memory. */
449	int fd = open(filename, O_RDONLY);
450	if (fd == -1)
451		err(1, "open");
452
453	struct stat st;
454	if (fstat(fd, &st) == -1)
455		err(1, "fstat");
456	if (st.st_size < (off_t)sizeof(Elf_Ehdr))
457		errx(1, "file too small to be ELF");
458	if ((uintmax_t)st.st_size > SIZE_MAX)
459		errx(1, "file too big to fit memory");
460	size_t filesize = st.st_size;
461
462	const char *p = mmap(NULL, filesize, PROT_READ, MAP_SHARED, fd, 0);
463	if (p == MAP_FAILED)
464		err(1, "mmap");
465
466	close(fd);
467
468	/* Read and validate ELF header. */
469	Elf_Ehdr ehdr;
470	memcpy(&ehdr, p, sizeof(ehdr));
471	if (!IS_ELF(ehdr))
472		errx(1, "file is not ELF");
473	if (ehdr.e_ident[EI_CLASS] != ELFCLASS)
474		errx(1, "unexpected word size");
475	if (ehdr.e_ident[EI_DATA] != ELFDATA)
476		errx(1, "unexpected data format");
477	if (ehdr.e_shoff > filesize)
478		errx(1, "bogus section table offset");
479	if (ehdr.e_shentsize < sizeof(Elf_Shdr))
480		errx(1, "unexpected section header size");
481	if (ehdr.e_shnum > (filesize - ehdr.e_shoff) / ehdr.e_shentsize)
482		errx(1, "bogus section header count");
483	if (ehdr.e_shstrndx >= ehdr.e_shnum)
484		errx(1, "bogus string table index");
485
486	/* Find section header string table location and size. */
487	Elf_Shdr shdr;
488	memcpy(&shdr, p + ehdr.e_shoff + ehdr.e_shstrndx * ehdr.e_shentsize,
489	    sizeof(shdr));
490	if (shdr.sh_type != SHT_STRTAB)
491		errx(1, "unexpected string table type");
492	if (shdr.sh_offset > filesize)
493		errx(1, "bogus string table offset");
494	if (shdr.sh_size > filesize - shdr.sh_offset)
495		errx(1, "bogus string table size");
496	const char *shstrtab = p + shdr.sh_offset;
497	size_t shstrtabsize = shdr.sh_size;
498
499	/* Search through section table for .debug_line section. */
500	size_t i;
501	for (i = 0; i < ehdr.e_shnum; i++) {
502		memcpy(&shdr, p + ehdr.e_shoff + i * ehdr.e_shentsize,
503		    sizeof(shdr));
504		if (0 == strncmp(".debug_line", shstrtab + shdr.sh_name,
505		    shstrtabsize - shdr.sh_name))
506			break;
507	}
508	if (i == ehdr.e_shnum)
509		errx(1, "no DWARF line number table found");
510	if (shdr.sh_offset > filesize)
511		errx(1, "bogus line table offset");
512	if (shdr.sh_size > filesize - shdr.sh_offset)
513		errx(1, "bogus line table size");
514	const char *linetab = p + shdr.sh_offset;
515	size_t linetabsize = shdr.sh_size;
516
517	const char *addrstr;
518	while ((addrstr = *argv++) != NULL) {
519		unsigned long addr = strtoul(addrstr, NULL, 16);
520
521		const char *dir, *file;
522		int line;
523		if (!db_dwarf_line_at_pc(linetab, linetabsize, addr,
524		    &dir, &file, &line)) {
525			dir = NULL;
526			file = "??";
527			line = 0;
528		}
529		if (showdir && dir != NULL)
530			printf("%s/", dir);
531		printf("%s:%d\n", file, line);
532	}
533
534	return (0);
535}
536#endif /* !_KERNEL */
537