Ein wichtiges Thema bei der Programmierung ist die Nutzung und Verwaltung des Arbeitsspeichers für die Laufzeitdaten des Programms. Rust setzt mit der Programmiersprache ein Speicherkonzept um, das sich so zwar auch in anderen Programmiersprachen (z. B. C++) gut umsetzen lässt, aber dem die direkte Unterstützung im Compiler fehlt. Durch die Überprüfung durch den Compiler werden damit die Programme am Ende robuster gegen bestimmte Fehlerquellen. Allerdings erfordert diese Konzept eine gewisse Eingewöhnung und führt vor allem anfangs zu einigen Kopfschmerzen.

Zugriffsanforderungen von Rust

Wenn ein Objekt (der Speicher eines Datensatzes) über zwei Variablen veränderbar ist, kommt es zu zwei Fragen: 1) wann darf der Speicher für das Objekt freigegeben werden und 2) was ist das Ergebnis, wenn von beiden Stellen aus geschrieben wird. Da genau diese beiden Fragen in der Vergangenheit bei Programmen oft zu Problemen – 1) Speicherlecks, 2) inkonsistente/kaputte Daten – geführt haben, erlaubt Rust diesen Zustand nicht und fordert:

let a = File::open("…")?;
let b = a;
a.metadata()?;      // nicht erlaubt, da die Datei von b übernommen wurde

let mut a = 12;
let b = &mut a;
let c = &mut a;     // nicht erlaubt, da bereits b das Schreibrecht hat
*b = 4; *c = 5;

Diese Anforderungen sind sehr restriktiv und man muss sich oft mit der Frage herumschlagen, wie man die Speicherzugriffe organisiert, damit diese Anforderungen von Rust erfüllt sind – der unliebsame Kontrolleur im Compiler heißt Borrow-Checker.

let mut store = Vec::new();
let mut msg = "Text".to_string();
store.push(msg);
// Zugriff auf msg ab hier nicht mehr möglich, da es im Vector liegt
msg.push_str(" Text");
println!("Eintrag der Länge {} hinzugefügt", msg.len());

Oft genügt das Umordnen der Codezeilen oder eine Hilfsvariable, sodass die Anforderungen erfüllt sind:

let mut store = Vec::new();
let mut msg = "Text".to_string();
msg.push_str(" Text");
let len = msg.len();
store.push(msg);
println!("Eintrag der Länge {} hinzugefügt", len);

In anderen Programmiersprachen hat man diese Probleme nicht, denn dort wird entweder (wie im Fall von C) auf Risiko gesetzt und die Verantwortung dem Programmierer übertragen oder es gibt (wie im Fall von Java, C#, …) versteckte Kosten für die Absicherung. In C hat man alle Freiheiten und sehr oft sind die Zugriffe auch völlig in Ordnung, nur wird dies bei komplexen Programmen und Objekten mit mehreren Attributen immer schwieriger zu überblicken, weshalb man sehr diszipliniert seien muss, um mit der Freiheit verantwortungsvoll umzugehen. Da dieses leider oft nicht funktioniert, wurde in Programmiersprachen wie Java oder C# der Weg der (fast1) Vollabsicherung eingeschlagen und die Laufzeitumgebung der Programmiersprache kümmert sich um die Speicherverwaltung mit einem Garbage-Collector2.

  1. Um exklusiven Schreibzugriff/Sperren von Objekten muss man sich meist noch von Hand kümmern. ↩

  2. Für Rust gibt es auch Ansätze für einen Garbage-Collector, aber ich habe (Stand Jan. 2021) keine einsatzfähige Lösung gefunden. ↩

Der Weg des Risikos hat sich leider als nicht immer gangbarer Weg erwiesen und die Vollabsicherung hat auch ihre Nachteile (Garbage-Collectoren nutzen oft einen Global interpreter lock, der das komplette Programm in schwer kontrollierbaren Momenten zum Stillstand bringt.). Da Rust das Ziel verfolgt, die Eingangs angesprochenen Speicherprobleme zu lösen, wurden die oben genannten Regeln aufgestellt. Dennoch kommt es zu Situationen, die sich unter den gegeben Regeln nicht lösen lassen, weil zum Beispiel von mehreren Codestellen aus ein Schreibzugriff notwendig ist. Das einfachste Beispiel sind doppelt verkettete Listen, bei denen eine Referenz sowohl im Vorgänger- als auch im Nachfolgerelement gespeichert ist und irgendwie das Element veränderbar seien muss, mindestens um Vorgänger und Nachfolger setzen zu können.

Forderung der bekannten Speichergröße

Zu den Problemen von Speicherfreigabe und Schreibzugriff gesellt sich noch ein drittes Problem, dass aus der Organisationsweise des Speichers herrührt. Ein Programm arbeitet mit zwei Typen von Speichern: dem Stack und dem Heap. Der Heap verhält sich im Groben so, wie man es intuitiv erwartet: man reserviert sich einen Speicherbereich einer bestimmten Größe und kann dann über die Speicheradresse darauf zugreifen.

Der Stack ist strenger organisiert. Mit jedem Funktionsaufruf wird ein neues Segment (Schachtel/Frame) eröffnet, indem eine Funktion Daten ablegen kann. Dort werden unter anderem die lokalen Variablen (inkl. Argumente) einer Funktion gespeichert, von denen aus die Verweise auf den funktionsübergreifenden Heap gehen. Am Ende einer Funktion wird der sogenannte Stack-Pointer wieder um die Segmentgröße zurückgesetzt und die aufrufende Funktion macht weiter. Eine simple Speicherverwaltung, die für die vielen Funktionsaufrufe effizient funktioniert.

Jeder Funktion wird beim Aufruf mitgeteilt »ab der Stelle … kannst du deine Daten ablegen«, um den Aufwand für die Organisation der Heap-Reservierungen nicht mit jedem Funktionsaufruf zu haben. Allerdings muss dafür der Compiler für die Daten auf dem Stack deren Größe (beim Erstellen des Programms) kennen. Das Speichern eines Kommandozeilenarguments auf dem Stack ist zum Beispiel nicht möglich, weil dieses mit jedem Aufruf eine andere Größe haben kann. Stattdessen werden diese Daten auf dem Heap abgelegt und auf dem Stack liegt nur der Verweis (Referenz/Pointer) dorthin, weil dessen Größe wiederum bei der Übersetzung bekannt ist – Speicherverweise haben für jede Computerarchitektur eine fest definierte Größe von zum Beispiel 32 oder 64 Bit.

Das ist der Hintergrund, weshalb man keine Zeichenfolgen, Vektoren oder andere dynamische Daten auf dem Stack ablegen kann. Sobald von einem Objekt die Größe nicht bei der Erstellung des Programms bekannt ist, muss das Objekt auf den Heap und auf dem Stack landet der Verweis dorthin.

fn main() {
    let a = String::from("test")[1..3];
}

error[E0277]: the size for values of type `str` cannot be known at compilation time
  --> src/main.rs:11:9
   |
11 |     let a = String::from("test")[1..3];
   |         ^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `str`
   = note: all local variables must have a statically known size
   = help: unsized locals are gated as an unstable feature

Wo dies noch deutlicher auffällt, ist die Verwendung für Attribute von Datentypen:

struct Stt {
    x: [u8],
    y: u32,
}

error[E0277]: the size for values of type `[u8]` cannot be known at compilation time
  --> src/main.rs:11:8
   |
11 |     x: [u8],
   |        ^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `[u8]`
   = note: only the last field of a struct may have a dynamically sized type
   = help: change the field's type to have a statically known size

Wobei es die kleine Ausnahme gibt, dass das letzte Element keine feste Größe haben muss, womit aber der gesamte Datentyp keine zur Übersetzung bestimmbare Größe hat. Das Problem wird dann nur an den Ersteller eines Datenobjekts weitergegeben, aber manchmal ist dies hilfreich:

struct Stt {
    x: u32,
    y: str,
}

fn main() {
    let val = &Stt {
        x: 12,
        y: *"Test",
    };
}

error[E0277]: the size for values of type `str` cannot be known at compilation time
  --> src/main.rs:16:16
   |
16 |       let val = &Stt {
   |  ________________^
17 | |         x: 12,
18 | |         y: *"Test",
19 | |     };
   | |_____^ doesn't have a size known at compile-time
   |
   = help: within `Stt`, the trait `Sized` is not implemented for `str`
   = note: required because it appears within the type `Stt`
   = note: structs must have a statically known size to be initialized

Somit erklärt sich, weshalb man ein festes Feld (Array) [1, 2, 3] in einer lokalen Variablen ablegen kann, diesem aber keine Werte hinzufügen kann. Dafür benötigt man eine komplexere Struktur Vec<…>, die die eigentlichen Daten auf dem Heap ablegt. Analog: str und String oder Path und PathBuf. Die reinen Daten können nur als Referenz (&str, &[], &Path) verwendet werden, weil die Größe der Referenz wiederum bekannt ist.

Box<…>

Eine Referenz erfordert aber, dass es irgendwo den Speicher gibt, auf den verwiesen wird und dass sich jemand um die Freigabe des Speichers kümmert. Wenn eine Variable mit einer Referenz ihren Gültigkeitsbereich verlässt, wird nur die Referenz und nicht der referenzierte Speicher freigegeben. Hierum kümmern sich die komplexeren Datentypen wie Vec<…>, String und PathBuf.

Benötigt man aber gar nicht die Funktionalität dieser Datentypen, kann man auf Box<…> zurückgreifen. Eine Box ist wie eine Referenz, die sich aber um die Freigabe des referenzierten Speichers kümmert.

Dies ist vor allem bei den Trait-Objekten notwendig, da diese ja nur über ihre Funktionalität (das Trait) und nicht über den eigentlichen Datentyp (der das Trait implementiert) definiert sind. Daher kann der Compiler bei der Erstellung des Programms nicht sagen, wie viel Speicher benötigt wird. Aber über ein Box<dyn …> lässt sich ein solches Trait-Objekt speichern.

trait Trt {
    fn fun(&self);
}

struct Stt1(u8);
impl Trt for Stt1 {
    fn fun(&self) { /* … */ }
}

struct Stt2(u32);
impl Trt for Stt2 {
    fn fun(&self) { /* … */ }
}

let action : Box<dyn Trt> = if true { Box::new(Stt1(1)) } else { Box::new(Stt2(2)) };

action.fun();

Eine Anweisung wie let action = if … { Stt1(1) } else { Stt2(2) } ist nicht möglich, weil Stt1 8 Bits groß ist und Stt2 32 Bits und daher der Compiler keine Größe für action ermitteln kann.

Mehrfacher Lesezugriff mit Rc und Arc

Für einige Aufgaben ist es notwendig, dass der gleiche Speicherbereich (das selbe Objekt) von mehreren Codestellen genutzt werden kann. Als einfaches Beispiel kann eine Datenstruktur in einer Hashmap dienen, die ihren Schlüsselwert selbst enthält:

struct Stt {
    key: String,
}

let mut hash = HashMap::new();
let data = Stt { key: "…".to_string() };
hash.insert(data.key.clone(), data);

Das Problem hieran ist, dass der Speicher für den Schlüssel zwei Mal auf dem Heap vorkommt. Wenn es sich um unveränderliche Daten handelt, mag dies kein großes Problem darstellen. Aber bei veränderlichen Daten können keine zwei Objekte existieren. Somit ist man beim Problem, wann die Speicherfreigabe erfolgen darf, wenn es mehrere Variablen/Nutzer gibt. Eine klassische Lösung dafür ist die Referenzzählung (engl. reference counting), die in Rust mit den Typen Rc und Arc umgesetzt ist.

Bei Rc und Arc führt jeder Aufruf von clone() nicht zum Verdoppeln der Daten, sondern es wird nur ein interner Zähler von Rc bzw. Arc erhöht. Am Ende eines Gültigkeitsbereichs einer Variablen mit Rc bzw. Arc wird der Zähler wieder verringert und sollte er Null sein, wird der Speicher freigegeben. Eine einfache Methode, die auch keinen übermäßigen Mehraufwand mit sich bringt und die Speicherbereinigung kontinuierlich während des Programmlaufs erledigt und somit nicht die erwähnten Probleme eines Garbage-Collectors hat.

Da der Zugriff auf den internen Zähler mit bestimmten Prozessoranweisungen passieren muss, um einen doppelten Zugriff zu verhindern, gibt es zwei Varianten dieser Datenstruktur: Rc ist nur für einfache Programme ohne Parallelität, Arc (engl. atomic reference counting) ist für Parallelität mit mehreren Threads.

Da der Speicher, den Rc und Arc verwalten, auf dem Heap liegt, können diese mit Datentypen unbekannter Größe umgehen:

struct Stt {
    key: Rc<str>,
}

let mut hash = HashMap::new();
let data = Stt { key: "…".into() };
hash.insert(data.key.clone(), data);

Bei mehreren Variablen, die auf das gleiche Objekt zugreifen können, kommt es unweigerlich zum Konflikt bei Schreibzugriffen, weshalb Rc und Arc nur einen lesenden Zugriff auf die verwalteten Daten erlauben. Für die Koordination der Schreibzugriffe sind weitere Datentypen notwendig, die in den folgenden Abschnitten erläutert werden.

Die beiden Datentypen Rc und Arc haben nur sehr wenige eigene Methoden und implementieren das Trait Deref. Durch die automatische Dereferenzierung löst der Compiler also alle Methoden und Attribute des verwalteten Objekts für Rc bzw. Arc auf. Eine Variable mit einer der beiden Datentypen verhält sich also bis auf wenige Fälle wie eine Variable mit dem eigentlichen Datentyp. Da es doch einige nützliche Funktionen für die Datentypen gibt, sind diese als Funktionen und nicht als Methoden des Datentyps implementiert und man muss sie mit Rc::…(&var) aufrufen.

Schwache Referenzen für Zyklen

Einen Nachteil hat die Methode der Referenzzählung allerdings: Sie lässt sich leicht in die Irre führen. Schon das oben erwähnte Beispiel einer doppelt verketteten Liste führt zu dem Problem, dass Objekte – wenn auch über mehrere Schritte – auf sich selbst verweisen und Zyklen bilden. Bei zwei Elementen verweise das erste aufs zweite und das zweite aufs erste und somit ist für beide Elemente der Zähler größer Null, selbst wenn es keinen Verweis vom Stack auf eines der Elemente gibt, wenn sie also vom Programm praktisch nicht mehr erreichbar sind.

Also auch bei der Verwendung von Rc und Arc muss man darauf Acht geben, wie man die Verweise setzt, damit die Referenzzählungsmethode wirklich funktioniert und es zu keinen Speicherlecks kommt. Als Lösung bietet sich zum einen eine organisierte Freigabe der Objekte an, also dass man mit der Freigabe des Verweises auf dem Stack durch die Liste läuft und alle Rückwärtsverweise entfernt. Damit kann der Referenzzähler auf Null sinken und das System funktioniert.

Eine andere Möglichkeit sind schwache Referenzen (engl. weak references), die nicht in die Zählung eingehen, aber auf das Objekt zugreifen können, sofern es noch vorhanden ist. Mit Rc::downgrade (und analog Arc::downgrade; beides sind keine Methoden, sondern Funktionen der Datentypen) kann man zu einer normalen Referenz eine schwache Referenz zu einem Objekt erstellen. Diese schwache Referenz lässt sich wiederum mit .upgrade() in eine normale Referenz umwandeln, falls das Objekt noch existiert.

An diesem Punkt merkt man, welche Annehmlichkeiten einen Programmiersprachen bieten, die sich um die Speicherfreigabe kümmern. Allerdings hat man bei diesen nicht die Wahl, den Ballast der Methoden abzuschütteln. Mit Rust ist die Programmierung teilweise aufwändiger, aber man hat dafür die Freiheit über das Wie und Wann zu entscheiden.

Sperren für gemeinsame Schreibzugriffe

Die Frage des Schreibzugriffs auf Daten ohne mut stellt sich auch unabhängig von mehrfachen Variablen. Deshalb existieren die Datentypen für die Behandlung auch unabhängig von den Datentypen für den Mehrfachzugriff. Wenn zum Beispiel eine Methode einen internen Puffer für Ergebnisse pflegen will, versteckt sich also hinter einem Lesezugriff ein Schreibzugriff:

#[derive(Default)]
struct Stt {
    cache: std::sync::RwLock<Option<usize>>,
}

impl Stt {
    fn fun(&self) -> usize {
        if let Some(val) = *self.cache.read().unwrap() {
            return val;
        }

        let answer = 42; // diese Berechnung braucht einige Zeit

        *self.cache.write().unwrap() = Some(answer);

        answer
    }
}

let readonly_var = Stt::default();

assert_eq!(readonly_var.fun(), 42);

Auch von Datentypen für die Sperrung gibt es wieder zwei Varianten: Cell bzw. RefCell für einfache Programme ohne Parallelität und RwLock bzw. Mutex für Programme mit mehreren Threads.

Cell und RefCell für Single-Threaded

Der Datentyp Cell speichert in Daten nicht auf dem Heap, sondern innerhalb seines eigenen Speicherbereichs, weshalb er nur Typen unterstützt, die kopierbar sind (Copy implementieren). Alle Schreiboperationen sind mit einem Kopiervorgang verbunden, weshalb die Daten auch nicht zu groß seien sollte. Einen wirklichen Einsatzfall für Cell hatte ich noch nicht, aber folgendes Beispiel veranschaulicht die Nutzung. Ein Nutzen ist, dass der Einsatz keine Mehrkosten (Speicher oder Rechenzeit) verursache und damit Zugriffe möglich sind, die der Borrow-Checker für normale Referenzen verhindert.

let x = std::cell::Cell::new(1);
let y = &x;
let z = &x;
x.set(2);
y.set(3);
z.set(4);
assert_eq!(x.get(), 4);

Mit RefCell kann man alle Datentypen nutzen und nicht nur jene, die Copy unterstützen. Da die Zugriffe, insbesondere die Abschnitte des Zugriffs, genauer verfolgt werden müssen, um die Lese- oder Schreibsperre (am Ende) wieder zu entfernen, geben die Methoden borrow() und borrow_mut() spezielle Objekte zurück, die aufgrund der automatischen Dereferenzierung sich wie die eigentlichen Objekte verhalten, aber bei deren Auflösung die Sperre entfernen.

use std::cell::RefCell;

let readonly_var = RefCell::new(123);
{
    let mut num = readonly_var.borrow_mut();
    *num = 4;
    assert_eq!(num.rotate_left(1), 8);
    assert_eq!(*num, 4);
}

assert_eq!(*readonly_var.borrow(), 4);

Sollten sich Codeabschnitte mit Schreib- und Lesezugriff überlappen, beenden die Methoden borrow() und borrow_mut() das Programm mit einer Panic. Es gibt auch jeweils eine Methode mit try_, die einen entsprechenden Fehler zurückgeben kann, aber für solche Situationen bleibt nur die Umstrukturierung des Codes und die explizite Freigabe der Sperre.

Allerdings ist auch nicht immer einfach, die Feinheiten des Gültigkeitsbereichs von Variablen (in dem Falle der Sperre) zu erkennen:

use std::cell::RefCell;

let readonly_var = RefCell::new(Some("oh no!"));

match *readonly_var.borrow() {
    Some(ref val) if val.starts_with("oh") => {
        // folgender Block wird nur mit `cargo run --features do_panic` ausgeführt
        #[cfg(do_panic)]
        {
            // Hier kommt es zum Abbruch mit `panic` in `borrow_mut`
            *readonly_var.borrow_mut() = None;
        }
    }

    _ => ()
};

let guard = readonly_var.borrow();
match *guard {
    Some(ref val) if val.starts_with("oh") => {
        drop(guard);
        *readonly_var.borrow_mut() = None;
    }

    _ => ()
};

RwLock und Mutex für Multi-Threaded

Wenn mehrere Threads gleichzeitig ausgeführt werden, wird der Aufwand für die Synchronisation noch größer und erfordert daher andere Datentypen als für den einfach Fall mit nur einem Thread.

Der Datentyp Mutex (engl. mutable exclusive) setzt eine allgemeine Sperre auf die Daten um, sodass die Daten gelesen und geschrieben werden können, während man die Sperre hält. Mit RwLock wird zwischen Lese- und Schreibsperren unterschieden, da auf Daten sehr häufig lesend, aber nur selten schreibend zugegriffen wird. Lesezugriffe können mehrere gleichzeitig passieren, nur die Schreibzugriffe müssen (auch von den Lesezugriffen) isoliert werden. Durch diese Trennung muss nicht so häufig auf eine Sperre gewartet werden und die Gesamtausführungszeit sinkt.

Für den Zugriff auf die Sperre kann es wie im Single-Threaded-Fall zu einem Abbruch (Panic) des Threads kommen, sollte der Thread gleichzeitig eine Lese- und Schreibsperre nutzen. In solch einem Fall, wenn die Sperre nicht ordnungsgemäß freigegeben werden konnte, wird die Sperre als defekt gekennzeichnet und kann von keinem anderen Code mehr genutzt werden. Daher können Mutex.lock() und RwLock.read() bzw. RwLock.write() auch einen Fehler liefern. Um den Zustand kaputter Sperren zu verhindern, gibt es für die jeweiligen Methoden noch eine Methode mit try_, die einen Fehler liefert und nicht den Thread abbricht.

Dies verdeutlicht dem Aufwand, der bei einigen Programmiersprachen auto-magisch hinter der Bühne passiert … für alle Objekte, egal ob es notwendig ist oder nicht.

Asynchrone Sperren

Sollte bei der Anforderung einer Sperre für RwLock und Mutex die Sperrung nicht möglich sein, weil ein anderer Thread dies verhindert, wird der anfordernde Thread pausiert, bis die Sperrung möglich ist. Da Rust auch die asynchrone Programmierung (eine andere Form der Parallelität als Multi-Threading) unterstützt, gibt es in der async-std auch hierfür spezielle Datentypen für die Synchronisation.

Diese heißen ebenfalls RwLock und Mutex, weil sie die gleiche Funktionalität bieten und fast 1:1-Ersetzungen seid. Im Fall von Threads können die Sperr-Datentypen jedoch feststellen, wann ein Konflikt vorliegt und ein Warten keine Aussicht hat – der Fall der Panic. Bei der asynchronen Programmierung ist dies nicht möglich, weshalb es in solchen Konfliktfällen zu einem dauerhaften Warten (einem Dead-Lock) kommt das Programm wird untätig stehenbleiben. Da es also keine defekten Sperren geben kann, liefern Mutex.lock() und RwLock.read() bzw. RwLock.write() auch keinen Fehler.

use async_mutex::Mutex;

let mutex = Mutex::new(10);
let guard = mutex.lock().await;
assert_eq!(*guard, 10);


use async_std::sync::RwLock;

let lock = RwLock::new(1);

let mut n = lock.write().await;
*n = 2;

assert!(lock.try_read().is_none());

Kombination: verteilte Schreibzugriffe

Und am Ende kann man alles wie wild miteinander kombinieren, wobei nicht alle Kombinationen sinnvoll sind:

Zu Nutzung bieten sich eigentlich nur Rc<RefCell<…>>, Arc<RwLock<…>> und Arc<Mutex<…>>, weil sie jeweils eine Sperrung (für den Schreibzugriff) innerhalb einer Kapsel für die Vervielfältigung halten.

Aber bei komplexen Datentypen können auch feingranularere Sperren für die relevanten Attribute gesetzt werden, um unveränderliche Attribute, die vielleicht auch sehr häufig genutzt werden, von der Sperrung ausnehmen (Beispiel aus dem Rust-Buch):

struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

Dieser Datentyp ist für einen Knoten in einem Baum. Da der Wert eines Knotens sich (aus inhaltlichen Gründen) nicht ändern kann, genügt der einfache Lesezugriff auf dieses Attribut. Der Elternknoten und die Kindknoten eines Knotens müssen jedoch veränderbar sein, weshalb diese in einer RefCell gespeichert sind. Der Zugriff auf einen Knoten eines Baumes muss vom Eltern-, wie von den Kindknoten aus möglich sein. Da aber seltener auf den Elternknoten zugegriffen wird (und auch aus inhaltlichen Gründen), wurde für diesen Weak gewählt und Rc für die Kindknoten. Da die relevanten Teile des Knotens mit RefCell veränderbar sind, kann der gesamte Knoten nur-lesbar sein, weshalb Rc genügt.

Weitere Informationsquellen