From patchwork Thu Apr 14 23:32:28 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Waiman Long X-Patchwork-Id: 8843851 Return-Path: X-Original-To: patchwork-linux-fsdevel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 04BB4C0553 for ; Thu, 14 Apr 2016 23:35:45 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id A819B2034C for ; Thu, 14 Apr 2016 23:35:43 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id F1304202EB for ; Thu, 14 Apr 2016 23:35:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752986AbcDNXey (ORCPT ); Thu, 14 Apr 2016 19:34:54 -0400 Received: from g1t6216.austin.hp.com ([15.73.96.123]:48777 "EHLO g1t6216.austin.hp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752316AbcDNXd2 (ORCPT ); Thu, 14 Apr 2016 19:33:28 -0400 Received: from g2t4689.austin.hpicorp.net (g2t4689.austin.hpicorp.net [15.94.10.175]) by g1t6216.austin.hp.com (Postfix) with ESMTP id AD2CB87; Thu, 14 Apr 2016 23:33:26 +0000 (UTC) Received: from RHEL65.localdomain (unknown [16.214.207.13]) by g2t4689.austin.hpicorp.net (Postfix) with ESMTP id 117BE36; Thu, 14 Apr 2016 23:33:24 +0000 (UTC) From: Waiman Long To: Alexander Viro , Jan Kara , Jeff Layton , "J. Bruce Fields" , Tejun Heo , Christoph Lameter Cc: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, Ingo Molnar , Peter Zijlstra , Andi Kleen , Dave Chinner , Boqun Feng , Scott J Norton , Douglas Hatch , Waiman Long Subject: [PATCH 1/5] lib/dlock-list: Distributed and lock-protected lists Date: Thu, 14 Apr 2016 19:32:28 -0400 Message-Id: <1460676752-57010-2-git-send-email-Waiman.Long@hpe.com> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1460676752-57010-1-git-send-email-Waiman.Long@hpe.com> References: <1460676752-57010-1-git-send-email-Waiman.Long@hpe.com> Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Spam-Status: No, score=-7.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 init_dlock_list_head(struct dlock_list_head **pdlock_head) 2. void dlock_list_add(struct dlock_list_node *node, struct dlock_list_head *head) 3. void dlock_list_del(struct dlock_list *node) Iteration of all the list entries within a group of per-cpu lists is done by calling either the dlock_list_iterate() or dlock_list_iterate_safe() functions in a while loop. 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_state structure that is passed to the iteration functions. Signed-off-by: Waiman Long Reviewed-by: Jan Kara --- include/linux/dlock-list.h | 233 ++++++++++++++++++++++++++++++++++++++++++++ lib/Makefile | 2 +- lib/dlock-list.c | 100 +++++++++++++++++++ 3 files changed, 334 insertions(+), 1 deletions(-) create mode 100644 include/linux/dlock-list.h create mode 100644 lib/dlock-list.c diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h new file mode 100644 index 0000000..43355f8 --- /dev/null +++ b/include/linux/dlock-list.h @@ -0,0 +1,233 @@ +/* + * Distributed/locked list + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * (C) Copyright 2016 Hewlett-Packard Enterprise Development LP + * + * Authors: Waiman Long + */ +#ifndef __LINUX_DLOCK_LIST_H +#define __LINUX_DLOCK_LIST_H + +#include +#include +#include + +/* + * include/linux/dlock-list.h + * + * A distributed (per-cpu) set of lists each of which is protected by its + * own spinlock, but acts like a single consolidated list to the callers. + * + * The dlock_list_head structure contains the spinlock, the other + * dlock_list_node structures only contains a pointer to the spinlock in + * dlock_list_head. + */ +struct dlock_list_head { + struct list_head list; + spinlock_t lock; +}; + +#define DLOCK_LIST_HEAD_INIT(name) \ + { \ + .list.prev = &name.list, \ + .list.next = &name.list, \ + .list.lock = __SPIN_LOCK_UNLOCKED(name), \ + } + +/* + * Per-cpu list iteration state + */ +struct dlock_list_state { + int cpu; + spinlock_t *lock; + struct list_head *head; /* List head of current per-cpu list */ + struct dlock_list_node *curr; + struct dlock_list_node *next; +}; + +#define DLOCK_LIST_STATE_INIT() \ + { \ + .cpu = -1, \ + .lock = NULL, \ + .head = NULL, \ + .curr = NULL, \ + .next = NULL, \ + } + +#define DEFINE_DLOCK_LIST_STATE(s) \ + struct dlock_list_state s = DLOCK_LIST_STATE_INIT() + +static inline void init_dlock_list_state(struct dlock_list_state *state) +{ + state->cpu = -1; + state->lock = NULL; + state->head = NULL; + state->curr = NULL; + state->next = NULL; +} + +#ifdef CONFIG_DEBUG_SPINLOCK +#define DLOCK_LIST_WARN_ON(x) WARN_ON(x) +#else +#define DLOCK_LIST_WARN_ON(x) +#endif + +/* + * Next per-cpu list entry + */ +#define dlock_list_next_entry(pos, member) list_next_entry(pos, member.list) + +/* + * Per-cpu node data structure + */ +struct dlock_list_node { + struct list_head list; + spinlock_t *lockptr; +}; + +#define DLOCK_LIST_NODE_INIT(name) \ + { \ + .list.prev = &name.list, \ + .list.next = &name.list, \ + .list.lockptr = NULL \ + } + +static inline void init_dlock_list_node(struct dlock_list_node *node) +{ + INIT_LIST_HEAD(&node->list); + node->lockptr = NULL; +} + +static inline void free_dlock_list_head(struct dlock_list_head **pdlock_head) +{ + free_percpu(*pdlock_head); + *pdlock_head = NULL; +} + +/* + * Check if all the per-cpu lists are empty + */ +static inline bool dlock_list_empty(struct dlock_list_head *dlock_head) +{ + int cpu; + + for_each_possible_cpu(cpu) + if (!list_empty(&per_cpu_ptr(dlock_head, cpu)->list)) + return false; + return true; +} + +/* + * Helper function to find the first entry of the next per-cpu list + * It works somewhat like for_each_possible_cpu(cpu). + * + * Return: true if the entry is found, false if all the lists exhausted + */ +static __always_inline bool +__dlock_list_next_cpu(struct dlock_list_head *head, + struct dlock_list_state *state) +{ + if (state->lock) + spin_unlock(state->lock); +next_cpu: + /* + * for_each_possible_cpu(cpu) + */ + state->cpu = cpumask_next(state->cpu, cpu_possible_mask); + if (state->cpu >= nr_cpu_ids) + return false; /* All the per-cpu lists iterated */ + + state->head = &per_cpu_ptr(head, state->cpu)->list; + if (list_empty(state->head)) + goto next_cpu; + + state->lock = &per_cpu_ptr(head, state->cpu)->lock; + spin_lock(state->lock); + /* + * There is a slight chance that the list may become empty just + * before the lock is acquired. So an additional check is + * needed to make sure that state->curr points to a valid entry. + */ + if (list_empty(state->head)) { + spin_unlock(state->lock); + goto next_cpu; + } + state->curr = list_entry(state->head->next, + struct dlock_list_node, list); + return true; +} + +/* + * Iterate to the next entry of the group of per-cpu lists + * + * Return: true if the next entry is found, false if all the entries iterated + */ +static inline bool dlock_list_iterate(struct dlock_list_head *head, + struct dlock_list_state *state) +{ + /* + * Find next entry + */ + if (state->curr) + state->curr = list_next_entry(state->curr, list); + + if (!state->curr || (&state->curr->list == state->head)) { + /* + * The current per-cpu list has been exhausted, try the next + * per-cpu list. + */ + if (!__dlock_list_next_cpu(head, state)) + return false; + } + + DLOCK_LIST_WARN_ON(state->curr->lockptr != state->lock); + return true; /* Continue the iteration */ +} + +/* + * Iterate to the next entry of the group of per-cpu lists and safe + * against removal of list_entry + * + * Return: true if the next entry is found, false if all the entries iterated + */ +static inline bool dlock_list_iterate_safe(struct dlock_list_head *head, + struct dlock_list_state *state) +{ + /* + * Find next entry + */ + if (state->curr) { + state->curr = state->next; + state->next = list_next_entry(state->next, list); + } + + if (!state->curr || (&state->curr->list == state->head)) { + /* + * The current per-cpu list has been exhausted, try the next + * per-cpu list. + */ + if (!__dlock_list_next_cpu(head, state)) + return false; + state->next = list_next_entry(state->curr, list); + } + + DLOCK_LIST_WARN_ON(state->curr->lockptr != state->lock); + return true; /* Continue the iteration */ +} + +extern void dlock_list_add(struct dlock_list_node *node, + struct dlock_list_head *head); +extern void dlock_list_del(struct dlock_list_node *node); +extern int init_dlock_list_head(struct dlock_list_head **pdlock_head); + +#endif /* __LINUX_DLOCK_LIST_H */ diff --git a/lib/Makefile b/lib/Makefile index a65e9a8..415fe5f 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -40,7 +40,7 @@ obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o \ - once.o + once.o dlock-list.o obj-y += string_helpers.o obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o obj-y += hexdump.o diff --git a/lib/dlock-list.c b/lib/dlock-list.c new file mode 100644 index 0000000..84d4623 --- /dev/null +++ b/lib/dlock-list.c @@ -0,0 +1,100 @@ +/* + * Distributed/locked list + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * (C) Copyright 2016 Hewlett-Packard Enterprise Development LP + * + * Authors: Waiman Long + */ +#include +#include + +/* + * The dlock list lock needs its own class to avoid warning and stack + * trace when lockdep is enabled. + */ +static struct lock_class_key dlock_list_key; + +/* + * Initialize the per-cpu list head + */ +int init_dlock_list_head(struct dlock_list_head **pdlock_head) +{ + struct dlock_list_head *dlock_head; + int cpu; + + dlock_head = alloc_percpu(struct dlock_list_head); + if (!dlock_head) + return -ENOMEM; + + for_each_possible_cpu(cpu) { + struct dlock_list_head *head = per_cpu_ptr(dlock_head, cpu); + + INIT_LIST_HEAD(&head->list); + head->lock = __SPIN_LOCK_UNLOCKED(&head->lock); + lockdep_set_class(&head->lock, &dlock_list_key); + } + + *pdlock_head = dlock_head; + return 0; +} + +/* + * List selection is based on the CPU being used when the dlock_list_add() + * function is called. However, deletion may be done by a different CPU. + * So we still need to use a lock to protect the content of the list. + */ +void dlock_list_add(struct dlock_list_node *node, struct dlock_list_head *head) +{ + struct dlock_list_head *myhead; + + /* + * Disable preemption to make sure that CPU won't gets changed. + */ + myhead = get_cpu_ptr(head); + spin_lock(&myhead->lock); + node->lockptr = &myhead->lock; + list_add(&node->list, &myhead->list); + spin_unlock(&myhead->lock); + put_cpu_ptr(head); +} + +/* + * Delete a node from a dlock list + * + * We need to check the lock pointer again after taking the lock to guard + * against concurrent delete of the same node. If the lock pointer changes + * (becomes NULL or to a different one), we assume that the deletion was done + * elsewhere. + */ +void dlock_list_del(struct dlock_list_node *node) +{ + spinlock_t *lock = READ_ONCE(node->lockptr); + + if (unlikely(!lock)) { + WARN(1, "dlock_list_del: node 0x%lx has no associated lock\n", + (unsigned long)node); + return; + } + + spin_lock(lock); + if (likely(lock == node->lockptr)) { + list_del_init(&node->list); + node->lockptr = NULL; + } else { + /* + * This path should never be executed. + */ + WARN_ON(1); + } + spin_unlock(lock); +}