From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755643AbdKBRa7 convert rfc822-to-8bit (ORCPT ); Thu, 2 Nov 2017 13:30:59 -0400 Received: from mx1.redhat.com ([209.132.183.28]:55938 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752408AbdKBRa5 (ORCPT ); Thu, 2 Nov 2017 13:30:57 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 9211F81DEB Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=longman@redhat.com Subject: Re: [PATCH v8 1/6] lib/dlock-list: Distributed and lock-protected lists To: Davidlohr Bueso 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 References: <1509475860-16139-1-git-send-email-longman@redhat.com> <1509475860-16139-2-git-send-email-longman@redhat.com> <20171102170431.oq3i5mxtjcg53uot@linux-n805> From: Waiman Long Organization: Red Hat Message-ID: <81bb3365-63f3-fea8-d238-e3880a4c8033@redhat.com> Date: Thu, 2 Nov 2017 13:30:53 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.0 MIME-Version: 1.0 In-Reply-To: <20171102170431.oq3i5mxtjcg53uot@linux-n805> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8BIT Content-Language: en-US X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.25]); Thu, 02 Nov 2017 17:30:57 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 11/02/2017 01:04 PM, Davidlohr Bueso wrote: > On Tue, 31 Oct 2017, Waiman Long wrote: > >> +/** >> + * 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. >> + */ > > I vote for doing this in the original version. How about the following? > >> +bool dlock_lists_empty(struct dlock_list_heads *dlist) >> +{ >> + int idx; >> + >> + for (idx = 0; idx < nr_cpu_ids; idx++) >> + if (!list_empty(&dlist->heads[idx].list)) >> + return false; >> + return true; >> +} >> +EXPORT_SYMBOL(dlock_lists_empty); > > ----------8<----------------------------------------------- > From: Davidlohr Bueso > Subject: [PATCH] lib/dlock-list: Scale dlock_lists_empty() > > 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. Cheers, Longman