Systems Operational ɒiʜꟼOS, wir haben ein Problem
Missing Feature
Für fast zwei Wochen war ich in Bulgarien. Danach erhielt ich beim ersten Übersetzungsversuch des ɒiʜꟼOS-Codes eine Fehlermeldung:
error[E0557]: feature has been removed
–> libs/kalloc/src/lib.rs:1:12
|
1 | #![feature(allocator)]
| ^^^^^^^^^
error: The attribute allocator is currently unknown to the compiler and may have meaning added to it in the future (see issue #29642)
–> libs/kalloc/src/lib.rs:2:1
|
2 | #![allocator]
| ^^^^^^^^^^^^^
|
= help: add #![feature(custom_attribute)] to the crate attributes to enable
error: aborting due to 2 previous errorsNatürlich fiel die Fehlermeldung nicht einfach so vom Himmel, ich hatte vorher – wie ich das regelmäßig tue – meine Toolchain mit rustup update aktualisiert.
Selbstverständlich hätte ich jetzt meine Toolchain auch wieder zurück setzen können, aber ich möchte, dass ɒiʜꟼOS mit der jeweilig aktuellen Toolchain übersetzbar ist.
Und da ich „nightly“ nutze, können solche abrupten Wechsel schon mal vorkommen. Also wird erstmal nichts aus der Erweiterung unseres Betriebssystem, sondern es heißt, den bestehenden Code wieder
lauffähig zu machen.
Auf der Suche nach dem verlorenen Attribut
Wie die Fehlermeldung angibt, wurde das Feature #![allocator] entfernt. Was nun? Ein rustc --explain E0557 hilft hier nicht weiter, und das angegebene Issue in GitHub
beschäftigt sich mit Customer-Attributen. Vielleicht braucht man das Attribut nicht mehr, es reicht, dass die Funktionen vorhanden sind?
Ein einfaches Auskommentieren hilft nicht:
error: no #[default_lib_allocator] found but one is required; is libstd not linked?
error: cannot continue compilation due to previous error
error: Could not compile aihPOS.Aha, sollte das Attribut einfach bloß umbenannt worden sein? Leider nein, #![allocator] war ein modulweites Attribut, im Gegensatz zu #[default_lib_allocator]. Im
„Unstable Book“ ist #[default_lib_allocator] nicht aufgeführt. Allerdings hilft der
GitHup-Issue zu #![allocator] weiter: Es verweist auf einen anderen Issue,
#42727, der wiederum auf anderes verweist, u.a. Issue #32838 und
die RFCs RFC 1974 und
RFC 1398. Daraus ergibt sich ein stimmiges Bild: Das Allokator-Interface wurde
überarbeitet und durch eine neue API ersetzt.
Im Folgendem wird beschrieben, wie das Allokator-Interface nun aussieht. Die entsprechenden Aussagen aus der Folge „Wir machen einen Haufen“ dieser Reihe sind als überholt zu betrachten.
Auf zu neuen Ufern
Allokator-API
Ein Allokator (im allgemeinen) ist eine Struktur, die den
Allocator-Trait implementiert. Der Trait ist zwar im Crate alloc
definiert, aber derzeit 1 noch nicht in der offiziellen
Dokumentation. Die
Quellfiles sind aber ausführlich kommentiert.
Der Trait besteht aus folgenden Funktionen:
pub unsafe trait Allocator {
unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout);
fn oom(&mut self, _: AllocErr) -> !;
fn usable_size(&self, layout: &Layout) -> (usize, usize);
unsafe fn realloc(&mut self,
ptr: *mut u8,
layout: Layout,
new_layout: Layout) -> Result<*mut u8, AllocErr>;
unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr>;
unsafe fn realloc_excess(&mut self,
ptr: *mut u8,
layout: Layout,
new_layout: Layout) -> Result<Excess, AllocErr>;
unsafe fn grow_in_place(&mut self,
ptr: *mut u8,
layout: Layout,
new_layout: Layout) -> Result<(), CannotReallocInPlace>;
unsafe fn shrink_in_place(&mut self,
ptr: *mut u8,
layout: Layout,
new_layout: Layout) -> Result<(), CannotReallocInPlace>;
fn alloc_one<T>(&mut self) -> Result<Unique<T>, AllocErr>
where Self: Sized;
unsafe fn dealloc_one<T>(&mut self, ptr: Unique<T>)
where Self: Sized;
fn alloc_array<T>(&mut self, n: usize) -> Result<Unique<T>, AllocErr>
where Self: Sized;
unsafe fn realloc_array<T>(&mut self,
ptr: Unique<T>,
n_old: usize,
n_new: usize) -> Result<Unique<T>, AllocErr>
where Self: Sized;
unsafe fn dealloc_array<T>(&mut self, ptr: Unique<T>, n: usize) -> Result<(), AllocErr>
where Self: Sized;
}
Müssen jetzt wirklich fünfzehn Funktionen implementiert werden? Und die neuen Typen, Layout, AllocErr, Excess, CannotReallocInPlace?
Tatsächlich sieht die Sache viel freundlicher aus: Nur zwei der Funktionen sind obligatorisch, nämlich alloc() und dealloc(). Alle anderen haben sinnvolle
Standardimplementationen (defaults).
Layout ist eine Struktur, die einen Speicherrequest beschreibt. Sie hat u.a. die beiden Methoden:
pub fn size(&self) -> usize;
und
pub fn align(&self) -> usize;
Der Summentyp2 AllocErr ist – wie der Name vorschlägt – für den Fehlerbericht bei der Allozierung zuständig. Er ist wie folgt definiert:
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum AllocErr {
Exhausted { request: Layout },
Unsupported { details: &'static str },
}
Alle anderen Dinge braucht man zunächst einmal nicht (können aber später zur besseren Effizienz genutzt werden). Es ist somit jetzt einfach, die Kompatibilität zum früheren Interface wieder herzustellen.
Die Allokator-API gilt für alle Allokatoren, Rust unterstützt
Hierarchien von Allokatoren. Am Ende wird irgendwann die
Speicherverwaltung des Betriebssystems von die
Standardbibliothek gerufen. Existiert kein solches (wie in unserem
Fall) oder wird nur die Standardbibliothek nicht eingebunden, aber
trotzdem Crates benutzt, die Allozierungen vornehmen wollen, muss ein
globaler Allokator angegeben werden. Dies wird einfach gemacht, indem
einer Instanz einer Allokator-Struktur mit dem Attribut
#[global_allocator] dazu erklärt wird. Warum bei der Fehlermeldung
oben dieses Attribut – das übrigens auch noch keinen Eintrag im
Unstable Book hat – nicht
genannt wurde, sondern #[default_lib_allocator] ist mir nicht ganz
klar; vermutlich ist das bloß
noch nicht stabilisiert.
Am Rande des Speichers
Ich nutze die Gelegenheit und implementiere eine eigene
Heapverwaltung. Dazu nutze ich das Boundary-Tag-Verfahren 3. Das
hat den Vorteil, dass die Wiedereingliederung von zurückgegebenen
Speicher eine konstante Komplexität \(\mathcal{O}(1)\) hat, jedoch
auf Kosten des Speicherverbrauchs: Jeder belegte Speicherabschnitt hat
zwei Tags Verwaltungsinformation, in denen die Größe des Abschnitts
und Statusflags stehen. In meiner Implementation ist ein Tag ein
usize (genauer: eine struct mit einem usize), so dass jeweils
pro Block 8 Bytes Overhead entstehen. Da es durch die
Alignmentanforderungen ohnehin zu Verschnitt kommt, halte ich dies für
vertretbar.
Um einen Speicherbereich zu belegen, wird einfach die Freispeicherliste durchsucht:
unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr> {
let start = MemoryRegion::new_from_memory(self.first.as_ptr() as usize);
for mut mr in start {
if mr.is_sufficient(&layout) {
return mr.allocate(layout);
}
}
Err(AllocErr::Exhausted{request: layout})
}
}
Die eigentliche „Arbeit“ liegt bei der allocate-Methode des
Speicherabschnitts: Hier wir überprüft, ob der Abschnitt als Ganzes
belegt werden soll, oder ob er aufgeteilt wird. Im letzteren Fall wird
die Teilung durchgeführt; der abgetrennte Bereich nimmt den Platz des
ursprünglichen Abschnittes in der Liste ein.
/// Belegt den Speicherbereich
/// Ggf. wird der Speicherbereich geteilt
///
/// #Safety
/// Es muss sichergestellt sein, dass eine korrekte doppeltverkettete Liste existiert.
pub unsafe fn allocate(&mut self, layout: Layout) -> Result<*mut u8, AllocErr> {
let dest_addr = align_up(self.client_addr().unwrap(),layout.align());
let front_padding = dest_addr - self.client_addr().unwrap();
let needed_size = cmp::max(align_up(front_padding + layout.size(),mem::align_of::<EndBoundaryTag>()),
Self::min_size());
// Vorgänger und Nachfolger in der Liste (so vorhanden)
let mut prev = self.prev.map_or(None,| a | Some(MemoryRegion::new_from_memory(a)) );
let mut next = self.next.map_or(None,| a | Some(MemoryRegion::new_from_memory(a)) );
// Lohnt es sich, den Bereich zu teilen?
if self.size - needed_size > Self::min_size() { // Teile den Bereich
// Initialisere den neuen Bereich.
let old_size = self.size;
self.set_size(needed_size);
let mut new_mr = MemoryRegion::new();
// Da der neue Bereich hinten abgetrennt wird, gibt es stets einen Vorgänger
new_mr.init(Some(self.end_addr.unwrap() + mem::size_of::<EndBoundaryTag>()),
old_size - self.size - 2 * mem::size_of::<EndBoundaryTag>(),
self.next, self.prev, false, self.upper_guard);
assert_eq!(old_size + 2 * mem::size_of::<EndBoundaryTag>(), self.size + new_mr.size + 4 * mem::size_of::<EndBoundaryTag>());
self.upper_guard = false;
// Setze Liste auf abgetrennten Bereich um
prev.map_or((),| mut mr | mr.set_next_addr(new_mr.addr));
next.map_or((),| mut mr | mr.set_prev_addr(new_mr.addr));
new_mr.write_to_memory();
} else { // Belege den gesamten Bereich
// Entferne Bereich aus der Liste
self.free = false;
prev.map_or((),| mut mr | mr.set_next_addr(self.next));
next.map_or((), | mut mr | mr.set_prev_addr(self.prev));
}
prev.map_or((),| mut mr | mr.write_to_memory());
next.map_or((), | mut mr | mr.write_to_memory());
// Markiere Bereich als reserviert und aktualisiere den Speicher
self.free = false;
self.write_to_memory();
Ok(dest_addr as *mut u8)
}
Die Komplexität der Reservierung ist immer noch \(\mathcal{O}(n)\), wobei \(n\) die Anzahl der freien Speicherblöcke ist. Im Unterschied zur vorherigen Lösung muss bei der Wiedereingliederung die Liste nicht durchsucht werden:
unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout) {
let end_tag_addr = memory_region::align_up(ptr as usize + cmp::max(layout.size(),MemoryRegion::min_size()),
mem::align_of::<EndBoundaryTag>());
let end_tag = EndBoundaryTag::new_from_memory(end_tag_addr);
let mut mr = MemoryRegion::new_from_memory(end_tag_addr - end_tag.size() - mem::size_of::<EndBoundaryTag>());
mr.set_free(true);
// Prüft, ob Bereiche zusammen gelegt werden können.
if !mr.coalesce_with_neighbors() {
// Keine physischen Nachbarn gefunden, Speicherbereich rückt an Listenanfang
let mut head: StartBoundaryTag = self.first.get();
mr.set_prev_addr(Some(&self.first as *const _ as usize));
mr.set_next_addr(head.next());
// Bisheriges TOL-Element rückt hinter neues Element
if let Some(next_addr) = mr.next_addr() {
let mut next = MemoryRegion::new_from_memory(next_addr);
next.set_prev_addr(mr.addr());
next.write_to_memory();
}
// Listenkopf zeigt auf einzugliedernden Bereich
head.set_next(mr.addr());
self.first.set(head);
mr.write_to_memory();
}
}
Das ist natürlich nur ein Teil des Gesamtcodes, der vollständige Code ist wieder auf GibHub zu finden.
Blick zurück in Freude
Nachdem mein neuer Allokator tadellos lief, stellte ich fest, dass die von mir früher verwendete Version 0.2.7 der linked_list_allocator-Bibliothek gar nicht mehr die aktuelle ist. Die
derzeit neuste Version ist 0.4.1 und hat die neue Allokator-API schon vollständig umgesetzt. Danke an den Autor Philipp Oppermann, von dem auch das Blog
„Writing an OS in Rust“ stammt. Ich werde zwar in ɒiʜꟼOS bei meinem Boundary-Tag-Allokator bleiben, es ist aber gut zu wissen, dass es eine Alternative gibt
und dass die Community so schnell reagiert.
- 18. Juli 2017 ↩
- Ich bin mir nicht sicher, was die beste Bezeichnung im Deutschen
für
enumist. Als C-Programmierer denkt man da an „Aufzählungstyp“, was aber in Rust in die Irre führt. „Summentyp“ ist typentheoretisch korrekt, klingt aber trotzdem etwas eigenartig. ↩ - D. Knuth, „The Art of Computer Programming“, 2nd Auflage, Addison Wesley, 1973, Seiten 441f ↩
Kommentare