From patchwork Fri Nov 3 13:34:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Davidlohr Bueso X-Patchwork-Id: 10040095 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id A717C602D8 for ; Fri, 3 Nov 2017 13:35:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9E7BC29603 for ; Fri, 3 Nov 2017 13:35:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 920672960D; Fri, 3 Nov 2017 13:35:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E889B29603 for ; Fri, 3 Nov 2017 13:35:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756222AbdKCNfY (ORCPT ); Fri, 3 Nov 2017 09:35:24 -0400 Received: from mx2.suse.de ([195.135.220.15]:33308 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756078AbdKCNfX (ORCPT ); Fri, 3 Nov 2017 09:35:23 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id CD8F7ADE9; Fri, 3 Nov 2017 13:35:21 +0000 (UTC) Date: Fri, 3 Nov 2017 06:34:20 -0700 From: Davidlohr Bueso To: Waiman Long Cc: Alexander Viro , Jan Kara , Jeff Layton , "J. Bruce Fields" , Tejun Heo , Christoph Lameter , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, Ingo Molnar , Peter Zijlstra , Andi Kleen , Dave Chinner , Boqun Feng Subject: Re: [PATCH v8 1/6] lib/dlock-list: Distributed and lock-protected lists Message-ID: <20171103133420.pngmrsfmtimataz4@linux-n805> References: <1509475860-16139-1-git-send-email-longman@redhat.com> <1509475860-16139-2-git-send-email-longman@redhat.com> <20171102170431.oq3i5mxtjcg53uot@linux-n805> <81bb3365-63f3-fea8-d238-e3880a4c8033@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <81bb3365-63f3-fea8-d238-e3880a4c8033@redhat.com> User-Agent: NeoMutt/20170421 (1.8.2) Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On Thu, 02 Nov 2017, Waiman Long wrote: >> Instead of the current O(N) implementation; at the cost >> of adding an atomic counter. We also need to add a heads >> pointer to the node structure such that we can unaccount >> a thread doing list_del(). >> > >The counter will then become the single contention point for all >concurrent updates to the dlock-list. So it will have a big impact on >performance. On the other hand, instead of being a counter of # of >items, we can make that a counter of # of non-empty lists. So its value >will only be changed when a list go from empty to non-empty and vice >versa. That will greatly reduce the number of updates to that counter. > > >> Signed-off-by: Davidlohr Bueso >> --- >> include/linux/dlock-list.h | 2 ++ >> lib/dlock-list.c | 40 ++++++++++++++++++++++++++++------------ >> 2 files changed, 30 insertions(+), 12 deletions(-) >> >> diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h >> index c00c7f92ada4..dd73d5787885 100644 >> --- a/include/linux/dlock-list.h >> +++ b/include/linux/dlock-list.h >> @@ -36,6 +36,7 @@ struct dlock_list_head { >> >> struct dlock_list_heads { >> struct dlock_list_head *heads; >> + atomic_t waiters; >> }; >> >> /* >> @@ -44,6 +45,7 @@ struct dlock_list_heads { >> struct dlock_list_node { >> struct list_head list; >> struct dlock_list_head *head; >> + struct dlock_list_heads *heads; >> }; >> > >I don't want to add a new data item into dlock_list_node as there can be >thousands or even of them in the system. Instead, I prefer increasing the >size of dlock_list_head which only have a limited number of them and >they have unused space because they are cacheline aligned. Both are good points. Thanks. ----8<-------------------------------------------------------- Subject: [PATCH] [PATCH v2] lib/dlock-list: Scale dlock_lists_empty() Instead of the current O(N) implementation, at the cost of adding an atomic counter, we can convert the call to an atomic_read(). The counter only serves for accounting empty to non-empty transitions, and vice versa; therefore only modified twice for each of the lists, during the lifetime of the dlock -- thus 2*nr_dlock_lists. In addition, to be able to unaccount a list_del(), we add a dlist pointer to each head, thus minimizing the overall memory footprint. Signed-off-by: Davidlohr Bueso --- include/linux/dlock-list.h | 2 ++ lib/dlock-list.c | 56 +++++++++++++++++++++++++++++++++++----------- 2 files changed, 45 insertions(+), 13 deletions(-) diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h index c00c7f92ada4..d176a2d00cd1 100644 --- a/include/linux/dlock-list.h +++ b/include/linux/dlock-list.h @@ -32,10 +32,12 @@ struct dlock_list_head { struct list_head list; spinlock_t lock; + struct dlock_list_heads *dlist; } ____cacheline_aligned_in_smp; struct dlock_list_heads { struct dlock_list_head *heads; + atomic_t waiters; }; /* diff --git a/lib/dlock-list.c b/lib/dlock-list.c index a4ddecc01b12..a84f42e800d5 100644 --- a/lib/dlock-list.c +++ b/lib/dlock-list.c @@ -122,8 +122,11 @@ int __alloc_dlock_list_heads(struct dlock_list_heads *dlist, INIT_LIST_HEAD(&head->list); head->lock = __SPIN_LOCK_UNLOCKED(&head->lock); + head->dlist = dlist; lockdep_set_class(&head->lock, key); } + + atomic_set(&dlist->waiters, 0); return 0; } EXPORT_SYMBOL(__alloc_dlock_list_heads); @@ -138,30 +141,36 @@ EXPORT_SYMBOL(__alloc_dlock_list_heads); void free_dlock_list_heads(struct dlock_list_heads *dlist) { kfree(dlist->heads); - dlist->heads = NULL; + atomic_set(&dlist->waiters, 0); } EXPORT_SYMBOL(free_dlock_list_heads); /** * dlock_lists_empty - Check if all the dlock lists are empty * @dlist: Pointer to the dlock_list_heads structure - * Return: true if list is empty, false otherwise. * - * This can be a pretty expensive function call. If this function is required - * in a performance critical path, we may have to maintain a global count - * of the list entries in the global dlock_list_heads structure instead. + * Return: true if all dlock lists are empty, false otherwise. */ bool dlock_lists_empty(struct dlock_list_heads *dlist) { - int idx; - /* Shouldn't be called before nr_dlock_lists is initialized */ WARN_ON_ONCE(!nr_dlock_lists); - for (idx = 0; idx < nr_dlock_lists; idx++) - if (!list_empty(&dlist->heads[idx].list)) - return false; - return true; + /* + * Serialize dlist->waiters such that a 0->1 transition is not missed + * by another thread checking if any of the dlock lists are used. + * + * CPU0 CPU1 + * dlock_list_add() dlock_lists_empty() + * [S] atomic_inc(waiters); + * smp_mb__after_atomic(); + * smp_mb__before_atomic(); + * [L] atomic_read(waiters) + * list_add() + * + */ + smp_mb__before_atomic(); + return !atomic_read(&dlist->waiters); } EXPORT_SYMBOL(dlock_lists_empty); @@ -179,6 +188,16 @@ void dlock_lists_add(struct dlock_list_node *node, struct dlock_list_head *head = &dlist->heads[this_cpu_read(cpu2idx)]; /* + * Bump the waiters counter _before_ taking the head->lock + * such that we don't miss a thread adding itself to a list + * while spinning for the lock. + */ + if (list_empty_careful(&head->list)) { + atomic_inc(&dlist->waiters); + smp_mb__after_atomic(); + } + + /* * There is no need to disable preemption */ spin_lock(&head->lock); @@ -199,8 +218,7 @@ EXPORT_SYMBOL(dlock_lists_add); * a bug. */ void dlock_lists_del(struct dlock_list_node *node) -{ - struct dlock_list_head *head; +{ struct dlock_list_head *head; bool retry; do { @@ -212,6 +230,18 @@ void dlock_lists_del(struct dlock_list_node *node) spin_lock(&head->lock); if (likely(head == node->head)) { list_del_init(&node->list); + /* + * We still hold the head->lock, a normal list_empty() + * check will do. + */ + if (list_empty(&head->list)) { + struct dlock_list_heads *dlist; + dlist = node->head->dlist; + + atomic_dec(&dlist->waiters); + smp_mb__after_atomic(); + } + node->head = NULL; retry = false; } else {