Коллекции

В конечном итоге вы захотите использовать динамические структуры данных (также известные как коллекции) в вашей программе. 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.

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

// Реализация распределителя указателя смещения

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

use cortex_m::interrupt;

// Распределитель указателя смещения для *одноядерных* систем
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);

            // перемещаем начало к следующей границе выравнивания
            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 и обработка ошибок

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

Если вы исключительно используете коллекции 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)

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

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

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

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

alloc требует настройки глобального распределителя, в то время как heapless нет. Однако heapless требует, чтобы вы выбирали емкость каждойインスタциируемой коллекции.

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