Re: RFC: patch to allow lock-free traversal of lists with insertion

Date: Tue Oct 09 2001 - 02:13:55 EST

Paul E. McKenney wrote:

>Request for comments...
>This is a proposal to provide a wmb()-like primitive that enables
>lock-free traversal of lists while elements are concurrently being
>inserted into these lists.
>This is already possible on many popular architectures, but not on
>some CPUs with very weak memory consistency models. See:
>for more details.
>I am particularly interested in comments from people who understand
>the detailed operation of the SPARC membar instruction and the PARISC
>SYNC instruction. My belief is that the membar("#SYNC") and SYNC
>instructions are sufficient, but the PA-RISC 2.0 Architecture book by
>Kane is not completely clear, and I have not yet received my copy of
>the SPARC architecture manual.

1) On Alpha this code does not improve performance since we end up using spinlocks
for my_global_data anyway, I think you already know this. I am a little confused
with the code snippet below

+ spin_lock_irqsave(&mb_global_data.mutex, flags); /* implied mb */
+ if ((mb_global_data.need_mb & this_cpu_mask) == 0) {
+ spin_unlock_irqrestore(&mb_global_data.mutex, flags);
+ return;
+ }
+ mb_global_data.need_mb &= this_cpu_mask;
+ if (mb_global_data.need_mb == 0) {
+ if (++mb_global_data.curgen - mb_global_data.maxgen <= 0) {
+ mb_global_data.need_mb = to_whom;
+ send_ipi_message(to_whom, IPI_MB);
+ }
+ }
+ spin_unlock_irqrestore(&mb_global_data.mutex, flags); /* implied mb */

Are we not checking for the same thing in
                (mb_global_data.need_mb &am
p; this_cpu_mask) == 0

and in
                mb_global_data.need_mb &= this_cpu_mask;
                if (mb_global_data.need_mb == 0) {

In case 1 we return, but in case two we increment the curgen and if curgen is less than
or equal to maxgen then we send IPI's again.

2) What are the rules for incrementing or changing the generation numbers curgen, mygen and
maxgen in your code?

The approach is good, but what are the pratical uses of the approach. Like u mentioned a newly
added element may not show up in the search, searches using this method may have to search again
and there is no way of guaranty that an element that we are looking for will be found (especially
if it is just being added to the list).

The idea is tremendous for approaches where we do not care about elements being newly added.
It should definitely be in the Linux kernel :-)


> Thanx, Paul

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Oct 15 2001 - 21:00:23 EST