В первой части этого цикла статей мы рассмотрели теорию, стоящую за одновременным доступом в моделях памяти, а также применение этой теории к простым чтениям и записям в память. Правда, этих примитивов оказывается недостаточны для построения высокоуровневых механизмов синхронизации вроде спинлоков, мьютексов и условных переменных. Хоть и полные барьеры памяти позволяют синхронизировать потоки с помощью приёмов, рассмотренных в предыдущей части (алгоритм Деккера), современные процессоры позволяют получить нужный эффект проще, быстрее и гибче — да, всё сразу! — с помощью операций compare-and-swap.

Для программистов ядра Linux операция обмена compare-and-swap выглядит так:

    T cmpxchg(T *ptr, T old, T new);

где T может быть либо числовым типом не больше указателя, либо указателем на что-нибудь. Так как в C нет обобщённых функций, то подобный полиморфизм реализуется макросами. cmpxchg() — это очень аккуратно реализованный макрос, который ведёт себя как функция (например, вычисляет аргументы только один раз). В Linux также есть макрос cmpxchg64(), который работает с 64-битными целыми числами и недоступен на 32-битных платформах.

cmpxchg() читает значение по указателю *ptr и, если оно равно old, то заменяет его на new. Иначе же после чтения ничего не происходит. Считанное значение возвращается как результат операции, независимо от того, произошла ли запись. И всё это выполняется атомарно: если другой поток одновременно с cmpxchg() записывает что-то по адресу *ptr, то cmpxchg() ничего не меняет. Либо old становится new, либо текущее значение остаётся нетронутым. Поэтому cmpxchg() называют атомарной операцией read-modify-write.

В ядре Linux cmpxchg() также предоставляет окружающему коду гарантии порядка операций с памятью. Для выполнения атомарного обмена значений требуется и читать, и писать в память. С некоторыми оговорками можно считать, что чтение здесь имеет acquire-семантику, а запись — это release-операция. То есть cmpxchg() будет синхронизироваться с load-acquire и store-release операциями в других потоках.

Стеки и очереди без блокировок

Статья «Lockless algorithms for mere mortals» рассказывает, как compare-and-swap позволяет работать со списками без мьютексов — с подробным разбором и иллюстрациями. Здесь же мы ограничимся рассмотрением односвязного списка в качестве примера: как его реализовать на C, где он может пригодиться. Начнём с простого: как добавляется элемент в начало односвязного списка.

    struct thing {
        struct thing *next;
        ...
    };
    struct thing *first;

    node->next = first;
    first = node;

Как мы теперь знаем, присваивание “first” следует выполнять release-операцией, чтобы другие потоки увидели “node->next” после выполнения load-acquire. Хорошо, пока всё идёт по плану и шаблону из первой статьи.

Однако, такой простой код корректно работает лишь для случая, когда ровно один поток может модифицировать список. Если таких потоков-писателей может быть несколько, то уже оба присваивания должны быть защищены критической секцией. В противном случае, если какой-то другой поток изменяет значение first (добавляет элемент, например), то node->next в свежедобавленном элементе может указывать на старое значение first и один элемент списка окажется утерян. Из этого следует важный урок: корректное использование acquire и release-семантики — это необходимое, но отнюдь не достаточное условие корректности неблокирующих алгоритмов. Сами по себе они не защищают вас от логических ошибок и гонок потоков.

К счастью, в данной ситуации вместо блокировки можно воспользоваться cmpxchg(), чтобы поймать ситуацию, когда какой-то другой поток изменил first первым. Следующий код будет корректным уже для любого числа потоков-писателей:

    if (cmpxchg(&first, node->next, node) == node->next)
        /* ура, сработало! */
    else
       /* и что теперь? */

И тут возникают вопросы. Во-первых, что же делать, когда cmpxchg() заметит изменения в first? В нашем случае ответ простой: считать новое значение, обновить node->next, попробовать добавить node в список ещё раз. Это новый элемент, который пока ещё не видно из других потоков. Если нам не повезло с добавлением — никто ничего не заметит.

Второй вопрос гораздо более хитрый: как именно в таком случае следует считывать first? По идее нам не нужна acquire или release-семантика, ведь нас волнует только значение first само по себе. С другой стороны, слишком умный оптимизирующий компилятор может подумать, что раз мы ничего не присваиваем first в этом потоке, то значение не могло измениться и ничего повторно читать из памяти не нужно. Хоть cmpxchg() в Linux и запрещает подобные оптимизации, хорошим тоном считается явно показывать с помощью READ_ONCE(), что мы хотим считать новое значение из памяти.

Улучшенная версия кода выглядит так:

    struct thing *old, *expected;
    old = READ_ONCE(first);
    do {
        node->next = expected = old;
        old = cmpxchg(&first, expected, node);
    } while (old != expected);

Отлично, добавление в список работает. Перейдём к другой стороне проблемы: как следует забирать значения из этого списка. Зависит из того, чего мы хотим добиться, передавая значения через список, сколько потоков будут из него читать, и в каком порядке они хотят это делать: LIFO или FIFO, от новых элементов к старым или наоборот.

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

Если чтения выполняются редко или группами, то можно сделать так, что писатели работают совместно, не блокируя друг друга, а доступ читателей строго синхронизируется. Берём rwlock и переворачиваем его! Писатели захватывают блокировку совместно (через read_lock()), а читатели требуют эксклюзивного доступа (через write_lock()). В таком случае запись в список не может происходить одновременно с чтением, так что читателям снова не нужны никакие атомарные операции. Остаётся только надеяться, что вы пишете хорошие комментарии к своему коду, чтобы у ваших читателей не случился взрыв мозга.

Если читателей много, но им не особо важен порядок элементов в списке — например, пул рабочих потоков, где каждый поток хочет взять себе работы — то для этого достаточно всего одной инструкции:

    my_tasks = xchg_acquire(&first, NULL);

xchg() подобно cmpxchg() атомарно выполняет одновременно чтение и запись в память. В данном случае читает и возвращает старое значение first, всегда записывая вместо него NULL. То есть переносит значение first в my_tasks. Здесь используется вариант xchg_acquire(), придающий acquire-семантику чтению из памяти, но при этом запись выполняется просто атомарно, без release-семантики (подобно WRITE_ONCE()). Тут достаточно лишь acquire-семантики, потому что release-половинка находится в другом месте (у писателей). В целом, это всё тот же приём из первой части, только расширенный на случай более чем двух потоков.

Можно ли при этом заменить cmpxchg() у писателя на cmpxchg_release() — с записью через release, но обычным чтением? По идее так можно сделать, ведь писателю важно только то, чтобы его запись в “node->next” была видна другим потокам. Однако, acquire-семантика чтения у cmpxchg() имеет полезный побочный эффект: так каждый следующий писатель синхронизируется с предыдущими писателями. Вызовы cmpxchg() упорядочиваются благодаря парам acquire и release-операций:

    поток 1: load-acquire first (возвращает NULL)
             store-release node1 --> first
                        поток 2: load-acquire first (возвращает node1)
               store-release node2 --> first
                             поток 3: load-acquire first (возвращает node2)
                  store-release node3 --> first
                                   поток 4: xchg-acquire first (возвращает node3)

Только cmpxchg() из третьего потока синхронизирована с xchg_acquire() в четвёртом потоке. Однако благодаря транзитивности, все другие cmxchg() происходят перед xchg_acquire(). Если писатели используют cmpxchg(), то после xchg_acquire() по списку можно пройти уже с помощью обычных операций чтения.

Если бы писатели использовали cmpxchg_release(), то отношения порядка между потоками выглядели бы так:

    поток 1: load first (возвращает NULL)
             store-release node1 --> first

      поток 2: load first (возвращает node1)
               store-release node2 --> first

         поток 3: load first (возвращает node2)
                  store-release node3 --> first
                                   поток 4: xchg-acquire first (возвращает node3)

Четвёртый поток конечно же прочитает node2 из node3->next, потому что он уже прочитал значение first, которое записал третий поток. Но вот для последующих элементов списка наблюдаемый порядок записей других потоков уже не гарантируется — при использовании обычных операций чтения — поэтому четвёртому потоку требуется использовать smp_load_acquire() для прохода по списку, чтобы точно увидеть node1 при чтении node2->next.

Конечно же односвязные списки давно реализованы в ядре Linux — linux/llist.h — поэтому можно не переизобретать колесо и пользоваться готовыми решениями. Теперь обратим внимание на ещё пару интересных функций: llist_del_first() и llist_reverse_order().

llist_del_first() вынимает и возвращает первый элемент списка. Документация предупреждает, что эта функция безопасна только для единственного читателя. Если несколько потоков одновременно забирают элементы списка, то при определённом стечении обстоятельств возможна так называемая проблема ABA. Я не буду вдаваться здесь в детали, просто не надо так делать. Возникает ситуация, похожая на предыдущий пример с rwlock: для корректной работы алгоритма в целом необходимо пользоваться блокировками, но определённые части могут обойтись без них. llist_del_first() позволяет любому количеству писателей добавлять элементы в список с помощью llist_add() без каких-либо блокировок, но если читателей несколько, то они между собой должны пользоваться мьютексом или спинлоком.

llist_del_first() превращает список в LIFO-контейнер (стек). Если же вам требуется FIFO-порядок (очередь), то можно воспользоваться следующим приёмом с llist_reverse_order(). Если забирать элементы из списка пачками с помощью xchg() (или же llist_del_all()), то пачки сохраняют FIFO-порядок между собой, только элементы в них следуют в обратном порядке. Воу, а что если...

    struct thing *first, *current_batch;

    if (current_batch == NULL) {
        current_batch = xchg_acquire(&first, NULL);
        /* перевернуть список current_batch */
    }
    node = current_batch;
    current_batch = current_batch->next;

Таким образом можно забирать элементы из списка в порядке их поступления, подобно очереди. Как и в случае с llist_del_first(), это работает только если элементы current_batch обрабатываются одним потоком. Пооная реализация этого алгоритма с помощью API llist оставляется читателю в качества упражнения.

На этом у меня пока всё. В следующей части мы продолжим изучать атомарные read-modify-write операции, посмотрим, что ещё можно сделать с compare-and-swap и как её можно использовать для ускорения счётчиков ссылок.

Дейв Чиннер — один из основных сопровождающих XFS и Btrfs — оставил замечательный комментарий касательно производительности cmpxchg().

Есть пара достаточно важных моментов про неблокирующие алгоритмы, использующие cmpxchg. Они как бы подразумеваются в статье, но явно не рассматриваются. cmpxchg определяется как «атомарная операция read-modify-write», что технически корректно, но умалчивает некоторые ограничения масштабирования, с которыми сталкиваются «неблокирующие» алгоритмы на основе cmpxchg.

1. cmpxchg — это блокирующая операция: на уровне железа, не программном, но всё же блокирующая. Кроме того, она инвалидирует кеш-линии, со всеми вытекающими: неизбежно наступает момент, когда межпроцессорная шина насыщается, нагрузка на процессоры начинает расти нелинейно и производительность падает.
2. cmpxchg не очень равномерно и справедливо распределяет нагрузку между процессорами, что легко может привести к взаимным блокировкам и просадкам производительности под высокой нагрузкой. Здесь уже вылезают особенности реализации протоколов когерентности кеша (при должном опыте по задержкам в исполнении инструкций можно догадываться о том, что там происходит на уровне железа).

Поэтому большинство алгоритмов в ядре выходят из цикла cmpxchg() после некоторого числа неудач, а потом переходят к плану Б: скажем, захватывают спинлок, чтобы избежать негативных последствий высокой нагрузки на cmpxchg. Например, dentry-кеш использует механизм lockref (lockref_get/lockref_put), который прекращает крутить цикл cmpxchg() после 100 неудачных попыток.

^{Dentry-кеш ускоряет работу с именами файлов, чтобы ядро не бегало каждый раз в файловую систему заново. Например, если вы открываете только что созданный файл, то он наверняка будет в dentry-кеше и ядру не придётся лишний раз перепроверять, что все промежуточные директории существуют.}

Чтобы вы примерно себе представляли, когда конфликты за кеш-линии становятся проблемой (при достижении протоколом когерентности кешей точки насыщения), на моей машине нагрузка на процессор перестаёт линейно расти где-то при 2,5–3 миллионах операций в секунду, если взять простой цикл с cmpxchg() для 64-битного значения на своей собственной кеш-линии, где больше ничего не происходит. Это в 32 потока на машине двухлетней давности с 32 ядрами. Они не прям под завязку нагружены, но если попрофайлить конкретный цикл, создавая 650000 файлов в секунду, то можно наблюдать, как суммарно этот цикл начинает занимать вполне значимое количество ресурсов: единицы процентов процессорного времени.

Если сравнить со спинлоками, то при похожей нагрузке приблизительно треть времени тратится только на то, чтобы крутить спинлоки. Конкретно, если посмотреть на спинлок, защищающий список inode в суперблоке файловой системы, то при 2,6 миллионах доступов в секунду на спинлоки уходит околе 10% процессорных ресурсов (то есть 3 из 32 процессоров). Очень похоже на cmpxchg, который начинает тупить где-то в этом же районе, и если подумать, как оба варианта обращаются с кешем, то наблюдаемое поведение вполне логично.

Другими словами, cmpxchg() масштабируется лучше, чем блокирующие алгоритмы, но это не волшебная таблетка, делающая всё быстрее. У cmpxchg() тоже есть пределы масштабируемости, так как это не вполне неблокирущая операция. Впрочем, мой опыт проектирования многопоточных алгоритмов подсказывает, что масштабируемость зависит больше от того, насколько часто алгоритму требуется читать или обновлять разделяемые данные, а не от того, насколько «(не)блокирующий» алгоритм используется. Мьютекс — это ж фактически просто атомарный флажок «захвачено» и немного оптимизаций. Так что неудивительно, что cmpxchg() и атомарные примитивы имеют схожие ограничения в масштабируемости с блокировками — фундаментально, если посмотреть с точки зрения кеша, все эти подходы об одном и том же. Просто cmpxchg() и атомарные операции дают более тонкий контроль над памятью, уменьшая частоту одновременного доступа к данным. Отсюда и выгода: если меньше трогать общую память, то можно делать больше независимой работы.

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

На что последовал ответ автора — Паоло.

Дейв, огромное спасибо за ответ. Прям в корень зришь — я сомневался, стоит ли вообще рассказывать о связных списках, во многом из-за описанных тобой причин. С одной стороны, связные списки — это прямо классический пример неблокирущих структур данных. С другой стороны, они не настолько широко применимы, как другие вещи, о которых я рассказываю, вот как раз из-за ограничений в масштабируемости. Нет, у связных списков есть своя ниша, но их слишком легко использовать там, где не надо. Например, в тех немногих случаях, когда мне были нужны именно llist, я принял такое решение не потому, что неблокирующее добавление в список — это круто (нет, это прикольно, но у него проблемы с распределением работы между процессорами при повышенной нагрузке). Наоборот, я знал, что писателей будет немного и записи будут редкими, а вот читатель будет лишь один и его хотелось сделать как можно более быстрым. Я бы не назвал это очевидным решением задачи.

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

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

• Если вы знаете пару-тройку широко известных приёмов (которые часто ещё и завёрнуты в удобные API), то внезапно ваш код становится проще поддерживать и масштабируемость тоже скорее всего будет получше, несмотря на то, что неблокирующее программирование сложнее мьютексов. И вот тут неблокирующие связные списки — это как раз плохой пример, потому что в неопытных руках от них порой больше вреда чем пользы.
• Следует как можно чётче разделять «быструю» неблокирующую часть кода — которая либо реализует один из рассмотренных приёмов, либо использует какую-нибудь готовую абстракцию вроде того же lockref — и «медленную» часть, где можно позволить себе блокировки. Гораздо проще выбрать правильный примитив, если неблокирующая часть небольшая и аккуратная.
• На выбор очень сильно влияют обстоятельства. Если у вас только один читатель или писатель, то дело существенно упрощается, так как скорее всего ваш алгоритм попадает в какой-нибудь из привычных, готовых шаблонов.

Чтобы добиться максимальной производительности, вам необходимо знать относительную частоту записей и чтений (или распределение работы между быстрой и медленной частями алгоритма). Иначе вы ж понятия не имеете, где у вас могут возникнуть проблемы с масштабируемостью. Неблокирующие алгоритмы — это всегда компромисс (моя история с llist служит примером, но пожалуй наиболее известный пример — это RCU). Стоит иметь это в виду, ведь если ваш код выполняется достаточно редко, то на медленную часть можно не особо обращать внимание, добавить туда мьютекс и превратить много читателей/писателей в одного (в один момент времени), что может значительно упростить вам жизнь, расширив количество применимых шаблонов неблокирующего программирования.