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

[Gabriel Ravier <gabravier@gmail.com>]

On 9/19/22 21:21, Rich Felker wrote:
> On Mon, Sep 19, 2022 at 09:07:57PM +0200, Gabriel Ravier wrote:
>> On 9/19/22 20:14, Szabolcs Nagy wrote:
>>> * baiyang <baiyang@gmail.com> [2022-09-20 01:40:48 +0800]:
>>>> I looked at the code of tcmalloc, but I didn't find any of the problems you mentioned in the implementation of malloc_usable_size (see: https://github.com/google/tcmalloc/blob/9179bb884848c30616667ba129bcf9afee114c32/tcmalloc/tcmalloc.cc#L1099 ).
>>>>
>>>> On the contrary, similar to musl, tcmalloc also directly uses the return value of malloc_usable_size in its realloc implementation to determine whether memory needs to be reallocated: https://github.com/google/tcmalloc/blob/9179bb884848c30616667ba129bcf9afee114c32/tcmalloc/tcmalloc.cc#L1499
>>>>
>>>> I think this is enough to show that the return value of malloc_usable_size in tcmalloc is accurate and reliable, otherwise its own realloc will cause a segment fault.
>>> obviously internally the implementation can use the internal chunk size...
>>>
>>> GetSize(p) is not the exact size (that the user allocated) but an internal
>>> size (which may be larger) and that must not be exposed *outside* of the
>>> malloc implementation (other than for diagnostic purposes).
>>>
>>> you can have 2 views:
>>>
>>> (1) tcmalloc and jemalloc are buggy because they expose an internal
>>>      that must not be exposed (becaues it can break user code).
>>>
>>> (2) user code is buggy if it uses malloc_usable_size for any purpose
>>>      other than diagnostic/statistics (because other uses are broken
>>>      on many implementations).
>>>
>>> either way the brokenness you want to support is a security hazard
>>> and you are lucky that musl saves the day: it works hard not to
>>> expose internal sizes so the code you seem to care about can operate
>>> safely (which is not true on tcmalloc and jemalloc: the compiler
>>> may break that code).
>> While I would agree that using malloc_usable_size is generally not a
>> great idea (it's at most acceptable as a small micro-optimization,
>> but I would only ever expect it to be seen in very well-tested code
>> in very hot loops, as it is indeed quite easily misused), it seems
>> like a bit of a stretch to say that all of:
>>
>> - sqlite3 (https://github.com/sqlite/sqlite/blob/master/src/mem1.c)
>>
>> - systemd
>> (https://github.com/systemd/systemd/blob/main/src/basic/alloc-util.h
>> , along with all files using MALLOC_SIZEOF_SAFE, i.e.
>> src/basic/alloc-util.c, src/basic/compress.c, src/basic/fileio.c,
>> src/basic/memory-util.h, src/basic/recurse-dir.c,
>> src/basic/string-util.c, src/libsystemd/sd-netlink/netlink-socket.c,
>> src/shared/journal-importer.c, src/shared/varlink.c,
>> src/test/test-alloc-util.c and src/test/test-compress.c)
>>
>> - rocksdb (https://github.com/facebook/rocksdb/blob/main/table/block_based/filter_policy.cc
>> , along with at least 20 other uses)
>>
>> - folly (https://github.com/facebook/folly/blob/main/folly/small_vector.h)
>>
>> - lzham_codec (https://github.com/richgel999/lzham_codec/blob/master/lzhamdecomp/lzham_mem.cpp)
>>
>> - quickjs
>> (https://raw.githubusercontent.com/bellard/quickjs/master/quickjs.c)
>>
>> - redis
>> (https://github.com/redis/redis/blob/unstable/src/networking.c,
>> along with a few other uses elsewhere)
>>
>> along with so many more well-known projects that I've given up on
>> listing them, are all buggy because of their usage of
>> malloc_usable_size...
> Depending on how you interpret the contract of malloc_usable_size
> (which was historically ambigious), either (1) or (2) above is
> *necessarily* true. It's not a matter of opinion just logical
> consequences of the choice you make.

Hmmmm... to me none of the two options you have given are true. Instead, 
I'd argue that, as seen by the C abstract machine, invocation of 
malloc_usable_size actually increases the size of a memory block, in 
place, as if by magic. This may seem stupid to some degree, but to me it 
is the only way one can make sense of the documentation for 
malloc_usable_size in glibc, as it has been present in glibc since 
malloc_usable_size was first added in 1996:

     This routine tells you how many bytes you can actually use in an
     allocated chunk, which may be more than you requested (although
     often not). You can use this many bytes without worrying about
     overwriting other allocated objects. Not a particularly great
     programming practice, but still sometimes useful.

To me, this note directly indicates that the function is intended to 
work, within the context of the abstract machine, as if it somehow 
increased the size of the block at the given address. It could perhaps 
have been better named as something like malloc_try_extend_in_place 
w.r.t. interpretation of the function's behavior as relating to the 
abstract machine, but the name it was given probably made more sense at 
the time, as one may have assumed that the other name would have meant 
that it might do some more work that just returning the internal 
allocated size.

This interpretation is also the one followed by pretty much every single 
program out there that uses malloc_usable_size, and the opposite 
interpretation (that malloc_usable_size is allowed to return a 
completely useless number that can't be used for anything useful) seems 
rather asinine to me


Such effects on the C abstract machine may seem ludicrous, as though 
nothing in C should be able to do things like this, but when you search 
for other examples of extensions to C that do weird things with the 
abstract machine, you can find some quite quickly:

- POSIX makes it so that storing into a function pointer by aliasing 
into it with a data pointer shall result in defined behavior

- GNU attributes like __attribute__((may_alias)) make it so that access 
through pointers with types with that attribute are defined even if they 
try to alias normally incompatible object types

- x86 intrinsics that access pointers are defined as having defined 
behavior even if they try to alias normally incompatible object types 
(the may_alias attribute above is used in GCC to implement them)

- POSIX makes it so that calling signal and then making the program 
multi-threaded shall result in defined behavior

- POSIX makes it so that calling fprintf with numbered argument 
conversion specifications (%n$), the apostrophe flag character (along 
with a few other things I'm too lazy to list) shall result in defined 
behavior

- Many more...

and yet all of these are quite often used and it is generally accepted 
that an implementation implementing such features should also make it so 
that the rules of the abstract machine, as implemented, are correctly 
affected and that the implementation does not suddenly make it so that 
using these result in UB where they claim that they implement the 
corresponding features.


You might say that you accept the changes POSIX makes to the abstract 
machine, but not those made by malloc_usable_size, but I would say that 
to define that function is to implicitly accept the semantics of it as 
defined by the implementation you're trying to follow: otherwise, it 
seems to me as though you're implementing the function wrongly, 
intentionally violating the specification of the function as originally 
written.


And yes, I would also argue that this does indeed make it so that 
_FORTIFY_SOURCE=3 as currently implemented is wrong (as shown in 
https://www.openwall.com/lists/musl/2022/09/19/23), instead of 
malloc_usable_size being a useless function

Also, the previously cited e-mail ended up leading me to a glibc 
bugzilla issue, in which it looks as though glibc developers have 
explicitly stated they consider the value returned by malloc_usable_size 
to be validly usable as the object size corresponding to the pointer: 
https://sourceware.org/bugzilla/show_bug.cgi?id=24775#c6


>
> Moreover, it's not at all a stretch to say 7+ popular projects have
> gigantic UB they don't care to fix. The whole story of musl has been
> finding *hundreds* of such projects, and eventually getting lots of
> them fixed.
>
> Rich