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

  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
  

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.