From: Nikita Popov <npopov@redhat.com>
To: debugedit@sourceware.org
Subject: [PATCH] Optimize do_read_32_relocated using binary search
Date: Wed, 17 Apr 2024 15:34:19 +0900 [thread overview]
Message-ID: <CAFUfLSV-RtBkOcq0C1xCenAf_-rEL6g72y-hsV1PDz5QS7OR8w@mail.gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1586 bytes --]
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 reply other threads:[~2024-04-17 6:34 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-17 6:34 Nikita Popov [this message]
2024-04-17 14:49 ` Mark Wielaard
2024-05-15 13:38 ` Mark Wielaard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAFUfLSV-RtBkOcq0C1xCenAf_-rEL6g72y-hsV1PDz5QS7OR8w@mail.gmail.com \
--to=npopov@redhat.com \
--cc=debugedit@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).