Proposed approach for malloc to deal with failing brk

[Rich Felker <dalias@aerifal.cx>]

Failure of malloc when a badly-placed VMA blocks the brk from being
expanded has been a known issue for a while, but I wasn't aware of how
bad it was breaking PIE binaries on affected systems. So now that it's
been raised again I'm looking to fix it, and I have a proposed
solution. First, some background:

We want brk. This is not because "brk is faster than mmap", but
because it takes a lot of work to replicate what brk does using mmap,
and there's no hope of making a complex dance of multiple syscalls
equally efficient. My best idea for emulating brk was to mmap a huge
PROT_NONE region and gradually mprotect it to PROT_READ|PROT_WRITE,
but it turns out this is what glibc does for per-thread arenas and
it's really slow, probably because it involves splitting one VMA and
merging into another.

So the solution is not to replicate brk. The reason we want brk
instead of mmap is to avoid pathological fragmentation: if we obtain a
new block of memory from mmap to add it to the heap, there's no
efficient way to track whether it's adjacent to another free region
which it could be merged with. But there's another solution to this
fragmentation problem: an asymptotic one. Here it goes:

Once brk has failed, begin obtaining new blocks to add to the heap via
mmap, with the size carefully chosen:

    MAX(requested_size, PAGE_SIZE<<(mmap_cnt/2))

where mmap_cnt is initially 0 and increments by 1 each time a new heap
block has to be obtained via mmap. This ensures exponential growth of
the blocks added, so that the fragmentation cost will be extremely
finite (asymptotically zero relative fragmentation) while bounding the
preallocation to roughly 50% beyond the actual amount of memory needed
so far.

Perhaps the best part is that this solution can be implemented in just
a few lines of code.

Rich