Bisher haben wir feste Adressen verwendet wie 0x500000 oft fest definiert (z.B. per #define in der config.h). Problematisch wird dies, sobald unser Kernel die vorgegebene Größe überschreitet oder neue globale BSS-Variablen hinzukommen. Es kann hierbei sehr schnell zu nicht mehr kontrolierten Systemverhalten kommen. Da wir eine Methode finden müssen, den Speicher zu verwalten, brauchen wir einen Weg, wie wir dies verhindern.
Ein Weg ist unser Linker-Script, denn alleine dieses weiß, wie der Speicher in unserem System verteilt ist. Wir verwenden es und lassen den Speicher einfach dynamisch hintereinander gelagert wachsen.
Das dynamische Linker-Skript (linker.ld)
Im ersten Teil des Scripts, lassen wir unser System bestehen, wie es ist. In diesem Teil wird definiert, wie der Kernel aufgebaut wird. Hier ist die einzige feste Adresse, die wir benutzen müssen, die Adresse des Kernel-Starts: 0x80000.
/* linker.ld - Für Raspberry Pi 4 AArch64 */
ENTRY(_start)
MEMORY {
ram : ORIGIN = 0x80000, LENGTH = 128M
}
SECTIONS {
. = 0x80000;
.init : {
*(.init)
} > ram
.text : {
*(.text*)
_etext = .;
} > ram
.rodata : {
*(.rodata*)
} > ram
.init_array : {
__init_start = .;
KEEP(*(SORT_BY_INIT_PRIORITY(.init_array.*)))
KEEP(*(.init_array))
__init_end = .;
} > ram
.ARM.exidx : {
__exidx_start = .;
*(.ARM.exidx*)
__exidx_end = .;
} > ram
.eh_frame : {
*(.eh_frame*)
} > ram
.data : {
_sdata = .;
*(.data*)
_edata = .;
} > ram
.bss (NOLOAD) : {
. = ALIGN(8);
__bss_start = .;
*(.bss*)
*(COMMON)
. = ALIGN(8);
__bss_end = .;
} > ram
_end = .;Anschließend lassen wir uns durch das Linker-Script die Adressen des Speichers errechnen:
/* -------------------------------------------------------------------- */
/* DYNAMISCHE SPEICHERAUFTEILUNG */
/* -------------------------------------------------------------------- */
/* 1. Coherent Region (DMA / Uncached Memory für spätere USB/Mailbox-Treiber) */
. = ALIGN(65536); /* 64KB Alignment für spätere 64KB MMU-Pages */
__coherent_start = .;
. = . + 0x400000; /* Reserviere 4 MB */
__coherent_end = .;
/* 2. Heap Allocator (Dynamischer Nutzspeicher für malloc / palloc) */
. = ALIGN(65536); /* 64KB Alignment für palloc-Anforderungen */
__heap_start = .;
. = . + 0x1000000; /* Reserviere 16 MB */
__heap_end = .;
/* 3. Systemspeicher / Freier RAM */
. = ALIGN(65536);
__memory_start = .;
__memory_end = ORIGIN(ram) + LENGTH(ram);Da wir das Script eigentlich nicht mehr anfassen wollen, definieren wir bereits jetzt schon unser Coherent-Bereich. Dieser Bereich ist später für die USB-Programmierung wichtig, da es der Bereich sein wird, in der die Hardware direkt schreiben kann. Dies wird nachher per MMU geregelt. Mehr dazu, später.
Für diesen Teil des Tutorials ist der "Heap Allocator" und natürlich unser "Systemspeicher".
Hier wird ". = ALIGN(65536);" verwendet. Dies ist für den ARM64-Prozessor extrem wichtig, da er hier auf 64-KB-Blöcke zugreift.
Verwendung von Linker-Symbolen in C
Da diese Symbole erst beim Linken entstehen, müssen wir diese Symbole zunächst dem C-Compiler mitteilen, damit er weiß, was für Werte das sind. Der Linker verwendet diese Symbole als Adressen und das müssen wir dem Compiler auch mitteilen:
// Deklaration der Linker-Symbole
extern char __heap_start;
extern char __heap_end;
extern char __memory_start;
extern char __memory_end;Damit sind die Symbole nun bekannt.
Im Code können wir diese dann wie folgt verwenden:
uintptr heap_start_addr = (uintptr)&__heap_start;
uintptr heap_end_addr = (uintptr)&__heap_end;Damit sind dann die echten Adressen in heap_start_addr und heap_end_addr abgelegt und wir können damit arbeiten.
Aufbau unserer Speicherverwaltung
Wir verwenden folgendes Chema:
[ Bereich 1: Header-Speicher (__heap_start bis __heap_end) ]
┌────────────────────────────────────────────────────────┐
│ HeapBlock #1 │ HeapBlock #2 │ HeapBlock #3 │ ... │ <- Hier liegen NUR die
│ (status, size,│ (status, size,│ (status, size,│ │ Strukturen/Metadaten
│ position...) │ position...) │ position...) │ │ (Array / Kette)
└────────────────────────────────────────────────────────┘
[ Bereich 2: Echter Nutzspeicher (__memory_start bis __memory_end) ]
┌────────────────────────────────────────────────────────┐
│ Puffer 1 (z.B. 128 Bytes für malloc) │
├────────────────────────────────────────────────────────┤
│ Page 1 (z.B. exakt 64 KB ausgerichtet für palloc) │ <- 100% sauberer RAM,
├────────────────────────────────────────────────────────┤ keine Header dazwischen!
│ Page 2 (z.B. 64 KB für MMU-Tabelle) │
└────────────────────────────────────────────────────────┘Im Speicherbereich __heap_start bis __heap_end definieren wir eine Art Karteikartensystem, welches HeapBlöcke hintereinander haben. In diesen Blöcken werden die einzelnen Speicheranforderungen gespeichert und verwaltet. Dort werden die Adressen des entsprechenden Speichers, der benötigt wird Im echten Nutzspeicher hinterlegt.
Inititierung der Heap-Kartei
Bisher hat der Kernel keinerlei Informationen zum Speicher. Dies müssen wir zuvor ihm mitteilen. Dazu erstellen wir einen ersten HeapBlock, der den gesamten Speicher als Frei definiert.
typedef struct HeapBlock
{
boolean status; // FALSE = frei, TRUE = belegt
u64 size; // Größe des verbleibenden Nutzspeichers
u64 position; // Startadresse des Nutzspeichers
struct HeapBlock* next; // Nächster Block (NULL = keiner)
} HeapBlock;
void init_heap(void)
{
uintptr heap_ctrl_start = (uintptr)&__heap_start;
uintptr data_ram_start = (uintptr)&__memory_start;
uintptr data_ram_end = (uintptr)&__memory_end;
// Der erste Verwaltungs-Knoten liegt im CONTROL-Bereich (__heap_start)
HeapBlock* first_header = (HeapBlock*)heap_ctrl_start;
first_header->status = FALSE; // Frei
first_header->position = data_ram_start; // Zeigt auf den Start von __memory_start
first_header->size = data_ram_end - data_ram_start; // Der gesamte RAM-Bereich ist frei
first_header->next = NULL;
}
Zunächst erzeugen wir eine Strucktur, die die Informationen für uns im Heap ablegt. Unter next kann ein Zeiger auf die nächste gleiche Struktur abgelegt werden. Mit init_heap() füllen wir den ersten Eintrag wie folgt:
- status = FALSE //Der Speicher hier im Block ist verfügbar
- position = data_ram_start //Begin unseres Speicherssystems
- size = ram_größe // Wieviel Speicher habe ich insgesamt.
- next = NULL // Da es noch keinen weiteren Block gibt.
Speicher reservieren mit alloc()
Die einzelnen Heap-Blöcke sollen den speicher verwalten. Sie werden bei jeder Speicheranforderung durchsucht und geschaut, ob die Menge an Speicher hier verfügbar ist. Wenn etwas vorhanden ist, dann soll diese als Ergebnis die Adresse des Speichers zurückgeben. Da wir diese Funktion universiell einzetzen werden, müssen wir auch Sonderlocken, wie Allokieren von Pages (align und feste Größe) unterstützen. Aus diesem Grund müssen wir auch eine Anforderung, wie align verwenden. Dazu übergeben wir alloc() die größe des Speichers, welchen wir benötigen, sowie den align-Parameter, damit das Ergebnis eine ausgerichtete Adresse ist.
void* alloc(u64 size, u64 align)
{
// Adressgrenzen aus den Linker-Symbolen beziehen
uintptr heap_ctrl_start = (uintptr)&__heap_start;
uintptr heap_ctrl_end = (uintptr)&__heap_end;
uintptr data_ram_end = (uintptr)&__memory_end;
// Mindestausrichtung für 64-Bit-Prozessoren sicherstellen
if (align < 8) {
align = 8;
}
...
}
Auch hier verwenden wir die Informationen aus dem Linker.
Eine wichtige Sache müssen wir hier berücksichtigen. Da der 64-Bit-Prozessor Schwierigkeiten hat, mit nicht ausgerichteten Speicherstellen, fordern wir eine Mindestausrichtung. Damit wird immer eine "einfache" Adresse zurückgegeben.
// Der Einstiegspunkt in die Kette liegt am Anfang des Header-Bereichs
HeapBlock* block = (HeapBlock*)heap_ctrl_start;
// Schutz vor zeitgleichem Multi-Core- oder Interrupt-Zugriff
EnterCritical2();
while (block)
{
...
}
LeaveCritical();
return NULL;Da wir bei der Initialisierung den ersten Block am Anfang unserers HeapBereichs gesetzt haben, werden wir hier unseren Einstiegspunkt verwenden.
Die Reservierung eines Speicherbereichs kann sehr kritisch werden, wenn andere Funktionen, wie Interrupts, oder eine andere CPU versucht, sich hier einzumischen. Dies kann zur folge haben, dass unsere Struktur, die wir hier erstellen, zerstört wird. Systemkritische Funktionen müssen so weit geschützt werden, dass nichts von aussen diesen weg zerstört. Hierfür wird EnterCritical2() verwendet, welches dem System verbietet, irgenwelche andere Dinge zu tun. Am Ende geben wir dies mit LeaveCritical wieder frei.
In der while-Schleife suchen wir dann unseren freien Bereich.
while (block)
{
if (!block->status) // Freien Block in der Karteikarte suchen
{
...
}
block = block->next;
}
Hier fragen wir jeden Block ab, ob dieser im status TRUE ist, was bedeutet, dass hier ein Block ist, der zwar Speicher besitzt, aber nicht reserviert ist. Ansonsten wiederholen wir die Schleife.
if (!block->status) // Freien Block in der Karteikarte suchen
{
u64 pos = block->position;
// 1. Ausrichten der Datenadresse an der geforderten Alignment-Grenze
u64 aligned_pos = (pos + align - 1) & ~(align - 1);
u64 padding = aligned_pos - pos;
// 2. Prüfen, ob der freie Datenbereich im RAM groß genug ist
if (block->size >= size + padding)
{
...
}
}Wenn wir einen Speicherplatz gefunden haben, der Frei ist, müssen wir überprüfen, ob der Platz darin ausreichend ist. Dazu holen wir uns zunächst die Speicheradresse, berechnen den align aus und testen, ob der Bereich ausreichend ist. Wenn nicht, suchen wir über die while-Schleife den nächten freien Bereich.
// 2. Prüfen, ob der freie Datenbereich im RAM groß genug ist
if (block->size >= size + padding)
{
block->status = TRUE;
// Wenn dies der letzte Block in unserer Verwaltungskette ist, spalten wir ihn auf
if (!block->next)
{
...
}
else
{
// Wiederverwendung eines bereits existierenden freien Blocks
....
}
}Wenn der Platz reicht, setzen wir den status des Blocks auf TRUE, was bedeutet, dass der Bereich nun reserviert ist. Wenn es keinen Zeiger auf den nächsten Block hat, wissen wir, dass wir das Ende der Kette erreicht haben. Wenn es einen nächsten Block gibt, verwenden wir einen exsitierenden Block und müssen ihn kennzeichnen.
Kommen wir zum Fall, dass wir das Ende der Kette erreicht haben.
block->size = size + padding;
block->position = aligned_pos;
// Der nächste VERWALTUNGS-HEADER wird direkt im Header-Bereich platziert!
HeapBlock* next_header = block + 1;
// Schutz: Prüfen, ob im HEADER-Bereich noch Platz für den nächsten Knoten ist
if ((uintptr)(next_header + 1) < heap_ctrl_end)
{
block->next = next_header;
// Konfiguration des neuen freien Verwaltungs-Knotens
next_header->status = FALSE;
next_header->next = NULL;
next_header->position = aligned_pos + size; // Folgende freie Datenadresse im RAM
// Restgröße im echten Daten-RAM berechnen
if (data_ram_end > next_header->position) {
next_header->size = data_ram_end - next_header->position;
} else {
next_header->size = 0;
}
}
LeaveCritical();
return (void*)aligned_pos; // Rückgabe der perfekten Daten-Adresse im RAM!
Zunächst setzen wir die Größe des reservierten Speichers und die Position in unseren aktuellen Block. Erzeugen dann einen neuen Block. Damit wir keinen Überlauf des Heaps erzeugen, prüfen wir erstmal, ob der neue Block noch in diesen Speicherbereich rein passt, wenn nicht, ignorieren wir es einfach und für den nächsten Block bleibt der Wert bei Null. Sollten wird nun versuchen, einen neuen Speicher zu reservieren, werden wir keinen mehr finden.
Wenn wir einen neuen Block erstellen konnten, wir die Adresse des Blocks in unseren aktuellen Header geschrieben. Der neue Block im Status FALSE, die Speicheradresse und Restgröße in den neuen Block geschrieben und der neue Zeiger auf NULL gesetzt.
Wenn wird dies durchgeführt haben, verlassen wir unseren sicheren Hafen (LeaveCritical) und geben die gefundene Adresse zurück.
else
{
// Wiederverwendung eines bereits existierenden freien Blocks
block->position = aligned_pos;
LeaveCritical();
return (void*)aligned_pos;
}
Falls wir allerdings den Fall hatten, das es einen folge Block gibt, schreiben unsere neue Position in den Block, verlassen die Systemsperre und geben nur die Position zurück.
Hiermit haben wir eine recht einfache Speicherverwaltung geschaffen, die uns das gibt, was wir in den nächsten Schritten benötigen.
Speicher wieder freigeben (free())
In unserer Tabelle, die wir mit alloc erstellt haben, speichern wir unsere Position des Speichers ab. Diese können wir für die Freigabe verwenden. Unsere free-Funktion übergeben wir einfach diese Position.
void free(void* ptr)
{
uintptr heap_start_addr = (uintptr)&__heap_start;
HeapBlock* block = (HeapBlock*)heap_start_addr;
EnterCritical2();
while (block)
{
if ((void*)block->position == ptr)
{
block->status = FALSE; // Als frei markieren
LeaveCritical();
return;
}
block = block->next;
}
LeaveCritical();
}Diese Funktion ist recht einfach, aber auch Systemkritisch, so das wir dort auch in den EnterCritical gehen müssen. Zunächst holen wir den Anfang unserer Heaptabelle, welches auf den ersten Block zeigt.
In einer while-Schleife prüfen wir nun jeden Block, ob die Adresse, die wir übergeben haben mit dem Wert aus der Tabelle übereinstimmt. Wenn wir ihn gefunden haben, setzen wir einfach nur den status auf FALSE und der Speicher ist frei.
Memory Allocation (malloc())
malloc() ist eine Standard-Funktion in C, die wir hier nachbilden und wird eine Wrapper-Funktion, die alloc(size, 64) mit 64-Byte Cache-Line-Alignment aufruft. Wir verwenden hier ein 64-Byte align, da die 64-Bit-Prozessoren mit diesen Adressen am besten umgehen können.
void *malloc (size_t nSize)
{
void *MemPos = alloc(nSize, 0x40); // 64-Byte Cache-Line Alignment
if (MemPos == 0)
{
printf("malloc: Not enough memory available or heap is full\n");
Stop();
}
return MemPos;
}Wie gerade besprochen, verwenden wir alloc und übergeben der Funktion die geforderte größe an Speicher. Zusätzlich übergeben wir ihr ein align von 64-Bytes.
Spezial-Funktion palloc
palloc() ist eine Spezial-Funktion, die ganze 64-KB-Pages (PAGE_SIZE) mit 64-KB-Alignment anfordert, um später die MMU-Tabellen darin unterzubringen.
void *palloc (void)
{
// Fordert 64 KB mit 64 KB Alignment an
void *MemPos = alloc(PAGE_SIZE, PAGE_SIZE);
if (MemPos == 0)
{
printf("palloc: Not enough memory available or heap is full\n");
Stop();
}
return MemPos;
}Den Code kannst du hier herunterladen: https://www.satyria.de/arm/sources/RPI4/C/speicher1.zip
Fazit
Nun sind wir der Herrscher über unsere Speicher und können beliebig darüber verfügen.