fs: use a sequence counter instead of file_lock in fd_install

Hi,

Currently obtaining a new file descriptor results in locking fdtable twice - once in order to reserve a slot and second time to fill it.

Hack below gets rid of the second lock usage.

It gives me a ~30% speedup (~300k ops -> ~400k ops) in a microbenchmark where 16 threads create a pipe (2 fds) and call 2 * close.

Results are fluctuating and even with the patch sometimes drop to around ~300k ops. However, without the patch they never get higher.

I can come up with a better benchmark if that's necessary.

Comments?

==============================================

Subject: [PATCH] fs: use a sequence counter instead of file_lock in fd_install

Because the lock is not held, it is possible that fdtable will be reallocated as we fill it.

RCU is used to guarantee the old table is not freed just in case we happen to write to it (which is harmless).

sequence counter is used to ensure we updated the right table.

Signed-off-by Mateusz Guzik <[email protected]>

---
 fs/file.c               | 24 +++++++++++++++++++-----
 include/linux/fdtable.h |  5 +++++
 2 files changed, 24 insertions(+), 5 deletions(-)

void fd_install(unsigned int fd, struct file *file)

include/linux/fdtable.h +1 -0

index 230f87b..9e41765 100644
@@ -12,6 +12,7 @@
 #include <linux/types.h>
 #include <linux/init.h>
 #include <linux/fs.h>
+#include <linux/seqlock.h>
 
 #include <linux/atomic.h>
 

include/linux/fdtable.h +3 -0

 	struct fdtable __rcu *fdt;
 	struct fdtable fdtab;
   /*

@@ -69,6 +71,9 @@ struct dentry;
 #define files_fdtable(files) \
 	rcu_dereference_check_fdtable((files), (files)->fdt)
 
+#define files_fdtable_seq(files) \
+	rcu_dereference((files)->fdt)
+
 /*
  * The caller must ensure that fd table isn't shared or hold rcu or file lock
  */

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 173

Quoted 10 lines · Mateusz Guzik

fs/file.c +2 -0

@@ -165,8 +165,10 @@ static int expand_fdtable(struct files_struct *files, int nr)
 	cur_fdt = files_fdtable(files);
 	if (nr >= cur_fdt->max_fds) {
 		/* Continue as planned */
+		write_seqcount_begin(&files->fdt_seqcount);
 		copy_fdtable(new_fdt, cur_fdt);
 		rcu_assign_pointer(files->fdt, new_fdt);
+		write_seqcount_end(&files->fdt_seqcount);
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);

Interesting. AFAICS, your test doesn't step anywhere near that path, does it? So basically you never hit the retries during that...

Quoted 14 lines · Al Viro

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 173

Quoted 10 lines · Mateusz Guzik

fs/file.c +2 -0

@@ -165,8 +165,10 @@ static int expand_fdtable(struct files_struct *files, int nr)
 	cur_fdt = files_fdtable(files);
 	if (nr >= cur_fdt->max_fds) {
 		/* Continue as planned */
+		write_seqcount_begin(&files->fdt_seqcount);
 		copy_fdtable(new_fdt, cur_fdt);
 		rcu_assign_pointer(files->fdt, new_fdt);
+		write_seqcount_end(&files->fdt_seqcount);
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);

Interesting. AFAICS, your test doesn't step anywhere near that path, does it? So basically you never hit the retries during that...

Right, but then the table is almost never changed for a given process, as we only increase it by power of two steps.

(So I scratch my initial comment, fdt_seqcount is really mostly read)

Quoted 16 lines · Eric Dumazet

Quoted 14 lines · Al Viro

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 173

Quoted 10 lines · Mateusz Guzik

fs/file.c +2 -0

@@ -165,8 +165,10 @@ static int expand_fdtable(struct files_struct *files, int nr)
 	cur_fdt = files_fdtable(files);
 	if (nr >= cur_fdt->max_fds) {
 		/* Continue as planned */
+		write_seqcount_begin(&files->fdt_seqcount);
 		copy_fdtable(new_fdt, cur_fdt);
 		rcu_assign_pointer(files->fdt, new_fdt);
+		write_seqcount_end(&files->fdt_seqcount);
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);

Interesting. AFAICS, your test doesn't step anywhere near that path, does it? So basically you never hit the retries during that...

Quoted 4 lines

Right, but then the table is almost never changed for a given process, as we only increase it by power of two steps.

(So I scratch my initial comment, fdt_seqcount is really mostly read)

I tested Mateusz patch with my opensock program, mimicking a bit more what a server does (having lot of sockets)

24 threads running, doing close(randomfd())/socket() calls like crazy.

Before patch :

# time ./opensock 

real 0m10.863s
user 0m0.954s
sys 2m43.659s

After patch :

# time ./opensock

real 0m9.750s
user 0m0.804s
sys 2m18.034s

So this is an improvement for sure, but not massive.

perf record ./opensock ; report

    87.80%  opensock  [kernel.kallsyms]  [k] _raw_spin_lock                     
               |--52.70%-- __close_fd
               |--46.41%-- __alloc_fd

Quoted 44 lines · Eric Dumazet

Quoted 16 lines · Eric Dumazet

Quoted 14 lines · Al Viro

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 173

Quoted 10 lines · Mateusz Guzik

fs/file.c +2 -0

@@ -165,8 +165,10 @@ static int expand_fdtable(struct files_struct *files, int nr)
 	cur_fdt = files_fdtable(files);
 	if (nr >= cur_fdt->max_fds) {
 		/* Continue as planned */
+		write_seqcount_begin(&files->fdt_seqcount);
 		copy_fdtable(new_fdt, cur_fdt);
 		rcu_assign_pointer(files->fdt, new_fdt);
+		write_seqcount_end(&files->fdt_seqcount);
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);

Interesting. AFAICS, your test doesn't step anywhere near that path, does it? So basically you never hit the retries during that...

Quoted 4 lines

Right, but then the table is almost never changed for a given process, as we only increase it by power of two steps.

(So I scratch my initial comment, fdt_seqcount is really mostly read)

I tested Mateusz patch with my opensock program, mimicking a bit more what a server does (having lot of sockets)

24 threads running, doing close(randomfd())/socket() calls like crazy.

Before patch :

# time ./opensock 

real 0m10.863s
user 0m0.954s
sys 2m43.659s

After patch :

# time ./opensock

real 0m9.750s
user 0m0.804s
sys 2m18.034s

Quoted 7 lines

So this is an improvement for sure, but not massive.

perf record ./opensock ; report

    87.80%  opensock  [kernel.kallsyms]  [k] _raw_spin_lock                     
               |--52.70%-- __close_fd
               |--46.41%-- __alloc_fd

My crap benchmark is here: http://people.redhat.com/~mguzik/pipebench.c
(compile with -pthread, run with -s 10 -n 16 for 10 second test + 16 threads)

As noted earlier it tends to go from rougly 300k ops/s to 400.

The fundamental problem here seems to be this pesky POSIX requirement of providing the lowest possible fd on each allocation (as a side note Linux breaks this with parallel fd allocs, where one of these backs off the reservation, not that I believe this causes trouble).

Ideally a process-wide switch could be implemented (e.g. prctl(SCRATCH_LOWEST_FD_REQ)) which would grant the kernel the freedom to return any fd it wants, so it would be possible to have fd ranges per thread and the like.

Having only a O_SCRATCH_POSIX flag passed to syscalls would still leave close() as a bottleneck.

In the meantime I consider the approach taken in my patch as an ok temporary improvement.

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 173

Quoted 10 lines · Mateusz Guzik

fs/file.c +2 -0

@@ -165,8 +165,10 @@ static int expand_fdtable(struct files_struct *files, int nr)
 	cur_fdt = files_fdtable(files);
 	if (nr >= cur_fdt->max_fds) {
 		/* Continue as planned */
+		write_seqcount_begin(&files->fdt_seqcount);
 		copy_fdtable(new_fdt, cur_fdt);
 		rcu_assign_pointer(files->fdt, new_fdt);
+		write_seqcount_end(&files->fdt_seqcount);
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);

Interesting. AFAICS, your test doesn't step anywhere near that path, does it? So basically you never hit the retries during that...

Hi,

Currently obtaining a new file descriptor results in locking fdtable twice - once in order to reserve a slot and second time to fill it

fs/file.c +5 -5

 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
-	BUG_ON(fdt->fd[fd] != NULL);
-	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+
+	rcu_read_lock();
+	do {
+		seq = read_seqcount_begin(&files->fdt_seqcount);
+		fdt = files_fdtable_seq(files);

Quoted 4 lines · Mateusz Guzik

Hi,

Currently obtaining a new file descriptor results in locking fdtable twice - once in order to reserve a slot and second time to fill it

...

fs/file.c EXPORT_SYMBOL(put_unused_fd); · line 559

Quoted 4 lines

void __fd_install(struct files_struct *files, unsigned int fd,

fs/file.c +1 -0

 		struct file *file)
 {
+	unsigned long seq;

	unsigned int seq;

Quoted 12 lines

fs/file.c +5 -5

 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
-	BUG_ON(fdt->fd[fd] != NULL);
-	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+
+	rcu_read_lock();
+	do {
+		seq = read_seqcount_begin(&files->fdt_seqcount);
+		fdt = files_fdtable_seq(files);

fs/file.c EXPORT_SYMBOL(put_unused_fd); · line 575

Quoted 10 lines

fs/file.c +9 -0

+		/*
+		 * Entry in the table can already be equal to file if we
+		 * had to restart and copy_fdtable picked up our update.
+		 */
+		BUG_ON(!(fdt->fd[fd] == NULL || fdt->fd[fd] == file));
+		rcu_assign_pointer(fdt->fd[fd], file);
+		smp_mb();
+	} while (__read_seqcount_retry(&files->fdt_seqcount, seq));
+	rcu_read_unlock();
 }

So one problem here is :

As soon as rcu_assign_pointer(fdt->fd[fd], file) is done, and other cpu does one expand_fdtable() and releases files->file_lock, another cpu can close(fd).

Then another cpu can reuse the [fd] now empty slot and install a new file in it.

Then this cpu will crash here :

BUG_ON(!(fdt->fd[fd] == NULL || fdt->fd[fd] == file));

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

Quoted 16 lines · Al Viro

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 4 lines

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

I would rather use an xchg() instead of rcu_assign_ponter()

old = xchg(&fdt->fd[fd], file);
if (unlikely(old))

	filp_close(old, files);

If threads are using close() on random fds, final result is not guaranteed anyway.

Quoted 22 lines · Eric Dumazet

Quoted 16 lines · Al Viro

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 4 lines

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

Quoted 9 lines

I would rather use an xchg() instead of rcu_assign_ponter()

old = xchg(&fdt->fd[fd], file);
if (unlikely(old))

	filp_close(old, files);

If threads are using close() on random fds, final result is not guaranteed anyway.

Well I don't see how could this be used to fix the problem.

If you are retrying and see NULL, you don't know whether your previous update was not picked up by memcpy OR the fd got closed, which also unreferenced the file you are installing. But you can't tell what happened.

If you see non-NULL and what you found is not the file you are installing, you know the file was freed so you can't close the old file.

One could try to introduce an invariant that files installed in a lockless manner have to start with refcount 1, you still can't infer anything from the fact that the counter is 1 when you retry (even if you take the lock). It could have been duped, or even sent over a unix socket and closed (although that awould surely require a solid pause in execution) and who knows what else.

In general I would say this approach is too hard to get right to be worthwile given expected speedup.

Hey, that's because I really meant (during the week end)

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

Quoted 16 lines · Al Viro

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 4 lines

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

Well as it was noted I have not checked how it's implemented at the time of writing the message. I agree embedding something like this into files struct is a non-starter.

I would say this could work with a small set of locks, selected by hashing struct files pointer.

Table resizing is supposed to be extremely rare - most processes should not need it at all (if they do, the default size is too small and should be adjusted). Not only that, the lock is only needed if the process in question is multithreaded.

So I would say this would not contend in real-world workloads, but still looks crappy.

Unfortunately the whole thing loses original appeal of a simple hack with no potential perfomrance drawbacks. Maybe I'll hack it up later and run some tests anyway.

Quoted 34 lines · Mateusz Guzik

Quoted 16 lines · Al Viro

Quoted 14 lines · Mateusz Guzik

I would say this makes the use of seq counter impossible. Even if we decided to fall back to a lock on retry, we cannot know what to do if the slot is reserved - it very well could be that something called close, and something else reserved the slot, so putting the file inside could be really bad. In fact we would be putting a file for which we don't have a reference anymore.

However, not all hope is lost and I still think we can speed things up.

A locking primitive which only locks stuff for current cpu and has another mode where it locks stuff for all cpus would do the trick just fine. I'm not a linux guy, quick search suggests 'lglock' would do what I want.

Quoted 4 lines

Quoted 2 lines

table reallocation is an extremely rare operation, so this should be fine. It would take the lock 'globally' for given table.

It would also mean percpu_alloc() for each descriptor table...

Well as it was noted I have not checked how it's implemented at the time of writing the message. I agree embedding something like this into files struct is a non-starter.

I would say this could work with a small set of locks, selected by hashing struct files pointer.

Table resizing is supposed to be extremely rare - most processes should not need it at all (if they do, the default size is too small and should be adjusted). Not only that, the lock is only needed if the process in question is multithreaded.

Quoted 7 lines

So I would say this would not contend in real-world workloads, but still looks crappy.

Unfortunately the whole thing loses original appeal of a simple hack with no potential perfomrance drawbacks. Maybe I'll hack it up later and run some tests anyway.

I just came up with another stupid hack, but this time it could really work just fine.

Note that the entire issue stems from the fact that the table can be resized at any moment. If only we had a guarantee the table "stands still", we would not even need that sequence couner. fd_install could just plop the file in.

So a stupid hack which comes to mind tells the kernel to make sure the table is big enough and then never resize it ever again (inherited on fork, cleared on exec):
prctl(FDTABLE_SIZE_FIXED, BIGNUM);

or

dup2(0, BIGNUM); /* sizes the table appropriately */ close(BIGNUM);
prctl(FDTABLE_SIZE_FIXED);

Thoughts?

Sorry for spam but I came up with another hack. :)

The idea is that we can have a variable which would signify the that given thread is playing with fd table in fd_install (kind of a lock embedded into task_struct). We would also have a flag in files struct indicating that a thread would like to resize it.

expand_fdtable would set the flag and iterate over all threads waiting for all of them to have the var set to 0.

Quoted 7 lines · Mateusz Guzik

Sorry for spam but I came up with another hack. :)

The idea is that we can have a variable which would signify the that given thread is playing with fd table in fd_install (kind of a lock embedded into task_struct). We would also have a flag in files struct indicating that a thread would like to resize it.

Quoted 2 lines

expand_fdtable would set the flag and iterate over all threads waiting for all of them to have the var set to 0.

The opposite : you have to block them in some way and add a rcu_sched() or something.

Quoted 9 lines · Eric Dumazet

Quoted 7 lines · Mateusz Guzik

Sorry for spam but I came up with another hack. :)

The idea is that we can have a variable which would signify the that given thread is playing with fd table in fd_install (kind of a lock embedded into task_struct). We would also have a flag in files struct indicating that a thread would like to resize it.

Quoted 5 lines

Quoted 2 lines

expand_fdtable would set the flag and iterate over all threads waiting for all of them to have the var set to 0.

The opposite : you have to block them in some way and add a rcu_sched() or something.

Here is the patch I cooked here but not yet tested.

Quoted 10 lines · Eric Dumazet

Quoted 9 lines · Eric Dumazet

Quoted 7 lines · Mateusz Guzik

Sorry for spam but I came up with another hack. :)

The idea is that we can have a variable which would signify the that given thread is playing with fd table in fd_install (kind of a lock embedded into task_struct). We would also have a flag in files struct indicating that a thread would like to resize it.

Quoted 6 lines

Quoted 5 lines

Quoted 2 lines

expand_fdtable would set the flag and iterate over all threads waiting for all of them to have the var set to 0.

The opposite : you have to block them in some way and add a rcu_sched() or something.

Quoted 1 line

Here is the patch I cooked here but not yet tested.

In following version :

1) I replaced the yield() hack by a proper wait queue.

2) I do not invoke synchronize_sched() for mono threaded programs.

3) I avoid multiple threads doing a resize and then only one wins the deal.

(copying/clearing big amount of memory only to discover another guy did the same is a big waste of resources)

This seems to run properly on my hosts.

Your comments/tests are most welcomed, thanks !

 fs/file.c               |   41 +++++++++++++++++++++++++++++++++-----
 include/linux/fdtable.h |    3 ++
 2 files changed, 39 insertions(+), 5 deletions(-)

fs/file.c +3 -0

index 93c5f89c248b..e0e113a56444 100644
@@ -147,6 +147,9 @@ static int expand_fdtable(struct files_struct *files, int nr)
 
 	spin_unlock(&files->file_lock);
 	new_fdt = alloc_fdtable(nr);
+	/* make sure no __fd_install() are still updating fdt */
+	if (atomic_read(&files->count) > 1)
+		synchronize_sched();
 	spin_lock(&files->file_lock);
 	if (!new_fdt)
 		return -ENOMEM;

fs/file.c +5 -1

 	}
+	/* coupled with smp_rmb() in __fd_install() */
+	smp_wmb();
 	return 1;
 }
 

@@ -187,19 +193,33 @@ static int expand_fdtable(struct files_struct *files, int nr)
 static int expand_files(struct files_struct *files, int nr)
 {
 	struct fdtable *fdt;
+	int expanded = 0;
 
+begin:
 	fdt = files_fdtable(files);
 
 	/* Do we need to expand? */
 	if (nr < fdt->max_fds)
-		return 0;
+		return expanded;
 
 	/* Can we expand? */

fs/file.c +20 -4

+
 	/* All good, so we try */
-	return expand_fdtable(files, nr);
+	files->resize_in_progress = true;
+	expanded = expand_fdtable(files, nr);
+	files->resize_in_progress = false;
+	wake_up_all(&files->resize_wait);
+	return expanded;
 }
 
 static inline void __set_close_on_exec(int fd, struct fdtable *fdt)

@@ -256,6 +276,8 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	atomic_set(&newf->count, 1);
 
 	spin_lock_init(&newf->file_lock);
+	newf->resize_in_progress = 0;
+	init_waitqueue_head(&newf->resize_wait);
 	newf->next_fd = 0;
 	new_fdt = &newf->fdtab;
 	new_fdt->max_fds = NR_OPEN_DEFAULT;

@@ -553,11 +575,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		rcu_read_lock_sched();
+	}
+	/* coupled with smp_wmb() in expand_fdtable() */
+	smp_rmb();
+	fdt = READ_ONCE(files->fdt);
 	BUG_ON(fdt->fd[fd] != NULL);
 	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock_sched();
 }
 
 void fd_install(unsigned int fd, struct file *file)

include/linux/fdtable.h +3 -0

index 230f87bdf5ad..fbb88740634a 100644
@@ -47,6 +47,9 @@ struct files_struct {
    * read mostly part
    */
 	atomic_t count;
+	bool resize_in_progress;
+	wait_queue_head_t resize_wait;
+
 	struct fdtable __rcu *fdt;
 	struct fdtable fdtab;
   /*

Quoted 11 lines · Eric Dumazet

Quoted 10 lines · Eric Dumazet

Quoted 9 lines · Eric Dumazet

Quoted 7 lines · Mateusz Guzik

Sorry for spam but I came up with another hack. :)

The idea is that we can have a variable which would signify the that given thread is playing with fd table in fd_install (kind of a lock embedded into task_struct). We would also have a flag in files struct indicating that a thread would like to resize it.

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

Quoted 2 lines

expand_fdtable would set the flag and iterate over all threads waiting for all of them to have the var set to 0.

The opposite : you have to block them in some way and add a rcu_sched() or something.

What I described would block them, although it was a crappy approach (iterating threads vs cpus). I was wondering if RCU could be abused for this feature and apparently it can.

Quoted 11 lines

Quoted 1 line

Here is the patch I cooked here but not yet tested.

In following version :

1) I replaced the yield() hack by a proper wait queue.

2) I do not invoke synchronize_sched() for mono threaded programs.

3) I avoid multiple threads doing a resize and then only one wins the deal.

One could argue this last bit could be committed separately (a different logical change).

As I read up about synchronize_sched and rcu_read_lock_sched, the code should be correct.

Also see nits below.

Quoted 27 lines

(copying/clearing big amount of memory only to discover another guy did the same is a big waste of resources)

This seems to run properly on my hosts.

Your comments/tests are most welcomed, thanks !

 fs/file.c               |   41 +++++++++++++++++++++++++++++++++-----
 include/linux/fdtable.h |    3 ++
 2 files changed, 39 insertions(+), 5 deletions(-)

fs/file.c +3 -0

index 93c5f89c248b..e0e113a56444 100644
@@ -147,6 +147,9 @@ static int expand_fdtable(struct files_struct *files, int nr)
 
 	spin_unlock(&files->file_lock);
 	new_fdt = alloc_fdtable(nr);
+	/* make sure no __fd_install() are still updating fdt */
+	if (atomic_read(&files->count) > 1)
+		synchronize_sched();
 	spin_lock(&files->file_lock);
 	if (!new_fdt)
 		return -ENOMEM;

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 178

Quoted 6 lines

fs/file.c +1 -0

@@ -170,9 +173,12 @@ static int expand_fdtable(struct files_struct *files, int nr)
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);
 	} else {
+		WARN_ON_ONCE(1);
 		/* Somebody else expanded, so undo our attempt */
 		__free_fdtable(new_fdt);

The reader may be left confused why there is a warning while the comment does not indicate anything is wrong.

Quoted 21 lines

fs/file.c +5 -1

 	}
+	/* coupled with smp_rmb() in __fd_install() */
+	smp_wmb();
 	return 1;
 }
 

@@ -187,19 +193,33 @@ static int expand_fdtable(struct files_struct *files, int nr)
 static int expand_files(struct files_struct *files, int nr)
 {
 	struct fdtable *fdt;
+	int expanded = 0;
 
+begin:
 	fdt = files_fdtable(files);
 
 	/* Do we need to expand? */
 	if (nr < fdt->max_fds)
-		return 0;
+		return expanded;
 
 	/* Can we expand? */

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 215

Quoted 10 lines

fs/file.c +7 -0

 	if (nr >= sysctl_nr_open)
 		return -EMFILE;
 
+	while (unlikely(files->resize_in_progress)) {
+		spin_unlock(&files->file_lock);
+		expanded = 1;
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		spin_lock(&files->file_lock);
+		goto begin;
+	}

This does not loop anymore, so s/while/if/ ?

Quoted 62 lines

fs/file.c +20 -4

+
 	/* All good, so we try */
-	return expand_fdtable(files, nr);
+	files->resize_in_progress = true;
+	expanded = expand_fdtable(files, nr);
+	files->resize_in_progress = false;
+	wake_up_all(&files->resize_wait);
+	return expanded;
 }
 
 static inline void __set_close_on_exec(int fd, struct fdtable *fdt)

@@ -256,6 +276,8 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	atomic_set(&newf->count, 1);
 
 	spin_lock_init(&newf->file_lock);
+	newf->resize_in_progress = 0;
+	init_waitqueue_head(&newf->resize_wait);
 	newf->next_fd = 0;
 	new_fdt = &newf->fdtab;
 	new_fdt->max_fds = NR_OPEN_DEFAULT;

@@ -553,11 +575,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		rcu_read_lock_sched();
+	}
+	/* coupled with smp_wmb() in expand_fdtable() */
+	smp_rmb();
+	fdt = READ_ONCE(files->fdt);
 	BUG_ON(fdt->fd[fd] != NULL);
 	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock_sched();
 }
 
 void fd_install(unsigned int fd, struct file *file)

include/linux/fdtable.h +3 -0

index 230f87bdf5ad..fbb88740634a 100644
@@ -47,6 +47,9 @@ struct files_struct {
    * read mostly part
    */
 	atomic_t count;
+	bool resize_in_progress;
+	wait_queue_head_t resize_wait;
+
 	struct fdtable __rcu *fdt;
 	struct fdtable fdtab;
   /*

Signature · 1 line

Mateusz Guzik

in dup_fd:

       for (i = open_files; i != 0; i--) {
                struct file *f = *old_fds++;
                if (f) {
                        get_file(f);

at least a data dependency barrier, or maybe smp_rmb for peace of mind

similarly in do_dup2:

        tofree = fdt->fd[fd];
        if (!tofree && fd_is_open(fd, fdt))
                goto Ebusy;

From: Eric Dumazet <[email protected]>

Mateusz Guzik reported :

Currently obtaining a new file descriptor results in locking fdtable twice - once in order to reserve a slot and second time to fill it.

Holding the spinlock in __fd_install() is needed in case a resize is done, or to prevent a resize.

Mateusz provided an RFC patch and a micro benchmark :
http://people.redhat.com/~mguzik/pipebench.c

A resize is an unlikely operation in a process lifetime, as table size is at least doubled at every resize.

We can use RCU instead of the spinlock :

__fd_install() must wait if a resize is in progress.

The resize must block new __fd_install() callers from starting, and wait that ongoing install are finished (synchronize_sched())

resize should be attempted by a single thread to not waste resources.

rcu_sched variant is used, as __fd_install() and expand_fdtable() run from process context.

It gives us a ~30% speedup using pipebench with 16 threads, and a ~10% speedup with another program using TCP sockets.

Signed-off-by Eric Dumazet <[email protected]>

Reported-by Mateusz Guzik <[email protected]>

---
 fs/file.c               |   66 +++++++++++++++++++++++++++-----------
 include/linux/fdtable.h |    3 +
 2 files changed, 50 insertions(+), 19 deletions(-)

fs/file.c +47 -19

index 93c5f89c248b..17cef5e52f16 100644
@@ -147,6 +147,13 @@ static int expand_fdtable(struct files_struct *files, int nr)
 
 	spin_unlock(&files->file_lock);
 	new_fdt = alloc_fdtable(nr);
+
+	/* make sure all __fd_install() have seen resize_in_progress
+	 * or have finished their rcu_read_lock_sched() section.
+	 */
+	if (atomic_read(&files->count) > 1)
+		synchronize_sched();
+
 	spin_lock(&files->file_lock);
 	if (!new_fdt)
 		return -ENOMEM;

@@ -158,21 +165,14 @@ static int expand_fdtable(struct files_struct *files, int nr)
 		__free_fdtable(new_fdt);
 		return -EMFILE;
 	}
-	/*
-	 * Check again since another task may have expanded the fd table while
-	 * we dropped the lock
-	 */
 	cur_fdt = files_fdtable(files);
-	if (nr >= cur_fdt->max_fds) {
-		/* Continue as planned */
-		copy_fdtable(new_fdt, cur_fdt);
-		rcu_assign_pointer(files->fdt, new_fdt);
-		if (cur_fdt != &files->fdtab)
-			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);
-	} else {
-		/* Somebody else expanded, so undo our attempt */
-		__free_fdtable(new_fdt);
-	}
+	BUG_ON(nr < cur_fdt->max_fds);
+	copy_fdtable(new_fdt, cur_fdt);
+	rcu_assign_pointer(files->fdt, new_fdt);
+	if (cur_fdt != &files->fdtab)
+		call_rcu(&cur_fdt->rcu, free_fdtable_rcu);
+	/* coupled with smp_rmb() in __fd_install() */
+	smp_wmb();
 	return 1;
 }
 

@@ -185,21 +185,38 @@ static int expand_fdtable(struct files_struct *files, int nr)
  * The files->file_lock should be held on entry, and will be held on exit.
  */
 static int expand_files(struct files_struct *files, int nr)
+	__releases(files->file_lock)
+	__acquires(files->file_lock)
 {
 	struct fdtable *fdt;
+	int expanded = 0;
 
+repeat:
 	fdt = files_fdtable(files);
 
 	/* Do we need to expand? */
 	if (nr < fdt->max_fds)
-		return 0;
+		return expanded;
 
 	/* Can we expand? */
 	if (nr >= sysctl_nr_open)
 		return -EMFILE;
 
+	if (unlikely(files->resize_in_progress)) {
+		spin_unlock(&files->file_lock);
+		expanded = 1;
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		spin_lock(&files->file_lock);
+		goto repeat;
+	}
+
 	/* All good, so we try */
-	return expand_fdtable(files, nr);
+	files->resize_in_progress = true;
+	expanded = expand_fdtable(files, nr);
+	files->resize_in_progress = false;
+
+	wake_up_all(&files->resize_wait);
+	return expanded;
 }
 
 static inline void __set_close_on_exec(int fd, struct fdtable *fdt)

@@ -256,6 +273,8 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	atomic_set(&newf->count, 1);
 
 	spin_lock_init(&newf->file_lock);
+	newf->resize_in_progress = false;
+	init_waitqueue_head(&newf->resize_wait);
 	newf->next_fd = 0;
 	new_fdt = &newf->fdtab;
 	new_fdt->max_fds = NR_OPEN_DEFAULT;

@@ -553,11 +572,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		rcu_read_lock_sched();
+	}
+	/* coupled with smp_wmb() in expand_fdtable() */
+	smp_rmb();
+	fdt = READ_ONCE(files->fdt);
 	BUG_ON(fdt->fd[fd] != NULL);
 	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock_sched();
 }
 
 void fd_install(unsigned int fd, struct file *file)

include/linux/fdtable.h +3 -0

index 230f87bdf5ad..fbb88740634a 100644
@@ -47,6 +47,9 @@ struct files_struct {
    * read mostly part
    */
 	atomic_t count;
+	bool resize_in_progress;
+	wait_queue_head_t resize_wait;
+
 	struct fdtable __rcu *fdt;
 	struct fdtable fdtab;
   /*

Quoted 28 lines · Eric Dumazet

From: Eric Dumazet <[email protected]>

Mateusz Guzik reported :

Currently obtaining a new file descriptor results in locking fdtable twice - once in order to reserve a slot and second time to fill it.

Holding the spinlock in __fd_install() is needed in case a resize is done, or to prevent a resize.

Mateusz provided an RFC patch and a micro benchmark :
http://people.redhat.com/~mguzik/pipebench.c

A resize is an unlikely operation in a process lifetime, as table size is at least doubled at every resize.

We can use RCU instead of the spinlock :

__fd_install() must wait if a resize is in progress.

The resize must block new __fd_install() callers from starting, and wait that ongoing install are finished (synchronize_sched())

resize should be attempted by a single thread to not waste resources.

rcu_sched variant is used, as __fd_install() and expand_fdtable() run from process context.

Quoted 5 lines

It gives us a ~30% speedup using pipebench with 16 threads, and a ~10% speedup with another program using TCP sockets.

Signed-off-by Eric Dumazet <[email protected]>

Reported-by Mateusz Guzik <[email protected]>

Reviewed-by Mateusz Guzik <[email protected]>

Tested-by Mateusz Guzik <[email protected]>

Quoted 17 lines

fs/file.c +10 -2

 	new_fdt->max_fds = NR_OPEN_DEFAULT;

@@ -553,11 +572,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		rcu_read_lock_sched();
+	}
+	/* coupled with smp_wmb() in expand_fdtable() */
+	smp_rmb();

fs/file.c void __fd_install(struct files_struct *files, unsigned int fd, · line 585

Quoted 1 line

fs/file.c +1 -0

+	fdt = READ_ONCE(files->fdt);

Quoted 6 lines

fs/file.c +1 -1

 	BUG_ON(fdt->fd[fd] != NULL);
 	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock_sched();
 }
 

fs/file.c +5 -2

@@ -553,11 +572,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();

Quoted 11 lines · Eric Dumazet

fs/file.c +5 -2

@@ -553,11 +572,20 @@ void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
 	struct fdtable *fdt;
-	spin_lock(&files->file_lock);
-	fdt = files_fdtable(files);
+
+	rcu_read_lock_sched();
+
+	while (unlikely(files->resize_in_progress)) {
+		rcu_read_unlock_sched();

fs/file.c void __fd_install(struct files_struct *files, unsigned int fd, · line 588

Quoted 10 lines

fs/file.c +7 -1

+		wait_event(files->resize_wait, !files->resize_in_progress);
+		rcu_read_lock_sched();
+	}
+	/* coupled with smp_wmb() in expand_fdtable() */
+	smp_rmb();
+	fdt = rcu_dereference_sched(files->fdt);
 	BUG_ON(fdt->fd[fd] != NULL);
 	rcu_assign_pointer(fdt->fd[fd], file);
-	spin_unlock(&files->file_lock);
+	rcu_read_unlock_sched();

Umm... You've taken something that was safe to use in atomic contexts and turned into something that might wait for GFP_KERNEL allocation; what's to guarantee that no users get broken by that? At the very least, you want to slap might_sleep() in there - the actual sleep is going to be very rare, so it would be an extremely hard to reproduce and debug.

AFAICS, all current in-tree users should be safe, but fd_install() is exported and quiet changes of that sort are rather antisocial. Generally I don't give a damn about out-of-tree code, but this one is over the top.

I _think_ it's otherwise OK, but please, add might_sleep() *AND* a note in Documentation/filesystems/porting.

Quoted 6 lines · Mateusz Guzik

in dup_fd:

       for (i = open_files; i != 0; i--) {
                struct file *f = *old_fds++;
                if (f) {
                        get_file(f);

I see no new requirement here. f is either NULL or not. multi threaded programs never had a guarantee dup_fd() would catch a non NULL pointer here.

Quoted 7 lines

at least a data dependency barrier, or maybe smp_rmb for peace of mind

similarly in do_dup2:

        tofree = fdt->fd[fd];
        if (!tofree && fd_is_open(fd, fdt))
                goto Ebusy;

Same here.

Quoted 9 lines · Eric Dumazet

Quoted 6 lines · Mateusz Guzik

in dup_fd:

       for (i = open_files; i != 0; i--) {
                struct file *f = *old_fds++;
                if (f) {
                        get_file(f);

Quoted 4 lines

I see no new requirement here. f is either NULL or not. multi threaded programs never had a guarantee dup_fd() would catch a non NULL pointer here.

It's not about seeing NULL f or not, but using the right address for dereference.

If I read memory-barriers.txt right (see 'DATA DEPENDENCY BARRIERS'), it is possible that cpus like alpha will see a non-NULL pointer and then proceed to dereference *the old* (here: NULL) value.

Hence I suspect this needs smp_read_barrier_depends (along with ACCESS_ONCE).

Other consumers (e.g. procfs code) use rcu_dereference macro which does ends up using lockless_dereference macro, which in turn does:
#define lockless_dereference(p) \

({ \
        typeof(p) _________p1 = ACCESS_ONCE(p); \
	        smp_read_barrier_depends(); /* Dependency order vs. p
		above. */ \
		        (_________p1); \
})

That said memory barriers are not exactly my strong suit, but I do believe my suspicion here is justified enough to ask someone with solid memory barrier-fu to comment.

Quoted 3 lines · Eric Dumazet

3) I avoid multiple threads doing a resize and then only one wins the deal.

One could argue this last bit could be committed separately (a different logical change).

As I read up about synchronize_sched and rcu_read_lock_sched, the code should be correct.

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 178

Quoted 10 lines

fs/file.c +1 -0

 	spin_lock(&files->file_lock);
 	if (!new_fdt)
 		return -ENOMEM;

@@ -170,9 +173,12 @@ static int expand_fdtable(struct files_struct *files, int nr)
 		if (cur_fdt != &files->fdtab)
 			call_rcu(&cur_fdt->rcu, free_fdtable_rcu);
 	} else {
+		WARN_ON_ONCE(1);
 		/* Somebody else expanded, so undo our attempt */
 		__free_fdtable(new_fdt);

The reader may be left confused why there is a warning while the comment does not indicate anything is wrong.

Quoted 25 lines

fs/file.c +5 -1

 	}
+	/* coupled with smp_rmb() in __fd_install() */
+	smp_wmb();
 	return 1;
 }
 

@@ -187,19 +193,33 @@ static int expand_fdtable(struct files_struct *files, int nr)
 static int expand_files(struct files_struct *files, int nr)
 {
 	struct fdtable *fdt;
+	int expanded = 0;
 
+begin:
 	fdt = files_fdtable(files);
 
 	/* Do we need to expand? */
 	if (nr < fdt->max_fds)
-		return 0;
+		return expanded;
 
 	/* Can we expand? */
 	if (nr >= sysctl_nr_open)
 		return -EMFILE;
 

fs/file.c static int expand_fdtable(struct files_struct *files, int nr) · line 215

Quoted 7 lines

fs/file.c +7 -0

+	while (unlikely(files->resize_in_progress)) {
+		spin_unlock(&files->file_lock);
+		expanded = 1;
+		wait_event(files->resize_wait, !files->resize_in_progress);
+		spin_lock(&files->file_lock);
+		goto begin;
+	}

This does not loop anymore, so s/while/if/ ?