L'allocazione di memoria

di Alessandro Rubini

Riprodotto con il permesso di Linux Magazine, Edizioni Master.

Anche il kernel, come lo spazio utente, deve implementare un meccanismo di allocazione della memoria, ad uso dei driver e dei vari sottosistemi del nucleo stesso.

I meccanismi offerti dal kernel sono strutturalmente diversi da quelli usati in spazio utente, in quanto devono operare con la memoria fisica e le problematiche di frammentazione esterna ed interna ad essa associate.

Questo articolo offre una panoramica introduttiva dei meccanismi di allocazione di memoria in spazio kernel, utilizzando codice di esempio scritto e verificato con la versione 2.6.10-rc2.

Le funzioni kmalloc e kfree

Le funzioni in spazio kernel che corrispondono alle classiche malloc e free si chiamano kmalloc e kfree. A differenza della versione utente, che riceve un solo argomento, kmalloc ne riceve due: la dimensione dell'area da allocare e la cosiddetta priorità usata per la allocazione. Tale argomento viene usato per indicare il tipo di memoria di cui si fa richiesta insieme al comportamento da seguire quando la memoria richiesta non sia immediatamente disponibile.

La scelta del tipo di memoria fa riferimento alla divisione della memoria in tre zone: memoria di DMA, memoria normale, memoria alta. Le tre zone sono descritte nel riquadro 1, mentre il secondo argomento di kmalloc è descritto nel riquadro 2.

Riquadro 1 - le tre zone di memoria

Il kernel divide la memoria RAM in tre zone: la memoria "utilizzabile per il DMA", la memoria "normale", la memoria "alta". Il significato della prima e della terza zona dipende dalla piattaforma, e molte di esse hanno solo memoria "normale". Nel caso del PC, la zona "DMA" comprende la memoria sotto i 16MB (utilizzabile dal DMA del bus ISA, mentre il bus PCI può fare trasferimenti diretti da e verso tutta la memoria RAM) e la zona "alta" esiste solo se definita nella configurazione del kernel; si tratta di una modalità di accesso solo utile se si ha più di 1GB di memoria RAM.

Questa la divisione della memoria come riportata da un 2.4.28, su una macchina con 512MB di memoria e il parametro mem=500m in linea di comando:

   500MB LOWMEM available.
   On node 0 totalpages: 128000
   zone(0): 4096 pages.
   zone(1): 123904 pages.
   zone(2): 0 pages.

Con la versione 2.6 è stato esplicitato il significato delle zone nel messaggio stampato all'avvio, ma è stato aggiunto un oscuro numero di batch associata a ciascuna zona:

   500MB LOWMEM available.
   On node 0 totalpages: 128000
     DMA zone: 4096 pages, LIFO batch:1
     Normal zone: 123904 pages, LIFO batch:16
     HighMem zone: 0 pages, LIFO batch:1

Riquadro 2 - Le priorità di kmalloc

Il secondo argomento di kmalloc, la cosiddetta priorità, è una maschera di bit, definiti in <linux/gfp.h> (get free page), che indicano come il kernel deve comportarsi nella ricerca di pagine di memoria, qualora l'allocazione non possa essere conclusa direttamente. Le due priorità normalmente usate dai driver sono GFP_KERNEL, per la normale allocazione da parte del kernel, e GFP_ATOMIC, per una allocazione che non può causare la sospensione dell'esecuzione.

La priorità GFP_ATOMIC viene normalmente usata per le allocazioni chiamate da un gestore di interruzioni o, più in generale, da codice che esegue in maniera asincrona rispetto ai processi; tale allocazione può accedere a pagine di memoria riservate specificamente per questo uso, ma potrebbe fallire se tali richieste di memoria sono più frequenti di quanto il sistema riesca a liberare memoria dalle sue varie strutture dati (processi, pagecache, ...).

Quando la memoria viene richiesta nel contesto di un processo, durante l'esecuzione di chiamate di sistema come read, write, ioctl, l'allocazione viene richiesta con GFP_KERNEL, e il sistema può sospendere il processo chiamante al fine di recuperare le pagine di memoria necessarie a soddisfare la richiesta (per esempio spostando in spazio di swap pagine dati di altri processi). Una allocazione con priorità GFP_KERNEL può fallire solo quando il sistema è sovraccarico (come utilizzo di memoria) o vengono richieste troppe pagine consecutive, normalmente non disponibili a causa della frammentazione esterna.

Quando questo succede, il kernel stampa un messaggio di "page allocation failure" seguito dallo stack di sistema a fini diagnostici; tale stampa è protetta da printk_ratelimit (di cui abbiamo parlato in uno dei precedenti articoli) per evitare di sovraccaricare ulteriormente il sistema. Se la funzione chiamante considera innocuo un possibile errore di allocazione, può speficicare __GFP_NOWARN tra i bit di priorità per evitare la stampa di errore e stack.

I bit __GFP_DMA e __GFP_HIGHMEM possono essere specificati per richiedere l'allocazione da una specifica zona di memoria, ma richieste di memoria meno "pregiata" potranno essere evase con memoria più pregiata.

Un modulo, per usare le funzioni kmalloc e kfree deve includere il file di intestazione <linux/slab.h>. Il file usato tempo fa, chiamato <linux/malloc.h>, non è più disponibile già da Linux-2.4, in quanto si è preferito esporre il nome dello specifico algoritmo di allocazione utilizzato internamente.

A differenza di quanto accade in spazio utente, dove la memoria è un vettore di byte contigui in cui l'allocazione avviene senza interruzioni, il kernel rende disponibile la memoria in aree di dimensione predefinita, corrispondenti a potenze di due all'interno di un certo intervallo (per esempio, su x86 si parte da 32 byte e si arriva a 128kB). Ogni allocazione di 1 byte perciò usa in realtà 32 byte, mentre ogni allocazione di 33 byte ne richiede 64. La massima dimensione allocabile è pari a 32 pagine su tutte le piattaforme (da cui i 128kB su piattaforma x86 che diventano 256kB su macchine Alpha). In effetti, su alcune piattaforme è possibile specificare CONFIG_LARGE_ALLOCS nella configurazione del kernel, per poter allocare aree di dimensione fino a 32MB; questa opzione non è disponibile su x86, anche se è possibile (e sconsigliato) abilitarla manualmente in mm/slab.c.

Una semplice verifica sul comportamento di kmalloc si può effettuare con il modulo kmalloc-test, mostrato in figura 1 e scaricabile da http://www.linux.it/kerneldocs/slab/src.tar.gz. Tale modulo misura l'utilizzo di memoria, in pagine, corrispondente all'allocazione di mille aree di dimensione 1, 2, 5, 10, 20, 50 byte (eccetera, fino a 500mila byte), registrando anche il tempo richiesto per effettuare le mille allocazioni. Le misure fatte vengono stampate nei messaggi di sistema e il modulo ritorna errore per venire rimosso dal sistema; è così possibile ricaricare subito il modulo per ottenere un altra sequenza di misure.

Figura 1 - kmalloc-test.c

#include <linux/config.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/init.h>
#include <linux/timex.h>
#include <linux/types.h>
#include <asm/msr.h>

MODULE_LICENSE("GPL");

#define NALLOC 1000
static void *pointers[NALLOC];

static void testalloc(int size)
{
	int free0, free1, i;
	struct sysinfo info;
	u32 tsc0, tsc1;

	si_meminfo(&info);
	free0 = info.freeram;
	rdtscl(tsc0);
	for (i=0; i<NALLOC; i++)
		pointers[i] = kmalloc(size, GFP_KERNEL);
	rdtscl(tsc1);
	si_meminfo(&info);
	free1 = info.freeram;
	for (i=0; i<NALLOC; i++)
		kfree(pointers[i]);
	printk("size %6i: free was %6i, now %6i (delta %6i)"
	       " time %4lius\n", size, free0, free1,
	       free1-free0, (tsc1-tsc0)/(cpu_khz/1000));
}

int kmt_init(void)
{
	int sizes[]={1,2,5,0};
	struct sysinfo info;
	int i, j;
	
	si_meminfo(&info);
	printk("free %li (unit %i)\n",
	       info.freeram, info.mem_unit);
	for(i = 1; i <= 100*1000; i*=10)
		for (j=0; sizes[j]; j++)
			testalloc(i*sizes[j]);
	return -ENODEV;
}

void kmt_exit(void) {} /* unused */

module_init(kmt_init);
module_exit(kmt_exit);

Il riquadro 3 mostra l'output ottenuto in una macchina x86 con 500MB di memoria RAM appena avviata e in assenza di carico. I valori riportati, come succede di frequente, non corrispondono a quanto ci si potrevve aspettare, ma sono comunque un risultato interessante da analizzare.

Le allocazioni di piccola dimensione apparentemente non utilizzano memoria; questo succede perché il kernel riserva prealloca alcune pagine associate ad ogni dimensione di memoria, per migliorare le prestazioni all'avvio del sistema. Infatti, nel caso riportato, mille di tali operazioni richiedono solo 40 microsecondi. Tale memoria preallocata può comunque essere liberata qualora l'attività del sistema richiedesse più RAM di quella rimasta disponibile.

Sempre dall'output del modulo, si evince che ogni allocazione di 5000 byte riserva due pagine (duemila in totale), cioè 8192 byte, e così via (sempre per potenze di due), fino a 128kB. Le allocazioni più grandi, infine, appaiono non utilizzare memoria semplicemente perché falliscono e il modulo di esempio non effettua alcun controllo di errore; kfree, dal cnato suo, ignora senza lamentarsi ogni richiesta di liberare puntatori nulli. È interessante notare come una allocazione fallita richieda circa lo stesso tempo di un'allocazione riuscita quando questa non richieda nuova memoria al sistema.

Prioma di probare il modulo kmalloc-test sulle proprie macchine, si noti che come distribuito il codi alloca mille aree per ogni dimensione, quindi richiede che ci siano almeno 128MB di memoria RAM disponibile per l'allocazione (cioè una macchina da 160MB o più), o l'impossibilità di soddisfare le richieste di memoria porterà ad una spiacevole caduta del sistema.

Riquadro 3 - Output di kmalloc-test

free 121755 (unit 4096)
size      1: free was 121755, now 121755 (delta      0) time   46us
size      2: free was 121755, now 121755 (delta      0) time   40us
size      5: free was 121755, now 121755 (delta      0) time   39us
size     10: free was 121755, now 121755 (delta      0) time   39us
size     20: free was 121755, now 121755 (delta      0) time   39us
size     50: free was 121755, now 121755 (delta      0) time   49us
size    100: free was 121755, now 121739 (delta    -16) time   60us
size    200: free was 121739, now 121707 (delta    -32) time   77us
size    500: free was 121707, now 121627 (delta    -80) time   98us
size   1000: free was 121691, now 121483 (delta   -208) time  157us
size   2000: free was 121675, now 121227 (delta   -448) time  264us
size   5000: free was 121659, now 119659 (delta  -2000) time  557us
size  10000: free was 121625, now 117625 (delta  -4000) time  552us
size  20000: free was 121557, now 113557 (delta  -8000) time  628us
size  50000: free was 121421, now 105421 (delta -16000) time  825us
size 100000: free was 121149, now  89149 (delta -32000) time 1466us
size 200000: free was 120605, now 120605 (delta      0) time   44us
lsize 500000: free was 120605, now 120605 (delta      0) time   43us

L'allocatore slab

Il meccanismo di allocazione di memoria usato nel kernel a partire dalla versione 2.2 è un'implementazione dell'algoritmo slab (piastra), presentato da Jeff Bonwick nel 1994. Questo algoritmo, dotato di una sua interfaccia indipendente che incontreremo più avanti, è quello usato internamente da kmalloc.

L'idea di base dell'algoritmo slab consiste nel dividere aree di memoria di dimensione considerevole (le piastre, appunto) in tanti blocchetti tutti della stessa dimensione, così che la gestione dei blocchetti risulti estremamente leggera (lo stato di ogni blocchetto può essere rappresentato in pochi bit e ogni piastra richiede una struttura di controllo di pochi byte). In questo modo, una piastra può essere deallocata solo se tutti i blocchetti in essa contenuti sono stati liberati; questo sovraccarico è normalmente accettabile in quanto l'allocazione e la liberazione di strutture dati avviene continuamente durante la vita del sistema. Inoltre, in situazioni di ristrettezza di memoria, il sistema necessita di intere pagine di memoria; la frammentazione interna ad una pagina, comunque inevitabile, rimane più gestibile con un frazionamento omogeneo della pagina.

Ma il vantaggio principale dell'allocatore slab rispetto alle alternative usate in precedenza sta proprio nella sua genericità. Mentre kmalloc internamente usa blocchetti da 32, 64 e 128 byte, spesso occorre manipolare grandi quantità di strutture dati di dimensione diversa (e arbitraria), come 48, 60 o 308 byte. L'allocatore permette ad ognuna di queste strutture dati di essere ospitate in una propria serie di piastre, limitando notevolmente lo spreco di memoria dovuto a frammentazione interna. Per esempio, su piattaforma PC, una pagina (4kB) può contenere 13 inode da 308 byte ciascuno, con uno spreco di 92 byte. L'uso di kmalloc in questo caso avrebbe permesso di allocare solo 8 inode in ogni pagina, sprecando 1636 byte (il 40% del totale). Una memoria cache che sia associata ad una struttura dati (un oggetto) è in ogni istante formata da zero o più piastre.

In questo allocatore, poi, ogni piastra è composta da una o più pagine consecutive di memoria, queste ultime sempre in potenza di due (2, 4, 8, 16, 32 pagine). Questa scelta permette di manipolare in maniera abbastanza semplice l'insieme di tutte le pagine di memoria del sistema, procedendo a bisezione o accorpamento in base alle necessità. In ogni caso, l'allocazione di un'area composta da più pagine risulta molto costosa per il sistema, a causa della granularità di pagina indotta dall'hardware; per questo motivo l'allocatore slab preferisce allocare piastre da una o massimo due pagine, anche quando questo porti a maggiori sprechi di memoria.

/proc/slabinfo

Una fotografia dello stato di uso della memoria dal punto di vista dell'allocatore è visibile in ogni momento nel file /proc/slabinfo che, come la maggior parte dei file informativi in /proc, è strutturato per righe.

Riquadro 4 - /proc/slabinfo

burla% grep test /proc/slabinfo
test-100000         1000   1000 100000    1   32 :   1000   1000      0
test-50000          1000   1000  50000    1   16 :   1000   1000      0
test-20000          1000   1000  20000    1    8 :   1000   1000      0
test-10000          1000   1000  10000    1    4 :   1000   1000      0
test-5000           1000   1000   5000    1    2 :   1000   1000      0
test-2000           1000   1000   2000    2    1 :    500    500      0
test-1000           1000   1000   1000    4    1 :    250    250      0
test-500            1000   1000    500    8    1 :    125    125      0
test-200            1000   1000    200   20    1 :     50     50      0
test-100            1000   1014    100   39    1 :     26     26      0
test-50             1000   1050     52   75    1 :     14     14      0
test-20             1000   1110     20  185    1 :      6      6      0
test-10             1000   1160     12  290    1 :      4      4      0
test-5              1000   1221      8  407    1 :      3      3      0

Ogni riga, dopo l'intestazione, contiene informazioni relative ad una specifica memoria cache. Le colonne più interessanti sono le prime cinque e le ultime tre; assumento che non si sia attivata l'opzione CONFIG_DEBUG_SLAB, che prevete l'aggiunta di ulteriori campi a /proc/slabinfo.

Le prime colonne numeriche descrivono l'utilizzo della cache a livello di oggetti (blocchetti di memoria):

Le ultime tre colonne rappresentano invece l'utilizzo a livello di piastre:
  • Numero totale di piastre
  • Numero di piastre liberabili Nel file appaiono tutte le memorie cache attive nel sistema. Queste comprendono sia le aree di memoria di kmalloc (divise in aree di memoria normale e aree di memoria DMA), sia una cache per ogni struttura dati usate frequentemente nel kernel, la cui presenza permette di velocizzare i tempi di creazione e distruzione senza sprecare spazio inutile in frammentazione interna.

    Un esempio di ottimizzazione della frammentazione interna della memoria si può vedere ordinando il file numericamente sulla quarta colonna ("sort -n +4 /proc/slabinfo"); per osservare le memorie cache elencate in ordine di dimensione dell'elemento:

        size-1024             40     40   1024    4    1 
        tcp_sock              16     21   1056    7    2
        task_struct           27     27   1296    3    1
    

    Nelle righe precedenti (di cui ho riportato solo le prime colonne) si nota come l'allocatore abbia disposto 4 aree da 1024 byte in una pagina (nessuno spreco) e tre aree da 1296 in una pagina (5% di spreco) ma accorpando due pagine ad ospitare 7 aree da 1056 byte (con uno spreco del 10%) piuttosto che usare pagine singole che contengono tre aree, con uno spreco del 22% di memoria.

    Creazione di una cache personale

    Quando ci si trova a scrivere codice in spazio kernel che tratti molte strutture dati dello stesso tipo, può essere conveniente creare una propria memoria cache di tipo slab, per poi distruggerla nella fase di rimozione del proprio modulo. L'uso di una cache personale, rispetto al più classico kmalloc è conveniente sia per migliorare l'efficienza d'uso della memoria, sia per aiutare ad identificare eventuali perdite di memoria dovute ad errori di programmazione: la funzione di distruzione della cache, infatti, segnala in maniera molto chiara la presenza al proprio interno di memoria non ancora liberata. Le seguenti funzioni vengono usate per creare e distruggere la cache:

      kmem_cache_t *kmem_cache_create(char *name, size_t size,
                                      size_t align, unsigned long flags,
                                           void (*contructor)(),
                                           void (*destructor)());
      int kmem_cache_destroy(kmem_cache_t *cache);
    

    Una volta creata la memoria cache, è possibile allocarvi e liberarvi oggetti tramite le due funzioni:

       void *kmem_cache_alloc(kmem_cache_t *cache, int prio);
       void kmem_cache_free(kmem_cache_t *cache, void *ptr);
    

    Un esempio pratico dell'uso di una cache personale, è il modulo cache-test.c, che non entra nel dettaglio dei vari argomenti passati a kmem_cache_create, usando semplicemente i valori di default. Tale modulo registra a utilizza alcune memorie cache, in modo simile a kmalloc-test; a differenza di quest'ultimo, però, cache-text non ritora un messaggio di errore e dilaziona la rimozione delle sue strutture dati alla procedura di uscita del modulo. Se si carica il modulo con i parametri predefiniti (1000 allocazioni per ogni dimensione, che richiedono circa 250MB di memoria), si potranno vedere in /proc/slabinfo righe simili a quelle riportate nel riquadro 4.

    Si può notare in queste righe come la dimensione del singolo blocchetto venga estesa fino ad essere un multiplo della lunghezza di parola della macchina ospite (4 byte per il PC). Questo comportamento, senza effetti collaterali, assicura di evitare problemi di allinemanento o sovrascrittura di un oggetto nelle macchine di tipo RISC, nelle quali l'accesso non allineato in memoria non è permesso.

    Riquadro 5 - Approfondimenti

    L'articolo originale di Bonwich sull'allocatore slab è disponibile presso http://www.usenix.org/publications/library/proceedings/bos94/bonwick.html .

    I sorgenti dell'implementazione di Linux-2.6 si trovano in mm/slab.c e (per la gestione pagine) in mm/page_alloc.c. Documentazione più approfondita si trova su "Linux Device Drivers", scaricabile dal sito di GNUtemberg o da http://lwn.net/Kernel/LDD2/, come su molti altri documenti in rete, più o meno aggiornati, facilmente recuperabili usando "slab allocator" come parole chiave per un motore di ricerca.

    Figura 2 - cache-test.c

    
    /* ... */
    
    static struct ctest {
    	kmem_cache_t *c;
    	char name[16];
    	void *pointers[NALLOC];
    } testdata[20];
    
    static void testalloc(int size)
    {
    	static struct ctest *t = testdata;
    	kmem_cache_t *c;
    	int free0, free1, i;
    	struct sysinfo info;
    	u32 tsc0, tsc1;
    
    	if (size < BYTES_PER_WORD) return;
    	if (size > (1<<5)*PAGE_SIZE) return;
    	sprintf(t->name, "test-%i", size);
    	c = kmem_cache_create(t->name, size, 0,
    			      0, NULL, NULL);
    
    	for (i=0; i