10

How would you write a function in C which does an atomic compare and swap on an integer value, using embedded machine code (assuming, say, x86 architecture)? Can it be any more specific if its written only for the i7 processor?

Does the translation act as a memory fence, or does it just ensure ordering relation just on that memory location included in the compare and swap? How costly is it compared to a memory fence?

Thank you.

OMG Ponies
  • 325,700
  • 82
  • 523
  • 502
axel22
  • 32,045
  • 9
  • 125
  • 137
  • Usually you compare and swap a value with a memory location, you seem to be talking about _two_ memory locations which is more complex. Is this definitely what you need? – CB Bailey Nov 18 '10 at 10:22
  • Sorry, I've meant a single memory location, I will clarify. – axel22 Nov 18 '10 at 10:40

5 Answers5

7

The easiest way to do it is probably with a compiler intrinsic like _InterlockedCompareExchange(). It looks like a function but is actually a special case in the compiler that boils down to a single machine op. In the case of the MSVC x86 intrinsic, that works as a read/write fence as well, but that's not necessarily true on other platforms. (For example, on the PowerPC, you'd need to explicitly issue a lwsync to fence memory reordering.)

In general, on many common systems, a compare-and-swap operation usually only enforces an atomic transaction upon the one address it's touching. Other memory access can be reordered, and in multicore systems, memory addresses other than the one you've swapped may not be coherent between the cores.

Crashworks
  • 40,496
  • 12
  • 101
  • 170
  • Thank you for your answer! But is it even possible to do a non-memory-fence compare-and-swap on any of the current multicore systems? In this question http://stackoverflow.com/questions/4183202/java-compare-and-swap-semantics-and-performance, a user claimed that on x86 architectures, the only compare-and-swap instruction is CMPXCHG, and that it has to protected via LOCK, which acts as a memory fence, to make it atomic - that this is the only way. Do you perhaps know if this claim is correct? – axel22 Nov 18 '10 at 11:07
  • 1
    I think for the x86 he is right (I'm not an expert on Intel). But there are other processors with other semantics. For example, the PowerPC has a different model where it creates a "reservation" on an address and then conditionally stores. But this only guarantees a fence on that one location. A preceding store to a different location by another core might appear to occur after the compare-and-swap. Also, on that chip, "coherency does not ensure that the result of a store by one processor is visible immediately to all other processors." – Crashworks Nov 18 '10 at 11:38
  • 1
    That is: say there's two cores, A and B. If A and then B both do C&S on address 0x100, they will agree about the order in which this happens. B will see first A's value and then B's. But, if A does an ordinary write of "0" to address 0x100, then B writes "1" to 0x100, and then they both C&S on address 0x200 -- afterwards they will both see the same value at 0x200, but A might still think that 0x100 contains "0". In fact, A's write might get to 0x100 after B's, so that the value really does end up being 0. – Crashworks Nov 18 '10 at 11:43
  • Thanks a lot for this clarification! This is what I wanted to know. – axel22 Nov 18 '10 at 12:45
  • I don't find your second paragraph to be entirely correct, or perhaps it is not clear. Generally a "lock" operation /does/ enforce some kind of ordering constraint, otherwise there'd be little value in using it. Also, while the actual memory may not be the same, the view on other memory is always coherent in a ccNUMA system. – edA-qa mort-ora-y Nov 18 '10 at 16:12
  • @edA-qa mort-ora-y: For examples, take a look at https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/F7E732FF811F783187256FDD004D3797/$file/pem_64bit_v3.0.2005jul15.pdf and https://www-01.ibm.com/chips/techlib/techlib.nsf/products/Cell_Broadband_Engine . – Crashworks Nov 18 '10 at 20:16
  • Then, unlike Intel i7 which is ccNUMA, PowerPC is not a ccNUMA system. From the link above: "The PowerPC Architecture provides for relaxed memory coherency." and "The order in which the processor performs memory accesses, the order in which those accesses complete in memory, and the order in which those accesses are viewed as occurring by another processor may all be different." – axel22 Nov 19 '10 at 08:22
7

You can use the CMPXCHG instruction with the LOCK prefix for atomic execution.

E.g.

lock cmpxchg DWORD PTR [ebx], edx

or

lock cmpxchgl %edx, (%ebx)

This compares the value in the EAX register with the value at the address stored in the EBX register and stores the value in the EDX register to that location if they are the same, otherwise it loads the value at the address stored in the EBX register into EAX.

You need to have a 486 or later for this instruction to be available.

CB Bailey
  • 755,051
  • 104
  • 632
  • 656
4

If your integer value is 64 bit than use cmpxchg8b 8 byte compare and exchange under IA32 x86. Variable must be 8 byte aligned.

Example:
      mov   eax, OldDataA           //load Old first 32 bits
      mov   edx, OldDataB           //load Old second 32 bits
      mov   ebx, NewDataA           //load first 32 bits
      mov   ecx, NewDataB           //load second 32 bits
      mov   edi, Destination        //load destination pointer
      lock cmpxchg8b qword ptr [edi]
      setz  al                      //if transfer is succesful the al is 1 else 0
GJ.
  • 10,810
  • 2
  • 45
  • 62
4

If the LOCK prefix is omitted in atomic processor instructions, atomic operation across multiprocessor environment will not be guaranteed.

In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted. Intel Instruction Set Reference

Without LOCK prefix the operation will guarantee not being interrupted by any event (interrupt) on current processor/core only.

bkausbk
  • 2,740
  • 1
  • 36
  • 52
2

It's interesting to note that some processors don't provide a compare-exchange, but instead provide some other instructions ("Load Linked" and "Conditional Store") that can be used to synthesize the unfortunately-named compare-and-swap (the name sounds like it should be similar to "compare-exchange" but should really be called "compare-and-store" since it does the comparison, stores if the value matches, and indicates whether the value matched and the store was performed). The instructions cannot synthesize compare-exchange semantics (which provides the value that was read in case the compare failed), but may in some cases avoid the ABA problem which is present with Compare-Exchange. Many algorithms are described in terms of "CAS" operations because they can be used on both styles of CPU.

A "Load Linked" instruction tells the processor to read a memory location and watch in some way to see if it might be written. A "Conditional Store" instruction instructs the processor to write a memory location only if nothing can have written it since the last "Load Linked" operation. Note that the determination may be pessimistic; processing an interrupt, for example, may invalidate a "Load-Linked"/"Conditional Store" sequence. Likewise in a multi-processor system, an LL/CS sequence may be invalidated by another CPU accessing to a location on the same cache line as the location being watched, even if the actual location being watched wasn't touched. In typical usage, LL/CS are used very close together, with a retry loop, so that erroneous invalidations may slow things down a little but won't cause much trouble.

supercat
  • 77,689
  • 9
  • 166
  • 211