This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
binutils/glibc .hashvals section ...
- From: michael meeks <michael dot meeks at novell dot com>
- To: binutils <binutils at sources dot redhat dot com>
- Date: Wed, 25 Jan 2006 14:34:18 +0000
- Subject: binutils/glibc .hashvals section ...
- Reply-to: michael dot meeks at novell dot com
Hi there,
So - in order to speedup linking: still the major CPU hog on OO.o load,
(cf. -Bdirect patches passim) I have a simpler, perhaps less
controversial approach: storing pre-computed elf hashes in a .hashvals
section.
This is rather nice because it turns the inner do_lookup_x loop into a
single L2 cache miss rather than 2 (.dynsym and .dynstr) - this gives
(as you might expect) a pleasant speedup. Of course, in addition since
we're accessing only a 32bit value - instead of a long (for me avg.
65byte) symbol name we also get better cache utilization.
eg. dlopening libsvx 10x over in a loop, twice gives:
pre-compute: 989.01 ms, 983.54 ms Avg: 986ms
normal: 1645.16 ms, 1642.92 ms Avg: 1644ms
ie. 40% faster. Similar numbers for VCL: ~51% faster. One would imagine
cachegrind numbers would demonstrate the improvement is ~all L2 cache
miss saving.
Trivial patch follows; of course, since this requires glibc support one
can't be overly optimistic wrt. inclusion ;-) but surely it's only
polite to post here for discussion.
HTH,
Michael.
--
michael.meeks@novell.com <><, Pseudo Engineer, itinerant idiot
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf.c binutils.current/bfd/elf.c
--- binutils-2.16.91.0.4/bfd/elf.c 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elf.c 2006-01-20 14:35:28.000000000 +0000
@@ -1212,6 +1212,7 @@
case DT_AUXILIARY: name = "AUXILIARY"; stringp = TRUE; break;
case DT_USED: name = "USED"; break;
case DT_FILTER: name = "FILTER"; stringp = TRUE; break;
+ case DT_SUSE_HASHVALS: name = "SUSE_HASHVALS"; break;
}
fprintf (f, " %-11s ", name);
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elflink.c binutils.current/bfd/elflink.c
--- binutils-2.16.91.0.4/bfd/elflink.c 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elflink.c 2006-01-20 15:03:00.000000000 +0000
@@ -174,6 +174,15 @@
flags = bed->dynamic_sec_flags;
+ if (info->hashvals)
+ {
+ s = bfd_make_section (abfd, ".suse.hashvals");
+ if (s == NULL
+ || ! bfd_set_section_flags (abfd, s, flags | SEC_READONLY)
+ || ! bfd_set_section_alignment (abfd, s, 2))
+ return FALSE;
+ }
+
/* A dynamically linked executable has a .interp section, but a
shared library does not. */
if (info->executable)
@@ -5728,6 +5737,26 @@
memset (s->contents, 0, section_sym_count * bed->s->sizeof_sym);
}
+ /* Create the direct bindings section - 1 entry per dynsym */
+ s = bfd_get_section_by_name (dynobj, ".suse.hashvals");
+ if (s)
+ {
+ if (dynsymcount == 0)
+ s->flags |= SEC_EXCLUDE;
+ else
+ {
+ fprintf (stderr, "Alloc suse.hashvals %d %d\n",
+ (int)dynsymcount, (int)bed->s->sizeof_hash_entry);
+ s->size = dynsymcount * bed->s->sizeof_hash_entry;
+ s->contents = bfd_zalloc (output_bfd, s->size);
+ if (s->contents == NULL)
+ return FALSE;
+ memset (s->contents, 0xfe, s->size);
+ if (!_bfd_elf_add_dynamic_entry (info, DT_SUSE_HASHVALS, 0))
+ return FALSE;
+ }
+ }
+
/* Compute the size of the hashing table. As a side effect this
computes the hash values for all the names we export. */
bucketcount = compute_bucket_count (info);
@@ -5799,6 +5828,8 @@
/* Array large enough to hold a section pointer for each local
symbol of any input BFD. */
asection **sections;
+ /* .suse.hashvals section */
+ asection *hashvals_sec;
/* Buffer to hold swapped out symbols. */
bfd_byte *symbuf;
/* And one for symbol section indices. */
@@ -6614,6 +6645,18 @@
((bfd_byte *) finfo->hash_sec->contents
+ (bucketcount + 2 + h->dynindx) * hash_entry_size));
+ if (finfo->hashvals_sec)
+ {
+ bfd_vma offset = hash_entry_size * h->dynindx;
+ if (offset > finfo->hashvals_sec->size)
+ fprintf (stderr, "Out of bounds hashvals section index %d size %d\n",
+ (int) offset, (int) finfo->hashvals_sec->size);
+ else
+ bfd_put (8 * hash_entry_size, finfo->output_bfd,
+ h->u.elf_hash_value,
+ finfo->hashvals_sec->contents + offset);
+ }
+
if (finfo->symver_sec != NULL && finfo->symver_sec->contents != NULL)
{
Elf_Internal_Versym iversym;
@@ -7786,6 +7829,7 @@
finfo.dynsym_sec = NULL;
finfo.hash_sec = NULL;
finfo.symver_sec = NULL;
+ finfo.hashvals_sec = NULL;
}
else
{
@@ -7794,6 +7838,7 @@
BFD_ASSERT (finfo.dynsym_sec != NULL && finfo.hash_sec != NULL);
finfo.symver_sec = bfd_get_section_by_name (dynobj, ".gnu.version");
/* Note that it is OK if symver_sec is NULL. */
+ finfo.hashvals_sec = bfd_get_section_by_name (dynobj, ".suse.hashvals");
}
finfo.contents = NULL;
@@ -8533,6 +8578,9 @@
case DT_HASH:
name = ".hash";
goto get_vma;
+ case DT_SUSE_HASHVALS:
+ name = ".suse.hashvals";
+ goto get_vma;
case DT_STRTAB:
name = ".dynstr";
goto get_vma;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/include/bfdlink.h binutils.current/include/bfdlink.h
--- binutils-2.16.91.0.4/include/bfdlink.h 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/include/bfdlink.h 2006-01-20 14:19:46.000000000 +0000
@@ -261,6 +261,10 @@
need much more time and therefore must be explicitly selected. */
unsigned int optimize: 1;
+ /* TRUE if we want to produced a section containing pre-computed
+ hash values. This consumes more space. */
+ unsigned int hashvals: 1;
+
/* TRUE if ok to have multiple definition. */
unsigned int allow_multiple_definition: 1;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/include/elf/common.h binutils.current/include/elf/common.h
--- binutils-2.16.91.0.4/include/elf/common.h 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/include/elf/common.h 2006-01-20 14:34:18.000000000 +0000
@@ -604,6 +604,11 @@
#define DT_FILTER 0x7fffffff
+/* Selected at random */
+#define DT_SUSE_LO 0x6cbdd030
+#define DT_SUSE_HASHVALS DT_SUSE_LO
+#define DT_SUSE_HI 0x6cbdd040
+
/* Values used in DT_FEATURE .dynamic entry. */
#define DTF_1_PARINIT 0x00000001
/* From
Files binutils-2.16.91.0.4/ld/ld-new and binutils.current/ld/ld-new differ
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/ld/lexsup.c binutils.current/ld/lexsup.c
--- binutils-2.16.91.0.4/ld/lexsup.c 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/ld/lexsup.c 2006-01-20 14:31:21.000000000 +0000
@@ -78,6 +78,7 @@
OPTION_EL,
OPTION_EMBEDDED_RELOCS,
OPTION_EXPORT_DYNAMIC,
+ OPTION_HASHVALS,
OPTION_HELP,
OPTION_IGNORE,
OPTION_MAP,
@@ -341,6 +342,8 @@
'\0', NULL, NULL, ONE_DASH },
{ {"static", no_argument, NULL, OPTION_NON_SHARED},
'\0', NULL, NULL, ONE_DASH },
+ { {"hashvals", no_argument, NULL, OPTION_HASHVALS},
+ '\0', NULL, N_("Store pre-computed elf hash codes"), ONE_DASH },
{ {"Bsymbolic", no_argument, NULL, OPTION_SYMBOLIC},
'\0', NULL, N_("Bind global references locally"), ONE_DASH },
{ {"check-sections", no_argument, NULL, OPTION_CHECK_SECTIONS},
@@ -1111,6 +1114,9 @@
case OPTION_SYMBOLIC:
link_info.symbolic = TRUE;
break;
+ case OPTION_HASHVALS:
+ link_info.hashvals = TRUE;
+ break;
case 't':
trace_files = TRUE;
break;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' glibc-pristine/elf/dl-lookup.c glibc-2.3/elf/dl-lookup.c
--- glibc-pristine/elf/dl-lookup.c 2005-11-17 17:48:13.000000000 +0000
+++ glibc-2.3/elf/dl-lookup.c 2006-01-23 14:45:22.000000000 +0000
@@ -206,10 +206,38 @@
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);
+ unsigned long int hash;
struct sym_val current_value = { NULL, NULL };
struct r_scope_elem **scope = symbol_scope;
+ /* This sucks mostly - but people sadly don't pass a symtab index, or hashvals ptr in */
+ const Elf_Symndx *hashvals;
+
+ if (__builtin_expect (undef_map != NULL, 1) &&
+ __builtin_expect (undef_map->l_info[SUSEIDX(DT_SUSE_HASHVALS)] != NULL, 1) &&
+ __builtin_expect ((hashvals = (const void *)D_PTR (undef_map, l_info[SUSEIDX(DT_SUSE_HASHVALS)])) != NULL, 1) &&
+ __builtin_expect (*ref != NULL, 1))
+ {
+ const ElfW(Sym) *symtab = (const void *) D_PTR (undef_map, l_info[DT_SYMTAB]);
+ hashvals += *ref - symtab;
+
+ if (__builtin_expect ((ElfW(Addr))hashvals >= undef_map->l_map_end, 0) ||
+ __builtin_expect ((ElfW(Addr))hashvals <= undef_map->l_map_start, 0))
+ _dl_debug_printf ("out of bounds madness ... 0x%x\n", (int) hashvals);
+ else
+ {
+ hash = *hashvals;
+#if 0
+ if (hash != _dl_elf_hash (undef_name))
+ _dl_debug_printf ("Hash difference ! 0x%x 0x%x [offset 0x%x]\n",
+ (int) _dl_elf_hash (undef_name),
+ (int) hash, (int) (*ref - symtab));
+#endif
+ }
+ }
+ else
+ hash = _dl_elf_hash (undef_name);
+
bump_num_relocations ();
/* No other flag than DL_LOOKUP_ADD_DEPENDENCY is allowed if we look
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' glibc-pristine/elf/do-lookup.h glibc-2.3/elf/do-lookup.h
--- glibc-pristine/elf/do-lookup.h 2005-04-06 07:57:05.000000000 +0100
+++ glibc-2.3/elf/do-lookup.h 2006-01-23 14:17:32.000000000 +0000
@@ -17,6 +17,9 @@
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
+# define SUSEIDX(sym) (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM + \
+ DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM + DT_SUSE_TAGIDX (sym))
+
/* 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. */
@@ -35,6 +38,7 @@
do
{
const ElfW(Sym) *symtab;
+ const Elf_Symndx *hashvals;
const char *strtab;
const ElfW(Half) *verstab;
Elf_Symndx symidx;
@@ -62,9 +66,10 @@
undef_name,
map->l_name[0] ? map->l_name : rtld_progname);
- symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]);
- strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]);
- verstab = map->l_versyms;
+ if (__builtin_expect (map->l_info[SUSEIDX(DT_SUSE_HASHVALS)] != NULL, 1))
+ hashvals = (const void *) D_PTR (map, l_info[SUSEIDX(DT_SUSE_HASHVALS)]);
+ else
+ hashvals = NULL;
/* Search the appropriate hash bucket in this object's symbol table
for a definition for the same symbol name. */
@@ -72,6 +77,20 @@
symidx != STN_UNDEF;
symidx = map->l_chain[symidx])
{
+ if (__builtin_expect (hashvals != NULL, 1) &&
+ __builtin_expect ((ElfW(Addr))hashvals < map->l_map_end, 1) &&
+ __builtin_expect ((ElfW(Addr))hashvals > map->l_map_start, 1))
+ {
+ if (__builtin_expect (hashvals[symidx] != hash, 1))
+ continue;
+ }
+ /* If hashvals is present 99.9% of the loop is done: what follows
+ is the very un-common / direct-hit case */
+
+ symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]);
+ strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]);
+ verstab = map->l_versyms;
+
sym = &symtab[symidx];
assert (ELF_RTYPE_CLASS_PLT == 1);
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' glibc-pristine/elf/dynamic-link.h glibc-2.3/elf/dynamic-link.h
--- glibc-pristine/elf/dynamic-link.h 2005-11-17 17:48:13.000000000 +0000
+++ glibc-2.3/elf/dynamic-link.h 2006-01-20 16:54:28.000000000 +0000
@@ -24,6 +24,10 @@
#ifndef VERSYMIDX
# define VERSYMIDX(sym) (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGIDX (sym))
#endif
+#ifndef SUSEIDX
+# define SUSEIDX(sym) (DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM + \
+ DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM + DT_SUSE_TAGIDX (sym))
+#endif
/* Read the dynamic section at DYN and fill in INFO with indices DT_*. */
@@ -52,6 +56,9 @@
else if (dyn->d_tag >= DT_LOPROC &&
dyn->d_tag < DT_LOPROC + DT_THISPROCNUM)
info[dyn->d_tag - DT_LOPROC + DT_NUM] = dyn;
+ else if (dyn->d_tag >= DT_SUSE_LO &&
+ dyn->d_tag < DT_SUSE_LO + DT_SUSENUM)
+ info[SUSEIDX(dyn->d_tag)] = dyn;
else if ((Elf32_Word) DT_VERSIONTAGIDX (dyn->d_tag) < DT_VERSIONTAGNUM)
info[VERSYMIDX (dyn->d_tag)] = dyn;
else if ((Elf32_Word) DT_EXTRATAGIDX (dyn->d_tag) < DT_EXTRANUM)
@@ -102,6 +109,8 @@
# endif
ADJUST_DYN_INFO (DT_JMPREL);
ADJUST_DYN_INFO (VERSYMIDX (DT_VERSYM));
+ ADJUST_DYN_INFO (SUSEIDX(DT_SUSE_HASHVALS));
+ ADJUST_DYN_INFO (SUSEIDX(DT_SUSE_DIRECT));
# undef ADJUST_DYN_INFO
assert (cnt <= DL_RO_DYN_TEMP_CNT);
}
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' glibc-pristine/elf/elf.h glibc-2.3/elf/elf.h
--- glibc-pristine/elf/elf.h 2005-11-17 17:48:13.000000000 +0000
+++ glibc-2.3/elf/elf.h 2006-01-20 15:27:22.000000000 +0000
@@ -729,6 +729,14 @@
#define DT_VERSIONTAGIDX(tag) (DT_VERNEEDNUM - (tag)) /* Reverse order! */
#define DT_VERSIONTAGNUM 16
+/* SUSE specific pieces - at a random OS specific address ... */
+#define DT_SUSE_LO 0x6cbdd030
+#define DT_SUSE_HASHVALS DT_SUSE_LO
+#define DT_SUSE_DIRECT DT_SUSE_LO + 1
+#define DT_SUSE_HI 0x6cbdd040
+#define DT_SUSE_TAGIDX(tag) (tag - DT_SUSE_LO)
+#define DT_SUSENUM 4
+
/* Sun added these machine-independent extensions in the "processor-specific"
range. Be compatible. */
#define DT_AUXILIARY 0x7ffffffd /* Shared object to load before self */
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' glibc-pristine/include/link.h glibc-2.3/include/link.h
--- glibc-pristine/include/link.h 2005-11-17 17:48:13.000000000 +0000
+++ glibc-2.3/include/link.h 2006-01-20 15:27:17.000000000 +0000
@@ -154,7 +154,7 @@
are indexed by DT_ADDRTAGIDX(tagvalue), see <elf.h>. */
ElfW(Dyn) *l_info[DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM
- + DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM];
+ + DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM + DT_SUSENUM];
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. */