libbacktrace: avoid ambiguous binary search
authorIan Lance Taylor <iant@golang.org>
Wed, 9 Sep 2020 01:18:48 +0000 (18:18 -0700)
committerIan Lance Taylor <iant@golang.org>
Wed, 9 Sep 2020 01:22:35 +0000 (18:22 -0700)
commit0755f573f0874e152a919c61c62bf8d31aa190f0
tree21161daf3e6f780e00778a45e319ec6e9aae3f7e
parent31a050462476f4f15dc5e1f9d6ac9a1dd0a70e74
libbacktrace: avoid ambiguous binary search

Searching for a range match can cause the search order to not match
the sort order, which can cause libbacktrace to miss matching entries.
Allocate 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.
Adjust the matching code accordingly.

Fixes https://github.com/ianlancetaylor/libbacktrace/issues/44.

* dwarf.c (function_addrs_search): Compare against the next entry
low address, not the high address.
(unit_addrs_search): Likewise.
(build_address_map): Add a trailing unit_addrs.
(read_function_entry): Add a trailing function_addrs.
(read_function_info): Likewise.
(report_inlined_functions): Search backward for function_addrs
match.
(dwarf_lookup_pc): Search backward for unit_addrs and
function_addrs matches.
libbacktrace/dwarf.c