From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 23053 invoked from network); 30 Sep 2021 16:25:13 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 30 Sep 2021 16:25:13 -0000 Received: (qmail 23851 invoked by uid 550); 30 Sep 2021 16:25:10 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 23824 invoked from network); 30 Sep 2021 16:25:09 -0000 Date: Thu, 30 Sep 2021 12:24:56 -0400 From: Rich Felker To: Jack Bond-Preston Cc: musl@lists.openwall.com Message-ID: <20210930162455.GF4428@brightrain.aerifal.cx> References: <36151c4f-872f-7f84-0402-8491234ea62a@arm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <36151c4f-872f-7f84-0402-8491234ea62a@arm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] Mallocng algorithm high-level overview On Thu, Sep 30, 2021 at 03:02:23PM +0100, Jack Bond-Preston wrote: > Hello, > > I'm currently working on porting mallocng to a new architecture and > could use some assistance understanding the algorithm. From searching > the web, I couldn't seem to find any high-level overview of musl's > mallocng allocator (save for the readme at github/richfelker > /mallocng-draft, which is a little briefer than what I am looking > for). If any such description exists, I would much appreciate > being pointed towards it. If not, would anyone be able to explain > some of the details of the allocator? Some documents: - README in draft repo, as well as its entire detailed git history: https://github.com/richfelker/mallocng-draft - New malloc - intro, motivation & design goals document: https://www.openwall.com/lists/musl/2019/10/22/3 - Review of mallocng motivation/goals: https://www.openwall.com/lists/musl/2020/05/18/3 There may be others I'm forgetting; I'll follow up if I think of some. > Mostly I am interested in a more general high-level overview of how > the allocator works. There are also some specifics I am interested > in, if anyone is able to shine some light on these: > - The uses/purposes of the structures in meta.h. Particularly, meta > and group, and the relation between the two. > > - The general overview of in-band and out-of-band metadata, and how/ > when they are used. struct group represents the storage for a group of slots allocated contiguously (something like a slab), with in-band metadata encoded in the bits of 3 bytes between slots, and a pointer to the out-of-band metadata at the very beginning. A group may be allocated in memory obtained from mmap or, for size and count smaller than a page, inside one slot of a larger group. struct meta is the out-of-band metadata that's allocated in memory intended to be difficult to reach/attack. It always contains a pointer back to the group it goes with for validation, and has a header containing a random secret at address&-4096 (beginning of 'page' for a page unit that need not match system page size) that also validates. This prevents invalid-/double-free bugs (in the absence of other much more powerful gadgets) from being used to construct fake heap metadata to produce an inconsistent allocator state. In-band metadata is treated as low-trust input, and only used for finding out-of-band metadata and validating lack of out-of-bounds writes between slots. It also facilitates rotating the used range within a slot each time it's reused to greatly extend the period for reuse of identical pointers, and catch UAF/DF. > - The purpose/meaning of the UNIT define in meta.h. UNIT is the fundamental allocation unit/alignment. On targets where alignof(max_align_t)==8 it could in theory be 8 instead of 16, but some additional tweaks might be needed to actually make this work, at least on 64-bit archs, due to lack of space for in-band metadata. If alignof(max_align_t) were larger it would need to be larger, which is a bad thing for memory usage, but should work without breaking anything. I made UNIT a constant 16 for the time being rather than an expression in terms of sizeof(void *) and alignof(max_align_t) because the emergent consequences of dropping it to 8, and how that works with size class thresholds for whole pages, were not invesitated to know if anything inefficient would come out. > - Any assumptions about alignment/pointer size the allocator may > make. Mainly that UNIT contains sufficient space for a pointer (to out of band meta) and the 4 byte header for the first slot. > Thanks very much for your time, I appreciate the request is a bit > broad, but any information is appreciated. Please don't hesitate to > reach out for more information. > > Cheers, > Jack