LinuxLists.cc - RFC: patch to allow lock-free traversal of lists with insertion

[permalink] [raw]

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

> 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,
>
> SYNC is sufficient but way too strict. You don't explicitly say what
> you need to happen. If you need all previous stores to finish
> before all subsequent memory operations then:
>
> membar #StoreStore | #StoreLoad
>
> is sufficient. If you need all previous memory operations to finish
> before all subsequent stores then:
>
> membar #StoreStore | #LoadStore
>
> is what you want.

I need to segregate the stores executed by the CPU doing the membar.
All other CPUs must observe the preceding stores before the following
stores. Of course, this means that the loads on the observing CPUs
must be ordered somehow. I need data dependencies between the loads
to be sufficient to order the loads.

For example, if a CPU executes the following:

a = new_value;
wmbdd();
p = &a;

then i need any other CPU executing:

d = *p;

to see either the value that "p" pointed to before the "p = &a" assignment,
or "new_value", -never- the old value of "a".

Does this do the trick?

membar #StoreStore

> Thoughts?
>
> I think if you need to perform IPIs and junk like that to make the
> memory barrier happen correctly, just throw your code away and use a
> spinlock instead.

The IPIs and related junk are I believe needed only on Alpha, which has
no single memory-barrier instruction that can do wmbdd()'s job. Given
that Alpha seems to be on its way out, this did not seem to me to be
too horrible.

Thanx, Paul

2001-10-09 05:56:00

by David Miller

[permalink] [raw]

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

From: "Paul McKenney" <[email protected]>
Date: Mon, 8 Oct 2001 22:27:44 -0700

All other CPUs must observe the preceding stores before the following
stores.
...
Does this do the trick?

membar #StoreStore

Yes.

The IPIs and related junk are I believe needed only on Alpha, which has
no single memory-barrier instruction that can do wmbdd()'s job. Given
that Alpha seems to be on its way out, this did not seem to me to be
too horrible.

I somehow doubt that you need an IPI to implement the equivalent of
"membar #StoreStore" on Alpha. Richard?

Franks a lot,
David S. Miller
[email protected]

2001-10-09 06:43:45

[permalink] [raw]

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

On Mon, Oct 08, 2001 at 10:56:10PM -0700, David S. Miller wrote:
> I somehow doubt that you need an IPI to implement the equivalent of
> "membar #StoreStore" on Alpha. Richard?

Lol. Of course not. Is someone under the impression that AXP
designers were smoking crack?

"wmb" == "membar #StoreStore".
"mb" == "membar #Sync".

See the nice mb/rmb/wmb macros in <asm/system.h>.

r~

2001-10-09 06:52:06

[permalink] [raw]

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

On Mon, Oct 08, 2001 at 06:55:24PM -0700, Paul E. McKenney wrote:
> 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.

I've discussed this with you before and you continue to have
completely missed the point.

Alpha requires that you issue read-after-read memory barriers on
the reader side if you require ordering between reads. That is
the extent of the weakness of the memory ordering.

Sparc64 is the same way.

This crap will never be applied. Your algorithms are simply broken
if you do not ensure proper read ordering via the rmb() macro.

r~

2001-10-09 07:13:33

[permalink] [raw]

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

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:
>
> http://lse.sourceforge.net/locking/wmbdd.html
>
>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.
>
>Thoughts?
>

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

Balbir

>
>
> Thanx, Paul
>

Attachments:

2001-10-09 07:41:17

by Dipankar Sarma

[permalink] [raw]

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

On Tue, Oct 09, 2001 at 12:43:55PM +0530, BALBIR SINGH wrote:
> 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.

It may if you don't update very often. It depends on your
read-to-write ratio.

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

Either you see the element or you don't. If you want to avoid duplication,
you could do a locked search before inserting it.
Like I said before, lock-less lookups are useful for read-mostly
data. Yes, updates are costly, but if they happen rarely, you still benefit.

Thanks
Dipankar
--
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

2001-10-09 08:21:16

[permalink] [raw]

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

Dipankar Sarma wrote:

>On Tue, Oct 09, 2001 at 12:43:55PM +0530, BALBIR SINGH wrote:
>
>>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.
>>
>
>It may if you don't update very often. It depends on your
>read-to-write ratio.
>
>>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 :-)
>>
>
>Either you see the element or you don't. If you want to avoid duplication,
>you could do a locked search before inserting it.
>Like I said before, lock-less lookups are useful for read-mostly
>data. Yes, updates are costly, but if they happen rarely, you still benefit.
>
How does this compare to the Read-Copy-Update mechanism? Is this just another way of implementing
it, given different usage rules.

Balbir

>
>Thanks
>Dipankar
>

Attachments:

2001-10-09 08:45:36

by Dipankar Sarma

[permalink] [raw]

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

On Tue, Oct 09, 2001 at 01:51:45PM +0530, BALBIR SINGH wrote:
> Dipankar Sarma wrote:
>
> >Either you see the element or you don't. If you want to avoid duplication,
> >you could do a locked search before inserting it.
> >Like I said before, lock-less lookups are useful for read-mostly
> >data. Yes, updates are costly, but if they happen rarely, you still benefit.
> >
> How does this compare to the Read-Copy-Update mechanism? Is this just another way of implementing
> it, given different usage rules.

Fundamentally, yes, RCU is a method for lock-less lookup. It is just
that RCU is elaborate enough to allow you deletion and freeing of
data as well.

Thanks
Dipankar
--
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

2001-10-09 09:09:13

by Rusty Russell

[permalink] [raw]

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

On Mon, 8 Oct 2001 23:52:08 -0700
Richard Henderson <[email protected]> wrote:

> On Mon, Oct 08, 2001 at 06:55:24PM -0700, Paul E. McKenney wrote:
> > 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.
>
> I've discussed this with you before and you continue to have
> completely missed the point.
>
> Alpha requires that you issue read-after-read memory barriers on
> the reader side if you require ordering between reads. That is
> the extent of the weakness of the memory ordering.

Actually, I think you are missing the point. On most architectures, a
writer can do:

int *global_ptr = NULL;

x = 1;
wmb();
global_ptr = &x;

And a reader can rely on the dereference as an implicit read barrier:

if (global_ptr) {
if (*global_ptr != 1)
BUG();
}

This is *not guarenteed* on the Alpha. To quote an earlier offline mail
from Paul McKenney (cc'd to you):

> The case that they said can cause trouble is if the CPU 1's caches are
> partitioned. In such cases, the partitions of the cache run pretty much
> independently. If "p" is in a cacheline handled by one partition, and
> "*p" is in a cacheline handled by the other partition, it is possible
> for the invalidation of "p" (due to the "p = &a") to get processed before
> the invalidation of "*p" (which is just "a", due to the "a = 1").

Now, expecting every piece of code to insert an rmb() before dereferencing
a pointer in these cases, just so Alphas don't fail occasionally is NOT a
good solution. Inventing a "rmb_me_harder()" macro for Alpha only is pretty
horrible too. I don't *like* making Alpha's wmb() stronger, but it is the
only solution which doesn't touch common code.

Of course, we can continue to ignore it, which is my preferred solution.

Hope that helps,
Rusty.
PS. This was used by Alan Cox for lock-free insertion into the firewall linked
list in 2.0 - 2.2, and will become more common.

2001-10-09 16:11:01

[permalink] [raw]

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

On Tue, Oct 09, 2001 at 07:03:37PM +1000, Rusty Russell wrote:
> I don't *like* making Alpha's wmb() stronger, but it is the
> only solution which doesn't touch common code.

It's not a "solution" at all. It's so heavy weight you'd be
much better off with locks. Just use the damned rmb_me_harder.

r~

2001-10-09 16:50:45

[permalink] [raw]

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

> On Mon, Oct 08, 2001 at 10:56:10PM -0700, David S. Miller wrote:
> > I somehow doubt that you need an IPI to implement the equivalent of
> > "membar #StoreStore" on Alpha. Richard?
>
> Lol. Of course not. Is someone under the impression that AXP
> designers were smoking crack?

The ones I have talked to showed no signs of having done so. However,
their architecture -does- make it quite challenging for anyone trying to
write lock-free common code, hence all the IPIs.

> "wmb" == "membar #StoreStore".
> "mb" == "membar #Sync".
>
> See the nice mb/rmb/wmb macros in <asm/system.h>.

OK, if "membar #StoreStore" really is equivalent to "wmb", then
"membar #StoreStore" definitely will -not- do the job required here.
Will "membar #SYNC" allow read-side "membar #ReadRead"s to be omitted,
or does "membar #SYNC" fail to detect when outstanding cache
invalidations complete?

Thanx, Paul

2001-10-09 16:50:54

[permalink] [raw]

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

> On Mon, Oct 08, 2001 at 06:55:24PM -0700, Paul E. McKenney wrote:
> > 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.
>
> I've discussed this with you before and you continue to have
> completely missed the point.

It would not be the first point that I have completely missed, but
please read on. I have discussed this algorithm with Alpha architects,
who tell me that it is sound.

> Alpha requires that you issue read-after-read memory barriers on
> the reader side if you require ordering between reads. That is
> the extent of the weakness of the memory ordering.

I agree that Alpha requires "mb" instructions to be executed on the
reading CPUs if the reading CPUs are to observe some other CPU's writes
occuring in order. And I agree that the usual way that this is done
is to insert "mb" instructions between the reads on the read side.

However, if the reading CPU executes an "mb" instruction between the
time that the writing CPU executes the "wmb" and the time that the writing
CPU executes the second store, then the reading CPU is guaranteed to
see the writes in order. Here is how this happens:

Initial values: a = 0, p = &a, b = 1.

Writing CPU Reading CPU

1) b = 2;

2) Execute "wmb" instruction

3) Send a bunch of IPIs

4) Receive IPI

5) Execute "mb" instruction

6) Indicate completion

7) Detect completion

8) p = &b

The combination of steps 2 and 5 guarantee that the reading CPU will
invalidate the cacheline containing the old value of "b" before it
can possibly reference the new value of "p". The CPU must read "p"
before "b", since it can't know where "p" points before reading it.

> Sparc64 is the same way.

I can believe that "membar #StoreStore" and friends operate in the same
way that the Alpha memory-ordering instructions do. However, some of
the code in Linux seems to rely on "membar #SYNC" waiting for outstanding
invalidations to complete. If this is the case, then "membar #SYNC"
could be used to segregate writes when the corresponding reads are
implicitly ordered by data dependencies, as they are during pointer
dereferences.

> This crap will never be applied. Your algorithms are simply broken
> if you do not ensure proper read ordering via the rmb() macro.

Please see the example above. I do believe that my algorithms are
reliably forcing proper read ordering using IPIs, just in an different
way. Please note that I have discussed this algorithm with Alpha
architects, who believe that it is sound.

But they (and I) may well be confused. If so, could you please
show me what I am missing?

Thanx, Paul

2001-10-09 16:50:45

[permalink] [raw]

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

> From: "Paul McKenney" <[email protected]>
> Date: Mon, 8 Oct 2001 22:27:44 -0700
>
> All other CPUs must observe the preceding stores before the following
> stores.
> ...
> Does this do the trick?
>
> membar #StoreStore
>
> Yes.

Cool! Thank you!!!

> The IPIs and related junk are I believe needed only on Alpha, which
has
> no single memory-barrier instruction that can do wmbdd()'s job. Given
> that Alpha seems to be on its way out, this did not seem to me to be
> too horrible.
>
> I somehow doubt that you need an IPI to implement the equivalent of
> "membar #StoreStore" on Alpha. Richard?

If "membar #StoreStore" is sufficient, then there is no equivalent of
it on Alpha. Neither the "mb" nor the "wmb" instructions wait for
outstanding invalidations to complete, and therefore do -not- guarantee
that reading CPUs will see writes occuring in the order that the writes
occurred on the writing CPU, even if data dependencies force the order
of the reads (as the pointer-dereference example I gave does).

On Alpha, there -must- be an "mb" on the reading CPU if the reading CPU
is to observe the stores in order. The IPIs are just a way of causing
those "mb"s to happen without having code like this:

d = p->a->b;

from having to be written as follows:

q = p->a;
rmb();
d = q->b;

More thoughts?

Thanx, Paul

2001-10-09 16:50:45

by Manfred Spraul

[permalink] [raw]

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

>
> On Tue, Oct 09, 2001 at 07:03:37PM +1000, Rusty Russell wrote:
> > I don't *like* making Alpha's wmb() stronger, but it is the
> > only solution which doesn't touch common code.
>
> It's not a "solution" at all. It's so heavy weight you'd be
> much better off with locks. Just use the damned rmb_me_harder.

rmb_me_harder? smp_mb__{before,after}_{atomic_dec,clear_bit} are already ugly enough.

What about hiding all these details in the list access macros? list_insert, list_get_next, etc. With a default implementation based
on a spinlock, and the capable SMP architectures could define an optimized version.

Then Alpha could do whatever flushing is required. But please do not scatter memory barrier instructions all around the kernel.

--
Manfred

2001-10-09 17:00:34

[permalink] [raw]

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

On Tue, Oct 09, 2001 at 08:45:15AM -0700, Paul McKenney wrote:
> Please see the example above. I do believe that my algorithms are
> reliably forcing proper read ordering using IPIs, just in an different
> way.

I wasn't suggesting that the IPI wouldn't work -- it will.
But it will be _extremely_ slow.

I am suggesting that the lock-free algorithms should add the
read barriers, and that failure to do so indicates that they
are incomplete. If nothing else, it documents where the real
dependancies are.

r~

2001-10-09 18:15:14

[permalink] [raw]

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

> On Tue, Oct 09, 2001 at 08:45:15AM -0700, Paul McKenney wrote:
> > Please see the example above. I do believe that my algorithms are
> > reliably forcing proper read ordering using IPIs, just in an different
> > way.
>
> I wasn't suggesting that the IPI wouldn't work -- it will.
> But it will be _extremely_ slow.

Ah! Please accept my apologies for belaboring the obvious
in my previous emails.

> I am suggesting that the lock-free algorithms should add the
> read barriers, and that failure to do so indicates that they
> are incomplete. If nothing else, it documents where the real
> dependancies are.

Such read barriers are not needed on any architecture where
data dependencies imply an rmb(). Examples include i386, PPC,
and IA64. On these architectures, read-side rmb()s add both
overhead and complexity.

On the completeness, it seems to me that in cases were updates
are rare, the IPIs fill in the gap, and with good performance
benefits. What am I missing here?

Thanx, Paul

2001-10-09 18:15:14

[permalink] [raw]

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

> On Tue, Oct 09, 2001 at 07:03:37PM +1000, Rusty Russell wrote:
> > I don't *like* making Alpha's wmb() stronger, but it is the
> > only solution which doesn't touch common code.
>
> It's not a "solution" at all. It's so heavy weight you'd be
> much better off with locks. Just use the damned rmb_me_harder.

There are a number of cases where updates are extremely rare.
FD management and module unloading are but two examples. In
such cases, the overhead of the IPIs in the extremely rare updates
is overwhelmed by the reduction in overhead in the very common
accesses.

And getting rid of rmb() or rmb_me_harder() makes the read-side
code less complex.

Thanx, Paul

2001-10-10 01:21:47

[permalink] [raw]

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

> The IPIs and related junk are I believe needed only on Alpha, which
has
> no single memory-barrier instruction that can do wmbdd()'s job. Given
> that Alpha seems to be on its way out, this did not seem to me to be
> too horrible.
>
> I somehow doubt that you need an IPI to implement the equivalent of
> "membar #StoreStore" on Alpha. Richard?

I received my copy of the SPARC Architecture Manual (Weaver and Germond)
today.

It turns out that there is -no- equivalent of "membar #StoreStore"
on Alpha, if I am correctly interpreting this manual.

>From section D.4.4, on page 260:

A memory order is legal in RMO if and only if:

(1) X <d Y & L(X) -> X <m Y

[... two other irrelevant cases omitted ...]

Rule (1) states that the RMO model will maintain dependence
when the preceding transaction is a load. Preceding stores
may be delayed in the implementation, so their order may
not be preserved globally.

In the example dereferencing a pointer, we first load the
pointer, then load the value it points to. The second load is
dependent on the first, and the first is a load. Thus, rule (1)
holds, and there is no need for a read-side memory barrier
between the two loads.

This is consistent with the book's definition of
"completion" and the description of the membar
instruction.

In contrast, on Alpha, unless there is an explicit rmb(), data
dependence between a pair of loads in no way forces the two loads
to be ordered. http://lse.sourceforge.net/locking/wmbdd.html
shows how Alpha can get the new value of the pointer, but the
old value of the data it points to. Alpha thus needs the rmb()
between the two loads, even though there is a data dependency.

Am I misinterpreting the SPARC manual?

Thanx, Paul

2001-10-10 01:43:52

by Andrea Arcangeli

[permalink] [raw]

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

On Tue, Oct 09, 2001 at 06:19:49PM -0700, Paul McKenney wrote:
>
> > The IPIs and related junk are I believe needed only on Alpha, which
> has
> > no single memory-barrier instruction that can do wmbdd()'s job. Given
> > that Alpha seems to be on its way out, this did not seem to me to be
> > too horrible.
> >
> > I somehow doubt that you need an IPI to implement the equivalent of
> > "membar #StoreStore" on Alpha. Richard?
>
> I received my copy of the SPARC Architecture Manual (Weaver and Germond)
> today.
>
> It turns out that there is -no- equivalent of "membar #StoreStore"
> on Alpha, if I am correctly interpreting this manual.

The equivalent of "membar #StoreStore" on alpha is be the "wmb" asm
instruction, in linux common code called wmb().

> >From section D.4.4, on page 260:
>
> A memory order is legal in RMO if and only if:
>
> (1) X <d Y & L(X) -> X <m Y
>
> [... two other irrelevant cases omitted ...]
>
> Rule (1) states that the RMO model will maintain dependence
> when the preceding transaction is a load. Preceding stores
> may be delayed in the implementation, so their order may
> not be preserved globally.
>
> In the example dereferencing a pointer, we first load the
> pointer, then load the value it points to. The second load is
> dependent on the first, and the first is a load. Thus, rule (1)
> holds, and there is no need for a read-side memory barrier
> between the two loads.
>
> This is consistent with the book's definition of
> "completion" and the description of the membar
> instruction.
>
> In contrast, on Alpha, unless there is an explicit rmb(), data
> dependence between a pair of loads in no way forces the two loads
> to be ordered. http://lse.sourceforge.net/locking/wmbdd.html
> shows how Alpha can get the new value of the pointer, but the
> old value of the data it points to. Alpha thus needs the rmb()
> between the two loads, even though there is a data dependency.

You remeber I was suprised when you told me alpha needs the rmb despite
of the data dependency :). I thought it wasn't needed (and in turn I
thought we didn't need the wmbdd). I cannot see this requirement
in any alpha specification infact. Are you sure the issue isn't
specific to old cpus or old cache coherency protocols that we can safely
ignore today? I think in SMP systems we care only about ev6 ev67 and
future chips. Also if this can really be reproduced it shouldn't be too
difficult to demonstrate it with a malicious application that stress the
race in loop, maybe somebody (Ivan?) could be interested to write such
application to test.

The IPI just for the rmb within two reads that depends on each other is
just too ugly... But yes, adding rmb() in the reader side looks even
uglier and nobody should really need it.

> Am I misinterpreting the SPARC manual?
>
> Thanx, Paul
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/

Andrea

2001-10-10 01:44:52

by Rusty Russell

[permalink] [raw]

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

In message <[email protected]> you write:
> On Tue, Oct 09, 2001 at 07:03:37PM +1000, Rusty Russell wrote:
> > I don't *like* making Alpha's wmb() stronger, but it is the
> > only solution which doesn't touch common code.
>
> It's not a "solution" at all. It's so heavy weight you'd be
> much better off with locks. Just use the damned rmb_me_harder.

Wow! I'm glad you're volunteering to audit all the kernel code to fix
this Alpha-specific bug by inserting rmb_me_harder() in all the
critical locations!

Don't miss any!

I look forward to seeing your patch,
Rusty.
--
Premature optmztion is rt of all evl. --DK

2001-10-10 02:05:17

by Andrea Arcangeli

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Tue, Oct 09, 2001 at 08:45:15AM -0700, Paul McKenney wrote:
> Please see the example above. I do believe that my algorithms are
> reliably forcing proper read ordering using IPIs, just in an different
> way. Please note that I have discussed this algorithm with Alpha
> architects, who believe that it is sound.

The IPI way is certainly safe.

The point here is that it is suprisingly that alpha needs this IPI
unlike all other architectures. So while the IPI is certainly safe we
wouldn't expect it to be necessary on alpha either.

Now my only worry is that when you worked on this years ago with the
alpha architects there were old chips, old caches and old machines (ev5
maybe?).

So before changing any code, I would prefer to double check with the
current alpha architects that the read dependency really isn't enough to
enforce read ordering without the need of rmb also on the beleeding edge
ev6/ev67/etc.. cores. So potentially as worse we'd need to redefine
wmb() as wmbdd() (and friends) only for EV5+SMP compiles of the kernel,
but we wouldn't be affected with any recent hardware compiling for
EV6/EV67. Jay, Peter, comments?

Andrea

2001-10-10 03:34:14

by Paul Mackerras

[permalink] [raw]

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

Richard Henderson writes:

> I am suggesting that the lock-free algorithms should add the
> read barriers, and that failure to do so indicates that they
> are incomplete. If nothing else, it documents where the real
> dependancies are.

Please, let's not go adding rmb's in places where there is already an
ordering forced by a data dependency - that will hurt performance
unnecessarily on x86, ppc, sparc, ia64, etc.

It seems to me that there are two viable alternatives:

1. Define an rmbdd() which is a no-op on all architectures except for
alpha, where it is an rmb. Richard can then have the job of
finding all the places where an rmbdd is needed, which sounds like
one of the smellier labors of Hercules to me. :)

2. Use Paul McKenney's scheme.

I personally don't really mind which gets chosen. Scheme 1 will
result in intermittent hard-to-find bugs on alpha (since the vast
majority of kernel hackers will not understand where or why rmbdd's
are required), but if Richard prefers that to scheme 2, it's his call
IMHO.

Regards,
Paul.

2001-10-10 05:06:22

by Linus Torvalds

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

In article <[email protected]>,
Andrea Arcangeli <[email protected]> wrote:
>On Tue, Oct 09, 2001 at 08:45:15AM -0700, Paul McKenney wrote:
>> Please see the example above. I do believe that my algorithms are
>> reliably forcing proper read ordering using IPIs, just in an different
>> way. Please note that I have discussed this algorithm with Alpha
>> architects, who believe that it is sound.
>
>The IPI way is certainly safe.

Now, before people get all excited, what is this particular code
actually _good_ for?

Creating a lock-free list that allows insertion concurrently with lookup
is _easy_.

But what's the point? If you insert stuff, you eventually have to remove
it. What goes up must come down. Insert-inane-quote-here.

And THAT is the hard part. Doing lookup without locks ends up being
pretty much worthless, because you need the locks for the removal
anyway, at which point the whole thing looks pretty moot.

Did I miss something?

Linus

2001-10-10 05:17:12

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

Linus Torvalds wrote:

>In article <[email protected]>,
>Andrea Arcangeli <[email protected]> wrote:
>
>>On Tue, Oct 09, 2001 at 08:45:15AM -0700, Paul McKenney wrote:
>>
>>>Please see the example above. I do believe that my algorithms are
>>>reliably forcing proper read ordering using IPIs, just in an different
>>>way. Please note that I have discussed this algorithm with Alpha
>>>architects, who believe that it is sound.
>>>
>>The IPI way is certainly safe.
>>
>
>Now, before people get all excited, what is this particular code
>actually _good_ for?
>
>Creating a lock-free list that allows insertion concurrently with lookup
>is _easy_.
>
>But what's the point? If you insert stuff, you eventually have to remove
>it. What goes up must come down. Insert-inane-quote-here.
>
>And THAT is the hard part. Doing lookup without locks ends up being
>pretty much worthless, because you need the locks for the removal
>anyway, at which point the whole thing looks pretty moot.
>
>Did I miss something?
>
> Linus
>

What about cases like the pci device list or any other such list. Sometimes
you do not care if somebody added something, while you were looking through
the list as long as you do not get illegal addresses or data.
Wouldn't this be very useful there? Most of these lists come up
at system startup and change rearly, but we look through them often.

Me too, Did I miss something?

Balbir

>
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to [email protected]
>More majordomo info at http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at http://www.tux.org/lkml/
>

Attachments:

2001-10-10 05:24:22

by Davide Libenzi

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001, BALBIR SINGH wrote:

> What about cases like the pci device list or any other such list. Sometimes
> you do not care if somebody added something, while you were looking through
> the list as long as you do not get illegal addresses or data.
> Wouldn't this be very useful there? Most of these lists come up
> at system startup and change rearly, but we look through them often.
>
> Me too, Did I miss something?

What means that changes rarely that you're going to use rarely_lock() ?
If you're going to remove even only 1 element in 1000000 jiffies then
you've to lock.
If your list can only grow, that's different.

- Davide

2001-10-10 05:47:18

by Linus Torvalds

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001, BALBIR SINGH wrote:
> >
> >And THAT is the hard part. Doing lookup without locks ends up being
> >pretty much worthless, because you need the locks for the removal
> >anyway, at which point the whole thing looks pretty moot.
>
> What about cases like the pci device list or any other such list. Sometimes
> you do not care if somebody added something, while you were looking through
> the list as long as you do not get illegal addresses or data.
> Wouldn't this be very useful there? Most of these lists come up
> at system startup and change rearly, but we look through them often.

It's not about "change rarely". You cannot use a non-locking lookup if
they _ever_ remove anything.

I can't think of many lists like that. The PCI lists certainly are both
add/remove: cardbus bridges and hotplug-PCI means that they are not just
purely "enumerate at bootup".

Sure, maybe there are _some_ things that don't need to ever be removed,
but I can't think of any interesting data structure off-hand. Truly static
stuff tends to be allocated in an array that is sized once - array lookups
are much faster than traversing a linked list anyway.

So the linked list approach tends to make sense for things that _aren't_
just static, but I don't know of anything that only grows and grows. In
fact, that would sound like a horrible memory leak to me if we had
something like that. Even slow growth is bad if you want up-times measured
in years.

Now, in all fairness I can imagine hacky lock-less removals too. To get
them to work, you have to (a) change the "next" pointer to point to the
next->next (and have some serialization between removals, but removals
only, to make sure you don't have next->next also going away from you) and
(b) leave the old "next" pointer (and thus the data structure) around
until you can _prove_ that nobody is looking anything up any more, and
that the now-defunct data structure can truly be removed.

However, apart from locking, there aren't all that many ways to "prove"
that non-use. You could probably do it with interesting atomic sequence
numbers etc, although by the time you generate atomic sequence numbers
your lookup is already getting heavier - to the point where locking
probably isn't so bad an idea any more.

Linus

2001-10-10 06:00:48

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

Linus Torvalds wrote:

>On Wed, 10 Oct 2001, BALBIR SINGH wrote:
>
>>>And THAT is the hard part. Doing lookup without locks ends up being
>>>pretty much worthless, because you need the locks for the removal
>>>anyway, at which point the whole thing looks pretty moot.
>>>
>>What about cases like the pci device list or any other such list. Sometimes
>>you do not care if somebody added something, while you were looking through
>>the list as long as you do not get illegal addresses or data.
>>Wouldn't this be very useful there? Most of these lists come up
>>at system startup and change rearly, but we look through them often.
>>
>
>It's not about "change rarely". You cannot use a non-locking lookup if
>they _ever_ remove anything.
>
>I can't think of many lists like that. The PCI lists certainly are both
>add/remove: cardbus bridges and hotplug-PCI means that they are not just
>purely "enumerate at bootup".
>

I agree, I just thought of one case quickly. Assume that somebody did a cat /proc/pci.
Meanwhile somebody is adding a new pci device (hotplug PCI) simultaneously (which is very rare).
I would not care if the new device showed up in the output of /proc/pci this time. It would
definitely show up next time. Meanwhile locking the list (just in case it changes) is an
overhead in the case above. I was referring to these cases in my earlier mail.

>
>Sure, maybe there are _some_ things that don't need to ever be removed,
>but I can't think of any interesting data structure off-hand. Truly static
>stuff tends to be allocated in an array that is sized once - array lookups
>are much faster than traversing a linked list anyway.
>
>So the linked list approach tends to make sense for things that _aren't_
>just static, but I don't know of anything that only grows and grows. In
>fact, that would sound like a horrible memory leak to me if we had
>something like that. Even slow growth is bad if you want up-times measured
>in years.
>
>Now, in all fairness I can imagine hacky lock-less removals too. To get
>them to work, you have to (a) change the "next" pointer to point to the
>next->next (and have some serialization between removals, but removals
>only, to make sure you don't have next->next also going away from you) and
>(b) leave the old "next" pointer (and thus the data structure) around
>until you can _prove_ that nobody is looking anything up any more, and
>that the now-defunct data structure can truly be removed.
>
The problem with removals is that somebody could be adding an element simulataneously
to the "next" element. Which might cause problems. I hope I correctly understood
the scenario here.

>
>However, apart from locking, there aren't all that many ways to "prove"
>that non-use. You could probably do it with interesting atomic sequence
>numbers etc, although by the time you generate atomic sequence numbers
>your lookup is already getting heavier - to the point where locking
>probably isn't so bad an idea any more.
>
> Linus
>
>
Balbir

Attachments:

2001-10-10 06:22:15

by Paul Mackerras

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

Linus Torvalds writes:

> And THAT is the hard part. Doing lookup without locks ends up being
> pretty much worthless, because you need the locks for the removal
> anyway, at which point the whole thing looks pretty moot.
>
> Did I miss something?

I believe this all becomes (much more) useful when you are doing
read-copy-update.

There is an assumption that anyone modifying the list (inserting or
deleting) would take a lock first, so the deletion is just a pointer
assignment. Any reader traversing the list (without a lock) sees
either the old pointer or the new, which is fine.

The difficulty is in making sure that no reader is still inspecting
the list element you just removed before you free it, or modify any
field that the reader would be looking at (particularly the `next'
field :). One way of doing that is to defer the free or modification
to a quiescent point. If you have a separate `next_free' field, you
could safely put the element on a list of elements to be freed at the
next quiescent point.

Paul.

2001-10-10 06:31:25

by Linus Torvalds

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001, Paul Mackerras wrote:
>
> There is an assumption that anyone modifying the list (inserting or
> deleting) would take a lock first, so the deletion is just a pointer
> assignment. Any reader traversing the list (without a lock) sees
> either the old pointer or the new, which is fine.

Right, that's not the problem.

> The difficulty is in making sure that no reader is still inspecting
> the list element you just removed before you free it, or modify any
> field that the reader would be looking at (particularly the `next'
> field :).

..which implies _some_ sort of locking, even if it may be deferred.

The locking can be per-CPU, whatever - have a per-CPU count for "this many
traversals in progress", and have every lookup increment it before
starting, and decrement it after stopping.

Then the deleter can actually free the thing once he has seen every CPU go
down to zero, with the proper memory barriers.

Yes, I see that it can work. But it sounds like a _lot_ of complexity for
not very much gain.

Right now, you already have to have eight CPU's to see locking as a large
problem in normal life. People have normal patches to bring that easily up
to 16. Then how much hard-to-debug-with-subtle-memory-ordering-issues code
do you want to handle the few machines that aren't in that range?

I'm just trying to inject a bit of realism here.

Linus

2001-10-10 07:14:01

by Kirill Ratkin

[permalink] [raw]

Subject: kdb requires kallsyms

Hi.

I've trouble with kdb. I've patched my kernel (stable
2.4.10) and tried to make kernel with kdb (from SGI)
and I see :
/bin/sh: /sbin/kallsyms: No such file or directory
make[1]: *** [kallsyms] error 127

Where can I find this kallsyms?

Regards,

__________________________________________________
Do You Yahoo!?
Make a great connection at Yahoo! Personals.
http://personals.yahoo.com

2001-10-10 07:38:17

[permalink] [raw]

Subject: Re: kdb requires kallsyms

Kirill Ratkin wrote:

>Hi.
>
>I've trouble with kdb. I've patched my kernel (stable
>2.4.10) and tried to make kernel with kdb (from SGI)
>and I see :
>/bin/sh: /sbin/kallsyms: No such file or directory
>make[1]: *** [kallsyms] error 127
>
>Where can I find this kallsyms?
>
modutils provides this executable. please use
rpm -q --whatprovides `type <name of file>' to see which package provides
the executable.

Regards,
Balbir

>
>Regards,
>
>
>
>
>
>__________________________________________________
>Do You Yahoo!?
>Make a great connection at Yahoo! Personals.
>http://personals.yahoo.com
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to [email protected]
>More majordomo info at http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at http://www.tux.org/lkml/
>

Attachments:

2001-10-10 07:36:57

by Paul Mackerras

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

2001-10-10 11:54:38

by Keith Owens

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001 05:05:10 +0000 (UTC),
[email protected] (Linus Torvalds) wrote:
>Now, before people get all excited, what is this particular code
>actually _good_ for?
>
>Creating a lock-free list that allows insertion concurrently with lookup
>is _easy_.
>
>But what's the point? If you insert stuff, you eventually have to remove
>it. What goes up must come down. Insert-inane-quote-here.
>
>And THAT is the hard part. Doing lookup without locks ends up being
>pretty much worthless, because you need the locks for the removal
>anyway, at which point the whole thing looks pretty moot.

<pedantic>

It is possible to do completely lock free queue management, I have done
it (once). There are several major requirements :-

* Storage must never change its type (type stable storage). Once a
block has been assigned as struct foo, it must always contain struct
foo. This can be relaxed slightly as long as the data types have a
common header format.

The biggest problem this causes is that storage can never be released
and unmapped. You never know if somebody is going to follow an old
pointer to access storage that you freed. You must put the storage
on a free list for struct foo instead of unmapping it, to maintain
the type stable storage.

* Every piece of code that traverses the data tree for structure foo
must take a copy of each struct foo into local storage. After taking
a copy it must verify that its local copy is self consistent, via
validity indicators in each struct. The validity indicators are
typically generation numbers, whatever you use, the indicators must
be atomically updated and atomically read, with suitable wmb and rmb
barriers for machines with weak memory ordering.

* After following a pointer in your local copy of struct foo to access
another data area, you must verify that the master version of your
local copy has not been changed. If the master copy has changed then
the pointer you just followed is no longer reliable. In almost every
case you have to start the traversal from the beginning. It makes
for very convoluted reader and updater code.

</pedantic>

The only reason I used lock free read and update was to hook into an
existing system that mandated sub second responses. Some of the new
operations that were performed during list traversal and update were
subject to unbounded delays that were completely outside my control. I
could not afford to lock the data structures during traversal because
any delay in the new operations would completely stall the existing
system, also the existing system had to be able to retrieve and delete
data for the new operations at any time.

I don't recommend doing lock free unless you have absolutely no
alternative. It requires convoluted code, it is difficult to debug, it
is expensive on memory bandwidth (forget zero copy) and tends to be
expensive on storage as well.

If you are interested in lock free work, take a look at
http://www.cs.pitt.edu/~moir/papers.html, particularly Practical
Implementations of Non-Blocking Synchronization Primitives. But
beware, that paper has an error which caused intermittent bugs that
took me 5 months to track down. Section 3.3, proc Copy, line 6 should
be

6: y := addr->data[i];

2001-10-10 13:25:28

by Ivan Kokshaysky

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, Oct 10, 2001 at 04:05:02AM +0200, Andrea Arcangeli wrote:
> So before changing any code, I would prefer to double check with the
> current alpha architects that the read dependency really isn't enough to
> enforce read ordering without the need of rmb also on the beleeding edge
> ev6/ev67/etc.. cores. So potentially as worse we'd need to redefine
> wmb() as wmbdd() (and friends) only for EV5+SMP compiles of the kernel,
> but we wouldn't be affected with any recent hardware compiling for
> EV6/EV67. Jay, Peter, comments?

21264 Compiler Writer's Guide [appendix C] explicitly says that the
second load cannot issue if its address depends on a result of previous
load until that result is available. I refuse to believe that it isn't
true for older alphas, especially because they are strictly in-order
machines, unlike ev6.

I suspect some confusion here - probably that architect meant loads
to independent addresses. Of course, in this case mb() is required
to assure ordering.

Ivan.

2001-10-10 13:41:38

by Andrea Arcangeli

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, Oct 10, 2001 at 05:24:31PM +0400, Ivan Kokshaysky wrote:
> On Wed, Oct 10, 2001 at 04:05:02AM +0200, Andrea Arcangeli wrote:
> > So before changing any code, I would prefer to double check with the
> > current alpha architects that the read dependency really isn't enough to
> > enforce read ordering without the need of rmb also on the beleeding edge
> > ev6/ev67/etc.. cores. So potentially as worse we'd need to redefine
> > wmb() as wmbdd() (and friends) only for EV5+SMP compiles of the kernel,
> > but we wouldn't be affected with any recent hardware compiling for
> > EV6/EV67. Jay, Peter, comments?
>
> 21264 Compiler Writer's Guide [appendix C] explicitly says that the
> second load cannot issue if its address depends on a result of previous
> load until that result is available. I refuse to believe that it isn't

Fine, btw I also recall to have read something on those lines, and not
even in the 21264 manual but in the alpha reference manual that would
apply to all the chips but I didn't find it with a short lookup. Thanks
for checking!

> true for older alphas, especially because they are strictly in-order
> machines, unlike ev6.

Yes, it sounds strange. However According to Paul this would not be the
cpu but a cache coherency issue. rmb() would enforce the cache coherency
etc... so maybe the issue is related to old SMP motherboard etc... not
even to the cpus ... dunno. But as said it sounded very strange that
also new chips and new boards have such a weird reodering trouble.

> I suspect some confusion here - probably that architect meant loads
> to independent addresses. Of course, in this case mb() is required
> to assure ordering.
>
> Ivan.

Andrea

2001-10-10 13:42:18

by Justin Piszcz

[permalink] [raw]

Subject: AIC7XXX

I'll try the new one out, but when I tried it out when it was first
introduced into the kernel, it had a lot of errors accessing my SCSI cdrom
drives.

2001-10-10 15:28:18

by Victor Yodaiken

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, Oct 10, 2001 at 11:31:08AM +0530, BALBIR SINGH wrote:
> Linus Torvalds wrote:
> >I can't think of many lists like that. The PCI lists certainly are both
> >add/remove: cardbus bridges and hotplug-PCI means that they are not just
> >purely "enumerate at bootup".
> >
>
> I agree, I just thought of one case quickly. Assume that somebody did a cat /proc/pci.
> Meanwhile somebody is adding a new pci device (hotplug PCI) simultaneously (which is very rare).
> I would not care if the new device showed up in the output of /proc/pci this time. It would
> definitely show up next time. Meanwhile locking the list (just in case it changes) is an
> overhead in the case above. I was referring to these cases in my earlier mail.

So you make the data structure and algorithms more complex and hard to maintain in
order to get an undetectable improvement in the speed of something that almost
never happens and and that is not even in the same neighborhood as being a
bottleneck?

2001-10-10 15:59:48

by Victor Yodaiken

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, Oct 10, 2001 at 05:36:18PM +1000, Paul Mackerras wrote:
> Linus Torvalds writes:
>
> > And THAT is the hard part. Doing lookup without locks ends up being
> > pretty much worthless, because you need the locks for the removal
> > anyway, at which point the whole thing looks pretty moot.
> >
> > Did I miss something?
>
> I believe this all becomes (much more) useful when you are doing
> read-copy-update.
>
> There is an assumption that anyone modifying the list (inserting or
> deleting) would take a lock first, so the deletion is just a pointer
> assignment. Any reader traversing the list (without a lock) sees
> either the old pointer or the new, which is fine.
>
> The difficulty is in making sure that no reader is still inspecting
> the list element you just removed before you free it, or modify any
> field that the reader would be looking at (particularly the `next'
> field :). One way of doing that is to defer the free or modification
> to a quiescent point. If you have a separate `next_free' field, you
> could safely put the element on a list of elements to be freed at the
> next quiescent point.

And the "next quiescent point" must be a synchronization point and that must
have spinlocks around it!
Although I kind of like the idea of
normal operation create mess by avoiding synchronization
when system seems idle, get BKL, and clean up.

>
> Paul.
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/

2001-10-10 17:02:04

[permalink] [raw]

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

On Wed, Oct 10, 2001 at 01:33:58PM +1000, Paul Mackerras wrote:
> 1. Define an rmbdd() which is a no-op on all architectures except for
> alpha, where it is an rmb. Richard can then have the job of
> finding all the places where an rmbdd is needed, which sounds like
> one of the smellier labors of Hercules to me. :)

I don't think it's actually all that bad. There won't be all
that many places that require the rmbdd, and they'll pretty
much exactly correspond to the places in which you have to put
wmb for all architectures anyway.

r~

2001-10-10 21:40:43

by Luigi Genoni

[permalink] [raw]

Subject: Re: AIC7XXX

I had similar problems at the beginning, but now this new driver is well
working, ate less for me.

Luigi

On Wed, 10 Oct 2001, war wrote:

> I'll try the new one out, but when I tried it out when it was first
> introduced into the kernel, it had a lot of errors accessing my SCSI cdrom
> drives.
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>

2001-10-10 21:51:33

[permalink] [raw]

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

> On Wed, Oct 10, 2001 at 01:33:58PM +1000, Paul Mackerras wrote:
> > 1. Define an rmbdd() which is a no-op on all architectures except for
> > alpha, where it is an rmb. Richard can then have the job of
> > finding all the places where an rmbdd is needed, which sounds like
> > one of the smellier labors of Hercules to me. :)
>
> I don't think it's actually all that bad. There won't be all
> that many places that require the rmbdd, and they'll pretty
> much exactly correspond to the places in which you have to put
> wmb for all architectures anyway.

Just to make sure I understand... This rmbdd() would use IPIs to
get all the CPUs' caches synchronized, right? Or do you have some
other trick up your sleeve? ;-)

Thanx, Paul

2001-10-10 21:56:54

by Keith Owens

[permalink] [raw]

Subject: Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001 09:54:36 -0600,
Victor Yodaiken <[email protected]> wrote:
>Although I kind of like the idea of
> normal operation create mess by avoiding synchronization
> when system seems idle, get BKL, and clean up.

That does not work. A process can read an entry from a list then
perform an operation that puts the process to sleep. When it wakes up
again, how can it tell if the list has been changed? How can the
cleanup code tell if any process has slept while it was traversing a
list? An idle system does not prevent processes from sleeping at the
wrong point.

Don't even think of requiring "processes must not sleep while
traversing a lock free list". Programmers cannot get "processes must
not sleep while holding a lock" correct and that error is much easier
to detect.

The inability for update code to know when a lock free list is being
traversed is the reason that most lock free work requires type stable
storage. You can mark a list entry as free and put it on a free chain
but you can never unmap the storage nor use the free entry for data of
a different type. That is the only way to guarantee that a process can
safely determine if the list has changed under it during traversal
while still allowing the process to be interrupted or to sleep.

2001-10-10 22:22:47

[permalink] [raw]

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

On Wed, Oct 10, 2001 at 02:47:05PM -0700, Paul McKenney wrote:
> Just to make sure I understand... This rmbdd() would use IPIs to
> get all the CPUs' caches synchronized, right?

No, it would expand to rmb on Alpha, and to nothing elsewhere.

r~

2001-10-10 22:27:08