scalable fd management

RFC PATCH In review Dipankar Sarma 2 participants 9 messages May 30, 2005 – Jun 1, 2005

Subsystems (15)

Networking Documentation VFS MIPS +11 more subsystems

lore

Share & tools

lore

Dipankar Sarma

author

2005-05-30 17:23 UTC #0 lore raw

cover scalable fd management

This is RFC-only at the moment, but if things look well, I would like to see this patchset get some testing in -mm.

This patchset probably doesn't set the record for longest gestation period, but I am still glad that we can use it to solve a problem that a lot of people care about *now*. Maneesh and I developed this patch in 2001
where we used somewhat dodgy locking and copious memory barriers to demonstrate making file descriptor look-up (then fget()) lock-free using RCU. The main advantage was with threads, but there were other problems confronting threads users then and I decided not to push for it. Since threads performance is now important for a lot of people, it is time to revisit the issue. Whether we like java or not, it is a reality, so are threaded apps. Andrew Tridgell has a test (http://samba.org/ftp/unpacked/junkcode/thread_perf.c)
which shows that on a 4-cpu P4 box, a "readwrite" syscall test ran twice as fast using processes as threads.

An earlier version of this patchset was published and discussed a few months ago :
(http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2)
The consensus there was that it makes sense to make fget()/fget_light() lock-free in order to avoid the cache line bouncing on ->files_lock typically when the fd table is shared. The problem with that version of the patchset was that it piggybacked on kref and complicated a simple kref api meant for use with strict safety rules. It required invasive changes to wherever f_count was being used. It also used an RCU model from 2001 with explicit memory barriers which we don't need to use anymore.

Recently, I rewrote the patchset with the following ideas :

1. Instead of using explicit memory barriers to make the fd table array and fdset updates appear atomic to lock-free readers, I split the fd table in files_struct and put it in a separate structure (struct fdtable). Whenever fd array/set expansion happens, I allocate a new fdtable, copy the contents and atomically update the pointer. This allows me to use the recent rcu_assign_pointer() and rcu_dereference() macros. Howver this required significant changes in file management code in VFS. With this new locking model, all the known issues of the past have been taken care of.

2. Greg and I agreed not to loosen the kref apis. Instead I wrote a set of rcuref APIs that work on a regular atomic_t counters. This is *not* a separate refcounting API set, it is meant for use in regular refcounters when needed with RCU. With this, f_count users, however wrong they are, are spared. There is a separate patchset to clean some of them up, but that does not affect this patchset.

3. I added documentation for both the rcuref apis and for the new locking model I used for file descriptor table and file reference counting.

Testing :
-------
I have been beating up this patchset with multiplce instances of LTP and a special test I wrote to exercise the vmalloced fdtable path that uses keventd for freeing. It has survived 24+ hour tests as well as a 72 hour run with chat benchmark
and fd_vmalloc tests. All this was on a 4(8)-way P4 xeon system.

No slab leak or vmalloc leak.

I would appreciate if someone tests this on an arch without cmpxchg (sparc32??). I intend to run some more tests with preemption enabled and also on ppc64 myself.

Performance results :
-------------------

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

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

So, the lock-free file table patchset gets rid of the overhead of doing I/O with thread.

Thanks
Dipankar

Dipankar Sarma

author

2005-05-30 10:54 UTC #1 lore raw

Re: [rfc: patch 1/6] 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-05-30 10:58 UTC #2 lore raw

Re: [rfc: patch 2/6] rcuref APIs

In reply to 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]>

 Documentation/RCU/rcuref.txt |   74 ++++++++++++++
 include/linux/rcuref.h       |  215 +++++++++++++++++++++++++++++++++++++++++++
 kernel/rcupdate.c            |   14 ++
 3 files changed, 303 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 +215 -0

215 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 :(
+ */
+
+static 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-05-30 11:03 UTC #3 lore raw

Re: [rfc: patch 3/6] Break up files struct

In reply to Dipankar Sarma

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-05-30 11:06 UTC #4 lore raw

Re: [rfc: patch 4/6] files struct with rcu

In reply to Dipankar Sarma

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 Maneesh Soni <[email protected]>

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

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

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-05-30 11:08 UTC #5 lore raw

Re: [rfc: patch 5/6] lock free fd lookup

In reply to Dipankar Sarma

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-05-30 11:09 UTC #6 lore raw

Re: [rfc: patch 6/6] files locking doc

In reply to Dipankar Sarma

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.

William Lee Irwin III

2005-06-01 11:25 UTC #7 lore raw

In reply to Dipankar Sarma

Quoted 3 lines · Dipankar Sarma

I would appreciate if someone tests this on an arch without cmpxchg (sparc32??). I intend to run some more tests with preemption enabled and also on ppc64 myself.

sparc32 SMP is not going to be a good choice for this. By and large ll/sc -style architectures don't have explicit cmpxchg instructions so ppc64 at least nominally fits the bill. SMP Alpha testing may also be enlightening (as usual).

-- wli

Dipankar Sarma

author

2005-06-01 12:54 UTC #8 lore raw

Quoted 9 lines · William Lee Irwin III

Quoted 3 lines · Dipankar Sarma
I would appreciate if someone tests this on an arch without cmpxchg (sparc32??). I intend to run some more tests with preemption enabled and also on ppc64 myself.
sparc32 SMP is not going to be a good choice for this. By and large ll/sc -style architectures don't have explicit cmpxchg instructions so ppc64 at least nominally fits the bill. SMP Alpha testing may also be enlightening (as usual).

Actually, I was talking about cmpxchg() primitive in the kernel, not necessarily the instruction. ppc64 has a cmpxchg() primitive based on LL/SC. For the archs that do not have cmpxchg(), rcuref_inc_lf() uses a hashed lock to serialize the reference count updates. It would be nice to see that code get a spin on real hardware. AFAICS, sparc32 fits the bill.

Thanks
Dipankar