[PATCH v3 tip/core/rcu 0/9

kernel/rcu/update.c void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp)) · line 431

Quoted 10 lines · Paul E. McKenney

kernel/rcu/update.c +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Quoted 14 lines · Oleg Nesterov

kernel/rcu/update.c void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp)) · line 431

Quoted 10 lines · Paul E. McKenney

kernel/rcu/update.c +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

Quoted 2 lines

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Excellent point, indeed it can!

And if I do it right, it will make CONFIG_TASKS_RCU=y safe for kernel tinification. ;-)

Quoted 18 lines · Paul E. McKenney

Quoted 16 lines · Oleg Nesterov

kernel/rcu/update.c void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp)) · line 431

Quoted 10 lines · Paul E. McKenney

kernel/rcu/update.c +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Quoted 4 lines

Excellent point, indeed it can!

And if I do it right, it will make CONFIG_TASKS_RCU=y safe for kernel tinification. ;-)

Unless, that is, we need to wait for trampolines in the idle loop...

Sounds like a question for Steven. ;-)

Quoted 25 lines · Paul E. McKenney

Quoted 22 lines · Paul E. McKenney

Quoted 14 lines · Oleg Nesterov

kernel/rcu/update.c void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp)) · line 431

Quoted 10 lines · Paul E. McKenney

kernel/rcu/update.c +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

Quoted 2 lines

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Excellent point, indeed it can!

And if I do it right, it will make CONFIG_TASKS_RCU=y safe for kernel tinification. ;-)

Quoted 3 lines

Unless, that is, we need to wait for trampolines in the idle loop...

Sounds like a question for Steven. ;-)

Sure, but the full blown synchronize_rcu_tasks() can't handle the idle threads anyway. An idle thread can not be deactivated and for_each_process() can't see it anyway.

Quoted 28 lines · Oleg Nesterov

Quoted 27 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 14 lines · Oleg Nesterov

kernel/rcu/update.c void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp)) · line 431

Quoted 10 lines · Paul E. McKenney

kernel/rcu/update.c +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

Quoted 7 lines

Quoted 2 lines

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Excellent point, indeed it can!

And if I do it right, it will make CONFIG_TASKS_RCU=y safe for kernel tinification. ;-)

Unless, that is, we need to wait for trampolines in the idle loop...

Quoted 5 lines

Quoted 1 line

Sounds like a question for Steven. ;-)

Sure, but the full blown synchronize_rcu_tasks() can't handle the idle threads anyway. An idle thread can not be deactivated and for_each_process() can't see it anyway.

Indeed, if idle threads need to be tracked, their tracking will need to be at least partially special-cased.

Quoted 35 lines · On Sat, 2 Aug 2014 15:58:57 -0700 "Paul E. McKenney"…

Quoted 33 lines · Oleg Nesterov

Quoted 20 lines · Paul E. McKenney

Quoted 18 lines · Paul E. McKenney

Quoted 16 lines · Oleg Nesterov

Review

Quoted 10 lines · Paul E. McKenney

(quoted diff) +9 -0

+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}

Btw, what about CONFIG_PREEMPT=n ?

I mean, can't synchronize_rcu_tasks() be synchronize_sched() in this case?

Quoted 8 lines

Quoted 4 lines

Excellent point, indeed it can!

And if I do it right, it will make CONFIG_TASKS_RCU=y safe for kernel tinification. ;-)

Unless, that is, we need to wait for trampolines in the idle loop...

Sounds like a question for Steven. ;-)

Sure, but the full blown synchronize_rcu_tasks() can't handle the idle threads anyway. An idle thread can not be deactivated and for_each_process() can't see it anyway.

Quoted 2 lines

Indeed, if idle threads need to be tracked, their tracking will need to be at least partially special-cased.

Yeah, idle threads can be affected by the trampolines. That is, we can still hook a trampoline to some function in the idle loop.

But we should be able to make the hardware call that puts the CPU to sleep a quiescent state too. May need to be arch dependent. :-/

Quoted 5 lines

Yeah, idle threads can be affected by the trampolines. That is, we can still hook a trampoline to some function in the idle loop.

But we should be able to make the hardware call that puts the CPU to sleep a quiescent state too. May need to be arch dependent. :-/

OK, my plan for this eventuality is to do the following:

1. Ignore the ->on_rq field, as idle tasks are always on a runqueue.

2. Watch the context-switch counter.

3. Ignore dyntick-idle state for idle tasks.

4. If there is no quiescent state from a given idle task after
a few seconds, schedule rcu_tasks_kthread() on top of the offending CPU.

Your idea is an interesting one, but does require another set of dyntick-idle-like functions and counters. Or moving the current rcu_idle_enter() and rcu_idle_exit() calls deeper into the idle loop.

Not sure which is a better approach. Alternatively, we could just rely on #4 above, on the grounds that battery life should not be too badly degraded by the occasional RCU-tasks interference.

Note that this is a different situation than NO_HZ_FULL in realtime environments, where the worst case causes trouble even if it happens very infrequently.

Quoted 26 lines · Paul E. McKenney

Quoted 5 lines

Yeah, idle threads can be affected by the trampolines. That is, we can still hook a trampoline to some function in the idle loop.

But we should be able to make the hardware call that puts the CPU to sleep a quiescent state too. May need to be arch dependent. :-/

OK, my plan for this eventuality is to do the following:

1. Ignore the ->on_rq field, as idle tasks are always on a runqueue.

2. Watch the context-switch counter.

3. Ignore dyntick-idle state for idle tasks.

4. If there is no quiescent state from a given idle task after
a few seconds, schedule rcu_tasks_kthread() on top of the offending CPU.

Your idea is an interesting one, but does require another set of dyntick-idle-like functions and counters. Or moving the current rcu_idle_enter() and rcu_idle_exit() calls deeper into the idle loop.

Not sure which is a better approach. Alternatively, we could just rely on #4 above, on the grounds that battery life should not be too badly degraded by the occasional RCU-tasks interference.

Quoted 3 lines

Note that this is a different situation than NO_HZ_FULL in realtime environments, where the worst case causes trouble even if it happens very infrequently.

Or you could shoot all CPUs with resched_cpu() which would have them cycle through schedule() even if there's nothing but the idle thread to run. That guarantees they'll go to sleep again in a !trampoline.

But I still very much hate the polling stuff...

Can't we abuse the preempt notifiers? Say we make it possible to install preemption notifiers cross-task, then the task-rcu can install a preempt-out notifier which completes the rcu-task wait.

After all, since we tagged it it was !running, and being scheduled out means it ran (once) and therefore isn't on a trampoline anymore.

And the tick, which checks to see if the task got to userspace can do the same, remove the notifier and then complete.

Quoted 3 lines

Or you could shoot all CPUs with resched_cpu() which would have them cycle through schedule() even if there's nothing but the idle thread to run. That guarantees they'll go to sleep again in a !trampoline.

Good point, that would be an easier way to handle the idle threads than messing with rcu_tasks_kthread()'s affinity. Thank you!

Quoted 6 lines

But I still very much hate the polling stuff...

Can't we abuse the preempt notifiers? Say we make it possible to install preemption notifiers cross-task, then the task-rcu can install a preempt-out notifier which completes the rcu-task wait.

Quoted 2 lines

After all, since we tagged it it was !running, and being scheduled out means it ran (once) and therefore isn't on a trampoline anymore.

Maybe I am being overly paranoid, but couldn't the task be preempted in a trampoline, be resumed, execute one instruction (still in the tramopoline) and be preempted again?

Quoted 2 lines

And the tick, which checks to see if the task got to userspace can do the same, remove the notifier and then complete.

My main concern with this sort of approach is that I have to deal with full-up concurrency (200 CPUs all complete tasks concurrently, for example), which would make for a much larger and more complex patch. Now, I do admit that it is quite possible that I will end up there anyway, for example, if more people start using RCU-tasks, but I see no need to hurry this process. ;-)

Quoted 4 lines · Paul E. McKenney

Quoted 3 lines

Or you could shoot all CPUs with resched_cpu() which would have them cycle through schedule() even if there's nothing but the idle thread to run. That guarantees they'll go to sleep again in a !trampoline.

Quoted 2 lines

Good point, that would be an easier way to handle the idle threads than messing with rcu_tasks_kthread()'s affinity. Thank you!

One issue though, resched_cpu() doesn't wait for that to complete. We'd need something that would guarantee the remote CPU has actually completed execution.

Quoted 1 line

Quoted 1 line

But I still very much hate the polling stuff...

Quoted 7 lines

Quoted 6 lines

Can't we abuse the preempt notifiers? Say we make it possible to install preemption notifiers cross-task, then the task-rcu can install a preempt-out notifier which completes the rcu-task wait.

After all, since we tagged it it was !running, and being scheduled out means it ran (once) and therefore isn't on a trampoline anymore.

Quoted 3 lines

Maybe I am being overly paranoid, but couldn't the task be preempted in a trampoline, be resumed, execute one instruction (still in the tramopoline) and be preempted again?

Ah, what I failed to state was we should check the sleep condition. So 'voluntary' schedule() calls.

Of course if we'd made something specific to the trampoline thing and not 'task'-rcu we could simply check if the IP was inside a trampoline or not.

Quoted 9 lines

Quoted 2 lines

And the tick, which checks to see if the task got to userspace can do the same, remove the notifier and then complete.

My main concern with this sort of approach is that I have to deal with full-up concurrency (200 CPUs all complete tasks concurrently, for example), which would make for a much larger and more complex patch. Now, I do admit that it is quite possible that I will end up there anyway, for example, if more people start using RCU-tasks, but I see no need to hurry this process. ;-)

You mean cacheline contention on the struct completion? I'd first make it simple and only fix it if/when it becomes a problem.

200 CPUs contending on a single cacheline _once_ is annoying, but probably still lots cheaper than polling state for at least that many tasks.

Quoted 1 line

Quoted 1 line

Quoted 1 line

But I still very much hate the polling stuff...

The nice thing about the polling approach is minimal overhead in the common case where RCU-tasks is not in use.

Quoted 4 lines · Paul E. McKenney

Quoted 1 line

Quoted 1 line

Quoted 1 line

But I still very much hate the polling stuff...

The nice thing about the polling approach is minimal overhead in the common case where RCU-tasks is not in use.

No, quite the reverse, there is overhead when its not in use, as opposed to no overhead at all.

I'm still not convinced we need this 'generic' rcu-task stuff and create yet another kthread with polling semantics, we want to let the system idle out when there's nothing to do, not keep waking it up.

So do we really need the call_rcu_task() thing and why isn't something like synchronize_tasks() good enough?

So the thing is, the one proposed user is very rare (*) and for that you're adding overhead outside of that user (a separate kthread) and your adding overhead when its not used.

* I'm assuming that, since tracing is 'rare' and this is some tracing thing.

Quoted 8 lines · Peter Zijlstra

Quoted 4 lines · Paul E. McKenney

Quoted 1 line

Quoted 1 line

Quoted 1 line

But I still very much hate the polling stuff...

The nice thing about the polling approach is minimal overhead in the common case where RCU-tasks is not in use.

No, quite the reverse, there is overhead when its not in use, as opposed to no overhead at all.

Say what???

Quoted 3 lines

I'm still not convinced we need this 'generic' rcu-task stuff and create yet another kthread with polling semantics, we want to let the system idle out when there's nothing to do, not keep waking it up.

Which is exactly what happens. The kthread is created only at first use, so if no one uses RCU-tasks, then no kthread is created, see
https://lkml.org/lkml/2014/8/4/630. Even if a kthread is created, if there is no more work for it to do, it sleeps indefinitely. See for example https://lkml.org/lkml/2014/8/4/629.

Quoted 2 lines

So do we really need the call_rcu_task() thing and why isn't something like synchronize_tasks() good enough?

Sounds like a question for Steven.

Quoted 3 lines

So the thing is, the one proposed user is very rare (*) and for that you're adding overhead outside of that user (a separate kthread) and your adding overhead when its not used.

If that really was the case, that would be bad. However, in the latest versions, that is no longer the case.

Quoted 2 lines

* I'm assuming that, since tracing is 'rare' and this is some tracing thing.

Another good point for Steven.

Quoted 12 lines

Quoted 2 lines

So do we really need the call_rcu_task() thing and why isn't something like synchronize_tasks() good enough?

Sounds like a question for Steven.

Quoted 3 lines

So the thing is, the one proposed user is very rare (*) and for that you're adding overhead outside of that user (a separate kthread) and your adding overhead when its not used.

If that really was the case, that would be bad. However, in the latest versions, that is no longer the case.

Quoted 4 lines

Quoted 2 lines

* I'm assuming that, since tracing is 'rare' and this is some tracing thing.

Another good point for Steven.

Yes.. and he's back now, so please :-)

Right, Steve (and Paul) please explain _why_ this is an 'RCU' at all? _Why_ do we have call_rcu_task(), and why is it entwined in the 'normal' RCU stuff? We've got SRCU -- which btw started out simple, without call_srcu() -- and that lives entirely independent. And SRCU is far more an actual RCU than this thing is, its got read side primitives and everything.

Also, I cannot think of any other use besides trampolines for this thing, but that might be my limited imagination.

Quoted 7 lines · Peter Zijlstra

Right, Steve (and Paul) please explain _why_ this is an 'RCU' at all? _Why_ do we have call_rcu_task(), and why is it entwined in the 'normal' RCU stuff? We've got SRCU -- which btw started out simple, without call_srcu() -- and that lives entirely independent. And SRCU is far more an actual RCU than this thing is, its got read side primitives and everything.

Quoted 2 lines

Also, I cannot think of any other use besides trampolines for this thing, but that might be my limited imagination.

Also, trampolines can end up in the return frames, right? So how can you be sure when to wipe them? Passing through schedule() isn't enough for that.

Userspace is, but kernel threads typically don't ever end up there.

Only voluntary calls to schedule() will be a quiescent state. Preempt doesn't count. And no, function callbacks to not call schedule(), function callbacks should be treated even stricter than interrupt handlers. They should never call schedule() directly or even take any locks. Heck, they should be stricter than NMIs for that matter.

Hence, once something calls schedule() directly, we know that it is not on a trampoline, nor is it going to return to one.

Quoted 8 lines · On Thu, 7 Aug 2014 15:49:07 -0400 Steven Rostedt <[email protected]> wrote:

Only voluntary calls to schedule() will be a quiescent state. Preempt doesn't count. And no, function callbacks to not call schedule(), function callbacks should be treated even stricter than interrupt handlers. They should never call schedule() directly or even take any locks. Heck, they should be stricter than NMIs for that matter.

Hence, once something calls schedule() directly, we know that it is not on a trampoline, nor is it going to return to one.

I should also be a bit clearer here. It's not just function callbacks, but anything that adds a trampoline that can be called from any context (like for kprobes). The point is, these trampolines that can execute anywhere (including in NMIs), must have strict use cases. These are not a notifier or other generic operation that normal RCU is fine for. These are for really specific cases that require the call_rcu_task() to free.

call_rcu_task() should seldom be used. The only cases really are for kprobes and function tracing, and perhaps other dynamic callers.

OK, you've got to start over and start at the beginning, because I'm really not understanding this..

What is a 'trampoline' and what are you going to use them for.

Quoted 4 lines · On Thu, 7 Aug 2014 22:08:13 +0200 Peter Zijlstra <[email protected]> wrote:

OK, you've got to start over and start at the beginning, because I'm really not understanding this..

What is a 'trampoline' and what are you going to use them for.

Great question! :-)

The trampoline is some code that is used to jump to and then jump someplace else. Currently, we use this for kprobes and ftrace. For ftrace we have the ftrace_caller trampoline, which is static. When booting, most functions in the kernel call the mcount code which simply returns without doing anything. This too is a "trampoline". At boot, we convert these calls to nops (as you already know). When we enable callbacks from functions, we convert those calls to call "ftrace_caller" which is a small assembly trampoline that will call some function that registered with ftrace.

Now why do we need the call_rcu_task() routine?

Right now, if you register multiple callbacks to ftrace, even if they are not tracing the same routine, ftrace has to change ftrace_caller to call another trampoline (in C), that does a loop of all ops registered with ftrace, and compares the function to the ops hash tables to see if the ops function should be called for that function.

What we want to do is to create a dynamic trampoline that is a copy of the ftrace_caller code, but instead of calling this list trampoline, it calls the ops function directly. This way, each ops registered with ftrace can have its own custom trampoline that when called will only call the ops function and not have to iterate over a list. This only happens if the function being traced only has this one ops registered. For functions with multiple ops attached to it, we need to call the list anyway. But for the majority of the cases, this is not the case.

The one caveat for this is, how do we free this custom trampoline when the ops is done with it? Especially for users of ftrace that dynamically create their own ops (like perf, and ftrace instances).

We need to find a way to free it, but unfortunately, there's no way to know when it is safe to free it. There's no way to disable preemption or have some other notifier to let us know if a task has jumped to this trampoline and has been preempted (sleeping). The only safe way to know that no task is on the trampoline is to remove the calls to it, synchronize the CPUS (so the trampolines are not even in the caches), and then wait for all tasks to go through some quiescent state. This state happens to be either not running, in userspace, or when it voluntarily calls schedule. Because nothing that uses this trampoline should do that, and if the task voluntarily calls schedule, we know it's not on the trampoline.

Make sense?

Quoted 53 lines · Steven Rostedt

Quoted 4 lines · On Thu, 7 Aug 2014 22:08:13 +0200 Peter Zijlstra <[email protected]> wrote:

OK, you've got to start over and start at the beginning, because I'm really not understanding this..

What is a 'trampoline' and what are you going to use them for.

Great question! :-)

The trampoline is some code that is used to jump to and then jump someplace else. Currently, we use this for kprobes and ftrace. For ftrace we have the ftrace_caller trampoline, which is static. When booting, most functions in the kernel call the mcount code which simply returns without doing anything. This too is a "trampoline". At boot, we convert these calls to nops (as you already know). When we enable callbacks from functions, we convert those calls to call "ftrace_caller" which is a small assembly trampoline that will call some function that registered with ftrace.

Now why do we need the call_rcu_task() routine?

Right now, if you register multiple callbacks to ftrace, even if they are not tracing the same routine, ftrace has to change ftrace_caller to call another trampoline (in C), that does a loop of all ops registered with ftrace, and compares the function to the ops hash tables to see if the ops function should be called for that function.

What we want to do is to create a dynamic trampoline that is a copy of the ftrace_caller code, but instead of calling this list trampoline, it calls the ops function directly. This way, each ops registered with ftrace can have its own custom trampoline that when called will only call the ops function and not have to iterate over a list. This only happens if the function being traced only has this one ops registered. For functions with multiple ops attached to it, we need to call the list anyway. But for the majority of the cases, this is not the case.

The one caveat for this is, how do we free this custom trampoline when the ops is done with it? Especially for users of ftrace that dynamically create their own ops (like perf, and ftrace instances).

We need to find a way to free it, but unfortunately, there's no way to know when it is safe to free it. There's no way to disable preemption or have some other notifier to let us know if a task has jumped to this trampoline and has been preempted (sleeping). The only safe way to know that no task is on the trampoline is to remove the calls to it, synchronize the CPUS (so the trampolines are not even in the caches), and then wait for all tasks to go through some quiescent state. This state happens to be either not running, in userspace, or when it voluntarily calls schedule. Because nothing that uses this trampoline should do that, and if the task voluntarily calls schedule, we know it's not on the trampoline.

Quoted 1 line

Make sense?

Ok, so they're purely used in the function prologue/epilogue callchain.

And you don't want to use synchronize_tasks() because registering a trace functions is atomic ?

But why would you use dynamic memory allocation for these trampolines at all? Why not use the one default trampoline for this?

Suppose that thing looks like:

ftrace_mcount_handler()

{
	for_each_hlist_rcu(entry,..)
		entry->func();
}

so why not make it look like:

ftrace_mcount_handler()

{
	asm_volatile_goto("jmp %l[label]" ::: &do_list);
	return;

do_list:

	for_each_hlist_rcu(entry,...)
		entry->func();
}

Then, for:

	no entries -> NOP, 
	one entry -> "CALL $func", 
	more entries -> "JMP &do_list.

No need for extra allocations and fancy means of getting rid of them, and only a few bytes extra wrt the existing function.

Quoted 56 lines · On Fri, 8 Aug 2014 08:40:20 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 54 lines · Steven Rostedt

Quoted 4 lines · On Thu, 7 Aug 2014 22:08:13 +0200 Peter Zijlstra <[email protected]> wrote:

OK, you've got to start over and start at the beginning, because I'm really not understanding this..

What is a 'trampoline' and what are you going to use them for.

Great question! :-)

The trampoline is some code that is used to jump to and then jump someplace else. Currently, we use this for kprobes and ftrace. For ftrace we have the ftrace_caller trampoline, which is static. When booting, most functions in the kernel call the mcount code which simply returns without doing anything. This too is a "trampoline". At boot, we convert these calls to nops (as you already know). When we enable callbacks from functions, we convert those calls to call "ftrace_caller" which is a small assembly trampoline that will call some function that registered with ftrace.

Now why do we need the call_rcu_task() routine?

Right now, if you register multiple callbacks to ftrace, even if they are not tracing the same routine, ftrace has to change ftrace_caller to call another trampoline (in C), that does a loop of all ops registered with ftrace, and compares the function to the ops hash tables to see if the ops function should be called for that function.

What we want to do is to create a dynamic trampoline that is a copy of the ftrace_caller code, but instead of calling this list trampoline, it calls the ops function directly. This way, each ops registered with ftrace can have its own custom trampoline that when called will only call the ops function and not have to iterate over a list. This only happens if the function being traced only has this one ops registered. For functions with multiple ops attached to it, we need to call the list anyway. But for the majority of the cases, this is not the case.

The one caveat for this is, how do we free this custom trampoline when the ops is done with it? Especially for users of ftrace that dynamically create their own ops (like perf, and ftrace instances).

We need to find a way to free it, but unfortunately, there's no way to know when it is safe to free it. There's no way to disable preemption or have some other notifier to let us know if a task has jumped to this trampoline and has been preempted (sleeping). The only safe way to know that no task is on the trampoline is to remove the calls to it, synchronize the CPUS (so the trampolines are not even in the caches), and then wait for all tasks to go through some quiescent state. This state happens to be either not running, in userspace, or when it voluntarily calls schedule. Because nothing that uses this trampoline should do that, and if the task voluntarily calls schedule, we know it's not on the trampoline.

Make sense?

Quoted 1 line

Ok, so they're purely used in the function prologue/epilogue callchain.

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

Which reminds me. On !CONFIG_PREEMPT, call_rcu_task() should be equivalent to call_rcu_sched().

Quoted 2 lines

And you don't want to use synchronize_tasks() because registering a trace functions is atomic ?

No. Has nothing to do with registering the trace function. The issue is that we have no idea when a task happens to be on a trampoline after it is registered. For example:

ops adds a callback to sys_read:

sys_read() {
call trampoline ->
set up regs for function call.
<interrupt>
preempt_schedule();

[ new task runs for long time ]

While this new task is running, we remove the trampoline and want to free it. Say this new task keeps the other task from running for minutes! We call synchronize_sched() or any other rcu call, and all grace periods finish and we free the trampoline. The sys_read() no longer calls our trampoline. Doesn't matter, because that task is still on it. Now we schedule that task back. It's on a trampoline that has just been freed! BOOM. It's executing code that no longer exits.

Quoted 3 lines

But why would you use dynamic memory allocation for these trampolines at all? Why not use the one default trampoline for this?

That's what ftrace does today.

Quoted 17 lines

Suppose that thing looks like:

ftrace_mcount_handler()

{
	for_each_hlist_rcu(entry,..)
		entry->func();
}

so why not make it look like:

ftrace_mcount_handler()

{
	asm_volatile_goto("jmp %l[label]" ::: &do_list);
	return;

do_list:

Quoted 8 lines

	for_each_hlist_rcu(entry,...)
		entry->func();
}

Then, for:

	no entries -> NOP, 
	one entry -> "CALL $func", 
	more entries -> "JMP &do_list.

Except that we don't use jump labels for this, but just update the trampoline directly (we've been doing this before jump labels ever existed, and the trampoline is all in assembly anyway).

Quoted 3 lines

No need for extra allocations and fancy means of getting rid of them, and only a few bytes extra wrt the existing function.

This doesn't address the issue we want to solve.

Say we have 1000 functions we want to trace with 1000 different callbacks. Each of theses functions has one call back. How do you solve that with your solution? Today, we do the list for every function. That is, for each of these 1000 functions, we run through 1000 ops looking for the ops that registered for this function. Not very efficient is it?

What we want to do today, is to create a dynamic trampoline for each of theses 1000 functions. Each function will call a separate trampoline that will only call the function that was registered to it. That way, we can have 1000 different ops registered to 1000 different functions and still have the same performance.

-- Steve

Quoted 64 lines · Steven Rostedt

Quoted 54 lines · On Fri, 8 Aug 2014 08:40:20 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 53 lines · Steven Rostedt

Quoted 4 lines · On Thu, 7 Aug 2014 22:08:13 +0200 Peter Zijlstra <[email protected]> wrote:

OK, you've got to start over and start at the beginning, because I'm really not understanding this..

What is a 'trampoline' and what are you going to use them for.

Great question! :-)

The trampoline is some code that is used to jump to and then jump someplace else. Currently, we use this for kprobes and ftrace. For ftrace we have the ftrace_caller trampoline, which is static. When booting, most functions in the kernel call the mcount code which simply returns without doing anything. This too is a "trampoline". At boot, we convert these calls to nops (as you already know). When we enable callbacks from functions, we convert those calls to call "ftrace_caller" which is a small assembly trampoline that will call some function that registered with ftrace.

Now why do we need the call_rcu_task() routine?

Right now, if you register multiple callbacks to ftrace, even if they are not tracing the same routine, ftrace has to change ftrace_caller to call another trampoline (in C), that does a loop of all ops registered with ftrace, and compares the function to the ops hash tables to see if the ops function should be called for that function.

What we want to do is to create a dynamic trampoline that is a copy of the ftrace_caller code, but instead of calling this list trampoline, it calls the ops function directly. This way, each ops registered with ftrace can have its own custom trampoline that when called will only call the ops function and not have to iterate over a list. This only happens if the function being traced only has this one ops registered. For functions with multiple ops attached to it, we need to call the list anyway. But for the majority of the cases, this is not the case.

The one caveat for this is, how do we free this custom trampoline when the ops is done with it? Especially for users of ftrace that dynamically create their own ops (like perf, and ftrace instances).

We need to find a way to free it, but unfortunately, there's no way to know when it is safe to free it. There's no way to disable preemption or have some other notifier to let us know if a task has jumped to this trampoline and has been preempted (sleeping). The only safe way to know that no task is on the trampoline is to remove the calls to it, synchronize the CPUS (so the trampolines are not even in the caches), and then wait for all tasks to go through some quiescent state. This state happens to be either not running, in userspace, or when it voluntarily calls schedule. Because nothing that uses this trampoline should do that, and if the task voluntarily calls schedule, we know it's not on the trampoline.

Quoted 3 lines

Quoted 1 line

Make sense?

Ok, so they're purely used in the function prologue/epilogue callchain.

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

Quoted 2 lines

Which reminds me. On !CONFIG_PREEMPT, call_rcu_task() should be equivalent to call_rcu_sched().

Almost. One difference is that call_rcu_sched() won't wait for idle-task execution. So presumably you are currently prohibited from putting kprobes in idle tasks.

Oleg slipped this one past me, and for more than a full hour,
(https://lkml.org/lkml/2014/8/2/18), but this time I remembered. ;-)

Thanx, Paul

Quoted 1 line

Ok, so they're purely used in the function prologue/epilogue callchain.

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

Which reminds me. On !CONFIG_PREEMPT, call_rcu_task() should be equivalent to call_rcu_sched().

Quoted 2 lines

And you don't want to use synchronize_tasks() because registering a trace functions is atomic ?

No. Has nothing to do with registering the trace function. The issue is that we have no idea when a task happens to be on a trampoline after it is registered. For example:

ops adds a callback to sys_read:

sys_read() {
call trampoline ->
set up regs for function call.
<interrupt>
preempt_schedule();

[ new task runs for long time ]

While this new task is running, we remove the trampoline and want to free it. Say this new task keeps the other task from running for minutes! We call synchronize_sched() or any other rcu call, and all grace periods finish and we free the trampoline. The sys_read() no longer calls our trampoline. Doesn't matter, because that task is still on it. Now we schedule that task back. It's on a trampoline that has just been freed! BOOM. It's executing code that no longer exits.

Quoted 2 lines

No need for extra allocations and fancy means of getting rid of them, and only a few bytes extra wrt the existing function.

This doesn't address the issue we want to solve.

Say we have 1000 functions we want to trace with 1000 different callbacks. Each of theses functions has one call back. How do you solve that with your solution? Today, we do the list for every function. That is, for each of these 1000 functions, we run through 1000 ops looking for the ops that registered for this function. Not very efficient is it?

What we want to do today, is to create a dynamic trampoline for each of theses 1000 functions. Each function will call a separate trampoline that will only call the function that was registered to it. That way, we can have 1000 different ops registered to 1000 different functions and still have the same performance.

Quoted 4 lines · Steven Rostedt

Quoted 1 line

Ok, so they're purely used in the function prologue/epilogue callchain.

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

And what is there to make sure the kprobe itself doesn't do 'funny'?

Quoted 3 lines

Which reminds me. On !CONFIG_PREEMPT, call_rcu_task() should be equivalent to call_rcu_sched().

Sure, as long as you make absolutely sure none of that code ends up calling cond_resched()/might_sleep() etc. Which I think you already said was true, so no worries there.

Quoted 19 lines

Quoted 3 lines

And you don't want to use synchronize_tasks() because registering a trace functions is atomic ?

No. Has nothing to do with registering the trace function. The issue is that we have no idea when a task happens to be on a trampoline after it is registered. For example:

ops adds a callback to sys_read:

sys_read() {
call trampoline ->
set up regs for function call.
<interrupt>
preempt_schedule();

[ new task runs for long time ]

Quoted 7 lines

While this new task is running, we remove the trampoline and want to free it. Say this new task keeps the other task from running for minutes! We call synchronize_sched() or any other rcu call, and all grace periods finish and we free the trampoline. The sys_read() no longer calls our trampoline. Doesn't matter, because that task is still on it. Now we schedule that task back. It's on a trampoline that has just been freed! BOOM. It's executing code that no longer exits.

Sure, I get that part. What I was getting as is _WHY_ you need call_rcu_task(), why isn't synchronize_tasks() good enough?

Quoted 6 lines

Quoted 3 lines

No need for extra allocations and fancy means of getting rid of them, and only a few bytes extra wrt the existing function.

This doesn't address the issue we want to solve.

Quoted 5 lines

Say we have 1000 functions we want to trace with 1000 different callbacks. Each of theses functions has one call back. How do you solve that with your solution? Today, we do the list for every function. That is, for each of these 1000 functions, we run through 1000 ops looking for the ops that registered for this function. Not very efficient is it?

Ah, but you didn't say that, didn't you :-)

Quoted 6 lines

What we want to do today, is to create a dynamic trampoline for each of theses 1000 functions. Each function will call a separate trampoline that will only call the function that was registered to it. That way, we can have 1000 different ops registered to 1000 different functions and still have the same performance.

And how will you limit the amount of memory tied up in this? This looks like a good way to tie up an immense amount of memory fast.

Quoted 6 lines · On Fri, 8 Aug 2014 16:34:13 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 4 lines · Steven Rostedt

Quoted 1 line

Ok, so they're purely used in the function prologue/epilogue callchain.

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

Quoted 3 lines

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

Quoted 1 line

And what is there to make sure the kprobe itself doesn't do 'funny'?

Well, kprobes, like function callbacks are just restricted like interrupt handlers are. If they break, they break. They should know better ;-)

Quoted 3 lines

Sure, as long as you make absolutely sure none of that code ends up calling cond_resched()/might_sleep() etc. Which I think you already said was true, so no worries there.

Right. There's no guarantees that someone wont do such a stupid thing. But then, there's no guarantees that someone wont register an NMI callback with the same code too.

Quoted 2 lines

Sure, I get that part. What I was getting as is _WHY_ you need call_rcu_task(), why isn't synchronize_tasks() good enough?

Oh, because that synchronize_tasks() may take minutes. And that means we wont be able to return for a long time. The only thing I can really see using call_rcu_task() is something that needs to free its data. Why wait around when all you're going to do is call free? It's basically just a garbage collector.

Quoted 6 lines

Quoted 5 lines

What we want to do today, is to create a dynamic trampoline for each of theses 1000 functions. Each function will call a separate trampoline that will only call the function that was registered to it. That way, we can have 1000 different ops registered to 1000 different functions and still have the same performance.

Quoted 2 lines

And how will you limit the amount of memory tied up in this? This looks like a good way to tie up an immense amount of memory fast.

Well, these operations are currently only allowed by root. Thus, it's the thing that root should be careful about. The trampolines are small, and it will take a hell of a lot of callbacks to cause issues.

The thing I'm worried about is to make sure they get freed. Otherwise a leak will cause more issues than anything else. Which also means we need to have a way to expedite call_rcu_tasks() if need be.

Quoted 3 lines

Well, kprobes, like function callbacks are just restricted like interrupt handlers are. If they break, they break. They should know better ;-)

But is there debugging infrastructure to test they don't do funny? Or are we just going to wait for some random runtime weirdness and then pull our hair out?

So do we run these handlers with preempt_disable() or anything like that? (maybe only as a debug option).

Quoted 5 lines

Quoted 4 lines

Sure, as long as you make absolutely sure none of that code ends up calling cond_resched()/might_sleep() etc. Which I think you already said was true, so no worries there.

Quoted 3 lines

Right. There's no guarantees that someone wont do such a stupid thing. But then, there's no guarantees that someone wont register an NMI callback with the same code too.

Well, kprobes is 'special' in that it it almost encourages random non kernel devs to write modules for it, so it gets extra special creative crap in.

I'm fairly sure you'll get your ftrace handler right, because that's only you and maybe a few other people ever touching that code. Not so with kprobes.

Quoted 4 lines

Quoted 3 lines

Sure, I get that part. What I was getting as is _WHY_ you need call_rcu_task(), why isn't synchronize_tasks() good enough?

Quoted 5 lines

Oh, because that synchronize_tasks() may take minutes. And that means we wont be able to return for a long time. The only thing I can really see using call_rcu_task() is something that needs to free its data. Why wait around when all you're going to do is call free? It's basically just a garbage collector.

Well the waiting has the advantage of being a natural throttle on the amount of memory tied up in the whole scheme.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

What we want to do today, is to create a dynamic trampoline for each of theses 1000 functions. Each function will call a separate trampoline that will only call the function that was registered to it. That way, we can have 1000 different ops registered to 1000 different functions and still have the same performance.

Quoted 6 lines

Quoted 2 lines

And how will you limit the amount of memory tied up in this? This looks like a good way to tie up an immense amount of memory fast.

Well, these operations are currently only allowed by root. Thus, it's the thing that root should be careful about. The trampolines are small, and it will take a hell of a lot of callbacks to cause issues.

You said 10e3 order things, I then give you a small 32bit arm system.

The thing is, even root is a clueless idiot most of the times, yes we'll let him shoot his foot off and give him enough rope to hang himself, and we'll even show him how to tie the knot at times, but how is he to know that this script that 'worked' now causes his machine to OOM and behave brick like?

Quoted 4 lines

The thing I'm worried about is to make sure they get freed. Otherwise a leak will cause more issues than anything else. Which also means we need to have a way to expedite call_rcu_tasks() if need be.

No.. for one, that doesn't follow. Things will get freed (eventually) even without expedite, and secondly implementing expedite would mean force scheduling tasks etc. And we're just so not going to do that.

Quoted 11 lines

Quoted 8 lines

Quoted 2 lines

Sure, I get that part. What I was getting as is _WHY_ you need call_rcu_task(), why isn't synchronize_tasks() good enough?

Oh, because that synchronize_tasks() may take minutes. And that means we wont be able to return for a long time. The only thing I can really see using call_rcu_task() is something that needs to free its data. Why wait around when all you're going to do is call free? It's basically just a garbage collector.

Well the waiting has the advantage of being a natural throttle on the amount of memory tied up in the whole scheme.

Yeah, but it would suck if you do "echo nop > current_tracer" while running something that is preventing a task to unload, and have to wait a few minutes for that to return.

Quoted 1 line

You said 10e3 order things, I then give you a small 32bit arm system.

Honestly, to allocate 1000 different callbacks now, requires allocating 1000 different ops, which are much larger than a single trampoline. Right now, the only way to do that is to create a 1000 ftrace instances, and those creates a 1000 directories, would would include 1000 event directories, each having its own dentry for each event (around 900).

I don't think we need to worry about this use to work on a small arm 32 bit system and it doesn't work now. The difference in memory consumption is not that much.

Well, see the _BIG_ difference is that currently, when I do nop > current_tracer all that memory is instantly freed again.

With the proposed scheme, if I setup state, reconsider, destroy state, try again, and generally muck about I can tie up unspecified amounts of memory.

And being the bumbling idiot that I am, that's actually fairly typical of how I end up tracing. There's no neat and tidy, I trace something, look at the trace, script a little, muck about with the settings and goto 1.

In any case, I think I now fully understand what you're trying to do, just not sure its all win.

Also, anyone can register a function handler (perf, systemtap, and even LTTng can).

Quoted 2 lines · Steven Rostedt

Also, anyone can register a function handler (perf, systemtap, and even LTTng can).

So how common is it to have more than 1 function event handler, and how many of those cases is there significant difference in the actual functions?

Because that's the case you're optimizing for. Why is that an important enough case.

I'm thinking I'll never trigger that, I only ever have the one normal ftrace handler. So no trampolines for me, the code you have now works just fine.

Quoted 4 lines · On Fri, 8 Aug 2014 18:17:09 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 2 lines · Steven Rostedt

Also, anyone can register a function handler (perf, systemtap, and even LTTng can).

Quoted 3 lines

So how common is it to have more than 1 function event handler, and how many of those cases is there significant difference in the actual functions?

For me, it's quite common. Of course, I tend to poweruse function tracing :-). I do make instances and trace a few functions here and there, while tracing all functions.

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

Unless this is done in idle, at which point RCU-sched is studiously ignoring any preempt_disable() sections.

Quoted 21 lines · Peter Zijlstra

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

Quoted 2 lines

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

Unless this is done in idle, at which point RCU-sched is studiously ignoring any preempt_disable() sections.

Quoted 25 lines · Paul E. McKenney

Quoted 23 lines · Peter Zijlstra

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

Quoted 2 lines

Unless this is done in idle, at which point RCU-sched is studiously ignoring any preempt_disable() sections.

Well, given that kprobes is already using it, it 'must' be good ;-) I suspect much of the idle loop is marked with __kprobe or so, or nobody has been brave enough to try.

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

With the per-cpu preempt count stuff we have on x86 that is 4 instructions for the preempt_*() stuff -- they're 'big' instructions though, since 3 have memops and 2 have a segment prefix.

Quoted 21 lines · On Fri, 8 Aug 2014 18:27:14 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

Quoted 8 lines

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

With the per-cpu preempt count stuff we have on x86 that is 4 instructions for the preempt_*() stuff -- they're 'big' instructions though, since 3 have memops and 2 have a segment prefix.

Now the question is, how do you do that atomically? And safely. Currently, all we replace at the call sites is a nop that is added by gcc -pg and us replacing the call mcount with it. That looks much more complex than our current solution.

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

With the per-cpu preempt count stuff we have on x86 that is 4 instructions for the preempt_*() stuff -- they're 'big' instructions though, since 3 have memops and 2 have a segment prefix.

Quoted 24 lines · On Fri, 8 Aug 2014 18:27:14 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 9 lines · Steven Rostedt

Quoted 6 lines

Quoted 2 lines

No, they are also used by optimized kprobes. This is why optimized kprobes depend on !CONFIG_PREEMPT. [ added Masami to the discussion ].

How do those work? Is that one where the INT3 relocates the instruction stream into an alternative 'text' and that JMPs back into the original stream at the end?

No, it's where we replace the 'int3' with a jump to a trampoline that simulates an INT3. Speeds things up quite a bit.

OK, so the trivial 'fix' for that is to patch the probe site like:

	preempt_disable();		INC	GS:%__preempt_count
	call trampoline;		CALL	0xDEADBEEF
	preempt_enable();		DEC	GS:%__preempt_count
					JNZ	1f
					CALL	___preempt_schedule
				1f:

At which point the preempt_disable/enable() are the read side primitives and call_rcu_sched/synchronize_sched are sufficient to release it.

Quoted 5 lines

With the per-cpu preempt count stuff we have on x86 that is 4 instructions for the preempt_*() stuff -- they're 'big' instructions though, since 3 have memops and 2 have a segment prefix.

Well, this looks like it may make kprobes a bit more complex, and even slow down slightly the optimized probe.

Also note that if we add call_rcu_tasks(), then perf function tracing can be called directly instead of being added to the trampoline that disables and enables preemption before calling it.

-- Steve

Quoted 8 lines · On Thu, 7 Aug 2014 20:46:35 +0200 Peter Zijlstra <[email protected]> wrote:

Quoted 7 lines · Peter Zijlstra

Right, Steve (and Paul) please explain _why_ this is an 'RCU' at all? _Why_ do we have call_rcu_task(), and why is it entwined in the 'normal' RCU stuff? We've got SRCU -- which btw started out simple, without call_srcu() -- and that lives entirely independent. And SRCU is far more an actual RCU than this thing is, its got read side primitives and everything.

Quoted 6 lines

Quoted 2 lines

Also, I cannot think of any other use besides trampolines for this thing, but that might be my limited imagination.

Also, trampolines can end up in the return frames, right? So how can you be sure when to wipe them? Passing through schedule() isn't enough for that.

Not sure what you mean.

Quoted 1 line

Userspace is, but kernel threads typically don't ever end up there.

Hence, once something calls schedule() directly, we know that it is not on a trampoline, nor is it going to return to one.

From: "Paul E. McKenney" <[email protected]>

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 ++++---
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 171 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 242 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..829efc99df3e 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if (ACCESS_ONCE((t)->rcu_tasks_holdout)) \
+			ACCESS_ONCE((t)->rcu_tasks_holdout) = 0; \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +0 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.

init/Kconfig +1 -0

+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +48 -0

index bc7883570530..50453589e3ca 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,173 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*

kernel/rcu/update.c +37 -0

+			flush_signals(current);
+			continue;
+		}
+
+		/*
+		 * Wait for all pre-existing t->on_rq and t->nvcsw
+		 * transitions to complete.  Invoking synchronize_sched()
+		 * suffices because all these transitions occur with
+		 * interrupts disabled.  Without this synchronize_sched(),
+		 * a read-side critical section that started before the
+		 * grace period might be incorrectly seen as having started
+		 * after the grace period.
+		 *
+		 * This synchronize_sched() also dispenses with the
+		 * need for a memory barrier on the first store to
+		 * ->rcu_tasks_holdout, as it forces the store to happen
+		 * after the beginning of the grace period.
+		 */
+		synchronize_sched();
+
+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				get_task_struct(t);
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}

kernel/rcu/update.c +58 -0

+			flush_signals(current);
+			rcu_read_lock();
+			list_for_each_entry_rcu(t, &rcu_tasks_holdouts,
+						rcu_tasks_holdout_list) {
+				if (ACCESS_ONCE(t->rcu_tasks_holdout)) {
+					if (t->rcu_tasks_nvcsw ==
+					    ACCESS_ONCE(t->nvcsw) &&
+					    ACCESS_ONCE(t->on_rq))
+						continue;
+					ACCESS_ONCE(t->rcu_tasks_holdout) = 0;
+				}
+				list_del_rcu(&t->rcu_tasks_holdout_list);
+				put_task_struct(t);
+			}
+			rcu_read_unlock();
+		}
+
+		/*
+		 * Because ->on_rq and ->nvcsw are not guaranteed
+		 * to have a full memory barriers prior to them in the
+		 * schedule() path, memory reordering on other CPUs could
+		 * cause their RCU-tasks read-side critical sections to
+		 * extend past the end of the grace period.  However,
+		 * because these ->nvcsw updates are carried out with
+		 * interrupts disabled, we can use synchronize_sched()
+		 * to force the needed ordering on all such CPUs.
+		 *
+		 * This synchronize_sched() also confines all
+		 * ->rcu_tasks_holdout accesses to be within the grace
+		 * period, avoiding the need for memory barriers for
+		 * ->rcu_tasks_holdout accesses.
+		 */
+		synchronize_sched();
+
+		/* Invoke the callbacks. */
+		while (list) {
+			next = list->next;
+			local_bh_disable();
+			list->func(list);
+			local_bh_enable();
+			list = next;
+			cond_resched();
+		}
+	}
+}
+
+/* Spawn rcu_tasks_kthread() at boot time. */
+static int __init rcu_spawn_tasks_kthread(void)
+{
+	struct task_struct __maybe_unused *t;
+
+	t = kthread_run(rcu_tasks_kthread, NULL, "rcu_tasks_kthread");
+	BUG_ON(IS_ERR(t));
+	return 0;
+}
+early_initcall(rcu_spawn_tasks_kthread);
+
+#endif /* #ifdef CONFIG_TASKS_RCU */

Signature · 1 line

1.8.1.5

Quoted 171 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 ++++---
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 171 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 242 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..829efc99df3e 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if (ACCESS_ONCE((t)->rcu_tasks_holdout)) \
+			ACCESS_ONCE((t)->rcu_tasks_holdout) = 0; \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +0 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.
 

init/Kconfig config PREEMPT_RCU · line 518

Quoted 9 lines

init/Kconfig +9 -0

+config TASKS_RCU
+	bool "Task_based RCU implementation using voluntary context switch"
+	default n
+	help
+	  This option enables a task-based RCU implementation that uses
+	  only voluntary context switch (not preemption!), idle, and
+	  user-mode execution as quiescent states.
+
+	  If unsure, say N.

I don't remember who said that, but indeed this is a pure internal feature only. The user doesn't need to select that option ever.

Quoted 99 lines

init/Kconfig +1 -0

+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +54 -0

index bc7883570530..50453589e3ca 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,173 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*
+	 * Each pass through the following loop makes one check for
+	 * newly arrived callbacks, and, if there are some, waits for
+	 * one RCU-tasks grace period and then invokes the callbacks.
+	 * This loop is terminated by the system going down.  ;-)
+	 */
+	for (;;) {

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 410

Quoted 4 lines

kernel/rcu/update.c +4 -0

+
+		/* Pick up any new callbacks. */
+		raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+		smp_mb__after_unlock_lock(); /* Enforce GP memory ordering. */

I have no idea which against what this is exactly ordering. GP is a vast thing. Especially for tricky barriers like __after_unlock_lock() which suggest very counter-intuitive ordering, a detailed comment is very welcome :)

Quoted 5 lines

kernel/rcu/update.c +5 -0

+		list = rcu_tasks_cbs_head;
+		rcu_tasks_cbs_head = NULL;
+		rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+		raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 418

Quoted 3 lines

kernel/rcu/update.c +3 -0

+		/* If there were none, wait a bit and start over. */
+		if (!list) {
+			schedule_timeout_interruptible(HZ);

So this thread is going to poll every second? I guess something prevents it to run when system is idle somewhere? But I'm not familiar with the whole patchset yet. But even without that it looks like a very annoying noise. why not use something wait/wakeup based?

Quoted 42 lines

kernel/rcu/update.c +42 -0

+			flush_signals(current);
+			continue;
+		}
+
+		/*
+		 * Wait for all pre-existing t->on_rq and t->nvcsw
+		 * transitions to complete.  Invoking synchronize_sched()
+		 * suffices because all these transitions occur with
+		 * interrupts disabled.  Without this synchronize_sched(),
+		 * a read-side critical section that started before the
+		 * grace period might be incorrectly seen as having started
+		 * after the grace period.
+		 *
+		 * This synchronize_sched() also dispenses with the
+		 * need for a memory barrier on the first store to
+		 * ->rcu_tasks_holdout, as it forces the store to happen
+		 * after the beginning of the grace period.
+		 */
+		synchronize_sched();
+
+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				get_task_struct(t);
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * Each pass through the following loop scans the list

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 465

Quoted 5 lines

kernel/rcu/update.c +5 -0

+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);

OTOH here it is not annoying because it should only happen when rcu task is used, which should be rare.

Thanks.

Quoted 61 lines

kernel/rcu/update.c +58 -0

+			flush_signals(current);
+			rcu_read_lock();
+			list_for_each_entry_rcu(t, &rcu_tasks_holdouts,
+						rcu_tasks_holdout_list) {
+				if (ACCESS_ONCE(t->rcu_tasks_holdout)) {
+					if (t->rcu_tasks_nvcsw ==
+					    ACCESS_ONCE(t->nvcsw) &&
+					    ACCESS_ONCE(t->on_rq))
+						continue;
+					ACCESS_ONCE(t->rcu_tasks_holdout) = 0;
+				}
+				list_del_rcu(&t->rcu_tasks_holdout_list);
+				put_task_struct(t);
+			}
+			rcu_read_unlock();
+		}
+
+		/*
+		 * Because ->on_rq and ->nvcsw are not guaranteed
+		 * to have a full memory barriers prior to them in the
+		 * schedule() path, memory reordering on other CPUs could
+		 * cause their RCU-tasks read-side critical sections to
+		 * extend past the end of the grace period.  However,
+		 * because these ->nvcsw updates are carried out with
+		 * interrupts disabled, we can use synchronize_sched()
+		 * to force the needed ordering on all such CPUs.
+		 *
+		 * This synchronize_sched() also confines all
+		 * ->rcu_tasks_holdout accesses to be within the grace
+		 * period, avoiding the need for memory barriers for
+		 * ->rcu_tasks_holdout accesses.
+		 */
+		synchronize_sched();
+
+		/* Invoke the callbacks. */
+		while (list) {
+			next = list->next;
+			local_bh_disable();
+			list->func(list);
+			local_bh_enable();
+			list = next;
+			cond_resched();
+		}
+	}
+}
+
+/* Spawn rcu_tasks_kthread() at boot time. */
+static int __init rcu_spawn_tasks_kthread(void)
+{
+	struct task_struct __maybe_unused *t;
+
+	t = kthread_run(rcu_tasks_kthread, NULL, "rcu_tasks_kthread");
+	BUG_ON(IS_ERR(t));
+	return 0;
+}
+early_initcall(rcu_spawn_tasks_kthread);
+
+#endif /* #ifdef CONFIG_TASKS_RCU */

Signature · 1 line

1.8.1.5

Quoted 5 lines · Frederic Weisbecker

So this thread is going to poll every second? I guess something prevents it to run when system is idle somewhere? But I'm not familiar with the whole patchset yet. But even without that it looks like a very annoying noise. why not use something wait/wakeup based?

And a later patch does the wait/wakeup thing. Start stupid, add small amounts of sophistication incrementally.

Quoted 43 lines

Quoted 43 lines

kernel/rcu/update.c +42 -0

+			flush_signals(current);
+			continue;
+		}
+
+		/*
+		 * Wait for all pre-existing t->on_rq and t->nvcsw
+		 * transitions to complete.  Invoking synchronize_sched()
+		 * suffices because all these transitions occur with
+		 * interrupts disabled.  Without this synchronize_sched(),
+		 * a read-side critical section that started before the
+		 * grace period might be incorrectly seen as having started
+		 * after the grace period.
+		 *
+		 * This synchronize_sched() also dispenses with the
+		 * need for a memory barrier on the first store to
+		 * ->rcu_tasks_holdout, as it forces the store to happen
+		 * after the beginning of the grace period.
+		 */
+		synchronize_sched();
+
+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				get_task_struct(t);
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * Each pass through the following loop scans the list

Quoted 8 lines

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 465

Quoted 5 lines

kernel/rcu/update.c +5 -0

+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);

OTOH here it is not annoying because it should only happen when rcu task is used, which should be rare.

Glad you like it!

I will likely also add checks for other things needing the current CPU.

From: "Paul E. McKenney" <[email protected]>

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 ++++---
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 171 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 242 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..829efc99df3e 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if (ACCESS_ONCE((t)->rcu_tasks_holdout)) \
+			ACCESS_ONCE((t)->rcu_tasks_holdout) = 0; \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +10 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.
 
+config TASKS_RCU
+	bool "Task_based RCU implementation using voluntary context switch"
+	default n
+	help
+	  This option enables a task-based RCU implementation that uses
+	  only voluntary context switch (not preemption!), idle, and
+	  user-mode execution as quiescent states.
+
+	  If unsure, say N.
+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +118 -0

index bc7883570530..50453589e3ca 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,173 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*
+	 * Each pass through the following loop makes one check for
+	 * newly arrived callbacks, and, if there are some, waits for
+	 * one RCU-tasks grace period and then invokes the callbacks.
+	 * This loop is terminated by the system going down.  ;-)
+	 */
+	for (;;) {
+
+		/* Pick up any new callbacks. */
+		raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+		smp_mb__after_unlock_lock(); /* Enforce GP memory ordering. */
+		list = rcu_tasks_cbs_head;
+		rcu_tasks_cbs_head = NULL;
+		rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+		raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+
+		/* If there were none, wait a bit and start over. */
+		if (!list) {
+			schedule_timeout_interruptible(HZ);
+			flush_signals(current);
+			continue;
+		}
+
+		/*
+		 * Wait for all pre-existing t->on_rq and t->nvcsw
+		 * transitions to complete.  Invoking synchronize_sched()
+		 * suffices because all these transitions occur with
+		 * interrupts disabled.  Without this synchronize_sched(),
+		 * a read-side critical section that started before the
+		 * grace period might be incorrectly seen as having started
+		 * after the grace period.
+		 *
+		 * This synchronize_sched() also dispenses with the
+		 * need for a memory barrier on the first store to
+		 * ->rcu_tasks_holdout, as it forces the store to happen
+		 * after the beginning of the grace period.
+		 */
+		synchronize_sched();
+
+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				get_task_struct(t);
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * Each pass through the following loop scans the list
+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);
+			flush_signals(current);
+			rcu_read_lock();
+			list_for_each_entry_rcu(t, &rcu_tasks_holdouts,
+						rcu_tasks_holdout_list) {
+				if (ACCESS_ONCE(t->rcu_tasks_holdout)) {

kernel/rcu/update.c +43 -0

+		}
+
+		/*
+		 * Because ->on_rq and ->nvcsw are not guaranteed
+		 * to have a full memory barriers prior to them in the
+		 * schedule() path, memory reordering on other CPUs could
+		 * cause their RCU-tasks read-side critical sections to
+		 * extend past the end of the grace period.  However,
+		 * because these ->nvcsw updates are carried out with
+		 * interrupts disabled, we can use synchronize_sched()
+		 * to force the needed ordering on all such CPUs.
+		 *
+		 * This synchronize_sched() also confines all
+		 * ->rcu_tasks_holdout accesses to be within the grace
+		 * period, avoiding the need for memory barriers for
+		 * ->rcu_tasks_holdout accesses.
+		 */
+		synchronize_sched();
+
+		/* Invoke the callbacks. */
+		while (list) {
+			next = list->next;
+			local_bh_disable();
+			list->func(list);
+			local_bh_enable();
+			list = next;
+			cond_resched();
+		}
+	}
+}
+
+/* Spawn rcu_tasks_kthread() at boot time. */
+static int __init rcu_spawn_tasks_kthread(void)
+{
+	struct task_struct __maybe_unused *t;
+
+	t = kthread_run(rcu_tasks_kthread, NULL, "rcu_tasks_kthread");
+	BUG_ON(IS_ERR(t));
+	return 0;
+}
+early_initcall(rcu_spawn_tasks_kthread);
+
+#endif /* #ifdef CONFIG_TASKS_RCU */

Quoted 347 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 ++++---
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 171 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 242 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..829efc99df3e 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if (ACCESS_ONCE((t)->rcu_tasks_holdout)) \
+			ACCESS_ONCE((t)->rcu_tasks_holdout) = 0; \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +10 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.
 
+config TASKS_RCU
+	bool "Task_based RCU implementation using voluntary context switch"
+	default n
+	help
+	  This option enables a task-based RCU implementation that uses
+	  only voluntary context switch (not preemption!), idle, and
+	  user-mode execution as quiescent states.
+
+	  If unsure, say N.
+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +122 -0

index bc7883570530..50453589e3ca 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,173 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*
+	 * Each pass through the following loop makes one check for
+	 * newly arrived callbacks, and, if there are some, waits for
+	 * one RCU-tasks grace period and then invokes the callbacks.
+	 * This loop is terminated by the system going down.  ;-)
+	 */
+	for (;;) {
+
+		/* Pick up any new callbacks. */
+		raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+		smp_mb__after_unlock_lock(); /* Enforce GP memory ordering. */
+		list = rcu_tasks_cbs_head;
+		rcu_tasks_cbs_head = NULL;
+		rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+		raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+
+		/* If there were none, wait a bit and start over. */
+		if (!list) {
+			schedule_timeout_interruptible(HZ);
+			flush_signals(current);
+			continue;
+		}
+
+		/*
+		 * Wait for all pre-existing t->on_rq and t->nvcsw
+		 * transitions to complete.  Invoking synchronize_sched()
+		 * suffices because all these transitions occur with
+		 * interrupts disabled.  Without this synchronize_sched(),
+		 * a read-side critical section that started before the
+		 * grace period might be incorrectly seen as having started
+		 * after the grace period.
+		 *
+		 * This synchronize_sched() also dispenses with the
+		 * need for a memory barrier on the first store to
+		 * ->rcu_tasks_holdout, as it forces the store to happen
+		 * after the beginning of the grace period.
+		 */
+		synchronize_sched();
+
+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				get_task_struct(t);
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * Each pass through the following loop scans the list
+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);
+			flush_signals(current);
+			rcu_read_lock();
+			list_for_each_entry_rcu(t, &rcu_tasks_holdouts,
+						rcu_tasks_holdout_list) {
+				if (ACCESS_ONCE(t->rcu_tasks_holdout)) {
+					if (t->rcu_tasks_nvcsw ==
+					    ACCESS_ONCE(t->nvcsw) &&
+					    ACCESS_ONCE(t->on_rq))
+						continue;