[PATCH] malloc: Make sure tcache_key is odd enough

[Florian Weimer]

* Samuel Thibault:

> We want tcache_key not to be a commonly-occurring value in memory, so ensure
> a minimum amount of one and zero bits.
>
> And we need it is non-zero, otherwise even if tcache_double_free_verify sets
> e->key to 0 before calling __libc_free, it gets called again by __libc_free,
> thus looping indefinitely.
>
> Fixes: c968fe50628db74b52124d863cd828225a1d305c ("malloc: Use tailcalls in __libc_free")
> ---
>  malloc/malloc.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 5ca390cc22..9c3d0cfda3 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -3152,6 +3152,15 @@ tcache_key_initialize (void)
>    if (__getrandom_nocancel_nostatus_direct (&tcache_key, sizeof(tcache_key),
>  					    GRND_NONBLOCK)
>        != sizeof (tcache_key))
> +    tcache_key = 0;
> +
> +  /* We want tcache_key not to be a commonly-occurring value in memory, so
> +   * ensure a minimum amount of one and zero bits.  */
> +  int minimum_bits = __WORDSIZE * 3 / 8;
> +  int maximum_bits = __WORDSIZE - minimum_bits;
> +
> +  while (__builtin_popcountl (tcache_key) < minimum_bits
> +      || __builtin_popcountl (tcache_key) > maximum_bits)
>      {
>        tcache_key = random_bits ();
>  #if __WORDSIZE == 64

I wonder if we should use a 64-bit value on 32-bit systems, too.

The reject probabilities are:

import math
def f(bits, limit):
    return 2 * sum([math.comb(bits, k) for k in range(limit)]) / 2 ** bits
for bits, limit in [
    (64, 24),
    (32, 10),
    (32, 11),
    (32, 12),
]:
    print(f'{bits} bits, limit {limit}, reject probability {f(bits, limit)}')

64 bits, limit 24, reject probability 0.0327657590988232
32 bits, limit 10, reject probability 0.020061607006937265
32 bits, limit 11, reject probability 0.050102459732443094
32 bits, limit 12, reject probability 0.11018416518345475

So the current values still do not have much impact on process startup
time.  But with 32 bits, the probability of hitting one of the common
values still quite high.

Thanks,
Florian