Re: ldso : dladdr support

[musl <b.brezillon.musl@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1806 bytes --]

On 26/08/2012 00:13, musl wrote:
> On 24/08/2012 20:38, Rich Felker wrote:
>> On Fri, Aug 24, 2012 at 09:29:29AM +0200, musl wrote:
>>> I tested it and it works well.
>> Is there anything I changed that you think might be better done a
>> different way?
>>
>>> My tests are based on small libs (with a small set of shared symbols).
>>> I mixed libs with gnu hash and sysv hash.
>>> Tried to resolve symbols via dlsym.
>>>
>>> Have you tested it on big libraries ?
>> No, just very minimal testing.
>>
>>> Do you want me to do some specific tests ?
>> Actually, the main thing I'm interested in is whether the bloom filter
>> is ever beneficial. I took it out trying to streamline the code and
>> shaved about 8% off the lookup time for symbols in the main program,
>> but I didn't investigate how the change affects symbols not found in
>> the first file searched. Would you be interested in running some tests
>> to determine if it might be useful to try adding it back?
>>
>> Since it seems to be working/non-broken right now, I'll probably go
>> ahead and commit soon unless you find a major problem I've overlooked.
>> Then we can work on improving it once it's in the repo.
> I executed your test program (gnuhash) with and without bloom filter test, and I get pretty much the same results in
> both cases if the symbol is defined.
> What compiler option did you use to compile gnuhash.c ?
>
> I also tried to search for a missing symbol and the version with bloom filter is 3% faster.
>
> I'll do more tests with bigger libs and different linker optimizations (some linker optims change the number of buckets
> in the hash table => less entries per hash chains => faster search in case there's no valid entry for a given name).
>
>  
Here is the patch I used to add bloom filter test.
>
>  
>> Rich


[-- Attachment #2: gnuhash-bloom-filter.diff --]
[-- Type: text/x-patch, Size: 958 bytes --]

diff --git a/src/ldso/dynlink.c b/src/ldso/dynlink.c
index c733dc5..a4b150c 100644
--- a/src/ldso/dynlink.c
+++ b/src/ldso/dynlink.c
@@ -138,6 +138,7 @@ static Sym *sysv_lookup(const char *s, uint32_t h, struct dso *dso)
 	return 0;
 }
 
+#define BWSZ (sizeof(size_t)*8)
 static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso)
 {
 	Sym *sym;
@@ -145,10 +146,15 @@ static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso)
 	uint32_t *hashtab = dso->ghashtab;
 	uint32_t nbuckets = hashtab[0];
 	uint32_t *buckets = hashtab + 4 + hashtab[2]*(sizeof(size_t)/4);
-	uint32_t h2;
+	size_t *maskwords = (size_t *)(hashtab + 4);
+	uint32_t h2 = h1 >> hashtab[3];
 	uint32_t *hashval;
-	uint32_t n = buckets[h1 % nbuckets];
+	uint32_t n = (h1/BWSZ) & (hashtab[2]-1);
+	size_t bm = (1 << (h1%BWSZ)) | (1 << (h2%BWSZ));
 
+	if ((maskwords[n] & bm) != bm) return 0;
+
+	n = buckets[h1 % nbuckets];
 	if (!n) return 0;
 
 	strings = dso->strings;