Implementing Spinlocks with ARM Exclusive Access

The Problem: Race Conditions

Imagine two CPU cores trying to increment a shared counter in memory. The operation counter++ seems simple, but at the machine level, it's a three-step read-modify-write sequence:

1. Read the current value of counter from memory into a register.
2. Modify the value in the register (increment it).
3. Write the new value from the register back to memory.

Now, consider this sequence of events with two cores, Core 0 and Core 1, both trying to increment counter when its initial value is 10:

Even though two increment operations occurred, the final value is 11, not 12. Core 1's work was completely lost because it started with a stale value. This is a classic race condition. The section of code that performs the read-modify-write is called a critical section, and we need a mechanism to ensure only one core can be inside it at a time. This property is called mutual exclusion.

Spinlocks: A Busy-Wait Solution

A spinlock is a basic and powerful synchronization primitive used to enforce mutual exclusion. The idea is simple:

• A single shared variable (the "lock") represents the state: LOCKED or UNLOCKED.
• Before entering a critical section, a core tries to acquire the lock.
• If the lock is UNLOCKED, the core atomically sets it to LOCKED and enters the critical section.
• If the lock is already LOCKED, the core "spins" in a tight loop, repeatedly checking the lock until it becomes free. This is known as busy-waiting.
• After leaving the critical section, the core releases the lock, setting it back to UNLOCKED.

To see how this is structured in a real-world C codebase and to introduce the key components, let's look at an implementation from the xv6 operating system.

The Need for Hardware Support: Atomic Operations

As the video explained, the "test and set" operation must be atomic. A C implementation like if (lock == 0) lock = 1; is not atomic and suffers from the same race condition we saw earlier. Between reading lock == 0 and writing lock = 1, another core could sneak in.

To solve this, processors provide special atomic instructions. In older ARM architectures, this was the SWP (Swap) instruction. However, SWP had performance limitations, especially in multi-core systems, as it would lock the memory bus. Modern ARMv7/v8 architectures use a more sophisticated and scalable approach: exclusive access instructions.

Let's dive into how these work.

In summary, LDREX and STREX work as a pair:

1. LDREX Rd, [Rn] (Load-Exclusive): It loads a value from the memory address in Rn into Rd. Crucially, it also "tags" this physical memory address within a local monitor inside the processor.
2. STREX Rd, Rm, [Rn] (Store-Exclusive): It attempts to store the value from Rm to the memory address in Rn. The store only succeeds if the processor's exclusive tag for that address is still valid.
   • If the store succeeds, the memory is updated, and Rd is set to 0.
   • If the store fails (because another core wrote to that address, clearing the tag), the memory is not updated, and Rd is set to 1.

This mechanism allows you to build a robust read-modify-write sequence. You LDREX the old value, modify it, and then use STREX to write the new value. If the STREX fails, you know a race occurred, and you must retry the entire sequence.

The "exclusive monitor" is the key hardware component here. It can be local to a core or global in the memory system, depending on the memory configuration.

Implementing a Spinlock in ARM Assembly

Now we have the tools to build our spinlock. The logic for the lock function is:

1. Use LDREX to read the current state of the lock variable.
2. Check if it is already locked. If so, spin and retry from step 1.
3. If it is unlocked, attempt to write the "locked" value using STREX.
4. Check the return status of STREX. If it failed (returned 1), another core got the lock in the tiny window between our LDREX and STREX. We must go back to step 1 and retry.
5. If STREX succeeded (returned 0), we now own the lock.

Let's examine a canonical assembly implementation.

Here is an analysis of that spinlock code, with an unlock function added for completeness. Assume r0 holds the address of the lock variable, and a value of 0 means UNLOCKED, 1 means LOCKED.

// void lock(int *lock_addr)
lock:
    // 1. Read the lock value exclusively
    ldrex   r1, [r0]

    // 2. Check if it's already locked (is it non-zero?)
    cmp     r1, #0
    bne     lock        // Spin: If not zero, loop back and try again

    // 3. Try to acquire the lock. Move 1 (LOCKED) into a register
    mov     r1, #1
    //    Attempt to store 1 into the lock address. r2 gets the status.
    strex   r2, r1, [r0]

    // 4. Check if the store succeeded.
    cmp     r2, #0      // Was STREX successful (status == 0)?
    bne     lock        // No: another core got there first. Retry everything.

    // 5. Success. We have the lock. But we need a memory barrier before proceeding.
    dmb

    // Return
    bx      lr

// void unlock(int *lock_addr)
unlock:
    // Before releasing the lock, ensure all memory accesses in the critical section are complete.
    dmb

    // Atomically write 0 (UNLOCKED) to the lock address.
    mov     r1, #0
    str     r1, [r0]  // A simple store is sufficient for release.

    bx      lr

Advanced Topic: The Crucial Role of Memory Barriers

You almost certainly noticed the DMB (Data Memory Barrier) instruction in the lock and unlock functions. This is not optional; it is essential for correctness.

Modern processors use complex techniques like out-of-order execution and store buffering to improve performance. This means the processor might reorder your memory access instructions. A compiler can do the same thing for optimization.

A lock is useless if the code it's meant to protect is reordered to execute before the lock is acquired or after it's released!

A DMB instruction ensures ordering. In our spinlock:

• The DMB after acquiring the lock ensures that no memory access from within the critical section can be moved before the lock acquisition.
• The DMB before releasing the lock ensures that all memory accesses within the critical section are completed before the lock is released.

We will cover memory barriers in much more detail in our next lesson.

Interview Corner

This topic is a staple in interviews for embedded multi-core roles.

Q1: What is a spinlock and when is it an appropriate synchronization mechanism?
A: A spinlock is a mutual exclusion mechanism where a processor busy-waits in a loop until a lock becomes available. It's appropriate for protecting very short critical sections, typically in low-level code like device drivers or an OS kernel. For short waits, the time spent spinning is less than the overhead of putting a task to sleep and performing a context switch, which is what a mutex would do.

Q2: How would you implement a multi-core safe lock in ARM assembly? Explain the instructions you would use.
A: I would use ARM's exclusive access instructions. The core of the lock function is a loop that uses LDREX to atomically read the lock's state and tag the address. If it's free, I use STREX to attempt to write the 'locked' value. STREX will only succeed if no other core has written to that address since my LDREX. If STREX fails, I have to restart the entire sequence. To ensure correct ordering of memory operations around the critical section, I must also use a DMB memory barrier after acquiring the lock and before releasing it.

Q3: Why is a simple read-modify-write of a flag variable in C not atomic on a multi-core processor?
A: A C statement like if(flag==0) flag=1; is compiled into multiple machine instructions: a load, a compare, and a store. A different core can interrupt this sequence after the load and before the store, leading to a race condition where both cores read flag==0 and both believe they have acquired the lock. This is why hardware-level atomic instructions like LDREX/STREX are necessary.

Q4: What is the difference between a spinlock and a mutex?
A: Both provide mutual exclusion, but they differ in their waiting strategy. A spinlock uses busy-waiting, where the CPU actively spins in a loop, consuming CPU cycles. A mutex is a blocking lock, typically provided by an OS. If a task fails to acquire a mutex, the OS puts the task to sleep (into a Blocked state) and schedules another task to run. The sleeping task consumes no CPU cycles until the mutex is released and the OS wakes it up.

Conclusion

Today we've gone from a high-level problem—the race condition—down to a complete, hardware-level solution. You've learned how to build one of the most fundamental multi-core synchronization primitives.

Key Takeaways:

• Simultaneous read-modify-write operations on shared data by multiple cores lead to race conditions.
• Spinlocks provide mutual exclusion using a busy-wait strategy.
• ARM processors provide LDREX and STREX instructions to implement atomic operations by using an exclusive monitor to detect intervening writes.
• A correct spinlock implementation must use a memory barrier (DMB) to prevent the processor and compiler from reordering memory accesses into or out of the critical section.

Next Lesson Preview:
We've touched on the critical importance of memory barriers. In our next lesson, we will do a deep dive into this topic. We will explore the different types of barriers (DMB, DSB, ISB), understand ARM's weakly-ordered memory model, and see practical examples of where and why these barriers are essential for writing correct multi-core code.