From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/4754 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Proposed approach for malloc to deal with failing brk Date: Sun, 30 Mar 2014 20:41:04 -0400 Message-ID: <20140331004104.GA15223@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1396226483 19510 80.91.229.3 (31 Mar 2014 00:41:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 31 Mar 2014 00:41:23 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-4758-gllmg-musl=m.gmane.org@lists.openwall.com Mon Mar 31 02:41:18 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1WUQHt-00042e-UK for gllmg-musl@plane.gmane.org; Mon, 31 Mar 2014 02:41:18 +0200 Original-Received: (qmail 11824 invoked by uid 550); 31 Mar 2014 00:41:16 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 11816 invoked from network); 31 Mar 2014 00:41:16 -0000 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:4754 Archived-At: 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