AOS - 17 - KERNEL MEMORY-MANAGEMENT IV

• Data: [2019-10-30 mer]

• Sito corso: link

• Slides: AOS - 3 KERNEL LEVEL MEMORY MANAGEMENT

• Progresso unità: 4/5

• Argomenti:

  • Homework #3

  • Core map

  • Memory Organization in UMA

  • Free lists

  • Buddy Allocator

  • Memory Management in NUMA

  • Mem-Policy

TODO.

Per riuscire ad allocare e deallocare memoria in modo flessibile, dopo aver inizializzato e modificato la kernel page table, dobbiamo fare il setup di altre due strutture dati, che sono la core-map e le free lists.

La core-map è una struttura dati che mantiene informazioni sullo stato della memoria fisica del sistema. In particolare è un array di struct page , o mem_map_t . A ciascun frame sono, in particolare, associate tre informazioni:

• struct list_head list , collega la entry ad altre entry dell'array per formare delle free lists.

• atomic_t count , che contiene un contatore atomico per sapere quante pagine logiche sono state mappate in quel frame;

• unsigned long flags , che contiene varie informazioni sul frame. I possibili valori per il campo flags sono i seguenti,

  La funzione free_area_init() viene utilizzata per inizializzare la core-map. Inizialmente tutti i frame hanno il bit PG_reserved . Per togliere questo bit, e quindi per poter utilizzare i frame, si esegue la funzione mem_init() .

In una architettura UMA , o NUMA unaware, o single NUMA zone, la memoria fisica è suddivisa in tre zone, che sono definite in include/linux/mmzone.h e sono

• ZONA_DMA (codice 0): Utilizzata per i dispositivi DMA, che storicamente non potevano indirizzare zone arbitrarie di memoria.

• ZONE_NORMAL (codice 1): Zona mappa direttamente con le pagine del kernel.

• ZONE_HIGHMEM (codice 2): Zona utilizzata per page cache e per le pagine dello user. In questa zona non si garantisce il direct mapping.

Ogni zona di memoria ha la sua free list.

Una free list è una struttura dati che ci permette di astrarre rispetto alla visione della memoria offerta della core-map. In particolare tramite le free lists siamo in grado di costruirci particolari visioni della memoria. Le informazioni sulle free list sono mantenute all'interno della struttura dati pg_data_t , definita nel file include/linux/mmzone.h .

typedef struct pglist_data
{
  // Array di zone_t. In particolare per ogni zona della memoria
  // abbiamo una struttura zone_t, che ci permette di vedere quella
  // zona di memoria in modi diversi. 
  zone_t node_zones[MAX_NR_ZONES];

  // ...
  
  // Pointer alla core-map che utilizziamo per fornire le visioni
  // della memoria ad un più alto livello. 
  struct page *node_mem_map;

  // ...
  
  // Size della core-map che stiamo gestendo. 
  unsigned long node_size;

} pg_data_t;

La struttura invece zone_t è definita sempre nel file include/linux/mmzone.h come segue

typedef struct zone_struct
{
  spinlock_t lock;

  // Questo array ci permette di vedere in MAX_ORDER modi diversi lo
  // stato della memoria. Ciascun modo diverso rappresenta una
  // particolare free list. Questo meccanismo forma il cosiddetto
  // buddy allocator system. 
  free_area_t free_area[MAX_ORDER];

  struct page *zone_mem_map;

} zone_t;

Notiamo che il lock serve per rendere le operazioni sulla memoria safe rispetto alla concorrenza. Presente anche nelle ultime versioni.

Osservazione: Lo studio di algoritmi non bloccanti per fare questo tipo di operazioni è un campo di ricerca importante.

Nelle architetture NUMA-aware per differenziare i vari nodi NUMA utilizziamo la struttura struct pglist_data . Questa struttura non è altro che una lista, o un array, di pg_data_t , e viene utilizzata anche in caso di macchina UMA. Ciascuna struttura pg_data_t gestisce la visione di un particolare nodo NUMA.

Ogni nodo NUMA può avere il suo buddy allocator, e a seconda di quale API utilizziamo, possiamo specificare su quale nodo NUMA vogliamo eseguire le nostre operazioni.

La funzione free_all_bootmem_core(pg_data_t *pgdat) viene utilizzata per rilasciare le pagine di memoria che erano state marcate come boot memory only. Tale funziona utilizza inernamente la funzione __free_page(page) , che è la prima API del buddy allocator utilizzata dal kernel.

Le allocazioni di memoria possono avvenire per due ragioni principali, che sono

• Process context: In questo caso l'allocazione della memoria è legata alle attività di uno specifico processo. Questo tipo di allocazione permette quindi di portare il thread che richiede la memoria in stato di wait, per aspettare che l'allocazione può essere eseguita.

• Interrupt: In questo caso l'allocazione della memoria è richiesta da un interrupt handler, e dunque non posso far aspettare l'handler. Devo quindi gestire l'allocazione in modo immediato, andando eventualmente a ritornare un fallimento, se non ho memoria disponibile.

Dopo il processo di start-up, la memoria può essere gestita tramite delle particolari API, che gestiscono le strutture dati menzionate precedentemente. I prototipi per queste API sono presenti in <linux/malloc.h> .

L'API di base è formata dalle seguenti funzioni,

• get_zeroed_page(): Rimuove un frame dalla free list, azzera il frame scelto, e ritorna il suo indirizzo virtuale.

  unsigned long get_zeroed_page(int flags);
  

• __get_free_page(): Rimuove un frame dalla free list e ritorna il suo indirizzo virtuale.

  unsigned long __get_free_page(int flags);
  

• __get_free_pages(): Rimuove un blocco continuo di frame a seconda dell'order dato dalla free list e ritorna l'indirizzo virtuale del primo frame.

  unsigned long __get_free_pages(int flags, unsigned long order);
  

• free_page(): Inserisce il frame associato a quell'indirizzo virtuale all'interno della free list.

  void free_page(unsigned long addr);
  

• free_pages(): Inserisce un blocco di frames di un certo ordine all'interno della free list. Se sbagliando l'ordine, tra l'allocazione e la deallocazione, possiamo corrompere varie configurazioni del kernel, ed avere gravi errori nel sistema.

  void free_pages(unsigned long addr, unsigned long order);
  

Le flags utilizzate sono le seguenti:

• GFP_ATOMIC, la chiamata non può portare a situazioni bloccanti tipo sleep(). Questa flag viene utilizzata per allocazioni in contesti generati da interrupt.

• GFP_USER, GFP_BUFFER, GFP_KERNEL, in questi casi invece la chiamata può portare a situazioni bloccanti.

Tutte le API del buddy-system ritornano indirizzi virtuali di pagine mappate in modo diretto. Conoscendo gli indirizzi virtuali possiamo quindi scoprire direttamente la posizione in memoria fisica dei relativi frames.

Dato poi che tutte le strutture dati core del sistema operativo vengono allocate dal buddy-system, ne segue che sono tutte allocate in modo diretto.

Dato che in una architettura NUMA abbiamo più buddy allocators, uno per ogni nodo NUMA, come facciamo a stabilire quale buddy-allocator utilizzare quando chiamiamo una API tipo free_pages() ? Questo problema viene risolto attraverso il concetto di mem_policy.

Ogni thread in esecuzione ha delle meta-informazioni associate. Tra queste meta-informazioni troviamo anche la mem_policy, che specifica il nodo NUMA in cui le operazioni di memoria devono essere effettuate. Le API più esterne quindi utilizzano la mem policy per chiamare delle API più interne. In particolare per allocare delle pagine, l'API più interna è la

struct page *alloc_page_nodes(int nid, unsigned int flags, unsigned int order);

Notiamo che questa API prende un parametro extra, il parametro nid, che specifica il nodo NUMA all'interno della fare eseguire l'allocazione e quindi specifica il buddy-allocator da utilizzare.

Il valore della mem policy di default è la FIRST-TOUCH, che consiste nell'utilizzare il nodo NUMA associato alla CPU dove il thread sta girando.