[Openmcl-devel] [openmcl-devel] atomic-incf

[Gary Byers]

On Sun, 18 Oct 2009, David L. Rager wrote:

> Hi,
> One more hopefully quick question about atomic-incf/atomic-decf:
> 
> Can the return value of an atomic-incf/decf be relied upon as the value
> right after that particular incf occurrs?  Given it's a compare and swap,
> I'm guessing that the answer to this question is "yes".
> 
> Another way to ask the same question is, if I perform two atomic-incf's in a
> row (i.e., as simultaneously as the x86 platform will allow me), will one of
> the atomic-incf calls return the intermediate value, and the other
> atomic-incf return the newest value?
> 
> E.g.:
> A long time ago, in some thread far far away:
> (defvar *x* 3)
> 
> In a current time, with two concurrent threads
> 
> Thread A:
> (atomic-incf *x*) ; sets *x* to 4, returns 4
> 
> Thread B:
> (atomic-incf *x*) ; sets *x* to 5, returns 5
> 
> Of course if Thread B occurred before Thread A, the B transcript would have
> "sets *x* to 4, returns 4" and the A transcript would also change to use the
> number 5.
>

Yes; after these two ATOMIC-INCFs complete, *X* will have the value 5,
and the return value of each ATOMIC-INCF will be the value stored in
the location at the time that it was successfully stored.  (That may
or may not be the same as "the contents of *X* by the time that you
can observe it.")

The code behaves something like:

(loop
   (let* ((old-value (contents-of loc))
          (new-value (1+ old-value))
          (win nil))
    (with-bus-locked
      (when (= (contents-of loc) old-value)  ; this is just compare-and-swap
        (setf (contents-of loc) new-value
              win t)))
    (if win (return new-value))))

where WITH-BUS-LOCKED is supposed to suggest some sort of hardware-imposed
atomicity and memory-ordering (the "lock" prefix on x86, cache-line reservations
and memory barriers on PPC, etc.)

This is a pretty obscure thing to note, but note that the compare-and-swap
doesn't quite guarantee that the location hasn't changed: it's possible that
it was incremented and decremented between the time it was read (at the top
of the loop) and the time that it was tested by compare-and-swap.  In a lot
of cases this doesn't matter; in some cases, it might.  (I think that that's
known as the "ABA" problem, where a memory location's contents change from
A to B and back to A; I know that it comes up, but don't remember canonical
examples that demonstrate cases where it matters.)

> Hopefully between my two versions of the question, my real question is
> clear.
> 
> Thanks,
> David
> 
>