[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 30 Sep 2021 12:24:56 -0400
From: Rich Felker <dalias@...c.org>
To: Jack Bond-Preston <jack.bond-preston@....com>
Cc: musl@...ts.openwall.com
Subject: Re: 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
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.
