File system: inode, cartelle, journaling e SSD

Il file system trasforma un disco, che è solo una lunga fila di blocchi numerati, in una gerarchia di cartelle e file con nomi, permessi e date. Deve farlo in modo efficiente per file minuscoli e enormi, e restare coerente anche se la corrente manca a metà di un’operazione. In questa lezione vediamo i metodi di allocazione dei blocchi, l’inode di Unix con il calcolo della dimensione massima di un file, le cartelle e i collegamenti, i permessi, il journaling con il ragionamento che ne garantisce la coerenza, e le particolarità delle memorie a stato solido.

L’allocazione dei blocchi

Il disco è diviso in blocchi, tipicamente di 4 KiB. Un file occupa un certo numero di blocchi, e il file system deve ricordare quali:

• allocazione contigua: i blocchi sono consecutivi; basta ricordare il primo e il numero. Lettura velocissima e accesso diretto facile, ma il disco si frammenta e un file non può crescere se il blocco successivo è occupato;
• allocazione concatenata: ogni blocco contiene il numero del successivo. Nessuna frammentazione, ma per arrivare al blocco 1000 bisogna leggere i 999 precedenti. La FAT dei vecchi sistemi Windows e delle schede di memoria tiene la catena in una tabella separata, letta in memoria;
• allocazione indicizzata: un blocco indice contiene l’elenco dei blocchi del file. Accesso diretto e nessuna frammentazione esterna; resta da decidere come gestire file con molti blocchi.

L’inode

In Unix ogni file è descritto da un inode, che contiene tutto tranne il nome: dimensione, proprietario, permessi, date e i puntatori ai blocchi. Per gestire sia file piccoli sia enormi, i puntatori sono di quattro tipi.

• 12 puntatori diretti a blocchi di dati;
• un puntatore singolo indiretto a un blocco che contiene puntatori a blocchi di dati;
• un doppio indiretto a un blocco di puntatori a blocchi singoli indiretti;
• un triplo indiretto, con un livello in più.

Teorema. Con blocchi di byte e puntatori di byte, cioè puntatori per blocco, la dimensione massima di un file è

Dimostrazione. I puntatori diretti indirizzano 12 blocchi. Il blocco singolo indiretto contiene puntatori a dati: blocchi. Il doppio indiretto contiene puntatori, ciascuno a un blocco di puntatori a dati: blocchi. Il triplo, con un livello in più, . Sommando e moltiplicando per la dimensione del blocco si ottiene la formula. ∎

Esempio. Con KiB e puntatori di 4 byte, : blocchi, per un massimo di circa 4 TiB. Un file piccolo, fino a 48 KiB, usa solo i puntatori diretti e si legge senza blocchi indice aggiuntivi: la struttura è ottimizzata per il caso comune, perché la maggior parte dei file è piccola. I file system moderni come ext4 sostituiscono i puntatori con gli extent, coppie (primo blocco, lunghezza) che descrivono intere sequenze contigue con un solo elemento.

Cartelle, nomi e collegamenti

Una cartella è un file speciale che contiene coppie (nome, numero di inode). Aprire /home/anna/tesi.txt significa leggere la cartella radice, trovarvi home, leggerne l’inode e la cartella, e così via. Poiché il nome sta nella cartella e non nell’inode, lo stesso file può avere più nomi: un collegamento fisso (hard link) è un’altra voce che punta allo stesso inode, che tiene un contatore dei collegamenti e viene liberato quando arriva a zero. Un collegamento simbolico è invece un piccolo file che contiene un percorso.

I permessi di Unix assegnano lettura, scrittura ed esecuzione (r, w, x) a tre categorie: proprietario, gruppo, altri. Il kernel li controlla a ogni apertura del file, in modalità kernel, e un processo utente non può aggirarli (lezione sulla virtualizzazione e la sicurezza).

La coerenza dopo un guasto

Creare un file richiede di modificare più strutture: la mappa dei blocchi liberi, l’inode, la cartella. Se la corrente manca a metà, il disco resta in uno stato incoerente: un blocco segnato come occupato ma non appartenente a nessun file, o peggio una cartella che punta a un inode non inizializzato. Un tempo, a ogni riavvio, un programma di controllo (fsck) esaminava tutto il disco, impiegando ore sui dischi grandi.

Il journaling risolve con la tecnica del registro scritto prima (write-ahead log), la stessa dei database:

1. le modifiche di un’operazione si scrivono prima in un’area sequenziale, il giornale, seguite da un record di conferma (commit);
2. solo dopo si applicano alle strutture definitive (checkpoint);
3. a operazione completata, la voce del giornale si può cancellare.

Dopo un guasto: se nel giornale c’è un’operazione confermata, la si riapplica dall’inizio; se manca la conferma, la si ignora. Riapplicare è sicuro perché la scrittura dei blocchi registrati è idempotente: scrivere due volte lo stesso contenuto nello stesso blocco dà lo stesso risultato. Ogni operazione è quindi o tutta applicata o per niente: è l’atomicità delle transazioni (lezione sulle transazioni di Sistemi informativi). Il ripristino richiede solo di leggere il giornale, pochi secondi. Per risparmiare scritture, di solito il giornale contiene solo i metadati, non i dati dei file.

Le memorie a stato solido

Le memorie flash (lezione sulle memorie a semiconduttore di Elettronica dei sistemi digitali) hanno regole diverse dai dischi: si scrive per pagine, ma si cancella solo per blocchi grandi, e ogni blocco sopporta un numero limitato di cancellazioni. Un livello di traduzione nel controllore (FTL) scrive sempre in pagine nuove, tiene la corrispondenza tra indirizzi logici e fisici, distribuisce l’usura su tutti i blocchi (wear leveling) e recupera lo spazio delle pagine obsolete in background. Il comando TRIM permette al sistema operativo di dire all’SSD quali blocchi non servono più, così il recupero non deve copiarli inutilmente. Non c’è più tempo di posizionamento della testina: gli algoritmi che ordinavano le richieste al disco per ridurre gli spostamenti del braccio perdono importanza, e conta invece mantenere molte richieste in parallelo.