DT_GNU_HASH: ~ 50% dynamic linking improvement
Jakub Jelinek
jakub@redhat.com
Wed Jul 5 09:05:00 GMT 2006
On Tue, Jul 04, 2006 at 10:50:50PM +0000, djamel anonymous wrote:
> first thank you, for your reply. i am sending this mail to explain further
> my idea.My suggestion
> was made primarily because of 2 assumptions:
I think you can implement the same while still not increasing the number of
used cache lines in the successful case.
Just put the bitmask along the chain offsets in the buckets array, then
(assuming .gnu.hash is always >= 8B aligned, which we can cheaply ensure),
the bitmask word will always be in the same cache line as the offset
into the chain array. In this case, for successful lookup or unsuccessful
one where the bit is not set in the bitmask we need just one cache line
access, otherwise it uses 2 (or more) as it used before. The shorter the
chain, the higher probability the bitmask saves the extra cache line read.
For extremely long chains, it wouldn't help at all (chain length >= 32
assuming all hash values in the chain have different topmost 5 bits),
but chains with length >= 7 are really rare and even for chain length
7 the probability the bitmask helps is ~ 78%.
The disadvantage of course is the increase in the .gnu.hash section
size, which grows from current
(2 + nbuckets + nsyms) * 4
to
(2 + 2 * nbuckets + nsyms) * 4.
I'll try to benchmark both of these variants and see if it is really worth
it.
Here is the interdiff on how would the glibc side of changes for
this look like (and I'm attaching also Uli's 2006-07-03 patch, which
hasn't been posted yet).
--- libc/elf/dl-lookup.c.jj 2006-07-05 08:59:01.000000000 +0200
+++ libc/elf/dl-lookup.c 2006-07-05 09:01:53.000000000 +0200
@@ -380,8 +380,8 @@ _dl_setup_hash (struct link_map *map)
+ DT_EXTRANUM + DT_VALNUM]);
map->l_nbuckets = *hash32++;
map->l_gnu_symbias = *hash32++;
- map->l_gnu_buckets = hash32;
- hash32 += map->l_nbuckets;
+ map->l_gnu_buckets = (void *) hash32;
+ hash32 += 2 * map->l_nbuckets;
map->l_gnu_hashbase = hash32;
return;
}
--- libc/elf/do-lookup.h.jj 2006-07-05 08:59:01.000000000 +0200
+++ libc/elf/do-lookup.h 2006-07-05 09:07:22.000000000 +0200
@@ -169,10 +169,15 @@ do_lookup_x (const char *undef_name, uin
if (__builtin_expect (map->l_gnu_buckets != NULL, 1))
{
/* Use the new GNU-style hash table. */
- size_t chainoff = map->l_gnu_buckets[new_hash % map->l_nbuckets];
+ Elf32_Word bitmask
+ = map->l_gnu_buckets[new_hash % map->l_nbuckets].bitmask;
- if (chainoff != 0xffffffff)
+ /* Bitmask has bit N set iff any of the hash values in
+ hasharr chain has (hash >> 27) == N. */
+ if (bitmask & (1 << (new_hash >> 27)))
{
+ size_t chainoff
+ = map->l_gnu_buckets[new_hash % map->l_nbuckets].chainoff;
const Elf32_Word *hasharr = &map->l_gnu_hashbase[chainoff];
Elf32_Word new_hash_masked = new_hash & ~1u;
--- libc/include/link.h.jj 2006-07-05 08:59:01.000000000 +0200
+++ libc/include/link.h 2006-07-05 09:00:41.000000000 +0200
@@ -141,7 +141,11 @@ struct link_map
/* Symbol hash table. */
Elf_Symndx l_nbuckets;
- const Elf32_Word *l_gnu_buckets;
+ const struct
+ {
+ Elf32_Word chainoff;
+ Elf32_Word bitmask;
+ } *l_gnu_buckets;
union
{
const Elf32_Word *l_gnu_hashbase;
Jakub
-------------- next part --------------
2006-07-03 Ulrich Drepper <drepper@redhat.com>
* elf/dl-lookup.c (dl_new_hash): New functions.
(_dl_lookup_symbol_x): Rename hash to old_hash and don't compute
value here. Compute new-style hash value. Pass new hash value
and reference to variable with the old value to do_lookup_x.
(_dl_setup_hash): If DT_GNU_HASH is defined, use it and not
old-style hash table.
(_dl_debug_bindings): Pass new hash value and reference to variable
with the old value to do_lookup_x.
* elf/do-lookup.h (do_lookup_x): Accept additional parameter with
new-style hash value and change old-style hash value parameter to
be a reference. Reoganize functions to determine whether
new-style hash table is available. Only fall back on old-style
table. If old-style hash value is needed, compute it here.
* elf/dynamic-link.h (elf_get_dynamic_info): Relocate DT_GNU_HASH
entry.
* elf/elf.h: Define SHT_GNU_HASH, DT_GNU_HASH, DT_TLSDEC_PLT,
DT_TLSDEC_GOT. Adjust DT_ADDRNUM.
* include/link.h (struct link_map): Add l_gnu_buckets and
l_gnu_hashbase.
* Makeconfig: If linker supports --hash-style option add it to all
linker command lines to build DSOs.
* config.make.in: Define have-hash-style.
* configure.in: Test whether linker supports --hash-style option.
--- libc/Makeconfig.jj 2006-05-15 11:21:55.000000000 -0700
+++ libc/Makeconfig 2006-06-26 13:51:15.000000000 -0700
@@ -413,6 +413,15 @@ LDFLAGS.so += $(relro-LDFLAGS)
LDFLAGS-rtld += $(relro-LDFLAGS)
endif
+ifeq (yes,$(have-hash-style))
+# For the time being we unconditionally use 'both'. At some time we
+# should declare statically linked code as 'out of luck' and compile
+# with --hash-style=gnu only.
+hashstyle-LDFLAGS = -Wl,--hash-style=both
+LDFLAGS.so += $(hashstyle-LDFLAGS)
+LDFLAGS-rtld += $(hashstyle-LDFLAGS)
+endif
+
# Command for linking programs with the C library.
ifndef +link
+link = $(CC) -nostdlib -nostartfiles -o $@ \
--- libc/config.make.in.jj 2006-04-26 08:17:41.000000000 -0700
+++ libc/config.make.in 2006-06-27 05:38:40.000000000 -0700
@@ -65,6 +65,7 @@ have-libcap = @have_libcap@
have-cc-with-libunwind = @libc_cv_cc_with_libunwind@
fno-unit-at-a-time = @fno_unit_at_a_time@
bind-now = @bindnow@
+have-hash-style = @libc_cv_hashstyle@
static-libgcc = @libc_cv_gcc_static_libgcc@
--- libc/configure.in.jj 2006-04-26 08:19:22.000000000 -0700
+++ libc/configure.in 2006-06-26 13:47:01.000000000 -0700
@@ -1589,6 +1589,22 @@ EOF
rm -f conftest*])
AC_SUBST(libc_cv_fpie)
+
+ AC_CACHE_CHECK(for --hash-style option,
+ libc_cv_hashstyle, [dnl
+ cat > conftest.c <<EOF
+int _start (void) { return 42; }
+EOF
+ if AC_TRY_COMMAND([${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS
+ -fPIC -shared -o conftest.so conftest.c
+ -Wl,--hash-style=both -nostdlib 1>&AS_MESSAGE_LOG_FD])
+ then
+ libc_cv_hashstyle=yes
+ else
+ libc_cv_hashstyle=no
+ fi
+ rm -f conftest*])
+ AC_SUBST(libc_cv_hashstyle)
fi
AC_CACHE_CHECK(for -fno-toplevel-reorder, libc_cv_fno_toplevel_reorder, [dnl
--- libc/elf/dl-lookup.c.jj 21 Dec 2005 22:16:20 -0000 1.121
+++ libc/elf/dl-lookup.c 3 Jul 2006 20:48:02 -0000
@@ -72,6 +72,16 @@ struct sym_val
#include "do-lookup.h"
+static uint_fast32_t
+dl_new_hash (const char *s)
+{
+ uint_fast32_t h = 5381;
+ for (unsigned char c = *s; c != '\0'; c = *++s)
+ h = h * 33 + c;
+ return h & 0xffffffff;
+}
+
+
/* Add extra dependency on MAP to UNDEF_MAP. */
static int
internal_function
@@ -206,7 +216,8 @@ _dl_lookup_symbol_x (const char *undef_n
const struct r_found_version *version,
int type_class, int flags, struct link_map *skip_map)
{
- const unsigned long int hash = _dl_elf_hash (undef_name);
+ const uint_fast32_t new_hash = dl_new_hash (undef_name);
+ unsigned long int old_hash = 0xffffffff;
struct sym_val current_value = { NULL, NULL };
struct r_scope_elem **scope = symbol_scope;
@@ -229,8 +240,9 @@ _dl_lookup_symbol_x (const char *undef_n
/* Search the relevant loaded objects for a definition. */
for (size_t start = i; *scope != NULL; start = 0, ++scope)
{
- int res = do_lookup_x (undef_name, hash, *ref, ¤t_value, *scope,
- start, version, flags, skip_map, type_class);
+ int res = do_lookup_x (undef_name, new_hash, &old_hash, *ref,
+ ¤t_value, *scope, start, version, flags,
+ skip_map, type_class);
if (res > 0)
break;
@@ -301,9 +313,9 @@ _dl_lookup_symbol_x (const char *undef_n
struct sym_val protected_value = { NULL, NULL };
for (scope = symbol_scope; *scope != NULL; i = 0, ++scope)
- if (do_lookup_x (undef_name, hash, *ref, &protected_value,
- *scope, i, version, flags, skip_map,
- ELF_RTYPE_CLASS_PLT) != 0)
+ if (do_lookup_x (undef_name, new_hash, &old_hash, *ref,
+ &protected_value, *scope, i, version, flags,
+ skip_map, ELF_RTYPE_CLASS_PLT) != 0)
break;
if (protected_value.s != NULL && protected_value.m != undef_map)
@@ -352,6 +364,22 @@ _dl_setup_hash (struct link_map *map)
Elf_Symndx *hash;
Elf_Symndx nchain;
+ if (__builtin_expect (map->l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM
+ + DT_THISPROCNUM + DT_VERSIONTAGNUM
+ + DT_EXTRANUM + DT_VALNUM] != NULL, 1))
+ {
+ Elf32_Word *hash32
+ = (void *) D_PTR (map, l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM
+ + DT_THISPROCNUM + DT_VERSIONTAGNUM
+ + DT_EXTRANUM + DT_VALNUM]);
+ map->l_nbuckets = *hash32++;
+ map->l_gnu_symbias = *hash32++;
+ map->l_gnu_buckets = hash32;
+ hash32 += map->l_nbuckets;
+ map->l_gnu_hashbase = hash32;
+ return;
+ }
+
if (!map->l_info[DT_HASH])
return;
hash = (void *) D_PTR (map, l_info[DT_HASH]);
@@ -399,9 +427,10 @@ _dl_debug_bindings (const char *undef_na
|| GLRO(dl_trace_prelink_map) == GL(dl_ns)[LM_ID_BASE]._ns_loaded)
&& undef_map != GL(dl_ns)[LM_ID_BASE]._ns_loaded)
{
- const unsigned long int hash = _dl_elf_hash (undef_name);
+ const uint_fast32_t new_hash = dl_new_hash (undef_name);
+ unsigned long int old_hash = 0xffffffff;
- do_lookup_x (undef_name, hash, *ref, &val,
+ do_lookup_x (undef_name, new_hash, &old_hash, *ref, &val,
undef_map->l_local_scope[0], 0, version, 0, NULL,
type_class);
--- libc/elf/do-lookup.h.jj 2006-02-26 12:49:30.000000000 -0800
+++ libc/elf/do-lookup.h 2006-07-03 13:24:14.000000000 -0700
@@ -17,14 +17,15 @@
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
+
/* Inner part of the lookup functions. We return a value > 0 if we
found the symbol, the value 0 if nothing is found and < 0 if
something bad happened. */
static int
__attribute_noinline__
-do_lookup_x (const char *undef_name, unsigned long int hash,
- const ElfW(Sym) *ref, struct sym_val *result,
- struct r_scope_elem *scope, size_t i,
+do_lookup_x (const char *undef_name, uint_fast32_t new_hash,
+ unsigned long int *old_hash, const ElfW(Sym) *ref,
+ struct sym_val *result, struct r_scope_elem *scope, size_t i,
const struct r_found_version *const version, int flags,
struct link_map *skip, int type_class)
{
@@ -67,105 +68,148 @@ do_lookup_x (const char *undef_name, uns
strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]);
verstab = map->l_versyms;
- /* Search the appropriate hash bucket in this object's symbol table
- for a definition for the same symbol name. */
- for (symidx = map->l_buckets[hash % map->l_nbuckets];
- symidx != STN_UNDEF;
- symidx = map->l_chain[symidx])
- {
- sym = &symtab[symidx];
-
- assert (ELF_RTYPE_CLASS_PLT == 1);
- if ((sym->st_value == 0 /* No value. */
+ const ElfW(Sym) *
+ __attribute_noinline__
+ check_match (const ElfW(Sym) *sym)
+ {
+ assert (ELF_RTYPE_CLASS_PLT == 1);
+ if (__builtin_expect ((sym->st_value == 0 /* No value. */
#ifdef USE_TLS
- && ELFW(ST_TYPE) (sym->st_info) != STT_TLS
+ && ELFW(ST_TYPE) (sym->st_info) != STT_TLS
#endif
- )
- || (type_class & (sym->st_shndx == SHN_UNDEF)))
- continue;
+ )
+ || (type_class & (sym->st_shndx == SHN_UNDEF)),
+ 0))
+ return NULL;
- if (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC
+ if (__builtin_expect (ELFW(ST_TYPE) (sym->st_info) > STT_FUNC
#ifdef USE_TLS
- && ELFW(ST_TYPE) (sym->st_info) != STT_TLS
+ && ELFW(ST_TYPE) (sym->st_info) != STT_TLS
#endif
- )
- /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC
- entries (and STT_TLS if TLS is supported) since these
- are no code/data definitions. */
- continue;
+ , 0))
+ /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC
+ entries (and STT_TLS if TLS is supported) since these
+ are no code/data definitions. */
+ return NULL;
- if (sym != ref && strcmp (strtab + sym->st_name, undef_name))
- /* Not the symbol we are looking for. */
- continue;
+ if (sym != ref && strcmp (strtab + sym->st_name, undef_name))
+ /* Not the symbol we are looking for. */
+ return NULL;
- if (version != NULL)
- {
- if (__builtin_expect (verstab == NULL, 0))
- {
- /* We need a versioned symbol but haven't found any. If
- this is the object which is referenced in the verneed
- entry it is a bug in the library since a symbol must
- not simply disappear.
+ if (version != NULL)
+ {
+ if (__builtin_expect (verstab == NULL, 0))
+ {
+ /* We need a versioned symbol but haven't found any. If
+ this is the object which is referenced in the verneed
+ entry it is a bug in the library since a symbol must
+ not simply disappear.
- It would also be a bug in the object since it means that
- the list of required versions is incomplete and so the
- tests in dl-version.c haven't found a problem.*/
- assert (version->filename == NULL
- || ! _dl_name_match_p (version->filename, map));
+ It would also be a bug in the object since it means that
+ the list of required versions is incomplete and so the
+ tests in dl-version.c haven't found a problem.*/
+ assert (version->filename == NULL
+ || ! _dl_name_match_p (version->filename, map));
- /* Otherwise we accept the symbol. */
- }
- else
- {
- /* We can match the version information or use the
- default one if it is not hidden. */
- ElfW(Half) ndx = verstab[symidx] & 0x7fff;
- if ((map->l_versions[ndx].hash != version->hash
- || strcmp (map->l_versions[ndx].name, version->name))
- && (version->hidden || map->l_versions[ndx].hash
- || (verstab[symidx] & 0x8000)))
- /* It's not the version we want. */
- continue;
- }
- }
- else
- {
- /* No specific version is selected. There are two ways we
- can got here:
+ /* Otherwise we accept the symbol. */
+ }
+ else
+ {
+ /* We can match the version information or use the
+ default one if it is not hidden. */
+ ElfW(Half) ndx = verstab[symidx] & 0x7fff;
+ if ((map->l_versions[ndx].hash != version->hash
+ || strcmp (map->l_versions[ndx].name, version->name))
+ && (version->hidden || map->l_versions[ndx].hash
+ || (verstab[symidx] & 0x8000)))
+ /* It's not the version we want. */
+ return NULL;
+ }
+ }
+ else
+ {
+ /* No specific version is selected. There are two ways we
+ can got here:
- - a binary which does not include versioning information
- is loaded
+ - a binary which does not include versioning information
+ is loaded
- - dlsym() instead of dlvsym() is used to get a symbol which
- might exist in more than one form
+ - dlsym() instead of dlvsym() is used to get a symbol which
+ might exist in more than one form
- If the library does not provide symbol version
- information there is no problem at at: we simply use the
- symbol if it is defined.
+ If the library does not provide symbol version information
+ there is no problem at at: we simply use the symbol if it
+ is defined.
- These two lookups need to be handled differently if the
- library defines versions. In the case of the old
- unversioned application the oldest (default) version
- should be used. In case of a dlsym() call the latest and
- public interface should be returned. */
- if (verstab != NULL)
- {
- if ((verstab[symidx] & 0x7fff)
- >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3))
- {
- /* Don't accept hidden symbols. */
- if ((verstab[symidx] & 0x8000) == 0
- && num_versions++ == 0)
- /* No version so far. */
- versioned_sym = sym;
+ These two lookups need to be handled differently if the
+ library defines versions. In the case of the old
+ unversioned application the oldest (default) version
+ should be used. In case of a dlsym() call the latest and
+ public interface should be returned. */
+ if (verstab != NULL)
+ {
+ if ((verstab[symidx] & 0x7fff)
+ >= ((flags & DL_LOOKUP_RETURN_NEWEST) ? 2 : 3))
+ {
+ /* Don't accept hidden symbols. */
+ if ((verstab[symidx] & 0x8000) == 0
+ && num_versions++ == 0)
+ /* No version so far. */
+ versioned_sym = sym;
- continue;
- }
- }
+ return NULL;
+ }
+ }
+ }
+
+ /* There cannot be another entry for this symbol so stop here. */
+ return sym;
+ }
+
+ if (__builtin_expect (map->l_gnu_buckets != NULL, 1))
+ {
+ /* Use the new GNU-style hash table. */
+ size_t chainoff = map->l_gnu_buckets[new_hash % map->l_nbuckets];
+
+ if (chainoff != 0xffffffff)
+ {
+ const Elf32_Word *hasharr = &map->l_gnu_hashbase[chainoff];
+ Elf32_Word new_hash_masked = new_hash & ~1u;
+
+ /* Note: this loop is optimized for the case of an
+ unsuccessful lookup. This is by far the more likely
+ outcome. If the hash value matches we compute the
+ symbol index using the pointer difference as opposed
+ to keeping track. This simplifies the loop itself
+ significantly. */
+ do
+ if ((*hasharr & ~1u) == new_hash_masked)
+ {
+ symidx = (map->l_gnu_symbias
+ + (hasharr - map->l_gnu_hashbase));
+ sym = check_match (&symtab[symidx]);
+ if (sym != NULL)
+ goto found_it;
+ }
+ while ((*hasharr++ & 1u) == 0);
}
+ }
+ else
+ {
+ if (*old_hash == 0xffffffff)
+ *old_hash = _dl_elf_hash (undef_name);
- /* There cannot be another entry for this symbol so stop here. */
- goto found_it;
+ /* Use the old SysV-style hash table. Search the appropriate
+ hash bucket in this object's symbol table for a definition
+ for the same symbol name. */
+ for (symidx = map->l_buckets[*old_hash % map->l_nbuckets];
+ symidx != STN_UNDEF;
+ symidx = map->l_chain[symidx])
+ {
+ sym = check_match (&symtab[symidx]);
+ if (sym != NULL)
+ goto found_it;
+ }
}
/* If we have seen exactly one versioned symbol while we are
--- libc/elf/dynamic-link.h.jj 15 Mar 2005 22:57:25 -0000 1.54
+++ libc/elf/dynamic-link.h 3 Jul 2006 20:48:36 -0000
@@ -143,6 +143,8 @@
# endif
ADJUST_DYN_INFO (DT_JMPREL);
ADJUST_DYN_INFO (VERSYMIDX (DT_VERSYM));
+ ADJUST_DYN_INFO (DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM + DT_THISPROCNUM
+ + DT_VERSIONTAGNUM + DT_EXTRANUM + DT_VALNUM);
# undef ADJUST_DYN_INFO
assert (cnt <= DL_RO_DYN_TEMP_CNT);
}
--- libc/elf/elf.h.jj 25 Feb 2006 01:57:44 -0000 1.154
+++ libc/elf/elf.h 3 Jul 2006 20:49:49 -0000
@@ -329,7 +329,8 @@
#define SHT_GROUP 17 /* Section group */
#define SHT_SYMTAB_SHNDX 18 /* Extended section indeces */
#define SHT_NUM 19 /* Number of defined types. */
-#define SHT_LOOS 0x60000000 /* Start OS-specific */
+#define SHT_LOOS 0x60000000 /* Start OS-specific. */
+#define SHT_GNU_HASH 0x6ffffff6 /* GNU-style hash table. */
#define SHT_GNU_LIBLIST 0x6ffffff7 /* Prelink library list */
#define SHT_CHECKSUM 0x6ffffff8 /* Checksum for DSO content. */
#define SHT_LOSUNW 0x6ffffffa /* Sun-specific low bound. */
@@ -699,6 +700,9 @@
If any adjustment is made to the ELF object after it has been
built these entries will need to be adjusted. */
#define DT_ADDRRNGLO 0x6ffffe00
+#define DT_GNU_HASH 0x6ffffef5 /* GNU-style hash table. */
+#define DT_TLSDESC_PLT 0x6ffffef6
+#define DT_TLSDESC_GOT 0x6ffffef7
#define DT_GNU_CONFLICT 0x6ffffef8 /* Start of conflict section */
#define DT_GNU_LIBLIST 0x6ffffef9 /* Library list */
#define DT_CONFIG 0x6ffffefa /* Configuration information. */
@@ -709,7 +713,7 @@
#define DT_SYMINFO 0x6ffffeff /* Syminfo table. */
#define DT_ADDRRNGHI 0x6ffffeff
#define DT_ADDRTAGIDX(tag) (DT_ADDRRNGHI - (tag)) /* Reverse order! */
-#define DT_ADDRNUM 10
+#define DT_ADDRNUM 11
/* The versioning entry types. The next are defined as part of the
GNU extension. */
--- libc/include/link.h.jj 1 Mar 2006 06:18:30 -0000 1.38
+++ libc/include/link.h 3 Jul 2006 20:50:24 -0000
@@ -124,7 +124,7 @@
const ElfW(Phdr) *l_phdr; /* Pointer to program header table in core. */
ElfW(Addr) l_entry; /* Entry point location. */
ElfW(Half) l_phnum; /* Number of program header entries. */
- ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */
+ ElfW(Half) l_ldnum; /* Number of dynamic segment entries. */
/* Array of DT_NEEDED dependencies and their dependencies, in
dependency order for symbol lookup (with and without
@@ -141,7 +141,17 @@
/* Symbol hash table. */
Elf_Symndx l_nbuckets;
- const Elf_Symndx *l_buckets, *l_chain;
+ const Elf32_Word *l_gnu_buckets;
+ union
+ {
+ const Elf32_Word *l_gnu_hashbase;
+ const Elf_Symndx *l_chain;
+ };
+ union
+ {
+ Elf32_Word l_gnu_symbias;
+ const Elf_Symndx *l_buckets;
+ };
unsigned int l_direct_opencount; /* Reference count for dlopen/dlclose. */
enum /* Where this object came from. */
More information about the Libc-alpha
mailing list