* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with
@ 2001-10-12 6:35 Paul McKenney
0 siblings, 0 replies; 5+ messages in thread
From: Paul McKenney @ 2001-10-12 6:35 UTC (permalink / raw)
To: Albert D. Cahalan
Cc: Andrea Arcangeli, cardoza, Peter Rival, Ivan Kokshaysky,
Jay.Estabrook, linux-kernel, lse-tech, Richard Henderson,
woodward
> > Note that they require a memory barrier (rmb()) between the time the
> > item is removed from the queue and the time that the data in the item
> > is referenced, despite the fact that there is a data dependency between
> > the dequeueing and the dereferencing. So, again, data dependency does
> > -not- substitute for an MB on Alpha.
>
> This looks an awful lot like the PowerPC architecture.
IIRC, the PowerPC architecture requires that data dependencies
imply ordering (as does SPARC). Unfortunately, I am currently >1000 km
from my PPC manual, and my eyes just aren't quite what they used to be.
I will look it up when I get back on Monday, and post my findings.
Sorry for the lack of an immediate answer!
> In an SMP system, one would most likely mark pages as
> requiring coherency. This means that stores to a memory
> location from multiple processors will give sane results.
> Ordering is undefined when multiple memory locations are
> involved.
Yep, the eieio and SYNC instructions are used to force
ordering.
> There is a memory barrier instruction called "eieio".
> This is commonly used for IO, but is also useful for RAM.
> Two separate sets of memory operations are simultaneously
> and independently affected by eieio:
>
> -- set one, generally memory-mapped IO space --
> loads to uncached + guarded memory
> stores to uncached + guarded memory
> stores to write-through-required memory
>
> -- set two, generally RAM on an SMP box --
> stores to cached + write-back + coherent
Set two is all we care about for SMP locking algorithms.
People writing drivers sometimes have to worry about
set one, but they often do so by use of locks, thus
avoiding the set-one issues.
> "The eieio instruction is intended for use in managing shared data
> structures ... the shared data structure and the lock that protects
> it must be altered only by stores that are in the same set"
> -- from the 32-bit ppc arch book
Yep! If you map the same physical memory as coherent on one
CPU and uncached on another, you are certainly taking your
chances. There may be a situation where doing this sort of
thing is useful, but I don't know of one.
Thanx, Paul
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion
@ 2001-10-10 15:24 Paul McKenney
2001-10-12 5:43 ` [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Albert D. Cahalan
2001-10-12 6:26 ` Paul Mackerras
0 siblings, 2 replies; 5+ messages in thread
From: Paul McKenney @ 2001-10-10 15:24 UTC (permalink / raw)
To: Andrea Arcangeli
Cc: Peter Rival, Ivan Kokshaysky, Jay.Estabrook, linux-kernel,
lse-tech, Richard Henderson, cardoza, woodward
> > 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.
It sounded strange to me, too. ;-) And my first reading of the
Alpha AXP Archtecture RM didn't help me much.
It was indeed a cache coherency issue. The architect I talked to felt
that it was a feature rather than a bug. I have an email in to him.
In the meantime, Compaq's patent #6,108,737 leads me to believe that
others in DEC/Compaq also believe it to be a feature. The paragraph
starting at column 2 line 20 of the body of this patent states:
In a weakly-ordered system, an order is imposed between selected
sets of memory reference operations, while other operations are
considered unordered. One or more MB instructions are used to
indicate the required order. In the case of an MB instruction
defined by the Alpha (R) 21264 processor instruction set, the MB
denotes that all memory reference instructions above the MB (i.e.,
pre-MB instructions) are ordered before all reference instructions
after the MB (i.e., post-MB instructions). However, no order
is required between reference instructions that are not separated
by an MB.
(The patent talks about the WMB instruction later on.)
In other words, if there is no MB, the CPU is not required to maintain
ordering. Regardless of data dependencies or anything else.
There is also an application note at
http://www.openvms.compaq.com/wizard/wiz_2637.html
which states:
For instance, your producer must issue a "memory barrier" instruction
after writing the data to shared memory and before inserting it on
the queue; likewise, your consumer must issue a memory barrier
instruction after removing an item from the queue and before reading
from its memory. Otherwise, you risk seeing stale data, since,
while the Alpha processor does provide coherent memory, it does
not provide implicit ordering of reads and writes. (That is, the
write of the producer's data might reach memory after the write of
the queue, such that the consumer might read the new item from the
queue but get the previous values from the item's memory.
Note that they require a memory barrier (rmb()) between the time the
item is removed from the queue and the time that the data in the item
is referenced, despite the fact that there is a data dependency between
the dequeueing and the dereferencing. So, again, data dependency does
-not- substitute for an MB on Alpha.
Comments from DEC/Compaq people who know Alpha architecture details?
Thanx, Paul
> > 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
>
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with
2001-10-10 15:24 [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion Paul McKenney
@ 2001-10-12 5:43 ` Albert D. Cahalan
2001-10-12 8:28 ` Alex Bligh - linux-kernel
2001-10-12 8:51 ` Jonathan Lundell
2001-10-12 6:26 ` Paul Mackerras
1 sibling, 2 replies; 5+ messages in thread
From: Albert D. Cahalan @ 2001-10-12 5:43 UTC (permalink / raw)
To: Paul McKenney
Cc: Andrea Arcangeli, Peter Rival, Ivan Kokshaysky, Jay.Estabrook,
linux-kernel, lse-tech, Richard Henderson, cardoza, woodward
Paul McKenney writes:
> In the meantime, Compaq's patent #6,108,737 leads me to believe that
> others in DEC/Compaq also believe it to be a feature. The paragraph
> starting at column 2 line 20 of the body of this patent states:
>
> In a weakly-ordered system, an order is imposed between selected
> sets of memory reference operations, while other operations are
> considered unordered. One or more MB instructions are used to
> indicate the required order. In the case of an MB instruction
> defined by the Alpha (R) 21264 processor instruction set, the MB
> denotes that all memory reference instructions above the MB (i.e.,
> pre-MB instructions) are ordered before all reference instructions
> after the MB (i.e., post-MB instructions). However, no order
> is required between reference instructions that are not separated
> by an MB.
>
> (The patent talks about the WMB instruction later on.)
>
> In other words, if there is no MB, the CPU is not required to maintain
> ordering. Regardless of data dependencies or anything else.
>
> There is also an application note at
>
> http://www.openvms.compaq.com/wizard/wiz_2637.html
>
> which states:
>
> For instance, your producer must issue a "memory barrier" instruction
> after writing the data to shared memory and before inserting it on
> the queue; likewise, your consumer must issue a memory barrier
> instruction after removing an item from the queue and before reading
> from its memory. Otherwise, you risk seeing stale data, since,
> while the Alpha processor does provide coherent memory, it does
> not provide implicit ordering of reads and writes. (That is, the
> write of the producer's data might reach memory after the write of
> the queue, such that the consumer might read the new item from the
> queue but get the previous values from the item's memory.
>
> Note that they require a memory barrier (rmb()) between the time the
> item is removed from the queue and the time that the data in the item
> is referenced, despite the fact that there is a data dependency between
> the dequeueing and the dereferencing. So, again, data dependency does
> -not- substitute for an MB on Alpha.
This looks an awful lot like the PowerPC architecture.
In an SMP system, one would most likely mark pages as
requiring coherency. This means that stores to a memory
location from multiple processors will give sane results.
Ordering is undefined when multiple memory locations are
involved.
There is a memory barrier instruction called "eieio".
This is commonly used for IO, but is also useful for RAM.
Two separate sets of memory operations are simultaneously
and independently affected by eieio:
-- set one, generally memory-mapped IO space --
loads to uncached + guarded memory
stores to uncached + guarded memory
stores to write-through-required memory
-- set two, generally RAM on an SMP box --
stores to cached + write-back + coherent
"The eieio instruction is intended for use in managing shared data
structures ... the shared data structure and the lock that protects
it must be altered only by stores that are in the same set"
-- from the 32-bit ppc arch book
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with
2001-10-12 5:43 ` [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Albert D. Cahalan
@ 2001-10-12 8:28 ` Alex Bligh - linux-kernel
2001-10-12 8:51 ` Jonathan Lundell
1 sibling, 0 replies; 5+ messages in thread
From: Alex Bligh - linux-kernel @ 2001-10-12 8:28 UTC (permalink / raw)
To: Albert D. Cahalan, Paul McKenney
Cc: Andrea Arcangeli, Peter Rival, Ivan Kokshaysky, Jay.Estabrook,
linux-kernel, lse-tech, Richard Henderson, cardoza, woodward,
Alex Bligh - linux-kernel
--On Friday, 12 October, 2001 1:43 AM -0400 "Albert D. Cahalan"
<acahalan@cs.uml.edu> wrote:
> There is a memory barrier instruction called "eieio"
This must be April 1 by some calendar.
With a read/write here, a read/write there... (etc.)
Guess the engineer was called Mr/Ms McDonald.
--
Alex Bligh
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with
2001-10-12 5:43 ` [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Albert D. Cahalan
2001-10-12 8:28 ` Alex Bligh - linux-kernel
@ 2001-10-12 8:51 ` Jonathan Lundell
1 sibling, 0 replies; 5+ messages in thread
From: Jonathan Lundell @ 2001-10-12 8:51 UTC (permalink / raw)
To: Alex Bligh - linux-kernel, Albert D. Cahalan, Paul McKenney
Cc: Andrea Arcangeli, Peter Rival, Ivan Kokshaysky, Jay.Estabrook,
linux-kernel, lse-tech, Richard Henderson, cardoza, woodward,
Alex Bligh - linux-kernel
At 9:28 AM +0100 10/12/01, Alex Bligh - linux-kernel wrote:
>>There is a memory barrier instruction called "eieio"
>
>This must be April 1 by some calendar.
PPC "Enforce In-Order Execution of I/O"
--
/Jonathan Lundell.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with
2001-10-10 15:24 [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion Paul McKenney
2001-10-12 5:43 ` [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Albert D. Cahalan
@ 2001-10-12 6:26 ` Paul Mackerras
1 sibling, 0 replies; 5+ messages in thread
From: Paul Mackerras @ 2001-10-12 6:26 UTC (permalink / raw)
To: Albert D. Cahalan
Cc: Paul McKenney, Andrea Arcangeli, Peter Rival, Ivan Kokshaysky,
Jay.Estabrook, linux-kernel, lse-tech, Richard Henderson,
cardoza, woodward
Albert D. Cahalan writes:
> This looks an awful lot like the PowerPC architecture.
>
> In an SMP system, one would most likely mark pages as
> requiring coherency. This means that stores to a memory
> location from multiple processors will give sane results.
> Ordering is undefined when multiple memory locations are
> involved.
The current PowerPC Architecture spec actually has a paragraph that
says that where a processor does two loads and the second load depends
on the first (i.e. the result from the first load is used in computing
the address for the second load), that they have to be performed in
program order with respect to other processors. In other cases you do
need a barrier as you say.
This constraint has evidently been added since the original PPC
architecture book was published. I strongly doubt that any of the
older PPC implementations would violate that constraint though.
Paul.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2001-10-12 8:52 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-10-12 6:35 [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Paul McKenney
-- strict thread matches above, loose matches on Subject: below --
2001-10-10 15:24 [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion Paul McKenney
2001-10-12 5:43 ` [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with Albert D. Cahalan
2001-10-12 8:28 ` Alex Bligh - linux-kernel
2001-10-12 8:51 ` Jonathan Lundell
2001-10-12 6:26 ` Paul Mackerras
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®