From patchwork Mon Nov 12 16:09:52 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 996531 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=sourceware.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=libc-alpha-return-97163-incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="PRDGxkUw"; dkim-atps=neutral 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 42twhN5ypwz9s1x for ; Tue, 13 Nov 2018 03:10:11 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:mime-version :content-type; q=dns; s=default; b=HlHaie1d+41+t7l9lxg64CZqbrSUd K6cth/MSto/FUJgaBSmqHgOrJYg/kWYrJo42P1S+HCIUQ82+Wwy2iJTGqTS38Q9j HVy72HIELMc98PBqfk/HBgiRlwLwlV7DcUPf4tVhvngMoDOD2Lt9O34sAdJWATI/ PjPlfdccPKlqpQ= 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:from:to:subject:date:message-id:mime-version :content-type; s=default; bh=UaLISbDuQY0b9ugx+a6au81B+hw=; b=PRD GxkUwrR6GZfC/z95d3pea1GXGkrRRuWpZePeo5Jb8VozPpk247xtxKqtz6DjlCj1 WnBr0URr5JBl9TzEnHj3qlCQoxbmkjDiamt+7HnzLCGDLTXA5RKZyWxgwVDmyXgR DJWWk+vclFhhiZ5s7YhK51FTvxfbsMUA8iC6Ef/Q= Received: (qmail 105067 invoked by alias); 12 Nov 2018 16:10:05 -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 105037 invoked by uid 89); 12 Nov 2018 16:10:04 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=races, dereference, victim X-HELO: mx1.redhat.com From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH] malloc: Use current (C11-style) atomics for fastbin access Date: Mon, 12 Nov 2018 17:09:52 +0100 Message-ID: <87va52nupb.fsf@oldenburg.str.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 This is another cleanup patch in preparation of the extended heap protector (which will cover the fd/bk/fd_nextsize/bk_nextsize fields in struct malloc_chunk, too). By the way, there is an optimization opportunity for the tcache backfill in _int_malloc: After the acquire MO load on the fastbin list head, we can traverse the fastbin list as far as we need in order to refill the tcache, and update the new list head with a single CAS. This does not have races (ABA races and the like) because we have acquired the arena lock at this point. Some backoff is probably needed in case the fastbin list head is contended. But it is probably a good idea to do the first traversal at least once. Thanks, Florian 2018-11-12 Florian Weimer * malloc/malloc.c (fastbin_push_entry): New function. (fastbin_pop_entry): Likewise. Replaces REMOVE_FB. (REMOVE_FB): Remove macro. (_int_malloc): Use fastbin_pop_entry and reindent. (_int_free): Use fastbin_push_entry. (malloc_consolidate): Use atomic_exchange_acquire. diff --git a/malloc/malloc.c b/malloc/malloc.c index bfc605aa3e..7c2186c307 100644 --- a/malloc/malloc.c +++ b/malloc/malloc.c @@ -1316,6 +1316,77 @@ nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ #define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s)) +/* Add an item to the atomic fastbin list at *ROOT. Returns the old + value at *ROOT. Note that properties of the old chunk are only + stable if the caller has acquired the arena lock. With out the + lock, it can be deallocated at any time. */ +static inline struct malloc_chunk * +fastbin_push_entry (struct malloc_chunk **root, struct malloc_chunk *e) +{ + struct malloc_chunk *head; + if (SINGLE_THREAD_P) + { + /* Check that the top of the bin is not the record we are going + to add (i.e., double free). */ + head = *root; + if (head == e) + malloc_printerr ("double free or corruption (fasttop)"); + e->fd = head; + *root = e; + } + else + do + { + /* Synchronize with the release release MO CAS below. We do + not need synchronization locally, but fastbin_pop_entry and + (especially) malloc_consolidate read the entire list after + synchronizing on the head, so we need to make sure that the + writes to the next (fd) pointers have happened. */ + head = atomic_load_acquire (root); + /* Check that the top of the bin is not the record we are + going to add (i.e., double free). */ + if (head == e) + malloc_printerr ("double free or corruption (fasttop)"); + e->fd = head; + } + /* Synchronizes with the acquire MO CAS in */ + while (!atomic_compare_exchange_weak_release (root, &head, e)); + return head; +} + +/* Remove an item from the atomic fastbin list at *ROOT. The caller + must have acquired the arena lock. */ +static inline struct malloc_chunk * +fastbin_pop_entry (struct malloc_chunk **root) +{ + struct malloc_chunk *head; + if (SINGLE_THREAD_P) + { + head = *root; + if (head != NULL) + *root = head->fd; + } + else + { + /* Synchromizes with the release MO store in fastbin_push_entry. + Synchronization is needed because we read the next list + pointer. */ + head = atomic_load_acquire (root); + struct malloc_chunk *tail; + do + if (head == NULL) + return NULL; + else + tail = head->fd; + /* Synchronizes with the release MO store in fastbin_push_entry. + We do not have an ABA issue here because the caller has + acquired the arena lock, which ensures that there is only one + thread which removes elements from this list. */ + while (!atomic_compare_exchange_weak_acquire (root, &head, tail)); + } + return head; +} + #pragma GCC poison mchunk_size #pragma GCC poison mchunk_prev_size @@ -3559,63 +3630,36 @@ _int_malloc (mstate av, size_t bytes) can try it without checking, which saves some time on this fast path. */ -#define REMOVE_FB(fb, victim, pp) \ - do \ - { \ - victim = pp; \ - if (victim == NULL) \ - break; \ - } \ - while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \ - != victim); \ - if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())) { idx = fastbin_index (nb); mfastbinptr *fb = &fastbin (av, idx); - mchunkptr pp; - victim = *fb; - + victim = fastbin_pop_entry (fb); if (victim != NULL) { - if (SINGLE_THREAD_P) - *fb = victim->fd; - else - REMOVE_FB (fb, pp, victim); - if (__glibc_likely (victim != NULL)) - { - size_t victim_idx = fastbin_index (chunksize (victim)); - if (__builtin_expect (victim_idx != idx, 0)) - malloc_printerr ("malloc(): memory corruption (fast)"); - check_remalloced_chunk (av, victim, nb); + size_t victim_idx = fastbin_index (chunksize (victim)); + if (victim_idx != idx) + malloc_printerr ("malloc(): memory corruption (fast)"); + check_remalloced_chunk (av, victim, nb); #if USE_TCACHE - /* While we're here, if we see other chunks of the same size, - stash them in the tcache. */ - size_t tc_idx = csize2tidx (nb); - if (tcache && tc_idx < mp_.tcache_bins) + /* While we're here, if we see other chunks of the same size, + stash them in the tcache. */ + size_t tc_idx = csize2tidx (nb); + if (tcache && tc_idx < mp_.tcache_bins) + { + /* While bin not empty and tcache not full, copy chunks. */ + while (tcache->counts[tc_idx] < mp_.tcache_count) { - mchunkptr tc_victim; - - /* While bin not empty and tcache not full, copy chunks. */ - while (tcache->counts[tc_idx] < mp_.tcache_count - && (tc_victim = *fb) != NULL) - { - if (SINGLE_THREAD_P) - *fb = tc_victim->fd; - else - { - REMOVE_FB (fb, pp, tc_victim); - if (__glibc_unlikely (tc_victim == NULL)) - break; - } - tcache_put (tc_victim, tc_idx); - } + mchunkptr tc_victim = fastbin_pop_entry (fb); + if (tc_victim == NULL) + break; + tcache_put (tc_victim, tc_idx); } -#endif - void *p = chunk2mem (victim); - alloc_perturb (p, bytes); - return p; } +#endif + void *p = chunk2mem (victim); + alloc_perturb (p, bytes); + return p; } } @@ -4227,28 +4271,7 @@ _int_free (mstate av, mchunkptr p, int have_lock) fb = &fastbin (av, idx); /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */ - mchunkptr old = *fb, old2; - - if (SINGLE_THREAD_P) - { - /* Check that the top of the bin is not the record we are going to - add (i.e., double free). */ - if (__builtin_expect (old == p, 0)) - malloc_printerr ("double free or corruption (fasttop)"); - p->fd = old; - *fb = p; - } - else - do - { - /* Check that the top of the bin is not the record we are going to - add (i.e., double free). */ - if (__builtin_expect (old == p, 0)) - malloc_printerr ("double free or corruption (fasttop)"); - p->fd = old2 = old; - } - while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) - != old2); + mchunkptr old = fastbin_push_entry (fb, p); /* Check that size of fastbin chunk at the top is the same as size of the chunk that we are adding. We can dereference OLD @@ -4439,7 +4462,9 @@ static void malloc_consolidate(mstate av) maxfb = &fastbin (av, NFASTBINS - 1); fb = &fastbin (av, 0); do { - p = atomic_exchange_acq (fb, NULL); + /* Synchronizes with the release MO store in + fastbin_push_entry. */ + p = atomic_exchange_acquire (fb, NULL); if (p != 0) { do { {