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

Paul McKenney (Paul.McKenney@us.ibm.com)
Tue, 9 Oct 2001 11:01:40 -0700


> 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

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