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

[Rich Felker <dalias@libc.org>]

On Mon, Sep 19, 2022 at 11:02:16PM +0200, Gabriel Ravier wrote:
> 
> 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:

I don't think that's stupid; it's a very reasonable model.
Unfortunately it's one that's very hard to make the compiler aware of,
and if the compiler can't be aware of the possibility of the object
changing size, then it loses the ability to protect you from memory
errors without having this kind of "false positive".

Note that you can't just reason that "malloc_usable_size could
internally have called realloc" because the compiler can see that the
caller is still using the "old pointer", which is invalid, *even if
realloc returned a bitwise-identical pointer* (even just comparing to
see if it's equal is UB).

I don't know how to make any of this non-awful. Basically,
malloc_usable_size ties your hands with lots of unexpected
constraints. This function alone is almost solely responsible for the
musl inclusion/exclusion criteria policy for nonstandard extensions
being extremely cautious about adding dubious extensions even if they
"look harmless" at first -- we made the mistake of including it long
ago, and don't want to repeat that.

Rich