[src/trunk]: src/libexec/ld.elf_so Use fast_remainder32 for the ELF hash. For...

[joerg <joerg%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/4f5f92ed034a
branches:  trunk
changeset: 753639:4f5f92ed034a
user:      joerg <joerg%NetBSD.org@localhost>
date:      Mon Apr 05 14:01:26 2010 +0000

description:
Use fast_remainder32 for the ELF hash. For the hot cache case, this
speeds up Firefox startup by over 2% on AMD64.
Limit hash table buckets to 32bit.

diffstat:

 libexec/ld.elf_so/headers.c |  20 +++++++++++++++++---
 libexec/ld.elf_so/reloc.c   |   9 +++++++--
 libexec/ld.elf_so/rtld.h    |   7 +++++--
 libexec/ld.elf_so/symbol.c  |   8 +++++---
 4 files changed, 34 insertions(+), 10 deletions(-)

diffs (145 lines):

diff -r 65a4a7cf267a -r 4f5f92ed034a libexec/ld.elf_so/headers.c
--- a/libexec/ld.elf_so/headers.c       Mon Apr 05 12:56:51 2010 +0000
+++ b/libexec/ld.elf_so/headers.c       Mon Apr 05 14:01:26 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: headers.c,v 1.28 2009/04/12 13:29:29 lukem Exp $        */
+/*     $NetBSD: headers.c,v 1.29 2010/04/05 14:01:26 joerg Exp $        */
 
 /*
  * Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
 
 #include <sys/cdefs.h>
 #ifndef lint
-__RCSID("$NetBSD: headers.c,v 1.28 2009/04/12 13:29:29 lukem Exp $");
+__RCSID("$NetBSD: headers.c,v 1.29 2010/04/05 14:01:26 joerg Exp $");
 #endif /* not lint */
 
 #include <err.h>
@@ -53,6 +53,7 @@
 #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 @@
                                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;
 
diff -r 65a4a7cf267a -r 4f5f92ed034a libexec/ld.elf_so/reloc.c
--- a/libexec/ld.elf_so/reloc.c Mon Apr 05 12:56:51 2010 +0000
+++ b/libexec/ld.elf_so/reloc.c Mon Apr 05 14:01:26 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: reloc.c,v 1.101 2010/01/16 10:37:51 skrll Exp $         */
+/*     $NetBSD: reloc.c,v 1.102 2010/04/05 14:01:26 joerg Exp $         */
 
 /*
  * Copyright 1996 John D. Polstra.
@@ -39,7 +39,7 @@
 
 #include <sys/cdefs.h>
 #ifndef lint
-__RCSID("$NetBSD: reloc.c,v 1.101 2010/01/16 10:37:51 skrll Exp $");
+__RCSID("$NetBSD: reloc.c,v 1.102 2010/04/05 14:01:26 joerg Exp $");
 #endif /* not lint */
 
 #include <err.h>
@@ -52,6 +52,7 @@
 #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 @@
                            " 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),
diff -r 65a4a7cf267a -r 4f5f92ed034a libexec/ld.elf_so/rtld.h
--- a/libexec/ld.elf_so/rtld.h  Mon Apr 05 12:56:51 2010 +0000
+++ b/libexec/ld.elf_so/rtld.h  Mon Apr 05 14:01:26 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: rtld.h,v 1.90 2010/03/18 22:17:55 roy Exp $     */
+/*     $NetBSD: rtld.h,v 1.91 2010/04/05 14:01:26 joerg Exp $   */
 
 /*
  * Copyright 1996 John D. Polstra.
@@ -162,7 +162,10 @@
 #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 */
 
diff -r 65a4a7cf267a -r 4f5f92ed034a libexec/ld.elf_so/symbol.c
--- a/libexec/ld.elf_so/symbol.c        Mon Apr 05 12:56:51 2010 +0000
+++ b/libexec/ld.elf_so/symbol.c        Mon Apr 05 14:01:26 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: symbol.c,v 1.52 2010/03/18 22:17:55 roy Exp $   */
+/*     $NetBSD: symbol.c,v 1.53 2010/04/05 14:01:26 joerg Exp $         */
 
 /*
  * Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
 
 #include <sys/cdefs.h>
 #ifndef lint
-__RCSID("$NetBSD: symbol.c,v 1.52 2010/03/18 22:17:55 roy Exp $");
+__RCSID("$NetBSD: symbol.c,v 1.53 2010/04/05 14:01:26 joerg Exp $");
 #endif /* not lint */
 
 #include <err.h>
@@ -53,6 +53,7 @@
 #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 @@
 {
        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;