Index: contrib/elftoolchain/addr2line/addr2line.c =================================================================== --- contrib/elftoolchain/addr2line/addr2line.c +++ contrib/elftoolchain/addr2line/addr2line.c @@ -25,6 +25,7 @@ */ #include +#include #include #include @@ -39,7 +40,6 @@ #include #include -#include "uthash.h" #include "_elftc.h" ELFTC_VCSID("$Id: addr2line.c 3499 2016-11-25 16:06:29Z emaste $"); @@ -63,7 +63,6 @@ char **srcfiles; Dwarf_Signed nsrcfiles; STAILQ_HEAD(, Func) funclist; - UT_hash_handle hh; }; static struct option longopts[] = { @@ -80,10 +79,24 @@ {"version", no_argument, NULL, 'V'}, {NULL, 0, NULL, 0} }; +/* New structure because CU doesn't have Dwarf_Die field */ +struct node { + RB_ENTRY(node) entry; + Dwarf_Unsigned lopc; + Dwarf_Unsigned hipc; + Dwarf_Die die; +}; static int demangle, func, base, inlines, print_addr, pretty_print; static char unknown[] = { '?', '?', '\0' }; static Dwarf_Addr section_base; -static struct CU *culist; +static Dwarf_Unsigned locache, hicache; +/* Need a new curlopc that stores last lopc value. + * We used to use locache to do this, but locache is not stable anymore + * as tree lookup updates cache. + */ +static Dwarf_Unsigned curlopc = ~0ULL; +static Dwarf_Die last_die = NULL; +static RB_HEAD(cutree, node) head = RB_INITIALIZER(&head); #define USAGE_MESSAGE "\ Usage: %s [options] hexaddress...\n\ @@ -102,6 +115,15 @@ -H | --help Print a help message.\n\ -V | --version Print a version identifier and exit.\n" +static int +lopccmp(struct node *e1, struct node *e2) +{ + return (e1->lopc < e2->lopc ? -1 : e1->lopc > e2->lopc); +} + +RB_PROTOTYPE(cutree, node, entry, lopccmp); +RB_GENERATE(cutree, node, entry, lopccmp) + static void usage(void) { @@ -393,6 +415,7 @@ struct Func *f; const char *funcname; char *file, *file0, *pfile; + struct node *new_node; char demangled[1024]; int ec, i, ret; @@ -402,9 +425,48 @@ file = unknown; cu = NULL; die = NULL; + ret = DW_DLV_OK; + - while ((ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL, - &de)) == DW_DLV_OK) { + if (addr >= locache && addr < hicache && last_die != NULL) { + die = last_die; + goto status_ok; + } + + /* Address isn't in cache. Check if it's in cutree. */ + struct node find, *res; + find.lopc = addr; + res = RB_NFIND(cutree, &head, &find); + if (res != NULL) { + /* go back one res if addr != res->lopc */ + if (res->lopc != addr) { + res = RB_PREV(cutree, &head, res); + /* res can be NULL when tree only has useless_node */ + } + /* Found the potential CU, but have to check if addr falls in range */ + if (res != NULL && (addr >= res->lopc) && (addr < res->hipc)) { + lopc = res->lopc; + hipc = res->hipc; + die = res->die; + goto cache_insert; + } + } + + while (true) { + /* + * We resume the CU scan from the last place we found a match. Because + * when we have 2 sequential addresses, and the second one is of the next CU, + * it is faster to just go to the next CU instead of starting from the beginning. + */ + ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL, + &de); + if (ret == DW_DLV_NO_ENTRY) { + if (curlopc == ~0ULL) { + goto out; + } + ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL, + &de); + } die = NULL; while (dwarf_siblingof(dbg, die, &ret_die, &de) == DW_DLV_OK) { if (die != NULL) @@ -420,12 +482,16 @@ if (tag == DW_TAG_compile_unit) break; } + if (ret_die == NULL) { warnx("could not find DW_TAG_compile_unit die"); goto next_cu; } if (dwarf_attrval_unsigned(die, DW_AT_low_pc, &lopc, &de) == DW_DLV_OK) { + if (lopc == curlopc) { + goto out; + } if (dwarf_attrval_unsigned(die, DW_AT_high_pc, &hipc, &de) == DW_DLV_OK) { /* @@ -449,23 +515,18 @@ dwarf_errmsg(de)); goto out; } - HASH_FIND(hh, culist, &off, sizeof(off), cu); - if (cu == NULL) { - if ((cu = calloc(1, sizeof(*cu))) == NULL) + if ((cu = calloc(1, sizeof(*cu))) == NULL) err(EXIT_FAILURE, "calloc"); cu->off = off; cu->lopc = lopc; cu->hipc = hipc; STAILQ_INIT(&cu->funclist); - HASH_ADD(hh, culist, off, sizeof(off), cu); - } if (addr >= lopc && addr < hipc) break; } - - next_cu: - if (die != NULL) { + next_cu: + if (die != NULL && die != last_die) { dwarf_dealloc(dbg, die, DW_DLA_DIE); die = NULL; } @@ -474,6 +535,25 @@ if (ret != DW_DLV_OK || die == NULL) goto out; + /* Add this addr's CU info from brute force to tree */ + if ((new_node = calloc(1, sizeof(*new_node))) == NULL) + err(EXIT_FAILURE, "calloc"); + new_node->lopc = lopc; + new_node->hipc = hipc; + new_node->die = die; + RB_INSERT(cutree, &head, new_node); + + /* update curlopc. Not affected by tree or cache lookup. */ + curlopc = lopc; + +cache_insert: + /* Either from a tree lookup or a brute-force search */ + locache = lopc; + hicache = hipc; + last_die = die; + +status_ok: + switch (dwarf_srclines(die, &lbuf, &lcount, &de)) { case DW_DLV_OK: break; @@ -572,21 +652,6 @@ cu->srcfiles != NULL && f != NULL && f->inlined_caller != NULL) print_inlines(cu, f->inlined_caller, f->call_file, f->call_line); - - if (die != NULL) - dwarf_dealloc(dbg, die, DW_DLA_DIE); - - /* - * Reset internal CU pointer, so we will start from the first CU - * next round. - */ - while (ret != DW_DLV_NO_ENTRY) { - if (ret == DW_DLV_ERROR) - errx(EXIT_FAILURE, "dwarf_next_cu_header: %s", - dwarf_errmsg(de)); - ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL, - &de); - } } static void @@ -730,6 +795,15 @@ else section_base = 0; + /* Add a useless node so RB_NFIND can find the last node that has info */ + struct node *useless_node; + if ((useless_node = calloc(1, sizeof(*useless_node))) == NULL) + err(EXIT_FAILURE, "calloc"); + useless_node->lopc = ~0ULL; + useless_node->hipc = 0ULL; + useless_node->die = NULL; + RB_INSERT(cutree, &head, useless_node); + if (argc > 0) for (i = 0; i < argc; i++) translate(dbg, e, argv[i]); @@ -739,6 +813,10 @@ translate(dbg, e, line); } + /*if (last_die != NULL) { + dwarf_dealloc(dbg, last_die, DW_DLA_DIE); + }*/ + dwarf_finish(dbg, &de); (void) elf_end(e);