Re: Re: [musl] The heap memory performance (malloc/free/realloc) is significantly degraded in musl 1.2 (compared to 1.1)

[baiyang <baiyang@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 6951 bytes --]

> The ones that return some value larger than the requested size are
> returning "the requested size, rounded up to a multiple of 16" or
> similar. Not "the requested size plus 1500 bytes". 
...
> They don't return 8100. They return something like 6608 or 6624.

No, AFAIK, There are many allocators whose return value of malloc_usable_size is 1KB (or more) larger than the requested value at malloc time.
For Example: if you do "void* p = malloc(6700)" on tcmalloc, then "malloc_usable_size(p)" will return **8192**. Far more than just "rounded up to a multiple of 16".

> This does not follow at all. tcmalloc is fast because it does not have
> global consistency, does not have any notable hardening, and (see the
> name) keeps large numbers of freed slots *cached* to reuse, thereby
> using lots of extra memory. Its malloc_usable_size is not fast because
> of returning the wrong value, if it even does return the wrong value
> (I have no idea). 

We don't need to refer to these features of tcmalloc, we only need to refer to its malloc_usable_size algorithm.

> It's fast because they store the size in-band right
> next to the allocated memory and trust that it's valid, rather than
> computing it from out-of-band metadata that is not subject to
> falsification unless the attacker already has nearly full control of
> execution.

No, if I understand correctly, tcmalloce doesn't store the size in-band right next to the allocated memory. On the contrary, when executing malloc_usable_size(p) (actually GetSize(p)), it will first find the size class corresponding to p through a quick lookup table, and then return the length of the size class. See: https://github.com/google/tcmalloc/blob/9179bb884848c30616667ba129bcf9afee114c32/tcmalloc/tcmalloc.cc#L1099 

My understanding: the biggest impediment to our inability to apply similar optimizations is that we have to return 6700, not 8192 (of course, you've denied this is the reason). 

On the other hand, if the low speed is not caused by having to return 6700, then we should be able to use a similar quick lookup table optimization ("tc_globals.pagemap().sizeclass(p)") to achieve at least dozens of times performance improvement.

Thanks :-P

--

   Best Regards
  BaiYang
  baiyang@gmail.com
  http://i.baiy.cn
**** < END OF EMAIL > **** 
 
 
From: Rich Felker
Date: 2022-09-20 11:28
To: baiyang
CC: musl
Subject: Re: Re: [musl] The heap memory performance (malloc/free/realloc) is significantly degraded in musl 1.2 (compared to 1.1)
On Tue, Sep 20, 2022 at 10:35:02AM +0800, baiyang wrote:
> > You seem to think that if the group stride was 8100, calling realloc might memcpy up to 8100 bytes. This is not the case.
> 
> Yes, I already understood that mallocng would only memcpy 6600 bytes
> when I was told that malloc_usable_size will return the size
> requested by the user.
> 
> But AFAIK, many other malloc implementations basically don't keep
> 6600 bytes of data. So they're actually going to memcpy the 8100
> bytes.
 
You have made up a problem that does not exist. Specifically, at least
as far as I can tell, no such implementation exists.
 
The ones that return some value larger than the requested size are
returning "the requested size, rounded up to a multiple of 16" or
similar. Not "the requested size plus 1500 bytes". For the
dlmalloc-style allocators, this is because they do not have uniform
slots for size classes; they have arbitrary splits, and only care
about aligning start/end on a properly aligned boundary. And for more
slab-like allocators, they all keep track of at least a coarse "actual
size" specifically so that realloc does not gratuitously copy large
amounts of unnecessary data (among other reasons).
 
> > You also seem to be under the impression that the work to determine
> > that the size was 6600 and not 8100 is where most (or at least a
> > significant portion of) the time is spent.  This is also not the case.
> > The majority of the metadata processing time is chasing pointers back
> > to the out-of-band metadata, validating it, validating that it
> > round-trips back, and validating various other things. Some of these
> > could in principle be omitted at the cost of loss-of-hardening.
> 
> Yes, according to my previous understanding (which seems wrong now),
> since other malloc_usable_size implementations that directly return
> 8100 (the actual allocated size class length)
 
They don't return 8100. They return something like 6608 or 6624.
 
> such as tcmalloc are
> all very fast, so I can only understand that mallocng is so much
> slower than them because it has to return 6600, not 8100.
 
This does not follow at all. tcmalloc is fast because it does not have
global consistency, does not have any notable hardening, and (see the
name) keeps large numbers of freed slots *cached* to reuse, thereby
using lots of extra memory. Its malloc_usable_size is not fast because
of returning the wrong value, if it even does return the wrong value
(I have no idea). It's fast because they store the size in-band right
next to the allocated memory and trust that it's valid, rather than
computing it from out-of-band metadata that is not subject to
falsification unless the attacker already has nearly full control of
execution.
 
> Apart from
> this difference, there is no reason it is slower than other
> implementations of malloc_usable_size as I understand it.
 
Comparing the speed of malloc_usable_size is utterly pointless. That
is not where the time is spent in any real-world load that's not
gratuitously doing stupid things. I imagine tcmalloc's is faster, for
the reasons explained above (which have nothing to do with whether the
value returned is the exact size you requested). But this has nothing
to do with why the overall performance is higher.
 
> If this is not the main reason, can we speed up this algorithm with
> the help of a fast lookup table mechanism like tcmalloc? As I said
> before, this not only greatly increases the performance of
> malloc_usable_size , but also the performance of realloc and free .
 
No, because the fundamental difference is where you're storing the
data, and the *whole point* of mallocng is that we're storing it in a
place where it's not subject to attack via overflows from other
objects, UAF/DF, etc. This makes it somewhat costlier (but still very
reasonable) to obtain.
 
If you have a particular application where you actually want to trade
safety and low memory usage for performance, you're perfectly free to
link that application to whatever malloc implementation you like. musl
has supported doing that since 1.1.20. It makes no sense to do this
system-wide. You would just increase memory usage and attack surface
drastically with nothing to show for it, since the vast majority of
programs *don't care* how long malloc takes.
 
Rich

[-- Attachment #2: Type: text/html, Size: 13675 bytes --]