From 96147998b34c85786d55bf2506cbd2fc60668e1a Mon Sep 17 00:00:00 2001 From: Fabian Rast Date: Tue, 2 Dec 2025 12:46:41 +0100 Subject: [PATCH v3] ldso: skip gnu hash calculation if precomputed calculating the hashes of symbol names takes a significant amount of time while applying relocations. however, in case of symbol lookups for symbols that are themselves part of the gnu hashtable in the object being relocated, the hashvalue is already present in that hashtable and can be efficiently retrieved using the symbol index. the gnu hash table only stores the upper 31 bits of the 32 bit wide hashes. the lsb is used to indicate the end of a chain. this missing bit can be inferred by guessing and checking the bloom filter to exclude incorrect guesses. In case the bloom filter check is positive for both possibilities, this optimization does not apply. --- ldso/dynlink.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-) diff --git a/ldso/dynlink.c b/ldso/dynlink.c index 44d9b181..189bace1 100644 --- a/ldso/dynlink.c +++ b/ldso/dynlink.c @@ -320,10 +320,24 @@ static Sym *gnu_lookup_filtered(uint32_t h1, uint32_t *hashtab, struct dso *dso, #if defined(__GNUC__) __attribute__((always_inline)) #endif -static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_def, int use_deps) +static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_def, int use_deps, struct dso *dso2, int sym_index) { - uint32_t h = 0, gh = gnu_hash(s), gho = gh / (8*sizeof(size_t)), *ght; - size_t ghm = 1ul << gh % (8*sizeof(size_t)); + uint32_t h = 0, gh, gho, *ght; + size_t ghm; + + if (dso2 && (ght = dso2->ghashtab) && sym_index >= ght[1]) { + uint32_t nbuckets = ght[0], *buckets = ght+4+ght[2]*(sizeof(size_t)/4); + uint32_t h0 = buckets[nbuckets+sym_index-ght[1]] & ~1u, h1 = h0|1, + r = h0 % (8*sizeof(size_t)); + size_t f = ((size_t *)(ght+4))[(h0 / (8*sizeof(size_t))) & (ght[2]-1)], + i = ((f >> r) | (f << 64-r)) & 3; + if (!(gh = (uint32_t[3]){h0, h1, 0}[i-1])) + gh = gnu_hash(s); + } else gh = gnu_hash(s); + + gho = gh / (8*sizeof(size_t)); + ghm = 1ul << gh % (8*sizeof(size_t)); + struct symdef def = {0}; struct dso **deps = use_deps ? dso->deps : 0; for (; dso; dso=use_deps ? *deps++ : dso->syms_next) { @@ -353,7 +367,7 @@ static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_d static struct symdef find_sym(struct dso *dso, const char *s, int need_def) { - return find_sym2(dso, s, need_def, 0); + return find_sym2(dso, s, need_def, 0, NULL, STN_UNDEF); } static struct symdef get_lfs64(const char *name) @@ -437,7 +451,7 @@ static void do_relocs(struct dso *dso, size_t *rel, size_t rel_size, size_t stri ctx = type==REL_COPY ? head->syms_next : head; def = (sym->st_info>>4) == STB_LOCAL ? (struct symdef){ .dso = dso, .sym = sym } - : find_sym(ctx, name, type==REL_PLT); + : find_sym2(ctx, name, type==REL_PLT, 0, dso, sym_index); if (!def.sym) def = get_lfs64(name); if (!def.sym && (sym->st_shndx != SHN_UNDEF || sym->st_info>>4 != STB_WEAK)) { @@ -2345,7 +2359,7 @@ static void *do_dlsym(struct dso *p, const char *s, void *ra) return 0; } else use_deps = 1; - struct symdef def = find_sym2(p, s, 0, use_deps); + struct symdef def = find_sym2(p, s, 0, use_deps, NULL, STN_UNDEF); if (!def.sym) { error("Symbol not found: %s", s); return 0; -- 2.52.0