On Tue, Sep 8, 2020 at 6:22 PM Ian Lance Taylor <i...@golang.org> wrote:
>
> This patch to libbacktrace avoids ambiguous binary searches.
> Searching for a range match can cause the search order to not match
> the sort order, which can cause libbacktrace to miss matching entries.
> This patch allocates an extra entry at the end of function_addrs and
> unit_addrs vectors, so that we can safely compare to the next entry
> when searching. It adjusts the matching code accordingly. This fixes
> https://github.com/ianlancetaylor/libbacktrace/issues/44.
> Bootstrapped and ran libbacktrace and libgo tests on
> x86_64-pc-linux-gnu. Committed to mainline.
I realized that this isn't quite right for the case where the PC value
we are looking up is equal to the low value in the array we are
searching. In that case to ensure consistent results we have to step
forward to the end of the sequence of identical low values, and only
then step backward. This patch implements that. It also ensures that
the right thing happens if someone decides to look up the PC value -1.
Bootstrapped and ran libbacktrace and Go tests on x86_64-pc-linux-gnu.
Committed to mainline.
Ian
* dwarf.c (report_inlined_functions): Handle PC == -1 and PC ==
p->low.
(dwarf_lookup_pc): Likewise.
diff --git a/libbacktrace/dwarf.c b/libbacktrace/dwarf.c
index 386701bffea..582f34bc816 100644
--- a/libbacktrace/dwarf.c
+++ b/libbacktrace/dwarf.c
@@ -3558,6 +3558,11 @@ report_inlined_functions (uintptr_t pc, struct function
*function,
if (function->function_addrs_count == 0)
return 0;
+ /* Our search isn't safe if pc == -1, as that is the sentinel
+ value. */
+ if (pc + 1 == 0)
+ return 0;
+
p = ((struct function_addrs *)
bsearch (&pc, function->function_addrs,
function->function_addrs_count,
@@ -3567,9 +3572,12 @@ report_inlined_functions (uintptr_t pc, struct function
*function,
return 0;
/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
- sorted by low, so we are at the end of a range of function_addrs
- with the same low alue. Walk backward and use the first range
- that includes pc. */
+ sorted by low, so if pc > p->low we are at the end of a range of
+ function_addrs with the same low value. If pc == p->low walk
+ forward to the end of the range with that low value. Then walk
+ backward and use the first range that includes pc. */
+ while (pc == (p + 1)->low)
+ ++p;
match = NULL;
while (1)
{
@@ -3636,8 +3644,10 @@ dwarf_lookup_pc (struct backtrace_state *state, struct
dwarf_data *ddata,
*found = 1;
- /* Find an address range that includes PC. */
- entry = (ddata->addrs_count == 0
+ /* Find an address range that includes PC. Our search isn't safe if
+ PC == -1, as we use that as a sentinel value, so skip the search
+ in that case. */
+ entry = (ddata->addrs_count == 0 || pc + 1 == 0
? NULL
: bsearch (&pc, ddata->addrs, ddata->addrs_count,
sizeof (struct unit_addrs), unit_addrs_search));
@@ -3649,9 +3659,12 @@ dwarf_lookup_pc (struct backtrace_state *state, struct
dwarf_data *ddata,
}
/* Here pc >= entry->low && pc < (entry + 1)->low. The unit_addrs
- are sorted by low, so we are at the end of a range of unit_addrs
- with the same low value. Walk backward and use the first range
- that includes pc. */
+ are sorted by low, so if pc > p->low we are at the end of a range
+ of unit_addrs with the same low value. If pc == p->low walk
+ forward to the end of the range with that low value. Then walk
+ backward and use the first range that includes pc. */
+ while (pc == (entry + 1)->low)
+ ++entry;
found_entry = 0;
while (1)
{
@@ -3832,9 +3845,12 @@ dwarf_lookup_pc (struct backtrace_state *state, struct
dwarf_data *ddata,
return callback (data, pc, ln->filename, ln->lineno, NULL);
/* Here pc >= p->low && pc < (p + 1)->low. The function_addrs are
- sorted by low, so we are at the end of a range of function_addrs
- with the same low alue. Walk backward and use the first range
- that includes pc. */
+ sorted by low, so if pc > p->low we are at the end of a range of
+ function_addrs with the same low value. If pc == p->low walk
+ forward to the end of the range with that low value. Then walk
+ backward and use the first range that includes pc. */
+ while (pc == (p + 1)->low)
+ ++p;
fmatch = NULL;
while (1)
{
