Re: [musl] Concrete case-by-case examples of mallocng @ low usage

[Rich Felker <dalias@libc.org>]

On Fri, Apr 10, 2020 at 01:04:07PM -0400, Rich Felker wrote:
> The following are tables of initial allocation behavior for all sizes
> up through 16k assuming 4k page size. The fine classing figures won't
> actually be used for initial allocations, but I've included them for
> comparison to illustrate why coarse classes are used. These numbers
> were all done by hand independently of the code, so that if actual
> behavior differs, it indicates a bug in one or the other.
> 
> 
> First 16 size classes, no coarse classing:
> 
>      0-12: 2x2032 -> 2x1008 -> 2x496 -> 30x16
>     13-28: 2x2032 -> 2x1008 -> 2x496 -> 15x32
>     29-44: 2x2032 -> 2x1008 -> 2x496 -> 10x48
>     45-60: 2x2032 -> 2x1008 -> 2x496 -> 7x64
>     61-76: 2x2032 -> 2x1008 -> 2x496 -> 6x80
>     77-92: 2x2032 -> 2x1008 -> 2x496 -> 5x96
>    93-108: 2x2032 -> 2x1008 -> 2x496 -> 4x112
>   109-124: 2x2032 -> 2x1008 -> 7x128
> 
>   125-140: 2x2032 -> 2x1008 -> 7x144

This line is a math error present in the actual code. 7x144 fit in
1008, but not with room for the header of one extra unit (16b). Thus
7x144 get allocated inside a 1168 slot instead. This badly harms
memory usage in small programs since the smallest 1168 group is 8k and
the group may not get used for anything but satisfying a single
malloc(128).

For now I'll probably just make it special-case this one as 6x144
instead of 7x, but that wastes space so a better solution should be
found. That might be applying coarse size classing so that this size
class can start at 14x144 once it switches to fine classing.

Rich