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

В первых двух статьях цикла мы рассмотрели четыре способа упорядочить доступ к памяти: load-acquire и store-release операции в первой части, барьеры чтения и записи в память — во второй. Теперь пришла очередь познакомиться с полными барьерами памяти, их влиянием на производительность, и примерами использования полных барьеров в ядре Linux.

Рассмотренные ранее примитивы ограничивают возможный порядок исполнения операций с памятью четырьмя различными способами:

• Load-acquire операции выполняются перед последующими чтениями и записями.
• Store-release операции выполняются после предыдущих чтений и записей.
• Барьеры чтения разделяют предыдущие и последующие чтения из памяти.
• Барьеры записи разделяют предыдущие и последующие записи в память.

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

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

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

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

Неблокирующие алгоритмы широко применяются в ядре Linux когда традиционные примитивы блокировки либо не могут быть использованы, либо недостаточно быстры. Эта тема многим интересна и время от времени всплывает на LWN. Из недавнего — вот эта июльская статья, которая собственно и сподвигла меня написать свою серию. Ещё чаще разговор заходит про механизм read-copy-update (RCU — руководство 2007 года всё ещё актуально), подсчёт ссылок, и способы сделать более понятные, высокоуровные API ко всему этому разнообразию. Ну а сейчас вас ждёт погружение в идеи, стоящие за неблокирующими алгоритмами, а также их использованием в ядре.

Знание низкоуровневой модели памяти в целом считается продвинутым уровнем понимания, которого страшатся даже опытные программисты-ядерщики. Словами нашего редактора (из его июльской статьи): «Понять модель памяти можно лишь правильно повёрнутым мозгом». Говорят, что моделью памяти Linux (и файлом memory-barriers.txt в частности) можно пугать детей. Порой для достижения эффекта достаточно всего лишь рявкнуть “acquire” или “release”.

И в то же время, механизмы вроде RCU и seqlocks так широко применяются в ядре, что практически каждый разработчик рано или поздно сталкивается с фундаментально неблокирующими интерфейсами. Поэтому многим будет полезно иметь хотя бы базовое представление о неблокирующей синхронизации. В этой серии статей я расскажу, что же на самом деле означает acquire и release-семантика, а также приведу пять сравнительно простых паттернов, которые покрывают большинство вариантов использования неблокирующих примитивов.

^{Увидев вот эту публикацию про браузерные войны, я хотел бы представить альтернативное наблюдение за тем, как мы докатились до такой жизни. Но Дрю ДеВолт уже всё сказал за меня.}

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

С помощью wget я скачал все 1217 спецификаций W3C, опубликованных на текущий момент. Существенная часть из них должна быть реализована в браузере, чтобы современный веб работал. Я подсчитал объём этих спецификаций. Как думаете, насколько сложен современный веб?

В WinAPI есть функция CreateRemoteThread, позволяющая запустить новый поток в адресном пространстве другого процесса. Её можно использовать для разнообразных DLL-инъекций как с нехорошими целями (читы в играх, кража паролей, и т. д.), так и для того, чтобы на лету исправить баг в работающей программе, или добавить плагины туда, где они не были предусмотрены.

В целом эта функция обладает сомнительной прикладной полезностью, поэтому не удивительно, что в Linux готового аналога CreateRemoteThread нет. Однако, мне было интересно, как он может быть реализован. Изучение темы вылилось в неплохое приключение.

Я подробно расскажу о том, как с помощью спецификации ELF, некоторого знания архитектуры x86_64 и системных вызовов Linux написать свой маленький кусочек отладчика, способный загрузить и исполнить произвольный код в уже запущенном и работающем процессе.

Для понимания текста потребуются базовые знания о системном программировании под Linux: язык Си, написание и отладка программ на нём, осознание роли машинного кода и памяти в работе компьютера, понятие системных вызовов, знакомство с основными библиотеками, навык чтения документации.

Как только вы переступаете через болевой порог Борроу-Чекера и осознаёте, что Rust позволяет вытворять невообразимые (и порой опасные) в других языках вещи, вас может постигнуть настолько же непреодолимое желание Переписать Всё на Rust. Хоть и в лучшем случае это банально непродуктивно (бессмысленное разбазаривание усилий на несколько проектов), а в худшем — приводит к уменьшению качества кода (ведь с чего вы считаете себя более опытным в области применения библиотеки, чем её изначальный автор?)

Гораздо полезнее будет предоставить безопасный интерфейс для оригинальной библиотеки, повторно используя её код.

Недавно zerocost написал интересную статью «Тесты на C++ без макросов и динамической памяти», в которой рассматривается минималистический фреймворк для тестирования Си++ кода. Автору (почти) удалось избежать использования макросов для регистрации тестов, однако вместо них в коде появились «волшебные» шаблоны, которые лично мне кажутся, простите, невообразимо уродскими. После прочтения статьи у меня оставалось смутное чувство неудовлетворённости, так как я знал, что можно сделать лучше. Я сразу не смог вспомнить где, но я точно видел код тестов, который не содержит ни единого лишнего символа для их регистрации:

void test_object_addition()
{
    ensure_equals("2 + 2 = ?", 2 + 2, 4);
}

Наконец-то я вспомнил, что этот фреймворк называется Cutter и он использует по-своему гениальный способ идентификации тестовых функций.

#include <iostream>

#include <LC/kernel.h>
#include <LC/church_numerals.h>

int main()
{
    // Представление натуральных чисел в виде лямбда-абстракций
    typedef ChurchEncode<2> Two;    // 2 = λfx.f (f x)
    typedef ChurchEncode<3> Three;  // 3 = λfx.f (f (f x))

    // * = λab.λf.a (b f)
    typedef Lambda<'a', Lambda<'b', Lambda<'f',
                Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > >
        > > > Multiply;

    // Вычисление (* 2 3)
    typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output;

    // Переход обратно от лямбда-абстракций к натуральным числам
    typedef ChurchDecode<Output> Result;

    std::cout << Result::value;
}

ilammy@ferocity ~ $ gcc cpp.cpp
ilammy@ferocity ~ $ ./a.out
6

• более 37000 скобок!
• разбор по косточкам семантики всех конструкций Scheme, а также его родственников;
• в том числе разбор его денотационной семантики — формального математического описания языка в терминах лямбда-исчисления;
• 11 интерпретаторов и 2 компилятора (в машинный код описываемой там же VM и транслятор в код на Си);
• объяснение сути рекурсии, замыканий и окружений, продолжений и стека вызовов, реализации макросов и метаязыков, а также чуть рефлексии и самомодифицирующегося кода;
• множество экскурсов в историю Лиспа и причины принятых решений в дизайне языка;
• собственная CLOS-подобная объектная система автора (и её реализация, разумеется);
• время от времени возникающее чувство: «Да это же X из языка Y»;
• список литературы по теме на 230 наименований.