Ответ 1
Может x86 переупорядочить узкий магазин с более широкой нагрузкой, которая полностью содержит это?
Да, x86 может изменить порядок узкого хранилища с более широкой нагрузкой, которая полностью его содержит.
Вот почему ваш алгоритм блокировки сломан, shared_value не равен 800000:
-
GCC 6.1.0 x86_64 - ссылка на код ассемблера: https://godbolt.org/g/ZK9Wql
-
shared_value =662198: http://coliru.stacked-crooked.com/a/157380085ccad40f
-
-
Clang 3.8.0 x86_64 - ссылка на код ассемблера: https://godbolt.org/g/qn7XuJ
-
shared_value =538246: http://coliru.stacked-crooked.com/a/ecec7f021a2a9782
-
См. ниже правильный пример.
Вопрос:
Блокировка ((INT8 *)) [1] = 1; и ((INT8 *)) [5] = 1; магазины не должны в том же месте, что и 64-битная загрузка блокировки. Однако каждый из них полностью сложенная этой нагрузкой, так делает это "считать" как одно и то же местоположение?
Нет, это не так.
Руководство разработчика программного обеспечения для разработчиков Intel® 64 и IA-32:
8.2.3.4 Нагрузки могут быть переупорядочены с более ранними магазинами в разных местах Модель памяти Intel-64 памяти позволяет загружать нагрузку переупорядочивается с более ранним хранилищем в другое место. Однако, нагрузки не переупорядочиваются с хранилищами в том же месте.
Это упрощенное правило для случая, когда STORE и LOAD имеют одинаковый размер.
Но общее правило заключается в том, что запись в память задерживается на какое-то время, а STORE (адрес + значение), помещенный в буфер хранилища, ожидает кэш-строку в эксклюзивном состоянии (E) - когда эта строка кэша будет быть недействительным (I) в кеше других CPU-ядер. Но вы можете использовать операцию asm MFENCE (или любую операцию с префиксом [LOCK]), чтобы принудительно ждать, пока запись не будет выполнена, и любые последующие инструкции могут быть выполнены только после того, как буфер хранилища будет очищен, а STORE будет видимым для всех процессорных ядер.
О переупорядочении двух строк:
((volatile INT8*)lock)[threadNum] = 1; // STORE
if (1LL << 8*threadNum != *lock) // LOAD
-
Если размер STORE и LOAD равен, то LOAD CPU-Core выполняет поиск в хранилище (Store-forwarding) в Store-Buffer и видит все необходимые данные - вы можете получить все фактические данные прямо сейчас, прежде чем STORE будет выполнен
-
Если размер STORE и LOAD не равен, STORE (1 байт) и LOAD (8 байт), то даже если LOAD CPU-Core выполняет поиск в Store-Buffer, тогда он видит только 1/8 требуемого данные - вы не можете получить все фактические данные прямо сейчас, прежде чем STORE будет выполнен. Здесь могут быть 2 варианта действий ЦП:
-
case-1: CPU-Core загружает другие данные из строки кэша, которые в состоянии общего доступа (S), и перекрывает 1 байт из буфера хранилища, но STORE все еще остается в буфера хранилища и ожидает получения строки кеша эксклюзивного состояния (E) для его модификации, т.е. CPU-Core считывает данные до завершения STORE - в вашем примере это расы данных (ошибка). STORE-LOAD переупорядочивается в LOAD-STORE во всем мире. - это именно то, что происходит на x86_64
-
case-2: CPU-Core ждет, когда Store-Buffer будет сброшен, STORE подождал эксклюзивное состояние (E) строки кэша и STORE, а затем CPU -Core загружает все требуемые данные из строки кеша. STORE-LOAD не переупорядочивается во всем мире. Но это то же самое, что если вы использовали
MFENCE.
-
Заключение, вы должны использовать MFENCE после STORE в любом случае:
- Он полностью решает проблему в case-1.
- Это не повлияет на поведение и производительность в case-2. Явный
MFENCEдля пустого хранилища-буфера немедленно закончится.
Правильный пример для C и x86_64 asm:
Мы вынуждаем CPU-Core действовать как в case-2, используя MFENCE, следовательно, не является упорядочением по StoreLoad
- GCC 6.1.0 (использует
MFENCEдля сброса буфера-хранилища): https://godbolt.org/g/dtNMZ7 - Clang 4.0 (использует
[LOCK] xchgb reg, [addr]для сброса Store-Buffer): https://godbolt.org/g/BQY6Ju
Примечание: xchgb всегда имеет префикс LOCK, поэтому он обычно не записывается в asm или не указан в скобках.
Все остальные компиляторы могут быть выбраны вручную по ссылкам выше: PowerPC, ARM, ARM64, MIPS, MIPS64, AVR.
C-code - должен использовать последовательную согласованность для первого STORE и следующего LOAD:
#ifdef __cplusplus
#include <atomic>
using namespace std;
#else
#include <stdatomic.h>
#endif
// lock - pointer to an aligned int64 variable
// threadNum - integer in the range 0..7
// volatiles here just to show direct r/w of the memory as it was suggested in the comments
int TryLock(volatile uint64_t* lock, uint64_t threadNum)
{
//if (0 != *lock)
if (0 != atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_acquire))
return 0; // another thread already had the lock
//((volatile uint8_t*)lock)[threadNum] = 1; // take the lock by setting our byte
uint8_t* current_lock = ((uint8_t*)lock) + threadNum;
atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)1, memory_order_seq_cst);
//if (1LL << 8*threadNum != *lock)
// You already know that this flag is set and should not have to check it.
if ( 0 != ( (~(1LL << 8*threadNum)) &
atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_seq_cst) ))
{ // another thread set its byte between our 1st and 2nd check. unset ours
//((volatile uint8_t*)lock)[threadNum] = 0;
atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)0, memory_order_release);
return 0;
}
return 1;
}
GCC 6.1.0 - x88_64 asm-code - должен использовать MFENCE для первого STORE:
TryLock(unsigned long volatile*, unsigned long):
movq (%rdi), %rdx
xorl %eax, %eax
testq %rdx, %rdx
je .L7
.L1:
rep ret
.L7:
leaq (%rdi,%rsi), %r8
leaq 0(,%rsi,8), %rcx
movq $-2, %rax
movb $1, (%r8)
rolq %cl, %rax
mfence
movq (%rdi), %rdi
movq %rax, %rdx
movl $1, %eax
testq %rdi, %rdx
je .L1
movb $0, (%r8)
xorl %eax, %eax
ret
Полный пример того, как это работает: http://coliru.stacked-crooked.com/a/65e3002909d8beae
shared_value = 800000
Что произойдет, если вы не используете MFENCE - Data-Races
Существует переупорядочение StoreLoad, как описано выше case-1 (т.е. если вы не используете Sequential Consistency для STORE) - asm: https://godbolt.org/g/p3j9fR
- GCC 6.1.0 x86_64 -
shared_value = 610307: http://coliru.stacked-crooked.com/a/469f087b1ce32977 - Clang 3.8.0 x86_64 -
shared_value = 678949: http://coliru.stacked-crooked.com/a/25070868d3cfbbdd
Я изменил барьер памяти для STORE с memory_order_seq_cst на memory_order_release, он удаляет MFENCE - и теперь есть расы данных - shared_value не равно 800000.
