/*	$OpenBSD: db_dwarf.c,v 1.1 2014/07/11 03:17:20 matthew Exp $	 */
/*
 * Copyright (c) 2014 Matthew Dempsky <matthew@dempsky.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifdef _KERNEL
#include <sys/param.h>
#include <sys/stdint.h>
#include <sys/systm.h>  
#include <sys/types.h>
#include <ddb/db_dwarf.h>
#ifdef DIAGNOSTIC
#define DWARN(fmt, ...) printf("ddb: " fmt "\n", __VA_ARGS__)
#else
#define DWARN(fmt, ...) ((void)0)
#endif
#else /* _KERNEL */
#include <err.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#define DWARN warnx
#endif /* _KERNEL */

enum {
	DW_LNS_copy			= 1,
	DW_LNS_advance_pc		= 2,
	DW_LNS_advance_line		= 3,
	DW_LNS_set_file			= 4,
	DW_LNS_set_column		= 5,
	DW_LNS_negate_stmt		= 6,
	DW_LNS_set_basic_block		= 7,
	DW_LNS_const_add_pc		= 8,
	DW_LNS_fixed_advance_pc		= 9,
	DW_LNS_set_prologue_end		= 10,
	DW_LNS_set_epilogue_begin	= 11,
};

enum {
	DW_LNE_end_sequence		= 1,
	DW_LNE_set_address		= 2,
	DW_LNE_define_file		= 3,
};

struct dwbuf {
	const char *buf;
	size_t len;
};

static inline bool
read_bytes(struct dwbuf *d, void *v, size_t n)
{
	if (d->len < n)
		return (false);
	memcpy(v, d->buf, n);
	d->buf += n;
	d->len -= n;
	return (true);
}

static bool
read_s8(struct dwbuf *d, int8_t *v)
{
	return (read_bytes(d, v, sizeof(*v)));
}

static bool
read_u8(struct dwbuf *d, uint8_t *v)
{
	return (read_bytes(d, v, sizeof(*v)));
}

static bool
read_u16(struct dwbuf *d, uint16_t *v)
{
	return (read_bytes(d, v, sizeof(*v)));
}

static bool
read_u32(struct dwbuf *d, uint32_t *v)
{
	return (read_bytes(d, v, sizeof(*v)));
}

static bool
read_u64(struct dwbuf *d, uint64_t *v)
{
	return (read_bytes(d, v, sizeof(*v)));
}

/* Read a DWARF LEB128 (little-endian base-128) value. */
static bool
read_leb128(struct dwbuf *d, uint64_t *v, bool signextend)
{
	unsigned int shift = 0;
	uint64_t res = 0;
	uint8_t x;
	while (shift < 64 && read_u8(d, &x)) {
		res |= (uint64_t)(x & 0x7f) << shift;
		shift += 7;
		if ((x & 0x80) == 0) {
			if (signextend && shift < 64 && (x & 0x40) != 0)
				res |= ~(uint64_t)0 << shift;
			*v = res;
			return (true);
		}
	}
	return (false);
}

static bool
read_sleb128(struct dwbuf *d, int64_t *v)
{
	return (read_leb128(d, (uint64_t *)v, true));
}

static bool
read_uleb128(struct dwbuf *d, uint64_t *v)
{
	return (read_leb128(d, v, false));
}

/* Read a NUL terminated string. */
static bool
read_string(struct dwbuf *d, const char **s)
{
	const char *end = memchr(d->buf, '\0', d->len);
	if (end == NULL)
		return (false);
	size_t n = end - d->buf + 1;
	*s = d->buf;
	d->buf += n;
	d->len -= n;
	return (true);
}

static bool
read_buf(struct dwbuf *d, struct dwbuf *v, size_t n)
{
	if (d->len < n)
		return (false);
	v->buf = d->buf;
	v->len = n;
	d->buf += n;
	d->len -= n;
	return (true);
}

static bool
skip_bytes(struct dwbuf *d, size_t n)
{
	if (d->len < n)
		return (false);
	d->buf += n;
	d->len -= n;
	return (true);
}

static bool
read_filename(struct dwbuf *names, const char **outdirname,
    const char **outbasename, uint8_t opcode_base, uint64_t file)
{
	if (file == 0)
		return (false);

	/* Skip over opcode table. */
	size_t i;
	for (i = 1; i < opcode_base; i++) {
		uint64_t dummy;
		if (!read_uleb128(names, &dummy))
			return (false);
	}

	/* Skip over directory name table for now. */
	struct dwbuf dirnames = *names;
	for (;;) {
		const char *name;
		if (!read_string(names, &name))
			return (false);
		if (*name == '\0')
			break;
	}

	/* Locate file entry. */
	const char *basename = NULL;
	uint64_t dir = 0;
	for (i = 0; i < file; i++) {
		uint64_t mtime, size;
		if (!read_string(names, &basename) || *basename == '\0' ||
		    !read_uleb128(names, &dir) ||
		    !read_uleb128(names, &mtime) ||
		    !read_uleb128(names, &size))
			return (false);
	}

	const char *dirname = NULL;
	for (i = 0; i < dir; i++) {
		if (!read_string(&dirnames, &dirname) || *dirname == '\0')
			return (false);
	}

	*outdirname = dirname;
	*outbasename = basename;
	return (true);
}

bool
db_dwarf_line_at_pc(const char *linetab, size_t linetabsize, uintptr_t pc,
    const char **outdirname, const char **outbasename, int *outline)
{
	struct dwbuf table = { .buf = linetab, .len = linetabsize };

	/*
	 * For simplicity, we simply brute force search through the entire
	 * line table each time.
	 */
	uint32_t unitsize;
	struct dwbuf unit;
next:
	/* Line tables are a sequence of compilation unit entries. */
	if (!read_u32(&table, &unitsize) || unitsize >= 0xfffffff0 ||
	    !read_buf(&table, &unit, unitsize))
		return (false);

	uint16_t version;
	uint32_t header_size;
	if (!read_u16(&unit, &version) || version > 2 ||
	    !read_u32(&unit, &header_size))
		goto next;

	struct dwbuf headerstart = unit;
	uint8_t min_insn_length, default_is_stmt, line_range, opcode_base;
	int8_t line_base;
	if (!read_u8(&unit, &min_insn_length) ||
	    !read_u8(&unit, &default_is_stmt) ||
	    !read_s8(&unit, &line_base) ||
	    !read_u8(&unit, &line_range) ||
	    !read_u8(&unit, &opcode_base))
		goto next;

	/*
	 * Directory and file names are next in the header, but for now we
	 * skip directly to the line number program.
	 */
	struct dwbuf names = unit;
	unit = headerstart;
	if (!skip_bytes(&unit, header_size))
		return (false);

	/* VM registers. */
	uint64_t address = 0, file = 1, line = 1, column = 0;
	uint8_t is_stmt = default_is_stmt;
	bool basic_block = false, end_sequence = false;
	bool prologue_end = false, epilogue_begin = false;

	/* Last line table entry emitted, if any. */
	bool have_last = false;
	uint64_t last_line = 0, last_file = 0;

	/* Time to run the line program. */
	uint8_t opcode;
	while (read_u8(&unit, &opcode)) {
		bool emit = false, reset_basic_block = false;

		if (opcode >= opcode_base) {
			/* "Special" opcodes. */
			uint8_t diff = opcode - opcode_base;
			address += diff / line_range;
			line += line_base + diff % line_range;
			emit = true;
		} else if (opcode == 0) {
			/* "Extended" opcodes. */
			uint64_t extsize;
			struct dwbuf extra;
			if (!read_uleb128(&unit, &extsize) ||
			    !read_buf(&unit, &extra, extsize) ||
			    !read_u8(&extra, &opcode))
				goto next;
			switch (opcode) {
			case DW_LNE_end_sequence:
				emit = true;
				end_sequence = true;
				break;
			case DW_LNE_set_address:
				switch (extra.len) {
				case 4: {
					uint32_t address32;
					if (!read_u32(&extra, &address32))
						goto next;
					address = address32;
					break;
				}
				case 8:
					if (!read_u64(&extra, &address))
						goto next;
					break;
				default:
					DWARN("unexpected address length: %zu",
					    extra.len);
					goto next;
				}
				break;
			case DW_LNE_define_file:
				/* XXX: hope this isn't needed */
			default:
				DWARN("unknown extended opcode: %d", opcode);
				goto next;
			}
		} else {
			/* "Standard" opcodes. */
			switch (opcode) {
			case DW_LNS_copy:
				emit = true;
				reset_basic_block = true;
				break;
			case DW_LNS_advance_pc: {
				uint64_t delta;
				if (!read_uleb128(&unit, &delta))
					goto next;
				address += delta * min_insn_length;
				break;
			}
			case DW_LNS_advance_line: {
				int64_t delta;
				if (!read_sleb128(&unit, &delta))
					goto next;
				line += delta;
				break;
			}
			case DW_LNS_set_file:
				if (!read_uleb128(&unit, &file))
					goto next;
				break;
			case DW_LNS_set_column:
				if (!read_uleb128(&unit, &column))
					goto next;
				break;
			case DW_LNS_negate_stmt:
				is_stmt = !is_stmt;
				break;
			case DW_LNS_set_basic_block:
				basic_block = true;
				break;
			case DW_LNS_const_add_pc:
				address += (255 - opcode_base) / line_range;
				break;
			case DW_LNS_set_prologue_end:
				prologue_end = true;
				break;
			case DW_LNS_set_epilogue_begin:
				epilogue_begin = true;
				break;
			default:
				DWARN("unknown standard opcode: %d", opcode);
				goto next;
			}
		}

		if (emit) {
			if (address > pc) {
				/* Found an entry after our target PC. */
				if (!have_last) {
					/* Give up on this program. */
					break;
				}
				/* Return the last entry. */
				*outline = last_line;
				return (read_filename(&names, outdirname,
				    outbasename, opcode_base, file));
			}

			last_file = file;
			last_line = line;
			have_last = true;
		}

		if (reset_basic_block)
			basic_block = false;
	}

	goto next;
}

#ifndef _KERNEL
#include <sys/endian.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <elf_abi.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#ifndef ELFDATA
#if BYTE_ORDER == LITTLE_ENDIAN
#define ELFDATA ELFDATA2LSB
#elif BYTE_ORDER == BIG_ENDIAN
#define ELFDATA ELFDATA2MSB
#else
#error Unsupported byte order
#endif
#endif /* !ELFDATA */

static void
usage()
{
	extern const char *__progname;
	errx(1, "usage: %s [-s] [-e filename] [addr addr ...]", __progname);
}

/*
 * Basic addr2line clone for stand-alone testing.
 */
int
main(int argc, char *argv[])
{
	const char *filename = "a.out";

	int ch;
	bool showdir = true;
	while ((ch = getopt(argc, argv, "e:s")) != EOF) {
		switch (ch) {
		case 'e':
			filename = optarg;
			break;
		case 's':
			showdir = false;
			break;
		default:
			usage();
		}
	}

	argc -= optind;
	argv += optind;

	/* Start by mapping the full file into memory. */
	int fd = open(filename, O_RDONLY);
	if (fd == -1)
		err(1, "open");

	struct stat st;
	if (fstat(fd, &st) == -1)
		err(1, "fstat");
	if (st.st_size < (off_t)sizeof(Elf_Ehdr))
		errx(1, "file too small to be ELF");
	if ((uintmax_t)st.st_size > SIZE_MAX)
		errx(1, "file too big to fit memory");
	size_t filesize = st.st_size;

	const char *p = mmap(NULL, filesize, PROT_READ, MAP_SHARED, fd, 0);
	if (p == MAP_FAILED)
		err(1, "mmap");

	close(fd);

	/* Read and validate ELF header. */
	Elf_Ehdr ehdr;
	memcpy(&ehdr, p, sizeof(ehdr));
	if (!IS_ELF(ehdr))
		errx(1, "file is not ELF");
	if (ehdr.e_ident[EI_CLASS] != ELFCLASS)
		errx(1, "unexpected word size");
	if (ehdr.e_ident[EI_DATA] != ELFDATA)
		errx(1, "unexpected data format");
	if (ehdr.e_shoff > filesize)
		errx(1, "bogus section table offset");
	if (ehdr.e_shentsize < sizeof(Elf_Shdr))
		errx(1, "unexpected section header size");
	if (ehdr.e_shnum > (filesize - ehdr.e_shoff) / ehdr.e_shentsize)
		errx(1, "bogus section header count");
	if (ehdr.e_shstrndx >= ehdr.e_shnum)
		errx(1, "bogus string table index");

	/* Find section header string table location and size. */
	Elf_Shdr shdr;
	memcpy(&shdr, p + ehdr.e_shoff + ehdr.e_shstrndx * ehdr.e_shentsize,
	    sizeof(shdr));
	if (shdr.sh_type != SHT_STRTAB)
		errx(1, "unexpected string table type");
	if (shdr.sh_offset > filesize)
		errx(1, "bogus string table offset");
	if (shdr.sh_size > filesize - shdr.sh_offset)
		errx(1, "bogus string table size");
	const char *shstrtab = p + shdr.sh_offset;
	size_t shstrtabsize = shdr.sh_size;

	/* Search through section table for .debug_line section. */
	size_t i;
	for (i = 0; i < ehdr.e_shnum; i++) {
		memcpy(&shdr, p + ehdr.e_shoff + i * ehdr.e_shentsize,
		    sizeof(shdr));
		if (0 == strncmp(".debug_line", shstrtab + shdr.sh_name,
		    shstrtabsize - shdr.sh_name))
			break;
	}
	if (i == ehdr.e_shnum)
		errx(1, "no DWARF line number table found");
	if (shdr.sh_offset > filesize)
		errx(1, "bogus line table offset");
	if (shdr.sh_size > filesize - shdr.sh_offset)
		errx(1, "bogus line table size");
	const char *linetab = p + shdr.sh_offset;
	size_t linetabsize = shdr.sh_size;

	const char *addrstr;
	while ((addrstr = *argv++) != NULL) {
		unsigned long addr = strtoul(addrstr, NULL, 16);

		const char *dir, *file;
		int line;
		if (!db_dwarf_line_at_pc(linetab, linetabsize, addr,
		    &dir, &file, &line)) {
			dir = NULL;
			file = "??";
			line = 0;
		}
		if (showdir && dir != NULL)
			printf("%s/", dir);
		printf("%s:%d\n", file, line);
	}

	return (0);
}
#endif /* !_KERNEL */