The Rustonomicon

% Выделение памяти

Использование Unique портит важную характеристику Vec (и на самом деле все стандартные коллекции): пустой Vec на самом деле вообще никак не размещается в памяти. Итак, если мы не размещаем ничего в памяти, а также не можем подсунуть нулевой указатель в ptr, что нам делать в Vec::new? Ну, просто подсунем какой-нить другой мусор туда!

Это отлично подходит, потому что мы уже ставили cap == 0 как проверку того, что выделение памяти не нужно. Нам даже не нужно специально перехватывать это в коде, потому что обычно требуется в любом случае проверить cap > len или len >0. По традиции в такой ситуации в Rust используют значение 0x01. Стандартная библиотека действительно экспортирует его в виде alloc::heap::EMPTY. Мы будем использовать heap::EMPTY довольно часто, потому что мы не выделяем память, а null сломало бы компилятор.

Всё API heap абсолютно нестабильно и скрыто под отключаемой нестабильной возможностью heap_api. Мы могли бы сами определить heap::EMPTY, но нам в любом случае нужна остальная часть API heap, поэтому давайте просто добавим зависимость от нее.

Итак:

#![feature(alloc, heap_api)]

use std::mem;

use alloc::heap::EMPTY;

impl<T> Vec<T> {
    fn new() -> Self {
        assert!(mem::size_of::<T>() != 0, "Мы не готовы работать с ТНР");
        unsafe {
            // необходимо явно привести EMPTY к настоящему типу ptr, позволим
            // выводу типов справиться с этим.
            Vec { ptr: Unique::new(heap::EMPTY as *mut _), len: 0, cap: 0 }
        }
    }
}

Я намеренно поставил assert, потому что ТНР потребуют особой обработки в нашем коде, а я хочу отложить эту проблему на потом. Без этого assert некоторые из наших ранних проектов делали бы Очень Плохие Вещи.

Следующее, что нам нужно, это определить, что делать, когда нам на самом деле нужно место в памяти. Для этого воспользуемся остальным heap_api. Он позволяет напрямую обращаться к аллокатору Rust (по умолчанию, jemalloc).

Также нам нужно обрабатывать условия нехватки памяти (англ. out-of-memory, OOM). Стандартная библиотека вызывает внутреннюю функцию abort, которая выполняет неправильную инструкцию, приводящую к краху всей программы. Причиной, по которой мы используем abort, а не панику, является то, что размотка может заставить выделить еще память, а это кажется не очень правильным, если выделение вернется с "эй, у меня же нет больше памяти".

Конечно, это немного глупо, ведь на большинстве платформ обычно не заканчивается память. Ваша ОС, наверняка, убьет приложение по другой причине, если оно станет использовать всю память. Самый вероятный случай, когда сработает OOM, является запрос смехотворного количества памяти за один раз (например, половина теоретического адресного пространства). В данном случае, вероятно, будет нормально вызвать панику, и ничего плохого не случится. Но мы пытаемся действовать как стандартная библиотека, поэтому просто убьем всю программу.

Мы сказали, что не будем использовать внутренние функции (intrinsics), поэтому сделаем то, что делает std - выйдем из программы. Вызовем std::process::exit со случайным числом.

#![allow(unused)]
fn main() {
fn oom() {
    ::std::process::exit(-9999);
}
}

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

if cap == 0:
    allocate()
    cap = 1
else:
    reallocate()
    cap *= 2

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

В частности, ptr::offset приносит немало неприятностей, потому что обладает семантикой ограниченных инструкций GEP LLVM (LLVM GEP inbounds instructions). Если вам везло раньше не сталкиваться с этими инструкциями, так вот, что делает GEP: анализ совпадения ссылок, анализ совпадения ссылок, анализ совпадения ссылок. Для оптимизирующего компилятора очень важно, чтобы он понимал зависимости данных и совпадения ссылок.

В качестве простого примера возьмем следующий фрагмент кода:

#![allow(unused)]
fn main() {
let x = &mut 0;
let y = &mut 0;
*x *= 7;
*y *= 3;
}

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

Если вы используете ограниченные инструкции GEP, вы особым образом говорите LLVM, что нужные вам смещения находятся внутри границ одной "размещенной" сущности. Основной выигрыш состоит в том, что LLVM может предположить, что если два указателя ссылаются на два непересекающихся объекта, смещения этих указателей также не совпадают (потому что вы не окажетесь в случайном месте в памяти). LLVM сильно оптимизирован на работу со смещениями GEP, а особенно с ограниченными инструкциями, поэтому важно использовать их по полной.

Итак, если это все, что делает GEP, то как же это может принести неприятности?

Первой проблемой является индексация массивов с помощью беззнаковых целых, а GEP (и, как следствие, ptr::offset) принимает целые со знаком. Это означает, что половина кажущихся правильными индексов вызовут переполнение GEP и, на самом деле, поведут в обратном направлении! Таким образом, мы должны ограничить все выделения памяти значением isize::MAX. Это означает, что мы должны волноваться только за объекты размером в 1 байт, потому что, например, выделение памяти под массив u16, длиной больше чем isize::MAX, просто исчерпает всю системную память. Однако для того, чтобы избежать проблем, когда кто-то будет интерпретировать массив длиной менее isize::MAX как байты, стандартная библиотека ограничивает выделение памяти isize::MAX байтами.

На всех 64-битных платформах, которые на данный момент поддерживает Rust, мы искусственно ограничены адресным пространством, гораздо меньшим чем все 64 бита (современные платформы x64 предлагают только 48-битную адресацию), поэтому, для начала, можем положиться на нехватку памяти. Однако на 32-битных платформах, особенно с расширенным адресным пространством (PAE x86 или x32), теоретически, возможно выделить больше чем isize::MAX байт в памяти.

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

Другой проблемой встают выделения нулевого размера. Тут два выделения, о которых надо волноваться: cap = 0 для всех T и cap > 0 для ТНР.

Эти случаи сложны, потому что придется обратиться к тому, что LLVM подразумевает под "распределением". Смысл распределения в LLVM существенно более абстрактный, чем то, как мы обычно понимаем его. Из-за того, что LLVM должен работать с разными семантиками языка и пользовательскими аллокаторами, она не может действительно глубоко понимать смысл распределения. Вместо этого, главной идеей, стоящей за распределением, является "не пересекаться с другими вещами". Вот поэтому выделенная память в куче, на стеке и глобальные переменные не пересекаются случайным образом. Да, это всё касается проверок совпадения ссылок. Таким образом, Rust может технически играть немного быстрее и свободнее с понятием распределения до тех пор, пока оно согласуется с LLVM.

Возвращаясь к случаю с выделением нулевого размера, есть пара мест, в которых мы хотим смещаться на 0 как следствие обобщенного кода. Встает тогда вопрос: согласовано ли так делать? Для ТНР мы пришли к выводу, что делать ограниченное GEP смещение на произвольное число элементов действительно согласовано. Это пустая операция во время исполнения, потому что каждый элемент не занимает места, и, нормальным считается предполагать, что бесконечное число ТНР расположены по адресу 0x01. Ни один аллокатор не выделит этот адрес, потому что они не будут выделять адрес 0x00 и, как правило, будут выделять память больше одного байта. Также, как правило, вся первая страница памяти в любом случае защищена от выделения в ней памяти (все 4k на многих платформах).

Однако, что насчет типов положительного размера? Они чуть посложнее. В принципе, вы можете поспорить, что смещение на 0 не дает информации LLVM: есть ли элемент до или после адреса, невозможно его распознать. Согласившись, что он может делать плохие вещи, защитимся от этого в явной форме.

Фух

Ок, отбросим всю эту чепуху, давайте наконец распределим память:

fn grow(&mut self) {
    // все здесь довольно деликатно, поэтому давайте скажем, что все небезопасно
    unsafe {
        // текущее API требует указания размера и выравнивания вручную.
        let align = mem::align_of::<T>();
        let elem_size = mem::size_of::<T>();

        let (new_cap, ptr) = if self.cap == 0 {
            let ptr = heap::allocate(elem_size, align);
            (1, ptr)
        } else {
            // подразумеваем, что `self.cap < isize::MAX`,
            // поэтому это не надо проверять.
            let new_cap = self.cap * 2;
            // аналогично, здесь не будет переполнения того, что мы раньше уже выделяли память такого размера
            let old_num_bytes = self.cap * elem_size;

            // проверяем, что новое выделение не превышает `isize::MAX` 
            // вообще, независимо от текущей ёмкости. Это объединяет проверки
            // `new_cap <= isize::MAX` и `new_num_bytes <= usize::MAX`, 
            // которые нам нужны. Хоть мы и теряем возможность выделить,
            // например, 2/3 из адресного пространства одному Vec из i16 на 32-битной платформе.
            // Увы, бедный Йорик - Я знал его, Горацио.
            assert!(old_num_bytes <= (::std::isize::MAX as usize) / 2,
                    "capacity overflow");

            let new_num_bytes = old_num_bytes * 2;
            let ptr = heap::reallocate(*self.ptr as *mut _,
                                        old_num_bytes,
                                        new_num_bytes,
                                        align);
            (new_cap, ptr)
        };

        // Если выделение или перераспределение возвращается с ошибкой, получим `null`
        if ptr.is_null() { oom(); }

        self.ptr = Unique::new(ptr as *mut _);
        self.cap = new_cap;
    }
}

Ничего особо сложного. Просто вычисления размеров и выравниваний и выполнения некоторых осторожных проверок умножения.