Re: [PATCH] Optimize do_read_32_relocated using binary search

[Mark Wielaard <mark@klomp.org>]

[-- Attachment #1: Type: text/plain, Size: 182 bytes --]

Hi,

I finally pushed this (already tested in Fedora rawhide).
I have some followup patches to handle relocations and strx better.
But this patch is correct.

Cheers,

Mark

[-- Attachment #2: 0001-Optimize-do_read_32_relocated-using-binary-search.patch --]
[-- Type: text/x-patch, Size: 1843 bytes --]

From fbad879eb03f7ecd58a9919865c84b422a473b37 Mon Sep 17 00:00:00 2001
From: Nikita Popov <npopov@redhat.com>
Date: Wed, 17 Apr 2024 15:34:19 +0900
Subject: [PATCH] Optimize do_read_32_relocated using binary search

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 | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)

diff --git a/tools/debugedit.c b/tools/debugedit.c
index f16eecd89a61..ae8e38fa58da 100644
--- a/tools/debugedit.c
+++ b/tools/debugedit.c
@@ -335,12 +335,28 @@ 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.45.0