Eigene Betriebssystementwicklung am PC  -  Teil 2

Stand 02.08.2009 - Dr. Erhard Henkes      

Teil 1    Teil 3

Inhaltsübersicht

Einleitung

Teil 1 dieses Tutorials führte in die Entwicklung eines eigenen Betriebssystems mit MS Windows als Host System und z.B. Bochs als Emulator. Hierzu gehört das Booten, das Umschalten nach Protected Mode und der Sprung zu einem Kernel, der im Falle von PrettyOS in C geschrieben wurde. Es gibt auch andere geeignete Programmiersprachen. Da das Zusammenspiel von C und Assembler jedoch nahtlos funktioniert, bleibe ich bei dieser Sprache.

Bildschirmausgaben und Tastatureingaben können bereits verarbeitet werden. Die Interrupt-Technik wurde eingeführt. Der System Timer liefert ein periodisches Signal, das uns als IRQ0 zur Verfügung steht. Später kann man dieses Signal für die Steuerung des Task Switch im Rahmen von Multitasking verwenden.

In diesem zweiten Teil wird nun ausgehend von dieser Basis PrettyOS weiter entwickelt, um wesentliche Elemente der OS-Entwicklung darzustellen. Ziel ist es, die Zusammenhänge darzustellen und Anregungen für eigene Experimente zu geben.

Dieses Skript wird in den nächsten Wochen/Monaten vielfach geändert/erweitert werden. Der jeweils aktuellste funktionierende Test-Sourcecode (in seinen letzten Erweiterungen evtl. noch nicht im Tutorial beschrieben, da er diesem voraus eilt) befindet sich hier: Aktuellste Testversion


"Die Software wird schneller langsamer als die Hardware schneller" (Erhard Henkes, damals IT-Verantwortlicher in einem großen Bereich, ca. 1990)
Vater: "Wie lädt man eigentlich ein Programm und führt es aus?" Sohn: "Doppelklick - einfach Doppelklick"


Key Queue und Key Handler

Unser Key Handler ist auf dem besten Weg den PC in eine elektrische Schreibmaschine zu verwandeln. Hier stellt sich die kritische Frage, was gehört wirklich zum Kernel dazu und was sollte extern, also im Nicht-Kernel Mode, z.B. im User Mode, ablaufen. Die theoretische Antwort lautet: Man soll den Kernel schlank halten. "Lean" ist also angsagt. Die Praxis zeigt jedoch, dass sich im Rahmen der Anpassung an praktische Bedürfnisse vieles in den Kernel hinein schleicht, was Theoretiker lieber draußen sehen würden. Dies hat vor allem Geschwindigkeitsgründe, denn "die Software wird schneller langsamer als die Hardware schneller", und dies muss ja nicht gerade für das OS selbst auch noch gelten.

Auf jeden Fall sollte unser Key Handler "abgemagert" werden. Er wird die Daten abholen und diese in einer Queue (First In First Out) speichern. Dort können die "Anwendungen" sich ihre Daten abholen. Das ist wie ein großer zentraler Postkasten in einer Firma. Allerdings halten wir den "Postkasten" klein, denn es macht wenig Sinn, wenn nach dem letzten Tastenanschlag noch Hunderte von Tastenanschlägen aus dem Postkasten auf den Bildschirm rieseln. Ein zeitnaher Zusammenhang zwischen Tastenanschlag und Wirkung sollte gegeben sein.

Wo platzieren wir diese FIFO-Queue, wir nennen diese ab jetzt Key Queue (KQ)? Dafür schaffen wir eine zentrale Struktur in PrettyOS, die wir Operating System Data Area (ODA) nennen. Dort können wir Daten ablegen, auf die wir von vielen Modulen zugreifen möchten.

Hier die Strukturen und Funktionsdeklarationen in os.h:

Die eigentliche KeyQueue ist als zirkularer Queue Buffer eingerichtet. Das heißt, wenn wir am Ende angelangt sind, machen wir am Kopf  weiter.
Wir benötigen einen Zeiger auf die vorderste Information (Head) und einen Zeiger auf die hinterste (Tail). Da sich head und tail durch die Zirkularität überholen können, benötigen wir noch eine Schreib-Lese-Zählung, die darüber wacht, wieviele Daten von der KQ gelesen und wieviele in diese geschrieben wurden. Damit können wir unsere KQ vollständig überwachen und betreiben. Die Zahl der Zeichen begrenzen wir auf 20.

Folgenden Code findet man nun in os.h:

typedef struct oda
{
    // Hardware Data
    ULONG COM1, COM2, COM3, COM4; // address
    ULONG LPT1, LPT2, LPT3, LPT4; // address
    ULONG Memory_Size;            // Memory size in Byte

    // Key Queue
    UCHAR  KEYQUEUE[KQSIZE];   // circular queue buffer
    UCHAR* pHeadKQ;            // pointer to the head of valid data
    UCHAR* pTailKQ;            // pointer to the tail of valid data
    ULONG  KQ_count_read;      // number of data read from queue buffer
    ULONG  KQ_count_write;     // number of data put into queue buffer
}oda_t;

// operatings system common data area
oda_t ODA;
extern oda_t* pODA;
extern void initODA();
extern void keyboard_install();
extern void keyboard_init();
extern UCHAR FetchAndAnalyzeScancode();
extern UCHAR ScanToASCII();
extern void keyboard_handler(struct regs* r);
extern int k_checkKQ_and_print_char();

Darüber hinaus bereinigen wir auch die Strukturen in keyboard.c, so dass ein möglichst schlanker Prozess resultiert. Als kleine Demoanwendung haben wir die Funktion  k_checkKQ_and_print_char() realisiert, die Zeichen aus der KQ abholt und auf den Bildschirm ausgibt. Was mit den Zeichen später passieren soll, sehen wir am besten, wenn echte Anwendungen laufen und Tastenanschläge verarbeiten sollen. Erst dann kümmern wir uns wieder ernsthaft um den Postkasten.

#include "keyboard.h"
#include "os.h"

UCHAR ShiftKeyDown = 0; // Variable for Shift Key Down
UCHAR KeyPressed   = 0; // Variable for Key Pressed
UCHAR scan         = 0; // Scan code from Keyboard

/* Wait until buffer is empty */
void keyboard_init()
{
    while( inportb(0x64)&1 )
        inportb(0x60);
};

UCHAR FetchAndAnalyzeScancode()
{
    if( inportb(0x64)&1 )
        scan = inportb(0x60);   // 0x60: get scan code from the keyboard

    // ACK: toggle bit 7 at port 0x61
    UCHAR port_value = inportb(0x61);
    outportb(0x61,port_value |  0x80); // 0->1
    outportb(0x61,port_value &~ 0x80); // 1->0

    if( scan & 0x80 ) // Key released? Check bit 7 (10000000b = 0x80) of scan code for this
    {
        KeyPressed = 0;
        scan &= 0x7F; // Key was released, compare only low seven bits: 01111111b = 0x7F
        if( scan == KRLEFT_SHIFT || scan == KRRIGHT_SHIFT ) // A key was released, shift key up?
        {
            ShiftKeyDown = 0;    // yes, it is up --> NonShift
        }
    }
    else // Key was pressed
    {
        KeyPressed = 1;
        if( scan == KRLEFT_SHIFT || scan == KRRIGHT_SHIFT )
        {
            ShiftKeyDown = 1; // It is down, use asciiShift characters
        }
    }
    return scan;
}

UCHAR ScanToASCII()
{
    UCHAR retchar;                       // The character that returns the scan code to ASCII code
    scan = FetchAndAnalyzeScancode();    // Grab scancode, and get the position of the shift key

    if( ShiftKeyDown )
        retchar = asciiShift[scan];      // (Upper) Shift Codes
    else
        retchar = asciiNonShift[scan];   // (Lower) Non-Shift Codes

    if( ( !(scan == KRLEFT_SHIFT || scan == KRRIGHT_SHIFT) ) && ( KeyPressed == 1 ) ) //filter Shift Key and Key Release
        return retchar; // ASCII version
    else
        return 0;
}

void keyboard_handler(struct regs* r)
{
   UCHAR KEY = ScanToASCII();
   if(KEY)
   {
       *(pODA->pTailKQ) = KEY;
       ++(pODA->KQ_count_write);

       if(pODA->pTailKQ > pODA->KEYQUEUE)
       {
           --pODA->pTailKQ;
       }
       if(pODA->pTailKQ == pODA->KEYQUEUE)
       {
           pODA->pTailKQ = (pODA->KEYQUEUE)+KQSIZE-1;
       }
   }
}

int k_checkKQ_and_print_char()
{
   if(pODA->KQ_count_write > pODA->KQ_count_read)
   {
       UCHAR KEY = *(pODA->pHeadKQ);
       ++(pODA->KQ_count_read);

       if(pODA->pHeadKQ > pODA->KEYQUEUE)
       {
           --pODA->pHeadKQ;
       }
       if(pODA->pHeadKQ == pODA->KEYQUEUE)
       {
           pODA->pHeadKQ = (pODA->KEYQUEUE)+KQSIZE-1;
       }

       restore_cursor();
       switch(KEY)
       {
           case KINS:
               break;
           case KDEL:
               move_cursor_right();
               putch('\b'); //BACKSPACE
               break;
           case KHOME:
               move_cursor_home();
               break;
           case KEND:
               move_cursor_end();
               break;
           case KPGUP:
               break;
           case KPGDN:
               break;
           case KLEFT:
               move_cursor_left();
               break;
           case KUP:
               break;
           case KDOWN:
               break;
           case KRIGHT:
               move_cursor_right();
               break;
           default:
               printformat("%c",KEY); // the ASCII character
               break;
       }
       save_cursor();
       return 1;
   }
   return 0;
}

void keyboard_install()
{
    /* Installs 'keyboard_handler' to IRQ1 */
    irq_install_handler(1, keyboard_handler);
    keyboard_init();
}

Konzentrieren wir uns auf den keyboard handler, der nun wirklich schlank ist:

void keyboard_handler(struct regs* r)
{
   UCHAR KEY = ScanToASCII();

Wir holen eine Information aus der Tastatur und legen diese in der Variable KEY ab. Sobald diese ungleich null ist gelangt diese an die hinterste Stelle (Tail) der KQ. Wir erhöhen unseren Schreibzähler:

   if(KEY)
   {
       *(pODA->pTailKQ) = KEY;
       ++(pODA->KQ_count_write);

Solange der Wert des Tail-Zeigers größer ist als der Anfang der KQ (pODA->KEYQUEUE), wird der Tail-Zeiger erniedrigt.

       if(pODA->pTailKQ > pODA->KEYQUEUE)
       {
           --pODA->pTailKQ;
       }

Sobald allerdings der Anfang erreicht ist, setzt der Zirkularmechanismus ein. Der Tail-Zeiger wird auf das hintere Ende der KQ (pODA->KEYQUEUE)+ KQSIZE-1  gesetzt. Damit ist der Kreis geschlossen.

       if(pODA->pTailKQ == pODA->KEYQUEUE)
       {
           pODA->pTailKQ = (pODA->KEYQUEUE)+ KQSIZE-1;
       }
   }
}

Der Head-Zeiger und Lesezähler kommen genau auf der anderen Seite, nämlich beim Lesen aus der KQ ins Spiel:

int k_checkKQ_and_print_char()
{
  
Solange mehr in die KQ hinein geschrieben als heraus gelesen wurde - also solange noch etwas im Postkasten liegt - lesen wir weiter. Der "Lesekopf" befindet sich beim Head-Zeiger. Der Lesezeiger zählt mit, damit wir keine "ungültigen" Zeichen heraus holen.

   if(pODA->KQ_count_write > pODA->KQ_count_read)
   {
       UCHAR KEY = *(pODA->pHeadKQ);
       ++(pODA->KQ_count_read);

Auch hier müssen wir - wie oben - den Zirkularmechanismus beachten. Solange der Kopf-Zeiger oberhalb des Anfangs der KQ liegt, bewegen wir uns auf diesen zu. Sobald wir ihn erreichen, erfolgt ein Sprung ans andere Ende, genau wie beim Schreiben.

       if(pODA->pHeadKQ > pODA->KEYQUEUE)
       {
           --pODA->pHeadKQ;
       }
       if(pODA->pHeadKQ == pODA->KEYQUEUE)
       {
           pODA->pHeadKQ = (pODA->KEYQUEUE)+ KQSIZE-1;
       }

Damit unsere KQ einen sauberen Einstieg hat, definieren wir uns in der neuen Datei os.c (im makefile ergänzen), die wir zukünftig für OS-spezifische Dinge nutzen wollen, einen Zeiger auf ODA und eine Funktion ODA_install:

#include "os.h"

oda_t* pODA = &ODA;

void ODA_install()
{
    int i;
    for(i=0;i<KQSIZE;++i)
       pODA->KEYQUEUE[i]=0;          // circular queue buffer
    pODA->pHeadKQ = pODA->KEYQUEUE;  // pointer to the head of valid data
    pODA->pTailKQ = pODA->KEYQUEUE;  // pointer to the tail of valid data
    pODA->KQ_count_read  = 0;        // number of data read from queue buffer
    pODA->KQ_count_write = 0;        // number of data put into queue buffer
}

Zur Demonstration dieses wichtigen Werkzeuges, dass man gleichartig auch für andere FIFO-Mechanismen verwenden kann, schreiben wir uns in main() eine kleine Routine:

#include "os.h"

int main()
{
    k_clear_screen();
    gdt_install(); idt_install(); isrs_install(); irq_install(); ODA_install;
    timer_install(); keyboard_install();
    sti();

    set_cursor(0,0);
    printformat("   ************************************************\n");
    printformat("   *           Welcome to PrettyOS                *\n");
    printformat("   *           Demo of the Key Queue              *\n");
    printformat("   ************************************************\n");

    // demo of the Key Queue (KQ)
    settextcolor(2,0);
    UCHAR c=0;
    while(TRUE)
    {
      if( k_checkKQ_and_print_char() )
      {
        ++c;
        if(c>5)
        {
          c=0;
          settextcolor(4,0);
          printformat("\nT: %x H: %x WRITE: %i Read: %i ",
          pODA->pTailKQ, pODA->pHeadKQ, pODA->KQ_count_write, pODA->KQ_count_read);
          printformat("*T: %c %i *H: %c %i\n",
          *(pODA->pTailKQ),*(pODA->pTailKQ),*(pODA->pHeadKQ),*(pODA->pHeadKQ));
          settextcolor(2,0);
        }
      }
    }
    return 0;
};

Auf dem Bildschirm können wir die Wirkung der Key Queue transparent verfolgen.




Speicher Management

Die Verwaltung des Speichers gehört zu den wichtigsten Aufgaben eines Betriebssystems. Hier finden sich Code, Daten und Verwaltungsstrukturen (z.B. Tabellen mit Zeigern auf Speicherbereiche) in geordneten Strukturen wie Kernel, Stacks, Heaps, Tasks, etc.

Physical Memory Management (PMM)

Bezüglich des Speichermanagements gibt es drei typische Prozesse:
1) Speicher belegen
2) Speicher frei geben
3) Speicher testen

Für die Anzeige der "Belegung" des Speichers werden wir ein Bit Array (auch Bitset oder Bitmap genannt) verwenden, um den Speicher möglichst effizient einzusetzen. Im Vorgriff auf das Paging verwenden wir sogenannte "Frames" (zusammenhängende Speicherbereiche) von 4096 Bytes = 4 KB.
Bei Belegung eines Frames setzen wir im Bit Array eine 1, bei Freigabe/Nichtbelegung eine 0. Das Testen erfolgt dann als Prüfung auf 0 oder 1 im Bit Array.

Für das physische Speichermanagement (pmm) verwenden wir folgende Funktionen und Variablen:

// A bitset of frames - used or free
ULONG   NFRAMES = (PHYSICAL_MEMORY/PAGESIZE);
ULONG*  frames; // pointer to the bitset (functions: set/clear/test)
ULONG   ind, offs;

static void get_Index_and_Offset(ULONG frame_addr)
{
    ULONG frame = frame_addr/PAGESIZE;
    ind         = frame/32;
    offs        = frame%32;
}

static void set_frame(ULONG frame_addr)
{
    get_Index_and_Offset(frame_addr);
    frames[ind] |= (1<<offs);
}

static void clear_frame(ULONG frame_addr)
{
    get_Index_and_Offset(frame_addr);
    frames[ind] &= ~(1<<offs);
}

static ULONG test_frame(ULONG frame_addr)
{
    get_Index_and_Offset(frame_addr);
    return( frames[ind] & (1<<offs) );
}

static ULONG first_frame() // find the first free frame in frames bitset
{
    ULONG index, offset;
    for(index=0; index<(NFRAMES/32); ++index)
    {
        if(frames[index] != ULONG_MAX)
        {
            for(offset=0; offset<32; ++offset)
            {
                if( !(frames[index] & 1<<offset) ) // bit set to zero?
                    return (index*32 + offset);
            }
        }
    }
    return ULONG_MAX; // no free page frames
}

static void bitset_install()
{
    frames = (ULONG*) k_malloc( NFRAMES/32, 0, 0 );
    k_memset( frames, 0, NFRAMES/32 );
}



Die Funktionen set/clear/test_frame(address) setzen/löschen/testen das Bit Array an der entsprechenden Stelle.
Den ersten nicht belegten Frame findet man mit first_frame().
Die Funktion bitset_install() implementiert mittels k_malloc(...) das Bit Array frames[...].

k_malloc( size, align, phys )

Zur Implementierung des Bit Array frames[ind] benötigen wir bereits die Funktion k_malloc(...), die uns einen festen Platz im Speicher für die Verwaltung der Frames zuweist. Diese Funktion wurde zur Demonstration wie folgt umgesetzt:

#define PAGESIZE          0x00001000     // 0x1000 = 4096 = 4K
ULONG placement_address = 0x00200000;

ULONG k_malloc(ULONG size, UCHAR align, ULONG* phys)
{
    // later on, there will be the heap code

    if( align == 1 )
    {
        if( !(placement_address == (placement_address & 0xFFFFF000) ) )
        {
            placement_address &= 0xFFFFF000;
            placement_address += PAGESIZE;
        }
    }
    if( phys )
    {
        *phys = placement_address;
    }

    ULONG temp = placement_address;
    placement_address += size;     // new placement_address is increased
    return temp;                   // old placement_address is returned
 }

Später wird k_malloc mit dem Heap zusammen arbeiten, sobald dieser existiert. Momentan bietet die Funktion uns nur das "Hochschieben" der (memory) placement_address. Aber das ist momentan genau das, was wir benötigen, um unsere ersten Strukturen hinter dem selbst gesetzten Ende (z.B. ab 0x200000) selbst zu platzieren und vor dem Überschreiben zu bewahren. Mit  bitset_install() platzieren wir das frames-Array für die physische Verwaltung des Speichers.

k_malloc() in der jetzigen Ausbaustufe startet mit einer (memory) placement_address und verschiebt diese um die Größe (size) des zu allokierenden Speicherbereichs nach oben. Als Rückgabewert der Allokierungs-Funktion gibt man die vorherige placement_address zurück. Damit vermeidet man eine Doppelbelegung des Speicherbereichs. Dieser Mechanismus macht natürlich nur Sinn für Daten, die man nicht mehr frei geben, also dauerhaft allokieren, möchte. Ein wichtiger Punkt hierbei ist das "alignment" auf die 4KB-Grenzen der Frames:

    if( align == 1 )
    {
        if( !(placement_address == (placement_address & 0xFFFFF000) ) )
        {
            placement_address &= 0xFFFFF000;
            placement_address += PAGESIZE;
        }
    }

Hierbei wird abgefragt, ob die alte placement_address eine bezüglich Einheiten von 0x1000 (später PAGESIZE) "runde" Zahl ist oder nicht.
Falls nein, wird diese zunächst abgerundet und anschließend um 0x1000 erhöht, damit es zu keiner Überlappung kommt!

Damit wir zwischen physischer und virtueller Adresse unterscheiden können, wurde dieser Mechanismus bereits in die Funktion eingebaut.
Später kommt noch der Heap (Freispeicher) als dynamischer Speicherbereich für wechselnde Daten hinzu.

Verlassen wir die physische Ebene und wenden uns nun dem virtuellen Abbild zu. Wir arbeiten in der Realität moderner Betriebssysteme immer mit diesen zwei Ebenen. Der Benutzer sieht die virtuelle Ebene, das OS kümmert sich um die Verbindung zwischen diesen beiden, damit keine Daten verloren gehen.

Virtual Memory Management (VMM)

Der Prozess einer virtuellen Speicherallokierung läuft typischerweise nach folgendem Code-Schema ab:

ULONG physical_address;
ULONG virtual_address = memory_alloc( size, align, &physical_address );
printformat ( "phys: %x, virt: %x\n" , physical_address, virtual_address );

Man unterscheidet also zwischen einer virtuellen Adresse, die sich im theoretischen Speicherraum befindet, und einer physischen Adresse, die sich im tatsächlich vorhandenen RAM oder auf einem Speichermedium wie z.B. einer Festplatte befindet.

Virtueller Speicher und Swapping

Die Technik des virtuellen Speichers wurde 1956 von dem deutschen Computer-Pionier Fritz-Rudolf Güntsch entwickelt. Dieses Konzept hat sich bei modernen OS als grundlegend und wegweisend durchgesetzt. Daher sollte auch PrettyOS dieses Konzept umsetzen. Um was geht es hierbei eigentlich?

Das Ziel besteht darin, schnellen Speicher (heute RAM) mit weniger schnellem dafür aber großem Speicher (z.B. Festplatte) zu "mischen", ohne dass die Anwendung dies als negativ empfindet (Kompromiss zwischen ausreichend Speicherplatz und Lese-/Schreib-Geschwindigkeit). Das sogenannte "swapping" wurde von Microsoft bei Windows 95 bzw. Windows 98 eingeführt und war ein richtiges Lebenselixier für MS Windows. Vielleicht damals der entscheidende Schritt! Die "Swap-Datei" auf der Festplatte assistiert, wenn der Arbeitsspeicher im RAM nicht mehr ausreicht. Dann werden auf intelligente Weise Daten hin und her geswappt. Eigentliche Ursache für diese Technik war die Einführung von Multitasking. Dieses ermöglicht das parallele Verarbeiten mehrerer gleichzeitig geöffneter komplexer Anwendungen. Das optimale Swapping kann das Leistungspotential des Computers erhöhen, und es gibt viele Artikel über die optimale Größe der "Swap-Datei". Entscheidend ist, dass der Prozess beim Paging nicht wissen muss, wohin er wirklich "greift", sondern eine virtuelle Speicherlandschaft als gegeben akzeptiert. Das schafft auf jeden Fall eine enorme Flexibilität bezüglich der physischen Realisierung und Nutzung des vorhandenen flüchtigen oder persistenten Speichers.


Heute sind gegenüber zehn bis fünfzehn Jahren beindruckende RAM-Volumen darstellbar. Mehrere Gigabyte sind kein Problem, und die Zukunft wird hier weitere Fortschritte bezüglich der Hardware bringen. Dennoch ist bedingt durch Multitasking und Swapping die Technik des virtuellen Speicher-Managements bei modernen Betriebssystemen noch immer übliche Praxis.

Paging

Der Begriff "Paging" bezeichnet den Vorgang der Abbildung (Mapping) von virtuellen Adressen auf physische Adressen. Programmcode oder Daten befinden sich in diesem Umfeld also gleichzeitig an einer physischen und einer virtuellen Adresse. Beide können hierbei deckungsgleich (identisch) sein oder verschieden (wichtig für das swapping). 

Bei einem 32-Bit-Prozessor umfassen die theoretisch möglichen Adressen insgesamt 4 GB = 232 Byte. Die Realisierung des Pagings erfolgt durch Zerlegung dieses Adressraums in viele kleine "Pages" (Seiten). Die Verwaltung erfolgt durch das Page Directory Base Register (PDBR), das als "Kontrollregister cr3" geführt wird.

Baumstrukturen von Tabellen und Zeigern (Adressvariablen) führen über das Page Directory (PD) und Page Tables (PT) zu Pages weiter, die mit Hilfe des Offsets in einer konkreten physischen Adresse münden (siehe Bild unten). Eine hervorragende Darstellung dieser Zusammenhänge mit ausführlichen Erklärungen und einem konkreten Rechenbeispiel findet sich hier.

Bei der Entwicklung des Sourcecodes für das Memory Management habe ich mich vom Tutorial von James Molloy aus dem Jahre 2008 leiten lassen (er verwendet allerdings GRUB als Bootloader). Einige Teile seines Codes verwende ich mit seiner Erlaubnis - jedoch nur soweit effizient und transparent - in modifizierter Form,  um das Rad nicht immer wieder neu zu erfinden. Die Lektüre des Tutorials von James Molloy, das in den vorderen Kapiteln auf einem älteren Skript - Bran's Tutorial - basiert, ist daher als ergänzende Lektüre zu empfehlen.

Das Paging ist eine Erweiterung der virtuellen Adressierung, die im Protected Mode mit der GDT als "Zeigertabelle" begonnen hat.
Der tatsächliche Zugriff auf eine physische Adresse wird nach Einschalten des "Paging-Modus" mittels

asm volatile("mov %0, %%cr3":: "r"(&kernel_directory->tablesPhysical));
ULONG cr0;
asm volatile("mov %%cr0, %0": "=r"(cr0));
cr0 |= 0x80000000;                        // Enable paging
asm volatile("mov %0, %%cr0":: "r"(cr0));

durch die MMU der CPU gesteuert:

Die Gliederung im Rahmen der 32-Bit-Adressierung erfolgt in nachstehender Baumstruktur:
Page Directory (PD)
 10 Bit  zeigt auf 1024 ( = 210 ) Page Tables
Page Table (PT)
 10 Bit  zeigt auf 1024 ( = 210 ) Pages
Page 12 Bit Offset  zeigt auf eine spezifische Adresse innerhalb der 4 KByte (212 Byte) umfassenden Page

Wir werden die klassische Aufteilung in Page Sizes von 4 KB bei behalten. Ab dem Pentium-Prozessor sind auch Page Sizes von 2 oder 4 MB möglich.


Die nachfolgende Grafik findet man in Intel's Manual 3A auf Seite 3-26:



Quelle: "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1"

Diese Handbücher zählen nach einhelliger Meinung zu den wichtigsten Unterlagen für die eigene OS-Entwicklung, da hier direkt vom Prozessoren-Hersteller die Zusammenhänge, Abläufe und Randbedingungen beschrieben sind. Sie stehen seitens Intel frei zum Download zur Verfügung und gehören in die eigene OSDEV-Bibliothek.

In das Kontrollregister cr3 wird die physische Adresse des Page Directory (PD) vor dem Einschalten des Paging Flag im cr0 (s.o.) transferiert:

// cr3: PDBR (Page Directory Base Register)
asm volatile( "mov %0, %%cr3" : : "r"(kernel_directory->physicalAddr) );

Die Page Directory Entries (PDE) verweisen auf die Basis-Adresse von insgesamt maximal 1024 Page Tables (PT).
Die Page Table Entries (PTE) verweisen wiederum auf die Basis-Adresse von insgesamt maximal 1024 Pages mit einer Größe von jeweils 4 KB.

Aus Sicht eines einzelnen Page Directory kann es somit 232 Adressen, 220 Pages, 210 Page Tables geben. Allerdings kann man mehrere Page Directory erstellen und z.B. bei einem Taskwechsel mittels Register cr3 tauschen. Verschiedene PDE können auch auf die gleiche PT zeigen.

Diese Baumstruktur  page_directory.tablesPhysical ==> page_table ==> pages ==> frame  wird in PrettyOS mittels folgender C-Structs repräsentiert:
// page_directory ==> page_table ==> page
typedef struct page
{
    ULONG present    :  1;   // 0: swapped out,       1: page present in memory
    ULONG rw         :  1;   // 0: read-only,         1: read/write
    ULONG user       :  1;   // 0: supervisor level,  1: user level
    ULONG accessed   :  1;   // Has the page been accessed since last refresh?
    ULONG dirty      :  1;   // Has the page been written to since last refresh?
    ULONG unused     :  7;   // Combination of unused and reserved bits
    ULONG frame      : 20;   // Frame address (shifted right 12 bits)
} page_t;

typedef struct page_table
{
    page_t pages[1024];
} page_table_t;

typedef struct page_directory
{
    ULONG tablesPhysical[1024]; //PDE
    page_table_t* tables[1024];
    ULONG physicalAddr;
} page_directory_t;

Die PDE befinden sich an der Stelle der tablesPhysical[1024]. Die physicalAddr erhalten wir, wenn wir die PD anlegen. Da es sich bei tablesPhysical[1024] um virtuelle Adressen handelt, müssen wir die physische Adresse extra speichern, weil wir diese für cr3 benötigen.

Zum Verständnis des Paging-Prozesses sollten wir gesitig trennen zwischen dem Physical Memory Management (PMM), das durch das Frames-Bitset mit seinen zugehörigen Verwaltungsfunktionen (in der Abb. in blau) implementiert wird, und dem Virtual Memory Management (VMM), das durch das eigentliche Paging realisiert wird. Das Mapping zwischen Pages (virtuelle Adressen) und Frames (physische Adressen) erfolgt durch die beiden Funktionen alloc_frame und free_frame. Die Funktionen paging_install, get-page und set_page (in der Abb. in rot) sorgen für das Erstellen/Freigeben bzw. Testen von paging-Strukturen:



Zunächst die Implementierungs-Funktion  paging_install() in der Übersicht:
void paging_install()
{
    bitset_install();

    printformat("make a page directory:\n");
    ULONG phys;
    kernel_directory = (page_directory_t*) k_malloc( sizeof(page_directory_t), 1, &phys );
    k_memset(kernel_directory, 0, sizeof(page_directory_t));
    kernel_directory->physicalAddr = phys;

    printformat("map phys addr to virt addr from 0x0 to the end of used memory:\n");
    ULONG counter=0, i=0;
    while( i < (placement_address) )
    {
        page_t* page = set_page(i, kernel_directory);
        alloc_frame( page, 0, 0 );
        i+=PAGESIZE; ++counter;
    }

    printformat("\nINFO from paging_install():\n");
    printformat("frames: %x\n", frames);
    printformat("kernel_directory->phys: %x\n", kernel_directory->physicalAddr);
    printformat("placement_address: %x allocated frames: %x\n\n", placement_address, counter);

    // cr3: PDBR (Page Directory Base Register)
    asm volatile( "mov %0, %%cr3" : : "r"(kernel_directory->physicalAddr) );

    // read cr0, set paging bit, write cr0 back
    ULONG cr0;
    asm volatile("mov %%cr0, %0": "=r"(cr0)); // read cr0
    cr0 |= 0x80000000; // set the paging bit in CR0 to enable paging
    asm volatile("mov %0, %%cr0":: "r"(cr0)); // write cr0
}

In ckernel.c verwenden wir folgenden Code:
#include "os.h"
#include "paging.h"

int main()
{
    k_clear_screen();
    gdt_install(); idt_install();
    isrs_install(); irq_install(); ODA_install();
    sti();
    timer_install();
    keyboard_install();
    paging_install();
    set_cursor(0,0);
    sleepSeconds(10);
    analyze_frames_bitset(3);

    return 0;
};

Bildschirmausdrucke von Bochs (mit copy):

setup bitset:          
old: 00200000h sz: 00002000h a: 0 new: 00202000h
make a page directory: 
old: 00202000h sz: 00002004h a: 1 new: 00204004h
map phys addr to virt addr from 0x0 to the end of used memory:
?old: 00205000h sz: 00001000h a: 1 new: 00206000h
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
INFO from paging_install():
frames: 00200000h
kernel_directory->phys: 00202000h
placement_address: 00206000h allocated frames: 00000206h		 Man startet bei 00200000h.
bitset_install() liefert frames[...].

Page Directory wird erstellt.

Ein Frame wird noch neu allokiert (?),
517 Frames sind bereits allokiert (!).




Insgesamt sind 518 (206h) Frames je 4KB (1000h) von 0h bis 206000h allokiert. Die frames-Verwaltung (bitset) beginnt ab 200000h.

00000000h  11111111111111111111111111111111
00020000h  11111111111111111111111111111111
00040000h  11111111111111111111111111111111
00060000h  11111111111111111111111111111111
00080000h  11111111111111111111111111111111
000A0000h  11111111111111111111111111111111
000C0000h  11111111111111111111111111111111
000E0000h  11111111111111111111111111111111
00100000h  11111111111111111111111111111111
00120000h  11111111111111111111111111111111
00140000h  11111111111111111111111111111111
00160000h  11111111111111111111111111111111
00180000h  11111111111111111111111111111111
001A0000h  11111111111111111111111111111111
001C0000h  11111111111111111111111111111111
001E0000h  11111111111111111111111111111111
00200000h  11111100000000000000000000000000
00220000h  00000000000000000000000000000000
00240000h  00000000000000000000000000000000
00260000h  00000000000000000000000000000000
00280000h  00000000000000000000000000000000
002A0000h  00000000000000000000000000000000
002C0000h  00000000000000000000000000000000
002E0000h  00000000000000000000000000000000
Hier erhält man auf einfache Weise eine Übersicht über das Frames-Bitset.

Im nachstehenden Sourcecode gibt alloc_frame übrigens die Nummer des Pageframes zurück, die man zur Kontrolle entsprechend anzeigen kann.


Eine Basis für eine Untersuchung des Zusammenhangs der Daten in cr3, PD und PT liefert folgende kleine Analyse-Funktion:

void analyze_PD_PT_Pages(ULONG PDE, ULONG PTE, page_directory_t* dir)
{
    k_clear_screen();
    ULONG cr3;
    asm volatile("mov %%cr3, %0": "=r"(cr3)); // read cr3
    printformat( "PDBR cr3:       %x\n", cr3 );
    printformat( "PD phys. addr.: %x\n", dir->physicalAddr );

    int i,j;
    for(i=0;i<PDE;++i)
    {
        printformat( "  PDE %d: phys: %x virt: %x\n", i, dir->tablesPhysical[i]&0xFFFFF000, dir->tables[i] );
        for(j=0;j<PTE;++j)
        {
            printformat( "    PTE %d: addr: %x frame-addr: %x\n", j,
                                &(dir->tables[i]->pages[j]),
                         (ULONG)( dir->tables[i]->pages[j].frame_addr)<<12
                       );
        }
    }
}

Setzt man in ckernel.c folgende Zeile ein:

analyze_PD_PT_Pages(1,10,kernel_directory);

so erhält man diesen Bildschirmausdruck:

PDBR cr3:       00202000h
PD phys. addr.: 00202000h
  PDE 0: phys: 00205000h virt: 00205000h
    PTE 0: addr: 00205000h frame-addr: 00000000h
    PTE 1: addr: 00205004h frame-addr: 00001000h
    PTE 2: addr: 00205008h frame-addr: 00002000h
    PTE 3: addr: 0020500Ch frame-addr: 00003000h
    PTE 4: addr: 00205010h frame-addr: 00004000h
    PTE 5: addr: 00205014h frame-addr: 00005000h
    PTE 6: addr: 00205018h frame-addr: 00006000h
    PTE 7: addr: 0020501Ch frame-addr: 00007000h
    PTE 8: addr: 00205020h frame-addr: 00008000h
    PTE 9: addr: 00205024h frame-addr: 00009000h

Nun erkennt man auch, warum oben diese Zeile erfolgte: ?old: 00205000h sz: 00001000h a: 1 new: 00206000h

PDBR: Page Directory Base Register
PD:   Page Directory
PDE:  Page Directory Entry (= Virtuelle Adresse einer Page Table)
PTE:  Page Table Entry     (= Virtuelle Adresse einer Page)

Man sieht, dass für eine Page 4 Byte (unsigned long integer) aufgewendet werden. Die Frame-Adresse wird 12 Bit nach links geschoben, weil diese im PTE als ein 12 Bit nach rechts geschobener 20-Bit-Wert abgespeichert ist.

bezüglich des Originalwertes 0x00205027 im Eintrag der PDE-physischen Adresse muss man daran denken, dass nur die linken 20 MSB gewertet werden dürfen. Die zwölf rechten "Bits" stehen für die Kennzeichnung der Eigenschaften der PDE bzw. PTE.

Die 27h = 100111b werden daher bezüglich der Adresse mit der Maske 0xFFFFF000 ausgeblendet. Wofür stehen nun aber die Bits 100111b ? Die Bits stehen für Present (im Speicher), Read/Write, Supervisor (Kernel-Privileg) und Accessed. Die 0 in Bit 7 bedeutet, dass wir 4 KByte Pagesize verwenden.



Quelle: "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1"



Bei den Page Table Entries (PTE) gilt übrigens eine leicht modifizierte Deutung der rechten 12 Bit. Diese Informationen erhält man aus den Intel Manuals:



Quelle: "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1"

Die Bedeutungen der Bits finden sich ausführlich in diesem Intel Manual. Daher führe ich dies hier nicht mehr detailliert aus. Bitte beachten Sie Access und Dirty (letzteres nur bei PTE).


Page Fault

Sollte eine Page Fault (PF) Exception auftreten, so sollte PrettyOS dem Anwender Hinweise geben bezüglich der Ursache des aufgetretenen Fehlers und der angesprochenen Adresse:

void fault_handler(struct regs* r)
{
    if (r->int_no < 32)
    {
        if (r->int_no == 14) //Page Fault
        {
            ULONG faulting_address;
            asm volatile("mov %%cr2, %0" : "=r" (faulting_address)); // faulting address => CR2 register

            // The error code gives us details of what happened.
            int present   = !(r->err_code & 0x1); // Page not present
            int rw        =   r->err_code & 0x2;  // Write operation?
            int us        =   r->err_code & 0x4;  // Processor was in user-mode?
            int reserved  =   r->err_code & 0x8;  // Overwritten CPU-reserved bits of page entry?
            int id        =   r->err_code & 0x10; // Caused by an instruction fetch?

            // Output an error message.
                          printformat("Page Fault (");
            if (present)  printformat("page not present");
            if (rw)       printformat(" read-only - write operation");
            if (us)       printformat(" user-mode");
            if (reserved) printformat(" overwritten CPU-reserved bits of page entry");
            if (id)       printformat(" caused by an instruction fetch");
                          printformat(") at %x - EIP: %x\n", faulting_address, r->eip);
        }
        printformat("%s >>> Exception. System Halted! <<<", exception_messages[r->int_no]);
        for (;;);
    }
}


Wenn wir nun diesen Auswertemechanismus haben, provozieren wir einen Page Fault:
ULONG* pointer = 0xA0000000;
ULONG make_a_page_fault = *pointer;
printformat("make_a_page_fault: %x\n", make_a_page_fault);

... und prompt kommt die Fehlermeldung mit der entsprechenden Information:
Page Fault (page not present) at A0000000h - EIP: 00008576h
Page Fault >>> Exception. System Halted! <<<

Wie Sie sehen erfolgt unser printformat(...) aus ckernel.c nicht mehr.

Wie bestimmt man das Ende des Kernels?

Wenn wir gerade bei Speichermanagement sind: Wie bestimmt man das Ende des Kernels?

Man kann es z.B. selbst berechnen, indem man im hex-Editor das Ende von MyOS.bin sucht, den Bootloader (0x200) abzieht und die Startadresse, an die der Kernel vom Bootloader geladen wird, addiert. Man erhält auf diese Weise das Ende der data-Section des Kernels ohne Berücksichtigung des bss.

Das Linkerscript erlaubt die Bestimmung des Endes exclusive oder inclusive bss.
Nachstehend die Version inclusive bss:

OUTPUT_FORMAT("binary")
ENTRY(RealMode)
phys = 0x00008000;
SECTIONS
{
  .text phys  : {
    *(.text)
  }
  .data  : {
    *(.data)
  }
  .bss : {
    *(.bss)   
  }
  _endkernel = .; 
}

Wie wir die Marke _endkernel in C abfragen, kennen Sie bereits mehrfach aus dem Wechselspiel zwischen Assembler und C:

//os.h
ULONG get_end_kernel(); //delivers end of kernel

//os.c
extern ULONG endkernel;
ULONG get_end_kernel()
{
    return (ULONG) &endkernel; //DON'T FORGET ADDRESS
}

//ckernel.c
int main()
{
    k_clear_screen();
    printformat("end of kernel %x\n", get_end_kernel());
    //...
}

Screen Output:


end of kernel 0000BC00h



Heap

Bisher haben wir Speicher statisch allokiert, d.h. eine Adresse namens placement_address wurde bei jeder Anforderung weiter geschoben. An eine Speicherfreigabe ist nicht mehr zu denken. So kann man natürlich nicht ständig weiter arbeiten, weil irgendwann der gesamte Speicher belegt wäre ohne die Chance einer geordneten Freigabe und Defragmentierung von Speicherbereichen. Hier kommt die dynamische Speicherbelegung ins Spiel. In C kennt man dies als malloc/free und in C++ als new/delete.

Für diese notwendige Funktionalität setzen wir die Heap-Implementierung von James Molloy ein, die auf dem Algorithmus von Doug Lea  basiert. Die Allokierung erfolgt grob nach folgendem Schema:

- Kleinstes Loch ("hole") für die gesuchte Größe in einem geordneten Array suchen. Wenn dies nicht klappt: Heap expandieren etc.
- Loch in zwei Teile zerlegen
- Nicht mehr existentes ursprüngliches Loch vom Index streichen
- Neuen Header und Footer für den allokierten Block schreiben
- Bei der Zweiteilung erzeugtes zweites nicht besetztes Loch in den Index eintragen
- Rückgabe der Adresse des allokierten Blocks plus  sizeof(header_t)

Wir verweisen bezüglich der Details auf die ausführlichen Erklärungen an den beiden Links.
Lassen Sie uns dem praktischen Einsatz zuwenden.

Wir beginnen ganz naiv und schreiben in ckernel.c die Zeile:  kheap = create_heap(...)

#include "os.h"
#include "paging.h"
#include "kheap.h"
#define PAGESIZE  0x1000
extern ULONG placement_address;
extern heap_t* kheap;
extern page_directory_t* kernel_directory;

int main()
{
//...
paging_install();
kheap = create_heap(KHEAP_START, KHEAP_START+KHEAP_INITIAL_SIZE, KHEAP_MAX, 0, 0);

Bochs zeigt folgenden Ablauf, der in einem Page Fault endet:

setup bitset:
old: 00200000h sz: 00002000h a: 0 new: 00202000h

make a page directory:
old: 00202000h sz: 00002004h a: 1 new: 00204004h

map phys addr to virt addr from 0x0 to the end of used memory:
old: 00205000h sz: 00001000h a: 1 new: 00206000h

INFO from paging_install():
frames: 00200000h
kernel_directory->phys: 00202000h
placement_address: 00206000h allocated frames: 00000206h

old: 00206000h sz: 00000020h a: 1 new: 00206020h
k_m of heap_t* heap (size: 32): 00206000h
before k_memset in place_ordered_array(...)
Page Fault (page not present read-only - write operation) at 01000000h - EIP: 00009590h
Page Fault >>> Exception. System Halted! <<<

In kheap.h findet man folgende Details:

#define KHEAP_START         0x01000000
#define KHEAP_INITIAL_SIZE  0x00100000
#define KHEAP_MAX           KHEAP_START + 0x00FFF000

Damit ist klar, dass das Paging im Bereich des angestrebten Heap Bereichs noch nicht tätig wurde. Das ist für den Prozessor noch Sperrgebiet (not present).
Was müssen wir unternehmen, dass die Frames allokiert werden?
Wir müssen  alloc_frame(...) und set_page(...) im Bereich zwischen  KHEAP_START und  KHEAP_MAX aktiv einsetzen:

// Map some pages in the heap area and create kernel heap there
for( i=KHEAP_START; i<KHEAP_MAX; i+=PAGESIZE )
    alloc_frame( set_page(i, kernel_directory), 0, 0);

Das reicht aber leider noch nicht. Diesmal kneift es weiter vorne im Speicher:

old: 00206000h sz: 00001000h a: 1 new: 00207000h
Page Fault (page not present read-only - write operation) at 00206000h - EIP: 000095D0h
Page Fault >>> Exception. System Halted! <<<

Hier müssen wir vorher doch noch einiges an "erlaubtem" Platz für Heap-Strukturen schaffen:

 // Map some pages for the the kernel heap
ULONG i = placement_address, num;
while( i < (placement_address+0x10000) )
{
    page_t* page = set_page(i, kernel_directory);
    num = alloc_frame( page, 0, 0 );
    printformat("alloc_frame: %x\n", num*PAGESIZE);
    i+=PAGESIZE;
}

Nun funktioniert der beabsichtigte Prozess der Heap-Erzeugung bestens, wie man den Bildschirm-Ausdrucken von Bochs entnehmen kann:


setup bitset: old: 00200000h sz: 00002000h a: 0 new: 00202000h
make a page directory: old: 00202000h sz: 00002004h a: 1 new: 00204004h
map phys addr to virt addr from 0x0 to the end of used memory: old: 00205000h sz: 00001000h a: 1 new: 00206000h

... frames: 200000h  kernel_directory->phys: 202000h  placement_address: 206000h  allocated frames: 206h

alloc_frame: 00206000h  alloc_frame: 00207000h  alloc_frame: 00208000h  alloc_frame: 00209000h
alloc_frame: 0020A000h  alloc_frame: 0020B000h  alloc_frame: 0020C000h  alloc_frame: 0020D000h
alloc_frame: 0020E000h  alloc_frame: 0020F000h  alloc_frame: 00210000h  alloc_frame: 00211000h
alloc_frame: 00212000h  alloc_frame: 00213000h  alloc_frame: 00214000h  alloc_frame: 00215000h

old: 00206000h sz: 00001000h a: 1 new: 00207000h
old: 00207000h sz: 00001000h a: 1 new: 00208000h
old: 00208000h sz: 00001000h a: 1 new: 00209000h
old: 00209000h sz: 00001000h a: 1 new: 0020A000h
old: 0020A000h sz: 00000020h a: 1 new: 0020A020h
 
k_m of heap_t* heap (size: 32): 0020A000h

HEAP start: 01081000h end: 01100000h max: 01FFF000h kernel mode: 0 read-only: 0
hole 01081000h hole-size: 0007F000h


  PDE 0: phys: 00205000h virt: 00205000h
    PTE 0: addr: 00205000h frame-addr: 00000000h
    PTE 1: addr: 00205004h frame-addr: 00001000h
    PTE 2: addr: 00205008h frame-addr: 00002000h

     ...

  PDE 4: phys: 00206000h virt: 00206000h
    PTE 0: addr: 00206000h frame-addr: 00216000h
    PTE 1: addr: 00206004h frame-addr: 00217000h
    PTE 2: addr: 00206008h frame-addr: 00218000h

  PDE 5: phys: 00207000h virt: 00207000h
    PTE 0: addr: 00207000h frame-addr: 00616000h
    PTE 1: addr: 00207004h frame-addr: 00617000h
    PTE 2: addr: 00207008h frame-addr: 00618000h

  PDE 6: phys: 00208000h virt: 00208000h
    PTE 0: addr: 00208000h frame-addr: 00A16000h
    PTE 1: addr: 00208004h frame-addr: 00A17000h
    PTE 2: addr: 00208008h frame-addr: 00A18000h
 
  PDE 7: phys: 00209000h virt: 00209000h
    PTE 0: addr: 00209000h frame-addr: 00E16000h
    PTE 1: addr: 00209004h frame-addr: 00E17000h
    PTE 2: addr: 00209008h frame-addr: 00E18000h





Nun verfügen wir über einen Heap-Speicher im Bereich  HEAP start: 01081000h end: 01100000h
Was macht man damit? Man fordert via k_malloc(...) nun dynamischen Speicher im Heap an.

//ckernel.c

ULONG addr, phys;
    addr = k_malloc(0x10000, 1, &phys);
    printformat("addr: %x phys: %x\n", addr, phys);

//kmalloc.c

ULONG k_malloc(ULONG size, UCHAR align, ULONG* phys)
{
    if( kheap!=0 )
    {
        void* addr = alloc(size, align, kheap);
        if (phys != 0)
        {
            page_t* page = get_page((ULONG)addr, kernel_directory);
            *phys = page->frame_addr*PAGESIZE + ((ULONG)addr&0x00000FFF);
        }
        printformat("k_m_heap: %x\n", (ULONG)addr);
        return (ULONG)addr;
    }
    //...
 }

Bochs-Screenshot:


k_m_heap: 01082000h

addr:     01082000h     phys:    00298000h

Nun kommt der entscheidende Test, ob der Heap-Algorithmus wirklich in der Lage ist, freigegebene Bereiche zu vereinen und bei einer Anforderung zur Verfügung zu stellen. Dafür allokieren wir zunächst 0x10000, dann 0x5000 Byte Speicher im Heap-Bereich. Nach der Freigabe beider Bereiche fordern wir 0x12000 Byte an, also mehr als das erste freigegebene Loch. Wenn der Algorithmus so funktioniert wie erwartet, muss die rückgelieferte Adresse die gleiche sein wie die Adresse des ursprünglich ersten Blocks. Der Test gelingt:

kheap = create_heap(KHEAP_START, KHEAP_START+KHEAP_INITIAL_SIZE, KHEAP_MAX, 0, 0);

ULONG addr1, phys1, addr2, phys2, addr3, phys3;

addr1 = k_malloc(0x10000, 1, &phys1);
printformat("addr1: %x phys1: %x\n", addr1, phys1);

addr2 = k_malloc(0x5000, 1, &phys2);
printformat("addr2: %x phys2: %x\n", addr2, phys2);

kfree(addr1);
kfree(addr2);

addr3 = k_malloc(0x12000, 1, &phys3);
printformat("addr3: %x phys3: %x\n", addr3, phys3);

Bochs-Screenshot:


addr1: 01082000h phys1: 00298000h

addr2: 01093000h phys2: 002A9000h

addr3: 01082000h phys3: 00298000h



Damit es in ckernel.c möglichst aufgeräumt aussieht, packen wir den Code zur Vorbereitung und Erzeugung des Kernel-Heaps in eine Funktion heap_install():

heap_t* heap_install()
{
    // Map some pages for the the kernel heap
    ULONG i = placement_address, num;
    while( i < (placement_address+0x10000) )
    {
        page_t* page = set_page(i, kernel_directory);
        num = alloc_frame( page, 0, 0 );
        printformat("alloc_frame: %x\n", num*PAGESIZE);
        i+=PAGESIZE;
    }

    // Map some pages in the heap area and create kernel heap there
    for( i=KHEAP_START; i<KHEAP_MAX; i+=PAGESIZE )
        alloc_frame( set_page(i, kernel_directory), 0, 0);

    kheap = create_heap(KHEAP_START, KHEAP_START+KHEAP_INITIAL_SIZE, KHEAP_MAX, 0, 0);
    return kheap;
}

In ckernel.c verwenden wir zum Test folgenden Code. Im Vorbeigehen schauen wir, ob die Funktionen expand() und contract() vernünftig arbeiteten:
#include "os.h"
#include "paging.h"
#include "kheap.h"

//TEST
extern heap_t* kheap;
//TEST

int main()
{
    k_clear_screen();
    gdt_install(); idt_install();
    isrs_install(); irq_install(); ODA_install();
    sti();
    timer_install();
    keyboard_install();
    paging_install();
    kheap = heap_install();

    //TEST
    printformat("kernel ends at: %x\n", get_end_kernel());
    printformat("&kheap: %x kheap->start %x kheap->end %x\n",
                 &kheap, kheap->start_address, kheap->end_address);
    k_malloc(0x100000,1,0);
    printformat("&kheap: %x kheap->start %x kheap->end %x\n",
                 &kheap, kheap->start_address, kheap->end_address);
    kfree((ULONG*)addr);
    printformat("&kheap: %x kheap->start %x kheap->end %x\n",
                 &kheap, kheap->start_address, kheap->end_address);
    //TEST

    return 0;
};

Der Screen-Output zeigt, dass Heap-Expandierung und -Kontrahierung arbeiten:

kernel ends at: 0000BBB0h
&kheap: 0000B2C0h kheap->start 01081000h kheap->end 01100000h
expand, new size: 0017F014h
k_m_heap: 01082000h
&kheap: 0000B2C0h kheap->start 01081000h kheap->end 01201000h
contract, new size: 00000000h
&kheap: 0000B300h kheap->start 01081000h kheap->end 010F1000h





Multitasking (Software)

Wie funktioniert Multitasking? Der de-facto-Standard ist heute der Software-Task-Switch im Interrupt. Zunächst schauen wir uns einen Beispiel-Code (nicht völlig konsistent mit den vorstehenden Kapiteln, da auf älterem Testcode basierend) an, in dem ein einfaches Multitasking umgesetzt wurde.
Bitte testen Sie nachfolgenden Code:


Zunächst ein Screen Output des aktuellen Programms:


Sie erkennen, dass Task 1 (der ursprüngliche Prozess), Task 2 ("MOO") und Task3("BAA") sich zyklisch abwechseln: 1-2-3-1-2-3-...
In diesem konkreten Fall erhält jeder Prozess (=Task) die gleiche Zeitspanne zur Verfügung.
Umgeschaltet wird durch den Timer-Interrupt IRQ0. 
Der Mechanismus im Betriebssystem verläuft in folgender Reihenfolge:
Beim Auslösen eines Interrupts (verwendet wird vor allem der Timer-Interrupt IRQ0) werden in irq_common_stub zunächst die 
Allgemein- und Segment-Register mit Ausnahme von esp mittels push auf den Stack gesichert, um diese mit pop wieder zurück zu holen. 
Der Stackpointer esp wird zuletzt auf den Stack gelegt, damit dieser von der Funktion irq_handler1(esp) als Argument übernommen wird. 
Der Taskswitch - also ein Wechsel des Prozesses - erfolgt in der Funktion task_switch1(esp), die den Stackpointer widerum als Argument übernimmt, 
um ihn in der Struktur task  zu speichern.

typedef struct task
{
  int id;                               // Process ID
  ULONG esp, ebp;                       // Stack and base pointers
  ULONG eip;                            // Instruction pointer
  page_directory_t* page_directory;     // Page directory
  ULONG kernel_stack;                   // Kernel stack location
  struct task* next;                    // The next task in a linked list
} task_t;

Innerhalb task_switch1 erfolgt ein Wechsel der Task im Rahmen einer einfach verlinkten Liste.
Sobald keine nächste Task mehr vorhanden ist (Ende der Liste), fängt man einfach wieder vorne in der Task-Liste (ready_queue)an.
Die Funktion task_switch1 liefert den Stackpointer der neuen Task zurück. Man fährt bei _irq_tail fort.
Der Rückgabewert in eax (Stackpointer der neuen Task) wird nach esp geschrieben. Nun holt man die auf den Stack gelegten sonstigen Register zurück.
Die Zeile add esp,8 ist notwendig, weil man die beiden Informationen Error Code und IRQ Number auf dem Stack entfernen (pop ohne Ziel) muss.

isr.asm

irq_common_stub:
   
    push eax
    push ecx
    push edx
    push ebx
    push ebp
    push esi
    push edi
   
    push ds
    push es
    push fs
    push gs

    mov ax, 0x10
    mov ds, ax
    mov es, ax
    mov fs, ax
    mov gs, ax
   
    push esp              ; parameter of _irq_handler1
    call _irq_handler1    
   


irq.c  

ULONG irq_handler1(ULONG esp)
{
    ULONG retVal;
    struct regs* r = (struct regs*)esp;

    if(!pODA->ts_flag)
        retVal = esp;
    else
        retVal = task_switch1(esp); //new task's esp

    //...

    return retVal;
}   


task.c

ULONG task_switch1(ULONG esp)
{
    // ...
    current_task->esp = esp;                                                 // save esp  
    current_task = current_task->next;                                       // task switch
    if(!current_task) current_task = ready_queue;                            // the last task? go to the first task
    current_directory = current_task->page_directory;                        // setup correct PD
    asm volatile("mov %0, %%cr3" : : "r" (current_directory->physicalAddr)); // task's address space
    tss_entry.esp0 = (current_task->kernel_stack)+KERNEL_STACK_SIZE;         // address of kernel stack
    return current_task->esp;                                                // return new task's esp
}


isr.asm

global _irq_tail  
_irq_tail:
    mov esp, eax          ; return value: changed or unchanged esp

    pop gs
    pop fs
    pop es
    pop ds
       
    pop edi
    pop esi
    pop ebp
    pop ebx
    pop edx
    pop ecx
    pop eax
   
    add esp, 8
    iret

Der Stackpointer zeigt nun auf den Stack der neuen Task.

Dieser Stack wurde zuvor in create_task mit k_malloc erzeugt, der Zeiger new_task->kernel_stack auf das hintere Ende des belegten Speichers gelegt
und der Inhalt dieses Stacks so aufgebaut, wie es nach der Rückkehr vom Interrupt inhaltlich bezüglich der Reihenfolge erwartet wird.

Als Argument wird der Zeiger auf eine Funktion übergeben. Dieser Zeiger wird als eip (instruction pointer) auf dem Stack übergeben.
Die eflags werden so gesetzt (0x200 oder 0x202, das ist egal, weil die CPU das reservierte Bit 1 immer auf 1 setzt), dass IF gesetzt ist.
Das Codesegment cs wird auf 0x08 und die Datensegmente ds, es, fs, gs auf 0x10 gesetzt.

Ansonsten wird die aktuelle Page Directory kopiert, damit man diese der neuen Task als PD zuweisen kann.
Die neue Task wird mit den entsprechenden Werten gefüllt. Die Prozess-ID (pid) wird von 1 ausgehend bei jedem neuen Prozess erhöht.
Da es sich bei einem neuen Task um den letzten in der Link-Liste handeln wird, wird der Zeiger auf das nächste Listenelement bereits auf 0 gesetzt.
Anschließend läuft man die Liste durch, bis man das jetzige letzte Element findet (task->next ist 0), und hängt die neue Task hinter diesem an der letzten Stelle ein.

task_t* create_task(void* entry)
{
    cli();
    page_directory_t* directory   = clone_directory(current_directory);
    task_t* new_task              = (task_t*)k_malloc(sizeof(task_t),0,0);

    new_task->id                  = next_pid++;
    new_task->page_directory      = directory;
    new_task->kernel_stack        = k_malloc(KERNEL_STACK_SIZE,1,0)+KERNEL_STACK_SIZE;
    new_task->next                = 0;

    task_t* tmp_task = (task_t*)ready_queue;
    while (tmp_task->next)
        tmp_task = tmp_task->next;
    tmp_task->next = new_task;

    ULONG* kernel_stack = (ULONG*) new_task->kernel_stack;

    *(--kernel_stack) = 0x0200;       // eflags = interrupts aktiviert und iopl = 0
    *(--kernel_stack) = 0x08;         // cs
    *(--kernel_stack) = (ULONG)entry; // eip
    *(--kernel_stack) = 0;            // error code
    *(--kernel_stack) = 0;            // interrupt nummer

    // general purpose registers without esp
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;

    // data segment registers
    *(--kernel_stack) = 0x10;
    *(--kernel_stack) = 0x10;
    *(--kernel_stack) = 0x10;
    *(--kernel_stack) = 0x10;

    new_task->esp = (ULONG)kernel_stack;
    new_task->eip = (ULONG)irq_tail;
   
    sti();
    return new_task;
}

In ckernel.c wird zunächst das Tasking installiert, dann die beiden zusätzlichen Tasks mit der Prozess-ID (pid) 2 und 3 erzeugt und anschließend(!)
der Multitasking-Mechanismus über ein in der ODA definiertes Flag tatsächlich eingeschaltet:

    tasking_install();

    task_t* task2 = create_task( baa );
    task_t* task3 = create_task( moo );

    pODA->ts_flag = 1;

    while(TRUE)
        printformat("%d", getpid());

Versuchen Sie sich zunächst klar zu machen, wie Long-term und Mid-term Scheduler sowie Dispatcher (= Short-term scheduler) bei diesem einfachen Round-Robin-Verfahren arbeiten.

Wir sprechen in unserem Fall von "präemptivem" Multitasking. Hierbei wird die Zeitscheibe für jede Task durch das Betriebssystem vergeben.
Die Tasks erhalten die CPU nur für eine bestimmte Zeit. Diese Zeit entspricht bei obigem Beispiel der Zeit zwischen zwei Ticks (1/100 sec = 10 ms), die einen IRQ0 auslösen. Verändern Sie versuchsweise die Frequenz in timer.c auf niedrigere Werte, z.B. 50 Hz, dann können die einzelnen Tasks länger arbeiten, also zum Beispiel Task 2 und 3 ihre Funktion moo() oder baa() öfter aufrufen als bei einer kürzeren Zeitscheibe.

Das Umschalten von einer Task auf die andere erfolgt unabhängig von der Aktion, die eine gerade aktive Task ausführt. Das bedeutet dass eine Task für eine bestimmte Aufgabe mehrere Zeitscheiben benötigen kann. Auf jeden Fall wird nach Ablauf einer Zeitscheibe auf die nächste Task umgeschaltet.

Das Gegenteil zu präemptiven Multitasking ist das kooperative Multitasking. Hier bestimmen die Tasks die für eine Aufgabe benötigte Zeitscheibe. Dies kann allerdings dazu führen, dass ein Task die CPU komplett für seine Zwecke blockiert.

Man unterscheidet zwischen Software- und Hardware-Multitasking. Im vorstehenden Fall haben wir es mit Software-Multitasking zu schaffen.
Die x86-CPU verwendet hierbei das TSS (Task State Segment), das durch folgende Struktur exakt nachgebildet wird:
      
struct tss_entry
{
    USHORT prev_tss;
    USHORT reserved10;

    ULONG  esp0;

    USHORT ss0;
    USHORT reserved09;

    ULONG  esp1;

    USHORT ss1;
    USHORT reserved08;

    ULONG  esp2;

    USHORT ss2;
    USHORT reserved07;

    ULONG  cr3;
    ULONG  eip;
    ULONG  eflags;
    ULONG  eax;
    ULONG  ecx;
    ULONG  edx;
    ULONG  ebx;
    ULONG  esp;
    ULONG  ebp;
    ULONG  esi;
    ULONG  edi;

    USHORT es;
    USHORT reserved06;

    USHORT cs;
    USHORT reserved05;

    USHORT ss;
    USHORT reserved04;

    USHORT ds;
    USHORT reserved03;

    USHORT fs;
    USHORT reserved02;

    USHORT gs;
    USHORT reserved01;

    USHORT ldt;
    USHORT reserved00;

    USHORT trap; //bit0 only! bit1...15 reserved
    USHORT iomap_base;
}

Man findet bei obigem Link:
"When an interrupt happens in protected (32-bit) mode, the x86 CPU will look in the TSS for SS0 and ESP0 and load their values into SS and ESP respectively. This allows for the kernel to use a different stack than the user program, and also have this stack be unique for each user program."

Das TSS wird in der GDT eingetragen: 

void gdt_install()
{
    gdt_register.limit = (sizeof(struct gdt_entry) * NUMBER_GDT_GATES)-1;
    gdt_register.base  = (ULONG) &gdt;

    gdt_set_gate(0, 0, 0, 0, 0);                // NULL descriptor
    gdt_set_gate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); // CODE, privilege level 0 for kernel code
    gdt_set_gate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); // DATA, privilege level 0 for kernel code

    write_tss   (3, 0x10, 0x0); //num, ss0, esp0

    gdt_flush((ULONG)&gdt_register); // inclusive gdt_load() in assembler code
    tss_flush();                     //in flush.asm: privilege level 0 for kernel mode 0x28
}

// in descriptor_tables.c

void write_tss(int num, USHORT ss0, ULONG esp0)
{
    ULONG base = (ULONG) &tss_entry;
    ULONG limit = sizeof(tss_entry);
   
    gdt_set_gate(num, base, limit, 0xE9, 0x00); //access = 0xE9, granularity = 0x0
    k_memset(&tss_entry, 0, sizeof(tss_entry));

    tss_entry.ss0  = ss0;  // Set the kernel stack segment.
    tss_entry.esp0 = esp0; // Set the kernel stack pointer.

    tss_entry.cs   = 0x08;
    tss_entry.ss = tss_entry.ds = tss_entry.es = tss_entry.fs = tss_entry.gs = 0x10;
}


// in flush.asm
GLOBAL _tss_flush    
_tss_flush:
    mov ax, 0x18      ; Load the index of our TSS structure
    ltr ax            ; Load ... into the task state register.
    ret


Bochs Debugger einsetzen

Gerade bei Multitasking - also dem Bestücken individueller Kernel-Stacks für eine Anwendung - passiert schnell ein Fehler, der das OS zum Wanken bringen kann. Ein wichtiges Hilfsmittel ist dann z.B. der bei Bochs bereits vorhandene Debugger. Wir setzen dieses Werkzeug nun an dem obigen funktionierenden Beispiel ein, damit Sie die wesentlichen Schritte kennen lernen, um die richtige Adresse zu finden (Linker), an diese zu gelangen (Debugger) und dort Informationen zu gewinnen (Debugger):

Zuerst muss man einige wichtige Befehle des Debuggers kennen:

Befehl
 Bedeutung
print-stack
 zeigt die Stack-Inhalte
s [count] man geht [count] Schritte (s = step) im Assemblercode vorwärts
c man setzt das Programm fort bis zum nächsten breakpoint bzw. bis zum Ende (c = continue)
lb [addr] setzt einen lineraen Adress-Breakpoint (Info aus kernel.map)
r zeigt die Register
info eflags zeigt die EFLAGS
info cpu
zeigt alles Wichtige in der Gesamtsicht
watch read [addr]
 Eine physische Adresse wird zur Überwachungsliste hinzu gefügt
watch
 Überwachungsliste anzeigen


Nun ist die entscheidende Frage, woher bekommt man die physischen Adressen für die Breakpoints?

Das geht wie folgt:
Man baut im  makefile bei der Linkeranweisung folgenden Parameter ein:  -Map kernel.map
Damit erhält man beim Linken zusätzlich eine Datei kernel.map, die Informationen über Funktionen und Strukturen im Code- und Daten-Segment offen legt.

Das ergibt bei dem oben angebotenen Test-Programm zum Multitasking folgende interessante Adressen:


0x000084e0                _baa
0x000084b8                _moo

0x00008406                _irq0
0x000096f0                _irq_handler1
0x00008495                _irq_tail

Nun streben wir geradlinig nach irq0. Wir starten  MyOS.bin mit dem Bochs Debugger:

lb 0x00008406
c (ziemlich oft einfach mit ENTER wiederholen, bis wir im Task-Wechsel angelangt sind)
s (mehrfach, Einzelschritt-Modus)
Next at t=173279006 (0) [0x8407] 08:8407 (unk. ctxt): push 0x00000000             ;6a00
Next at t=173279007 (0) [0x8409] 08:8409 (unk. ctxt): push 0x00000020             ;6a20
Next at t=173279008 (0) [0x840b] 08:840b (unk. ctxt): jmp .+0x00000069 (0x8476)   ;eb69
Next at t=173279009 (0) [0x8476] 08:8476 (unk. ctxt): push eax                    ;50
Next at t=173279010 (0) [0x8477] 08:8477 (unk. ctxt): push ecx                    ;51
Next at t=173279011 (0) [0x8478] 08:8478 (unk. ctxt): push edx                    ;52

lb 0x00008495
print-stack
Stack address size 4
 | STACK 0x401056f0 [0x000b8000]
 | STACK 0x401056f4 [0x00000004]
 | STACK 0x401056f8 [0x00000020]
 | STACK 0x401056fc [0x00000000]
 | STACK 0x40105700 [0x000086c0]
 | STACK 0x40105704 [0x00000008]
 | STACK 0x40105708 [0x00000202]
 | STACK 0x4010570c [0x4010572c]
 | STACK 0x40105710 [0x00008847]
 | STACK 0x40105714 [0x00000500]
 | STACK 0x40105718 [0x00000500]
 | STACK 0x4010571c [0x4010572c]
 | STACK 0x40105720 [0x00008820]
 | STACK 0x40105724 [0x00000005]
 | STACK 0x40105728 [0x00000000]
 | STACK 0x4010572c [0x401057dc]

info cpu
rax: 0x00000000:00000004 rcx: 0x00000000:000b8000
rdx: 0x00000000:0000054d rbx: 0x00000000:00000780
rsp: 0x00000000:401056f0 rbp: 0x00000000:4010571c
rsi: 0x00000000:00000000 rdi: 0x00000000:000084b0
r8 : 0x00000000:00000000 r9 : 0x00000000:00000000
r10: 0x00000000:00000000 r11: 0x00000000:00000000
r12: 0x00000000:00000000 r13: 0x00000000:00000000
r14: 0x00000000:00000000 r15: 0x00000000:00000000
rip: 0x00000000:00008478
eflags 0x00000002
id vip vif ac vm rf nt IOPL=0 of df if tf sf zf af pf cf

Wenden Sie auch die Anweisungen watch read und watch an, um erwartete Veränderungen im Speicher zu beobachten.

Background-Wissen: Aufruf einer C-Funktion

Ein wichtiger Punkt bei der Entwicklung eines OS ist die Frage, wie eine C-Funktion aus Sicht der Assembler-Ebene aufruft ("caller") und aufgerufen ("callee") wird. Dazu gehen wir experimentell wie folgt vor. Wir fügen zunächst die primitive Funktion nop(), die keine Argumente übernimmt, keine Aktion durchführt und keinen Rückgabewert liefert, zweimal in einer Funktion eines Tasks ein:

// util.c

inline void nop() { asm volatile ( "nop" ); }    // Do nothing


// ckernel.c

void f2()
{
    while(TRUE)
    {
      settextcolor(getpid(),0);
      putch(getpid()+'@');
      nop();
      nop();
      //...
    }
}

Dann verfolgen wir den Ablauf mit dem Bochs Debugger: Wir suchen uns in kernel.map die Adresse von nop() heraus:  0x00009c42  _nop

Beim ersten Auffinden der Adresse sehen wir die Welt im Debugger-Einzelschritt-Modus aus Sicht des "callee", denn wir beginnen die Verfolgung der Assembler-Befehle nach dem call _nop.
Das heißt, wir starten mit dem Prolog der Funktion nop(), gehen dann zum Body der Funktion (wir machen nichts = nop) über und enden mit dem Epilog:

; prolog des callee
push ebp      ; ebp des callers sichern           
mov ebp, esp  ; ebp des callee erstellen          

nop           ; body des callee        

; epilog des callee
pop ebp       ; ebp des callers wiederherstellen
ret           ; Rücksprung zum gesicherten eip des callers 

Prolog: Zunächst wird der Stackframe des callers auf den Stack gesichert. Anschließend wird der Stackframe des callee erstellt.
Body: Die eigentliche Funktion wird ausgeführt.
Epilog: Der Stackframe des callers wird wiederhergestellt. Anschließend springt man zum instruction pointer (gesichert auf dem Stack) des callers zurück.

Nun wird es spannend. Denn wir befinden uns nun in der Sphäre des callers f2, der als nächste Funktion wieder nop() aufrufen möchte und daher zunächst seinen eigenen Kontext sichern muss.
Es passiert im Code nicht viel. Nach dem Return wird sofort wieder  call 0x00009c42  aufgerufen, und das Spiel des callee beginnt von vorne.

Also müssen wir uns den Stack und die Register genau anschauen, denn dort wird das eigentliche Bühnenstück von caller und callee aufgeführt.
So sieht es vor dem Prolog der Funktion - also nach dem call - auf dem Stack aus: Auf dem "stack top" (esp) liegt die Rücksprungadresse, also der Austiegs-EIP des caller.

STACK 0x402057e0 [0x000082ea]
STACK 0x402057e4 [0x00000042]

esp: 0x402057e0 ebp: 0x402057fc
eip: 0x00009c42


Im nächsten Schritt wird der Stackframe (ebp) des caller mittels  push ebp auf den Stack gesichert:

push ebp

STACK 0x402057dc [0x402057fc]
STACK 0x402057e0 [0x000082ea]
...
STACK 0x402057fc [0x00000000]

esp: 0x402057dc ebp: 0x402057fc
eip: 0x00009c43

Jetzt wird der Stackpointer esp als neuer Stackframe ebp des callee installiert. Dieser Basepointer spielt im callee eine wichtige Rolle als fester Ankerpunkt zum Auffinden von Daten:

mov ebp, esp

STACK 0x402057dc [0x402057fc]
STACK 0x402057e0 [0x000082ea]
STACK 0x402057e4 [0x00000042]


esp: 0x402057dc ebp: 0x402057dc
eip: 0x00009c45


Der Body der Funktion ist bewusst langweilig gehalten. Es wird nur der eip einen Schritt vorgerückt und keine Aktion ausgeführt.

nop

eip: 0x00009c46


Der Epilog der Funktion stellt den Stackframe des caller wieder her, indem er den gesicherten ebp des caller vom Stack holt:

pop ebp

STACK 0x402057e0 [0x000082ea]
STACK 0x402057e4 [0x00000042]

esp: 0x402057e0 ebp: 0x402057fc
eip: 0x00009c47

Nun ist der alte Stackframe hergestellt und die Return-Adresse liegt oben auf dem Stack.
Die Instruktion ret holt diesen Wert im letzten Schritt des callee vom Stack und transferiert ihn nach eip, damit der caller am Unterbrechungspunkt fortfahren kann.


ret

STACK 0x402057e4 [0x00000042]
STACK 0x402057e8 [0x00000000]

esp: 0x402057e4 ebp: 0x402057fc
eip: 0x000082ea


call 0x00009c42

STACK 0x402057e0 [0x000082ef]
STACK 0x402057e4 [0x00000042]

esp: 0x402057e0 ebp: 0x402057fc
eip: 0x00009c42
Stackpointer
 Inhalt
 Bedeutung des Inhalts
0x402057dc [ebp + 0] des callee
 0x402057fc Stackframe (ebp) des caller
0x402057e0 [ebp + 4]
 0x000082ea Instruction Pointer (eip) des caller = Rücksprungadresse
0x402057e4 [ebp + 8]
 ... (argument1, in diesem einfachen Fall nicht vorhanden)
0x402057e8 [ebp + 12]
 ... (argument2, in diesem einfachen Fall nicht vorhanden)


Eine ausführliche Darstellung komplexerer Situationen mit von caller und callee gesicherten Registern, übergebenen Argumenten, lokalen Variablen und temporärem Speicherbereich findet man hier.

Alle Theorie ist grau. Daher probieren wir dies auch selbst an einem Beispiel aus. Wir schaffen uns eine künstliche Funktion int foo2(int a, int b), die zwei Argumente übernimmt, eine lokale Variable besitzt und einen Rückgabewert liefert. Diese setzen wir experimentell wie folgt ein:
int foo2(int a, int b)
{
    int loc1, loc2, loc3;
    loc1 = a + b;
    loc3 = loc2 - loc1;
    int retVal = loc3 + 42;
    return retVal;
}

void f2()
{
    while(TRUE)
    {
      settextcolor(getpid(),0);
      putch(getpid()+'@');
      nop();
      foo2(42,0);
      //...
    }
}

Wir verwenden wieder unser nop() als ersten Haltepunkt im Debugger und gehen nach dem ret schrittweise weiter zu foo2(...):
Zunächst holt der caller noch zwei Werte (ohne Ziel) vom Stack, daher die  add esp, n*4  Methode:

add esp, 0x00000008

In den nächsten beiden Schritten schiebt der caller die beiden Argumente 0 und 42 (von rechts nach links) auf den Stack. 

push 0x00000000
push 0x0000002a

STACK 0x402057e4 [0x0000002a] <-- Argument1
STACK 0x402057e8 [0x00000000] <-- Argument2
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057e4 ebp: 0x402057fc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082ff


Nun wird die Funktion _foo2 aufgerufen.
Hierbei wird die Rücksprungadresse (nächster eip des callers) auf den Stack gesichert:
Die Instruktion  call ...  ist der letzte Schritt des callers.
Ab dann beherrscht der callee den Stack.

call 0x000082b0  (_foo2)

STACK 0x402057e0 [0x00008304] <-- Rücksprungadresse
STACK 0x402057e4 [0x0000002a] <-- Argument1
STACK 0x402057e8 [0x00000000] <-- Argument2
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057e0 ebp: 0x402057fc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082b0


Nach der Rücksprungadresse folgt der Stackframe (ebp) des callers:

push ebp

STACK 0x402057dc [0x402057fc] <-- ebp des caller
STACK 0x402057e0 [0x00008304] <-- Rücksprungadresse
STACK 0x402057e4 [0x0000002a] <-- Argument1
STACK 0x402057e8 [0x00000000] <-- Argument2
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057dc ebp: 0x402057fc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082b1


Nun wird der Stackframe des callee eingerichtet.
Damit ist die Lage der Argumente fixiert. Diese beginnen ab [esp+8] :

mov ebp, esp

STACK 0x402057dc [0x402057fc] <-- ebp des caller     [ebp +  0]
STACK 0x402057e0 [0x00008304] <-- Rücksprungadresse  [ebp +  4]
STACK 0x402057e4 [0x0000002a] <-- Argument1          [ebp +  8]
STACK 0x402057e8 [0x00000000] <-- Argument2          [ebp + 12]
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057dc ebp: 0x402057dc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082b3


Das Argument1 bei [ebp+8] wird von eax subtrahiert:

sub eax, dword ptr ss:[ebp+0x8]
STACK unverändert

eax: 0xffffffd8 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057dc ebp: 0x402057dc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082b6

eflags 0x00000297
id vip vif ac vm rf nt IOPL=0 of df IF tf SF zf AF PF CF


Das Argument2 bei [ebp+12] wird ebenfalls von eax subtrahiert:

sub eax, dword ptr ss:[ebp+0xc]

STACK unverändert

eax: 0xffffffd8 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057dc ebp: 0x402057dc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082b9

eflags 0x00000286
id vip vif ac vm rf nt IOPL=0 of df IF tf SF zf af PF cf


Nun wird noch die Konstante 42 addiert:

add eax, 0x0000002a      

STACK unverändert

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057dc ebp: 0x402057dc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082bc

eflags 0x00000213
id vip vif ac vm rf nt IOPL=0 of df IF tf sf zf AF pf CF


Der Epilog beginnt wie üblich mit der Rücksicherung des Stackframes (ebp) des caller:

pop ebp

STACK 0x402057e0 [0x00008304] <-- Rücksprungadresse 
STACK 0x402057e4 [0x0000002a] <-- Argument1         
STACK 0x402057e8 [0x00000000] <-- Argument2         
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057e0 ebp: 0x402057fc
esi: 0x00000000 edi: 0x00000000
eip: 0x000082bd


Nun setzt der Caller bei der gesicherten Rücksprungadresse 0x00008304 fort.
Diesen Wert erhält er vom Stack:

ret

STACK 0x402057e4 [0x0000002a] <-- Argument1         
STACK 0x402057e8 [0x00000000] <-- Argument2         
STACK 0x402057ec [0x00000000]
STACK 0x402057f0 [0x00000000]

eax: 0x00000002 ecx: 0x000b8000
edx: 0x000003d5 ebx: 0x00000000
esp: 0x402057e4 ebp: 0x402057fc
esi: 0x00000000 edi: 0x00000000
eip: 0x00008304

Nun liegen noch die beiden Argumente 42 und 0 auf dem Stack, die man evtl. mit  add esp, 0x00000008  (ohne Ziel) vom Stack entfernen könnte.
Im konkreten Fall wird dies nicht durchgeführt, weil nicht notwendig.

Wahrscheinlich wundern Sie sich, warum keine lokalen Variablen auf dem Stack angelegt wurden. Der Compiler optimiert das Hin- und Herschaufeln von Daten soweit wie möglich und versucht anstelle des Stack-Speichers seine CPU-Register zu verwenden. Es gibt hier aber ein kleines Zauberwort in C, dessen Wirkung wir an obiger Funktion testen wollen:  volatile
int foo2(int a, int b)
{
    int volatile loc1, loc2, loc3;
    loc1 = a + b;
    loc3 = loc2 - loc1;
    int retVal = loc3 + 42;
    return retVal;
}

void f2()
{
    //...
}

... und sofort läuft das Ganze wie im Lehrbuch für das Zusammenspiel von C und Assembler. Auf dem Stack wird Platz für drei lokale Variablen von jeweils 4 Byte angelegt. Hierzu verwendet der callee bezogen auf seinen eigenen Stackframe (ebp) die drei Speicherstellen [EBP - 4], [EBP - 8] und [EBP - 12]. Der Code entspricht nun dem Ablauf der C-Funktion, allerdings ist er komplizierter als notwendig. Daher sollte man volatile sehr vorsichtig verwenden. Man knipst die kreative Intelligenz des Compilers mit diesem "Schalter" aus.

Zunächst der erzeugte Assembler-Code des Callee im Überblick:

;Prolog
push ebp                 
mov ebp, esp             

;Body
sub esp, 0x0000000c                          ; int volatile loc1, loc2, loc3;   

mov eax, dword ptr ss:[ebp+0xc]              ; argument b
add eax, dword ptr ss:[ebp+0x8]              ; argument a
mov      dword ptr ss:[ebp+0xfffffffc], eax  ; loc1 = a + b;

mov eax, dword ptr ss:[ebp+0xfffffff8]       ; loc3 = loc2 - loc1;
mov edx, dword ptr ss:[ebp+0xfffffffc]
sub eax, edx                                
mov      dword ptr ss:[ebp+0xfffffff4], eax   

mov eax, dword ptr ss:[ebp+0xfffffff4]      
add eax, 0x0000002a                          ; int retVal = loc3 + 42; return retVal;

;Epilog
mov esp, ebp             
pop ebp                  
ret                      


Schauen wir uns den Stack nach dem Einrichten des Platzes für die drei - zufällig initialisierten - lokalen Variablen genauer an:
sub esp, 0x0000000c

STACK 0x402057d0 [0x00008930] <-- lokale Var. 3      [ebp - 12]
STACK 0x402057d4 [0x00000000] <-- lokale Var. 2      [ebp -  8]
STACK 0x402057d8 [0x00000000] <-- lokale Var. 1      [ebp -  4]
STACK 0x402057dc [0x402057fc] <-- ebp des caller     [ebp +  0]
STACK 0x402057e0 [0x0000831a] <-- Rücksprungadresse  [ebp +  4]
STACK 0x402057e4 [0x0000002a] <-- Argument 1         [ebp +  8]
STACK 0x402057e8 [0x00000000] <-- Argument 2         [ebp + 12]

esp: 0x402057d0 ebp: 0x402057dc
eip: 0x000082b6

Den nächsten Halt machen wir vor dem Epilog, denn dort taucht eine neue Zeile auf, die anschließend den Stackzeiger (esp) auf den Stackframe (ebp) des callee justiert, also die drei lokalen Variablen "ziellos vom Stack nimmt", um anschließend den an dieser Stelle gespeicherten Wert für den Stackframe des caller vor dem Rücksprung nach ebp zu tranferieren.

add eax, 0x0000002a

STACK 0x402057d0 [0xffffffd6] <-- lokale Var. 3      [ebp - 12]
STACK 0x402057d4 [0x00000000] <-- lokale Var. 2      [ebp -  8]
STACK 0x402057d8 [0x0000002a] <-- lokale Var. 1      [ebp -  4]
STACK 0x402057dc [0x402057fc] <-- ebp des caller     [ebp +  0]
STACK 0x402057e0 [0x0000831a] <-- Rücksprungadresse  [ebp +  4]
STACK 0x402057e4 [0x0000002a] <-- Argument 1         [ebp +  8]
STACK 0x402057e8 [0x00000000] <-- Argument 2         [ebp + 12]

esp: 0x402057d0 ebp: 0x402057dc
eip: 0x000082d0


Dieses "Stackzeiger auf null stellen" findet man typischerweise im Epilog, wenn lokale Variablen oder andere temporäre Speicher auf dem Stack eingerichtet wurden.
Die lokalen Variablen sind nun nicht mehr "gültig":

mov esp, ebp

STACK 0x402057dc [0x402057fc] <-- ebp des caller     [ebp +  0]
STACK 0x402057e0 [0x0000831a] <-- Rücksprungadresse  [ebp +  4]
STACK 0x402057e4 [0x0000002a] <-- Argument 1         [ebp +  8]
STACK 0x402057e8 [0x00000000] <-- Argument 2         [ebp + 12]

esp: 0x402057dc ebp: 0x402057dc
eip: 0x000082d2


Der weitere Verlauf des Epilogs erfolgt wie oben.

Es gibt übrigens inzwischen eine Konvention, dass der callee bevorzugt die Register EAX (z.B. zum Rechnen, Transferieren und als Rückgabewert), ECX (z.B. als Schleifenzähler) und EDX (in obiger Fuktion. z.B. zum Rechnen) verwendet. Daher sichert der caller, falls notwendig, diese Register auf den Stack, während sich der callee ggf. um die Sicherung der Register EBX, EDI, ESI kümmert.

http://de.wikipedia.org/wiki/Aufrufkonvention#stdcall
Die Register EAX, ECX, und EDX sind reserviert für die Verwendung innerhalb der Funktion, werden also unter Umständen verändert.
Rückgabewerte werden im EAX-Register zurückgegeben.

http://www.agner.org/optimize/calling_conventions.pdf  (Chapter 6, Register Usage)
Scratch registers are registers that can be used for temporary storage without restrictions (also called caller-save or volatile registers):
EAX, ECX, EDX.
Callee-save registers are registers that you have to save before using them and restore after using them (also called non-volatile registers).
You can rely on these registers having the same value after a call as before the call: EBX, ESI, EDI, EBP




Einfaches Programm ausführen


Es hat bei der Entwicklung eines eigenen Betriebssystems einen großen Reiz, ein Programm von außen einzuspielen ("laden") und mit Hilfe des OS ausführen zu können. Da wir noch kein Filesystem und keinen Zugriff auf äußere Speichermedien haben, müssen wir uns mit dem Zugriff auf den Hauptspeicher begnügen. Aber da muss ein Programm zum Ablauf auf jeden Fall platziert werden. Ja, wie machen wir es?

Wir erstellen ein kleines Assembler-Programm mittels NASM, das das Wort "Test" in den ersten vier Zellen des Bildschirmspeichers ausgibt.
Wir nennen es  file_data.asm  und assemblieren es mit Hilfe des makefile zu einer Datei namens file_data.dat:

nasmw -f bin file_data.asm -o file_data.dat
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Test Program for PrettyOS      ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
[BITS 32]
start:
   Mov [0x000b8000], byte 'T'
   Mov [0x000b8002], byte 'e'
   Mov [0x000b8004], byte 's'
   Mov [0x000b8006], byte 't'
   Ret

Vergessen Sie nicht die Anweisung [BITS 32]. Nun verfügen wir über ein binäres Programm, das wir mittels des incbin-Tricks in unseren Kernel laden.
process.asm:

global _file_data_start
global _file_data_end
_file_data_start:
incbin "file_data.dat"
_file_data_end:

In Assemblercode können wir nun mittels _file_data_start und in C mittels file_data_start auf den Programm-Code zugreifen.
Die Lage der physischen Adresse des Programms erhalten wir aus der vom Linker erzeugten Datei kernel.map (siehe oben).
Der Zugriff auf den Einstiegspunkt in das kleine Programm wird mit der Assembler-Anweisung call erfolgen.

Wir haben ja bereits zwei zusätzliche Tasks "baa" und "moo" erzeugt.
In zwei weiteren Tasks werden wir erstens mittels call auf die Funktion settextcolor (als Testfall mit zwei Parametern) zugreifen und zweitens unser selbst erzeugtes Programm, das "Test" ausgeben soll, starten.

Hierbei benötigen wir für den call auf settextcolor eine eigene Funktion create_task2(...), die zwei Argumente für Vorder- und Hintergundfarbe übernimmt sowie eine Dummy-Rücksprungadresse auf den Stack legt. Dies ist ein wichtiger Punkt. Da wir nicht die C-Funktion selbst aufrufen, sondern einfach mittels Assembler "an allem vorbei" mit dem Label settextcolor zum Anfang des Funktionscodes springen, ist diese Vorbereitung des Stacks notwendig. Die C-Funktion erwartet folgende Reihenfolge auf dem Stack von "oben" (Vorsicht: dies bedeutet aus Sicht der niedrigen Adressen!) gesehen: Rücksprungadresse, Argument 1, Argument 2.

void moo()
{
  while(TRUE)
  {
      settextcolor(2,0);
      printformat("MOO %d", getpid()); // <-- cow
      settextcolor(15,0);
  }
}

void baa()
{
  while(TRUE)
  {
      settextcolor(4,0);
      printformat("BAA %d", getpid()); // <- sheep
      settextcolor(15,0);
  }
}

void surprise(ULONG a, ULONG b) // <- function with 2 arguments
{
  asm volatile ("push %0" :/* no output registers */: "r" (b));
  asm volatile ("push %0" :/* no output registers */: "r" (a));
  while(TRUE)
  {
      asm volatile ("call _settextcolor");
      printformat("%d", getpid());
      settextcolor(15,0);
  }
}

void test()                    // <- program from outside "loaded" by incbin ...
{
  while(TRUE)
  {
      asm volatile ("call _file_data_start");
      printformat("%d", getpid());
      settextcolor(15,0);
  }
}

//main:   

task_t* task2 = create_task(moo);
task_t* task3 = create_task(baa);
task_t* task4 = create_task2(surprise,4,2);
task_t* task5 = create_task(test);


//task.c

task_t* create_task2(void* entry, ULONG arg1, ULONG arg2)
{
    //...
    ULONG* kernel_stack = (ULONG*) new_task->kernel_stack;

    *(--kernel_stack) = arg2; // arg2
    *(--kernel_stack) = arg1; // arg1
    *(--kernel_stack) = 0x0;  // return address dummy

    *(--kernel_stack) = 0x0202; // eflags = interrupts aktiviert und iopl = 0

    //...
    return new_task;
}

Damit kann man schon eine ganze Menge "spielen". Task 1 bis 5 laufen im Round Robin Verfahren nacheinander abwechselnd ab.
Die Ausgabe des Textes "Test" sieht man nur im Debugging-Modus, da dieser ansonsten zu schnell überschrieben wird:


 
Oben im Display wird der Ablauf der fünf Tasks sichtbar. Links oben sieht man das Wort "Test" von Task Nr. 5. 
Beim Schritt-Modus des Debuggers sieht man die Übertragung des großen T (ASCII: 0x54) in die Speicherstelle 0xb8000 des Video-RAM.
Analysieren Sie bitte den Weg, den die beiden Parameter 4 (rot) und 2 (grün) für die Funktion settextcolor(...) nehmen.
  


Virtual File System und RAM Disk

Wer Daten in einem OS handhabt, kommt um ein Filemanagement nicht herum. Wir machen uns das Leben hier einfach und verwenden zunächst das virtuelle Filesystem (VFS) und die RAM Disk aus Kapitel 8 von James Molloy's Tutorial.

Die Zusammenhänge sind an dieser Stelle ebenfalls gut dargestellt. Das VFS gibt uns die Möglichkeit, ganz verschiedenartige Elemente wie Daten- oder Programm-Files, Verzeichnisse, Verknüpfungen, Geräte, Sockets oder Pipes (Verbindungen zwischen Prozessen) auf abstrakte Weise als File anzusprechen.
"Alles ist ein File" ist eines der Grundkonzepte von UNIX, das hier ebenfalls umgesetzt wird. Das hierarchische Filesystem entspricht einer Baumstruktur mit Knoten (node), wie man Sie z.B. auch aus dem Windows Explorer kennt. Für jeden Knoten gilt die in fs.h definierte abstrakte Filesystem-Node-Struktur:

typedef struct fs_node
{
    CHAR  name[128];                 // The filename.
    ULONG mask;                      // The permissions mask.
    ULONG uid;                       // The owning user.
    ULONG gid;                       // The owning group.
    ULONG flags;                     // Includes the node type.
    ULONG inode;                     // This is device-specific - provides a way for a filesystem to identify files.
    ULONG length;                    // Size of the file, in bytes.
    ULONG impl;                      // An implementation-defined number.
    read_type_t     read;
    write_type_t    write;
    open_type_t     open;
    close_type_t    close;
    readdir_type_t  readdir;
    finddir_type_t  finddir;
    struct fs_node* ptr;             // Used by mountpoints and symlinks.
} fs_node_t;

Die "Initial RAM Disk" bietet ein eigenständiges Fileformat. Hier kann man sich kreativ betätigen. Wir haben hier das Format von James Molloy für die RAM Disk und die Files übernommen:

In den ersten vier Byte  wird die Anzahl Files gespeichert, die folgen. Hier steht in "file_data.da1" eine 3:  03 00 00 00

Anschließend kommt eine Header-Struktur für die nachfolgenden Files, die Namen, Offset und Größe umfasst.

Mit dem Filesystemgenerator (make_initrd.c, Kap. 8.3.1 JM's Tutorial; kompiliertes Programm liegt im Download oben als make_initrd.exe bei) kann man Daten / Programme in ein selbst definiertes Filesystem einbinden. In unserem Fall wurden mit diesem Programm die drei beiliegenden Texte test1.txt, test2.txt und test3.txt in die Datei "file_data.da1" gebunden. Hier können Sie sowohl mit dem Fileformat als auch mit den Inhalten experimentieren. Nachstehend werden wir auch unser kleines Test-Programm in dieses Filesystem nachträglich manuell einklinken, damit Sie den Mechanismus genau verstehen.

Header der RAM Disk und Header des Fileformats in dieser RAM Disk sind in initrd.h definiert.

typedef struct
{
    ULONG nfiles;            // The number of files in the ramdisk.
} initrd_header_t;
typedef struct
{
    ULONG magic;             // Magic number, for error checking.
    CHAR  name[64];          // Filename.
    ULONG off;               // Offset in the initrd that the file starts.
    ULONG length;            // Length of the file.
} initrd_file_header_t;

Wir setzen unsere "Initial RAM Disk" auf den Beginn des Kernel-Heaps:

ULONG ramdisk_start = 0x40081000;           // In the heap
fs_root = install_initrd( ramdisk_start );

Unser Mini-Programm für test() gehört nachfolgend noch nicht zur RAM Disk dazu. Hierzu müssten wir erst dieses File-Format verwenden, um den Offset für den Programmanfang zu finden.


Im nachfolgenden Sourcecode/Daten-Paket finden Sie:
- unser kleines lauffähiges Programm (siehe oben:  file_data.dat),
- weitere Informationen, die aus text1.txt, text2.txt, text3.txt mittels make_initrd.exe zu file_data.da1 in einem eigenen Fileformat zusammen gebunden wurden und mittels incbin und  memcpy  direkt hinter den Bereich der RAM Disk in den Heap transferiert werden.

Damit man unser einfaches binäres Programm-File findet - wir haben ja noch keine spezielle Kennung zum Auffinden des Namens, des Offsets oder der Größe im Format - fügen wir zwischen dem File-Datenpaket und unserem Programm ein zusätzliches Label ein:
; data for ramdisk
global _file_data_start
global _file_data_end
global _prog_start

 _file_data_start:
         incbin "file_data.da1"
_prog_start:
         incbin "file_data.dat"
_file_data_end:

Nach der Eröffnung unseres PrettyOS sehen Sie, dass sich die Daten zunächst im Adressbereich von A090h bis B41Fh befinden.
Von dort werden sie hinter die RAM Disk kopiert:
k_memcpy( (void*)ramdisk_start,&file_data_start,(ULONG)&file_data_end - (ULONG)&file_data_start );     

Anschließend wird unser fs_root auf der RAM Disk nach directories und files durchsucht.

Welcome to PrettyOS 0.08

HEAP start: 40081000h end: 40200000h max: 4FFFF000h kernel mode: 0 read-only: 0
hole 40081000h hole-size: 0017F000h

first task structure: 0020A000h
id: 1 ... PD: 00000000h k_stack: 0020B800h next: 00000000h

VFS & RAM Disk install
ramdisk_start: 40081000h file_data_start: 0000A090h file_data_end: 0000B41Fh

Found file dev

        (directory)

Found file f1

         contents: "PrettyOS: My filename is test1.txt!"

Found file f2

         contents: "PrettyOS: My filename is test2.txt!"

Found file f3

         contents: "PrettyOS: My filename is test3.txt!"

Schauen Sie sich die mitgelieferte Datei "file_data.da1" mit dem Hex-Editor an: Nach dem Erkennungszeichen bf finden Sie "f1" bzw. an späterer Stelle "f2" und "f3" und nachfolgend die Adresse, an der die zugehörigen Daten des "Files" jeweils zu finden sind.
03 00 00 00  ¿  f1 (Offset) (Länge) ¿  f2 (Offset) (Länge) ¿  f3 (Offset) (Länge)

......
   
PrettyOS: My filename is test1.txt!PrettyOS: My filename is test2.txt!PrettyOS: My filename is test3.txt!

Im Anschluss an diese Daten im erwarteten Fileformat haben wir unser kleines "Test"-Programm platziert. Unser Programm hat noch kein spezielles Format, sondern ist ein einfaches Binärformat, das an der Stelle ramdisk_start + (ULONG)&prog_start - (ULONG)&file_data_start beginnt.
Wir rufen diese Adresse in test mittels call wie bereits erprobt auf.

Einbinden des Test-Programms in das Filesystem der RAM Disk

Aufgabe:
Sie können als Herausforderung versuchen, das Programm manuell (im Hex-Editor die File-Informationen verändern) oder später via  make_initrd.exe in das "Filesystem" der RAM Disk zu integrieren. Was muss dazu passieren?

Lösung:
Zunächst überzeugen wir uns manuell mit dem Hex-Editor, dass das angestrebte "vierte File" wie beabsichtigt direkt hinter dem letzten File (test3.txt) mit dem Inhalt "PrettyOS: My filename is test3.txt!" im Speicher liegt. Dazu prüfen wir die Datei MyOS.bin und vergleichen mit file_data.dat:


Wir sehen, dass unser kleines Assembler-Programm aus file_data.dat, das das Wort TEST links oben auf dem Bildschirm ausgibt, nahtlos an test3.txt anschließt. Nun müssen wir abmessen, wie lang dieses File ist und wir benötigen den Offset zum Anfang des Filesystems.

Die Länge können wir einfach abzählen: 29

Den Offset errechnen wir aus dem Offset des Files test3.txt plus der Länge (35 Zeichen, hex: 23) dieses Files test3.txt.
Diese Daten finden wir am Anfang des Filesystems der RAM Disk in MyOS.bin oder in der Datei file_data_da1.
Bevor wir nun manipulieren, müssen wir uns zunächst den Aufbau für den Filesystem-Header und die File-Header bewusst machen:

ULONG nfiles;            // The number of files in the ramdisk.
--------------------------------------------------------------------------
ULONG magic;             // Magic number, for error checking.
CHAR  name[64];          // Filename.
ULONG off;               // Offset in the initrd that the file starts.
ULONG length;            // Length of the file.
--------------------------------------------------------------------------
ULONG magic;             // Magic number, for error checking.
CHAR  name[64];          // Filename.
ULONG off;               // Offset in the initrd that the file starts.
ULONG length;            // Length of the file.
--------------------------------------------------------------------------
// etc.

Diesen Filesystem- und die drei File-Header sowie den zu erstellenden neuen vierten File-Header markieren wir uns zur Sicherheit im Hex-Editor, damit wir ein vertieftes Verständnis für den Aufbau erhalten und dann auch selbst manipulieren können:



Die Bereiche des vierten File-Headers, deren Inhalte wir im Hex-Editor nun selbst implementieren werden, wurden entsprechend den Vorbildern farbig markiert.

Was müssen wir verändern?
1) Das niederwertigste Byte des Filesystem-Headers müssen wir von 03 auf 04 verändern ( 4 Files)
2) Zu Beginn des vierten File-Headers muss die Magic-Number eingefügt werden: bf 00 00 00
3) Der Name des neuen Files muss festgelegt werden: Test-Programm\0 (null-terminierter ASCII-String)
4) Offset File Nr. 4 = Offset + Länge File Nr. 3 (Little Endian Format): 4a 13 + 23 00 ==> (4a + 23) (13 + 00) ==> 6D 13
5) Die Filelänge muss eingetragen werden: 1D (dezimal 29)

Wir tragen diese in rot dargestellten Daten manuell in der Datei file_data_da1 mit einem Hex-Editor ein.Vergessen Sie nicht die abschließende null ('\0') für den String im Filenamen-Bereich. Sie müssen die nachfolgenden Daten nicht löschen, können diese aber auf null setzen, wenn Ihnen das besser gefällt (bei File Nr. 1 bis 3 finden sich dort momentan zufällige Zeichen).


Wenn alles richtig berechnet und eingetragen wurde, sollte nun File Nr. 4 "Test-Programm" gefunden werden, und tatsächlich, es klappt!
Welcome to PrettyOS ...
...
VFS & RAM Disk install
...
Found file dev
        (directory)
Found file f1
         contents: "PrettyOS: My filename is test1.txt!"
Found file f2
         contents: "PrettyOS: My filename is test2.txt!"
Found file f3
         contents: "PrettyOS: My filename is test3.txt!"
Found file Test-Programm
         contents: "ƤTƤeƤsƤtÃ"

Ein sinnvoller Text wird in diesem Fall nicht ausgegeben, allerdings erkennt man das Programm mit der Ausgabe "...T...e...s...t".
Wir sind also richtig gelandet.

Ich hoffe, Ihnen ist bewusst geworden, was wir da gemacht haben, denn wir haben ein File an unser Filesystem, das wir frei gestalten können, physisch angehängt, ihm den notwenigen File-Header verpasst und es in die Header-Struktur des Filesystems eingebunden. Solch einen Vorgang könnte man auch "Abspeichern" nennen, wenn man Daten in einem Filesystem ablegt.

Sie erkennen, dass im Fileformat bisher nicht erkennbar ist, ob es sich hier um ein Text-, Programm- oder anderes File handelt. Da bleibt noch viel Raum für kreatives Gestalten des Filesystems. Man ist hier völlig frei, es sei denn, man möchte bereits existierende Files anderer OS verwenden.

Man kann es auch einfacher sagen: Wir haben das ausführbare File "Test-Programm" mit NASM erstellt, mittels incbin in den Speicher geladen, im Speicher verschoben (k_memcpy) und in unserer RAM Disk wiederauffindbar gespeichert. Damit wären wir in der Lage mittels des Filesystems der RAM Disk dieses Programm zu "laden" bzw. aufzurufen, da wir nun wissen
- auf welchem Datenträger es sich befindet (-> RAM Disk)
- wie es heißt (-> Name führt beim "Abklappern" aller Files-Header zum gesuchten File-Header)
- wo es liegt (-> File-Header enthält Offset)
- wie groß (-> File-Header enthält Länge) es ist.
Mit diesen Informationen kann man die "gespeicherten" Daten an gewünschter Stelle im Speicher darstellen, sprich "laden".

Analysieren Sie diesbezüglich bitte die Funktionen dieses Code-Abschnitts:
    // list the content of files
    ULONG i = 0;
    struct dirent* node = 0;
    while( (node = readdir_fs(fs_root, i)) != 0)
    {
        printformat("Found file %s\n",node->name);
        fs_node_t* fsnode = finddir_fs(fs_root, node->name);

        if((fsnode->flags & 0x7) == FS_DIRECTORY)
        {
            printformat("\t(directory)\n");
        }
        else
        {
            printformat("\t contents: \"");
            CHAR buf[256];
            ULONG sz = read_fs(fsnode, 0, fsnode->length, buf);
            ULONG j;
            for(j=0; j<sz; ++j)
            printformat("%c",buf[j]);
            printformat("\"\n");
        }
        ++i;
    }

Wir werden nun die Möglichkeit, das "Programm" aus dem Array  buf[...] an eine vorgesehene Stelle ( address_TEST ) zu transportieren und diese Adresse dem Prozess  test zur Ausführung zu übergeben, experimentell in die Tat umsetzen, um zu sehen, ob dies auch wirklich klappt:
#include ...
...
ULONG ramdisk_start = 0x40081000; // In the heap
UCHAR address_TEST[256];
...
void test()                   
{
  while(TRUE)
  {
      asm volatile("call *%0"::"r"(address_TEST));
      ...
  }
}

int main()
{
    ...
    k_memcpy((void*)ramdisk_start, &file_data_start, (ULONG)&file_data_end - (ULONG)&file_data_start); // process.asm
    fs_root = install_initrd(ramdisk_start);

    // list the content of files <- data from outside "loaded" by incbin ...
    ULONG i = 0;
    struct dirent* node = 0;
    while( (node = readdir_fs(fs_root, i)) != 0)
    {
            ...
            UCHAR buf[256];
            ULONG sz = read_fs(fsnode, 0, fsnode->length, buf);

            ULONG j;
            for(j=0; j<sz; ++j)
            {
                if( k_strcmp(node->name,"Test-Programm")==0 )
                {
                    printformat("%x ",buf[j]);
                    address_TEST[j] = buf[j];
                }
                else
                    printformat("%c",buf[j]);
            }
            printformat("\"\n");
        }
        ++i;
        printformat("\naddress_TEST: %x",address_TEST);
    }

    ...   
    create_task(test);
    ...
}

Ausdruck (etwas gekürzt):
Found file Test-Programm
         contents: "C6h 05h 00h 80h 0Bh 00h 54h C6h 05h 02h 80h 0Bh 00h 65h C6h 05h
                    04h 80h 0Bh 00h 73h C6h 05h 06h 80h 0Bh 00h 74h C3h "

address_TEST: D6B0h

In obigem Beispiel werden die Files des Filesystems der RAM Disk in der while-Schleife sequentiell gelesen. Die Daten von Test-Programm landen hierbei zunächst in der lokalen Variable buf[...]. In der for-Schleife werden diese Daten in die globale Variable address_TEST übertragen.

User Mode (Ring 3) und Systemaufrufe

Beim 80x86 gibt es ab dem Protected Mode das Schutzkonzept des Privilegs. Dieses sieht vier Ebenen vor: 0, 1, 2, 3. Man spricht auch von Ring 0, Ring 3 usw.
Sie kennen dies bereits aus der GDT (Code - und Datensegmente, TSS) oder dem Page Directory Entry (für eine Page Table) als Zugriffsrecht. Der Kernel bzw. Supervisor hat das höchste Privileg, nämlich Ring 0. Er darf auf alles zugreifen und alles ausführen. Das User-Programm erhält  zur Sicherheit die niedrigsten Rechte, nämlich Ring 3. Möchte das User-Programm auf Teile des Kernels zugreifen, müssen hierfür sogenannte Systemaufrufe (system calls) eingesetzt werden.

Nachfolgend eine mögliche Realisierung der Systemaufrufe ähnlich Linux (analog Kap. 10 des Tutorials von James Molloy):

Wir verwenden den Interrupt 127 (0x7F) anstelle 128 (0x80) in Linux.

Man deklariert und definiert zunächst allgemein in syscall.h die Syntax in Abhängigkeit von der Anzahl der Parameter.
Dort werden ebenfalls konkret die für Systemaufrufe zugelassenen Funktionen (puts, putch, ...) deklariert.

In syscall.c werden diese Funktionen dann implementiert und erhalten eine laufende Nummer für das Array von Zeigern syscalls[NUM_SYSCALLS].
Wenn ein neuer systemaufruf zugelassen werden soll muss dieser also sowohl in syscall.h als auch in syscall.c exakt deklariert und definiert werden.

// syscall.h

#define DECL_SYSCALL0(fn)     int syscall_##fn();
#define DECL_SYSCALL1(fn,p1)  int syscall_##fn(p1);
// etc.

#define DEFN_SYSCALL0(fn, num) \
int syscall_##fn() \
{ \
  int a; \
  asm volatile("int $0x7F" : "=a" (a) : "0" (num)); \
  return a; \
}

#define DEFN_SYSCALL1(fn, num, P1) \
int syscall_##fn(P1 p1) \
{ \
  int a; \
  asm volatile("int $0x7F" : "=a" (a) : "0" (num), "b" ((int)p1)); \
  return a; \
}
// etc.

DECL_SYSCALL1(puts,  UCHAR*)
DECL_SYSCALL1(putch, UCHAR)
DECL_SYSCALL2(settextcolor, UCHAR, UCHAR)
DECL_SYSCALL0(getpid)
DECL_SYSCALL0(f3)
DECL_SYSCALL0(nop)
DECL_SYSCALL0(switch_context)

// -------------------------------------------------------------------
// syscall.c

DEFN_SYSCALL1( puts,                0, UCHAR*       )
DEFN_SYSCALL1( putch,               1, UCHAR        )
DEFN_SYSCALL2( settextcolor,        2, UCHAR, UCHAR )
DEFN_SYSCALL0( getpid,              3               )
DEFN_SYSCALL0( f3,                  4               )
DEFN_SYSCALL0( nop,                 5               )
DEFN_SYSCALL0( switch_context,      6               )

#define NUM_SYSCALLS 7

static void* syscalls[NUM_SYSCALLS] =
{
    &puts,
    &putch,
    &settextcolor,
    &getpid,
    &f3,
    &nop,
    &switch_context
};

Diese Systemaufrufe überbrücken z.B. die noch zu errichtende Kluft, die zwischen einem Prozess in Ring 3 und einer Funktion in Ring 0 aufgebaut wird.
Das User-Programm nutzt Systemaufrufe, um Kernel-Funktionen zu verwenden. So aufwändig dies auch ist, so ist auf diese Weise der Kernelbereich "geschützt".
Ring 0 bestimmt selbst, wer von außen, d.h. von Ring 1-3, Zugriff auf bestimmte Funktionen (Systemaufrufe) hat.
Bei  create_task(...) müssen wir bei einem Kontextwechsel zusätzlich SS und ESP auf dem Stack anbieten (Intel Manual 3A, Kap. 5.12).
Code- und Daten-Segment müssen ebenfalls für den user mode eingerichtet werden:

task_t* create_task(void* entry, UCHAR privilege)
{
    cli();
    page_directory_t* directory = clone_directory(current_directory);
    task_t* new_task            = (task_t*)k_malloc(sizeof(task_t),0,0);

    new_task->id  = next_pid++;
    new_task->page_directory = directory;
    new_task->kernel_stack   = k_malloc(KERNEL_STACK_SIZE,1,0)+KERNEL_STACK_SIZE;
    new_task->next = 0;

    task_t* tmp_task = (task_t*)ready_queue;
    while (tmp_task->next)
        tmp_task = tmp_task->next;
    tmp_task->next = new_task;

    ULONG* kernel_stack = (ULONG*) new_task->kernel_stack;

    ULONG code_segment=0x08, data_segment=0x10;

    *(--kernel_stack) = 0x0;  // return address dummy

    if(privilege == 3)
    {
        // general information: Intel 3A Chapter 5.12
        *(--kernel_stack) = new_task->ss = 0x23;    // ss
        *(--kernel_stack) = new_task->kernel_stack; // esp0
        code_segment = 0x1B;                        // 0x18|0x3=0x1B
    }

    *(--kernel_stack) = 0x0202; // eflags = interrupts activated and iopl = 0
    *(--kernel_stack) = code_segment; // cs
    *(--kernel_stack) = (ULONG)entry; // eip
    *(--kernel_stack) = 0; // error code

    *(--kernel_stack) = 0; // interrupt nummer

    // general purpose registers w/o esp
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;
    *(--kernel_stack) = 0;

    if(privilege == 3) data_segment = 0x23; // 0x20|0x3=0x23

    *(--kernel_stack) = data_segment;
    *(--kernel_stack) = data_segment;
    *(--kernel_stack) = data_segment;
    *(--kernel_stack) = data_segment;

    //setup TSS
    tss_entry.ss0   = 0x10;
    tss_entry.esp0  = new_task->kernel_stack;
    tss_entry.ss    = data_segment;


    //setup task_t
    new_task->ebp = 0xd00fc0de; // test value
    new_task->esp = (ULONG)kernel_stack;
    new_task->eip = (ULONG)irq_tail;
    new_task->ss  = data_segment;

    sti();
    return new_task;
}

Das Einrichten der Segmente für den user mode erfolgt in der Funktion gdt_install() in gdt.c.
Wir erzeugen folgende Deskriptoren, die zusätzlich User-Segmente für Code und Daten schaffen:

void gdt_install()
{
    /* Setup the GDT pointer and limit */
    gdt_register.limit = (sizeof(struct gdt_entry) * NUMBER_GDT_GATES)-1;
    gdt_register.base  = (ULONG) &gdt;

    /* GDT GATES -  desriptors with pointers to the linear memory address */
    gdt_set_gate(0, 0, 0, 0, 0);                // NULL descriptor
    gdt_set_gate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); // CODE, privilege level 0 for kernel code
    gdt_set_gate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); // DATA, privilege level 0 for kernel code

    //...
    gdt_set_gate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF); // User mode code segment
    gdt_set_gate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF); // User mode data segment
    //...
   
    write_tss(5, 0x10, 0x0);                    // num, ss0, esp0

    gdt_flush((ULONG)&gdt_register);
    tss_flush();                    
}

In ckernel.c verwenden wir den user mode (Ring 3) für die Funktion f3. Daher müssen wir die entsprechenden Systemaufrufe anstelle der normalen Kernel-Funktionen verwenden, ansonsten erfolgt eine Exception.
void f2()
{
    while(TRUE)
    {
      settextcolor(getpid(),0);
      putch(getpid()+'@');
      switch_context();
    }
}

void f3() //user mode at ring 3 requires syscall_...
{
    while(TRUE)
    {
      syscall_settextcolor(syscall_getpid(),0);
      syscall_putch(syscall_getpid()+'@');
      syscall_switch_context();
    }
}

//...

    // create two additional tasks
    /* task_t* task2 = */ create_task (f2,0); // kernel mode (ring 0)
    /* task_t* task3 = */ create_task (f3,3); // user mode   (ring 3)

Zum Beispiel, wenn man folgenden Code verwendet ...
void f3() //user mode at ring 3 requires syscall_...
{
    while(TRUE)
    {
      /*syscall_*/settextcolor(syscall_getpid(),0);
      syscall_putch(syscall_getpid()+'@');
      syscall_switch_context();
    }
}

... erhält man dieses Resultat:
AB

Page Fault ( read-only - write operation user-mode) at 0000D6F4h - EIP: 0000D025h
err_code: 00000007h address(eip): 0000D025h edi: 00000000h esi: 00000000h ebp: 402097DCh
eax: 00000003h ebx: 00000000h ecx: 00000000h edx: 00000003h
cs: 0000001Bh ds: 00000023h es: 00000023h fs: 00000023h gs 00000023h ss 00000023h
int_no 14 eflags 00010206h useresp 402097DCh

Page Fault >>> Exception. System Halted! <<<

Unser Programm f3, das im user mode läuft, versucht auf diese Weise die nur lesbare Kernel-Funktion settextcolor(...) auszuführen.
Hier greift der "Protected Mode" mit einem Page Fault ein, unterbindet und meldet diesen "unerhörten" Vorgang.

Dies zeigt deutlich, dass man aus dem user mode heraus nur Systemaufrufe verwenden darf, um Funktionen im Ring 0 aufzurufen.

Nun verfolgen wir den etwas verschlungenen Pfad von syscall_... im Code:

In  isr.asm  findet sich der Aufruf von fault_handler:
global _isr127 ; syscall

_isr127:
    cli
    push dword 0
    push dword 127
    jmp isr_common_stub

isr_common_stub:
    push eax
    push ecx
    push edx
    push ebx
    push ebp
    push esi
    push edi
   
    push ds
    push es
    push fs
    push gs

    mov ax, 0x10
    mov ds, ax
    mov es, ax
    mov fs, ax
    mov gs, ax
   
    push esp              ; parameter of _fault_handler
    call _fault_handler   
    ...

Die Funktion fault_handler findet sich in isrs.c. Sie wird eingesetzt, um Exceptions zu behandeln. Wir verwenden diesen Weg auch für syscall_...
Wir übergeben in der Assemblerroutine esp als Argument an die Funktion fault_handler. Der Stackpointer kommt von der alten Task. Bei einem Systemaufruf wechseln wir nicht grundsätzlich die Task. Wir rufen die Funktion syscall_handler(r) auf, die sich um den Aufruf der korrekten Kernel-Funktion kümmert:

ULONG fault_handler(ULONG esp)
{
    ULONG retVal;
    struct regs* r = (struct regs*)esp;

    if(!pODA->ts_flag){ retVal = esp; }
    else
    {
        if(r->int_no == 127) { retVal = esp; }
        else                 { retVal = task_switch(esp); }
    }

      //...

    if (r->int_no == 127)    { syscall_handler(r); }
    return retVal;
}

void syscall_handler(struct regs* r)
{
    if( r->eax >= NUM_SYSCALLS ) return; // Syscall number in EAX valid?
    void* address = syscalls[r->eax];    // Syscall address
    int ret;

    asm volatile ("   \
      push %1;        \
      push %2;        \
      push %3;        \
      push %4;        \
      push %5;        \
      call *%6;       \
      add $20, %%esp; \
    " : "=a" (ret) : "r" (r->edi), "r" (r->esi), "r" (r->edx), "r" (r->ecx), "r" (r->ebx), "r" (address));

    r->eax = ret;
}

In eax wird die Nummer des Syscalls übergeben, die über das statische Array zur Adresse der Kernel-Funktion führt. Dienzugehörigen Argumente werden in syscall_handler auf den Stack gelegt. nach dem Aufruf der gewünschten Kernel-Funktion wird der Stack bezüglich der Argumente wieder aufgeräumt.

Nach dem Aufruf von fault_handler mit der Interrupt-Nr. 127 geht es wie folgt weiter:
    global _fault_tail
 
_fault_tail:
    mov esp, eax          ; return value: changed or unchanged esp
   
    pop gs
    pop fs
    pop es
    pop ds
   
    pop edi
    pop esi
    pop ebp
    pop ebx
    pop edx
    pop ecx
    pop eax
   
    add esp, 8
    iret

Der Interrupt wird mit iret beendet. Sie erkennen, dass ein Systemaufruf eine "teure" Angelegenheit ist. Der Protected Mode fordert seinen Tribut.

Cross-Compiler, mingw32-make, makefile, elf32-Format


Für die Übersetzung des Assembler-Codes in linkbare Objektdateien haben wir bisher mit dem Linker ld 2.13 aus DJGPP die Formate aout und coff verwendet. Das Format coff benötigt hierbei reinrassigen 32-Bit-Code. Das Format elf wird von ld 2.13 nicht akzeptiert, dafür benötigt man modernere Versionen.

Format
 Bemerkungen
aout: packt 16/32 bit code gemischt, passt für den ld 2.13, aber nicht für den Linker in den cross-tools
coff: funktioniert nur mit reinem 32 bit code, passt für den ld 2.13 und Linker in den cross-tools
elf: Linker in den cross-tools verarbeitet dieses Format, jedoch nicht der ältere ld 2.13 aus DJGPP

Cross-Compiler

Wir setzen nun auf unserem Host-System Windows einen Cross-Compiler ein. Optimal ist folgender Link, der einem das Leben deutlich erleichtert:
http://lowlevel.brainsware.org/wiki/index.php/Crosscompiler_f%C3%BCr_Windows
Vergessen Sie nicht, den Pfad entsprechend einzustellen.

mingw32-make

Man benötigt hierfür ergänzend noch ein möglichst mächtiges make-Tool, nämlich mingw32-make ab Version 3.81. Das findet sich in unserem Editor code::blocks oder direkt hier:
http://sourceforge.net/project/showfiles.php?group_id=2435&package_id=23918

makefile

Nun benötigen wir noch ein makefile mit Variablen, damit wir leicht Experimente durchführen und nicht alle Dateien einzeln aufführen müssen. Hier ist es:
 
SOURCES = kernel.asm $(filter-out file_data.asm boot.asm kernel.asm make_initrd.c,$(wildcard *.asm *.c))
OBJECTS = $(addsuffix .o,$(basename $(SOURCES)))

ASFLAGSBIN= -O32 -f bin
ASFLAGSOBJ= -O32 -f elf
NASM = nasmw

CFLAGS=    -O -ffreestanding -fleading-underscore   
CC= i586-elf-gcc

LDFLAGS= -T kernel.ld -Map kernel.map
LD= i586-elf-ld

all: boot.bin ckernel.bin
    make -s image
    make -s floppyimage

process.asm: file_data.dat file_data.da1

file_data.dat: file_data.asm
    $(NASM) $(ASFLAGSBIN) $< -o $@

boot.bin: boot.asm
    $(NASM) $(ASFLAGSBIN) $< -o $@

%.o: %.asm
    $(NASM) $(ASFLAGSOBJ) $< -o $@

ckernel.bin: $(OBJECTS)
    $(LD) $(LDFLAGS) $+ -o $@
   
image:
    cmd /c copy /b boot.bin + ckernel.bin MyOS   
    del *.o
    del *.bin
    cmd /c rename MyOS MyOS.bin

floppyimage:   
    partcopy MyOS.bin 0 7000 -f0   

#    $<        Erste Abhängigkeit
#    $+        Liste aller Abhängigkeiten   
#    $@        Name des Targets

Mit dieser Toolchain kann man nun auch andere OS, z.B. als Kernel im elf-Format kompilieren/linken, ohne auf Linux als Entwicklungssystem ausweichen zu müssen.

elf32-Format

Was ist nun dieses elf-Format? Der Name kommt von "Executable and Linking Format ". Dieses Format wurde 1995 in Linux eingeführt. Es ist der Nachfolger der Formate aout und coff.

Man unterscheidet verschiedene elf-Formate:

Wir probieren zunächst experimentell aus, wie sich das elf-Format darstellt.


elf32-object-Format

Unser kleines TEST-Programm wurde bisher im Binär-Format erzeugt, also nur Code, sonst nichts.
Nun verändern wir im makefile das Format von binär auf elf32:

ASFLAGSBIN= -O32 -f bin
ASFLAGSOBJ= -O32 -f elf

file_data.dat: file_data.asm
    $(NASM) $(ASFLAGSOBJ) $< -o $@

Damit erhalten wir nun unser Programm im elf-Format als linkbares Objekt-File. Mit unserem primitiven Filesystem in der RAM Disk klappt dies nun nicht mehr, weil sich der Offset in der Objekt-Datei gegenüber dem Binär-Format um 0x130 verschoben hat (könnte man im File-Header leicht anpassen), denn wir haben nun einige Informationen, bevor der eigentliche Code beginnt. Schauen wir uns beide Formate im direkten Vergleich zunächst im Hex-Editor an: elf32 (object-file) und binär:


Mit dem bin-Tool  i586-elf-readelf.exe  kann man folgende Informationen aus dem neu erzeugten elf-Objekt-File auslesen:
G:\OSDev\Test\50 cp>i586-elf-readelf.exe -a file_data.dat
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          64 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           40 (bytes)
  Number of section headers:         6
  Section header string table index: 3

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al

  [ 0]                   NULL            00000000 000000 000000 00      0   0  0

  [ 1] .text             PROGBITS        00000000 000130 00001d 00  AX  0   0 16

  [ 2] .comment          PROGBITS        00000000 000150 00001f 00      0   0  1

  [ 3] .shstrtab         STRTAB          00000000 000170 00002a 00      0   0  1

  [ 4] .symtab           SYMTAB          00000000 0001a0 000040 10      5   4  4

  [ 5] .strtab           STRTAB          00000000 0001e0 000015 00      0   0  1

Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings)
  I (info), L (link order), G (group), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

There are no relocations in this file.

There are no unwind sections in this file.

Symbol table '.symtab' contains 4 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 00000000     0 FILE    LOCAL  DEFAULT  ABS file_data.asm
     2: 00000000     0 SECTION LOCAL  DEFAULT    1
     3: 00000000     0 NOTYPE  LOCAL  DEFAULT    1 start

No version information found in this file.

In der ersten Zeile erkennt man die elf-Datei an ihrer magic Number: 0x7f gefolgt von den ASCII-Werten E (0x45), L (0x4c), F (0x46)
Die "Class" (elf32) zeigt, dass es sich um eine 32-Bit-Maschine handelt.
Der Typ der Datei ist REL, was bedeutet, dass es sich um eine linkbare Objekt-Datei  handelt (Gegensatz: EXEC, ausführbare Datei).

In nachfolgender Abbildung ist der Aufbau der Objekt-Datei im elf-Format an obigem Beispiel etwas genauer dargestellt:

elf32-exec-Format

Mit der Anweisung  i586-elf-ld -nostdinc -o program.elf file_data.dat  kann man mittels Linker aus der elf-Objektdatei eine ausführbare Datei im elf-Format erzeugen.
Hierbei gibt der Linker folgende Warnung aus:  i586-elf-ld: warning: cannot find entry symbol _start; defaulting to 08048060

Die ausführbare Datei ist um einiges größer. Unser kleines Programm finden wir nun am Offset 0x60:



... und wieder setzen wir unser Tool readelf ein:
G:\OSDev\Test\50 cp>i586-elf-readelf -a program.elf
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x8048060
  Start of program headers:          52 (bytes into file)
  Start of section headers:          200 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         1
  Size of section headers:           40 (bytes)
  Number of section headers:         6
  Section header string table index: 3

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al

  [ 0]                   NULL            00000000 000000 000000 00      0   0  0

  [ 1] .text             PROGBITS        08048060 000060 00001d 00  AX  0   0 16

  [ 2] .comment          PROGBITS        00000000 00007d 00001f 00      0   0  1

  [ 3] .shstrtab         STRTAB          00000000 00009c 00002a 00      0   0  1

  [ 4] .symtab           SYMTAB          00000000 0001b8 000080 10      5   5  4

  [ 5] .strtab           STRTAB          00000000 000238 00002d 00      0   0  1

Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings)
  I (info), L (link order), G (group), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x000060 0x08048060 0x08048060 0x0001d 0x0001d R E 0x10

 Section to Segment mapping:
  Segment Sections...
   00     .text

There is no dynamic section in this file.

There are no relocations in this file.

There are no unwind sections in this file.

Symbol table '.symtab' contains 8 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 08048060     0 SECTION LOCAL  DEFAULT    1
     2: 00000000     0 SECTION LOCAL  DEFAULT    2
     3: 00000000     0 FILE    LOCAL  DEFAULT  ABS file_data.asm
     4: 08048060     0 NOTYPE  LOCAL  DEFAULT    1 start
     5: 0804907d     0 NOTYPE  GLOBAL DEFAULT  ABS __bss_start
     6: 0804907d     0 NOTYPE  GLOBAL DEFAULT  ABS _edata
     7: 08049080     0 NOTYPE  GLOBAL DEFAULT  ABS _end

No version information found in this file.

Detaillierte Informationen über das elf-Format findet man z.B. hier. Damit schaffen Sie es sicher selbst, dieses ausführbare Format für unseren konkrten Fall zu zerlegen.
Versuchen Sie es.

Vergleicht man elf-object- und -executable-Format, so findet man folgenden grundsätzlichen Aufbau:



Der "Program Header" im ausführbaren elf-Format ist wie folgt aufgebaut:
t y p e d e f s t r u c t
{
  E l f 3 2 _ W o r d    p _ t y p e ;
  E l f 3 2 _ O f f      p _ o f f s e t ;
  E l f 3 2 _ A d d r    p _ v a d d r ;
  E l f 3 2 _ A d d r    p _ p a d d r ;
  E l f 3 2 _ W o r d    p _ f i l e s z ;
  E l f 3 2 _ W o r d    p _ m e m s z ;
  E l f 3 2 _ W o r d    p _ f l a g s ;
  E l f 3 2 _ W o r d    p _ a l i g n ;
}
E l f 3 2 _ P h d r ;

Mit dieser Information können wir den program header (hier ab offset 0x34) analysieren:



Typ = 01 bedeutet hier:
PT_LOAD: The array element specifies a loadable segment, described by p_filesz and p_memsz. The bytes from the file are mapped to the beginning of the memory segment.
If the segment’s memory size (p_memsz) is larger than the file size (p_filesz), the ‘‘extra’’ bytes are defined to hold the value 0 and to follow the segment’s initialized area.
The file size may not be larger than the memory size. Loadable segment entries in the program header table appear in ascending order, sorted on the p_vaddr member.



User Mode (Fortsetzung)

Der Kernel wird abgeschottet

Zunächst müssen wir hier etwas klären: Der bisherige Kernel von PrettyOS war aus Sicht von Ring 3 ziemlich "User-freundlich", weil die Pages auf "user" und "read-only" eingestellt waren. Daher konnten wir mittels create_task aus Ring 3 eine Kernel-Funktion aufrufen. Für einen echten Kernel müssen wir diesbezüglich gegenüber dem user-space einen deutlichen Riegel vorschieben:

//in paging.h
#define SV   1   // supervisor
#define US   0   // user

#define RW   1   // read-write
#define RO   0   // read-only

//in paging.c
alloc_frame( get_page(i, 1, kernel_directory), SV, RO); // supervisor and read-only
 
Auch beim Kernel-Heap halten wir die User nun fern:

for( i=KHEAP_START; i<KHEAP_START+KHEAP_INITIAL_SIZE; i+=0x1000 )
    alloc_frame( get_page(i, 1, kernel_directory), SV, RW); // supervisor and read/write

kheap = create_heap(KHEAP_START, KHEAP_START+KHEAP_INITIAL_SIZE, KHEAP_MAX, 1, 0); // supervisor and read/write

User-Pages

Um User-Programme nicht nur in Ring 3 (entsprechendes Code- und Datensegment), sondern zusätzlich auch auf "User-Pages" laufen zu lassen, schaffen wir einen Bereich zwischen 0x400000 und 0x500000, dessen Pages als "user" gekennzeichnet sind.

    //Allocate user space
    ULONG user_space_start = 0x400000;
    ULONG user_space_end   = 0x500000;
    i=user_space_start;
    while( i < user_space_end )
    {
        alloc_frame( get_page(i, 1, kernel_directory), US, RO); // user and read-only
        i += PAGESIZE;
    }

User-Programme

Bezüglich der Erstellung der User-Programme schaffen wir uns nun eigene Unterverzeichniss und Linkerskripts:

- user
    - user_programm
    - init_rd_img

Da wir nun das elf-executable-Format kennen, werden wir dieses einsetzen. Im Verzeichnis user_program findet man nun die Quellcode-Datei program.asm, die mit folgendem Linkerskript (user.ld) und makefile in program.bin, program.o und program.elf umgesetzt wird:
ENTRY(_start)
OUTPUT_FORMAT(elf32-i386)
 
SECTIONS
{
    . = 0x400100;
   
    .text :
    {
      *(.text*)
    }
    .data :
    {
      *(.data*)
      *(.rodata*)
    }
    .bss :
    {
      *(.bss*)
    }
}
ASFLAGSBIN= -O32 -f bin
ASFLAGSOBJ= -O32 -f elf
NASM = nasmw

CFLAGS=    -O -ffreestanding -fleading-underscore   
CC= i586-elf-gcc

LDFLAGS= -T user.ld -Map kernel.map -nostdinc
LD= i586-elf-ld

all: program.bin program.elf

program.bin: program.asm
    $(NASM) $(ASFLAGSBIN) $< -o $@

program.o: program.asm
    $(NASM) $(ASFLAGSOBJ) $< -o $@

program.elf: program.o
    $(LD) $(LDFLAGS) $+ -o $@

#    $<        Erste Abhängigkeit
#    $+        Liste aller Abhängigkeiten   
#    $@        Name des Targets

Die erzeugte Datei program.elf kopieren wir in das Verzeichnis init_rd_img. Dort findet sich folgendes makefile:
all:
    make_initrd test1.txt file1 test2.txt file2 test3.txt file3 program.elf Test-Programm

Damit wird unser elf-executable-Programm in das selbst definierte Filesystem der RAM Disk eingebunden. Das Ergebnis ist die binäre Datei initrd.img, die wir in das Hauptverzeichnis kopieren, damit diese nun mit dem "incbin"-Trick in den Kernel transportiert wird, von wo wir es weiter verarbeiten können. initrd.img wird folgenden Weg nehmen:
//process.asm
global _file_data_start
global _file_data_end
_file_data_start:
incbin "initrd.img"
_file_data_end:

//ckernel.c
k_memcpy((void*)ramdisk_start, &file_data_start, (ULONG)&file_data_end - (ULONG)&file_data_start);
//...
if( k_strcmp(node->name,"Test-Programm")==0 )
{
    address_TEST[j] = buf[j];
}
//...
k_memcpy((void*)address_user, address_TEST, 4096); // Test-Programm ==> user space

Mittels incbin gelangt das Image zunächst nach _file_data_start.Von dort wird es mittels Kopie nach ramdisk_start verschoben. Die Befehle des VFS helfen uns das File mit dem Programm nun zu finden und dieses nach address_TEST zu speichern. Von dort wird es nach 0x400000 kopiert. Da das elf-Format den ausführbaren Code mit dem Offset 0x60 gespeichert hat, können wir nun also an Adresse 0x400060 in das Programm einspringen.

Mit folgendem Codesnippet kann man sich sicherheitshalber vom Inhalt des Speichers überzeugen:
    ULONG j;
    for(j=0x400060; j<0x400100; ++j)
    {
        printformat("%d ",*((UCHAR*)j));
    }

Als "Programm" verwenden wir folgenden Assemblersourcecode, den wir assemblieren und linken (program.elf) und :

;program.asm:

[BITS 32]
start:
   mov [0x000b8000], byte 'T'
   mov [0x000b8002], byte 'e'
   mov [0x000b8004], byte 's'
   mov [0x000b8006], byte 't'
   mov [0x000b8008], byte ' '
   mov eax, 4
   int 0x7F
   jmp start

Ohne "Öffnung" des Video-RAM gibt es hiermit einen PageFault. Daher ist folgender kleiner Trick hierfür notwendig:
    i=0;
    while( i < placement_address + 0x2000 ) //important to add more!
    {
        if( ((i>=0xb8000) && (i<=0xbf000)) || ((i>=0xd000) && (i<0xe000)) )
        {
            alloc_frame( get_page(i, 1, kernel_directory), US, RW); // user and read-write
        }
        else
        {
            alloc_frame( get_page(i, 1, kernel_directory), SV, RO); // supervisor and read-only
        }
        i += PAGESIZE;
    }

Man ruft als User den Kernel mittels syscalls auf. Dazu gibt man die gewünschte Nummer der Funktion nach eax und ruft den Interrupt 0x7F.
Die Zahl 4, die wir eax übergeben, führt in nachstehendem Array (beginnt mit null) von Funktionszeigern (in syscall.c) zur Funktion nop():
static void* syscalls[NUM_SYSCALLS] =
{
    &puts,
    &putch,
    &settextcolor,
    &getpid,
    &nop,            // <------- Nummer 4
    &switch_context
};

Den Weg, den das User-Programm nimmt, kann man sehr gut mit dem Debugger bis zum nop() verfolgen:
<bochs:1> lb 0x00400060
<bochs:2> c
400060 (unk. ctxt): mov byte ptr ds:0xb8000, 0x54
<bochs:3> s
400067 (unk. ctxt): mov byte ptr ds:0xb8002, 0x65
40006e (unk. ctxt): mov byte ptr ds:0xb8004, 0x73
400075 (unk. ctxt): mov byte ptr ds:0xb8006, 0x74
40007c (unk. ctxt): mov byte ptr ds:0xb8008, 0x20
400083 (unk. ctxt): mov eax, 0x00000004      
400088 (unk. ctxt): int 0x7f                 
....
....
be04 (unk. ctxt): call eax
c644 (unk. ctxt): push ebp
c645 (unk. ctxt): mov ebp, esp
c647 (unk. ctxt): nop
c648 (unk. ctxt): pop ebp
c649 (unk. ctxt): ret

Nun erhält man ein erstes Gefühl für die User-Umgebung unseres PrettyOS. Immer, wenn wir den Kernel benötigen, müssen wir ihm dies in Form eines syscalls mitteilen. Das direkte Schreiben in den Video RAM sollte man einem User-Programm ebenfalls untersagen. Wir haben dies hier nur zu Testzwecken eingesetzt. 



Einfach nichts machen, ist zwar ein interessanter Test, aber nicht das Ziel eines Programms. Daher wollen wir in der nächsten Variante zwei der zur Zeit vorhandenen Syscalls testen, nämlich settextcolor(a,b) und putch(a). Wir zielen auf folgendes ab: Die Vordergrundfarbe soll auf rot (4) und die Hintergrundfarbe auf schwarz (0) gesetzt werden. Als Buchstabe geben wir 'T' aus:
;program.asm:

[BITS 32]
start:
   mov ebx, 0x4  ; 1. Argument
   mov ecx, 0x0  ; 2. Argument
   mov eax, 2    ; settextcolor
   int 0x7F
  
   mov ebx, 0x54 ; 'T'
   mov eax, 1    ; putch
   int 0x7F
  
   jmp start

Wie man die Argumente an eine via Syscall aufgerufene Funktion übergibt, hängt vom Aufbau im Syscall-Handler ab. Bei PrettyOS haben wir das so gelöst, dass die maximal 5 Argumente in den Registern ebx, ecx, edx, esi, edi (Reihenfolge der Argumente von links nach rechts aufgeführt) übergeben werden:

// syscall.c:

void syscall_handler(struct regs* r)
{
    if( r->eax >= NUM_SYSCALLS )  return;
    void* addr = syscalls[r->eax];
    int ret;
    asm volatile (" \
      push %1; \
      push %2; \
      push %3; \
      push %4; \
      push %5; \
      call *%6; \
      add $20, %%esp; \
    " : "=a" (ret) : "r" (r->edi), "r" (r->esi), "r" (r->edx), "r" (r->ecx), "r" (r->ebx), "r" (addr));
    r->eax = ret;
}

Wie Sie sehen funktioniert das Wechselspiel zwischen User-Programm und Kernel-Funktionen bestens.
Das User-Programm gibt sein rotes 'T' solange nacheinander aus, bis der 100 Hz-Timer die Tasks via IRQ0 umschaltet.
Wir benötigen hier keinen direkten Zugriff auf das Video RAM.
Das Multitasking zwischen dem User-Prozess und den drei Kernel-Prozessen läuft wie erwartet:



Will man, dass der User-Prozess selbst die Kontrolle abgibt, so ruft man syscall_switch_context() auf:
[BITS 32]
start:
   mov ebx, 0x4  ; 1. Argument
   mov ecx, 0x0  ; 2. Argument
   mov eax, 2    ; settextcolor
   int 0x7F
  
   mov ebx, 0x54 ; 'T'
   mov eax, 1    ; putch
   int 0x7F
  
   mov eax, 5    ; switch_context
   int 0x7F
  
   jmp start




Nun haben wir eine erste Basis für die Weiternentwicklung von PrettyOS auf User-Applikations-Ebene gelegt.
PrettyOS könnte sich von nun an z.B. wie folgt melden:



Probieren Sie diese Umgestaltung!

Nun rücken die Themen Kernel-Design und User-Programme in den Mittelpunkt.
Dieser Themenkreis wird in Teil 3 dieses Tutorials behandelt.