AOS - 15 - KERNEL MEMORY-MANAGEMENT II

In x86 protected mode possiamo lavorare in due modalità diverse, a seconda della granularità delle pagine. A seconda della modalità in cui stiamo lavorando, la relativa page table avrà una struttura diversa. In particolare,

• Se lavoriamo a granularità di 4MB , la page table è una struttura flat formata da 1024 elementi, ciascuno che punta a pagine di 4MB . Infatti l'indirizzo in questa modalità è suddiviso nel seguente modo,

       <10 bits page number, 22 bit page offset>
  

• Se lavoriamo a granularità di 4KB , la page table non è più flat, ma è una struttura gerarchica formata da una tabella con 1024 elementi, in cui ciascun elemento punta ad un'altra tabella formatata nuovamente da 1024 elementi, in cui gli elementi puntano a pagine fisiche di 4KB . L'indirizzo logico in questa modalità è suddiviso nel seguente modo,

       <20 bits page number, 12 bits page offset>
  

  I bits per il page number sono poi utilizzati nel seguente modo: i primi 10 bits vengono utilizzati per capire la sezione della memoria in cui ci muoviamo, mentre gli altri 10 sono utilizzati per muoverci all'interno della page table associata a quella sezione di memoria.

Graficamente troviamo,

In entrambi i casì le informazioni presenti nelle entry della tabella ci dicono se quella entry sta puntando ad un'altra tabella oppure sta puntando alla memoria fisica.

Notiamo poi che queste tabelle non possono essere collocate in modo arbitrario nella memoria. In particolare ciascuna tabella deve essere allocata in memoria fisica in una zona allineata ai 4KB. Quindi il registro CR3 ci permette di puntare alla memoria a livello di frames.

Infine, tramite la Physical Address Exstension (PAE) siamo in grado di indirizzare fino a 64GB di memoria, anche in x86 protected mode.

Osservazione: utilizzare più livelli di paginazione rende più performante lo sharing di informazioni, specialmente in caso di modifiche.

La memoria virtuale della porzione della PGD (PDE) associata alla kernel page table è rappresentata dal simbolo swapper_pg_dir definito all'interno del file arch/i386/kernel/head.S . Il valore di questo simbolo è inizializzato a compile-time, a seconda del memory layout definito per la kernel bootable image.

Abbiamo poi delle strutture dati per definire le varie entry delle pagine, a seconda della natura della pagina. In particulare nel file include/asm-i386/page.h sono presenti le seguenti definizioni

typedef struct { unsigned long pte_low; } pte_t;
typedef struct { unsigned long pmd; } pmd_t;
typedef struct { unsigned long pgd; } pgd_t;

Notiamo che stiamo definendo in tre modi diversi lo stipo tipo base (unsigned long) per cercare di aiutare il programmatore a capire eventuali errori a compile time. In particolare in C diversi alias per lo stesso tipo sono considerati tipi uguali, e quindi possiamo fare cose come

typedef unsigned long pgd_t;
typedef unsigned long pte_t;

pgd_t x; pte_t y;

x = y; y = x

per cercare di capire se stiamo commettendo un errore, e magari assegnando ad una variabile di tipo pgd_t un valore di tipo pte_t , dobbiamo necessariamente definire delle struct diverse.

Le entry della PDE di i386, che corrispondono alle entry della PDG di Linux, possono puntare o a page table di grandezza 4KB, oppure a frame di grandezza 4MB. Il formato di una entrata della tabella PDE, che è la tabella di primo livello, è il seguente

Segue qualche precisazione:

• The Read/Write value defines the access level for a given page or sets of pages. A A 0 value means read only access.

• The write-through value indicates the caching policy for the page. A 0 value means write-back , non-zero means write-through .

• Il fatto che il present bit sia 0, non implica che le informazioni contenute importanti non sono importanti. Può succedere infatti che il software del kernel possa utilizzare le informazioni presenti nella entry, anche quando il present bit è settato a 0, ad esempio per mantenere delle informazioni sullo swap device utilizzato per swappare la pagina. Dunque l'unica cosa che possiamo concludere se il present bit è settato a 0 è che il firmware non utilizzerà le informazioni presenti nella entry.

• Gli available bits vengono utilizzati dal software di sistema. Ad esempio questi bit sono stati sfruttati per implementare un meccanismo di salvataggio automatico delle pagine logiche di un'applicazione nel caso in cui queste stanno subendo una modifica. Per fare questo in particolare posso settare tutte le pagine a read-only, e ogni volta che eseguo una scrittura posso intercettare la scrittura tramite un gestore di page-fault per vedere se la pagina era effettivamente protetta o meno utilizzando gli available bits, e nel caso in cui non fosse protetta, posso modificare il contenuto della pagina e salvare il contenuto in memoria.

• If Page size is set to 0, the address in the entry points to a 4KB 2nd level page table. Otherwise it points to a 4MB frame.

• The Accessed bit indicates wheter the page has been accessed. This is a stickly flag, which means that it is not resetted by the firmware.

Le entry della PTE di i386, che corrispondono ad entry della PTE di Linux, puntano a frame di grandezza 4KB. Il formato di una entry della tabella PTE è il seguente

Notiamo che tramite due livelli di paginazione possiamo avere permessi a varia granularità.

Notiamo poi che nella versione protected mode di x86, sia nella PDE sia nella PTE non sono presenti nessun tipo di bits per stabilire se la pagine possono essere eseguite o meno. Questo significa che lavorando in protected mode non abbiamo un modo per discriminare da dove il codice può essere fetchato. Questo ha inevitabilmente portato a varie tipologie di attacchi, tutti bassati sull'iniezione di codice in qualche porzione della memoria del processo vittima.

Nel file include/asm-i386/pgtable.h sono presenti alcune macro che definiscono la posizione dei control bits presenti all'interno delle entries di una tabella PDE o PTE. Esistono anche delle macro machine dependent per fare il masking e settare il valore di quei particolari bits di controllo.

#define _PAGE_PRESENT  0x001
#define _PAGE_RW       0x002
#define _PAGE_USER     0x004
#define _PAGE_PWT      0x008
#define _PAGE_PCD      0x010
#define _PAGE_ACCESSED 0x010

#define _PAGE_DIRTY    0x020 /* proper of PTE */ 

Queste macro possono essere utilizzate con gli operatori logici offerti dal C nel seguente modo

pte_t x;

x = ...;

if ( (x.pte_low) & _PAGE_PRESENT) {
    // page is loaded in a frame
 } else {
     // page is not loaded in any frame
}

L'ordine in cui il firmware controlla i bit di controllo è ben specificato. L'esecuzione di un accesso alla page table avviene secondo il seguente schema:

1. Dopo una TLB miss, il firmware accede alla page table;

2. Il primo bit visto è tipicamente il _PAGE_PRESENT bit;

3. Se il bit è zero, viene generato un page fault , che da origine ad una software trap (con un dato displacement all'interno della trap/interrupt table).

4. Una volta che la trap è stata gestita, l'esecuzione può nuovamente cominciare.

5. A seconda dei successivi controlli che il firmware fa sui bit di controllo, ulteriori traps possono essere generate. Ad esempio se stiamo tentando ad accedere ad una read only page viene generata una segmentation fault.

Il seguente pezzo di codice ci dice se la paginazione avvine tramite uno schema a 4MB oppure a 4KB. Il codice è stato girato su una macchina i386, con kernel version 2.4.

#include <kernel.h>

#define PAGE_SIZE_BIT 1 << 7

// Fixing a reference on the kernel boundary. In i386 the kernel is
// situated in the virtual address space betwen the 3GB addr and the
// 4GB one, taking up a total of 1 GB space. 
unsigned long addr = 3 << 30; 

asmlinkage int sys_page_size()
{
  // addr = (unsigned long) sys_page_size;

  // addr >> 22 is used as a displacement in the level 1 page table,
  // i.e. the PGD (linux) or PDE (i386).

  // Q: Why do I need to cast it as a int?

  // By doing the & MASK we are getting only the bit related to the
  // page size. If the bit is 1, then we have only one level of
  // paging, with pages of 4MB, else we have two levels of paging,
  // with pages of 4KB. 
  return (swapper_pg_dir[(int) ((unsigned long) addr >> 22)] & PAGE_SIZE_BIT ? 4: << 20 : 4 << 10);
}

La kernel page table è inizializzata a compile time. In particolare mappa due pagine, ciascuna da 4MB, a partire dai 3GB. La prima pagina è caricata nella entry 768 della PGD.

L'algoritmo che inizializza la kernel page table è un algoritmo iterativo che esegue ciclicamente i seguenti passi:

1. Si determina l'indirizzo virtuale da mappare, salvato nella variabile addr;

2. Una pagina da 4KB viene allocata. Questa pagina conterrà una page table di secondo livello (PTE table).

3. Iterativamente andiamo a riempire la page table allocata andando ad inserire il relativo mapping degli indirizzi virtuali a quelli fisici.

4. L'indirizzo virtuale viene incrementato di 4MB .

5. Saltiamo al passo (1) per ripetere il processo finché non abbiamo più indirizzi virtuali da allocare, o finché non termina la memoria fisica.

Il codice vero e proprio è preso dalla funzione pagetable_init() , ed è il seguente

       for( ; i < PTRS_PER_PGD; pgd++, i++) {

         // Initially i is set to 3GB, i.e. i = 3 << 30
         // PGDIR_SIZE is set to 4MB.
         vaddr = i * PGDIR_SIZE:

         // end the setup when we finished our virtual memory
         if(end && (vaddr >= end)) break;

         // pgd initialized to (swapper_pg_dir + i)
         pmd = (pmd_t *) pgd;

         //...

         // NOTE: This loop is entered only ONCE per iteration,
         // because PTRS_PER_PMD = 1. This is done to be compatible
         // with tree levels of paging, even though x86 only uses two.
         for (j = 0; j < PTRS_PER_PMD; pmd++, j++) {

           // ...

           // Allocate a new 4KB page in the memory. 
           pte_base = pte = (pte_t *)alloc_bootmem_low_pages(PAGE_SIZE);

           // In this loop we iterate over the newly allocated page table,
           // and for each entry we map the virtual address with the
           // corresponding physical address.
           for(k = 0; k < PTRS_PER_PTE; pte++, k++) {

             // Compute virtual address by taking into considerations the
             // various level of paging.
             //
             // NOTE: in i386 j = 0 always, so we don't take that into
             // account. 
             vaddr = i * PGDIR_SIZE + j * PMD_SIZE + k * PAGE_SIZE;

             if(end && (vaddr >= end)) break;

             // ...

             // The mk_pte_phys(physpage, pgrpot) is used to build a complete
             // PTE entry and it retuns a pointer of type pte_t. Its input
             // parameters are:
             //
             // 1) A frame physical address of type unsigned long, that
             // represents the base address of the frame
             //
             // 2) a bit string pgprot for a PTE, of type pgprot_t, which
             // represents the metadata of that frame.
             //
             // The resuling value can be assigned to one PTE entry.
             // 
             *pte = mk_pte_phys(__pa(vaddr), PAGE_KERNEL);
           }

           // The set_pmd macro simply sets the value into one PMD
           // entry. It's input parameters are:
           //
           // 1) The pmd pointer to an entry of PMD
           //
           // 2) The value to be loaded pmdval
           //
           // This macro is used in combination with __pa() which returns an
           // unsigned long corresponding to the physical to a given directly mapped virtual
           // address within kernel space. 
           set_pmd(pmd, __pmd(_KERNPG_TABLE + __pa(pte_base)));
         }
        }

Notiamo che il buffer finale della PDE alla fine coincide con la page table iniziale che mappa pagine di 4MB. Notiamo che dobbiamo modificare le varie entry della PDE solamente quando abbiamo già popolato la corrispettiva PTE. Questo viene fatto in quanto, altrimenti, se modificato la PDE durante il filling della PTE, nel caso di TLB miss potremmo perdere il memory mapping per la traduzione dell'indirizzo virtuale.