Порядок использования памяти в C11

Я читал о том, что имеет отношение зависимости и упорядочено по зависимостям, которое использует его в своем определении 5.1.2.4(p16):

Оценка A упорядочивается по зависимости перед оценкой B, если:

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

- для некоторой оценки X, A упорядочивается по зависимости перед X, а X несет зависимость от B.

Поэтому я попытался придумать пример, в котором это могло бы быть полезно. Вот:

static _Atomic int i;

void *produce(void *ptr){
    int int_value = *((int *) ptr);
    atomic_store_explicit(&i, int_value, memory_order_release);
    return NULL;
}

void *consume(void *ignored){
    int int_value = atomic_load_explicit(&i, memory_order_consume);
    int new_int_value = int_value + 42;
    printf("Consumed = %d\n", new_int_value);
}

int main(int args, const char *argv[]){
    int int_value = 123123;
    pthread_t t2;
    pthread_create(&t2, NULL, &produce, &int_value);

    pthread_t t1;
    pthread_create(&t1, NULL, &consume, NULL);

    sleep(1000);
}

В функции void *consume(void*) int_value несет зависимость для new_int_value, поэтому, если atomic_load_explicit(&i, memory_order_consume); считывает значение, записанное некоторым atomic_store_explicit(&i, int_value, memory_order_release);, тогда new_int_value вычисление упорядоченное-зависимое-перед atomic_store_explicit(&i, int_value, memory_order_release);.

Но какие полезные вещи может дать нам упорядоченная ранее зависимость?

В настоящее время я думаю, что memory_order_consume вполне можно заменить на memory_order_acquire, не вызывая гонки за данные ...


c multithreading c11 stdatomic
person Some Name    schedule 18.04.2019    source источник

Ответы (2)


arrow_upward
11
arrow_downward

consume дешевле, чем acquire. Все процессоры (кроме известной слабой модели памяти DEC Alpha AXP 1) делают это бесплатно, в отличие от acquire. (за исключением x86 и SPARC-TSO, где оборудование имеет упорядочение памяти acq / rel без дополнительных барьеров и специальных инструкций.)

На ARM / AArch64 / PowerPC / MIPS / и т. Д. ISA со слабым упорядочением consume и relaxed - единственные упорядочения, которые не требуют каких-либо дополнительных барьеров, только обычные дешевые инструкции по загрузке. т.е. все инструкции загрузки asm являются (как минимум) consume загрузками, кроме Alpha. acquire требует упорядочивания LoadStore и LoadLoad, что является более дешевой барьерной инструкцией, чем полная барьерная инструкция для seq_cst, но все же дороже, чем ничего.

mo_consume похож на acquire только для нагрузок с зависимостью данных от потребляемой нагрузки. например float *array = atomic_ld(&shared, mo_consume);, то доступ к любому array[i] безопасен, если производитель сохранил буфер и затем использовал хранилище mo_release для записи указателя на общую переменную. Но независимые загрузки / сохранения не должны ждать завершения consume загрузки и могут произойти раньше, даже если они появятся позже в программном порядке. Поэтому consume заказывает только самый минимум, не влияя на другие грузы или магазины.

(В принципе, реализовать поддержку семантики consume в оборудовании для большинства конструкций ЦП можно бесплатно, потому что OoO exec не может нарушить истинные зависимости, а загрузка имеет зависимость данных от указателя, поэтому загрузка указателя и затем разыменование его по своей сути упорядочивает эти 2 загрузки только по природе причинно-следственной связи. Если только ЦП не выполняют прогнозирование значений или что-то безумное. Предсказание значений похоже на прогнозирование ветвления, но угадайте, какое значение будет загружено, а не в какую сторону будет идти.

Alpha пришлось сделать несколько сумасшедших вещей, чтобы сделать процессоры, которые действительно могли загружать данные до того, как значение указателя было действительно загружено, когда хранение было выполнено по порядку с достаточными барьерами.

В отличие от магазинов, где в буфере хранилища может происходить переупорядочение между выполнением хранилища и фиксацией в кеш-памяти L1d, загрузки становятся "видимыми" "путем извлечения данных из кэша L1d при их выполнении, а не при окончательном подтверждении вывода на пенсию +. Таким образом, заказывая 2 загрузки по весу. друг друга на самом деле просто означает выполнение этих двух загрузок по порядку. При зависимости данных друг от друга причинно-следственная связь требует этого на ЦП без прогнозирования значений, и на большинстве архитектур правила ISA этого требуют. Таким образом, вам не нужно использовать барьер между загрузкой + с помощью указателя в asm, например для просмотра связанного списка.)

См. также Изменение порядка зависимых нагрузок в ЦП

Но нынешние компиляторы просто сдаются и улучшают consume до acquire

... вместо того, чтобы пытаться сопоставить зависимости C с зависимостями asm data (без случайного нарушения, имея только контрольную зависимость, которую можно было бы обойти с помощью предсказания ветвления + спекулятивного выполнения). Очевидно, компиляторам сложно отследить это и сделать его безопасным.

Сопоставить C с asm нетривиально, потому что, если зависимость находится только в форме условной ветки, правила asm не применяются. Так что трудно определить правила C для mo_consume распространения зависимостей только способами, которые совпадают с тем, что «несет зависимость» в терминах правил asm ISA.

Так что да, вы правы, что consume можно безопасно заменить на acquire, но вы полностью упускаете суть.

У ISA со слабыми правилами упорядочивания памяти действительно есть правила о том, какие инструкции имеют зависимость. Таким образом, даже такая инструкция, как ARM eor r0,r0, которая безоговорочно обнуляет r0, архитектурно требуется, чтобы по-прежнему нести зависимость данных от старого значения, в отличие от x86, где идиома xor eax,eax специально распознается как разрушающая зависимость 2.

См. Также http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

Я также упомянул mo_consume в ответе на Атомарные операции, std :: atomic ‹› и заказ писем.

Сноска 1. Несколько альфа-моделей, которые теоретически могли «нарушить причинно-следственную связь», не выполняли прогнозирования значений, был другой механизм с их банковским кешем. Думаю, я видел более подробное объяснение того, как это было возможно, но комментарии Линуса о том, насколько редко это было на самом деле, интересны.

Линус Торвальдс (ведущий разработчик Linux) в ветке форума RealWorldTech

Интересно, вы сами видели отсутствие причинности на Alpha или просто в руководстве?

Я никогда не видел этого сам и не думаю, что какая-либо из моделей, к которым у меня когда-либо был доступ, действительно это делала. Что на самом деле делало (медленную) инструкцию ПКМ еще более раздражающей, потому что это был просто недостаток.

Даже на процессорах, которые действительно могли изменять порядок нагрузок, на практике это было практически невозможно. Что на самом деле довольно неприятно. Это привело к появлению «ой, я забыл барьер, но все работало нормально в течение десяти лет, с тремя странными сообщениями об ошибках с мест». Разобраться в том, что происходит, чертовски больно.

На каких моделях это действительно было? И как именно они сюда попали?

Я думаю, что это был 21264, и у меня эта тусклая память связана с разделенным кешем: даже если исходный ЦП сделал две записи по порядку (с wmb между ними), ЦП чтения может в конечном итоге получить первую запись отложено (потому что раздел кеша, в который он вошел, был занят другими обновлениями), и сначала будет читать вторую запись. Если эта вторая запись была адресом первой, она могла бы следовать за этим указателем и без барьера чтения для синхронизации разделов кеша могла бы увидеть старое устаревшее значение.

Но обратите внимание на «тусклую память». Возможно, я перепутал это с чем-то другим. Я практически не использовал альфу почти два десятилетия назад. Вы можете получить очень похожие эффекты от прогнозирования стоимости, но я не думаю, что какая-либо альфа-микроархитектура когда-либо делала это.

В любом случае, определенно были версии альфы, которые могли это сделать, и это не было чисто теоретическим.

(ПКМ = чтение asm-инструкции барьера памяти и / или имя функции ядра Linux rmb(), которая обертывает все встроенные asm-файлы, необходимые для этого. Например, на x86, просто барьер для переупорядочения во время компиляции, asm("":::"memory"). Я думаю, что современный Linux удается избежать барьера приобретения, когда требуется только зависимость данных, в отличие от C11 / C ++ 11, но я забываю. Linux переносится только на несколько компиляторов, и эти компиляторы действительно заботятся о поддержке того, от чего зависит Linux, поэтому они легче, чем стандарт ISO C11, приготовить что-то, что работает на практике с настоящими ISA.)

См. Также https://lkml.org/lkml/2012/2/1/521 re: smp_read_barrier_depends() Linux, который необходим в Linux только из-за Alpha. (Но в ответе от Ганса Боэма указывается, что " компиляторы могут, а иногда и удаляют зависимости ", поэтому поддержка C11 memory_order_consume должна быть настолько сложной, чтобы избежать риска поломки. Таким образом, smp_read_barrier_depends потенциально хрупкий.)

Сноска 2: x86 упорядочивает все загрузки независимо от того, несут ли они зависимость данных от указателя или нет, поэтому ему не нужно сохранять «ложные» зависимости, а с набором инструкций переменной длины он фактически сохраняет размер кода xor eax,eax (2 байта) вместо mov eax,0 (5 байтов).

Итак, xor reg,reg стал стандартной идиомой с начала 8086-х годов, и теперь он распознается и фактически обрабатывается как mov, без зависимости от старого значения или RAX. (И на самом деле более эффективно, чем mov reg,0, помимо размера кода: Как лучше всего обнулить регистр в сборке x86: xor, mov или and? )

Но это невозможно для ARM или большинства других слабо упорядоченных ISA, как я уже сказал, им буквально не разрешено это делать.

ldr r3, [something]       ; load r3 = mem
eor r0, r3,r3             ; r0 = r3^r3 = 0
ldr r4, [r1, r0]          ; load r4 = mem[r1+r0].  Ordered after the other load

требуется для внедрения зависимости от r0 и упорядочивания загрузки r4 после загрузки r3, даже если адрес загрузки r1+r0 всегда равен r1, потому что r3^r3 = 0. Но только эту загрузку, а не все другие последующие загрузки; это не препятствие для приобретения или нагрузка для приобретения.

person Peter Cordes    schedule 18.04.2019
comment
Итак, подведем итог mo_consume гарантирует нам, что 2 последующих зависимых груза не будут переупорядочены. На x86 (в отличие от Alpha) он предоставляется бесплатно, как указано в 8.2.3.2 Ни нагрузки, ни магазины не переупорядочиваются с использованием подобных операций. - person Some Name; 19.04.2019
comment
@SomeName: На x86 у нас acquire бесплатно, consume не интересен и не особенный. Но на ARM / AArch64 / PowerPC / MIPS / и т. Д. У нас есть только consume (и relaxed) бесплатно, все остальное требует как минимум дешевых барьеров. (Однако не так дорого, как полные барьеры StoreLoad, необходимые для seq_cst). Модель памяти TSO x86 - seq_cst + буфер хранилища (с переадресацией хранилища), поэтому хранилища могут получить только позже, а все остальное упорядочено. - person Peter Cordes; 19.04.2019
comment
@SomeName: Кроме того, не уверен, что вы имеете в виду под двумя последовательными зависимыми нагрузками. Любое количество загрузок с зависимостью данных от нагрузки consume будет учитывать причинно-следственную связь. например float *array = atomic_load(&shared, mo_consume); позволяет вам перебирать array[i] и просматривать данные, сохраненные другим потоком перед сохранением указателя на shared. Или указатель на структуру, который вы используете с ptr->a, ptr->b и т. Д. Но если вы имеете в виду цепочку нагрузок (например, связанный список), тогда нет, каждый шаг в цепочке должен быть потребляющей нагрузкой, а не каждым другим. (Я не изучал внимательно формулировки в стандарте C для использования.) - person Peter Cordes; 19.04.2019
comment
Итак, важная часть mo_consume, поскольку она не гарантирует видимость упорядоченных действий, выполняемых одним и тем же потоком 5.1.2.4(p15): A выполняет операцию освобождения атомарного объекта M, а в другом потоке выполняет потребляет операцию на M и считывает значение, записанное любым побочным эффектом в последовательности выпуска, озаглавленной A - person Some Name; 19.04.2019
comment
@SomeName: верно, потребление похоже на получение только для нагрузок с зависимостью данных от нагрузки потребления. Независимые загрузки / сохранения могут происходить до этого, не дожидаясь завершения consume загрузки. - person Peter Cordes; 19.04.2019
comment
Я перечитал некоторые части 5.1.2.4 и вижу следующее формальное объяснение разницы между выпуском - приобретением / выпуском - потреблением: выпуск синхронизируется с приобретением, но выпуск не синхронизируется с потребляют. В соответствии с первым маркером межпотока происходит до определения A синхронизируется с X, а X упорядочивается до B, мы можем утверждать, что все действия в потоке, выполняющем выпуск, упорядочены до выпуска (даже с несвязанными ячейками памяти ) видны всем действиям после получения, которые нельзя применить к потреблению из-за отсутствия синхронизации с. - person Some Name; 19.04.2019
comment
@SomeName: я на самом деле (недавно) не читал язык в стандарте, который определяет потребление, я просто знаю, для чего он предполагается с точки зрения раскрытия этого полезного поведения asm. Но да, в этом есть смысл, synchronize-with - это технический язык, который подразумевает, что все, что после этого момента, является после всего, что было до выпуска, и весь смысл consume не в том, чтобы задерживать / блокировать другие операции, чтобы дождаться этого произойдет. - person Peter Cordes; 19.04.2019
comment
вот почему поддержка C11 memory_order_consume должна быть настолько сложной, чтобы вы могли надежно получить желаемый эффект, щедро используя volatile, в отличие от ненадежной реализации потребления? volatile int index = consume_get(); T *volatile p = addr; T r = p[index-index]; дает вам реальный зависимый ноль на реальных компиляторах, потому что обработка простых случаев volatile значений стабильна в отличие от новой семантики потребления, которая имеет тенденцию теряться в промежуточном языке и кандидате для арифметической оптимизации. - person curiousguy; 25.05.2019
comment
@SomeName , поскольку это не гарантирует видимость упорядоченных действий, выполняемых одним и тем же потоком, что может даже означать гарантия видимости текущего действия потока? - person curiousguy; 25.05.2019
comment
@curiousguy: Возможно, но введение 2 хранилищ и 3 перезагрузок через volatile может быть хуже, чем acquire, особенно на AArch64, у которого есть загрузки на аппаратном уровне (со специальной инструкцией загрузки, а не барьером). И, очевидно, намного хуже на x86, где усиление потребления для приобретения бесплатно. Кроме того, я не на 100% уверен, что правила упорядочивания зависимостей в типичных RISC ISA следуют сохранению / перезагрузке через память. Я не рассматривал это, может быть, это все еще нормально по законам причинно-следственной связи, пока ISA не разрешает реализации, которые выполняют прогнозирование значений для нагрузок. - person Peter Cordes; 25.05.2019
comment
Или если вас интересуют только реальные реализации этих ISA, которые на данный момент не выполняют прогнозирования значений. - person Peter Cordes; 25.05.2019

arrow_upward
1
arrow_downward

memory_order_consume в настоящее время не указан, и некоторые продолжаются работать, чтобы исправить это. В настоящее время AFAIK все реализации неявно продвигают его до memory_order_acquire.

person janneb    schedule 18.04.2019
comment
Было бы интересно узнать мотивацию внедрения _1 _... - person Some Name; 18.04.2019
comment
Я думаю, что это было в основном для реализации RCU, см. Работу Пола Маккенни. - person janneb; 18.04.2019
comment
Не указано или полностью указано бесполезным образом? - person curiousguy; 25.05.2019