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
