From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933199AbdK2PcW (ORCPT ); Wed, 29 Nov 2017 10:32:22 -0500 Received: from mx2.suse.de ([195.135.220.15]:40817 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933161AbdK2PcS (ORCPT ); Wed, 29 Nov 2017 10:32:18 -0500 Date: Wed, 29 Nov 2017 07:29:02 -0800 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: <20171129152902.7y6xir6nrrzukgoi@linux-n805> References: <1509475860-16139-1-git-send-email-longman@redhat.com> <1509475860-16139-2-git-send-email-longman@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: <1509475860-16139-2-git-send-email-longman@redhat.com> User-Agent: NeoMutt/20170421 (1.8.2) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 31 Oct 2017, Waiman Long wrote: >Linked list is used everywhere in the Linux kernel. However, if many >threads are trying to add or delete entries into the same linked list, >it can create a performance bottleneck. > >This patch introduces a new list APIs that provide a set of distributed >lists (one per CPU), each of which is protected by its own spinlock. >To the callers, however, the set of lists acts like a single >consolidated list. This allows list entries insertion and deletion >operations to happen in parallel instead of being serialized with a >global list and lock. > >List entry insertion is strictly per cpu. List deletion, however, can >happen in a cpu other than the one that did the insertion. So we still >need lock to protect the list. Because of that, there may still be >a small amount of contention when deletion is being done. > >A new header file include/linux/dlock-list.h will be added with the >associated dlock_list_head and dlock_list_node structures. The following >functions are provided to manage the per-cpu list: > > 1. int alloc_dlock_list_heads(struct dlock_list_heads *dlist) > 2. void free_dlock_list_heads(struct dlock_list_heads *dlist) > 3. void dlock_list_add(struct dlock_list_node *node, > struct dlock_list_heads *dlist) > 4. void dlock_list_del(struct dlock_list *node) > >Iteration of all the list entries within a dlock list array >is done by calling either the dlist_for_each_entry() or >dlist_for_each_entry_safe() macros. They correspond to the >list_for_each_entry() and list_for_each_entry_safe() macros >respectively. The iteration states are keep in a dlock_list_iter >structure that is passed to the iteration macros. > >Signed-off-by: Waiman Long >Reviewed-by: Jan Kara Reviewed-by: Davidlohr Bueso