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

[Torvald Riegel <triegel at redhat dot com>]

On Wed, 2015-02-11 at 17:46 +0100, Leonhard Holz wrote:
> Am 11.02.2015 um 16:58 schrieb Torvald Riegel:
> > 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?
> >
> 
> Right, as long as every call to _int_malloc_ has the arena lock (which is the case 
> in the current code) everything is fine. But it seems odd to first aquire a lock 
> and afterwards use atomic operations

But it is necessary in the code, right?  There is still concurrency
between insertions to the free-list and removals.  The lock just makes
removals mutually exclusive.  (I'm not trying to say that the malloc
synchronization is ideal -- just that this isn't really odd in code that
uses both locks and atomics).

> and I think that the initial aim of the code 
> was to work lockless. See 
> https://sourceware.org/git/gitweb.cgi?p=glibc.git;a=blob;f=malloc/malloc.c;hb=425ce2edb9d11cc1ff650fac16dfbc450241896a#l3586

Maybe.  But there are other ways to handle it than DCAS.

> Yes, a different data structure could also be a way to go. Or maybe a spinlock for 
> the fastbin path instead of the mutex as the free-list insert & removal operations 
> are very fast. A way to avoid the complicated code for non-blocking concurrency 
> would be nice.

It would be convenient, and lock-based code can be very efficient -- but
I custom concurrent code using atomics and such does have its place, and
can be more efficient too.

For HW with HTM, a combination of transactions and a lock-based fallback
path might also be something that could work well in cases such as this
one.