Коллекции

Рано или поздно вам понадобятся динамические структуры данных (они же коллекции) в вашей программе. std предоставляет набор распространённых коллекций: Vec, String, HashMap и т. д. Все коллекции, реализованные в std, используют глобальный аллокатор динамической памяти (он же куча).

Поскольку core по определению не использует выделение памяти, этих реализаций там нет, но их можно найти в крейте alloc, который поставляется вместе с компилятором.

Если вам нужны коллекции, реализация с выделением в куче — не единственный вариант. Вы также можете использовать коллекции фиксированной ёмкости; одна такая реализация есть в крейте heapless.

В этом разделе мы рассмотрим и сравним эти две реализации.

Использование alloc

Крейт alloc поставляется со стандартным дистрибутивом Rust. Чтобы подключить крейт, можно напрямую использовать use, не объявляя его как зависимость в файле Cargo.toml.

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

Чтобы использовать любую коллекцию, сначала нужно с помощью атрибута global_allocator объявить глобальный аллокатор, который будет использовать ваша программа. Выбранный аллокатор должен реализовывать трейт GlobalAlloc.

Для полноты и чтобы сделать этот раздел максимально самодостаточным, мы реализуем простой аллокатор bump pointer и используем его в качестве глобального аллокатора. Однако мы настоятельно советуем использовать в вашей программе проверенный временем аллокатор с crates.io вместо него.

// Реализация аллокатора bump pointer

use core::alloc::{GlobalAlloc, Layout};
use core::cell::UnsafeCell;
use core::ptr;

use cortex_m::interrupt;

// Аллокатор bump pointer для *однопроцессорных* систем
struct BumpPointerAlloc {
    head: UnsafeCell<usize>,
    end: usize,
}

unsafe impl Sync for BumpPointerAlloc {}

unsafe impl GlobalAlloc for BumpPointerAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // `interrupt::free` — это критическая секция, которая делает наш аллокатор безопасным
        // для использования из прерываний
        interrupt::free(|_| {
            let head = self.head.get();
            let size = layout.size();
            let align = layout.align();
            let align_mask = !(align - 1);

            // сдвигаем start до следующей границы выравнивания
            let start = (*head + align - 1) & align_mask;

            if start + size > self.end {
                // нулевой указатель сигнализирует об ошибке нехватки памяти (Out Of Memory)
                ptr::null_mut()
            } else {
                *head = start + size;
                start as *mut u8
            }
        })
    }

    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
        // этот аллокатор никогда не освобождает память
    }
}

// Объявление глобального аллокатора памяти
// ВАЖНО: пользователь должен гарантировать, что область памяти `[0x2000_0100, 0x2000_0200]`
// не используется другими частями программы
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
    head: UnsafeCell::new(0x2000_0100),
    end: 0x2000_0200,
};

Помимо выбора глобального аллокатора, пользователь также должен определить, как обрабатываются ошибки нехватки памяти (Out Of Memory, OOM), с помощью нестабильного атрибута alloc_error_handler.

#![feature(alloc_error_handler)]

use cortex_m::asm;

#[alloc_error_handler]
fn on_oom(_layout: Layout) -> ! {
    asm::bkpt();

    loop {}
}

Когда всё это настроено, пользователь наконец может использовать коллекции из alloc.

#[entry]
fn main() -> ! {
    let mut xs = Vec::new();

    xs.push(42);
    assert!(xs.pop(), Some(42));

    loop {
        // ..
    }
}

Если вы использовали коллекции из крейта std, они покажутся знакомыми, так как реализация точно такая же.

Использование heapless

heapless не требует никакой настройки, так как его коллекции не зависят от глобального аллокатора памяти. Просто используйте use для его коллекций и создавайте их экземпляры:

// версия heapless: v0.4.x
use heapless::Vec;
use heapless::consts::*;

#[entry]
fn main() -> ! {
    let mut xs: Vec<_, U8> = Vec::new();

    xs.push(42).unwrap();
    assert_eq!(xs.pop(), Some(42));
    loop {}
}

Вы заметите два отличия этих коллекций от коллекций из alloc.

Во-первых, вам нужно заранее объявить ёмкость коллекции. Коллекции heapless никогда не перераспределяются и имеют фиксированную ёмкость; эта ёмкость является частью сигнатуры типа коллекции. В данном случае мы объявили, что у xs ёмкость 8 элементов, то есть вектор может содержать не более 8 элементов. Это обозначено U8 (см. typenum) в сигнатуре типа.

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

Начиная с версии v0.4.x все коллекции heapless хранят все свои элементы inline. Это означает, что такая операция, как let x = heapless::Vec::new();, разместит коллекцию в стеке, но также возможно разместить коллекцию в переменной static или даже в куче (Box<Vec<_, _>>).

Компромиссы

Имейте это в виду при выборе между коллекциями с выделением в куче, буфер которых может перемещаться при росте, и коллекциями фиксированной ёмкости.

Нехватка памяти и обработка ошибок

При выделении в куче нехватка памяти (Out Of Memory) — это всегда возможность, и она может возникнуть в любом месте, где коллекции могут расти: например, любой вызов alloc::Vec.push потенциально может привести к OOM. Таким образом, некоторые операции могут неявно завершиться неудачей. Некоторые коллекции alloc предоставляют методы try_reserve, которые позволяют проверить возможные OOM при росте коллекции, но для этого нужно проявлять инициативу и использовать их.

Если вы исключительно используете коллекции heapless и не применяете аллокатор памяти ни для чего другого, то OOM-ситуация невозможна. Вместо этого вам придётся обрабатывать случаи, когда коллекции исчерпывают свою ёмкость, в каждом конкретном месте. То есть вам придётся обработать все Result, возвращаемые методами вроде Vec.push.

Ошибки OOM бывает сложнее отлаживать, чем, например, вызов unwrap для всех Result, возвращаемых heapless::Vec.push, потому что наблюдаемое место сбоя может не совпадать с местом, где находится причина проблемы. Например, даже vec.reserve(1) может вызвать OOM, если аллокатор почти исчерпан, потому что какая-то другая коллекция утекла памятью (утечки памяти возможны в безопасном Rust).

Использование памяти

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

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

Кроме того, коллекции фиксированной ёмкости, выделенные в стеке, будут учтены флагом -Z emit-stack-sizes, а значит, инструменты, которые анализируют использование стека (например, stack-sizes), будут включать их в анализ.

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

Наихудшее время выполнения (WCET)

Если вы создаёте чувствительные ко времени или приложения жёсткого реального времени, то вас, возможно, очень волнует наихудшее время выполнения (worst case execution time, WCET) разных частей вашей программы.

Коллекции alloc могут перераспределяться, поэтому WCET операций, которые могут увеличивать коллекцию, также будет включать время, которое занимает перераспределение. Оно, в свою очередь, зависит от времени выполнения ёмкости коллекции. Из-за этого трудно определить WCET, например, операции alloc::Vec.push, так как она зависит и от используемого аллокатора, и от его ёмкости во время выполнения.

С другой стороны, коллекции фиксированной ёмкости никогда не перераспределяются, поэтому все операции имеют предсказуемое время выполнения. Например, heapless::Vec.push выполняется за константное время.

Простота использования

alloc требует настройки глобального аллокатора, тогда как heapless — нет. Однако heapless требует, чтобы вы выбрали ёмкость каждой создаваемой коллекции.

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