Added support for GNU hash style into dynamic linker

8 files changed, 247 insertions, 32 deletions

diff --git a/Rules.mak b/Rules.mak
index 0197fa338..1e7bdb85a 100644
--- a/Rules.mak
+++ b/Rules.mak
@@ -408,6 +408,16 @@ ifeq ($(UCLIBC_BUILD_NOW),y)
 LDFLAGS_NOSTRIP+=-Wl,-z,now
 endif
 
+ifeq ($(LDSO_GNU_HASH_SUPPORT),y)
+# Be sure that binutils support it
+LDFLAGS_GNUHASH :=$(call check_ld,--hash-style=gnu)
+ifeq ($(LDFLAGS_GNUHASH),)
+$(error Your binutils don't support --hash-style option, while you want to use it)
+else
+LDFLAGS_NOSTRIP += -Wl,$(LDFLAGS_GNUHASH)
+endif
+endif
+
 LDFLAGS:=$(LDFLAGS_NOSTRIP) -Wl,-z,defs
 ifeq ($(DODEBUG),y)
 #CFLAGS += -g3
diff --git a/extra/Configs/Config.in b/extra/Configs/Config.in
index 30b4a4c89..cc23a98ad 100644
--- a/extra/Configs/Config.in
+++ b/extra/Configs/Config.in
@@ -322,6 +322,21 @@ config UCLIBC_CTOR_DTOR
 	  or dtors and want your binaries to be as small as possible, then
 	  answer N.
 
+config LDSO_GNU_HASH_SUPPORT
+	bool "Enable GNU hash style support"
+	depends on HAVE_SHARED
+	default n
+	help
+	  Newest binutils support a new hash style named GNU-hash. The dynamic
+	  linker will use the new GNU-hash section (.gnu.hash) for symbol lookup 
+	  if present into the ELF binaries, otherwise it will use the old SysV 
+	  hash style (.hash). This ensures that it is completely backward compatible.
+	  Further, being the hash table implementation self-contained into each
+	  executable and shared libraries, objects with mixed hash style can
+	  peacefully coexist in the same process.
+	  
+	  If you want to use this new feature, answer Y  
+
 config HAS_NO_THREADS
 	bool
 	default n
diff --git a/include/elf.h b/include/elf.h
index 19805d7c9..eb298292f 100644
--- a/include/elf.h
+++ b/include/elf.h
@@ -431,6 +431,7 @@ typedef struct
 #define SHT_SYMTAB_SHNDX  18		/* Extended section indeces */
 #define	SHT_NUM		  19		/* Number of defined types.  */
 #define SHT_LOOS	  0x60000000	/* Start OS-specific */
+#define SHT_GNU_HASH	  0x6ffffff6	/* GNU-style hash table.  */
 #define SHT_GNU_LIBLIST	  0x6ffffff7	/* Prelink library list */
 #define SHT_CHECKSUM	  0x6ffffff8	/* Checksum for DSO content.  */
 #define SHT_LOSUNW	  0x6ffffffa	/* Sun-specific low bound.  */
@@ -813,6 +814,7 @@ typedef struct
    If any adjustment is made to the ELF object after it has been
    built these entries will need to be adjusted.  */
 #define DT_ADDRRNGLO	0x6ffffe00
+#define DT_GNU_HASH	0x6ffffef5	/* GNU-style hash table.  */
 #define DT_GNU_CONFLICT	0x6ffffef8	/* Start of conflict section */
 #define DT_GNU_LIBLIST	0x6ffffef9	/* Library list */
 #define DT_CONFIG	0x6ffffefa	/* Configuration information.  */
diff --git a/ldso/include/dl-elf.h b/ldso/include/dl-elf.h
index 9d8da0d13..3e418622d 100644
--- a/ldso/include/dl-elf.h
+++ b/ldso/include/dl-elf.h
@@ -84,8 +84,11 @@ extern void _dl_protect_relro (struct elf_resolve *l);
 #endif
 
 /* OS and/or GNU dynamic extensions */
-#define OS_NUM 1
-#define DT_RELCONT_IDX DT_NUM
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+# define OS_NUM 2 /* for DT_RELOCCOUNT and DT_GNU_HASH entries */
+#else
+# define OS_NUM 1 /* for DT_RELOCCOUNT entry */
+#endif
 
 #ifndef ARCH_DYNAMIC_INFO
   /* define in arch specific code, if needed */
@@ -93,6 +96,13 @@ extern void _dl_protect_relro (struct elf_resolve *l);
 #endif
 
 #define DYNAMIC_SIZE (DT_NUM+OS_NUM+ARCH_NUM)
+/* Keep ARCH specific entries into dynamic section at the end of the array */
+#define DT_RELCONT_IDX (DYNAMIC_SIZE - OS_NUM - ARCH_NUM)
+
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+/* GNU hash comes just after the relocation count */
+# define DT_GNU_HASH_IDX (DT_RELCONT_IDX + 1)
+#endif
 
 extern void _dl_parse_dynamic_info(ElfW(Dyn) *dpnt, unsigned long dynamic_info[],
                                    void *debug_addr, DL_LOADADDR_TYPE load_off);
@@ -131,6 +141,10 @@ void __dl_parse_dynamic_info(ElfW(Dyn) *dpnt, unsigned long dynamic_info[],
 			if (dpnt->d_tag == DT_FLAGS_1 &&
 			    (dpnt->d_un.d_val & DF_1_NOW))
 				dynamic_info[DT_BIND_NOW] = 1;
+#ifdef __LDSO_GNU_HASH_SUPPORT__				
+			if (dpnt->d_tag == DT_GNU_HASH)
+				dynamic_info[DT_GNU_HASH_IDX] = dpnt->d_un.d_ptr;
+#endif				
 		}
 #ifdef ARCH_DYNAMIC_INFO
 		else {
@@ -149,6 +163,9 @@ void __dl_parse_dynamic_info(ElfW(Dyn) *dpnt, unsigned long dynamic_info[],
 	ADJUST_DYN_INFO(DT_SYMTAB, load_off);
 	ADJUST_DYN_INFO(DT_RELOC_TABLE_ADDR, load_off);
 	ADJUST_DYN_INFO(DT_JMPREL, load_off);
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+	ADJUST_DYN_INFO(DT_GNU_HASH_IDX, load_off);
+#endif	
 #undef ADJUST_DYN_INFO
 }
 
diff --git a/ldso/include/dl-hash.h b/ldso/include/dl-hash.h
index c21094020..5239467c1 100644
--- a/ldso/include/dl-hash.h
+++ b/ldso/include/dl-hash.h
@@ -40,14 +40,39 @@ struct elf_resolve {
   unsigned short int init_flag;
   unsigned long rtld_flags; /* RTLD_GLOBAL, RTLD_NOW etc. */
   Elf_Symndx nbucket;
+  
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+  /* Data needed to support GNU hash style */
+  Elf32_Word l_gnu_bitmask_idxbits;
+  Elf32_Word l_gnu_shift;
+  const ElfW(Addr) *l_gnu_bitmask;
+
+  union
+  {
+    const Elf32_Word *l_gnu_chain_zero;
+    const Elf_Symndx *elf_buckets;
+  };
+#else
   Elf_Symndx *elf_buckets;
+#endif
+  
   struct init_fini_list *init_fini;
   struct init_fini_list *rtld_local; /* keep tack of RTLD_LOCAL libs in same group */
   /*
    * These are only used with ELF style shared libraries
    */
   Elf_Symndx nchain;
+
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+  union
+  {
+    const Elf32_Word *l_gnu_buckets;
+    const Elf_Symndx *chains;
+  };
+#else	
   Elf_Symndx *chains;
+#endif  
+  
   unsigned long dynamic_info[DYNAMIC_SIZE];
 
   unsigned long n_phent;
diff --git a/ldso/include/ldso.h b/ldso/include/ldso.h
index 40ac12a57..d96d137e9 100644
--- a/ldso/include/ldso.h
+++ b/ldso/include/ldso.h
@@ -66,9 +66,17 @@ extern int   _dl_debug_file;
 	_dl_dprintf(_dl_debug_file, "%s:%i: " fmt, __FUNCTION__, __LINE__, ## args);
 # define _dl_if_debug_dprint(fmt, args...) \
 	do { if (_dl_debug) __dl_debug_dprint(fmt, ## args); } while (0)
+# define _dl_assert(expr)						\
+	do {								\
+		if (!(expr)) {						\
+			__dl_debug_dprint("assert(%s)\n", #expr);	\
+			_dl_exit(45);					\
+		}							\
+	} while (0)
 #else
-# define _dl_debug_dprint(fmt, args...)
+# define __dl_debug_dprint(fmt, args...)
 # define _dl_if_debug_dprint(fmt, args...)
+# define _dl_assert(expr)
 # define _dl_debug_file 2
 #endif /* __SUPPORT_LD_DEBUG__ */
 
diff --git a/ldso/ldso/dl-hash.c b/ldso/ldso/dl-hash.c
index 2d5ecddbb..c85035ba8 100644
--- a/ldso/ldso/dl-hash.c
+++ b/ldso/ldso/dl-hash.c
@@ -53,6 +53,19 @@ struct dyn_elf *_dl_symbol_tables = NULL;
  */
 struct dyn_elf *_dl_handles = NULL;
 
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+/* This is the new hash function that is used by the ELF linker to generate the
+ * GNU hash table that each executable and library will have if --hash-style=[gnu,both]
+ * is passed to the linker. We need it to decode the GNU hash table.  */
+static inline Elf_Symndx _dl_gnu_hash (const unsigned char *name)
+{
+  unsigned long h = 5381;
+  unsigned char c;
+  for (c = *name; c != '\0'; c = *++name)
+    h = h * 33 + c;
+  return h & 0xffffffff;
+}
+#endif
 
 /* This is the hash function that is used by the ELF linker to generate the
  * hash table that each executable and library is required to have.  We need
@@ -108,6 +121,29 @@ struct elf_resolve *_dl_add_elf_hash_table(const char *libname,
 	tpnt->libname = _dl_strdup(libname);
 	tpnt->dynamic_addr = (ElfW(Dyn) *)dynamic_addr;
 	tpnt->libtype = loaded_file;
+	
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+	if (dynamic_info[DT_GNU_HASH_IDX] != 0) {
+			
+			Elf32_Word *hash32 = (Elf_Symndx*)dynamic_info[DT_GNU_HASH_IDX];
+						
+			tpnt->nbucket = *hash32++;
+			Elf32_Word symbias = *hash32++;
+			Elf32_Word bitmask_nwords = *hash32++;
+			/* Must be a power of two.  */
+			_dl_assert ((bitmask_nwords & (bitmask_nwords - 1)) == 0);
+			tpnt->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
+			tpnt->l_gnu_shift = *hash32++;
+
+			tpnt->l_gnu_bitmask = (ElfW(Addr) *) hash32;
+			hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
+
+			tpnt->l_gnu_buckets = hash32;
+			hash32 += tpnt->nbucket;
+			tpnt->l_gnu_chain_zero = hash32 - symbias;	 
+	} else
+	/* Fall using old SysV hash table if GNU hash is not present */
+#endif
 
 	if (dynamic_info[DT_HASH] != 0) {
 		hash_addr = (Elf_Symndx*)dynamic_info[DT_HASH];
@@ -124,22 +160,117 @@ struct elf_resolve *_dl_add_elf_hash_table(const char *libname,
 }
 
 
+/* Routine to check whether the symbol matches.  */
+static __attribute_noinline__ const ElfW(Sym) *
+check_match (const ElfW(Sym) *sym, char *strtab, const char* undef_name, int type_class) {
+
+		if (type_class & (sym->st_shndx == SHN_UNDEF))
+			/* undefined symbol itself */
+			return NULL;
+			
+		if (sym->st_value == 0)
+			/* No value */
+			return NULL;
+			
+		if (ELF_ST_TYPE(sym->st_info) > STT_FUNC
+			&& ELF_ST_TYPE(sym->st_info) != STT_COMMON)
+			/* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC
+			 * and STT_COMMON entries since these are no
+			 * code/data definitions
+			 */
+			return NULL;
+
+		if (_dl_strcmp(strtab + sym->st_name, undef_name) != 0)
+			return NULL;
+
+		/* This is the matching symbol */			
+		return sym;
+}
+
+
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+
+static __always_inline const ElfW(Sym) * 
+_dl_lookup_gnu_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash, 
+					const char* undef_name, int type_class) {
+
+	Elf_Symndx symidx;
+	const ElfW(Sym) *sym;
+	char *strtab;
+	
+	const ElfW(Addr) *bitmask = tpnt->l_gnu_bitmask;
+
+	ElfW(Addr) bitmask_word	= bitmask[(hash / __ELF_NATIVE_CLASS) & tpnt->l_gnu_bitmask_idxbits];	
+
+	unsigned int hashbit1 = hash & (__ELF_NATIVE_CLASS - 1);
+	unsigned int hashbit2 = ((hash >> tpnt->l_gnu_shift) & (__ELF_NATIVE_CLASS - 1));
+
+	_dl_assert (bitmask != NULL);
+
+	if (unlikely((bitmask_word >> hashbit1) & (bitmask_word >> hashbit2) & 1)) {
+	
+		Elf32_Word bucket = tpnt->l_gnu_buckets[hash % tpnt->nbucket];
+		
+		if (bucket != 0) {
+			const Elf32_Word *hasharr = &tpnt->l_gnu_chain_zero[bucket];
+			do {
+				if (((*hasharr ^ hash) >> 1) == 0) {
+					symidx = hasharr - tpnt->l_gnu_chain_zero;
+					strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
+					sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
+					if (sym != NULL)
+						return sym;
+				}
+			} while ((*hasharr++ & 1u) == 0);
+		}
+	}
+	/* No symbol found.  */
+	return NULL;
+}
+#endif
+
+static __always_inline const ElfW(Sym) * 
+_dl_lookup_sysv_hash(struct elf_resolve *tpnt, ElfW(Sym) *symtab, unsigned long hash,  const char* undef_name, int type_class) {
+
+	unsigned long hn;
+	char *strtab;
+	const ElfW(Sym) *sym;
+	Elf_Symndx symidx;
+	
+	/* Avoid calling .urem here. */
+	do_rem(hn, hash, tpnt->nbucket);
+	strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
+	
+	_dl_assert(tpnt->elf_buckets != NULL);
+	
+	for (symidx = tpnt->elf_buckets[hn]; symidx != STN_UNDEF; symidx = tpnt->chains[symidx]) {
+		sym = check_match (&symtab[symidx], strtab, undef_name, type_class);
+		if (sym != NULL)
+			/* At this point the symbol is that we are looking for */
+			return sym;
+	}
+	/* No symbol found into the current module*/
+	return NULL;
+}	
+
 /*
  * This function resolves externals, and this is either called when we process
  * relocations or when we call an entry in the PLT table for the first time.
  */
 char *_dl_find_hash(const char *name, struct dyn_elf *rpnt, struct elf_resolve *mytpnt, int type_class)
 {
-	struct elf_resolve *tpnt;
-	int si;
-	char *strtab;
+	struct elf_resolve *tpnt = NULL;
 	ElfW(Sym) *symtab;
-	unsigned long elf_hash_number, hn;
-	const ElfW(Sym) *sym;
-	char *weak_result = NULL;
 
-	elf_hash_number = _dl_elf_hash((const unsigned char *)name);
+	unsigned long elf_hash_number = 0xffffffff;
+	const ElfW(Sym) *sym = NULL;
+
+	char *weak_result = NULL;
 
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+	unsigned long gnu_hash_number = _dl_gnu_hash((const unsigned char *)name);
+#endif
+	
 	for (; rpnt; rpnt = rpnt->next) {
 		tpnt = rpnt->dyn;
 
@@ -165,29 +296,32 @@ char *_dl_find_hash(const char *name, struct dyn_elf *rpnt, struct elf_resolve *
 		if (tpnt->nbucket == 0)
 			continue;
 
-		/* Avoid calling .urem here. */
-		do_rem(hn, elf_hash_number, tpnt->nbucket);
-		symtab = (ElfW(Sym) *) tpnt->dynamic_info[DT_SYMTAB];
-		strtab = (char *) (tpnt->dynamic_info[DT_STRTAB]);
-
-		for (si = tpnt->elf_buckets[hn]; si != STN_UNDEF; si = tpnt->chains[si]) {
-			sym = &symtab[si];
+		symtab = (ElfW(Sym) *) (intptr_t) (tpnt->dynamic_info[DT_SYMTAB]);              
+               
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+		/* Prefer GNU hash style, if any */
+		if(tpnt->l_gnu_bitmask) {
+			if((sym = _dl_lookup_gnu_hash(tpnt, symtab, gnu_hash_number, name, type_class)) != NULL)
+			/* If sym has been found, do not search further */
+			break;                  
+		} else {
+#endif        
+		/* Use the old SysV-style hash table */
+		
+		/* Calculate the old sysv hash number only once */
+		if(elf_hash_number == 0xffffffff)       
+			elf_hash_number = _dl_elf_hash((const unsigned char *)name);
 
-			if (type_class & (sym->st_shndx == SHN_UNDEF))
-				continue;
-			if (sym->st_value == 0)
-				continue;
-			if (ELF_ST_TYPE(sym->st_info) > STT_FUNC
-			&& ELF_ST_TYPE(sym->st_info) != STT_COMMON)
-			/* Ignore all but STT_NOTYPE, STT_OBJECT, STT_FUNC
-		 	 * and STT_COMMON entries since these are no
-			 * code/data definitions
-			 */
-				continue;
-			if (_dl_strcmp(strtab + sym->st_name, name) != 0)
-				continue;
+		if((sym = _dl_lookup_sysv_hash(tpnt, symtab, elf_hash_number, name, type_class)) != NULL )
+			break;
+#ifdef __LDSO_GNU_HASH_SUPPORT__                      
+		}
+#endif                
+	} /* end of for (; rpnt; rpnt = rpnt->next) { */
 
-			switch (ELF_ST_BIND(sym->st_info)) {
+	if(sym) {
+		/* At this point we have found the requested symbol, do binding */
+		switch (ELF_ST_BIND(sym->st_info)) {
 			case STB_WEAK:
 #if 0
 /* Perhaps we should support old style weak symbol handling
@@ -200,7 +334,6 @@ char *_dl_find_hash(const char *name, struct dyn_elf *rpnt, struct elf_resolve *
 				return (char*) DL_RELOC_ADDR(tpnt->loadaddr, sym->st_value);
 			default:	/* Local symbols not handled here */
 				break;
-			}
 		}
 	}
 	return weak_result;
diff --git a/test/Rules.mak b/test/Rules.mak
index ac210a72e..ce639778a 100644
--- a/test/Rules.mak
+++ b/test/Rules.mak
@@ -107,6 +107,11 @@ ifeq ($(findstring -static,$(LDFLAGS)),)
 	LDFLAGS += -Wl,--dynamic-linker,$(UCLIBC_LDSO_ABSPATH)/$(UCLIBC_LDSO)
 endif
 
+ifeq ($(LDSO_GNU_HASH_SUPPORT),y)
+# Check for binutils support is done on root Rules.mak
+LDFLAGS += -Wl,${LDFLAGS_GNUHASH}
+endif
+
 
 # Filter output
 MAKEFLAGS += --no-print-directory