From 71b8e6690d5d3df35fd8c7ca3a9617d31a5fd328 Mon Sep 17 00:00:00 2001 From: Jonathan Lebon Date: Fri, 30 May 2014 15:42:00 -0400 Subject: [PATCH] dwflpp.cxx: use lower_bound() instead of manual binary search This is a follow-up to commit 1d50099. We previously implemented our own binary search to find the line record associated with the function's entrypc. To be on the safe side, we instead rely on lower_bound() for binary searching, which will pick the first element in a range of equal addresses, thus avoiding issues such as BZ1099133. --- dwflpp.cxx | 42 ++++++++++++++++++------------------------ 1 file changed, 18 insertions(+), 24 deletions(-) diff --git a/dwflpp.cxx b/dwflpp.cxx index ff3c1a65d..67a63c409 100644 --- a/dwflpp.cxx +++ b/dwflpp.cxx @@ -2222,6 +2222,18 @@ dwflpp::resolve_prologue_endings (func_info_map_t & funcs) DWARF_ASSERT ("dwarf_getsrclines", dwarf_getsrclines(cu, &lines, &nlines)); + // Dump them into our own array for easier searching. They should already be + // sorted by addr, but we doublecheck that here. We want to keep the indices + // between lines and addrs the same. + vector addrs; + for (size_t i = 0; i < nlines; i++) + { + Dwarf_Line* line = dwarf_onesrcline(lines, i); + Dwarf_Addr addr = DWARF_LINEADDR(line); + if (!addrs.empty() && addr < addrs.back()) + throw SEMANTIC_ERROR(_("lines from dwarf_getsrclines() not sorted")); + addrs.push_back(addr); + } // We normally ignore a function's decl_line, since it is associated with the // line at which the identifier appears in the declaration, and has no // meaningful relation to the lineno associated with the entrypc (which is @@ -2258,34 +2270,16 @@ dwflpp::resolve_prologue_endings (func_info_map_t & funcs) unsigned entrypc_srcline_idx = 0; Dwarf_Line *entrypc_srcline = NULL; - // open-code binary search for exact match { - unsigned l = 0, h = nlines; - while (l < h) + vector::const_iterator it_addr = + lower_bound(addrs.begin(), addrs.end(), entrypc); + if (it_addr != addrs.end()) { - entrypc_srcline_idx = (l + h) / 2; - Dwarf_Line* lr = dwarf_onesrcline(lines, entrypc_srcline_idx); - Dwarf_Addr addr = DWARF_LINEADDR(lr); - if (addr == entrypc) { entrypc_srcline = lr; break; } - else if (l + 1 == h) { break; } // ran off bottom of tree - else if (addr < entrypc) { l = entrypc_srcline_idx; } - else { h = entrypc_srcline_idx; } - } - - // We may by chance have fallen on the second of two consecutive line - // records for the same addr. If the previous Dwarf_Line is indeed at - // the same address, pick that one instead. It means that there is no - // prologue, which the code that follows will soon find. (BZ1099133). - if (entrypc_srcline && entrypc_srcline_idx > 0) - { - Dwarf_Line* lr = dwarf_onesrcline(lines, entrypc_srcline_idx-1); - if (DWARF_LINEADDR(lr) == entrypc) - { - entrypc_srcline = lr; - entrypc_srcline_idx--; - } + entrypc_srcline_idx = it_addr - addrs.begin(); + entrypc_srcline = dwarf_onesrcline(lines, entrypc_srcline_idx); } } + if (!entrypc_srcline) { if (sess.verbose > 2) -- 2.43.5