Небезопасный Rust сложнее C

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

В прошлом году я написал программу Photohash для индексации своего NAS и поиска дубликатов фото ^[1] без использования хэширования, независимого от поворота изображения, и перцептивного хэширования. Чтобы полноценно задействовать все ядра процессора и диски, эта программа распределяет работу между воркерами, отвечающими за вычисления и ввод-вывод. Происходит это распределение по каналам, представляющим синхронизированные очереди задач.

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

Rust предоставляет широкий выбор реализаций каналов, наиболее качественными среди которых являются std::sync::mpsc ^[2], futures::channel ^[3], tokio::sync ^[4], crossbeam::channel ^[5], flume ^[6], и kanal ^[7].

К сожалению, ни один из них не отвечает полноценно моим потребностям, поэтому я решил написать собственный канал мечты. На своей прежней работе (в EdenFS ^[8] и Watchman ^[9]) я часто сталкивался с созданием каналов под конкретные задачи, поэтому примерно понимал, что мне нужно. Ближе всего подходил kanal, но он пронизан unsafe кодом и использованием спинлоков, которые отлично выглядят в микробенчмарках, но совершенно неуместны в пользовательском ПО ^[10].

Знакомимся с batch-channel ^[11], каналом, оптимизированным под повышение пропускной способности. Вот его основные характеристики:

• Множество отправителей (producers) и получателей (consumers). Параллелизм как при отправке, так и при получении.
• Поддержка синхронного и асинхронного кода для получателей и отправителей. Такое комбинирование обеспечивают гибкость, позволяющую использовать канал в любой разновидности пула потоков, асинхронной среде или FFI (foreign functions interface, интерфейс внешних функций).
• Ограниченный или неограниченный. Ограниченный для контроля обратного потока, а неограниченный для ситуаций, в которых нельзя гарантировать отсутствие взаимных блокировок.
• Отправка и получение множества значений. Мне зачастую нужно отправлять много значений, например, считывая все пути в каталоге или записывая в базу данных множество строк. Объединение в пакеты позволяет сокращать затраты на обработку отдельных операций. Неразумно получать блокировку канала N раз для передачи N значений. То же касается стороны получателей: воркеры могут получать все ожидающие элементы работы за одно считывание канала. Здесь вы можете вспомнить о lock-free очередях, и для них есть своё место, но в начале (head) и хвосте (tail) соперничество всё равно сохраняется, и атомарные операции остаются медленными даже на современных ядрах Intel. Если же у вас в очереди всё равно предполагается соперничество, то смысл пакетных каналов заключается в том, чтобы располагать всё за мьютексом и максимизировать размер пакета на обеих сторонах.

На момент написания статьи я ещё не реализовал следующие цели:

• Приоритетность. Отправители могут влиять на порядок обработки.
• Ограничение числа элементов переменного размера. Например, возможность заявить, что очередь может содержать до 20 МБ путей, вне зависимости от их длины.

И, наконец, цель дизайна, которая привела к написанию этой статьи:

• Никаких аллокаций при стабильном состоянии. Операции аллокации являются источником соперничества, сбоев и лишних издержек, особенно при использовании медленных системных аллокаторов.

▍ Форма канала

Чтобы понять, почему в моей программе вообще присутствует unsafe Rust, разберём реализацию канала.

pub struct Channel<T> {
  q: VecDeque<T>,
  // Заблокированные получатели.
  waiting_for_elements: Vec<Waker>,
  // Заблокированные отправители.
  waiting_for_capacity: Vec<Waker>,
  // Для синхронного использования также требуются условные переменные.
}

Когда асинхронный получатель блокируется в recv() из-за того, что канал пустой, сохраняется waker задачи, чтобы при поступлении значения канал эту задачу пробудил.

Waker [12] — это идентификатор заблокированной задачи. Когда асинхронная среда выполнения в очередной раз будет опрашивать канал, он просигнализирует ей о необходимости пробуждения задачи. Waker представляет собой широкий указатель ^[13], размером в два слова, который используется так:

pub struct Recv<'a, T> {
  channel: &'a Channel<T>,
}

impl<'a, T> Future for Recv<'a, T> {
  type Output = T;
  
  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
    // Очередь пуста?
    if let Some(element) = self.channel.q.pop_front() {
      // В очереди есть элемент, возвращаем его.
      Poll::Ready(element)
    } else {
      // Очередь пуста, значит блокируем задачу и повторяем попытку позже.
      self.channel.waiting_for_elements.push(cx.waker().clone());
      Poll::Pending
    }
  }
}

Примечание: Код выше чисто показательный. В реальности у канала есть Mutex и несколько условных переменных, но для данной статьи это несущественно.

Если очередь в момент вызова recv() пуста, в канале сохраняется waker, а задача блокируется.

Позднее, когда в очередь будет добавлено значение, все ожидающие задачи активируются:

fn send<T>(channel: &mut Channel<T>, value: T) {
  channel.q.push_back(value);
  let wakers = mem::take(&mut channel.waiting_for_elements);
  // Примечание: здесь мьютексы освобождаются, перед пробуждением задач.
  // Если не предусмотреть какой-то способ фильтрации, то придётся пробудить все промисы (futures), так как мы не знаем, какой из них попытается произвести очередной опрос, и есть ли вообще такой.
  for waker in wakers {
    waker.wake();
  }
}

И вот в чём проблема: waiting_for_elements — это Vec<Waker >. Канал не может знать, сколько задач заблокировано, поэтому нельзя использовать массив фиксированного размера. Использование Vec означает, что мы аллоцируем память каждый раз, когда ставим в очередь waker, и эта память занимается/освобождается при каждом пробуждении задач.

Получается, что в случае примитивной реализации мы будем раз за разом аллоцировать и освобождать память при отправке и получении в стабильном режиме, а это весьма приличный объём.

▍ Можно ли использовать интрузивный список?

Интересно, можно ли в качестве оптимизации не аллоцировать память для Vec при каждом блокировании задачи в очереди, а сохранять список waker внутри самих заблокированных промисов (futures)? Мы знаем, что нужно сохранять лишь столько waker, сколько заблокировано в качестве промисов, а значит, такое решение должно сработать.

И выглядеть оно будет примерно так:

pub struct Channel<T> {
  q: VecDeque<T>,
  // Начало внедряемого двусвязного списка.
  waiting_for_elements: WakerList,
}

fn send<T>(channel: &Channel<T>, value: T) {
  channel.q.push_back(value);
  let wakers = channel.waiting_for_elements.extract_list();
  // Освобождаем все мьютексы перед пробуждением.
  for waker in wakers {
    waker.wake();
  }
}

pub struct Recv<'a, T> {
  channel: &'a Channel<T>,
  // Каждый Future получает WakerSlot, который является узлом интрузивного двусвязного 
// списка, защищённым мьютексом Channel.

  waker: WakerSlot,
}

impl<'a, T> Future for Recv<'a, T> {
  type Output = T;
  
  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
    if let Some(element) = self.channel.q.pop_front() {
      Poll::Ready(element)
    } else {
      // Очередь пуста — повторяем попытку позже.
      // Сохраняем waker в этом Future, связывая его со списком канала.
      self.channel.waiting_for_elements.link(&mut self.waker, cx.waker().clone());
      Poll::Pending
    }
  }
}

И на этом мой надуманный показательный код заканчивается. Пора переходить к деталям. Как выразить интрузивный связанный список в Rust?

▍ Крейты для создания интрузивных списков

Идея эта оказалась не нова, и я нашёл несколько подходящих крейтов:

• intrusive-collections [14] является весьма популярным, но узлы списков в нём должны жить дольше самого списка. В моём же случае промис никогда не будет жить дольше канала.
• futures-intrusive [15] — интересный крейт, который реализует ту же оптимизацию, но не отвечает моим целям.
• multilist [16] — это эксперимент Патрика Уолтона, ещё не достигший версии 1.0. Хорошая идея, но здесь узлы аллоцируются в куче.

Есть ещё два примера реализации подхода для продакшена:

• lilos-list [17] является частью разработанной Клиффом Биффлом встраиваемой ОС lilos ^[18]. Этот крейт сохраняет waker вместе с интрузивным списком, и он уже ближе к тому, что мне нужно. Но код этой встраиваемой ОС имеет собственную модель конкурентности. В частности, потребуется проделать некоторую работу для его интеграции с мьютексами стандартной библиотеки, плюс он вызывает waker при удерживаемых блокировках ^[19], что нежелательно. С другой стороны, поскольку в lilos нет потоков, это позволяет избежать реализации Send и использовать std::cell::Cell [20] для временной мутации ссылок, которые в противном случае являлись бы совместно используемыми.
• tokio [21] тоже сохраняет создаваемых waker в интрузивном списке. Его реализация содержит на удивление много кода, зато он ближе всего к тому, что мне нужно. Хотя это спорный момент, поскольку сей нюанс реализации за пределами Tokio не виден. (Подробнее читайте в заметке Элис Рил ^[22] на тему сложностей при работе с интрузивными структурами в Rust.)

▍ Закрепление (Pin)

Пора писать крейт.

Я хочу, чтобы канал сохранял WakerList, и у каждого промиса был член WakerSlot. Слоты можно связывать со списком и отвязывать при пробуждении либо при отмене промиса.

WakerList и WakerSlot формируют самореферентную структуру данных. Такие структуры в Rust известны своей проблемностью, так как требуют использовать небезопасный код.

В C++ подобное реализуется относительно просто. Вы удаляете операции перемещения и копирования, после чего должным образом исправляете указатели ссылок.

Собственно, поэтому, столкнувшись с описанной задачей в Rust, но продолжая мыслить в контексте C++, я решил, что будет «легко»!

Мне лишь нужно было исключить перемещение с помощью !Unpin (по факту PhantomPinned [23]) и обеспечить, чтобы все методы получали Pin<&mut WakerList> и Pin<&mut WakerSlot>.

Если вы встречаете Pin<&mut T>, то можете быть уверены, что T больше никогда не переместится. Я не стану разбирать тип Pin подробно — у Йона Гьенсета есть прекрасный ролик ^[24], где он объясняет его смысл и способ использования.

А вот здесь всё усложняется. Возможность закрепления (Pin) была добавлена значительно позже того, как Rust 1.0 стал стабилен. В этом языке повсеместно предполагается, что значения любого типа могут перемещаться с помощью memcpy, поэтому написание структуры данных, которая нарушает это допущение, делает сами публичные API весьма странными.

Вот, что я попробовал изначально:

struct WakerSlot(...);
struct WakerList(...);

impl WakerList {
  fn link<'list : 'slot, 'slot>(
    self: Pin<&'list mut WakerList>,
    slot: Pin<&'slot mut WakerSlot>,
  )
}

Я думал, что факт связывания должен ограничить «закреплённость» и время жизни, то есть список в итоге будет существовать дольше слота. Увы, но принцип времени жизни так не работает ^[25]. Вызов функции не может ограничивать фактические сроки жизни её параметров. Анализатор заимствований без стеснений просто сократит время жизни 'list и 'slot до наименьшего, чтобы обеспечить соблюдение прописанного мной ограничения. В итоге составленное выше определение link никакого эффекта не оказывает.

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

(Писать подобную статью после всего этого кажется странным, поскольку «конечно, всё работает не так», но я искренне документирую ход своего обучения.)

Может ли WakerSlot сам определить время жизни списка, на который ссылается?

struct WakerList(...);
struct WakerSlot<'list>(...);

impl WakerSlot<'_> {
  fn new(list: &WakerList) -> WakerSlot<'_>;
}

Такой вариант не работает. Если вы представите, что WakerSlot содержит ссылку на WakerList, то никогда не сможете создать &mut WakerList где-либо ещё, поскольку основное правило времени жизни в Rust гласит, что у вас может быть либо одна мутабельная ссылка, либо множество иммутабельных, но не то и другое одновременно.

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

▍ Когда паника не обеспечивает нужную безопасность

В принципе, операции link и unlink получают мутабельные ссылки на список и слот, но я так и не нашёл способ обеспечить соответствие всем правилам системы типов:

• Параметр времени жизни WakerSlot не превышает время жизни списка.
• Допустима лишь одна &mut ссылка одновременно.
• Никогда нельзя использовать &mut и & одновременно.

И здесь я перестал стараться выразить эти правила в системе типов, решив использовать утверждение в среде выполнения, где действуют следующие правила времени жизни:

• WakerList при отбрасывании должен быть пуст. В противном случае слоты будут содержать указатели на недействительные области памяти.
• WakerSlot при отбрасывании должен быть отвязан (unlink). В противном случае список будет ссылаться на освобождённую память.

И извещения о нарушении этих требований с помощью panic! недостаточно. Сообщения panic! можно перехватить, но программа продолжит находиться в состоянии, когда безопасный код может обращаться к зависшим указателям, вызывая неопределённое поведение (undefined behavior, UB)

Поэтому, когда требование нарушается, программа должна останавливаться.

Но я не могу просто вызывать abort: мне нужно, чтобы этот вспомогательный крейт действовал как [no_std], поэтому решение об остановке (abort) должна принимать вызывающая программа.

Самым простым вариантом, какой я нашёл, стало выполнение panic! из функции extern "C" и возложение ответственности за перевод этой паники в отмену на Rust.

#[allow(non_snake_case)]
#[inline(never)]
#[cold]
extern "C" fn MUST_UNLINK_WakerSlot_BEFORE_DROP() -> ! {
    // panic! из extern "C" ведёт к отмене с сообщением об ошибке.
    panic!("Must unlink WakerSlot before drop")
    // Ещё одним решением ценой добавления крохотной, стабильной зависимости является крейт `abort`.
    //abort::abort()
}

▍ Закрепление структур

В коде выше я опустил эту деталь, но доступ к WakerList должен происходить через мьютекс. Однако ни std::sync::Mutex [26], ни parking_lot::Mutex [27] не дают возможности закрепления структур ^[28]. То есть lock() — это &Mutex<T> поверх &mut T, позволяющий перемещать T.

Мне требовался безопасный API для получения Pin<&mut T> из Pin<&Mutex<T>>.

Для этого я написал крейт pinned-mutex [29], который предоставляет обёртки Mutex, MutexGuard и Condvar с закрепляемыми структурами.

Обратите внимание, что существует крейт pinarcmutex ^[30], в котором есть тип PinArcMutex<T >, примерно равнозначный Pin<Arc<Mutex<T>>>, но без возможности закрепления структур. Однако он использует аллокацию, и вы не можете встроить мьютекс parking_lot, который быстрее и легче мьютекса из стандартной библиотеки.

Можно помечтать о будущей версии Rust, в которой закрепление реализуется более естественно и имеет повсеместную (или неявную) поддержку в стандартной библиотеке.

▍ Эргономика закрепления

Боатс недавно написал хороший очерк ^[31] на тему, почему Pin создан именно таким образом, и почему его так сложно использовать.

Кроме того, в интернете полно топиков вроде «Pin Suffering Continues ^[32]».

Если вы хотите безопасно использовать закреплённые API в своём коде, вам придётся согласиться на зависимость от крейта вроде pin-project [33] или pin-project-lite [34]. (И не забудьте о макросе pinned_drop! [35])

Этот подход прекрасно работает, но в итоге вы получаете примерно такой код:

let mut wakers = state.as_mut().project().base.project().rx_wakers.extract_some_wakers();
while wakers.wake_all() {
    let mut state = self.project_ref().state.lock();
    wakers.extract_more(state.as_mut().base().project().rx_wakers);
}

Писать такой код очень невесело. Компилятор будет давать вам подсказки, но меня не покидала мысль: «Ты же знаешь, что мне нужно, просто сделай это!»

▍ Заработало!

Можно спокойно выдохнуть — тесты пройдены. WakerList и WakerSlot предоставляют нужный мне интерфейс, поэтому я разместил их в крейте wakerset [36], который предоставляет безопасный, интрузивный no_std список waker.

С его помощью я смог удалить в batch_channel основной источник аллокаций в стабильном состоянии.

Пришло время всё подчистить и убедиться, что я ничего не упустил, но это лишь середина статьи.

▍ Неопределённое поведение, санитайзеры и MIRI

Одной из моих изначальных целей использования batch-channel было избежание небезопасного кода.

К сожалению, в двух оптимизациях он всё же оказался неизбежен. Помимо описанного выше интрузивного списка, сами объекты MPMC-каналов управлялись с помощью двух счётчиков ссылок, один для отправителей и один для получателей. Здесь требовался раздельный подсчёт ссылок: когда одна половина канала отбрасывалась, он закрывался.

Для упрощения контроля я поместил весь этот новый unsafe код за безопасным API и отдельными крейтами:

• splitrc [37]
• wakerset [36]
• pinned-mutex [29]

В безопасном Rust, за исключением выдаваемых компилятором ошибок и неправильно спроектированных API, неопределённое поведение отсутствует. При этом небезопасный Rust, напротив, лишает вас защитных ограждений и делает возможными массу вариантов UB ^[38].

Есть три способа обработки возможного неопределённого поведения. Приведу их в порядке повышения спокойствия со временем:

• Надеяться на лучшее и разбираться с багами по мере их появления.
• Тщательно всё обдумывать и верить, что ваш код корректен.
• Автоматизированные санитайзеры.

К счастью, Rust поддерживает санитайзеры ^[39], которые обнаруживают различные виды неопределённого поведения. Двумя наиболее полезными являются ASan ^[40] и TSan ^[41]. Программисты C++ хорошо знакомы с ними в этом контексте, и я считаю их неотъемлемой частью любого проекта на C или С++.

Но для Rust есть кое-что получше: MIRI ^[42]. Этот инструмент отлавливает нарушения в модели псевдонимов, являясь более скрупулёзным в сравнении с ASAN. И именно за устранением причин претензий MIRI я провёл больше всего времени.

▍ Модель псевдонимов в Rust

Когда я первый раз запустил MIRI, проверка провалилась:

test link_and_notify_all ...
error: Undefined Behavior: trying to retag from <254318> for SharedReadWrite permission at alloc88289[0x10], but that tag does not exist in the borrow stack for this location
...
trying to retag from <254318> for SharedReadWrite permission at alloc88289[0x10], but that tag does not exist in the borrow stack for this location
...
help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information

Stacked borrows? Что это вообще такое?

И здесь мне стала ясна моя первая ошибка: я углубился прямиком в unsafe Rust и должен был заранее получше ознакомиться с документацией:

• Learning Rust With Entirely Too Many Linked Lists ^[43]
• Rust Unsafe Code Guidelines ^[44]
• The Rustonomicon ^[45]

Моей второй ошибкой было «мыслить на С». Хорошее знакомство с семантикой этого языка ^[46] здесь не помогло. Сейчас, когда я оглядываюсь назад, мне кажется, было глупо предполагать, что модель псевдонимов в Rust аналогична их модели в C. В C наличие указателей на значение, как правило, не несёт никакого смысла. Там вы в первую очередь продумываете операции разыменовывания указателей.

Например, в C абсолютно допустимо, если p == q:

void foo(int* p, const int* q) {
  printf("%dn", *q);
  *p = 456;
  printf("%dn", *q); // Если p == q, выводится 456.
  *(int*)q = 789;
  printf("%dn", *p); // Если p == q, выводится 789.
}

Ключевое слово const здесь «бессмысленно» в том плане, что не препятствует возможному изменению указателя, поэтому компилятор не может произвести на основе этого оптимизацию.

fn foo(a: &u32, b: &mut u32) {
    println!("{a}");
    *b = 123;
    println!("{a}"); // Всегда выводит то же значение, что и выше.
}

С другой стороны, в Rust главное правило использования псевдонимов гласит, что на объект в любой момент времени может присутствовать либо уникальная &mut ссылка, либо множество совместно используемых & ссылок, но никак не то и другое.

И оптимизатор учитывает это. Значение a не загружается повторно из памяти, так как запись в b не может создать для него псевдоним.

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

▍ Box::leak

Начнём с самого непонятного примера, с которым я столкнулся:

let p = Box::leak(Box::new(MyThing::new())) as *mut MyThing;
// Позднее:
let ref: &MyThing = *p;
ref.method();

Проверка MIRI провалилась с сообщением о том, что p была сформирована из бессрочной &mut, возвращённой Box::leak, а значит, последующее создание на неё общей ссылки &MyThing вызовет неопределённое поведение.

Исправлением стала аллокация без формирования ссылки:

let p = Box::into_raw(MyThing::new());
// Позднее:
let ref: &MyThing = *p;
ref.method();

Примечание: это мог быть баг MIRI, или с тех пор правила были смягчены, так как в версии nightly-2024-06-12 я эту ошибку воспроизвести уже не могу. Вот где модель памяти и неполноценность правил использования псевдонимов вызвали боль: когда проверка MIRI проваливается, неясно, моя в том вина или же нет. Например, если учесть, что &mut сразу же была превращена в указатель, продолжает ли &mut ссылка существовать? Здесь можно интерпретировать правила по-разному.

▍ Box::from_raw

Хорошо, если вы аллоцируете память с помощью Box::into_raw, то предполагаете её освобождение с помощью Box::from_raw, верно? Но и здесь MIRI не согласилась.

В итоге мне пришлось написать следующее:

unsafe {
    let ptr = ptr.as_ptr();
    std::ptr::drop_in_place(ptr);
    std::alloc::dealloc(
        ptr as *mut u8,
        std::alloc::Layout::new::<Inner<T>>());
}

Примечание: это тоже могло быть багом MIRI. Воспроизвести я эту ошибку больше не смог. Я изменил splitrc на использование Box::into_raw и Box::from_raw, после чего проверка MIRI была пройдена. Я включил MIRI в свою схему непрерывной интеграции, так что мы увидим, если в дальнейшем она вдруг укажет на какие-то проблемы.

▍ Связывание, ссылки и внутренняя мутабельность

На этом разбор темы аллокации памяти под канал и её освобождения завершён. Теперь перейдём к интрузивным указателям в wakerset.

В связанном списке у каждого узла есть структура, связывающая его с другими узлами.

struct Pointers {
    next: *mut Pointers,
    prev: *mut Pointers,
    pinned: PhantomPinned,
}

struct WakerList {
    pointers: Pointers,
}

struct WakerSlot {
    pointers: Pointers,
    // Необходимо утвердить, что этот слот никогда не отвязывается от списка, к которому не относится.
    owner: *mut WakerList,
    waker: Option<Waker>,
}

А теперь представим два потока. Поток А содержит &mut WakerList с целью извлечения ожидающих waker. Поток B как раз в то же время содержит &WakerSlot.

Если код, который обходит эти указатели, сформирует &mut WakerSlot (или даже &WakerSlot) при том, что любой из потоков тоже может иметь &mut WakerSlot, возникнет неопределённое поведение, поскольку будут нарушены правила использования псевдонимов. &mut ссылка всегда должна быть эксклюзивной, даже если она никогда не разыменовывается. И в этом состоит важное отличие от C.

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

Нам нужно не дать компилятору оптимизировать &WakerSlot в ранние операции чтения полей pointers и waker.

Реализовать это нам поможет инструмент UnsafeCell [47]. Он вносит «барьер мутабельности», а UnsafeCell<Pointers> исключает кэширование операций чтения. Мы обязаны проследить, чтобы при доступе к полям Pointer не нарушались правила использования псевдонимов.

struct WakerList {
    pointers: Pointers,
}

struct WakerSlot {
    // UnsafeCell: запись производит WakerList, независимо от ссылок WakerSlot.
    pointers: UnsafeCell<Pointers>,
    // Необходимо утвердить, что этот слот никогда не отвязывается от списка, к которому не относится.
    owner: *mut WakerList,
    waker: Option<Waker>,
}

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

Проделал я это, обеспечив важную и тонкую гарантию для API: все операции с привязыванием и отвязыванием должны получать &mut WakerList. Если для отвязывания было бы достаточно &mut WakerSlot, то в случае расположения WakerList за мьютексом безопасность потоков оказалась бы под угрозой. (Это также означает, что WakerList не требует UnsafeCell<Pointers>.)

Крейт pinned-aliasable [48] решает связанную с этим проблему: «Как определять самореферентные структуры данных с мутабельными ссылками, которые не приведут к искажениям при компиляции?» Почитайте в документации крейта о причинах его создания. Эта ситуация касается асинхронных промисов, которые являются самореферентными, в связи с чем закрепляются, но при этом от синтаксического сахара не очищаются. Подробнее можете изучить тему в открытом Issue #63818 ^[49].

▍ Полный отказ от ссылок

Как уже говорилось, при обходе связанного списка легко сформировать конфликтующие &mut ссылки на узлы. Разберём следующий, слегка надуманный, пример с отвязыванием:

let p = &slot.pointers as *mut Pointers;
let next: &mut Pointers = *(*p).next;
let prev: &mut Pointers = *(*p).prev;
next.prev = prev as *mut Pointers;
prev.next = next as *mut Pointers;
(*p).next = ptr::null_mut();
(*p).prev = ptr::null_mut();

Если slot — это единственный слот в списке, тогда и next, и prev будут указывать на WakerList, и мы только что создали две мутабельные ссылки на одно и то же значение, что является неопределённым поведением.

Конкретно в этом случае мы можем обеспечить, чтобы разыменовывание каждого указателя происходило как временное. Так мы ограничим область действия каждой ссылки одной строкой.

let p = &slot.pointers as *mut Pointers;
let next = (*p).next;
let prev = (*p).prev;
(*next).prev = prev;
(*prev).next = next;
(*p).next = ptr::null_mut();
(*p).prev = ptr::null_mut();

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

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

let nextp = addr_of_mut!((*node).next);
let prevp = addr_of_mut!((*node).prev);
let next = nextp.read();
let prev = prevp.read();
addr_of_mut!((*prev).next).write(next);
addr_of_mut!((*next).prev).write(prev);
nextp.write(ptr::null_mut());
prevp.write(ptr::null_mut());

(Так много синтаксиса, что невольно начинаешь ценить C).

Ключом здесь является addr_of_mut!: она вычисляет указатель на выражение аллокации памяти, не формируя ссылку. Но тут есть подвох: вы всё равно можете случайно создать ссылку внутри аргумента addr_of_mut!. Подробнее читайте в документации ^[50].

Примечание: когда я публиковал эту статью, в Rust 1.82 как раз добавили новый синтаксис ^[51], позволяющий заменять addr_of_mut! на &raw mut, а addr_of! — на &raw const. Но мне пока неясно, насколько это позволит избежать случайного создания ссылок.

Несмотря на эту новость, из соображений безопасности я в итоге преобразовал все WakerSet в операции чтения и записи указателей. Тем не менее grep этого не покажет: код по-прежнему выглядит так, будто в нём полно разыменовываний указателей, но все они находятся внутри addr_of_mut!, и выражения аллокации памяти имеют правильную структуру.

Думаю, это Патрик Уолтон однажды предложил ввести для небезопасного Rust и указателей синтаксический сахар с использованием гипотетического оператора ->. Это было бы удобнее и проще для восприятия.

До тех пор, пока разработчики Rust как следует не стабилизируют модель использования памяти и не определят полноценно правила использования псевдонимов, лучшим вариантом для вас остаётся добавление в CI любого проекта, где есть unsafe код, инструментов ASAN, TSAN и MIRI (stacked borrows ^[52] и tree borrows ^[53]).

Если же ваш проект пишется на безопасном Rust, но зависит от крейта, который активно использует unsafe код, то наверняка лучше добавить в него санитайзеры. Я не мог обнаружить всё неопределённое поведение в wakerset, пока не интегрировал его в batch-channel.

▍ MIRI: Stacked Borrows и Tree Borrows

MIRI поддерживает две модели использования псевдонимов: stacked borrows и tree borrows.

Я не буду пытаться их объяснить. Это разные подходы с одной целью: формализовать и проверить модель управления памятью в Rust. Ральф Юнг, Невен Виллани и другие ребята проделывают невероятную работу. Без MIRI было бы сложно доверять небезопасному Rust.

Я решил использовать stacked borrows и tree borrows — пока ложных срабатываний замечено не было.

▍ Самореферентные структуры данных активно разрабатываются

Эта тема активно прорабатывается ^[54], так что, надеюсь, через пару лет данная статья утратит свою актуальность.

Вокруг самореферентных структур данных и закрепления сегодня идёт много разговоров. К примеру, проект Rust-for-Linux ^[55], реализующий программы системного уровня, ставит удобство использования Pin и самореферентные структуры данных в начало списка желаемых функций ^[56].

В частности, это касается проблемы инициализации закреплённых структур ^[57]. В ядре Linux есть самореферентные структуры данных, которые на данный момент сложно инициализировать с помощью безопасного кода. В wakerset я обошёл эту проблему ценой небольшой потери эффективности выполнения, создав для WakerList два пустых состояния: одно подвижное и одно закреплённое. Первое преобразуется во второе при первом использовании после закрепления.

К слову, у y86-dev есть прекрасная статья «Safe Pinned Initialization ^[58]».

▍ Заключение

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

Что я усвоил из всего этого процесса?

• При любом использовании unsafe необходимо быть предельно осторожным.
• Ссылки, даже если никогда не используются, опаснее указателей в C.
• Синтаксис для закрепления просто ужасен, но, судя по всему, его однажды доведут до ума.
• Для интрузивных структур данных необходим UnsafeCell.
• Я не знаю, как статически ограничить время жизни связей с помощью интрузивных структур, но, возможно, это реально? Было бы круто исключить необходимость применения утверждений для среды выполнения.
• Крайне важно использовать MIRI, особенно многопоточные стресс-тесты.
• Изложить всё это словами было не легче, чем писать сам код.