task_work: remove fifo ordering guarantee
Subsystems (4)
PATCH 1/1 task_work: remove fifo ordering guarantee
From: Eric Dumazet <[email protected]>
In commit f341861fb0b ("task_work: add a scheduling point in task_work_run()") I fixed a latency problem adding a cond_resched() call.
Later, commit ac3d0da8f329 added yet another loop to reverse a list, bringing back the latency spike :
I've seen in some cases this loop taking 275 ms, if for example a process with 2,000,000 files is killed.
We could add yet another cond_resched() in the reverse loop, or we can simply remove the reversal, as I do not think anything would depend on order of task_work_add() submitted works.
--- kernel/task_work.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-)
kernel/task_work.c +2 -10
@@ -18,6 +18,8 @@ static struct callback_head work_exited; /* all we need is ->next == NULL */* This is like the signal handler which runs in kernel mode, but it doesn't * try to wake up the @task. * +* Note: there is no ordering guarantee on works queued here. +* * RETURNS: * 0 if succeeds or -ESRCH. */
@@ -108,16 +110,6 @@ void task_work_run(void)raw_spin_unlock_wait (&task->pi_lock);smp_mb (); -/* Reverse the list to run the works in fifo order */ - head =NULL ; -do { - next = work->next; - work->next = head; - head = work; - work = next; - }while (work); - - work = head; do { next = work->next; work->func(work);
Quoted 4 lines · Eric Dumazet
We could add yet another
cond_resched()in the reverse loop, or we can simply remove the reversal, as I do not think anything would depend on order oftask_work_add()submitted works.
So I think this should be ok, with things like file closing not really caring about ordering as far as I can tell.
However, has anybody gone through all the task-work users? I looked quickly at the task_work_add() cases, and didn't see anything that looked like it would care, but others should look too. In the vfs, theres' the delayed fput and mnt freeing, and there's a keyring installation one.
The threaded irq handlers use it as that exit-time hack, which certainly shouldn't care, and there's some uprobe thing.
Can anybody see anything fishy?
Linus
Quoted 14 lines · Linus Torvalds
Quoted 4 lines · Eric Dumazet
We could add yet another
cond_resched()in the reverse loop, or we can simply remove the reversal, as I do not think anything would depend on order oftask_work_add()submitted works.So I think this should be ok, with things like file closing not really caring about ordering as far as I can tell.
However, has anybody gone through all the task-work users? I looked quickly at the
task_work_add()cases, and didn't see anything that looked like it would care, but others should look too. In the vfs, theres' the delayed fput and mnt freeing, and there's a keyring installation one.
Quoted 4 lines
The threaded irq handlers use it as that exit-time hack, which certainly shouldn't care, and there's some uprobe thing.
Can anybody see anything fishy?
So I'm wondering, is there any strong reason why we couldn't use a double linked list and still do FIFO and remove that silly linear list walking hack?
Thanks,
Ingo
Quoted 3 lines · Ingo Molnar
So I'm wondering, is there any strong reason why we couldn't use a double linked list and still do FIFO and remove that silly linear list walking hack?
This will obviously enlarge callback_head, and it is often embedded. But this is minor.
If we use a double linked list we can't do task_work_add() lockless. So we will need another spinlock_t in task_struct. We can't use pi_lock.
Oleg.
Quoted 10 lines · Oleg Nesterov
Quoted 3 lines · Ingo Molnar
So I'm wondering, is there any strong reason why we couldn't use a double linked list and still do FIFO and remove that silly linear list walking hack?
This will obviously enlarge
callback_head, and it is often embedded. But this is minor.If we use a double linked list we can't do
task_work_add()lockless. So we will need anotherspinlock_tintask_struct. We can't usepi_lock.
The fact that the O(N) overhead was measured in real apps to be in the milliseconds IMHO weakens cycle-level concerns about also having a spinlock next to the list head. (There's no additional cacheline bouncing concerns with the
spinlock: the head of a LIFO list is essentially a bouncing cacheline.)
If there's some other solution, sure, but LIFO queues tend to be trouble down the line.
Thanks,
Ingo
Quoted 11 lines · Ingo Molnar
Quoted 8 lines · Oleg Nesterov
Quoted 3 lines · Ingo Molnar
So I'm wondering, is there any strong reason why we couldn't use a double linked list and still do FIFO and remove that silly linear list walking hack?
This will obviously enlarge
callback_head, and it is often embedded. But this is minor.
Quoted 7 lines
Quoted 2 lines
If we use a double linked list we can't do
task_work_add()lockless. So we will need anotherspinlock_tintask_struct. We can't usepi_lock.The fact that the O(N) overhead was measured in real apps to be in the milliseconds IMHO weakens cycle-level concerns about also having a spinlock next to the list head. (There's no additional cacheline bouncing concerns with the
spinlock: the head of a LIFO list is essentially a bouncing cacheline.)
I agree. I just tried to explain that we need a bit more changes than just s/callback_head/list_head/ in task_struct.
And. The fact that this O(N) overhead was measured means that we have more overhead with offload-fput-to-exit_task_work which would be nice to remove as well.
Oleg.
Quoted 7 lines · Eric Dumazet
From: Eric Dumazet <[email protected]>
In commit
f341861fb0b("task_work: add a scheduling point intask_work_run()") I fixed a latency problem adding acond_resched()call.
Quoted 7 lines
Later, commit
ac3d0da8f329added yet another loop to reverse a list, bringing back the latency spike :I've seen in some cases this loop taking 275 ms, if for example a process with 2,000,000 files is killed.
We could add yet another
cond_resched()in the reverse loop,
Can't we do this?
Quoted 3 lines
or we
can simply remove the reversal, as I do not think anything would depend on order oftask_work_add()submitted works.
Personally I'd prefer to keep the fifo ordering. It just makes more sense imho. Even if currently nobody depends on it (although I am not sure about out-of-tree modules, say, systemtap).
Let's look keyctl_session_to_parent(). It does task_work_cancel() but only because we can not trust user-space. Otherwise we could remove it and just do task_work_add(), but this needs fifo.
Fifo just looks more sane to me.
Oleg.
Quoted 11 lines · Oleg Nesterov
Quoted 10 lines · Eric Dumazet
From: Eric Dumazet <[email protected]>
In commit
f341861fb0b("task_work: add a scheduling point intask_work_run()") I fixed a latency problem adding acond_resched()call.Later, commit
ac3d0da8f329added yet another loop to reverse a list, bringing back the latency spike :
Quoted 6 lines
Quoted 4 lines
I've seen in some cases this loop taking 275 ms, if for example a process with 2,000,000 files is killed.
We could add yet another
cond_resched()in the reverse loop,Can't we do this?
Well, I stated in the changelog we could. Obviously we can.
Adding 275 ms of pure overhead to perform this list reversal for files to be closed is quite unfortunate.
Quoted 7 lines
Personally I'd prefer to keep the fifo ordering. It just makes more sense imho. Even if currently nobody depends on it (although I am not sure about out-of-tree modules, say, systemtap).
Let's look
keyctl_session_to_parent(). It doestask_work_cancel()but only because we can not trust user-space. Otherwise we could remove it and just dotask_work_add(), but this needs fifo.
So it looks like there is no problem today, right, other than the possibility to parse a long list while blocking IRQ ?
Quoted 2 lines
Fifo just looks more sane to me.
Well, files are closed in a random order. These are the main user of this stuff.
If this is that critical, maybe use 2 lists, one for stuff needing fifo, and another one for un-ordered stuff (ed : file closing), and add a boolean to task_work_add()/task_work_cancel(). This adds yet another field into struct task_struct.
Now we also could question why we needed commit 4a9d4b024a3102fc083c925c242d98ac27b1c5f6 ("switch fput to task_work_add ") since it seems quite an overhead at task exit with 10^6 of files to close.
I understood the 'schedule_work() for interrupt/kernel_thread callers' part, but not the task_work_add() one.
Quoted 7 lines · Eric Dumazet
Now we also could question why we needed commit
4a9d4b024a3102fc083c925c242d98ac27b1c5f6("switch fput totask_work_add") since it seems quite an overhead at task exit with 10^6 of files to close.I understood the '
schedule_work()for interrupt/kernel_thread callers' part, but not thetask_work_add()one.
If this needs to be kept, maybe then add following, to make sure we flush the list at most every BITS_PER_LONG files
fs/file.c +1 -0
@@ -22,6 +22,7 @@#include <linux/spinlock.h> #include <linux/rcupdate.h> #include <linux/workqueue.h> +#include <linux/task_work.h> int sysctl_nr_open__read_mostly =1024 *1024 ;int sysctl_nr_open_min =BITS_PER_LONG ;
@@ -392,6 +393,7 @@ static struct fdtable *close_files(struct
files_struct * files)
i++;
set >>= 1;
}
+ task_work_run();
}
return fdt;
Quoted 3 lines · Eric Dumazet
If this needs to be kept, maybe then add following, to make sure we flush the list at most every
BITS_PER_LONGfiles
Hmm.
I'm wondering if we should just make close_files() (or maybe even filp_close()) use a synchronous fput().
Iirc, the reason we delay fput() is that we had some nasty issues for the generic fput case. It was called from interrupt context by the aio code, and just in general there's a lot of nasty cases that can cause the final fput to happen (so there are lockdep issues with the mmap locks because the last fput being from munmap etc).
Maybe I forget some detail - it's been several years by now - but I think we could make the regular "close()" and "exit()" cases just use the synchronous fput (it's called "__fput_sync()" and currently explicitly limited to just kernel threads).
Al?
Because it feels all kinds of stupid to add things to the task-work queue just to then remove it almost immediately again. And close_files() is also called from various contexts. but the whole "put the final 'files_struct' case is certainly not at all as special as the 'put the final file'.
Linus
Quoted 26 lines · Linus Torvalds
Quoted 3 lines · Eric Dumazet
If this needs to be kept, maybe then add following, to make sure we flush the list at most every
BITS_PER_LONGfilesHmm.
I'm wondering if we should just make
close_files()(or maybe evenfilp_close()) use a synchronousfput().Iirc, the reason we delay
fput()is that we had some nasty issues for the generic fput case. It was called from interrupt context by the aio code, and just in general there's a lot of nasty cases that can cause the final fput to happen (so there are lockdep issues with the mmap locks because the last fput being from munmap etc).Maybe I forget some detail - it's been several years by now - but I think we could make the regular "
close()" and "exit()" cases just use the synchronous fput (it's called "__fput_sync()" and currently explicitly limited to just kernel threads).Al?
Quoted 8 lines
Because it feels all kinds of stupid to add things to the task-work queue just to then remove it almost immediately again. And
close_files()is also called from various contexts. but the whole "put the final 'files_struct' case is certainly not at all as special as the 'put the final file'.Linus
—
why not provide API like:fput()fput_nosync() ?
because synchronous version are reasonable and safe in most time,
let the user to select which version to use is more feasible, no matter if it is kthread or not.
Thanks
Al Viro
maintainerQuoted 6 lines · yalin wang
why not provide API like:
fput()fput_nosync()?because synchronous version are reasonable and safe in most time,
let the user to select which version to use is more feasible, no matter if it is kthread or not.
Synchronous version is *NOT* safe in a lot of situations, from "deep enough in kernel stack" to "now a function seven levels out in call chain happens to hold a mutex grabbed elsewhere inside a mutex taken by unexpected ->release() instance, causing a deadlock", etc.
It's not sync vs. async; we still guarantee execution before return from syscall. The only case when we really get async is kernel threads - there we do *not* return to userland at all, so we have to schedule it really asynchronous. Which is why we need an explicit sync version (for kernel threads only, not exported, don't use unless you really understand what you are doing and can explain why that particular case is safe, etc.)
Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Eric Dumazet
If this needs to be kept, maybe then add following, to make sure we flush the list at most every
BITS_PER_LONGfilesHmm.
I'm wondering if we should just make
close_files()(or maybe evenfilp_close()) use a synchronousfput().
Heh. I thought about the same change. So perhaps it is even the right thing to do. Still I am worried, because "it can't be that simple" ;)
And, with this change close_files() is called before exit_fs() and exit_task_namespaces(). This is fine (iiuc), but this means that the creative code in drivers/ can (wrongly) rely on this fact again. IIRC, the change which moved __fput() into task_work_exit() uncovered some interesting problems, like filp_open() called from fop->release().
Anyway, this is the question to Al, I guess.
Oleg.
Al Viro
maintainerQuoted 11 lines · Linus Torvalds
Hmm.
I'm wondering if we should just make
close_files()(or maybe evenfilp_close()) use a synchronousfput().Iirc, the reason we delay
fput()is that we had some nasty issues for the generic fput case. It was called from interrupt context by the aio code, and just in general there's a lot of nasty cases that can cause the final fput to happen (so there are lockdep issues with the mmap locks because the last fput being from munmap etc).
Quoted 6 lines
Maybe I forget some detail - it's been several years by now - but I think we could make the regular "
close()" and "exit()" cases just use the synchronous fput (it's called "__fput_sync()" and currently explicitly limited to just kernel threads).Al?
First of all, we'd better not count on e.g. delayed fput() *NOT* doing task_work_add() - we still need to check if any new work had been added. After all, final close() might very well have done a final mntput() on a lazy-unmounted filesystem, possibly leaving us with fs shutdown via task_work_add(). And if that sucker e.g. closes a socket, well, we are back to closing an opened struct file, with task_work_add() etc.
I'm a bit nervious about filp_close() (that sucker is exported and widely abused), but close_files()... sure, shouldn't be a problem. And yes, we can teach __close_fd() to do the same. I really don't understand what's the benefit, though - it's about the case when we are closing the last descriptor for given opened file, so I would be rather surprised if slower path taken on the way out to userland was not lost in noise...
Al Viro
maintainerQuoted 7 lines · Al Viro
First of all, we'd better not count on e.g. delayed
fput()*NOT* doingtask_work_add()- we still need to check if any new work had been added. After all, finalclose()might very well have done a finalmntput()on a lazy-unmounted filesystem, possibly leaving us with fs shutdown viatask_work_add(). And if that sucker e.g. closes a socket, well, we are back to closing an opened struct file, withtask_work_add()etc.
Quoted 6 lines
I'm a bit nervious about
filp_close()(that sucker is exported and widely abused), butclose_files()... sure, shouldn't be a problem. And yes, we can teach__close_fd()to do the same. I really don't understand what's the benefit, though - it's about the case when we are closing the last descriptor for given opened file, so I would be rather surprised if slower path taken on the way out to userland was not lost in noise...
OK, having found the beginning of the thread, I understand what is being attempted, but... why the hell bother with FIFO in the first place? AFAICS, task_work_add() uses in VFS (final fput() and final mntput() alike) do not care about the FIFO at all.
Sure, some out-of-tree mer^H^Hodule might rely on that. So what?
IMO, unless we have a good in-tree reason for insisting on FIFO, dropping it is the most obvious solution...
Quoted 10 lines · Al Viro
OK, having found the beginning of the thread, I understand what is being attempted, but... why the hell bother with FIFO in the first place? AFAICS,
task_work_add()uses in VFS (finalfput()and finalmntput()alike) do not care about the FIFO at all.Sure, some out-of-tree mer^H^Hodule might rely on that. So what?
IMO, unless we have a good in-tree reason for insisting on FIFO, dropping it is the most obvious solution...
I agree. We should just try that.
I'll apply Eric's patch from the beginning of this tree, and let's just see if anybody ever notices.
Removing code and possibly fixing a latency issue sounds like a win-win.
Linus
change filp_close() to use __fput_sync() ? (Was: [PATCH] task_work: remove fifo ordering guarantee)
In reply to Eric DumazetQuoted 16 lines · Eric Dumazet
Quoted 14 lines · Oleg Nesterov
Quoted 13 lines · Eric Dumazet
From: Eric Dumazet <[email protected]>
In commit
f341861fb0b("task_work: add a scheduling point intask_work_run()") I fixed a latency problem adding acond_resched()call.Later, commit
ac3d0da8f329added yet another loop to reverse a list, bringing back the latency spike :I've seen in some cases this loop taking 275 ms, if for example a process with 2,000,000 files is killed.
Quoted 8 lines
Quoted 3 lines
Quoted 1 line
We could add yet another
cond_resched()in the reverse loop,Can't we do this?
Well, I stated in the changelog we could. Obviously we can.
Adding 275 ms of pure overhead to perform this list reversal for files to be closed is quite unfortunate.
Well, if the first loop takes 275 ms, then probably the next one which actually does a lot of __fput's takes much, much more time, so perhaps these 275 ms are not very noticable. Ignoring the latency problem.
But of course, this is not good, I agree. Please see below.
Quoted 4 lines
Quoted 1 line
Fifo just looks more sane to me.
Well, files are closed in a random order. These are the main user of this stuff.
This is the most "heavy" user. But task_works is the generic API.
Quoted 4 lines
Now we also could question why we needed commit
4a9d4b024a3102fc083c925c242d98ac27b1c5f6("switch fput totask_work_add") since it seems quite an overhead at task exit with 10^6 of files to close.
How about the patch below? I didn't try to test it yet, but since filp_close() does ->flush() I think __fput_sync() should be safe here.
Al, what do you think?
Oleg.
fs/file_table.c +1 -4
@@ -292,11 +292,8 @@ void fput(struct file *file)*/ void __fput_sync (struct file *file) { -if (atomic_long_dec_and_test (&file->f_count)) { -struct task_struct *task = current; -BUG_ON (!(task->flags &PF_KTHREAD )); +if (atomic_long_dec_and_test (&file->f_count))__fput (file); - } }EXPORT_SYMBOL (fput);
fs/open.c +1 -1
@@ -1074,7 +1074,7 @@ int filp_close(struct file *filp, fl_owner_t id)dnotify_flush (filp, id);locks_remove_posix (filp, id); } -fput (filp); +__fput_sync (filp);return retval; }
Al Viro
maintainerQuoted 5 lines · Oleg Nesterov
Let's look
keyctl_session_to_parent(). It doestask_work_cancel()but only because we can not trust user-space. Otherwise we could remove it and just dotask_work_add(), but this needs fifo.Fifo just looks more sane to me.
Not if it costs us. As far as files closing is concerned, the order really doesn't matter. Ditto for final mntput() uses of that stuff.
What *does* matter is task_work_add() issued by callback not getting lost.
IMO the obvious solution is to lose the reordering...
[PATCH?] fput: don't abuse task_work_add() too much
Quoted 10 lines · Al Viro
Quoted 5 lines · Oleg Nesterov
Let's look
keyctl_session_to_parent(). It doestask_work_cancel()but only because we can not trust user-space. Otherwise we could remove it and just dotask_work_add(), but this needs fifo.Fifo just looks more sane to me.
Not if it costs us.
OK, Eric reports this trivial lockless loop takes 275ms. Apparently the list of ____fput() works is huge. Now, how much does it cost to _create_ this huge list using task_work_add() which does cmpxchg() ? I guess a bit more. This is what should be fixed if we think this hurts performance-wise.
And again, ignoring the latency problem due to the lack of cond_resched, I am wondering if these 275ms are actually noticable compared to the time the next loop needs to call all these ____fput's.
Quoted 2 lines
As far as files closing is concerned, the order
really doesn't matter. Ditto for finalmntput()uses of that stuff.
Sure, fput/mntput do not care about the ordering. And more, they do not even really need task_work_add(). We can just remove it from fput() and everything will work fine. Correctness-wise, I mean.
And yes, unfortunately we do not have in-kernel users which already rely on fifo.
But task_work_add() is the generic API, loosing the ordering makes it less useful or at least less convenient.
Just for (yes sure, artificial) example. Suppose we want to implement sys_change_process_flags(int pid, uint set, uint clr). Only current can change its ->flags, so we can use task_work_add() to do this. But obviously only if it is fifo.
fput() differs because it does not care which process actually does __fput(). And thus imo we should not count this user if we need to decide do we need fifo or not.
Quoted 1 line
IMO the obvious solution is to lose the reordering...
Oh, I disagree. But I guess I can't convince you/Eric/Linus, so I have to shut up.
Damn. But I can't relax ;) Al, Linus, could you comment the patch below?
Not for inclusion, lacks the changelog/testing, fput() can be simplified. But as you can see it is simple. With this patch task_work_add(____fput) will be called only once by (say) do_exit() path. ->fput_list does not need any serialization / atomic ops / etc. Probably we also need to move cond_resched() from task_work_run() to ____fput() after this patch.
Again, it is not that I think this actually makes sense, but since you dislike these 275ms...
What do you think?
Oleg.
---
fs/file_table.c +18 -2
@@ -241,7 +241,13 @@ static void delayed_fput(struct work_struct *unused)static void ____fput (struct callback_head *work) { - __fput(container_of(work, struct file, f_u.fu_rcuhead)); +struct task_struct *task = current; +do { +struct file *file = task->fput_list; + task->fput_list = file->f_u.fu_next; +__fput (file); + + }while (task->fput_list); }/*
@@ -267,9 +273,19 @@ void fput(struct file *file)struct task_struct *task = current;if (likely (!in_interrupt () && !(task->flags &PF_KTHREAD ))) { +if (task->fput_list) { +/* task_work_add() below was already called */ + file->f_u.fu_next = task->fput_list; + task->fput_list = file; +return ; + } +init_task_work (&file->f_u.fu_rcuhead, ____fput); -if (!task_work_add (task, &file->f_u.fu_rcuhead, true)) +if (!task_work_add (task, &file->f_u.fu_rcuhead, true)) { + file->f_u.fu_next =NULL ; + task->fput_list = file;return ; + }/* * After this task has run exit_task_work(), * task_work_add() will fail. Fall through to delayed
include/linux/fs.h +1 -0
@@ -830,6 +830,7 @@ struct file {union {struct llist_node fu_llist;struct rcu_head fu_rcuhead; +struct file *fu_next; } f_u;struct path f_path;struct inode *f_inode;/* cached value */
include/linux/sched.h +1 -0
@@ -1477,6 +1477,7 @@ struct task_struct {struct fs_struct *fs;/* open file information */ struct files_struct *files; +struct file *fput_list;/* namespaces */ struct nsproxy *nsproxy;/* signal handlers */
kernel/fork.c +1 -0
@@ -1007,6 +1007,7 @@ static int copy_files(unsigned long clone_flags, struct task_struct *tsk)struct files_struct *oldf, *newf;int error =0 ; + tsk->fput_list =NULL ;/* * A background process may not have any files ... */
PATCH v2 1/1 fput: don't abuse task_work_add() too much
Quoted 13 lines · Oleg Nesterov
Oh, I disagree. But I guess I can't convince you/Eric/Linus, so I have to shut up.
Damn. But I can't relax ;) Al, Linus, could you comment the patch below?
Not for inclusion, lacks the changelog/testing,
fput()can be simplified. But as you can see it is simple. With this patchtask_work_add(____fput)will be called only once by (say)do_exit()path. ->fput_list does not need any serialization / atomic ops / etc. Probably we also need to movecond_resched()fromtask_work_run()to____fput()after this patch.
Quoted 4 lines
Again, it is not that I think this actually makes sense, but since you dislike these 275ms...
What do you think?
Yes, task_struct->fput_list is ugly. We can avoid it, but then we need another ->next pointer in struct file. Perhaps we can reuse ->f_version?
This way the change looks really simple and not too bad to me. Although I am not sure you will agree.
Oleg.
---
fs/file_table.c +22 -2
@@ -241,7 +241,15 @@ static void delayed_fput(struct work_struct *unused)static void ____fput (struct callback_head *work) { - __fput(container_of(work, struct file, f_u.fu_rcuhead)); + struct file *file = container_of(work, struct file, f_u.fu_rcuhead); +struct file *next; + +do { + next = file->f_next_put; +__fput (file); + file = next; + + }while (file); }/*
@@ -267,9 +275,21 @@ void fput(struct file *file)struct task_struct *task = current;if (likely (!in_interrupt () && !(task->flags &PF_KTHREAD ))) { +struct callback_head *work =READ_ONCE (task->task_works); +struct file *prev; + +if (work && work->func == ____fput) { + prev = container_of(work, struct file, f_u.fu_rcuhead); + file->f_next_put = prev->f_next_put; + prev->f_next_put = file; +return ; + } +init_task_work (&file->f_u.fu_rcuhead, ____fput); -if (!task_work_add (task, &file->f_u.fu_rcuhead, true)) +if (!task_work_add (task, &file->f_u.fu_rcuhead, true)) { + file->f_next_put =NULL ;return ; + }/* * After this task has run exit_task_work(), * task_work_add() will fail. Fall through to delayed
include/linux/fs.h +4 -1
@@ -849,7 +849,10 @@ struct file {const struct cred *f_cred;struct file_ra_state f_ra; -u64 f_version; +union { +u64 f_version; +struct file *f_next_put; + };#ifdef CONFIG_SECURITY void *f_security;#endif