From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x22f.google.com (mail-lj1-x22f.google.com [IPv6:2a00:1450:4864:20::22f]) by sourceware.org (Postfix) with ESMTPS id 47CEA385355A for ; Tue, 6 Sep 2022 15:44:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 47CEA385355A 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-x22f.google.com with SMTP id l12so4310634ljg.9 for ; Tue, 06 Sep 2022 08:44:50 -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=/wAfssnqzRE1x/kLt20PDBa4mcf0Jll/U70H2SPy7D4=; b=eMkfzMZou5oA0rl/7AxFpo/om+G9RnwsKJH8x/c7+ZaX5kvIvzJ5z4VuandT6YiKg5 oT2Mxa69ImLISSWMMb2XqeaXJWB25ArAfrPCd+7nkm+e9ASWFNha+i1QC0HQPlS5M3CJ 1VO1rts2E3Ji5jE8UhkPAlIO8gmCL3I4AV3mgMdjqgGf7PA4NBO3sj1PZrmuTArhFt3y HI5CXnIi1yjdejt11HpBgP58aK1l/idAkyJ71Mgss3Eziu3Afw3MfGLuRZOLuhRjsGK5 6vASCmM0k9yrsEtyiWS8q78bJi6BolCI+HyroMhWFg35vZVo56vbi46uSFSX2x2jGMm9 t8MA== 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=/wAfssnqzRE1x/kLt20PDBa4mcf0Jll/U70H2SPy7D4=; b=HZZv8I8/nXooWljcAp+QZ6ffydZdlWa4EQR4g+hpZ2yNG/xCnC/WFJyKlA5S76uieF 07cqlSwPNfVpn0YPOUUiClZ1GDfj//bLvaCodtoDZThByP7hQb4irNqSBJ4FrNS4aBBh CuIeA33pdP6naHRJUmdRcUZGvKfXtXYZQ2kpMyaqd/eua1AY3MdfzxclBFS82k7q2NbZ Am/pKPCgQ0oQnap+4PovrpWtvcK0IY//CRlfnLrAQ+geGtJ0LR29hBzmcDW3oWpKOd/i nM7d5JvCqWLzQwvrCo0rjPF8hN0Yf0ZD2dtXVjLp5VsvCgoixE3eCyNxMzAZXjj7xs/J Ln0w== X-Gm-Message-State: ACgBeo0DkijZHYz7yqitw98WG3Y1MwtWBO1gOJyz5IRtkPCuo+0JG1Ql mowaX7aN70yHvfo9mKNUIj1C/BteEVzwtJMN X-Google-Smtp-Source: AA6agR50IDZ2eRyFn4C5fWKCu5/rNxNs+c0rCbUo5NS2DL/2RnStfAJv6jIXQmoHANpLc4117RfJIQ== X-Received: by 2002:a2e:98c:0:b0:26a:9b25:b76f with SMTP id 134-20020a2e098c000000b0026a9b25b76fmr1573513ljj.256.1662479088745; Tue, 06 Sep 2022 08:44:48 -0700 (PDT) Received: from localhost.localdomain (dsl-tkubng21-58c01c-243.dhcp.inet.fi. [88.192.28.243]) by smtp.gmail.com with ESMTPSA id e2-20020ac25462000000b004949f7cbb6esm1809398lfn.79.2022.09.06.08.44.48 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 Sep 2022 08:44:48 -0700 (PDT) From: =?UTF-8?q?Martin=20Storsj=C3=B6?= To: binutils@sourceware.org Subject: [PATCH v2 1/2] ld: pe: Improve performance of object file exclude symbol directives Date: Tue, 6 Sep 2022 18:44:46 +0300 Message-Id: <20220906154447.1402361-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=-12.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,GIT_PATCH_0,JMQ_SPF_NEUTRAL,KAM_STOCKGEN,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 | 124 ++++++++++++++++++++++++++++++++++++++------------ ld/pe-dll.c | 8 ++-- 3 files changed, 99 insertions(+), 35 deletions(-) diff --git a/ld/deffile.h b/ld/deffile.h index a247639628e..89ffe9f972e 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. */ + unsigned int num_exclude_symbols, max_exclude_symbols; def_file_exclude_symbol *exclude_symbols; } def_file; diff --git a/ld/deffilep.y b/ld/deffilep.y index 27db336e0f5..ed8f0d6719a 100644 --- a/ld/deffilep.y +++ b/ld/deffilep.y @@ -32,6 +32,8 @@ #define ROUND_UP(a, b) (((a)+((b)-1))&~((b)-1)) +#define SYMBOL_LIST_ARRAY_GROW 64 + /* Remap normal yacc parser interface names (yyparse, yylex, yyerror, etc), as well as gratuitiously global symbol names, so we can have multiple yacc generated parsers in ld. Note that these are only the variables @@ -440,6 +442,7 @@ void def_file_free (def_file *fdef) { int i; + unsigned int ui; if (!fdef) return; @@ -497,14 +500,11 @@ def_file_free (def_file *fdef) free (c); } - while (fdef->exclude_symbols) + for (ui = 0; ui < fdef->num_exclude_symbols; ui++) { - def_file_exclude_symbol *e = fdef->exclude_symbols; - - fdef->exclude_symbols = fdef->exclude_symbols->next; - free (e->symbol_name); - free (e); + free (fdef->exclude_symbols[ui].symbol_name); } + free (fdef->exclude_symbols); free (fdef); } @@ -949,6 +949,93 @@ 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. The max parameter indicates the number of elements in the + array. On return, *is_ident indicates whether the returned array index + points at an element which is identical to the one searched for. */ + +static unsigned int +find_exclude_in_list (def_file_exclude_symbol *b, unsigned int max, + const char *name, bool *is_ident) +{ + int e; + unsigned int l, r, p; + + *is_ident = false; + if (!max) + return 0; + if ((e = strcmp (b[0].symbol_name, name)) <= 0) + { + if (!e) + *is_ident = true; + 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 = true; + 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 = true; + 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 = true; + return l; +} + +static def_file_exclude_symbol * +def_file_add_exclude_symbol (def_file *fdef, const char *name) +{ + def_file_exclude_symbol *e; + unsigned pos; + bool is_dup = false; + + pos = find_exclude_in_list (fdef->exclude_symbols, fdef->num_exclude_symbols, + name, &is_dup); + + /* We need to avoid duplicates. */ + if (is_dup) + return (fdef->exclude_symbols + pos); + + if (fdef->num_exclude_symbols >= fdef->max_exclude_symbols) + { + fdef->max_exclude_symbols += SYMBOL_LIST_ARRAY_GROW; + fdef->exclude_symbols = xrealloc (fdef->exclude_symbols, + fdef->max_exclude_symbols * sizeof (def_file_exclude_symbol)); + } + + e = fdef->exclude_symbols + pos; + /* If we're inserting in the middle of the array, we need to move the + following elements forward. */ + if (pos != fdef->num_exclude_symbols) + memmove (&e[1], e, (sizeof (def_file_exclude_symbol) * (fdef->num_exclude_symbols - pos))); + /* Wipe the element for use as a new entry. */ + memset (e, 0, sizeof (def_file_exclude_symbol)); + e->symbol_name = xstrdup (name); + fdef->num_exclude_symbols++; + return e; +} + struct { char *param; @@ -1280,30 +1367,7 @@ 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; - } - - 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); } static void diff --git a/ld/pe-dll.c b/ld/pe-dll.c index fbf180ec0f2..60584a88571 100644 --- a/ld/pe-dll.c +++ b/ld/pe-dll.c @@ -671,6 +671,7 @@ static void process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info *info) { int i, j; + unsigned int ui; struct bfd_link_hash_entry *blhe; bfd *b; struct bfd_section *s; @@ -720,11 +721,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 (ui = 0; ui < pe_def_file->num_exclude_symbols; ui++) { - pe_dll_add_excludes (ac->symbol_name, EXCLUDESYMS); - ac = ac->next; + pe_dll_add_excludes (pe_def_file->exclude_symbols[ui].symbol_name, + EXCLUDESYMS); } } -- 2.25.1