В настоящей статье мы поговорим о том, как в абсолютно корректном C++-коде можно заглянуть в будущее, совершенно об этом не подозревая. Эта статья родилась из спора, который развернулся под этим ответом на StackOverflow. До этого спора я был совершенно уверен, что C++ гарантирует получение последнего значения объекта std::atomic, когда к нему применяются операции чтения-модификации-записи (ЧМЗ, англ. Read-Modify-Write). Ниже мы рассмотрим, почему это не более чем заблуждение, а также разберём, почему нужно осторожно относиться к прилагательному «последний», говоря об операциях над объектами.

Зачин

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

#include <thread>
#include <print>

int main()
{
    alignas(64) std::atomic<int> timeline{0};
    alignas(64) std::atomic<int> seer{0};

    std::jthread t1([&](){
        timeline.store(1, std::memory_order::relaxed);  // П1-1
        int tmp = timeline.load(std::memory_order::relaxed); // П1-2
        seer.store(tmp, std::memory_order::relaxed); // П1-3
    });
    std::jthread t2([&](){
        auto timepoint = seer.load(std::memory_order::relaxed); // П2-1
        if(timepoint) // П2-2
            if(!timeline.fetch_add(timepoint + 1, std::memory_order::relaxed)) // П2-3
                std::print("Time-traveled!"); // П2-4
    });
}

Мы определяем две переменные, инициализируя их нулём:

alignas(64) std::atomic<int> timeline{0};
alignas(64) std::atomic<int> seer{0};

Они будут использоваться в разных потоках, поэтому делаем их атомарными. Выравниваем их по границе в 64 байта, чтобы гарантировать их нахождение в разных кэш-линиях (предполагается, что размер кэш-линии равен 64 байтам). timeline у нас будет отвечать за разделяемый между потоками ресурс, который оба изменяют; seer будет изменяться только в одном потоке, но может служить хранителем знания о timeline. Т. е. легенда такая: Есть два потока одного сущего, время в котором дискретно, и каждый из потоков может двигать его вперёд. Оракул есть некая сущность, также пребывающая в обоих потоках, к услугам которой прибегают для уточнения состояния шкалы времени. Ожидается, что каждый поток смещает шкалу не более чем на один пункт.

Теперь рассмотрим код первого потока:

timeline.store(1, std::memory_order::relaxed);  // П1-1
int tmp = timeline.load(std::memory_order::relaxed); // П1-2
seer.store(tmp, std::memory_order::relaxed); // П1-3

Здесь (как и во втором потоке) мы используем исключительно std::memory_order::relaxed, потому что нам не нужна синхронизация, только атомарность, как мы наивно полагаем (у нас «есть» гарантии!). Итак, мы помещаем 1 в timeline, затем считываем то, что записали в tmp, и уже это считанное значение помещаем в seer. Строго говоря, П1-2 и П1-3 можно совместить в одну строку, но раздельно получается нагляднее. Или в терминах легенды: Временная шкала смещается в первую позицию, что немедленно прозревает оракул.

Но самое интересное происходит во втором потоке:

auto timepoint = seer.load(std::memory_order::relaxed); // П2-1
if(timepoint) // П2-2
    if(!timeline.fetch_add(timepoint + 1, std::memory_order::relaxed)) // П2-3
        std::print("Time-traveled!"); // П2-4

Считываем значение seer, удостоверяемся, что оно ненулевое, после чего атомарно инкрементируем timeline. std::fetch_add() возвращает значение timeline, которое эта переменная принимала до выполнения операции. Если timeline находилась в своём изначальном состоянии (нуля), то мы выполняем П2-4 и печатаем текст в консоль. По-легендарному это можно записать так: Законы мира запрещают второму потоку смещать шкалу начала времён, разрешается двигать лишь ранее изменённую — в этом случае она смещается на одну позицию вправо. Благодаря этому закону, путешествия во времени полностью исключены. Ежели оракул возвестит о ранее совершённом временном сдвиге, шкала смещается ещё на одну позицию.

Но я утверждаю, что ситуация, при которой временная шкала сместится сразу на два пункта, возможна, но тогда и только тогда, когда оракул узрел значение шкалы из грядущего, тогда как потоку текущему ведомо лишь настоящее. Т. е. налицо путешествие во времени (оракула).

Правда, в рамках легенды этого доказать не получится, потому что описанное в ней «мироустройство» действительно не позволяет такой ситуации произойти. А вот если мы отринем язык легенд и вооружимся языком техническим, мы сумеем доказать путешествие во времени.

Путешествие

Для начала давайте попробуем разобраться в терминах C++, что у нас вообще в коде происходит и какие гарантии в нём присутствуют. Часть гарантий, описывающих ход выполнения инструкций, описана в стандарте в разделах basic.exec и atomics.order. Мы будем их упоминать далее, так что предполагается знакомство с ними (хотя бы в общих чертах). Отдельно хочется выделить следующую гарантию:

Атомарные операции чтения-модификации-записи должны всегда читать последнее значение (в неком едином порядке изменений), записанное в переменную до последующей записи, ассоциированной с данной операцией.

Оригинал

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

Для меня эта цитата всегда сводилась к следующему: «должны всегда читать последнее значение». Именно так и никак иначе я читал вышеприведённый текст; мы ещё к нему вернёмся, а пока давайте разберёмся с тем, что должно произойти в нашем C++-коде, чтобы он напечатал текст в консоль.

Для этого нужно соблюдение двух условий: if(timepoint) и if(!timeline.fetch_add(...)), т. е. timepoint должна быть единицей, и вызов fetch_add(...) должен вернуть ноль. Исходя из кода первого потока:

timeline.store(1, std::memory_order::relaxed);  // П1-1
int tmp = timeline.load(std::memory_order::relaxed); // П1-2
seer.store(tmp, std::memory_order::relaxed); // П1-3

seer, а значит и timepoint, становится единицей тогда и только тогда, когда timeline уже была выставлена в единицу. Следовательно, учитывая приведённую выше цитату из стандарта, fetch_add(...), будучи атомарной операцией ЧМЗ, должна вернуть последнее записанное значение переменной timeline, а мы знаем, что это единица, иначе мы бы не «провалились» в вышестоящее условие. Из этого следует, что программа никогда не может выполнить std::print("Time-traveled!"), это попросту невозможно! Это всё логически вытекает из правил, описанных в стандарте.

Но я сказал, что такая ситуация возможна, как же так? Дело в том, что логика верна, а вот предпосылка — нет. Цитата выше мною была истолкована неверно, что делает все последующие логические построения бесполезными. Давайте ещё раз обратимся к этой цитате и на этот раз попытаемся понять, что же она реально означает. Самым важным в этой цитате является слово «<...> последнее значение <...>», оно даже уточнено: «последнее в порядке изменения (ПИ)». А это однозначно говорит о том, что если мы выполнили timeline.store(1, std::memory_order::relaxed), то последующий timeline.fetch_add(timepoint + 1, std::memory_order::relaxed) обязан вернуть единицу. Но «последующий» где? В «едином ПИ». А что это такое?

Это абстрактное понятие (intro.races/p4), которое описывает череду изменений одного атомарного объекта, которая может быть произвольной, но обязательно должна быть единственной в рамках одного исполнения. К примеру, если у вас есть некий атомарный объект A и программа, в которой туда, скажем, три потока записывают значения от 1 до 3, то могут получиться следующие ПИ: {1,2,3}, {3,2,1}, {3,1,2} и т. д. Но в рамках одного исполнения только один из этих порядков возможен, и каждый поток может увидеть только его. Стандартом запрещено, чтобы, скажем, первый поток увидел {1,2,3}, а второй — {2,1,3}, но при этом допускается, что первый увидел {1,2,3}, а второй лишь {2,3}. Т. е. каждый поток должен видеть согласованный ПИ, но совершенно не обязательно весь.

Итак, слово «последний» имеет однозначное трактование в стандарте и относится исключительно к ПИ, оно не имеет никакого отношения к людскому понятию времени. Следовательно, последнее значение в ПИ и последнее значение во времени могут существовать одновременно и быть разными! Это важно, но мы пока на этом останавливаться не будем.

Исходя из всего вышесказанного, получается, что наша цитата говорит лишь о том, что атомарные операции ЧМЗ являются атомарными. Это просто «масло масляное», не более того: если ЧМЗ возвращает значение N, а записывает M, то в ПИ это всегда будет выглядеть как {..., N, M,...} (при условии, что поток K видел оба значения); ничто не может вклиниться между N и M. Это просто констатация неделимости операции.

Разобрались с тем, что atomics.order/p9 за нас ничего доказать не может, теперь давайте попробуем зайти с другой стороны и, используя ПИ, попытаемся доказать, что ситуация с путешествием во времени невозможна. Ещё раз приведу код обоих потоков для упрощения понимания:

std::jthread t1([&](){
    timeline.store(1, std::memory_order::relaxed);  // П1-1
    int tmp = timeline.load(std::memory_order::relaxed); // П1-2
    seer.store(tmp, std::memory_order::relaxed); // П1-3
});
std::jthread t2([&](){
    auto timepoint = seer.load(std::memory_order::relaxed); // П2-1
    if(timepoint) // П2-2
        if(!timeline.fetch_add(timepoint + 1, std::memory_order::relaxed)) // П2-3
            std::print("Time-traveled!"); // П2-4
});

Чтобы доказать возможность исполнения выражения П2-4, необходимо и достаточно показать, что П2-3 происходит после (happens after) П1-1. Начнём с первого потока: П1-3 следует за (инверсия sequenced before) П1-2, которое, в свою очередь, следует за П1-1. Из этого вытекает, что П1-3 происходит после П1-1. Это очень простая логика, которая использует элементарные однопоточные правила, диктующие, что набор выражений, записанных друг за другом, должен исполняться в порядке записи. То же самое будет происходить и во втором потоке, поэтому отдельно проговаривать его не стану.

В коде также присутствует набор зависимостей, например, П1-3 зависит от П1-2. Эти зависимости ничего в нашей логике изменить не могут и лишь усложняют текст, поэтому я опустил их явное перечисление, но они нужны, чтобы компилятор не мог поменять местами выражения. Об этом полезно знать в общем, но для данной статьи это не важно.

Также мы можем выжать из нашего кода ещё одну зависимость (atomics.order/p3): когда условие if(timepoint) исполняется, это означает, что ранее в seer была записана единица, а это, в свою очередь, означает, что П2-3 когерентно упорядоченно после (инверсия coherence-ordered before) П1-3. К сожалению, это всё, что можно сказать о нашем коде. Чтобы построить отношение происходит после между находящимися в разных потоках П2-3 и П1-1, необходимо задействовать более строгие гарантии, которые наш код, в силу его «расслабленности», не предоставляет. Таким образом, мы не можем доказать, что std::print("Time-traveled!") никогда не будет выполнен, используя лишь терминологию стандарта.

Но если что-то явно не запрещено в стандарте, вовсе не означает, что такое поведение разрешено. Может, это дефект в нём! Давайте спустимся на уровень ниже абстрактной машины C++, чтобы посмотреть на то, какие условия могут привести к исполнению П2-4 на некой абстрактной архитектуре, в которой используется вариация MESI-протокола и буфер записи.

Для достижения желаемого следующая цепочка событий должна произойти. Исполняя П1-1, ЦПУ1 помещает запись единицы в timeline в буфер записи; кэш-линия, содержащая timeline, в ЦПУ1 отсутствует, поэтому она запрашивается извне. П1-2 считывает значение прямо из буфера записи, а затем П1-3 помещает запись единицы в seer в буфер записи; кэш-линия, содержащая seer, в ЦПУ1 присутствует, а потому seer в буфере долго не задерживается и «проваливается» в кэш.

В это время ЦПУ2 запрашивает кэш-линию с seer, получает её от ЦПУ1 и записывает единицу в timepoint, исполняя П2-1. Затем он доходит до П2-3, читает timeline, находящуюся в его кэше и равную нулю, записывает туда двойку и исполняет П2-4, печатая Time-traveled!!

Вот так вот просто, это банальная перестановка двух операций записи по различным адресам (англ. Store-Store reordering) в первом потоке. Поэтому мы и не смогли доказать обратного с помощью стандарта — это абсолютно нормальная, рабочая ситуация: путешествие во времени возможно! А стало оно возможным благодаря двум особенностям, которые применяются в нашей абстрактной архитектуре:

1. Операция чтения может считать необходимое ей значение из буфере записи, если оно в нём есть. Т. е. дело до кэша даже не доходит. В англоязычной литературе это поведение известно как «store-buffer forwarding» или «store-load forwarding».

2. Перемещение данных из буфера записи в кэш может не соблюдать очерёдность, с которой данные попадали в буфер. В нашем примере seer попадает в буфер после timeline, но покидает его раньше. Следовательно, наша архитектура позволяет освобождать буфер записи в любом порядке.

Конечно, это всё очень интересно, все эти абстрактные рассуждения, модели, архитектуры, но что там в реальности? Если взять архитектуру x86, то в ней применяется первая оптимизация, но вторая запрещена: буфер записи x86-архитектуры представляется собой очередь (FIFO). Так что на традиционных x86-процессорах вы Time-traveled! совершенно точно не увидите. А вот в другой распространённой архитектуре ARM обе эти оптимизации возможны, а значит, могут попасться такие чипы, в которых вы сможете лицезреть желаемый вывод. Конечно, я отдаю себе отчёт, что с кодом из статьи такое произойти вряд ли может — уж слишком он упрощён. Но добавив циклов и прочих задержек, мы вполне можем получить этот результат, потому что архитектура его допускает.

Послесловие

Изначально я не собирался писать текст легенды в первом разделе, но текст рождает себя сам, и в результате легенда оказалась действительно кстати. Ведь именно так, как описано в легенде, мы и воспринимаем мир, а следовательно, и код: как некий набор последовательных действий, порядок которых может быть неизвестен, но он совершенно точно определён. Но чем дальше мы уходили от легенды и погружались в технические детали, тем менее адекватной оставалась такая картина мира. Она имеет право на существование и в многопоточном коде, но только в случае его последовательной согласованности (англ. sequential consistency). А это лишь одна, самая строгая модель; как только мы ослабляем гарантии, всё превращается в «Дикий Запад».

Проблема в том, что перейти от последовательной согласованности к «Дикому Западу» очень просто, для этого достаточно спуститься на уровень атомарных переменных, а потом изменить передаваемый по умолчанию std::memory_order на что-то менее строгое. Я видел такое не раз: люди просто выставляют std::memory_order::relaxed, потому что им кажется, что так будет быстрее. Но далеко не всегда они обладают достаточной квалификацией, чтобы оценить все последствия. Да даже когда обладают: многопоточный код в целом нетривиален, а писать правильно алгоритмы на низкоуровневых примитивах — чрезвычайно сложная задача. Честно говоря, я не знаю в программировании ничего сложнее написания низкоуровневого многопоточного кода, потому что наш мозг плохо приспособлен к анализу параллельного исполнения.

Причём начинаешь действительно ценить ту работу, что провел комитет стандартизации C++ по разработке модели памяти и исполнения в многопоточной среде. Анализ с помощью абстрактной C++-модели значительно упрощает понимание, ведь он сильно сокращает количество сущностей и отношений между ними. В статье я привёл более низкую, но тоже абстрактную модель с буфером записи, рассуждать в рамках которой уже гораздо сложнее, чем оперировать понятиями стандарта. Тем не менее даже эта модель сильно упрощена. В действительности процессоры оперируют куда большим количеством различных элементов, и я даже не буду притворяться, что я их все знаю.

Однако, хотя я и предпочитаю рассуждать исключительно в терминах C++, иногда полезно спускаться ниже. Хотя бы по той причине, что не всё удаётся описать с их помощью. Как это и получилось в данной статье: нам не удалось произвести доказательство исключительно C++-терминами, поэтому мы спустились ниже, что позволило найти контр-пример. И хотя я неустанно твержу, что от низкоуровневого программирования многопоточных сред нужно держаться подальше, реальность такова, что не всем это удаётся. Кто-то ведь должен писать lock-free и wait-free алгоритмы. Да и просто интересно же в конце концов!

Кстати об интересе, из неопределённого (выведет/не выведет) кода в статье можно легко сделать определённый (не выведет) множеством способов. Какие-то из них требуют знания архитектуры, под которую будет собираться код, другие — нет. Но все они довольно просты (буквально одно-два изменения). Я их приводить не буду, пусть это останется задачей для читателя.