[PATCH 0/1] libgcc: Add sdata8 binary search support to _Unwind_Find_FDE

[Farid Zakaria]

The FDE lookup in unwind-dw2-fde-dip.c uses a binary search on the
.eh_frame_hdr table, but only when the table encoding is
DW_EH_PE_datarel | DW_EH_PE_sdata4 (8-byte entries).  When
-large-eh-encoding produces DW_EH_PE_datarel | DW_EH_PE_sdata8
(16-byte entries), the code falls through to linear_search_fdes(),
regressing FDE lookup from O(log N) to O(N).

This patch extends the binary search to also handle sdata8 table
entries, maintaining O(log N) lookup for large binaries where
offsets exceed 2GiB.

We recently added support in lld (LLVM) to support sdata8 for
eh_frame_hdr automatically regardless of code-model.
https://github.com/llvm/llvm-project/pull/179089

Benchmark results (FDE lookup with sdata8 encoding):

Before (falls through to linear_search_fdes):

  depth1(1)       719.49us     1.39K
  depth5(1)       723.31us     1.38K
  depth10(1)      726.60us     1.38K
  depth20(1)      739.54us     1.35K
  depth40(1)      779.26us     1.28K
  manyFdes(1)      13.02s     76.82m

After (binary search for sdata8):

  depth1(1)         1.47us   679.29K
  depth5(1)         2.49us   402.15K
  depth10(1)        3.75us   266.96K
  depth20(1)        6.81us   146.93K
  depth40(1)       11.76us    85.03K
  manyFdes(1)      18.45ms    54.21

The manyFdes case improves from ~13s to ~18ms (~700x speedup).

Note: there are no existing tests in the GCC testsuite for the
sdata4 binary search path in find_fde_tail (the PT_GNU_EH_FRAME /
dl_iterate_phdr path).  

Bootstrapped and regression tested on x86_64-pc-linux-gnu.

Farid Zakaria (1):
  libgcc: Add sdata8 binary search support to _Unwind_Find_FDE

 libgcc/unwind-dw2-fde-dip.c | 64 ++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 15 deletions(-)

-- 
2.52.0