From patchwork Wed Apr 26 14:16:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Matz X-Patchwork-Id: 87876 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp277488vqo; Wed, 26 Apr 2023 07:17:06 -0700 (PDT) X-Google-Smtp-Source: AKy350bZs2Th5BPgnf1nq+5tvszNOJuQccWWSSMCVYomCLMf+4IE+4KfFknuSo6IiIf77PhwNHHn X-Received: by 2002:aa7:dbcc:0:b0:506:bf7e:6312 with SMTP id v12-20020aa7dbcc000000b00506bf7e6312mr16818800edt.1.1682518626359; Wed, 26 Apr 2023 07:17:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1682518626; cv=none; d=google.com; s=arc-20160816; b=Y+MsTHl6nr4LQDjAgJ7c/2d3FwWUgtOg6sv4ul9nXDhck5wxmoAUj+Oqhl/UhLv/Kf VPaUqrlSunbO+Ztn6ndQmQEpTYA8XKYdmA7RHXO/7R6fPQzEWZlwBPVf1ItS+FYzxXqc vK0AIQf6QajfgtPz+konCb0NQ0FX6f3jWmulXxxEh9lnfxe5G9TL+udMmAATW+Xc0pj2 mACXhzf8hdACFJdVkhK4mIm1XV8x2DPhchtvGKVwm5cKJ7x5Rf8hUHiOHpIHU6/7Eany qvGZEPwVFxmEYmPr0/oorrIRehcYCTLvUwLsKQq0AjszSHgyCFmqpM45ChJUs7dhibLn GAvA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:mime-version :user-agent:message-id:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=CROwBDPk10wrHXetNSiwrMgCG0tT3IhQlAWzFn0DpKM=; b=tiVd/dRRw7429Nh/L+04FAtWaRIhMKwjWd6rcD0RajSXmAkvockHXVcYheaQX6kkV6 MgChNzNPhW4i+8tSt9ql9lVVDPap12xcJTkBAojaJ4nmETalE9On2hoVorKnywVWklPD ecQ6JVhg4SFz/OM+7Y/XGbssInkPbumJi8zvVfH/ZoXGyvCOJ0za8c3j9CSXBHZEk8tH J22rTyCR+Bm9BE6slFNwqGEpQXk7UOH7lpLjmDTQuu7IWteZyN3iyx6wwggxbErthFPx UtFhF39o4hQM+XuUYmAag6qYaHnUj6AvyAlFhhLazDj0UrOzZssRl7YLN8uXu1wNWG2P +JoA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=UHuPyOTN; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id w7-20020a50fa87000000b005068d7657f1si9999772edr.599.2023.04.26.07.17.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Apr 2023 07:17:06 -0700 (PDT) Received-SPF: pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=UHuPyOTN; spf=pass (google.com: domain of binutils-bounces+ouuuleilei=gmail.com@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="binutils-bounces+ouuuleilei=gmail.com@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0523F3858401 for ; Wed, 26 Apr 2023 14:17:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0523F3858401 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1682518625; bh=CROwBDPk10wrHXetNSiwrMgCG0tT3IhQlAWzFn0DpKM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=UHuPyOTN2JPT8Y/+ZmI/yvVVZspSw0Adxfw/TrCFPgPwGb6Ib8DCCmmpjZfQLL9W8 jNVQZAx/hmb/j/aQzQPE/AgFAWLPNT/hjZw0tErsR5Twk3xi9uROQF/xX48TnnOt48 0L4OCPIGxUZi9z1+Ue73VjEU/FQP3E6q17naD5H4= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 8A6ED3858C53 for ; Wed, 26 Apr 2023 14:16:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8A6ED3858C53 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id AA7D11FDD0 for ; Wed, 26 Apr 2023 14:16:55 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id A23762C141 for ; Wed, 26 Apr 2023 14:16:55 +0000 (UTC) Received: by wotan.suse.de (Postfix, from userid 10510) id 9493E6419; Wed, 26 Apr 2023 14:16:55 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by wotan.suse.de (Postfix) with ESMTP id 93001636D for ; Wed, 26 Apr 2023 14:16:55 +0000 (UTC) Date: Wed, 26 Apr 2023 14:16:55 +0000 (UTC) To: binutils@sourceware.org Subject: [PATCH] Fix PR30358, performance with --sort-section Message-ID: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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-Patchwork-Original-From: Michael Matz via Binutils From: Michael Matz Reply-To: Michael Matz Errors-To: binutils-bounces+ouuuleilei=gmail.com@sourceware.org Sender: "Binutils" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1764248651164317773?= X-GMAIL-MSGID: =?utf-8?q?1764248651164317773?= since af31506c we only use the binary tree when section sorting is required. While its unbalanced and hence can degrade to a linear list it should otherwise have been equivalent to the old code relying on insertion sort. Unfortunately it was not. The old code directly used lang_add_section to populate the sorted list, the new code first populates the tree and only then does lang_add_section on the sorted result. In the testcase we have very many linkonce section groups, and hence lang_add_section won't actually insert anything for most of them. That limited the to-be-sorted list length previously. The tree-sorting code OTOH first created a tree of all candidates sections, including those that wouldn't be inserted by lang_add_section, hence increasing the size of the sorting problem. In the testcase the chain length went from about 1500 to 106000, and in the degenerated case (as in the testcase) that goes in quadratically. This splits out most of the early-out code from lang_add_section to its own function and uses the latter to avoid inserting into the tree. This refactoring slightly changes the order of early-out tests (the ones based on section flags is now done last, and only in lang_add_section). The new function is not a pure predicate: it can give warnings and it might change output_section, like the old early-out code did. I have also added a skip-warning case in the first discard case, whose non-existence seemed to have been an oversight. PR 30358 * ldlang.c (wont_add_section_p): Split out from ... (lang_add_section): ... here. (output_section_callback_sort): Use wont_add_section_p to not always add sections to the sort tree. --- Of course it would also be nice if the sort tree would be balanced (or some other non-O(n^2) sorting structure be used). But even then it's better to not even have to sort stuff that's not going to be included in the link. Either way, until such time this patch restores performance in the degenerate cases. Tested on 158 targets without regressions. Okay for master? --- ld/ldlang.c | 92 +++++++++++++++++++++++++++++++++++------------------ 1 file changed, 61 insertions(+), 31 deletions(-) diff --git a/ld/ldlang.c b/ld/ldlang.c index 9ad405aa06c..aa01c81e661 100644 --- a/ld/ldlang.c +++ b/ld/ldlang.c @@ -80,6 +80,8 @@ static unsigned int opb_shift = 0; /* Forward declarations. */ static void exp_init_os (etree_type *); static lang_input_statement_type *lookup_name (const char *); +static bool wont_add_section_p (asection *, + lang_output_section_statement_type *); static void insert_undefined (const char *); static bool sort_def_symbol (struct bfd_link_hash_entry *, void *); static lang_statement_union_type *new_statement (enum statement_enum type, @@ -687,6 +689,11 @@ output_section_callback_sort (lang_wild_statement_type *ptr, if (unique_section_p (section, os)) return; + /* Don't add sections to the tree when we already know that + lang_add_section won't do anything with it. */ + if (wont_add_section_p (section, os)) + return; + node = (lang_section_bst_type *) xmalloc (sizeof (lang_section_bst_type)); node->left = 0; node->right = 0; @@ -2514,27 +2521,20 @@ lang_discard_section_p (asection *section) return discard; } -/* The wild routines. - - These expand statements like *(.text) and foo.o to a list of - explicit actions, like foo.o(.text), bar.o(.text) and - foo.o(.text, .data). */ +/* Return TRUE if SECTION is never going to be added to output statement + OUTPUT. lang_add_section() definitely won't do anything with SECTION + if this returns TRUE. It may do something (or not) if this returns FALSE. -/* Add SECTION to the output section OUTPUT. Do this by creating a - lang_input_section statement which is placed at PTR. */ + Can be used as early-out to filter matches. This may set + output_section of SECTION, if it was unset, to the abs section in case + we discover SECTION to be always discarded. This may also give + warning messages. */ -void -lang_add_section (lang_statement_list_type *ptr, - asection *section, - struct wildcard_list *pattern, - struct flag_info *sflag_info, - lang_output_section_statement_type *output) +static bool +wont_add_section_p (asection *section, + lang_output_section_statement_type *output) { - flagword flags = section->flags; - bool discard; - lang_input_section_type *new_section; - bfd *abfd = link_info.output_bfd; /* Is this section one we know should be discarded? */ discard = lang_discard_section_p (section); @@ -2548,41 +2548,35 @@ lang_add_section (lang_statement_list_type *ptr, { if (section->output_section == NULL) { - /* This prevents future calls from assigning this section. */ + /* This prevents future calls from assigning this section or + warning about it again. */ section->output_section = bfd_abs_section_ptr; } + else if (bfd_is_abs_section (section->output_section)) + ; else if (link_info.non_contiguous_regions_warnings) einfo (_("%P:%pS: warning: --enable-non-contiguous-regions makes " "section `%pA' from `%pB' match /DISCARD/ clause.\n"), NULL, section, section->owner); - return; - } - - if (sflag_info) - { - bool keep; - - keep = bfd_lookup_section_flags (&link_info, sflag_info, section); - if (!keep) - return; + return true; } if (section->output_section != NULL) { if (!link_info.non_contiguous_regions) - return; + return true; /* SECTION has already been handled in a special way (eg. LINK_ONCE): skip it. */ if (bfd_is_abs_section (section->output_section)) - return; + return true; /* Already assigned to the same output section, do not process it again, to avoid creating loops between duplicate sections later. */ if (section->output_section == output->bfd_section) - return; + return true; if (link_info.non_contiguous_regions_warnings && output->bfd_section) einfo (_("%P:%pS: warning: --enable-non-contiguous-regions may " @@ -2597,6 +2591,42 @@ lang_add_section (lang_statement_list_type *ptr, size_input_section as appropriate. */ } + return false; +} + +/* The wild routines. + + These expand statements like *(.text) and foo.o to a list of + explicit actions, like foo.o(.text), bar.o(.text) and + foo.o(.text, .data). */ + +/* Add SECTION to the output section OUTPUT. Do this by creating a + lang_input_section statement which is placed at PTR. */ + +void +lang_add_section (lang_statement_list_type *ptr, + asection *section, + struct wildcard_list *pattern, + struct flag_info *sflag_info, + lang_output_section_statement_type *output) +{ + flagword flags = section->flags; + + lang_input_section_type *new_section; + bfd *abfd = link_info.output_bfd; + + if (wont_add_section_p (section, output)) + return; + + if (sflag_info) + { + bool keep; + + keep = bfd_lookup_section_flags (&link_info, sflag_info, section); + if (!keep) + return; + } + /* We don't copy the SEC_NEVER_LOAD flag from an input section to an output section, because we want to be able to include a SEC_NEVER_LOAD section in the middle of an otherwise loaded