diff mbox

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

Message ID 56740C24.90901@redhat.com
State New
Headers show

Commit Message

Florian Weimer Dec. 18, 2015, 1:37 p.m. UTC 
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

Comments

Torvald Riegel Dec. 21, 2015, 3:21 p.m. UTC | #1 
On Fri, 2015-12-18 at 14:37 +0100, Florian Weimer wrote:
> 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 eventually, a thread would pick up the most recent values and
given that the arena's stick around forever, the list navigation bug
might not lead to an error.  However, when a new arena is added, a
thread may read unitialized values for the elements of the arena struct
(because the pointer to the arena is published with mo_release but not
read with mo_acquire).

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

OK.  The changes should be enough to make the issue stand out.

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

Okay, that's important, and it seems to be required for correctness.

> 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).

Agreed, based on your description of the situation.

Overall, this patch looks good to me.  Thanks!
Carlos O'Donell Dec. 21, 2015, 9:54 p.m. UTC | #2 
Florian,

One quibble.

On 12/18/2015 08:37 AM, Florian Weimer wrote:
> 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.  */

This last sentence seems ambiguous to me. I assume you mean to say that
at the point at which list_lock is acquired there are no other arena
locks held, but that after list_lock is acquired, other arena locks may
be acquired afterwards?

In which case the sentence should end with ".. arena locks after list_lock
is acquired." which clarifies the sentence a bit more.

Cheers,
Carlos.
Florian Weimer Dec. 22, 2015, 7:32 p.m. UTC | #3 
On 12/21/2015 10:54 PM, Carlos O'Donell wrote:

>> +   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.  */
> 
> This last sentence seems ambiguous to me. I assume you mean to say that
> at the point at which list_lock is acquired there are no other arena
> locks held, but that after list_lock is acquired, other arena locks may
> be acquired afterwards?

That was my intent.  Is this clearer?

  list_lock also prevents concurrent forks.  At the time list_lock is
  acquired, no arena lock must have been acquired, but it is permitted
  to acquire arena locks subsequently, while list_lock is acquired.

I'm following Torvald's earlier guidance not to speak of “held” locks.

Florian
Carlos O'Donell Dec. 22, 2015, 8:16 p.m. UTC | #4 
On 12/22/2015 02:32 PM, Florian Weimer wrote:
> On 12/21/2015 10:54 PM, Carlos O'Donell wrote:
> 
>>> +   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.  */
>>
>> This last sentence seems ambiguous to me. I assume you mean to say that
>> at the point at which list_lock is acquired there are no other arena
>> locks held, but that after list_lock is acquired, other arena locks may
>> be acquired afterwards?
> 
> That was my intent.  Is this clearer?
> 
>   list_lock also prevents concurrent forks.  At the time list_lock is
>   acquired, no arena lock must have been acquired, but it is permitted
>   to acquire arena locks subsequently, while list_lock is acquired.
> 
> I'm following Torvald's earlier guidance not to speak of “held” locks.

Looks good to me.

Cheers,
Carlos.
diff mbox

Patch

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