Skip to contentSkip to conversation

Initial vfs scalability patches again

PATCH In review Nick Piggin 6 participants 18 messages Jun 4, 2010 – Jun 8, 2010

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover Initial vfs scalability patches again

OK, I realised what I was smoking last time. So I put down the pipe and went to score some stronger crack. And then:
- reduced ifdefs as much as feasible
- add more comments, avoided churn
- vastly improved lock library code, works with lockdep
- added helpers for file list iterations
- lglock type for what was previously open coded in file list locking

It looks in much better shape now I hope. Al would you consider them?

With all patches applied, I ran some single threaded microbenchmarks, and it was difficult to tell much difference from the noise. I don't claim that there is no slowdown because there is more instructions and memory accesses for SMP. But it doesn't seem too bad.

Opteron, ran each test 30 times. Each run lasts for 3 seconds performing as many operations as possible. Between each 10 runs, a rebooted. After all that you still get artifacts, oh well.

Difference at 95.0% confidence (times, positive means patch is slower)
dup/close No difference proven at 95.0% confidence
open/close -2.48989% +/- 0.538414%
creat/unlink 3.14688% +/- 0.32411%

#1 lore raw

PATCH 1/4 fs: cleanup files_lock

Lock tty_files with a new spinlock, tty_files_lock; provide helpers to manipulate the per-sb files list; unexport the files_lock spinlock.

---
 drivers/char/pty.c       |    6 +++++-
 drivers/char/tty_io.c    |   26 ++++++++++++++++++--------
 fs/file_table.c          |   42 ++++++++++++++++++------------------------
 fs/open.c                |    4 ++--
 include/linux/fs.h       |    7 ++-----
 include/linux/tty.h      |    1 +
 security/selinux/hooks.c |    4 ++--
 7 files changed, 48 insertions(+), 42 deletions(-)
drivers/char/pty.c +5 -1
Index: linux-2.6/drivers/char/pty.c
===================================================================
@@ -650,7 +650,11 @@ static int __ptmx_open(struct inode *ino
 
 	set_bit(TTY_PTY_LOCK, &tty->flags); /* LOCK THE SLAVE */
 	filp->private_data = tty;
-	file_move(filp, &tty->tty_files);
+
+	file_sb_list_del(filp); /* __dentry_open has put it on the sb list */
+	spin_lock(&tty_files_lock);
+	list_add(&filp->f_u.fu_list, &tty->tty_files);
+	spin_unlock(&tty_files_lock);
 
 	retval = devpts_pty_new(inode, tty->link);
 	if (retval)
drivers/char/tty_io.c +18 -8
Index: linux-2.6/drivers/char/tty_io.c
===================================================================
@@ -136,6 +136,9 @@ LIST_HEAD(tty_drivers);			/* linked list
 DEFINE_MUTEX(tty_mutex);
 EXPORT_SYMBOL(tty_mutex);
 
+/* Spinlock to protect the tty->tty_files list */
+DEFINE_SPINLOCK(tty_files_lock);
+
 static ssize_t tty_read(struct file *, char __user *, size_t, loff_t *);
 static ssize_t tty_write(struct file *, const char __user *, size_t, loff_t *);
 ssize_t redirected_tty_write(struct file *, const char __user *,
@@ -234,11 +237,11 @@ static int check_tty_count(struct tty_st
 	struct list_head *p;
 	int count = 0;
 
-	file_list_lock();
+	spin_lock(&tty_files_lock);
 	list_for_each(p, &tty->tty_files) {
 		count++;
 	}
-	file_list_unlock();
+	spin_unlock(&tty_files_lock);
 	if (tty->driver->type == TTY_DRIVER_TYPE_PTY &&
 	    tty->driver->subtype == PTY_TYPE_SLAVE &&
 	    tty->link && tty->link->count)
@@ -517,7 +520,7 @@ static void do_tty_hangup(struct work_st
 	lock_kernel();
 	check_tty_count(tty, "do_tty_hangup");
 
-	file_list_lock();
+	spin_lock(&tty_files_lock);
 	/* This breaks for file handles being sent over AF_UNIX sockets ? */
 	list_for_each_entry(filp, &tty->tty_files, f_u.fu_list) {
 		if (filp->f_op->write == redirected_tty_write)
@@ -528,7 +531,7 @@ static void do_tty_hangup(struct work_st
 		tty_fasync(-1, filp, 0);	/* can't block */
 		filp->f_op = &hung_up_tty_fops;
 	}
-	file_list_unlock();
+	spin_unlock(&tty_files_lock);
 
 	tty_ldisc_hangup(tty);
 
@@ -1419,9 +1422,9 @@ static void release_one_tty(struct work_
 	tty_driver_kref_put(driver);
 	module_put(driver->owner);
 
-	file_list_lock();
+	spin_lock(&tty_files_lock);
 	list_del_init(&tty->tty_files);
-	file_list_unlock();
+	spin_unlock(&tty_files_lock);
 
 	put_pid(tty->pgrp);
 	put_pid(tty->session);
@@ -1666,7 +1669,10 @@ int tty_release(struct inode *inode, str
 	 *  - do_tty_hangup no longer sees this file descriptor as
 	 *    something that needs to be handled for hangups.
 	 */
-	file_kill(filp);
+	spin_lock(&tty_files_lock);
+	BUG_ON(list_empty(&filp->f_u.fu_list));
+	list_del_init(&filp->f_u.fu_list);
+	spin_unlock(&tty_files_lock);
 	filp->private_data = NULL;
 
 	/*
@@ -1835,7 +1841,11 @@ got_driver:
 	}
 
 	filp->private_data = tty;
-	file_move(filp, &tty->tty_files);
+	BUG_ON(list_empty(&filp->f_u.fu_list));
+	file_sb_list_del(filp); /* __dentry_open has put it on the sb list */
+	spin_lock(&tty_files_lock);
+	list_add(&filp->f_u.fu_list, &tty->tty_files);
+	spin_unlock(&tty_files_lock);
 	check_tty_count(tty, "tty_open");
 	if (tty->driver->type == TTY_DRIVER_TYPE_PTY &&
 	    tty->driver->subtype == PTY_TYPE_MASTER)
fs/file_table.c +18 -24

104 lines not on this page · raw message

fs/open.c +2 -2
Index: linux-2.6/fs/open.c
===================================================================
@@ -675,7 +675,7 @@ static struct file *__dentry_open(struct
 	f->f_path.mnt = mnt;
 	f->f_pos = 0;
 	f->f_op = fops_get(inode->i_fop);
-	file_move(f, &inode->i_sb->s_files);
+	file_sb_list_add(f, inode->i_sb);
 
 	error = security_dentry_open(f, cred);
 	if (error)
@@ -721,7 +721,7 @@ cleanup_all:
 			mnt_drop_write(mnt);
 		}
 	}
-	file_kill(f);
+	file_sb_list_del(f);
 	f->f_path.dentry = NULL;
 	f->f_path.mnt = NULL;
 cleanup_file:
include/linux/fs.h +2 -5
Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -949,9 +949,6 @@ struct file {
 	unsigned long f_mnt_write_state;
 #endif
 };
-extern spinlock_t files_lock;
-#define file_list_lock() spin_lock(&files_lock);
-#define file_list_unlock() spin_unlock(&files_lock);
 
 #define get_file(x)	atomic_long_inc(&(x)->f_count)
 #define fput_atomic(x)	atomic_long_add_unless(&(x)->f_count, -1, 1)
@@ -2182,8 +2179,8 @@ static inline void insert_inode_hash(str
 	__insert_inode_hash(inode, inode->i_ino);
 }
 
-extern void file_move(struct file *f, struct list_head *list);
-extern void file_kill(struct file *f);
+extern void file_sb_list_add(struct file *f, struct super_block *sb);
+extern void file_sb_list_del(struct file *f);
 #ifdef CONFIG_BLOCK
 struct bio;
 extern void submit_bio(int, struct bio *);
security/selinux/hooks.c +2 -2
Index: linux-2.6/security/selinux/hooks.c
===================================================================
@@ -2219,7 +2219,7 @@ static inline void flush_unauthorized_fi
 
 	tty = get_current_tty();
 	if (tty) {
-		file_list_lock();
+		spin_lock(&tty_files_lock);
 		if (!list_empty(&tty->tty_files)) {
 			struct inode *inode;
 
@@ -2235,7 +2235,7 @@ static inline void flush_unauthorized_fi
 				drop_tty = 1;
 			}
 		}
-		file_list_unlock();
+		spin_unlock(&tty_files_lock);
 		tty_kref_put(tty);
 	}
 	/* Reset controlling tty. */
include/linux/tty.h +1 -0
Index: linux-2.6/include/linux/tty.h
===================================================================
@@ -467,6 +467,7 @@ extern struct tty_struct *tty_pair_get_t
 extern struct tty_struct *tty_pair_get_pty(struct tty_struct *tty);
 
 extern struct mutex tty_mutex;
+extern spinlock_t tty_files_lock;
 
 extern void tty_write_unlock(struct tty_struct *tty);
 extern int tty_write_lock(struct tty_struct *tty, int ndelay);
#2 lore raw

Re: [patch 1/4] fs: cleanup files_lock

Quoted 2 lines · Nick Piggin

Lock tty_files with a new spinlock, tty_files_lock; provide helpers to manipulate the per-sb files list; unexport the files_lock spinlock.

I'm still not entirely happy with this. You keep making the tty a special case by removing it from the files per-sb files list while nothing else in the system is removed from it.

Thinks would be much better if you could untangle the tty code from abuse of file->f_u.fu_list entirely. And from a naive look at the tty code that actually seems pretty easy. file->private for ttys currently directly points to the tty struct. If you add a tty_private there which points back to the file, the tty and contains a list_head the open files in tty code tracking code can be completely divorced from the per-sb file tracking. After that we can decide what to do with the per-sb file tracking, where my favourite still is to get rid of it entirely.

#3 lore raw

Re: [patch 1/4] fs: cleanup files_lock

Quoted 8 lines · Christoph Hellwig
Quoted 2 lines · Nick Piggin

Lock tty_files with a new spinlock, tty_files_lock; provide helpers to manipulate the per-sb files list; unexport the files_lock spinlock.

I'm still not entirely happy with this. You keep making the tty a special case by removing it from the files per-sb files list while nothing else in the system is removed from it.

Quoted 7 lines

Thinks would be much better if you could untangle the tty code from abuse of file->f_u.fu_list entirely. And from a naive look at the tty code that actually seems pretty easy. file->private for ttys currently directly points to the tty struct. If you add a tty_private there which points back to the file, the tty and contains a list_head the open files in tty code tracking code can be completely divorced from the per-sb file tracking.

Well it is already a special case, I just switched it to using a different lock for its private list. I wanted to keep surgery to a minimum.

Quoted 3 lines

After that we can decide what to do
with the per-sb file tracking, where my favourite still is to get rid of it entirely.

Again, this would be nice, but I didn't see an easy way to do it. Even if refcounting obsoleted may_remount_ro, we still have mark_files_ro. It's no more complex to rip this all out after my patch. I don't see the problem in doing this patch. It has good numbers.

#4 lore raw

Re: [patch 1/4] fs: cleanup files_lock

Quoted 6 lines · Nick Piggin

Again, this would be nice, but I didn't see an easy way to do it. Even if refcounting obsoleted may_remount_ro, we still have mark_files_ro. It's no more complex to rip this all out after my patch. I don't see the problem in doing this patch. It has good numbers.

Yes agreed. The global lock is currently really painful on workloads that do a lot of opens and anything to make this better would be good asap.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#5 lore raw

Re: [patch 1/4] fs: cleanup files_lock

In reply to Nick Piggin
Quoted 3 lines · Nick Piggin

Well it is already a special case, I just switched it to using a different lock for its private list. I wanted to keep surgery to a minimum.

You make it even more special. Really, the right thing here is to fix that hack for real.

#6 lore raw

RFC PATCH 1/1 tty: stop abusing file->f_u.fu_list

In reply to Nick Piggin

The ttry code currently abuses the file anchor for the per-sb file list to track instances of a given tty. But there's no good reason for that, we can just install a proxy object in file->private that gets added to the list and points to the tty and keep the list away from VFS internals.

Note that I've just if 0'd the selinux mess poking into it. While we could trivially port it to the new code by making the tty_private structure public this code is just too revolting to be kept around. It would never have been there anyway if a person with some amount of clue had ever reviewed the selinux code. And no, it's not just the tty portion, the rest of that function is just as bad.

drivers/char/pty.c +4 -2
Index: linux-2.6/drivers/char/pty.c
===================================================================
@@ -649,8 +649,10 @@ static int __ptmx_open(struct inode *ino
 	}
 
 	set_bit(TTY_PTY_LOCK, &tty->flags); /* LOCK THE SLAVE */
-	filp->private_data = tty;
-	file_move(filp, &tty->tty_files);
+
+	retval = tty_add_file(tty, filp);
+	if (retval)
+		goto out;
 
 	retval = devpts_pty_new(inode, tty->link);
 	if (retval)
drivers/char/tty_io.c +75 -31

254 lines not on this page · raw message

security/selinux/hooks.c +4 -1
Index: linux-2.6/security/selinux/hooks.c
===================================================================
@@ -2212,11 +2212,13 @@ static inline void flush_unauthorized_fi
 {
 	struct common_audit_data ad;
 	struct file *file, *devnull = NULL;
-	struct tty_struct *tty;
 	struct fdtable *fdt;
 	long j = -1;
 	int drop_tty = 0;
 
+#ifdef SANITIY /* selinux on crack */
+	struct tty_struct *tty;
+
 	tty = get_current_tty();
 	if (tty) {
 		file_list_lock();
@@ -2238,6 +2240,7 @@ static inline void flush_unauthorized_fi
 		file_list_unlock();
 		tty_kref_put(tty);
 	}
+#endif
 	/* Reset controlling tty. */
 	if (drop_tty)
 		no_tty();
include/linux/tty.h +2 -0
Index: linux-2.6/include/linux/tty.h
===================================================================
@@ -288,6 +288,7 @@ struct tty_struct {
 	void *disc_data;
 	void *driver_data;
 	struct list_head tty_files;
+	spinlock_t tty_files_lock;
 
 #define N_TTY_BUF_SIZE 4096
 
@@ -455,6 +456,7 @@ extern void proc_clear_tty(struct task_s
 extern struct tty_struct *get_current_tty(void);
 extern void tty_default_fops(struct file_operations *fops);
 extern struct tty_struct *alloc_tty_struct(void);
+extern int tty_add_file(struct tty_struct *tty, struct file *file);
 extern void free_tty_struct(struct tty_struct *tty);
 extern void initialize_tty_struct(struct tty_struct *tty,
 		struct tty_driver *driver, int idx);
fs/file_table.c +3 -2
Index: linux-2.6/fs/file_table.c
===================================================================
@@ -32,8 +32,9 @@ struct files_stat_struct files_stat = {
 	.max_files = NR_FILE
 };
 
-/* public. Not pretty! */
-__cacheline_aligned_in_smp DEFINE_SPINLOCK(files_lock);
+static __cacheline_aligned_in_smp DEFINE_SPINLOCK(files_lock);
+#define file_list_lock() spin_lock(&files_lock);
+#define file_list_unlock() spin_unlock(&files_lock);
 
 /* SLAB cache for file structures */
 static struct kmem_cache *filp_cachep __read_mostly;
include/linux/fs.h +0 -5
Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -949,9 +949,6 @@ struct file {
 	unsigned long f_mnt_write_state;
 #endif
 };
-extern spinlock_t files_lock;
-#define file_list_lock() spin_lock(&files_lock);
-#define file_list_unlock() spin_unlock(&files_lock);
 
 #define get_file(x)	atomic_long_inc(&(x)->f_count)
 #define fput_atomic(x)	atomic_long_add_unless(&(x)->f_count, -1, 1)
@@ -2182,8 +2179,6 @@ static inline void insert_inode_hash(str
 	__insert_inode_hash(inode, inode->i_ino);
 }
 
-extern void file_move(struct file *f, struct list_head *list);
-extern void file_kill(struct file *f);
 #ifdef CONFIG_BLOCK
 struct bio;
 extern void submit_bio(int, struct bio *);
fs/internal.h +2 -0
Index: linux-2.6/fs/internal.h
===================================================================
@@ -80,6 +80,8 @@ extern void chroot_fs_refs(struct path *
 /*
  * file_table.c
  */
+extern void file_move(struct file *f, struct list_head *list);
+extern void file_kill(struct file *f);
 extern void mark_files_ro(struct super_block *);
 extern struct file *get_empty_filp(void);
 
maintainer
#7 lore raw

Re: [PATCH, RFC] tty: stop abusing file->f_u.fu_list

Quoted 6 lines · Christoph Hellwig

The ttry code currently abuses the file anchor for the per-sb file list to track instances of a given tty. But there's no good reason for that, we can just install a proxy object in file->private that gets added to the list and points to the tty and keep the list away from VFS internals.

Quoted 6 lines

Note that I've just if 0'd the selinux mess poking into it. While we could trivially port it to the new code by making the tty_private structure public this code is just too revolting to be kept around. It would never have been there anyway if a person with some amount of clue had ever reviewed the selinux code. And no, it's not just the tty portion, the rest of that function is just as bad.

This is disgusting, as much as selinux code you've mentioned ;-/

FWIW, selinux problem here is interesting - essentially, it violates its own rules since the real object here is not an inode. It's tty. And inode pretty much serves as a name - potentially one of many. So the policy should've been associated with tty instead...

#8 lore raw

Re: [PATCH, RFC] tty: stop abusing file->f_u.fu_list

In reply to Christoph Hellwig
Quoted 5 lines · Christoph Hellwig

The ttry code currently abuses the file anchor for the per-sb file list to track instances of a given tty. But there's no good reason for that, we can just install a proxy object in file->private that gets added to the list and points to the tty and keep the list away from VFS internals.

Well thanks for this. Yes it is an obviously nicer way to do it, so tty doesn't have to know what vfs uses files list for.

Quoted 6 lines

Note that I've just if 0'd the selinux mess poking into it. While we could trivially port it to the new code by making the tty_private structure public this code is just too revolting to be kept around. It would never have been there anyway if a person with some amount of clue had ever reviewed the selinux code. And no, it's not just the tty portion, the rest of that function is just as bad.

Why is it a mess? Just because of the conceptual nastiness of checking a tty object via a random one of its inodes? How would be a better way to do this?

I think for a first pass, a simple conversion for all code would be good for me because then it stops blocking the scaling patch. (and it's more bisectable).

#9 lore raw

Re: [PATCH, RFC] tty: stop abusing file->f_u.fu_list

In reply to Christoph Hellwig
Quoted 5 lines · Christoph Hellwig

The ttry code currently abuses the file anchor for the per-sb file list to track instances of a given tty. But there's no good reason for that, we can just install a proxy object in file->private that gets added to the list and points to the tty and keep the list away from VFS internals.

Well this code looks like the error handling is broken and it's pretty convoluted to fix (eg. tty_release requires tty from filp but is called to clean up code from before tty file private structure is allocated).

So I really prefer to put my original patch first. I really don't see how it makes the tty code more of a special case. In both cases, it must know that the vfs does not require the file's presence on the s_files list so it can be reused for tty code. After my patch, it no longer knows any details about how the vfs does locking for the list.

Possibly a lighter way to do what you want is to have the vfs not use fu_list for device inodes and define drivers to be allowed to use it for their own purpose. But that is easily possible after my patch.

#10 lore raw

PATCH 2/4 lglock: introduce special lglock and brlock spin locks

In reply to Nick Piggin

This patch introduces "local-global" locks (lglocks). These can be used to:

- Provide fast exclusive access to per-CPU data, with exclusive access to another CPU's data allowed but possibly subject to contention, and to provide very slow exclusive access to all per-CPU data.
- Or to provide very fast and scalable read serialisation, and to provide very slow exclusive serialisation of data (not necessarily per-CPU data).

Brlocks are also implemented as a short-hand notation for the latter use case.

Thanks to Paul for local/global naming convention.

Cc Al Viro <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Frank Mayhar <[email protected]>,
Cc John Stultz <[email protected]>
Cc Andi Kleen <[email protected]>
---
 include/linux/lglock.h |  165 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)
include/linux/lglock.h new file +165 -0
Index: linux-2.6/include/linux/lglock.h
===================================================================
@@ -0,0 +1,165 @@
+/*
+ * Specialised local-global spinlock. Can only be declared as global variables
+ * to avoid overhead and keep things simple (and we don't want to start using
+ * these inside dynamically allocated structures).
+ *
+ * "local/global locks" (lglocks) can be used to:
+ *
+ * - Provide fast exclusive access to per-CPU data, with exclusive access to
+ *   another CPU's data allowed but possibly subject to contention, and to
+ *   provide very slow exclusive access to all per-CPU data.
+ * - Or to provide very fast and scalable read serialisation, and to provide
+ *   very slow exclusive serialisation of data (not necessarily per-CPU data).
+ *
+ * Brlocks are also implemented as a short-hand notation for the latter use
+ * case.
+ *
+ * Copyright 2009, 2010, Nick Piggin, Novell Inc.
+ */
+#ifndef __LINUX_LGLOCK_H
+#define __LINUX_LGLOCK_H
+
+#include <linux/spinlock.h>
+#include <linux/lockdep.h>
+#include <linux/percpu.h>
+#include <asm/atomic.h>
+
+/* can make br locks by using local lock for read side, global lock for write */
+#define br_lock_init(name)	name##_lock_init()
+#define br_read_lock(name)	name##_local_lock()
+#define br_read_unlock(name)	name##_local_unlock()
+#define br_write_lock(name)	name##_global_lock()
+#define br_write_unlock(name)	name##_global_unlock()
+#define atomic_dec_and_br_write_lock(atomic, name)	name##_atomic_dec_and_global_lock(atomic)
+
+#define DECLARE_BRLOCK(name)	DECLARE_LGLOCK(name)
+#define DEFINE_BRLOCK(name)	DEFINE_LGLOCK(name)
+
+
+#define lg_lock_init(name)	name##_lock_init()
+#define lg_local_lock(name)	name##_local_lock()
+#define lg_local_unlock(name)	name##_local_unlock()
+#define lg_local_lock_cpu(name, cpu)	name##_local_lock_cpu(cpu)
+#define lg_local_unlock_cpu(name, cpu)	name##_local_unlock_cpu(cpu)
+#define lg_global_lock(name)	name##_global_lock()
+#define lg_global_unlock(name)	name##_global_unlock()
+#define atomic_dec_and_lg_global_lock(atomic, name)	name##_atomic_dec_and_global_lock(atomic)
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+#define LOCKDEP_INIT_MAP lockdep_init_map
+
+#define DEFINE_LGLOCK_LOCKDEP(name)					\
+ struct lock_class_key name##_lock_key;					\
+ struct lockdep_map name##_lock_dep_map;				\
+ EXPORT_SYMBOL(name##_lock_dep_map)
+
+#else
+#define LOCKDEP_INIT_MAP(a, b, c, d)
+
+#define DEFINE_LGLOCK_LOCKDEP(name)
+#endif
+
+
+#define DECLARE_LGLOCK(name)						\
+ extern void name##_lock_init(void);					\
+ extern void name##_local_lock(void);					\
+ extern void name##_local_unlock(void);					\
+ extern void name##_local_lock_cpu(int cpu);				\
+ extern void name##_local_unlock_cpu(int cpu);				\
+ extern void name##_global_lock(void);					\
+ extern void name##_global_unlock(void);				\
+ extern int name##_atomic_dec_and_global_lock(atomic_t *a);		\
+
+#define DEFINE_LGLOCK(name)						\
+									\
+ DEFINE_PER_CPU(arch_spinlock_t, name##_lock);				\
+ DEFINE_LGLOCK_LOCKDEP(name);						\
+									\
+ void name##_lock_init(void) {						\
+	int i;								\
+	LOCKDEP_INIT_MAP(&name##_lock_dep_map, #name, &name##_lock_key, 0); \
+	for_each_possible_cpu(i) {					\
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		*lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;	\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_lock_init);					\
+									\
+ void name##_local_lock(void) {						\
+	arch_spinlock_t *lock;						\
+	preempt_disable();						\
+	rwlock_acquire_read(&name##_lock_dep_map, 0, 0, _THIS_IP_);	\
+	lock = &__get_cpu_var(name##_lock);				\
+	arch_spin_lock(lock);						\
+ }									\
+ EXPORT_SYMBOL(name##_local_lock);					\
+									\
+ void name##_local_unlock(void) {					\
+	arch_spinlock_t *lock;						\
+	rwlock_release(&name##_lock_dep_map, 1, _THIS_IP_);		\
+	lock = &__get_cpu_var(name##_lock);				\
+	arch_spin_unlock(lock);						\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_local_unlock);					\
+									\
+ void name##_local_lock_cpu(int cpu) {			\
+	arch_spinlock_t *lock;						\
+	preempt_disable();						\
+	rwlock_acquire_read(&name##_lock_dep_map, 0, 0, _THIS_IP_);	\
+	lock = &per_cpu(name##_lock, cpu);				\
+	arch_spin_lock(lock);						\
+ }									\
+ EXPORT_SYMBOL(name##_local_lock_cpu);					\
+									\
+ void name##_local_unlock_cpu(int cpu) {			\
+	arch_spinlock_t *lock;						\
+	rwlock_release(&name##_lock_dep_map, 1, _THIS_IP_);		\
+	lock = &per_cpu(name##_lock, cpu);				\
+	arch_spin_unlock(lock);						\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_local_unlock_cpu);				\
+									\
+ void name##_global_lock(void) {					\
+	int i;								\
+	preempt_disable();						\
+	rwlock_acquire(&name##_lock_dep_map, 0, 0, _RET_IP_);		\
+	for_each_online_cpu(i) {					\
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_lock(lock);					\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_global_lock);					\
+									\
+ void name##_global_unlock(void) {					\
+	int i;								\
+	rwlock_release(&name##_lock_dep_map, 1, _RET_IP_);		\
+	for_each_online_cpu(i) {					\
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_unlock(lock);					\
+	}								\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_global_unlock);					\
+									\
+ static int name##_atomic_dec_and_global_lock__failed(atomic_t *a) {	\
+	name##_global_lock();						\
+	if (!atomic_dec_and_test(a)) {					\
+		name##_global_unlock();					\
+		return 0;						\
+	}								\
+	return 1;							\
+ }									\
+ 									\
+ int name##_atomic_dec_and_global_lock(atomic_t *a) {			\
+	if (likely(atomic_add_unless(a, -1, 1)))			\
+		return 0;						\
+	return name##_atomic_dec_and_global_lock__failed(a);		\
+ }									\
+ EXPORT_SYMBOL(name##_atomic_dec_and_global_lock);
+
+#endif
#11 lore raw

Re: [patch 2/4] lglock: introduce special lglock and brlock spin locks

Quoted 22 lines · Nick Piggin

pièce jointe document texte brut (kernel-introduce-brlock.patch) This patch introduces "local-global" locks (lglocks). These can be used to:

- Provide fast exclusive access to per-CPU data, with exclusive access to another CPU's data allowed but possibly subject to contention, and to provide very slow exclusive access to all per-CPU data.
- Or to provide very fast and scalable read serialisation, and to provide very slow exclusive serialisation of data (not necessarily per-CPU data).

Brlocks are also implemented as a short-hand notation for the latter use case.

Thanks to Paul for local/global naming convention.

Cc Al Viro <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Frank Mayhar <[email protected]>,
Cc John Stultz <[email protected]>
Cc Andi Kleen <[email protected]>
Quoted 4 lines
---
 include/linux/lglock.h |  165 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)

IMHO some changes in Documentation/ would be needed

include/linux/lglock.h line 129

Quoted 6 lines
								\

+ void name##_global_lock(void) { \

include/linux/lglock.h new file +4 -0
+	int i;								\
+	preempt_disable();						\
+	rwlock_acquire(&name##_lock_dep_map, 0, 0, _RET_IP_);		\
+	for_each_online_cpu(i) {					\

for_each_possible_cpu()

include/linux/lglock.h line 140

Quoted 11 lines
include/linux/lglock.h new file +11 -0
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_lock(lock);					\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_global_lock);					\
+									\
+ void name##_global_unlock(void) {					\
+	int i;								\
+	rwlock_release(&name##_lock_dep_map, 1, _RET_IP_);		\
+	for_each_online_cpu(i) {					\

for_each_possible_cpu()

Quoted 8 lines
include/linux/lglock.h new file +8 -0
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_unlock(lock);					\
+	}								\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_global_unlock);					\
+									\
#12 lore raw

Re: [patch 2/4] lglock: introduce special lglock and brlock spin locks

Quoted 28 lines · Eric Dumazet
Quoted 22 lines · Nick Piggin

pièce jointe document texte brut (kernel-introduce-brlock.patch) This patch introduces "local-global" locks (lglocks). These can be used to:

- Provide fast exclusive access to per-CPU data, with exclusive access to another CPU's data allowed but possibly subject to contention, and to provide very slow exclusive access to all per-CPU data.
- Or to provide very fast and scalable read serialisation, and to provide very slow exclusive serialisation of data (not necessarily per-CPU data).

Brlocks are also implemented as a short-hand notation for the latter use case.

Thanks to Paul for local/global naming convention.

Cc Al Viro <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Frank Mayhar <[email protected]>,
Cc John Stultz <[email protected]>
Cc Andi Kleen <[email protected]>
Quoted 4 lines
---
 include/linux/lglock.h |  165 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)
Quoted 1 line

IMHO some changes in Documentation/ would be needed

I wonder where, and what?

Quoted 7 lines

include/linux/lglock.h line 129

Quoted 5 lines

+ void name##_global_lock(void) { \

include/linux/lglock.h new file +4 -0
+	int i;								\
+	preempt_disable();						\
+	rwlock_acquire(&name##_lock_dep_map, 0, 0, _RET_IP_);		\
+	for_each_online_cpu(i) {					\

for_each_possible_cpu()

Oh good spotting. brlock does not need this but lglock does if it protects offline cpu data too. Maybe better to move file handles in the event of hotplug.

#13 lore raw

Re: [patch 2/4] lglock: introduce special lglock and brlock spin locks

Quoted 7 lines · Nick Piggin
Quoted 1 line · Eric Dumazet

IMHO some changes in Documentation/ would be needed

I wonder where, and what?

Documentation/memory-barriers.txt (around line 1111)

Documentation/spinlocks.txt (change its name ?)

Section 1 : spinlocks

Section 2 : rwlocks

Section 3 : lglock/brlock ?

#14 lore raw

Re: [patch 2/4] lglock: introduce special lglock and brlock spin locks

In reply to Nick Piggin
Quoted 8 lines · Nick Piggin

This patch introduces "local-global" locks (lglocks). These can be used to:

- Provide fast exclusive access to per-CPU data, with exclusive access to another CPU's data allowed but possibly subject to contention, and to provide very slow exclusive access to all per-CPU data.
- Or to provide very fast and scalable read serialisation, and to provide very slow exclusive serialisation of data (not necessarily per-CPU data).

Quoted 4 lines

Brlocks are also implemented as a short-hand notation for the latter use case.

Thanks to Paul for local/global naming convention.

;-)

One set of questions about how this relates to real-time below.

(And I agree with Eric's point about for_each_possible_cpu(), FWIW.)

Quoted 98 lines
Cc Al Viro <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Frank Mayhar <[email protected]>,
Cc John Stultz <[email protected]>
Cc Andi Kleen <[email protected]>
---
 include/linux/lglock.h |  165 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)

Index: linux-2.6/include/linux/lglock.h
===================================================================

include/linux/lglock.h new file +81 -0
@@ -0,0 +1,165 @@
+/*
+ * Specialised local-global spinlock. Can only be declared as global variables
+ * to avoid overhead and keep things simple (and we don't want to start using
+ * these inside dynamically allocated structures).
+ *
+ * "local/global locks" (lglocks) can be used to:
+ *
+ * - Provide fast exclusive access to per-CPU data, with exclusive access to
+ *   another CPU's data allowed but possibly subject to contention, and to
+ *   provide very slow exclusive access to all per-CPU data.
+ * - Or to provide very fast and scalable read serialisation, and to provide
+ *   very slow exclusive serialisation of data (not necessarily per-CPU data).
+ *
+ * Brlocks are also implemented as a short-hand notation for the latter use
+ * case.
+ *
+ * Copyright 2009, 2010, Nick Piggin, Novell Inc.
+ */
+#ifndef __LINUX_LGLOCK_H
+#define __LINUX_LGLOCK_H
+
+#include <linux/spinlock.h>
+#include <linux/lockdep.h>
+#include <linux/percpu.h>
+#include <asm/atomic.h>
+
+/* can make br locks by using local lock for read side, global lock for write */
+#define br_lock_init(name)	name##_lock_init()
+#define br_read_lock(name)	name##_local_lock()
+#define br_read_unlock(name)	name##_local_unlock()
+#define br_write_lock(name)	name##_global_lock()
+#define br_write_unlock(name)	name##_global_unlock()
+#define atomic_dec_and_br_write_lock(atomic, name)	name##_atomic_dec_and_global_lock(atomic)
+
+#define DECLARE_BRLOCK(name)	DECLARE_LGLOCK(name)
+#define DEFINE_BRLOCK(name)	DEFINE_LGLOCK(name)
+
+
+#define lg_lock_init(name)	name##_lock_init()
+#define lg_local_lock(name)	name##_local_lock()
+#define lg_local_unlock(name)	name##_local_unlock()
+#define lg_local_lock_cpu(name, cpu)	name##_local_lock_cpu(cpu)
+#define lg_local_unlock_cpu(name, cpu)	name##_local_unlock_cpu(cpu)
+#define lg_global_lock(name)	name##_global_lock()
+#define lg_global_unlock(name)	name##_global_unlock()
+#define atomic_dec_and_lg_global_lock(atomic, name)	name##_atomic_dec_and_global_lock(atomic)
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+#define LOCKDEP_INIT_MAP lockdep_init_map
+
+#define DEFINE_LGLOCK_LOCKDEP(name)					\
+ struct lock_class_key name##_lock_key;					\
+ struct lockdep_map name##_lock_dep_map;				\
+ EXPORT_SYMBOL(name##_lock_dep_map)
+
+#else
+#define LOCKDEP_INIT_MAP(a, b, c, d)
+
+#define DEFINE_LGLOCK_LOCKDEP(name)
+#endif
+
+
+#define DECLARE_LGLOCK(name)						\
+ extern void name##_lock_init(void);					\
+ extern void name##_local_lock(void);					\
+ extern void name##_local_unlock(void);					\
+ extern void name##_local_lock_cpu(int cpu);				\
+ extern void name##_local_unlock_cpu(int cpu);				\
+ extern void name##_global_lock(void);					\
+ extern void name##_global_unlock(void);				\
+ extern int name##_atomic_dec_and_global_lock(atomic_t *a);		\
+
+#define DEFINE_LGLOCK(name)						\
+									\
+ DEFINE_PER_CPU(arch_spinlock_t, name##_lock);				\
+ DEFINE_LGLOCK_LOCKDEP(name);						\
+									\
+ void name##_lock_init(void) {						\
+	int i;								\
+	LOCKDEP_INIT_MAP(&name##_lock_dep_map, #name, &name##_lock_key, 0); \
+	for_each_possible_cpu(i) {					\

include/linux/lglock.h line 91

Quoted 10 lines
include/linux/lglock.h new file +10 -0
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		*lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;	\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_lock_init);					\
+									\
+ void name##_local_lock(void) {						\
+	arch_spinlock_t *lock;						\
+	preempt_disable();						\

In a -rt kernel, I believe we would not want the above preempt_disable(). Of course, in this case the arch_spin_lock() would need to become spin_lock() or some such.

The main point of this approach is to avoid cross-CPU holding of these locks, correct? And then the point of arch_spin_lock() is to avoid the redundant preempt_disable(), right?

Thanx, Paul

Quoted 76 lines
include/linux/lglock.h new file +74 -0
+	rwlock_acquire_read(&name##_lock_dep_map, 0, 0, _THIS_IP_);	\
+	lock = &__get_cpu_var(name##_lock);				\
+	arch_spin_lock(lock);						\
+ }									\
+ EXPORT_SYMBOL(name##_local_lock);					\
+									\
+ void name##_local_unlock(void) {					\
+	arch_spinlock_t *lock;						\
+	rwlock_release(&name##_lock_dep_map, 1, _THIS_IP_);		\
+	lock = &__get_cpu_var(name##_lock);				\
+	arch_spin_unlock(lock);						\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_local_unlock);					\
+									\
+ void name##_local_lock_cpu(int cpu) {			\
+	arch_spinlock_t *lock;						\
+	preempt_disable();						\
+	rwlock_acquire_read(&name##_lock_dep_map, 0, 0, _THIS_IP_);	\
+	lock = &per_cpu(name##_lock, cpu);				\
+	arch_spin_lock(lock);						\
+ }									\
+ EXPORT_SYMBOL(name##_local_lock_cpu);					\
+									\
+ void name##_local_unlock_cpu(int cpu) {			\
+	arch_spinlock_t *lock;						\
+	rwlock_release(&name##_lock_dep_map, 1, _THIS_IP_);		\
+	lock = &per_cpu(name##_lock, cpu);				\
+	arch_spin_unlock(lock);						\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_local_unlock_cpu);				\
+									\
+ void name##_global_lock(void) {					\
+	int i;								\
+	preempt_disable();						\
+	rwlock_acquire(&name##_lock_dep_map, 0, 0, _RET_IP_);		\
+	for_each_online_cpu(i) {					\
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_lock(lock);					\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_global_lock);					\
+									\
+ void name##_global_unlock(void) {					\
+	int i;								\
+	rwlock_release(&name##_lock_dep_map, 1, _RET_IP_);		\
+	for_each_online_cpu(i) {					\
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		arch_spin_unlock(lock);					\
+	}								\
+	preempt_enable();						\
+ }									\
+ EXPORT_SYMBOL(name##_global_unlock);					\
+									\
+ static int name##_atomic_dec_and_global_lock__failed(atomic_t *a) {	\
+	name##_global_lock();						\
+	if (!atomic_dec_and_test(a)) {					\
+		name##_global_unlock();					\
+		return 0;						\
+	}								\
+	return 1;							\
+ }									\
+ 									\
+ int name##_atomic_dec_and_global_lock(atomic_t *a) {			\
+	if (likely(atomic_add_unless(a, -1, 1)))			\
+		return 0;						\
+	return name##_atomic_dec_and_global_lock__failed(a);		\
+ }									\
+ EXPORT_SYMBOL(name##_atomic_dec_and_global_lock);
+
+#endif
#15 lore raw

Re: [patch 2/4] lglock: introduce special lglock and brlock spin locks

Quoted 19 lines · Paul E. McKenney
Quoted 8 lines · Nick Piggin

This patch introduces "local-global" locks (lglocks). These can be used to:

- Provide fast exclusive access to per-CPU data, with exclusive access to another CPU's data allowed but possibly subject to contention, and to provide very slow exclusive access to all per-CPU data.
- Or to provide very fast and scalable read serialisation, and to provide very slow exclusive serialisation of data (not necessarily per-CPU data).

Quoted 4 lines

Brlocks are also implemented as a short-hand notation for the latter use case.

Thanks to Paul for local/global naming convention.

;-)

One set of questions about how this relates to real-time below.

(And I agree with Eric's point about for_each_possible_cpu(), FWIW.)

...

Quoted 19 lines
Quoted 4 lines

+ void name##_lock_init(void) { \

include/linux/lglock.h new file +3 -0
+	int i;								\
+	LOCKDEP_INIT_MAP(&name##_lock_dep_map, #name, &name##_lock_key, 0); \
+	for_each_possible_cpu(i) {					\

include/linux/lglock.h line 91

Quoted 10 lines
include/linux/lglock.h new file +10 -0
+		arch_spinlock_t *lock;					\
+		lock = &per_cpu(name##_lock, i);			\
+		*lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;	\
+	}								\
+ }									\
+ EXPORT_SYMBOL(name##_lock_init);					\
+									\
+ void name##_local_lock(void) {						\
+	arch_spinlock_t *lock;						\
+	preempt_disable();						\

In a -rt kernel, I believe we would not want the above preempt_disable(). Of course, in this case the arch_spin_lock() would need to become spin_lock() or some such.

Quoted 3 lines

The main point of this approach is to avoid cross-CPU holding of these locks, correct? And then the point of arch_spin_lock() is to avoid the redundant preempt_disable(), right?

Yes. Preempt count and possibly lockdep will have issues with taking so many nested locks in the write path.

The brlock version of this does avoid holding cross-CPU locks in the fastpath. The lglock version used by files_list locking in the next patch does need to sometimes take a cross-CPU lock.

#16 lore raw

PATCH 3/4 fs: scale files_lock

In reply to Nick Piggin

Improve scalability of files_lock by adding per-cpu, per-sb files lists, protected with an lglock. The lglock provides fast access to the per-cpu lists to add and remove files. It also provides a snapshot of all the per-cpu lists (although this is very slow).

One difficulty with this approach is that a file can be removed from the list by another CPU. We must track which per-cpu list the file is on. Scalability could suffer if files are frequently removed from different cpu's list.

However loads with frequent removal of files imply short interval between adding and removing the files, and the scheduler attempts to avoid moving processes too far away. Also, even in the case of cross-CPU removal, the hardware has much more opportunity to parallelise cacheline transfers with N cachelines than with 1.

A worst-case test of 1 CPU allocating files subsequently being freed by N CPUs degenerates to contending on a single lock, which is no worse than before. When more than one CPU are allocating files, even if they are always freed by different CPUs, there will be more parallelism than the single-lock case.

Testing results:

On a 2 socket, 8 core opteron, I measure the number of times the lock is taken to remove the file, the number of times it is removed by the same CPU that added it, and the number of times it is removed by the same node that added it.

Booting: locks= 25049 cpu-hits= 23174 (92.5%) node-hits= 23945 (95.6%)
kbuild -j16 locks=2281913 cpu-hits=2208126 (96.8%) node-hits=2252674 (98.7%)
dbench 64 locks=4306582 cpu-hits=4287247 (99.6%) node-hits=4299527 (99.8%)

So a file is removed from the same CPU it was added by over 90% of the time. It remains within the same node 95% of the time.

Tim Chen run some numbers for a 64 thread Nehalem system performing a compile.

throughput
2.6.34-rc2 24.5
+patch 24.9

                us      sys     idle    IO wait (in %)
2.6.34-rc2      51.25   28.25   17.25   3.25
+patch          53.75   18.5    19      8.75

So significantly less CPU time spent in kernel code, higher idle time and slightly higher throughput.

Single threaded performance difference was within the noise of even my microbenchmarks. That is not to say one does not exist, the code is larger and more memory accesses required.

Cc Al Viro <[email protected]>
Cc Frank Mayhar <[email protected]>,
Cc John Stultz <[email protected]>
Cc "Eric W. Biederman" <[email protected]>,
Cc Tim Chen <[email protected]>
Cc Andi Kleen <[email protected]>
---
 fs/file_table.c    |   99 +++++++++++++++++++++++++++++++++++++++++++----------
 fs/super.c         |   18 +++++++++
 include/linux/fs.h |    7 +++
 3 files changed, 106 insertions(+), 18 deletions(-)
fs/file_table.c +81 -18
Index: linux-2.6/fs/file_table.c
===================================================================
@@ -20,7 +20,9 @@
 #include <linux/cdev.h>
 #include <linux/fsnotify.h>
 #include <linux/sysctl.h>
+#include <linux/lglock.h>
 #include <linux/percpu_counter.h>
+#include <linux/percpu.h>
 #include <linux/ima.h>
 
 #include <asm/atomic.h>
@@ -32,7 +34,8 @@ struct files_stat_struct files_stat = {
 	.max_files = NR_FILE
 };
 
-static __cacheline_aligned_in_smp DEFINE_SPINLOCK(files_lock);
+DECLARE_LGLOCK(files_lglock);
+DEFINE_LGLOCK(files_lglock);
 
 /* SLAB cache for file structures */
 static struct kmem_cache *filp_cachep __read_mostly;
@@ -327,30 +330,89 @@ void put_filp(struct file *file)
 	}
 }
 
+/* helper for file_sb_list_add to reduce ifdefs */
+static inline void __file_sb_list_add(struct file *file, struct super_block *sb)
+{
+	struct list_head *list;
+#ifdef CONFIG_SMP
+	int cpu;
+	cpu = smp_processor_id();
+	file->f_sb_list_cpu = cpu;
+	list = per_cpu_ptr(sb->s_files, cpu);
+#else
+	list = &sb->s_files;
+#endif
+	list_add(&file->f_u.fu_list, list);
+}
+
+/**
+ * file_sb_list_add - add a file to the sb's file list
+ * @file: file to add
+ * @sb: sb to add it to
+ *
+ * Use this function to associate a file with the superblock of the inode it
+ * refers to.
+ */
 void file_sb_list_add(struct file *file, struct super_block *sb)
 {
-	spin_lock(&files_lock);
-	BUG_ON(!list_empty(&file->f_u.fu_list));
-	list_add(&file->f_u.fu_list, &sb->s_files);
-	spin_unlock(&files_lock);
+	lg_local_lock(files_lglock);
+	__file_sb_list_add(file, sb);
+	lg_local_unlock(files_lglock);
 }
 
+/**
+ * file_sb_list_del - remove a file from the sb's file list
+ * @file: file to remove
+ * @sb: sb to remove it from
+ *
+ * Use this function to remove a file from its superblock.
+ */
 void file_sb_list_del(struct file *file)
 {
 	if (!list_empty(&file->f_u.fu_list)) {
-		spin_lock(&files_lock);
+		lg_local_lock_cpu(files_lglock, file->f_sb_list_cpu);
 		list_del_init(&file->f_u.fu_list);
-		spin_unlock(&files_lock);
+		lg_local_unlock_cpu(files_lglock, file->f_sb_list_cpu);
 	}
 }
 
+#ifdef CONFIG_SMP
+
+/*
+ * These macros iterate all files on all CPUs for a given superblock.
+ * files_lglock must be held globally.
+ */
+#define do_file_list_for_each_entry(__sb, __file)		\
+{								\
+	int i;							\
+	for_each_possible_cpu(i) {				\
+		struct list_head *list;				\
+		list = per_cpu_ptr((__sb)->s_files, i);		\
+		list_for_each_entry((__file), list, f_u.fu_list)
+
+#define while_file_list_for_each_entry				\
+	}							\
+}
+
+#else
+
+#define do_file_list_for_each_entry(__sb, __file)		\
+{								\
+	struct list_head *list;					\
+	list = &(sb)->s_files;					\
+	list_for_each_entry((__file), list, f_u.fu_list)
+
+#define while_file_list_for_each_entry				\
+}
+
+#endif
+
 int fs_may_remount_ro(struct super_block *sb)
 {
 	struct file *file;
-
 	/* Check that no files are currently opened for writing. */
-	spin_lock(&files_lock);
-	list_for_each_entry(file, &sb->s_files, f_u.fu_list) {
+	lg_global_lock(files_lglock);
+	do_file_list_for_each_entry(sb, file) {
 		struct inode *inode = file->f_path.dentry->d_inode;
 
 		/* File with pending delete? */
@@ -360,11 +422,11 @@ int fs_may_remount_ro(struct super_block
 		/* Writeable file? */
 		if (S_ISREG(inode->i_mode) && (file->f_mode & FMODE_WRITE))
 			goto too_bad;
-	}
-	spin_unlock(&files_lock);
+	} while_file_list_for_each_entry;
+	lg_global_unlock(files_lglock);
 	return 1; /* Tis' cool bro. */
 too_bad:
-	spin_unlock(&files_lock);
+	lg_global_unlock(files_lglock);
 	return 0;
 }
 
@@ -380,8 +442,8 @@ void mark_files_ro(struct super_block *s
 	struct file *f;
 
 retry:
-	spin_lock(&files_lock);
-	list_for_each_entry(f, &sb->s_files, f_u.fu_list) {
+	lg_global_lock(files_lglock);
+	do_file_list_for_each_entry(sb, f) {
 		struct vfsmount *mnt;
 		if (!S_ISREG(f->f_path.dentry->d_inode->i_mode))
 		       continue;
@@ -397,12 +459,12 @@ retry:
 		file_release_write(f);
 		mnt = mntget(f->f_path.mnt);
 		/* This can sleep, so we can't hold the spinlock. */
-		spin_unlock(&files_lock);
+		lg_global_unlock(files_lglock);
 		mnt_drop_write(mnt);
 		mntput(mnt);
 		goto retry;
-	}
-	spin_unlock(&files_lock);
+	} while_file_list_for_each_entry;
+	lg_global_unlock(files_lglock);
 }
 
 void __init files_init(unsigned long mempages)
@@ -422,5 +484,6 @@ void __init files_init(unsigned long mem
 	if (files_stat.max_files < NR_FILE)
 		files_stat.max_files = NR_FILE;
 	files_defer_init();
+	lg_lock_init(files_lglock);
 	percpu_counter_init(&nr_files, 0);
 } 
fs/super.c +18 -0
Index: linux-2.6/fs/super.c
===================================================================
@@ -54,7 +54,22 @@ static struct super_block *alloc_super(s
 			s = NULL;
 			goto out;
 		}
+#ifdef CONFIG_SMP
+		s->s_files = alloc_percpu(struct list_head);
+		if (!s->s_files) {
+			security_sb_free(s);
+			kfree(s);
+			s = NULL;
+			goto out;
+		} else {
+			int i;
+
+			for_each_possible_cpu(i)
+				INIT_LIST_HEAD(per_cpu_ptr(s->s_files, i));
+		}
+#else
 		INIT_LIST_HEAD(&s->s_files);
+#endif
 		INIT_LIST_HEAD(&s->s_instances);
 		INIT_HLIST_HEAD(&s->s_anon);
 		INIT_LIST_HEAD(&s->s_inodes);
@@ -108,6 +123,9 @@ out:
  */
 static inline void destroy_super(struct super_block *s)
 {
+#ifdef CONFIG_SMP
+	free_percpu(s->s_files);
+#endif
 	security_sb_free(s);
 	kfree(s->s_subtype);
 	kfree(s->s_options);
include/linux/fs.h +7 -0
Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -925,6 +925,9 @@ struct file {
 #define f_vfsmnt	f_path.mnt
 	const struct file_operations	*f_op;
 	spinlock_t		f_lock;  /* f_ep_links, f_flags, no IRQ */
+#ifdef CONFIG_SMP
+	int			f_sb_list_cpu;
+#endif
 	atomic_long_t		f_count;
 	unsigned int 		f_flags;
 	fmode_t			f_mode;
@@ -1339,7 +1342,11 @@ struct super_block {
 
 	struct list_head	s_inodes;	/* all inodes */
 	struct hlist_head	s_anon;		/* anonymous dentries for (nfs) exporting */
+#ifdef CONFIG_SMP
+	struct list_head __percpu *s_files;
+#else
 	struct list_head	s_files;
+#endif
 	/* s_dentry_lru and s_nr_dentry_unused are protected by dcache_lock */
 	struct list_head	s_dentry_lru;	/* unused dentry lru */
 	int			s_nr_dentry_unused;	/* # of dentry on lru */
#17 lore raw

PATCH 4/4 fs: brlock vfsmount_lock

In reply to Nick Piggin

Use a brlock for the vfsmount lock. It must be taken for write whenever modifying the mount hash or associated fields, and may be taken for read when performing mount hash lookups.

The number of atomics should remain the same for fastpath rlock cases, though code will be slightly slower due to per-cpu access. Scalability will probably not be much improved in common cases yet, due to other locks getting in the way. However independent path lookups over mountpoints should be one case where scalability is improved.

The slowpath will be made significantly slower due to use of brlock. On a 64 core, 64 socket, 32 node Altix system (so a decent amount of latency to remote nodes), a simple umount microbenchmark (mount --bind mnt mnt2 ; umount mnt2 loop 1000 times), before this patch it took 6.8s, afterwards took 7.1s, for about 5% increase in elapsed time.

---
 fs/dcache.c    |   11 +--
 fs/internal.h  |    5 +
 fs/namei.c     |    7 +-
 fs/namespace.c |  174 +++++++++++++++++++++++++++++++++++----------------------
 fs/pnode.c     |   11 ++-
 5 files changed, 131 insertions(+), 77 deletions(-)
fs/dcache.c +6 -5
Index: linux-2.6/fs/dcache.c
===================================================================
@@ -1926,7 +1926,7 @@ char *__d_path(const struct path *path,
 	char *end = buffer + buflen;
 	char *retval;
 
-	spin_lock(&vfsmount_lock);
+	br_read_lock(vfsmount_lock);
 	prepend(&end, &buflen, "\0", 1);
 	if (d_unlinked(dentry) &&
 		(prepend(&end, &buflen, " (deleted)", 10) != 0))
@@ -1962,7 +1962,7 @@ char *__d_path(const struct path *path,
 	}
 
 out:
-	spin_unlock(&vfsmount_lock);
+	br_read_unlock(vfsmount_lock);
 	return retval;
 
 global_root:
@@ -2193,11 +2193,12 @@ int path_is_under(struct path *path1, st
 	struct vfsmount *mnt = path1->mnt;
 	struct dentry *dentry = path1->dentry;
 	int res;
-	spin_lock(&vfsmount_lock);
+
+	br_read_lock(vfsmount_lock);
 	if (mnt != path2->mnt) {
 		for (;;) {
 			if (mnt->mnt_parent == mnt) {
-				spin_unlock(&vfsmount_lock);
+				br_read_unlock(vfsmount_lock);
 				return 0;
 			}
 			if (mnt->mnt_parent == path2->mnt)
@@ -2207,7 +2208,7 @@ int path_is_under(struct path *path1, st
 		dentry = mnt->mnt_mountpoint;
 	}
 	res = is_subdir(dentry, path2->dentry);
-	spin_unlock(&vfsmount_lock);
+	br_read_unlock(vfsmount_lock);
 	return res;
 }
 EXPORT_SYMBOL(path_is_under);
fs/namei.c +4 -3
Index: linux-2.6/fs/namei.c
===================================================================
@@ -601,15 +601,16 @@ int follow_up(struct path *path)
 {
 	struct vfsmount *parent;
 	struct dentry *mountpoint;
-	spin_lock(&vfsmount_lock);
+
+	br_read_lock(vfsmount_lock);
 	parent = path->mnt->mnt_parent;
 	if (parent == path->mnt) {
-		spin_unlock(&vfsmount_lock);
+		br_read_unlock(vfsmount_lock);
 		return 0;
 	}
 	mntget(parent);
 	mountpoint = dget(path->mnt->mnt_mountpoint);
-	spin_unlock(&vfsmount_lock);
+	br_read_unlock(vfsmount_lock);
 	dput(path->dentry);
 	path->dentry = mountpoint;
 	mntput(path->mnt);
fs/namespace.c +98 -57

471 lines not on this page · raw message

fs/pnode.c +9 -2
Index: linux-2.6/fs/pnode.c
===================================================================
@@ -126,6 +126,9 @@ static int do_make_slave(struct vfsmount
 	return 0;
 }
 
+/*
+ * vfsmount lock must be held for write
+ */
 void change_mnt_propagation(struct vfsmount *mnt, int type)
 {
 	if (type == MS_SHARED) {
@@ -270,12 +273,12 @@ int propagate_mnt(struct vfsmount *dest_
 		prev_src_mnt  = child;
 	}
 out:
-	spin_lock(&vfsmount_lock);
+	br_write_lock(vfsmount_lock);
 	while (!list_empty(&tmp_list)) {
 		child = list_first_entry(&tmp_list, struct vfsmount, mnt_hash);
 		umount_tree(child, 0, &umount_list);
 	}
-	spin_unlock(&vfsmount_lock);
+	br_write_unlock(vfsmount_lock);
 	release_mounts(&umount_list);
 	return ret;
 }
@@ -296,6 +299,8 @@ static inline int do_refcount_check(stru
  * other mounts its parent propagates to.
  * Check if any of these mounts that **do not have submounts**
  * have more references than 'refcnt'. If so return busy.
+ *
+ * vfsmount lock must be held for read or write
  */
 int propagate_mount_busy(struct vfsmount *mnt, int refcnt)
 {
@@ -353,6 +358,8 @@ static void __propagate_umount(struct vf
  * collect all mounts that receive propagation from the mount in @list,
  * and return these additional mounts in the same list.
  * @list: the list of mounts to be unmounted.
+ *
+ * vfsmount lock must be held for write
  */
 int propagate_umount(struct list_head *list)
 {
fs/internal.h +4 -1
Index: linux-2.6/fs/internal.h
===================================================================
@@ -9,6 +9,8 @@
  * 2 of the License, or (at your option) any later version.
  */
 
+#include <linux/lglock.h>
+
 struct super_block;
 struct linux_binprm;
 struct path;
@@ -70,7 +72,8 @@ extern struct vfsmount *copy_tree(struct
 
 extern void __init mnt_init(void);
 
-extern spinlock_t vfsmount_lock;
+DECLARE_BRLOCK(vfsmount_lock);
+
 
 /*
  * fs_struct.c