files: scalable fd management (V4)

PATCH In review Dipankar Sarma 2 participants 12 messages Jun 14, 2005 – Jun 15, 2005

Subsystems (15)

Networking Documentation VFS MIPS +11 more subsystems

lore

Share & tools

lore

Dipankar Sarma

author

2005-06-14 14:28 UTC #0 lore raw

cover files: scalable fd management (V4)

This is an updated version of patchset published earlier
at - http://marc.theaimsgroup.com/?l=linux-kernel&m=111747394710704&w=2

Since then I have done the following additional testing :

1. SMP/UP kernels with and without CONFIG_PREEMPT on x86 and ppc64. running various tests like ltp, dbench, tiobench, reaim.

2. Testing with a testcase that creates > 1024 fds and exercises the vmalloc allocation and freeing path.

3. More 24+ hour runs on both x86 and ppc64

4. Touch testing with X running on a desktop.

5. Testing with __ARCH_HAS_CMPXCHG undefined. I booted and ran some basic tests with this on a ppc64 SMP box in order to exercise the hashed locking.

Additional performance #s :
---------------------------

tiobench on a 4-way ppc64 system :
(lockfree)
Test 2.6.10-vanilla Stdev 2.6.10-fd Stdev
-------------------------------------------------------------

Seqread         1428            32.47   1475.0          29.11
Randread        1469.2          17.27   1599.6          35.95
Seqwrite        262.06          9.31    246.8           30.94
Randwrite       548.38          12.49   521.4           61.98

With LL/SC based locks, cache line bouncing effect of file_lock is not as pronounced, but it still makes a difference with seq and random reads.

Andrew, would it be possible to give this some testing time in -mm ? If so, please let me know what would be an appropriate time for that and I will send patches against -mm.

Thanks
Dipankar

Dipankar Sarma

author

2005-06-14 14:30 UTC #1 lore raw

Re: [PATCH 0/6] files: fix rcu initializers

RCU head initilizer no longer needs the head varible name since we don't use list.h lists anymore.

Signed-off-by Dipankar Sarma <[email protected]>

 include/linux/rcupdate.h |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

include/linux/rcupdate.h renamed from include/linux/rcupdate.h~fix-rcu-initializer +2 -2

diff -puN include/linux/rcupdate.h~fix-rcu-initializer include/linux/rcupdate.h
@@ -52,8 +52,8 @@ struct rcu_head {
 	void (*func)(struct rcu_head *head);
 };
 
-#define RCU_HEAD_INIT(head) { .next = NULL, .func = NULL }
-#define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT(head)
+#define RCU_HEAD_INIT 	{ .next = NULL, .func = NULL }
+#define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT
 #define INIT_RCU_HEAD(ptr) do { \
        (ptr)->next = NULL; (ptr)->func = NULL; \
 } while (0)

Dipankar Sarma

author

2005-06-14 14:31 UTC #2 lore raw

Re: [PATCH 0/6] files: rcuref APIs

Adds a set of primitives to do reference counting for objects that are looked up without locks using RCU.

Signed-off-by Ravikiran Thirumalai <[email protected]>

Signed-off-by Dipankar Sarma <[email protected]>

 Documentation/RCU/rcuref.txt |   74 ++++++++++++++
 include/linux/rcuref.h       |  220 +++++++++++++++++++++++++++++++++++++++++++
 kernel/rcupdate.c            |   14 ++
 3 files changed, 308 insertions(+)

Documentation/RCU/rcuref.txt new file +74 -0

diff -puN /dev/null Documentation/RCU/rcuref.txt
@@ -0,0 +1,74 @@
+Refcounter framework for elements of lists/arrays protected by
+RCU.
+
+Refcounting on elements of  lists which are protected by traditional
+reader/writer spinlocks or semaphores are straight forward as in:
+
+1.					2.
+add()					search_and_reference()
+{					{
+	alloc_object				read_lock(&list_lock);
+	...					search_for_element
+	atomic_set(&el->rc, 1);			atomic_inc(&el->rc);	
+	write_lock(&list_lock);			...
+	add_element				read_unlock(&list_lock);
+	...					...
+	write_unlock(&list_lock);	}
+}					
+
+3.					4.
+release_referenced()			delete()
+{					{
+	...				write_lock(&list_lock);
+	atomic_dec(&el->rc, relfunc)	...
+	...				delete_element
+}					write_unlock(&list_lock);
+ 					...
+					if (atomic_dec_and_test(&el->rc))
+						kfree(el);
+					...
+					}
+
+If this list/array is made lock free using rcu as in changing the 
+write_lock in add() and delete() to spin_lock and changing read_lock
+in search_and_reference to rcu_read_lock(), the rcuref_get in 
+search_and_reference could potentially hold reference to an element which
+has already been deleted from the list/array.  rcuref_lf_get_rcu takes
+care of this scenario. search_and_reference should look as;
+
+1.					2.
+add()					search_and_reference()
+{					{
+ 	alloc_object				rcu_read_lock();
+	...					search_for_element
+	atomic_set(&el->rc, 1);			if (rcuref_inc_lf(&el->rc)) {
+	write_lock(&list_lock);				rcu_read_unlock();
+							return FAIL;
+	add_element				}
+	...					...
+	write_unlock(&list_lock);		rcu_read_unlock();
+}					}
+3.					4.
+release_referenced()			delete()
+{					{
+	...				write_lock(&list_lock);
+	rcuref_dec(&el->rc, relfunc)	...
+	...				delete_element
+}					write_unlock(&list_lock);
+ 					...
+					if (rcuref_dec_and_test(&el->rc))
+						call_rcu(&el->head, el_free);
+					...
+					}
+ 
+Sometimes, reference to the element need to be obtained in the 
+update (write) stream.  In such cases, rcuref_inc_lf might be an overkill
+since the spinlock serialising list updates are held. rcuref_inc
+is to be used in such cases.  
+For arches which do not have cmpxchg rcuref_inc_lf 
+api uses a hashed spinlock implementation and the same hashed spinlock 
+is acquired in all rcuref_xxx primitives to preserve atomicity.
+Note: Use rcuref_inc api only if you need to use rcuref_inc_lf on the
+refcounter atleast at one place.  Mixing rcuref_inc and atomic_xxx api
+might lead to races. rcuref_inc_lf() must be used in lockfree
+RCU critical sections only.

include/linux/rcuref.h new file +220 -0

220 lines not on this page · raw message

kernel/rcupdate.c renamed from kernel/rcupdate.c~rcuref-apis +14 -0

diff -puN kernel/rcupdate.c~rcuref-apis kernel/rcupdate.c
@@ -45,6 +45,7 @@
 #include <linux/percpu.h>
 #include <linux/notifier.h>
 #include <linux/rcupdate.h>
+#include <linux/rcuref.h>
 #include <linux/cpu.h>
 
 /* Definition for rcupdate control block. */

@@ -72,6 +73,19 @@ DEFINE_PER_CPU(struct rcu_data, rcu_bh_d
 static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL};
 static int maxbatch = 10;
 
+#ifndef __HAVE_ARCH_CMPXCHG
+/* 
+ * We use an array of spinlocks for the rcurefs -- similar to ones in sparc
+ * 32 bit atomic_t implementations, and a hash function similar to that
+ * for our refcounting needs.
+ * Can't help multiprocessors which donot have cmpxchg :(
+ */
+
+spinlock_t __rcuref_hash[RCUREF_HASH_SIZE] = {
+	[0 ... (RCUREF_HASH_SIZE-1)] = SPIN_LOCK_UNLOCKED
+};
+#endif
+
 /**
  * call_rcu - Queue an RCU callback for invocation after a grace period.
  * @head: structure to be used for queueing the RCU updates.

Dipankar Sarma

author

2005-06-14 14:43 UTC #3 lore raw

Re: [PATCH 3/6] files: break up files struct

In order for the RCU to work, the file table array, sets and their sizes must be updated atomically. Instead of ensuring this through too many memory barriers, we put the arrays and their sizes in a separate structure. This patch takes the first step of putting the file table elements in a separate structure fdtable that is embedded withing files_struct. It also changes all the users to refer to the file table using files_fdtable() macro. Subsequent applciation of RCU becomes easier after this.

Signed-off-by Dipankar Sarma <[email protected]>

 arch/alpha/kernel/osf_sys.c     |    4 +
 arch/sparc64/solaris/ioctl.c    |    8 ++-
 drivers/char/tty_io.c           |    4 +
 fs/compat.c                     |    9 ++--
 fs/exec.c                       |    8 ++-
 fs/fcntl.c                      |   46 +++++++++++++---------
 fs/file.c                       |   42 ++++++++++++--------
 fs/locks.c                      |    8 ++-
 fs/open.c                       |   41 +++++++++++---------
 fs/proc/array.c                 |    5 +-
 fs/proc/base.c                  |    4 +
 fs/select.c                     |   12 ++++-
 include/linux/file.h            |   23 +++++++----
 include/linux/init_task.h       |   13 ++++--
 kernel/exit.c                   |   21 ++++++----
 kernel/fork.c                   |   82 ++++++++++++++++++++++++----------------
 net/ipv4/netfilter/ipt_owner.c  |   12 ++++-
 net/ipv6/netfilter/ip6t_owner.c |    8 ++-
 security/selinux/hooks.c        |    6 +-
 19 files changed, 225 insertions(+), 131 deletions(-)

arch/alpha/kernel/osf_sys.c renamed from arch/alpha/kernel/osf_sys.c~break-up-files-struct +3 -1

diff -puN arch/alpha/kernel/osf_sys.c~break-up-files-struct arch/alpha/kernel/osf_sys.c
@@ -974,6 +974,7 @@ osf_select(int n, fd_set __user *inp, fd
 	size_t size;
 	long timeout;
 	int ret = -EINVAL;
+	struct fdtable *fdt;
 
 	timeout = MAX_SCHEDULE_TIMEOUT;
 	if (tvp) {

@@ -995,7 +996,8 @@ osf_select(int n, fd_set __user *inp, fd
 		}
 	}
 
-	if (n < 0 || n > current->files->max_fdset)
+	fdt = files_fdtable(current->files);
+	if (n < 0 || n > fdt->max_fdset)
 		goto out_nofds;
 
 	/*

arch/sparc64/solaris/ioctl.c renamed from arch/sparc64/solaris/ioctl.c~break-up-files-struct +5 -3

diff -puN arch/sparc64/solaris/ioctl.c~break-up-files-struct arch/sparc64/solaris/ioctl.c
@@ -293,11 +293,13 @@ static struct module_info {
 static inline int solaris_sockmod(unsigned int fd, unsigned int cmd, u32 arg)
 {
 	struct inode *ino;
+	struct fdtable *fdt;
 	/* I wonder which of these tests are superfluous... --patrik */
 	spin_lock(&current->files->file_lock);
-	if (! current->files->fd[fd] ||
-	    ! current->files->fd[fd]->f_dentry ||
-	    ! (ino = current->files->fd[fd]->f_dentry->d_inode) ||
+	fdt = files_fdtable(current->files);
+	if (! fdt->fd[fd] ||
+	    ! fdt->fd[fd]->f_dentry ||
+	    ! (ino = fdt->fd[fd]->f_dentry->d_inode) ||
 	    ! S_ISSOCK(ino->i_mode)) {
 		spin_unlock(&current->files->file_lock);
 		return TBADF;

drivers/char/tty_io.c renamed from drivers/char/tty_io.c~break-up-files-struct +3 -1

diff -puN drivers/char/tty_io.c~break-up-files-struct drivers/char/tty_io.c
@@ -2415,6 +2415,7 @@ static void __do_SAK(void *arg)
 	int		i;
 	struct file	*filp;
 	struct tty_ldisc *disc;
+	struct fdtable *fdt;
 	
 	if (!tty)
 		return;

@@ -2441,7 +2442,8 @@ static void __do_SAK(void *arg)
 		task_lock(p);
 		if (p->files) {
 			spin_lock(&p->files->file_lock);
-			for (i=0; i < p->files->max_fds; i++) {
+			fdt = files_fdtable(p->files);
+			for (i=0; i < fdt->max_fds; i++) {
 				filp = fcheck_files(p->files, i);
 				if (!filp)
 					continue;

fs/compat.c renamed from fs/compat.c~break-up-files-struct +5 -4

diff -puN fs/compat.c~break-up-files-struct fs/compat.c
@@ -1694,7 +1694,8 @@ compat_sys_select(int n, compat_ulong_t 
 	fd_set_bits fds;
 	char *bits;
 	long timeout;
-	int size, max_fdset, ret = -EINVAL;
+	int size, ret = -EINVAL;
+	struct fdtable *fdt;
 
 	timeout = MAX_SCHEDULE_TIMEOUT;
 	if (tvp) {

@@ -1720,9 +1721,9 @@ compat_sys_select(int n, compat_ulong_t 
 		goto out_nofds;
 
 	/* max_fdset can increase, so grab it once to avoid race */
-	max_fdset = current->files->max_fdset;
-	if (n > max_fdset)
-		n = max_fdset;
+	fdt = files_fdtable(current->files);
+	if (n > fdt->max_fdset)
+		n = fdt->max_fdset;
 
 	/*
 	 * We need 6 bitmaps (in/out/ex for both incoming and outgoing),

fs/exec.c renamed from fs/exec.c~break-up-files-struct +5 -3

diff -puN fs/exec.c~break-up-files-struct fs/exec.c
@@ -787,6 +787,7 @@ no_thread_group:
 static inline void flush_old_files(struct files_struct * files)
 {
 	long j = -1;
+	struct fdtable *fdt;
 
 	spin_lock(&files->file_lock);
 	for (;;) {

@@ -794,12 +795,13 @@ static inline void flush_old_files(struc
 
 		j++;
 		i = j * __NFDBITS;
-		if (i >= files->max_fds || i >= files->max_fdset)
+		fdt = files_fdtable(files);
+		if (i >= fdt->max_fds || i >= fdt->max_fdset)
 			break;
-		set = files->close_on_exec->fds_bits[j];
+		set = fdt->close_on_exec->fds_bits[j];
 		if (!set)
 			continue;
-		files->close_on_exec->fds_bits[j] = 0;
+		fdt->close_on_exec->fds_bits[j] = 0;
 		spin_unlock(&files->file_lock);
 		for ( ; set ; i++,set >>= 1) {
 			if (set & 1) {

fs/fcntl.c renamed from fs/fcntl.c~break-up-files-struct +28 ~~-18~~

112 lines not on this page · raw message

fs/file.c renamed from fs/file.c~break-up-files-struct +25 ~~-17~~

100 lines not on this page · raw message

fs/locks.c renamed from fs/locks.c~break-up-files-struct +5 -3

diff -puN fs/locks.c~break-up-files-struct fs/locks.c
@@ -2175,21 +2175,23 @@ void steal_locks(fl_owner_t from)
 {
 	struct files_struct *files = current->files;
 	int i, j;
+	struct fdtable *fdt;
 
 	if (from == files)
 		return;
 
 	lock_kernel();
 	j = 0;
+	fdt = files_fdtable(files);
 	for (;;) {
 		unsigned long set;
 		i = j * __NFDBITS;
-		if (i >= files->max_fdset || i >= files->max_fds)
+		if (i >= fdt->max_fdset || i >= fdt->max_fds)
 			break;
-		set = files->open_fds->fds_bits[j++];
+		set = fdt->open_fds->fds_bits[j++];
 		while (set) {
 			if (set & 1) {
-				struct file *file = files->fd[i];
+				struct file *file = fdt->fd[i];
 				if (file)
 					__steal_locks(file, from);
 			}

fs/open.c renamed from fs/open.c~break-up-files-struct +24 ~~-17~~

86 lines not on this page · raw message

fs/proc/array.c renamed from fs/proc/array.c~break-up-files-struct +4 -1

diff -puN fs/proc/array.c~break-up-files-struct fs/proc/array.c
@@ -159,6 +159,7 @@ static inline char * task_state(struct t
 {
 	struct group_info *group_info;
 	int g;
+	struct fdtable *fdt = NULL;
 
 	read_lock(&tasklist_lock);
 	buffer += sprintf(buffer,

@@ -179,10 +180,12 @@ static inline char * task_state(struct t
 		p->gid, p->egid, p->sgid, p->fsgid);
 	read_unlock(&tasklist_lock);
 	task_lock(p);
+	if (p->files)
+		fdt = files_fdtable(p->files);
 	buffer += sprintf(buffer,
 		"FDSize:\t%d\n"
 		"Groups:\t",
-		p->files ? p->files->max_fds : 0);
+		fdt ? fdt->max_fds : 0);
 
 	group_info = p->group_info;
 	get_group_info(group_info);

fs/proc/base.c renamed from fs/proc/base.c~break-up-files-struct +3 -1

diff -puN fs/proc/base.c~break-up-files-struct fs/proc/base.c
@@ -978,6 +978,7 @@ static int proc_readfd(struct file * fil
 	int retval;
 	char buf[NUMBUF];
 	struct files_struct * files;
+	struct fdtable *fdt;
 
 	retval = -ENOENT;
 	if (!pid_alive(p))

@@ -1001,8 +1002,9 @@ static int proc_readfd(struct file * fil
 			if (!files)
 				goto out;
 			spin_lock(&files->file_lock);
+			fdt = files_fdtable(files);
 			for (fd = filp->f_pos-2;
-			     fd < files->max_fds;
+			     fd < fdt->max_fds;
 			     fd++, filp->f_pos++) {
 				unsigned int i,j;

fs/select.c renamed from fs/select.c~break-up-files-struct +9 -3

diff -puN fs/select.c~break-up-files-struct fs/select.c
@@ -132,11 +132,13 @@ static int max_select_fd(unsigned long n
 	unsigned long *open_fds;
 	unsigned long set;
 	int max;
+	struct fdtable *fdt;
 
 	/* handle last in-complete long-word first */
 	set = ~(~0UL << (n & (__NFDBITS-1)));
 	n /= __NFDBITS;
-	open_fds = current->files->open_fds->fds_bits+n;
+	fdt = files_fdtable(current->files);
+	open_fds = fdt->open_fds->fds_bits+n;
 	max = 0;
 	if (set) {
 		set &= BITS(fds, n);

@@ -299,6 +301,7 @@ sys_select(int n, fd_set __user *inp, fd
 	char *bits;
 	long timeout;
 	int ret, size, max_fdset;
+	struct fdtable *fdt;
 
 	timeout = MAX_SCHEDULE_TIMEOUT;
 	if (tvp) {

@@ -326,7 +329,8 @@ sys_select(int n, fd_set __user *inp, fd
 		goto out_nofds;
 
 	/* max_fdset can increase, so grab it once to avoid race */
-	max_fdset = current->files->max_fdset;
+	fdt = files_fdtable(current->files);
+	max_fdset = fdt->max_fdset;
 	if (n > max_fdset)
 		n = max_fdset;

@@ -464,9 +468,11 @@ asmlinkage long sys_poll(struct pollfd _
  	unsigned int i;
 	struct poll_list *head;
  	struct poll_list *walk;
+	struct fdtable *fdt;
 
 	/* Do a sanity check on nfds ... */
-	if (nfds > current->files->max_fdset && nfds > OPEN_MAX)
+	fdt = files_fdtable(current->files);
+	if (nfds > fdt->max_fdset && nfds > OPEN_MAX)
 		return -EINVAL;
 
 	if (timeout) {

include/linux/file.h renamed from include/linux/file.h~break-up-files-struct +15 -8

diff -puN include/linux/file.h~break-up-files-struct include/linux/file.h
@@ -16,23 +16,29 @@
  */
 #define NR_OPEN_DEFAULT BITS_PER_LONG
 
+struct fdtable {
+	int max_fds;
+	int max_fdset;
+	int next_fd;
+	struct file ** fd;      /* current fd array */
+	fd_set *close_on_exec;
+	fd_set *open_fds;
+};
+
 /*
  * Open file table structure
  */
 struct files_struct {
         atomic_t count;
         spinlock_t file_lock;     /* Protects all the below members.  Nests inside tsk->alloc_lock */
-        int max_fds;
-        int max_fdset;
-        int next_fd;
-        struct file ** fd;      /* current fd array */
-        fd_set *close_on_exec;
-        fd_set *open_fds;
+	struct fdtable fdtab;
         fd_set close_on_exec_init;
         fd_set open_fds_init;
         struct file * fd_array[NR_OPEN_DEFAULT];
 };
 
+#define files_fdtable(files) (&(files)->fdtab)
+
 extern void FASTCALL(__fput(struct file *));
 extern void FASTCALL(fput(struct file *));

@@ -63,9 +69,10 @@ extern int expand_files(struct files_str
 static inline struct file * fcheck_files(struct files_struct *files, unsigned int fd)
 {
 	struct file * file = NULL;
+	struct fdtable *fdt = files_fdtable(files);
 
-	if (fd < files->max_fds)
-		file = files->fd[fd];
+	if (fd < fdt->max_fds)
+		file = fdt->fd[fd];
 	return file;
 }

include/linux/init_task.h renamed from include/linux/init_task.h~break-up-files-struct +9 -4

diff -puN include/linux/init_task.h~break-up-files-struct include/linux/init_task.h
@@ -3,16 +3,21 @@
 
 #include <linux/file.h>
 
-#define INIT_FILES \
-{ 							\
-	.count		= ATOMIC_INIT(1), 		\
-	.file_lock	= SPIN_LOCK_UNLOCKED, 		\
+#define INIT_FDTABLE \
+{							\
 	.max_fds	= NR_OPEN_DEFAULT, 		\
 	.max_fdset	= __FD_SETSIZE, 		\
 	.next_fd	= 0, 				\
 	.fd		= &init_files.fd_array[0], 	\
 	.close_on_exec	= &init_files.close_on_exec_init, \
 	.open_fds	= &init_files.open_fds_init, 	\
+}
+
+#define INIT_FILES \
+{ 							\
+	.count		= ATOMIC_INIT(1), 		\
+	.file_lock	= SPIN_LOCK_UNLOCKED, 		\
+	.fdtab		= INIT_FDTABLE,			\
 	.close_on_exec_init = { { 0, } }, 		\
 	.open_fds_init	= { { 0, } }, 			\
 	.fd_array	= { NULL, } 			\

kernel/exit.c renamed from kernel/exit.c~break-up-files-struct +13 -8

diff -puN kernel/exit.c~break-up-files-struct kernel/exit.c
@@ -363,17 +363,19 @@ EXPORT_SYMBOL(daemonize);
 static inline void close_files(struct files_struct * files)
 {
 	int i, j;
+	struct fdtable *fdt;
 
 	j = 0;
+	fdt = files_fdtable(files);
 	for (;;) {
 		unsigned long set;
 		i = j * __NFDBITS;
-		if (i >= files->max_fdset || i >= files->max_fds)
+		if (i >= fdt->max_fdset || i >= fdt->max_fds)
 			break;
-		set = files->open_fds->fds_bits[j++];
+		set = fdt->open_fds->fds_bits[j++];
 		while (set) {
 			if (set & 1) {
-				struct file * file = xchg(&files->fd[i], NULL);
+				struct file * file = xchg(&fdt->fd[i], NULL);
 				if (file)
 					filp_close(file, files);
 			}

@@ -398,16 +400,19 @@ struct files_struct *get_files_struct(st
 
 void fastcall put_files_struct(struct files_struct *files)
 {
+	struct fdtable *fdt;
+
 	if (atomic_dec_and_test(&files->count)) {
 		close_files(files);
 		/*
 		 * Free the fd and fdset arrays if we expanded them.
 		 */
-		if (files->fd != &files->fd_array[0])
-			free_fd_array(files->fd, files->max_fds);
-		if (files->max_fdset > __FD_SETSIZE) {
-			free_fdset(files->open_fds, files->max_fdset);
-			free_fdset(files->close_on_exec, files->max_fdset);
+		fdt = files_fdtable(files);
+		if (fdt->fd != &files->fd_array[0])
+			free_fd_array(fdt->fd, fdt->max_fds);
+		if (fdt->max_fdset > __FD_SETSIZE) {
+			free_fdset(fdt->open_fds, fdt->max_fdset);
+			free_fdset(fdt->close_on_exec, fdt->max_fdset);
 		}
 		kmem_cache_free(files_cachep, files);
 	}

kernel/fork.c renamed from kernel/fork.c~break-up-files-struct +50 ~~-32~~

150 lines not on this page · raw message

net/ipv4/netfilter/ipt_owner.c renamed from net/ipv4/netfilter/ipt_owner.c~break-up-files-struct +9 -3

diff -puN net/ipv4/netfilter/ipt_owner.c~break-up-files-struct net/ipv4/netfilter/ipt_owner.c
@@ -25,6 +25,7 @@ match_comm(const struct sk_buff *skb, co
 {
 	struct task_struct *g, *p;
 	struct files_struct *files;
+	struct fdtable *fdt;
 	int i;
 
 	read_lock(&tasklist_lock);

@@ -36,7 +37,8 @@ match_comm(const struct sk_buff *skb, co
 		files = p->files;
 		if(files) {
 			spin_lock(&files->file_lock);
-			for (i=0; i < files->max_fds; i++) {
+			fdt = files_fdtable(files);
+			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) ==
 				    skb->sk->sk_socket->file) {
 					spin_unlock(&files->file_lock);

@@ -58,6 +60,7 @@ match_pid(const struct sk_buff *skb, pid
 {
 	struct task_struct *p;
 	struct files_struct *files;
+	struct fdtable *fdt;
 	int i;
 
 	read_lock(&tasklist_lock);

@@ -68,7 +71,8 @@ match_pid(const struct sk_buff *skb, pid
 	files = p->files;
 	if(files) {
 		spin_lock(&files->file_lock);
-		for (i=0; i < files->max_fds; i++) {
+		fdt = files_fdtable(files);
+		for (i=0; i < fdt->max_fds; i++) {
 			if (fcheck_files(files, i) ==
 			    skb->sk->sk_socket->file) {
 				spin_unlock(&files->file_lock);

@@ -90,6 +94,7 @@ match_sid(const struct sk_buff *skb, pid
 {
 	struct task_struct *g, *p;
 	struct file *file = skb->sk->sk_socket->file;
+	struct fdtable *fdt;
 	int i, found=0;
 
 	read_lock(&tasklist_lock);

@@ -102,7 +107,8 @@ match_sid(const struct sk_buff *skb, pid
 		files = p->files;
 		if (files) {
 			spin_lock(&files->file_lock);
-			for (i=0; i < files->max_fds; i++) {
+			fdt = files_fdtable(files);
+			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) == file) {
 					found = 1;
 					break;

net/ipv6/netfilter/ip6t_owner.c renamed from net/ipv6/netfilter/ip6t_owner.c~break-up-files-struct +6 -2

diff -puN net/ipv6/netfilter/ip6t_owner.c~break-up-files-struct net/ipv6/netfilter/ip6t_owner.c
@@ -25,6 +25,7 @@ match_pid(const struct sk_buff *skb, pid
 {
 	struct task_struct *p;
 	struct files_struct *files;
+	struct fdtable *fdt;
 	int i;
 
 	read_lock(&tasklist_lock);

@@ -35,7 +36,8 @@ match_pid(const struct sk_buff *skb, pid
 	files = p->files;
 	if(files) {
 		spin_lock(&files->file_lock);
-		for (i=0; i < files->max_fds; i++) {
+		fdt = files_fdtable(files);
+		for (i=0; i < fdt->max_fds; i++) {
 			if (fcheck_files(files, i) == skb->sk->sk_socket->file) {
 				spin_unlock(&files->file_lock);
 				task_unlock(p);

@@ -61,6 +63,7 @@ match_sid(const struct sk_buff *skb, pid
 	read_lock(&tasklist_lock);
 	do_each_thread(g, p) {
 		struct files_struct *files;
+		struct fdtable *fdt;
 		if (p->signal->session != sid)
 			continue;

@@ -68,7 +71,8 @@ match_sid(const struct sk_buff *skb, pid
 		files = p->files;
 		if (files) {
 			spin_lock(&files->file_lock);
-			for (i=0; i < files->max_fds; i++) {
+			fdt = files_fdtable(files);
+			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) == file) {
 					found = 1;
 					break;

security/selinux/hooks.c renamed from security/selinux/hooks.c~break-up-files-struct +4 -2

diff -puN security/selinux/hooks.c~break-up-files-struct security/selinux/hooks.c
@@ -1672,6 +1672,7 @@ static inline void flush_unauthorized_fi
 	struct avc_audit_data ad;
 	struct file *file, *devnull = NULL;
 	struct tty_struct *tty = current->signal->tty;
+	struct fdtable *fdt;
 	long j = -1;
 
 	if (tty) {

@@ -1705,9 +1706,10 @@ static inline void flush_unauthorized_fi
 
 		j++;
 		i = j * __NFDBITS;
-		if (i >= files->max_fds || i >= files->max_fdset)
+		fdt = files_fdtable(files);
+		if (i >= fdt->max_fds || i >= fdt->max_fdset)
 			break;
-		set = files->open_fds->fds_bits[j];
+		set = fdt->open_fds->fds_bits[j];
 		if (!set)
 			continue;
 		spin_unlock(&files->file_lock);

Dipankar Sarma

author

2005-06-14 14:37 UTC #4 lore raw

Re: [PATCH 4/6] files: files struct with RCU

Patch to eliminate struct files_struct.file_lock spinlock on the reader side and use rcu refcounting rcuref_xxx api for the f_count refcounter. The updates to the fdtable are done by allocating a new fdtable structure and setting files->fdt to point to the new structure. The fdtable structure is protected by RCU thereby allowing lock-free lookup. For fd arrays/sets that are vmalloced,
we use keventd to free them since RCU callbacks can't
sleep. A global list of fdtable to be freed is not scalable, so we use a per-cpu list. If keventd is already handling
the current cpu's work, we use a timer to defer queueing
of that work.

Since the last publication, this patch has been re-written to avoid using explicit memory barriers and use rcu_assign_pointer(), rcu_dereference() premitives instead. This required that the fd information is kept in
a separate structure (fdtable) and updated atomically.

This patch needs the rcuref api additions as pre-req.

Signed-off-by Dipankar Sarma <[email protected]>

 fs/aio.c                  |    3 
 fs/fcntl.c                |   13 +
 fs/file.c                 |  393 ++++++++++++++++++++++++++++++----------------
 fs/file_table.c           |   40 +++-
 fs/open.c                 |    5 
 include/linux/file.h      |   11 +
 include/linux/fs.h        |    4 
 include/linux/init_task.h |    5 
 kernel/exit.c             |   15 -
 kernel/fork.c             |   23 +-
 10 files changed, 346 insertions(+), 166 deletions(-)

fs/aio.c renamed from fs/aio.c~files-struct-rcu +2 -1

diff -puN fs/aio.c~files-struct-rcu fs/aio.c
@@ -29,6 +29,7 @@
 #include <linux/highmem.h>
 #include <linux/workqueue.h>
 #include <linux/security.h>
+#include <linux/rcuref.h>
 
 #include <asm/kmap_types.h>
 #include <asm/uaccess.h>

@@ -498,7 +499,7 @@ static int __aio_put_req(struct kioctx *
 	/* Must be done under the lock to serialise against cancellation.
 	 * Call this aio_fput as it duplicates fput via the fput_work.
 	 */
-	if (unlikely(atomic_dec_and_test(&req->ki_filp->f_count))) {
+	if (unlikely(rcuref_dec_and_test(&req->ki_filp->f_count))) {
 		get_ioctx(ctx);
 		spin_lock(&fput_lock);
 		list_add(&req->ki_list, &fput_head);

fs/fcntl.c renamed from fs/fcntl.c~files-struct-rcu +10 -3

diff -puN fs/fcntl.c~files-struct-rcu fs/fcntl.c
@@ -16,6 +16,7 @@
 #include <linux/security.h>
 #include <linux/ptrace.h>
 #include <linux/signal.h>
+#include <linux/rcupdate.h>
 
 #include <asm/poll.h>
 #include <asm/siginfo.h>

@@ -64,8 +65,8 @@ static int locate_fd(struct files_struct
 	if (orig_start >= current->signal->rlim[RLIMIT_NOFILE].rlim_cur)
 		goto out;
 
-	fdt = files_fdtable(files);
 repeat:
+	fdt = files_fdtable(files);
 	/*
 	 * Someone might have closed fd's in the range
 	 * orig_start..fdt->next_fd

@@ -95,9 +96,15 @@ repeat:
 	if (error)
 		goto repeat;
 
+	/*
+	 * We reacquired files_lock, so we are safe as long as
+	 * we reacquire the fdtable pointer and use it while holding
+	 * the lock, no one can free it during that time.
+	 */
+	fdt = files_fdtable(files);
 	if (start <= fdt->next_fd)
 		fdt->next_fd = newfd + 1;
-	
+
 	error = newfd;
 	
 out:

@@ -162,7 +169,7 @@ asmlinkage long sys_dup2(unsigned int ol
 	if (!tofree && FD_ISSET(newfd, fdt->open_fds))
 		goto out_fput;
 
-	fdt->fd[newfd] = file;
+	rcu_assign_pointer(fdt->fd[newfd], file);
 	FD_SET(newfd, fdt->open_fds);
 	FD_CLR(newfd, fdt->close_on_exec);
 	spin_unlock(&files->file_lock);

fs/file.c renamed from fs/file.c~files-struct-rcu +260 ~~-133~~

447 lines not on this page · raw message

fs/file_table.c renamed from fs/file_table.c~files-struct-rcu +29 ~~-11~~

diff -puN fs/file_table.c~files-struct-rcu fs/file_table.c
@@ -14,6 +14,7 @@
 #include <linux/fs.h>
 #include <linux/security.h>
 #include <linux/eventpoll.h>
+#include <linux/rcupdate.h>
 #include <linux/mount.h>
 #include <linux/cdev.h>

@@ -52,11 +53,17 @@ void filp_dtor(void * objp, struct kmem_
 	spin_unlock_irqrestore(&filp_count_lock, flags);
 }
 
-static inline void file_free(struct file *f)
+static inline void file_free_rcu(struct rcu_head *head)
 {
+	struct file *f =  container_of(head, struct file, f_rcuhead);
 	kmem_cache_free(filp_cachep, f);
 }
 
+static inline void file_free(struct file *f)
+{
+	call_rcu(&f->f_rcuhead, file_free_rcu);
+}
+
 /* Find an unused file structure and return a pointer to it.
  * Returns NULL, if there are no more free file structures or
  * we run out of memory.

@@ -107,7 +114,7 @@ EXPORT_SYMBOL(get_empty_filp);
 
 void fastcall fput(struct file *file)
 {
-	if (atomic_dec_and_test(&file->f_count))
+	if (rcuref_dec_and_test(&file->f_count))
 		__fput(file);
 }

@@ -151,11 +158,17 @@ struct file fastcall *fget(unsigned int 
 	struct file *file;
 	struct files_struct *files = current->files;
 
-	spin_lock(&files->file_lock);
+	rcu_read_lock();
 	file = fcheck_files(files, fd);
-	if (file)
-		get_file(file);
-	spin_unlock(&files->file_lock);
+	if (file) {
+		if (!rcuref_inc_lf(&file->f_count)) {
+			/* File object ref couldn't be taken */
+			rcu_read_unlock();
+			return NULL;
+		}
+	}	
+	rcu_read_unlock();
+
 	return file;
 }

@@ -177,21 +190,25 @@ struct file fastcall *fget_light(unsigne
 	if (likely((atomic_read(&files->count) == 1))) {
 		file = fcheck_files(files, fd);
 	} else {
-		spin_lock(&files->file_lock);
+		rcu_read_lock();
 		file = fcheck_files(files, fd);
 		if (file) {
-			get_file(file);
-			*fput_needed = 1;
+			if (rcuref_inc_lf(&file->f_count))
+				*fput_needed = 1;
+			else
+				/* Didn't get the reference, someone's freed */
+				file = NULL;
 		}
-		spin_unlock(&files->file_lock);
+		rcu_read_unlock();
 	}
+
 	return file;
 }
 
 
 void put_filp(struct file *file)
 {
-	if (atomic_dec_and_test(&file->f_count)) {
+	if (rcuref_dec_and_test(&file->f_count)) {
 		security_file_free(file);
 		file_kill(file);
 		file_free(file);

@@ -252,4 +269,5 @@ void __init files_init(unsigned long mem
 	files_stat.max_files = n; 
 	if (files_stat.max_files < NR_FILE)
 		files_stat.max_files = NR_FILE;
+	files_defer_init();
 }

fs/open.c renamed from fs/open.c~files-struct-rcu +3 -2

diff -puN fs/open.c~files-struct-rcu fs/open.c
@@ -23,6 +23,7 @@
 #include <linux/fs.h>
 #include <linux/pagemap.h>
 #include <linux/syscalls.h>
+#include <linux/rcupdate.h>
 
 #include <asm/unistd.h>

@@ -929,7 +930,7 @@ void fastcall fd_install(unsigned int fd
 	fdt = files_fdtable(files);
 	if (unlikely(fdt->fd[fd] != NULL))
 		BUG();
-	fdt->fd[fd] = file;
+	rcu_assign_pointer(fdt->fd[fd], file);
 	spin_unlock(&files->file_lock);
 }

@@ -1029,7 +1030,7 @@ asmlinkage long sys_close(unsigned int f
 	filp = fdt->fd[fd];
 	if (!filp)
 		goto out_unlock;
-	fdt->fd[fd] = NULL;
+	rcu_assign_pointer(fdt->fd[fd], NULL);
 	FD_CLR(fd, fdt->close_on_exec);
 	__put_unused_fd(files, fd);
 	spin_unlock(&files->file_lock);

include/linux/file.h renamed from include/linux/file.h~files-struct-rcu +9 -2

diff -puN include/linux/file.h~files-struct-rcu include/linux/file.h
@@ -9,6 +9,7 @@
 #include <linux/posix_types.h>
 #include <linux/compiler.h>
 #include <linux/spinlock.h>
+#include <linux/rcupdate.h>
 
 /*
  * The default fd array needs to be at least BITS_PER_LONG,

@@ -23,6 +24,9 @@ struct fdtable {
 	struct file ** fd;      /* current fd array */
 	fd_set *close_on_exec;
 	fd_set *open_fds;
+	struct rcu_head rcu;
+	struct files_struct *free_files;
+	struct fdtable *next;
 };
 
 /*

@@ -31,13 +35,14 @@ struct fdtable {
 struct files_struct {
         atomic_t count;
         spinlock_t file_lock;     /* Protects all the below members.  Nests inside tsk->alloc_lock */
+	struct fdtable *fdt;
 	struct fdtable fdtab;
         fd_set close_on_exec_init;
         fd_set open_fds_init;
         struct file * fd_array[NR_OPEN_DEFAULT];
 };
 
-#define files_fdtable(files) (&(files)->fdtab)
+#define files_fdtable(files) (rcu_dereference((files)->fdt))
 
 extern void FASTCALL(__fput(struct file *));
 extern void FASTCALL(fput(struct file *));

@@ -65,6 +70,8 @@ extern fd_set *alloc_fdset(int);
 extern void free_fdset(fd_set *, int);
 
 extern int expand_files(struct files_struct *, int nr);
+extern void free_fdtable(struct fdtable *fdt);
+extern void __init files_defer_init(void);
 
 static inline struct file * fcheck_files(struct files_struct *files, unsigned int fd)
 {

@@ -72,7 +79,7 @@ static inline struct file * fcheck_files
 	struct fdtable *fdt = files_fdtable(files);
 
 	if (fd < fdt->max_fds)
-		file = fdt->fd[fd];
+		file = rcu_dereference(fdt->fd[fd]);
 	return file;
 }

include/linux/fs.h renamed from include/linux/fs.h~files-struct-rcu +3 -1

diff -puN include/linux/fs.h~files-struct-rcu include/linux/fs.h
@@ -9,6 +9,7 @@
 #include <linux/config.h>
 #include <linux/limits.h>
 #include <linux/ioctl.h>
+#include <linux/rcuref.h>
 
 /*
  * It's silly to have NR_OPEN bigger than NR_FILE, but you can change

@@ -600,12 +601,13 @@ struct file {
 	spinlock_t		f_ep_lock;
 #endif /* #ifdef CONFIG_EPOLL */
 	struct address_space	*f_mapping;
+	struct rcu_head 	f_rcuhead;
 };
 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_inc(&(x)->f_count)
+#define get_file(x)	rcuref_inc(&(x)->f_count)
 #define file_count(x)	atomic_read(&(x)->f_count)
 
 #define	MAX_NON_LFS	((1UL<<31) - 1)

include/linux/init_task.h renamed from include/linux/init_task.h~files-struct-rcu +5 -0

diff -puN include/linux/init_task.h~files-struct-rcu include/linux/init_task.h
@@ -2,6 +2,7 @@
 #define _LINUX__INIT_TASK_H
 
 #include <linux/file.h>
+#include <linux/rcupdate.h>
 
 #define INIT_FDTABLE \
 {							\

@@ -11,12 +12,16 @@
 	.fd		= &init_files.fd_array[0], 	\
 	.close_on_exec	= &init_files.close_on_exec_init, \
 	.open_fds	= &init_files.open_fds_init, 	\
+	.rcu		= RCU_HEAD_INIT, 		\
+	.free_files	= NULL,		 		\
+	.next		= NULL,		 		\
 }
 
 #define INIT_FILES \
 { 							\
 	.count		= ATOMIC_INIT(1), 		\
 	.file_lock	= SPIN_LOCK_UNLOCKED, 		\
+	.fdt		= &init_files.fdtab, 		\
 	.fdtab		= INIT_FDTABLE,			\
 	.close_on_exec_init = { { 0, } }, 		\
 	.open_fds_init	= { { 0, } }, 			\

kernel/exit.c renamed from kernel/exit.c~files-struct-rcu +8 -7

diff -puN kernel/exit.c~files-struct-rcu kernel/exit.c
@@ -406,15 +406,16 @@ void fastcall put_files_struct(struct fi
 		close_files(files);
 		/*
 		 * Free the fd and fdset arrays if we expanded them.
+		 * If the fdtable was embedded, pass files for freeing
+		 * at the end of the RCU grace period. Otherwise,
+		 * you can free files immediately.
 		 */
 		fdt = files_fdtable(files);
-		if (fdt->fd != &files->fd_array[0])
-			free_fd_array(fdt->fd, fdt->max_fds);
-		if (fdt->max_fdset > __FD_SETSIZE) {
-			free_fdset(fdt->open_fds, fdt->max_fdset);
-			free_fdset(fdt->close_on_exec, fdt->max_fdset);
-		}
-		kmem_cache_free(files_cachep, files);
+		if (fdt == &files->fdtab)
+			fdt->free_files = files;
+		else 
+			kmem_cache_free(files_cachep, files);
+		free_fdtable(fdt);
 	}
 }

kernel/fork.c renamed from kernel/fork.c~files-struct-rcu +17 -6

diff -puN kernel/fork.c~files-struct-rcu kernel/fork.c
@@ -35,6 +35,7 @@
 #include <linux/syscalls.h>
 #include <linux/jiffies.h>
 #include <linux/futex.h>
+#include <linux/rcupdate.h>
 #include <linux/ptrace.h>
 #include <linux/mount.h>
 #include <linux/audit.h>

@@ -559,13 +560,12 @@ static inline int copy_fs(unsigned long 
 	return 0;
 }
 
-static int count_open_files(struct files_struct *files, int size)
+static int count_open_files(struct fdtable *fdt)
 {
+	int size = fdt->max_fdset;
 	int i;
-	struct fdtable *fdt;
 
 	/* Find the last open fd */
-	fdt = files_fdtable(files);
 	for (i = size/(8*sizeof(long)); i > 0; ) {
 		if (fdt->open_fds->fds_bits[--i])
 			break;

@@ -586,13 +586,17 @@ static struct files_struct *alloc_files(
 	atomic_set(&newf->count, 1);
 
 	spin_lock_init(&newf->file_lock);
-	fdt = files_fdtable(newf);
+	fdt = &newf->fdtab;
 	fdt->next_fd = 0;
 	fdt->max_fds = NR_OPEN_DEFAULT;
 	fdt->max_fdset = __FD_SETSIZE;
 	fdt->close_on_exec = &newf->close_on_exec_init;
 	fdt->open_fds = &newf->open_fds_init;
 	fdt->fd = &newf->fd_array[0];
+	INIT_RCU_HEAD(&fdt->rcu);
+	fdt->free_files = NULL;
+	fdt->next = NULL;
+	rcu_assign_pointer(newf->fdt, fdt);
 out:
 	return newf;
 }

@@ -631,7 +635,7 @@ static int copy_files(unsigned long clon
 	old_fdt = files_fdtable(oldf);
 	new_fdt = files_fdtable(newf);
 	size = old_fdt->max_fdset;
-	open_files = count_open_files(oldf, old_fdt->max_fdset);
+	open_files = count_open_files(old_fdt);
 	expand = 0;
 
 	/*

@@ -655,7 +659,14 @@ static int copy_files(unsigned long clon
 		spin_unlock(&newf->file_lock);
 		if (error < 0)
 			goto out_release;
+		new_fdt = files_fdtable(newf);
+		/*
+		 * Reacquire the oldf lock and a pointer to its fd table
+		 * who knows it may have a new bigger fd table. We need
+		 * the latest pointer.
+		 */
 		spin_lock(&oldf->file_lock);
+		old_fdt = files_fdtable(oldf);
 	}
 
 	old_fds = old_fdt->fd;

@@ -677,7 +688,7 @@ static int copy_files(unsigned long clon
 			 */
 			FD_CLR(open_files - i, new_fdt->open_fds);
 		}
-		*new_fds++ = f;
+		rcu_assign_pointer(*new_fds++, f);
 	}
 	spin_unlock(&oldf->file_lock);

Dipankar Sarma

author

2005-06-14 14:44 UTC #5 lore raw

Re: [PATCH 5/6] files: lock-free fd look-up

With the use of RCU in files structure, the look-up of files using fds can now be lock-free. The lookup is protected by rcu_read_lock()/rcu_read_unlock(). This patch changes the readers to use lock-free lookup.

Signed-off-by Maneesh Soni <[email protected]>

Signed-off-by Ravikiran Thirumalai <[email protected]>

Signed-off-by Dipankar Sarma <[email protected]>

 arch/mips/kernel/irixioctl.c    |    5 +++--
 arch/sparc64/solaris/ioctl.c    |    7 ++++---
 drivers/char/tty_io.c           |    4 ++--
 fs/fcntl.c                      |    4 ++--
 fs/proc/base.c                  |   29 +++++++++++++++--------------
 fs/select.c                     |   13 ++++++++++---
 net/ipv4/netfilter/ipt_owner.c  |   17 +++++++++--------
 net/ipv6/netfilter/ip6t_owner.c |   11 ++++++-----
 security/selinux/hooks.c        |    2 +-
 9 files changed, 52 insertions(+), 40 deletions(-)

arch/mips/kernel/irixioctl.c renamed from arch/mips/kernel/irixioctl.c~lock-free-fd-lookup +3 -2

diff -puN arch/mips/kernel/irixioctl.c~lock-free-fd-lookup arch/mips/kernel/irixioctl.c
@@ -14,6 +14,7 @@
 #include <linux/syscalls.h>
 #include <linux/tty.h>
 #include <linux/file.h>
+#include <linux/rcupdate.h>
 
 #include <asm/uaccess.h>
 #include <asm/ioctl.h>

@@ -33,7 +34,7 @@ static struct tty_struct *get_tty(int fd
 	struct file *filp;
 	struct tty_struct *ttyp = NULL;
 
-	spin_lock(&current->files->file_lock);
+	rcu_read_lock();
 	filp = fcheck(fd);
 	if(filp && filp->private_data) {
 		ttyp = (struct tty_struct *) filp->private_data;

@@ -41,7 +42,7 @@ static struct tty_struct *get_tty(int fd
 		if(ttyp->magic != TTY_MAGIC)
 			ttyp =NULL;
 	}
-	spin_unlock(&current->files->file_lock);
+	rcu_read_unlock();
 	return ttyp;
 }

arch/sparc64/solaris/ioctl.c renamed from arch/sparc64/solaris/ioctl.c~lock-free-fd-lookup +4 -3

diff -puN arch/sparc64/solaris/ioctl.c~lock-free-fd-lookup arch/sparc64/solaris/ioctl.c
@@ -24,6 +24,7 @@
 #include <linux/netdevice.h>
 #include <linux/mtio.h>
 #include <linux/time.h>
+#include <linux/rcupdate.h>
 #include <linux/compat.h>
 
 #include <net/sock.h>

@@ -295,16 +296,16 @@ static inline int solaris_sockmod(unsign
 	struct inode *ino;
 	struct fdtable *fdt;
 	/* I wonder which of these tests are superfluous... --patrik */
-	spin_lock(&current->files->file_lock);
+	rcu_read_lock();
 	fdt = files_fdtable(current->files);
 	if (! fdt->fd[fd] ||
 	    ! fdt->fd[fd]->f_dentry ||
 	    ! (ino = fdt->fd[fd]->f_dentry->d_inode) ||
 	    ! S_ISSOCK(ino->i_mode)) {
-		spin_unlock(&current->files->file_lock);
+		rcu_read_unlock();
 		return TBADF;
 	}
-	spin_unlock(&current->files->file_lock);
+	rcu_read_unlock();
 	
 	switch (cmd & 0xff) {
 	case 109: /* SI_SOCKPARAMS */

drivers/char/tty_io.c renamed from drivers/char/tty_io.c~lock-free-fd-lookup +2 -2

diff -puN drivers/char/tty_io.c~lock-free-fd-lookup drivers/char/tty_io.c
@@ -2441,7 +2441,7 @@ static void __do_SAK(void *arg)
 		}
 		task_lock(p);
 		if (p->files) {
-			spin_lock(&p->files->file_lock);
+			rcu_read_lock();
 			fdt = files_fdtable(p->files);
 			for (i=0; i < fdt->max_fds; i++) {
 				filp = fcheck_files(p->files, i);

@@ -2456,7 +2456,7 @@ static void __do_SAK(void *arg)
 					break;
 				}
 			}
-			spin_unlock(&p->files->file_lock);
+			rcu_read_unlock();
 		}
 		task_unlock(p);
 	} while_each_task_pid(session, PIDTYPE_SID, p);

fs/fcntl.c renamed from fs/fcntl.c~lock-free-fd-lookup +2 -2

diff -puN fs/fcntl.c~lock-free-fd-lookup fs/fcntl.c
@@ -40,10 +40,10 @@ static inline int get_close_on_exec(unsi
 	struct files_struct *files = current->files;
 	struct fdtable *fdt;
 	int res;
-	spin_lock(&files->file_lock);
+	rcu_read_lock();
 	fdt = files_fdtable(files);
 	res = FD_ISSET(fd, fdt->close_on_exec);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock();
 	return res;
 }

fs/proc/base.c renamed from fs/proc/base.c~lock-free-fd-lookup +15 ~~-14~~

diff -puN fs/proc/base.c~lock-free-fd-lookup fs/proc/base.c
@@ -28,6 +28,7 @@
 #include <linux/namespace.h>
 #include <linux/mm.h>
 #include <linux/smp_lock.h>
+#include <linux/rcupdate.h>
 #include <linux/kallsyms.h>
 #include <linux/mount.h>
 #include <linux/security.h>

@@ -236,16 +237,16 @@ static int proc_fd_link(struct inode *in
 
 	files = get_files_struct(task);
 	if (files) {
-		spin_lock(&files->file_lock);
+		rcu_read_lock();
 		file = fcheck_files(files, fd);
 		if (file) {
 			*mnt = mntget(file->f_vfsmnt);
 			*dentry = dget(file->f_dentry);
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 			put_files_struct(files);
 			return 0;
 		}
-		spin_unlock(&files->file_lock);
+		rcu_read_unlock();
 		put_files_struct(files);
 	}
 	return -ENOENT;

@@ -1001,7 +1002,7 @@ static int proc_readfd(struct file * fil
 			files = get_files_struct(p);
 			if (!files)
 				goto out;
-			spin_lock(&files->file_lock);
+			rcu_read_lock();
 			fdt = files_fdtable(files);
 			for (fd = filp->f_pos-2;
 			     fd < fdt->max_fds;

@@ -1010,7 +1011,7 @@ static int proc_readfd(struct file * fil
 
 				if (!fcheck_files(files, fd))
 					continue;
-				spin_unlock(&files->file_lock);
+				rcu_read_unlock();
 
 				j = NUMBUF;
 				i = fd;

@@ -1022,12 +1023,12 @@ static int proc_readfd(struct file * fil
 
 				ino = fake_ino(tid, PROC_TID_FD_DIR + fd);
 				if (filldir(dirent, buf+j, NUMBUF-j, fd+2, ino, DT_LNK) < 0) {
-					spin_lock(&files->file_lock);
+					rcu_read_lock();
 					break;
 				}
-				spin_lock(&files->file_lock);
+				rcu_read_lock();
 			}
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 			put_files_struct(files);
 	}
 out:

@@ -1200,9 +1201,9 @@ static int tid_fd_revalidate(struct dent
 
 	files = get_files_struct(task);
 	if (files) {
-		spin_lock(&files->file_lock);
+		rcu_read_lock();
 		if (fcheck_files(files, fd)) {
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 			put_files_struct(files);
 			if (task_dumpable(task)) {
 				inode->i_uid = task->euid;

@@ -1214,7 +1215,7 @@ static int tid_fd_revalidate(struct dent
 			security_task_to_inode(task, inode);
 			return 1;
 		}
-		spin_unlock(&files->file_lock);
+		rcu_read_unlock();
 		put_files_struct(files);
 	}
 	d_drop(dentry);

@@ -1306,7 +1307,7 @@ static struct dentry *proc_lookupfd(stru
 	if (!files)
 		goto out_unlock;
 	inode->i_mode = S_IFLNK;
-	spin_lock(&files->file_lock);
+	rcu_read_lock();
 	file = fcheck_files(files, fd);
 	if (!file)
 		goto out_unlock2;

@@ -1314,7 +1315,7 @@ static struct dentry *proc_lookupfd(stru
 		inode->i_mode |= S_IRUSR | S_IXUSR;
 	if (file->f_mode & 2)
 		inode->i_mode |= S_IWUSR | S_IXUSR;
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock();
 	put_files_struct(files);
 	inode->i_op = &proc_pid_link_inode_operations;
 	inode->i_size = 64;

@@ -1324,7 +1325,7 @@ static struct dentry *proc_lookupfd(stru
 	return NULL;
 
 out_unlock2:
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock();
 	put_files_struct(files);
 out_unlock:
 	iput(inode);

fs/select.c renamed from fs/select.c~lock-free-fd-lookup +10 -3

diff -puN fs/select.c~lock-free-fd-lookup fs/select.c
@@ -22,6 +22,7 @@
 #include <linux/personality.h> /* for STICKY_TIMEOUTS */
 #include <linux/file.h>
 #include <linux/fs.h>
+#include <linux/rcupdate.h>
 
 #include <asm/uaccess.h>

@@ -185,9 +186,9 @@ int do_select(int n, fd_set_bits *fds, l
 	int retval, i;
 	long __timeout = *timeout;
 
- 	spin_lock(&current->files->file_lock);
+	rcu_read_lock();
 	retval = max_select_fd(n, fds);
-	spin_unlock(&current->files->file_lock);
+	rcu_read_unlock();
 
 	if (retval < 0)
 		return retval;

@@ -329,8 +330,10 @@ sys_select(int n, fd_set __user *inp, fd
 		goto out_nofds;
 
 	/* max_fdset can increase, so grab it once to avoid race */
+	rcu_read_lock();
 	fdt = files_fdtable(current->files);
 	max_fdset = fdt->max_fdset;
+	rcu_read_unlock();
 	if (n > max_fdset)
 		n = max_fdset;

@@ -469,10 +472,14 @@ asmlinkage long sys_poll(struct pollfd _
 	struct poll_list *head;
  	struct poll_list *walk;
 	struct fdtable *fdt;
+	int max_fdset;
 
 	/* Do a sanity check on nfds ... */
+	rcu_read_lock();
 	fdt = files_fdtable(current->files);
-	if (nfds > fdt->max_fdset && nfds > OPEN_MAX)
+	max_fdset = fdt->max_fdset;
+	rcu_read_unlock();
+	if (nfds > max_fdset && nfds > OPEN_MAX)
 		return -EINVAL;
 
 	if (timeout) {

net/ipv4/netfilter/ipt_owner.c renamed from net/ipv4/netfilter/ipt_owner.c~lock-free-fd-lookup +9 -8

diff -puN net/ipv4/netfilter/ipt_owner.c~lock-free-fd-lookup net/ipv4/netfilter/ipt_owner.c
@@ -11,6 +11,7 @@
 #include <linux/module.h>
 #include <linux/skbuff.h>
 #include <linux/file.h>
+#include <linux/rcupdate.h>
 #include <net/sock.h>
 
 #include <linux/netfilter_ipv4/ipt_owner.h>

@@ -36,18 +37,18 @@ match_comm(const struct sk_buff *skb, co
 		task_lock(p);
 		files = p->files;
 		if(files) {
-			spin_lock(&files->file_lock);
+			rcu_read_lock();
 			fdt = files_fdtable(files);
 			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) ==
 				    skb->sk->sk_socket->file) {
-					spin_unlock(&files->file_lock);
+					rcu_read_unlock();
 					task_unlock(p);
 					read_unlock(&tasklist_lock);
 					return 1;
 				}
 			}
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 		}
 		task_unlock(p);
 	} while_each_thread(g, p);

@@ -70,18 +71,18 @@ match_pid(const struct sk_buff *skb, pid
 	task_lock(p);
 	files = p->files;
 	if(files) {
-		spin_lock(&files->file_lock);
+		rcu_read_lock();
 		fdt = files_fdtable(files);
 		for (i=0; i < fdt->max_fds; i++) {
 			if (fcheck_files(files, i) ==
 			    skb->sk->sk_socket->file) {
-				spin_unlock(&files->file_lock);
+				rcu_read_unlock();
 				task_unlock(p);
 				read_unlock(&tasklist_lock);
 				return 1;
 			}
 		}
-		spin_unlock(&files->file_lock);
+		rcu_read_unlock();
 	}
 	task_unlock(p);
 out:

@@ -106,7 +107,7 @@ match_sid(const struct sk_buff *skb, pid
 		task_lock(p);
 		files = p->files;
 		if (files) {
-			spin_lock(&files->file_lock);
+			rcu_read_lock();
 			fdt = files_fdtable(files);
 			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) == file) {

@@ -114,7 +115,7 @@ match_sid(const struct sk_buff *skb, pid
 					break;
 				}
 			}
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 		}
 		task_unlock(p);
 		if (found)

net/ipv6/netfilter/ip6t_owner.c renamed from net/ipv6/netfilter/ip6t_owner.c~lock-free-fd-lookup +6 -5

diff -puN net/ipv6/netfilter/ip6t_owner.c~lock-free-fd-lookup net/ipv6/netfilter/ip6t_owner.c
@@ -11,6 +11,7 @@
 #include <linux/module.h>
 #include <linux/skbuff.h>
 #include <linux/file.h>
+#include <linux/rcupdate.h>
 #include <net/sock.h>
 
 #include <linux/netfilter_ipv6/ip6t_owner.h>

@@ -35,17 +36,17 @@ match_pid(const struct sk_buff *skb, pid
 	task_lock(p);
 	files = p->files;
 	if(files) {
-		spin_lock(&files->file_lock);
+		rcu_read_lock();
 		fdt = files_fdtable(files);
 		for (i=0; i < fdt->max_fds; i++) {
 			if (fcheck_files(files, i) == skb->sk->sk_socket->file) {
-				spin_unlock(&files->file_lock);
+				rcu_read_unlock();
 				task_unlock(p);
 				read_unlock(&tasklist_lock);
 				return 1;
 			}
 		}
-		spin_unlock(&files->file_lock);
+		rcu_read_unlock();
 	}
 	task_unlock(p);
 out:

@@ -70,7 +71,7 @@ match_sid(const struct sk_buff *skb, pid
 		task_lock(p);
 		files = p->files;
 		if (files) {
-			spin_lock(&files->file_lock);
+			rcu_read_lock();
 			fdt = files_fdtable(files);
 			for (i=0; i < fdt->max_fds; i++) {
 				if (fcheck_files(files, i) == file) {

@@ -78,7 +79,7 @@ match_sid(const struct sk_buff *skb, pid
 					break;
 				}
 			}
-			spin_unlock(&files->file_lock);
+			rcu_read_unlock();
 		}
 		task_unlock(p);
 		if (found)

security/selinux/hooks.c renamed from security/selinux/hooks.c~lock-free-fd-lookup +1 -1

diff -puN security/selinux/hooks.c~lock-free-fd-lookup security/selinux/hooks.c
@@ -1730,7 +1730,7 @@ static inline void flush_unauthorized_fi
 						continue;
 					}
 					if (devnull) {
-						atomic_inc(&devnull->f_count);
+						rcuref_inc(&devnull->f_count);
 					} else {
 						devnull = dentry_open(dget(selinux_null), mntget(selinuxfs_mount), O_RDWR);
 						if (!devnull) {

Dipankar Sarma

author

2005-06-14 14:45 UTC #6 lore raw

Re: [PATCH 6/6] files: files locking doc

Add documentation describing the new locking scheme for file descriptor table.

Signed-off-by Dipankar Sarma <[email protected]>

 Documentation/filesystems/files.txt |  103 ++++++++++++++++++++++++++++++++++++
 1 files changed, 103 insertions(+)

Documentation/filesystems/files.txt new file +103 -0

diff -puN /dev/null Documentation/filesystems/files.txt
@@ -0,0 +1,103 @@
+File management in the Linux kernel
+-----------------------------------
+
+This document describes how locking for files (struct file)
+and file descriptor table (struct files) works.
+
+Up until 2.6.12, the file descriptor table has been protected
+with a lock (files->file_lock) and reference count (files->count).
+->file_lock protected accesses to all the file related fields
+of the table. ->count was used for sharing the file descriptor
+table between tasks cloned with CLONE_FILES flag. Typically
+this would be the case for posix threads. As with the common
+refcounting model in the kernel, the last task doing 	
+a put_files_struct() frees the file descriptor (fd) table.
+The files (struct file) themselves are protected using
+reference count (->f_count).
+
+In the new lock-free model of file descriptor management,
+the reference counting is similar, but the locking is
+based on RCU. The file descriptor table contains multiple
+elements - the fd sets (open_fds and close_on_exec, the
+array of file pointers, the sizes of the sets and the array
+etc.). In order for the updates to appear atomic to
+a lock-free reader, all the elements of the file descriptor
+table are in a separate structure - struct fdtable.
+files_struct contains a pointer to struct fdtable through
+which the actual fd table is accessed. Initially the
+fdtable is embedded in files_struct itself. On a subsequent
+expansion of fdtable, a new fdtable structure is allocated
+and files->fdtab points to the new structure. The fdtable
+structure is freed with RCU and lock-free readers either
+see the old fdtable or the new fdtable making the update
+appear atomic. Here are the locking rules for
+the fdtable structure -
+
+1. All references to the fdtable must be done through
+   the files_fdtable() macro :
+
+	struct fdtable *fdt;
+
+	rcu_read_lock();
+
+	fdt = files_fdtable(files);
+	....
+	if (n <= fdt->max_fds)
+		....
+	...
+	rcu_read_unlock();
+
+   files_fdtable() uses rcu_dereference() macro which takes care of
+   the memory barrier requirements for lock-free dereference.
+   The fdtable pointer must be read within the read-side
+   critical section.
+
+2. Reading of the fdtable as described above must be protected
+   by rcu_read_lock()/rcu_read_unlock().
+
+3. For any update to the the fd table, files->file_lock must
+   be held.
+
+4. To look up the file structure given an fd, a reader
+   must use either fcheck() or fcheck_files() APIs. These
+   take care of barrier requirements due to lock-free lookup.
+   An example :
+
+	struct file *file;
+
+	rcu_read_lock();
+	file = fcheck(fd);
+	if (file) {
+		...
+	}
+	....
+	rcu_read_unlock();
+
+5. Handling of the file structures is special. Since the look-up
+   of the fd (fget()/fget_light()) are lock-free, it is possible
+   that look-up may race with the last put() operation on the
+   file structure. This is avoided using the rcuref APIs
+   on ->f_count :
+
+	rcu_read_lock();
+	file = fcheck_files(files, fd);
+	if (file) {
+		if (rcuref_inc_lf(&file->f_count))
+			*fput_needed = 1;
+		else
+		/* Didn't get the reference, someone's freed */
+			file = NULL;
+	}
+	rcu_read_unlock();
+	....
+	return file;
+
+   rcuref_inc_lf() detects if refcounts is already zero or
+   goes to zero during increment. If it does, we fail
+   fget()/fget_light().
+
+6. Since both fdtable and file structures can be looked up
+   lock-free, they must be installed using rcu_assign_pointer()
+   API. If they are looked up lock-free, rcu_dereference()
+   must be used. However it is advisable to use files_fdtable()
+   and fcheck()/fcheck_files() which take care of these issues.

Dipankar Sarma

author

2005-06-14 14:48 UTC #7 lore raw

Re: [PATCH 0/6] files: rcuref APIs

In reply to Dipankar Sarma

Quoted 8 lines · Dipankar Sarma

Adds a set of primitives to do reference counting for objects that are looked up without locks using RCU.
Signed-off-by Ravikiran Thirumalai <[email protected]>
Signed-off-by Dipankar Sarma <[email protected]>

Should be 2 of 6. Sorry again.

Dipankar

Dipankar Sarma

author

2005-06-14 14:45 UTC #8 lore raw

Re: [PATCH 0/6] files: fix rcu initializers

In reply to Dipankar Sarma

Quoted 7 lines · Dipankar Sarma

RCU head initilizer no longer needs the head varible name since we don't use list.h lists anymore.
Signed-off-by Dipankar Sarma <[email protected]>

Dang. Should be 1 of 6. Sorry.

Dipankar

Andrew Morton

2005-06-14 20:04 UTC #9 lore raw

In reply to Dipankar Sarma

Quoted 9 lines · Dipankar Sarma

tiobench on a 4-way ppc64 system :
(lockfree)
Test 2.6.10-vanilla Stdev 2.6.10-fd Stdev
-------------------------------------------------------------
 Seqread         1428            32.47   1475.0          29.11
 Randread        1469.2          17.27   1599.6          35.95
 Seqwrite        262.06          9.31    246.8           30.94
 Randwrite       548.38          12.49   521.4           61.98

We don't seem to have gained anything?

Dipankar Sarma

author

2005-06-14 20:14 UTC #10 lore raw

Quoted 11 lines · Andrew Morton

Quoted 9 lines · Dipankar Sarma
tiobench on a 4-way ppc64 system :
(lockfree)
Test 2.6.10-vanilla Stdev 2.6.10-fd Stdev
-------------------------------------------------------------
 Seqread         1428            32.47   1475.0          29.11
 Randread        1469.2          17.27   1599.6          35.95
 Seqwrite        262.06          9.31    246.8           30.94
 Randwrite       548.38          12.49   521.4           61.98

Quoted 1 line

We don't seem to have gained anything?

Look at the read numbers - lockfree is statistically better. The write numbers varied just too much to mean anything. Besides, this is on ppc64, with LL/SC type of lock. Here are the x86 numbers -

tiobench on a 4(8)-way (HT) P4 system on ramdisk :

(lockfree)
Test 2.6.10-vanilla Stdev 2.6.10-fd Stdev
-------------------------------------------------------------

Seqread         1400.8          11.52   1465.4          34.27
Randread        1594            8.86    2397.2          29.21
Seqwrite        242.72          3.47    238.46          6.53
Randwrite       445.74          9.15    446.4           9.75

The performance improvement is very significant.
We are getting killed by the cacheline bouncing of the files_struct lock here. Writes on ramdisk (ext2) seems to vary just too much to get any meaningful number.

Also, With Tridge's thread_perf test on a 4(8)-way (HT) P4 xeon system :

2.6.12-rc5-vanilla :

Running test 'readwrite' with 8 tasks
Threads 0.34 +/- 0.01 seconds
Processes 0.16 +/- 0.00 seconds

2.6.12-rc5-fd :

Running test 'readwrite' with 8 tasks
Threads 0.17 +/- 0.02 seconds
Processes 0.17 +/- 0.02 seconds

Thanks
Dipankar

Dipankar Sarma

author

2005-06-15 12:21 UTC #11 lore raw

In reply to Andrew Morton

Hello Andrew,

Quoted 8 lines · Andrew Morton

Quoted 5 lines · Dipankar Sarma
tiobench on a 4-way ppc64 system :
(lockfree)
Test 2.6.10-vanilla Stdev 2.6.10-fd Stdev
-------------------------------------------------------------
Seqread 1428 32.47 1475.0 29.11
We don't seem to have gained anything?

I repeated the measurements on ramfs (as opposed to ext2 on ramdisk in the earlier measurement) and I got more consistent results from tiobench :

4(8) way xeon P4
-----------------

                                        (lock-free)
Test            2.6.12-rc5      Stdev   2.6.12-rc5-fd   Stdev
-------------------------------------------------------------
Seqread         1282            18.59   1343.6          26.37
Randread        1517            7       2415            34.27
Seqwrite        702.2           5.27    709.46           5.9 
Randwrite       846.86          15.15   919.68          21.4

4-way ppc64
------------

                                        (lock-free)
Test            2.6.12-rc5      Stdev   2.6.12-rc5-fd   Stdev
-------------------------------------------------------------
Seqread         1549            91.16   1569.6          47.2 
Randread        1473.6          25.11   1585.4          69.99
Seqwrite        1096.8          20.03   1136            29.61
Randwrite       1189.6           4.04   1275.2          32.96

Also running Tridge's thread_perf test on ppc64 :

2.6.12-rc5-vanilla
--------------------
Running test 'readwrite' with 4 tasks
Threads 0.20 +/- 0.02 seconds
Processes 0.16 +/- 0.01 seconds

2.6.12-rc5-fd
--------------------
Running test 'readwrite' with 4 tasks
Threads 0.18 +/- 0.04 seconds
Processes 0.16 +/- 0.01 seconds

The benefits are huge (upto ~60%) in some cases on x86 primarily due to the atomic operations during acquisition of ->file_lock and cache line bouncing in fast path. ppc64 benefits are modest due to LL/SC based locking, but still statistically significant.

Thanks
Dipankar