From patchwork Fri Dec 18 13:37:40 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 558879 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 762F314017E for ; Sat, 19 Dec 2015 00:37:52 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b=tTgFUfoA; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:references:cc:from:message-id:date :mime-version:in-reply-to:content-type; q=dns; s=default; b=Fivx VutjG1FYB4gFw4rBa+nZeymtK1iI8UN3z8OFMrMnqxjsXA8D2rINaVJmhxrJUTMe mZqBresoJ/IXYQjxhFbwIln8xYZWcAdDuPAv0UEvOt3SslB73jtavULPjP6uMEJv MPZiSv0Zr++0bytqzZ0TfFa6lZCr9MB9G2Gzwus= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:references:cc:from:message-id:date :mime-version:in-reply-to:content-type; s=default; bh=mNyNBYY0VD sHZvWtvXqWKozEKzs=; b=tTgFUfoAs75rtib07D6OTh50Tick+ewqy7F9OsIloA TRVFnMgicnFi3h5acdqclrFgj/gRN5zlJQ7VbX4GV4UqMNiW5HnV2wb8O/6Erv2D hY/NbQc89cNgIAKzVBhEsg5lwVKhKA3LdQkZO/KC0QbCUnXe8oQUDbOn0TgWJjwJ I= Received: (qmail 6384 invoked by alias); 18 Dec 2015 13:37:45 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 6375 invoked by uid 89); 18 Dec 2015 13:37:45 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, T_RP_MATCHES_RCVD, UNSUBSCRIBE_BODY autolearn=no version=3.3.2 spammy=*next, Switch, simplifies, 8477 X-HELO: mx1.redhat.com Subject: Re: [PATCH v2] malloc: Fix list_lock/arena lock deadlock [BZ #19182] To: Torvald Riegel References: <56389C10.6060001@redhat.com> <56642691.7060806@redhat.com> <1449852593.27311.98.camel@localhost.localdomain> <566F1114.1060706@redhat.com> <1450380373.26597.29.camel@localhost.localdomain> Cc: GNU C Library From: Florian Weimer X-Enigmail-Draft-Status: N1110 Message-ID: <56740C24.90901@redhat.com> Date: Fri, 18 Dec 2015 14:37:40 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: <1450380373.26597.29.camel@localhost.localdomain> 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: From: Florian Weimer 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 + + [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 * 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