RFC: malloc fastbin concurrency bug

[DJ Delorie]

Wilco Dijkstra <Wilco.Dijkstra@arm.com> writes:
> The fastbin code in _int_malloc seems to have an ABA concurrency bug.
> Basically it does 2 racy reads of the fastbin head and next pointer, then
> uses a compare-exchange to verify the fastbin head was the right one.
> However that ignores that the next pointer may have changed inbetween:
>
> victim = *fb;                  // racy read of fastbin head
> pp = REVEAL_PTR (victim->fd);  // racy read of next pointer
> // another thread may make changes to fb and *fb->next at this point
> if (atomic_compare_exchange_acquire (fb, &victim, pp))
>    // here we have verified the racy read of fb was indeed correct
>    // but the next pointer pp may still have changed inbetween!
>
> The victim's next pointer may be changed if another thread pops off victim
> and pushes victim again with a different next pointer before the compare-
> exchange.

The code above is itself inside the lock taken by __libc_malloc; the
only code I see that touches fastbins outside an arena lock is in
_int_free, which only adds chunks to the fastbins, and it sets ->fd
before putting it on the list.

So, I think your "pops off then pushes" scenario can't happen, the only
race outside the lock is for pushing, which is what the atomic
compare-exchange is for.

If I'm wrong (heh, "if" he says ;) then please point out where in the
code the extra pop could happen, and specifically where the race could
come from, because I don't see it...

> I'm wondering whether there is an easy fix for this - we could check that
> pp == REVEAL_PTR (victim->fd) but if that fails we have corrupted the
> fastbin list already, so we crash... Any ideas?

We'd have to atomically read and write all fastbin data (for starters)
or put all fastbin accesses inside a lock.  Both have serious
performance considerations.