lib/list_batch: A simple list insertion/deletion batching facility
Subsystems (3)
v2 cover lib/list_batch: A simple list insertion/deletion batching facility
v1->v2:
- Address feedbacks from PeterZ and Andi Kleen.
This patchset introduces a simple list insertion/deletion batching facility to batch multiple list insertion and deletion operations into a single one under one lock/unlock critical section.
Patch 1 introduces this new facility.
Patch 2 enables it for the x86 architecture.
Patch 3 makes the insertion and deletion of the VFS superblock's inode list to use the new list batching functions.
On x86-64, the generated code (gcc v4.8.5) of the inode_sb_list_add() function without the patch was:
0x0000000000001030 <+0>: callq 0x1035 <inode_sb_list_add+5> 0x0000000000001035 <+5>: push %rbp 0x0000000000001036 <+6>: mov %rsp,%rbp 0x0000000000001039 <+9>: push %rbx 0x000000000000103a <+10>: mov 0x28(%rdi),%rax 0x000000000000103e <+14>: mov %rdi,%rbx 0x0000000000001041 <+17>: lea 0x600(%rax),%rdi 0x0000000000001048 <+24>: callq 0x104d <inode_sb_list_add+29> 0x000000000000104d <+29>: mov 0x28(%rbx),%rsi 0x0000000000001051 <+33>: lea 0x120(%rbx),%rdi 0x0000000000001058 <+40>: mov 0x608(%rsi),%rdx 0x000000000000105f <+47>: add $0x608,%rsi 0x0000000000001066 <+54>: callq 0x106b <inode_sb_list_add+59> 0x000000000000106b <+59>: mov 0x28(%rbx),%rdi 0x000000000000106f <+63>: add $0x600,%rdi 0x0000000000001076 <+70>: callq *0x0 0x000000000000107d <+77>: pop %rbx 0x000000000000107e <+78>: pop %rbp 0x000000000000107f <+79>: retq
With the patch, the function became:
0x0000000000001030 <+0>: callq 0x1035 <inode_sb_list_add+5> 0x0000000000001035 <+5>: push %rbp 0x0000000000001036 <+6>: mov %rsp,%rbp 0x0000000000001039 <+9>: push %r13 0x000000000000103b <+11>: lea 0x120(%rdi),%r13 0x0000000000001042 <+18>: push %r12 0x0000000000001044 <+20>: push %rbx 0x0000000000001045 <+21>: mov 0x28(%rdi),%r12 0x0000000000001049 <+25>: lea 0x600(%r12),%rbx 0x0000000000001051 <+33>: mov %rbx,%rdi 0x0000000000001054 <+36>: callq 0x1059 <inode_sb_list_add+41> 0x0000000000001059 <+41>: test %eax,%eax 0x000000000000105b <+43>: je 0x1081 <inode_sb_list_add+81> 0x000000000000105d <+45>: mov 0x618(%r12),%rsi 0x0000000000001065 <+53>: mov %r13,%rdi 0x0000000000001068 <+56>: mov (%rsi),%rdx 0x000000000000106b <+59>: callq 0x1070 <inode_sb_list_add+64> 0x0000000000001070 <+64>: mov %rbx,%rdi 0x0000000000001073 <+67>: callq *0x0 0x000000000000107a <+74>: pop %rbx 0x000000000000107b <+75>: pop %r12 0x000000000000107d <+77>: pop %r13 0x000000000000107f <+79>: pop %rbp 0x0000000000001080 <+80>: retq 0x0000000000001081 <+81>: lea 0x618(%r12),%rdx 0x0000000000001089 <+89>: mov %r13,%rcx 0x000000000000108c <+92>: mov %rbx,%rsi 0x000000000000108f <+95>: xor %edi,%edi 0x0000000000001091 <+97>: callq 0x1096 <inode_sb_list_add+102> 0x0000000000001096 <+102>: jmp 0x107a <inode_sb_list_add+74>
For the fastpath, the only overheads are the testing of the return value of the spin_trylock function and the push/pop of 2 more registers. Other than that, they look very similar.
Waiman Long (3):
lib/list_batch: A simple list insertion/deletion batching facility lib/list_batch, x86: Enable list insertion/deletion batching for x86
vfs: Enable list batching for the superblock's inode list
arch/x86/Kconfig | 1 + fs/inode.c | 13 ++--- fs/super.c | 1 + include/linux/fs.h | 2 + include/linux/list_batch.h | 133 ++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig | 7 ++ lib/Makefile | 1 + lib/list_batch.c | 125 +++++++++++++++++++++++++++++++++++++++++ 8 files changed, 275 insertions(+), 8 deletions(-) create mode 100644 include/linux/list_batch.h create mode 100644 lib/list_batch.c
PATCH v2 1/3 lib/list_batch: A simple list insertion/deletion batching facility
Linked list insertion or deletion under lock is a very common activity in the Linux kernel. If this is the only activity under lock, the locking overhead can be pretty large compared with the actual time spent on the insertion or deletion operation itself especially on a large system with many CPUs.
This patch introduces a simple list insertion/deletion batching facility where a group of list insertion and deletion operations are grouped together in a single batch under lock. This can reduce the locking overhead and improve overall system performance.
The fast path of this batching facility will be similar in performance to the "lock; listop; unlock;" sequence of the existing code. If the lock is not available, it will enter slowpath where the batching happens.
A new config option LIST_BATCHING is added so that we can control on which architecture do we want to have this facility enabled.
--- include/linux/list_batch.h | 133 ++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig | 7 ++ lib/Makefile | 1 + lib/list_batch.c | 125 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 266 insertions(+), 0 deletions(-) create mode 100644 include/linux/list_batch.h create mode 100644 lib/list_batch.c
include/linux/list_batch.h new file +133 -0
@@ -0,0 +1,133 @@ +/* +* List insertion/deletion batching facility +* +* 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 <[email protected]> +*/ +#ifndef __LINUX_LIST_BATCH_H +#define __LINUX_LIST_BATCH_H + +#include <linux/spinlock.h> +#include <linux/list.h> + +/* +* include/linux/list_batch.h +* +* Inserting or deleting an entry from a linked list under a spinlock is a +* very common operation in the Linux kernel. If many CPUs are trying to +* grab the lock and manipulate the linked list, it can lead to significant +* lock contention and slow operation. +* +* This list operation batching facility is used to batch multiple list +* operations under one lock/unlock critical section, thus reducing the +* locking and cacheline bouncing overhead and improving overall performance. +*/ +enum list_batch_cmd { + lb_cmd_add, + lb_cmd_del, + lb_cmd_del_init +}; + +enum list_batch_state { + lb_state_waiting,/* Node is waiting */ + lb_state_batch,/* Queue head to perform batch processing */ + lb_state_done/* Job is done */ +}; + +struct list_batch_qnode { +struct list_batch_qnode *next; +struct list_head *entry; +enum list_batch_cmd cmd; +enum list_batch_state state; +}; + +struct list_batch { +struct list_head *list; +struct list_batch_qnode *tail; +}; + +#define LIST_BATCH_INIT (_list) \ + { \ + .list = _list, \ + .tail = NULL \ + } + +static inline void list_batch_init (struct list_batch *batch, +struct list_head *list) +{ + batch->list = list; + batch->tail =NULL ; +} + +static __always_inline void _list_batch_cmd(enum list_batch_cmd cmd, +struct list_head *head, +struct list_head *entry) +{ +switch (cmd) { +case lb_cmd_add: +list_add (entry, head); +break ; + +case lb_cmd_del: +list_del (entry); +break ; + +case lb_cmd_del_init: +list_del_init (entry); +break ; + } +} + +#ifdef CONFIG_LIST_BATCHING + +extern void do_list_batch_slowpath (spinlock_t *lock,enum list_batch_cmd cmd, +struct list_batch *batch, +struct list_head *entry); + +/* +* The caller is expected to pass in a constant cmd parameter. As a +* result, most of unneeded code in the switch statement of _list_batch_cmd() +* will be optimized away. This should make the fast path almost as fast +* as the "lock; listop; unlock;" sequence it replaces. +*/ +static inline void do_list_batch (spinlock_t *lock,enum list_batch_cmd cmd, +struct list_batch *batch, +struct list_head *entry) +{ +/* +* Fast path +*/ +if (likely (spin_trylock (lock))) { +_list_batch_cmd (cmd, batch->list, entry); +spin_unlock (lock); +return ; + } +do_list_batch_slowpath (lock, cmd, batch, entry); +} + + +#else /* CONFIG_LIST_BATCHING */ + +static inline void do_list_batch (spinlock_t *lock,enum list_batch_cmd cmd, +struct list_batch *batch, +struct list_head *entry) +{ +spin_lock (lock); +_list_batch_cmd (cmd, batch->list, entry); +spin_unlock (lock); +} + +#endif /* CONFIG_LIST_BATCHING */ + +#endif /* __LINUX_LIST_BATCH_H */
lib/Kconfig +7 -0
@@ -514,6 +514,13 @@ config OID_REGISTRY config UCS2_STRING tristate +config LIST_BATCHING + def_bool y if ARCH_USE_LIST_BATCHING + depends on SMP + +config ARCH_USE_LIST_BATCHING + bool + source "lib/fonts/Kconfig" config SG_SPLIT
lib/Makefile +1 -0
@@ -210,6 +210,7 @@ quiet_cmd_build_OID_registry = GEN $@ clean-files += oid_registry_data.c obj-$(CONFIG_UCS2_STRING) += ucs2_string.o +obj-$(CONFIG_LIST_BATCHING) += list_batch.o obj-$(CONFIG_UBSAN) += ubsan.o UBSAN_SANITIZE_ubsan.o := n
lib/list_batch.c new file +125 -0
125 lines not on this page · raw message
Signature · 1 line
1.7.1
Quoted 20 lines · Waiman Long
Linked list insertion or deletion under lock is a very common activity in the Linux kernel. If this is the only activity under lock, the locking overhead can be pretty large compared with the actual time spent on the insertion or deletion operation itself especially on a large system with many CPUs.
This patch introduces a simple list insertion/deletion batching facility where a group of list insertion and deletion operations are grouped together in a single batch under lock. This can reduce the locking overhead and improve overall system performance.
The fast path of this batching facility will be similar in performance to the "lock; listop; unlock;" sequence of the existing code. If the lock is not available, it will enter slowpath where the batching happens.
A new config option
LIST_BATCHINGis added so that we can control on which architecture do we want to have this facility enabled.Signed-off-by Waiman Long <[email protected]>
....
include/linux/list_batch.h line 103
Quoted 12 lines
include/linux/list_batch.h new file +12
-0+#ifdef CONFIG_LIST_BATCHING + +extern void do_list_batch_slowpath (spinlock_t *lock,enum list_batch_cmd cmd, +struct list_batch *batch, +struct list_head *entry); + +/* +* The caller is expected to pass in a constant cmd parameter. As a +* result, most of unneeded code in the switch statement of _list_batch_cmd() +* will be optimized away. This should make the fast path almost as fast +* as the "lock; listop; unlock;" sequence it replaces. +*/
This strikes me as needlessly complex. Simple inline functions are much easier to read and verify correct, and we don't have to rely on the compiler to optimise out dead code:
static inline void list_batch_add(struct list_head *entry,
struct list_batch *batch)
{
if (!spin_trylock(&batch->lock))
return do_list_batch_slowpath(entry, batch, lb_cmd_add);
list_add(entry, &batch->list)
spin_unlock(&batch->lock);
}lib/list_batch.c line 27
Quoted 10 lines
lib/list_batch.c new file +10
-0+#include <linux/list_batch.h> + +/* +* List processing batch size = 128 +* +* The batch size shouldn't be too large. Otherwise, it will be too unfair +* to the task doing the batch processing. It shouldn't be too small neither +* as the performance benefit will be reduced. +*/ +#define LB_BATCH_SIZE (1 << 7)
Ok, so arbitrary operations are going to see longer delays when they are selected as the batch processor. I'm not sure I really like this idea, as it will be the first in the queue that sees contention that takes the delay which reduces the fairness of the operations. i.e. the spinlock uses fair queuing, but now we can be grossly unfair the to the first spinner...
lib/list_batch.c line 65
Quoted 13 lines
lib/list_batch.c new file +13
-0+/* +* We rely on the implictit memory barrier of xchg() to make sure +* that node initialization will be done before its content is being +* accessed by other CPUs. +*/ + prev =xchg (&batch->tail, &node); + +if (prev) { +WRITE_ONCE (prev->next, &node); +while (READ_ONCE (node.state) == lb_state_waiting) +cpu_relax (); +if (node.state == lb_state_done) +return ;
So we spin waiting for the batch processor to process the list, or
lib/list_batch.c line 66
Quoted 1 line
lib/list_batch.c new file +1
-0+WARN_ON (node.state != lb_state_batch);
tell us we are not the batch processor.
So, effectively, the reduction in runtime is due to the fact the list operations spin on their own cache line rather than the spin lock cacheline until they have been processed and/or made the batch processor?
lib/list_batch.c line 78
Quoted 12 lines
lib/list_batch.c new file +12
-0+ } + +/* +* We are now the queue head, we should acquire the lock and +* process a batch of qnodes. +*/ + loop =LB_BATCH_SIZE ; + next = &node; +spin_lock (lock); + +do_list_again: + do {
While we are batch processing, all operations will fail the trylock and add themselves to the tail of the queue, and spin on their own cacheline at that point. So it doesn't reduce the amount of spinning, just removes the cacheline contention that slows the spinning.
Hmmm - there's another point of unfairness - when switching batch processors, other add/delete operations can get the list lock and perform their operations directly, thereby jumping the batch queue....
So at what point does simply replacing the list_head with a list_lru become more efficient than this batch processing (i.e.
https://lkml.org/lkml/2015/3/10/660)? The list_lru isn't a great fit for the inode list (doesn't need any of the special LRU/memcg stuff https://lkml.org/lkml/2015/3/16/261) but it will tell us if, like Ingo suggested, moving more towards a generic per-cpu list would provide better overall performance...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoted 40 lines · Dave Chinner
Quoted 20 lines · Waiman Long
Linked list insertion or deletion under lock is a very common activity in the Linux kernel. If this is the only activity under lock, the locking overhead can be pretty large compared with the actual time spent on the insertion or deletion operation itself especially on a large system with many CPUs.
This patch introduces a simple list insertion/deletion batching facility where a group of list insertion and deletion operations are grouped together in a single batch under lock. This can reduce the locking overhead and improve overall system performance.
The fast path of this batching facility will be similar in performance to the "lock; listop; unlock;" sequence of the existing code. If the lock is not available, it will enter slowpath where the batching happens.
A new config option
LIST_BATCHINGis added so that we can control on which architecture do we want to have this facility enabled.Signed-off-by Waiman Long<[email protected]>....
include/linux/list_batch.h line 103
Quoted 12 lines
include/linux/list_batch.h new file +12
-0+#ifdef CONFIG_LIST_BATCHING + +extern void do_list_batch_slowpath (spinlock_t *lock,enum list_batch_cmd cmd, +struct list_batch *batch, +struct list_head *entry); + +/* +* The caller is expected to pass in a constant cmd parameter. As a +* result, most of unneeded code in the switch statement of _list_batch_cmd() +* will be optimized away. This should make the fast path almost as fast +* as the "lock; listop; unlock;" sequence it replaces. +*/ This strikes me as needlessly complex. Simple inline functions are much easier to read and verify correct, and we don't have to rely on the compiler to optimise out dead code:
static inline void list_batch_add(struct
list_head*entry,
structlist_batch*batch)
Quoted 7 lines
{
if (!spin_trylock(&batch->lock))
return do_list_batch_slowpath(entry, batch, lb_cmd_add);
list_add(entry,&batch->list)
spin_unlock(&batch->lock);
}Will do so.
Quoted 8 lines
Quoted 8 lines
lib/list_batch.c new file +8
-0+#include <linux/list_batch.h> + +/* +* List processing batch size = 128 +* +* The batch size shouldn't be too large. Otherwise, it will be too unfair +* to the task doing the batch processing. It shouldn't be too small neither +* as the performance benefit will be reduced.
Quoted 9 lines
Quoted 2 lines
+ */
+#defineLB_BATCH_SIZE(1<< 7)Ok, so arbitrary operations are going to see longer delays when they are selected as the batch processor. I'm not sure I really like this idea, as it will be the first in the queue that sees contention that takes the delay which reduces the fairness of the operations. i.e. the spinlock uses fair queuing, but now we can be grossly unfair the to the first spinner...
That is certainly true. It is well known that a bit of unfairness can often improve overall system performance. Interrupt handling, for example, is also unfair to the process currently running on the CPU. The amount of unfairness is controlled by the batch size parameter. Maybe we can make this parameter a read-mostly constant set up at boot time which has a value depending on the # of CPUs in a system so that smaller system can have a smaller batch size. That will reduce the unfairness, at least in smaller systems.
Quoted 16 lines
lib/list_batch.c line 65
Quoted 13 lines
lib/list_batch.c new file +13
-0+/* +* We rely on the implictit memory barrier of xchg() to make sure +* that node initialization will be done before its content is being +* accessed by other CPUs. +*/ + prev =xchg (&batch->tail,&node); + +if (prev) { +WRITE_ONCE (prev->next,&node); +while (READ_ONCE (node.state) == lb_state_waiting) +cpu_relax (); +if (node.state == lb_state_done) +return ;So we spin waiting for the batch processor to process the list, or
Quoted 7 lines
lib/list_batch.c line 66
Quoted 1 line
lib/list_batch.c new file +1
-0+WARN_ON (node.state != lb_state_batch);tell us we are not the batch processor.
So, effectively, the reduction in runtime is due to the fact the list operations spin on their own cache line rather than the spin lock cacheline until they have been processed and/or made the batch processor?
Yes, that can a major part of it.
Quoted 18 lines
lib/list_batch.c line 78
Quoted 12 lines
lib/list_batch.c new file +12
-0+ } + +/* +* We are now the queue head, we should acquire the lock and +* process a batch of qnodes. +*/ + loop =LB_BATCH_SIZE ; + next =&node; +spin_lock (lock); + +do_list_again: + do {While we are batch processing, all operations will fail the trylock and add themselves to the tail of the queue, and spin on their own cacheline at that point. So it doesn't reduce the amount of spinning, just removes the cacheline contention that slows the spinning.
Quoted 4 lines
Hmmm - there's another point of unfairness - when switching batch processors, other add/delete operations can get the list lock and perform their operations directly, thereby jumping the batch queue....
That is true too.
Quoted 7 lines
So at what point does simply replacing the
list_headwith alist_lrubecome more efficient than this batch processing (i.e.
https://lkml.org/lkml/2015/3/10/660)? Thelist_lruisn't a great fit for the inode list (doesn't need any of the special LRU/memcg stuff https://lkml.org/lkml/2015/3/16/261) but it will tell us if, like Ingo suggested, moving more towards a generic per-cpu list would provide better overall performance...
I will take a look at the list_lru patch to see if that help. As for the per-cpu list, I tried that and it didn't quite work out.
Thanks,
Longman
Quoted 11 lines · Waiman Long
Quoted 7 lines · Dave Chinner
So at what point does simply replacing the
list_headwith alist_lrubecome more efficient than this batch processing (i.e.
https://lkml.org/lkml/2015/3/10/660)? Thelist_lruisn't a great fit for the inode list (doesn't need any of the special LRU/memcg stuff https://lkml.org/lkml/2015/3/16/261) but it will tell us if, like Ingo suggested, moving more towards a generic per-cpu list would provide better overall performance...I will take a look at the
list_lrupatch to see if that help. As for the per-cpu list, I tried that and it didn't quite work out.
OK, see my last email as to why Andi's patch didn't change anything. The list_lru implementation has a list per node, a lock per node, and each item is placed on the list for the node it is physically allocated from. Hence for local workloads, the list/lock that is accessed for add/remove should be local to the node and hence should reduce cache line contention mostly to within a single node.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoted 18 lines · Dave Chinner
Quoted 10 lines · Waiman Long
Quoted 7 lines · Dave Chinner
So at what point does simply replacing the
list_headwith alist_lrubecome more efficient than this batch processing (i.e.
https://lkml.org/lkml/2015/3/10/660)? Thelist_lruisn't a great fit for the inode list (doesn't need any of the special LRU/memcg stuff https://lkml.org/lkml/2015/3/16/261) but it will tell us if, like Ingo suggested, moving more towards a generic per-cpu list would provide better overall performance...I will take a look at the
list_lrupatch to see if that help. As for the per-cpu list, I tried that and it didn't quite work out.OK, see my last email as to why Andi's patch didn't change anything. The
list_lruimplementation has a list per node, a lock per node, and each item is placed on the list for the node it is physically allocated from. Hence for local workloads, the list/lock that is accessed for add/remove should be local to the node and hence should reduce cache line contention mostly to within a single node.
Quoted 3 lines
Cheers,
Dave.
I have just sent out a new patchset using per-cpu list with per-cpu locks. I used the per-cpu list as the changes will be simpler and easier to review. Please let me know your thought on that.
Thanks,
Longman
PATCH v2 2/3 lib/list_batch, x86: Enable list insertion/deletion batching for x86
In reply to Waiman LongSystem with a large number of CPUs will benefit from the list batching facility when the list lock is contended. If the lock isn't contended, the performance of the list batching function should be similar to the "lock; listop; unlock;" sequence that it replaces.
This patch enables it for the x86 architecture.
--- arch/x86/Kconfig | 1 + 1 files changed, 1 insertions(+), 0 deletions(-)
arch/x86/Kconfig +1 -0
@@ -42,6 +42,7 @@ config X86 select ARCH_SUPPORTS_NUMA_BALANCING if X86_64 select ARCH_USE_BUILTIN_BSWAP select ARCH_USE_CMPXCHG_LOCKREF if X86_64 + select ARCH_USE_LIST_BATCHING select ARCH_USE_QUEUED_RWLOCKS select ARCH_USE_QUEUED_SPINLOCKS select ARCH_WANT_BATCHED_UNMAP_TLB_FLUSH if SMP
Signature · 1 line
1.7.1
PATCH v2 3/3 vfs: Enable list batching for the superblock's inode list
In reply to Waiman LongThe inode_sb_list_add() and inode_sb_list_del() functions in the vfs layer just perform list addition and deletion under lock. So they can use the new list batching facility to speed up the list operations when many CPUs are trying to do it simultaneously.
In particular, the inode_sb_list_del() function can be a performance bottleneck when large applications with many threads and associated inodes exit. 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 (48 cores, 96 threads) were as follows:
Kernel Elapsed Time System Time ------ ------------ ----------- Vanilla 4.4 65.29s 82m14s Patched 4.4 45.69s 49m44s
The elapsed time and the reported system time were reduced by 30% and 40% respectively.
--- fs/inode.c | 13 +++++-------- fs/super.c | 1 + include/linux/fs.h | 2 ++ 3 files changed, 8 insertions(+), 8 deletions(-)
fs/inode.c +5 -8
@@ -424,19 +424,16 @@ 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); +do_list_batch (&inode->i_sb->s_inode_list_lock, lb_cmd_add, + &inode->i_sb->s_list_batch, &inode->i_sb_list); }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)) +do_list_batch (&inode->i_sb->s_inode_list_lock, lb_cmd_del_init, + &inode->i_sb->s_list_batch, &inode->i_sb_list); }static unsigned long hash (struct super_block *sb,unsigned long hashval)
fs/super.c +1 -0
@@ -206,6 +206,7 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags)mutex_init (&s->s_sync_lock);INIT_LIST_HEAD (&s->s_inodes);spin_lock_init (&s->s_inode_list_lock); +list_batch_init (&s->s_list_batch, &s->s_inodes);if (list_lru_init_memcg (&s->s_dentry_lru)) goto fail;
include/linux/fs.h +2 -0
@@ -9,6 +9,7 @@#include <linux/stat.h> #include <linux/cache.h> #include <linux/list.h> +#include <linux/list_batch.h> #include <linux/list_lru.h> #include <linux/llist.h> #include <linux/radix-tree.h>
@@ -1403,6 +1404,7 @@ struct super_block {/* s_inode_list_lock protects s_inodes */ spinlock_t s_inode_list_lock____cacheline_aligned_in_smp ;struct list_head s_inodes;/* all inodes */ +struct list_batch s_list_batch; };extern struct timespec current_fs_time (struct super_block *sb);
Signature · 1 line
1.7.1
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 13 lines · Waiman Long
The
inode_sb_list_add()andinode_sb_list_del()functions in the vfs layer just perform list addition and deletion under lock. So they can use the new list batching facility to speed up the list operations when many CPUs are trying to do it simultaneously.In particular, the
inode_sb_list_del()function can be a performance bottleneck when large applications with many threads and associated inodes exit. 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 (48 cores, 96 threads) were as follows:
Quoted 7 lines
Kernel Elapsed Time System Time ------ ------------ ----------- Vanilla 4.4 65.29s 82m14s Patched 4.4 45.69s 49m44sThe elapsed time and the reported system time were reduced by 30% and 40% respectively.
That's pretty impressive!
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably reasonably well cached benchmark running on a system with enough RAM? Are these perhaps thousands of temporary files, already deleted, and released when all the file descriptors are closed as part of sys_exit()?
If that's the case then I suspect an even bigger win would be not just to batch the (sb-)global list fiddling, but to potentially turn the sb list into a percpu_alloc() managed set of per CPU lists? It's a bigger change, but it could speed up a lot of other temporary file intensive usecases as well, not just batched delete.
Thanks,
Ingo
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 8 lines
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably reasonably well cached benchmark running on a system with enough RAM? Are these perhaps thousands of temporary files, already deleted, and released when all the file descriptors are closed as part of
sys_exit()?If that's the case then I suspect an even bigger win would be not just to batch the (sb-)global list fiddling, but to potentially turn the sb list into a
percpu_alloc()managed set of per CPU lists? It's a bigger change, but it could
We had such a patch in the lock elision patchkit (It avoided a lot of cache line bouncing leading to aborts)
-Andi
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 8 lines · Andi Kleen
Quoted 8 lines
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably reasonably well cached benchmark running on a system with enough RAM? Are these perhaps thousands of temporary files, already deleted, and released when all the file descriptors are closed as part of
sys_exit()?If that's the case then I suspect an even bigger win would be not just to batch the (sb-)global list fiddling, but to potentially turn the sb list into a
percpu_alloc()managed set of per CPU lists? It's a bigger change, but it could
Quoted 8 lines
We had such a patch in the lock elision patchkit (It avoided a lot of cache line bouncing leading to aborts)
-Andi
I like your patch though it cannot be applied cleanly for the current upstream kernel. I will port it to the current kernel and run my microbenchmark to see what performance gain I can get.
Cheers,
Longman
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 12 lines · Waiman Long
Quoted 11 lines · Andi Kleen
Quoted 8 lines
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably reasonably well cached benchmark running on a system with enough RAM? Are these perhaps thousands of temporary files, already deleted, and released when all the file descriptors are closed as part of
sys_exit()?If that's the case then I suspect an even bigger win would be not just to batch the (sb-)global list fiddling, but to potentially turn the sb list into a
percpu_alloc()managed set of per CPU lists? It's a bigger change, but it couldWe had such a patch in the lock elision patchkit (It avoided a lot of cache line bouncing leading to aborts)
Quoted 9 lines
Quoted 6 lines
-Andi
I like your patch though it cannot be applied cleanly for the current upstream kernel. I will port it to the current kernel and run my microbenchmark to see what performance gain I can get.
Unfortunately, using per-cpu list didn't have the performance benefit that I expected. I saw maybe 1 or 2% of performance increase, but nothing significant. I guess the bulk of the performance improvement in my patch is in the elimination of most of the cacheline transfer latencies when the lock ownership is passed from one CPU to another. Those latencies are still there even if we use the per-cpu list.
Cheers,
Longman
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 31 lines · Waiman Long
Quoted 21 lines · Waiman Long
Quoted 20 lines · Andi Kleen
Quoted 8 lines
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably
reasonably well cached benchmark running on a system with enough RAM? Are these
perhaps thousands of temporary files, already deleted, and released when all the
file descriptors are closed as part ofsys_exit()?Quoted 6 lines
If that's the case then I suspect an even bigger win would be not just to batch
the (sb-)global list fiddling, but to potentially turn the sb list into apercpu_alloc()managed set of per CPU lists? It's a bigger change, but it couldWe had such a patch in the lock elision patchkit (It avoided a lot of cache line bouncing leading to aborts)
Quoted 8 lines
Quoted 3 lines
-Andi
I like your patch though it cannot be applied cleanly for the current upstream kernel. I will port it to the current kernel and run my microbenchmark to see what performance gain I can get.
Quoted 7 lines
Unfortunately, using per-cpu list didn't have the performance benefit that I expected. I saw maybe 1 or 2% of performance increase, but nothing significant. I guess the bulk of the performance improvement in my patch is in the elimination of most of the cacheline transfer latencies when the lock ownership is passed from one CPU to another. Those latencies are still there even if we use the per-cpu list.
Now that I look at the above patch, it doesn't get rid of the global list lock. hence it won't change any of the existing global lock cacheline contention. The list structure change to per-cpu is completely irrelevant because it doesn't address the problem being seen.
A proper per-cpu list implementation will provide either per-cpu locks or some other mechanism to protect each list and eliminate a large amount of global cacheline bouncing. Given this, I would not use the above patch and results as a reason for saying this approach will not work, or be a better solution....
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
In reply to Ingo MolnarQuoted 20 lines · Ingo Molnar
Quoted 18 lines · Waiman Long
The
inode_sb_list_add()andinode_sb_list_del()functions in the vfs layer just perform list addition and deletion under lock. So they can use the new list batching facility to speed up the list operations when many CPUs are trying to do it simultaneously.In particular, the
inode_sb_list_del()function can be a performance bottleneck when large applications with many threads and associated inodes exit. 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 (48 cores, 96 threads) were as follows:Kernel Elapsed Time System Time ------ ------------ ----------- Vanilla 4.4 65.29s 82m14s Patched 4.4 45.69s 49m44s
Quoted 8 lines
Quoted 2 lines
The elapsed time and the reported system time were reduced by 30% and 40% respectively.
That's pretty impressive!
I'm wondering, why are inode_sb_list_add()/del() even called for a presumably reasonably well cached benchmark running on a system with enough RAM? Are these perhaps thousands of temporary files, already deleted, and released when all the file descriptors are closed as part of
sys_exit()?
The inodes that need to be deleted were actually procfs files which have to go away when the processes/threads exit. I encountered this problem when running the SPECjbb2013 benchmark on large machine where sometimes it might seems to hang for 30 mins or so after the benchmark complete. I wrote a simple microbenchmark to simulate this situation which is in the attachment.
Quoted 9 lines
If that's the case then I suspect an even bigger win would be not just to batch the (sb-)global list fiddling, but to potentially turn the sb list into a
percpu_alloc()managed set of per CPU lists? It's a bigger change, but it could speed up a lot of other temporary file intensive usecases as well, not just batched delete.Thanks,
Ingo
Yes, that can be another possible. I will investigate further on that one. Thanks for the suggestion.
Cheers,
Longman
/*
* 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.
*
* Authors: Waiman Long <[email protected]>
*/
/*
* This is an exit test
*/
#include <ctype.h>
#include <errno.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/syscall.h>
#define do_exit() syscall(SYS_exit)
#define gettid() syscall(SYS_gettid)
#define MAX_THREADS 2048
static inline void cpu_relax(void)
{
__asm__ __volatile__("rep;nop": : :"memory");
}static inline void atomic_inc(volatile int *v)
{
__asm__ __volatile__("lock incl %0": "+m" (*v));
}static volatile int exit_now = 0;
static volatile int threadcnt = 0;
/*
* Walk the /proc/<pid> filesystem to make them fill the dentry cache */
static void walk_procfs(void)
{
char cmdbuf[256];
pid_t tid = gettid();
snprintf(cmdbuf, sizeof(cmdbuf), "find /proc/%d > /dev/null 2>&1", tid);
if (system(cmdbuf) < 0)
perror("system() failed!");
}static void *exit_thread(void *dummy)
{
long tid = (long)dummy;
walk_procfs();
atomic_inc(&threadcnt);
/*
* Busy wait until the do_exit flag is set and then call exit
*/
while (!exit_now)
sleep(1);
do_exit();
}static void exit_test(int threads)
{
pthread_t thread[threads];
long i = 0, finish;
time_t start = time(NULL);
while (i++ < threads) {
if (pthread_create(thread + i - 1, NULL, exit_thread,
(void *)i)) {
perror("pthread_create");
exit(1);
}
#if 0
/*
* Pipelining to reduce contention & improve speed
*/
if ((i & 0xf) == 0)
while (i - threadcnt > 12)
usleep(1);
#endif
}
while (threadcnt != threads)
usleep(1);
walk_procfs();
printf("Setup time = %lus\n", time(NULL) - start);
printf("Process ready to exit!\n");
kill(0, SIGKILL);
exit(0);
}int main(int argc, char *argv[])
{
int tcnt; /* Thread counts */
char *cmd = argv[0];
if ((argc != 2) || !isdigit(argv[1][0])) {
fprintf(stderr, "Usage: %s <thread count>\n", cmd);
exit(1);
}
tcnt = strtoul(argv[1], NULL, 10);
if (tcnt > MAX_THREADS) {
fprintf(stderr, "Error: thread count should be <= %d\n",
MAX_THREADS);
exit(1);
}
exit_test(tcnt);
return 0; /* Not reaachable */
}Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
In reply to Waiman LongQuoted 10 lines · Waiman Long
The
inode_sb_list_add()andinode_sb_list_del()functions in the vfs layer just perform list addition and deletion under lock. So they can use the new list batching facility to speed up the list operations when many CPUs are trying to do it simultaneously.In particular, the
inode_sb_list_del()function can be a performance bottleneck when large applications with many threads and associated inodes exit. 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
I've never seen sb inode list contention in typical workloads in exit processing. Can you post the test script you are using?
The inode sb list contention I usually often than not, it's workloads that turn over the inode cache quickly (i.e. instantiating lots of inodes through concurrent directory traversal or create workloads). These are often latency sensitive, so I'm wondering what the effect of spinning waiting for batch processing on every contended add is going to do to lookup performance...
Quoted 7 lines
on a 4-socket Intel E7-4820 v3 system (48 cores, 96 threads) were as follows:
Kernel Elapsed Time System Time ------ ------------ ----------- Vanilla 4.4 65.29s 82m14s Patched 4.4 45.69s 49m44s
I wonder if you'd get the same results on such a benchmark simply by making the spin lock a mutex, thereby reducing the number of CPUs spinning on a single lock cacheline at any one point in time. Certainly the system time will plummet....
Quoted 15 lines
The elapsed time and the reported system time were reduced by 30% and 40% respectively.
Signed-off-by Waiman Long <[email protected]>--- fs/inode.c | 13 +++++-------- fs/super.c | 1 + include/linux/fs.h | 2 ++ 3 files changed, 8 insertions(+), 8 deletions(-)fs/inode.c +0
-0
fs/inode.c static void inode_lru_list_del(struct inode *inode) · line 428
Quoted 8 lines
fs/inode.c +2
-3@@ -424,19 +424,16 @@ 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); +do_list_batch (&inode->i_sb->s_inode_list_lock, lb_cmd_add, + &inode->i_sb->s_list_batch, &inode->i_sb_list);
I don't like the API. This should simply be:
void inode_sb_list_add(struct inode *inode)
{
list_batch_add(&inode->i_sb_list, &inode->i_sb->s_inodes);
}void inode_sb_list_del(struct inode *inode)
{
list_batch_del(&inode->i_sb_list, &inode->i_sb->s_inodes);
}And all the locks, lists and batch commands are internal to the struct list_batch and the API implementation.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH v2 3/3] vfs: Enable list batching for the superblock's inode list
Quoted 6 lines · Dave Chinner
Quoted 5 lines · Waiman Long
The
inode_sb_list_add()andinode_sb_list_del()functions in the vfs layer just perform list addition and deletion under lock. So they can use the new list batching facility to speed up the list operations when many CPUs are trying to do it simultaneously.
Quoted 7 lines
Quoted 5 lines
In particular, the
inode_sb_list_del()function can be a performance bottleneck when large applications with many threads and associated inodes exit. 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 patchI've never seen sb inode list contention in typical workloads in exit processing. Can you post the test script you are using?
I have posted it in one of my earlier email.
Quoted 6 lines
The inode sb list contention I usually often than not, it's workloads that turn over the inode cache quickly (i.e. instantiating lots of inodes through concurrent directory traversal or create workloads). These are often latency sensitive, so I'm wondering what the effect of spinning waiting for batch processing on every contended add is going to do to lookup performance...
I think the batch processor will get higher latency, but the other will see a shorter one. If each CPU has a more or less chance to become the batch processor, the overall impact to system performance should not be that significatn.
Quoted 11 lines
Quoted 7 lines
on a 4-socket Intel E7-4820 v3 system (48 cores, 96 threads) were as follows:
Kernel Elapsed Time System Time ------ ------------ ----------- Vanilla 4.4 65.29s 82m14s Patched 4.4 45.69s 49m44sI wonder if you'd get the same results on such a benchmark simply by making the spin lock a mutex, thereby reducing the number of CPUs spinning on a single lock cacheline at any one point in time. Certainly the system time will plummet....
I don't think it is a good idea to use mutex as we can't sleep.
Quoted 30 lines
Quoted 15 lines
The elapsed time and the reported system time were reduced by 30% and 40% respectively.
Signed-off-by Waiman Long<[email protected]>--- fs/inode.c | 13 +++++-------- fs/super.c | 1 + include/linux/fs.h | 2 ++ 3 files changed, 8 insertions(+), 8 deletions(-)fs/inode.c +0
-0fs/inode.c static void inode_lru_list_del(struct inode *inode) · line 428
Quoted 8 lines
fs/inode.c +2
-3@@ -424,19 +424,16 @@ 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); +do_list_batch (&inode->i_sb->s_inode_list_lock, lb_cmd_add, + &inode->i_sb->s_list_batch,&inode->i_sb_list);I don't like the API. This should simply be:
void
inode_sb_list_add(struct inode *inode){ list_batch_add(&inode->i_sb_list,&inode->i_sb->s_inodes); }
Quoted 8 lines
void
inode_sb_list_del(struct inode *inode){ list_batch_del(&inode->i_sb_list,&inode->i_sb->s_inodes); }And all the locks, lists and batch commands are internal to the struct
list_batchand the API implementation.
Points taken. I will update the patch to do that. Thanks for the review.
Cheers,
Longman