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_UNLOCKED  { 0 }
#define SPINLOCK_INIT_WRITE_LOCKED  { 0x80000000 }
#define SPINLOCK_INIT_READ_LOCKED(n) { n }
#define SPINLOCK_MODE_READ  0
#define SPINLOCK_MODE_WRITE 1

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
    wfene
    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)
[KRN:BCMnel8]ebcurce8
nif8 1or08# 1ls @ 0x50 "ex0c.
 iKRar C
e f81a03tr: p110 .2
 41N]expansi CPlib60ry01
 3 
 815f] Core105CP2 =600001bu
libra Cor
 80e f70: 100001
41RNutility.librarl"
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
eKRurcCM
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
...

I think I will never understand that

Today morning I was reviewing some small bit of code, which surprisingly compiled on i386 target just fine, but failed for ARM target. As always, the first thing I though was “Oh no! That could be variadic function!” and I was right, again.

But this time I was really surprised. The author of the code started just right fine:

#include <stdarg.h>
[...]

char * STDARGS GetKeyWord(int value, char *def, ...)
{
    [...]
    va_list va;
    [...]
    va_start(va, def);

And then, out of sudden, the motivation for using stdarg passes away, va is casted to a LONG * type and varargs handled manually. Why oh why? Why the coder uses tons of casting, where he could use a simple va_arg? Why string = *((char **) args) instead of string=va_arg(va, char *)? Why advancing the args pointer? Where is the missing va_end? I don’t know and I think I will never understand that.

Merry X-mas

Merry Christmas to You all out there! 🙂

And sorry for disappointing many of You during this year. Some of you hoped this year I will do something nice for them. And I failed many times. I would really like to tell you that I’m really sorry about that. I feel really bad about it.

Stephen, I feel really sorry that I failed and didn’t gave you the promised enchantments to AROS. I do know you were really disappointed with (lacking) results of my work even if you never said that. Thanks for everything you did to AROS.

ACube, I feel really sorry that I cannot give you any good news about progress I made. There is no progress. I’m sorry but work and real life are eating all the spare time I could have for you.

Nikos, I feel awfully that I cannot give you the X-mas gift – overlay for intel GMA. I really wanted to but, once again, I failed. I failed. Forgive me. Keep good work on supporting AROS.

sorry guys…

Update, again

Hello folks,

Today a short report only. Markus Weiss was working intensively on getting OWB to compile and work on PPC targets. Of course, he succeeded! Thank you, Markus.
In my last post I’ve told you about some issues with setjmp/longjmp. The unaligned FPU double access, which crossed 16-byte boundary generates an alignment exception on PowerPC machines. My first fix was rather stupid one – alignment enforcement in setjmp and longjmp calls. Now, I wrote a special exception handler which takes care of misaligned data. It helped Markus a bit and make OWB work on Sam440EP.
Thanks to Markus work and his great fixes to the code, DHCP client does not enter an endless loop on Sam440 anymore. Now, setting network up on Samantha is a matter of few mouse clicks.
Stay tuned for more news. New ISO is on the way (I may tell you that its size increased again. Now it has 475 MB approximately).
PS. This blog entry was written on AROS running on Sam440EP in OWB browser 🙂

Any news?

Hello there.

Yup, typical me 🙂 I made some fuzz about things being currently done (or not done) and then disappeared for a while. No information, no updates. Nothing :)I’ve been asked several times about the status update of AROS for sam440. Well, there are few changes which have happened to the whole AROS recently. We do have a changeable mouse pointers and they do work on Sam440. Since there are few of them delivered on the ISO, you may change the red triangle to something more Amiga-like, if you want to. A red mouse pointer with alpha blending and shadow? No problem. Start preferences, select the correct image and voilà!

Markus Weiss managed to compile OWB for PPC target and, if it works as expected, you will find it on the next ISO. Neil Cafferkey made some important improvements to the installer. Now, it installation on sam440 shall be simpler. Keep in mind the installation will be incomplete, since the AROS’ slb (aka Parthenope) is not installed yet.

The changes local to Sam440 port include support for the onboard I²C bus. The RTC is used by the battclock.resource, so now you will see the correct time on AROS, provided your RTC is correctly set up. If not, you may use AROS’ time preferences to adjust it. Additionally, few fixes for the setjmp/longjmp are made, so that the functions do not crash in case of unaligned jmp_buf pointer. Anything else? Ah yes, I’m working on the EHCI Poseidon driver for Sam440 AROS. Stay tuned 🙂

Screenshot? Here you have it. Nothing special in it. Just AROS on Sam440 in a bit higher resolution 🙂
Greetings from the German Aerospace Center 🙂