R – Implement atomic increment using atomic swap

assemblyatomicmultithreading

Suppose I'm writing (assembly) code for a CPU whose only atomic operation is an unconditional swap — no LL/SC, no compare-and-swap, just plain swap. (An ARM9 would be an example of such a beast.) Is there a way to perform atomic increment/decrement operations using the swap operation?

There is a relatively easy answer, which is to use the swap to build a spinlock, and use that to provide a critical section around ordinary increment and decrement. But that seems clunky, and I know it can be done without a lock if CAS or LL/SC are available. So what I'm really wondering is if there's a way to do it without using a lock.

Best Answer

I can't think of another way to do it, simply because you need to both swap and compare to detect if you're allowed to proceed. If you don't have a compare-and-swap command, you'll have to implement it with a looping swap and compare, something like:

; Emulate atomic add/sub with atomic swap.
; On entry:
;   r0 contains address of variable
;   r1 contains value to add or subtract.

mutex:    defw    0           ; mutual exclusion semaphore (0=free, 1=busy).

chng:     push    r2          ; save variables.
          ld      r2,1        ; claiming value.
spin:     swap    r2,(mutex)  ; atomic swap (sounds like a good name for a band).
          bnz     spin        ; loop until you have it.
          add     (r0),r1     ; emulated atomic change.
          swap    r2,(mutex)  ; free mutex for everyone else.
          pop     r2          ; restore registers.
          ret

It's only really klunky if you're doing it in a lot of places in your code. I've often found that isolating 'klunky' code to a function (like above) makes it far less klunky since you then end up with lots of code segments looking like the much simpler:

myvar:    defw    0
          : : : : :
          ld      r0,myvar
          ld      r1,1        ; increment
          call    chng

or, if you want your code even simpler, provide separate incr and decr functions:

; Emulate atomic incr/decr with emulated atomic change.
; On entry:
;   r0 contains address of variable

incr:     push    r1          ; save registers.
          ld      r1,1        ; increment.
          call    chng        ; do it.
          pop     r1          ; restore registers.
          ret
decr:     push    r1          ; save registers.
          ld      r1,-1       ; decrement.
          call    chng        ; do it.
          pop     r1          ; restore registers.
          ret

Then your code sequences become:

          ld      r0,myvar
          call    incr

or, if you can do macros, an even simpler:

atincr:   defm                ; do this once to define macro
          ld      r0,&1
          call    incr
          endm

          atincr  myvar       ; do this in your code, as much as you like.

Related Solutions

Ios – What’s the difference between the atomic and nonatomic attributes

The last two are identical; "atomic" is the default behavior (~~note that it is not actually a keyword; it is specified only by the absence of nonatomic~~ -- atomic was added as a keyword in recent versions of llvm/clang).

Assuming that you are @synthesizing the method implementations, atomic vs. non-atomic changes the generated code. If you are writing your own setter/getters, atomic/nonatomic/retain/assign/copy are merely advisory. (Note: @synthesize is now the default behavior in recent versions of LLVM. There is also no need to declare instance variables; they will be synthesized automatically, too, and will have an _ prepended to their name to prevent accidental direct access).

With "atomic", the synthesized setter/getter will ensure that a whole value is always returned from the getter or set by the setter, regardless of setter activity on any other thread. That is, if thread A is in the middle of the getter while thread B calls the setter, an actual viable value -- an autoreleased object, most likely -- will be returned to the caller in A.

In nonatomic, no such guarantees are made. Thus, nonatomic is considerably faster than "atomic".

What "atomic" does not do is make any guarantees about thread safety. If thread A is calling the getter simultaneously with thread B and C calling the setter with different values, thread A may get any one of the three values returned -- the one prior to any setters being called or either of the values passed into the setters in B and C. Likewise, the object may end up with the value from B or C, no way to tell.

Ensuring data integrity -- one of the primary challenges of multi-threaded programming -- is achieved by other means.

Adding to this:

atomicity of a single property also cannot guarantee thread safety when multiple dependent properties are in play.

Consider:

 @property(atomic, copy) NSString *firstName;
 @property(atomic, copy) NSString *lastName;
 @property(readonly, atomic, copy) NSString *fullName;

In this case, thread A could be renaming the object by calling setFirstName: and then calling setLastName:. In the meantime, thread B may call fullName in between thread A's two calls and will receive the new first name coupled with the old last name.

To address this, you need a transactional model. I.e. some other kind of synchronization and/or exclusion that allows one to exclude access to fullName while the dependent properties are being updated.

C++ atomic operations for lock-free structures

Already kindof answered here.

The C++0x standard will provide some atomic datatypes, mainly integer and void types using std::atomic<> template. That article mentions Boehm's atomic_ops project which you can download and use today.

If not, can't you implement your assembler inline in the compiler? I know MSVC has the __asm keyword for inline assembler routines. Google says yes, gcc can do it too.

Best Answer

Related Solutions

Ios – What’s the difference between the atomic and nonatomic attributes

C++ atomic operations for lock-free structures

Related Topic