Do two parity flip in the writer to fix race condition

On Sat, Feb 07, 2009 at 07:10:28AM -0800, Paul E. McKenney wrote:
> So, how to fix?  Here are some approaches:
>
> o     Make urcu_publish_content() do two parity flips rather than one.
>       I use this approach in my rcu_rcpg, rcu_rcpl, and rcu_rcpls
>       algorithms in CodeSamples/defer.
>
> o     Use a single free-running counter, in a manner similar to rcu_nest,
>       as suggested earlier.  This one is interesting, as I rely on a
>       read-side memory barrier to handle the long-preemption case.
>       However, if you believe that any thread that waits several minutes
>       between executing adjacent instructions must have been preempted
>       (which the memory barriers that are required to do a context
>       switch), then a compiler barrier suffices.  ;-)
>
> Of course, the probability of seeing this failure during test is quite
> low, since it is unlikely that thread 0 would run just long enough to
> execute its signal handler.  However, it could happen.  And if you were
> to adapt this algorithm for use in a real-time application, then priority
> boosting could cause this to happen naturally.

And here is a patch, taking the first approach.  It also exposes a
synchronize_rcu() API that is used by the existing urcu_publish_content()
API.  This allows easier handling of structures that are referenced by
more than one pointer.  And should also allow to be more easily plugged
into my rcutorture test.  ;-)

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

diff --git a/urcu.c b/urcu.c
index e401d8dc75d34bf04d2e62da56df3cc08f0d470d..1a276ce33663439b7cb128e1ab6bea147faec1ed 100644 (file)
--- a/urcu.c
+++ b/urcu.c
@@ -113,13 +113,35 @@ void wait_for_quiescent_state(int parity)
        force_mb_all_threads();
 }
 
+static void switch_qparity(void)
+{
+       int prev_parity;
+
+       /* All threads should read qparity before accessing data structure. */
+       /* Write ptr before changing the qparity */
+       force_mb_all_threads();
+       prev_parity = switch_next_urcu_qparity();
+
+       /*
+        * Wait for previous parity to be empty of readers.
+        */
+       wait_for_quiescent_state(prev_parity);
+}
+
+void synchronize_rcu(void)
+{
+       rcu_write_lock();
+       switch_qparity();
+       switch_qparity();
+       rcu_write_unlock();
+}
+
 /*
  * Return old pointer, OK to free, no more reference exist.
  * Called under rcu_write_lock.
  */
 void *urcu_publish_content(void **ptr, void *new)
 {
-       int prev_parity;
        void *oldptr;
 
        /*
@@ -134,19 +156,10 @@ void *urcu_publish_content(void **ptr, void *new)
         */
        oldptr = *ptr;
        *ptr = new;
-       /* All threads should read qparity before ptr */
-       /* Write ptr before changing the qparity */
-       force_mb_all_threads();
-       prev_parity = switch_next_urcu_qparity();
 
-       /*
-        * Wait for previous parity to be empty of readers.
-        */
-       wait_for_quiescent_state(prev_parity);
-       /*
-        * Deleting old data is ok !
-        */
-       
+       switch_qparity();
+       switch_qparity();
+
        return oldptr;
 }