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 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
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):
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.
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.
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