AOS - 18 - KERNEL MEMORY-MANAGEMENT V

• Data: [2019-11-04 lun]

• Sito corso: link

• Slides: AOS - 3 KERNEL LEVEL MEMORY MANAGEMENT

• Progresso unità: 5/5

• Argomenti:

  • Quicklists

  • SLAB allocators

  • Kernel page remapping and TLB

• Introduzione: Nella scorsa lezione avevamo introdotto il buddy system per l'allocazione e la deallocazione di pagine di memoria fisica (frames) tramite uno schema di direct-mapping. Il buddy system però, per garantire la sincronizzazione della visione della memoria tra CPU-core diversi, utilizza dei meccanismi di spinlock. Questo rende l'allocaziona e la deallocazione molto dispendiosa, specialmente per zone di memoria che vengono richieste e rilasciate molto frequentemente.

Il buddy system non scala rispetto al numero di CPU-core che possiamo ospitare su un dato NUMA node. Per migliorare questo problema sono stati introdotti degli allocatori di più alto livello. Inizialmente questi allocatori venivano utilizzati solamente per specifiche strutture dati, come ad esempio le page tables. Attualmente sono disponibili delle API per allocare e deallocare della memoria in modo veloce e flessibile.

Queste API funzionano utilizzando le API dei buddy allocators per fare del "pre-reserving" della memoria. In particolare si ottengono delle pagine logiche dal buddy allocators e queste pagine vengono gestite non più al livello del buddy allocators ma ad un più alto livello. Queste free list prendono il nome di quicklists.

Per le allocazioni delle page tables sono presenti delle API che utilizzano questo concetto di quicklists, che sono

  pgd_alloc(), pgd_free()
  pmd_alloc(), pmd_free()
  pte_alloc(), pte_free()

In linux la struttura della quicklist è definita nel file include/linux/quicklist.h . Se la quicklist è piena, il buddy system viene utilizzato per aggiornare lo stato della quicklist.

The following macros can be used to translate between logical and physical addresses for directly mapped memory pages.

// in include/asm-i386/io.h
virt_to_phys(unsigned int addr);
phys_to_virt(unsigned int addr);

// in generic kernel versions
__pa(virtual_addr);
__va(physical_addr); 

Questo running example ci permette di analizzare la differenza in performance tra l'utilizzo di quicklists e l'utilizzo del buddy system. Il kernel utilizzato è 3.x , in quanto nei nuovi kernel è difficile misurare la differenza in performance.

// Used to allocate memory. If LOCAL is defined, then we use the
// quicklists, otherwise we use the buddy system.
asmlinkage void* get_buffer(void){
  void* the_addr = NULL;
#ifdef LOCAL
  int *x;
  int cpu_id;

  // NOTE: This is used to understand if the CPU-core that has
  // started the module entered already once this function. Note
  // that since we are using a static variable, we are not able
  // to run this program un multiple cores, because after one
  // core has entered the function, all other cores will see
  // set=1, even though they have not yet initialized the
  // variable me with the proper value.
  static int set = 0;

  if(set == 0){
    x = this_cpu_ptr(&me);
    *x = smp_processor_id();
    set = 1;
  }
  cpu_id = this_cpu_read(me);
  the_addr = lists[cpu_id];
  lists[cpu_id] = *((void**)the_addr);

#else
  // Use the buddy system. 
  the_addr = __get_free_pages(GFP_KERNEL,0);
#endif
  DEBUG
    printk("%s: get_buffer called - allocation returned address %p\n",MODNAME,the_addr);
  if(the_addr == NULL){
    return NULL;
  }     

  return the_addr;
}

Il kernel linux offre infine degli allocatori a grana più piccola di una pagina. In particolare le APIs principali sono definite in <linux/malloc.h> , e sono riportate a seguire. Notiamo che tutti i buffer ottenuti da questo sottosistema sono cache alligned. Idealmente dovrebbero essere utilizzati per allocare taglie di memoria piccola.

• kmalloc(): Equivalente ad una malloc() a livello applicativo.

  void *kmalloc(size_t size, gfp_t flags);
  

• kfree(): Equivalente ad una free() a livello applicativo.

  void *kfree(void *obj);
  

• kzalloc(): Ci assicura che la memoria viene azzerata.

  void *kzalloc(size_t size, gfp_t flags);
  

• kmalloc_node(): Le funzione viste prima sono NUMA-unaware, e si affidano, tramite l'utilizzo delle mem-policy, a delle API di livello più basso, tra cui troviamo la seguente.

  void *kmalloc_node(size_t size, int flags, int node);
  

Se vogliamo allocare memoria di un size più grande, possiamo invece utilizzare le seguenti APIs.

• vmalloc(): Alloca della memoria di un dato size. La memoria allocata non necessariamente è continua. La funzione ritorna l'indirizzo virtuale della pagina.

  void *vmalloc(unsigned long size);
  

• vfree(): Libera zone di memoria allocate con una vmalloc()

  void vreee(void *addr);
  

Notiamo che l'utilizzo della vmalloc può cambiare la kernel page table, e quindi cambia lo stato della TLB. In generale le pagine mappate tramite vmalloc non sono necessariamente direct-mapped.

La tabella seguente riporta le differenze principali tra una vmalloc() e una kmalloc()

Notiamo che la kernel page table ha una natura "globale", nel senso che ogni core può utilizzare la stessa kernel page table. Quando eseguiamo servizi come vmalloc() e vfree() , che possono potenzialmente modificare il contenuto della kernel page table, ci dobbiamo quindi porre la seguente domanda:

Quando un CPU-core modifica il contenuto di una page table, il firmware è in grado di capire che la modifica sta avendo luogo in modo da modificare il contenuto della TLB? Detto altrimenti, qual è il livello di automazione nella gestione dello stato della TLB?

Nelle architetture moderne l'automazione di riallineamento della TLB rispetto lo stato della page table è solo parziale. Per esempio in x86 il firmware cambia automaticamente lo stato della TLB solamente quando il registro CR3 viene modificato. Questa modifica però viene fatta solamente nel CPU-core che ha modificato il registro CR3. Se al posto di cambiare page table ne vogliamo solamente modificare il contenuto, aggiornando comunque la TLB, possiamo

1. Modificare la page table.

2. Riscrivere in CR3 lo stesso valore di prima.

Questo aggiornamento però verrà eseguito solamente su un solo CPU-core.

In generale quindi se l'architetture non supporta questo tipo di automazione sta software del kernel il compito di gestire l'allineamento dello stato del TLB rispetto allo stato della page table.