matthew (nobody.delete@this.example.com) on August 19, 2018 7:58 pm wrote:
> Travis (travis.downs.delete@this.gmail.com) on August 19, 2018 2:32 pm wrote:
> > 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.

Yup, I saw that, but it seems like a mis-designed software in that case. In the case your critical section is very short, sure you want to co-locate the data and lock so you can get the line, lock, do your work and unlock, all very quickly and likely before any other core steals the line, except in extreme contention.

In your scenario though the lock is held for a while while the lock holder does work and there is enough contention other threads are spinning on the lock. The best options are to reduce the contention or holding period, but if you can't then in this scenario the lock and data should go on separate lines: let the holding core do its work!

> I believe Intel CPUs (at least) have a hardware
> optimisation which makes locks more unfair to reduce this traffic, but I know no details.

Well lock "fairness" is mostly a consequence of software design, but at a lower level the hardware arbitration for contented cache lines plays a role too: but my impression is that this is largely fair: at least in the sense that line owners always given up their lines essentially immediately when probes occur, and there is also a mechanism to ensure that under contention from multiple cores the line goes around fairly evenly between cores with no starvation (this applies at the line-transfer level only: of course in software you can still experience starvation depending on exactly what you need to do to make progress).

> > 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:
> ...
> 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!)

Yes, I know that a spinlock is very simple in software, but I wasn't saying the lock itself was complex. I was saying the process of sending any instructions to another core to execute on behalf of the sender is complex! Consider that the other core with its giant pipeline full of 100+ instructions in flight, and store buffers full of unretired, retired and senior stores now has to accommodate an external to compute some value atomically, playing by all the memory ordering rules. Consider even the complexity of dealing with the fact that the cores might have totally different page tables (e.g., CR3 values).

The main problem was though that it doesn't scale well: to "spin" every spinning core needs to continually send these remote messages every time it wants to check the lock. It changed the common operation from local to remote.



> 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.

Yeah you do kind of want a user-mode MONITOR/MWAIT for effect spin-free lock handoff. Fair handoff-based locks are pretty unpopular though. Maybe you could abuse XBEGIN/XABORT for it as kind of a message passing/cheap user-mode IPI.