mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Rich Felker <dalias@libc.org>
To: musl@lists.openwall.com
Subject: Re: New malloc - first preview
Date: Fri, 29 Nov 2019 08:55:23 -0500	[thread overview]
Message-ID: <20191129135523.GP16318@brightrain.aerifal.cx> (raw)
In-Reply-To: <CANtPb7bY_uMMwZ26zQ88gFV6eQwg8GHEdj4pdmDL1DVhx3c4rw@mail.gmail.com>

On Fri, Nov 29, 2019 at 09:37:15AM +0300, Vasya Boytsov wrote:
> Is your malloc implementation any better than
> https://github.com/microsoft/mimalloc?
> AFAIK one can use mimalloc in their projects as it has compatible license.
> the only thing that bothers is that it is done by Microsoft research.

"Better" is not meaningful without specifying criteria for evaluation.
The information on mimalloc is sparse, not covering the basic design
it uses AFAICT, rather mainly the new properties it has which are
mostly for the purpose of its specialized sharding API (not
useful/usable for malloc API). So without reading into it much more,
it's hard to say.

From the summary, their idea of "small" is on a completely different
order of magnitude from musl's. 6kLOC is gigantic, far larger than any
single component of musl. Of course it might be really sparse code
with lots of whitespace and comments, but still doesn't bode well.

Regarding "fast", everyone aiming for "fast" claims fast with their
own benchmarks. I generally don't trust malloc benchmarks after N
times of digging into them and finding they were tuned just
above/below a threshold to make a competitor look bad. That's not to
say the same happened here, but "fast at what?" is a real question
here, and the only meaningful test seems to be measurement under
real-world workloads.

The security measures mentioned seem weaker than WIP new malloc and
likely not much better than current one. But it's hard to evaluate
security/hardening measures without a model of proposed attacks and
which ones they mitigate. This is one thing I've focused on in the new
malloc, classifying and addressing them such that we can rule out
entire classes. Roughly, without already having complex capability to
follow multiple pointers and clobber resulting memory, only the
application data stored in the heap, not the allocator's heap state,
is subject to corruption by common methods (linear overflow, UAF, DF).
Not all of this is implemented yet in the draft.

Those things aside, ultimately the answer is that the question is not
what is the best malloc for some arbitrary definition of best, but
what's the best that fits into the constraints of musl, including:

- low absolute space cost at low malloc utilization
- low relative space cost at moderate to high utilization
- compatibility with 32-bit address space
- compatibility with nommu
- compatibility with RLIMIT_AS, no-overcommit configurations

and also provides hardening improvements over the current allocator,
which gets by with only minimal measures.

Nobody should be expecting magical performance improvements out of
this. The likely user-facing changes will be:

- elimination of heap size explosion in multithreaded apps (known bug)
- better return of freed memory to system
- greatly reduced exploitability of bugs related to malloc usage

Speed could go up or down. Hopefully it goes up for lots of things. It
will be a "win" in terms of speed if it merely avoids going down by
more than fixing the "heap size explosion" bug would make it go down
with the current dlmalloc-type design -- see:

https://www.openwall.com/lists/musl/2019/04/12/4

since fixing this bug is absolutely necessary; it keeps impacting
users.

Rich



> On 11/29/19, Rich Felker <dalias@libc.org> wrote:
> > On Thu, Nov 28, 2019 at 04:56:42PM -0500, Rich Felker wrote:
> >> Work on the new malloc is well underway, and I have a draft version
> >> now public at:
> >>
> >> https://github.com/richfelker/mallocng-draft
> >>
> >> Some highlights:
> >>
> >> - Smallest size-class now has 12 of 16 bytes usable for storage,
> >>   compared to 8 of 16 (32-bit archs) or 16 of 32 (64-bit archs) with
> >>   the old malloc, plus 1.5 bytes (32-bit) or 2.5 bytes (64-bit) of
> >>   out-of-band metadata. This overhead (5.5 or 6.5 bytes per
> >>   allocation) is uniform across all sizes.
> >
> > Make that 6 or 7 since there's also a 16-byte (counting alignment,
> > which is most of it) group header that imposes 0.5 bytes of overhead
> > per slot for a full-length 32-slot group.
> >
> > Rich


  reply	other threads:[~2019-11-29 13:55 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-10-22 17:40 New malloc - intro, motivation & design goals document Rich Felker
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 [this message]
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=20191129135523.GP16318@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).