RCU-tasks implementation

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

RCU-tasks requires the occasional voluntary context switch from CPU-bound in-kernel tasks. In some cases, this requires instrumenting cond_resched(). However, there is some reluctance to countenance unconditionally instrumenting cond_resched() (see
http://lwn.net/Articles/603252/),

so this commit creates a separate
cond_resched_rcu_qs() that may be used in place of cond_resched() in locations prone to long-duration in-kernel looping.

Quoted 7 lines · Paul E. McKenney

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

RCU-tasks requires the occasional voluntary context switch from CPU-bound in-kernel tasks. In some cases, this requires instrumenting cond_resched(). However, there is some reluctance to countenance unconditionally instrumenting cond_resched() (see
http://lwn.net/Articles/603252/),

No, if its a good reason mention it, if not ignore it.

Quoted 3 lines

so this commit creates a separate
cond_resched_rcu_qs() that may be used in place of cond_resched() in locations prone to long-duration in-kernel looping.

Sounds like a pain and a recipe for mistakes. How is joe kernel hacker supposed to 1) know about this new api, and 2) decide which to use?

Heck, even I wouldn't know, and I just read the damn patch.

Quoted 10 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

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

RCU-tasks requires the occasional voluntary context switch from CPU-bound in-kernel tasks. In some cases, this requires instrumenting cond_resched(). However, there is some reluctance to countenance unconditionally instrumenting cond_resched() (see
http://lwn.net/Articles/603252/),

No, if its a good reason mention it, if not ignore it.

Fair enough. ;-)

Quoted 8 lines

Quoted 3 lines

so this commit creates a separate
cond_resched_rcu_qs() that may be used in place of cond_resched() in locations prone to long-duration in-kernel looping.

Sounds like a pain and a recipe for mistakes. How is joe kernel hacker supposed to 1) know about this new api, and 2) decide which to use?

Heck, even I wouldn't know, and I just read the damn patch.

When Joe Hacker gets stall warning messages due to loops in the kernel that contain cond_resched(), that is a hint that cond_resched_rcu_qs() is required. These stall warnings can occur when using RCU-tasks and when using normal RCU in NO_HZ_FULL kernels in cases where the scheduling-clock interrupt is left off while executing a long code path in the kernel. (Of course, in both cases, another eminently reasonable fix is to shorten the offending code path in the kernel.)

I should add words to that effect to Documentation/RCU/stallwarn.txt, shouldn't I? Done.

Quoted 31 lines · Paul E. McKenney

Quoted 10 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

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

RCU-tasks requires the occasional voluntary context switch from CPU-bound in-kernel tasks. In some cases, this requires instrumenting cond_resched(). However, there is some reluctance to countenance unconditionally instrumenting cond_resched() (see
http://lwn.net/Articles/603252/),

No, if its a good reason mention it, if not ignore it.

Fair enough. ;-)

Quoted 8 lines

Quoted 3 lines

so this commit creates a separate
cond_resched_rcu_qs() that may be used in place of cond_resched() in locations prone to long-duration in-kernel looping.

Sounds like a pain and a recipe for mistakes. How is joe kernel hacker supposed to 1) know about this new api, and 2) decide which to use?

Heck, even I wouldn't know, and I just read the damn patch.

When Joe Hacker gets stall warning messages due to loops in the kernel that contain cond_resched(), that is a hint that cond_resched_rcu_qs() is required. These stall warnings can occur when using RCU-tasks and when using normal RCU in NO_HZ_FULL kernels in cases where the scheduling-clock interrupt is left off while executing a long code path in the kernel. (Of course, in both cases, another eminently reasonable fix is to shorten the offending code path in the kernel.)

Quoted 2 lines

I should add words to that effect to Documentation/RCU/stallwarn.txt, shouldn't I? Done.

No, but why can't we make the regular cond_resched() do this?

Quoted 1 line

No, but why can't we make the regular cond_resched() do this?

Well, I got a lot of grief when I tried it a few weeks ago.

But from what I can see, you are the maintainer or cond_resched(), so if you are good with making the normal cond_resched() do this, I am more than happy to make it so! ;-)

Quoted 4 lines · Paul E. McKenney

Quoted 1 line

No, but why can't we make the regular cond_resched() do this?

Well, I got a lot of grief when I tried it a few weeks ago.

Quoted 3 lines

But from what I can see, you are the maintainer or cond_resched(), so if you are good with making the normal cond_resched() do this, I am more than happy to make it so! ;-)

Well, its the 'obvious' thing to do. But clearly I haven't tried so I'm blissfully unaware of any problems. And the Changelog didn't inform me either (you had a link in there, which I didn't read :-)

Quoted 9 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

Quoted 1 line

No, but why can't we make the regular cond_resched() do this?

Well, I got a lot of grief when I tried it a few weeks ago.

But from what I can see, you are the maintainer or cond_resched(), so if you are good with making the normal cond_resched() do this, I am more than happy to make it so! ;-)

Quoted 3 lines

Well, its the 'obvious' thing to do. But clearly I haven't tried so I'm blissfully unaware of any problems. And the Changelog didn't inform me either (you had a link in there, which I didn't read :-)

Then again, last time we touched cond_resched() we had a scalability issue or somesuch, or am I misremembering things?

This commit adds synchronization with exiting tasks, so that RCU-tasks avoids waiting on tasks that no longer exist.

Quoted 3 lines · Paul E. McKenney

This commit adds synchronization with exiting tasks, so that RCU-tasks avoids waiting on tasks that no longer exist.

I don't understand this patch yet, but it seems that it adds more than just synchronization with exiting tasks?

kernel/rcu/update.c void rcu_barrier_tasks(void) · line 716

Quoted 7 lines

kernel/rcu/update.c +7 -0

+		ACCESS_ONCE(t->rcu_tasks_holdout) = 1;
+		spin_unlock(&t->rcu_tasks_lock);
+		smp_mb();  /* Order ->rcu_tasks_holdout store before "if". */
+		if (t == current || !ACCESS_ONCE(t->on_rq) || is_idle_task(t)) {
+			smp_store_release(&t->rcu_tasks_holdout, 0);
+			goto next_thread;
+		}

This should avoid the race with schedule()->rcu_note_voluntary_context_switch(), right?

kernel/rcu/update.c static int __noreturn rcu_tasks_kthread(void *arg) · line 514

Quoted 5 lines

kernel/rcu/update.c +0 -5

-		rcu_read_lock();
-		do_each_thread(g, t) {
-			if (t != current && ACCESS_ONCE(t->on_rq) &&
-			    !is_idle_task(t)) {
-				t->rcu_tasks_holdout = 1;

Because before this patch the code looks obviously racy, a task can do sleep(FOREVER) and block rcu_tasks_kthread() if it reads ->on_rq == 1 after rcu_note_voluntary_context_switch() was already called.

However, I am not sure this race is actually closed even after this change... why rcu_note_voluntary_context_switch() can not miss ->rcu_tasks_holdout != 0 ?

OK, it seems that you are going to send the next version anyway, so please ignore.

Oleg.

kernel/sched/core.c +1 -0

index bc1638b33449..a0d2f3a03566 100644
@@ -2762,6 +2762,7 @@ need_resched:
 		} else {
 			deactivate_task(rq, prev, DEQUEUE_SLEEP);
 			prev->on_rq = 0;
+			rcu_note_voluntary_context_switch(prev);
 
 			/*
 			 * If a worker went to sleep, notify and ask workqueue

Quoted 15 lines · Paul E. McKenney

kernel/sched/core.c +1 -0

index bc1638b33449..a0d2f3a03566 100644
@@ -2762,6 +2762,7 @@ need_resched:
 		} else {
 			deactivate_task(rq, prev, DEQUEUE_SLEEP);
 			prev->on_rq = 0;
+			rcu_note_voluntary_context_switch(prev);
 
 			/*
 			 * If a worker went to sleep, notify and ask workqueue

@@ -2828,6 +2829,7 @@ asmlinkage __visible void __sched schedule(void)
 	struct task_struct *tsk = current;
 

kernel/sched/core.c asmlinkage __visible void __sched schedule(void) · line 2834

Quoted 4 lines

kernel/sched/core.c +1 -0

 	sched_submit_work(tsk);
+	rcu_note_voluntary_context_switch(tsk);
 	__schedule();
 }

Yeah, not entirely happy with that, you add two calls into one of the hotest paths of the kernel.

And I'm still not entirely sure why, your 0/x babbled something about trampolines, but I'm not sure I understand how those lead to this.

Quoted 16 lines · Peter Zijlstra

Quoted 15 lines · Paul E. McKenney

kernel/sched/core.c +1 -0

index bc1638b33449..a0d2f3a03566 100644
@@ -2762,6 +2762,7 @@ need_resched:
 		} else {
 			deactivate_task(rq, prev, DEQUEUE_SLEEP);
 			prev->on_rq = 0;
+			rcu_note_voluntary_context_switch(prev);
 
 			/*
 			 * If a worker went to sleep, notify and ask workqueue

@@ -2828,6 +2829,7 @@ asmlinkage __visible void __sched schedule(void)
 	struct task_struct *tsk = current;
 

Quoted 7 lines

kernel/sched/core.c asmlinkage __visible void __sched schedule(void) · line 2834

Quoted 4 lines

kernel/sched/core.c +1 -0

 	sched_submit_work(tsk);
+	rcu_note_voluntary_context_switch(tsk);
 	__schedule();
 }

Yeah, not entirely happy with that, you add two calls into one of the hotest paths of the kernel.

I did look into leveraging counters, but cannot remember why I decided that this was a bad idea. I guess it is time to recheck...

The ->nvcsw field in the task_struct structure looks promising:

o Looks like it does in fact get incremented in __schedule() via
the switch_count pointer.

o Looks like it is unconditionally compiled in.

o There are no memory barriers, but a synchronize_sched()
should take care of that, given that this counter is incremented with interrupts disabled.

So I should be able to snapshot the task_struct structure's ->nvcsw field and avoid the added code in the fastpaths.

Seem plausible, or am I confused about the role of ->nvcsw?

Quoted 2 lines

And I'm still not entirely sure why, your 0/x babbled something about trampolines, but I'm not sure I understand how those lead to this.

Steven Rostedt sent an email recently giving more detail. And of course now I am having trouble finding it. Maybe he will take pity on us and send along a pointer to it. ;-)

Quoted 35 lines · Paul E. McKenney

Quoted 16 lines · Peter Zijlstra

Quoted 15 lines · Paul E. McKenney

kernel/sched/core.c +1 -0

index bc1638b33449..a0d2f3a03566 100644
@@ -2762,6 +2762,7 @@ need_resched:
 		} else {
 			deactivate_task(rq, prev, DEQUEUE_SLEEP);
 			prev->on_rq = 0;
+			rcu_note_voluntary_context_switch(prev);
 
 			/*
 			 * If a worker went to sleep, notify and ask workqueue

@@ -2828,6 +2829,7 @@ asmlinkage __visible void __sched schedule(void)
 	struct task_struct *tsk = current;
 

Quoted 7 lines

kernel/sched/core.c asmlinkage __visible void __sched schedule(void) · line 2834

Quoted 4 lines

kernel/sched/core.c +1 -0

 	sched_submit_work(tsk);
+	rcu_note_voluntary_context_switch(tsk);
 	__schedule();
 }

Yeah, not entirely happy with that, you add two calls into one of the hotest paths of the kernel.

I did look into leveraging counters, but cannot remember why I decided that this was a bad idea. I guess it is time to recheck...

The ->nvcsw field in the task_struct structure looks promising:

o Looks like it does in fact get incremented in __schedule() via
the switch_count pointer.

o Looks like it is unconditionally compiled in.

Quoted 3 lines

o There are no memory barriers, but a synchronize_sched()
should take care of that, given that this counter is incremented with interrupts disabled.

Well, there's obviously the actual context switch, which should imply an actual MB such that tasks are self ordered even when execution continues on another cpu etc..

Quoted 4 lines

So I should be able to snapshot the task_struct structure's ->nvcsw field and avoid the added code in the fastpaths.

Seem plausible, or am I confused about the role of ->nvcsw?

Nope, that's the 'I scheduled to go to sleep' counter.

There is of course the 'polling' issue I raised in a further email...

Quoted 6 lines

Quoted 2 lines

And I'm still not entirely sure why, your 0/x babbled something about trampolines, but I'm not sure I understand how those lead to this.

Steven Rostedt sent an email recently giving more detail. And of course now I am having trouble finding it. Maybe he will take pity on us and send along a pointer to it. ;-)

Yah, would make good Changelog material that ;-)

Quoted 7 lines

Quoted 3 lines

o There are no memory barriers, but a synchronize_sched()
should take care of that, given that this counter is incremented with interrupts disabled.

Well, there's obviously the actual context switch, which should imply an actual MB such that tasks are self ordered even when execution continues on another cpu etc..

True enough, except that it appears that the context switch happens after the ->nvcsw increment, which means that it doesn't help RCU-tasks guarantee that if it has seen the increment, then all prior processing has completed. There might be enough stuff prior the increment, but I don't see anything that I feel comfortable relying on. Am I missing some ordering?

Quoted 6 lines

Quoted 4 lines

So I should be able to snapshot the task_struct structure's ->nvcsw field and avoid the added code in the fastpaths.

Seem plausible, or am I confused about the role of ->nvcsw?

Nope, that's the 'I scheduled to go to sleep' counter.

I am assuming that the "Nope" goes with "am I confused" rather than "Seem plausible" -- if not, please let me know. ;-)

Quoted 1 line

There is of course the 'polling' issue I raised in a further email...

Yep, and other flavors of RCU go to lengths to avoid scanning the task_struct lists. Steven said that updates will be rare and that it is OK for them to have high latency and overhead. Thus far, I am taking him at his word. ;-)

I considered interrupting the task_struct polling loop periodically, and would add that if needed. That said, this requires nailing down the task_struct at which the vacation is taken. Here "nailing down" does not simply mean "prevent from being freed", but rather "prevent from being removed from the lists traversed by do_each_thread/while_each_thread."

Of course, if there is some easy way of doing this, please let me know!

Quoted 8 lines · Paul E. McKenney

Quoted 7 lines

Quoted 3 lines

o There are no memory barriers, but a synchronize_sched()
should take care of that, given that this counter is incremented with interrupts disabled.

Well, there's obviously the actual context switch, which should imply an actual MB such that tasks are self ordered even when execution continues on another cpu etc..

Quoted 6 lines

True enough, except that it appears that the context switch happens after the ->nvcsw increment, which means that it doesn't help RCU-tasks guarantee that if it has seen the increment, then all prior processing has completed. There might be enough stuff prior the increment, but I don't see anything that I feel comfortable relying on. Am I missing some ordering?

There's the smp_mb__before_spinlock() + raw_spin_lock_irq(), but that's about it I suppose.

Quoted 9 lines

Quoted 6 lines

Quoted 4 lines

So I should be able to snapshot the task_struct structure's ->nvcsw field and avoid the added code in the fastpaths.

Seem plausible, or am I confused about the role of ->nvcsw?

Nope, that's the 'I scheduled to go to sleep' counter.

I am assuming that the "Nope" goes with "am I confused" rather than "Seem plausible" -- if not, please let me know. ;-)

Yah :-)

Quoted 13 lines

Quoted 1 line

There is of course the 'polling' issue I raised in a further email...

Yep, and other flavors of RCU go to lengths to avoid scanning the task_struct lists. Steven said that updates will be rare and that it is OK for them to have high latency and overhead. Thus far, I am taking him at his word. ;-)

I considered interrupting the task_struct polling loop periodically, and would add that if needed. That said, this requires nailing down the task_struct at which the vacation is taken. Here "nailing down" does not simply mean "prevent from being freed", but rather "prevent from being removed from the lists traversed by do_each_thread/while_each_thread."

Quoted 1 line

Of course, if there is some easy way of doing this, please let me know!

Well, one reason I'm not liking this is because its in an anonymous context (kthread) which makes accounting for it hard.

I feel we're doing far too much async stuff already and it keeps getting worse and worse. Ideally we'd be able to account every cycle of kernel 'overhead' to a specific user action.

Another reason is that I fundamentally dislike polling stuff.. but yes, I'm not really seeing how to do this differently, partly because I'm not entirely sure why we need this to begin with. I'm not sure what problem we're solving.

Quoted 3 lines

I feel we're doing far too much async stuff already and it keeps getting worse and worse. Ideally we'd be able to account every cycle of kernel 'overhead' to a specific user action.

Hmmm...

In theory, we could transfer the overhead of the kthread for a given grace period to the task invoking the corresponding synchronize_rcu_tasks(). In practice, the overhead might need to be parceled out among several tasks that concurrently invoked synchronize_rcu_tasks(). Or I suppose that the overhead could be assigned to the first such task that woke up, on the theory that things would even out over time.

So exactly how annoyed are you about the lack of accounting? ;-)

Quoted 4 lines

Another reason is that I fundamentally dislike polling stuff.. but yes, I'm not really seeing how to do this differently, partly because I'm not entirely sure why we need this to begin with. I'm not sure what problem we're solving.

As I recall it...

Steven is working on some sort of tracing infrastructure that involves dynamically allocated trampolines being inserted into some/all functions. The trampoline code can be preempted, but never does voluntary context switches, and presumably never calls anything that does voluntary context switches.

Easy to insert a trampoline, but the trick is removing them.

The thought is to restore the instructions at the begining of the function in question, wait for an RCU-tasks grace period, then dispose of the trampoline.

Of course, you could imagine disabling preemption or otherwise entering an RCU read-side critical section before transferring to the trampoline, but this was apparently a no-go due to the overhead for small functions.

Quoted 13 lines · Paul E. McKenney

Quoted 3 lines

I feel we're doing far too much async stuff already and it keeps getting worse and worse. Ideally we'd be able to account every cycle of kernel 'overhead' to a specific user action.

Hmmm...

In theory, we could transfer the overhead of the kthread for a given grace period to the task invoking the corresponding synchronize_rcu_tasks(). In practice, the overhead might need to be parceled out among several tasks that concurrently invoked synchronize_rcu_tasks(). Or I suppose that the overhead could be assigned to the first such task that woke up, on the theory that things would even out over time.

Quoted 1 line

So exactly how annoyed are you about the lack of accounting? ;-)

Its a general annoyance that people don't seem to consider this at all.

And RCU isn't the largest offender by a long shot.

Quoted 15 lines

Quoted 4 lines

Another reason is that I fundamentally dislike polling stuff.. but yes, I'm not really seeing how to do this differently, partly because I'm not entirely sure why we need this to begin with. I'm not sure what problem we're solving.

As I recall it...

Steven is working on some sort of tracing infrastructure that involves dynamically allocated trampolines being inserted into some/all functions. The trampoline code can be preempted, but never does voluntary context switches, and presumably never calls anything that does voluntary context switches.

Easy to insert a trampoline, but the trick is removing them.

Quoted 7 lines

The thought is to restore the instructions at the begining of the function in question, wait for an RCU-tasks grace period, then dispose of the trampoline.

Of course, you could imagine disabling preemption or otherwise entering an RCU read-side critical section before transferring to the trampoline, but this was apparently a no-go due to the overhead for small functions.

So why not use the freezer to get the kernel into a known good state and then remove them trampolines? That would mean a more noticeable disruption of service, but it might be ok for something like disabling a tracer or so. Dunno.

Kernel threads are the problem here, lemme ponder this for a bit.

kernel/rcu/update.c +8 -0

+		/*
+		 * 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);

Quoted 13 lines · Paul E. McKenney

kernel/rcu/update.c +13 -0

+		/*
+		 * 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 (smp_load_acquire(&t->rcu_tasks_holdout))
+					continue;

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

Quoted 5 lines

kernel/rcu/update.c +5 -0

+				list_del_init(&t->rcu_tasks_holdout_list);
+				/* @@@ need to check for usermode on CPU. */
+			}
+			rcu_read_unlock();
+		}

That's a potential CPU runtime sink.. imagine having to scan 100k tasks 10 times a second. Polling O(nr_tasks) is not good.

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.

kernel/rcu/tiny.c void rcu_check_callbacks(int cpu, int user) · line 259

Quoted 7 lines · Paul E. McKenney

kernel/rcu/tiny.c +2 -0

@@ -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);
 }

There's nothing like sending email you can't find something... :-)

Quoted 10 lines · Peter Zijlstra

kernel/rcu/tiny.c void rcu_check_callbacks(int cpu, int user) · line 259

Quoted 7 lines · Paul E. McKenney

kernel/rcu/tiny.c +2 -0

@@ -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);
 }

There's nothing like sending email you can't find something... :-)

Well, this is unfortunately only a partial solution. It does not handle the NO_HZ_FULL scheduling-clock-free usermode execution. I have ink on paper indicating a couple of ways to do that, but figured I should get feedback on this stuff before going too much farther.

Quoted 12 lines · Paul E. McKenney

Quoted 10 lines · Peter Zijlstra

kernel/rcu/tiny.c void rcu_check_callbacks(int cpu, int user) · line 259

Quoted 7 lines · Paul E. McKenney

kernel/rcu/tiny.c +2 -0

@@ -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);
 }

There's nothing like sending email you can't find something... :-)

Quoted 4 lines

Well, this is unfortunately only a partial solution. It does not handle the NO_HZ_FULL scheduling-clock-free usermode execution. I have ink on paper indicating a couple of ways to do that, but figured I should get feedback on this stuff before going too much farther.

Yah, so the nohz_full already has the horrid overhead of user<->kernel switches, so you can 'trivially' hook into those.

FWIW its _the_ thing that makes nohz_full uninteresting for me. The required overhead is insane. But yes there are people willing to pay that etc..

Quoted 3 lines · Peter Zijlstra

FWIW its _the_ thing that makes nohz_full uninteresting for me. The required overhead is insane. But yes there are people willing to pay that etc..

It would indeed be good to reduce the overhead. I could imagine all sorts of insane approaches involving assuming that CPU write buffers flush in bounded time, though CPU vendors seem unwilling to make guarantees in this area. ;-)

Or is something other than rcu_user_enter() and rcu_user_exit() causing the pain here?

Quoted 11 lines · Paul E. McKenney

Quoted 3 lines · Peter Zijlstra

FWIW its _the_ thing that makes nohz_full uninteresting for me. The required overhead is insane. But yes there are people willing to pay that etc..

It would indeed be good to reduce the overhead. I could imagine all sorts of insane approaches involving assuming that CPU write buffers flush in bounded time, though CPU vendors seem unwilling to make guarantees in this area. ;-)

Quoted 2 lines

Or is something other than rcu_user_enter() and rcu_user_exit() causing the pain here?

Border guards stamping visas. Note native_sched_clock().

echo 0 > sched_wakeup_granularity_ns
taskset -c 3 pipe-test 1

    CONFIG_NO_HZ_FULL=y 604.2 KHz           CONFIG_NO_HZ_FULL=y, nohz_full=3 303.5 KHz
    10.45%   __schedule                     8.74%   native_sched_clock
    10.03%   system_call                    5.63%   __schedule
     4.86%   _raw_spin_lock_irqsave         4.75%   _raw_spin_lock
     4.51%   __switch_to                    4.35%   reschedule_interrupt
     4.31%   copy_user_generic_string       3.91%   _raw_spin_unlock_irqrestore
     3.50%   pipe_read                      3.35%   system_call
     3.02%   pipe_write                     2.73%   context_tracking_user_exit
     2.76%   mutex_lock                     2.30%   _raw_spin_lock_irqsave
     2.30%   native_sched_clock             2.08%   context_tracking_user_enter
     2.27%   copy_page_to_iter_iovec        1.94%   __switch_to
     2.16%   mutex_unlock                   1.88%   copy_user_generic_string
     2.15%   _raw_spin_unlock_irqrestore    1.80%   account_system_time
     1.86%   copy_page_from_iter_iovec      1.77%   rcu_eqs_enter_common.isra.42
     1.85%   vfs_write                      1.60%   pipe_read
     1.67%   new_sync_read                  1.58%   pipe_write
     1.61%   new_sync_write                 1.39%   mutex_lock
     1.49%   vfs_read                       1.37%   enqueue_task_fair
     1.47%   fsnotify                       1.25%   rcu_eqs_exit_common.isra.43
     1.43%   __fget_light                   1.14%   get_vtime_delta
     1.36%   enqueue_task_fair              1.11%   flat_send_IPI_mask
     1.28%   finish_task_switch             1.07%   tracesys
     1.26%   dequeue_task_fair              1.03%   dequeue_task_fair
     1.25%   __sb_start_write               1.01%   copy_page_to_iter_iovec
     1.22%   _raw_spin_lock_irq             1.01%   int_check_syscall_exit_work
     1.20%   try_to_wake_up                 0.97%   vfs_write
     1.16%   update_curr                    0.94%   __context_tracking_task_switch
     1.05%   __fsnotify_parent              0.93%   mutex_unlock
     1.03%   pick_next_task_fair            0.88%   copy_page_from_iter_iovec
     1.02%   sys_write                      0.87%   new_sync_write
     1.01%   sys_read                       0.86%   __fget_light
     1.00%   __wake_up_sync_key             0.85%   __sb_start_write
     0.93%   __wake_up_common               0.85%   int_ret_from_sys_call
     0.92%   copy_page_to_iter              0.83%   syscall_trace_leave
     0.90%   check_preempt_wakeup           0.78%   new_sync_read
     0.90%   __srcu_read_lock               0.78%   account_user_time
     0.89%   put_prev_task_fair             0.76%   update_curr
     0.88%   copy_page_from_iter            0.74%   fsnotify
     0.82%   __sb_end_write                 0.73%   try_to_wake_up
     0.76%   __percpu_counter_add           0.71%   finish_task_switch
     0.74%   prepare_to_wait                0.70%   _raw_spin_lock_irq
     0.72%   touch_atime                    0.69%   __wake_up_sync_key
     0.71%   pipe_wait                      0.69%   __tick_nohz_task_switch

pinned endless stat("/", &buf)

    CONFIG_NO_HZ_FULL=y                     CONFIG_NO_HZ_FULL=y, nohz_full=3
    17.13%   system_call                    8.78%   system_call
    11.20%   kmem_cache_alloc               8.52%   native_sched_clock
     7.14%   lockref_get_not_dead           6.02%   context_tracking_user_exit
     7.10%   kmem_cache_free                4.53%   kmem_cache_alloc
     6.42%   path_init                      4.46%   _raw_spin_lock
     5.69%   copy_user_generic_string       4.13%   copy_user_generic_string
     5.25%   lockref_put_or_lock            4.01%   kmem_cache_free
     4.14%   strncpy_from_user              3.36%   context_tracking_user_enter
     3.99%   path_lookupat                  3.25%   lockref_get_not_dead
     3.12%   complete_walk                  3.25%   lockref_put_or_lock
     2.91%   getname_flags                  2.86%   rcu_eqs_enter_common.isra.42
     2.88%   cp_new_stat                    2.84%   path_init
     2.79%   vfs_fstatat                    2.56%   rcu_eqs_exit_common.isra.43
     2.59%   user_path_at_empty             2.52%   int_check_syscall_exit_work
     1.93%   link_path_walk                 2.51%   tracesys
     1.81%   generic_fillattr               2.08%   cp_new_stat
     1.75%   dput                           2.00%   syscall_trace_leave
     1.71%   filename_lookup.isra.50        1.75%   complete_walk
     1.66%   mntput                         1.69%   path_lookupat
     1.45%   vfs_getattr_nosec              1.58%   strncpy_from_user
     1.04%   final_putname                  1.56%   get_vtime_delta
     1.02%   SYSC_newstat                   1.34%   int_with_check

CONFIG_NO_HZ_FULL=y, nohz_full=3

-    8.53%  [kernel]         [k] native_sched_clock                                                                                                                                                                                        ▒
   - native_sched_clock                                                                                                                                                                                                                    ▒
      - 96.76% local_clock                                                                                                                                                                                                                 ▒
         - get_vtime_delta                                                                                                                                                                                                                 ▒
            - 51.95% vtime_account_user                                                                                                                                                                                                    ▒
                 99.96% context_tracking_user_exit                                                                                                                                                                                         ▒
                    syscall_trace_enter                                                                                                                                                                                                    ▒
                    tracesys                                                                                                                                                                                                               ▒
                    __xstat64                                                                                                                                                                                                              ▒
                    __libc_start_main                                                                                                                                                                                                      ▒
            - 48.05% __vtime_account_system                                                                                                                                                                                                ▒
                 99.96% vtime_user_enter                                                                                                                                                                                                   ▒
                    context_tracking_user_enter                                                                                                                                                                                            ▒
                    syscall_trace_leave                                                                                                                                                                                                    ◆
                    int_check_syscall_exit_work                                                                                                                                                                                            ▒
                    __xstat64                                                                                                                                                                                                              ▒
                    __libc_start_main                                                                                                                                                                                                      ▒
      - 3.23% get_vtime_delta                                                                                                                                                                                                              ▒
           52.96% vtime_account_user                                                                                                                                                                                                       ▒
              context_tracking_user_exit                                                                                                                                                                                                   ▒
              syscall_trace_enter                                                                                                                                                                                                          ▒
              tracesys                                                                                                                                                                                                                     ▒
              __xstat64                                                                                                                                                                                                                    ▒
              __libc_start_main                                                                                                                                                                                                            ▒
           47.04% __vtime_account_system                                                                                                                                                                                                   ▒
              vtime_user_enter                                                                                                                                                                                                             ▒
              context_tracking_user_enter                                                                                                                                                                                                  ▒
              syscall_trace_leave                                                                                                                                                                                                          ▒
              int_check_syscall_exit_work                                                                                                                                                                                                  ▒
              __xstat64                                                                                                                                                                                                                    ▒

__libc_start_main

So the delta accounting is much of the pain. Hmmm...

Quoted 1 line · Paul E. McKenney

So the delta accounting is much of the pain. Hmmm...

(overhead picture was incomplete, just fixing that...)

executive summary:

nohz_full=NA cpu=3      604.2 KHz  1.000
nohz_full=3, cpu=3      303.5 KHz   .502
nohz_full=3, cpu=2      460.4 KHz   .761

boring details:

    nohz_full=NA, pipe-test cpu=3           nohz_full=3, pipe-test cpu=3               nohz_full=3, pipe-test cpu=2
    10.45%   __schedule                     8.74%   native_sched_clock                 9.22%   __schedule
    10.03%   system_call                    5.63%   __schedule                         5.29%   system_call
     4.86%   _raw_spin_lock_irqsave         4.75%   _raw_spin_lock                     4.79%   context_tracking_user_exit
     4.51%   __switch_to                    4.35%   reschedule_interrupt               3.81%   _raw_spin_lock_irqsave
     4.31%   copy_user_generic_string       3.91%   _raw_spin_unlock_irqrestore        3.57%   __switch_to
     3.50%   pipe_read                      3.35%   system_call                        3.45%   copy_user_generic_string
     3.02%   pipe_write                     2.73%   context_tracking_user_exit         2.90%   context_tracking_user_enter
     2.76%   mutex_lock                     2.30%   _raw_spin_lock_irqsave             2.86%   pipe_read
     2.30%   native_sched_clock             2.08%   context_tracking_user_enter        2.33%   mutex_lock
     2.27%   copy_page_to_iter_iovec        1.94%   __switch_to                        2.14%   pipe_write
     2.16%   mutex_unlock                   1.88%   copy_user_generic_string           1.89%   copy_page_to_iter_iovec
     2.15%   _raw_spin_unlock_irqrestore    1.80%   account_system_time                1.88%   tracesys
     1.86%   copy_page_from_iter_iovec      1.77%   rcu_eqs_enter_common.isra.42       1.78%   native_sched_clock
     1.85%   vfs_write                      1.60%   pipe_read                          1.70%   mutex_unlock
     1.67%   new_sync_read                  1.58%   pipe_write                         1.68%   _raw_spin_unlock_irqrestore
     1.61%   new_sync_write                 1.39%   mutex_lock                         1.67%   int_check_syscall_exit_work
     1.49%   vfs_read                       1.37%   enqueue_task_fair                  1.54%   __context_tracking_task_switch
     1.47%   fsnotify                       1.25%   rcu_eqs_exit_common.isra.43        1.39%   copy_page_from_iter_iovec
     1.43%   __fget_light                   1.14%   get_vtime_delta                    1.38%   new_sync_read
     1.36%   enqueue_task_fair              1.11%   flat_send_IPI_mask                 1.38%   __tick_nohz_task_switch
     1.28%   finish_task_switch             1.07%   tracesys                           1.37%   syscall_trace_leave
     1.26%   dequeue_task_fair              1.03%   dequeue_task_fair                  1.35%   vfs_write
     1.25%   __sb_start_write               1.01%   copy_page_to_iter_iovec            1.34%   new_sync_write
     1.22%   _raw_spin_lock_irq             1.01%   int_check_syscall_exit_work        1.31%   int_ret_from_sys_call
     1.20%   try_to_wake_up                 0.97%   vfs_write                          1.30%   enqueue_task_fair
     1.16%   update_curr                    0.94%   __context_tracking_task_switch     1.23%   fsnotify
     1.05%   __fsnotify_parent              0.93%   mutex_unlock                       1.22%   finish_task_switch
     1.03%   pick_next_task_fair            0.88%   copy_page_from_iter_iovec          1.14%   vfs_read
     1.02%   sys_write                      0.87%   new_sync_write                     1.12%   _raw_spin_lock_irq
     1.01%   sys_read                       0.86%   __fget_light                       1.08%   dequeue_task_fair
     1.00%   __wake_up_sync_key             0.85%   __sb_start_write                   1.06%   sys_read
     0.93%   __wake_up_common               0.85%   int_ret_from_sys_call              1.04%   int_with_check
     0.92%   copy_page_to_iter              0.83%   syscall_trace_leave                1.02%   update_curr
     0.90%   check_preempt_wakeup           0.78%   new_sync_read                      0.99%   syscall_trace_enter
     0.90%   __srcu_read_lock               0.78%   account_user_time                  0.96%   __fget_light
     0.89%   put_prev_task_fair             0.76%   update_curr                        0.93%   __sb_start_write
     0.88%   copy_page_from_iter            0.74%   fsnotify                           0.89%   copy_page_to_iter
     0.82%   __sb_end_write                 0.73%   try_to_wake_up                     0.87%   try_to_wake_up
     0.76%   __percpu_counter_add           0.71%   finish_task_switch                 0.86%   check_preempt_wakeup
     0.74%   prepare_to_wait                0.70%   _raw_spin_lock_irq                 0.86%   sys_write
     0.72%   touch_atime                    0.69%   __wake_up_sync_key                 0.83%   __fsnotify_parent
     0.71%   pipe_wait                      0.69%   __tick_nohz_task_switch            0.81%   __wake_up_sync_key

Does building with CONFIG_NO_HZ_FULL_SYSIDLE=y slow things down even more? If so, that would give me a rough idea of the cost of RCU's dyntick-idle handling.

Quoted 3 lines · Paul E. McKenney

Does building with CONFIG_NO_HZ_FULL_SYSIDLE=y slow things down even more? If so, that would give me a rough idea of the cost of RCU's dyntick-idle handling.

Nope. Deltas are all down in the statistical frog hair.

kernel/rcu/update.c +7 -0

+		/*
+		 * 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);

Quoted 12 lines · Paul E. McKenney

kernel/rcu/update.c +12 -0

+		/*
+		 * 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 (smp_load_acquire(&t->rcu_tasks_holdout))

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

Quoted 5 lines

kernel/rcu/update.c +5 -0

+					continue;
+				list_del_init(&t->rcu_tasks_holdout_list);
+				/* @@@ need to check for usermode on CPU. */
+			}
+			rcu_read_unlock();

Maybe I missed something. The task @t may already exited and we access to the stale memory here if without patch 8/9.

kernel/rcu/update.c +40 -0

+/* 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;
+		}
+
+		/*
+		 * 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.
+		 */

Quoted 45 lines · Paul E. McKenney

kernel/rcu/update.c +45 -0

+/* 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;
+		}
+
+		/*
+		 * 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();
+		do_each_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				t->rcu_tasks_holdout = 1;

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

Quoted 5 lines

kernel/rcu/update.c +5 -0

+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		} while_each_thread(g, t);
+		rcu_read_unlock();

I think you need for_each_process_thread() to be RCU-safe. while_each_thread() has shown to be racy against exec even with rcu_read_lock().

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.

kernel/rcu/update.c +19 -0

+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);

Quoted 6 lines · Paul E. McKenney

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.

I still hope I will read this series later. Not that I really hope I will understand it ;)

Just one question for now,

Quoted 24 lines

kernel/rcu/update.c +24 -0

+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);

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

Quoted 5 lines

kernel/rcu/update.c +5 -0

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

Why? And I see more flush_signals() in the current kernel/rcu/ code. Unless a kthread does allow_signal() it can't have a pending signal?