Nick,
call me a worry-wart, but I slept on this, and started worrying..
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.
So I'd like you to ask around some CPU people, and get people from both
Intel and AMD to sign off on your spinlocks as safe. I suspect you already
have the required contacts, but if you don't, I can send things off to the
appropriate people at least inside Intel.
Linus
-
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/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
