This is the mail archive of the mailing list for the glibc project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

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 and I think that the initial aim of the code was to work lockless. See;a=blob;f=malloc/malloc.c;hb=425ce2edb9d11cc1ff650fac16dfbc450241896a#l3586

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.

I agree.

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.

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.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]