Skip to contentSkip to conversation

QRCU with lockless fastpath

PATCH In review Paul E. McKenney 2 participants 2 messages Feb 25, 2007 Sleepable read-copy update (SRCU)

lore
Share & tools
lore
#0 lore raw

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
diff -urpNa -X dontdiff linux-2.6.19/include/linux/srcu.h linux-2.6.19-qrcu-fp/include/linux/srcu.h
@@ -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_struct
 void 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

#1 lore raw
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 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.

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.)

Thanks! This fastpath really improves QRCU.

Oleg.