Performance improvements for the ELF dynamic linker. These

particularly help programs which load many shared libraries with
a lot of relocations.  Large C++ programs such as are found in KDE
are a prime example.

While relocating a shared object, maintain a vector of symbols
which have already been looked up, directly indexed by symbol
number.  Typically, symbols which are referenced by a relocation
entry are referenced by many of them.  This is the same optimization
I made to the a.out dynamic linker in 1995 (rtld.c revision 1.30).

Also, compare the first character of a sought-after symbol with its
symbol table entry before calling strcmp().

On a PII/400 these changes reduce the start-up time of a typical
KDE program from 833 msec (elapsed) to 370 msec.

MFC after:	5 days

5 files changed, 60 insertions, 18 deletions

diff --git a/libexec/rtld-elf/alpha/reloc.c b/libexec/rtld-elf/alpha/reloc.c
index e27f922..f963476 100644
--- a/libexec/rtld-elf/alpha/reloc.c
+++ b/libexec/rtld-elf/alpha/reloc.c
@@ -71,6 +71,11 @@ static int
 reloc_non_plt_obj(Obj_Entry *obj_rtld, Obj_Entry *obj, const Elf_Rela *rela)
 {
 	Elf_Addr *where = (Elf_Addr *) (obj->relocbase + rela->r_offset);
+	SymCache *cache;
+
+	cache = (SymCache *)alloca(obj->nchains * sizeof(SymCache));
+	if (cache != NULL)
+	    memset(cache, 0, obj->nchains * sizeof(SymCache));
 
 	switch (ELF_R_TYPE(rela->r_info)) {
 
@@ -82,7 +87,7 @@ reloc_non_plt_obj(Obj_Entry *obj_rtld, Obj_Entry *obj, const Elf_Rela *rela)
 			const Obj_Entry *defobj;
 
 			def = find_symdef(ELF_R_SYM(rela->r_info), obj,
-			    &defobj, false);
+			    &defobj, false, cache);
 			if (def == NULL)
 				return -1;
 			store64(where,
@@ -97,7 +102,7 @@ reloc_non_plt_obj(Obj_Entry *obj_rtld, Obj_Entry *obj, const Elf_Rela *rela)
 			Elf_Addr val;
 
 			def = find_symdef(ELF_R_SYM(rela->r_info), obj,
-			    &defobj, false);
+			    &defobj, false, cache);
 			if (def == NULL)
 				return -1;
 			val = (Elf_Addr) (defobj->relocbase + def->st_value +
@@ -228,7 +233,8 @@ reloc_jmpslots(Obj_Entry *obj)
 
 	    assert(ELF_R_TYPE(rel->r_info) == R_ALPHA_JMP_SLOT);
 	    where = (Elf_Addr *)(obj->relocbase + rel->r_offset);
-	    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true);
+	    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true,
+	        NULL);
 	    if (def == NULL)
 		return -1;
 	    reloc_jmpslot(where,
@@ -246,7 +252,8 @@ reloc_jmpslots(Obj_Entry *obj)
 
 	    assert(ELF_R_TYPE(rela->r_info) == R_ALPHA_JMP_SLOT);
 	    where = (Elf_Addr *)(obj->relocbase + rela->r_offset);
-	    def = find_symdef(ELF_R_SYM(rela->r_info), obj, &defobj, true);
+	    def = find_symdef(ELF_R_SYM(rela->r_info), obj, &defobj, true,
+	        NULL);
 	    if (def == NULL)
 		return -1;
 	    reloc_jmpslot(where,
diff --git a/libexec/rtld-elf/amd64/reloc.c b/libexec/rtld-elf/amd64/reloc.c
index 360733a..aff70b0 100644
--- a/libexec/rtld-elf/amd64/reloc.c
+++ b/libexec/rtld-elf/amd64/reloc.c
@@ -114,6 +114,11 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 {
 	const Elf_Rel *rellim;
 	const Elf_Rel *rel;
+	SymCache *cache;
+
+	cache = (SymCache *)alloca(obj->nchains * sizeof(SymCache));
+	if (cache != NULL)
+	    memset(cache, 0, obj->nchains * sizeof(SymCache));
 
 	rellim = (const Elf_Rel *) ((caddr_t) obj->rel + obj->relsize);
 	for (rel = obj->rel;  rel < rellim;  rel++) {
@@ -130,7 +135,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -149,7 +154,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -179,7 +184,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -238,7 +243,7 @@ reloc_jmpslots(Obj_Entry *obj)
 
 	assert(ELF_R_TYPE(rel->r_info) == R_386_JMP_SLOT);
 	where = (Elf_Addr *)(obj->relocbase + rel->r_offset);
-	def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true);
+	def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true, NULL);
 	if (def == NULL)
 	    return -1;
 	reloc_jmpslot(where, (Elf_Addr)(defobj->relocbase + def->st_value));
diff --git a/libexec/rtld-elf/i386/reloc.c b/libexec/rtld-elf/i386/reloc.c
index 360733a..aff70b0 100644
--- a/libexec/rtld-elf/i386/reloc.c
+++ b/libexec/rtld-elf/i386/reloc.c
@@ -114,6 +114,11 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 {
 	const Elf_Rel *rellim;
 	const Elf_Rel *rel;
+	SymCache *cache;
+
+	cache = (SymCache *)alloca(obj->nchains * sizeof(SymCache));
+	if (cache != NULL)
+	    memset(cache, 0, obj->nchains * sizeof(SymCache));
 
 	rellim = (const Elf_Rel *) ((caddr_t) obj->rel + obj->relsize);
 	for (rel = obj->rel;  rel < rellim;  rel++) {
@@ -130,7 +135,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -149,7 +154,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -179,7 +184,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry *obj_rtld)
 		    const Obj_Entry *defobj;
 
 		    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj,
-		      false);
+		      false, cache);
 		    if (def == NULL)
 			return -1;
 
@@ -238,7 +243,7 @@ reloc_jmpslots(Obj_Entry *obj)
 
 	assert(ELF_R_TYPE(rel->r_info) == R_386_JMP_SLOT);
 	where = (Elf_Addr *)(obj->relocbase + rel->r_offset);
-	def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true);
+	def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true, NULL);
 	if (def == NULL)
 	    return -1;
 	reloc_jmpslot(where, (Elf_Addr)(defobj->relocbase + def->st_value));
diff --git a/libexec/rtld-elf/rtld.c b/libexec/rtld-elf/rtld.c
index 0cffa74..4e907f3 100644
--- a/libexec/rtld-elf/rtld.c
+++ b/libexec/rtld-elf/rtld.c
@@ -427,7 +427,7 @@ _rtld_bind(Obj_Entry *obj, Elf_Word reloff)
 	rel = (const Elf_Rel *) ((caddr_t) obj->pltrela + reloff);
 
     where = (Elf_Addr *) (obj->relocbase + rel->r_offset);
-    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true);
+    def = find_symdef(ELF_R_SYM(rel->r_info), obj, &defobj, true, NULL);
     if (def == NULL)
 	die();
 
@@ -821,7 +821,7 @@ find_library(const char *name, const Obj_Entry *refobj)
  */
 const Elf_Sym *
 find_symdef(unsigned long symnum, const Obj_Entry *refobj,
-    const Obj_Entry **defobj_out, bool in_plt)
+    const Obj_Entry **defobj_out, bool in_plt, SymCache *cache)
 {
     const Elf_Sym *ref;
     const Elf_Sym *def;
@@ -829,6 +829,17 @@ find_symdef(unsigned long symnum, const Obj_Entry *refobj,
     const char *name;
     unsigned long hash;
 
+    /*
+     * If we have already found this symbol, get the information from
+     * the cache.
+     */
+    if (symnum >= refobj->nchains)
+	return NULL;	/* Bad object */
+    if (cache != NULL && cache[symnum].sym != NULL) {
+	*defobj_out = cache[symnum].obj;
+	return cache[symnum].sym;
+    }
+
     ref = refobj->symtab + symnum;
     name = refobj->strtab + ref->st_name;
     hash = elf_hash(name);
@@ -845,9 +856,14 @@ find_symdef(unsigned long symnum, const Obj_Entry *refobj,
 	defobj = obj_main;
     }
 
-    if (def != NULL)
+    if (def != NULL) {
 	*defobj_out = defobj;
-    else
+	/* Record the information in the cache to avoid subsequent lookups. */
+	if (cache != NULL) {
+	    cache[symnum].sym = def;
+	    cache[symnum].obj = defobj;
+	}
+    } else
 	_rtld_error("%s: Undefined symbol \"%s\"", refobj->path, name);
     return def;
 }
@@ -1926,7 +1942,7 @@ symlook_obj(const char *name, unsigned long hash, const Obj_Entry *obj,
 	    symp = obj->symtab + symnum;
 	    strp = obj->strtab + symp->st_name;
 
-	    if (strcmp(name, strp) == 0)
+	    if (name[0] == strp[0] && strcmp(name, strp) == 0)
 		return symp->st_shndx != SHN_UNDEF ||
 		  (!in_plt && symp->st_value != 0 &&
 		  ELF_ST_TYPE(symp->st_info) == STT_FUNC) ? symp : NULL;
diff --git a/libexec/rtld-elf/rtld.h b/libexec/rtld-elf/rtld.h
index 5ac7c12..3476826 100644
--- a/libexec/rtld-elf/rtld.h
+++ b/libexec/rtld-elf/rtld.h
@@ -166,6 +166,15 @@ typedef struct Struct_Obj_Entry {
 #define RTLD_MAGIC	0xd550b87a
 #define RTLD_VERSION	1
 
+/*
+ * Symbol cache entry used during relocation to avoid multiple lookups
+ * of the same symbol.
+ */
+typedef struct Struct_SymCache {
+    const Elf_Sym *sym;		/* Symbol table entry */
+    const Obj_Entry *obj;	/* Shared object which defines it */
+} SymCache;
+
 extern void _rtld_error(const char *, ...) __printflike(1, 2);
 extern Obj_Entry *map_object(int, const char *, const struct stat *);
 extern void *xcalloc(size_t);
@@ -179,7 +188,7 @@ extern Elf_Addr _GLOBAL_OFFSET_TABLE_[];
 int do_copy_relocations(Obj_Entry *);
 unsigned long elf_hash(const char *);
 const Elf_Sym *find_symdef(unsigned long, const Obj_Entry *,
-  const Obj_Entry **, bool);
+  const Obj_Entry **, bool, SymCache *);
 void init_pltgot(Obj_Entry *);
 void lockdflt_init(LockInfo *);
 void obj_free(Obj_Entry *);