Atomic operations using stcond

Atomic operations are simple calculations performed directly on a memory location with a guarantee that nothing else (i.e. other CPUs, peripherals, threads or interrupt handlers) comes along and alters the value in memory between the point where the value is loaded and the point where it is written back. For example, if an interrupt is raised while an atomic increment-by-one is performed and the interrupt handler would increment the value by one as well, the end result should be that the value is incremented by two. If the operation wasn't atomic, the value might have ended up being incremented by one, effectively discarding the change done by the interrupt handler.

Since AVR32 is a RISC architecture, it doesn't have any instructions that operate directly on memory (with a couple of exceptions, most notably xchg.) Thus, in order to increment a value in memory, you need to load the value from memory into a register, increment the value and store it back into memory. This is not atomic since an interrupt handler can come along at any time and alter the memory location while the value is being held in a register by the interrupted code. When the interrupt handler returns, the interrupted code will simply store the result of its calculation back into memory, overwriting whatever modifications the interrupt handler did.

Note that even on architectures that support operating directly on values in memory (e.g. i386), special care must be taken since such instructions are usually split into RISC-like micro-ops before the are executed on the core. i386 has a "lock" prefix that ensures exclusive access while doing atomic operations, but this is beyond the scope of this article since AVR32 and most other RISC architectures work in a very different way.

How stcond works

The basic principle for stcond is quite simple: If the L bit in the status register is set, it performs a regular store. If the L bit is not set, it does nothing. In either case, the L bit is copied to the Z bit afterwards, allowing a conditional branch immediately afterwards to decide what to do based on whether the store was actually performed or not. If you have done atomic operations on e.g. MIPS or ARM v6 before, this probably sounds familiar.

The L bit is automatically cleared by the rete instruction, i.e. when returning from an interrupt or exception handler. This means that if an interrupt or exception happens between the point where the L bit is set and the stcond instruction, the store will not be performed so any modifications done by the interrupt or exception handler are kept intact. The stcond instruction is then usually followed by a brne instruction back to the beginning of the atomic sequence, allowing the whole operation to be re-tried.

Examples

The following examples are implemented as out-of-line assembly functions to keep things simple. Atomic operations are often performed in hot paths (if it isn't performance critical you might as well use regular locking) so it's often best to implement them inline. See include/asm-avr32/atomic.h in the Linux kernel source for a more complete example on how to do this, but note that a patch was just submitted for 2.6.22-stable to fix a bug in atomic_add_unless() and atomic_sub_unless(), so you should pick a recent version like 2.6.23-rc1 or 2.6.22.atmel.3.

Atomic Add

Add addend to the value stored at p and return the result.

        /* int atomic_add(int *p, int addend) */
retry:  ssrf    5               /* set the L bit */
        ld.w    r8, r12[0]      /* load the value at p into r8 */
        add     r8, r11         /* Add addend to the value loaded from p */
        stcond  r12[0], r8      /* Store the result back to p */
        brne    retry           /* If we were interrupted, try again */
        retal   r8              /* Return the result (if necessary) */

Atomic Add Unless

Add addend to the value at p unless this value is already equal to unless. If the atomic addition was performed, return 1, or if the the value at p was equal to unless, return 0.

        /* int atomic_add_unless(int *p, int addend, int unless) */
retry:  ssrf    5               /* set the L bit */
        ld.w    r8, r12[0]      /* load the value at p into r8 */
        cp.w    r8, r10         /* If the value is equal to "unless"... */
        reteq   0               /* ...don't do anything */
        add     r8, r11         /* Add addend to the value */
        stcond  r12[0], r8      /* Store the result back to p */
        brne    retry           /* If we were interrupted, try again */
        retal   1               /* We were successful */