From: Rich Felker <dalias@libc.org>
To: musl@lists.openwall.com
Subject: New malloc - intro, motivation & design goals document
Date: Tue, 22 Oct 2019 13:40:51 -0400 [thread overview]
Message-ID: <20191022174051.GA24726@brightrain.aerifal.cx> (raw)
[-- Attachment #1: Type: text/plain, Size: 1214 bytes --]
Alongside time64 and other enhancements, over the next few months I'll
be working on a major project to replace musl's malloc, which has
known fundamental problems that can't really be fixed without
significant redesign. The early stages of this, in progress now,
involve preparing tests that can identify pitfalls into pathological
fragmentation, some of which may be avoidable and others of which may
be fundamental, for use in assessing possible allocation strategies
and other existing malloc implementations.
I'm attaching a document describing motivations and goals for the
project, and a dead simple minimal test to demonstrate the unbounded
heap expansion problem that's the core motivation. The latter produces
no output but can be watched via top(1) or similar.
I'll follow up soon with some thoughts/findings so far on designs that
might work for us, or that don't work but have interesting properties
that suggest they may lead to workable designs.
I'm not going to try to do development of this inside the musl tree;
getting the ability to experiment with and do this out-of-tree, then
integrate it later, was one of the motivations for supporting malloc
replacement which musl 1.1.20 introduced.
[-- Attachment #2: newmalloc.txt --]
[-- Type: text/plain, Size: 3042 bytes --]
musl libc next-gen malloc implementation
***
Motivation and Design Goals
Desirable qualities of existing allocator:
- Very small code size.
- Near-zero constant minimal overhead, preventing large numbers of
small processes with only minor use of malloc from consuming excess
resources.
- Low, well-understood internal fragmentation.
- Returning of (physical storage for) large contiguous freed memory to
the operating system.
- Detection of heap-based overflows (with limitations) at realloc/free
time via clobbered headers/footers.
- Detection of double-free (with inherent limitations) via chunk
header/flags.
Known flaws in existing allocator:
- Race condition (not data race, a distinct concept) in determining
the availability of free chunk of desired size while
splitting/merging is in progress leads to external fragmentation
(unnecessary splitting of larger chunks) and over-expansion of heap
(via failure to see large free zone in bin 63).
- Reliance on fine-grained per-bin locking to achieve good performance
on typical (not even all; it doesn't help when all threads want the
same size of allocation) multithreaded loads fundamentally precludes
fixing the above race without significant performance regressions.
- The overall dlmalloc design (arbitrary split/merge) inherently has
usage patterns that can produce catastrophic external fragmentation.
- Heuristic for returning dirty pages to kernel (via MADV_DONTNEED) is
over-aggressive in some cases (bad performance), under-aggressive in
others (failure to return memory), and it's not clear that it can be
significantly improved in a dlmalloc-like design.
Together, these necessitate not just enhancements to the existing
allocator, but a completely different design.
Goals for new allocator:
Primarily, the new allocator should eliminate the above known flaws
while preserving the good properties of the existing allocator to the
maximum extent that's possible/practical. In addition, it should:
- Harden protections against heap-based overflows and double free not
to be susceptible to attacks that blindly replace clobbered
headers/footers with valid data. This likely involves out-of-band
metadata and random secrets, but may be achieved in whatever way is
determined to be most effective and compatible with other goals.
- Provide either strong rigorous bounds on external fragmentation, or
heuristically mitigate the chance of reasonable usage patterns
leading to unbounded external fragmentation.
- Expand or restructure the heap only when no free chunks that satisfy
an allocation request (without significant internal fragmentation)
exist.
- Take advantage of realloc as an opportunity to defragment.
- Improve performance, both under reasonable contention and under
single-thread load (with or without existence of other threads).
This likely amounts to short fast-case code paths and designing
synchronization around minimizing the number of atomic/lock
operations.
[-- Attachment #3: expand_race.c --]
[-- Type: text/plain, Size: 259 bytes --]
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
static void *worker(void *p)
{
for (;;) {
void *p = malloc(100000);
free(p);
}
}
int main()
{
for (int i=0; i<10; i++)
pthread_create(&(pthread_t){0}, 0, worker, 0);
for (;;) pause();
}
next reply other threads:[~2019-10-22 17:40 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-22 17:40 Rich Felker [this message]
2019-11-06 3:46 ` Non-candidate allocator designs, things to learn from them Rich Felker
2019-11-06 10:06 ` Florian Weimer
2019-11-28 21:56 ` New malloc - first preview Rich Felker
2019-11-28 22:22 ` Rich Felker
2019-11-29 6:37 ` Vasya Boytsov
2019-11-29 13:55 ` Rich Felker
2019-11-30 5:54 ` Rich Felker
2019-11-29 16:41 ` Roman Yeryomin
2019-11-30 4:49 ` Rich Felker
2019-11-29 19:45 ` Markus Wichmann
2019-11-30 3:15 ` Rich Felker
2019-11-30 22:11 ` Rich Felker
2019-12-06 5:06 ` Rich Felker
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191022174051.GA24726@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).