Travis (travis.downs.delete@this.gmail.com) on August 19, 2018 2:32 pm wrote:
> matthew (nobody.delete@this.example.com) on August 19, 2018 12:51 pm wrote:
> > I think there's a good counter-example to your point, which is the Itanium McKinley implementation
> > of fetchadd. If the line is in L1, the CPU does it. If it's not, the core tells the
> > L2 to do it. Obviously no-one's citing Itanium as a good example of much these days,
> > but I never heard anyone complain about its implementation of atomics.
>
> As far as I can tell McKinley only ever had 1 core, right? So was this some kind
> of optimization for multiple socket machines? The line still had to get back to
> the core, since this is fetch and add, so you always suffer L2 latency?

Yes, the only dual-core-per-socket Itaniums was the Hondo hack which glued two Madisons into a single socket. They didn't even share L3 that I recall. But you have to remember that back in 2002, HP was all about 2-64 socket machines. They weren't optimising for workstations.

> > Let's talk about something that might make sense. A lock is typically on a cacheline which contains other
> > data that is also being operated on. If the lock is uncontended
> > (either no CPU has the cacheline or another
> > CPU has the cacheline in an unlocked state), you want to bring in the cacheline. If the lock is contended,
> > the last thing you want is to steal the cacheline from that CPU; at the very least it wants to access the
> > cacheline again to release the lock, and chances are it's operating on other data in that cacheline.
>
> Definitely, that's one way I can see this working: either with new instructions/hints for the cases the
> developer knows benefit from remote atomics, or some kind of prediction/dynamic behavior. The locking one
> is a good example: right now you have to steal the cache line only to find out that it's locked, maybe
> you could have a type of atomic that leaves the line in place if it is the locked state, since stealing
> it won't be useful anyways. Still, that's not really "remote atomics" because when you do get the lock
> you want to bring it into your cache so that unlock and subsequent lock/unlock pairs are really fast. It's
> more like an optimization of the RFO protocol to embed knowledge of the locking into the probe.

Yes, that's the general direction I'm thinking in.

> Stuff like that doesn't seem to popular though: there is a lot of probably low hanging fruit to
> really optimize locking: for example with some cooperation with the OS scheduler you could avoid
> switching out threads that were in the middle of short, contended critical sections since that ends
> causing a big caravan as all the other threads slam up against the lock before the owning thread
> is scheduled. It seems "easy" to do something like this in a fairly cheap way (e.g,. set a flag
> in the thread control block or something), maybe on an opt-in basis, but it hasn't happened.

Solaris had the ability for a thread to tell the kernel it was holding a mutex and that it shouldn't be preempted until it had dropped the lock. There have been several attempts to add something like that to Linux, but none have succeeded yet. Nothing with hardware assists either.

> > It's fiendishly complicated. It'd almost be better to have a way to transmit a series of operations
> > and have the remote CPU execute them, because there isn't just one way to acquire a lock.
>
> Sure, making it general is tough.
>
> Then you also have to understand what you are saving. The current mechanism is that the waiting
> CPU sends a "message" (a probe) which is snooped by the CPU holding lock, which invalidates its
> copy of the line (without really slowing down), and then the line goes back to the waiting CPU,
> and after that it can perform local operations on it (spinning) until the holding CPU finally
> wants to exit the lock at which point it needs to steal the line back (and then finally the holding
> waiting CPU takes the line back one more time and this time probably gets the lock).

Ah, but the bit you missed is that the cacheline with the lock on it probably also contains data being operated on by the lock owner. So you might well see a flood of coherency traffic as the cacheline transitions from exclusive -> shared -> exclusive -> shared due to all the other CPUs spinning on the cacheline while the owning CPU modifies the cacheline. I believe Intel CPUs (at least) have a hardware optimisation which makes locks more unfair to reduce this traffic, but I know no details.

> Consider sending instructions to a remote CPU to execute. This has the downside of slowing down the very
> CPU that is holding the lock, which is the one agent in the system you don't want to slow down! Also,
> if getting the lock fails, you haven't brought the line back locally, so every time you want to check the
> lock again, you need to interrupt the lock-holding CPU. Add more cores and the problem gets worse.

It depends what your instruction sequence is to acquire the lock. Linux is just "lock cmpxchg" for a spinlock acquire. That's actually fairly easy to handle ... the remote CPU knows whether the cmpxchg succeeded or not and can send the cacheline across:

0000000000000110 :
110: 31 c0 xor %eax,%eax
112: ba 01 00 00 00 mov $0x1,%edx
117: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
11b: 85 c0 test %eax,%eax
11d: 75 01 jne 120
11f: c3 retq

So the requesting CPU only has to send across the contents of %edx and the lock insn. The remote CPU only has to execute the cmpxchg (and that doesn't need much of an ALU!)

Now, that's the fast path. The slow path (ie where the jne leads) does this:

5: ba 01 00 00 00 mov $0x1,%edx
a: 8b 07 mov (%rdi),%eax
c: 85 c0 test %eax,%eax
e: 75 09 jne 19
10: f0 0f b1 17 lock cmpxchg %edx,(%rdi)
14: 85 c0 test %eax,%eax
16: 75 f2 jne a
18: c3 retq
19: f3 90 pause
1b: eb ed jmp a

But if we're going all-out crazy redesign the world, maybe the remote CPU doesn't execute the lock cmpxchg. Maybe we just give the CPU designers one 32-bit word in our data structures and we just have a "spinlock" instruction which ends up being implemented as "the remote CPU does not return the cacheline until you won the lock", and the CPU can use the contents of that word for whatever fair queueing algorithm it wants to use.