DT_GNU_HASH: ~ 50% dynamic linking improvement

[Jakub Jelinek]

On Thu, Jun 29, 2006 at 07:27:06PM +0100, Michael Meeks wrote:
> 	3. What we hash:
> 		+ it is incredible to me that UNDEF symbols are
> 		  included in the symbol hash; I see no legitimate
> 		  use for that [ eg. 'free' is an expensive hit in the
> 		  hash for virtually every app ;-]

More comments later, but as you can see in the patch, undefined
symbols are never added to .gnu.hash chains, only defined ones
(and, as I was lazy, also some of the undefined PLT symbols [*]).

That's what the:
+  /* Ignore also local symbols and undefined symbols.  */
+  if (h->forced_local
+      || h->root.type == bfd_link_hash_undefined
+      || h->root.type == bfd_link_hash_undefweak
+      || ((h->root.type == bfd_link_hash_defined
+          || h->root.type == bfd_link_hash_defweak)
+         && h->root.u.def.section->output_section == NULL))
+    return TRUE;
in elf_collect_gnu_hash_codes and elf_renumber_gnu_hash_syms
does, .dynsym after sorting contains first the special symbols
(0, STT_SECTION, STB_LOCAL), then SHN_UNDEF symbols and only
after this contains the defined ones, sorted by the hash % nbuckets
value.

[*] SHN_UNDEF symbols with st_value != 0 need to be in .gnu.hash
(and are there), as they are used when resolving relocations that
take address of functions.  These are at that point still
bfd_link_hash_defined with non-NULL output_section and only
during dynamic symbol finalization are turned into st_shndx SHN_UNDEF.
But, on i386/x86_64 we have an optimization where if the binary
never takes address of some function, st_value on its SHN_UNDEF
symbol is cleared (see e.g. elf64_x86_64_finish_dynamic_symbol
          /* Mark the symbol as undefined, rather than as defined in
             the .plt section.  Leave the value if there were any
             relocations where pointer equality matters (this is a clue
             for the dynamic linker, to make function pointer
             comparisons work between an application and shared
             library), otherwise set it to zero.  If a function is only
             called from a binary, there is no need to slow down
             shared libraries because of that.  */
          sym->st_shndx = SHN_UNDEF;
          if (!h->pointer_equality_needed)
            sym->st_value = 0;
).  Such symbols could be left out of .gnu.hash too, assuming we
add some target hook, as pointer_equality_needed bit is target specific.

	Jakub