From 66a962ce675f3386156405c78fe7d7a1e6a852bb Mon Sep 17 00:00:00 2001 From: jdp Date: Sat, 5 May 2001 23:21:05 +0000 Subject: 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 --- libexec/rtld-elf/alpha/reloc.c | 15 +++++++++++---- libexec/rtld-elf/amd64/reloc.c | 13 +++++++++---- libexec/rtld-elf/i386/reloc.c | 13 +++++++++---- libexec/rtld-elf/rtld.c | 26 +++++++++++++++++++++----- libexec/rtld-elf/rtld.h | 11 ++++++++++- 5 files changed, 60 insertions(+), 18 deletions(-) (limited to 'libexec') 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 *); -- cgit v1.1