Small ld.elf_so speed up

[Joerg Sonnenberger <joerg%britannica.bec.de@localhost>]

Hi all,
please test the attached patch. It improves startup time for Firefox by
2% or more here.

Joerg

Index: headers.c
===================================================================
RCS file: /home/joerg/repo/netbsd/src/libexec/ld.elf_so/headers.c,v
retrieving revision 1.28
diff -u -p -r1.28 headers.c
--- headers.c   12 Apr 2009 13:29:29 -0000      1.28
+++ headers.c   31 Mar 2010 20:08:25 -0000
@@ -53,6 +53,7 @@ __RCSID("$NetBSD: headers.c,v 1.28 2009/
 #include <unistd.h>
 #include <sys/types.h>
 #include <sys/mman.h>
+#include <sys/bitops.h>
 #include <dirent.h>
 
 #include "debug.h"
@@ -138,10 +139,23 @@ _rtld_digest_dynamic(const char *execnam
                                const Elf_Word *hashtab = (const Elf_Word *)
                                (obj->relocbase + dynp->d_un.d_ptr);
 
-                               obj->nbuckets = hashtab[0];
+                               if (hashtab[0] > UINT32_MAX)
+                                       obj->nbuckets = UINT32_MAX;
+                               else
+                                       obj->nbuckets = hashtab[0];
                                obj->nchains = hashtab[1];
                                obj->buckets = hashtab + 2;
                                obj->chains = obj->buckets + obj->nbuckets;
+                               /*
+                                * Should really be in _rtld_relocate_objects,
+                                * but _rtld_symlook_obj might be used before.
+                                */
+                               if (obj->nbuckets) {
+                                       fast_divide32_prepare(obj->nbuckets,
+                                           &obj->nbuckets_m,
+                                           &obj->nbuckets_s1,
+                                           &obj->nbuckets_s2);
+                               }
                        }
                        break;
 
Index: reloc.c
===================================================================
RCS file: /home/joerg/repo/netbsd/src/libexec/ld.elf_so/reloc.c,v
retrieving revision 1.101
diff -u -p -r1.101 reloc.c
--- reloc.c     16 Jan 2010 10:37:51 -0000      1.101
+++ reloc.c     31 Mar 2010 20:03:03 -0000
@@ -52,6 +52,7 @@ __RCSID("$NetBSD: reloc.c,v 1.101 2010/0
 #include <unistd.h>
 #include <sys/types.h>
 #include <sys/mman.h>
+#include <sys/bitops.h>
 #include <dirent.h>
 
 #include "debug.h"
@@ -154,6 +155,10 @@ _rtld_relocate_objects(Obj_Entry *first,
                            " symbol table", obj->path);
                        return -1;
                }
+               if (obj->nbuckets == UINT32_MAX) {
+                       _rtld_error("%s: Symbol table too large", obj->path);
+                       return -1;
+               }
                rdbg((" relocating %s (%ld/%ld rel/rela, %ld/%ld plt rel/rela)",
                    obj->path,
                    (long)(obj->rellim - obj->rel),
Index: rtld.h
===================================================================
RCS file: /home/joerg/repo/netbsd/src/libexec/ld.elf_so/rtld.h,v
retrieving revision 1.90
diff -u -p -r1.90 rtld.h
--- rtld.h      18 Mar 2010 22:17:55 -0000      1.90
+++ rtld.h      30 Mar 2010 23:10:06 -0000
@@ -162,7 +162,10 @@ typedef struct Struct_Obj_Entry {
 #endif
 
        const Elf_Word *buckets;        /* Hash table buckets array */
-       unsigned long   nbuckets;       /* Number of buckets */
+       uint32_t        nbuckets;       /* Number of buckets */
+       uint32_t        nbuckets_m;     /* Precomputed for fast remainder */
+       uint8_t         nbuckets_s1;
+       uint8_t         nbuckets_s2;
        const Elf_Word *chains;         /* Hash table chain array */
        unsigned long   nchains;        /* Number of chains */
 
Index: symbol.c
===================================================================
RCS file: /home/joerg/repo/netbsd/src/libexec/ld.elf_so/symbol.c,v
retrieving revision 1.52
diff -u -p -r1.52 symbol.c
--- symbol.c    18 Mar 2010 22:17:55 -0000      1.52
+++ symbol.c    31 Mar 2010 20:03:35 -0000
@@ -53,6 +53,7 @@ __RCSID("$NetBSD: symbol.c,v 1.52 2010/0
 #include <unistd.h>
 #include <sys/types.h>
 #include <sys/mman.h>
+#include <sys/bitops.h>
 #include <dirent.h>
 
 #include "debug.h"
@@ -229,7 +230,8 @@ _rtld_symlook_obj(const char *name, unsi
 {
        unsigned long symnum;
 
-       for (symnum = obj->buckets[hash % obj->nbuckets];
+       for (symnum = obj->buckets[fast_remainder32(hash, obj->nbuckets,
+            obj->nbuckets_m, obj->nbuckets_s1, obj->nbuckets_s2)];
             symnum != ELF_SYM_UNDEFINED;
             symnum = obj->chains[symnum]) {
                const Elf_Sym  *symp;