
Memory-Layout von Topsy v3 (ia32)
============================================================

Includes:
  Topsy/ia32/cpu.h 
             CoreLoad.h
  Memory/ia32/MemoryLayout.h
              MMHal.c
  Boot/ia32/LowCore/CoreLoad/coreload.inc


KERNEL MEMORY
------------------------------------------------------------
Physical memory        : 0x00000000-   PhysMax = xxxMB
Memory management      : 0x00000000-0xffffffff =   4GB 
Control structures     : 0x00000000-0x   20000 = 128KB
  GDT                  : 0x    1000-0x   10000 =  60KB
  IDT                  : 0x   10000-0x   11000 =   4KB
  BSP TSS              : 0x   1E000-0x   1E068 =  104B
Kernel Code            : 0x   20000-0x   38000 =  96KB
Kernel Data            : 0x   38000-0x   3F000 =  28KB
User Code / Data       : 0x  200000-0x  20c6a8 =  @2MB
Steal Allocator        : 0x  800000-0x   xxxxx =  @8MB
Hardware IO            : 0x   A0000-0x  100000 =
IO-APIC                : 0xfec00000-0xfed00000 =
APIC                   : 0xfee00000-0xfef00000 =
Kernel Mode Stacks     : 0xc0000000-0x     xxx =  @3GB


SEGMENTIERUNG
------------------------------------------------------------
GDT                       : Base      : Size      : Sel
   0: Dummy
   1: OS Code             : 0x     0  : 4GB       : 0x8
   2: OS Data             : 0x     0  : 4GB       : 0x10
   3: OS Global           : 0x     0  : 4GB       : 0x18
   4: OS Video            : 0x B8000  : 0xFBF     : 0x20
   5: OS GDT              : 0x  1000  : 64KB      : 0x28
   6: IDT Alias           : 0x 10000  : 1 Page    : 0x30
   7: BSP TSS             : 0x 1E000  : 104Byte   : 0x38
   8: BSP TSS Alias       :                       : 0x40
   i: Memory Mapped IO    : vom Ende des physikalischen Speichers an
                              für jedes Device 1 Segment, auf Pagegrösse aufgerundet
   j: 3 Segmente pro Prozess: Code, Data, TSS ???
   
   Einfachkeitshalber alle Segmente in GDT registrieren
     -> Dies limitiert die maximale Anzahl von gleichzeitig lauffähigen Prozessen auf ~2k.
   Basisadresse im GDT Register (lgdt, sgdt)
        
LDT
  Ist im GDT registriert.
  Basisadresse im LDT Register (lldt, sldt), gehört zum TSS jedes Prozesses
  LDT enthält max 8192 Deskriptoren à 8Byte
    -> bis 64KB gross -> 16 Pages (512 Segmente pro Page)

  
Layout (virtuelle Adressen)
   4GB :
  >3GB :  Kernel Mode Stack
   xxx :  MMIO
  pmax :  Stack
       :   ||
       :   \/
       :  Free, Shared Libraries, Page Loan
       :   /\
       :   ||
       :  Heap
       :  BSS
       :  Data
   xxx :  Text    
     0 :  Kernel-Strukturen: GDT, IDT, ...

  - Page Loan in den freien Bereich in der Mitte
  - Protection Domain = 3 Segmente: Code, Data, (TSS ???) 
  (- Segmente an 4MB Page-Table Grenze ausrichten)


PAGING
------------------------------------------------------------

Globale Bitmap der Pagebelegung im PDT Segment.
Kein Auslagern von Pages.

Kein PAE: 4GB sollten reichen

Page Directories
  1 für Kernel
  1 pro Prozess
    -> verschiedene Mappings für verschidene Prozesse
    -> Schützt Memory vor Übergriffen anderer Prozessen, wenn Mappings disjunkt
    -> Pro Prozess 1 Page mit Page Directory


Page Tables:
  (Lokalität in Page Tables erstrebenswert, da gemeinsam im Cache.)
  jeder Prozess hat Menge von Page Tables
    1 Page Table belegt eine Page und verwaltet 4MB Speicher
    
    

Implementierung
  Speicher anlegen:
    pro Prozess:
      1 Page Directory                  : 1 Page
      k Page Tables                     : k Pages (zB 1024 für 4GB VM)
     
    Global  
      TSS-Segmente                    : 2 Pages (für ~80 TSS)
      Verwaltungsinformationen        : im Datensegemnt des Kernels

    Benötigter Speicher für n Prozesse:
      n(1 + k) Pages für n Prozesse à k Page Tables
        n <= 2k    :  Limitierung der GDT   : MAX_PROCESSES = 50    : wie im ixp2400 Port
        k <= 1024  :  4GB VM                : MAX_PT        = 16    : 64 MB VM pro Prozess 
                                                => 850 Pages, 3.4MB Verwaltungsinformationen

  Speicher organisieren: (wie ixp2400)
    alloziiere ~4MB Memory
    Fülle Speicher "von oben"  mit Page Tables
                   "von unten" mit Page Directories
    Statische Variablen:
                   pmap_freelist_pdir     : Listenkopf der Löcher im PDir-Segment
                   pmap_freelist_ptbl     : ""         ""  ""        PTbl-Segment
                   pmap_pdir_seg_top      : Oberer  Rand des PDir-Segments 
                   pmap_ptbl_seg_bottom   : Unterer Rand des PTbl-Segments
                   pmap_vbase             : virtual Base 
                   pmap_pbase             : physical Base
                   pmap_buf_size          : Grösse des Buffers
    
    Beispiel:
            _____________   TOP = pmap_vbase + pmap_buf_size (pmap_pbase + pmap_buf_size)
       12  |  PTbl 1     | 
       11  |  PTbl 2     |
       10  | ->next free |  pmap_free_ptbl = 10
        9  |  PTbl 3     |  pmap_ptbl_seg_bottom = 9
        8  |             |
        7  |             |
        6  |             |
        5  |             | 
        4  |  PDir 3     |  pmap_pdir_seg_top = 4
        3  |  PDir 2     |
        2  | ->next free |  pmap_free_pdir = 2
        1  |  PDir 1     |
            ̅̅̅̅̅̅̅̅̅̅̅̅̅   BOTTOM = pmap_vbase (pmap_pbase)


    Wohin mit Strukturen, welche im ProcContext sein müssen, aber ims vm_pmap gehören, da für alle Threads eines PD gleich? 
          int tf_ldt_seg;
          int tf_pdbr;
          unsigned short tf_tss_seg;
          unsigned short tf_tss_alias;
    ??? Was sollte passieren wenn:
          1) Adressen in vm_pmap_enter() nicht an Pagegrenze ausgerichtet sind?
              -> OK
          2) Adressen in vm_pmap_region_enter() nicht an Pagegrenze ausgerichtet sind?
              -> ausrichten, Waste
          3) Virtuelle Adresse schon gemappt
              a) phys, flags identisch -> OK
              b) phys identisch -> ???
              c) phys unterschiedlich -> Fehler
    numerischer Typ von void pointern ist unsigned long.
    ??? mapSpecialRegions() in vm_hal.c:
         - Memory Mapped IO Area: 0x80000-0xe0000 
         - MSR_MAP_LLV			0x0001    Low Level Mapping, aktualisiere pmap mit vm_pmap_region_enter()
         - MSR_MAP_HLV			0x0002    High Level Mapping, aktualisiere map mit vm_region_add()
         - MSR_MAP_ALL			0x0003    LLV | HLV
         - MSR_IN_KERNEL		0x0004    MSR for Kernel
    ??? Wie werden getSegStart() und getSegEnd() verwendet?

  Aktivieren der MMU:
    1. Laden des PDBR nach cr3
    2. Aktivieren des PE-Bits in cr0
    3. Long jump leert Pipeline
    
  
FRAGEN zum DESIGN ???
------------------------------------------------------------
Segmentierung:
  Eigendlich braucht es nur 2 Code- und 2 Daten-Segmente, jeweils für USER und KERNEL
  
Paging
  Wieso nur 2 PD? 
  
  

THREADS
------------------------------------------------------------

Datenstrukturen im PD des tmThreads und an gleicher Stelle im Zielthread:
  Thread 
  ProcContext
    ProcStackFramePtr : Pointer auf aktuellen Zustand auf dem Kernel Stack
    ProcTSSPtr        : Pointer auf TSS der aktuellen CPU 
    esp0              : Stack Pointer auf Exception Stack
    ss0               : Stack Segment des Exception Stacks
  Kernel Mode Stack
  => 2 Pages sollten reichen, schliesslich ist der ProcContext und der Stack relativ klein. 
        zum Schutz könnte man ss0 auf 2 Pages reduzieren, anstatt KDSEG zu verwenden??? 
  
TSS:
  Jeder CPU ist ein TSS mit den aktuellen Infos des laufenden Threads zugeordnet (wie Linux).

Unterbrechungen:
  User   -> Kernel    : Springe an den Beginn des Kernel Mode Stacks
  User   <- Kernel    : Springe zurück auf den User Mode Stack
  
  Kernel -> Kernel    : Kernel Stack wird weiter verwendet
  Kernel <- Kernel    : Kernel Stack wird abgebaut, "wieder wie vorher"


SaveContext von prev:
  a) SOFTWARE SWITCHING:
  
      Kernel (Mode) Stack: 
         +-----------------------------+
      8k | ProcStackFrame 0            |  ⎫  Interrupt 0
         |  :                          |  ⎮
         |  esp=xxx                    |  ⎮
         |  :                          |  ⎬ Stack-Frame 0  
         | status = xxx                |  ⎮
         | prio = xxx                  |  ⎮
         | last = 0                    |  ⎭ <- last des ProcStackFrames 0 ist immer 0
    8k-n | Stack 0                     |  ⎫ Stack des Interrupt Handlers 0
         |  :                          |  ¦  
         +-----------------------------+  
       y | ProcStackFrame 1            |  Interrupt 1
         |  :                          |
         | esp=y                       |    
         |  :                          |  
         | status = xxx                |
         | prio = xxx                  |
         | last = 8x                   |
     y-n | Stack 1                     |
         |  :                          |
         +-----------------------------+
       z | ProcStackFrame 2            |  Interrupt 2
         |  :                          |
         | esp=z                       |    
         |  :                          |
         | status = xxx                |
         | prio = xxx                  |
         | last = y                    |
     z-n | Stack 2                     |
         |  :                          |
         +-----------------------------+
         |  :                          |  <= %esp 
         | Thread                      |  Verwaltungsinformationen
       0 | ProcContext                 |  
         +-----------------------------+  
         
      Kernel/User Stack when running normaly:
         +-----------------------------+
         | exit Message                | ⎫
         | exit Code                   | ⎮
         | Argument 1                  | ⎬ Beende Thread, wenn Funktion returnt
         | Argument 0                  | ⎮
         | Return Address              | ⎭
         +-----------------------------+
         | Stack (StackFrame for KTS)  | ⎫ Stack, esp points to here (for KTS the Stack overwrites the StackFrame after restoreContext)
         | :                           | ¦
         +-----------------------------+
         
  
    1. INTGATE: DPL=0, CS=KCSEL0, 
        Wechsle auf den Kernel Mode Stack des laufenden Threads.
          Die CPU erledigt dies anhand des TSS, wenn ein Privilegienwechsel stattfindet. 
          Wenn man schon im Ring 0 ist, wird der normale Stack weiterverwendet.
    2. __general_ExceptionHandler()
        Speichert Hardware Kontext auf Stack, lässt Raum für Scheduling-Infos
        Wenn kein Privilegienwechsel stattgefunden hat:
          muss nichts unternommen werden, da man "den gleichen Weg" zurück nimmt
          -> ACHTUNG: keine Schreibzugriffe auf esp und ss des StackFrames, da diese auf Bereiche im "alten" Stack zeigen!
        Setzt %ds und %es auf das Kernel Daten Segment
    3. _INTHandler(ProcStackFrame procStackFrame)
        Speichere Pointer zu letztem Stack-Frame auf Stack-Frame
        Setze procStackFramePtr des Threads auf Kontext im Kernel Stack
        Wechsele in VM des tmThreads (mainKernelPD)
          -> %esp sollte immer noch auf gleiche Position im Kernel Mode Stack zeigen
              => Kernel Mode Stack im mainKernelPD an gleiche Stelle mappen...
        Gib ihm eine höhere Priorität
        sti ???
          -> da Stack-Frame vollständig aufgebaut
          -> Achtung: scheduler Funktionen setzen Lock. Besonders bei schedulerSetBlocked() müssen Interrupts aber maskiert sein, was zu einem Deadlock führen kann, wenn andere Scheduler-Funktionen unterbrochen werden können.
              -> Interrupts bei allen Scheduler-Funktionen maskieren. ???
                  cli in tmHalThreadSet*()?
    4. Behandle Interrupt
       cli: Nachfolgend darf kein Interrupt mehr kommen, Exceptions nur an bestimmten Stellen möglich
       Scheduling
        stelle status und prio vom letzten StackFrame wieder her
          -> verschiebe Thread in neue prio Queue
          -> verschiebe Thread eventuell in Blocked Queue
        schedule()
    5. restoreContext(ProcContextPtr next):  (aktueller Thread ist prev)
        speichere neues esp0 im ProcContext
          -> nicht nötig, da esp0 immer auf den Anfang des Stacks zeigt ;)
        TSS
          aktualisiere TSS der aktuellen CPU mit next.ProcTSS.esp0
        Stelle Zustand aus ProcContext wieder her: 
          CPU = next->procStackFrame:   stelle alten CPU-Zustand (zB %esp) wieder her 
        wechsle in PD von next
          -> erst, wenn auf neuem Stack, da alter Stack nicht in neuem PD
        setze next->procStackFrame auf next->procStackFrame->tf_last
        iret
          Baut Kernel Mode Stack wieder ab und springt an Stelle zurück, bevor Interrupt aufgetreten ist.
          
     ???
       - Wohin mit dem Kernel Stack? 
          -> @3GB
       - Wohin mit dem TSS-Array?
          -> noch kein Array ;)
       - Initialisierung in TSSInit() (Init.c) und tmInit() (topsyMain() in Startup.c)
          -> Änderungen im architekturunabhängigen Teil
       - CPU-affines Scheduling: schedule(tm_this_cpu())
          -> viele Locks, immer in "aufsteigender Reihenfolge" anfordern.
           
            
  b) HARDWARE SWITCHING
      1. INTGATE: TSS zum tmThread
      2. _INTHandler()
          Sucht laufenden Thread
          Kopiere Kontext aus TSS der CPU in ProcContext
          Behandle Interrupt
      3. schedule()
          finde neuen lauffähigen Task
      4. restoreContext()
          Update TSS der CPU
          JMP in TSS der CPU
      

VM eines Threads
  Kernel:
    - Sektion .sasm
      _INTHandler(),__set_PDBR(),tmThreadPdbr, restoreContext(), Interrupt Vektoren, __general_ExceptionHandler()...
    => ganzer Kernel??? -> ja
        Privilegien: "Superviser mode" (CPL<3) nicht implementierbar mit diesen Flags
        Access: Read-only
  IDT, GDT, OS Video
  TSS-Array
  Kernel Mode Stack, ProcContext

Offsets ???
  wie sollte im Assembler-Code der Offset von c-Strukturen erraten werden?
    -> Linux generiert sie automatisch in Kbuild mittels arch/i386/kernel/asm-offsets.c



ARCHITEKTUR
-----------------------

Kernel Mode Stacks
 8k gross, an 8k-Grenzen aligniert 
 zuunterst ProcContext
   -> ProcContextPtr = (%esp & ~0x2000)
 Für Kernel Threads ist Kernel Mode Stack identisch mit "normalem" Kernel Stack
   -> keine oder nur untiefe Rekursion
   -> keine dynamische Arrays
 in tmThread und Zielthread an gleiche Stelle gemappt

Stack-Frame
  Speichert Prozessor-Zustand
    bei rpl-change mit ss,esp, sonst ohne
  last-Pointer
    zeigt auf letztes Stack-Frame
    eigentlich bräuchte es den ProcStackFramePtr im Kontext und damit auch den last-Pointer nicht, da jederzeit aus dem aktuellen esp die Position des letzten StackFrames abgeleitet werden kann. Dies ist aber _sehr_ mühsam, da bei jeder Änderung einer Funktionsschnittstelle oder sogar bei Änderungen beim kompilieren, müssten die Werte angepasst werden. 

Unterbrechungen
 - Interrupts / Exceptions
    User   -> Kernel
    Kernel -> Kernel
 - Nested Exceptions
    Kernel -> Kernel
 - "Rückwege"
    Kernel <- Kernel
    User   <- Kernel

Scheduling
 Scheduling-Informationen (status, prio) auf Stack-Frame
   ermöglicht kurzzeitig höhere Priorität
     zB bei Abarbeitung eines Interrupts, da sonst Priority-Inversion auftreten kann
   status muss auf RUNNING gesetzt werden auch wenn der User Thread eigentlich BLOCKED ist, da sonst eventuell Interrupt nie fertig bearbeitet wird
   Bei Ankunft von Messages kann nicht unterschieden werden, welches StackFrame auf READY gesetzt werden muss. 
     -> INTHandler darf nicht blockieren, also kein Empfangen von Messages
     -> Immer User Thread aufwecken
 Beim Beendigung des INT-Handlers ist
  prio = prio auf Stack-Frame
  status = status auf Stack-Frame
    eventuell Thread in Blocked-Queue des Schedulers verschieben
  Erst jetzt darf schedule() ausgeführt werden, sonst wird Thread anhand vom falschen Status und Priorität ausgewählt.
    -> um unnötige Kontextwechsel zu vermeiden, speichere schedflags im StackFrame, welches angibt, ob ein schedule() nötig ist. 
Implementation:
  - msgDispatcher() resp kSend() rufen tmThreadSetReady(), thThreadSetBlocked(), tmHalThreadYield() und tmThreadSetResched() auf
  - tmThread*() 
     a) wenn in einer Exception -> passe das richtige StackFrame an
      -> ändere immer StackFrame0, da andere nie blockieren dürfen!
     b) sonst rufe scheduler*() Funktionen auf
  - nach der Bahandlung des Interrupts im INTHandler werden gemäss den Flags die scheduler*() Funktionen ausgeführt.
  - schedulerSetBlocked() und schedulerSetReady() verschieben Thread in die richtige Queue



