Spin locks and the beauty of conditional instructions


Low-level toying with multiple CPUs without proper locking mechanisms is asking for trouble. I have already seen many cryptic boot logs form native AROS on RaspberryPi2 which you simply cannot decode. This happens every time when more than one core tries to speak over serial line.

The locking primitive which we have just added to AROS is a spin lock. It does not have an owner, so one cannot re-enter it — trying to do so will result in an endless loop with no exit. The spin lock can be obtained either for reading or for writing. When spin lock is in read mode, it can be acquired by many clients but as long as at least one of them is holding a read lock, code willing to switch it into write mode will have to wait. When spin lock is in write mode, it gives an exclusive access to not more nor less but only one caller. Until it is released again, no other code will be able to obtain the lock at all.

So, here it goes, the spin lock:

typedef struct {
    volatile unsigned long lock;
} spinlock_t;

#define SPINLOCK_INIT_WRITE_LOCKED  { 0x80000000 }

The spin lock comes with three default initializers for those who want to put it in some defined state into e.g. data section. The lock uses one 32-bit value which defines the state of lock:

  • lock == 0 – the lock is in its free state, everyone can lock it in either mode
  • lock > 0 – locked in READ mode. Everyone can lock it in READ state (up to 2^31 times, then it wraps), but attempting to lock it in WRITE mode will blocks until it is free.
  • lock == 0x80000000 – the lock is in WRITE mode. Further attempts to lock it in either modes will block.

The code for locking and unlocking uses the LDREX and STREX instructions which guarantee exclusive access to addressed memory. The code uses also a nice feature of ARM processors – conditional execution of instructions. Let’s look at the code – it assumes that register r0 points to the lock

    mov       r3, #0x80000000
1:  ldrex     r2, [r0]
    teq       r2, #0
    strexeq   r2, r3, [r0]
    teq       r2, #0
    bne       1b

Only one single loop inside. When the function finishes, the spin lock is acquired in WRITE mode. How does it work? The LDREX function reads the lock value into r2 register and marks exclusive access to addressed memory. The lock value is compared against zero. If the lock value was not zero, then the WFE instruction will be executed (please note the “ne” suffix). It puts the CPU into sleep mode until either an interrupt or an event from any other core is sent. If the lock value was zero, the WFE instruction is not executed at all. The next one is conditional variant of STREX. It is executed only if the lock value equals zero (spin lock is free, note the suffix “eq” after STREX). The STREX stores register r3 at address pointed by register r0. If write succeeds, i.e. exclusive lock was still granted, register r2 will be set to value 0, if write fails, r2 will contain value 1. Finally, register r2 is tested against value 0 and, if it’s not zero, we jump back and repeat.

Please note, that in second comparison r2 can contain one of three values:

  • 0, if STREXeq was executed and succeeded,
  • 1, if STREXeq was executed and filed,
  • 0x80000000, if the lock was already acquired and our CPU went to sleep (WFEne).

The last case means, that CPU has received either an event (from another CPU core when it released a spin lock) or an interrupt was triggered. In both cases the CPU will re-attempt to acquire the lock. It wakes up, STREXeq is not executed, 0x80000000 is compared against 0x00000000 and if they are not equal, CPU does a branch. Nice, isn’t it?

There is one more scenario to be considered. What happens if there was an interrupt triggered between LDREX and STREX? Well, in that case AROS code needs to release the exclusive memory by either issuing a CLREX instruction (ARM v7 cpus and up) or by issuing a dummy STREX instruction to some arbitrary memory location. In that case the interrupted code will re-attempt the process of obtaining a spin lock.

Now after the locks were added and properly used, you can turn this:

[KRN:ide27 modbces 08_dritpri fl #s veacion nam00:
0 (0147300 7ff0)
nif8 1or08# 1ls @ 0x50 "ex0c.
 iKRar C
e f81a03tr: p110 .2
 41N]expansi CPlib60ry01
 815f] Core105CP2 =600001bu
libra Cor
 80e f70: 100001
e @ 0e500c:ec00
0x0001889a 8RN]41o"er2 .library@
b3e10 C1 e41 Bootstrad t.re @ 0x0"
[d0c: or9 2 cpu1 ontek.reizurc12
+ KR1a1Ca8e 2 cp 01tx @ 0pr00e3eb0
08] 0fm2948_ini4_c1r 43

into this:

[KRN:BCM2708] Initialising Multicore System
[KRN:BCM2708] bcm2708_init: Copy SMP trampoline from f800074c to 00002000 (100 bytes)
[KRN:BCM2708] bcm2708_init: Patching data for trampoline at offset 80
[KRN:BCM2708] bcm2708_init: Attempting to wake core #1
[KRN:BCM2708] bcm2708_init: core #1 stack @ 0x000b4380 (sp=0x000dc370)
[KRN:BCM2708] bcm2708_init: core #1 fiq stack @ 0x000dc390 (sp=0x000dd380)
[KRN:BCM2708] bcm2708_init: core #1 tls @ 0x000dd3a0
[KRN] Core 1 Boostrapping..
[KRN] Core 1 CPSR=600001d3
[KRN] Core 1 CPSR=60000193
[KRN] Core 1 TLS @ 0x000dd3a0
[KRN] Core 1 KernelBase @ 0x000b3ec0
[KRN] Core 1 SysBase @ 0x000b3200
[KRN] Core 1 Bootstrap task @ 0x000dd3c0
[KRN] Core 1 cpu context size 2124
[KRN] Core 1 cpu ctx @ 0x000dd460
[KRN:BCM2708] bcm2708_init_core(1)
[KRN] Core 1 operational
[KRN] Core 1 waiting for interrupts
[KRN:BCM2708] bcm2708_init: Attempting to wake core #2