This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

binutils/glibc .hashvals section ...


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.  */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]