Ticket spinlocks

Seeing algorithms like these come into being is nothing short of beautiful.

Is this an old trick just now brought to the Linux kernel, or something new Nick came up with?

I believe DEC implemented a similar lock queue algorithm in the Topaz operating system for
their Firefly multiprocessor system in the 1980s. I think their system avoided polling the
spinlock, thus eliminating memory bus contention. They had some sort of cascading queue of
locks.

If your spinlocks have this much contention, maybe they should sleep (in a wait queue) instead
of spinning?

Hi, this is Nick,

I must say first that Jon's writeup is very good, much better than my own attempts to explain
the problem/solution! :)

Secondly, I cannot take credit for the basic algorithm. I didn't actually look at any ticket
lock implementations before implementing this one, however the basic idea of implementing a
fifo using a continually incrementing head and tail index is not new at all.

If anything, I might take credit for distilling it down to somewhere close to the optimal x86
implementation. This is based just on the fact that I had a famous CPU designer ask if they
could use it as their company's reference ticket lock assembly sequence! (but I don't consider
myself an x86 guru, so I wouldn't be surprised if someone else coded this up well before me!)

The main trick I use, as Jon's article points to, is to increment the "next" part of the lock
and load the "owner" part in a single instruction. I do this by using 16 bit wide memory
operations on the 8+8 bit wide ticket lock.

The basic implementation of the algorithm would first increment the next part, and then load
the owner part. Doing it like this is probably fine, but it will increase the load on the L1
cache or on some CPUs it might have to invoke the store forwarding logic or even have to stall
until the store exists the store queue.

To answer cpeterso's question, yes in most situations, if you have enough contention on your
lock that starvation is a problem then sure you have a larger problem with your algorithm.
However, what can happen is that you have a common-case-uncontended lock but 0.001% of your
users will actually generate a lot of contention on that lock. Even if the critical section
itself is very tiny, the cost of transferring the lock cacheline will end up being a limiting
factor as the frequency of acquisition and the core count increases. It is, IMO, better to
survive the corner cases gracefully than to squeeze another couple of cycles out of the
algorithm in the case that you expect. (Also don't forget that often sleeping locks are
implemented using a spinlock)

I could easily be mistaken, but I believe it will result in a better kernel. We'll see.

> That raises the maximum system size to 32768 processors. 

hm, why is this a signed 16 bit number when the "small" version of the 
patch uses unsigned 8 bit values? Unsigned 16 bit integers allow up to 
65536 processors...

>That raises the maximum system size to 65536 processors - who could ever want more than that?

SGI.

I think you missed the ironical reference to Bill Gates' alleged comment『640K of memory
should be enough for anybody.』:)

Bill Gates claims this is a urban legend though.

I have to ask...  What happens if a task is interrupted/NMIed/whatever-ed just as its turn
arrives?  Especially given a long-running handler?  Or is this scenario sufficiently rare so
as to have little or no performance impact?

Is that a correct statement? Not an x86 guru but whatever instruction is used to atomically increment the 16bit number is that guaranteed to complete in hw? In other words consider a 16 way processor if all threads incremented simulataneously is there a guarantee all 16 threads increment (in whatever order) or is it possible that on some of them the thread can context switch out before execution. If such is true then it does not guarantee no starvation.

There is also the case for multi-vCPU guests running in a VM.  For regular spinlocks you have
the problem that a guest vCPU may be preempted while holding a spinlock, thereby potentially
causing large delays for other vCPUs (i.e., think spinlock wait times in the order of hundreds
of milliseconds rather than nanoseconds).  A guest vCPU0 is preempted while holding a
spinlock.  Guest vCPU1 is scheduled and spends its whole timeslice wating for the usually
shortly held spinlock to be released; not knowing that the holder of the spinlock is not
really running at the time.

One might argue that it's stupid to run an MP guest system on a single physical processor, but
the above scenario is also present for MP guests running on multiple physical processors.  You
only get around the problem if you perform strict gang-scheduling of all the vCPUs.  The other
option is to add heuristics to prevent prempting guest vCPUs holding spinlocks.

Using ticket spinlocks the problem with preempting lock-holders is increased.  Not only do you
have the problem that preempting a lock-holder is bad for performance, but since all the
waiters must be granted the lock in FIFO order one had better make sure that the different
lock contenders are scheduled in the proper order.  Failure to do so will massively increase
the lock waiting time.  With regular spinlocks you have the chance that any one of the waiting
vCPUs can grab the lock and be done with it quicky.  With ticket spinlocks you don't have this
option.

I would expect that anyone trying to run a multi-MP guest kernel will run into this
performance problem rather quickly (subject to number of vCPUs and kernel workload, of
course).

FINALLY!  I have always wondered why an approach like this wasn't attempted earlier.  This is
the good stuff, my friends.

Not sure what the advantages of the 8-bit or 16-bit version are over putting everything in a 32-bit value. Most of my systems like to talk to RAM in 32-bit chunks (or larger). And all of my linux systems have 32-bit registers (or larger).