From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from de-smtp-delivery-102.mimecast.com (de-smtp-delivery-102.mimecast.com [194.104.109.102]) by sourceware.org (Postfix) with ESMTPS id 6AD22385AC0F for ; Tue, 29 Mar 2022 06:07:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6AD22385AC0F Received: from EUR02-AM5-obe.outbound.protection.outlook.com (mail-am5eur02lp2058.outbound.protection.outlook.com [104.47.4.58]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id de-mta-15-gePP9pKLPmajZcMNuYENIA-1; Tue, 29 Mar 2022 08:07:11 +0200 X-MC-Unique: gePP9pKLPmajZcMNuYENIA-1 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZwLmxLoqaVzEr5yiV8cf6zVIZk+y0p99pr5R5R29u6FVPjzrqys8UmR32HoE7Ctqnpva/SPv7W8ZdffoYIo7D+ocnOsyphqiVvoNUkYNlnR/DAGR7WZKpwC/NzLMXK/mPn3HA0mer8oWo3yyN9tzGJIeaXUrdnHlqxyHEco7fnA75h4V9veJKOIH6kQciK2gf+POKiuh/zOiZZMk8hALSO2ap9zNkfVFI3Q+dyJkkwXIf6563H8+lmlv25PF6H6gEyfjJStjvXzfutN3VZLwV2oFJ1Gtv8XwvhmX7TlJR6q7WVbdwPp1PXx2h+bxKX/P7CVvjsLRGreet9uRa8ORnA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=+GCcqcUHXia1OIsD9rkO7IUJ2flBhS+yiO3PnHHrqJ4=; b=SQtDy4t0jupCRiGvuBMMKSoL3f0eg1lsti/fdxGc0a28SdaoNPm8CQOvpBBq0UiMN2M8mN7JFet04h1XdtViKi1bheipMAaCsuc0j0x3JsK20O39F/pXRBQYAGg/xzXBB3djV4O4imsX3qq8AqNgjkF3yEiVBshI0fA9ShkZ9/BiMItZTaxtpeCa+xZZrQRsJGsH0YQ5UCCMwkLDlHL6+lQ3uZQ3oqMnqyAVB7rNn9bCE1rmlJ7j3LcNyoYUko6R59yZ6S05FVyjqDksLCGZaoC+g2wlwKxI5GoFNo9IACyboHDoX4tibgZ95pnIS8/t61uSIaV01IeaDnis51Ki+A== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=suse.com; dmarc=pass action=none header.from=suse.com; dkim=pass header.d=suse.com; arc=none Received: from DU2PR04MB8616.eurprd04.prod.outlook.com (2603:10a6:10:2db::16) by VI1PR0401MB2639.eurprd04.prod.outlook.com (2603:10a6:800:58::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.23; Tue, 29 Mar 2022 06:07:08 +0000 Received: from DU2PR04MB8616.eurprd04.prod.outlook.com ([fe80::914d:e08d:7798:8476]) by DU2PR04MB8616.eurprd04.prod.outlook.com ([fe80::914d:e08d:7798:8476%5]) with mapi id 15.20.5102.023; Tue, 29 Mar 2022 06:07:08 +0000 Message-ID: <6c45bf8e-00e5-f7c6-025b-e4b9c3832da3@suse.com> Date: Tue, 29 Mar 2022 08:07:07 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 Subject: Re: [PATCH] Add a trie to map quickly from address range to compilation unit. Content-Language: en-US To: Alan Modra CC: sesse@chromium.org, binutils@sourceware.org, "Steinar H. Gunderson" , Nick Clifton References: <20220321094030.1256430-1-sesse@google.com> <63191455-2374-5db9-f55e-ddf794c7d88e@redhat.com> <49afcaee-63a8-2d18-64d1-0fc0abfe4669@suse.com> From: Jan Beulich In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: AM7PR02CA0012.eurprd02.prod.outlook.com (2603:10a6:20b:100::22) To DU2PR04MB8616.eurprd04.prod.outlook.com (2603:10a6:10:2db::16) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 9a8d21e9-fd68-4ad5-48f8-08da114a5b5a X-MS-TrafficTypeDiagnostic: VI1PR0401MB2639:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: DVSlGWSVQpztmC0txALUifRKWBVMo4FlR1JfGb8CJSPWrQHDn+NwGHSeYBh3MU/JFyffvx6MbEKf0nuDP1IvBtFGwS+567IGCNK2kL/40Sr1XKsCnMBTMeyntV/xvLhMNCI38VXASGAA3luPJIcsNr1qcFWBt1YA8CAFplh/yE1FrhkVA8HnYBUKqoFP1vNpJp+Eio1blM5OTh9UC4kyTjic67BbRA0CL9MJuBhL+hppfAjwXX2ja+5XUMk45O1AAN5/dEQvESJgsQ6FZnucVYdRKjPa+rOwxTtFt0+LLvo4g45V72BY8sxTGP/coEB09Q9rFPmk1X3feJrm26DO0okT8AhZVBume7U9eSeZ+DKBbOW/LKDKkicR+sGhllfYnjEfAJYoiY8CbGMaDtPhSOzLGPGnCI7/ASubTmH6p3NacodS2HQ3H+WK8HWxPUPfUj+imX1rgXvv/uqd3TfSBbcoyOhqhxJedV80167SGfvZyGau0Y/Dpxs5wMeKC5VQfavkCOeRlW84A+SMDXy4/HeZZ6tmgDE3dix1vpIpnu0krbR0umtO86vzWtYGx4hR4U+LIn2TPxTltKccYIGW+7h5zbJjoBlJsT0gMAhJVhGbU4Xg6s4hQlP61IAknju0oUruCEiI3ERFbbMwcI26/tzzr6bcv+4+1XvB4++9zsuompziAwet8Ynk1CKnbOIKvwxiuCqfHykkoafuMkRLbHfQXD8IVGumd7R6Y2M5Sbv2K6Lg7c4iHG63qXkk9aXmzhhmOoLhS9aWeRd0WqXzb90SdQZ0pRIn5LPPpEGsb6Tix6r+Dl4ckZD5cqRi8BeDrpjGPkNCqMjFzqLL7m4BbPxKKpJnTZi0jhHzZa7SVkYJso7L4/n5R3VzfqW5gVQf X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:DU2PR04MB8616.eurprd04.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230001)(366004)(53546011)(6512007)(6506007)(316002)(186003)(2616005)(26005)(83380400001)(36756003)(31686004)(6916009)(8676002)(31696002)(66476007)(66556008)(2906002)(508600001)(966005)(38100700002)(6486002)(66946007)(86362001)(54906003)(4326008)(8936002)(5660300002)(45980500001)(43740500002); DIR:OUT; SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?Dni6XJep/ynhzGwCUwLyyijUctRrvKcAMdNGHmfWx7ymD/jNbtcwZBYGyKyL?= =?us-ascii?Q?JBvisp+1XWspPhJxosSsHeHE22hJbcM8fBUVk90o67nebSrM/xJKLhGeUbpq?= =?us-ascii?Q?kaI5rIofo3sFNf4OWgbWLQ69hfYufuwv4DSVJByCi9RXm0dyQx+y/iJ5xWuX?= =?us-ascii?Q?XnyOPnsUjB9TEpaBg8zDpIiTQMPK1h5RuXBXcWaaHuCooWlgTI4hMU98kGKO?= =?us-ascii?Q?I22Xizv8iGMQwARRhobk1v/UztX6IhjWB07ZmKBfeagPf2IH38v2opO1Oycv?= =?us-ascii?Q?90YkyxMKX4rgmbxnukdAeUqEjck+/0Vs7t5RyvdU66LCTY9GN77PdNgU/csO?= =?us-ascii?Q?LMuo6KFigLTVgBkTamfOTDRrhWK2NkxAGQwY4V16rb5pY5r6yByUEabM8ODu?= =?us-ascii?Q?UXRCWdRLgrbwbs6Y/P3F3fZpSrklKRozGv5p+MU0ywPivaKa1k501LCTurqY?= =?us-ascii?Q?Z037tGOeViezUo0oJXL6Nxrh3fwaCkhagCbePph20xz1ad5h5fufNoG/8f8f?= =?us-ascii?Q?S9EaEvx2ePDqWh50i68cKbqee2NdBZm+4PamDaDqySF5vEfwmgh3r0m2byoL?= =?us-ascii?Q?ns7YjamTj7LXdV5J1TYVsID2miyB+g7KxEc99lMGXZny0QZcplNF9wUue/Xs?= =?us-ascii?Q?xuB63zYa66T9d4SEzwbLRmgJ8a46pepaK5Nia+9Lzhh7x92Q9qzZl/EOolgd?= =?us-ascii?Q?596R1imaPAuhoEHN7jGJXyivw40m0wO5VVhYswT4n9kyL12bkinWvhi7YAva?= =?us-ascii?Q?UdBqiOzuD7+quBXXjRZ4Av1EMWAdGkx/cega5vnLc2mXTPFYQ7vYqp44UiIO?= =?us-ascii?Q?yrMqotL04VblUVj3G/J86DDVL7nIflx7biBLfhFS3UXbKOCDkKXS/uk1ySB7?= =?us-ascii?Q?KvGjEMAjRkLBA9ko96jMhw9JH+cbCG1MrpvwjsNOKrED7LS3HFheUpNjORlx?= =?us-ascii?Q?+bGP86+Wfg0CuaKmeJkmOXJx5s256N0UgAkDLzedrrJE4keuG3iuyNJ1eoi3?= =?us-ascii?Q?sYGgKA4F4JFL8cf1p6muwOMsvxjdpPhMHZV4kQPRKl7/IURoVz6eFvNxIZwx?= =?us-ascii?Q?TjVG+AeMcqPFSR8UYcmYgq9fNlRGC01+8HwSAHxXLXagmdAEA+LHHOrLYWcW?= =?us-ascii?Q?m5fqybsTc2zqCxRdTWRhkUnZEWuHTQIuR2dwhlH5b5KLbwj+eZr8fPV1fMCZ?= =?us-ascii?Q?q8GgH9WvG0IoaRFE40c1IQrIsu0WbBs8d2yu6oietj0PHAr8vZUpnGyoikw4?= =?us-ascii?Q?G8N69ynnF90n6VaAzG0M3W6Pknkr4z2F3g72l02FmrfTnIivX/IpkLm2op5u?= =?us-ascii?Q?0iX0QrnQyeLadxklZ8vjLkvEol6Cw4AMBS+pVvMKc/hWzcI6QQzewu8ou0uZ?= =?us-ascii?Q?a4nz3OMZvEydQ7sKjLtSUvkVZ+dNOOj/6iN9DiLwnFBYtNXreqKVHjQoLtqX?= =?us-ascii?Q?TF1f5AitQPVWCVkgxZGOarfqipzAgRUT6SYaVSnPvxG2BBnImJUERqMqM1iq?= =?us-ascii?Q?eP1tF/zKsqZwAsue7MTQQ6F5zyBmZNf/WRyHSjEJkl+HSf2BjiiN3Z4FFvLQ?= =?us-ascii?Q?BBQknEkcIgqSp/lOD+N8HEoAm1/wIjamV8RqLhg0/0aLlah0M3l0gqPI//b4?= =?us-ascii?Q?mEGJjbctOwIQvFiSZ6O3x6AxNFqHgqZ505tfjMUTF8yFhh0jY5Kf79HKMroj?= =?us-ascii?Q?PiDc05jGH+zHvhGetWwfm9/zxnO0pMTC6Qz0AeejLc4TNqy47jU+ctgPJGTM?= =?us-ascii?Q?9c4Xu8s1cg=3D=3D?= X-OriginatorOrg: suse.com X-MS-Exchange-CrossTenant-Network-Message-Id: 9a8d21e9-fd68-4ad5-48f8-08da114a5b5a X-MS-Exchange-CrossTenant-AuthSource: DU2PR04MB8616.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 29 Mar 2022 06:07:08.5335 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: f7a17af6-1c5c-4a36-aa8b-f5be247aa4ba X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: dIa5VE92Y8v1+WFA2VtOYf+kxPkGWv/QB8ZnNuvLQ2DNIK91Rv/7qi9+CThZT2GgRRM4hZZHh670pBfAAQRsIA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0401MB2639 X-Spam-Status: No, score=-3037.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 29 Mar 2022 06:07:19 -0000 On 29.03.2022 01:47, Alan Modra wrote: > On Mon, Mar 28, 2022 at 12:19:52PM +0200, Jan Beulich wrote: >> On 25.03.2022 00:30, Alan Modra via Binutils wrote: >>> On Thu, Mar 24, 2022 at 09:01:38AM +0100, Steinar H. Gunderson wrote: >>>> On Thu, Mar 24, 2022 at 03:52:27PM +1030, Alan Modra wrote: >>>>> Huh, I remember looking at this code a while ago and finding it >>>>> confusing. I think the code would be clearer, and behave the same on >>>>> normal line number info with the following patch: >>>> >>>> An interesting question is: Do you want to keep searching through >>>> compilation units once you've found a match with a line number? >>>> Should we go straight to =E2=80=9Cgoto done=E2=80=9D then? >>> >>> This would be reverting commit 240d6706c6a2. In >>> https://sourceware.org/bugzilla/show_bug.cgi?id=3D15935#c3 I came to th= e >>> conclusion that the pr15935 testcase had bogus debug info and closed >>> the bug as invalid. The reporter apparently opened another bug, >>> https://sourceware.org/bugzilla/show_bug.cgi?id=3D15994 a month later >>> that Nick fixed by making _bfd_dwarf2_find_nearest_line do extra work. >>> Which of course is unnecessary with good debug info, but in many cases >>> we try to make binutils give the best result even with bad input. I >>> don't know the details beyond that. It might have been that the >>> compiler producing the bad debug info was one supported by RedHat. >>> >>> Now we have pr28592 and others complaining that objdump or addr2line >>> have significantly slowed. Given that pr15935 dates back to 2013, I >>> would presume that people have moved on from whatever broken compiler >>> produced bad line info, and that we should indeed revert commit >>> 240d6706c6a2. Nick? >> >> Since I ended up working on that function as well, I did notice another >> potentially relevant aspect: The adjustment done back at the time was >> only for the case of already processed CUs. The subsequent loop reading >> any remaining ones doesn't similarly attempt to find a better match. >> IOW the effects of that change can only have been partial anyway. >=20 > Yes, Steinar noticed that too. Another thing I noticed is that prior > to Nick's original patch looking for the best line range match, we > used to return a function name result for addresses that matched a > DW_TAG_subprogram (and similar) address ramge info. See the > comp_unit_find_nearest_line change in the following, a patch to revert > commit 240d6706c6a2. Yeah, makes sense to me. I guess if bad input was to be worked around again, a testcase covering the specific situation would want adding, so it won't be lost what specifically is to be worked around. Jan > PR 28592 > PR 15994 > PR 15935 > * dwarf2.c (lookup_address_in_line_info_table): Return bool rather > than a range. > (comp_unit_find_nearest_line): Likewise. Return true if function > info found without line info. > (_bfd_dwarf2_find_nearest_line): Revert range handling code. >=20 > diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c > index 8b5ac6012e1..4beebcd2835 100644 > --- a/bfd/dwarf2.c > +++ b/bfd/dwarf2.c > @@ -2543,13 +2543,12 @@ decode_line_info (struct comp_unit *unit) > return NULL; > } > =20 > -/* If ADDR is within TABLE set the output parameters and return the > - range of addresses covered by the entry used to fill them out. > - Otherwise set * FILENAME_PTR to NULL and return 0. > +/* If ADDR is within TABLE set the output parameters and return TRUE, > + otherwise set *FILENAME_PTR to NULL and return FALSE. > The parameters FILENAME_PTR, LINENUMBER_PTR and DISCRIMINATOR_PTR > are pointers to the objects to be filled in. */ > =20 > -static bfd_vma > +static bool > lookup_address_in_line_info_table (struct line_info_table *table, > bfd_vma addr, > const char **filename_ptr, > @@ -2608,12 +2607,12 @@ lookup_address_in_line_info_table (struct line_in= fo_table *table, > *linenumber_ptr =3D info->line; > if (discriminator_ptr) > *discriminator_ptr =3D info->discriminator; > - return seq->last_line->address - seq->low_pc; > + return true; > } > =20 > fail: > *filename_ptr =3D NULL; > - return 0; > + return false; > } > =20 > /* Read in the .debug_ranges section for future reference. */ > @@ -4008,14 +4007,11 @@ comp_unit_contains_address (struct comp_unit *uni= t, bfd_vma addr) > } > =20 > /* If UNIT contains ADDR, set the output parameters to the values for > - the line containing ADDR. The output parameters, FILENAME_PTR, > - FUNCTION_PTR, and LINENUMBER_PTR, are pointers to the objects > - to be filled in. > - > - Returns the range of addresses covered by the entry that was used > - to fill in *LINENUMBER_PTR or 0 if it was not filled in. */ > + the line containing ADDR and return TRUE. Otherwise return FALSE. > + The output parameters, FILENAME_PTR, FUNCTION_PTR, and > + LINENUMBER_PTR, are pointers to the objects to be filled in. */ > =20 > -static bfd_vma > +static bool > comp_unit_find_nearest_line (struct comp_unit *unit, > bfd_vma addr, > const char **filename_ptr, > @@ -4023,7 +4019,7 @@ comp_unit_find_nearest_line (struct comp_unit *unit= , > unsigned int *linenumber_ptr, > unsigned int *discriminator_ptr) > { > - bool func_p; > + bool line_p, func_p; > =20 > if (!comp_unit_maybe_decode_line_info (unit)) > return false; > @@ -4033,10 +4029,11 @@ comp_unit_find_nearest_line (struct comp_unit *un= it, > if (func_p && (*function_ptr)->tag =3D=3D DW_TAG_inlined_subroutine) > unit->stash->inliner_chain =3D *function_ptr; > =20 > - return lookup_address_in_line_info_table (unit->line_table, addr, > - filename_ptr, > - linenumber_ptr, > - discriminator_ptr); > + line_p =3D lookup_address_in_line_info_table (unit->line_table, addr, > + filename_ptr, > + linenumber_ptr, > + discriminator_ptr); > + return line_p || func_p; > } > =20 > /* Check to see if line info is already decoded in a comp_unit. > @@ -5187,54 +5184,17 @@ _bfd_dwarf2_find_nearest_line (bfd *abfd, > } > else > { > - bfd_vma min_range =3D (bfd_vma) -1; > - const char * local_filename =3D NULL; > - struct funcinfo *local_function =3D NULL; > - unsigned int local_linenumber =3D 0; > - unsigned int local_discriminator =3D 0; > - > for (each =3D stash->f.all_comp_units; each; each =3D each->next_u= nit) > { > - bfd_vma range =3D (bfd_vma) -1; > - > found =3D ((each->arange.high =3D=3D 0 > || comp_unit_contains_address (each, addr)) > - && (range =3D (comp_unit_find_nearest_line > - (each, addr, &local_filename, > - &local_function, &local_linenumber, > - &local_discriminator))) !=3D 0); > + && comp_unit_find_nearest_line (each, addr, > + filename_ptr, > + &function, > + linenumber_ptr, > + discriminator_ptr)); > if (found) > - { > - /* PRs 15935 15994: Bogus debug information may have provided us > - with an erroneous match. We attempt to counter this by > - selecting the match that has the smallest address range > - associated with it. (We are assuming that corrupt debug info > - will tend to result in extra large address ranges rather than > - extra small ranges). > - > - This does mean that we scan through all of the CUs associated > - with the bfd each time this function is called. But this does > - have the benefit of producing consistent results every time the > - function is called. */ > - if (range <=3D min_range) > - { > - if (filename_ptr && local_filename) > - * filename_ptr =3D local_filename; > - if (local_function) > - function =3D local_function; > - if (discriminator_ptr && local_discriminator) > - * discriminator_ptr =3D local_discriminator; > - if (local_linenumber) > - * linenumber_ptr =3D local_linenumber; > - min_range =3D range; > - } > - } > - } > - > - if (* linenumber_ptr) > - { > - found =3D true; > - goto done; > + goto done; > } > } > =20 > @@ -5259,7 +5219,7 @@ _bfd_dwarf2_find_nearest_line (bfd *abfd, > filename_ptr, > &function, > linenumber_ptr, > - discriminator_ptr) !=3D 0); > + discriminator_ptr)); > =20 > if (found) > break; >=20