From cdecfd781b74b591612cb11d698acbccf5227cb3 Mon Sep 17 00:00:00 2001
Message-Id: <cdecfd781b74b591612cb11d698acbccf5227cb3.1450181230.git.fweimer@redhat.com>
From: Florian Weimer <fweimer@redhat.com>
Date: Tue, 15 Dec 2015 13:06:51 +0100
Subject: [PATCH] malloc: Fix list_lock/arena lock deadlock [BZ #19182]
To: libc-alpha@sourceware.org

---
 ChangeLog      | 15 +++++++++++++++
 malloc/arena.c | 54 +++++++++++++++++++++++++++++++++++++++---------------
 2 files changed, 54 insertions(+), 15 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 3b1750c..f769a4d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,20 @@
 2015-12-15  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.
+	(get_free_list): Switch to free_list_lock.
+	(reused_arena): Acquire free_list_lock around detach_arena call
+	and attached threads counter update.
+	(arena_thread_freeres): Switch to free_list_lock.
+
+2015-12-15  Florian Weimer  <fweimer@redhat.com>
+
 	* dlfcn/tst-rec-dlopen.c (call_func): Cast dlsym result, fixing an
 	aliasing violation.
 
diff --git a/malloc/arena.c b/malloc/arena.c
index 3dab7bb..a84bb22 100644
--- a/malloc/arena.c
+++ b/malloc/arena.c
@@ -68,15 +68,23 @@ 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
+   synchronized via atomic_full_barrier before the write in
+   _int_new_arena.)  list_lock also prevents concurrenct 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 +215,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 +297,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 +315,7 @@ ptmalloc_unlock_all2 (void)
       if (ar_ptr == &main_arena)
         break;
     }
+
   mutex_init (&list_lock);
   atfork_recursive_cntr = 0;
 }
@@ -735,7 +748,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,12 +801,9 @@ _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;
   atomic_write_barrier ();
@@ -801,6 +811,19 @@ _int_new_arena (size_t size)
 
   (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: We may not have exclusive access to this
+     arena anymore because the arena is now accessible from the
+     main_arena.next list and could have been picked by reused_arena
+     in the meantime.  This can only happen for the last arena created
+     (before the arena limit is reached).  This seems unlikely, so we
+     do not protect against this special case.  */
+
+  (void) mutex_lock (&a->mutex);
+
   return a;
 }
 
@@ -812,7 +835,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 +848,7 @@ get_free_list (void)
 
 	  detach_arena (replaced_arena);
 	}
-      (void) mutex_unlock (&list_lock);
+      (void) mutex_unlock (&free_list_lock);
 
       if (result != NULL)
         {
@@ -884,11 +907,12 @@ reused_arena (mstate avoid_arena)
 
 out:
   {
+    /* 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);
@@ -984,7 +1008,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);
@@ -993,7 +1017,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);
-- 
2.4.3

