Какие точные правила в модели памяти C ++ предотвращают переупорядочение перед операциями получения?

Question

У меня есть вопрос относительно порядка операций в следующем коде:

std::atomic<int> x;
std::atomic<int> y;
int r1;
int r2;
void thread1() {
  y.exchange(1, std::memory_order_acq_rel);
  r1 = x.load(std::memory_order_relaxed);
}
void thread2() {
  x.exchange(1, std::memory_order_acq_rel);
  r2 = y.load(std::memory_order_relaxed);
}

Учитывая описание std::memory_order_acquire на странице cppreference (https://en.cppreference.com/w/cpp/atomic/memory_order),, что

Операция загрузки с этим порядком памяти выполняет операцию получения в уязвимом месте памяти: никакие операции чтения или записи в текущем потоке не могут быть переупорядочены до этой загрузки.

кажется очевидным, чтоникогда не может быть результатом того, что r1 == 0 && r2 == 0 после одновременного запуска thread1 и thread2.

Однако я не могу найти никакой формулировки в стандарте C ++ (глядя на черновик C ++ 14 прямо сейчас),который устанавливает гарантии того, что две расслабленные нагрузки не могут быть переупорядочены с обменом приобретением-выпуском.Я обновил программу, чтобы использовать загрузку-сборку следующим образом:

std::atomic<int> x;
std::atomic<int> y;
int r1;
int r2;
void thread1() {
  y.exchange(1, std::memory_order_acq_rel);
  r1 = x.load(std::memory_order_acquire);
}
void thread2() {
  x.exchange(1, std::memory_order_acq_rel);
  r2 = y.load(std::memory_order_acquire);
}

Теперь можно получить оба, а r1 и r2 равные 0 после cв настоящее время выполняет thread1 и thread2?Если нет, то какие правила C ++ предотвращают это?

Answer 1

У вас уже есть ответ на языковую часть юриста.Но я хочу ответить на связанный с этим вопрос о том, как понять, почему это возможно в asm на возможной архитектуре ЦП, которая использует LL / SC для атома RMW .

Это не делаетсмысл в C ++ 11 запретить это переупорядочение: в этом случае потребуется барьер загрузки хранилища, когда некоторые архитектуры ЦП могут его избежать.

Это может быть на самом деле возможно с реальными компиляторами на PowerPC, учитывая путьони отображают C ++ 11-порядки памяти в asm-инструкции.

В PowerPC64 функция с обменом acq_rel и загрузкой захвата (с использованием аргументов указателя вместо статических переменных) компилируется следующим образом с gcc6.3 -O3 -mregnames.Это из версии C11, потому что я хотел посмотреть на вывод clang для MIPS и SPARC, и установка Clang Годболта работает для C11 <atomic.h>, но не работает для C ++ 11 <atomic> при использовании -target sparc64.

(источник + asm на Godbolt для MIPS32R6, SPARC64, ARM 32 и PowerPC64. )

foo:
    lwsync            # with seq_cst exchange this is full sync, not just lwsync
                      # gone if we use exchage with mo_acquire or relaxed
                      # so this barrier is providing release-store ordering
    li %r9,1
.L2:
    lwarx %r10,0,%r4    # load-linked from 0(%r4)
    stwcx. %r9,0,%r4    # store-conditional 0(%r4)
    bne %cr0,.L2        # retry if SC failed
    isync             # missing if we use exchange(1, mo_release) or relaxed

    ld %r3,0(%r3)       # 64-bit load double-word of *a
    cmpw %cr7,%r3,%r3
    bne- %cr7,$+4       # skip over the isync if something about the load? PowerPC is weird
    isync             # make the *a load a load-acquire
    blr

isync не является барьером загрузки магазина;для этого требуется только выполнение предыдущих инструкций локально (удалить из неработающей части ядра).Он не ожидает очистки буфера хранилища, поэтому другие потоки могут видеть более ранние хранилища.

Таким образом, хранилище SC (stwcx.), которое является частью обмена, может находиться в буфере хранилища.и становятся глобально видимыми после чистой нагрузки, которая следует за ней. На самом деле, еще один вопрос и ответ уже задавали этот вопрос, и ответ таков: мы думаем, что это изменение порядка возможно. Предотвращает ли `isync` переупорядочение Store-Load на CPU PowerPC?

Если чистая загрузка равна seq_cst, PowerPC64 gcc ставит sync перед ld.Принятие exchange seq_cst делает не предотвращением переупорядочения.Помните, что C ++ 11 гарантирует только один общий порядок для операций SC, поэтому для обеспечения C ++ 11 для обмена и загрузки необходимо использовать SC.

Так что в PowerPC есть что-то необычноеотображение из C ++ 11 в asm для атомики.Большинство систем ставят более жесткие барьеры для магазинов, что позволяет последующим нагрузкам быть дешевле или иметь барьер только с одной стороны.Я не уверен, требовалось ли это для крайне слабого упорядочения памяти PowerPC, или был возможен другой выбор.

https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html показывает некоторые возможные реализации на различных архитектурах.В нем упоминается несколько альтернатив для ARM.

---

На AArch64 мы получаем это для исходной версии thread1 на C ++:

thread1():
    adrp    x0, .LANCHOR0
    mov     w1, 1
    add     x0, x0, :lo12:.LANCHOR0
.L2:
    ldaxr   w2, [x0]            @ load-linked with acquire semantics
    stlxr   w3, w1, [x0]        @ store-conditional with sc-release semantics
    cbnz    w3, .L2             @ retry until exchange succeeds

    add     x1, x0, 8           @ the compiler noticed the variables were next to each other
    ldar    w1, [x1]            @ load-acquire

    str     w1, [x0, 12]        @ r1 = load result
    ret

Переупорядочение не может произойти, потому что выпуск AArch64-магазины последовательный -релиз, не простой выпуск.Это означает, что они не могут переупорядочить с более поздними загрузками.

Но на гипотетической машине, которая также имеет или вместо этого имеет простую атомизацию LL / SC, легко видеть, что acq_rel не останавливается позжезагружает в разные строки кэша, чтобы он становился глобально видимым после LL, но до SC обмена.

---

Если exchange реализовано с одной транзакцией, как в x86, то загрузка иХранилище смежно в глобальном порядке операций с памятью, тогда, конечно, никакие более поздние операции не могут быть переупорядочены с помощью обмена acq_rel, и это в основном эквивалентно seq_cst.

Но LL / SC не должен бытьнастоящая атомарная транзакция, которая дает атомарность RMW для этого местоположения .

Фактически, одиночная инструкция asm swap могла бы иметь ослабленную семантику acq_rel.SPARC64 нуждается в membar инструкциях вокруг его swap инструкции, поэтому в отличие от x86 xchg он не является seq-cst сам по себе.(SPARC имеет действительно хорошую / понятную человеку мнемонику инструкций, особенно по сравнению с PowerPC. Ну, в принципе, все более читабельно, чем PowerPC.)

Таким образом, для C ++ 11 не имеет смысла требовать, чтобы это было:это повредило бы реализацию на процессоре, который иначе не нуждался бы в барьере загрузки магазина.

Answer 2

Стандарт не определяет модель памяти C ++ с точки зрения того, как операции упорядочены вокруг атомарных операций с определенным параметром упорядочения.Вместо этого для модели упорядочения получения / выпуска она определяет формальные отношения, такие как «синхронизирует с» и «происходит до», которые определяют, как данные синхронизируются между потоками.

N4762, §29.4.2 - [atomics.order]

Атомная операция A, которая выполняет операцию освобождения атомарного объекта M, синхронизируется с атомарной операцией B, которая выполняет операцию получения для M и получает свое значение от любого побочного эффекта впоследовательность освобождения, возглавляемая A.

В §6.8.2.1-9 стандарт также гласит, что, если хранилище A синхронизируется с нагрузкой B, все, что упорядочено перед A, происходит между нитями «before-before»все, что упорядочено после B.

Во втором примере не установлено никакого отношения "синхронизирует с" (и, следовательно, происходит до того, как возникнет другой поток) (первый еще слабее), потому что отношения во время выполнения (которые проверяют возврат)значения из нагрузок) отсутствуют.
Но даже если вы проверите возвращаемое значение, это не поможетПоэтому операции exchange на самом деле ничего не «освобождают» (т. е. никакие операции с памятью не выполняются до выполнения этих операций).Neiter делает операции с атомной нагрузкой «приобретением» чего-либо, поскольку после нагрузок никакие операции не упорядочены.

Поэтому, согласно стандарту, каждый из четырех возможных результатов для нагрузок в обоих примерах (включая 0 0) равендействительный.На самом деле гарантии, данные стандартом, не сильнее memory_order_relaxed для всех операций.

Если вы хотите исключить результат 0 0 из своего кода, все 4 операции должны использовать std::memory_order_seq_cst.Это гарантирует единый общий порядок задействованных операций.

Answer 3

in Порядок Release-Acquire для создания точки синхронизации между двумя потоками нам нужен атомарный объект M, который будет таким же в обеих операциях

атомарная операция A, которая выполняет операцию освобождения атомарного объекта M синхронизируется с атомарной операцией B, который выполняет операцию получения для M и получает свое значение от любого побочного эффекта в последовательности деблокирования, возглавляемой A.

или более подробно:

Если элементарное хранилище в потоке A помечено memory_order_release и атомная нагрузка в потоке B из той же переменной помечено memory_order_acquire, все записи в память (неатомарные и расслабленные атомарные), которые произошли - до атомарного хранилища с точки зрения потока A,становятся видимыми побочные эффекты в теме B.То есть, как только атомная загрузка будет завершена, поток B гарантированно увидит все, что поток A записал в память.

Синхронизация установлена ​​толькомежду потоками, освобождающими и получающими одинаковую атомную переменную .

     N = u                |  if (M.load(acquire) == v)    :[B]
[A]: M.store(v, release)  |  assert(N == u)

здесь точка синхронизации на M store-release и load-receive (которые берут ценность из магазина-релиза!)как результат хранилище N = u в потоке A (до выхода из магазина в M), видимое в B (N == u) послезагрузка-получение для того же M

, если взять пример:

atomic<int> x, y;
int r1, r2;

void thread_A() {
  y.exchange(1, memory_order_acq_rel);
  r1 = x.load(memory_order_acquire);
}
void thread_B() {
  x.exchange(1, memory_order_acq_rel);
  r2 = y.load(memory_order_acquire);
}

что мы можем выбрать для общего атомного объекта M?скажи x?x.load(memory_order_acquire); будет точкой синхронизации с x.exchange(1, memory_order_acq_rel) (memory_order_acq_rel включает memory_order_release (более сильный) и exchange включает store), если x.load значение нагрузки от x.exchange, а основной будет синхронизированная нагрузка после получения (быть в коде после получения ничего не существует) с магазинами до выпуска (но снова перед обменом ничего в коде).

правильное решение (искать почти точно вопрос ) может быть следующим:

atomic<int> x, y;
int r1, r2;

void thread_A()
{
    x.exchange(1, memory_order_acq_rel); // [Ax]
    r1 = y.exchange(1, memory_order_acq_rel); // [Ay]
}

void thread_B()
{
    y.exchange(1, memory_order_acq_rel); // [By]
    r2 = x.exchange(1, memory_order_acq_rel); // [Bx]
}

предположим, что r1 == 0.

Все модификации любой конкретной атомной переменной происходят в общем порядке, характерном дляэто одна атомная переменная.

у нас есть 2 модификации y: [Ay] и [By].потому что r1 == 0 это означает, что [Ay] происходит до [By] в общем порядке изменения y.из этого - [By] читать значение, сохраненное [Ay].таким образом, у нас есть следующее:

• A записывается в x - [Ax]
• A делает store-release [Ay] в y после этого ( acq_rel включает выпуск , exchange включает store )
• B получение данных о загрузкес y (* [By] значение сохраняется [Ay]
• после завершения атомного захвата нагрузки (на y) поток B гарантированно увидит всепоток A записывал в память перед выпуском из хранилища (y), поэтому он просматривает побочные эффекты [Ax] - и r2 == 1

---

другое возможное решение использовать atomic_thread_fence

atomic<int> x, y;
int r1, r2;

void thread_A()
{
    x.store(1, memory_order_relaxed); // [A1]
    atomic_thread_fence(memory_order_acq_rel); // [A2]
    r1 = y.exchange(1, memory_order_relaxed); // [A3]
}

void thread_B()
{
    y.store(1, memory_order_relaxed); // [B1]
    atomic_thread_fence(memory_order_acq_rel); // [B2]
    r2 = x.exchange(1, memory_order_relaxed); // [B3]
}

еще раз, потому что все модификации атомарной переменной y происходят в общем порядке. [A3] будет до [B1] или до визыверсия

1. , если [B1] до [A3] - [A3] читать значение, сохраненное [B1] => r1 == 1.

2. если [A3] до [B1] - [B1] - это считанное значение, хранящееся в [A3] и Fence-fENCE синхронизации :

Ограничение освобождения [A2] в потоке A синхронизируется с ограничителем получения [B2] в потоке B, если:

• Существует атомарный объект y,
• Существует атомарная запись [A3] (с любым порядком памяти), которая изменяет y в потоке A
• [A2] секвенируется до [A3] в потоке A

• Существует элементарное чтение [B1] (с любым порядком памяти) в потоке B

• [B1] читает значение, записанное [A3]

• [B1] упорядочено до [B2] в потоке B

В этом случае все магазины ([A1]), которыеПоследовательность - до [A2] в потоке A произойдет - до того, как все нагрузки ([B3]) из тех же мест (x), сделанные в потоке B после [B2]

, так что [A1] (сохранить от 1 до x) будет раньше и иметь видимый эффект для [B3] (загрузить форму x и сохранить результат в r2).так будет загружаться 1 с x и r2==1

[A1]: x = 1               |  if (y.load(relaxed) == 1) :[B1]
[A2]: ### release ###     |  ### acquire ###           :[B2]
[A3]: y.store(1, relaxed) |  assert(x == 1)            :[B3]

Answer 4

В исходной версии можно увидеть r1 == 0 && r2 == 0, потому что не требуется, чтобы хранилища распространялись на другой поток до того, как он его прочитает.Это не переупорядочение операций любого из потоков, а, например, чтение устаревшего кэша.

Thread 1's cache   |   Thread 2's cache
  x == 0;          |     x == 0;
  y == 0;          |     y == 0;

y.exchange(1, std::memory_order_acq_rel); // Thread 1
x.exchange(1, std::memory_order_acq_rel); // Thread 2

Выпуск в потоке 1 игнорируется потоком 2, и наоборот,В абстрактной машине нет согласованности со значениями x и y в потоках

Thread 1's cache   |   Thread 2's cache
  x == 0; // stale |     x == 1;
  y == 1;          |     y == 0; // stale

r1 = x.load(std::memory_order_relaxed); // Thread 1
r2 = y.load(std::memory_order_relaxed); // Thread 2

Вам нужно больше потоков, чтобы получить "нарушения причинности" с приобретениемпары / release, как обычные правила упорядочения, в сочетании с «становится видимым побочным эффектом» заставляют по крайней мере один из load s видеть 1.

Без потери общности, давайте предположим,этот поток 1 выполняется первым.

Thread 1's cache   |   Thread 2's cache
  x == 0;          |     x == 0;
  y == 0;          |     y == 0;

y.exchange(1, std::memory_order_acq_rel); // Thread 1

Thread 1's cache   |   Thread 2's cache
  x == 0;          |     x == 0;
  y == 1;          |     y == 1; // sync 

Релиз в потоке 1 образует пару с получением в потоке 2, и абстрактная машина описывает согласованное y в обоих потоках

r1 = x.load(std::memory_order_relaxed); // Thread 1
x.exchange(1, std::memory_order_acq_rel); // Thread 2
r2 = y.load(std::memory_order_relaxed); // Thread 2