From patchwork Fri Nov 25 16:44:54 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Matz X-Patchwork-Id: 26094 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp4152216wrr; Fri, 25 Nov 2022 08:45:11 -0800 (PST) X-Google-Smtp-Source: AA0mqf6vPiGrXMnP8rEDVt9v5eEqslnBpPuAuahoEK/JbMeRiSO4KcNNYJ2hegh72kiTfzQIfD3u X-Received: by 2002:a17:906:9255:b0:7ad:c66e:ad9d with SMTP id c21-20020a170906925500b007adc66ead9dmr31710222ejx.413.1669394711248; Fri, 25 Nov 2022 08:45:11 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1669394711; cv=none; d=google.com; s=arc-20160816; b=SfgSAq5nZ47+uWygex5qkmLBSOs+IWi0HzXVPqgcuisViG8ZajgS/yM/u8EYBbWQmj b5dB/c/7+uy15qT5v5MHjPVcs15gcbtVMTgVgv9q1bkEhgXzWGpMw0wU5Hv0ksrAlMNN LkP4jX24kRYUZZHDY0QqnSePNXBWYafiYJ+L8F8It+f2A3fqhJe2MJnNQ22Ev/S5VMhi 01G8eLPK5dFAfbnUmYu0fdSnt/OWY3gm84y4niwSC+2ptSCF+Ghg73DLJrxZvmI/kvwk wEAXW4zMQ/3D01bZypT9zIGB2IQZbH6s3obbzH/ves3Iy9U6gcYIvunD/3gr/s5Eu4Zp 4SoA== 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:references:message-id:in-reply-to:subject:to:date :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=pBiUq8ExWdktUpW3jhVjWj6qtVgscL/Nm/OYGYqikEk=; b=vnnxaVNR0L3iRb71AMTH+C6gR2BZKuCWGz/5jAU/N9R4BmTpaKqlv9guibM782wnTL /iku/E/9AHp/xIwdFzk+IlpC9PC9f2ZSRg1/2icHzxvG0dK2zL9hNn81vrhibWUGvznu 0OHVmQFaWh2S5Tv9c1Yw4hXzsI4FshNCR+L9g3T/HbPB7zZEfVwDyPZnc+DSVRA/DPVt bhmn6jblVJ0Gwc7N56dYt3x+IRWK96OrEEbZ/zn7+Xcr0o0vcVdQc/ZFB1cWEteA4TFy 4UzZ8IPWeimki7oTNdZMQfOSQrQLiQZ+E79r0f2XKGrx9LXkOUTijrWkP5ctsu9NQxa6 yl9g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b="h/byaOld"; 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 go18-20020a1709070d9200b007aeaacd5592si3095262ejc.124.2022.11.25.08.45.11 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 25 Nov 2022 08:45:11 -0800 (PST) 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="h/byaOld"; 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 1DA50384A482 for ; Fri, 25 Nov 2022 16:45:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1DA50384A482 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669394706; bh=pBiUq8ExWdktUpW3jhVjWj6qtVgscL/Nm/OYGYqikEk=; h=Date:To:Subject:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=h/byaOldIa/VDh/TmRcymS78ypMOl8D4xc3cfVZpeEyw5wmtzWaVB8lXotFAhuHcP 7JolvpYVq0YUR7V1LZLKLkAvw/YPdOn+S8eL4tqu+HhsYEOTgM01u6E4T516tzIyj/ 9Vx47bQZbS3PcCJsccBrrxN/QKcd9htUC7FdliqA= X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 97D22384E396 for ; Fri, 25 Nov 2022 16:44:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 97D22384E396 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id D3A8E1FD84 for ; Fri, 25 Nov 2022 16:44:54 +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 CF3592C141 for ; Fri, 25 Nov 2022 16:44:54 +0000 (UTC) Received: by wotan.suse.de (Postfix, from userid 10510) id C96816586; Fri, 25 Nov 2022 16:44:54 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by wotan.suse.de (Postfix) with ESMTP id C832C6238 for ; Fri, 25 Nov 2022 16:44:54 +0000 (UTC) Date: Fri, 25 Nov 2022 16:44:54 +0000 (UTC) To: binutils@sourceware.org Subject: [PATCH 1/8] section-select: Lazily resolve section matches In-Reply-To: Message-ID: References: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 X-Spam-Status: No, score=-9.1 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 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?1750487228955273424?= X-GMAIL-MSGID: =?utf-8?q?1750487228955273424?= and remember the results. Before this the order of section matching is basically: foreach script-wild-stmt S foreach pattern P of S foreach inputfile I foreach section S of I match S against P if match: do action for S And this process is done three or four times: for each top-level call to walk_wild() or wild(), that is: check_input_sections, lang_gc_sections, lang_find_relro_sections and of course map_input_to_output_sections. So we iterate over all sections of all files many many times (for each glob). Reality is a bit more complicated (some special glob types don't need the full iteration over all sections, only over all files), but that's the gist of it. For future work this shuffles the whole ordering a bit by lazily doing the matching process and memoizing results, trading a little memory for a 75% speedup of the overall section selection process. This lazy resolution introduces a problem with sections added late that's corrected in the next patch. --- ld/ldlang.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++- ld/ldlang.h | 12 ++++++++ 2 files changed, 99 insertions(+), 1 deletion(-) diff --git a/ld/ldlang.c b/ld/ldlang.c index 81a6aeb7a89..c92ebd472f4 100644 --- a/ld/ldlang.c +++ b/ld/ldlang.c @@ -1072,8 +1072,27 @@ walk_wild_file (lang_wild_statement_type *s, } } +static lang_statement_union_type * +new_statement (enum statement_enum type, + size_t size, + lang_statement_list_type *list); static void -walk_wild (lang_wild_statement_type *s, callback_t callback, void *data) +add_matching_callback (lang_wild_statement_type *ptr, + struct wildcard_list *sec, + asection *section, + lang_input_statement_type *file, + void *data ATTRIBUTE_UNUSED) +{ + lang_input_matcher_type *new_section; + /* Add a section reference to the list. */ + new_section = new_stat (lang_input_matcher, &ptr->matching_sections); + new_section->section = section; + new_section->pattern = sec; + new_section->input_stmt = file; +} + +static void +walk_wild_resolve (lang_wild_statement_type *s) { const char *file_spec = s->filename; char *p; @@ -1083,6 +1102,66 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data) /* Perform the iteration over all files in the list. */ LANG_FOR_EACH_INPUT_STATEMENT (f) { + //printf("XXX %s\n", f->filename); + walk_wild_file (s, f, add_matching_callback, NULL); + } + } + else if ((p = archive_path (file_spec)) != NULL) + { + LANG_FOR_EACH_INPUT_STATEMENT (f) + { + if (input_statement_is_archive_path (file_spec, p, f)) + walk_wild_file (s, f, add_matching_callback, NULL); + } + } + else if (wildcardp (file_spec)) + { + LANG_FOR_EACH_INPUT_STATEMENT (f) + { + if (fnmatch (file_spec, f->filename, 0) == 0) + walk_wild_file (s, f, add_matching_callback, NULL); + } + } + else + { + lang_input_statement_type *f; + + /* Perform the iteration over a single file. */ + f = lookup_name (file_spec); + if (f) + walk_wild_file (s, f, add_matching_callback, NULL); + } +} + +static void +walk_wild (lang_wild_statement_type *s, callback_t callback, void *data) +{ + const char *file_spec = s->filename; + //char *p; + + if (!s->resolved) + { + //printf("XXX %s\n", file_spec ? file_spec : ""); + walk_wild_resolve (s); + s->resolved = true; + } + + { + lang_statement_union_type *l; + for (l = s->matching_sections.head; l; l = l->header.next) + { + (*callback) (s, l->input_matcher.pattern, l->input_matcher.section, l->input_matcher.input_stmt, data); + } + return; + } + +#if 0 + if (file_spec == NULL) + { + /* Perform the iteration over all files in the list. */ + LANG_FOR_EACH_INPUT_STATEMENT (f) + { + printf("XXX %s\n", f->filename); walk_wild_file (s, f, callback, data); } } @@ -1111,6 +1190,7 @@ walk_wild (lang_wild_statement_type *s, callback_t callback, void *data) if (f) walk_wild_file (s, f, callback, data); } +#endif } /* lang_for_each_statement walks the parse tree and calls the provided @@ -1982,6 +2062,8 @@ insert_os_after (lang_output_section_statement_type *after) case lang_group_statement_enum: case lang_insert_statement_enum: continue; + case lang_input_matcher_enum: + FAIL (); } break; } @@ -4347,6 +4429,8 @@ map_input_to_output_sections break; case lang_insert_statement_enum: break; + case lang_input_matcher_enum: + FAIL (); } } } @@ -8343,6 +8427,8 @@ lang_add_wild (struct wildcard_spec *filespec, new_stmt->section_list = section_list; new_stmt->keep_sections = keep_sections; lang_list_init (&new_stmt->children); + new_stmt->resolved = false; + lang_list_init (&new_stmt->matching_sections); analyze_walk_wild_section_handler (new_stmt); } diff --git a/ld/ldlang.h b/ld/ldlang.h index 713c5282b55..50ad64ce057 100644 --- a/ld/ldlang.h +++ b/ld/ldlang.h @@ -76,6 +76,7 @@ enum statement_enum lang_fill_statement_enum, lang_group_statement_enum, lang_input_section_enum, + lang_input_matcher_enum, lang_input_statement_enum, lang_insert_statement_enum, lang_output_section_statement_enum, @@ -335,6 +336,14 @@ typedef struct void *pattern; } lang_input_section_type; +typedef struct +{ + lang_statement_header_type header; + asection *section; + void *pattern; + lang_input_statement_type *input_stmt; +} lang_input_matcher_type; + struct map_symbol_def { struct bfd_link_hash_entry *entry; struct map_symbol_def *next; @@ -389,6 +398,8 @@ struct lang_wild_statement_struct bool keep_sections; lang_statement_list_type children; struct name_list *exclude_name_list; + lang_statement_list_type matching_sections; + bool resolved; walk_wild_section_handler_t walk_wild_section_handler; struct wildcard_list *handler_data[4]; @@ -440,6 +451,7 @@ typedef union lang_statement_union lang_fill_statement_type fill_statement; lang_group_statement_type group_statement; lang_input_section_type input_section; + lang_input_matcher_type input_matcher; lang_input_statement_type input_statement; lang_insert_statement_type insert_statement; lang_output_section_statement_type output_section_statement;