[PATCH v5 06/11] elf: Implement a string table for ldconfig, with tail merging

Adhemerval Zanella adhemerval.zanella@linaro.org
Tue Dec 1 12:49:59 GMT 2020



On 01/12/2020 08:18, Florian Weimer via Libc-alpha wrote:
> 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.
> 
> Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>
> 
> ---

[...]

> +/* Sort reversed strings in reverse lexicographic order.  This is used
> +   for tail merging.  */
> +static int
> +finalize_compare (const void *l, const void *r)
> +{
> +  struct stringtable_entry *left = *(struct stringtable_entry **) l;
> +  struct stringtable_entry *right = *(struct stringtable_entry **) r;
> +  size_t to_compare;
> +  if (left->length < right->length)
> +    to_compare = left->length;
> +  else
> +    to_compare = right->length;
> +  for (size_t i = 1; i <= to_compare; ++i)
> +    {
> +      unsigned char lch = left->string[left->length - i];
> +      unsigned char rch = right->string[right->length - i];
> +      if (lch != rch)
> +        return rch - lch;
> +    }

The core change of this new version is the fix of the comparison loop,
where previous version where not comparing the right characters.

For instance, with string:

  left = { "defgh", 5"} and right = { "abcdefgh", 8 }

The v4 failed since it compared

  for (ssize_t i in { 4, 3, 2, 1, 0 })
     if (left->string[i] != right->string[i])
       return ...

Which results in:

  left->string[4] == right->string[4] -> 'h' == 'e'


Which now v5 it does the expected tail comparing:

  for (size_t i in { 1, 2, 3, 4, 5})
    if (left->string[left->length - i] != right->string[right->length - i])
      ...

Which results in:

  left->string[7] == right->string[4] -> 'h' == 'h'
  left->string[6] == right->string[3] -> 'g' == 'g'
  left->string[5] == right->string[2] -> 'f' == 'f'
  left->string[4] == right->string[1] -> 'e' == 'e'
  left->string[3] == right->string[0] -> 'd' == 'd'


This looks the correct output, but it worries me that it was not caught on
the tst-stringtable. Could you add a test for it?

PS: it would be good if you outline what you have changed in the newer
version.


More information about the Libc-alpha mailing list