From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/12751 Path: news.gmane.org!.POSTED!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: What's wrong with musl's malloc Date: Fri, 20 Apr 2018 16:09:04 -0400 Message-ID: <20180420200904.GS3094@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1524254839 15603 195.159.176.226 (20 Apr 2018 20:07:19 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 20 Apr 2018 20:07:19 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-12767-gllmg-musl=m.gmane.org@lists.openwall.com Fri Apr 20 22:07:15 2018 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1f9cJN-0003tN-AP for gllmg-musl@m.gmane.org; Fri, 20 Apr 2018 22:07:13 +0200 Original-Received: (qmail 5245 invoked by uid 550); 20 Apr 2018 20:09:19 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 5210 invoked from network); 20 Apr 2018 20:09:18 -0000 Content-Disposition: inline Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:12751 Archived-At: I've talked on and off about musl's malloc needing to be overhauled or replaced, and gaining the ability to experiment with that is one of the motivations for making malloc interposable/replacable. Here's a brief write-up of what's wrong that needs to be addressed: The main benefits of musl's malloc vs the standard dlmalloc algorithms it's based on is the fine-grained locking. As long as there are binned free chunks of various sizes available, threads calling malloc will only contend for a lock when they're requesting allocations of same or similar size. This works out well under artificial random loads; I'm not sure how much it helps on typical real-world loads. In any case, the fine-grained locking also created a problem I didn't anticipate when I designed it: when allocating memory that involves splitting a free chunk, or when freeing memory that will get merged with an adjacent free chunk, the operation as a whole is not atomic; rather, a large free chunk is consumed, possibly emptying the bin it lies in, split or merged, then returned either to the same or a different bin. By saying this operation is non-atomic, I mean other threads see the intermediate state where the large free chunk has been consumed but not yet returned, and when this happens, they unnecessarily split another free chunk or expand the heap rather than waiting for it to be returned. This yields bad, potentially catastrophic, fragmentation. The malloc side already partially mitigates this with the "pretrim" function, which is used whenever the leftover part after splitting would remain in the same bin it was already in. In particular his covers splitting small allocations off a large "top of heap" zone, but it doesn't help with splitting small chunks. And the free side is much worse -- large free zones momentarily disappear every time something adjacent to them is freed. In order to overcome this fully while maintaining the fine-grained locking, we'd need the ability to hold multiple locks concurrently, which would require a protocol for lock acquisition order to avoid deadlock. But there may be cheap mitigations that could be made in free like on the malloc side. For instance it might be possible to make a simpler protocol whereby we could always hold the lock for bin 63, thereby avoiding exposing a state where large free zones are unavailable. If there's a way to make this work, moving the binmap masking for newly-emptied bins from unbin() to unlock_bin() would ensure that malloc doesn't "see" a "temporary empty" state. In the long term, I think the whole malloc design we're using now is wrong, and should be replaced, but until the time comes to actually do that, it may make sense to try to improve some of the worst properties, or even to reduce or eliminate the granularity of the locking if it proves not to be very valuable on real-world loads. Rich