Skip to content

Prototype RCU usable from idle, exception, offline

Paul E. McKenney lkml rcu stable 4 versions – In review

Get series with b4
b4 am 20200415181856.GA11037@paulmck-ThinkPad-P72

Versions newest first · linked by author and title

  1. v4 Latest38 patches 2 repliesIn review
  2. v3 RFC34 patches 0 repliesSuperseded
  3. v2 RFC22 patches 32 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v1 RFC16 patches23 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/38rcu: Add comments marking transitions between RCU watching and notkernel/rcu/tree.c+25 -40 replies
2/38rcu-tasks: Use context-switch hook for PREEMPT=y kernelskernel/rcu/tree_plugin.h+2 -00 replies
3/38sched/core: Add function to sample state of locked-down taskinclude/linux/wait.h kernel/sched/core.c+50 -00 replies
4/38rcu: Add per-task state to RCU CPU stall warningskernel/rcu/tree_stall.h+36 -20 replies
5/38rcu-tasks: Move Tasks RCU to its own filekernel/rcu/tasks.h kernel/rcu/update.c+372 -3642 replies
6/38rcu-tasks: Create struct to hold state informationkernel/rcu/tasks.h+46 -270 replies
7/38rcu: Reinstate synchronize_rcu_mult()include/linux/rcupdate_wait.h+19 -00 replies
8/38rcutorture: Add a test for synchronize_rcu_mult()kernel/rcu/rcutorture.c+7 -20 replies
9/38rcu-tasks: Refactor RCU-tasks to allow variants to be addedinclude/linux/rcupdate.h kernel/rcu/Kconfig kernel/rcu/tasks.h +1 more+272 -2390 replies
10/38rcu-tasks: Add an RCU-tasks rude variantinclude/linux/rcupdate.h kernel/rcu/Kconfig kernel/rcu/tasks.h+111 -10 replies
11/38rcutorture: Add torture tests for RCU Tasks Rudekernel/rcu/Kconfig.debug kernel/rcu/rcu.h kernel/rcu/rcutorture.c +3 more+44 -20 replies
12/38rcu-tasks: Use unique names for RCU-Tasks kthreads and messageskernel/rcu/tasks.h+16 -90 replies
13/38rcu-tasks: Further refactor RCU-tasks to allow adding more variantskernel/rcu/tasks.h+108 -580 replies
14/38rcu-tasks: Code movement to allow more Tasks RCU variantskernel/rcu/tasks.h+63 -590 replies
15/38rcu-tasks: Add an RCU Tasks Trace to simplify protection of tracing hooksinclude/linux/rcupdate_trace.h include/linux/sched.h init/init_task.c +3 more+463 -50 replies
16/38rcutorture: Add torture tests for RCU Tasks Tracekernel/rcu/Kconfig.debug kernel/rcu/rcu.h kernel/rcu/rcutorture.c +3 more+58 -10 replies
17/38rcu-tasks: Add stall warnings for RCU Tasks Tracekernel/rcu/tasks.h+66 -40 replies
18/38rcu-tasks: Move #ifdef into tasks.hkernel/rcu/tasks.h kernel/rcu/update.c+5 -40 replies
19/38rcu-tasks: Add RCU tasks to rcutorture writer stall outputkernel/rcu/rcu.h kernel/rcu/tasks.h kernel/rcu/tree_stall.h+45 -30 replies
20/38rcu-tasks: Make rcutorture writer stall output include GP statekernel/rcu/tasks.h+72 -50 replies
21/38rcu-tasks: Make RCU Tasks Trace make use of RCU scheduler hooksinclude/linux/rcupdate.h include/linux/rcutiny.h kernel/rcu/tasks.h +1 more+43 -140 replies
22/38rcu-tasks: Add a grace-period start time for throttling and debugkernel/rcu/tasks.h+2 -00 replies
23/38rcu-tasks: Provide boot parameter to delay IPIs until late in grace periodDocumentation/admin-guide/kernel-parameters.txt kernel/rcu/tasks.h+17 -50 replies
24/38rcu-tasks: Split ->trc_reader_need_endinclude/linux/rcupdate_trace.h include/linux/sched.h init/init_task.c +2 more+31 -190 replies
25/38rcu-tasks: Add grace-period and IPI counts to statisticskernel/rcu/tasks.h+9 -10 replies
26/38rcu-tasks: Add Kconfig option to mediate smp_mb() vs. IPIinclude/linux/rcupdate_trace.h kernel/rcu/Kconfig kernel/rcu/tasks.h+22 -20 replies
27/38rcu-tasks: Avoid IPIing userspace/idle tasks if kernel is so builtkernel/rcu/rcu.h kernel/rcu/tasks.h kernel/rcu/tree.c +2 more+72 -100 replies
28/38rcu-tasks: Allow rcu_read_unlock_trace() under scheduler lockskernel/rcu/tasks.h kernel/rcu/update.c+12 -10 replies
29/38rcu-tasks: Disable CPU hotplug across RCU tasks trace scanskernel/rcu/tasks.h+14 -40 replies
30/38rcu-tasks: Handle the running-offline idle-task special casekernel/rcu/tasks.h+6 -20 replies
31/38rcu-tasks: Make RCU tasks trace also wait for idle taskskernel/rcu/tasks.h+13 -50 replies
32/38rcu-tasks: Add rcu_dynticks_zero_in_eqs() effectiveness statisticskernel/rcu/tasks.h+11 -20 replies
33/38rcu-tasks: Add count for idle tasks on offline CPUskernel/rcu/tasks.h+5 -10 replies
34/38rcutorture: Add TRACE02 scenario enabling RCU Tasks Trace IPIstools/testing/selftests/rcutorture/configs/rcu/CFLIST tools/testing/selftests/rcutorture/configs/rcu/TRACE01 tools/testing/selftests/rcutorture/configs/rcu/TRACE02 +1 more+14 -00 replies
35/38rcu-tasks: Add IPI failure count to statisticskernel/rcu/tasks.h+7 -40 replies
36/38rcu-tasks: Allow standalone use of TASKS_{TRACE_,}RCUkernel/rcu/tasks.h+30 -240 replies
37/38ftrace: Use synchronize_rcu_tasks_rude() instead of ftrace_sync()kernel/trace/Kconfig kernel/trace/ftrace.c+4 -140 replies
38/38rcu: Don't acquire lock in NMI handler in rcu_nmi_enter_common()kernel/rcu/tree.c+1 -10 replies

Reviews trailers per patch

2 of 38 patches have a Reviewed-by or Acked-by.

PatchJoel Fernandes (Google)Steven Rostedt (VMware)
1/38
2/38
3/38R-b R-b
4/38
5/38
6/38
7/38
8/38
9/38
10/38
11/38
12/38
13/38
14/38
15/38
16/38
17/38
18/38
19/38
20/38
21/38
22/38
23/38
24/38
25/38
26/38
27/38
28/38
29/38
30/38
31/38
32/38
33/38
34/38
35/38
36/38
37/38
38/38R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 tip/core/rcu 0/38] Prototype RCU usable from idle, exception, offline

Hello!

This series provides a non-RFC posting for two variants of Tasks RCU, a rude variant inspired by Steven Rostedt's use of schedule_on_each_cpu(), and a tracing variant requested by the BPF folks to be used (for example) to protect BPF programs that unconditionally access userspace memory, and thus might occasionally take a page fault, resulting in a voluntary context switch.

The rude variant uses context switches and offline as its quiescent states, so that preempt-disabled regions of code executing on online CPUs form the tasks rude RCU readers.

The tracing variant has explicit read-side markers to permit finite grace periods even given in-kernel loops in PREEMPT=n builds. These markers are rcu_read_lock_trace() and rcu_read_unlock_trace(), so that any code not under rcu_read_lock_trace() is a quiescent state. This variant also protects marked code in the idle loop, on exception entry/exit paths, and on the various CPU-hotplug online/offline code paths, thus having protection properties similar to SRCU. However, unlike SRCU, this variant avoids expensive instructions in the read-side primitives, thus having read-side overhead similar to that of preemptible RCU. This difference is important for some BPF programs, according to benchmarking from Alexei Starovoitov:

https://lore.kernel.org/lkml/20200310014043.4dbagqbr2wsbuarm@ast-mbp/

There are of course downsides. The grace-period code can send IPIs to CPUs, even when those CPUs are in the idle loop or in nohz_full userspace. However, this version enlists the aid of the context-switch hooks, which eliminates the need for IPIs in context-switch-heavy workloads. It also prohibits sending of IPIs early in the grace period based on a new rcupdate.rcu_task_ipi_delay kernel boot parameter, which provides additional opportunity for the hooks to do their job. Finally, a new TASKS_TRACE_RCU_READ_MB Kconfig option avoids sending IPIs to tasks executing userspace or in the idle loop, at the expense of higher overhead readers during kernel entry/exit code and in the idle loop.

It is also necessary to scan the full tasklist, much as for Tasks RCU. There is a single callback queue guarded by a single lock, again, much as for Tasks RCU. If needed, these downsides can be at least partially remedied.

Perhaps most important, this variant of RCU does not affect the vanilla flavors, rcu_preempt and rcu_sched. The fact that RCU Tasks Trace readers can operate from idle, offline, and exception entry/exit in no way allows rcu_preempt and rcu_sched readers to also do so.

The RCU tasks trace mechanism is based off of RCU tasks rather than SRCU because the latter is more complex and also because the latter uses a CPU-by-CPU approach to tracking quiescent states instead of the task-by-task approach that is needed. It is in theory possible to mash RCU tasks trace into the Tree SRCU implementation, but there will need to be extremely good reasons for doing so. The vanilla RCU mechanism could in theory be used in CONFIG_PREEMPT=y kernels, but fails utterly in CONFIG_PREEMPT=n kernels. Tasks RCU does not work because page faults can result in a voluntary context switch, which prevents it from protecting a BPF program that page faults. The new "rude" variant only protected preempt-disable regions of code, thus also failing to protect BPF programs that page fault.

This effort benefited greatly from off-list discussions of BPF requirements with Alexei Starovoitov and Andrii Nakryiko, as well as from numerous on-list discussions, at least some of which are captured in the "Link:" tags on the patches themselves.

The patches in this series are as follows, with asterisks indicating significant change from v3:

1*. Add comments marking transitions between RCU watching and not.

2*. rcu-tasks: Use context-switch hook for PREEMPT=y kernels.

3. sched/core: Add function to sample state of locked-down task.

4. Add per-task state to RCU CPU stall warnings.

5. rcu-tasks: Move Tasks RCU to its own file.

6. rcu-tasks: Create struct to hold state information.

7. Reinstate synchronize_rcu_mult().

8. Add a test for synchronize_rcu_mult().

9. rcu-tasks: Refactor RCU-tasks to allow variants to be added.

10. rcu-tasks: Add an RCU-tasks rude variant.

11. Add torture tests for RCU Tasks Rude.

12. rcu-tasks: Use unique names for RCU-Tasks kthreads and messages.

13. rcu-tasks: Further refactor RCU-tasks to allow adding more variants.

14. rcu-tasks: Code movement to allow more Tasks RCU variants.

15. rcu-tasks: Add an RCU Tasks Trace to simplify protection of
tracing hooks.

16. Add torture tests for RCU Tasks Trace.

17. rcu-tasks: Add stall warnings for RCU Tasks Trace.

18. rcu-tasks: Move #ifdef into tasks.h.

19. rcu-tasks: Add RCU tasks to rcutorture writer stall output.

20. rcu-tasks: Make rcutorture writer stall output include GP state.

21. rcu-tasks: Make RCU Tasks Trace make use of RCU scheduler hooks.

22. rcu-tasks: Add a grace-period start time for throttling and debug.

23. rcu-tasks: Provide boot parameter to delay IPIs until late in
grace period.

24. rcu-tasks: Split ->trc_reader_need_end.

25. rcu-tasks: Add grace-period and IPI counts to statistics.

26. rcu-tasks: Add Kconfig option to mediate smp_mb() vs. IPI.

27. rcu-tasks: Avoid IPIing userspace/idle tasks if kernel is so built.

28. rcu-tasks: Allow rcu_read_unlock_trace() under scheduler locks.

29. rcu-tasks: Disable CPU hotplug across RCU tasks trace scans.

30. rcu-tasks: Handle the running-offline idle-task special case.

31. rcu-tasks: Make RCU tasks trace also wait for idle tasks.

32. rcu-tasks: Add rcu_dynticks_zero_in_eqs() effectiveness statistics.

33. rcu-tasks: Add count for idle tasks on offline CPUs.

34. Add TRACE02 scenario enabling RCU Tasks Trace IPIs.

35. rcu-tasks: Add IPI failure count to statistics.

36*. rcu-tasks: Allow standalone use of TASKS_{TRACE_,}RCU.

37*. Use synchronize_rcu_tasks_rude() instead of ftrace_sync().

38*. Don't acquire lock in NMI handler in rcu_nmi_enter_common().

This code has passed serious rcutorture testing. It should therefore be ready for production use (famous last words!).

Changes since v3:

o Fix #ifdef issues preventing standalone use of RCU tasks rude.

o Apply RCU tasks rude to ftrace.

o Added commit enabling the RCU-tasks context-switch hook for
PREEMPT=y kernels.

o Prevent rcu_nmi_enter_common() from acquiring locks within NMI
handlers. (Added due to inter-commit dependencies.)

o Comment the transitions between RCU watching and not. (Also added
due ot inter-commit dependencies.)

Changes since v2:

o Leveraged idle entry/exit hooks to reduce IPIing of idle and
userspace tasks.

o Switch to read-side memory barriers during idle and userspace
execution in kernels built for real-time or battery-powered use, mediated by a new TASKS_TRACE_RCU_READ_MB Kconfig option. Also add an rcutorture test scenario for this option.

o Adjust rcutorture to better test the IPI path. (Seeing zero IPIs
might be satisfying to me personally, but it is a lousy test strategy!)

o Added more information to stall warnings and rcutorture
end-of-test printout.

o Make rcu_read_unlock_trace() usable when invoked with
scheduler locks held.

o Make rcu_read_unlock_trace() usable in interrupt and NMI
handlers.

o Fix handling of idle tasks, including those "running" on
offline CPUs.

o Fixed a number of other bugs found during testing and responded
to review feedback.

Changes since v1:

o Updated this cover letter to provide more detail, including
on roads not taken.

o Updated commit logs based on feedback from v1.

o Updated the function providing a consistent view of the
specified non-running task's state to invoke the specified function even if the task is currently running. This will be necessary to safely eliminate IPIs for long-term idle and userspace execution. The function may also now return false to transmit a failure indication to the caller, for example, if the function cannot handle being invoked on a running CPU. The function is now passed the relevant task_struct pointer as well as the specified argument.

Changes were of course made to use the new API.

o Leveraged context-switch hooks to avoid unnecessary IPIs.

o Held off IPIs for the first half second (by default) of each
grace period to give the context-switch hooks a better chance to do their job.

o Lots of testing.

o Fixed a number of bugs and responded to v2 feedback.

Thanx, Paul

------------------------------------------------------------------------

 Documentation/admin-guide/kernel-parameters.txt             |    7 
 include/linux/rcupdate.h                                    |   53 
 include/linux/rcupdate_trace.h                              |   98 
 include/linux/rcupdate_wait.h                               |   19 
 include/linux/rcutiny.h                                     |    2 
 include/linux/sched.h                                       |   12 
 include/linux/wait.h                                        |    2 
 init/init_task.c                                            |    5 
 kernel/fork.c                                               |    5 
 kernel/rcu/Kconfig                                          |   50 
 kernel/rcu/Kconfig.debug                                    |    4 
 kernel/rcu/rcu.h                                            |    5 
 kernel/rcu/rcutorture.c                                     |   84 
 kernel/rcu/tasks.h                                          | 2143 +++++++++---
 kernel/rcu/tree.c                                           |   55 
 kernel/rcu/tree.h                                           |    2 
 kernel/rcu/tree_plugin.h                                    |   26 
 kernel/rcu/tree_stall.h                                     |   40 
 kernel/rcu/update.c                                         |  375 --
 kernel/sched/core.c                                         |   48 
 kernel/trace/Kconfig                                        |    1 
 kernel/trace/ftrace.c                                       |   17 
 tools/testing/selftests/rcutorture/configs/rcu/CFLIST       |    3 
 tools/testing/selftests/rcutorture/configs/rcu/RUDE01       |   10 
 tools/testing/selftests/rcutorture/configs/rcu/RUDE01.boot  |    1 
 tools/testing/selftests/rcutorture/configs/rcu/TRACE01      |   11 
 tools/testing/selftests/rcutorture/configs/rcu/TRACE01.boot |    1 
 tools/testing/selftests/rcutorture/configs/rcu/TRACE02      |   11 
 tools/testing/selftests/rcutorture/configs/rcu/TRACE02.boot |    1 
 29 files changed, 2193 insertions(+), 898 deletions(-)