Re: What's wrong with musl's malloc

[Rich Felker <dalias@libc.org>]

On Sat, Apr 21, 2018 at 01:28:12AM -0400, Rich Felker wrote:
> One protocol that might work:
> 
> When locking multiple bins, they must be locked in decreasing order.
> 
> For malloc, this is the natural thing to do -- the bin you return the
> excess to will be the same or smaller than the bin you allocate from.
> 
> For free, take the freelock from the beginning, rather than just
> momentarily at the end. Then you know the bin sizes you'll be working
                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> with (up to at most 3 -- self, prev, and next) and can lock them in
  ^^^^^^^^^^^^^^^^^^^^^

I don't think this is actually quite correct. A concurrent malloc
could consume part of either of the adjacent free chunks. It's okay if
it consumes the whole thing, but if it only consumes part, you'll end
up with a new adjacent free chunk of a different size (different bin).

Of course loop-and-retry is an option but doesn't seem like a good
one; the retry time could be unbounded.

Not sure if this is salvagable or not. Problems like this keep
pointing in the direction of wanting to lock chunks (via their
header/footer) rather than locking just bins. On the plus side it's
much finer-grained locking and MT-friendly. Unfortunately it's also
more complex and might have more fixed overhead.

Rich