Dieses Kapitel beschäftigt sich mit der Darstellung von Werten im Speicher. Der Wert eines Typs ist zunächst ein gedankliches Konzept, so wie das bei einem mathematischen Objekt ist. Ein mathematisches Objekt wie eine Zahl befindet sich in einem platonischen Universum, so nennt man den Raum aller erdenklichen Objekte. Erst die Darstellung der Zahl durch ein Zahlensystem ermöglicht ihre physische Erfassung. Wir schreiben ja immer nur die Ziffern einer Zahl auf, die Zahl selbst haben wir nie gesehen. Je nach Zahlensystem nimmt die Darstellung der Zahl dabei eine andere Gestalt an.
Auch zur physischen Speicherung eines Wertes bedarf es offensichtlich einer Darstellung. Werte werden in Computern als Binärzahlen abgelegt, soviel ist klar. Bei der Darstellung im Speicher gibt es allerdings noch ein wenig mehr zu beachten. Das fängt schon damit an, dass die Bits immer zu Gruppen aus acht, den Bytes zusammengefasst sind. Die Kenntnis der Darstellung zerbricht im Nebeneffekt die Abstraktion zum benutzten Computer.
Jedes im Arbeitsspeicher abgelegte Datum besitzt eine Adresse. Enthält ein Zeiger diese Adresse als Wert, bekommt das Programm durch Dereferenzierung des Zeigers den Zugriff auf das Datum. Eine Adresse ist die Anzahl an Bytes, um die der Zeiger vom Ursprung des Speichers aus verschoben wurde.
Es verhält sich nun für gewöhnlich aber so, dass ein Datum nicht jede mögliche Adresse besitzen kann. Computer arbeiten intern mit Datenworten, kurz Worten. Typische Wortgrößen moderner Architekturen sind 32 Bit und 64 Bit. Für den Computer sind die Elemente des Speichers nicht die Bytes, sondern die Worte, der Computer kann sie effizient laden und speichern. Infolge ist es günstig, wenn ein Datum im Speicher so ausgerichtet ist, dass es möglichst wenige Worte überspannt, denn andernfalls würde das Laden und Speichern eine erhöhte Anzahl an Operationen erfordern.
Betrachten wir eine Architektur mit der Wortgröße 32.
Jede Zahl vom Typ u32 ist in dieser Architektur gemäß des
Gesagten so im Speicher ausgerichtet, dass ihre Adresse ein
ganzzahliges Vielfaches von vier ist. Das heißt, die
Zusicherung in
let x: u32 = 0; let address = &x as *const u32 as usize; assert!(address % 4 == 0);
ist immer erfüllt, und für
let a: [u32; 2] = [1, 2]; let address = &a[0] as *const u32 as usize; assert!(address % 4 == 0);
gilt dasselbe. Schärfer setzt uns die Standardbibliothek unmissverständlich über
std::mem::align_of::<u32>() == 4
in Kenntnis.
Die Ausrichtung betrifft im weiteren Fortgang gleichermaßen die Einträge von Tupeln und Strukturen. Betrachten wir dazu:
struct S {i: u32, b: u8}
assert_eq!(4, std::mem::align_of::<S>());
assert_eq!(8, std::mem::size_of::<S>());
Die Ausrichtung der Struktur ist gleich der des Eintrags
i. Das erscheint logisch, denn wäre dieser Betrag geringer,
wäre sie dergestalt im Speicher verschiebbar, dass der Eintrag
i unausgerichtet sein würde.
Aber weshalb beträgt die Größe der Struktur acht Bytes und nicht fünf? Das liegt daran, dass zur Größe der Struktur Padding hinzukommt, so dass jedes Element einer direkten Abfolge dieser Strukturen im Speicher ausgerichtet ist.
Unter Padding versteht man das Auffüllen einer Datenstruktur mit ungenutztem Freiraum, so dass alle ihre Bestandteile im Speicher ausgerichtet sind. Beispielsweise erzeugt
#[repr(C)]
struct S {b1: u8, i: u32, b2: u8}
println!("{}/{}", align_of::<S>(), size_of::<S>());
die Ausgabe 4/12. Die Größe der Struktur bläht
sich von sechs auf zwölf auf, weil einmal für b1
drei Bytes und ebenso für b2 drei Bytes an Padding
eingefügt werden.
Entfernen wir das Attribut repr(C), dann ist es
dem Compiler erlaubt, die Reihenfolge der Einträge umzuordnen,
so dass die Struktur die Gestalt
#[repr(C)]
struct S {b1: u8, b2: u8, i: u32}
oder
#[repr(C)]
struct S {i: u32, b1: u8, b2: u8}
erhält und damit die Größe acht bekommt. Weil b1
und b2 nämlich keiner Ausrichtung bedürfen, dürfen
sie direkt hintereinander abgelegt werden, womit zwei Bytes
Padding genügen.
Es ist auch machbar, das Padding und infolge die Ausrichtung
in Strukturen zu unterlassen. Man spricht dann von einer
gepackten Struktur. In der Konsequenz sind Lese- und
Schreibvorgänge allerdings, so wissen wir, ineffizient. Gepackte
Strukturen würden deshalb am ehesten bei Schnittstellen und
Dateiformaten zur Anwendung kommen. Solche Darstellungen werden vom
Compiler rustc mit dem Attribut repr(packed)
unterstützt, ihr Gebrauch ist allerdings nicht empfohlen.
Wie gesagt schließt die Größe eines Typs Padding mit ein,
womit ein Element ebenfalls ausgerichtet ist, wenn es direkt hinter
ein ausgerichtetes Element gesetzt wird. Die Größe des Typs stimmt
mit der Zahl überein, um die ein Bytezeiger verschoben werden muss,
damit er auf das nächste Element zeigt. Für jeden Typ T
und jede Länge N ist die Gleichung
size_of::<[T; N]> == N*size_of::<T>()
erfüllt.
Bei vielen Typen belegt die Darstellung mehr Bits als zur Kodierung der Information notwendig wäre. Allgemeiner betrachtet erlauben die Bitfolgen einen größeren Wertebereich als notwendig. Dafür gibt es unterschiedliche Ursachen:
Solche ungenutzten Werte oder Wertebereiche werden Nischen genannt. Man kann sie zur Kodierung weiterer Information ausnutzen, womit sich die Speichergröße zusammengesetzter Typen verringern lässt.
Betrachten wir als einfaches Beispiel den Typ
Option<u32>, wobei für
Result<u32, ()> eine gleichartige Überlegung
gilt. Vermindern wir den Wertebereich um eins, kann der Wert
u32::MAX zur Darstellung von None
genutzt werden. Das reduziert die Speichergröße von acht auf
vier Bytes! Nicht schlecht.
Bei einigen Typen ist der Wert null verboten. Hier stellt die
Standardbibliothek Typen wie NonZeroU32 und
NonZeroU64 zur Verfügung. Bei
Option<
wird NonZeroU32>None als null dargestellt. Wieder reduziert
sich die Speichergröße auf die Hälfte.
Bei Zeigertypen wie &T, &mut T,
Box<T>, Rc<T> und
Arc<T> ist null ein verbotener Wert.
Bei jedem solchen Zeigertyp P ist für
Option<P> der Wert None entsprechend
als null kodiert; ein zuweilen unter der Bezeichnung
Nullzeigeroptimierung geläufiger Vorgang.
Somit stimmt die Speichergröße von
Option<P> mit der von P überein.
Bei den Zeigertypen *const T und
*mut T liegt der Wert null dagegen im
erlaubten Wertebereich, man erhält ihn durch std::ptr::null()
bzw. std::ptr::null_mut().
Bei den Enumerationen entsteht eine Nische durch das Tag. Bei
enum E {A, B}
verarbeitet der Compiler Option<E> so als
läge
enum OptionE {A, B, None}
vor. Nun ist Option<E> aber selbst wieder eine
Enumeration. In der Konsequenz braucht
Option<Option<E>>
ebenfalls lediglich ein Byte Speicher.
Es gibt auch so einige Nischen die der Compiler bisweilen nicht ausnutzen kann. Betrachten wir dazu für eine Langzahlarithmetik den Typ:
enum Sign {Plus, Minus}
struct LongInt {sign: Sign, digits: Vec<u32>}
enum Int {I32(i32), Long(LongInt)}
Auf einem 64 Bit-System hat Int eine Größe von
40 Bytes. Nehmen wir nun an, die meisten Zahlen sind klein,
dann ist das eine ziemliche Verschwendung von Speicher. Mit der
Modifikation
enum Int {I32(i32), Long(Rc<LongInt>)}
verringert sich die Größe zunächst auf 16 Byte. Nun kann man
aber im Wertebereich des Zeigers Nischen finden. Mitnichten deckt
der Adressenraum eines gewöhnlichen Computers den gesamten
Zahlenraum der 64 Bit ab, womit man das Tag in das höchstwertige
Bit bringen kann, sofern das Laufzeitsystem dieses nicht bereits
für irgendetwas anderes verwendet. Ein alternativer Ansatz besteht
in der Ausnutzung, dass die Ausrichtung des Zeigertyps
Rc<LongInt> acht beträgt, womit sich in den
Bereich der nicht durch acht teilbaren Werte weitere Informationen
packen lässt. In beiden Ansätzen ist i32 ohne Probleme
unterzubringen. Somit kann man die Speichergröße von Int
letztendlich auf 8 Byte einschrumpfen lassen. Allerdings muss man
dies leider manuell unter Nutzung unsicherer Konzepte implementieren.
Eigentlich müssen sämtliche Operationen den Regeln des Typsystems genügen. Jedes Argument einer Funktion bzw. Operation muss genau den Typ besitzen, der in ihrer Signatur vorgeschrieben wurde. Unter Anwendung unsicherer Hilfsmittel ist es allerdings machbar, einen Wert an dieser Typprüfung vorbeizumogeln.
Zur Schaffung von Klarheit müssen wir zwischen zwei Arten von Typumwandlung unterscheiden:
std::convert zu finden.
Gegenstand dieses Abschnitts ist zweite Art der Typumwandlung.
Eine Methode des Typcasts ist der Zeigercast mit dem
Operator as. Aufgabe sei die Interpretation eines
Feldes von Ganzzahlen als ihre Darstellung im Speicher.
Man tut das wie folgt:
let a: [i32; 2] = [1, 2];
let p = &a as *const [i32; 2] as *const [u8; 8];
let data: &[u8; 8] = &unsafe {*p};
println!("{:02x?}", data);
Das Programm erzeugt auf einem Little-Endian-System die Ausgabe:
[01, 00, 00, 00, 02, 00, 00, 00]
Eine Alternative bietet die Nutzung der Funktion
transmute. Mir ihr lässt sich der Vorgang ein
wenig kürzer in der Form
let a: [i32; 2] = [1, 2];
let data: &[u8; 8] = unsafe {std::mem::transmute(&a)};
durchführen. Die Funktion transmute ist allerdings
wesentlich vielseitiger als der Zeigercast. Wie
let a: [u32; 2] = [1, 2];
let data: [u8; 8] = unsafe {std::mem::transmute(a)};
verdeutlicht, kann sie neben Zeigertypen auch andere Typen umwandeln. Die Typen müssen dafür mindestens Werte der gleichen Speichergröße beschreiben. Das Programmfragment
let a: [u32; 2] = [1, 2];
let data: [u8; 7] = unsafe {std::mem::transmute(a)};
ist dagegen nicht kompilierbar.
Man könnte denken, dass die umgekehrte Umwandlung
let data: [u8; 8] = [1, 0, 0, 0, 2, 0, 0, 0];
let a: &[i32; 2] = unsafe {std::mem::transmute(&data)};
ebenfalls durchführbar sein muss. Dem ist aber nicht so. Wir
erinnern uns daran, dass mit u8 die Ausrichtung des
Feldes eins ist, ein Feld von Elementen des Typs i32
jedoch die Ausrichtung vier erfordert. Somit ist ein verbotenes
Programm konstruiert. Den Compiler störte das im Jahr 2021
nicht. Erst Miri monierte:
Undefined Behavior: type validation failed: encountered an unaligned reference (required 4 byte alignment but found 1)
Und das heißt nicht einmal, Miri war immer imstande, alle falschen Annahmen zur Ausrichtung zu detektieren. Selbst Miri ließ sich recht leicht austricksen. Der Zeiger besaß im konkreten Fall einen Rest modulo 4. Verkürzte man das Ziel um ein Element und verschob den Zeiger um so viele Bytes, dass der Rest null wurde, war Miri besänftigt. Das Problem wurde erst aufgespürt, sobald Miri mit der Option
-Zmiri-symbolic-alignment-check
pedantischer gemacht wurde.