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

Ответ 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 чтение cmpxchg8b атомарным.

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

Код возвращается к 0x8048565 (после загрузки mov, включая copy и 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 фактически из того же чтения, которое cmpxchg8b использовал для части сравнения. В цикле нет отдельной перезагрузки.

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

То же __atomic_compare_exchange_n (type *ptr, type *expected, type desired, bool weak, int success_memorder, int failure_memorder) делает современная встроенная в 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 (вместо булева выгружены/didn't-своп результата для __sync_bool_compare_and_swap)

Ответ 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 неверно, цикл будет повторен снова, поэтому не будет проблем, если oldValue прочитано привело к неверному значению.

64-битный доступ к *dest с помощью lock cmpxchg8b является атомарным (как часть атомарного RMW *dest). Любые разрывы при загрузке двух половинок будут обнаружены здесь. Или, если запись из другого ядра произошла после начального чтения, до lock cmpxchg8b: это возможно даже с cmpxchg -retry с одним регистром ширины. (например, чтобы реализовать атомарный 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;
    }
  }
}

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