Skip site navigation (1)Skip section navigation (2)
Date:      Mon, 30 Apr 2012 13:31:11 +0000 (UTC)
From:      Konstantin Belousov <kib@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r234841 - in head/libexec/rtld-elf: . amd64 arm i386 ia64 powerpc powerpc64 sparc64
Message-ID:  <201204301331.q3UDVBAB067832@svn.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: kib
Date: Mon Apr 30 13:31:10 2012
New Revision: 234841
URL: http://svn.freebsd.org/changeset/base/234841

Log:
  Add GNU hash support for rtld.
  
  Based on dragonflybsd support for GNU hash by John Marino <draco marino st>
  Reviewed by:	kan
  Tested by:	bapt
  MFC after:	2 weeks

Modified:
  head/libexec/rtld-elf/amd64/reloc.c
  head/libexec/rtld-elf/arm/reloc.c
  head/libexec/rtld-elf/i386/reloc.c
  head/libexec/rtld-elf/ia64/reloc.c
  head/libexec/rtld-elf/powerpc/reloc.c
  head/libexec/rtld-elf/powerpc64/reloc.c
  head/libexec/rtld-elf/rtld.c
  head/libexec/rtld-elf/rtld.h
  head/libexec/rtld-elf/sparc64/reloc.c

Modified: head/libexec/rtld-elf/amd64/reloc.c
==============================================================================
--- head/libexec/rtld-elf/amd64/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/amd64/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -132,7 +132,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	 * limited amounts of stack available so we cannot use alloca().
 	 */
 	if (obj != obj_rtld) {
-	    cache = calloc(obj->nchains, sizeof(SymCache));
+	    cache = calloc(obj->dynsymcount, sizeof(SymCache));
 	    /* No need to check for NULL here */
 	} else
 	    cache = NULL;

Modified: head/libexec/rtld-elf/arm/reloc.c
==============================================================================
--- head/libexec/rtld-elf/arm/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/arm/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -328,7 +328,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
  	 * The dynamic loader may be called from a thread, we have
 	 * limited amounts of stack available so we cannot use alloca().
 	 */
-	cache = calloc(obj->nchains, sizeof(SymCache));
+	cache = calloc(obj->dynsymcount, sizeof(SymCache));
 	/* No need to check for NULL here */
 
 	rellim = (const Elf_Rel *)((caddr_t)obj->rel + obj->relsize);

Modified: head/libexec/rtld-elf/i386/reloc.c
==============================================================================
--- head/libexec/rtld-elf/i386/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/i386/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -133,7 +133,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	 * limited amounts of stack available so we cannot use alloca().
 	 */
 	if (obj != obj_rtld) {
-	    cache = calloc(obj->nchains, sizeof(SymCache));
+	    cache = calloc(obj->dynsymcount, sizeof(SymCache));
 	    /* No need to check for NULL here */
 	} else
 	    cache = NULL;

Modified: head/libexec/rtld-elf/ia64/reloc.c
==============================================================================
--- head/libexec/rtld-elf/ia64/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/ia64/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -104,7 +104,7 @@ alloc_fptrs(Obj_Entry *obj, bool mapped)
 	struct fptr **fptrs;
 	size_t fbytes;
 
-	fbytes = obj->nchains * sizeof(struct fptr *);
+	fbytes = obj->dynsymcount * sizeof(struct fptr *);
 
 	/*
 	 * Avoid malloc, if requested. Happens when relocating
@@ -138,7 +138,7 @@ free_fptrs(Obj_Entry *obj, bool mapped)
 	if (fptrs == NULL)
 		return;
 
-	fbytes = obj->nchains * sizeof(struct fptr *);
+	fbytes = obj->dynsymcount * sizeof(struct fptr *);
 	if (mapped)
 		munmap(fptrs, fbytes);
 	else
@@ -348,7 +348,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	const Elf_Rela *relalim;
 	const Elf_Rela *rela;
 	SymCache *cache;
-	int bytes = obj->nchains * sizeof(SymCache);
+	int bytes = obj->dynsymcount * sizeof(SymCache);
 	int r = -1;
 
 	/*

Modified: head/libexec/rtld-elf/powerpc/reloc.c
==============================================================================
--- head/libexec/rtld-elf/powerpc/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/powerpc/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -299,7 +299,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	 * limited amounts of stack available so we cannot use alloca().
 	 */
 	if (obj != obj_rtld) {
-		cache = calloc(obj->nchains, sizeof(SymCache));
+		cache = calloc(obj->dynsymcount, sizeof(SymCache));
 		/* No need to check for NULL here */
 	} else
 		cache = NULL;

Modified: head/libexec/rtld-elf/powerpc64/reloc.c
==============================================================================
--- head/libexec/rtld-elf/powerpc64/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/powerpc64/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -287,7 +287,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	const Elf_Rela *relalim;
 	const Elf_Rela *rela;
 	SymCache *cache;
-	int bytes = obj->nchains * sizeof(SymCache);
+	int bytes = obj->dynsymcount * sizeof(SymCache);
 	int r = -1;
 
 	/*

Modified: head/libexec/rtld-elf/rtld.c
==============================================================================
--- head/libexec/rtld-elf/rtld.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/rtld.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -133,7 +133,8 @@ static int symlook_global(SymLook *, Don
 static void symlook_init_from_req(SymLook *, const SymLook *);
 static int symlook_list(SymLook *, const Objlist *, DoneList *);
 static int symlook_needed(SymLook *, const Needed_Entry *, DoneList *);
-static int symlook_obj1(SymLook *, const Obj_Entry *);
+static int symlook_obj1_sysv(SymLook *, const Obj_Entry *);
+static int symlook_obj1_gnu(SymLook *, const Obj_Entry *);
 static void trace_loaded_objects(Obj_Entry *);
 static void unlink_object(Obj_Entry *);
 static void unload_object(Obj_Entry *);
@@ -150,6 +151,7 @@ static int  object_match_name(const Obj_
 static void ld_utrace_log(int, void *, void *, size_t, int, const char *);
 static void rtld_fill_dl_phdr_info(const Obj_Entry *obj,
     struct dl_phdr_info *phdr_info);
+static uint32_t gnu_hash(const char *);
 static bool matched_symbol(SymLook *, const Obj_Entry *, Sym_Match_Result *,
     const unsigned long);
 
@@ -488,6 +490,9 @@ _rtld(Elf_Addr *sp, func_ptr_type *exit_
     }
 
     digest_dynamic(obj_main, 0);
+    dbg("%s valid_hash_sysv %d valid_hash_gnu %d dynsymcount %d",
+	obj_main->path, obj_main->valid_hash_sysv, obj_main->valid_hash_gnu,
+	obj_main->dynsymcount);
 
     linkmap_add(obj_main);
     linkmap_add(&obj_rtld);
@@ -825,6 +830,11 @@ digest_dynamic1(Obj_Entry *obj, int earl
     Needed_Entry **needed_tail = &obj->needed;
     Needed_Entry **needed_filtees_tail = &obj->needed_filtees;
     Needed_Entry **needed_aux_filtees_tail = &obj->needed_aux_filtees;
+    const Elf_Hashelt *hashtab;
+    const Elf32_Word *hashval;
+    Elf32_Word bkt, nmaskwords;
+    int bloom_size32;
+    bool nmw_power2;
     int plttype = DT_REL;
 
     *dyn_rpath = NULL;
@@ -914,12 +924,35 @@ digest_dynamic1(Obj_Entry *obj, int earl
 
 	case DT_HASH:
 	    {
-		const Elf_Hashelt *hashtab = (const Elf_Hashelt *)
-		  (obj->relocbase + dynp->d_un.d_ptr);
+		hashtab = (const Elf_Hashelt *)(obj->relocbase +
+		    dynp->d_un.d_ptr);
 		obj->nbuckets = hashtab[0];
 		obj->nchains = hashtab[1];
 		obj->buckets = hashtab + 2;
 		obj->chains = obj->buckets + obj->nbuckets;
+		obj->valid_hash_sysv = obj->nbuckets > 0 && obj->nchains > 0 &&
+		  obj->buckets != NULL;
+	    }
+	    break;
+
+	case DT_GNU_HASH:
+	    {
+		hashtab = (const Elf_Hashelt *)(obj->relocbase +
+		    dynp->d_un.d_ptr);
+		obj->nbuckets_gnu = hashtab[0];
+		obj->symndx_gnu = hashtab[1];
+		nmaskwords = hashtab[2];
+		bloom_size32 = (__ELF_WORD_SIZE / 32) * nmaskwords;
+		/* Number of bitmask words is required to be power of 2 */
+		nmw_power2 = ((nmaskwords & (nmaskwords - 1)) == 0);
+		obj->maskwords_bm_gnu = nmaskwords - 1;
+		obj->shift2_gnu = hashtab[3];
+		obj->bloom_gnu = (Elf_Addr *) (hashtab + 4);
+		obj->buckets_gnu = hashtab + 4 + bloom_size32;
+		obj->chain_zero_gnu = obj->buckets_gnu + obj->nbuckets_gnu -
+		  obj->symndx_gnu;
+		obj->valid_hash_gnu = nmw_power2 && obj->nbuckets_gnu > 0 &&
+		  obj->buckets_gnu != NULL;
 	    }
 	    break;
 
@@ -1096,6 +1129,22 @@ digest_dynamic1(Obj_Entry *obj, int earl
 	obj->pltrelasize = obj->pltrelsize;
 	obj->pltrelsize = 0;
     }
+
+    /* Determine size of dynsym table (equal to nchains of sysv hash) */
+    if (obj->valid_hash_sysv)
+	obj->dynsymcount = obj->nchains;
+    else if (obj->valid_hash_gnu) {
+	obj->dynsymcount = 0;
+	for (bkt = 0; bkt < obj->nbuckets_gnu; bkt++) {
+	    if (obj->buckets_gnu[bkt] == 0)
+		continue;
+	    hashval = &obj->chain_zero_gnu[obj->buckets_gnu[bkt]];
+	    do
+		obj->dynsymcount++;
+	    while ((*hashval++ & 1u) == 0);
+	}
+	obj->dynsymcount += obj->symndx_gnu;
+    }
 }
 
 static void
@@ -1312,6 +1361,22 @@ elf_hash(const char *name)
 }
 
 /*
+ * The GNU hash function is the Daniel J. Bernstein hash clipped to 32 bits
+ * unsigned in case it's implemented with a wider type.
+ */
+static uint32_t
+gnu_hash(const char *s)
+{
+	uint32_t h;
+	unsigned char c;
+
+	h = 5381;
+	for (c = *s; c != '\0'; c = *++s)
+		h = h * 33 + c;
+	return (h & 0xffffffff);
+}
+
+/*
  * Find the library with the given name, and return its full pathname.
  * The returned string is dynamically allocated.  Generates an error
  * message and returns NULL if the library cannot be found.
@@ -1387,7 +1452,7 @@ find_symdef(unsigned long symnum, const 
      * If we have already found this symbol, get the information from
      * the cache.
      */
-    if (symnum >= refobj->nchains)
+    if (symnum >= refobj->dynsymcount)
 	return NULL;	/* Bad object */
     if (cache != NULL && cache[symnum].sym != NULL) {
 	*defobj_out = cache[symnum].obj;
@@ -1885,6 +1950,8 @@ do_load_object(int fd, const char *name,
 	object_add_name(obj, name);
     obj->path = path;
     digest_dynamic(obj, 0);
+    dbg("%s valid_hash_sysv %d valid_hash_gnu %d dynsymcount %d", obj->path,
+	obj->valid_hash_sysv, obj->valid_hash_gnu, obj->dynsymcount);
     if (obj->z_noopen && (flags & (RTLD_LO_DLOPEN | RTLD_LO_TRACE)) ==
       RTLD_LO_DLOPEN) {
 	dbg("refusing to load non-loadable \"%s\"", obj->path);
@@ -2168,8 +2235,8 @@ relocate_objects(Obj_Entry *first, bool 
 	if (obj != rtldobj)
 	    dbg("relocating \"%s\"", obj->path);
 
-	if (obj->nbuckets == 0 || obj->nchains == 0 || obj->buckets == NULL ||
-	    obj->symtab == NULL || obj->strtab == NULL) {
+	if (obj->symtab == NULL || obj->strtab == NULL ||
+	  !(obj->valid_hash_sysv || obj->valid_hash_gnu)) {
 	    _rtld_error("%s: Shared object has no run-time symbol table",
 	      obj->path);
 	    return -1;
@@ -2841,7 +2908,7 @@ dladdr(const void *addr, Dl_info *info)
      * Walk the symbol list looking for the symbol whose address is
      * closest to the address sent in.
      */
-    for (symoffset = 0; symoffset < obj->nchains; symoffset++) {
+    for (symoffset = 0; symoffset < obj->dynsymcount; symoffset++) {
         def = obj->symtab + symoffset;
 
         /*
@@ -3412,7 +3479,15 @@ symlook_obj(SymLook *req, const Obj_Entr
     SymLook req1;
     int flags, res, mres;
 
-    mres = symlook_obj1(req, obj);
+    /*
+     * There is at least one valid hash at this point, and we prefer to use
+     * the faster GNU version if available.
+     */
+    if (obj->valid_hash_gnu)
+	mres = symlook_obj1_gnu(req, obj);
+    else
+	mres = symlook_obj1_sysv(req, obj);
+
     if (mres == 0) {
 	if (obj->needed_filtees != NULL) {
 	    flags = (req->flags & SYMLOOK_EARLY) ? RTLD_LO_EARLY : 0;
@@ -3553,8 +3628,13 @@ matched_symbol(SymLook *req, const Obj_E
 	return (true);
 }
 
+/*
+ * Search for symbol using SysV hash function.
+ * obj->buckets is known not to be NULL at this point; the test for this was
+ * performed with the obj->valid_hash_sysv assignment.
+ */
 static int
-symlook_obj1(SymLook *req, const Obj_Entry *obj)
+symlook_obj1_sysv(SymLook *req, const Obj_Entry *obj)
 {
 	unsigned long symnum;
 	Sym_Match_Result matchres;
@@ -3582,6 +3662,56 @@ symlook_obj1(SymLook *req, const Obj_Ent
 	return (ESRCH);
 }
 
+/* Search for symbol using GNU hash function */
+static int
+symlook_obj1_gnu(SymLook *req, const Obj_Entry *obj)
+{
+	Elf_Addr bloom_word;
+	const Elf32_Word *hashval;
+	Elf32_Word bucket;
+	Sym_Match_Result matchres;
+	unsigned int h1, h2;
+	unsigned long symnum;
+
+	matchres.sym_out = NULL;
+	matchres.vsymp = NULL;
+	matchres.vcount = 0;
+
+	/* Pick right bitmask word from Bloom filter array */
+	bloom_word = obj->bloom_gnu[(req->hash_gnu / __ELF_WORD_SIZE) &
+	    obj->maskwords_bm_gnu];
+
+	/* Calculate modulus word size of gnu hash and its derivative */
+	h1 = req->hash_gnu & (__ELF_WORD_SIZE - 1);
+	h2 = ((req->hash_gnu >> obj->shift2_gnu) & (__ELF_WORD_SIZE - 1));
+
+	/* Filter out the "definitely not in set" queries */
+	if (((bloom_word >> h1) & (bloom_word >> h2) & 1) == 0)
+		return (ESRCH);
+
+	/* Locate hash chain and corresponding value element*/
+	bucket = obj->buckets_gnu[req->hash_gnu % obj->nbuckets_gnu];
+	if (bucket == 0)
+		return (ESRCH);
+	hashval = &obj->chain_zero_gnu[bucket];
+	do {
+		if (((*hashval ^ req->hash_gnu) >> 1) == 0) {
+			symnum = hashval - obj->chain_zero_gnu;
+			if (matched_symbol(req, obj, &matchres, symnum)) {
+				req->sym_out = matchres.sym_out;
+				req->defobj_out = obj;
+				return (0);
+			}
+		}
+	} while ((*hashval++ & 1) == 0);
+	if (matchres.vcount == 1) {
+		req->sym_out = matchres.vsymp;
+		req->defobj_out = obj;
+		return (0);
+	}
+	return (ESRCH);
+}
+
 static void
 trace_loaded_objects(Obj_Entry *obj)
 {
@@ -4365,6 +4495,7 @@ symlook_init(SymLook *dst, const char *n
 	bzero(dst, sizeof(*dst));
 	dst->name = name;
 	dst->hash = elf_hash(name);
+	dst->hash_gnu = gnu_hash(name);
 }
 
 static void
@@ -4373,6 +4504,7 @@ symlook_init_from_req(SymLook *dst, cons
 
 	dst->name = src->name;
 	dst->hash = src->hash;
+	dst->hash_gnu = src->hash_gnu;
 	dst->ventry = src->ventry;
 	dst->flags = src->flags;
 	dst->defobj_out = NULL;

Modified: head/libexec/rtld-elf/rtld.h
==============================================================================
--- head/libexec/rtld-elf/rtld.h	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/rtld.h	Mon Apr 30 13:31:10 2012	(r234841)
@@ -210,7 +210,16 @@ typedef struct Struct_Obj_Entry {
     const Elf_Hashelt *buckets;	/* Hash table buckets array */
     unsigned long nbuckets;	/* Number of buckets */
     const Elf_Hashelt *chains;	/* Hash table chain array */
-    unsigned long nchains;	/* Number of chains */
+    unsigned long nchains;	/* Number of entries in chain array */
+
+    Elf32_Word nbuckets_gnu;		/* Number of GNU hash buckets*/
+    Elf32_Word symndx_gnu;		/* 1st accessible symbol on dynsym table */
+    Elf32_Word maskwords_bm_gnu;  	/* Bloom filter words - 1 (bitmask) */
+    Elf32_Word shift2_gnu;		/* Bloom filter shift count */
+    Elf32_Word dynsymcount;		/* Total entries in dynsym table */
+    Elf_Addr *bloom_gnu;		/* Bloom filter used by GNU hash func */
+    const Elf_Hashelt *buckets_gnu;	/* GNU hash table bucket array */
+    const Elf_Hashelt *chain_zero_gnu;	/* GNU hash table value array (Zeroed) */
 
     char *rpath;		/* Search path specified in object */
     Needed_Entry *needed;	/* Shared objects needed by this one (%) */
@@ -257,6 +266,8 @@ typedef struct Struct_Obj_Entry {
     bool irelative : 1;		/* Object has R_MACHDEP_IRELATIVE relocs */
     bool gnu_ifunc : 1;		/* Object has references to STT_GNU_IFUNC */
     bool crt_no_init : 1;	/* Object' crt does not call _init/_fini */
+    bool valid_hash_sysv : 1;	/* A valid System V hash hash tag is available */
+    bool valid_hash_gnu : 1;	/* A valid GNU hash tag is available */
 
     struct link_map linkmap;	/* For GDB and dlinfo() */
     Objlist dldags;		/* Object belongs to these dlopened DAGs (%) */
@@ -316,6 +327,7 @@ struct Struct_RtldLockState {
 typedef struct Struct_SymLook {
     const char *name;
     unsigned long hash;
+    uint32_t hash_gnu;
     const Ver_Entry *ventry;
     int flags;
     const Obj_Entry *defobj_out;

Modified: head/libexec/rtld-elf/sparc64/reloc.c
==============================================================================
--- head/libexec/rtld-elf/sparc64/reloc.c	Mon Apr 30 13:29:21 2012	(r234840)
+++ head/libexec/rtld-elf/sparc64/reloc.c	Mon Apr 30 13:31:10 2012	(r234841)
@@ -305,7 +305,7 @@ reloc_non_plt(Obj_Entry *obj, Obj_Entry 
 	 * limited amounts of stack available so we cannot use alloca().
 	 */
 	if (obj != obj_rtld) {
-		cache = calloc(obj->nchains, sizeof(SymCache));
+		cache = calloc(obj->dynsymcount, sizeof(SymCache));
 		/* No need to check for NULL here */
 	} else
 		cache = NULL;



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201204301331.q3UDVBAB067832>