understanding page/chunk reclaim algorithm

[Jason Evans]

On Aug 11, 2014, at 4:28 PM, Sideropoulos, Alexander <Alexander.Sideropoulos at netapp.com> wrote:
> Hey all. We are trying to understand how Jemalloc reclaims free runs and chunks.
> Specifically for small allocation sizes, what are the heuristics for
> 
> 1) free runs being reclaimed within the chunk to be reused for a different size and

jemalloc uses a lowest-address best fit search to allocate page runs.  In other words, it finds the set of runs which are closest to the minimum necessary size, and chooses the run from that set that is lowest in memory from which to split an appropriately sized run (the split tail, if any, remains unallocated).

> 2) free chunks being released back to the OS?

jemalloc maps/unmaps chunks as indivisible units, so chunks are released back to the OS as aggressively as possible, with two caveats:

- Each arena maintains a “spare” chunk, which avoids excessive chunk allocation/deallocation activity if memory usage repeatedly fluctuates in a manner that would require a new short-lived chunk during each growth.
- On Linux, the —disable-munmap configure option is the default, so chunk contents are madvise()d away, but they remain irreversibly mapped once created.  This avoids poor interactions with the Linux kernel’s fragile heuristics for finding available regions of virtual memory.  Without this workaround, it’s common for virtual memory holes to accumulate, and the kernel uses linear-time algorithms to scan the virtual memory map in some performance-critical operations.

Jason