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

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

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

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

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

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

• Множество отправителей (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 — это идентификатор заблокированной задачи. Когда асинхронная среда выполнения в очередной раз будет опрашивать канал, он просигнализирует ей о необходимости пробуждения задачи. Waker представляет собой широкий указатель, размером в два слова, который используется так:

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 является весьма популярным, но узлы списков в нём должны жить дольше самого списка. В моём же случае промис никогда не будет жить дольше канала.
• futures-intrusive — интересный крейт, который реализует ту же оптимизацию, но не отвечает моим целям.
• multilist — это эксперимент Патрика Уолтона, ещё не достигший версии 1.0. Хорошая идея, но здесь узлы аллоцируются в куче.

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

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

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

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

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

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

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

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

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

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

А вот здесь всё усложняется. Возможность закрепления (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>,
  )
}

Я думал, что факт связывания должен ограничить «закреплённость» и время жизни, то есть список в итоге будет существовать дольше слота. Увы, но принцип времени жизни так не работает. Вызов функции не может ограничивать фактические сроки жизни её параметров. Анализатор заимствований без стеснений просто сократит время жизни '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, ни parking_lot::Mutex не дают возможности закрепления структур. То есть lock() — это &Mutex<T> поверх &mut T, позволяющий перемещать T.

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

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

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

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

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

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

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

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

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

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, который предоставляет безопасный, интрузивный no_std список waker.

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

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

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

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

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

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

• splitrc
• wakerset
• pinned-mutex

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

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

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

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

Но для Rust есть кое-что получше: MIRI. Этот инструмент отлавливает нарушения в модели псевдонимов, являясь более скрупулёзным в сравнении с 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
• Rust Unsafe Code Guidelines
• The Rustonomicon

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

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

void foo(int* p, const int* q) {
  printf("%d\n", *q);
  *p = 456;
  printf("%d\n", *q); // Если p == q, выводится 456.
  *(int*)q = 789;
  printf("%d\n", *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. Он вносит «барьер мутабельности», а 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 решает связанную с этим проблему: «Как определять самореферентные структуры данных с мутабельными ссылками, которые не приведут к искажениям при компиляции?» Почитайте в документации крейта о причинах его создания. Эта ситуация касается асинхронных промисов, которые являются самореферентными, в связи с чем закрепляются, но при этом от синтаксического сахара не очищаются. Подробнее можете изучить тему в открытом Issue #63818.

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

Как уже говорилось, при обходе связанного списка легко сформировать конфликтующие &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!. Подробнее читайте в документации.

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

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

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

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

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

▍ MIRI: Stacked Borrows и Tree Borrows

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

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

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

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

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

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

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

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

▍ Заключение

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

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

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

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻