Why does __sync_add_and_fetch work for a 64 bit va

问题:

Consider the following condensed code:

/* Compile: gcc -pthread -m32 -ansi x.c */
#include <stdio.h>
#include <inttypes.h>
#include <pthread.h>

static volatile uint64_t v = 0;

void *func (void *x) {
    __sync_add_and_fetch (&v, 1);
    return x;
}

int main (void) {
    pthread_t t;
    pthread_create (&t, NULL, func, NULL);
    pthread_join (t, NULL);
    printf ("v = %"PRIu64"\n", v);
    return 0;
}

I have a uint64_t variable that I want to increment atomically, because the variable is a counter in a multi-threaded program. To achieve the atomicity I use GCC's atomic builtins.

If I compile for an amd64 system (-m64) the produced assembler code is easy to understand. By using a lock addq, the processor guarantees the increment to be atomic.

 400660:       f0 48 83 05 d7 09 20    lock addq $0x1,0x2009d7(%rip)

But the same C code produces a very complicated ASM code on an ia32 system (-m32):

804855a:       a1 28 a0 04 08          mov    0x804a028,%eax
804855f:       8b 15 2c a0 04 08       mov    0x804a02c,%edx
8048565:       89 c1                   mov    %eax,%ecx
8048567:       89 d3                   mov    %edx,%ebx
8048569:       83 c1 01                add    $0x1,%ecx
804856c:       83 d3 00                adc    $0x0,%ebx
804856f:       89 ce                   mov    %ecx,%esi
8048571:       89 d9                   mov    %ebx,%ecx
8048573:       89 f3                   mov    %esi,%ebx
8048575:       f0 0f c7 0d 28 a0 04    lock cmpxchg8b 0x804a028
804857c:       08 
804857d:       75 e6                   jne    8048565 <func+0x15>

Here is what I don't understand:

• lock cmpxchg8b does guarantee that the changed variable is only written if the expected value still resides in the target address. The compare-and-swap is guaranteed to happen atomically.
• But what guarantees that the reading of the variable in 0x804855a and 0x804855f to be atomic?

Probably it does not matter if there was a "dirty read", but could someone please outline a short proof that there is no problem?

Further: Why does the generated code jump back to 0x8048565 and not 0x804855a? I am positive that this is only correct if other writers, too, only increment the variable. Is this an implicated requirement for the __sync_add_and_fetch function?

回答1:

The read is guaranteed to be atomic due to it being aligned correctly (and it fits on one cache line) and because Intel made the spec this way, see the Intel Architecture manual Vol 1, 4.4.1:

A word or doubleword operand that crosses a 4-byte boundary or a quadword operand that crosses an 8-byte boundary is considered unaligned and requires two separate memory bus cycles for access.

Vol 3A 8.1.1:

The Pentium processor (and newer processors since) guarantees that the following additional memory operations will always be carried out atomically:

• Reading or writing a quadword aligned on a 64-bit boundary

• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus

The P6 family processors (and newer processors since) guarantee that the following additional memory operation will always be carried out atomically:

• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line

Thus by being aligned, it can be read in 1 cycle, and it fits into one cache line making the read atomic.

The code jumps back to 0x8048565 because the pointers have already be loaded, there is no need to load them again, as CMPXCHG8B will set EAX:EDX to the value in the destination if it fails:

CMPXCHG8B Description for the Intel ISA manual Vol. 2A:

Compare EDX:EAX with m64. If equal, set ZF and load ECX:EBX into m64. Else, clear ZF and load m64 into EDX:EAX.

Thus the code needs only to increment the newly returned value and try again. If we this of it in C code it becomes easier:

value = dest;
While(!CAS8B(&dest,value,value + 1))
{
    value = dest;
}

回答2:

The reading of the variable in 0x804855a and 0x804855f does not need to be atomic. Using the compare-and-swap instruction to increment looks like this in pseudocode:

oldValue = *dest;
do {
    newValue = oldValue+1;
} while (!compare_and_swap(dest, &oldValue, newValue));

Since the compare-and-swap checks that *dest == oldValue before swapping, it will act as a safeguard - so that if the value in oldValue is incorrect, the loop will be tried again, so there's no problem if the non-atomic read resulted in an incorrect value.

Your second question was why the line oldValue = *dest is not inside the loop. This is because the compare_and_swap function will always replace the value of oldValue with the actual value of *dest. So it will essentially perform the line oldValue = *dest for you, and there's no point in doing it again. In the case of the cmpxchg8b instruction, it will put the contents of the memory operand in edx:eax when the comparison fails.

The pseudocode for compare_and_swap is:

bool compare_and_swap (int *dest, int *oldVal, int newVal)
{
  do atomically {
    if ( *oldVal == *dest ) {
        *dest = newVal;
        return true;
    } else {
        *oldVal = *dest;
        return false;
    }
  }
}

By the way, in your code you need to ensure that v is aligned to 64 bits - otherwise it could be split between two cache lines and the cmpxchg8b instruction will not be performed atomically. You can use GCC's __attribute__((aligned(8))) for this.