Implement support for DT_GNU_HASH, taking all the interesting bits

from Matt Dillon's implementation in DragonFlyBSD commit 7629c631.
One difference is that as long as DT_HASH is still present, ld.so
will use that to get the total number of symbols rather than walking
the GNU hash chains.  Note that the GPLv2 binutils we have doesn't
support DT_GNU_HASH, so this only helps archs were lld is used.

ok kettenis@ mpi@

2 files changed, 136 insertions, 21 deletions

diff --git a/libexec/ld.so/resolve.c b/libexec/ld.so/resolve.c
index e1df6956e4b..c1f9eddfb44 100644
--- a/libexec/ld.so/resolve.c
+++ b/libexec/ld.so/resolve.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.c,v 1.86 2018/11/16 21:15:47 guenther Exp $ */
+/*	$OpenBSD: resolve.c,v 1.87 2018/11/28 03:18:00 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -50,6 +50,7 @@ struct symlookup {
 	const elf_object_t	*sl_weak_obj_out;
 	const Elf_Sym		*sl_weak_sym_out;
 	unsigned long		sl_elf_hash;
+	uint32_t		sl_gnu_hash;
 	int			sl_flags;
 };
 
@@ -261,6 +262,7 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
     int phdrc, const int objtype, const long lbase, const long obase)
 {
 	elf_object_t *object;
+	Elf_Addr gnu_hash = 0;
 
 #if 0
 	_dl_printf("objname [%s], dynp %p, objtype %x lbase %lx, obase %lx\n",
@@ -302,6 +304,8 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
 			object->relacount = dynp->d_un.d_val;
 		if (dynp->d_tag == DT_RELCOUNT)
 			object->relcount = dynp->d_un.d_val;
+		if (dynp->d_tag == DT_GNU_HASH)
+			gnu_hash = dynp->d_un.d_val;
 		dynp++;
 	}
 	DL_DEB((" flags %s = 0x%x\n", objname, object->obj_flags ));
@@ -329,8 +333,6 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
 	 */
 	if (object->Dyn.info[DT_PLTGOT])
 		object->Dyn.info[DT_PLTGOT] += obase;
-	if (object->Dyn.info[DT_HASH])
-		object->Dyn.info[DT_HASH] += obase;
 	if (object->Dyn.info[DT_STRTAB])
 		object->Dyn.info[DT_STRTAB] += obase;
 	if (object->Dyn.info[DT_SYMTAB])
@@ -358,13 +360,59 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
 	if (object->Dyn.info[DT_PREINIT_ARRAY])
 		object->Dyn.info[DT_PREINIT_ARRAY] += obase;
 
+	if (gnu_hash) {
+		Elf32_Word *hashtab = (Elf32_Word *)(gnu_hash + obase);
+		Elf32_Word nbuckets = hashtab[0];
+		Elf32_Word nmaskwords = hashtab[2];
+
+		/* validity check */
+		if (nbuckets > 0 && (nmaskwords & (nmaskwords - 1)) == 0) {
+			Elf32_Word symndx = hashtab[1];
+			int bloom_size32 = (ELFSIZE / 32) * nmaskwords;
+
+			object->nbuckets = nbuckets;
+			object->symndx_gnu = symndx;
+			object->mask_bm_gnu = nmaskwords - 1;
+			object->shift2_gnu = hashtab[3];
+			object->bloom_gnu = (Elf_Addr *)(hashtab + 4);
+			object->buckets_gnu = hashtab + 4 + bloom_size32;
+			object->chains_gnu = object->buckets_gnu + nbuckets
+			    - symndx;
+
+			/*
+			 * If the ELF hash is present, get the total symbol
+			 * count ("nchains") from there.  Otherwise, count
+			 * the entries in the GNU hash chain.
+			 */
+			if (object->Dyn.info[DT_HASH] == 0) {
+				Elf32_Word n;
+
+				for (n = 0; n < nbuckets; n++) {
+					Elf_Word bkt = object->buckets_gnu[n];
+					const Elf32_Word *hashval;
+					if (bkt == 0)
+						continue;
+					hashval = &object->chains_gnu[bkt];
+					do {
+						symndx++;
+					} while ((*hashval++ & 1U) == 0);
+				}
+				object->nchains = symndx;
+			}
+			object->status |= STAT_GNU_HASH;
+		}
+	}
 	if (object->Dyn.info[DT_HASH] != 0) {
-		Elf_Word *hashtab = (Elf_Word *)object->Dyn.info[DT_HASH];
+		Elf_Word *hashtab = (Elf_Word *)(object->Dyn.info[DT_HASH]
+		    + obase);
 
-		object->nbuckets = hashtab[0];
 		object->nchains = hashtab[1];
-		object->buckets = hashtab + 2;
-		object->chains = object->buckets + object->nbuckets;
+		if (object->nbuckets == 0) {
+			object->nbuckets = hashtab[0];
+			object->buckets_elf = hashtab + 2;
+			object->chains_elf = object->buckets_elf +
+			    object->nbuckets;
+		}
 	}
 
 	object->phdrp = phdrp;
@@ -579,15 +627,53 @@ static int
 _dl_find_symbol_obj(elf_object_t *obj, struct symlookup *sl)
 {
 	const Elf_Sym	*symt = obj->dyn.symtab;
-	long	si;
 
-	for (si = obj->buckets[sl->sl_elf_hash % obj->nbuckets];
-	    si != STN_UNDEF; si = obj->chains[si]) {
-		const Elf_Sym *sym = symt + si;
+	if (obj->status & STAT_GNU_HASH) {
+		uint32_t hash = sl->sl_gnu_hash;
+		Elf_Addr bloom_word;
+		unsigned int h1;
+		unsigned int h2;
+		Elf32_Word bucket;
+		const Elf32_Word *hashval;
+
+		/* pick right bitmask word from Bloom filter array */
+		bloom_word = obj->bloom_gnu[(hash / ELFSIZE) &
+		    obj->mask_bm_gnu];
+
+		/* calculate modulus ELFSIZE of gnu hash and its derivative */
+		h1 = hash & (ELFSIZE - 1);
+		h2 = (hash >> obj->shift2_gnu) & (ELFSIZE - 1);
 
-		int r = matched_symbol(obj, sym, sl);
-		if (r)
-			return r > 0;
+		/* Filter out the "definitely not in set" queries */
+		if (((bloom_word >> h1) & (bloom_word >> h2) & 1) == 0)
+			return 0;
+
+		/* Locate hash chain and corresponding value element */
+		bucket = obj->buckets_gnu[hash % obj->nbuckets];
+		if (bucket == 0)
+			return 0;
+		hashval = &obj->chains_gnu[bucket];
+		do {
+			if (((*hashval ^ hash) >> 1) == 0) {
+				const Elf_Sym *sym = symt +
+				    (hashval - obj->chains_gnu);
+				
+				int r = matched_symbol(obj, sym, sl);
+				if (r)
+					return r > 0;
+			}
+		} while ((*hashval++ & 1U) == 0);
+	} else {
+		Elf_Word si;
+
+		for (si = obj->buckets_elf[sl->sl_elf_hash % obj->nbuckets];
+		    si != STN_UNDEF; si = obj->chains_elf[si]) {
+			const Elf_Sym *sym = symt + si;
+
+			int r = matched_symbol(obj, sym, sl);
+			if (r)
+				return r > 0;
+		}
 	}
 	return 0;
 }
@@ -597,7 +683,8 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
     int flags, const Elf_Sym *ref_sym, elf_object_t *req_obj,
     const elf_object_t **pobj)
 {
-	const char *p = name;
+	const unsigned char *p;
+	unsigned char c;
 	struct dep_node *n, *m;
 	struct symlookup sl = {
 		.sl_name = name,
@@ -605,15 +692,18 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 		.sl_weak_obj_out = NULL,
 		.sl_weak_sym_out = NULL,
 		.sl_elf_hash = 0,
+		.sl_gnu_hash = 5381,
 		.sl_flags = flags,
 	};
 
-	while (*p) {
+	/* Calculate both hashes in one pass */
+	for (p = (const unsigned char *)name; (c = *p) != '\0'; p++) {
 		unsigned long g;
-		sl.sl_elf_hash = (sl.sl_elf_hash << 4) + *p++;
+		sl.sl_elf_hash = (sl.sl_elf_hash << 4) + c;
 		if ((g = sl.sl_elf_hash & 0xf0000000))
 			sl.sl_elf_hash ^= g >> 24;
 		sl.sl_elf_hash &= ~g;
+		sl.sl_gnu_hash = sl.sl_gnu_hash * 33 + c;
 	}
 
 	if (req_obj->dyn.symbolic)
diff --git a/libexec/ld.so/resolve.h b/libexec/ld.so/resolve.h
index ff0738dfa6a..b5c6629d889 100644
--- a/libexec/ld.so/resolve.h
+++ b/libexec/ld.so/resolve.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.h,v 1.86 2018/11/16 21:15:47 guenther Exp $ */
+/*	$OpenBSD: resolve.h,v 1.87 2018/11/28 03:18:00 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -119,6 +119,7 @@ struct elf_object {
 #define	STAT_UNLOADED	0x20
 #define	STAT_NODELETE	0x40
 #define	STAT_VISITED	0x80
+#define	STAT_GNU_HASH	0x100
 
 	Elf_Phdr	*phdrp;
 	int		phdrc;
@@ -130,10 +131,34 @@ struct elf_object {
 #define	OBJTYPE_DLO	4
 	int		obj_flags;	/* c.f. <sys/exec_elf.h> DF_1_* */
 
-	Elf_Word	*buckets;
+	/* shared by ELF and GNU hash */
 	u_int32_t	nbuckets;
-	Elf_Word	*chains;
-	u_int32_t	nchains;
+	u_int32_t	nchains;	/* really, number of symbols */
+	union {
+		struct {
+			/* specific to ELF hash */
+			const Elf_Word	*buckets;
+			const Elf_Word	*chains;
+		} u_elf;
+		struct {
+			/* specific to GNU hash */
+			const Elf32_Word	*buckets;
+			const Elf32_Word	*chains;
+			const Elf_Addr		*bloom;
+			Elf32_Word		mask_bm;
+			Elf32_Word		shift2;
+			Elf32_Word		symndx;
+		} u_gnu;
+	} hash_u;
+#define buckets_elf	hash_u.u_elf.buckets
+#define chains_elf	hash_u.u_elf.chains
+#define buckets_gnu	hash_u.u_gnu.buckets
+#define chains_gnu	hash_u.u_gnu.chains
+#define bloom_gnu	hash_u.u_gnu.bloom
+#define mask_bm_gnu	hash_u.u_gnu.mask_bm
+#define shift2_gnu	hash_u.u_gnu.shift2
+#define symndx_gnu	hash_u.u_gnu.symndx
+
 	Elf_Dyn		*dynamic;
 
 	TAILQ_HEAD(,dep_node)	child_list;	/* direct dep libs of object */