Page MenuHomeFreeBSD
Differential D23418 Diff 67570 contrib/elftoolchain/addr2line/addr2line.c

Changeset View

Standalone View

View Options

contrib/elftoolchain/addr2line/addr2line.c

Show All 19 Lines
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE. * SUCH DAMAGE.
*/ */
#include <sys/param.h> #include <sys/param.h>
#include <sys/tree.h>
#include <capsicum_helpers.h> #include <capsicum_helpers.h>
#include <dwarf.h> #include <dwarf.h>
#include <err.h> #include <err.h>
#include <fcntl.h> #include <fcntl.h>
#include <gelf.h> #include <gelf.h>
#include <getopt.h> #include <getopt.h>
#include <libdwarf.h> #include <libdwarf.h>
#include <libelftc.h> #include <libelftc.h>
#include <libgen.h> #include <libgen.h>
#include <stdio.h> #include <stdio.h>
#include <stdlib.h> #include <stdlib.h>
#include <string.h> #include <string.h>
#include "uthash.h"
#include "_elftc.h" #include "_elftc.h"
ELFTC_VCSID("$Id: addr2line.c 3499 2016-11-25 16:06:29Z emaste $"); ELFTC_VCSID("$Id: addr2line.c 3499 2016-11-25 16:06:29Z emaste $");
struct Func { struct Func {
char *name; char *name;
Dwarf_Unsigned lopc; Dwarf_Unsigned lopc;
Dwarf_Unsigned hipc; Dwarf_Unsigned hipc;
Dwarf_Unsigned call_file; Dwarf_Unsigned call_file;
Dwarf_Unsigned call_line; Dwarf_Unsigned call_line;
Dwarf_Ranges *ranges; Dwarf_Ranges *ranges;
Dwarf_Signed ranges_cnt; Dwarf_Signed ranges_cnt;
struct Func *inlined_caller; struct Func *inlined_caller;
STAILQ_ENTRY(Func) next; STAILQ_ENTRY(Func) next;
}; };
struct CU { struct CU {
RB_ENTRY(CU) entry;
Dwarf_Off off; Dwarf_Off off;
Dwarf_Unsigned lopc; Dwarf_Unsigned lopc;
Dwarf_Unsigned hipc; Dwarf_Unsigned hipc;
char **srcfiles; char **srcfiles;
Dwarf_Signed nsrcfiles; Dwarf_Signed nsrcfiles;
STAILQ_HEAD(, Func) funclist; STAILQ_HEAD(, Func) funclist;
UT_hash_handle hh; Dwarf_Die die;
}; };
static struct option longopts[] = { static struct option longopts[] = {
{"addresses", no_argument, NULL, 'a'}, {"addresses", no_argument, NULL, 'a'},
{"target" , required_argument, NULL, 'b'}, {"target" , required_argument, NULL, 'b'},
{"demangle", no_argument, NULL, 'C'}, {"demangle", no_argument, NULL, 'C'},
{"exe", required_argument, NULL, 'e'}, {"exe", required_argument, NULL, 'e'},
{"functions", no_argument, NULL, 'f'}, {"functions", no_argument, NULL, 'f'},
{"inlines", no_argument, NULL, 'i'}, {"inlines", no_argument, NULL, 'i'},
{"section", required_argument, NULL, 'j'}, {"section", required_argument, NULL, 'j'},
{"pretty-print", no_argument, NULL, 'p'}, {"pretty-print", no_argument, NULL, 'p'},
{"basename", no_argument, NULL, 's'}, {"basename", no_argument, NULL, 's'},
{"help", no_argument, NULL, 'H'}, {"help", no_argument, NULL, 'H'},
{"version", no_argument, NULL, 'V'}, {"version", no_argument, NULL, 'V'},
{NULL, 0, NULL, 0} {NULL, 0, NULL, 0}
}; };
markjUnsubmitted
Not Done
Inline Actions

Why not add a DIE field to struct CU above? Otherwise you are duplicating the lowpc/hipc fields.

markj: Why not add a DIE field to struct CU above? Otherwise you are duplicating the lowpc/hipc fields.
static int demangle, func, base, inlines, print_addr, pretty_print; static int demangle, func, base, inlines, print_addr, pretty_print;
static char unknown[] = { '?', '?', '\0' }; static char unknown[] = { '?', '?', '\0' };
static Dwarf_Addr section_base; static Dwarf_Addr section_base;
static struct CU *culist; static struct CU *last_cu;
/* 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 RB_HEAD(cutree, CU) head = RB_INITIALIZER(&head);
static int
lopccmp(struct CU *e1, struct CU *e2)
{
return (e1->lopc < e2->lopc ? -1 : e1->lopc > e2->lopc);
}
RB_PROTOTYPE(cutree, CU, entry, lopccmp);
RB_GENERATE(cutree, CU, entry, lopccmp)
#define USAGE_MESSAGE "\ #define USAGE_MESSAGE "\
Usage: %s [options] hexaddress...\n\ Usage: %s [options] hexaddress...\n\
Map program addresses to source file names and line numbers.\n\n\ Map program addresses to source file names and line numbers.\n\n\
Options:\n\ Options:\n\
-a | --addresses Display address prior to line number info.\n\ -a | --addresses Display address prior to line number info.\n\
-b TGT | --target=TGT (Accepted but ignored).\n\ -b TGT | --target=TGT (Accepted but ignored).\n\
-e EXE | --exe=EXE Use program \"EXE\" to translate addresses.\n\ -e EXE | --exe=EXE Use program \"EXE\" to translate addresses.\n\
-f | --functions Display function names.\n\ -f | --functions Display function names.\n\
-i | --inlines Display caller info for inlined functions.\n\ -i | --inlines Display caller info for inlined functions.\n\
-j NAME | --section=NAME Values are offsets into section \"NAME\".\n\ -j NAME | --section=NAME Values are offsets into section \"NAME\".\n\
-p | --pretty-print Display line number info and function name\n\ -p | --pretty-print Display line number info and function name\n\
in human readable manner.\n\ in human readable manner.\n\
-s | --basename Only show the base name for each file name.\n\ -s | --basename Only show the base name for each file name.\n\
-C | --demangle Demangle C++ names.\n\ -C | --demangle Demangle C++ names.\n\
-H | --help Print a help message.\n\ -H | --help Print a help message.\n\
-V | --version Print a version identifier and exit.\n" -V | --version Print a version identifier and exit.\n"
static void static void
usage(void) usage(void)
{ {
(void) fprintf(stderr, USAGE_MESSAGE, ELFTC_GETPROGNAME()); (void) fprintf(stderr, USAGE_MESSAGE, ELFTC_GETPROGNAME());
exit(1); exit(1);
} }
static void static void
markjUnsubmitted
Not Done
Inline Actions

As a matter of style I would move this above the #define of USAGE_MESSAGE. USAGE_MESSAGE is used by usage() below.

markj: As a matter of style I would move this above the #define of USAGE_MESSAGE. USAGE_MESSAGE is…
version(void) version(void)
{ {
fprintf(stderr, "%s (%s)\n", ELFTC_GETPROGNAME(), elftc_version()); fprintf(stderr, "%s (%s)\n", ELFTC_GETPROGNAME(), elftc_version());
exit(0); exit(0);
} }
/* /*
▲ Show 20 Lines • Show All 255 Lines • ▼ Show 20 Linesprint_inlines(struct CU *cu, struct Func *f, Dwarf_Unsigned call_file,
if (f->inlined_caller != NULL) if (f->inlined_caller != NULL)
print_inlines(cu, f->inlined_caller, f->call_file, print_inlines(cu, f->inlined_caller, f->call_file,
f->call_line); f->call_line);
} }
static void static void
translate(Dwarf_Debug dbg, Elf *e, const char* addrstr) translate(Dwarf_Debug dbg, Elf *e, const char* addrstr)
{ {
struct CU find;
Dwarf_Die die, ret_die; Dwarf_Die die, ret_die;
Dwarf_Line *lbuf; Dwarf_Line *lbuf;
Dwarf_Error de; Dwarf_Error de;
Dwarf_Half tag; Dwarf_Half tag;
Dwarf_Unsigned lopc, hipc, addr, lineno, plineno; Dwarf_Unsigned lopc, hipc, addr, lineno, plineno;
Dwarf_Signed lcount; Dwarf_Signed lcount;
Dwarf_Addr lineaddr, plineaddr; Dwarf_Addr lineaddr, plineaddr;
Dwarf_Off off; Dwarf_Off off;
struct CU *cu; struct CU *cu;
struct Func *f; struct Func *f;
struct CU *res;
const char *funcname; const char *funcname;
char *file, *file0, *pfile; char *file, *file0, *pfile;
char demangled[1024]; char demangled[1024];
markjUnsubmitted
Not Done
Inline Actions

Extra newline.

markj: Extra newline.
int ec, i, ret; int ec, i, ret;
addr = strtoull(addrstr, NULL, 16); addr = strtoull(addrstr, NULL, 16);
addr += section_base; addr += section_base;
lineno = 0; lineno = 0;
file = unknown; file = unknown;
cu = NULL; cu = NULL;
die = NULL; die = NULL;
ret = DW_DLV_OK;
while ((ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL,
&de)) == DW_DLV_OK) { if (last_cu != NULL && addr >= last_cu->lopc && addr < last_cu->hipc) {
cu = last_cu;
die = last_cu->die;
goto status_ok;
}
/* Address isn't in cache. Check if it's in cutree. */
markjUnsubmitted
Not Done
Inline Actions

Do we need to keep the last_die cache anymore? Does it really help much?

markj: Do we need to keep the last_die cache anymore? Does it really help much?
find.lopc = addr;
markjUnsubmitted
Not Done
Inline Actions

Per style(9) variable declarations should be at the beginning of the function.

markj: Per style(9) variable declarations should be at the beginning of the function.
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) {
die = res->die;
cu = res;
last_cu = cu;
goto status_ok;
}
} else {
/* We check the max node */
res = RB_MAX(cutree, &head);
if (res != NULL && addr >= res->lopc && addr < res->hipc) {
die = res->die;
cu = res;
last_cu = cu;
goto status_ok;
}
}
markjUnsubmitted
Not Done
Inline Actions

I would suggest putting this in a subroutine, culookup() or so.

markj: I would suggest putting this in a subroutine, culookup() or so.
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; die = NULL;
while (dwarf_siblingof(dbg, die, &ret_die, &de) == DW_DLV_OK) { while (dwarf_siblingof(dbg, die, &ret_die, &de) == DW_DLV_OK) {
if (die != NULL) if (die != NULL)
dwarf_dealloc(dbg, die, DW_DLA_DIE); dwarf_dealloc(dbg, die, DW_DLA_DIE);
die = ret_die; die = ret_die;
if (dwarf_tag(die, &tag, &de) != DW_DLV_OK) { if (dwarf_tag(die, &tag, &de) != DW_DLV_OK) {
warnx("dwarf_tag failed: %s", warnx("dwarf_tag failed: %s",
dwarf_errmsg(de)); dwarf_errmsg(de));
goto next_cu; goto next_cu;
} }
/* XXX: What about DW_TAG_partial_unit? */ /* XXX: What about DW_TAG_partial_unit? */
if (tag == DW_TAG_compile_unit) if (tag == DW_TAG_compile_unit)
break; break;
} }
if (ret_die == NULL) { if (ret_die == NULL) {
warnx("could not find DW_TAG_compile_unit die"); warnx("could not find DW_TAG_compile_unit die");
goto next_cu; goto next_cu;
} }
if (dwarf_attrval_unsigned(die, DW_AT_low_pc, &lopc, &de) == if (dwarf_attrval_unsigned(die, DW_AT_low_pc, &lopc, &de) ==
DW_DLV_OK) { DW_DLV_OK) {
if (lopc == curlopc) {
goto out;
}
if (dwarf_attrval_unsigned(die, DW_AT_high_pc, &hipc, if (dwarf_attrval_unsigned(die, DW_AT_high_pc, &hipc,
&de) == DW_DLV_OK) { &de) == DW_DLV_OK) {
/* /*
* Check if the address falls into the PC * Check if the address falls into the PC
* range of this CU. * range of this CU.
*/ */
if (handle_high_pc(die, lopc, &hipc) != if (handle_high_pc(die, lopc, &hipc) !=
DW_DLV_OK) DW_DLV_OK)
goto out; goto out;
} else { } else {
/* Assume ~0ULL if DW_AT_high_pc not present */ /* Assume ~0ULL if DW_AT_high_pc not present */
hipc = ~0ULL; hipc = ~0ULL;
} }
/*
* Record the CU in the hash table for faster lookup
* later.
*/
if (dwarf_dieoffset(die, &off, &de) != DW_DLV_OK) { if (dwarf_dieoffset(die, &off, &de) != DW_DLV_OK) {
warnx("dwarf_dieoffset failed: %s", warnx("dwarf_dieoffset failed: %s",
dwarf_errmsg(de)); dwarf_errmsg(de));
goto out; goto out;
} }
HASH_FIND(hh, culist, &off, sizeof(off), cu);
if (cu == NULL) { if (addr >= lopc && addr < hipc) {
if ((cu = calloc(1, sizeof(*cu))) == NULL) if ((cu = calloc(1, sizeof(*cu))) == NULL) {
markjUnsubmitted
Not Done
Inline Actions

I think this structure never gets freed? Before that kind of made sense since we were putting it in an (unused) hash table, but now it does not.

That said, I think it makes sense for struct node and struct CU to be merged, in which case you would not want to free the CUs since they end up in the lookup tree.

markj: I think this structure never gets freed? Before that kind of made sense since we were putting…
err(EXIT_FAILURE, "calloc"); err(EXIT_FAILURE, "calloc");
}
cu->off = off; cu->off = off;
cu->lopc = lopc; cu->lopc = lopc;
cu->hipc = hipc; cu->hipc = hipc;
cu->die = die;
STAILQ_INIT(&cu->funclist); STAILQ_INIT(&cu->funclist);
HASH_ADD(hh, culist, off, sizeof(off), cu);
}
if (addr >= lopc && addr < hipc)
break; break;
markjUnsubmitted
Not Done
Inline Actions

I think we want to check for a match before doing any allocation, not after.

markj: I think we want to check for a match before doing any allocation, not after.
tig_freebsdfoundation.orgAuthorUnsubmitted
Done
Inline Actions

Yes. We should just allocate cu here and add it to our tree.

tig_freebsdfoundation.org: Yes. We should just allocate cu here and add it to our tree.
} }
}
next_cu: next_cu:
if (die != NULL) { if (die != NULL) {
dwarf_dealloc(dbg, die, DW_DLA_DIE); dwarf_dealloc(dbg, die, DW_DLA_DIE);
die = NULL; die = NULL;
} }
} }
if (ret != DW_DLV_OK || die == NULL) if (ret != DW_DLV_OK || die == NULL)
goto out; goto out;
/* Add this addr's CU info from brute force to tree */
RB_INSERT(cutree, &head, cu);
markjUnsubmitted
Not Done
Inline Actions

I think the insertion should be done in the block where cu is allocated.

markj: I think the insertion should be done in the block where cu is allocated.
/* update curlopc. Not affected by tree or cache lookup. */
curlopc = lopc;
/* update single cache */
last_cu = cu;
markjUnsubmitted
Not Done
Inline Actions

Again, do we really need the single-entry cache anymore?

markj: Again, do we really need the single-entry cache anymore?
tig_freebsdfoundation.orgAuthorUnsubmitted
Not Done
Inline Actions

I think we do because tree lookup is O(n) and it's O(1) if it's a single cache HIT. This is good for sequential lookups.

tig_freebsdfoundation.org: I think we do because tree lookup is O(n) and it's O(1) if it's a single cache HIT. This is…
markjUnsubmitted
Not Done
Inline Actions

I guess my real question is, does it make a difference in practice? That is, can you measure a significant benefit from it when input is sorted?

I don't object to keeping it if so, but the goal here is really just to ensure that addr2line is not abysmally slow. A 1% improvement is not very important and not worth the extra complexity in my opinion.

markj: I guess my real question is, does it make a difference in practice? That is, can you measure a…
tig_freebsdfoundation.orgAuthorUnsubmitted
Not Done
Inline Actions

The performance is basically exactly the same after I removed the single cache. I removed it.

tig_freebsdfoundation.org: The performance is basically exactly the same after I removed the single cache. I removed it.
tig_freebsdfoundation.orgAuthorUnsubmitted
Not Done
Inline Actions

The performance is similar in both cases (sequential addresses and random addresses).

tig_freebsdfoundation.org: The performance is similar in both cases (sequential addresses and random addresses).
status_ok:
switch (dwarf_srclines(die, &lbuf, &lcount, &de)) { switch (dwarf_srclines(die, &lbuf, &lcount, &de)) {
markjUnsubmitted
Not Done
Inline Actions

This label name doesn't really make sense to me: the code which does the cache insertion comes before the label.

markj: This label name doesn't really make sense to me: the code which does the cache insertion comes…
case DW_DLV_OK: case DW_DLV_OK:
break; break;
case DW_DLV_NO_ENTRY: case DW_DLV_NO_ENTRY:
/* If a CU lacks debug info, just skip it. */ /* If a CU lacks debug info, just skip it. */
goto out; goto out;
default: default:
warnx("dwarf_srclines: %s", dwarf_errmsg(de)); warnx("dwarf_srclines: %s", dwarf_errmsg(de));
goto out; goto out;
Show All 25 Lines for (i = 0; i < lcount; i++) {
plineaddr = lineaddr; plineaddr = lineaddr;
plineno = lineno; plineno = lineno;
pfile = file; pfile = file;
} }
out: out:
f = NULL; f = NULL;
funcname = NULL; funcname = NULL;
if (ret == DW_DLV_OK && (func || inlines) && cu != NULL) { if (ret == DW_DLV_OK && (func || inlines) && cu != NULL) {
markjUnsubmitted
Not Done
Inline Actions

On a cache hit, we will have cu == NULL here. Is that correct?

Note that addr2line has -f and -i options that cause the (func || inlines) check to be true. Make sure that this case still works.

markj: On a cache hit, we will have cu == NULL here. Is that correct? Note that addr2line has -f and…
if (cu->srcfiles == NULL) if (cu->srcfiles == NULL)
if (dwarf_srcfiles(die, &cu->srcfiles, &cu->nsrcfiles, if (dwarf_srcfiles(die, &cu->srcfiles, &cu->nsrcfiles,
&de)) &de))
warnx("dwarf_srcfiles: %s", dwarf_errmsg(de)); warnx("dwarf_srcfiles: %s", dwarf_errmsg(de));
if (STAILQ_EMPTY(&cu->funclist)) { if (STAILQ_EMPTY(&cu->funclist)) {
collect_func(dbg, die, NULL, cu); collect_func(dbg, die, NULL, cu);
die = NULL; die = NULL;
} }
Show All 39 Linesout:
(void) printf("%s:%ju\n", base ? basename(file) : file, (void) printf("%s:%ju\n", base ? basename(file) : file,
(uintmax_t) lineno); (uintmax_t) lineno);
if (ret == DW_DLV_OK && inlines && cu != NULL && if (ret == DW_DLV_OK && inlines && cu != NULL &&
cu->srcfiles != NULL && f != NULL && f->inlined_caller != NULL) cu->srcfiles != NULL && f != NULL && f->inlined_caller != NULL)
print_inlines(cu, f->inlined_caller, f->call_file, print_inlines(cu, f->inlined_caller, f->call_file,
f->call_line); 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 static void
find_section_base(const char *exe, Elf *e, const char *section) find_section_base(const char *exe, Elf *e, const char *section)
{ {
Dwarf_Addr off; Dwarf_Addr off;
Elf_Scn *scn; Elf_Scn *scn;
GElf_Ehdr eh; GElf_Ehdr eh;
▲ Show 20 Lines • Show All 133 Lines • ▼ Show 20 Lines else
section_base = 0; section_base = 0;
if (argc > 0) if (argc > 0)
for (i = 0; i < argc; i++) for (i = 0; i < argc; i++)
translate(dbg, e, argv[i]); translate(dbg, e, argv[i]);
else { else {
setvbuf(stdout, NULL, _IOLBF, 0); setvbuf(stdout, NULL, _IOLBF, 0);
while (fgets(line, sizeof(line), stdin) != NULL) while (fgets(line, sizeof(line), stdin) != NULL)
translate(dbg, e, line); translate(dbg, e, line);
markjUnsubmitted
Not Done
Inline Actions

I don't really like the useless node. Instead of using it, can't we modify the lookup algorithm slightly to look at RB_LAST() if RB_NFIND() returns NULL?

markj: I don't really like the useless node. Instead of using it, can't we modify the lookup algorithm…
} }
markjUnsubmitted
Not Done
Inline Actions

This code should just be deleted.

markj: This code should just be deleted.
dwarf_finish(dbg, &de); dwarf_finish(dbg, &de);
(void) elf_end(e); (void) elf_end(e);
exit(0); exit(0);
} }