| Message ID | 1454095846-19628-4-git-send-email-Waiman.Long@hpe.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
* Waiman Long <Waiman.Long@hpe.com> wrote: > The 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. 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 -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Jan 29, 2016 at 02:30:46PM -0500, Waiman Long wrote: > The 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 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... > 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.... > The elapsed time and the reported system time were reduced by 30% > and 40% respectively. > > Signed-off-by: Waiman Long <Waiman.Long@hpe.com> > --- > fs/inode.c | 13 +++++-------- > fs/super.c | 1 + > include/linux/fs.h | 2 ++ > 3 files changed, 8 insertions(+), 8 deletions(-) > > diff --git a/fs/inode.c b/fs/inode.c > index 9f62db3..870de8c 100644 > --- a/fs/inode.c > +++ b/fs/inode.c > @@ -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.
> 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) https://git.kernel.org/cgit/linux/kernel/git/ak/linux-misc.git/commit/?h=hle315/combined&id=f1cf9e715a40f44086662ae3b29f123cf059cbf4 -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 01/30/2016 03:35 AM, Ingo Molnar wrote: > * Waiman Long<Waiman.Long@hpe.com> wrote: > >> The 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. > 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. > 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 <waiman.long@hp.com> */ /* * 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 */ }
On 02/01/2016 12:45 PM, Andi Kleen wrote: >> 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) > > https://git.kernel.org/cgit/linux/kernel/git/ak/linux-misc.git/commit/?h=hle315/combined&id=f1cf9e715a40f44086662ae3b29f123cf059cbf4 > > -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 -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 02/01/2016 05:03 PM, Waiman Long wrote: > On 02/01/2016 12:45 PM, Andi Kleen wrote: >>> 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) >> >> https://git.kernel.org/cgit/linux/kernel/git/ak/linux-misc.git/commit/?h=hle315/combined&id=f1cf9e715a40f44086662ae3b29f123cf059cbf4 >> >> >> -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 -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 01/31/2016 07:04 PM, Dave Chinner wrote: > On Fri, Jan 29, 2016 at 02:30:46PM -0500, Waiman Long wrote: >> The 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 > I'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. > 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. >> 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.... I don't think it is a good idea to use mutex as we can't sleep. >> The elapsed time and the reported system time were reduced by 30% >> and 40% respectively. >> >> Signed-off-by: Waiman Long<Waiman.Long@hpe.com> >> --- >> fs/inode.c | 13 +++++-------- >> fs/super.c | 1 + >> include/linux/fs.h | 2 ++ >> 3 files changed, 8 insertions(+), 8 deletions(-) >> >> diff --git a/fs/inode.c b/fs/inode.c >> index 9f62db3..870de8c 100644 >> --- a/fs/inode.c >> +++ b/fs/inode.c >> @@ -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. > Points taken. I will update the patch to do that. Thanks for the review. Cheers, Longman -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Feb 03, 2016 at 05:59:17PM -0500, Waiman Long wrote: > On 02/01/2016 05:03 PM, Waiman Long wrote: > >On 02/01/2016 12:45 PM, Andi Kleen wrote: > >>>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) > >> > >>https://git.kernel.org/cgit/linux/kernel/git/ak/linux-misc.git/commit/?h=hle315/combined&id=f1cf9e715a40f44086662ae3b29f123cf059cbf4 > >> > >> > >>-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. 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.
diff --git a/fs/inode.c b/fs/inode.c index 9f62db3..870de8c 100644 --- a/fs/inode.c +++ b/fs/inode.c @@ -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) diff --git a/fs/super.c b/fs/super.c index 1182af8..b0e8540 100644 --- a/fs/super.c +++ b/fs/super.c @@ -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; diff --git a/include/linux/fs.h b/include/linux/fs.h index 1a20462..11d8b77 100644 --- a/include/linux/fs.h +++ b/include/linux/fs.h @@ -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);
The 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. Signed-off-by: Waiman Long <Waiman.Long@hpe.com> --- fs/inode.c | 13 +++++-------- fs/super.c | 1 + include/linux/fs.h | 2 ++ 3 files changed, 8 insertions(+), 8 deletions(-)