Date: Sun, 30 Mar 2014 20:41:04 -0400 From: Rich Felker <dalias@...ifal.cx> To: musl@...ts.openwall.com Subject: Proposed approach for malloc to deal with failing brk 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
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.