Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1377394 > unrolled thread

[PATCH v7 0/4] vfs: Use per-cpu list for SB's s_inodes list

Back to article view | Back to linux.kernel

Contents

  [PATCH v7 0/4] vfs: Use per-cpu list for SB's s_inodes list Waiman Long <Waiman.Long@hpe.com> - 2016-04-13 01:00 +0200
    [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks Waiman Long <Waiman.Long@hpe.com> - 2016-04-13 01:10 +0200
      Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Boqun Feng <boqun.feng@gmail.com> - 2016-04-13 04:20 +0200
        Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Waiman Long <waiman.long@hpe.com> - 2016-04-13 20:00 +0200
          Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Boqun Feng <boqun.feng@gmail.com> - 2016-04-15 01:40 +0200
      Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Christoph Lameter <cl@linux.com> - 2016-04-13 17:10 +0200
        Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Waiman Long <waiman.long@hpe.com> - 2016-04-13 19:50 +0200
          Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Christoph Lameter <cl@linux.com> - 2016-04-13 20:10 +0200
      Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Jan Kara <jack@suse.cz> - 2016-04-14 16:20 +0200
        Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated  per-cpu locks Waiman Long <waiman.long@hpe.com> - 2016-04-14 20:50 +0200

#1377394 — [PATCH v7 0/4] vfs: Use per-cpu list for SB's s_inodes list

v6->v7:
 - Fix the race condition in __pcpu_list_next_cpu() as reported by
   Jan Kara.
 - No changes in patches 2-4.

v5->v6:
 - Remove patch 5 which can increase the kernel testing matrix.
 - Disable preemption in pcpu_list_add() as it was complained by
   the 0-day test even though it is not technically necessary.
 - Add a PERCPU_LIST_WARN_ON() macro to simplify code.
 - No changes in patches 2-4.

v4->v5:
 - Fix the UP panic problem reported by 0day test by unifying the SMP
   and UP code.
 - Add patch 5 to add a new kernel config parameter to allow disabling
   per-cpu list for small systems that won't benefit much from this
   feature.

v3->v4:
 - Fix some racing conditions in the code.
 - Add another patch from Jan to replace list_for_each_entry_safe()
   by list_for_each_entry().
 - Add lockdep annotation.

v2->v3:
 - Directly replace list_for_each_entry() and
   list_for_each_entry_safe() by pcpu_list_iterate() and
   pcpu_list_iterate_safe() respectively instead. Those 2 functions
   provide a stateful per-cpu list iteration interface.
 - Include Jan Kara's patch to clean up the fsnotify_unmount_inodes()
   function.

v1->v2:
 - Use separate structures for list head and nodes & provide a
   cleaner interface.
 - Use existing list_for_each_entry() or list_for_each_entry_safe()
   macros for each of the sb's s_inodes iteration functions instead
   of using list_for_each_entry_safe() for all of them which may not
   be safe in some cases.
 - Use an iterator interface to access all the nodes of a group of
   per-cpu lists. This approach is cleaner than the previous double-for
   macro which is kind of hacky. However, it does require more lines
   of code changes.
 - Add a preparatory patch 2 to extract out the per-inode codes from
   the superblock s_inodes list iteration functions to minimize code
   changes needed in the patch 3.

This patch is a replacement of my previous list batching patch -
https://lwn.net/Articles/674105/. Compared with the previous patch,
this one provides better performance and fairness. However, it also
requires a bit more changes in the VFS layer.

This patchset is a derivative of Andi Kleen's patch on "Initial per
cpu list for the per sb inode list"

https://git.kernel.org/cgit/linux/kernel/git/ak/linux-misc.git/commit/?h=hle315/
combined&id=f1cf9e715a40f44086662ae3b29f123cf059cbf4

Patch 1 introduces the per-cpu list.

Patch 2 cleans up the fsnotify_unmount_inodes() function by making
the code simpler and more standard.

Patch 3 replaces the use of list_for_each_entry_safe() in
evict_inodes() and invalidate_inodes() by list_for_each_entry().

Patch 4 modifies the superblock and inode structures to use the per-cpu
list. The corresponding functions that reference those structures
are modified.

Jan Kara (2):
  fsnotify: Simplify inode iteration on umount
  vfs: Remove unnecessary list_for_each_entry_safe() variants

Waiman Long (2):
  lib/percpu-list: Per-cpu list with associated per-cpu locks
  vfs: Use per-cpu list for superblock's inode list

 fs/block_dev.c              |   13 ++-
 fs/drop_caches.c            |   10 +-
 fs/fs-writeback.c           |   13 ++-
 fs/inode.c                  |   40 +++-----
 fs/notify/inode_mark.c      |   53 +++--------
 fs/quota/dquot.c            |   16 ++--
 fs/super.c                  |    7 +-
 include/linux/fs.h          |    8 +-
 include/linux/percpu-list.h |  231 +++++++++++++++++++++++++++++++++++++++++++
 lib/Makefile                |    2 +-
 lib/percpu-list.c           |  100 +++++++++++++++++++
 11 files changed, 397 insertions(+), 96 deletions(-)
 create mode 100644 include/linux/percpu-list.h
 create mode 100644 lib/percpu-list.c

[toc] | [next] | [standalone]

#1377402 — [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

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 pcpu_list_head and pcpu_list_node structures. The following
functions are provided to manage the per-cpu list:

 1. int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
 2. void pcpu_list_add(struct pcpu_list_node *node,
		       struct pcpu_list_head *head)
 3. void pcpu_list_del(struct pcpu_list *node)

Iteration of all the list entries within a group of per-cpu
lists is done by calling either the pcpu_list_iterate() or
pcpu_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 pcpu_list_state
structure that is passed to the iteration functions.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 include/linux/percpu-list.h |  231 +++++++++++++++++++++++++++++++++++++++++++
 lib/Makefile                |    2 +-
 lib/percpu-list.c           |  100 +++++++++++++++++++
 3 files changed, 332 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..ce8238a
--- /dev/null
+++ b/include/linux/percpu-list.h
@@ -0,0 +1,231 @@
+/*
+ * 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 pcpu_list_head structure contains the spinlock, the other
+ * pcpu_list_node structures only contains a pointer to the spinlock in
+ * pcpu_list_head.
+ */
+struct pcpu_list_head {
+	struct list_head list;
+	spinlock_t lock;
+};
+
+#define PCPU_LIST_HEAD_INIT(name)				\
+	{							\
+		.list.prev = &name.list,			\
+		.list.next = &name.list,			\
+		.list.lock = __SPIN_LOCK_UNLOCKED(name),	\
+	}
+
+/*
+ * Per-cpu list iteration state
+ */
+struct pcpu_list_state {
+	int			 cpu;
+	spinlock_t		*lock;
+	struct list_head	*head;	/* List head of current per-cpu list */
+	struct pcpu_list_node	*curr;
+	struct pcpu_list_node	*next;
+};
+
+#define PCPU_LIST_STATE_INIT()			\
+	{					\
+		.cpu  = -1,			\
+		.lock = NULL,			\
+		.head = NULL,			\
+		.curr = NULL,			\
+		.next = NULL,			\
+	}
+
+#define DEFINE_PCPU_LIST_STATE(s)		\
+	struct pcpu_list_state s = PCPU_LIST_STATE_INIT()
+
+static inline void init_pcpu_list_state(struct pcpu_list_state *state)
+{
+	state->cpu  = -1;
+	state->lock = NULL;
+	state->head = NULL;
+	state->curr = NULL;
+	state->next = NULL;
+}
+
+#ifdef CONFIG_DEBUG_SPINLOCK
+#define PERCPU_LIST_WARN_ON(x)	WARN_ON(x)
+#else
+#define PERCPU_LIST_WARN_ON(x)
+#endif
+
+/*
+ * Next per-cpu list entry
+ */
+#define pcpu_list_next_entry(pos, member) list_next_entry(pos, member.list)
+
+/*
+ * Per-cpu node data structure
+ */
+struct pcpu_list_node {
+	struct list_head list;
+	spinlock_t *lockptr;
+};
+
+#define PCPU_LIST_NODE_INIT(name)		\
+	{					\
+		.list.prev = &name.list,	\
+		.list.next = &name.list,	\
+		.list.lockptr = NULL		\
+	}
+
+static inline void init_pcpu_list_node(struct pcpu_list_node *node)
+{
+	INIT_LIST_HEAD(&node->list);
+	node->lockptr = NULL;
+}
+
+static inline void free_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
+{
+	free_percpu(*ppcpu_head);
+	*ppcpu_head = NULL;
+}
+
+/*
+ * Check if all the per-cpu lists are empty
+ */
+static inline bool pcpu_list_empty(struct pcpu_list_head *pcpu_head)
+{
+	int cpu;
+
+	for_each_possible_cpu(cpu)
+		if (!list_empty(&per_cpu_ptr(pcpu_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
+__pcpu_list_next_cpu(struct pcpu_list_head *head, struct pcpu_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 pcpu_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 pcpu_list_iterate(struct pcpu_list_head *head,
+				     struct pcpu_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 (!__pcpu_list_next_cpu(head, state))
+			return false;
+	}
+
+	PERCPU_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 pcpu_list_iterate_safe(struct pcpu_list_head *head,
+					  struct pcpu_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 (!__pcpu_list_next_cpu(head, state))
+			return false;
+		state->next = list_next_entry(state->curr, list);
+	}
+
+	PERCPU_LIST_WARN_ON(state->curr->lockptr != state->lock);
+	return true;	/* Continue the iteration */
+}
+
+extern void pcpu_list_add(struct pcpu_list_node *node,
+			  struct pcpu_list_head *head);
+extern void pcpu_list_del(struct pcpu_list_node *node);
+extern int  init_pcpu_list_head(struct pcpu_list_head **ppcpu_head);
+
+#endif /* __LINUX_PERCPU_LIST_H */
diff --git a/lib/Makefile b/lib/Makefile
index a65e9a8..387ed2b 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 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..8a96001
--- /dev/null
+++ b/lib/percpu-list.c
@@ -0,0 +1,100 @@
+/*
+ * 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>
+#include <linux/lockdep.h>
+
+/*
+ * The per-cpu list lock needs its own class to avoid warning and stack
+ * trace when lockdep is enabled.
+ */
+static struct lock_class_key percpu_list_key;
+
+/*
+ * Initialize the per-cpu list head
+ */
+int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
+{
+	struct pcpu_list_head *pcpu_head = alloc_percpu(struct pcpu_list_head);
+	int cpu;
+
+	if (!pcpu_head)
+		return -ENOMEM;
+
+	for_each_possible_cpu(cpu) {
+		struct pcpu_list_head *head = per_cpu_ptr(pcpu_head, cpu);
+
+		INIT_LIST_HEAD(&head->list);
+		head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
+		lockdep_set_class(&head->lock, &percpu_list_key);
+	}
+
+	*ppcpu_head = pcpu_head;
+	return 0;
+}
+
+/*
+ * List selection is based on the CPU being used when the pcpu_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 pcpu_list_add(struct pcpu_list_node *node, struct pcpu_list_head *head)
+{
+	struct pcpu_list_head *myhead;
+
+	/*
+	 * Disable preemption to make sure that CPU won't gets changed.
+	 */
+	preempt_disable();
+	myhead = this_cpu_ptr(head);
+	spin_lock(&myhead->lock);
+	node->lockptr = &myhead->lock;
+	list_add(&node->list, &myhead->list);
+	spin_unlock(&myhead->lock);
+	preempt_enable();
+}
+
+/*
+ * Delete a node from a percpu 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 pcpu_list_del(struct pcpu_list_node *node)
+{
+	spinlock_t *lock = READ_ONCE(node->lockptr);
+
+	if (unlikely(!lock)) {
+		WARN(1, "pcpu_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);
+}
-- 
1.7.1

[toc] | [prev] | [next] | [standalone]

#1377468 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

Hi Waiman,

On Tue, Apr 12, 2016 at 06:54:43PM -0400, Waiman Long wrote:
[...]
> +
> +/*
> + * Initialize the per-cpu list head
> + */
> +int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
> +{
> +	struct pcpu_list_head *pcpu_head = alloc_percpu(struct pcpu_list_head);
> +	int cpu;
> +
> +	if (!pcpu_head)
> +		return -ENOMEM;
> +
> +	for_each_possible_cpu(cpu) {
> +		struct pcpu_list_head *head = per_cpu_ptr(pcpu_head, cpu);
> +
> +		INIT_LIST_HEAD(&head->list);
> +		head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
> +		lockdep_set_class(&head->lock, &percpu_list_key);
> +	}
> +
> +	*ppcpu_head = pcpu_head;
> +	return 0;
> +}

The first time I looked at this patch, I had a hard time to figure out
which "struct pcpu_list_head" pointer is pointing to percpu data(the
pointer could be the parameter for per/this_cpu_ptr()), and which
pointer is pointing to actual structure. For example, 'pcpu_head' and
'head' above are different types of pointers.

So besides improving my code reading skills, I think the following patch
helps ;-) Also it can resolve several splats of sparse when running
'make C=1 lib/'.

Thoughts?

Regards,
Boqun

-------------------------------------------->8
From: Boqun Feng <boqun.feng@gmail.com>
Date: Wed, 13 Apr 2016 09:49:13 +0800
Subject: [PATCH] lib/percpu-list: Add __percpu modifier for parameters

Add __percpu modifier properly to help:

1.	Differ pointers to actual structures with those to percpu
	structures, which could improve readability.

2. 	Prevent sparse from complaining about "different address spaces"

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 include/linux/percpu-list.h | 16 +++++++++-------
 lib/percpu-list.c           |  8 +++++---
 2 files changed, 14 insertions(+), 10 deletions(-)

diff --git a/include/linux/percpu-list.h b/include/linux/percpu-list.h
index ce8238a78198..4c8496004dc2 100644
--- a/include/linux/percpu-list.h
+++ b/include/linux/percpu-list.h
@@ -107,7 +107,8 @@ static inline void init_pcpu_list_node(struct pcpu_list_node *node)
 	node->lockptr = NULL;
 }
 
-static inline void free_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
+static inline void
+free_pcpu_list_head(struct pcpu_list_head __percpu **ppcpu_head)
 {
 	free_percpu(*ppcpu_head);
 	*ppcpu_head = NULL;
@@ -116,7 +117,7 @@ static inline void free_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
 /*
  * Check if all the per-cpu lists are empty
  */
-static inline bool pcpu_list_empty(struct pcpu_list_head *pcpu_head)
+static inline bool pcpu_list_empty(struct pcpu_list_head __percpu *pcpu_head)
 {
 	int cpu;
 
@@ -133,7 +134,8 @@ static inline bool pcpu_list_empty(struct pcpu_list_head *pcpu_head)
  * Return: true if the entry is found, false if all the lists exhausted
  */
 static __always_inline bool
-__pcpu_list_next_cpu(struct pcpu_list_head *head, struct pcpu_list_state *state)
+__pcpu_list_next_cpu(struct pcpu_list_head __percpu *head,
+		     struct pcpu_list_state *state)
 {
 	if (state->lock)
 		spin_unlock(state->lock);
@@ -170,7 +172,7 @@ next_cpu:
  *
  * Return: true if the next entry is found, false if all the entries iterated
  */
-static inline bool pcpu_list_iterate(struct pcpu_list_head *head,
+static inline bool pcpu_list_iterate(struct pcpu_list_head __percpu *head,
 				     struct pcpu_list_state *state)
 {
 	/*
@@ -198,7 +200,7 @@ static inline bool pcpu_list_iterate(struct pcpu_list_head *head,
  *
  * Return: true if the next entry is found, false if all the entries iterated
  */
-static inline bool pcpu_list_iterate_safe(struct pcpu_list_head *head,
+static inline bool pcpu_list_iterate_safe(struct pcpu_list_head __percpu *head,
 					  struct pcpu_list_state *state)
 {
 	/*
@@ -224,8 +226,8 @@ static inline bool pcpu_list_iterate_safe(struct pcpu_list_head *head,
 }
 
 extern void pcpu_list_add(struct pcpu_list_node *node,
-			  struct pcpu_list_head *head);
+			  struct pcpu_list_head __percpu *head);
 extern void pcpu_list_del(struct pcpu_list_node *node);
-extern int  init_pcpu_list_head(struct pcpu_list_head **ppcpu_head);
+extern int  init_pcpu_list_head(struct pcpu_list_head __percpu **ppcpu_head);
 
 #endif /* __LINUX_PERCPU_LIST_H */
diff --git a/lib/percpu-list.c b/lib/percpu-list.c
index 8a9600169966..ef2bcb8e5a1b 100644
--- a/lib/percpu-list.c
+++ b/lib/percpu-list.c
@@ -27,9 +27,10 @@ static struct lock_class_key percpu_list_key;
 /*
  * Initialize the per-cpu list head
  */
-int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
+int init_pcpu_list_head(struct pcpu_list_head __percpu **ppcpu_head)
 {
-	struct pcpu_list_head *pcpu_head = alloc_percpu(struct pcpu_list_head);
+	struct pcpu_list_head __percpu *pcpu_head =
+				alloc_percpu(struct pcpu_list_head);
 	int cpu;
 
 	if (!pcpu_head)
@@ -52,7 +53,8 @@ int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
  * 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 pcpu_list_add(struct pcpu_list_node *node, struct pcpu_list_head *head)
+void pcpu_list_add(struct pcpu_list_node *node,
+		   struct pcpu_list_head __percpu *head)
 {
 	struct pcpu_list_head *myhead;
 
-- 
2.8.0

[toc] | [prev] | [next] | [standalone]

#1378149 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On 04/12/2016 10:09 PM, Boqun Feng wrote:
> Hi Waiman,
>
> On Tue, Apr 12, 2016 at 06:54:43PM -0400, Waiman Long wrote:
> [...]
>> +
>> +/*
>> + * Initialize the per-cpu list head
>> + */
>> +int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
>> +{
>> +	struct pcpu_list_head *pcpu_head = alloc_percpu(struct pcpu_list_head);
>> +	int cpu;
>> +
>> +	if (!pcpu_head)
>> +		return -ENOMEM;
>> +
>> +	for_each_possible_cpu(cpu) {
>> +		struct pcpu_list_head *head = per_cpu_ptr(pcpu_head, cpu);
>> +
>> +		INIT_LIST_HEAD(&head->list);
>> +		head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
>> +		lockdep_set_class(&head->lock,&percpu_list_key);
>> +	}
>> +
>> +	*ppcpu_head = pcpu_head;
>> +	return 0;
>> +}
> The first time I looked at this patch, I had a hard time to figure out
> which "struct pcpu_list_head" pointer is pointing to percpu data(the
> pointer could be the parameter for per/this_cpu_ptr()), and which
> pointer is pointing to actual structure. For example, 'pcpu_head' and
> 'head' above are different types of pointers.
>
> So besides improving my code reading skills, I think the following patch
> helps ;-) Also it can resolve several splats of sparse when running
> 'make C=1 lib/'.
>
> Thoughts?

Yes, I think your patch is helpful. I will include your patch in my 
patchset.

Thanks,
Longman

[toc] | [prev] | [next] | [standalone]

#1379369 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

[Multipart message — attachments visible in raw view] — view raw

On Wed, Apr 13, 2016 at 01:38:33PM -0400, Waiman Long wrote:
> On 04/12/2016 10:09 PM, Boqun Feng wrote:
> > Hi Waiman,
> > 
> > On Tue, Apr 12, 2016 at 06:54:43PM -0400, Waiman Long wrote:
> > [...]
> > > +
> > > +/*
> > > + * Initialize the per-cpu list head
> > > + */
> > > +int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
> > > +{
> > > +	struct pcpu_list_head *pcpu_head = alloc_percpu(struct pcpu_list_head);
> > > +	int cpu;
> > > +
> > > +	if (!pcpu_head)
> > > +		return -ENOMEM;
> > > +
> > > +	for_each_possible_cpu(cpu) {
> > > +		struct pcpu_list_head *head = per_cpu_ptr(pcpu_head, cpu);
> > > +
> > > +		INIT_LIST_HEAD(&head->list);
> > > +		head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
> > > +		lockdep_set_class(&head->lock,&percpu_list_key);
> > > +	}
> > > +
> > > +	*ppcpu_head = pcpu_head;
> > > +	return 0;
> > > +}
> > The first time I looked at this patch, I had a hard time to figure out
> > which "struct pcpu_list_head" pointer is pointing to percpu data(the
> > pointer could be the parameter for per/this_cpu_ptr()), and which
> > pointer is pointing to actual structure. For example, 'pcpu_head' and
> > 'head' above are different types of pointers.
> > 
> > So besides improving my code reading skills, I think the following patch
> > helps ;-) Also it can resolve several splats of sparse when running
> > 'make C=1 lib/'.
> > 
> > Thoughts?
> 
> Yes, I think your patch is helpful. I will include your patch in my
> patchset.
> 

Given that a renaming will happen in the next version, carrying this as
a standalone patch will be a pain, I think. So feel free to squash this
into the patch #1, if that could make your job eariser ;-)

Regards,
Boqun

> Thanks,
> Longman
> 

[toc] | [prev] | [next] | [standalone]

#1378028 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On Tue, 12 Apr 2016, Waiman Long wrote:

> 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.

Ok then the list is not per cpu anymore. Can we call this something else
please to avoid confusion? Spinlocks in per cpu structures are a bit
confusing otherwise. Seems that there is no requirement that the list can
only be accessed from a single cpu so its not per cpu per se anymore.

Maybe lock-list instead of percpu-list?

[toc] | [prev] | [next] | [standalone]

#1378137 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On 04/13/2016 11:03 AM, Christoph Lameter wrote:
> On Tue, 12 Apr 2016, Waiman Long wrote:
>
>> 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.
> Ok then the list is not per cpu anymore. Can we call this something else
> please to avoid confusion? Spinlocks in per cpu structures are a bit
> confusing otherwise. Seems that there is no requirement that the list can
> only be accessed from a single cpu so its not per cpu per se anymore.
>
> Maybe lock-list instead of percpu-list?
>

I am fine with a name change. I am not that good in naming stuff. How 
about distributed and locked list, or dlock_list in short?

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1378152 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On Wed, 13 Apr 2016, Waiman Long wrote:

> I am fine with a name change. I am not that good in naming stuff. How about
> distributed and locked list, or dlock_list in short?

dlock_list sounds better.

[toc] | [prev] | [next] | [standalone]

#1378893 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On Tue 12-04-16 18:54:43, 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 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 pcpu_list_head and pcpu_list_node structures. The following
> functions are provided to manage the per-cpu list:
> 
>  1. int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
>  2. void pcpu_list_add(struct pcpu_list_node *node,
> 		       struct pcpu_list_head *head)
>  3. void pcpu_list_del(struct pcpu_list *node)
> 
> Iteration of all the list entries within a group of per-cpu
> lists is done by calling either the pcpu_list_iterate() or
> pcpu_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 pcpu_list_state
> structure that is passed to the iteration functions.
> 
> Signed-off-by: Waiman Long <Waiman.Long@hpe.com>

The patch looks good to me now. So you can add:

Reviewed-by: Jan Kara <jack@suse.cz>

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[toc] | [prev] | [next] | [standalone]

#1379208 — Re: [PATCH v7 1/4] lib/percpu-list: Per-cpu list with associated per-cpu locks

On 04/14/2016 10:10 AM, Jan Kara wrote:
> On Tue 12-04-16 18:54:43, 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 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 pcpu_list_head and pcpu_list_node structures. The following
>> functions are provided to manage the per-cpu list:
>>
>>   1. int init_pcpu_list_head(struct pcpu_list_head **ppcpu_head)
>>   2. void pcpu_list_add(struct pcpu_list_node *node,
>> 		       struct pcpu_list_head *head)
>>   3. void pcpu_list_del(struct pcpu_list *node)
>>
>> Iteration of all the list entries within a group of per-cpu
>> lists is done by calling either the pcpu_list_iterate() or
>> pcpu_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 pcpu_list_state
>> structure that is passed to the iteration functions.
>>
>> Signed-off-by: Waiman Long<Waiman.Long@hpe.com>
> The patch looks good to me now. So you can add:
>
> Reviewed-by: Jan Kara<jack@suse.cz>
>
> 								Honza

Thanks for the review.

Cheers,
Longman

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web