[PATCH] Optimize do_read_32_relocated using binary search

[Nikita Popov]

debugedit is currently very slow when processing DWARF 5 debuginfo
produced by clang. For some kernel modules, debugedit processing
takes hours.

The root cause of the issue is the loop for finding the correct
REL entry in do_read_32_relocated. This is currently a simple
linear scan. For large objects, it may loop for hundreds of
thousands of iterations.

As the relocations are sorted, we can use a binary search instead,
which is what this patch implements. The time to run debugedit on
a large kernel module (nouveau.ko) drops down to 3 seconds with
this change.

Signed-off-by: Nikita Popov <npopov@redhat.com>
---
 tools/debugedit.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/tools/debugedit.c b/tools/debugedit.c
index f16eecd..d678673 100644
--- a/tools/debugedit.c
+++ b/tools/debugedit.c
@@ -335,12 +335,27 @@ strptr (DSO *dso, size_t sec, size_t offset)
 REL *relptr, *relend;
 int reltype;

+static inline REL *find_rel_for_ptr(unsigned char *xptr)
+{
+  size_t l = 0, r = relend - relptr;
+  while (l < r)
+  {
+    size_t m = (l + r) / 2;
+    if (relptr[m].ptr < xptr)
+      l = m + 1;
+    else if (relptr[m].ptr > xptr)
+      r = m;
+    else
+      return &relptr[m];
+  }
+  return relend;
+}
+
 #define do_read_32_relocated(xptr) ({ \
   uint32_t dret = do_read_32 (xptr); \
   if (relptr) \
     { \
-      while (relptr < relend && relptr->ptr < (xptr)) \
- ++relptr; \
+      relptr = find_rel_for_ptr((xptr)); \
       if (relptr < relend && relptr->ptr == (xptr)) \
  { \
   if (reltype == SHT_REL) \
-- 
2.44.0
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://sourceware.org/pipermail/debugedit/attachments/20240417/7e7858f0/attachment.htm>