From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 05ED43858D20 for ; Wed, 17 Apr 2024 06:34:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 05ED43858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 05ED43858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1713335698; cv=none; b=P50qJ+VpblByHu+va5bVn8BT5crjELvbLCNst5e++c/184bRCh4VXx4zB1z/0OUXlTutOS9nDvk1jlAE9Zt4CKgHd6NvMqp/vzoWscr+J/xWUqhek9SZoXDuNQ8b0r1yTqvO54tGixnXO11zO3Qo+F4vVox2YeNXOinm6nA7Znk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1713335698; c=relaxed/simple; bh=8mMPTNelbuFE6V9b8INjsoBSoLl402bIp+GCGcQEfgw=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=gjjmGsMq4mK1gEUnlvEVe8S89SpiITjzLKge3IDrkXYdpyKr1z7yoUyKj5fYFuYVDC3dlcuxkdM/AmG4ahJRcN4yNsJOkUko4cPS1CW13WPZeM97cZgrM4Wpru3yi86h/bOlcIWIuRLTsY7eWfc6q81F/qd7qv2O+RcdaC2ezig= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1713335691; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=eghUEZfzW61OtIWRHhgoHt5SYZGPjGxUUQBjmFNJvJA=; b=ZptXWH275YyUVl/fIou3kS1BhJQjAvEDmhuMtwQVAPaIyt/dr0pdRjtlxpUgq7fI6i5yq2 TP0F5KnuRQY9/xsu0W13nuLhZpMKEqxxAooSE/IPdzSNWC4maOgf51mue3vxmT+ZaDvtq0 Rr8a4MzL2x7GbCnmfA30AlE3j7XO60Y= Received: from mail-ej1-f69.google.com (mail-ej1-f69.google.com [209.85.218.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-588-FQjVnplNOrSLZuF2lnMkDg-1; Wed, 17 Apr 2024 02:34:48 -0400 X-MC-Unique: FQjVnplNOrSLZuF2lnMkDg-1 Received: by mail-ej1-f69.google.com with SMTP id a640c23a62f3a-a51cb1feb23so193889266b.1 for ; Tue, 16 Apr 2024 23:34:48 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713335686; x=1713940486; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=e46KX0Dd4xKsf9Bi9taTbpuuL5Sq4lQHlMwadKUpVIU=; b=o21yx3s+SuGcNYEPquBMBMG3qQcSl1h4sH3cFoxBi+Q8k2jKRdoPRyKEYX3wbuhAA7 OoKDnJuIyr9NpBtk64iQFX3rDHCcRwK0dTShYF21TkBbIeRfNFR7tJXhKEqhlHR5t1LN B1y5Tnnv+3WGFZQuLFJYyCHEg+vknyH8sjslMIfgtD/HZDcdWdB+xg1fDsL2hS9ZP5BE WB0nbhF39cFJ/HGo+ydHR6ufJIUhSbBC+N8KWX7i1TRqV8kZ4ZWAurvIflDnawLWakKQ Lir801T9pdfI4ryYu+n/apK75AXpB+y3CyJVOWLGKHYY92GbJtin9vCNtyu1hclM3hR1 Ff4A== X-Gm-Message-State: AOJu0YybK9flJa++7GF66doBlMOT3+0xCRnCW8IERUuR2VsufMIPqHkW HoFhZ0EYiQSWfl0zlaKECmpivzybztGxmrE+FyFWSTDs2DrQZlh972vf+csWUU7OrT0AsryM/GG mW7Tike74irDgh1ru4vYl67ec8ct3/EUIUF18bPx29EZ80ep/s9fCJuRSU+LcL9DONSb7oVHdJZ Kb9wTBfJPqcolqVmgjjduW/oNmhznnk9tnDpYQgzI9gA== X-Received: by 2002:a17:907:d8a:b0:a55:38e2:75a3 with SMTP id go10-20020a1709070d8a00b00a5538e275a3mr3644367ejc.16.1713335686789; Tue, 16 Apr 2024 23:34:46 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHqIRJuj+mLOQ4zuO5MPmfu8aOKP+tQvgyk0dNk1i9qMyh/G0fCo4XANl+vyJWCkBBbNmXkGtwwBIY0qdjRAxw= X-Received: by 2002:a17:907:d8a:b0:a55:38e2:75a3 with SMTP id go10-20020a1709070d8a00b00a5538e275a3mr3644354ejc.16.1713335686288; Tue, 16 Apr 2024 23:34:46 -0700 (PDT) MIME-Version: 1.0 From: Nikita Popov Date: Wed, 17 Apr 2024 15:34:19 +0900 Message-ID: Subject: [PATCH] Optimize do_read_32_relocated using binary search To: debugedit@sourceware.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/alternative; boundary="000000000000f66cc30616450c48" X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --000000000000f66cc30616450c48 Content-Type: text/plain; charset="UTF-8" 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 --- 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 --000000000000f66cc30616450c48--