Может ли x86 переупорядочить узкий магазин с более широкой нагрузкой, которая полностью его содержит?

Может ли x86 переупорядочить узкий магазин с более широкой нагрузкой, которая полностью его содержит?

Да, x86 может переупорядочить узкий магазин с более широкой нагрузкой, которая полностью его содержит.

Вот почему ваш алгоритм блокировки сломан, shared_value не равен 800000:

1. GCC 6.1.0 x86_64 – ссылка на код ассемблера: https://godbolt.org/g/ZK9Wql

   • shared_value = 662198 : http://coliru.stacked-crooked.com/a/157380085ccad40f

2. 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 будет видимым для всех CPU-ядра.

О переупорядочении двух строк:

 ((volatile INT8*)lock)[threadNum] = 1; // STORE if (1LL << 8*threadNum != *lock) // LOAD 

• Если размер STORE и LOAD равен, то LOAD CPU-Core делает (сохранение в магазине) поиск в Store-Buffer и видит все необходимые данные - вы можете получить все фактические данные прямо сейчас, прежде чем STORE будет выполнен

• Если размер STORE и LOAD не равен, STORE (1 байт) и LOAD (8 байт), то даже если LOAD CPU-Core выполняет поиск в Store-Buffer, тогда он видит только 1/8 требуемых данных - вы не можете получить все фактические данные прямо сейчас, прежде чем STORE будет выполнен. Здесь могут быть 2 варианта действий ЦП:

  1. case-1: CPU-Core загружает другие данные из строки кеша, которые в состоянии общего доступа (S), и перекрывает 1 байт из буфера хранилища, но STORE все еще остается в буфере хранилища и ожидает получения эксклюзивного состояния ( E), чтобы изменить его, то есть CPU-Core считывает данные до завершения STORE - в вашем примере это расы данных (ошибка). STORE-LOAD переупорядочивается в LOAD-STORE во всем мире. - Это именно то, что происходит на x86_64

  2. case-2: CPU-Core ждет, когда Store-Buffer будет сброшен, STORE подождал эксклюзивное состояние (E) строки кэша и STORE, а CPU-Core загружает все необходимые данные из строки кеша. STORE-LOAD не переупорядочивается во всем мире. Но это то же самое, как если бы вы использовали MFENCE .

Заключение, вы должны использовать MFENCE после STORE в любом случае:

1. Он полностью решает проблему в случае-1.
2. Это не повлияет на поведение и производительность в случае-2. Явная MFENCE для пустого Store-Buffer немедленно закончится.

---

Правильный пример для C и x86_64 asm:

Мы вынуждаем CPU-Core действовать так же, как и в случае-2 , используя MFENCE , следовательно, не существует переупорядочения StoreLoad

• GCC 6.1.0 (использует mfence для mfence Store-Buffer): https://godbolt.org/g/dtNMZ7
• Clang 4.0 (использует [LOCK] xchgb reg, [addr] для [LOCK] xchgb reg, [addr] буфера-хранилища): https://godbolt.org/g/BQY6Ju

Примечание: xchgb всегда имеет префикс LOCK , поэтому он обычно не записывается в asm или не указан в скобках.

Все остальные компиляторы можно выбрать вручную по ссылкам выше: PowerPC, ARM, ARM64, MIPS, MIPS64, AVR.

C-код - должен использовать последовательную согласованность для первого STORE и следующего LOAD:

 #ifdef __cplusplus #include  using namespace std; #else #include  #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, как в описанном выше случае-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.

Может ли mov byte [rcx+r8], 1 переупорядочить с помощью cmp qword [rcx], rdx load, которая следует за ним? Это lock[threadNum]=1 и следующая загрузка, чтобы никто не написал байт.

Нагрузка должна возвращать данные, которые include в себя хранилище, поскольку исполняемый stream всегда наблюдает за своими действиями, которые происходят в программном порядке. (Это верно даже для слабоупорядоченных ISA).

---

Оказывается, эта точная идея блокировки была предложена раньше (для ядра Linux), а Линус Торвальдс объяснил, что x86 действительно разрешает такое переупорядочение

Несмотря на термин «сбой в хранилище или срыв» , это не означает, что данные должны фиксировать кеш, прежде чем загрузка сможет его прочитать. Он действительно может быть прочитан из буфера хранилища, в то время как строка кэша все еще находится в состоянии S ( MESI ). (И на ядрах Atom в порядке, вы даже не получаете магазин-переадресацию.)

Реальное оборудование работает так (как показывают тесты Алекса): процессор будет объединять данные из L1D с данными из буфера хранилища, не связывая хранилище с L1D.

Это само по себе не переупорядочивает еще ¹ (нагрузка видит данные магазина, и они смежны в глобальном порядке), но он оставляет дверь открытой для переупорядочения. Линия кэша может быть аннулирована другим kernelм после загрузки, но до того, как будет зафиксирован магазин. Магазин из другого ядра может стать глобально видимым после нашей загрузки, но перед нашим магазином.

Таким образом, нагрузка включает данные из нашего собственного магазина, но не из другого магазина из другого ЦП. Другой процессор может видеть тот же эффект для своей нагрузки, и поэтому оба streamа входят в критический раздел.

---

¹ (Это то, что я делал в комментариях к ответу Алекса . Если x86 не разрешал это переупорядочивание, процессоры все равно могли бы осуществлять перепродажу хранилища спекулятивно до того, как хранилище станет глобально видимым, и запустит его, если другой процессор аннулирует кеш-память до тех пор, пока магазин не совершил. Эта часть ответа Алекса не доказывает, что x86 работал так, как это делается. Только экспериментальное тестирование и тщательная аргументация в отношении блокирующего алгоритма дали нам это.)

Если x86 не разрешало это переупорядочение, пара с хранилищем / частично перекрывающимся-перезагрузкой работала бы как MFENCE: более ранние нагрузки не могут стать глобально видимыми перед загрузкой, а более ранние магазины не могут стать глобально видимыми перед магазином. Нагрузка должна стать глобально видимой до любых следующих нагрузок или магазинов, и это также остановило бы хранение магазина.

Учитывая это рассуждение, не совсем очевидно, почему прекрасно перекрывающиеся магазины не эквивалентны MFENCE. Возможно, они на самом деле есть, и x86 справляется с тем, чтобы быстро и эффективно выполнять переполнение / перезагрузку или переход через стек со спекулятивным исполнением!

---

Схема блокировки:

Похоже, что TryLock может терпеть неудачу для обоих / всех вызывающих: все они видят, что изначально ноль, все они записывают свой байт, тогда все они видят по крайней мере два ненулевых байта каждый. Это не идеально подходит для сильно заблокированных замков, по сравнению с использованием команды lock ed. Существует аппаратный арбитражный механизм для обработки конфликтующих lock . (TODO: найдите сообщение на форуме Intel, где инженер Intel разместил это в ответ на другую цепочку повторных попыток программного обеспечения и тему с инструкциями по lock , IIRC.)

Узкая запись / широкоформатное чтение всегда будет запускать стойку хранения на современном оборудовании x86. Я думаю, это просто означает, что результат нагрузки не готов к нескольким циклам, а не к выполнению других инструкций (по крайней мере, не в дизайне ООО).

В слабо контролируемой блокировке, которая используется часто, ветвь будет правильно outlookировать, чтобы перейти на путь без конфликта. Спекулятивное выполнение по этому пути до тех пор, пока загрузка окончательно не завершится, и ветка может уйти в отставку, не должна останавливаться, потому что хранилища-переадресаторы не достаточно длинны, чтобы заполнить ROB.

• SnB: ~ 12 циклов дольше, чем при работе с магазином (~ 5c)
• HSW: ~ 10c дольше
• SKL: ~ 11c дольше, чем при работе с хранилищем (4c для 32 и 64-битных операндов, что на 1 c меньше, чем у предыдущих процессоров)
• AMD K8 / K10: Agner Fog не дает числа.

• AMD Bulldozer-family: 25-26c (Steamroller)

• Atom: «В отличие от большинства других процессоров, Atom может выполнять переадресацию, даже если операнд чтения больше, чем предыдущий операнд записи или по-разному выровнен», и есть только 1 c латентность. Только сбой при пересечении границы линии кэша.

• Silvermont: ~ 5c дополнительно (база: 7c)
• AMD Bobcat / Jaguar: 4-11c дополнительно (база: 8c / 3c)

Так что, если вся схема блокировки работает, она может хорошо справиться с легкомысленными замками.

Я думаю, вы можете превратить его в блокировку с несколькими считывателями / одиночными писателями, используя бит 1 в каждом байте для читателей и бит 2 для авторов. TryLock_reader игнорирует биты считывателя в других байтах. TryLock_writer будет работать как оригинал, требуя нуля во всех битах в других байтах.

---

BTW, для хранения в памяти вещей вообще, блог Джеффа Прешинга превосходный .