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

[Adhemerval Zanella]

On 30/10/2020 14:08, Florian Weimer wrote:
> * 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.

Looks better, thanks.

> 
>>> 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.

Wouldn't both usages make the above check unnecessary? 

> 
>>> +  /* 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.

Yes, to avoid allocation memory on both new item insertion and on the
finalize operation itself. But I think such optimization does not really
matter for the ldconfig usage.

> 
>>> +/* 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
>