[k4st]

A nice simplification of would be to use the current CPU number as your ID. That eliminates the dependence on thread-local storage, and with high probability avoids issues where there are collisions between threads whose IDs modulo N are equivalent.

You could use an instruction like `RDTSC` to extract the CPU number. There might also be ways of getting at it efficiently with glibc/pthreads.

[haberman]

> A nice simplification of would be to use the current CPU number as your ID.

I don't think that works unfortunately. The thread could be rescheduled on a different CPU in the middle of the read-side critical section. When the critical section is exited, it will decrement a different counter. Scan() will wait until every counter is zero, but this will never happen unless another critical section is also rescheduled in the reverse order.

[k4st]

That is fine ;-) Sum up the counters.

[haberman]

I don't think that works. You can't get a consistent view of the counters without a lock. Consider the following scenario:

       CPU1                   CPU2
       ----                   ----
                              T1 rcu_read_lock (+1)
       read counter (0)
       T2 rcu_read_lock (+1)
                              T2 rcu_read_unlock (-1)
                              read counter (0)

We'll find that zero is the sum of all counters, even though T1 is still in its read lock.

[k4st]

Indeed! I think I missed that in the original algorithm it doesn't wait for all slots to be zero, just that each slot go to zero. In that way it is just like waiting for each reader to go through a period of quiescence. This is a lot like the the version of rcu where the writer shuttles itself across cpus to use syscalls returns as a proxy for knowing that a particular cpu is not in any read side critical sections.

If there were a nice way to swap out the counters then summing would work, unfortunately that introduces an even bigger race :-(

Thanks for the correction!