From: Waiman Long <Waiman.Long@hpe.com>
To: Alexander Viro <viro@zeniv.linux.org.uk>,
Jan Kara <jack@suse.com>, Jeff Layton <jlayton@poochiereds.net>,
"J. Bruce Fields" <bfields@fieldses.org>,
Tejun Heo <tj@kernel.org>,
Christoph Lameter <cl@linux-foundation.org>
Cc: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
Ingo Molnar <mingo@redhat.com>,
Peter Zijlstra <peterz@infradead.org>,
Andi Kleen <andi@firstfloor.org>,
Dave Chinner <dchinner@redhat.com>,
Scott J Norton <scott.norton@hp.com>,
Douglas Hatch <doug.hatch@hp.com>,
Waiman Long <Waiman.Long@hpe.com>
Subject: [RFC PATCH 1/2] lib/percpu-list: Per-cpu list with associated per-cpu locks
Date: Tue, 16 Feb 2016 20:31:19 -0500 [thread overview]
Message-ID: <1455672680-7153-2-git-send-email-Waiman.Long@hpe.com> (raw)
In-Reply-To: <1455672680-7153-1-git-send-email-Waiman.Long@hpe.com>
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 per-cpu list subystem with associated
per-cpu locks for protecting each of the lists individually. 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/percpu-list.h will be added with the
associated percpu_list structure. The following functions are used
to manage the per-cpu list:
1. int init_percpu_list_head(struct percpu_list **pclist_handle)
2. void percpu_list_add(struct percpu_list *new,
struct percpu_list *head)
3. void percpu_list_del(struct percpu_list *entry)
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
include/linux/percpu-list.h | 117 +++++++++++++++++++++++++++++++++++++++++++
lib/Makefile | 2 +-
lib/percpu-list.c | 80 +++++++++++++++++++++++++++++
3 files changed, 198 insertions(+), 1 deletions(-)
create mode 100644 include/linux/percpu-list.h
create mode 100644 lib/percpu-list.c
diff --git a/include/linux/percpu-list.h b/include/linux/percpu-list.h
new file mode 100644
index 0000000..94be520
--- /dev/null
+++ b/include/linux/percpu-list.h
@@ -0,0 +1,117 @@
+/*
+ * Per-cpu 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 <waiman.long@hpe.com>
+ */
+#ifndef __LINUX_PERCPU_LIST_H
+#define __LINUX_PERCPU_LIST_H
+
+#include <linux/spinlock.h>
+#include <linux/list.h>
+#include <linux/percpu.h>
+
+/*
+ * include/linux/percpu-list.h
+ *
+ * A per-cpu list protected by a per-cpu spinlock.
+ *
+ * The list head percpu_list structure contains the spinlock, the other
+ * entries in the list contain the spinlock pointer.
+ */
+struct percpu_list {
+ struct list_head list;
+ union {
+ spinlock_t lock; /* For list head */
+ spinlock_t *lockptr; /* For other entries */
+ };
+};
+
+/*
+ * A simplified for_all_percpu_list_entries macro without the next and pchead
+ * parameters.
+ */
+#define for_all_percpu_list_entries_simple(pos, pclock, head, member) \
+ for_all_percpu_list_entries(pos, next, pchead, pclock, head, member)
+
+#define PERCPU_LIST_HEAD_INIT(name) \
+ { \
+ .list.prev = &name.list, \
+ .list.next = &name.list, \
+ .list.lock = __SPIN_LOCK_UNLOCKED(name), \
+ }
+
+#define PERCPU_LIST_ENTRY_INIT(name) \
+ { \
+ .list.prev = &name.list, \
+ .list.next = &name.list, \
+ .list.lockptr = NULL \
+ }
+
+static inline void INIT_PERCPU_LIST_HEAD(struct percpu_list *pcpu_list)
+{
+ INIT_LIST_HEAD(&pcpu_list->list);
+ pcpu_list->lock = __SPIN_LOCK_UNLOCKED(&pcpu_list->lock);
+}
+
+static inline void INIT_PERCPU_LIST_ENTRY(struct percpu_list *pcpu_list)
+{
+ INIT_LIST_HEAD(&pcpu_list->list);
+ pcpu_list->lockptr = NULL;
+}
+
+#define PERCPU_LIST_HEAD(name) struct percpu_list __percpu *name
+
+static inline void free_percpu_list_head(struct percpu_list **pclist_handle)
+{
+ free_percpu(*pclist_handle);
+ *pclist_handle = NULL;
+}
+
+static inline bool percpu_list_empty(struct percpu_list *pcpu_list)
+{
+ int cpu;
+
+ for_each_possible_cpu (cpu)
+ if (!list_empty(&per_cpu_ptr(pcpu_list, cpu)->list))
+ return false;
+ return true;
+}
+
+/**
+ * for_all_percpu_list_entries - iterate over all the per-cpu list with locking
+ * @pos: the type * to use as a loop cursor for the current .
+ * @next: an internal type * variable pointing to the next entry
+ * @pchead: an internal struct list * of percpu list head
+ * @pclock: an internal variable for the current per-cpu spinlock
+ * @head: the head of the per-cpu list
+ * @member: the name of the per-cpu list within the struct
+ */
+#define for_all_percpu_list_entries(pos, next, pchead, pclock, head, member)\
+ { \
+ int cpu; \
+ for_each_possible_cpu (cpu) { \
+ typeof(*pos) *next; \
+ spinlock_t *pclock = per_cpu_ptr(&(head)->lock, cpu); \
+ struct list_head *pchead = &per_cpu_ptr(head, cpu)->list;\
+ spin_lock(pclock); \
+ list_for_each_entry_safe(pos, next, pchead, member.list)
+
+#define end_all_percpu_list_entries(pclock) spin_unlock(pclock); } }
+
+extern int init_percpu_list_head(struct percpu_list **pclist_handle);
+extern void percpu_list_add(struct percpu_list *new, struct percpu_list *head);
+extern void percpu_list_del(struct percpu_list *entry);
+
+#endif /* __LINUX_PERCPU_LIST_H */
diff --git a/lib/Makefile b/lib/Makefile
index a7c26a4..71a25d4 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -27,7 +27,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 percpu-list.o
obj-y += string_helpers.o
obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
obj-y += hexdump.o
diff --git a/lib/percpu-list.c b/lib/percpu-list.c
new file mode 100644
index 0000000..e5c04bf
--- /dev/null
+++ b/lib/percpu-list.c
@@ -0,0 +1,80 @@
+/*
+ * Per-cpu 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 <waiman.long@hpe.com>
+ */
+#include <linux/percpu-list.h>
+
+/*
+ * Initialize the per-cpu list
+ */
+int init_percpu_list_head(struct percpu_list **pclist_handle)
+{
+ struct percpu_list *pclist = alloc_percpu(struct percpu_list);
+ int cpu;
+
+ if (!pclist)
+ return -ENOMEM;
+
+ for_each_possible_cpu (cpu)
+ INIT_PERCPU_LIST_HEAD(per_cpu_ptr(pclist, cpu));
+
+ *pclist_handle = pclist;
+ return 0;
+}
+
+/*
+ * List selection is based on the CPU being used when the percpu_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 percpu_list_add(struct percpu_list *new, struct percpu_list *head)
+{
+ spinlock_t *lock;
+
+ /*
+ * We need to disable preemption before accessing the per-cpu data
+ * to make sure that the cpu won't be changed because of preemption.
+ */
+ preempt_disable();
+ lock = this_cpu_ptr(&head->lock);
+ spin_lock(lock);
+ new->lockptr = lock;
+ list_add(&new->list, this_cpu_ptr(&head->list));
+ spin_unlock(lock);
+ preempt_enable();
+}
+
+/*
+ * Delete an entry from a percpu list
+ *
+ * We need to check the lock pointer again after taking the lock to guard
+ * against concurrent delete of the same entry. If the lock pointer changes
+ * or becomes NULL, we assume that the deletion was done elsewhere.
+ */
+void percpu_list_del(struct percpu_list *entry)
+{
+ spinlock_t *lock = READ_ONCE(entry->lockptr);
+
+ if (unlikely(!lock))
+ return;
+
+ spin_lock(lock);
+ if (likely(entry->lockptr && (lock == entry->lockptr))) {
+ list_del_init(&entry->list);
+ entry->lockptr = NULL;
+ }
+ spin_unlock(lock);
+}
--
1.7.1
next prev parent reply other threads:[~2016-02-17 1:32 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-02-17 1:31 [RFC PATCH 0/2] vfs: Use per-cpu list for SB's s_inodes list Waiman Long
2016-02-17 1:31 ` Waiman Long [this message]
2016-02-17 9:53 ` [RFC PATCH 1/2] lib/percpu-list: Per-cpu list with associated per-cpu locks Dave Chinner
2016-02-17 11:00 ` Peter Zijlstra
2016-02-17 11:05 ` Peter Zijlstra
2016-02-17 16:16 ` Waiman Long
2016-02-17 16:22 ` Peter Zijlstra
2016-02-17 16:27 ` Christoph Lameter
2016-02-17 17:12 ` Waiman Long
2016-02-17 17:18 ` Peter Zijlstra
2016-02-17 17:41 ` Waiman Long
2016-02-17 18:22 ` Peter Zijlstra
2016-02-17 18:45 ` Waiman Long
2016-02-17 19:39 ` Peter Zijlstra
2016-02-17 11:10 ` Dave Chinner
2016-02-17 11:26 ` Peter Zijlstra
2016-02-17 11:36 ` Peter Zijlstra
2016-02-17 15:56 ` Waiman Long
2016-02-17 16:02 ` Peter Zijlstra
2016-02-17 15:13 ` Christoph Lameter
2016-02-17 1:31 ` [RRC PATCH 2/2] vfs: Use per-cpu list for superblock's inode list Waiman Long
2016-02-17 7:16 ` Ingo Molnar
2016-02-17 15:40 ` Waiman Long
2016-02-17 10:37 ` Dave Chinner
2016-02-17 16:08 ` Waiman Long
2016-02-18 23:58 ` [RFC PATCH 0/2] vfs: Use per-cpu list for SB's s_inodes list Dave Chinner
2016-02-19 21:04 ` Long, Wai Man
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1455672680-7153-2-git-send-email-Waiman.Long@hpe.com \
--to=waiman.long@hpe.com \
--cc=andi@firstfloor.org \
--cc=bfields@fieldses.org \
--cc=cl@linux-foundation.org \
--cc=dchinner@redhat.com \
--cc=doug.hatch@hp.com \
--cc=jack@suse.com \
--cc=jlayton@poochiereds.net \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=scott.norton@hp.com \
--cc=tj@kernel.org \
--cc=viro@zeniv.linux.org.uk \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).