The MIPS R4000, part 7: Memory access (atomic)
Atomic memory access on the MIPS R4000 is performed with the load-linked and store-conditional instructions. This pattern shouldn’t be much of a surprise because we already encountered it on the Alpha AXP.
LL rd, disp16(rs) ; load linked SC rs, disp16(rd) ; store conditional
LL instruction loads a value from memory and monitors the memory address to see if another processor writes to it. The
SC instruction stores the value to memory, provided there have been no writes¹ to the monitored memory address² and no exceptions have occurred.³ If the store succeeds, then rs is set to one; otherwise it is set to zero.
In both cases, the memory address must be word-aligned.
The intended usage pattern is
retry: LL r1, disp16(r2) ; load linked ADDIU r1, r1, 1 ; increment SC r1, disp16(r2) ; store conditional BEQ r1, 0, retry ; if failed, then retry NOP ; (we'll learn about this later)
The state created by the
LL is ephemeral, and the subsequent
SC is permitted (but not required) to fail if any of the following occur prior to the
- A memory access is performed.
- A branch is taken.
- More than 512 instructions are executed.
Furthermore, after the
SC (either successful or unsuccessful), all subsequent
SC instructions are required to fail until a new
LL is executed.
LL from an address is followed by
SC which does not write to the same address, then it is unspecified whether the
SC succeeds. So don’t do that.
It is legal to execute the
LL instruction and not follow it with the
SC instruction. This can happen if you want to perform a conditional atomic operation, and you discover that the condition is not met.
Before and after the
SC operation, you probably want to do a
SYNC ; memory barrier
All memory operations that precede the
SYNC must complete before any operations that follow the
SYNC can begin.
Note that atomic operations are supported only on aligned words. For aligned sub-word objects, you can perform the atomic operation on the containing word. But if the object is not aligned, then you’re out of luck.
Next time, we enter the exciting world of control transfer. That’s where the
NOP above gets its moment to shine.
¹ Note that if another processor writes the value that is already there back to the memory, or if there is an ABA condition where another processor changes the value, and then changes it back, then the conditional store will fail, even though the value in memory is the same value you started with. This is one cause for the mysterious case of the
weak spurious failure.
² The architecture permits implementations to be sloppy with the detection of a write. In particular, any modification on the same 4KB page as the locked address is permitted to cause the subsequent store conditional instruction to fail. Mind you, an implementation that was this sloppy would not be a very good implementation, but it is technically legal.
³ This last clause is actually an operating system convention, not something inherent in the processor architecture. One of the things that kernel mode does before returning to user mode is execute the
SC instruction with a scratch writable memory location. The
SC might succeed, it might not, but it doesn’t matter. The reason for the
SC is to ensure that if the next atomic memory operation performed by user-mode code is
SC, then that operation definitely fails. This is important in the case where the interrupt occurred after the user-mode code performed the
LL but before it could execute the subsequent
SC. Without it, the
SC in user mode might succeed accidentally.