Re: [PATCH][malloc] Avoid atomics in have_fastchunks

[Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>]

DJ Delorie wrote:
>
> I think the key here is to look at all accesses to that variable, and
> consider "what's the worst that could happen if the wrong value is there
> forever".  If the worst case doesn't counter the benefits, it's a net
> win.
>
> Buy my biggest concern is wondering how long a "wrong value" can persist
> and cause problems.

Note that the "wrong value" case exists in current GLIBC, even single-threaded.

The single-threaded case is a free that adds a chunk to the fastbin (which sets
have_fastchunks), then a malloc that reuses it (which leaves have_fastchunks
unchanged). If the next malloc is large it will call malloc_consolidate unnecessarily
when there are no actual chunks to consolidate. This is fine as have_fastchunks
is an approximation.

However since free is lock-free, there is no ordering constraint and all 4 possible
combinations of have_fastchunks and the fastbins being empty or not are 
possible in the multithreaded case. This could happen when some threads
execute free while another does malloc, so we end up racing the multiple writes
to have_fastchunks as well as the insertion into and emptying of the fastbins.

I guess the worst-case scenario would be several blocks being added to the
fast bins while have_fastchunks remains false. Then those blocks would not be
consolidated in subsequent mallocs until a later free sets have_fastchunks,
potentially increasing fragmentation. Best-case scenario is another call to
malloc_consolidate which has no effect.

Again this is what the existing code does before my patch - doing the updates to
have_fastchunks using the most constrained memory order does not change that.

Wilco