[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 24 Jun 2015 02:24:51 +0300
From: Alexander Monakov <amonakov@...ras.ru>
To: musl@...ts.openwall.com
Cc: Alexander Monakov <amonakov@...ras.ru>
Subject: [PATCH 1/5] dynlink.c: use bloom filter in gnu hash lookup
Introduce gnu_lookup_filtered and use it to speed up symbol lookups in
find_sym (do_dlsym is left as is, based on an expectation that frequently
dlsym queries will use a dlopen handle rather than RTLD_NEXT or RTLD_DEFAULT,
and will not need to look at more than one DSO). The size of the bloom filter
table minus 1, ghashmask, is stored in the dso struct together with the
hashtable pointer to reduce pointer chasing on the hot path.
---
src/ldso/dynlink.c | 30 ++++++++++++++++++++++++++----
1 file changed, 26 insertions(+), 4 deletions(-)
diff --git a/src/ldso/dynlink.c b/src/ldso/dynlink.c
index b77c6f6..fa91b39 100644
--- a/src/ldso/dynlink.c
+++ b/src/ldso/dynlink.c
@@ -54,6 +54,7 @@ struct dso {
Sym *syms;
uint32_t *hashtab;
uint32_t *ghashtab;
+ uint32_t ghashmask;
int16_t *versym;
char *strings;
unsigned char *map;
@@ -200,6 +201,19 @@ static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso)
return 0;
}
+static Sym *gnu_lookup_filtered(const char *s, uint32_t h1, struct dso *dso, uint32_t fofs, size_t fmask)
+{
+ uint32_t *hashtab = dso->ghashtab;
+ size_t *bloomwords = hashtab+4;
+ size_t f = bloomwords[fofs & dso->ghashmask];
+ if (!(f & fmask)) return 0;
+
+ f >>= (h1 >> hashtab[3]) % (8 * sizeof f);
+ if (!(f & 1)) return 0;
+
+ return gnu_lookup(s, h1, dso);
+}
+
#define OK_TYPES (1<<STT_NOTYPE | 1<<STT_OBJECT | 1<<STT_FUNC | 1<<STT_COMMON | 1<<STT_TLS)
#define OK_BINDS (1<<STB_GLOBAL | 1<<STB_WEAK | 1<<STB_GNU_UNIQUE)
@@ -209,14 +223,20 @@ static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso)
static struct symdef find_sym(struct dso *dso, const char *s, int need_def)
{
- uint32_t h = 0, gh = 0;
+ uint32_t h = 0, gh, gho;
+ size_t ghm = 0;
struct symdef def = {0};
for (; dso; dso=dso->next) {
Sym *sym;
if (!dso->global) continue;
if (dso->ghashtab) {
- if (!gh) gh = gnu_hash(s);
- sym = gnu_lookup(s, gh, dso);
+ if (!ghm) {
+ gh = gnu_hash(s);
+ int maskbits = 8 * sizeof ghm;
+ gho = gh / maskbits;
+ ghm = 1ul << gh % maskbits;
+ }
+ sym = gnu_lookup_filtered(s, gh, dso, gho, ghm);
} else {
if (!h) h = sysv_hash(s);
sym = sysv_lookup(s, h, dso);
@@ -682,8 +702,10 @@ static void decode_dyn(struct dso *p)
p->rpath_orig = (void *)(p->strings + dyn[DT_RPATH]);
if (dyn[0]&(1<<DT_RUNPATH))
p->rpath_orig = (void *)(p->strings + dyn[DT_RUNPATH]);
- if (search_vec(p->dynv, dyn, DT_GNU_HASH))
+ if (search_vec(p->dynv, dyn, DT_GNU_HASH)) {
p->ghashtab = (void *)(p->base + *dyn);
+ p->ghashmask = p->ghashtab[2]-1;
+ }
if (search_vec(p->dynv, dyn, DT_VERSYM))
p->versym = (void *)(p->base + *dyn);
}
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
