Module Name: src
Committed By: kamil
Date: Sat Feb 29 04:23:05 UTC 2020
Modified Files:
src/libexec/ld.elf_so: reloc.c rtld.c rtld.h symbol.c
Log Message:
Implement and integrate GNU Hashing function
Define Elf_Hash struct that contains ELF/SYSV and GNU hash checksum.
Implement _rtld_gnu_hash() for DT_GNU_HASH.
Adapt existing code to compute all Elf_Hash types, instead of only
the ELF/SYSV one.
Rename _rtld_elf_hash() to _rtld_sysv_hash() to match the GNU toolchain
terminology.
_rtld_gnu_hash() uses Dan Bernstein's string hash function posted eons ago
on comp.lang.c.
To generate a diff of this commit:
cvs rdiff -u -r1.114 -r1.115 src/libexec/ld.elf_so/reloc.c
cvs rdiff -u -r1.201 -r1.202 src/libexec/ld.elf_so/rtld.c
cvs rdiff -u -r1.136 -r1.137 src/libexec/ld.elf_so/rtld.h
cvs rdiff -u -r1.70 -r1.71 src/libexec/ld.elf_so/symbol.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/libexec/ld.elf_so/reloc.c
diff -u src/libexec/ld.elf_so/reloc.c:1.114 src/libexec/ld.elf_so/reloc.c:1.115
--- src/libexec/ld.elf_so/reloc.c:1.114 Sun Dec 30 01:48:37 2018
+++ src/libexec/ld.elf_so/reloc.c Sat Feb 29 04:23:05 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: reloc.c,v 1.114 2018/12/30 01:48:37 christos Exp $ */
+/* $NetBSD: reloc.c,v 1.115 2020/02/29 04:23:05 kamil Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -39,7 +39,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: reloc.c,v 1.114 2018/12/30 01:48:37 christos Exp $");
+__RCSID("$NetBSD: reloc.c,v 1.115 2020/02/29 04:23:05 kamil Exp $");
#endif /* not lint */
#include <err.h>
@@ -67,12 +67,15 @@ _rtld_do_copy_relocation(const Obj_Entry
void *dstaddr = (void *)(dstobj->relocbase + rela->r_offset);
const Elf_Sym *dstsym = dstobj->symtab + ELF_R_SYM(rela->r_info);
const char *name = dstobj->strtab + dstsym->st_name;
- unsigned long hash = _rtld_elf_hash(name);
+ Elf_Hash hash;
size_t size = dstsym->st_size;
const void *srcaddr;
const Elf_Sym *srcsym = NULL;
Obj_Entry *srcobj;
+ hash.sysv = _rtld_sysv_hash(name);
+ hash.gnu = _rtld_gnu_hash(name);
+
if (__predict_false(size == 0)) {
#if defined(__powerpc__) && !defined(__LP64) /* PR port-macppc/47464 */
if (strcmp(name, "_SDA_BASE_") == 0
@@ -90,7 +93,7 @@ _rtld_do_copy_relocation(const Obj_Entry
}
for (srcobj = dstobj->next; srcobj != NULL; srcobj = srcobj->next) {
- srcsym = _rtld_symlook_obj(name, hash, srcobj, 0,
+ srcsym = _rtld_symlook_obj(name, &hash, srcobj, 0,
_rtld_fetch_ventry(dstobj, ELF_R_SYM(rela->r_info)));
if (srcsym != NULL)
break;
Index: src/libexec/ld.elf_so/rtld.c
diff -u src/libexec/ld.elf_so/rtld.c:1.201 src/libexec/ld.elf_so/rtld.c:1.202
--- src/libexec/ld.elf_so/rtld.c:1.201 Sun Dec 8 22:35:27 2019
+++ src/libexec/ld.elf_so/rtld.c Sat Feb 29 04:23:05 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.c,v 1.201 2019/12/08 22:35:27 uwe Exp $ */
+/* $NetBSD: rtld.c,v 1.202 2020/02/29 04:23:05 kamil Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: rtld.c,v 1.201 2019/12/08 22:35:27 uwe Exp $");
+__RCSID("$NetBSD: rtld.c,v 1.202 2020/02/29 04:23:05 kamil Exp $");
#endif /* not lint */
#include <sys/param.h>
@@ -1098,16 +1098,17 @@ dlopen(const char *name, int mode)
void *
_rtld_objmain_sym(const char *name)
{
- unsigned long hash;
+ Elf_Hash hash;
const Elf_Sym *def;
const Obj_Entry *obj;
DoneList donelist;
- hash = _rtld_elf_hash(name);
+ hash.sysv = _rtld_sysv_hash(name);
+ hash.gnu = _rtld_gnu_hash(name);
obj = _rtld_objmain;
_rtld_donelist_init(&donelist);
- def = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj, 0,
+ def = _rtld_symlook_list(name, &hash, &_rtld_list_main, &obj, 0,
NULL, &donelist);
if (def != NULL)
@@ -1142,7 +1143,7 @@ static void *
do_dlsym(void *handle, const char *name, const Ver_Entry *ventry, void *retaddr)
{
const Obj_Entry *obj;
- unsigned long hash;
+ Elf_Hash hash;
const Elf_Sym *def;
const Obj_Entry *defobj;
DoneList donelist;
@@ -1153,7 +1154,8 @@ do_dlsym(void *handle, const char *name,
lookup_mutex_enter();
- hash = _rtld_elf_hash(name);
+ hash.sysv = _rtld_sysv_hash(name);
+ hash.gnu = _rtld_gnu_hash(name);
def = NULL;
defobj = NULL;
@@ -1170,7 +1172,7 @@ do_dlsym(void *handle, const char *name,
switch ((intptr_t)handle) {
case (intptr_t)NULL: /* Just the caller's shared object. */
- def = _rtld_symlook_obj(name, hash, obj, flags, ventry);
+ def = _rtld_symlook_obj(name, &hash, obj, flags, ventry);
defobj = obj;
break;
@@ -1180,7 +1182,7 @@ do_dlsym(void *handle, const char *name,
case (intptr_t)RTLD_SELF: /* Caller included */
for (; obj; obj = obj->next) {
- if ((def = _rtld_symlook_obj(name, hash, obj,
+ if ((def = _rtld_symlook_obj(name, &hash, obj,
flags, ventry)) != NULL) {
defobj = obj;
break;
@@ -1194,7 +1196,7 @@ do_dlsym(void *handle, const char *name,
*/
if (!def || ELF_ST_BIND(def->st_info) == STB_WEAK) {
const Elf_Sym *symp = _rtld_symlook_obj(name,
- hash, &_rtld_objself, flags, ventry);
+ &hash, &_rtld_objself, flags, ventry);
if (symp != NULL) {
def = symp;
defobj = &_rtld_objself;
@@ -1203,7 +1205,7 @@ do_dlsym(void *handle, const char *name,
break;
case (intptr_t)RTLD_DEFAULT:
- def = _rtld_symlook_default(name, hash, obj, &defobj,
+ def = _rtld_symlook_default(name, &hash, obj, &defobj,
flags, ventry);
break;
@@ -1222,7 +1224,7 @@ do_dlsym(void *handle, const char *name,
if (obj->mainprog) {
/* Search main program and all libraries loaded by it */
- def = _rtld_symlook_list(name, hash, &_rtld_list_main,
+ def = _rtld_symlook_list(name, &hash, &_rtld_list_main,
&defobj, flags, ventry, &donelist);
} else {
Needed_Entry fake;
@@ -1234,7 +1236,7 @@ do_dlsym(void *handle, const char *name,
fake.name = 0;
_rtld_donelist_init(&depth);
- def = _rtld_symlook_needed(name, hash, &fake, &defobj,
+ def = _rtld_symlook_needed(name, &hash, &fake, &defobj,
flags, ventry, &donelist, &depth);
}
@@ -1301,7 +1303,7 @@ dlvsym(void *handle, const char *name, c
if (version != NULL) {
ver_entry.name = version;
ver_entry.file = NULL;
- ver_entry.hash = _rtld_elf_hash(version);
+ ver_entry.hash = _rtld_sysv_hash(version);
ver_entry.flags = 0;
ventry = &ver_entry;
}
Index: src/libexec/ld.elf_so/rtld.h
diff -u src/libexec/ld.elf_so/rtld.h:1.136 src/libexec/ld.elf_so/rtld.h:1.137
--- src/libexec/ld.elf_so/rtld.h:1.136 Sun Dec 30 01:48:37 2018
+++ src/libexec/ld.elf_so/rtld.h Sat Feb 29 04:23:05 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.h,v 1.136 2018/12/30 01:48:37 christos Exp $ */
+/* $NetBSD: rtld.h,v 1.137 2020/02/29 04:23:05 kamil Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -76,6 +76,11 @@ extern size_t _rtld_pagesz;
assert((dlp)->objs != NULL), \
(dlp)->num_used = 0)
+
+typedef struct Struct_Elf_Hash {
+ unsigned long sysv;
+ unsigned long gnu;
+} Elf_Hash;
#endif /* _RTLD_SOURCE */
/*
@@ -410,19 +415,20 @@ void _rtld_call_ifunc(Obj_Entry *, sigse
Obj_Entry *_rtld_load_library(const char *, const Obj_Entry *, int);
/* symbol.c */
-unsigned long _rtld_elf_hash(const char *);
-const Elf_Sym *_rtld_symlook_obj(const char *, unsigned long,
+unsigned long _rtld_sysv_hash(const char *);
+unsigned long _rtld_gnu_hash(const char *);
+const Elf_Sym *_rtld_symlook_obj(const char *, Elf_Hash *,
const Obj_Entry *, u_int, const Ver_Entry *);
const Elf_Sym *_rtld_find_symdef(unsigned long, const Obj_Entry *,
const Obj_Entry **, u_int);
const Elf_Sym *_rtld_find_plt_symdef(unsigned long, const Obj_Entry *,
const Obj_Entry **, bool);
-const Elf_Sym *_rtld_symlook_list(const char *, unsigned long,
+const Elf_Sym *_rtld_symlook_list(const char *, Elf_Hash *,
const Objlist *, const Obj_Entry **, u_int, const Ver_Entry *, DoneList *);
-const Elf_Sym *_rtld_symlook_default(const char *, unsigned long,
+const Elf_Sym *_rtld_symlook_default(const char *, Elf_Hash *,
const Obj_Entry *, const Obj_Entry **, u_int, const Ver_Entry *);
-const Elf_Sym *_rtld_symlook_needed(const char *, unsigned long,
+const Elf_Sym *_rtld_symlook_needed(const char *, Elf_Hash *,
const Needed_Entry *, const Obj_Entry **, u_int, const Ver_Entry *,
DoneList *, DoneList *);
Index: src/libexec/ld.elf_so/symbol.c
diff -u src/libexec/ld.elf_so/symbol.c:1.70 src/libexec/ld.elf_so/symbol.c:1.71
--- src/libexec/ld.elf_so/symbol.c:1.70 Sat Feb 29 04:21:42 2020
+++ src/libexec/ld.elf_so/symbol.c Sat Feb 29 04:23:05 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: symbol.c,v 1.70 2020/02/29 04:21:42 kamil Exp $ */
+/* $NetBSD: symbol.c,v 1.71 2020/02/29 04:23:05 kamil Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: symbol.c,v 1.70 2020/02/29 04:21:42 kamil Exp $");
+__RCSID("$NetBSD: symbol.c,v 1.71 2020/02/29 04:23:05 kamil Exp $");
#endif /* not lint */
#include <err.h>
@@ -85,7 +85,7 @@ _rtld_donelist_check(DoneList *dlp, cons
* this. It is specified by the System V ABI.
*/
unsigned long
-_rtld_elf_hash(const char *name)
+_rtld_sysv_hash(const char *name)
{
const unsigned char *p = (const unsigned char *) name;
unsigned long h = 0;
@@ -103,8 +103,24 @@ _rtld_elf_hash(const char *name)
return (h);
}
+/*
+ * Hash function for symbol table lookup. Don't even think about changing
+ * this. It is specified by the GNU toolchain ABI.
+ */
+unsigned long
+_rtld_gnu_hash(const char *name)
+{
+ const unsigned char *p = (const unsigned char *) name;
+ uint_fast32_t h = 5381;
+ unsigned char c;
+
+ for (c = *p; c != '\0'; c = *++p)
+ h = h * 33 + c;
+ return (unsigned long)h;
+}
+
const Elf_Sym *
-_rtld_symlook_list(const char *name, unsigned long hash, const Objlist *objlist,
+_rtld_symlook_list(const char *name, Elf_Hash *hash, const Objlist *objlist,
const Obj_Entry **defobj_out, u_int flags, const Ver_Entry *ventry,
DoneList *dlp)
{
@@ -142,7 +158,7 @@ _rtld_symlook_list(const char *name, uns
* to the symbol, or NULL if no definition was found.
*/
const Elf_Sym *
-_rtld_symlook_needed(const char *name, unsigned long hash,
+_rtld_symlook_needed(const char *name, Elf_Hash *hash,
const Needed_Entry *needed, const Obj_Entry **defobj_out, u_int flags,
const Ver_Entry *ventry, DoneList *breadth, DoneList *depth)
{
@@ -315,14 +331,14 @@ _rtld_symlook_obj_matched_symbol(const c
* eliminates many recomputations of the hash value.
*/
const Elf_Sym *
-_rtld_symlook_obj(const char *name, unsigned long hash,
+_rtld_symlook_obj(const char *name, Elf_Hash *hash,
const Obj_Entry *obj, u_int flags, const Ver_Entry *ventry)
{
unsigned long symnum;
const Elf_Sym *vsymp = NULL;
int vcount = 0;
- for (symnum = obj->buckets[fast_remainder32(hash, obj->nbuckets,
+ for (symnum = obj->buckets[fast_remainder32(hash->sysv, obj->nbuckets,
obj->nbuckets_m, obj->nbuckets_s1, obj->nbuckets_s2)];
symnum != ELF_SYM_UNDEFINED;
symnum = obj->chains[symnum]) {
@@ -352,7 +368,7 @@ _rtld_find_symdef(unsigned long symnum,
const Elf_Sym *def;
const Obj_Entry *defobj;
const char *name;
- unsigned long hash;
+ Elf_Hash hash;
ref = refobj->symtab + symnum;
name = refobj->strtab + ref->st_name;
@@ -368,9 +384,10 @@ _rtld_find_symdef(unsigned long symnum,
refobj->path, symnum);
}
- hash = _rtld_elf_hash(name);
+ hash.sysv = _rtld_sysv_hash(name);
+ hash.gnu = _rtld_gnu_hash(name);
defobj = NULL;
- def = _rtld_symlook_default(name, hash, refobj, &defobj, flags,
+ def = _rtld_symlook_default(name, &hash, refobj, &defobj, flags,
_rtld_fetch_ventry(refobj, symnum));
} else {
rdbg(("STB_LOCAL symbol %s in %s", name, refobj->path));
@@ -430,7 +447,7 @@ _rtld_find_plt_symdef(unsigned long symn
* defining object via the reference parameter DEFOBJ_OUT.
*/
const Elf_Sym *
-_rtld_symlook_default(const char *name, unsigned long hash,
+_rtld_symlook_default(const char *name, Elf_Hash *hash,
const Obj_Entry *refobj, const Obj_Entry **defobj_out, u_int flags,
const Ver_Entry *ventry)
{
