Skip to content
Working draft of nextgen malloc implementation for musl libc
C C++ Makefile
Branch: master
Clone or download
Rich Felker
Rich Felker release physical memory for page-aligned subranges on free
this applies only to allocations large enough to contain at least a
full (aligned) page, and skips others with no significant work. slots
in a group are not themselves page-aligned, so the first and last page
overlapping the the slot generally can't be released. in principle
they could be when the adjacent slot is also free, but that would
require further synchronization and madvise under lock, and would also
preclude having persistent state to cycle used offset within the slot.

for now, MADV_DONTNEED is used to release pages of physical memory.
MADV_FREE would be faster and may be the right thing to switch to
later, but would make it harder to observe the effectiveness/benefits
of the change since it's not reflected in memory usage until memory
pressure causes the pages to be discarded. MADV_DONTNEED also
potentially allows making "whole-page subranges always start
zero-filled" an invariant that calloc could use (and that calloc and
possibly malloc could assert to catch some use-after-free).
Latest commit ff7051e Dec 14, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore add .gitignore file Dec 10, 2019
LICENSE add LICENSE file Nov 28, 2019
Makefile add missing deps for new headers to Makefile Dec 11, 2019
README.md add brief high-level design description to readme Nov 27, 2019
aligned_alloc.c fix reversed argument order in aligned_alloc Dec 13, 2019
assert.h begin separation into multiple files Dec 10, 2019
atomic.h move atomics out of malloc.c to a header Dec 11, 2019
dump.c dump_heap: replace useless printing of free meta records with counts Dec 13, 2019
free.c release physical memory for page-aligned subranges on free Dec 14, 2019
locking.h add pthread mutex locking backend as alt to rwlock, use it by default Dec 11, 2019
malloc.c cache page size in malloc context if it's runtime-variable Dec 14, 2019
malloc_usable_size.c begin separation into multiple files Dec 10, 2019
memalign.c record and cycle used offset within a slot each time it's allocated Dec 13, 2019
meta.h cache page size in malloc context if it's runtime-variable Dec 14, 2019
posix_memalign.c begin separation into multiple files Dec 10, 2019
realloc.c

README.md

Next-gen malloc for musl libc - Working draft

This is a draft of the upcoming next-gen malloc implementation for musl libc. It is not complete, lacking some logic for strategy to obtain new memory, memalign-family functions, etc. as well as some hardening features and optimizations that the final version is expected to include.

The included Makefile builds static and shared library files that programs can link with, or use with LD_PRELOAD (for the shared version).

High-level design

This allocator organizes memory dynamically into small slab-style groups of up to 32 identical-size allocation units with status controlled by bitmasks, and utilizes a mix of in-band and out-of-band metadata to isolate sensitive state from regions easily accessible through out-of-bounds writes, while avoiding the need for expensive global data structures.

The closest analogue among other well-known allocators is probably OpenBSD's omalloc.

Base allocation granularity and alignment is 16 bytes. Large allocations are made individually by mmap, but they also have out-of-band metadata records treating them as special one-member groups, allowing realloc and free to validate them. Smaller allocations come from groups of one of 48 size classes, spaced linearly up to 128 (the first 8 classes), then roughly geometrically with four steps per doubling, but adjusted to divide powers of two with minimal remainder (waste).

You can’t perform that action at this time.