Index: contrib/elftoolchain/addr2line/addr2line.c
===================================================================
--- contrib/elftoolchain/addr2line/addr2line.c
+++ contrib/elftoolchain/addr2line/addr2line.c
@@ -25,6 +25,7 @@
  */
 
 #include <sys/param.h>
+#include <sys/tree.h>
 
 #include <capsicum_helpers.h>
 #include <dwarf.h>
@@ -39,7 +40,6 @@
 #include <stdlib.h>
 #include <string.h>
 
-#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,12 +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 = ~0ULL, hicache;
+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\
@@ -104,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)
 {
@@ -395,6 +415,7 @@
 	struct Func *f;
 	const char *funcname;
 	char *file, *file0, *pfile;
+	struct node *new_node;
 	char demangled[1024];
 	int ec, i, ret;
 
@@ -404,6 +425,7 @@
 	file = unknown;
 	cu = NULL;
 	die = NULL;
+	ret = DW_DLV_OK;
 
 
 	if (addr >= locache && addr < hicache && last_die != NULL) {
@@ -411,6 +433,25 @@
 		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 
@@ -420,7 +461,7 @@
 		ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL, 
 		    &de);
 		if (ret == DW_DLV_NO_ENTRY) {
-			if (locache == ~0ULL) {
+			if (curlopc == ~0ULL) {
 				goto out;
 			}
 			ret = dwarf_next_cu_header(dbg, NULL, NULL, NULL, NULL, NULL,
@@ -448,7 +489,7 @@
 		}
 		if (dwarf_attrval_unsigned(die, DW_AT_low_pc, &lopc, &de) ==
 		    DW_DLV_OK) {
-			if (lopc == locache) {
+			if (lopc == curlopc) {
 				goto out;
 			}
 			if (dwarf_attrval_unsigned(die, DW_AT_high_pc, &hipc,
@@ -474,22 +515,17 @@
 				    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:
+		next_cu:
 		if (die != NULL && die != last_die) {
 			dwarf_dealloc(dbg, die, DW_DLA_DIE);
 			die = NULL;
@@ -499,12 +535,21 @@
 	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;
-	if (last_die != NULL) {
-		dwarf_dealloc(dbg, last_die, DW_DLA_DIE);
-		last_die = NULL;
-	}
 	last_die = die;
 
 status_ok:
@@ -750,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]);
@@ -759,9 +813,9 @@
 			translate(dbg, e, line);
 	}
 
-	if (last_die != NULL) {
+	/*if (last_die != NULL) {
 		dwarf_dealloc(dbg, last_die, DW_DLA_DIE);
-	}
+	}*/
 
 	dwarf_finish(dbg, &de);