Ненадежный код: бич каждого программиста. В таких языках, как Rust и C#, небезопасный код формально отделен от остального кода на уровне языка. Хотя по своей сути они «небезопасны», они часто служат основой большинства «безопасных» абстракций.

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

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

Блок опций

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

• Ключ — целое число.
• Значение может быть любого типа T.
• Хэш-функция — это просто функция тождества.¹

Простое представление

У нас может возникнуть соблазн реализовать DAT в терминах [Option<T>; N], где N — это usize, представляющий количество записей в DAT. Однако, по причинам, выходящим за рамки данной статьи²массив необязательных значений неэффективен для памяти. В худшем случае представление [Option<T>; N] требует вдвое больше памяти, чем DAT, который мы будем реализовывать.

РЕКЛАМА: Тип Option, как и большинство типов enum, несущих данные, в Rust, по сути, являются маркированными союзами. Таким образом, он состоит из двух частей данных: полезной нагрузки и дискриминанта/тега.

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

Есть только несколько исключений из этого правила. А именно, это ссылки (&T и &mut T), умные указатели (Box<T>, Rc<T>, Arc<T> и др. ), и ненулевые варианты целочисленных типов (NonZeroU8, NonZeroU16 и т.д.).³

use core::{mem::size_of, num::NonZeroU32};

// We obtain 8 bytes here: 4 bytes for the actual `u32`
// plus 4 more bytes for the `enum` discriminant (which
// has been padded for alignment).
type Unoptimized = Option<u32>;
assert_eq!(size_of::<Unoptimized>(), 8);

// We obtain 4 bytes here. There is no need to explicitly
// store a discriminant because the value itself implicitly
// encodes it. That is, the "zero" value is treated as the
// `None` variant. Otherwise, the value is in the `Some` variant.
type Optimized = Option<NonZeroU32>;
assert_eq!(size_of::<Optimized>(), 4);

Из приведенного примера должно быть очевидно, что представление [Unoptimized; N] занимает вдвое больше памяти, чем представление [Optimized; N] для любого размера N. Это наихудший сценарий, когда однобитный дискриминант занимает слишком много места.

Альтернативное представление

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

// A neat wrapper that marks data as "maybe-uninitialized".
use core::mem::MaybeUninit;

// A block of 32 optional values.
pub struct Block32<T> {
    // An array of 32 "maybe-uninitialized" values.
    data: [MaybeUninit<T>; 32],
    // Since we have 32 values, we use an
    // unsigned 32-bit integer as our mask.
    // The least significant bit keeps track
    // of the discriminant at index `0`.
    mask: u32,
}

Самое примечательное, что наше новое представление использует массив «возможно неинициализированных» значений. Значение в базовом массиве инициализируется, если (и только если) оно является действительной записью в DAT. Обертка core::mem::MaybeUninit из стандартной библиотеки облегчает этот случай использования.

О Maybe-Uninitialized Memory

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

1. Метод MaybeUninit::<T>::assume_init приводит MaybeUninit<T> к T.
   • Аналогично, метод assume_init_ref приводит &MaybeUninit<T> к &T.
   • Тем временем, метод assume_init_mut приводит &mut MaybeUninit<T> к &mut T.
2. Базовый внутренний тип T должен быть правильно инициализирован перед вызовом любого из методов assume_init.
   • В противном случае поведение будет неопределенным из-за использования мусорной памяти.
3. По умолчанию MaybeUninit<T> (как есть) не сбрасывает внутреннее значение T — даже если внутреннее значение правильно инициализировано!
   • Поскольку T может быть неинициализированным, мы не можем предположить, что вызов деструктора на потенциально «мусорной памяти» безопасен.
   • Стандартная библиотека использует консервативный подход, не вызывая деструктор вообще. Таким образом, утечка памяти на самом деле очень проста!
   • Существует два способа сбросить внутреннее значение:
     • Вызовите метод assume_init_drop, который принимает &mut MaybeUninit<T> и бросает внутренний T на месте.
     • Вызовите метод assume_init на принадлежащем MaybeUninit<T> и просто отбросьте полученный T (покинув текущую область видимости).

use core::mem::MaybeUninit;

// IMPORTANT: Accessing garbage memory is undefined behavior!
let uninit = MaybeUninit::<u32>::uninit();
let _ = unsafe { uninit.assume_init() }; // Garbage Memory!

// IMPORTANT: Improperly initialized values invoke undefined behavior!
// Recall that references can never be null.
let null_ref = MaybeUninit::<&u32>::zeroed();
let _ = unsafe { null_ref.assume_init() }; // Invalid Initialization!

// IMPORTANT: `MaybeUninit` (as is) does not invoke destructors.
let valid_string = MaybeUninit::new(String::from("Hello!"));
drop(valid_string); // Memory Leak!

Реализация некоторых базовых операций

Теперь мы можем реализовать DAT. Сначала мы определим конструктор по умолчанию.

#![feature(maybe_uninit_uninit_array)]

impl<T> Default for Block32<T> {
    fn default() -> Self {
        Self {
            // As of Rust 1.62, note that the `uninit_array` method
            // is a nightly-only feature. For the sake of brevity,
            // we will be using this function.
            //
            // Alternatively, for stable toolchains, we may opt to
            // directly inline the definition for `uninit_array`
            // instead. Please consult the documentation accordingly.
            data: MaybeUninit::uninit_array(),
            // We then start with an empty mask.
            mask: 0,
        }
    }
}

Затем мы переходим к простым, безопасным функциям. Метод is_vacant особенно важен, поскольку он будет широко использоваться для поддержания безопасности.

impl<T> Block32<T> {
    // Checks whether the DAT is empty.
    pub const fn is_empty(&self) -> bool {
        self.mask == 0
    }

    // Returns the number of valid entries in the DAT.
    pub const fn len(&self) -> u32 {
        self.mask.count_ones()
    }

    // Checks whether the slot at the `index` contains a
    // valid entry. Panics if the `index` is out of bounds.
    pub const fn is_vacant(&self, index: usize) -> bool {
        assert!(index < 32);
        let query = 1 << index;
        self.mask & query == 0
    }
}

Далее мы реализуем методы insert и remove. Поскольку эти методы взаимодействуют с MaybeUninit, нам нужно быть немного более осторожными с неизбежным небезопасным кодом.

Лучшей практикой (в идеале не только в Rust) является добавление «комментария безопасности» для всех случаев использования кода unsafe. Как следует из названия, комментарии безопасности должны объяснять, почему безопасно вызывать процедуру unsafe. Как правило, в них разъясняются (внутренние и внешние) инварианты, которые соблюдаются до и после процедуры.

use core::mem::replace;

impl<T> Block32<T> {
    // Inserts a `value` at `index`. Returns the old value, if any.
    pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
        // Extract the old value
        let wrapped = MaybeUninit::new(value);
        let old_vacant = self.is_vacant(index);
        let old_value = replace(&mut self.data[index], wrapped);

        // Ensure that the bit in the mask is set to 1
        self.mask |= 1 << index;

        // Return the old value
        if old_vacant {
            None
        } else {
            // SAFETY: Old value has been verified
            // to be properly initialized.
            Some(unsafe { old_value.assume_init() })
        }
    }

    // Removes a `value` at `index`. Returns the old value, if any.
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if self.is_vacant(index) {
            return None;
        }

        // Extract the old value
        let dest = &mut self.data[index];
        let old_value = replace(dest, MaybeUninit::uninit());

        // Ensure that the bit in the mask is reset to 0
        self.mask &= !(1 << index);

        // SAFETY: We have verified that the slot is not vacant.
        Some(unsafe { old_value.assume_init() })
    }
}

Наконец, мы реализуем методы getter. Они относительно более просты, поскольку нам не нужно думать о мутации внутренней битовой маски.

impl<T> Block32<T> {
    // Immutably borrow the value at `index`.
    pub fn get(&self, index: usize) -> Option<&T> {
        if self.is_vacant(index) {
            None
        } else {
            // SAFETY: Slot is initialized.
            Some(unsafe { self.data[index].assume_init_ref() })
        }
    }

    // Mutably borrow the value at `index`.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if self.is_vacant(index) {
            None
        } else {
            // SAFETY: Slot is initialized.
            Some(unsafe { self.data[index].assume_init_mut() })
        }
    }
}

Реализация Clone

Теперь мы должны дать пользователю возможность клонировать DAT по своему усмотрению. К сожалению, мы не можем просто derive(Clone) в нашей реализации. Предполагая, что внутренний тип T реализует Copy, реализация Clone на удивление тривиальна.

//     `T` must implement `Copy`...
//     👇
impl<T: Copy> Clone for Block32<T> {
    fn clone(&self) -> Self {
        Self {
            // Recall that `MaybeUninit<T>` implements `Copy` if
            // (and only if) `T` implements `Copy` as well.
            // Therefore, a bitwise copy of an array of `T` values
            // should be trivial.
            //
            // There are no extra lifetime considerations here since
            // `Copy` guarantees that `T` cannot implement a fancy
            // `Drop` implementation (stated in the documentation).
            data: self.data,
            mask: self.mask,
        }
    }
}

Однако у этого подхода есть одна серьезная проблема. Значительно реже типы реализуют Copy! В идеале, мы хотим реализовать Clone для нашего DAT, если (и только если) внутренний тип T также реализует Clone. Требование Copy является слишком ограничительным!

Поскольку мы ослабляем ограничение Copy, чтобы было просто Clone, то побитовая копия data больше не является правильной. Мы должны явно клонировать каждый T в data в новый DAT, чтобы вызвать любую дополнительную (но необходимую) логику клонирования. Для большинства типов достаточно побитового копирования; для других (таких как String) необходима дополнительная очистка и ведение учета.

//     `T` is only required to implement `Clone` (not `Copy`).
//     This should be less restrictive and hence applicable to
//     more types...
//     👇
impl<T: Clone> Clone for Block32<T> {
    fn clone(&self) -> Self {
        let mut block = Self::default();
        block.mask = self.mask;

        for i in 0..32 {
            // Do not clone vacant slots
            if self.is_vacant(i) {
                continue;
            }

            // SAFETY: Slot is not vacant, and hence initialized.
            let value = unsafe { self.data[i].assume_init_ref() };

            // Manually clone the data
            block.data[i] = MaybeUninit::new(value.clone());
        }

        block
    }
}

О, нет! Потенциальные утечки памяти!

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

let mut block = Block32::default();
block.insert(0, String::from("Hello"));
block.insert(1, String::from("World"));
block.insert(2, String::from("Rusty"));
block.remove(2);
drop(block); // Leaks "Hello" and "World"!

Этот невинный на первый взгляд фрагмент кода на самом деле утекает много памяти! Вспомните, что MaybeUninit (как есть) никогда не вызывает деструктор. Чтобы правильно сбросить значение, мы должны сначала вызвать assume_init, чтобы привести MaybeUninit<T> к T. Преобразование в T позволяет применить обычные правила выпадения.

Возвращаясь к примеру, нет никаких проблем с операциями insert и remove. Поскольку они обе вызывают assume_init внутри, каждая String правильно удаляется при перемещении из block.

Утечка памяти происходит, когда сам block выходит из области видимости, но в базовом массиве все еще остаются некоторые инициализированные элементы. Поскольку деструкторы не запускаются, память, конечно, утекает. Решение состоит в том, чтобы реализовать Drop для нашего DAT, чтобы все оставшиеся элементы были надлежащим образом уничтожены.

impl<T> Drop for Block32<T> {
    fn drop(&mut self) {
        for i in 0..32 {
            // No more memory leaks! An `Option<T>` is dropped
            // here, which implies dropping the inner `T`, if any.
            self.remove(i);
        }
    }
}

Улучшенный отпечаток памяти

use core::{mem::size_of, num::NonZeroU8};

// 64 Bytes
type Unoptimized = [Option<u8>; 32];
assert_eq!(size_of::<Unoptimized>(), 32 * 2);

// 32 Bytes
type Optimized = [Option<NonZeroU8>; 32];
assert_eq!(size_of::<Optimized>(), 32);

// 36 Bytes
assert_eq!(size_of::<Block32<u8>>(), 32 + 4);

В худшем случае, оригинальное представление «массив опциональных значений» требует 64 байта памяти. Для каждой из 32 записей выделяется два байта: один байт для фактической полезной нагрузки u8 и еще один байт для дискриминанта enum. Это занимает в два раза больше байт, чем необходимо!

Между тем, лучший сценарий (использование NonZeroU8) требует всего 32 байта памяти. Хранение дискриминанта enum больше не требуется, что сокращает объем памяти вдвое! К сожалению, для большинства типов эта оптимизация все равно не подходит.

Для таких случаев наша реализация DAT обеспечивает достаточно близкий объем памяти к оптимальному сценарию. Есть только (возможно) незначительные накладные расходы, связанные с обязательной битовой маской, которые, тем не менее, значительно лучше, чем у неоптимизированной версии.

Заключение

Честно говоря, я хотел бы закончить эту статью утверждением, что небезопасный код не так страшен, как кажется. Однако, как мы убедились, здесь есть над чем подумать — даже для нашего относительно простого примера с MaybeUninit! Реализуя DAT, мы затронули такие темы, как неинициализированная память, деструкторы, побитовые копии и явные клоны.

Может возникнуть соблазн вообще отказаться от небезопасного кода, учитывая, насколько громоздко реализовывать низкоуровневые структуры данных. Но… в этом-то и есть смысл. Написание unsafe кода неудобно, потому что он по своей природе сложен для правильной работы! Языки, изолирующие небезопасный код, побуждают нас думать более тщательно.

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

Общая нить, которая связывает все воедино, — это документация. Четкое документирование инвариантов дополняет демаркацию на уровне языка между безопасными абстракциями и небезопасными низкоуровневыми операциями. В идеале это дает нам мысленный контрольный список инвариантов, которые нужно соблюдать, как в некотором роде Unsafe Bingo. Когда контрольный список составлен, мы можем утверждать о безопасности с достаточной степенью уверенности.

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

Бонус: Ящик option-block

let mut block = option_block::Block8::<

Для вашего удобства я опубликовал набор option-block, который включает в себя 8-, 16-, 32-, 64- и 128-элементные варианты блока опций фиксированного размера, который мы реализовали в этой статье. Эти варианты соответственно называются Block8, Block16, Block32, Block64 и Block128.

Крейт также добавляет некоторые дополнительные методы, которые делают публичный API нашего DAT более совместимым со стандартными коллекциями. Среди этих возможностей — итераторы⁴ и удобные геттеры (get_or, get_or_else, и get_or_default).

Учитывая это, пожалуйста, не стесняйтесь поднимать вопросы и отправлять запросы на исправление!

1. Другими словами, ключ к карте — это буквально индекс в базовом хранилище массивов.

2. См. оптимизацию нулевого указателя. 

3. Обратите внимание, что все эти типы имеют одну общую черту: дискриминант неявно кодируется значением. Ссылки никогда не могут быть недействительными, поэтому компилятор кодирует None::<&T> как нулевой указатель. Те же рассуждения применимы к Box<T>, которые также никогда не бывают нулевыми. Аналогично, для ненулевых целых чисел литерал ноль используется для кодирования варианта None. Поскольку дискриминант является неявным, компилятор оптимизирует представление в памяти, исключая накладные расходы на дискриминант.

4. На момент написания статьи я еще не реализовал метод iter_mut.