Re: [musl] Options for mallocng+ldso reclaim_gaps

[Rich Felker <dalias@libc.org>]

On Tue, May 12, 2020 at 06:08:02PM -0400, Rich Felker wrote:
> I have an out-of-tree mockup of the ldso reclaim_gaps equivalent for
> mallocng. Right now the way it works is by repeatedly placing a
> single-slot group of each power-of-two-sized class (in which nested
> groups can be allocated) that fits, in order of decreasing powers. So
> a 2600 byte gap would get filled with
> 
> - 2048 (16 header + 1x2032)
> - 512 (16 header + 1x496)
> - (remainder 40 bytes too small to be useful)
> 
> This yields a total of 5x496 for groups of small allocations, and even
> some larger things like 2x240 that might be useful for struct dso. But
> it's only one option.
> 
> The other option is treating each donation as a blank slate for bump
> allocation of permanent groups of any size that fit. For example the
> above could fit:
> 
> - 1x1632, 1x676, 1x240
> - 1x1344, 1x672, 1x496[, 1x64]
> - 1x1008, 1x1344, 1x240
> - etc.
> 
> Desptie this seeming attractive, the permanence of the division (it
> really doesn't make sense to make any complex dlmalloc reinvention for
> merging these back for reuse in different divisions) means it's very
> possible that small programs that benefit the most from reclaim_gaps
> might never get to use the reclaimed memory again, if they don't need
> the same size class again. On the other hand, the largest-fit
> power-of-two mockup I have now gives slots that can hold almost any
> nested group of smaller size.
> 
> Thoughts on any of this? Anything I might be missing in pros or cons
> or other reasonable choices that might be better?

The first method is working really well in practice with my WIP
integration. I have, coming from just main program and libc gaps, and
possibly also the gaps of the LD_PRELOAD library measuing this:

2 1x128
1 1x240
3 1x496
2 1x1008
3 1x2032

Inside those, the following fit with plenty of space left over:

1 30x16
1 15x32
1 10x48
1 7x64
1 5x96
2 2x240
1 3x320
3 2x496
2 2x1008

Making up nominal allocations of 2996 bytes and free slots worth up to
6272 bytes.

The only non-gap memory this test trace is using is one page for the
out-of-band metadata. (Presently I'm not using gaps for that because
it has a predictable address. But the below-data gaps, if any, are
naturally guarded by text and would be fairly safe to use, aside from
having predictable addresses, if we wanted to.)

Rich