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

[Florian Weimer <fweimer at redhat dot com>]

On 12/17/2015 08:26 PM, Torvald Riegel wrote:
> 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?

I'm worried that the exit condition used for the loop does not trigger
reliably and that two or more threads could loop endlessly in
reused_arena.  I don't know if it can happen in practice.

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

The attached version of the patch points out the data races I know of.
I also adjusted the comments in struct malloc_state in malloc.c.

> 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?

Arenas are allocated once and then stick around until the process exits.

The locking during arena selection is only there to select an
uncontended arena.  Releasing an arena lock and reacquiring it changes
the way arenas are selected and means that another thread is more likely
to select the same arena.

I'm not sure why we even perform arena selection in parallel.  The risk
is that the lock probing detects the additional selection process, but
not actual arena usage (for which the acquired lock might be a poor
indicator anyway).

Anyway, with the introduction of free_list_lock, we no longer need to
temporarily release the arena lock, which simplifies thing.

Florian

From aac1d62e6c41044cc90ec6e519083205a45b5846 Mon Sep 17 00:00:00 2001
Message-Id: <aac1d62e6c41044cc90ec6e519083205a45b5846.1450445849.git.fweimer@redhat.com>
From: Florian Weimer <fweimer@redhat.com>
Date: Fri, 18 Dec 2015 14:37:13 +0100
Subject: [PATCH] malloc: Fix list_lock/arena lock deadlock [BZ #19182]
To: libc-alpha@sourceware.org

---
 ChangeLog       | 19 +++++++++++++++++
 malloc/arena.c  | 66 ++++++++++++++++++++++++++++++++++++++++++++-------------
 malloc/malloc.c |  6 +++---
 3 files changed, 73 insertions(+), 18 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 65d3c89..acbdf1e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,22 @@
+2015-12-18  Florian Weimer  <fweimer@redhat.com>
+
+	[BZ #19182]
+	* malloc/arena.c (list_lock): Document lock ordering requirements.
+	(free_list_lock): New lock.
+	(ptmalloc_lock_all): Comment on free_list_lock.
+	(ptmalloc_unlock_all2): Reinitialize free_list_lock.
+	(detach_arena): Update comment.  free_list_lock is now needed.
+	(_int_new_arena): Use free_list_lock around detach_arena call.
+	Acquire arena lock after list_lock.  Add comment, including FIXME
+	about incorrect synchronization.
+	(get_free_list): Switch to free_list_lock.
+	(reused_arena): Acquire free_list_lock around detach_arena call
+	and attached threads counter update.  Add two FIXMEs about
+	incorrect synchronization.
+	(arena_thread_freeres): Switch to free_list_lock.
+	* malloc/malloc.c (struct malloc_state): Update comments to
+	mention free_list_lock.
+
 2015-12-18  Torvald Riegel  <triegel@redhat.com>
 
 	* math/atest-exp2.c (mp_exp_m1): Remove.
diff --git a/malloc/arena.c b/malloc/arena.c
index 73bda84..85f1194 100644
--- a/malloc/arena.c
+++ b/malloc/arena.c
@@ -68,15 +68,28 @@ extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
 
 static __thread mstate thread_arena attribute_tls_model_ie;
 
-/* Arena free list.  list_lock protects the free_list variable below,
-   and the next_free and attached_threads members of the mstate
-   objects.  No other (malloc) locks must be taken while list_lock is
-   active, otherwise deadlocks may occur.  */
+/* Arena free list.  free_list_lock synchronizes access to the
+   free_list variable below, and the next_free and attached_threads
+   members of struct malloc_state objects.  No other locks must be
+   acquired after free_list_lock has been acquired.  */
 
-static mutex_t list_lock = _LIBC_LOCK_INITIALIZER;
+static mutex_t free_list_lock = _LIBC_LOCK_INITIALIZER;
 static size_t narenas = 1;
 static mstate free_list;
 
+/* list_lock prevents concurrent writes to the next member of struct
+   malloc_state objects.
+
+   Read access to the next member is supposed to synchronize with the
+   atomic_write_barrier and the write to the next member in
+   _int_new_arena.  This suffers from data races; see the FIXME
+   comments in _int_new_arena and reused_arena.
+
+   list_lock also prevents concurrent forks.  When list_lock is
+   acquired, no arena lock must be acquired, but it is permitted to
+   acquire arena locks after list_lock.  */
+static mutex_t list_lock = _LIBC_LOCK_INITIALIZER;
+
 /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
 static unsigned long arena_mem;
 
@@ -207,6 +220,9 @@ ptmalloc_lock_all (void)
   if (__malloc_initialized < 1)
     return;
 
+  /* We do not acquire free_list_lock here because we completely
+     reconstruct free_list in ptmalloc_unlock_all2.  */
+
   if (mutex_trylock (&list_lock))
     {
       if (thread_arena == ATFORK_ARENA_PTR)
@@ -286,6 +302,7 @@ ptmalloc_unlock_all2 (void)
 
   /* Push all arenas to the free list, except save_arena, which is
      attached to the current thread.  */
+  mutex_init (&free_list_lock);
   if (save_arena != NULL)
     ((mstate) save_arena)->attached_threads = 1;
   free_list = NULL;
@@ -303,6 +320,7 @@ ptmalloc_unlock_all2 (void)
       if (ar_ptr == &main_arena)
         break;
     }
+
   mutex_init (&list_lock);
   atfork_recursive_cntr = 0;
 }
@@ -735,7 +753,7 @@ heap_trim (heap_info *heap, size_t pad)
 /* Create a new arena with initial size "size".  */
 
 /* If REPLACED_ARENA is not NULL, detach it from this thread.  Must be
-   called while list_lock is held.  */
+   called while free_list_lock is held.  */
 static void
 detach_arena (mstate replaced_arena)
 {
@@ -788,19 +806,34 @@ _int_new_arena (size_t size)
   mstate replaced_arena = thread_arena;
   thread_arena = a;
   mutex_init (&a->mutex);
-  (void) mutex_lock (&a->mutex);
 
   (void) mutex_lock (&list_lock);
 
-  detach_arena (replaced_arena);
-
   /* Add the new arena to the global list.  */
   a->next = main_arena.next;
+  /* FIXME: The barrier is an attempt to synchronize with read access
+     in reused_arena, which does not acquire list_lock while
+     traversing the list.  */
   atomic_write_barrier ();
   main_arena.next = a;
 
   (void) mutex_unlock (&list_lock);
 
+  (void) mutex_lock (&free_list_lock);
+  detach_arena (replaced_arena);
+  (void) mutex_unlock (&free_list_lock);
+
+  /* Lock this arena.  NB: Another thread may have been attached to
+     this arena because the arena is now accessible from the
+     main_arena.next list and could have been picked by reused_arena.
+     This can only happen for the last arena created (before the arena
+     limit is reached).  At this point, some arena has to be attached
+     to two threads.  We could acquire the arena lock before list_lock
+     to make it less likely that reused_arena picks this new arena,
+     but this could result in a deadlock with ptmalloc_lock_all.  */
+
+  (void) mutex_lock (&a->mutex);
+
   return a;
 }
 
@@ -814,7 +847,7 @@ get_free_list (void)
   mstate result = free_list;
   if (result != NULL)
     {
-      (void) mutex_lock (&list_lock);
+      (void) mutex_lock (&free_list_lock);
       result = free_list;
       if (result != NULL)
 	{
@@ -825,7 +858,7 @@ get_free_list (void)
 
 	  detach_arena (replaced_arena);
 	}
-      (void) mutex_unlock (&list_lock);
+      (void) mutex_unlock (&free_list_lock);
 
       if (result != NULL)
         {
@@ -845,6 +878,7 @@ static mstate
 reused_arena (mstate avoid_arena)
 {
   mstate result;
+  /* FIXME: Access to next_to_use suffers from data races.  */
   static mstate next_to_use;
   if (next_to_use == NULL)
     next_to_use = &main_arena;
@@ -857,6 +891,7 @@ reused_arena (mstate avoid_arena)
       if (!arena_is_corrupt (result) && !mutex_trylock (&result->mutex))
         goto out;
 
+      /* FIXME: This is a data race, see _int_new_arena.  */
       result = result->next;
     }
   while (result != next_to_use);
@@ -888,11 +923,12 @@ out:
   /* Attach the arena to the current thread.  Note that we may have
      selected an arena which was on free_list.  */
   {
+    /* Update the arena thread attachment counters.   */
     mstate replaced_arena = thread_arena;
-    (void) mutex_lock (&list_lock);
+    (void) mutex_lock (&free_list_lock);
     detach_arena (replaced_arena);
     ++result->attached_threads;
-    (void) mutex_unlock (&list_lock);
+    (void) mutex_unlock (&free_list_lock);
   }
 
   LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
@@ -988,7 +1024,7 @@ arena_thread_freeres (void)
 
   if (a != NULL)
     {
-      (void) mutex_lock (&list_lock);
+      (void) mutex_lock (&free_list_lock);
       /* If this was the last attached thread for this arena, put the
 	 arena on the free list.  */
       assert (a->attached_threads > 0);
@@ -997,7 +1033,7 @@ arena_thread_freeres (void)
 	  a->next_free = free_list;
 	  free_list = a;
 	}
-      (void) mutex_unlock (&list_lock);
+      (void) mutex_unlock (&free_list_lock);
     }
 }
 text_set_element (__libc_thread_subfreeres, arena_thread_freeres);
diff --git a/malloc/malloc.c b/malloc/malloc.c
index a030109..1a03079 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -1710,12 +1710,12 @@ struct malloc_state
   struct malloc_state *next;
 
   /* Linked list for free arenas.  Access to this field is serialized
-     by list_lock in arena.c.  */
+     by free_list_lock in arena.c.  */
   struct malloc_state *next_free;
 
   /* Number of threads attached to this arena.  0 if the arena is on
-     the free list.  Access to this field is serialized by list_lock
-     in arena.c.  */
+     the free list.  Access to this field is serialized by
+     free_list_lock in arena.c.  */
   INTERNAL_SIZE_T attached_threads;
 
   /* Memory allocated from the system in this arena.  */
-- 
2.4.3