I think a simple spinlock that doesn't have any of the really major / obvious performance problems on x86 is something like this. Of course a real mutex implementation would use a system call (like Linux futex) after spinning for a while, and unlocking would have to check if it needs to notify any waiters with another system call. This is important; you don't want to spin forever wasting CPU time (and energy / heat) doing nothing. But conceptually this is the spin part of a mutex before you take the fallback path. It's an important piece of how light-weight locking is implemented. (Only attempting to take the lock once before calling the kernel would be a valid choice, instead of spinning at all.)
Implement as much of this as you like in inline asm, or preferably using C11 stdatomic, like this semaphore implementation. This is NASM syntax. If using GNU C inline asm, make sure you use a "memory" clobber to stop compile-time reordering of memory access. But don't use inline asm; use C _Atomic uint8_t or C++ std::atomic<uint8_t> with .exchange(1, std::memory_order_acquire) and .store(0, std::memory_order_release), and _mm_pause() from immintrin.h.
;;; UNTESTED ;;;;;;;;
;;; TODO: **IMPORTANT** fall back to OS-supported sleep/wakeup after spinning some
;;; e.g. Linux futex
; first arg in rdi as per AMD64 SysV ABI (Linux / Mac / etc)
;;;;;void spin_lock (volatile char *lock)
global spin_unlock
spin_unlock:
; movzx eax, byte [rdi] ; debug check for double-unlocking. Expect 1
mov byte [rdi], 0 ; lock.store(0, std::memory_order_release)
ret
align 16
;;;;;void spin_unlock(volatile char *lock)
global spin_lock
spin_lock:
mov eax, 1 ; only need to do this the first time, otherwise we know al is non-zero
.retry:
xchg al, [rdi]
test al,al ; check if we actually got the lock
jnz .spinloop
ret ; no taken branches on the fast-path
align 8
.spinloop: ; do {
pause
cmp byte [rdi], al ; C++11
jne .retry ; if (lock.load(std::memory_order_acquire) != 1)
jmp .spinloop
; if not translating this to inline asm, you could put the spin loop *before* the function entry point, saving the last jmp
; but since this is probably too simplistic for real use, I'm going to leave it as-is.
A plain store has release semantics, but not sequential-consistency (which you'd get from an xchg or something). Acquire/release is enough to protect a critical section (hence the name).
If you were using a bitfield of atomic flags, you could use lock bts (test and set) for the equivalent of xchg-with-1. You can spin on bt or test. To unlock, you'd need lock btr, not just btr, because it would be a non-atomic read-modify-write of the byte, or even the containing 32-bits.
With a byte or int sized lock like you should normally use, you don't even need a locked operation to unlock; release semantics are enough. glibc's pthread_spin_unlock does it the same as my unlock function: a simple store.
(lock bts is not necessary; xchg or lock cmpxchg are just as good if for a normal lock.)
The first access should be an atomic RMW
See discussion on Does cmpxchg write destination cache line on failure? If not, is it better than xchg for spinlock? - if the first access is read-only, the CPU might send out just a share request for that cache line. Then, if it sees the line unlocked (the hopefully-common low-contention case) it would have to send out an RFO (Read For Ownership) to actually be able to write the cache line. So that's twice as many off-core transactions.
The downside is that this will take MESI exclusive ownership of that cache line, but what really matters is that the thread owning the lock can efficiently store a 0 so we can see it unlocked. Either way, read-only or RMW, that core will lose exclusive ownership of the line and have to RFO before it can commit that unlocking store.
I think a read-only first access would just optimize for slightly less traffic between cores when multiple threads queue up to wait for a lock that's already taken. That would be a silly thing to optimize for.
(Fastest inline-assembly spinlock also tested the idea for a massively contended spinlock with multiple threads doing nothing but trying to take the lock, with poor results. That linked answer makes some incorrect claims about xchg globally locking a bus - aligned locks don't do that, just a cache lock (Is incrementing an int effectively atomic in specific cases?), and each core can be doing a separate atomic RMW on a different cache line at the same time.)
However, if that initial attempt finds it locks, we don't want to keep hammering on the cache line with atomic RMWs. That's when we fall back to read-only. 10 threads all spamming xchg for the same spinlock would keep the memory arbitration hardware pretty busy. It would likely delay the visibility of the store that unlocks (because that thread has to contend for exclusive ownership of the line), so it's directly counter-productive. It may also memory in general in general for other cores.
PAUSE is also essential, to avoid mis-speculation about memory ordering by the CPU. You exit the loop only when the memory you're reading was modified by another core. However, we don't want to pause in the un-contended case. On Skylake, PAUSE waits a lot longer, like ~100 cycles up from ~5, so you should definitely keep the spin-loop separate from the initial check for unlocked.
I'm sure Intel's and AMD's optimization manuals talk about this, see the x86 tag wiki for that and tons of other links.
Not good enough? Should I for example make use of the register keyword in C?
register is a meaningless hint in modern optimizing compilers, except in debug builds (gcc -O0).
cmpand assume they can take the lock. – Auriccmpthe next thread might get the cpu and also does itscmp. – Auriclock cmpxchg– Auricstd::atomic, and look at the asm output (e.g. on gcc.godbolt.org). Also, I answered a recent question about rolling your own semaphore counting-locks, with C11 atomics. I talked some about how it compiles into x86 code. – Blanchettelock xchg, instead of on a normal load, and doesn't use thepauseinstruction. – Blanchette