Bei der Programmierung tritt früher oder später der Bedarf nach dynamischer Speicherverwaltung auf. Die Idee dabei ist einfach: Man fragt einen Allokator nach freiem Haldenspeicher, arbeitet mit diesem und gibt den nicht benötigten Speicher später wieder frei. Zum Arbeiten mit dem Speicher benutzt man eine Referenz auf den Speicher, einen sogenannten Zeiger. Ein Zeiger ist dabei eigentlich nicht viel mehr als eine Variable, die die Speicheradresse des zugewiesenen Speichers enthält.
So einfach wie diese Überlegung auch erscheinen mag, sie öffnet die Büchse der Pandora, wie wir in Retrospektive sagen können. Wenn der Computer ein Programm ausführt, muss man sich das vorstellen wie eine Zustandsmaschine, ein System das Schrittweise von einem gültigen Zustand in den nächsten übergeht. Es kann nun Operationen geben die einen Übergang in einen ungültigen Zustand erlauben. Das korrekte Arbeiten des Systems mag aber empfindlich davon abhängen, sich immer in gültigen Zuständen zu bewegen. Dieses korrekte Arbeiten nennt man Integrität des Systems. Verlust der Integrität bedeutet im besten Fall, dass das System nach kurzer Zeit abstürzt. Problematischer ist es, wenn bis zum Absturz eine lange Zeit vergeht, was mit einer Verschleierung der Ursache des Problems einhergehen kann. Im schlimmsten Fall findet ein Angreifer oder eine Schadsoftware eine Sicherheitslücke, die zur Kompromittierung des Systems führt.
Bei der Ausführung von Programmen gibt es auf der untersten Ebene eine grundlegende Form von Integrität, die Gewährleistung dieser wird als Speichersicherheit (memory safety) bezeichnet. Beim Arbeiten mit Zeigern gibt es eine Reihe von unerlaubten Operationen, welche die Speichersicherheit unterminieren:
Es ist nun so, dass die Situation schnell unübersichtlich werden kann. Im zugewiesenen Speicher lassen sich Strukturen oder Arrays von Strukturen speichern, die selbst wieder Zeiger auf weitere Strukturen enthalten können, diese können wieder Zeiger enthalten und so weiter. Es entstehen komplexe Datenstrukturen die man auch als gerichtete Graphen betrachten kann. Ein Zeiger ist dabei ein Pfeil von einem Knoten zu einem anderen. Diese Graphen können auch Zyklen enthalten, man spricht dann von zyklischen Datenstrukturen.
Es ist möglich das Typsystem so zu gestalten, dass es das sichere Arbeiten mit Zeigern erlaubt. Zur Einordnung klären wir zunächst ein paar allgemeine Grundbegriffe.
Ein Typsystem das in jedem Zustand nur solche Operationen zulässt, die die Integrität des Laufzeitsystems bewahren, heißt korrekt (sound) oder typsicher (type safe). Legt man das Verhalten eines Laufzeitsystems, das in einen ungültigen Zustand geraten ist, nicht weiter fest, spricht man von undefiniertem Verhalten (undefined behavior). Nämlich kann das genaue Verhalten ab einem ungültigen Zustand in der Implementation des Laufzeitsystems festgelegt sein. Dies ist dann ein technisches Detail des Laufzeitsystems, gehört bei diesem Ansatz also nicht mehr zur Spezifikation der Programmiersprache. Daher legt man das Verhalten als undefiniert fest, damit sich das Laufzeitsystem aussuchen kann, was dann zu tun ist.
Nur weil ein Typsystem korrekt ist, muss das nicht heißen, dass der Compiler dieses auch fehlerfrei umsetzt. Wie jede andere Software auch, kann ein Compiler alle möglichen Arten von Bugs enthalten. Ein Compiler der eine fehlerlose Typprüfung vornimmt und Maschinencode erzeugt, welcher der geforderten formalen Semantik entspricht, wird zertifizierend genannt. Die Programmierung eines zertifizierenden Compilers gilt als schwierig, man benötigt hierzu einen Theorembeweisassistent. Entsprechend wenige solcher Compiler sind verfügbar. Auch für Rust ist das Zukunftsmusik, denn der Rust-Compiler ist recht komplex, womit ein solches Unterfangen zur Mammut-Aufgabe wird. Man muss dabei beachten, dass ein entsprechender Beweis auch für das Compiler-Backend (den Code-Erzeuger) erbracht werden muss.
Übrigens erlauben auch Laufzeitprüfungen die Gewährleistung der Typsicherheit. Auf dieses Mittel greift man normalerweise dann zurück, wenn eine Prüfung zur Kompilierzeit zu schwierig wäre.
Out of bounds access verschwindet mit einer Laufzeitprüfung der Arraylänge. Hierzu wird ein aus Zeiger und Länge bestehendes Paar gespeichert, in Rust als Slice bezeichnet. Arrays fester Länge kennen ihre eigene Länge zur Kompilierzeit, haben also nur den Zeiger, was etwas effizienter ist. Auch in diesem Fall gibt es die Laufzeitprüfung der Arraylänge. Es gibt allerdings in vielen Fällen Formulierungen und Optimierungen mit denen man die Laufzeitprüfungen reduzieren kann oder ganz los wird.
Die Benutzung von Zeigern lässt sich so einschränken, dass die Speichersicherheit unverletzt bleibt. Out of bounds access wurde schon abgearbeitet. Es verbleiben noch uninitialisierte Variablen und Use after free bzw. Aliasing.
Uninitialisierte Variablen verschwinden mit der Festlegung, dass jede Variable vor dem Zugriff auf sie voll initialisiert sein muss indem der Variable ein Wert zugewiesen wird. Dies kann der Compiler durch Kontrollflussanalyse schon zur Kompilierzeit prüfen.
Eine genaue Betrachtung von Use after free führt zu der folgenden Beobachtung. Es entsteht durch das Kopieren von Zeigern. Gäbe es immer nur einen gültigen Zeiger auf die Daten, würden die Daten also immer nur einen einzigen Besitzer haben, könnte man über diesen bedenkenlos auf die Daten zugreifen.
Unsere Überlegungen manifestieren sich im folgenden Formalismus:
p = q
führt dazu, dass q ungültig wird, sonst gäbe es zwei
Besitzer. Es handelt sich hierbei also anschaulich formuliert
um einen Wechsel des Besitzers. Ein ungültig gewordene Variable
ist gleichbedeutend mit einer uninitialisierten Variable.
Dieser Formalismus wird affine Logik genannt. Ein Typsystem, das diese umsetzt, nennt man affin.
Die Beschränkung auf Move-Semantik ist ziemlich einschränkend. Viele Funktionen bleiben nicht Besitzer eines Wertes, sie borgen sich den Wert nur zum Lesen oder zur Manipulation aus. In einigen Fällen könnte man das zwar so formulieren, dass der Wert wieder als Rückgabewert auftaucht anstatt zu verschwinden, jedoch ist dies recht umständlich.
Stattdessen wollen wir das Ausborgen von Werten erlauben, indem ein Zeiger zum Wert an die Funktion übergeben wird. Wir sprechen von einer Leihgabe, engl. borrow. Dies wirft Probleme auf. Betrachten wir das folgende Programm.
fn main() {
let mut v: Vec<u32> = vec![0, 0, 0, 0];
let p: &u32 = &v[0];
v.push(0);
println!("{}", *p);
}
Dieses Programm erzeugt als erstes ein dynamisches Feld
v. Als nächstes lassen wir einen Zeiger p
auf das erste Element des internen Puffers von v zeigen.
Damit gibt es nun zwei Zeiger auf denselben Puffer, einmal den
internen Zeiger von v und einmal p. Dies
bezeichnet man als Aliasing. Die nächste Operation
v.push(0) kann nun dazu führen, dass der interne Puffer
realloziert wird. Gehen wir davon aus, dies geschieht.
Hierdurch kommt es zu einer Zeiger-Invalidierung von p,
womit p nunmehr ein hängender Zeiger ist. Die Benutzung
*p in der nächsten Zeile ist dann undefiniertes
Verhalten in Form von Use after free, weil der ursprüngliche
Speicherbereich bereits an den Allokator freigegeben wurde. Dies stellt
einen Bug dar, der im schlimmsten Fall eine Sicherheitslücke
bedeuten kann.
Zwei kritische Beobachtungen:
Manchmal möchte man die Referenz auf einen Wert haben, welcher in einem bestimmten lexikalischen Bereich erzeugt wurde. Betrachten wir das folgende Programm.
enum Object {Int(i32), String(String)}
fn print_object(x: &Object) {
match x {
Object::Int(x) => println!("{}", x),
Object::String(x) => println!("{}", &x)
}
}
fn main() {
print_object(&Object::Int(12));
print_object(&Object::String("Tee".to_string()));
}
Angenommen, aus unerfindlichen Gründen ist nun eine Formulierung
gesucht, bei welcher der Aufruf von println nur noch
einmal vorkommt. Die naive Überlegung dazu ist:
fn print_object(x: &Object) {
let s: &str = match x {
Object::Int(x) => &x.to_string(),
Object::String(x) => &x
};
println!("{}", s);
}
Das würgt der Compiler jedoch ab, weil die Lebenszeit der mit
x.to_string() erzeugten Zeichenkette auf ihren
lexikalischen Bereich beschränkt ist. Um ein wesentliches Problem
handelt es sich hierbei aber nicht. Einführung einer zusätzlichen
Variable sorgt für die gewünschte Verlängerung der Lebenszeit.
fn print_object(x: &Object) {
let ts;
let s: &str = match x {
Object::Int(x) => {ts = x.to_string(); &ts},
Object::String(x) => &x
};
println!("{}", s);
}
Man würde nun auch gerne haben, dass die in s
gespeicherte Referenz die Funktion verlassen kann. Hierzu kann der
Smart-Pointer-Typ Cow herangezogen werden.
use std::borrow::Cow;
enum Object {Int(i32), String(String)}
impl Object {
fn as_str(&self) -> Cow<str> {
match self {
Object::Int(x) => Cow::Owned(x.to_string()),
Object::String(x) => Cow::Borrowed(&x)
}
}
}
fn main() {
let x = Object::Int(12);
let y = Object::String("Tee".to_string());
println!("{}", x.as_str());
println!("{}", y.as_str());
}
Explizit ausgeschrieben besitzt as_str die Signatur
fn as_str<'a>(&'a self) -> Cow<'a, str>.
Ein anderes Beispiel für die Notwendigkeit von Hilfsvariablen sind Trait-Objekte. Gerne schreiben würde man z. B. folgendes:
fn f1() -> impl Fn(i32)->i32 {|x| x + 1}
fn f2() -> impl Fn(i32)->i32 {|x| 2*x}
fn phi(n: i32) -> i32 {
let f = if n == 1 {f1()} else {f2()};
f(10)
}
fn main() {
println!("{}, {}", phi(1), phi(2));
}
Das soll bedeuten, in einer Fallunterscheidung wird eine
der beiden (dynamisch erzeugten) Funktionen f(x):=x+1 und
f(x):=2*x gewählt. Nun verhält es sich so, dass die Typen
von f1() und f2() unterschiedlich sind. Was
die Typsignatur jetzt genau bedeutet, ist nicht so wichtig. Beide Typen
implementieren aber denselben Trait. Um die beiden Typen gleich zu
bekommen, müssen diese in Trait-Objekte umgewandelt werden. Man würde
also gerne schreiben:
let f: &dyn Fn(i32) -> i32 = if n == 1 {&f1()} else {&f2()};
Das klappt wegen der Lebenszeitproblematik nicht. Wir könnten das durch Boxen umgehen, das ist möglich:
let f: Box<dyn Fn(i32) -> i32> =
if n == 1 {Box::new(f1())} else {Box::new(f2())};
Allerdings führt das zu unnötigen Speicherallokationen. Die Lösung des Problems liegt wieder in der Benutzung von Hilfsvariablen:
let (tf1, tf2);
let f: &dyn Fn(i32) -> i32 =
if n == 1 {tf1 = f1(); &tf1} else {tf2 = f2(); &tf2};