QRCU with lockless fastpath
PATCH 1/1 QRCU with lockless fastpath
Hello!
This is an updated version of Oleg Nesterov's QRCU that avoids the earlier lock acquisition on the synchronize_qrcu() fastpath. This passes rcutorture on x86 and the weakly ordered POWER. A promela model of the code passes as noted before for 2 readers and 3 updaters and for 3 readers and 2 updaters. 3 readers and 3 updaters runs every machine that I have access to out of memory -- nothing like a little combinatorial explosion! However, after some thought, the proof ended up being simple enough:
1. If synchronize_qrcu() exits too soon, then by definition
there has been a reader present during synchronize_srcu()'s full execution.
2. The counter corresponding to this reader will be at least
1 at all times.
3. The synchronize_qrcu() code forces at least one of the counters
to be at least one at all times -- if there is a reader, the sum will be at least two. (Unfortunately, we cannot fetch the pair of counters atomically.)
4. Therefore, the only way that synchronize_qrcu()s fastpath can
see a sum of 1 is if it races with another synchronize_qrcu() -- the first synchronize_qrcu() must read one of the counters before the second synchronize_qrcu() increments it, and must read the other counter after the second synchronize_qrcu() decrements it. There can be at most one reader present through this entire operation -- otherwise, the first synchronize_qrcu() will see a sum of 2 or greater.
5. But the second synchronize_qrcu() will not release the mutex
until after the reader is done. During this time, the first synchronize_qrcu() will always see a sum of at least 2, and therefore cannot take the remainder of the fastpath until the reader is done.
6. Because the second synchronize_qrcu() holds the mutex, no other
synchronize_qrcu() can manipulate the counters until the reader is done. A repeat of the race called out in #4 above therefore cannot happen until after the reader is done, in which case it is safe for the first synchronize_qrcu() to proceed.
Therefore, two summations of the counter separated by a memory barrier suffices and the implementation shown below also suffices.
(And, yes, the fastpath -could- check for a sum of zero and exit immediately, but this would help only in case of a three-way race between two synchronize_qrcu()s and a qrcu_read_unlock(), would add another compare, so is not worth it.)
---
include/linux/srcu.h | 22 +++++++++++++ kernel/srcu.c | 86 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 108 insertions(+)
include/linux/srcu.h +22 -0
@@ -27,6 +27,8 @@#ifndef _LINUX_SRCU_H#define _LINUX_SRCU_H +#include <linux/wait.h> +struct srcu_struct_array {int c[2 ]; };
@@ -50,4 +52,24 @@ void srcu_read_unlock(struct srcu_structvoid synchronize_srcu (struct srcu_struct *sp);long srcu_batches_completed (struct srcu_struct *sp); +/* +* fully compatible with srcu, but optimized for writers. +*/ + +struct qrcu_struct { +int completed; +atomic_t ctr[2 ]; +wait_queue_head_t wq; +struct mutex mutex; +}; + +int init_qrcu_struct (struct qrcu_struct *qp); +int qrcu_read_lock (struct qrcu_struct *qp); +void qrcu_read_unlock (struct qrcu_struct *qp,int idx); +void synchronize_qrcu (struct qrcu_struct *qp); + +static inline void cleanup_qrcu_struct (struct qrcu_struct *qp) +{ +} +#endif
kernel/srcu.c +86 -0
89 lines not on this page · raw message
Quoted 45 lines · Paul E. McKenney
This is an updated version of Oleg Nesterov's QRCU that avoids the earlier lock acquisition on the
synchronize_qrcu()fastpath. This passes rcutorture on x86 and the weakly ordered POWER. A promela model of the code passes as noted before for 2 readers and 3 updaters and for 3 readers and 2 updaters. 3 readers and 3 updaters runs every machine that I have access to out of memory -- nothing like a little combinatorial explosion! However, after some thought, the proof ended up being simple enough:1. If
synchronize_qrcu()exits too soon, then by definition
there has been a reader present during synchronize_srcu()'s full execution.2. The counter corresponding to this reader will be at least
1 at all times.3. The
synchronize_qrcu()code forces at least one of the counters
to be at least one at all times -- if there is a reader, the sum will be at least two. (Unfortunately, we cannot fetch the pair of counters atomically.)4. Therefore, the only way that synchronize_qrcu()s fastpath can
see a sum of 1 is if it races with anothersynchronize_qrcu()-- the firstsynchronize_qrcu()must read one of the counters before the secondsynchronize_qrcu()increments it, and must read the other counter after the secondsynchronize_qrcu()decrements it. There can be at most one reader present through this entire operation -- otherwise, the firstsynchronize_qrcu()will see a sum of 2 or greater.5. But the second
synchronize_qrcu()will not release the mutex
until after the reader is done. During this time, the firstsynchronize_qrcu()will always see a sum of at least 2, and therefore cannot take the remainder of the fastpath until the reader is done.6. Because the second
synchronize_qrcu()holds the mutex, no other
synchronize_qrcu()can manipulate the counters until the reader is done. A repeat of the race called out in #4 above therefore cannot happen until after the reader is done, in which case it is safe for the firstsynchronize_qrcu()to proceed.Therefore, two summations of the counter separated by a memory barrier suffices and the implementation shown below also suffices.
Quoted 6 lines
(And, yes, the fastpath -could- check for a sum of zero and exit immediately, but this would help only in case of a three-way race between two synchronize_qrcu()s and a
qrcu_read_unlock(), would add another compare, so is not worth it.)Signed-off-by Paul E. McKenney <[email protected]>
Thanks! This fastpath really improves QRCU.
Oleg.