Sammlungen (Collections)
Irgendwann wirst du in deinem Programm dynamische Datenstrukturen (auch bekannt als Collections) verwenden wollen. Die Standardbibliothek (std) stellt eine Reihe gängiger Collections bereit: Vec, String, HashMap usw. Alle in std implementierten Collections nutzen einen globalen dynamischen Speicherverwalter (den sogenannten Heap).
Da core definitionsgemäß frei von Speicherzuweisungen ist, stehen diese Implementierungen dort nicht zur Verfügung; sie sind jedoch im alloc-Crate zu finden, das mit dem Compiler ausgeliefert wird.
Wenn Sie Sammlungen benötigen, ist eine auf dem Heap alloziierte Implementierung nicht Ihre einzige Option. Sie können auch Sammlungen mit fester Kapazität verwenden; eine solche Implementierung findet sich im heapless-Crate.
In diesem Abschnitt werden wir diese beiden Implementierungen untersuchen und vergleichen.
Verwendung von alloc
Die alloc-Crate ist in der Standard-Rust-Distribution enthalten. Um das Crate zu importieren, können Sie es direkt per use einbinden, ohne es als Abhängigkeit in Ihrer Cargo.toml-Datei zu deklarieren.
#![feature(alloc)]
extern crate alloc;
use alloc::vec::Vec;Um eine beliebige Collection nutzen zu können, müssen Sie zunächst das Attribut global_allocator verwenden, um den globalen Allocator zu deklarieren, den Ihr Programm einsetzen soll. Der gewählte Allocator muss zwingend das Trait GlobalAlloc implementieren.
Der Vollständigkeit halber und um diesen Abschnitt so in sich abgeschlossen wie möglich zu halten, implementieren wir einen einfachen Bump-Pointer-Allokator und verwenden diesen als globalen Allokator. Wir empfehlen Ihnen jedoch dringend, in Ihrem Programm stattdessen einen praxiserprobten Allokator von crates.io zu verwenden.
// Implementierung eines Bump-Pointer-Allocators
use core::alloc::{GlobalAlloc, Layout};
use core::cell::UnsafeCell;
use core::ptr;
use cortex_m::interrupt;
// Bump-Pointer-Allocator fuer Systeme mit *einem* Rechenkern
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` ist ein kritischer Abschnitt, der die sichere
// Verwendung unseres Allocators aus Interrupts heraus ermoeglicht.
interrupt::free(|_| {
let head = self.head.get();
let size = layout.size();
let align = layout.align();
let align_mask = !(align - 1);
// Verschiebe den Startpunkt zur naechsten Ausrichtungsgrenze.
let start = (*head + align - 1) & align_mask;
if start + size > self.end {
// ein Nullzeiger signalisiert einen „Out of Memory“-Zustand
ptr::null_mut()
} else {
*head = start + size;
start as *mut u8
}
})
}
unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
// Dieser Allokator gibt niemals Speicher frei.
}
}
// Deklaration des globalen Speicher-Allocators
// HINWEIS: Der Benutzer muss sicherstellen, dass der Speicherbereich
// `[0x2000_0100, 0x2000_0200]` nicht von anderen Teilen des Programms
// verwendet wird.
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
head: UnsafeCell::new(0x2000_0100),
end: 0x2000_0200,
};
Neben der Auswahl eines globalen Allocators muss der Benutzer auch festlegen, wie mit „Out of Memory“ (OOM)-Fehlern umgegangen wird; hierfür wird das instabile Attribut alloc_error_handler verwendet.
#![feature(alloc_error_handler)]
use cortex_m::asm;
#[alloc_error_handler]
fn on_oom(_layout: Layout) -> ! {
asm::bkpt();
loop {}
}Sobald alles vorhanden ist, kann der Benutzer endlich die Sammlungen in „alloc“ verwenden.
#[entry]
fn main() -> ! {
let mut xs = Vec::new();
xs.push(42);
assert!(xs.pop(), Some(42));
loop {
// ..
}
}Wenn Sie die Sammlungen aus dem std-Crate bereits verwendet haben, werden Ihnen diese vertraut vorkommen, da es sich um exakt dieselbe Implementierung handelt.
Verwendung von heapless
heapless erfordert keine Einrichtung, da seine Datenstrukturen nicht von einem globalen Speicher-Allocator abhängen. Binde die Datenstrukturen einfach per use ein und instanziiere sie:
// heapless version: 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 {}
}Sie werden zwei Unterschiede zwischen diesen Sammlungen und denen in alloc feststellen.
Erstens muss die Kapazität der Sammlung im Voraus deklariert werden. heapless-Sammlungen werden nie neu allokiert und haben eine feste Kapazität; diese Kapazität ist Teil der Typsignatur der Sammlung. In diesem Fall haben wir deklariert, dass xs eine Kapazität von 8 Elementen hat, d. h. der Vektor kann maximal 8 Elemente aufnehmen. Dies wird durch das u8 (siehe typenum) in der Typsignatur angezeigt.
Zweitens geben die Methode push sowie viele weitere Methoden ein Result zurück. Da heapless-Datenstrukturen über eine feste Kapazität verfügen, können alle Operationen, die Elemente in die Struktur einfügen, potenziell fehlschlagen. Die API trägt diesem Umstand Rechnung, indem sie ein Result liefert, das anzeigt, ob die Operation erfolgreich war oder nicht. Im Gegensatz dazu passen alloc-Datenstrukturen ihre Kapazität durch eine erneute Speicherzuweisung auf dem Heap an.
Seit Version v0.4.x speichern alle heapless-Datenstrukturen ihre Elemente direkt „inline“. Das bedeutet, dass eine Operation wie let x = heapless::Vec::new(); die Datenstruktur auf dem Stack anlegt; es ist jedoch auch möglich, sie in einer static-Variablen oder sogar auf dem Heap (Box<Vec<_, _>>) zu speichern.
Abwägungen
Berücksichtigen Sie diese Punkte, wenn Sie zwischen auf dem Heap alloziierten, verschiebbaren Sammlungen und Sammlungen mit fester Kapazität wählen.
„Out of Memory“ und Fehlerbehandlung
Bei Heap-Allokationen ist ein „Out of Memory“ (OOM) – also ein Speichermangel – immer möglich; er kann überall dort auftreten, wo eine Collection wachsen muss: So können beispielsweise alle Aufrufe von alloc::Vec.push potenziell zu einer OOM-Situation führen. Folglich können manche Operationen implizit fehlschlagen. Einige alloc-Collections bieten try_reserve-Methoden an, mit denen sich potenzielle OOM-Situationen beim Vergrößern der Collection überprüfen lassen; man muss diese Methoden jedoch aktiv einsetzen.
Wenn man ausschließlich heapless-Collections verwendet und keinen Speicher-Allocator für andere Zwecke nutzt, ist eine OOM-Situation ausgeschlossen. Stattdessen muss man im Einzelfall damit umgehen, wenn die Kapazität einer Collection erschöpft ist. Das bedeutet, man muss alle Result-Werte behandeln, die von Methoden wie Vec.push zurückgegeben werden.
Fehler durch Speichermangel (OOM) können schwieriger zu debuggen sein als etwa das Aufrufen von unwrap auf allen Result-Werten von heapless::Vec.push, da die Stelle, an der der Fehler sichtbar wird, nicht unbedingt mit der Ursache des Problems übereinstimmen muss. So kann beispielsweise selbst vec.reserve(1) ein OOM auslösen, wenn der Allocator nahezu erschöpft ist, weil eine andere Collection Speicher verloren hat (Speicherlecks sind auch in „Safe Rust“ möglich).
Speichernutzung
Die Einschätzung des Speicherverbrauchs von auf dem Heap allozierten Collections ist schwierig, da sich die Kapazität langlebiger Collections zur Laufzeit ändern kann. Manche Operationen führen möglicherweise zu einer impliziten Neuzuweisung des Speichers, wodurch der Speicherbedarf steigt; andere Collections bieten Methoden wie shrink_to_fit an, die den genutzten Speicher potenziell verringern können – wobei letztlich der Allocator entscheidet, ob die Speicherzuweisung tatsächlich reduziert wird. Zudem muss der Allocator unter Umständen mit Speicherfragmentierung umgehen, was den scheinbaren Speicherverbrauch erhöhen kann.
Verwendet man hingegen ausschließlich Collections mit fester Kapazität, legt die meisten davon in static-Variablen ab und legt eine maximale Größe für den Aufruf-Stack (Call Stack) fest, so erkennt der Linker, wenn mehr Speicher beansprucht wird, als physisch verfügbar ist.
Darüber hinaus werden auf dem Stack alloziierte Collections mit fester Kapazität durch das Flag -Z emit-stack-sizes erfasst; das bedeutet, dass Werkzeuge zur Analyse der Stack-Nutzung (wie stack-sizes) diese in ihre Auswertung einbeziehen.
Sammlungen mit fester Kapazität können jedoch nicht verkleinert werden, was zu niedrigeren Auslastungsgraden (dem Verhältnis zwischen der Größe der Sammlung und ihrer Kapazität) führen kann, als sie bei Sammlungen mit veränderbarer Kapazität möglich sind.
Maximale Ausführungszeit (WCET)
Wenn Sie zeitkritische oder Echtzeitanwendungen entwickeln, ist Ihnen die Worst-Case-Ausführungszeit (WCET) der verschiedenen Programmteile wahrscheinlich sehr wichtig.
Da alloc-Collections Speicher neu allokieren können, umfasst die WCET von Operationen, die die Collection vergrößern, auch die Zeit für die Neuallokation. Diese hängt wiederum von der Laufzeitkapazität der Collection ab. Daher ist es schwierig, die WCET beispielsweise der Operation alloc::Vec.push zu bestimmen, da sie sowohl vom verwendeten Allokator als auch von dessen Laufzeitkapazität abhängt.
Collections mit fester Kapazität hingegen allokieren nie Speicher neu, sodass alle Operationen eine vorhersehbare Ausführungszeit haben. Beispielsweise wird heapless::Vec.push in konstanter Zeit ausgeführt.
Benutzerfreundlichkeit
Für alloc muss ein globaler Allocator eingerichtet werden, für heapless hingegen nicht. Allerdings erfordert heapless, dass man bei der Instanziierung jeder Collection deren Kapazität festlegt.
Die alloc-API dürfte so gut wie jedem Rust-Entwickler vertraut sein. Die heapless-API orientiert sich zwar eng an der alloc-API, unterscheidet sich jedoch aufgrund der expliziten Fehlerbehandlung – manche Entwickler empfinden diese explizite Fehlerbehandlung womöglich als übertrieben oder zu umständlich.