Почему __sync_add_and_fetch работает для 64-битной переменной в 32-битной системе?

Question

Рассмотрим следующий сокращенный код:

/* 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;
}

У меня есть переменная uint64_t, которую я хочу увеличить атомарно, потому что переменная является счетчиком в многопоточной программе. Для достижения атомарности я использую атомные встраивания GCC .

Если я скомпилирую для системы amd64 (-m64), полученный ассемблерный код будет легко понять. Используя lock addq, процессор гарантирует, что приращение будет атомарным.

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

Но тот же код C создает очень сложный код ASM в системе ia32 (-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>

Вот что я не понимаю:

• lock cmpxchg8b делает гарантией того, что измененная переменная записывается только в том случае, если ожидаемое значение все еще находится в целевом адресе. Сравнение и обмен гарантированно будут происходить атомарно.
• Но что гарантирует, что чтение переменной в 0x804855a и 0x804855f будет атомарным?

Возможно, не имеет значения, было ли "грязное чтение", но может ли кто-нибудь изложить короткое доказательство , что проблем нет?

Далее: Почему сгенерированный код возвращается к 0x8048565, а не к 0x804855a? Я уверен, что это верно только в том случае, если другие авторы тоже только увеличивают переменную. Является ли это имплицитным требованием для функции __sync_add_and_fetch?

Answer 1

начальная , считанная с двумя отдельными mov инструкциями, является не атомарной, но она не в цикле. @ ответ interjay объясняет, почему это хорошо.

---

Забавный факт: чтение, выполненное cmpxchg8b, будет атомарным даже без префикса lock. (Но этот код действительно использует префикс lock, чтобы сделать всю операцию RMW атомарной, а не разделять атомарную загрузку и атомарное хранилище.)

Гарантируется, что он является атомарным, поскольку он правильно выровнен (и он помещается на одной строке кэша), а также потому, что Intel разработала спецификацию таким образом, см. Руководство по архитектуре Intel, том 1, 4.4.1:

Операнд слова или двойного слова, который пересекает 4-байтовую границу или операнд четырех слов, который пересекает 8-байтовую границу не выровнен и требует двух отдельных циклов шины памяти для доступа.

Том 3А 8.1.1:

Процессор Pentium (и более новые процессоры с тех пор) гарантирует, что следующие дополнительные операции с памятью всегда будут выполняться атомно:

• Чтение или запись четырех слов, выровненных по 64-битной граница

• 16-битный доступ к некэшируемым областям памяти, которые соответствуют в пределах 32-битной шины данных

Процессоры семейства P6 (и новее процессоры т.к.) гарантируют, что следующая дополнительная память операция всегда будет выполняться атомарно:

• Выровнены 16-, 32-, и 64-битный доступ к кеш-памяти, которая помещается в строку кеша

Таким образом, будучи выровненным, он может быть прочитан за 1 цикл и помещается в одну строку кэша, что делает cmpxchg8b читаемым атомарным.

Если данные были выровнены неправильно, префикс lock будет все еще сделать его атомарным, но затраты на производительность будут очень высокими из-за простой блокировки кеша (задержка ответа MESI Отклонять запросы на эту одну строку кэша) больше не будет достаточно.

---

Код возвращается к 0x8048565 (после загрузки mov, включая копию и add-1), поскольку v уже загружен; нет необходимости загружать его снова, поскольку CMPXCHG8B установит EAX:EDX на значение в месте назначения, если произойдет сбой:

CMPXCHG8B Описание для руководства Intel ISA Vol. 2A:

Сравните EDX: EAX с m64. Если равно, установите ZF и загрузите ECX: EBX в m64. Иначе, очистите ZF и загрузите m64 в EDX: EAX.

Таким образом, коду нужно только увеличить новое возвращаемое значение и повторить попытку. Если мы посмотрим на это в C-коде, это станет проще:

value = dest;                    // non-atomic but usually won't tear
while(!CAS8B(&dest,value,value + 1))
{
    value = dest;                // atomic; part of lock cmpxchg8b
}

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * value = dest на самом деле от того же чтения, который * 10 6 * * используется для части сравнения). В цикле нет отдельной перезагрузки.

Фактически, C11 atomic_compare_exchange_weak / _strong имеет это встроенное поведение: он обновляет «ожидаемый» операнд.

То же самое делает современная встроенная в GCC __atomic_compare_exchange_n (type *ptr, type *expected, type desired, bool weak, int success_memorder, int failure_memorder) - она ​​принимает значение expected для справки.

С устаревшими GCC __sync встроенными , __sync_val_compare_and_swap возвращает старое значение val (вместо логического результата swap / not-swap для __sync_bool_compare_and_swap)

Answer 2

Чтение переменной в 0x804855a и 0x804855f не обязательно должно быть атомарным.Использование инструкции сравнения и замены для приращения в псевдокоде выглядит следующим образом:

oldValue = *dest; // non-atomic: tearing between the halves is unlikely but possible
do {
    newValue = oldValue+1;
} while (!compare_and_swap(dest, &oldValue, newValue));

Поскольку сравнение и замена проверяет, что *dest == oldValue перед заменой, оно будет действовать в качестве защиты - так что еслизначение в oldValue неверно, цикл будет повторяться снова, поэтому нет проблем, если неатомарное чтение привело к неверному значению.

64-битный доступ к *dest сделан lock cmpxchg8b является атомным (как часть атомного RMW *dest).Любые разрывы при загрузке двух половинок будут обнаружены здесь.Или, если запись из другого ядра произошла после начального чтения, до lock cmpxchg8b: это возможно даже с циклами с однократной регистрацией cmpxchg -ryry.(например, для реализации атомарного fetch_mul или атомарного float, или других операций RMW, которые префикс x86 lock не позволяет нам делать напрямую.)

---

Ваш второй вопрос был, почему строка oldValue = *dest не в цикле.Это связано с тем, что функция compare_and_swap всегда заменяет значение oldValue фактическим значением *dest.Таким образом, он по существу выполнит для вас строку oldValue = *dest, и нет смысла делать это снова.В случае инструкции cmpxchg8b содержимое операнда памяти будет помещено в edx:eax, когда сравнение не удастся.

Псевдокод для compare_and_swap:

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Кстати, в вашем коде вы должны убедиться, что v выровнен по 64 битам - в противном случае он может быть разбит на две строки кэша, и инструкция cmpxchg8b не будет выполняться атомарно.Для этого вы можете использовать GCC __attribute__((aligned(8))).