13.03.2021 13:02
ilammy 3 3700 Источник

В первой статье цикла мы познакомились с простыми неблокирующими алгоритмами, а также рассмотрели отношение “happens before”, позволяющее их формализовать. Следующим шагом мы рассмотрим понятие «гонки данных» (data race), а также примитивы, которые позволяют избежать гонок данных. После этого познакомимся с атомарными примитивами, барьерами памяти, а также их использованием в механизме “seqcount”.


С барьерами памяти некоторые разработчики ядра Linux уже давно знакомы. Первый документ, содержащий что-то похожее на спецификацию гарантий, предоставляемых ядром при одновременном доступе к памяти — он так и называется: memory-barriers.txt. В этом файле описывается целый зоопарк барьеров вместе с ожидаемым поведением многопоточного кода в ядре. Также там описывается понятие «парных барьеров» (barrier pairing), что похоже на пары release-acquire операций и тоже помогает упорядочивать работу потоков.


В этой статье мы не будем закапываться так же глубоко, как memory-barriers.txt. Вместо этого мы сравним барьеры с моделью acquire и release-операций и рассмотрим, как они упрощают (или, можно сказать, делают возможной) реализацию примитива “seqcount”. К сожалению, даже если ограничиться лишь наиболее популярными применениями барьеров — это слишком обширная тема, поэтому о полных барьерах памяти мы поговорим в следующий раз.



Гонки данных и атомарные операции


Рассматриваемое здесь определение гонок данных впервые сформулировано в C++11 и с тех пор используется многими другими языками, в частности, C11 и Rust. Все эти языки довольно строго относятся к совместному доступу к данным без использования мьютексов: так позволяется делать только со специальными атомарными типами данных, используя атомарное чтение и атомарную запись в память.


Гонка данных возникает между двумя операциями доступа к памяти, если 1) они происходят одновременно (то есть, не упорядочены отношением «A происходит перед B»), 2) одна из этих операций — это запись, и 3) хотя бы одна из операций не является атомарной. В результате гонки данных (с точки зрения C11/C++11) может произойти что угодно — неопределённое поведение. Отсутствие гонок данных ещё не означает невозможность «состояний гонки» (race conditions) в алгортимах: гонка данных — это нарушение стандарта языка, а состояние гонки — это ошибка в реализации алгортима, вызванная неправильным использованием мьютексов, acquire-release семантики, или и того и другого.


Избежать гонок данных и вызываемого ими неопределённого поведения очень легко. Самый простой способ — это работать с данными только из одного потока. Если данные должны быть доступны другим потокам, то работа с ними должна быть упорядочена нужным вам образом с помощью acquire и release-операций. Наконец, вы можете воспользоваться атомарными операциями.


C11, C++11, Rust предоставляют целый спектр атомарных операций доступа к памяти, гарантирующих некоторый порядок доступа (memory ordering). Нас интересуют три вида: acquire (для чтения), release (для записи), и relaxed (для того и другого). Что делают acquire и release вам уже должно быть ясно, в ядре Linux это называется smp_load_acquire() и smp_store_release(). А вот relaxed-операции обеспечивают так называемый «нестрогий» порядок доступа к памяти. Нестрогие операции не создают никаких отношений порядка между потоками. Их единственная задача — это предотвратить гонку данных и избежать нарушения строгой буквы стандарта.


На практике, Linux ожидает от компиляторов и процессоров больше гарантий, чем того требуют стандарты языков программирования. В частности, в ядре считается, что обычные, неатомарные операции доступа к памяти не приводят к неопределённому поведению лишь потому, что где-то там другой процессор трогает тот же участок памяти. Нет, естественно, при гонке данных считанное или записанное значение может быть неопределённым и содержать что попало. Например, половинку старого и половинку нового значения; и если это указатель, то разыменовывать его не стоит. Но от гонки данных как таковой компьютер не взрывается.


Кроме того, компиляторы порой очень изобретательны при оптимизациях и им очень многое позволяется делать, при условии сохранении наблюдаемого поведения в одном потоке (даже ценой неожиданного поведения во всех остальных потоках). Так что идея нестрого упорядоченного — но строго атомарного — доступа к памяти оказывается полезна и в ядре Linux, где для этих целей существуют макросы READ_ONCE() и WRITE_ONCE(). Считается хорошим стилем использовать READ_ONCE() и WRITE_ONCE(), когда вам нужны явные операции с памятью, что мы отныне и будем делать в примерах кода.


Эти макросы уже встречались в первой части:


    поток 1                           поток 2
    -----------------------------     ------------------------
    a.x = 1;
    smp_wmb();
    WRITE_ONCE(message, &a);          datum = READ_ONCE(message);
                                      smp_rmb();
                                      if (datum != NULL)
                                        printk("%x\n", datum->x);

Они похожи на smp_load_acquire() и smp_store_release(), но первый аргумент тут является lvalue, а не указателем (внимание на присваивание message в потоке 1). При отсутствии иных механизмов, избегающих гонок данных (вроде захваченного спинлока), настоятельно рекомендуется использовать READ_ONCE() и WRITE_ONCE() при обращении к данным, доступным другим потокам. Сами эти операции не упорядочены, но всегда используются вместе с чем-то ещё, вроде другого примитива или механизма синхронизации, который уже обладает release и acquire семантикой. Так атомарные операции оказываются в итоге упорядочены нужным образом.


Пусть, например, у вас есть struct work_struct, которые в фоне затирают ненужные массивы единичками. После запуска задачи у вас есть другие важные дела и массив вам не нужен. Когда понадобится, то вы делаете flush_work() и гарантированно получаете единички. flush_work(), как и pthread_join(), обладает acquire-семантикой и синхронизируется с завершением struct work_struct. Поэтому читать из массива можно и обычными операциями чтения, которые гарантированно произойдут после записи, выполненной задачей. Однако, если вы забиваете единичками регионы, которые могут пересекаться и обновляться из нескольких потоков, то им следует использовать WRITE_ONCE(a[x], 1), а не просто a[x] = 1.


Всё становится сложнее, если release и acquire-семантика обеспечивается барьерами памяти. Рассмотрим в качестве примера реальный механизм “seqcount”.



Seqcounts


Seqcount (sequence counter) — это специализированный примитив, сообщающий вам, а не изменилась ли структура данных, пока вы с ней работали. У seqcounts довольно узкая зона применимости, где они показывают себя хорошо: защищаемых ими данных должно быть немного, при чтении не должно быть никаких побочных эффектов, а записи должны быть сравнительно быстрыми и редкими. Но зато читатели никогда не блокируют писателей и никак не влияют на их кеш. Эти довольно существенные преимущества, когда вам нужна масштабируемость.


Seqcount работает с одним писателем и множеством читателей. Обычно seqcount комбинируется с мьютексом или спинлоком для того, чтобы гарантировать эксклюзивный доступ писателям; в результате получается примитив seqlock_t, как его называют в Linux. Вне ядра слова seqlock и seqcount порой используются как синонимы.


Фактически, seqcount — это счётчик поколений. Нечётный номер поколения означает, что в этот момент времени со структурой данных работает писатель. Если читатель увидел нечётный номер на входе в критическую секцию или если номер изменился на выходе из критической секции, то структура данных возможно изменялась. Читатель мог увидеть лишь несогласованную часть этих изменений, так что ему следует повторить всю свою работу с начала. Для корректного функционирования seqcount читатель должен корректно опознавать начало и конец работы писателя. По паре load-acquire и store-release операций на каждую сторону. Если раскрыть все макросы, то простая [и неправильная] реализация seqcount на уровне отдельных операций с памятью выглядит примерно так:


    поток 1 (писатель)                 поток 2 (читатель)
    --------------------------------    ------------------------
                                        do {
    WRITE_ONCE(sc, sc + 1);                 old = smp_load_acquire(&sc) & ~1;

    smp_store_release(&data.x, 123);        copy.y = READ_ONCE(data.y);
    WRITE_ONCE(data.y, 456);                copy.x = smp_load_acquire(&data.x);

    smp_store_release(&sc, sc + 1);     } while(READ_ONCE(sc) != old);

Этот код слегка похож на «передачу сообщений» из первой части. Здесь видно две пары load-acquire — store-release операций: для sc и для data.x. И довольно легко показать, что они обе необходимы:


  • Когда поток 2 выполняется после потока 1, то при первом чтении sc он должен увидеть значение, которое поток 1 туда записал вторым присваиванием. Пара smp_store_release() и smp_load_acquire() здесь гарантирует, что чтение произойдёт после записи.
  • Когда потоки исполняются одновременно, то если поток 2 уже увидел новое значение какого-либо поля — пусть data.x — то он должен увидеть и новое значение sc при проверке цикла. Пара smp_store_release() и smp_load_acquire() здесь гарантирует, что как минимум первый инкремент sc будет видно и поток 2 уйдёт на второй круг.

Вопрос на самопроверку: зачем читатель делает «& ~1»?


Но если внимательно присмотреться и подумать*, то в коде есть хитрая ошибка! Так как писатель не делает ни одной acquire-операции, то присваивание data.y в принципе может произойти ещё до первого инкремента sc. Конечно, можно психануть и делать вообще всё исключительно через load-acquire/store-release, но это пальба из пушки по воробьям и только маскирует проблему. Если подумать ещё чуть-чуть, то можно найти правильное и эффективное решение.
________
* Вот я, например, сразу не заметил этой ошибки и мне уже в комментариях подсказали.


В первой статье мы видели, что порой в Linux используют WRITE_ONCE() и smp_wmb() вместо smp_store_release(). Аналогично, smp_rmb() и READ_ONCE() — вместо smp_load_acquire(). Эти частичные барьеры памяти создают особый тип отношений порядка между потоками. А именно, smp_wmb() делает все последующие неупорядоченные присваивания release-операциями, а smp_rmb(), соответственно, превращает предыдущие неупорядоченные чтения в load-acquire. (Строго говоря, это не совсем так, но примерно так о них можно думать.)


Попробуем улучшить работу с полями data:


    поток 1 (писатель)                 поток 2 (читатель)
    ------------------------------      ------------------------
    // write_seqcount_begin(&sc)        do {
    WRITE_ONCE(sc, sc + 1);                 // read_seqcount_begin(&sc)
    smp_wmb();                              old = smp_load_acquire(&sc) & ~1;

    WRITE_ONCE(data.x, 123);                copy.y = READ_ONCE(data.y);
    WRITE_ONCE(data.y, 456);                copy.x = READ_ONCE(data.x);

    // write_seqcount_end(&sc)              // read_seqcount_retry(&sc, old)
    smp_store_release(&sc, sc + 1);         smp_rmb();
                                        } while(READ_ONCE(sc) != old);

Даже если не знать семантики smp_wmb() и smp_rmb(), любому программисту очевидно, что такой код гораздо проще завернуть в удобный API. С данными можно работать, используя обычные атомарные операции (а модель памяти Linux даже позволяет и неатомарные), тогда как волшебные барьеры можно спрятать за read_seqcount_retry() и write_seqcount_begin().


Добавленные барьеры разделяют READ_ONCE() и WRITE_ONCE() на группы, обеспечивая безопасность работы seqcount. Но тут есть пара нюансов:


  • Во-первых, неупорядоченные атомарные операции остаются неупорядоченными. Поток 2 может увидеть новое значение data.y вместе со старым data.x. Для seqcount это не проблема, так как последующая проверка sc приведёт к повтору цикла.
  • Во-вторых, барьеры дают меньше гарантий, чем load-acquire и store-release. Чтение через smp_load_acquire() гарантированно происходит перед чтениями и записями в память, которые следуют за ним. Аналогично, присваивание через smp_store_release() происходит не только после предыдущих записей в память, но и чтений в том числе. Тогда как smp_rmb() упорядочивает лишь чтения, а smp_wmb() — только записи. Правда, взаимный порядок между чтениями и записями, наблюдаемый из других потоков редко важен на практике — именно по этой причине в ядре долгое время использовались только smp_rmb() и smp_wmb().

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


Предыдущий абзац очень неформально всё описывает, но это хорошая иллюстрация того, почему важно знать паттерны неблокирующего программирования. Это знание позволяет размышлять о коде на более высоком уровне без потери точности. Вместо того, чтобы описывать каждую инструкцию отдельно, вы можете просто сказать: «data.x и data.y защищены seqcount sc». Или как в предыдущем примере: «a передаётся другому потоку через message». Мастерство неблокирующего программирования отчасти состоит в умении узнавать и использовать подобные паттерны, облегчающие понимание кода.


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