From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/1705 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: ldso : dladdr support Date: Thu, 23 Aug 2012 18:21:13 -0400 Message-ID: <20120823222113.GT27715@brightrain.aerifal.cx> References: <20120808115202.GL30810@port70.net> <5022703B.3090105@gmail.com> <20120811230536.GQ27715@brightrain.aerifal.cx> <20120817053934.GS27715@brightrain.aerifal.cx> <50311776.9040802@gmail.com> <20120820020626.GD27715@brightrain.aerifal.cx> <503233A8.8000604@gmail.com> <50324A60.7040206@gmail.com> <20120823213937.GS27715@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="fwqqG+mf3f7vyBCB" X-Trace: ger.gmane.org 1345760382 4730 80.91.229.3 (23 Aug 2012 22:19:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 23 Aug 2012 22:19:42 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-1706-gllmg-musl=m.gmane.org@lists.openwall.com Fri Aug 24 00:19:42 2012 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1T4fka-0003g1-Vs for gllmg-musl@plane.gmane.org; Fri, 24 Aug 2012 00:19:41 +0200 Original-Received: (qmail 20423 invoked by uid 550); 23 Aug 2012 22:19:39 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 20415 invoked from network); 23 Aug 2012 22:19:38 -0000 Content-Disposition: inline In-Reply-To: <20120823213937.GS27715@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:1705 Archived-At: --fwqqG+mf3f7vyBCB Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Thu, Aug 23, 2012 at 05:39:37PM -0400, Rich Felker wrote: > On Mon, Aug 20, 2012 at 04:32:00PM +0200, musl wrote: > > I missed a bug in my previous patch : > > in find_sym func precomptab was always set to sysv_precomp. > > It's still broken; h is being used in the comparisons even if h was > not initialized, rather than using gh. I'm working on integrating the > code right now. I'll either commit my version or reply with a patch > here soon for review. Here's my proposed patch for gnu hash support. I've left dladdr to be committed separately. I handled the precomputed hashes by duplicating the code in the two branches; this is _ugly_ but it's moderately faster, and I really don't like the performance impact of these checks to begin with, so I'd rather not make them even worse. Some other changes I've made since Boris's last version: - Prefer GNU hash if it's available. It's a lot faster even in single runs, and should make even more difference when data-locality issues come into play (resolving whole files rather than just a single dlsym call). - Omit bloom filter checks. It's not clear if they're beneficial on average in large programs, but for single lookups where the symbol is present, they increase lookup time by about 8%. - Replace the over-complicated decode_vec2 with search_vec, since we only need a single extended entry anyway. In any case, the big-O performance of high-entry lookups will always be the same as this linear search unless we use heavy data structures, so we might as well just do it this super-simple way. Comments welcome. I'll hold off on committing for a while in case I made any dumb mistakes. Rich --fwqqG+mf3f7vyBCB Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="gnuhash.diff" diff --git a/configure b/configure index 1e8b974..1105180 100755 --- a/configure +++ b/configure @@ -268,7 +268,7 @@ fi # Some patched GCC builds have these defaults messed up... tryflag CFLAGS_AUTO -fno-stack-protector -tryldflag LDFLAGS_AUTO -Wl,--hash-style=sysv +tryldflag LDFLAGS_AUTO -Wl,--hash-style=both # Disable dynamic linking if ld is broken and can't do -Bsymbolic-functions LDFLAGS_DUMMY= diff --git a/src/ldso/dynlink.c b/src/ldso/dynlink.c index 9692c6b..d7d6800 100644 --- a/src/ldso/dynlink.c +++ b/src/ldso/dynlink.c @@ -53,6 +53,7 @@ struct dso { int refcnt; Sym *syms; uint32_t *hashtab; + uint32_t *ghashtab; char *strings; unsigned char *map; size_t map_len; @@ -95,7 +96,15 @@ static void decode_vec(size_t *v, size_t *a, size_t cnt) } } -static uint32_t hash(const char *s0) +static int search_vec(size_t *v, size_t *r, size_t key) +{ + for (; v[0]!=key; v+=2) + if (!v[0]) return 0; + *r = v[1]; + return 1; +} + +static uint32_t sysv_hash(const char *s0) { const unsigned char *s = (void *)s0; uint_fast32_t h = 0; @@ -106,7 +115,16 @@ static uint32_t hash(const char *s0) return h & 0xfffffff; } -static Sym *lookup(const char *s, uint32_t h, struct dso *dso) +static uint32_t gnu_hash(const char *s0) +{ + const unsigned char *s = (void *)s0; + uint_fast32_t h = 5381; + for (; *s; s++) + h = h*33 + *s; + return h; +} + +static Sym *sysv_lookup(const char *s, uint32_t h, struct dso *dso) { size_t i; Sym *syms = dso->syms; @@ -119,20 +137,61 @@ static Sym *lookup(const char *s, uint32_t h, struct dso *dso) return 0; } +static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso) +{ + Sym *sym; + char *strings; + uint32_t *hashtab = dso->ghashtab; + uint32_t nbuckets = hashtab[0]; + uint32_t *buckets = hashtab + 4 + hashtab[2]*(sizeof(size_t)/4); + uint32_t h2; + uint32_t *hashval; + uint32_t n = buckets[h1 % nbuckets]; + + if (!n) return 0; + + strings = dso->strings; + sym = dso->syms + n; + hashval = buckets + nbuckets + (n - hashtab[1]); + + for (h1 |= 1; ; sym++) { + h2 = *hashval++; + if ((h1 == (h2|1)) && !strcmp(s, strings + sym->st_name)) + return sym; + if (h2 & 1) break; + } + + return 0; +} + #define OK_TYPES (1<ghashtab) { + gh = gnu_hash(s); + if (gh == 0xf9040207 && !strcmp(s, "dlopen")) rtld_used = 1; + if (gh == 0xf4dc4ae && !strcmp(s, "dlsym")) rtld_used = 1; + if (gh == 0x1f4039c9 && !strcmp(s, "__stack_chk_fail")) ssp_used = 1; + } else { + h = sysv_hash(s); + if (h == 0x6b366be && !strcmp(s, "dlopen")) rtld_used = 1; + if (h == 0x6b3afd && !strcmp(s, "dlsym")) rtld_used = 1; + if (h == 0x595a4cc && !strcmp(s, "__stack_chk_fail")) ssp_used = 1; + } for (; dso; dso=dso->next) { Sym *sym; if (!dso->global) continue; - sym = lookup(s, h, dso); + if (dso->ghashtab) { + if (!gh) gh = gnu_hash(s); + sym = gnu_lookup(s, gh, dso); + } else { + if (!h) h = sysv_hash(s); + sym = sysv_lookup(s, h, dso); + } if (sym && (!need_def || sym->st_shndx) && sym->st_value && (1<<(sym->st_info&0xf) & OK_TYPES) && (1<<(sym->st_info>>4) & OK_BINDS)) { @@ -325,8 +384,11 @@ static void decode_dyn(struct dso *p) size_t dyn[DYN_CNT] = {0}; decode_vec(p->dynv, dyn, DYN_CNT); p->syms = (void *)(p->base + dyn[DT_SYMTAB]); - p->hashtab = (void *)(p->base + dyn[DT_HASH]); p->strings = (void *)(p->base + dyn[DT_STRTAB]); + if (dyn[0]&(1<hashtab = (void *)(p->base + dyn[DT_HASH]); + if (search_vec(p->dynv, dyn, DT_GNU_HASH)) + p->ghashtab = (void *)(p->base + *dyn); } static struct dso *load_library(const char *name) @@ -788,7 +850,7 @@ end: static void *do_dlsym(struct dso *p, const char *s, void *ra) { size_t i; - uint32_t h; + uint32_t h = 0, gh = 0; Sym *sym; if (p == RTLD_NEXT) { for (p=head; p && (unsigned char *)ra-p->map>p->map_len; p=p->next); @@ -802,12 +864,23 @@ static void *do_dlsym(struct dso *p, const char *s, void *ra) if (!res) goto failed; return res; } - h = hash(s); - sym = lookup(s, h, p); + if (p->ghashtab) { + gh = gnu_hash(s); + sym = gnu_lookup(s, gh, p); + } else { + h = sysv_hash(s); + sym = sysv_lookup(s, h, p); + } if (sym && sym->st_value && (1<<(sym->st_info&0xf) & OK_TYPES)) return p->base + sym->st_value; if (p->deps) for (i=0; p->deps[i]; i++) { - sym = lookup(s, h, p->deps[i]); + if (p->deps[i]->ghashtab) { + if (!gh) gh = gnu_hash(s); + sym = gnu_lookup(s, h, p->deps[i]); + } else { + if (!h) h = sysv_hash(s); + sym = sysv_lookup(s, h, p->deps[i]); + } if (sym && sym->st_value && (1<<(sym->st_info&0xf) & OK_TYPES)) return p->deps[i]->base + sym->st_value; } --fwqqG+mf3f7vyBCB--