[PATCH] malloc: Make sure tcache_key is odd enough

[Wilco Dijkstra]

Hi Samuel/Florian,

> +  /* We want tcache_key not to be a commonly-occurring value in memory, so
> +   * ensure a minimum amount of one and zero bits.  */

It's is worth mentioning that zero is not a valid tcache_key here
in case people don't check the commit logs.

> +  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)

Should we be using stdc_count_ones? That also has the advantage
of adjusting to a 32-bit type on 32-bit targets.

>      {
>        tcache_key = random_bits ();
>  #if __WORDSIZE == 64

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

That would require changes to tcache layout - I think it might just fit, but
it's not obvious it is worth it (particularly since it is a bad design - there
are much better alternatives if only we could change the block layout...).

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

I measured actual calls to random_bits. Maximum iterations is
similar for 64 bits and 32 bits, around 25 in 1E8 tests. 

If we limit one/zero bits to 1/4 of the WORDSIZE and also exclude
values up to 0x1000000 (which is essential since 8 or 16 set bits implies
lots of common small values are accepted), it reduces to 6 iterations.
This has 0.55% reject probability on 32-bit and 0.10% on 64-bit.

Cheers,
Wilco