mailing list of musl libc
 help / color / mirror / code / Atom feed
* [musl] Options for mallocng+ldso reclaim_gaps
@ 2020-05-12 22:08 Rich Felker
  2020-06-07  2:13 ` Rich Felker
  0 siblings, 1 reply; 2+ messages in thread
From: Rich Felker @ 2020-05-12 22:08 UTC (permalink / raw)
  To: musl

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?

^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [musl] Options for mallocng+ldso reclaim_gaps
  2020-05-12 22:08 [musl] Options for mallocng+ldso reclaim_gaps Rich Felker
@ 2020-06-07  2:13 ` Rich Felker
  0 siblings, 0 replies; 2+ messages in thread
From: Rich Felker @ 2020-06-07  2:13 UTC (permalink / raw)
  To: musl

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

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2020-06-07  2:13 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-12 22:08 [musl] Options for mallocng+ldso reclaim_gaps Rich Felker
2020-06-07  2:13 ` Rich Felker

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).