YeXo - een kernel programmeren

24 april 2006

Physical memory manager 2

Na mijn eerdere post over een PMM nu wat aanvullingen en correcties. Een stack is op meerdere manieren te implementeren. De eerste manier (die ik in het eerdere artikel beschreef) is een echte stack: een doorlopend stuk geheugen met achter elkaar de adressen van vrije pages. Een tweede manier kan echter zijn om een pointer bij te houden naar de eerste vrije page. De eerste 4 bytes van die page bestaan dan weer uit een pointer naar de volgende vrije page, enzovoort.

Ook kun je, wat nogal lijkt op de tweede manier van de stack, een linked list gebruiken. Om deze linked list niet al te veel geheugen te laten gebruiken, is het het meest efficient om naast elkaar liggende pages in een element van de list op te slaan. Dit kan bijvoorbeeld door elk element niet alleen een adres, maar ook een grootte te geven. Om twee naburige stukken weer aan elkaar te plakken, is het handig om de elementen gesorteed te bewaren op adres.

Tot slot nog een paar links over dit onderwerp (in het engels):
Archiefpagina van het forum op codecomments.com
De mega-tokyo pagina over memory management

22 april 2006

Virtual memory manager

Een VMM is een extra laag bovenop de PMM. De VMM zorgt ervoor dat als een process (of de kernel zelf) extra geheugen aanvraagt dat dit geheugen direct achter het vorig aangevraagde geheugen lijkt te liggen. Dit kan door middel van een techniek die paging heet. Paging heb ik al eerder aangezet bij het laden van de kernel op 3gb in het virtueel geheugen. Bij het initiƫren van de VMM moet deze ervoor zorgen dat hij weet waar de page directory en de page tables zich bevinden. Verder moet de VMM twee functies hebben: een om een page aan te vragen op een bepaald virtueel adres en een om een page op een virtueel adres weer vrij te geven. Bij mij heten deze functies vmmMapPage en vmmUnmapPage.

De functie vmmMapPage controleert eerst op welke plaats in welke page table het virtuele adres staat. Daarna wordt gekeken of die page table al bestaat en anders wordt eerst die page table aangemaakt. Daarna wordt het juisten adres (verkregen van de PMM) weggeschreven met de waarde 3 (kernel-level en read/write).

18 april 2006

Een virtuele floppy gebruiken

Dit bericht is voor hen die net als ik geen zin hebben om telkens te wachten tot bochs weer een bestand van je floppy gelezen heeft, en voor diegenen die geen floppy in hun computer hebben zitten. Een virtuele floppy is de oplossing! Virtual Floppy Driver is hier een heel handig programma voor. Download en installeer het. Voer daarna vfdwin.exe uit. Open nu een virtuele floppy (dit wijst zich vanzelf) in drive 0 onder bijvoorbeeld drive-letter B. Let erop dat je het image als file en niet in het ram opent. Als je een image in het ram opent gaan de wijzigingen verloren zodra je vfd weer afsluit.

11 april 2006

Physical memory manager

Wat doet een physical memory manager?

De pmm houdt een overzicht bij welke pages vrij zijn. Een page is een aaneensluitend blok geheugen van precies 4kb (4096 bytes) groot. Het adres van zo'n page heeft als laatste 12 bits 0. De adressen overlappen elkaar dan ook niet. In de loop van de tijd zijn er steeds meer manieren bedacht om bij te houden welke pages vrij zijn en welke niet. Het kan handig zijn om een onderscheid te maken tussen de adressen onder 16mb en de adressen daarboven. Voor dma is het noodzakelijk dat de adressen uit de eerste 16mb van het fysieke geheugen komen.Je kunt bijvoorbeeld voor de adressen onder 16mb een bitmap gebruiken en voor de adressen daarboven een stack. Ik zal hierna een paar van die manieren uitleggen en aan het eind een overzicht van de voor en nadelen geven.


Bitmap

De meest simpele manier om dit overzicht te houden is voor elke page in het fysieke geheugen 1 bit op 1 in te stellen als de page bezet is en op 0 te zetten als deze 4kb vrij zijn. Voor een computer met 1gb aan geheugen neemt een bitmap 8kb (twee pages) in beslag. Het dealloceren van een page is erg gemakkelijk: je moet gewoon het bijbehorende bitje op 0 instellen. Het alloceren kan echter wat meer tijd kosten omdat je de hele bitmap moet doorzoeken op zoek naar een bitje die op 0 staat. Gelukkig kan dit met 32 bits tegelijk. Een mogelijke uitbreiding hierop kan zijn dat je het adres bijhoudt waar je tijdens het zoeken in de bitmap gebleven bent. De volgende keer kun je zo makkelijk weer verdergaan waar je gebleven was met zoeken. Een andere variatie hierop kan zijn dat je verschillende lagen bitmaps hebt. Je maakt een aantal bitmaps voor bijvoorbeeld 32mb elk, en dan nog een bitmap die aangeeft in welke van die bitmaps nog vrije pages zitten. Als er nu een stuk van 32mb niet meer vrij is, hoef je daar in ieder geval niet meer in te zoeken.


Stack

De naam van dit algoritme zegt het eigenlijk al: we houden gewoon een stack bij met de adressen van de vrije pages. Als we nu een vrije page moeten aanleveren poppen we gewoon een adres van de stack en als er weer een page vrij gemaakt wordt pushen we dat adres weer op de stack. Een groot nadeel van een stack is dat het erg lastig is om een reeks adressen achter elkaar te verkrijgen. Hiervoor moet vaak de stack doorzocht worden en dat kost erg veel tijd.


Buddy Allocation System

Dit is het algoritme dat de linux kernel gebruikt. Het is een stuk lastiger om te implementeren dan een bitmap of een stack, maar kan bij grote allocaties een stuk sneller zijn. De benodigte ruimte zit ergens tussen die van een bitmap en van een stack in, en de snelheid ook. Het is dus een mooi compromis. De totale vrije ruimte wordt opgedeelt in een aantal stukken van 16 pages, 8 pages, 2 pages en losse pages. Die blokken worden dan in meerdere linked lists (een voor elke grootte) bijgehouden. Als er nu om een losse page gevraagt wordt en de linked list voor losse pages is leeg, moet er eentje uit de linked list voor 2 pages gehaald worden en in twee stukken gehakt. Een wat geavanceerdere allocator zou ook de linked list kunnen doorzoeken als er verder niks te doen is en dan pages die naast elkaar passen aan elkaar plakken. Ook zou je de voor elke grootte twee linked list kunnen gebruiken: een voor adressen onder en een voor adressen boven 16mb.


Combinaties van deze systemen

Je zou ipv een stack een combinatie van een stack en een bitmap kunnen gebruiken: Je gebruikt een stack met bijvoorbeeld maximaal 20 pages erop en verder een bitmap. Je kunt dan de stack gebruiken om snel een vrij adres te vinden. Als er een adres vrijkomt en de stack is vol geef je dat aan in de bitmap. Als je een adres moet hebben en de stack is leeg doorzoek je de bitmap en vul je de stack.


Overzicht voor en nadelen

Hieronder geef ik een vergelijking tussen de eerste drie algoritmes. De nummer 1 is telkens de beste.
Snelheid (voor losse pages):

  1. Stack
  2. Buddy
  3. Bitmap
Snelheid (meerdere pages achter elkaar), let op, meerdere pages achter elkaar in fysiek geheugen is bijna alleen nodig voor dma.
  1. Buddy
  2. Bitmap
  3. Stack
Geheugengebruik:
  1. Bitmap
  2. Buddy
  3. Stack

07 april 2006

Hoe virtueel geheugen werkt

Virtueel geheugen kan ervoor zorgen dat twee geheugenplaatsen naast elkaar lijken te liggen op een willekeurig adres. Ook kun je ervoor zorgen dat meerdere programma's op hetzelfde virtuele adres geladen worden. Dit klinkt natuurlijk erg vreemd, meerdere programma's op dezelfde plaats laden. Het kan omdat de verwijzing naar het virtuele adres eerst omgezet wordt door een speciaal gedeelte in je CPU, namelijk de mmu. Eerst een voorbeeld hoe virtueel geheugen werkt. Stel, het physieke geheugen ziet er als volgt uit:

AdresWaarde
1o
2x
3y
4e

Als je dan zorgt voor de volgende omzetting van de virtuele naar physieke adressen (ook wel mapping genoemd), kun je in het virtuele geheugen opeens de naam van deze site lezen!
Virtueel AdresPhysiek adresWaarde
13y
24e
32x
41o

Je zou er natuurlijk ook voor kunnen zorgen dat je een heel ander woord leest op virtueel adres 1 tot en met 4, of zelfs hetzelfde woord op een ander virtueel adres. Hoe je aan de processor doorgeeft welk virtueel adres naar welk physiek adres verwijst leg ik in een volgend bericht uit.
01 april 2006

Variabel aantal argumenten voor functie

Functies met een variabel aantal argumenten kunnen erg handig zijn, bijvoorbeeld voor printf. Het eerste argument voor printf is een zogenaamde format string, een tekst waarin met speciale codes staat aangegeven op welke plaats de argumenten moeten worden ingevoegd. Deze codes zijn:

%c
In plaats hiervan wordt een character ingevoegd.
%s
In plaats hiervan wordt een string (tekenreeks) ingevoegd.
%d
Hier komt een decimaal getal te staan.
%x
Hier komt een hexadecimaal getal te staan.
Je zou de functie printf dus als volgt kunnen gebruiken: printf("%d %c %d = %x",8,'+',8,8+8);Dit geeft dan de volgende uitvoer:8 + 8 = 0x10Om zelf een print functie te schrijven voor een kernel moeten we eerst een paar macros maken. De kprintf functie moet namelijk wel de argumenten een voor een op kunnen vragen.

Een functie met een variabel aantal argumenten definieer je als volgt:void kprintf(char *str, ... );In de functie moet je daarna een aantal macros gebruiken om de argumenten op te vragen. Let erop dat de functie alleen weet hoeveel argumenten er doorgegeven worden als hij dat af kan lijden uit de string. Je hebt de volgende macros nodig:typedef struct {
void **ptr;
} va_list;

#define va_start( ap, lastarg ) ap.ptr = (void**)( (unsigned int)&lastarg + sizeof(void**) );


#define va_arg( ap, type) ((type)*(ap.ptr)); ap.ptr = (void**)( ((unsigned int)ap.ptr) + sizeof( unsigned long ) );

#define va_end( ap ) ap.ptr = NULL;
De functie kprintf kan er daarna bijvoorbeeld zo uitzien:void kprintf(char *text, ...){
va_list ap;
va_start(ap, text);
char *tp = text;
while( *tp != '\0' ){
if( *tp == '%' ){
*tp++;
unsigned long temp = va_arg(ap, unsigned long);
switch(*tp){
case 'c':
putch((char)temp);
break;
case 's':
kprintString((char*)temp);
break;
case 'd':
kprintInt(temp);
break;
case 'f':
kprintFloat((float)temp);
break;
case 'x':
kprinthex(temp);
break;
}
}
else {
putch(*tp);
}
*tp++;
}
va_end(ap);
}
Vergeet niet de functies te implementeren waarvan kprintf afhankelijk is, dus kprinthex, kprintString enz.