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