[v3] malloc: Prevent arena free_list from turning cyclic [BZ #19048]
diff mbox

Message ID 56293B70.70108@redhat.com
State New
Headers show

Commit Message

Florian Weimer Oct. 22, 2015, 7:39 p.m. UTC
On 10/13/2015 01:31 PM, Florian Weimer wrote:
> On 10/09/2015 08:28 PM, Siddhesh Poyarekar wrote:
>> The only time a thread ever switches arenas is when it fails to allocate
>> on the earlier arena.  Also, what's hidden in the implementation is that
>> the switch always happens from the main arena to a non-main arena and
>> never in any other condition.  So you could consolidate the replacement
>> logic to just arena_get2 where you do tsd_setspecific (arena_key, NULL)
>> if avoid_arena is set and decrement the refcount on avoid_arena.
>> There's no other place where you want to detach from an arena.
>>
>> It makes no sense to stick to the avoided arena anyway because we failed
>> to allocate on that arena and if we don't find another arena either
>> through a free list or reused_arena, we will try mmap and if even that
>> fails, we fail allocation.
> 
> Thanks for your comments.  The code is difficult to follow (and it does
> not seem to do what some people expect it to do, it seems).  But I do
> not want to refactor it in a major way right now.
> 
> I believe I have addressed your comments in the attached patch.  I would
> really like to have a review of the pthread_atfork changes because these
> bits are really tricky.

I have rebased the attached patch to the current master, picking up the
TLS cleanup.

The test suite passes, but I have not tried this version on my Fedora
desktop yet.

Florian

Comments

Carlos O'Donell Oct. 28, 2015, 6:42 a.m. UTC | #1
On 10/22/2015 03:39 PM, Florian Weimer wrote:
> On 10/13/2015 01:31 PM, Florian Weimer wrote:
>> > On 10/09/2015 08:28 PM, Siddhesh Poyarekar wrote:
>>> >> The only time a thread ever switches arenas is when it fails to allocate
>>> >> on the earlier arena.  Also, what's hidden in the implementation is that
>>> >> the switch always happens from the main arena to a non-main arena and
>>> >> never in any other condition.  So you could consolidate the replacement
>>> >> logic to just arena_get2 where you do tsd_setspecific (arena_key, NULL)
>>> >> if avoid_arena is set and decrement the refcount on avoid_arena.
>>> >> There's no other place where you want to detach from an arena.
>>> >>
>>> >> It makes no sense to stick to the avoided arena anyway because we failed
>>> >> to allocate on that arena and if we don't find another arena either
>>> >> through a free list or reused_arena, we will try mmap and if even that
>>> >> fails, we fail allocation.
>> > 
>> > Thanks for your comments.  The code is difficult to follow (and it does
>> > not seem to do what some people expect it to do, it seems).  But I do
>> > not want to refactor it in a major way right now.
>> > 
>> > I believe I have addressed your comments in the attached patch.  I would
>> > really like to have a review of the pthread_atfork changes because these
>> > bits are really tricky.
> I have rebased the attached patch to the current master, picking up the
> TLS cleanup.
> 
> The test suite passes, but I have not tried this version on my Fedora
> desktop yet.

One nit.

See below.

OK with the nit fixed.

> 0001-malloc-Prevent-arena-free_list-from-turning-cyclic-B.patch
> 
> 
> 2015-10-22  Florian Weimer  <fweimer@redhat.com>
> 
> 	[BZ# 19048]
> 	* malloc/malloc.c (struct malloc_state): Update comment.  Add
> 	attached_threads member.
> 	(main_arena): Initialize attached_threads.
> 	* malloc/arena.c (list_lock): Update comment.
> 	(ptmalloc_lock_all, ptmalloc_unlock_all): Likewise.
> 	(ptmalloc_unlock_all2): Reinitialize arena reference counts.
> 	(deattach_arena): New function.
> 	(_int_new_arena): Initialize arena reference count and deattach
> 	replaced arena.
> 	(get_free_list, reused_arena): Update reference count and deattach
> 	replaced arena.
> 	(arena_thread_freeres): Update arena reference count and only put
> 	unreferenced arenas on the free list.
> 
> diff --git a/NEWS b/NEWS
> index 00e3b03..d4a7863 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -19,9 +19,9 @@ Version 2.23
>    18857, 18863, 18870, 18872, 18873, 18875, 18887, 18918, 18921, 18928,
>    18951, 18952, 18953, 18956, 18961, 18966, 18967, 18969, 18970, 18977,
>    18980, 18981, 18982, 18985, 19003, 19007, 19012, 19016, 19018, 19032,
> -  19046, 19049, 19050, 19059, 19071, 19074, 19076, 19077, 19078, 19079,
> -  19085, 19086, 19088, 19094, 19095, 19124, 19125, 19129, 19134, 19137,
> -  19156.
> +  19046, 19048, 19049, 19050, 19059, 19071, 19074, 19076, 19077, 19078,
> +  19079, 19085, 19086, 19088, 19094, 19095, 19124, 19125, 19129, 19134,
> +  19137, 19156.

Please keep NEWS out of the diff. It makes it easier to use cli pwclient
to fetch and apply patch without needing a merge driver. We'll soon do away
with this requirement by automating the generation of the list from bugzilla.

Should we add a NEWS item to highlight the behavioural change in malloc?

>  
>  * There is now a --disable-timezone-tools configure option for disabling the
>    building and installing of the timezone related utilities (zic, zdump, and
> diff --git a/malloc/arena.c b/malloc/arena.c
> index caf718d..aa69923 100644
> --- a/malloc/arena.c
> +++ b/malloc/arena.c
> @@ -68,7 +68,10 @@ extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
>  
>  static __thread mstate thread_arena attribute_tls_model_ie;
>  
> -/* Arena free list.  */
> +/* 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.  */

OK.

>  
>  static mutex_t list_lock = MUTEX_INITIALIZER;
>  static size_t narenas = 1;
> @@ -225,7 +228,10 @@ ptmalloc_lock_all (void)
>    save_free_hook = __free_hook;
>    __malloc_hook = malloc_atfork;
>    __free_hook = free_atfork;
> -  /* Only the current thread may perform malloc/free calls now. */
> +  /* Only the current thread may perform malloc/free calls now.
> +     save_arena will be reattached to the current thread, in
> +     ptmalloc_lock_all, so save_arena->attached_threads is not
> +     updated.  */

OK.

>    save_arena = thread_arena;
>    thread_arena = ATFORK_ARENA_PTR;
>  out:
> @@ -243,6 +249,9 @@ ptmalloc_unlock_all (void)
>    if (--atfork_recursive_cntr != 0)
>      return;
>  
> +  /* Replace ATFORK_ARENA_PTR with save_arena.
> +     save_arena->attached_threads was not changed in ptmalloc_lock_all
> +     and is still correct.  */

OK.

>    thread_arena = save_arena;
>    __malloc_hook = save_malloc_hook;
>    __free_hook = save_free_hook;
> @@ -274,12 +283,19 @@ ptmalloc_unlock_all2 (void)
>    thread_arena = save_arena;
>    __malloc_hook = save_malloc_hook;
>    __free_hook = save_free_hook;
> +
> +  /* Push all arenas to the free list, except save_arena, which is
> +     attached to the current thread.  */
> +  if (save_arena != NULL)
> +    ((mstate) save_arena)->attached_threads = 1;

OK.

>    free_list = NULL;
>    for (ar_ptr = &main_arena;; )
>      {
>        mutex_init (&ar_ptr->mutex);
>        if (ar_ptr != save_arena)
>          {
> +	  /* This arena is no longer attached to any thread.  */
> +	  ar_ptr->attached_threads = 0;

OK.

>            ar_ptr->next_free = free_list;
>            free_list = ar_ptr;
>          }
> @@ -718,6 +734,22 @@ 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.  */
> +static void
> +detach_arena (mstate replaced_arena)
> +{
> +  if (replaced_arena != NULL)
> +    {
> +      assert (replaced_arena->attached_threads > 0);
> +      /* The current implementation only detaches from main_arena in
> +	 case of allocation failure.  This means that it is likely not
> +	 beneficial to put the arena on free_list even if the
> +	 reference count reaches zero.  */
> +      --replaced_arena->attached_threads;
> +    }
> +}

OK.

> +
>  static mstate
>  _int_new_arena (size_t size)
>  {
> @@ -739,6 +771,7 @@ _int_new_arena (size_t size)
>      }
>    a = h->ar_ptr = (mstate) (h + 1);
>    malloc_init_state (a);
> +  a->attached_threads = 1;
>    /*a->next = NULL;*/
>    a->system_mem = a->max_system_mem = h->size;
>    arena_mem += h->size;
> @@ -752,12 +785,15 @@ _int_new_arena (size_t size)
>    set_head (top (a), (((char *) h + h->size) - ptr) | PREV_INUSE);
>  
>    LIBC_PROBE (memory_arena_new, 2, a, 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);
> +

OK.

>    /* Add the new arena to the global list.  */
>    a->next = main_arena.next;
>    atomic_write_barrier ();
> @@ -772,13 +808,24 @@ _int_new_arena (size_t size)
>  static mstate
>  get_free_list (void)
>  {
> +  mstate replaced_arena = thread_arena;
>    mstate result = free_list;
>    if (result != NULL)
>      {
>        (void) mutex_lock (&list_lock);
>        result = free_list;
>        if (result != NULL)
> -        free_list = result->next_free;
> +	{
> +	  free_list = result->next_free;
> +
> +	  /* Arenas on the free list are not attached to any thread.  */
> +	  assert (result->attached_threads == 0);
> +	  /* But the arena will now be attached to this thread.  */
> +	  result->attached_threads = 1;
> +
> +	  if (result != NULL)
> +	    detach_arena (replaced_arena);

Why check `result != NULL`?

if (replaced_arena != NULL)
  detach_arena (replaced_arena);

?

I wouldn't expect thread_arena to ever be NULL, so it seems
like we should be able to just write:

deatch_arena (replaced_arena);

and be done.

> +	}
>        (void) mutex_unlock (&list_lock);
>  
>        if (result != NULL)
> @@ -837,6 +884,14 @@ reused_arena (mstate avoid_arena)
>    (void) mutex_lock (&result->mutex);
>  
>  out:
> +  {
> +    mstate replaced_arena = thread_arena;
> +    (void) mutex_lock (&list_lock);
> +    detach_arena (replaced_arena);
> +    ++result->attached_threads;
> +    (void) mutex_unlock (&list_lock);

OK.

> +  }
> +
>    LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
>    thread_arena = result;
>    next_to_use = result->next;
> @@ -931,8 +986,14 @@ arena_thread_freeres (void)
>    if (a != NULL)
>      {
>        (void) mutex_lock (&list_lock);
> -      a->next_free = free_list;
> -      free_list = a;
> +      /* If this was the last attached thread for this arena, put the
> +	 arena on the free list.  */
> +      assert (a->attached_threads > 0);
> +      if (--a->attached_threads == 0)
> +	{
> +	  a->next_free = free_list;
> +	  free_list = a;
> +	}

OK.

>        (void) mutex_unlock (&list_lock);
>      }
>  }
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 9371b5a..35c8863 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -1709,9 +1709,15 @@ struct malloc_state
>    /* Linked list */
>    struct malloc_state *next;
>  
> -  /* Linked list for free arenas.  */
> +  /* Linked list for free arenas.  Access to this field is serialized
> +     by 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.  */
> +  INTERNAL_SIZE_T attached_threads;

OK.

> +
>    /* Memory allocated from the system in this arena.  */
>    INTERNAL_SIZE_T system_mem;
>    INTERNAL_SIZE_T max_system_mem;
> @@ -1755,7 +1761,8 @@ struct malloc_par
>  static struct malloc_state main_arena =
>  {
>    .mutex = MUTEX_INITIALIZER,
> -  .next = &main_arena
> +  .next = &main_arena,
> +  .attached_threads = 1

OK.

>  };
>  
>  /* There is only one instance of the malloc parameters.  */
> -- 2.4.3

Cheers,
Carlos.

Patch
diff mbox

2015-10-22  Florian Weimer  <fweimer@redhat.com>

	[BZ# 19048]
	* malloc/malloc.c (struct malloc_state): Update comment.  Add
	attached_threads member.
	(main_arena): Initialize attached_threads.
	* malloc/arena.c (list_lock): Update comment.
	(ptmalloc_lock_all, ptmalloc_unlock_all): Likewise.
	(ptmalloc_unlock_all2): Reinitialize arena reference counts.
	(deattach_arena): New function.
	(_int_new_arena): Initialize arena reference count and deattach
	replaced arena.
	(get_free_list, reused_arena): Update reference count and deattach
	replaced arena.
	(arena_thread_freeres): Update arena reference count and only put
	unreferenced arenas on the free list.

diff --git a/NEWS b/NEWS
index 00e3b03..d4a7863 100644
--- a/NEWS
+++ b/NEWS
@@ -19,9 +19,9 @@  Version 2.23
   18857, 18863, 18870, 18872, 18873, 18875, 18887, 18918, 18921, 18928,
   18951, 18952, 18953, 18956, 18961, 18966, 18967, 18969, 18970, 18977,
   18980, 18981, 18982, 18985, 19003, 19007, 19012, 19016, 19018, 19032,
-  19046, 19049, 19050, 19059, 19071, 19074, 19076, 19077, 19078, 19079,
-  19085, 19086, 19088, 19094, 19095, 19124, 19125, 19129, 19134, 19137,
-  19156.
+  19046, 19048, 19049, 19050, 19059, 19071, 19074, 19076, 19077, 19078,
+  19079, 19085, 19086, 19088, 19094, 19095, 19124, 19125, 19129, 19134,
+  19137, 19156.
 
 * There is now a --disable-timezone-tools configure option for disabling the
   building and installing of the timezone related utilities (zic, zdump, and
diff --git a/malloc/arena.c b/malloc/arena.c
index caf718d..aa69923 100644
--- a/malloc/arena.c
+++ b/malloc/arena.c
@@ -68,7 +68,10 @@  extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
 
 static __thread mstate thread_arena attribute_tls_model_ie;
 
-/* Arena free list.  */
+/* 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.  */
 
 static mutex_t list_lock = MUTEX_INITIALIZER;
 static size_t narenas = 1;
@@ -225,7 +228,10 @@  ptmalloc_lock_all (void)
   save_free_hook = __free_hook;
   __malloc_hook = malloc_atfork;
   __free_hook = free_atfork;
-  /* Only the current thread may perform malloc/free calls now. */
+  /* Only the current thread may perform malloc/free calls now.
+     save_arena will be reattached to the current thread, in
+     ptmalloc_lock_all, so save_arena->attached_threads is not
+     updated.  */
   save_arena = thread_arena;
   thread_arena = ATFORK_ARENA_PTR;
 out:
@@ -243,6 +249,9 @@  ptmalloc_unlock_all (void)
   if (--atfork_recursive_cntr != 0)
     return;
 
+  /* Replace ATFORK_ARENA_PTR with save_arena.
+     save_arena->attached_threads was not changed in ptmalloc_lock_all
+     and is still correct.  */
   thread_arena = save_arena;
   __malloc_hook = save_malloc_hook;
   __free_hook = save_free_hook;
@@ -274,12 +283,19 @@  ptmalloc_unlock_all2 (void)
   thread_arena = save_arena;
   __malloc_hook = save_malloc_hook;
   __free_hook = save_free_hook;
+
+  /* Push all arenas to the free list, except save_arena, which is
+     attached to the current thread.  */
+  if (save_arena != NULL)
+    ((mstate) save_arena)->attached_threads = 1;
   free_list = NULL;
   for (ar_ptr = &main_arena;; )
     {
       mutex_init (&ar_ptr->mutex);
       if (ar_ptr != save_arena)
         {
+	  /* This arena is no longer attached to any thread.  */
+	  ar_ptr->attached_threads = 0;
           ar_ptr->next_free = free_list;
           free_list = ar_ptr;
         }
@@ -718,6 +734,22 @@  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.  */
+static void
+detach_arena (mstate replaced_arena)
+{
+  if (replaced_arena != NULL)
+    {
+      assert (replaced_arena->attached_threads > 0);
+      /* The current implementation only detaches from main_arena in
+	 case of allocation failure.  This means that it is likely not
+	 beneficial to put the arena on free_list even if the
+	 reference count reaches zero.  */
+      --replaced_arena->attached_threads;
+    }
+}
+
 static mstate
 _int_new_arena (size_t size)
 {
@@ -739,6 +771,7 @@  _int_new_arena (size_t size)
     }
   a = h->ar_ptr = (mstate) (h + 1);
   malloc_init_state (a);
+  a->attached_threads = 1;
   /*a->next = NULL;*/
   a->system_mem = a->max_system_mem = h->size;
   arena_mem += h->size;
@@ -752,12 +785,15 @@  _int_new_arena (size_t size)
   set_head (top (a), (((char *) h + h->size) - ptr) | PREV_INUSE);
 
   LIBC_PROBE (memory_arena_new, 2, a, 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 ();
@@ -772,13 +808,24 @@  _int_new_arena (size_t size)
 static mstate
 get_free_list (void)
 {
+  mstate replaced_arena = thread_arena;
   mstate result = free_list;
   if (result != NULL)
     {
       (void) mutex_lock (&list_lock);
       result = free_list;
       if (result != NULL)
-        free_list = result->next_free;
+	{
+	  free_list = result->next_free;
+
+	  /* Arenas on the free list are not attached to any thread.  */
+	  assert (result->attached_threads == 0);
+	  /* But the arena will now be attached to this thread.  */
+	  result->attached_threads = 1;
+
+	  if (result != NULL)
+	    detach_arena (replaced_arena);
+	}
       (void) mutex_unlock (&list_lock);
 
       if (result != NULL)
@@ -837,6 +884,14 @@  reused_arena (mstate avoid_arena)
   (void) mutex_lock (&result->mutex);
 
 out:
+  {
+    mstate replaced_arena = thread_arena;
+    (void) mutex_lock (&list_lock);
+    detach_arena (replaced_arena);
+    ++result->attached_threads;
+    (void) mutex_unlock (&list_lock);
+  }
+
   LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
   thread_arena = result;
   next_to_use = result->next;
@@ -931,8 +986,14 @@  arena_thread_freeres (void)
   if (a != NULL)
     {
       (void) mutex_lock (&list_lock);
-      a->next_free = free_list;
-      free_list = a;
+      /* If this was the last attached thread for this arena, put the
+	 arena on the free list.  */
+      assert (a->attached_threads > 0);
+      if (--a->attached_threads == 0)
+	{
+	  a->next_free = free_list;
+	  free_list = a;
+	}
       (void) mutex_unlock (&list_lock);
     }
 }
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 9371b5a..35c8863 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -1709,9 +1709,15 @@  struct malloc_state
   /* Linked list */
   struct malloc_state *next;
 
-  /* Linked list for free arenas.  */
+  /* Linked list for free arenas.  Access to this field is serialized
+     by 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.  */
+  INTERNAL_SIZE_T attached_threads;
+
   /* Memory allocated from the system in this arena.  */
   INTERNAL_SIZE_T system_mem;
   INTERNAL_SIZE_T max_system_mem;
@@ -1755,7 +1761,8 @@  struct malloc_par
 static struct malloc_state main_arena =
 {
   .mutex = MUTEX_INITIALIZER,
-  .next = &main_arena
+  .next = &main_arena,
+  .attached_threads = 1
 };
 
 /* There is only one instance of the malloc parameters.  */
-- 
2.4.3