On Wed, 27 Jun 2007, Linus Torvalds wrote:

quoted text
> On Tue, 26 Jun 2007, Linus Torvalds wrote:
> > 
> > So try it with just a byte counter, and test some stupid micro-benchmark 
> > on both a P4 and a Core 2 Duo, and if it's in the noise, maybe we can make 
> > it the normal spinlock sequence just because it isn't noticeably slower.
> 
> So I thought about this a bit more, and I like your sequence counter 
> approach, but it still worried me.
> 
> In the current spinlock code, we have a very simple setup for a 
> successful grab of the spinlock:
> 
> 	CPU#0					CPU#1
> 
> 	A (= code before the spinlock)
> 						lock release
> 
> 	lock decb mem	(serializing instruction)
> 
> 	B (= code after the spinlock)
> 
> and there is no question that memory operations in B cannot leak into A.
> 
> With the sequence counters, the situation is more complex:
> 
> 	CPU #0					CPU #1
> 
> 	A (= code before the spinlock)
> 
> 	lock xadd mem	(serializing instruction)
> 
> 	B (= code afte xadd, but not inside lock)
> 
> 						lock release
> 
> 	cmp head, tail
> 
> 	C (= code inside the lock)
> 
> Now, B is basically the empty set, but that's not the issue I worry about. 
> The thing is, I can guarantee by the Intel memory ordering rules that 
> neither B nor C will ever have memops that leak past the "xadd", but I'm 
> not at all as sure that we cannot have memops in C that leak into B!
> 
> And B really isn't protected by the lock - it may run while another CPU 
> still holds the lock, and we know the other CPU released it only as part 
> of the compare. But that compare isn't a serializing instruction!
> 
> IOW, I could imagine a load inside C being speculated, and being moved 
> *ahead* of the load that compares the spinlock head with the tail! IOW, 
> the load that is _inside_ the spinlock has effectively moved to outside 
> the protected region, and the spinlock isn't really a reliable mutual 
> exclusion barrier any more!
> 
> (Yes, there is a data-dependency on the compare, but it is only used for a 
> conditional branch, and conditional branches are control dependencies and 
> can be speculated, so CPU speculation can easily break that apparent 
> dependency chain and do later loads *before* the spinlock load completes!)
> 
> Now, I have good reason to believe that all Intel and AMD CPU's have a 
> stricter-than-documented memory ordering, and that your spinlock may 
> actually work perfectly well. But it still worries me. As far as I can 
> tell, there's a theoretical problem with your spinlock implementation.

Nice catch ;) But wasn't Intel suggesting in not relying on the old 
"strict" ordering rules? IOW shouldn't an mfence always be there? Not only 
loads could leak up into the wait phase, but stores too, if they have no 
dependency with the "head" and "tail" loads.



- Davide


-
unsubscribe notice
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/