From nobody Sun Feb 8 05:23:35 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 A00E1C7EE29 for ; Fri, 9 Jun 2023 07:47:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237988AbjFIHry (ORCPT ); Fri, 9 Jun 2023 03:47:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54864 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239076AbjFIHrj (ORCPT ); Fri, 9 Jun 2023 03:47:39 -0400 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 07AE330D2; Fri, 9 Jun 2023 00:47:29 -0700 (PDT) Date: Fri, 09 Jun 2023 07:47:27 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1686296848; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=BDPaSVjfCDzLcF7//YwLg51Z4m12AiJ5I8kqkjtTci0=; b=kTNdN0NR7S0TjQPUsvSvSE7saueobAW5K6rW+FxTOo5pbRot7VXXGb5NS94rqVfqDtKnSw /UJ9/8TFfsuwVeSdjoRmj08TgobqGgCewPKgCFkdvuY9jMs0XXOb4iga1O/ewhpqv+8Ugf Cv95YRGB8zxBFR5CHBe7SbNDK+YCTtAsM5vkY70TCnTG0j4hNq04VbIjmqGhhkXTkdbj+2 Mx04lQBKczIqh3XDDGzxs8Xta0/TXjYqmRmffc7f3Mus6Tl90UrrSfFZFvQZne76Vz9VBO CNGnJwkeNqnk1cArdI4Sr8VTSW4Eb8GJkiQnDtMw5OXHGmCpCRbD9lldQYiqIA== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1686296848; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=BDPaSVjfCDzLcF7//YwLg51Z4m12AiJ5I8kqkjtTci0=; b=XqOFBEnugSUAv9V6s5vi3R2SG8CpABeq+l/8QAvoF1IH1nhvLbepxlGPBAkbnLBSqhw87r V0P1fvISDSH8dWBQ== From: "tip-bot2 for Josh Poimboeuf" Sender: tip-bot2@linutronix.de Reply-to: linux-kernel@vger.kernel.org To: linux-tip-commits@vger.kernel.org Subject: [tip: objtool/core] objtool: Shrink elf hash nodes Cc: Josh Poimboeuf , x86@kernel.org, linux-kernel@vger.kernel.org In-Reply-To: <6e8cd305ed22e743c30d6e72cfdc1be20fb94cd4.1685464332.git.jpoimboe@kernel.org> References: <6e8cd305ed22e743c30d6e72cfdc1be20fb94cd4.1685464332.git.jpoimboe@kernel.org> MIME-Version: 1.0 Message-ID: <168629684776.404.12793392226437928486.tip-bot2@tip-bot2> Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The following commit has been merged into the objtool/core branch of tip: Commit-ID: 02b54001066364aee72bc4c802b42a96c6e0dc1f Gitweb: https://git.kernel.org/tip/02b54001066364aee72bc4c802b42a96c= 6e0dc1f Author: Josh Poimboeuf AuthorDate: Tue, 30 May 2023 10:21:11 -07:00 Committer: Josh Poimboeuf CommitterDate: Wed, 07 Jun 2023 10:03:25 -07:00 objtool: Shrink elf hash nodes 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 Link: https://lore.kernel.org/r/6e8cd305ed22e743c30d6e72cfdc1be20fb94cd4.16= 85464332.git.jpoimboe@kernel.org 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 4b0de0e..04038b1 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))] + +#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; =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) + 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 7b808ac..03a9040 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;