[PATCH 24/28] elf: Implement a string table for ldconfig, with tail merging

[Florian Weimer]

* Adhemerval Zanella via Libc-alpha:

> On 01/10/2020 13:34, Florian Weimer via Libc-alpha wrote:
>> This will be used in ldconfig to reduce the ld.so.cache size slightly.
>
> Could you extend the commit message to explain why the 32-bit FNV-1a hash
> is used and how the hash table is organized (how collisions are handled,
> expected memory usage, strategy used to increase/decrease the bucket size)?
>
> It could help also to explain the usercase a bit more, the 'tail merging'
> is not straightforward to understand without dig deep in the code.  Also
> why kind of cache size decrease do you expect by using strategy?

That depends whether cached DSOs use sonames as file names (so that no
symbolic links are needed).  Typically that's not the case today, so the
savings are really small.  glibc-hwcaps may change that.

The repost will have an expanded commit message:

elf: Implement a string table for ldconfig, with tail merging

This will be used in ldconfig to reduce the ld.so.cache size slightly.

Tail merging is an optimization where a pointer points into another
string if the first string is a suffix of the second string.

The hash function FNV-1a was chosen because it is simple and achieves
good dispersion even for short strings (so that the hash table bucket
count can be a power of two).  It is clearly superior to the hsearch
hash and the ELF hash in this regard.

The hash table uses chaining for collision resolution.

>> diff --git a/elf/stringtable.c b/elf/stringtable.c
>> new file mode 100644
>> index 0000000000..f9ade50249
>> --- /dev/null
>> +++ b/elf/stringtable.c
>> @@ -0,0 +1,201 @@
>> +/* String tables for ld.so.cache construction.  Implementation.
>
> This file misses the Copyright year.

Fixed throughout.

>> +static void
>> +stringtable_init (struct stringtable *table)
>> +{
>> +  table->count = 0;
>> +  table->allocated = 16;
>> +  table->entries = xcalloc (table->allocated, sizeof (table->entries[0]));
>> +}
>> +
>
> Why 16 elements as initial size?

I'm increasing it to 128 with a comment.  128 is based on the number of
DSOs within glibc itself.

>> +struct stringtable_entry *
>> +stringtable_intern (struct stringtable *table, const char *string)
>> +{
>> +  if (table->allocated == 0)
>> +    stringtable_init (table);
>
> How this could happen? Is it expect the caller to set 'allocated'
> explicitly?

Zero-initialization is valid.  stringtable_free also leaves the table
ready for re-use.

>> +  /* Copy the strings.  */
>> +  for (uint32_t i = 0; i < table->allocated; ++i)
>> +    for (struct stringtable_entry *e = table->entries[i]; e != NULL;
>> +         e = e->next)
>> +      if (result->strings[e->offset] == '\0')
>> +        memcpy (&result->strings[e->offset], e->string, e->length + 1);
>> +}
>
> Ok, I guess allocating a new stringtable_finalized should be simpler than
> operating the table itself.

Sorry, I don't understand.  Do you mean reusing the table allocation in
some way?  Yes, that would be fairly complicated.

>> +/* Adds STRING to TABLE.  May return the address of an existing entry.  */
>> +struct stringtable_entry *stringtable_intern (struct stringtable *table,
>> +                                              const char *string);
>
> I think this name is confusing, why not just 'stringtable_add' or
> 'stringtable_add_element'?

I'm changing it to stringtable_add.  Didn't realize that interning is
obscure terminology.

Thanls,
Florian
-- 
Red Hat GmbH, https://de.redhat.com/ , Registered seat: Grasbrunn,
Commercial register: Amtsgericht Muenchen, HRB 153243,
Managing Directors: Charles Cachera, Brian Klemm, Laurie Krebs, Michael O'Neill