RCU and CONFIG_PREEMPT_RT progress, part 2
Subsystems (3)
RFC 1/1 RCU and CONFIG_PREEMPT_RT progress, part 2
Hello!
More progress on CONFIG_PREEMPT_RT-compatible RCU.
o Earlier this week, declared my CONFIG_PREEMPT_RT education
complete enough to take on a counter-based approach.
o Selected a simple counter-based approach, and created
a Promela model of it, which passes spin. See attached "ctrflipRCU.spin" and "ctrflipRCU.sh" files. The spin analyzer is open-source software, available at
http://spinroot.com/spin/whatispin.html if you want to check it out. Will be running the model by some people here early next week.
o Started prototyping Linux-kernel implementation, initially
in the CONFIG_PREEMPT environment. (Yes, I am still being cowardly!) The implementation is as follows:
o Use a per-CPU pair of counters to track the number
of outstanding RCU read-side critical sections started on the corresponding CPU (though these may have migrated to some other CPU in the meantime).
o In case of a race with the flipping of the counters,
just increment the other counter for the corresponding CPU. This suppresses further counter flips.
o Grace-period advancement depends entirely on
synchronize_rcu() calls. If your workload avoids making any synchronize_kernel() calls (which is not hard to do given that call_rcu() is often used instead of synchronize_rcu()), then RCU will be a big memory leak. (This will be fixed later.)
o In theory, you can "cat /proc/rcugp" to force the
kernel to invoke synchronize_rcu(), but I have not tested this yet, and will not do so until it actually boots. ;-) The long-term fix will likely involve periodic grace-period forcing from a kernel task or from the workqueue environment.
o The rcu_read_lock() and rcu_read_unlock() primitives
still use heavy-weight atomic operations in the common case (avoided only in the case of nested rcu_read_lock() calls). Longer term, I expect to make changes to avoid the atomics in the (hopefully) common case where there is no preemption of RCU read-side critical sections. But simple things first!
o The rcu_read_lock() and rcu_read_unlock() primitives
use memory-barrier instructions. In theory, it is possible to dispense with these, but doing so requires some very strange code. Not clear that this is practical.
o Started running tests in vanilla CONFIG_PREEMPT environment
to check solidity with stock RCU. Will need solid base when stress-test time arrives.
Extremely broken patch included below for your amusement. Feel free to take bets on how much it differs from the eventual working patch. ;-)
Thanx, Paul
arch/i386/Kconfig +13 -0
@@ -523,6 +523,19 @@ config PREEMPT Say Y here if you are building a kernel for a desktop, embedded or real-time system. Say N if you are unsure. +config PREEMPT_RCU + bool "Preemptible RCU read-side critical sections" + default y + help + This option reduces the latency of the kernel when reacting to + real-time or interactive events by allowing a low priority process to + be preempted even if it is in an RCU read-side critical section. + This allows applications to run more reliably even when the system is + under load. + + Say Y here if you enjoy debugging random oopses. + Say N if, for whatever reason, you want your kernel to actually work. + config PREEMPT_BKL bool "Preempt The Big Kernel Lock" depends on PREEMPT
fs/proc/proc_misc.c +17 -0
@@ -549,6 +549,20 @@ void create_seq_entry(char *name, mode_t entry->proc_fops = f; } +#define RCU_STATS + +#ifdef RCU_STATS +int rcu_read_proc_gp (char *page,char **start,off_t off, +int count,int *eof,void *data) +{ +int len; +extern int rcu_read_proc_gp_data (char *page); + + len =rcu_read_proc_gp_data (page); +return proc_calc_metrics (page, start, off, count, eof, len); +} +#endif /* #ifdef RCU_STATS */ +void __init proc_misc_init (void ) {struct proc_dir_entry *entry;
@@ -571,6 +585,9 @@ void __init proc_misc_init(void) {"cmdline", cmdline_read_proc}, {"locks", locks_read_proc}, {"execdomains", execdomains_read_proc}, +#ifdef RCU_STATS + {"rcugp", rcu_read_proc_gp}, +#endif /* #ifdef RCU_STATS */ {NULL,} };for (p = simple_ones; p->name; p++)
include/linux/rcupdate.h +27 -0
@@ -59,6 +59,7 @@ struct rcu_head { } while (0) +#ifndef CONFIG_PREEMPT_RCU /* Global control variables for rcupdate callback mechanism. */ struct rcu_ctrlblk {
@@ -192,6 +193,18 @@ static inline int rcu_pending(int cpu)*/ #define rcu_read_unlock () preempt_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ + +#define rcu_qsctr_inc (cpu) +#define rcu_bh_qsctr_inc (cpu) +#define call_rcu_bh (head, rcu) call_rcu(head, rcu) + +extern void rcu_read_lock (void ); +extern void rcu_read_unlock (void ); +extern int rcu_pending (int cpu); + +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ +/* * So where is rcu_write_lock()? It does not exist, as there is no * way for writers to lock out RCU readers. This is a feature, not
@@ -213,14 +226,22 @@ static inline int rcu_pending(int cpu)* can use just rcu_read_lock(). * */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_lock_bh () local_bh_disable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_lock_bh () { rcu_read_lock(); local_bh_disable(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /* * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section * * See rcu_read_lock_bh() for more information. */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_unlock_bh () local_bh_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_unlock_bh () { local_bh_enable(); rcu_read_unlock(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /** * rcu_dereference - fetch an RCU-protected pointer in an
@@ -238,6 +259,7 @@ static inline int rcu_pending(int cpu) (_________p1); \ }) +/** * rcu_assign_pointer - assign (publicize) a pointer to a newly * initialized structure that will be dereferenced by RCU read-side
@@ -256,6 +278,7 @@ static inline int rcu_pending(int cpu) (p) = (v); \ }) +/** * synchronize_sched - block until all CPUs have exited any non-preemptive * kernel code sequences.
@@ -269,7 +292,11 @@ static inline int rcu_pending(int cpu)* synchronize_kernel() API. In contrast, synchronize_rcu() only * guarantees that rcu_read_lock() sections will have completed. */ +#ifdef CONFIG_PREEMPT_RCU +extern void synchronize_sched (void ); +#else /* #ifdef CONFIG_PREEMPT_RCU */ #define synchronize_sched () synchronize_rcu() +#endif /* #else #ifdef CONFIG_PREEMPT_RCU */ extern void rcu_init (void );extern void rcu_check_callbacks (int cpu,int user);
include/linux/sched.h +5 -0
@@ -740,6 +740,11 @@ struct task_struct {nodemask_t mems_allowed;int cpuset_mems_generation;#endif +#ifdef CONFIG_PREEMPT_RCU +int rcu_read_lock_nesting; +atomic_t *rcu_flipctr1; +atomic_t *rcu_flipctr2; +#endif };static inline pid_t process_group (struct task_struct *tsk)
kernel/rcupdate.c +341 -0
350 lines not on this page · raw message
#define PASSES 10
bit flip = 0;
bit ctr[2];
byte passctr = 0;
proctype rdr()
{
bit lcl_flip;
bit both;
do
:: passctr < PASSES ->
lcl_flip = flip;
/* need smp_read_barrier_depends() */
ctr[lcl_flip]++;
/* need smp_mb__after_atomic_inc() */
if
:: lcl_flip == flip ->
both = 0
:: else ->
ctr[!lcl_flip]++;
/* need smp_mb__after_atomic_inc() */
both = 1
fi;
passctr++;
passctr++;
/* need smp_mb__before_atomic_dec() */
ctr[lcl_flip]--;
if
:: both ->
ctr[!lcl_flip]--;
:: else -> skip
fi;
:: passctr >= PASSES ->
break
od
}proctype upd()
{
byte lcl_passctr;
do
:: passctr < PASSES ->
lcl_passctr = passctr;
if
:: lcl_passctr / 2 * 2 == lcl_passctr ->
lcl_passctr = 255
:: else -> skip
fi;
do
:: ctr[!flip] == 0 -> break
:: true -> skip
od;
/* Need smp_mb()? */
flip = !flip;
/* Need smp_mb()? */
do
:: ctr[!flip] == 0 -> break
:: true -> skip
od;
assert(lcl_passctr != passctr);
:: passctr >= PASSES ->
break
od
}init {
atomic {
ctr[0] = 0;
ctr[1] = 0;
run rdr();
run upd();
}
}Hello!
More progress on CONFIG_PREEMPT_RT-compatible RCU.
o Continued prototyping Linux-kernel implementation, still
in the CONFIG_PREEMPT environment.
o Reasonably reliably boots, still fragile.
o Using workqueues to ensure that grace periods advance
even if synchronize_rcu() is never called. This seems like a bad choice in retrospect, will be recoding to allow per-CPU scheduling-clock tick to advance the grace period. Doing this should simplify the code and eliminate the need for workqueues.
o Numerous boneheaded bugs fixed, a number remain.
o A number of /proc entries provide debug info. These
will likely be removed in the final version.
o Shortcomings remain, will fix once I have flushed out
a few more bugs:
o The rcu_read_lock() and rcu_read_unlock() primitives
still use heavy-weight atomic operations in the common case (avoided only in the case of nested rcu_read_lock() calls). Longer term, I expect to make changes to avoid the atomics in the (hopefully) common case where there is no preemption of RCU read-side critical sections. But simple things first!
o The rcu_read_lock() and rcu_read_unlock() primitives
use memory-barrier instructions. In theory, it is possible to dispense with these, but doing so requires some very strange code. Not clear that this is practical.
o Callbacks are queued globally. Will be changing
to per-CPU callbacks.
Broken patch included below for your amusement.
Thanx, Paul
arch/i386/Kconfig +28 -0
@@ -523,6 +523,34 @@ config PREEMPT Say Y here if you are building a kernel for a desktop, embedded or real-time system. Say N if you are unsure. +config PREEMPT_RCU + bool "Preemptible RCU read-side critical sections" + depends on PREEMPT + default y + help + This option reduces the latency of the kernel when reacting to + real-time or interactive events by allowing a low priority process to + be preempted even if it is in an RCU read-side critical section. + This allows applications to run more reliably even when the system is + under load. + + Say Y here if you enjoy debugging random oopses. + Say N if, for whatever reason, you want your kernel to actually work. + +config RCU_STATS + bool "/proc stats for preemptible RCU read-side critical sections" + depends on PREEMPT_RCU + default y + help + This option provides /proc stats to provide debugging info. + real-time or interactive events by allowing a low priority process to + be preempted even if it is in an RCU read-side critical section. + This allows applications to run more reliably even when the system is + under load. + + Say Y here if you want to see RCU stats in /proc + Say N if you are unsure. + config PREEMPT_BKL bool "Preempt The Big Kernel Lock" depends on PREEMPT
fs/proc/proc_misc.c +48 -0
60 lines not on this page · raw message
include/linux/rcupdate.h +25 -0
@@ -59,6 +59,7 @@ struct rcu_head { } while (0) +#ifndef CONFIG_PREEMPT_RCU /* Global control variables for rcupdate callback mechanism. */ struct rcu_ctrlblk {
@@ -192,6 +193,18 @@ static inline int rcu_pending(int cpu)*/ #define rcu_read_unlock () preempt_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ + +#define rcu_qsctr_inc (cpu) +#define rcu_bh_qsctr_inc (cpu) +#define call_rcu_bh (head, rcu) call_rcu(head, rcu) + +extern void rcu_read_lock (void ); +extern void rcu_read_unlock (void ); +extern int rcu_pending (int cpu); + +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ +/* * So where is rcu_write_lock()? It does not exist, as there is no * way for writers to lock out RCU readers. This is a feature, not
@@ -213,14 +226,22 @@ static inline int rcu_pending(int cpu)* can use just rcu_read_lock(). * */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_lock_bh () local_bh_disable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_lock_bh () { rcu_read_lock(); local_bh_disable(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /* * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section * * See rcu_read_lock_bh() for more information. */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_unlock_bh () local_bh_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_unlock_bh () { local_bh_enable(); rcu_read_unlock(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /** * rcu_dereference - fetch an RCU-protected pointer in an
@@ -269,7 +290,11 @@ static inline int rcu_pending(int cpu)* synchronize_kernel() API. In contrast, synchronize_rcu() only * guarantees that rcu_read_lock() sections will have completed. */ +#ifndef CONFIG_PREEMPT_RCU #define synchronize_sched () synchronize_rcu() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +extern void synchronize_sched (void ); +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ extern void rcu_init (void );extern void rcu_check_callbacks (int cpu,int user);
include/linux/sched.h +5 -0
@@ -740,6 +740,11 @@ struct task_struct {nodemask_t mems_allowed;int cpuset_mems_generation;#endif +#ifdef CONFIG_PREEMPT_RCU +int rcu_read_lock_nesting; +atomic_t *rcu_flipctr1; +atomic_t *rcu_flipctr2; +#endif };static inline pid_t process_group (struct task_struct *tsk)
kernel/rcupdate.c +526 -0
535 lines not on this page · raw message
Quoted 6 lines · Paul E. McKenney
Hello!
More progress on CONFIG_PREEMPT_RT-compatible RCU.
o Continued prototyping Linux-kernel implementation, still
in theCONFIG_PREEMPTenvironment.
cool! With the debugging code removed it doesnt look all that complex. Do you think i can attempt to plug this into the -RT tree, or should i wait some more? (One observation: if you know some branch is slowpath in a common codepath then it's useful to mark the condition via unlikely(). That results in better code layout and is also a guidance for the casual reader of the code.)
Ingo
Quoted 10 lines · Ingo Molnar
Quoted 6 lines · Paul E. McKenney
Hello!
More progress on CONFIG_PREEMPT_RT-compatible RCU.
o Continued prototyping Linux-kernel implementation, still
in theCONFIG_PREEMPTenvironment.
Quoted 6 lines
cool! With the debugging code removed it doesnt look all that complex. Do you think i can attempt to plug this into the -RT tree, or should i wait some more? (One observation: if you know some branch is slowpath in a common codepath then it's useful to mark the condition via
unlikely(). That results in better code layout and is also a guidance for the casual reader of the code.)
I would hold off, as it is still quite fragile. I can make it break quite easily, so it is not yet time to unleash it on all users of CONFIG_PREEMPT_RT.
Good point on the unlikely(), updated the ones checking for races. The checks in rcu_read_lock() and rcu_read_unlock() for racing counter flips seem to be the most important, but I also added them to the checks for concurrent synchronize_rcu() calls, see below.
Thanx, Paul
arch/i386/Kconfig +28 -0
@@ -523,6 +523,34 @@ config PREEMPT Say Y here if you are building a kernel for a desktop, embedded or real-time system. Say N if you are unsure. +config PREEMPT_RCU + bool "Preemptible RCU read-side critical sections" + depends on PREEMPT + default y + help + This option reduces the latency of the kernel when reacting to + real-time or interactive events by allowing a low priority process to + be preempted even if it is in an RCU read-side critical section. + This allows applications to run more reliably even when the system is + under load. + + Say Y here if you enjoy debugging random oopses. + Say N if, for whatever reason, you want your kernel to actually work. + +config RCU_STATS + bool "/proc stats for preemptible RCU read-side critical sections" + depends on PREEMPT_RCU + default y + help + This option provides /proc stats to provide debugging info. + real-time or interactive events by allowing a low priority process to + be preempted even if it is in an RCU read-side critical section. + This allows applications to run more reliably even when the system is + under load. + + Say Y here if you want to see RCU stats in /proc + Say N if you are unsure. + config PREEMPT_BKL bool "Preempt The Big Kernel Lock" depends on PREEMPT
fs/proc/proc_misc.c +48 -0
60 lines not on this page · raw message
include/linux/rcupdate.h +25 -0
@@ -59,6 +59,7 @@ struct rcu_head { } while (0) +#ifndef CONFIG_PREEMPT_RCU /* Global control variables for rcupdate callback mechanism. */ struct rcu_ctrlblk {
@@ -192,6 +193,18 @@ static inline int rcu_pending(int cpu)*/ #define rcu_read_unlock () preempt_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ + +#define rcu_qsctr_inc (cpu) +#define rcu_bh_qsctr_inc (cpu) +#define call_rcu_bh (head, rcu) call_rcu(head, rcu) + +extern void rcu_read_lock (void ); +extern void rcu_read_unlock (void ); +extern int rcu_pending (int cpu); + +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ +/* * So where is rcu_write_lock()? It does not exist, as there is no * way for writers to lock out RCU readers. This is a feature, not
@@ -213,14 +226,22 @@ static inline int rcu_pending(int cpu)* can use just rcu_read_lock(). * */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_lock_bh () local_bh_disable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_lock_bh () { rcu_read_lock(); local_bh_disable(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /* * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section * * See rcu_read_lock_bh() for more information. */ +#ifndef CONFIG_PREEMPT_RCU #define rcu_read_unlock_bh () local_bh_enable() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +#define rcu_read_unlock_bh () { local_bh_enable(); rcu_read_unlock(); } +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ /** * rcu_dereference - fetch an RCU-protected pointer in an
@@ -269,7 +290,11 @@ static inline int rcu_pending(int cpu)* synchronize_kernel() API. In contrast, synchronize_rcu() only * guarantees that rcu_read_lock() sections will have completed. */ +#ifndef CONFIG_PREEMPT_RCU #define synchronize_sched () synchronize_rcu() +#else /* #ifndef CONFIG_PREEMPT_RCU */ +extern void synchronize_sched (void ); +#endif /* #else #ifndef CONFIG_PREEMPT_RCU */ extern void rcu_init (void );extern void rcu_check_callbacks (int cpu,int user);
include/linux/sched.h +5 -0
@@ -740,6 +740,11 @@ struct task_struct {nodemask_t mems_allowed;int cpuset_mems_generation;#endif +#ifdef CONFIG_PREEMPT_RCU +int rcu_read_lock_nesting; +atomic_t *rcu_flipctr1; +atomic_t *rcu_flipctr2; +#endif };static inline pid_t process_group (struct task_struct *tsk)
kernel/rcupdate.c +526 -0
535 lines not on this page · raw message