Re: [PATCH] Remove atomic operations from malloc.c

[Torvald Riegel <triegel at redhat dot com>]

On Wed, 2015-02-11 at 09:30 +0100, Leonhard Holz wrote:
> The fastbin path of malloc/free features atomic operations, which were probably an 
> attempt for lock-free code. But there is an ABA problem in malloc's
> 
> while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
>          != victim);
> 
> because even if *fd == victim, victim->fd might have changed in the meantime. 

I agree that this would be prone to ABA under memory reuse and
concurrent removals from the free-list; also, it would likely lack a
memory barrier in the load of victim (so that loading ->fd actually sees
the right data).

However, I haven't see a case of concurrent free-list removal; all calls
to _int_malloc seem to happen while the (non-recursive, AFAICT) arena
lock is acquired.  I'm not really familiar with the malloc code, so
maybe I've missed something.  If you are aware of such concurrency, can
you point me to it?

If we don't have concurrent removals, concurrent additions to the
free-list should be fine.  Nobody can remove an element from the
free-list, so we "own" every element in the free-list.  If concurrent
_int_free adds elements to it, that doesn't matter, the memory of
everything in the free-list can't be reused, so we don't hit the ABA.

If you agree with this analysis, I'd still encourage you to send a patch
with documentation explaining this.

> There is no easy way to fix this, an old comment mentions the need for a CAS2 
> operation with tagged pointers. Consequently malloc is right now wrapped by a lock 
> to avoid problems.

I agree that allowing concurrent removal from the free-list would be
difficult.  It's not impossible to do something there, but it would be
complex.  For example, hazard pointers for users of the arena, or an
obstruction-free free-list would be possibilities (it doesn't have to
really be a list or a stack as right now, it just needs to be a bag of
free stuff).

However, I'm not familiar enough with malloc and it's performance
properties to make a concrete suggestion.