Re: [PATCH v2] malloc: Fix list_lock/arena lock deadlock [BZ #19182]

[Torvald Riegel <triegel at redhat dot com>]

On Mon, 2015-12-14 at 19:57 +0100, Florian Weimer wrote:
> On 12/11/2015 05:49 PM, Torvald Riegel wrote:
> > I would provide more detail on the synchronization of read-only
> > traversals of the list.  list_lock seems to be used to enforce mutual
> > exclusion between modification operations to the list (including
> > necessary reading/traversal of the list, so you can't go in without a
> > lock, figure out you need to change, and then grab list_lock).  For
> > traversal-only / write-op synchronization, atomic operations are used.
> > This is the reason why write ops do not need to use acquire fences when
> > traversing the list.  The acquire fences are missing in reused_arena,
> > and ptmalloc_[un]lock_all[2], it seems.
> 
> Yeah.  reused_arena also has a data race on the local static variable
> (and this one could actually be harmful).

The lack of acquire fences is harmful.  Or do you mean that this piece
of code might be more likely to cause code-generation-related problems
triggered by data races?

> > (Remember that if you want to use a synchronizes-with edge, there must
> > be a *pair* of release and acquire MOs -- just an release MO fence (or
> > atomic_write_barrier) is not sufficient.)
> 
> This is legacy code.  We need to backport this, and the system compiler
> (GCC 4.4) does not support memory ordering in the new way. :-(

We do have atomic_read_barrier, which seems to have been intended to be
equivalent to an acquire MO fence.  We also have atomic_forced_read that
can be used instead of atomic_load_relaxed.

> > I would also say "atomic ops" instead of barriers in the docs because we
> > have to use atomics there instead of plain accesses (although we don't
> > currently),
> 
> I can add a FIXME, but I don't want to move the documentation ahead of
> the code because that would just be confusing.

I think a FIXME would be good; we know there is a bug, so we should just
document that.

> >>  static mutex_t list_lock = _LIBC_LOCK_INITIALIZER;
> >>  static size_t narenas = 1;
> >> @@ -790,7 +792,16 @@ _int_new_arena (size_t size)
> >>    mutex_init (&a->mutex);
> >>    (void) mutex_lock (&a->mutex);
> >>  
> >> -  (void) mutex_lock (&list_lock);
> >> +  /* Put the arena in the global list.  If we cannot acquire
> >> +     list_lock, we have to temporarily release the arena lock, to
> >> +     avoid deadlocks.  NB: mutex_trylock returns 0 if the lock was
> >> +     acquired.  */
> >> +  bool reacquire_arena_lock = mutex_trylock (&list_lock);
> >> +  if (reacquire_arena_lock)
> >> +    {
> >> +      mutex_unlock (&a->mutex);
> >> +      (void) mutex_lock (&list_lock);
> >> +    }
> >>  
> >>    detach_arena (replaced_arena);
> >>  
> >> @@ -801,6 +812,9 @@ _int_new_arena (size_t size)
> >>  
> >>    (void) mutex_unlock (&list_lock);
> >>  
> >> +  if (reacquire_arena_lock)
> >> +    (void) mutex_lock (&a->mutex);
> >> +
> > 
> > Why can't we simply acquire a->mutex later?
> 
> Once a->mutex is on the global arena list, reused_arena can pick it (and
> will prefer it slightly) if its arena mutex is not acquired by another
> thread.

But this change can have both executions (ie, one that is equivalent to
acquiring later).  So either something is wrong there, or we can pick
the weaker option all the time.

I saw that you changed that bit in v3, but I want to point this out
nonetheless in case something else might be odd here.

> >> @@ -884,11 +898,22 @@ reused_arena (mstate avoid_arena)
> >>  
> >>  out:
> >>    {
> >> +    /* Update the arena thread attachment counters.  If we cannot
> >> +       acquire list_lock, we have to temporarily release the arena
> >> +       lock, to avoid deadlocks.  NB: mutex_trylock returns 0 if the
> >> +       lock was acquired.  */
> > 
> > Why can you temporarily release the lock?  Will the memory not be reused
> > for a different arena or something else?  The comment should explain
> > that as well or point to an existing comment.
> 
> Sharing arenas between different threads is not a problem because they
> are locked upon use.  If we release the lock temporarily, some other
> thread concurrently selecting its malloc arena is more likely to choose
> it (same thing as above).

I'm not sure whether my question came across, so let me ask again:  When
the lock is released temporarily, we still holds a pointer to the arena.
Until when we reacquire the lock, what can happen to the arena?  Can the
arena and it's memory be deleted or similar, and the memory be reused
for something else?

When a lock is temporarily released, then a few things can be the case.
First, the first and second critical section could be logically
unrelated.  Second, the program can re-confirm in the second critical
section that the world-view from the first critical section is still
correct, so it could have done stuff from the first section in the
second, informally.  Otherwise, why is breaking atomicity okay?  Is one
of the critical sections actually not necessary, or is there a bug?
Documenting the intent on this level would be useful for readers of this
code, I believe.