* [PATCH v4 1/5] lib/dlock-list: Distributed and lock-protected lists
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
@ 2016-07-22 20:35 ` Waiman Long
2016-07-22 20:35 ` [PATCH v4 2/5] fsnotify: Simplify inode iteration on umount Waiman Long
` (4 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-07-22 20:35 UTC (permalink / raw)
To: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
Christoph Lameter
Cc: linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch, Waiman Long
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 *dlist)
2. void dlock_list_add(struct dlock_list_node *node,
struct dlock_list_head *dlist)
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 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 <Waiman.Long@hpe.com>
Reviewed-by: Jan Kara <jack@suse.cz>
---
include/linux/dlock-list.h | 242 ++++++++++++++++++++++++++++++++++++++++++++
lib/Makefile | 2 +-
lib/dlock-list.c | 182 +++++++++++++++++++++++++++++++++
3 files changed, 425 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..ceb4228
--- /dev/null
+++ b/include/linux/dlock-list.h
@@ -0,0 +1,242 @@
+/*
+ * Distributed and 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 <waiman.long@hpe.com>
+ */
+#ifndef __LINUX_DLOCK_LIST_H
+#define __LINUX_DLOCK_LIST_H
+
+#include <linux/spinlock.h>
+#include <linux/list.h>
+#include <linux/percpu.h>
+
+/*
+ * 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_percpu structure contains the spinlock, the other
+ * dlock_list_node structures only contains a pointer to the spinlock in
+ * dlock_list_head_percpu.
+ */
+struct dlock_list_head_percpu {
+ struct list_head list;
+ spinlock_t lock;
+};
+
+struct dlock_list_head {
+ struct dlock_list_head_percpu __percpu *head;
+};
+
+/*
+ * dlock list node data structure
+ */
+struct dlock_list_node {
+ struct list_head list;
+ spinlock_t *lockptr;
+};
+
+/*
+ * dlock list iteration state
+ *
+ * This is an opaque data structure that may change. Users of this structure
+ * should not access the structure members directly other than using the
+ * helper functions and macros provided in this header file.
+ */
+struct dlock_list_iter {
+ int cpu;
+ struct dlock_list_head *head;
+ struct dlock_list_head_percpu *pcpu_head;
+};
+
+#define DLOCK_LIST_ITER_INIT(dlist) \
+ { \
+ .cpu = -1, \
+ .head = dlist, \
+ }
+
+#define DEFINE_DLOCK_LIST_ITER(s, dlist) \
+ struct dlock_list_iter s = DLOCK_LIST_ITER_INIT(dlist)
+
+static inline void init_dlock_list_iter(struct dlock_list_iter *iter,
+ struct dlock_list_head *head)
+{
+ *iter = (struct dlock_list_iter)DLOCK_LIST_ITER_INIT(head);
+}
+
+#define DLOCK_LIST_NODE_INIT(name) \
+ { \
+ .list = LIST_HEAD_INIT(name) \
+ }
+
+static inline void init_dlock_list_node(struct dlock_list_node *node)
+{
+ *node = (struct dlock_list_node)DLOCK_LIST_NODE_INIT(node->list);
+}
+
+/**
+ * dlock_list_empty - Check if all the dlock lists are empty
+ * @dlist: Pointer to the dlock_list_head 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_head structure instead.
+ */
+static inline bool dlock_list_empty(struct dlock_list_head *dlist)
+{
+ int cpu;
+
+ for_each_possible_cpu(cpu)
+ if (!list_empty(&per_cpu_ptr(dlist->head, cpu)->list))
+ return false;
+ return true;
+}
+
+/**
+ * dlock_list_unlock - unlock the spinlock that protects the percpu list
+ * @iter: Pointer to the dlock list iterator structure
+ */
+static inline void dlock_list_unlock(struct dlock_list_iter *iter)
+{
+ spin_unlock(&iter->pcpu_head->lock);
+}
+
+/**
+ * dlock_list_relock - lock the spinlock that protects the percpu list
+ * @iter: Pointer to the dlock list iterator structure
+ */
+static inline void dlock_list_relock(struct dlock_list_iter *iter)
+{
+ spin_lock(&iter->pcpu_head->lock);
+}
+
+/*
+ * Allocation and freeing of dlock list
+ */
+extern int alloc_dlock_list_head(struct dlock_list_head *dlist);
+extern void free_dlock_list_head(struct dlock_list_head *dlist);
+
+/*
+ * The dlock list addition and deletion functions here are not irq-safe.
+ * Special irq-safe variants will have to be added if we need them.
+ */
+extern void dlock_list_add(struct dlock_list_node *node,
+ struct dlock_list_head *dlist);
+extern void dlock_list_del(struct dlock_list_node *node);
+
+/*
+ * Find the first entry of the next per-cpu list.
+ */
+extern struct dlock_list_node *
+__dlock_list_next_cpu(struct dlock_list_iter *iter);
+
+/**
+ * __dlock_list_next_entry - Iterate to the next entry of the dlock list
+ * @curr : Pointer to the current dlock_list_node structure
+ * @iter : Pointer to the dlock list iterator structure
+ * Return: Pointer to the next entry or NULL if all the entries are iterated
+ *
+ * The iterator has to be properly initialized before calling this function.
+ */
+static inline struct dlock_list_node *
+__dlock_list_next_entry(struct dlock_list_node *curr,
+ struct dlock_list_iter *iter)
+{
+ /*
+ * Find next entry
+ */
+ if (curr)
+ curr = list_next_entry(curr, list);
+
+ if (!curr || (&curr->list == &iter->pcpu_head->list)) {
+ /*
+ * The current per-cpu list has been exhausted, try the next
+ * per-cpu list.
+ */
+ curr = __dlock_list_next_cpu(iter);
+ }
+
+ return curr; /* Continue the iteration */
+}
+
+/**
+ * dlock_list_first_entry - get the first element from a list
+ * @iter : The dlock list iterator.
+ * @type : The type of the struct this is embedded in.
+ * @member: The name of the dlock_list_node within the struct.
+ * Return : Pointer to the next entry or NULL if all the entries are iterated.
+ */
+#define dlock_list_first_entry(iter, type, member) \
+ ({ \
+ struct dlock_list_node *_n; \
+ _n = __dlock_list_next_entry(NULL, iter); \
+ _n ? list_entry(_n, type, member) : NULL; \
+ })
+
+/**
+ * dlock_list_next_entry - iterate to the next entry of the list
+ * @pos : The type * to cursor
+ * @iter : The dlock list iterator.
+ * @member: The name of the dlock_list_node within the struct.
+ * Return : Pointer to the next entry or NULL if all the entries are iterated.
+ *
+ * Note that pos can't be NULL.
+ */
+#define dlock_list_next_entry(pos, iter, member) \
+ ({ \
+ struct dlock_list_node *_n; \
+ _n = __dlock_list_next_entry(&(pos)->member, iter); \
+ _n ? list_entry(_n, typeof(*(pos)), member) : NULL; \
+ })
+
+/**
+ * dlist_for_each_entry - iterate over the dlock list
+ * @pos : Type * to use as a loop cursor
+ * @iter : The dlock list iterator
+ * @member: The name of the dlock_list_node within the struct
+ *
+ * This iteration macro isn't safe with respect to list entry removal, but
+ * it can correctly iterate newly added entries right after the current one.
+ * This iteration function is designed to be used in a while loop.
+ */
+#define dlist_for_each_entry(pos, iter, member) \
+ for (pos = dlock_list_first_entry(iter, typeof(*(pos)), member);\
+ pos != NULL; \
+ pos = dlock_list_next_entry(pos, iter, member))
+
+/**
+ * dlist_for_each_entry_safe - iterate over the dlock list & safe over removal
+ * @pos : Type * to use as a loop cursor
+ * @n : Another type * to use as temporary storage
+ * @iter : The dlock list iterator
+ * @member: The name of the dlock_list_node within the struct
+ *
+ * This iteration macro is safe with respect to list entry removal.
+ * However, it cannot correctly iterate newly added entries right after the
+ * current one.
+ */
+#define dlist_for_each_entry_safe(pos, n, iter, member) \
+ for (pos = dlock_list_first_entry(iter, typeof(*(pos)), member);\
+ ({ \
+ bool _b = (pos != NULL); \
+ if (_b) \
+ n = dlock_list_next_entry(pos, iter, member); \
+ _b; \
+ }); \
+ pos = n)
+
+#endif /* __LINUX_DLOCK_LIST_H */
diff --git a/lib/Makefile b/lib/Makefile
index 499fb35..92e8c38 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..54006dc
--- /dev/null
+++ b/lib/dlock-list.c
@@ -0,0 +1,182 @@
+/*
+ * Distributed and 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 <waiman.long@hpe.com>
+ */
+#include <linux/dlock-list.h>
+#include <linux/lockdep.h>
+
+/*
+ * As all the locks in the dlock list are dynamically allocated, they need
+ * to belong to their own special lock class to avoid warning and stack
+ * trace in kernel log when lockdep is enabled. Statically allocated locks
+ * don't have this problem.
+ */
+static struct lock_class_key dlock_list_key;
+
+/**
+ * alloc_dlock_list_head - Initialize and allocate the per-cpu list head
+ * @dlist: Pointer to the dlock_list_head structure to be initialized
+ * Return: 0 if successful, -ENOMEM if memory allocation error
+ *
+ * This function does not allocate the dlock_list_head structure itself. The
+ * callers will have to do their own memory allocation, if necessary. However,
+ * this allows embedding the dlock_list_head structure directly into other
+ * structures.
+ */
+int alloc_dlock_list_head(struct dlock_list_head *dlist)
+{
+ struct dlock_list_head dlist_tmp;
+ int cpu;
+
+ dlist_tmp.head = alloc_percpu(struct dlock_list_head_percpu);
+ if (!dlist_tmp.head)
+ return -ENOMEM;
+
+ for_each_possible_cpu(cpu) {
+ struct dlock_list_head_percpu *head;
+
+ head = per_cpu_ptr(dlist_tmp.head, cpu);
+ INIT_LIST_HEAD(&head->list);
+ head->lock = __SPIN_LOCK_UNLOCKED(&head->lock);
+ lockdep_set_class(&head->lock, &dlock_list_key);
+ }
+
+ dlist->head = dlist_tmp.head;
+ return 0;
+}
+
+/**
+ * free_dlock_list_head - Free the per-cpu list head of dlock list
+ * @dlist: Pointer of the dlock_list_head structure to be freed
+ *
+ * This function doesn't free the dlock_list_head structure itself. So
+ * the caller will have to do it, if necessary.
+ */
+void free_dlock_list_head(struct dlock_list_head *dlist)
+{
+ free_percpu(dlist->head);
+ dlist->head = NULL;
+}
+
+/**
+ * dlock_list_add - Adds a node to the given dlock list
+ * @node : The node to be added
+ * @dlist: The dlock list where the node is to be added
+ *
+ * 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 *dlist)
+{
+ struct dlock_list_head_percpu *head;
+
+ /*
+ * Disable preemption to make sure that CPU won't gets changed.
+ */
+ head = get_cpu_ptr(dlist->head);
+ spin_lock(&head->lock);
+ node->lockptr = &head->lock;
+ list_add(&node->list, &head->list);
+ spin_unlock(&head->lock);
+ put_cpu_ptr(dlist->head);
+}
+
+/**
+ * dlock_list_del - Delete a node from a dlock list
+ * @node : The node to be deleted
+ *
+ * We need to check the lock pointer again after taking the lock to guard
+ * against concurrent deletion of the same node. If the lock pointer changes
+ * (becomes NULL or to a different one), we assume that the deletion was done
+ * elsewhere. A warning will be printed if this happens as it is likely to be
+ * a bug.
+ */
+void dlock_list_del(struct dlock_list_node *node)
+{
+ spinlock_t *lock;
+ bool retry;
+
+ do {
+ lock = READ_ONCE(node->lockptr);
+ if (WARN_ONCE(!lock,
+ "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;
+ retry = false;
+ } else {
+ /*
+ * The lock has somehow changed. Retry again if it is
+ * not NULL. Otherwise, just ignore the delete
+ * operation.
+ */
+ retry = (node->lockptr != NULL);
+ }
+ spin_unlock(lock);
+ } while (retry);
+}
+
+/**
+ * __dlock_list_next_cpu: Find the first entry of the next per-cpu list
+ * @dlist: Pointer to the dlock_list_head structure
+ * @iter : Pointer to the dlock list iterator structure
+ * Return: true if the entry is found, false if all the lists exhausted
+ *
+ * The information about the next per-cpu list will be put into the iterator.
+ */
+struct dlock_list_node *__dlock_list_next_cpu(struct dlock_list_iter *iter)
+{
+ struct dlock_list_node *next;
+
+ if (iter->pcpu_head) {
+ spin_unlock(&iter->pcpu_head->lock);
+ iter->pcpu_head = NULL;
+ }
+
+next_cpu:
+ /*
+ * for_each_possible_cpu(cpu)
+ */
+ iter->cpu = cpumask_next(iter->cpu, cpu_possible_mask);
+ if (iter->cpu >= nr_cpu_ids)
+ return NULL; /* All the per-cpu lists iterated */
+
+ iter->pcpu_head = per_cpu_ptr(iter->head->head, iter->cpu);
+ if (list_empty(&iter->pcpu_head->list))
+ goto next_cpu;
+
+ spin_lock(&iter->pcpu_head->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 iter->curr points to a valid entry.
+ */
+ if (list_empty(&iter->pcpu_head->list)) {
+ spin_unlock(&iter->pcpu_head->lock);
+ goto next_cpu;
+ }
+ next = list_entry(iter->pcpu_head->list.next, struct dlock_list_node,
+ list);
+ WARN_ON_ONCE(next->lockptr != &iter->pcpu_head->lock);
+
+ return next;
+}
--
1.7.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v4 2/5] fsnotify: Simplify inode iteration on umount
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
2016-07-22 20:35 ` [PATCH v4 1/5] lib/dlock-list: Distributed and lock-protected lists Waiman Long
@ 2016-07-22 20:35 ` Waiman Long
2016-07-22 20:35 ` [PATCH v4 3/5] vfs: Remove unnecessary list_for_each_entry_safe() variants Waiman Long
` (3 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-07-22 20:35 UTC (permalink / raw)
To: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
Christoph Lameter
Cc: linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch, Jan Kara, Waiman Long
From: Jan Kara <jack@suse.cz>
fsnotify_unmount_inodes() played complex tricks to pin next inode in the
sb->s_inodes list when iterating over all inodes. If we switch to
keeping current inode pinned somewhat longer, we can make the code much
simpler and standard.
Signed-off-by: Jan Kara <jack@suse.cz>
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
fs/notify/inode_mark.c | 45 +++++++++------------------------------------
1 files changed, 9 insertions(+), 36 deletions(-)
diff --git a/fs/notify/inode_mark.c b/fs/notify/inode_mark.c
index 741077d..a364524 100644
--- a/fs/notify/inode_mark.c
+++ b/fs/notify/inode_mark.c
@@ -150,12 +150,10 @@ int fsnotify_add_inode_mark(struct fsnotify_mark *mark,
*/
void fsnotify_unmount_inodes(struct super_block *sb)
{
- struct inode *inode, *next_i, *need_iput = NULL;
+ struct inode *inode, *iput_inode = NULL;
spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry_safe(inode, next_i, &sb->s_inodes, i_sb_list) {
- struct inode *need_iput_tmp;
-
+ list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
/*
* We cannot __iget() an inode in state I_FREEING,
* I_WILL_FREE, or I_NEW which is fine because by that point
@@ -178,49 +176,24 @@ void fsnotify_unmount_inodes(struct super_block *sb)
continue;
}
- need_iput_tmp = need_iput;
- need_iput = NULL;
-
- /* In case fsnotify_inode_delete() drops a reference. */
- if (inode != need_iput_tmp)
- __iget(inode);
- else
- need_iput_tmp = NULL;
+ __iget(inode);
spin_unlock(&inode->i_lock);
-
- /* In case the dropping of a reference would nuke next_i. */
- while (&next_i->i_sb_list != &sb->s_inodes) {
- spin_lock(&next_i->i_lock);
- if (!(next_i->i_state & (I_FREEING | I_WILL_FREE)) &&
- atomic_read(&next_i->i_count)) {
- __iget(next_i);
- need_iput = next_i;
- spin_unlock(&next_i->i_lock);
- break;
- }
- spin_unlock(&next_i->i_lock);
- next_i = list_next_entry(next_i, i_sb_list);
- }
-
- /*
- * We can safely drop s_inode_list_lock here because either
- * we actually hold references on both inode and next_i or
- * end of list. Also no new inodes will be added since the
- * umount has begun.
- */
spin_unlock(&sb->s_inode_list_lock);
- if (need_iput_tmp)
- iput(need_iput_tmp);
+ if (iput_inode)
+ iput(iput_inode);
/* for each watch, send FS_UNMOUNT and then remove it */
fsnotify(inode, FS_UNMOUNT, inode, FSNOTIFY_EVENT_INODE, NULL, 0);
fsnotify_inode_delete(inode);
- iput(inode);
+ iput_inode = inode;
spin_lock(&sb->s_inode_list_lock);
}
spin_unlock(&sb->s_inode_list_lock);
+
+ if (iput_inode)
+ iput(iput_inode);
}
--
1.7.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v4 3/5] vfs: Remove unnecessary list_for_each_entry_safe() variants
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
2016-07-22 20:35 ` [PATCH v4 1/5] lib/dlock-list: Distributed and lock-protected lists Waiman Long
2016-07-22 20:35 ` [PATCH v4 2/5] fsnotify: Simplify inode iteration on umount Waiman Long
@ 2016-07-22 20:35 ` Waiman Long
2016-07-22 20:35 ` [PATCH v4 4/5] vfs: Use dlock list for superblock's inode list Waiman Long
` (2 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-07-22 20:35 UTC (permalink / raw)
To: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
Christoph Lameter
Cc: linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch, Jan Kara, Waiman Long
From: Jan Kara <jack@suse.cz>
evict_inodes() and invalidate_inodes() use list_for_each_entry_safe()
to iterate sb->s_inodes list. However, since we use i_lru list entry for
our local temporary list of inodes to destroy, the inode is guaranteed
to stay in sb->s_inodes list while we hold sb->s_inode_list_lock. So
there is no real need for safe iteration variant and we can use
list_for_each_entry() just fine.
Signed-off-by: Jan Kara <jack@suse.cz>
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
fs/inode.c | 8 ++++----
1 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/fs/inode.c b/fs/inode.c
index 4ccbc21..8204813 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -597,12 +597,12 @@ static void dispose_list(struct list_head *head)
*/
void evict_inodes(struct super_block *sb)
{
- struct inode *inode, *next;
+ struct inode *inode;
LIST_HEAD(dispose);
again:
spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry_safe(inode, next, &sb->s_inodes, i_sb_list) {
+ list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
if (atomic_read(&inode->i_count))
continue;
@@ -647,11 +647,11 @@ again:
int invalidate_inodes(struct super_block *sb, bool kill_dirty)
{
int busy = 0;
- struct inode *inode, *next;
+ struct inode *inode;
LIST_HEAD(dispose);
spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry_safe(inode, next, &sb->s_inodes, i_sb_list) {
+ list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
spin_lock(&inode->i_lock);
if (inode->i_state & (I_NEW | I_FREEING | I_WILL_FREE)) {
spin_unlock(&inode->i_lock);
--
1.7.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v4 4/5] vfs: Use dlock list for superblock's inode list
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
` (2 preceding siblings ...)
2016-07-22 20:35 ` [PATCH v4 3/5] vfs: Remove unnecessary list_for_each_entry_safe() variants Waiman Long
@ 2016-07-22 20:35 ` Waiman Long
2016-07-22 20:35 ` [PATCH v4 5/5] lib/dlock-list: Allow cacheline alignment of percpu head Waiman Long
2016-07-25 13:48 ` [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Christoph Lameter
5 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-07-22 20:35 UTC (permalink / raw)
To: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
Christoph Lameter
Cc: linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch, Waiman Long
When many threads are trying to add or delete inode to or from
a superblock's s_inodes list, spinlock contention on the list can
become a performance bottleneck.
This patch changes the s_inodes field to become a dlock list which
is a distributed set of lists with per-list spinlocks. As a result,
the following superblock inode list (sb->s_inodes) iteration functions
in vfs are also being modified:
1. iterate_bdevs()
2. drop_pagecache_sb()
3. wait_sb_inodes()
4. evict_inodes()
5. invalidate_inodes()
6. fsnotify_unmount_inodes()
7. add_dquot_ref()
8. remove_dquot_ref()
With an exit microbenchmark that creates a large number of threads,
attachs many inodes to them and then exits. The runtimes of that
microbenchmark with 1000 threads before and after the patch on a
4-socket Intel E7-4820 v3 system (40 cores, 80 threads) were as
follows:
Kernel Elapsed Time System Time
------ ------------ -----------
Vanilla 4.5-rc4 65.29s 82m14s
Patched 4.5-rc4 22.81s 23m03s
Before the patch, spinlock contention at the inode_sb_list_add()
function at the startup phase and the inode_sb_list_del() function at
the exit phase were about 79% and 93% of total CPU time respectively
(as measured by perf). After the patch, the dlock_list_add()
function consumed only about 0.04% of CPU time at startup phase. The
dlock_list_del() function consumed about 0.4% of CPU time at exit
phase. There were still some spinlock contention, but they happened
elsewhere.
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
Reviewed-by: Jan Kara <jack@suse.cz>
---
fs/block_dev.c | 9 ++++-----
fs/drop_caches.c | 9 ++++-----
fs/fs-writeback.c | 9 ++++-----
fs/inode.c | 34 +++++++++++++---------------------
fs/notify/inode_mark.c | 9 ++++-----
fs/quota/dquot.c | 14 ++++++--------
fs/super.c | 7 ++++---
include/linux/fs.h | 8 ++++----
8 files changed, 43 insertions(+), 56 deletions(-)
diff --git a/fs/block_dev.c b/fs/block_dev.c
index 71ccab1..fdd5f7f 100644
--- a/fs/block_dev.c
+++ b/fs/block_dev.c
@@ -1896,9 +1896,9 @@ EXPORT_SYMBOL(__invalidate_device);
void iterate_bdevs(void (*func)(struct block_device *, void *), void *arg)
{
struct inode *inode, *old_inode = NULL;
+ DEFINE_DLOCK_LIST_ITER(iter, &blockdev_superblock->s_inodes);
- spin_lock(&blockdev_superblock->s_inode_list_lock);
- list_for_each_entry(inode, &blockdev_superblock->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
struct address_space *mapping = inode->i_mapping;
spin_lock(&inode->i_lock);
@@ -1909,7 +1909,7 @@ void iterate_bdevs(void (*func)(struct block_device *, void *), void *arg)
}
__iget(inode);
spin_unlock(&inode->i_lock);
- spin_unlock(&blockdev_superblock->s_inode_list_lock);
+ dlock_list_unlock(&iter);
/*
* We hold a reference to 'inode' so it couldn't have been
* removed from s_inodes list while we dropped the
@@ -1923,8 +1923,7 @@ void iterate_bdevs(void (*func)(struct block_device *, void *), void *arg)
func(I_BDEV(inode), arg);
- spin_lock(&blockdev_superblock->s_inode_list_lock);
+ dlock_list_relock(&iter);
}
- spin_unlock(&blockdev_superblock->s_inode_list_lock);
iput(old_inode);
}
diff --git a/fs/drop_caches.c b/fs/drop_caches.c
index d72d52b..8db1374 100644
--- a/fs/drop_caches.c
+++ b/fs/drop_caches.c
@@ -16,9 +16,9 @@ int sysctl_drop_caches;
static void drop_pagecache_sb(struct super_block *sb, void *unused)
{
struct inode *inode, *toput_inode = NULL;
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
spin_lock(&inode->i_lock);
if ((inode->i_state & (I_FREEING|I_WILL_FREE|I_NEW)) ||
(inode->i_mapping->nrpages == 0)) {
@@ -27,15 +27,14 @@ static void drop_pagecache_sb(struct super_block *sb, void *unused)
}
__iget(inode);
spin_unlock(&inode->i_lock);
- spin_unlock(&sb->s_inode_list_lock);
+ dlock_list_unlock(&iter);
invalidate_mapping_pages(inode->i_mapping, 0, -1);
iput(toput_inode);
toput_inode = inode;
- spin_lock(&sb->s_inode_list_lock);
+ dlock_list_relock(&iter);
}
- spin_unlock(&sb->s_inode_list_lock);
iput(toput_inode);
}
diff --git a/fs/fs-writeback.c b/fs/fs-writeback.c
index 989a2ce..da0e585 100644
--- a/fs/fs-writeback.c
+++ b/fs/fs-writeback.c
@@ -2155,6 +2155,7 @@ EXPORT_SYMBOL(__mark_inode_dirty);
static void wait_sb_inodes(struct super_block *sb)
{
struct inode *inode, *old_inode = NULL;
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
/*
* We need to be protected against the filesystem going from
@@ -2163,7 +2164,6 @@ static void wait_sb_inodes(struct super_block *sb)
WARN_ON(!rwsem_is_locked(&sb->s_umount));
mutex_lock(&sb->s_sync_lock);
- spin_lock(&sb->s_inode_list_lock);
/*
* Data integrity sync. Must wait for all pages under writeback,
@@ -2172,7 +2172,7 @@ static void wait_sb_inodes(struct super_block *sb)
* In which case, the inode may not be on the dirty list, but
* we still have to wait for that writeout.
*/
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
struct address_space *mapping = inode->i_mapping;
spin_lock(&inode->i_lock);
@@ -2183,7 +2183,7 @@ static void wait_sb_inodes(struct super_block *sb)
}
__iget(inode);
spin_unlock(&inode->i_lock);
- spin_unlock(&sb->s_inode_list_lock);
+ dlock_list_unlock(&iter);
/*
* We hold a reference to 'inode' so it couldn't have been
@@ -2205,9 +2205,8 @@ static void wait_sb_inodes(struct super_block *sb)
cond_resched();
- spin_lock(&sb->s_inode_list_lock);
+ dlock_list_relock(&iter);
}
- spin_unlock(&sb->s_inode_list_lock);
iput(old_inode);
mutex_unlock(&sb->s_sync_lock);
}
diff --git a/fs/inode.c b/fs/inode.c
index 8204813..50b45a7 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -28,7 +28,7 @@
* inode->i_state, inode->i_hash, __iget()
* Inode LRU list locks protect:
* inode->i_sb->s_inode_lru, inode->i_lru
- * inode->i_sb->s_inode_list_lock protects:
+ * inode->i_sb->s_inodes->head->lock protects:
* inode->i_sb->s_inodes, inode->i_sb_list
* bdi->wb.list_lock protects:
* bdi->wb.b_{dirty,io,more_io,dirty_time}, inode->i_io_list
@@ -37,7 +37,7 @@
*
* Lock ordering:
*
- * inode->i_sb->s_inode_list_lock
+ * inode->i_sb->s_inodes->head->lock
* inode->i_lock
* Inode LRU list locks
*
@@ -45,7 +45,7 @@
* inode->i_lock
*
* inode_hash_lock
- * inode->i_sb->s_inode_list_lock
+ * inode->i_sb->s_inodes->head->lock
* inode->i_lock
*
* iunique_lock
@@ -431,19 +431,14 @@ static void inode_lru_list_del(struct inode *inode)
*/
void inode_sb_list_add(struct inode *inode)
{
- spin_lock(&inode->i_sb->s_inode_list_lock);
- list_add(&inode->i_sb_list, &inode->i_sb->s_inodes);
- spin_unlock(&inode->i_sb->s_inode_list_lock);
+ dlock_list_add(&inode->i_sb_list, &inode->i_sb->s_inodes);
}
EXPORT_SYMBOL_GPL(inode_sb_list_add);
static inline void inode_sb_list_del(struct inode *inode)
{
- if (!list_empty(&inode->i_sb_list)) {
- spin_lock(&inode->i_sb->s_inode_list_lock);
- list_del_init(&inode->i_sb_list);
- spin_unlock(&inode->i_sb->s_inode_list_lock);
- }
+ if (!list_empty(&inode->i_sb_list.list))
+ dlock_list_del(&inode->i_sb_list);
}
static unsigned long hash(struct super_block *sb, unsigned long hashval)
@@ -598,11 +593,12 @@ static void dispose_list(struct list_head *head)
void evict_inodes(struct super_block *sb)
{
struct inode *inode;
+ struct dlock_list_iter iter;
LIST_HEAD(dispose);
again:
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ init_dlock_list_iter(&iter, &sb->s_inodes);
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
if (atomic_read(&inode->i_count))
continue;
@@ -623,13 +619,12 @@ again:
* bit so we don't livelock.
*/
if (need_resched()) {
- spin_unlock(&sb->s_inode_list_lock);
+ dlock_list_unlock(&iter);
cond_resched();
dispose_list(&dispose);
goto again;
}
}
- spin_unlock(&sb->s_inode_list_lock);
dispose_list(&dispose);
}
@@ -649,9 +644,9 @@ int invalidate_inodes(struct super_block *sb, bool kill_dirty)
int busy = 0;
struct inode *inode;
LIST_HEAD(dispose);
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
spin_lock(&inode->i_lock);
if (inode->i_state & (I_NEW | I_FREEING | I_WILL_FREE)) {
spin_unlock(&inode->i_lock);
@@ -673,7 +668,6 @@ int invalidate_inodes(struct super_block *sb, bool kill_dirty)
spin_unlock(&inode->i_lock);
list_add(&inode->i_lru, &dispose);
}
- spin_unlock(&sb->s_inode_list_lock);
dispose_list(&dispose);
@@ -888,7 +882,7 @@ struct inode *new_inode_pseudo(struct super_block *sb)
spin_lock(&inode->i_lock);
inode->i_state = 0;
spin_unlock(&inode->i_lock);
- INIT_LIST_HEAD(&inode->i_sb_list);
+ init_dlock_list_node(&inode->i_sb_list);
}
return inode;
}
@@ -909,8 +903,6 @@ struct inode *new_inode(struct super_block *sb)
{
struct inode *inode;
- spin_lock_prefetch(&sb->s_inode_list_lock);
-
inode = new_inode_pseudo(sb);
if (inode)
inode_sb_list_add(inode);
diff --git a/fs/notify/inode_mark.c b/fs/notify/inode_mark.c
index a364524..ae3dd1d 100644
--- a/fs/notify/inode_mark.c
+++ b/fs/notify/inode_mark.c
@@ -151,9 +151,9 @@ int fsnotify_add_inode_mark(struct fsnotify_mark *mark,
void fsnotify_unmount_inodes(struct super_block *sb)
{
struct inode *inode, *iput_inode = NULL;
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
/*
* We cannot __iget() an inode in state I_FREEING,
* I_WILL_FREE, or I_NEW which is fine because by that point
@@ -178,7 +178,7 @@ void fsnotify_unmount_inodes(struct super_block *sb)
__iget(inode);
spin_unlock(&inode->i_lock);
- spin_unlock(&sb->s_inode_list_lock);
+ dlock_list_unlock(&iter);
if (iput_inode)
iput(iput_inode);
@@ -190,9 +190,8 @@ void fsnotify_unmount_inodes(struct super_block *sb)
iput_inode = inode;
- spin_lock(&sb->s_inode_list_lock);
+ dlock_list_relock(&iter);
}
- spin_unlock(&sb->s_inode_list_lock);
if (iput_inode)
iput(iput_inode);
diff --git a/fs/quota/dquot.c b/fs/quota/dquot.c
index ff21980..b760dd7 100644
--- a/fs/quota/dquot.c
+++ b/fs/quota/dquot.c
@@ -936,12 +936,12 @@ static int dqinit_needed(struct inode *inode, int type)
static void add_dquot_ref(struct super_block *sb, int type)
{
struct inode *inode, *old_inode = NULL;
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
#ifdef CONFIG_QUOTA_DEBUG
int reserved = 0;
#endif
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
spin_lock(&inode->i_lock);
if ((inode->i_state & (I_FREEING|I_WILL_FREE|I_NEW)) ||
!atomic_read(&inode->i_writecount) ||
@@ -951,7 +951,7 @@ static void add_dquot_ref(struct super_block *sb, int type)
}
__iget(inode);
spin_unlock(&inode->i_lock);
- spin_unlock(&sb->s_inode_list_lock);
+ dlock_list_unlock(&iter);
#ifdef CONFIG_QUOTA_DEBUG
if (unlikely(inode_get_rsv_space(inode) > 0))
@@ -969,9 +969,8 @@ static void add_dquot_ref(struct super_block *sb, int type)
* later.
*/
old_inode = inode;
- spin_lock(&sb->s_inode_list_lock);
+ dlock_list_relock(&iter);
}
- spin_unlock(&sb->s_inode_list_lock);
iput(old_inode);
#ifdef CONFIG_QUOTA_DEBUG
@@ -1039,9 +1038,9 @@ static void remove_dquot_ref(struct super_block *sb, int type,
{
struct inode *inode;
int reserved = 0;
+ DEFINE_DLOCK_LIST_ITER(iter, &sb->s_inodes);
- spin_lock(&sb->s_inode_list_lock);
- list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
+ dlist_for_each_entry(inode, &iter, i_sb_list) {
/*
* We have to scan also I_NEW inodes because they can already
* have quota pointer initialized. Luckily, we need to touch
@@ -1056,7 +1055,6 @@ static void remove_dquot_ref(struct super_block *sb, int type,
}
spin_unlock(&dq_data_lock);
}
- spin_unlock(&sb->s_inode_list_lock);
#ifdef CONFIG_QUOTA_DEBUG
if (reserved) {
printk(KERN_WARNING "VFS (%s): Writes happened after quota"
diff --git a/fs/super.c b/fs/super.c
index d78b984..4c33204 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -163,6 +163,7 @@ static void destroy_super(struct super_block *s)
{
list_lru_destroy(&s->s_dentry_lru);
list_lru_destroy(&s->s_inode_lru);
+ free_dlock_list_head(&s->s_inodes);
security_sb_free(s);
WARN_ON(!list_empty(&s->s_mounts));
kfree(s->s_subtype);
@@ -204,9 +205,9 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags)
INIT_HLIST_NODE(&s->s_instances);
INIT_HLIST_BL_HEAD(&s->s_anon);
mutex_init(&s->s_sync_lock);
- INIT_LIST_HEAD(&s->s_inodes);
- spin_lock_init(&s->s_inode_list_lock);
+ if (alloc_dlock_list_head(&s->s_inodes))
+ goto fail;
if (list_lru_init_memcg(&s->s_dentry_lru))
goto fail;
if (list_lru_init_memcg(&s->s_inode_lru))
@@ -427,7 +428,7 @@ void generic_shutdown_super(struct super_block *sb)
if (sop->put_super)
sop->put_super(sb);
- if (!list_empty(&sb->s_inodes)) {
+ if (!dlock_list_empty(&sb->s_inodes)) {
printk("VFS: Busy inodes after unmount of %s. "
"Self-destruct in 5 seconds. Have a nice day...\n",
sb->s_id);
diff --git a/include/linux/fs.h b/include/linux/fs.h
index dd28814..d5233ec 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -32,6 +32,7 @@
#include <linux/workqueue.h>
#include <linux/percpu-rwsem.h>
#include <linux/delayed_call.h>
+#include <linux/dlock-list.h>
#include <asm/byteorder.h>
#include <uapi/linux/fs.h>
@@ -664,7 +665,7 @@ struct inode {
u16 i_wb_frn_history;
#endif
struct list_head i_lru; /* inode LRU list */
- struct list_head i_sb_list;
+ struct dlock_list_node i_sb_list;
union {
struct hlist_head i_dentry;
struct rcu_head i_rcu;
@@ -1445,9 +1446,8 @@ struct super_block {
*/
int s_stack_depth;
- /* s_inode_list_lock protects s_inodes */
- spinlock_t s_inode_list_lock ____cacheline_aligned_in_smp;
- struct list_head s_inodes; /* all inodes */
+ /* The internal percpu locks protect s_inodes */
+ struct dlock_list_head s_inodes; /* all inodes */
};
extern struct timespec current_fs_time(struct super_block *sb);
--
1.7.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v4 5/5] lib/dlock-list: Allow cacheline alignment of percpu head
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
` (3 preceding siblings ...)
2016-07-22 20:35 ` [PATCH v4 4/5] vfs: Use dlock list for superblock's inode list Waiman Long
@ 2016-07-22 20:35 ` Waiman Long
2016-07-25 13:48 ` [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Christoph Lameter
5 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-07-22 20:35 UTC (permalink / raw)
To: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
Christoph Lameter
Cc: linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch, Waiman Long
Christoph Lameter had raised the concern that the spinlock in the
dlock_list_head_percpu structure may cause undesirable cacheline
contention in the percpu area that normally shouldn't have contention
of this kind.
This patch addresses this issue by allowing an option to force the
dlock_list_head_percpu structure to be cacheline aligned so that any
contention on the spinlock will not affect any nearby data items. It
then forces cacheline alignment when alloc_dlock_list_head() is called
by alloc_super() in fs/super.c.
Reported-by: Christoph Lameter <cl@linux.com>
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
fs/super.c | 2 +-
include/linux/dlock-list.h | 2 +-
lib/dlock-list.c | 20 ++++++++++++++++++--
3 files changed, 20 insertions(+), 4 deletions(-)
diff --git a/fs/super.c b/fs/super.c
index 4c33204..39f2214 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -206,7 +206,7 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags)
INIT_HLIST_BL_HEAD(&s->s_anon);
mutex_init(&s->s_sync_lock);
- if (alloc_dlock_list_head(&s->s_inodes))
+ if (alloc_dlock_list_head(&s->s_inodes, 1))
goto fail;
if (list_lru_init_memcg(&s->s_dentry_lru))
goto fail;
diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h
index ceb4228..f0a0b2a 100644
--- a/include/linux/dlock-list.h
+++ b/include/linux/dlock-list.h
@@ -127,7 +127,7 @@ static inline void dlock_list_relock(struct dlock_list_iter *iter)
/*
* Allocation and freeing of dlock list
*/
-extern int alloc_dlock_list_head(struct dlock_list_head *dlist);
+extern int alloc_dlock_list_head(struct dlock_list_head *dlist, int align);
extern void free_dlock_list_head(struct dlock_list_head *dlist);
/*
diff --git a/lib/dlock-list.c b/lib/dlock-list.c
index 54006dc..f117d11 100644
--- a/lib/dlock-list.c
+++ b/lib/dlock-list.c
@@ -26,22 +26,38 @@
*/
static struct lock_class_key dlock_list_key;
+struct dlock_list_head_percpu_caligned {
+ struct dlock_list_head_percpu head;
+} ____cacheline_aligned_in_smp;
+
/**
* alloc_dlock_list_head - Initialize and allocate the per-cpu list head
* @dlist: Pointer to the dlock_list_head structure to be initialized
+ * @align: A boolean flag for cacheline alignment
* Return: 0 if successful, -ENOMEM if memory allocation error
*
* This function does not allocate the dlock_list_head structure itself. The
* callers will have to do their own memory allocation, if necessary. However,
* this allows embedding the dlock_list_head structure directly into other
* structures.
+ *
+ * As the percpu spinlocks can be accessed remotely from other CPUs, it may
+ * have a performance impact on other percpu data items resided in the same
+ * cacheline as the spinlock. This performance impact can be avoided by
+ * setting the align flag forcing cacheline alignment for the percpu head
+ * structure at the expense of some wasted memory space.
*/
-int alloc_dlock_list_head(struct dlock_list_head *dlist)
+int alloc_dlock_list_head(struct dlock_list_head *dlist, int align)
{
struct dlock_list_head dlist_tmp;
int cpu;
- dlist_tmp.head = alloc_percpu(struct dlock_list_head_percpu);
+ if (align)
+ dlist_tmp.head = (struct dlock_list_head_percpu __percpu *)
+ alloc_percpu(struct dlock_list_head_percpu_caligned);
+ else
+ dlist_tmp.head = alloc_percpu(struct dlock_list_head_percpu);
+
if (!dlist_tmp.head)
return -ENOMEM;
--
1.7.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* Re: [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list
2016-07-22 20:35 [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Waiman Long
` (4 preceding siblings ...)
2016-07-22 20:35 ` [PATCH v4 5/5] lib/dlock-list: Allow cacheline alignment of percpu head Waiman Long
@ 2016-07-25 13:48 ` Christoph Lameter
2016-07-25 17:41 ` Tejun Heo
5 siblings, 1 reply; 10+ messages in thread
From: Christoph Lameter @ 2016-07-25 13:48 UTC (permalink / raw)
To: Waiman Long
Cc: Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields, Tejun Heo,
linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch
On Fri, 22 Jul 2016, Waiman Long wrote:
> - Add a new patch to make the percpu head structure cacheline aligned
> to prevent cacheline contention from disrupting the performance
> of nearby percpu variables.
It would be better not to use the percpu allocation etc for this.
Given the frequency of off node data access I would say that the data
structure does not qualify as per cpu data. You have per cpu data items
yes but this is not used as per cpu data.
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list
2016-07-25 13:48 ` [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list Christoph Lameter
@ 2016-07-25 17:41 ` Tejun Heo
2016-07-27 15:12 ` Christoph Lameter
0 siblings, 1 reply; 10+ messages in thread
From: Tejun Heo @ 2016-07-25 17:41 UTC (permalink / raw)
To: Christoph Lameter
Cc: Waiman Long, Alexander Viro, Jan Kara, Jeff Layton,
J. Bruce Fields, linux-fsdevel, linux-kernel, Ingo Molnar,
Peter Zijlstra, Andi Kleen, Dave Chinner, Boqun Feng,
Scott J Norton, Douglas Hatch
Hello, Christoph.
On Mon, Jul 25, 2016 at 08:48:25AM -0500, Christoph Lameter wrote:
> On Fri, 22 Jul 2016, Waiman Long wrote:
>
> > - Add a new patch to make the percpu head structure cacheline aligned
> > to prevent cacheline contention from disrupting the performance
> > of nearby percpu variables.
>
> It would be better not to use the percpu allocation etc for this.
> Given the frequency of off node data access I would say that the data
> structure does not qualify as per cpu data. You have per cpu data items
> yes but this is not used as per cpu data.
I don't get it. What's the harm of using percpu memory here? Other
percpu data structures have remote access too. They're to a lower
degree but I don't see a clear demarcation line and making addtions
per-cpu seems to have significant benefits here. If there's a better
way of splitting the list and locking, sure, let's try that but short
of that I don't see anything wrong with doing this per-cpu.
Thanks.
--
tejun
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list
2016-07-25 17:41 ` Tejun Heo
@ 2016-07-27 15:12 ` Christoph Lameter
2016-08-09 3:26 ` Waiman Long
0 siblings, 1 reply; 10+ messages in thread
From: Christoph Lameter @ 2016-07-27 15:12 UTC (permalink / raw)
To: Tejun Heo
Cc: Waiman Long, Alexander Viro, Jan Kara, Jeff Layton,
J. Bruce Fields, linux-fsdevel, linux-kernel, Ingo Molnar,
Peter Zijlstra, Andi Kleen, Dave Chinner, Boqun Feng,
Scott J Norton, Douglas Hatch
On Mon, 25 Jul 2016, Tejun Heo wrote:
> I don't get it. What's the harm of using percpu memory here? Other
> percpu data structures have remote access too. They're to a lower
> degree but I don't see a clear demarcation line and making addtions
> per-cpu seems to have significant benefits here. If there's a better
> way of splitting the list and locking, sure, let's try that but short
> of that I don't see anything wrong with doing this per-cpu.
For the regular global declarations we have separate areas for "SHARED"
per cpu data like this. See DECLARE_PER_CPU_SHARED* and friends.
Even if you align a percpu_alloc() there is still the possibility that
other percpu variables defined after this will suffer from aliasing.
The aligning causes space to be wasted for performance critical areas
where you want to minimize cache line usage. The variables cannot be
packed as densely as before. I think allocations like this need to be
separate. Simply allocate an array of these structs using
kcalloc(nr_cpu_ids, sizeof(my_struct), GFP_KERNEL)?
Why bother with percpu_alloc() if its not per cpu data?
Well if we do not care about that detail that much then lets continue going down this patch.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4 0/5] vfs: Use dlock list for SB's s_inodes list
2016-07-27 15:12 ` Christoph Lameter
@ 2016-08-09 3:26 ` Waiman Long
0 siblings, 0 replies; 10+ messages in thread
From: Waiman Long @ 2016-08-09 3:26 UTC (permalink / raw)
To: Christoph Lameter
Cc: Tejun Heo, Alexander Viro, Jan Kara, Jeff Layton, J. Bruce Fields,
linux-fsdevel, linux-kernel, Ingo Molnar, Peter Zijlstra,
Andi Kleen, Dave Chinner, Boqun Feng, Scott J Norton,
Douglas Hatch
On 07/27/2016 11:12 AM, Christoph Lameter wrote:
> On Mon, 25 Jul 2016, Tejun Heo wrote:
>
>> I don't get it. What's the harm of using percpu memory here? Other
>> percpu data structures have remote access too. They're to a lower
>> degree but I don't see a clear demarcation line and making addtions
>> per-cpu seems to have significant benefits here. If there's a better
>> way of splitting the list and locking, sure, let's try that but short
>> of that I don't see anything wrong with doing this per-cpu.
> For the regular global declarations we have separate areas for "SHARED"
> per cpu data like this. See DECLARE_PER_CPU_SHARED* and friends.
>
> Even if you align a percpu_alloc() there is still the possibility that
> other percpu variables defined after this will suffer from aliasing.
> The aligning causes space to be wasted for performance critical areas
> where you want to minimize cache line usage. The variables cannot be
> packed as densely as before. I think allocations like this need to be
> separate. Simply allocate an array of these structs using
>
> kcalloc(nr_cpu_ids, sizeof(my_struct), GFP_KERNEL)?
>
> Why bother with percpu_alloc() if its not per cpu data?
>
> Well if we do not care about that detail that much then lets continue going down this patch.
>
I think that make sense. The various lists don't really need to be in
the percpu area. Allocated as an array may increase contention a bit
when multiple CPUs try to access the list heads that happen to be in the
same cacheline. However, it can speed up dlock list iterations as less
cachelines need to be traversed. I will make the change to allocate the
head array using kcalloc instead of using the percpu_alloc.
Thanks for the suggestion.
Cheers,
Longman
^ permalink raw reply [flat|nested] 10+ messages in thread