ARM и программирование без блокировок

в 7:05, , рубрики: c++, c++11, lock-free, Блог компании Яндекс, Программирование, Процессоры

ARM и программирование без блокировок - 1

Выпуск ARM-процессора Apple M1 вдохновил меня на то, чтобы написать в Твиттер про опасности программирования без блокировок (lock-free). Этот твит вызвал бурную дискуссию. Обсуждение прошло довольно неплохо, учитывая то, что попытки втиснуть в рамки Твиттера обсуждениие такой сложной темы, как модели памяти центрального процессора, — в принципе бессмысленны. Но у меня осталось желание немного раскрыть тему.

Этот пост задуман не только как обычная вводная статья про опасности программирования без блокировок (о которых я в последний раз писал около 15 лет назад), но и как объяснение, почему слабая модель памяти ARM ломает некоторый код, и почему этот код, вероятно, не работал изначально. Я также хочу объяснить, почему стандарт C++11 значительно улучшил ситуацию в программировании без блокировок (несмотря на возражения против противоположной точки зрения).

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

Основные проблемы программирования без блокировок лучше всего объяснять на примере паттерна производитель/потребитель, в котором не используются блокировки и поток-производитель выглядит следующим образом (псевдокод C ++ без деления на функции):

// Поток-производитель

Data_t g_data1, g_data2, g_data3;
bool g_flag
g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
g_flag = true; // Сигнализируем, что данные можно использовать.

А вот поток-потребитель, который извлекает и использует данные:

// Поток-потребитель
if (g_flag) {
  DoSomething(g_data1, g_data1, g_data2, g_data3);

Здесь опущено множество деталей: Когда сбрасывается g_flag? Как потоки избегают простоя (spinning)? Но этого примера достаточно для наших целей. Вопрос в том, что не так с этим кодом, особенно с потоком-производителем?

Основная проблема в том, что этот код предполагает, что данные будут записываться в три переменные g_data до флага, но этот код не может этого гарантировать. Если компилятор переставит местами инструкции записи, то флаг g_flag может получить значение true до того, как будут записаны все данные, и поток-потребитель увидит неверные значения.

Оптимизирующие компиляторы могут очень интенсивно менять местами инструкции. Это один из способов заставить сгенерированный код работать быстрее. Компиляторы делают это, чтобы использовать меньше регистров, лучше использовать конвеер процессора, или просто из-за какой-то случайной эвристики, которую добавили, чтобы немного ускорить загрузку Office XP. Нет смысла слишком много думать о том, почему компиляторы могут что-то переставлять, важно понимать, что они это умеют и практикуют.

Компиляторам разрешено переставлять местами инструкции записи, потому что есть правило as-if, которое гласит, что компилятор выполнил свою работу, если программа, которую он генерирует, ведет себя так, «как если бы» её не оптимизировали. Поскольку абстрактная машина C/C ++ долгое время допускала только однопоточное выполнение — без внешних наблюдателей — вся эта перестановка инструкций записи была правильной и разумной и использовалась десятилетиями.

Весь вопрос в том, что нужно сделать, чтобы компилятор не ломал наш красивый код? Давайте на минуточку представим себя программистом 2005 примерно года, который пытается сделать так, чтобы этот код сработал. Вот несколько не очень хороших идей:

  1. Объявить g_flag как volatile. Это не позволит компилятору пропустить чтение/запись g_flag, но, к удивлению многих, не избавит от основной проблемы — перестановки. Компиляторам запрещено переставлять инструкции чтения/записи volatile-переменных относительно друг друга, но разрешено переставлять их относительно обычных инструкций чтения/записи. То, что мы добавили volatile, никак не решает нашу проблему перестановок (/volatile:ms на VC ++ решает, но это нестандартное расширение языка, из-за которого код будет выполняться медленнее).
  2. Если недостаточно объявить g_flag как volatile, тогда давайте попробуем объявить все четыре переменные как volatile! Тогда компилятор не сможет изменить порядок записи и наш код будет работать… на некоторых компьютерах.

Оказывается, не только компиляторы любят переставлять инструкции чтения и записи. Процессоры тоже любят это делать. Не нужно путать это с out-of-order исполнением, всегда незаметным для вашего кода, к тому же на самом деле есть in-order процессоры, которые меняют порядок чтения/записи (Xbox 360), и есть out-of-order процессоры, которые в большинстве случаев не меняют местами чтение и запись (x86/x64).

Таким образом, если вы объявите все четыре переменные как volatile, вы получите код, который будет правильно исполняться только на x86/x64. И этот код потенциально неэффективен, потому что при оптимизации нельзя будет удалить никакие операции чтения/записи этих переменных, а это может привести к лишней работе (например, когда g_data1 дважды передается в DoSomething).

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

Чтобы предотвратить перестановку в x86/x64, нужно использовать компиляторный барьер памяти. Вот как это делается:

g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
_ReadWriteBarrier(); // Только для VC++ и уже deprecated, но для 2005 это окей.
g_flag = true; // Сигнализируем, что данные можно использовать.

Здесь мы говорим компилятору не переносить инструкции записи через этот барьер, а это как раз то, что нам нужно. После записи в g_flag может потребоваться еще один барьер, который будет гарантировать, что значение записано, но тут столько подробностей и неопределенностей, что я бы не хотел их обсуждать. Аналогичный барьер нужно использовать в потоке-потребителе, но я пока для простоты игнорирую этот поток.

Проблема в том, что этот код не будет работать на процессорах со слабой моделью памяти. «Слабая модель памяти» означает, что процессоры могут переставлять инструкции чтения и записи (для большей эффективности или простоты реализации). К таким процессорам относятся, например, процессоры с архитектурами: ARM, PowerPC, MIPS и практически все используемые сейчас процессоры, кроме x86/x64. Эту проблему решает тот же барьер памяти, но на этот раз это должна быть инструкция процессора, которая сообщает ему, что менять порядок не нужно. Что-то вроде этого:

g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
MemoryBarrier(); // Дорогостоящий полный барьер памяти (full memory barrier). Только для Windows.

g_flag = true; // Сигнализируем, что данные можно использовать.

Конкретная реализация MemoryBarrier зависит от процессора. На самом деле, как сказано в комментарии в коде, MemoryBarrier здесь не идеальный выбор, потому что нам просто нужен барьер между записями в память (write-write) вместо гораздо более дорогого полного барьера памяти (full memory barrier), который заставляет операции чтения ждать окончательного завершения операции записи. Но сейчас этого достаточно для наших целей.

Здесь предполагается, что встроенная функция MemoryBarrier также является компиляторным барьером памяти, поэтому нам достаточно чего-то одного. И наш потрясающий и эффективный поток-производитель теперь становится таким:

#ifdef X86_OR_X64
#define GenericBarrier _ReadWriteBarrier
#else
#define GenericBarrier MemoryBarrier
#endif
g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
GenericBarrier(); // И почему мне пришлось самому это писать?
g_flag = true; // Сигнализируем, что данные можно использовать.

Если у вас есть код 2005 приблизительно года, и он без этих барьеров памяти, то ваш код не работает и никогда не работал как надо, на всех процессорах, потому что компиляторам всегда разрешалось переставлять инструкции записи. С барьерами памяти, реализованными для разных компиляторов и платформ, ваш код будет красивым и портируемым.

Оказывается, слабая модель памяти ARM совсем не усложняет ситуацию. Если вы пишете код без блокировок и нигде не используете барьеры памяти, то ваш код потенциально сломан везде из-за перестановок, которые выполняет компилятор. Если вы используете барьеры памяти, вам будет легко добавить в них и аппаратные барьеры памяти.

Код, который я привёл выше, может содержать ошибки (как реализованы эти барьеры?), к тому же он избыточен и неэффективен. К счастью, когда появился C++11, у нас появились варианты получше. На самом деле до C ++ 11 в языке не было модели памяти, было лишь встроено неявное предположение, что весь код является однопоточным, и если вы меняете общие данные не под блокировкой, то пусть бог простит вашу грешную душу. В C ++ 11 появилась модель памяти, которая признаёт существование потоков. Стало очевидным, что приведенный выше код без барьеров не работал, но одновременно у нас появились возможности, чтобы его исправить, например:

// Поток-производитель

Data_t g_data1, g_data2, g_data3;
std::atomic<bool> g_flag // Обратите внимание!
g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
g_flag = true; // Сигнализируем, что данные можно использовать.

Небольшое изменение, которое легко не заметить. Я только изменил тип данных g_flag с bool на std :: atomic . Для компилятора это означает — не игнорировать инструкции чтения и записи этой переменной (ну, в основном), не менять порядок чтения и записи между чтением и записью в эту переменную и, при необходимости, добавлять соответствующие процессорные барьеры памяти. Мы даже можем немного оптимизировать этот код:

// Поток-производитель

Data_t g_data1, g_data2, g_data3;
std::atomic<bool> g_flag
g_data1 = calc1();
g_data2 = calc2();
g_data3 = calc3();
g_flag.store(true, std::memory_order_release);

С помощью memory_order_release мы сообщаем компилятору, что именно мы делаем, чтобы он мог использовать соответствующий (менее затратный) тип инструкции барьера памяти или, наоборот, вообще не использовать барьер памяти (в случае x86/x64). Наш код теперь относительно чист и наиболее эффективен.

Теперь написать поток-потребитель очень просто. Фактически, с новым описанием g_flag исходная версия потока-потребителя теперь верна! Но мы можем ещё немного улучшить её:

// Поток-потребитель

if (g_flag.load(std::memory_order_acquire)) {
  DoSomething(g_data1, g_data1, g_data2, g_data3);

Флаг std :: memory_order_acquire сообщает компилятору, что нам не нужен полный барьер памяти. Барьер чтения-захвата (read-acquire) гарантирует, что до g_flag нет чтения общих данных, не блокируя при этом другие перестановки.

Здесь я предоставлю читателю возможность потренироваться, и самому закончить пример так, чтобы потоки могли избежать работы вхолостую (Busy-Wait) и других проблем.

Если вы хотите научиться использовать этот подход, советую вам начать с внимательного изучения статей: Jeff Preshing’s introduction to lock-free programming или This is Why They Call It a Weakly-Ordered CPU. После этого подумайте, не лучше ли вам уйти в монастырь (мужской или женский). Lock-free programming — это самое опасное оружие в арсенале C++ (а это о многом говорит) и применять его стоит лишь в редких случаях.

Примечание: Чтобы написать x86-эмулятор на ARM, придётся помучаться с этим подходом, потому что никогда не знаешь, в какой момент перестановка инструкций станет проблемой. Из-за этого приходится вставлять много барьеров памяти. Или можно следовать стратегии Apple, то есть добавить в CPU режим, который обеспечивает порядок доступов к памяти как в x86|x64 и включать его при эмуляции.

Автор: Леонид Клюев

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js