From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) by sourceware.org (Postfix) with ESMTPS id 7C2FE3858C54 for ; Fri, 2 Sep 2022 10:59:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7C2FE3858C54 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=martin.st Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=martin.st Received: by mail-lj1-x236.google.com with SMTP id bx38so1840085ljb.10 for ; Fri, 02 Sep 2022 03:59:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=martin-st.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:from:to:cc:subject:date; bh=w6WTLuTABHXikdVG0QKaycSoQ2rtgVKpBQ0vuy1f/YQ=; b=esJAATRAM0KBKxxUsdfb0VUk+B6CqXn8BtNlBqsDjFbmC/HdQhhgZCV/NVb6wEhA4M dFd+BUw7pR5P07w/PH+zTPaBeekmIPg9uSmIKOH2Wk0b3OjzLeRkcDL+HN170CgDKqbx FKTG/IqZ6KYnR9QQPnGgr1tSjhlQNsR+ESzAnYTi0Rb64vFxR/0GXUWSD2lL8Xp07pCI 0eJCPB4rTyjUXj6raZDnW3KC/XViEjRBoWGBLMNsZS/RtvvUb45/bA9bS72e9EizfRGJ fo0bdYeO56dYuaAKDQaHR1ke7b1llViR3Sk0Wq9Zm6hTlVXu/S0As8W+u8Judl/ZECTI GF5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:x-gm-message-state:from:to:cc:subject:date; bh=w6WTLuTABHXikdVG0QKaycSoQ2rtgVKpBQ0vuy1f/YQ=; b=ut5KiAxxVGQHFq7Hj7G1IYmn6MhM+el2BkJwlcKlSVHa3kYsQPQ+TxFKDns3gsH/+q 5BfZxLg8ZQO5SPv4M1qaeKtCZLXWp0k7wgsOCxUGWNf3WCNz+R0rTetUjcRpp9fM2NdG ChVBUgJsq6OfvgUNsKJYk3dVjBxOhwyR/SxyCQ8yq8JeiiJXkFOwmnzBlobA4rCeqr4x jLZn8HBI/yWLBe6gKkJNuOASmVKHrYOGYN4gZQgHYocs/KHAKYV+salQw9Scd06zvKsS LHi0hEGFLmPyQR3bnvGkhSriQxO/GsVTi7YOBzP9qHxIRdgDK5YDMuAvBzvHfZF+EJLS nX7w== X-Gm-Message-State: ACgBeo2n3BhExexnsG7lJ0bQo22eEcOpvly+ixKzDDp3fe+BZWzl7e5A EwffY+9KcfHNz1ZmGcJ031tIf0ZOPn26/h0z X-Google-Smtp-Source: AA6agR4TmjUjed5l4TdiN9mcKbdYmg61lcrU8Vm3EQU6Ao87bK1NdLgjx2tDGTGhHA3m7xRJ4Wpqag== X-Received: by 2002:a05:651c:1591:b0:261:c388:aa58 with SMTP id h17-20020a05651c159100b00261c388aa58mr11242741ljq.277.1662116344887; Fri, 02 Sep 2022 03:59:04 -0700 (PDT) Received: from localhost.localdomain (dsl-tkubng21-58c01c-243.dhcp.inet.fi. [88.192.28.243]) by smtp.gmail.com with ESMTPSA id b7-20020a2eb907000000b00261b4df9ec4sm152566ljb.138.2022.09.02.03.59.04 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 02 Sep 2022 03:59:04 -0700 (PDT) From: =?UTF-8?q?Martin=20Storsj=C3=B6?= To: binutils@sourceware.org Subject: [PATCH] ld: pe: Improve performance of object file exclude symbol directives Date: Fri, 2 Sep 2022 13:59:03 +0300 Message-Id: <20220902105903.2249507-1-martin@martin.st> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,GIT_PATCH_0,JMQ_SPF_NEUTRAL,RCVD_IN_DNSWL_NONE,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 List-Id: Store the list of excluded symbols in a sorted list, speeding up checking for duplicates when inserting new entries. This is done in the same way as is done for exports and imports (while the previous implementation was done with a linked list, based on the implementation for aligncomm). When linking object files with excluded symbols, there can potentially be very large numbers of excluded symbols (just like builds with exports can have a large number of exported symbols). This improves the link performance somewhat, when linking with large numbers of excluded symbols. The later actual use of the excluded symbols within pe-dll.c handles them via an unordered linked list still, though. --- ld/deffile.h | 2 +- ld/deffilep.y | 122 ++++++++++++++++++++++++++++++++++++++------------ ld/pe-dll.c | 7 ++- 3 files changed, 97 insertions(+), 34 deletions(-) diff --git a/ld/deffile.h b/ld/deffile.h index a247639628e..e6e4cf8eebc 100644 --- a/ld/deffile.h +++ b/ld/deffile.h @@ -62,7 +62,6 @@ typedef struct def_file_aligncomm { } def_file_aligncomm; typedef struct def_file_exclude_symbol { - struct def_file_exclude_symbol *next; /* Chain pointer. */ char *symbol_name; /* Name of excluded symbol. */ } def_file_exclude_symbol; @@ -101,6 +100,7 @@ typedef struct def_file { def_file_aligncomm *aligncomms; /* From EXCLUDE_SYMBOLS or embedded directives. */ + int num_exclude_symbols; def_file_exclude_symbol *exclude_symbols; } def_file; diff --git a/ld/deffilep.y b/ld/deffilep.y index 27db336e0f5..97f9fa4abaf 100644 --- a/ld/deffilep.y +++ b/ld/deffilep.y @@ -497,13 +497,13 @@ def_file_free (def_file *fdef) free (c); } - while (fdef->exclude_symbols) + if (fdef->exclude_symbols) { - def_file_exclude_symbol *e = fdef->exclude_symbols; - - fdef->exclude_symbols = fdef->exclude_symbols->next; - free (e->symbol_name); - free (e); + for (i = 0; i < fdef->num_exclude_symbols; i++) + { + free (fdef->exclude_symbols[i].symbol_name); + } + free (fdef->exclude_symbols); } free (fdef); @@ -949,6 +949,91 @@ def_file_add_import_at (def_file *fdef, return i; } +/* Search the position of the identical element, or returns the position + of the next higher element. If last valid element is smaller, then MAX + is returned. */ + +static int +find_exclude_in_list (def_file_exclude_symbol *b, int max, + const char *name, int *is_ident) +{ + int e, l, r, p; + + *is_ident = 0; + if (!max) + return 0; + if ((e = strcmp (b[0].symbol_name, name)) <= 0) + { + if (!e) + *is_ident = 1; + return 0; + } + if (max == 1) + return 1; + if ((e = strcmp (b[max - 1].symbol_name, name)) > 0) + return max; + else if (!e || max == 2) + { + if (!e) + *is_ident = 1; + return max - 1; + } + l = 0; r = max - 1; + while (l < r) + { + p = (l + r) / 2; + e = strcmp (b[p].symbol_name, name); + if (!e) + { + *is_ident = 1; + return p; + } + else if (e < 0) + r = p - 1; + else if (e > 0) + l = p + 1; + } + if ((e = strcmp (b[l].symbol_name, name)) > 0) + ++l; + else if (!e) + *is_ident = 1; + return l; +} + +static def_file_exclude_symbol * +def_file_add_exclude_symbol (def_file *fdef, const char *name, int *is_dup) +{ + def_file_exclude_symbol *e; + int pos; + int max_exclude_symbols = ROUND_UP(fdef->num_exclude_symbols, 32); + + /* We need to avoid duplicates. */ + *is_dup = 0; + pos = find_exclude_in_list (fdef->exclude_symbols, fdef->num_exclude_symbols, + name, is_dup); + + if (*is_dup != 0) + return (fdef->exclude_symbols + pos); + + if (fdef->num_exclude_symbols >= max_exclude_symbols) + { + max_exclude_symbols = ROUND_UP(fdef->num_exclude_symbols + 1, 32); + if (fdef->exclude_symbols) + fdef->exclude_symbols = xrealloc (fdef->exclude_symbols, + max_exclude_symbols * sizeof (def_file_exclude_symbol)); + else + fdef->exclude_symbols = xmalloc (max_exclude_symbols * sizeof (def_file_exclude_symbol)); + } + + e = fdef->exclude_symbols + pos; + if (pos != fdef->num_exclude_symbols) + memmove (&e[1], e, (sizeof (def_file_exclude_symbol) * (fdef->num_exclude_symbols - pos))); + memset (e, 0, sizeof (def_file_exclude_symbol)); + e->symbol_name = xstrdup (name); + fdef->num_exclude_symbols++; + return e; +} + struct { char *param; @@ -1280,30 +1365,9 @@ def_aligncomm (char *str, int align) static void def_exclude_symbols (char *str) { - def_file_exclude_symbol *c, *p; - - p = NULL; - c = def->exclude_symbols; - while (c != NULL) - { - int e = strcmp (c->symbol_name, str); - if (!e) - return; - c = (p = c)->next; - } + int is_dup = 0; - c = xmalloc (sizeof (def_file_exclude_symbol)); - c->symbol_name = xstrdup (str); - if (!p) - { - c->next = def->exclude_symbols; - def->exclude_symbols = c; - } - else - { - c->next = p->next; - p->next = c; - } + def_file_add_exclude_symbol (def, str, &is_dup); } static void diff --git a/ld/pe-dll.c b/ld/pe-dll.c index fbf180ec0f2..806715b2be2 100644 --- a/ld/pe-dll.c +++ b/ld/pe-dll.c @@ -720,11 +720,10 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info * if (pe_def_file->exclude_symbols) { - def_file_exclude_symbol *ac = pe_def_file->exclude_symbols; - while (ac) + for (i = 0; i < pe_def_file->num_exclude_symbols; i++) { - pe_dll_add_excludes (ac->symbol_name, EXCLUDESYMS); - ac = ac->next; + pe_dll_add_excludes (pe_def_file->exclude_symbols[i].symbol_name, + EXCLUDESYMS); } } -- 2.25.1