From nobody Sun Feb 8 11:07:10 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id D6DE1C7EE23 for ; Tue, 30 May 2023 17:22:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233455AbjE3RWv (ORCPT ); Tue, 30 May 2023 13:22:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50146 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233250AbjE3RVo (ORCPT ); Tue, 30 May 2023 13:21:44 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4EC43FE for ; Tue, 30 May 2023 10:21:39 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id BB121630DB for ; Tue, 30 May 2023 17:21:38 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 61182C433A7; Tue, 30 May 2023 17:21:38 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1685467298; bh=FMKirBi6c8n5y7aSisMhuMOzaOwJD8A67Hi2Xih1kgQ=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=Q96xRZ8Gp3x4c8ouOPI335jvybyekk1BwDQAeA4eP0jRMs3a7efTb3cfbRmzkXEEl cllEIbQjA7bqxKAzUM1O+6iB3NqPJcSdoHbmvokyraiGcx4j754gzZrt4DyoqCuqMY UttBIfS/aj4ZwmpsOszBVx1Jj66a+daRDPbftrsyPFrnpgV+zcTCEoI7K4VfsCCPs9 Sgv00CbKcztQsuQPnM4xonVnO0iYtuUF7BTrQlnR8UoDTcp+S7XF5vHWI29SkX1V6U pk/+qJEolqLZIfBKFh9+XaASjDhO5FHIi/W3vAsCjM9LD6kNjqERjMRh0RQsxFnTf6 tj/kky7o29eqg== From: Josh Poimboeuf To: x86@kernel.org Cc: linux-kernel@vger.kernel.org, Peter Zijlstra , Miroslav Benes Subject: [PATCH 19/22] objtool: Shrink elf hash nodes Date: Tue, 30 May 2023 10:21:11 -0700 Message-Id: <6e8cd305ed22e743c30d6e72cfdc1be20fb94cd4.1685464332.git.jpoimboe@kernel.org> X-Mailer: git-send-email 2.40.1 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Instead of using hlist for the 'struct elf' hashes, use a custom single-linked list scheme. With allyesconfig + CONFIG_DEBUG_INFO: - Before: peak heap memory consumption: 36.89G - After: peak heap memory consumption: 35.12G Signed-off-by: Josh Poimboeuf --- tools/objtool/elf.c | 52 ++++++++++++++++++++++++----- tools/objtool/include/objtool/elf.h | 24 +++++++------ 2 files changed, 58 insertions(+), 18 deletions(-) diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c index 4b0de0e56068..04038b1324cf 100644 --- a/tools/objtool/elf.c +++ b/tools/objtool/elf.c @@ -32,16 +32,52 @@ static inline u32 str_hash(const char *str) #define __elf_table(name) (elf->name##_hash) #define __elf_bits(name) (elf->name##_bits) =20 -#define elf_hash_add(name, node, key) \ - hlist_add_head(node, &__elf_table(name)[hash_min(key, __elf_bits(name))]) +#define __elf_table_entry(name, key) \ + __elf_table(name)[hash_min(key, __elf_bits(name))] =20 -#define elf_hash_for_each_possible(name, obj, member, key) \ - hlist_for_each_entry(obj, &__elf_table(name)[hash_min(key, __elf_bits(nam= e))], member) +#define elf_hash_add(name, node, key) \ +({ \ + struct elf_hash_node *__node =3D node; \ + __node->next =3D __elf_table_entry(name, key); \ + __elf_table_entry(name, key) =3D __node; \ +}) + +static inline void __elf_hash_del(struct elf_hash_node *node, + struct elf_hash_node **head) +{ + struct elf_hash_node *cur, *prev; + + if (node =3D=3D *head) { + *head =3D node->next; + return; + } + + for (prev =3D NULL, cur =3D *head; cur; prev =3D cur, cur =3D cur->next) { + if (cur =3D=3D node) { + prev->next =3D cur->next; + break; + } + } +} + +#define elf_hash_del(name, node, key) \ + __elf_hash_del(node, &__elf_table_entry(name, key)) + +#define elf_list_entry(ptr, type, member) \ +({ \ + typeof(ptr) __ptr =3D (ptr); \ + __ptr ? container_of(__ptr, type, member) : NULL; \ +}) + +#define elf_hash_for_each_possible(name, obj, member, key) \ + for (obj =3D elf_list_entry(__elf_table_entry(name, key), typeof(*obj), m= ember); \ + obj; \ + obj =3D elf_list_entry(obj->member.next, typeof(*(obj)), member)) =20 #define elf_alloc_hash(name, size) \ ({ \ __elf_bits(name) =3D max(10, ilog2(size)); \ - __elf_table(name) =3D mmap(NULL, sizeof(struct hlist_head) << __elf_bits(= name), \ + __elf_table(name) =3D mmap(NULL, sizeof(struct elf_hash_node *) << __elf_= bits(name), \ PROT_READ|PROT_WRITE, \ MAP_PRIVATE|MAP_ANON, -1, 0); \ if (__elf_table(name) =3D=3D (void *)-1L) { \ @@ -713,10 +749,10 @@ __elf_create_symbol(struct elf *elf, struct symbol *s= ym) first_non_local =3D symtab->sh.sh_info; old =3D find_symbol_by_index(elf, first_non_local); if (old) { - old->idx =3D new_idx; =20 - hlist_del(&old->hash); - elf_hash_add(symbol, &old->hash, old->idx); + elf_hash_del(symbol, &old->hash, old->idx); + elf_hash_add(symbol, &old->hash, new_idx); + old->idx =3D new_idx; =20 if (elf_update_symbol(elf, symtab, symtab_shndx, old)) { WARN("elf_update_symbol move"); diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/ob= jtool/elf.h index 7b808ac3156c..03a9040f696c 100644 --- a/tools/objtool/include/objtool/elf.h +++ b/tools/objtool/include/objtool/elf.h @@ -26,10 +26,14 @@ #define ELF_C_READ_MMAP ELF_C_READ #endif =20 +struct elf_hash_node { + struct elf_hash_node *next; +}; + struct section { struct list_head list; - struct hlist_node hash; - struct hlist_node name_hash; + struct elf_hash_node hash; + struct elf_hash_node name_hash; GElf_Shdr sh; struct rb_root_cached symbol_tree; struct list_head symbol_list; @@ -45,8 +49,8 @@ struct section { struct symbol { struct list_head list; struct rb_node node; - struct hlist_node hash; - struct hlist_node name_hash; + struct elf_hash_node hash; + struct elf_hash_node name_hash; GElf_Sym sym; struct section *sec; char *name; @@ -67,7 +71,7 @@ struct symbol { }; =20 struct reloc { - struct hlist_node hash; + struct elf_hash_node hash; union { GElf_Rela rela; GElf_Rel rel; @@ -93,11 +97,11 @@ struct elf { int section_name_bits; int reloc_bits; =20 - struct hlist_head *symbol_hash; - struct hlist_head *symbol_name_hash; - struct hlist_head *section_hash; - struct hlist_head *section_name_hash; - struct hlist_head *reloc_hash; + struct elf_hash_node **symbol_hash; + struct elf_hash_node **symbol_name_hash; + struct elf_hash_node **section_hash; + struct elf_hash_node **section_name_hash; + struct elf_hash_node **reloc_hash; =20 struct section *section_data; struct symbol *symbol_data; --=20 2.40.1