malloc & uncommitting memory

malloc & uncommitting memory

[Rich Felker]

Adding the ability for malloc to "uncommit" memory that it's already
obtained has been a goal for a long time, but I haven't found a way to
make it efficient. On the kernel side there's been the whole "vrange"
idea floating around for a while, but it's only going to work on
really new kernels, and only on mainstream archs, even if it gets
adopted, and so far the interface seems ugly and unlikely to work very
well. Here's a potential alternative approach:

Whenever a chunk is added (merged, updated, and re-added) to the
bin-63 free list (the largest bin, usually not used directly for
satisfying allocation requests but as a source for trimming when no
smaller-size bins have free chunks that can satisfy the allocation),
move it to the end of the bin rather than the beginning if it's larger
than the chunk currently at the end. This allows us to track the
largest free area.

If the number of free chunks in bin 63 exceeds a certain threshold
(possibly very small), allocate the largest one (unbin it), mmap a new
PROT_NONE zero region over top of the middle of it, and store it in a
new linked list of "frozen" memory regions.

When no free chunks are available in bin 63 and one is needed, before
trying to expand the brk or use mmap, remove a chunk from the frozen
list, mprotect it accessible, and use it. If it's excessively large,
split it and only mprotect a reasonable-size part, re-adding the
remainder to the frozen list. (Note: mprotect can fail here due to
commit limit, and in that case, the frozen chunk would be stuck
frozen and malloc would have to fail the allocation.)

As long as thresholds are chosen right, I don't think this approach
would be costly from a performance standpoint. But it might have
consequences for fragmentation. So I'd like to discuss it further, see
what ideas emerge, and whether it looks reasonable before trying to
implement anything.

It's also possible that this whole goal is undesirable, since it would
create _more_ situations where malloc could fail in the app that's
being nice about "uncommitting" its memory; the benefit is that it
reduces the chance of malloc failure in other apps when one app has
momentarily used huge amounts of memory (allocated in small units, so
that mmap wasn't used) then returned it.

Rich

Re: malloc & uncommitting memory

[Rich Felker]

On Wed, Apr 02, 2014 at 05:08:05PM -0400, Rich Felker wrote:
> As long as thresholds are chosen right, I don't think this approach
> would be costly from a performance standpoint. But it might have
> consequences for fragmentation. So I'd like to discuss it further, see
> what ideas emerge, and whether it looks reasonable before trying to
> implement anything.

Basically, the way fragmentation can result from having "frozen"
chunks is when small chunks adjacent to them are freed: these free
chunks are unable to be merged with the frozen chunk, so they get
reused for small allocations despite being adjacent to a large free
(albeit frozen) region.

I see several possible ways to reduce or avoid this:

1. Always leave large padding (large enough to stay in bin-63) on both
   sides of the frozen chunk when freezing. This would force adjacent
   freed chunks to get merged into a bin-63 chunk, preventing them
   from getting used for small allocations unless nothing smaller were
   available. However, they could still get used and gradually
   depleted.

2. When a chunk is freed, check if it's a neighbor to a frozen chunk,
   and if so, put it at the end of its bin rather than the beginning,
   so that other free chunks of the appropriate size get used first.
   However this wouldn't help when it's the only chunk of its size but
   another slightly-larger chunk would be a better candidate to split.

3. Allow merging directly into frozen chunks, the same way merging
   into free chunks is done now, with logic to expand the region
   that's PROT_NONE similar to the current logic for expanding the
   MADV_DONTNEED region.

Of these, option 3 looks the most promising.

Rich

Re: malloc & uncommitting memory

[M. Ziebell]

[-- Attachment #1: Type: text/plain, Size: 2591 bytes --]

Am Thu, 3 Apr 2014 00:43:23 -0400
schrieb Rich Felker <dalias@aerifal.cx>:

> On Wed, Apr 02, 2014 at 05:08:05PM -0400, Rich Felker wrote:
> > As long as thresholds are chosen right, I don't think this approach
> > would be costly from a performance standpoint. But it might have
> > consequences for fragmentation. So I'd like to discuss it further,
> > see what ideas emerge, and whether it looks reasonable before
> > trying to implement anything.
> 
> Basically, the way fragmentation can result from having "frozen"
> chunks is when small chunks adjacent to them are freed: these free
> chunks are unable to be merged with the frozen chunk, so they get
> reused for small allocations despite being adjacent to a large free
> (albeit frozen) region.
> 
> I see several possible ways to reduce or avoid this:
> 
> 1. Always leave large padding (large enough to stay in bin-63) on both
>    sides of the frozen chunk when freezing. This would force adjacent
>    freed chunks to get merged into a bin-63 chunk, preventing them
>    from getting used for small allocations unless nothing smaller were
>    available. However, they could still get used and gradually
>    depleted.
> 
> 2. When a chunk is freed, check if it's a neighbor to a frozen chunk,
>    and if so, put it at the end of its bin rather than the beginning,
>    so that other free chunks of the appropriate size get used first.
>    However this wouldn't help when it's the only chunk of its size but
>    another slightly-larger chunk would be a better candidate to split.
> 
> 3. Allow merging directly into frozen chunks, the same way merging
>    into free chunks is done now, with logic to expand the region
>    that's PROT_NONE similar to the current logic for expanding the
>    MADV_DONTNEED region.
> 
> Of these, option 3 looks the most promising.
> 
> Rich

As far as i understand "uncommitted" memory is allocated address space.
A region in memory which is not used by the program, but the address
space expanded to make a smaller region available to the programm for
use.
Please correct me if I am wrong.


Based on that understanding, the idea or your proposal sounds not
really desirable.
You have to take care of tons of exceptions and special cases.
I'm pretty sure I don't understand what uncommitted memory is for, but
I'm heary is hundreds of lines of complex code, if-else constructs
everywhere and bugs.

The way you suggest to manage these regions in memory sound pretty and
advanced, please don't feel offended by my statement. 

Marco

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: malloc & uncommitting memory

[Rich Felker]

On Thu, Apr 03, 2014 at 08:17:25PM +0200, M. Ziebell wrote:
> As far as i understand "uncommitted" memory is allocated address space.
> A region in memory which is not used by the program, but the address
> space expanded to make a smaller region available to the programm for
> use.
> Please correct me if I am wrong.

I'm not clear on exactly what you're asking so I'll try to just
clarify the issue. There are basically three types of memory usage
that matter:

- Virtual address space: Process-local resource. Aside from relatively
  low overhead in kernel bookkeeping, this only matters in that, if
  you run out of addresses, you can't allocate anything else.

- Anonymous pages: Global resource. These are pages that actually
  consume (rather than just temporarily using as cache) physical
  storage (ram or swap) because they're not backed by a file or device
  or the zero page or shared (via COW) with another mapping.

- Commit charge: Global resource. A superset of anonymous pages, also
  counting mapped pages that are presently shared (COW) with the zero
  page, a file, another process, etc. but which will need their own
  storage if/when they're written.

At present, musl's malloc can deallocate only the following:

* All three, only when resizing or freeing an allocation that was
  large enough to be serviced individually by mmap.

* Anonymous pages only, by calling madvise with MADV_DONTNEED to reset
  them to COW copies of the zero page when a large free range
  coalesces in the heap.

In particular, neither commit charge nor virtual address space from
the heap used for small allocations is ever freed. Avoiding freeing
the virtual address space is generally a good thing, since doing so
could result in pathological fragmentation. But not freeing the commit
charge means that an application which momentarily used a large amount
of memory by allocating a small bit at a time (think hideous tree/list
structures used in C++ and glib-based code) then freeing it all will
continue to tie part of the commit limit and reduce the amount of
memory available to other programs (note: this only applies with
overcommit disabled).

> Based on that understanding, the idea or your proposal sounds not
> really desirable.
> You have to take care of tons of exceptions and special cases.
> I'm pretty sure I don't understand what uncommitted memory is for, but
> I'm heary is hundreds of lines of complex code, if-else constructs
> everywhere and bugs.

The whole of malloc is under 600 lines, so anything measured in
"hundreds of lines" is definitely inappropriate as an addition.
However the basic concept (frozen chunk list, described in the first
mail) is at most tens of lines of code, and the strategies 1-3 for
avoiding fragmentation would each be somewhere on the same order of
magnitude, I think.

Rich