[RFC PATCH 3/3] fs/proc: split the inode list

[Huang Shijie]

The global s_inode_list_lock is heavily contended in procfs
on a 384-CPU, 12-NUMA-node Hygon machine running Hadoop TestDFSIO:
  #hadoop jar xxxx.jar TestDFSIO -read -nrFiles 1000 -size 100MB

The hadoop will create lot of threads during the test.
The perf shows it consuming ~90% of the lock hotspot in procfs.
The lock is hit from both directions:
   -- inode creation (~49%) :
           getdents64 ->
              proc_readfd_common ->
	         new_inode ->
		   inode_sb_list_add()

   -- inode eviction (~41%):
           process exit ->
	      release_task ->
	         proc_invalidate_siblings_dcache ->
		     evict ->
		        inode_sb_list_del()

This patch spreads the inode list across per-shard locks for procfs:
   --- Add "shards" pointer shares a union with s_inodes.
       Guard all shard accesses with an explicit s_inode_list_sharded
       field in super_block.

   --- Add inode_list_add()/inode_list_del() callbacks to super_operations;
       procfs implements them to round-robin inodes
       onto nr_shards = DIV_ROUND_UP(num_possible_cpus(), 32)
       shards allocated at mount time, each protected by its own spinlock.

   --- evict_inodes(), generic_shutdown_super()
       iterate the shards when the super_block inode list is sharded.
       struct inode_shard is cacheline-aligned to avoid false
       sharing between shard locks on different NUMA nodes.

This reduces the s_inode_list_lock hotspot from ~90% to ~1% in above
TestDFSIO. And we can improve the hadoop exec performance over 50%.

Signed-off-by: Huang Shijie <huangsj@xxxxxxxx>
---
 fs/inode.c                     | 80 ++++++++++++++++++++++------------
 fs/proc/inode.c                | 53 ++++++++++++++++++++++
 fs/proc/internal.h             |  2 +
 fs/proc/root.c                 |  6 +++
 fs/super.c                     | 40 +++++++++++++----
 include/linux/fs/super_types.h | 22 +++++++++-
 include/linux/proc_fs.h        |  1 +
 7 files changed, 167 insertions(+), 37 deletions(-)

diff --git a/fs/inode.c b/fs/inode.c
index ba7da39be4a3..687c2e299258 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -635,6 +635,10 @@ void inode_sb_list_add(struct inode *inode)
 {
 	struct super_block *sb = inode->i_sb;
 
+	if (sb->s_inode_list_sharded && sb->s_op->inode_list_add) {
+		sb->s_op->inode_list_add(sb, inode);
+		return;
+	}
 	spin_lock(&sb->s_inode_list_lock);
 	list_add(&inode->i_sb_list, &sb->s_inodes);
 	spin_unlock(&sb->s_inode_list_lock);
@@ -646,6 +650,10 @@ static inline void inode_sb_list_del(struct inode *inode)
 	struct super_block *sb = inode->i_sb;
 
 	if (!list_empty(&inode->i_sb_list)) {
+		if (sb->s_inode_list_sharded && sb->s_op->inode_list_del) {
+			sb->s_op->inode_list_del(sb, inode);
+			return;
+		}
 		spin_lock(&sb->s_inode_list_lock);
 		list_del_init(&inode->i_sb_list);
 		spin_unlock(&sb->s_inode_list_lock);
@@ -879,41 +887,57 @@ void evict_inodes(struct super_block *sb)
 {
 	struct inode *inode;
 	LIST_HEAD(dispose);
+	struct list_head *head;
+	spinlock_t *lock;
+	unsigned int nr, i;
+	const bool sharded = sb->s_inode_list_sharded;
 
-again:
-	spin_lock(&sb->s_inode_list_lock);
-	list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
-		if (icount_read_once(inode))
-			continue;
+	nr = sharded ? sb->nr_shards : 1;
 
-		spin_lock(&inode->i_lock);
-		if (icount_read(inode)) {
-			spin_unlock(&inode->i_lock);
-			continue;
-		}
-		if (inode_state_read(inode) & (I_NEW | I_FREEING | I_WILL_FREE)) {
-			spin_unlock(&inode->i_lock);
-			continue;
+	for (i = 0; i < nr; i++) {
+		if (sharded) {
+			head = &sb->shards[i].list;
+			lock = &sb->shards[i].lock;
+		} else {
+			head = &sb->s_inodes;
+			lock = &sb->s_inode_list_lock;
 		}
 
-		inode_state_set(inode, I_FREEING);
-		inode_lru_list_del(inode);
-		spin_unlock(&inode->i_lock);
-		list_add(&inode->i_lru, &dispose);
+again:
+		spin_lock(lock);
+		list_for_each_entry(inode, head, i_sb_list) {
+			if (icount_read_once(inode))
+				continue;
 
-		/*
-		 * We can have a ton of inodes to evict at unmount time given
-		 * enough memory, check to see if we need to go to sleep for a
-		 * bit so we don't livelock.
-		 */
-		if (need_resched()) {
-			spin_unlock(&sb->s_inode_list_lock);
-			cond_resched();
-			dispose_list(&dispose);
-			goto again;
+			spin_lock(&inode->i_lock);
+			if (icount_read(inode)) {
+				spin_unlock(&inode->i_lock);
+				continue;
+			}
+			if (inode_state_read(inode) & (I_NEW | I_FREEING | I_WILL_FREE)) {
+				spin_unlock(&inode->i_lock);
+				continue;
+			}
+
+			inode_state_set(inode, I_FREEING);
+			inode_lru_list_del(inode);
+			spin_unlock(&inode->i_lock);
+			list_add(&inode->i_lru, &dispose);
+
+			/*
+			 * We can have a ton of inodes to evict at unmount time given
+			 * enough memory, check to see if we need to go to sleep for a
+			 * bit so we don't livelock.
+			 */
+			if (need_resched()) {
+				spin_unlock(lock);
+				cond_resched();
+				dispose_list(&dispose);
+				goto again;
+			}
 		}
+		spin_unlock(lock);
 	}
-	spin_unlock(&sb->s_inode_list_lock);
 
 	dispose_list(&dispose);
 }
diff --git a/fs/proc/inode.c b/fs/proc/inode.c
index b7634f975d98..d412018b73d9 100644
--- a/fs/proc/inode.c
+++ b/fs/proc/inode.c
@@ -65,6 +65,7 @@ static struct inode *proc_alloc_inode(struct super_block *sb)
 	ei->sysctl_entry = NULL;
 	INIT_HLIST_NODE(&ei->sibling_inodes);
 	ei->ns_ops = NULL;
+	ei->shard_idx = 0;
 	return &ei->vfs_inode;
 }
 
@@ -80,6 +81,56 @@ static void proc_free_inode(struct inode *inode)
 	kmem_cache_free(proc_inode_cachep, PROC_I(inode));
 }
 
+static void proc_inode_list_add(struct super_block *sb, struct inode *inode)
+{
+	struct proc_fs_info *fs_info = proc_sb_info(sb);
+	struct proc_inode *ei = PROC_I(inode);
+	struct inode_shard *shard;
+	unsigned int idx, seq;
+
+	seq = atomic_fetch_inc(&fs_info->shard_seq);
+	idx = seq % sb->nr_shards;
+	ei->shard_idx = idx;
+	shard = &sb->shards[idx];
+
+	spin_lock(&shard->lock);
+	list_add(&inode->i_sb_list, &shard->list);
+	spin_unlock(&shard->lock);
+}
+
+static void proc_inode_list_del(struct super_block *sb, struct inode *inode)
+{
+	struct proc_inode *ei = PROC_I(inode);
+	struct inode_shard *shard = &sb->shards[ei->shard_idx];
+
+	spin_lock(&shard->lock);
+	list_del_init(&inode->i_sb_list);
+	spin_unlock(&shard->lock);
+}
+
+#define PROC_LIST_ALIGN	32
+int proc_init_inode_shards(struct super_block *sb)
+{
+	struct inode_shard *shards;
+	unsigned int nr_shards;
+	int i;
+
+	nr_shards = DIV_ROUND_UP(num_possible_cpus(), PROC_LIST_ALIGN);
+	shards = kcalloc(nr_shards, sizeof(*shards), GFP_KERNEL);
+	if (!shards)
+		return -ENOMEM;
+
+	for (i = 0; i < nr_shards; i++) {
+		INIT_LIST_HEAD(&shards[i].list);
+		spin_lock_init(&shards[i].lock);
+	}
+
+	sb->shards = shards;
+	sb->nr_shards = nr_shards;
+	sb->s_inode_list_sharded = true;
+	return 0;
+}
+
 static void init_once(void *foo)
 {
 	struct proc_inode *ei = (struct proc_inode *) foo;
@@ -191,6 +242,8 @@ const struct super_operations proc_sops = {
 	.evict_inode	= proc_evict_inode,
 	.statfs		= simple_statfs,
 	.show_options	= proc_show_options,
+	.inode_list_add	= proc_inode_list_add,
+	.inode_list_del	= proc_inode_list_del,
 };
 
 enum {BIAS = -1U<<31};
diff --git a/fs/proc/internal.h b/fs/proc/internal.h
index 04bd6c9e65a7..edbe357263c2 100644
--- a/fs/proc/internal.h
+++ b/fs/proc/internal.h
@@ -127,6 +127,7 @@ struct proc_inode {
 	struct hlist_node sibling_inodes;
 	const struct proc_ns_operations *ns_ops;
 	struct inode vfs_inode;
+	unsigned int shard_idx;
 } __randomize_layout;
 
 /*
@@ -317,6 +318,7 @@ void proc_init_kmemcache(void);
 void proc_invalidate_siblings_dcache(struct hlist_head *inodes, spinlock_t *lock);
 void set_proc_pid_nlink(void);
 extern struct inode *proc_get_inode(struct super_block *, struct proc_dir_entry *);
+extern int proc_init_inode_shards(struct super_block *);
 extern void proc_entry_rundown(struct proc_dir_entry *);
 
 /*
diff --git a/fs/proc/root.c b/fs/proc/root.c
index 99adddfeb4a4..4bd916b88cdf 100644
--- a/fs/proc/root.c
+++ b/fs/proc/root.c
@@ -275,6 +275,10 @@ static int proc_fill_super(struct super_block *s, struct fs_context *fc)
 	s->s_time_gran = 1;
 	s->s_fs_info = fs_info;
 
+	ret = proc_init_inode_shards(s);
+	if (ret)
+		return ret;
+
 	if (fs_info->pidonly == PROC_PIDONLY_ON)
 		s->s_iflags |= SB_I_RESTRICTED_VARIANT;
 
@@ -359,6 +363,8 @@ static void proc_kill_sb(struct super_block *sb)
 	struct proc_fs_info *fs_info = proc_sb_info(sb);
 
 	kill_anon_super(sb);
+	if (sb->s_inode_list_sharded)
+		kfree(sb->shards);
 	if (fs_info) {
 		put_pid_ns(fs_info->pid_ns);
 		put_cred(fs_info->mounter_cred);
diff --git a/fs/super.c b/fs/super.c
index 4b1314545522..38a452e78ca2 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -726,7 +726,16 @@ EXPORT_SYMBOL(retire_super);
 
 static bool sb_inodes_empty(struct super_block *sb)
 {
-	return list_empty(&sb->s_inodes);
+	unsigned int i;
+
+	if (!sb->s_inode_list_sharded)
+		return list_empty(&sb->s_inodes);
+
+	for (i = 0; i < sb->nr_shards; i++)
+		if (!list_empty(&sb->shards[i].list))
+			return false;
+
+	return true;
 }
 
 /**
@@ -788,14 +797,29 @@ void generic_shutdown_super(struct super_block *sb)
 			 * iput_final() or such crashes cleanly.
 			 */
 			struct inode *inode;
-
-			spin_lock(&sb->s_inode_list_lock);
-			list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
-				inode->i_op = VFS_PTR_POISON;
-				inode->i_sb = VFS_PTR_POISON;
-				inode->i_mapping = VFS_PTR_POISON;
+			struct list_head *head;
+			spinlock_t *lock;
+			unsigned int nr, i;
+			const bool sharded = sb->s_inode_list_sharded;
+
+			nr = sharded ? sb->nr_shards : 1;
+			for (i = 0; i < nr; i++) {
+				if (sharded) {
+					head = &sb->shards[i].list;
+					lock = &sb->shards[i].lock;
+				} else {
+					head = &sb->s_inodes;
+					lock = &sb->s_inode_list_lock;
+				}
+
+				spin_lock(lock);
+				list_for_each_entry(inode, head, i_sb_list) {
+					inode->i_op = VFS_PTR_POISON;
+					inode->i_sb = VFS_PTR_POISON;
+					inode->i_mapping = VFS_PTR_POISON;
+				}
+				spin_unlock(lock);
 			}
-			spin_unlock(&sb->s_inode_list_lock);
 		}
 	}
 	/*
diff --git a/include/linux/fs/super_types.h b/include/linux/fs/super_types.h
index ecd96aeb1cee..6d6aae2d1fbc 100644
--- a/include/linux/fs/super_types.h
+++ b/include/linux/fs/super_types.h
@@ -130,8 +130,20 @@ struct super_operations {
 
 	/* Report a filesystem error */
 	void (*report_error)(const struct fserror_event *event);
+
+	void (*inode_list_add)(struct super_block *sb, struct inode *inode);
+	void (*inode_list_del)(struct super_block *sb, struct inode *inode);
 };
 
+/*
+ * Sharded inode list used by procfs to spread s_inode_list_lock contention
+ * across per-shard locks.
+ */
+struct inode_shard {
+	struct list_head	list;
+	spinlock_t		lock;
+} ____cacheline_aligned_in_smp;
+
 struct super_block {
 	struct list_head			s_list;		/* Keep this first */
 	dev_t					s_dev;		/* search index; _not_ kdev_t */
@@ -269,9 +281,17 @@ struct super_block {
 	 */
 	int s_stack_depth;
 
+	bool					s_inode_list_sharded;
+
 	/* s_inode_list_lock protects s_inodes */
 	spinlock_t				s_inode_list_lock ____cacheline_aligned_in_smp;
-	struct list_head			s_inodes;	/* all inodes */
+	union {
+		struct list_head			s_inodes;	/* all inodes */
+		struct {
+			struct inode_shard		*shards;	/* used by procfs */
+			unsigned int			nr_shards;
+		};
+	};
 
 	spinlock_t				s_inode_wblist_lock;
 	struct list_head			s_inodes_wb;	/* writeback inodes */
diff --git a/include/linux/proc_fs.h b/include/linux/proc_fs.h
index 47d7deaeed8f..37eed34f3a93 100644
--- a/include/linux/proc_fs.h
+++ b/include/linux/proc_fs.h
@@ -70,6 +70,7 @@ struct proc_fs_info {
 	const struct cred *mounter_cred;
 	enum proc_hidepid hide_pid;
 	enum proc_pidonly pidonly;
+	atomic_t shard_seq;
 	struct rcu_head rcu;
 };
 
-- 
2.53.0