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

[Gary Byers]

On Thu, 15 Oct 2009, David L. Rager wrote:

> Hello Gary and Co.,
>
> Two questions about atomic-incf:
>
> (1) It's not showing up as external for me (release 1.3).  Is it
> reasonable to make it external?  Is there a reason that it's not
> exposed other than just not wanting to make too many promises about an
> API?

Laziness and sloth also factor into it.

>
> (2) By "atomic", does it mean that no other threads can read/write
> that variable during the actual increment?  I'm not worried about all
> the code that wraps the increment (perhaps it checks the type of the
> argument, etc.).  I'm just trying to make sure the increment itself is
> thread-safe.

Incrementing a memory location that contains a fixnum by 1 (and ignoring
overflow) is something like:

   (load reg @loc) ; reg <- contents-of (loc)
   (add reg #fixnum-one) ; reg <- reg+1
   (store reg @loc) ; contents-of (loc) <- reg

Even if it's implemented as a single CISCy instruction, there's likely
to be a similar sequence of independent read, modify, and write
operations at some microarchitectural level.  If two or more threads
are running concurrently, those operations could be interleaved; if
"loc" contains 0 and two threads try to increment it by one, then we
could have something like:

   (load reg @loc) ; on thread 1, reg = 1
   (add reg #fixnum-one) ; on thread 1, reg = 1
   (load reg @loc) ; on thread 2, reg = 0
   (add reg #fixnum-one) ; on thread 2, reg = 1
   (store reg @loc) ; on thread 2, contents-of (loc) = 1
   (store reg @loc) ; on thread 1, contents-of (loc) = 1

and each thread would think that it'd successfully incremented "loc"
from 0 to 1.  ATOMIC-INCF basically tries to guarantee that the
read-modify-write sequence happens atomically.


>
> My guess is that atomic-incf calls the X86 instruction that locks the
> bus for a particular memory address and increments that variable.
>> From looking at the implementation in x86-misc.lisp, it looks like it
> does indeed perform a lock on a memory address, performs a compare and
> exchange with an atomicity guarantee, and then loops back to the
> beginning of the function if that compare and exchange failed.  In the
> PPC implementation, it looks like the lrarx and strcx instructions
> combine to also provide an atomic increment.

I think that we could actually implement it as

   (lock)
   (addq ($ fixnumone) (@ loc))

or

   (movq increment-by (% reg))
   (lock)
   (addq (% reg) (@ loc))

on x86; we actually do a similar compare-and-swap loop on both
architectures.

(If anyone's curious, "lrarx" and "strcx" are macros that expand
into word-size specific PPC instructions, e.g. "lwarx/stwcx." on
32-bit PPC, "ldarx/swdcx." on PPC64.)




>
> Thanks,
> David
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>