Carmelo AMOROSO wrote:
Hi All,
just to make you aware of I'm working (at STMicroelectronics)
to add the support for the GNU hash style into the dynamic linker.
A first implementation is working but needs to be reviewed,
and to be fully tested.
It is based on uclibc-nptl port for sh4 (www.stlinux.com).
Shortly I'll post a patch to add this support to the trunk,
as a first draft to share the implementation with the community.
Best regards,
Carmelo
_______________________________________________
uClibc mailing list
[email protected]
http://busybox.net/cgi-bin/mailman/listinfo/uclibc
Hi Folks,
as previously announced, the GNU hash support has been completed
and fully tested (at least on sh4 nptl port).
I successfully run all uClibc testsuite and LTP built with GNU hash only,
and all tests passed.
Further I've done tests with mixed shared objects (GNU ans SysV hash style),
being able to relocate both of them, this guarantees the ld.so to be
backward
compatible, without forcing to rebuild all shared libraries (even if
they lack of
the benefits of the GNU hash)
I'm glad to share this work with the uClibc community hoping to see
more development activities in the future.
This patch applies on latest svn trunk (r20164). I removed from this all TLS
changes :-(.
Actually I've not yet tested this on trunk, only on the nptl port.
Any comments/advice are welcome.
Kind regards,
Carmelo
* GNU hash support for uClibc dynamic linker *
Newest binutils ( > 2.17.50.0.2) 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.
Detailed changes description:
file: extra/Configs/Config.in
- Added a new config option LDSO_GNU_HASH_SUPPORT under
"General libraries settings"
file: include/elf.h
- Added DT_GNU_HASH and SHT_GNU_HASH macros
file: ldso/include/dl-elf.h
- Updated some macros to keep into account the new entry
into the ELF dynamic section
- Updated '_dl_parse_dynamic_info' to parse the GNU hash table
information
file: ldso/include/dl-hash.h
- Updated 'struct elf_resolve' adding new fields to support GNU hash
table and the new lookup algorithm based on "Bloom filter"
file: ldso/ldso/dl-hash.c
- Added 'dl_gnu_hash' to compute th GNU hash number
- Updated '_dl_add_elf_hash_table' to initialise 'struct elf_resolve'
fields
- Splitted '_dl_find_hash' into three helper functions
- '_dl_lookup_gnu_hash': implementing the new GNU lookup algorithm
- '_dl_lookup_sysv_hash': implementing the old SysV lookup algorithm
- 'check_match: implementing the symbol matching into the ELF symbol
table
file: Rules.make - test/Rules.mak
- Modified to add --hash-style=gnu to LDFLAGS if binutils support it
Signed-off-by: Carmelo Amoroso <[EMAIL PROTECTED]>
diff -Naupr uClibc-trunk/Rules.mak uClibc-trunk-st/Rules.mak
--- uClibc-trunk/Rules.mak 2007-09-24 20:42:10.000000000 +0200
+++ uClibc-trunk-st/Rules.mak 2007-10-03 08:47:02.708801000 +0200
@@ -404,7 +404,18 @@ ifeq ($(UCLIBC_BUILD_NOW),y)
LDFLAGS_NOSTRIP+=-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 += $(LDFLAGS_GNUHASH)
+endif
+endif
+
LDFLAGS:=$(LDFLAGS_NOSTRIP) -z defs
+
ifeq ($(DODEBUG),y)
#CFLAGS += -g3
CFLAGS += -O0 -g3
diff -Naupr uClibc-trunk/extra/Configs/Config.in
uClibc-trunk-st/extra/Configs/Config.in
--- uClibc-trunk/extra/Configs/Config.in 2007-09-24 20:42:07.000000000
+0200
+++ uClibc-trunk-st/extra/Configs/Config.in 2007-10-03 08:33:58.155155000
+0200
@@ -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 -Naupr uClibc-trunk/include/elf.h uClibc-trunk-st/include/elf.h
--- uClibc-trunk/include/elf.h 2006-11-17 19:27:02.000000000 +0100
+++ uClibc-trunk-st/include/elf.h 2007-10-03 08:35:30.295580000 +0200
@@ -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 -Naupr uClibc-trunk/ldso/include/dl-elf.h
uClibc-trunk-st/ldso/include/dl-elf.h
--- uClibc-trunk/ldso/include/dl-elf.h 2006-09-19 09:42:30.000000000 +0200
+++ uClibc-trunk-st/ldso/include/dl-elf.h 2007-10-03 08:38:17.706355000
+0200
@@ -84,8 +84,11 @@ extern void _dl_protect_relro (struct el
#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 el
#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) *
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) *
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 -Naupr uClibc-trunk/ldso/include/dl-hash.h
uClibc-trunk-st/ldso/include/dl-hash.h
--- uClibc-trunk/ldso/include/dl-hash.h 2006-09-29 11:38:52.000000000 +0200
+++ uClibc-trunk-st/ldso/include/dl-hash.h 2007-10-03 08:39:33.536710000
+0200
@@ -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 -Naupr uClibc-trunk/ldso/include/ldso.h uClibc-trunk-st/ldso/include/ldso.h
--- uClibc-trunk/ldso/include/ldso.h 2007-02-03 18:40:02.000000000 +0100
+++ uClibc-trunk-st/ldso/include/ldso.h 2007-10-03 08:59:32.042289000 +0200
@@ -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 -Naupr uClibc-trunk/ldso/ldso/dl-hash.c uClibc-trunk-st/ldso/ldso/dl-hash.c
--- uClibc-trunk/ldso/ldso/dl-hash.c 2007-09-29 07:39:15.000000000 +0200
+++ uClibc-trunk-st/ldso/ldso/dl-hash.c 2007-10-03 08:51:55.610166000 +0200
@@ -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_tab
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,115 @@ struct elf_resolve *_dl_add_elf_hash_tab
}
+/* 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)
+ /* Ignore all but STT_NOTYPE, STT_OBJECT and STT_FUNC
+ * 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 (__builtin_expect ((bitmask_word >> hashbit1) & (bitmask_word >>
hashbit2) & 1, 0)) {
+
+ 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;
@@ -160,29 +289,38 @@ char *_dl_find_hash(const char *name, st
/* Don't search the executable when resolving a copy reloc. */
if ((type_class & ELF_RTYPE_CLASS_COPY) && tpnt->libtype ==
elf_executable)
continue;
-
+
/* If the hash table is empty there is nothing to do here. */
if (tpnt->nbucket == 0)
continue;
+
+ 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((sym = _dl_lookup_sysv_hash(tpnt, symtab, elf_hash_number,
name, type_class)) != NULL )
+ break;
- /* 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];
-
- if (type_class & (sym->st_shndx == SHN_UNDEF))
- continue;
- if (_dl_strcmp(strtab + sym->st_name, name) != 0)
- continue;
- if (sym->st_value == 0)
- continue;
- if (ELF_ST_TYPE(sym->st_info) > STT_FUNC)
- continue;
-
- switch (ELF_ST_BIND(sym->st_info)) {
+#ifdef __LDSO_GNU_HASH_SUPPORT__
+ }
+#endif
+ } /* end of for (; rpnt; rpnt = rpnt->next) { */
+
+ 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
@@ -195,7 +333,6 @@ char *_dl_find_hash(const char *name, st
return (char*) DL_RELOC_ADDR(tpnt->loadaddr,
sym->st_value);
default: /* Local symbols not handled here */
break;
- }
}
}
return weak_result;
diff -Naupr uClibc-trunk/test/Rules.mak uClibc-trunk-st/test/Rules.mak
--- uClibc-trunk/test/Rules.mak 2007-03-06 06:51:41.000000000 +0100
+++ uClibc-trunk-st/test/Rules.mak 2007-10-03 08:50:44.709834000 +0200
@@ -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
_______________________________________________
uClibc mailing list
[email protected]
http://busybox.net/cgi-bin/mailman/listinfo/uclibc
