UNIVERSITÀ DEGLI STUDI DI MODENA E REGGIO EMILIA
Facoltà di Ingegneria – Sede di Modena Corso di Laurea in Ingegneria Informatica
Analisi di alcune implementazioni moderne di file systems: Ext3,
ReiserFS e WinFS
Relatore: Tesi di Laurea di:
Prof.ssa Letizia Leonardi Alessandro Davolio Correlatore:
Ing. Luca Ferrari
__________________________________________________________________________
Anno accademico 2004-2005
SOMMARIO
INTRODUZIONE 4
1 REQUISITI DI UN FILE SYSTEM MODERNO 6
1.1 STRUTTURA DI BASE E MASSIMA CAPACITÀ DI PARTIZIONE 7
1.2 GARANZIA D’INTEGRITÀ DEI DATI 9
1.3 PROBLEMI DI OCCUPAZIONE DEL DISCO IN SISTEMI MULTIUTENTE 11 1.4 PRESERVARE I DATI PRIVATI DA MODIFICHE NON AUTORIZZATE 12
2 IL FILE SYSTEM VIRTUALE DI LINUX (VFS) 15
2.1 DOVE REPERIRE IL CODICE 17
2.2 COLLEGARE UN FILE SYS TEM AL KERNEL 19
2.3 CONNETTERE UN FILE SYSTEM AL DIS CO 20
2.4 TROVARE UN FILE 22
2.5 OPERAZIONI SUGLI INODE 23
3 IL FILE SYSTEM EXT3 27
3.1 STRUTTURA FISICA 27
3.2 GESTIONE DELLE DIRECTORY 30
3.3 ATTRIBUTI ESTESI ED ACL 32
3.4 QUOTE DISCO IN EXT3 34
3.5 JOURNALING 36
3.6 ALTRI PARTICOLARI DI EXT3 39
4 IL FILE SYSTEM REISERFS 41
4.1 ORGANIZZAZIONE DELLA MEMORIA 41
4.2 STRUTTURA FISICA 44
4.3 IMPLEMENTAZIONE DI STREAM DI DATI E DI ATTRIBUTI 47
4.4 JOURNALING 48
4.5 REPACKING 50
4.6 FUTURE CARATTERISTICHE DEL FILE SYSTEM 51
5 WINFS 53
5.1 MEMORIZZAZIONE DEI DAT I: IL MODELLO NTFS 54
5.2 MODELLI DEI DATI 58
5.3 TIPI E SOTTOTIPI 58
5.4 PROPRIETÀ DEGLI OGGETTI E CAMPI DATI 59
5.5 LINGUAGGIO DI DEFINIZIONE DEGLI SCHEMI 60
5.6 RELAZIONI 61
5.7 USARE IL MODELLO DATI DI WINFS 62
5.8 ADO.NET E WINFS 62
5.9 NOTIFICAZIONI 63
6 CONFRONTO PRESTAZIONALE 64
6.1 MONGO BENCHMARK 64
6.2 SLOW BENCHMARK 68
7 CONCLUSIONI 69
APPENDICE A – GLI ALBERI DI DATI 71
A.1. DEFINIZIONI 72
A.2. CHIAVI 73
A.3. BILANCIAMENTO DELLA STRUTTURA 74
APPENDICE B: ACCESS CONTROL LISTS (ACLS) 77
B.1. EVOLUZIONE DEI PERMESSI D’ACCESSO NEI FILE SYS TEM 77
B.2. STRUTTURA DI UNA ACL 78
B.3. ALGORITMO DI CONTROLLO DEGLI ACCESSI 79
APPENDICE C – LINKED LISTS 81
RIFERIMENTI BIBLIOGRAFICI 84
Introduzione
Un file system è quella parte del sistema operativo che consente all’utente di interagire con i dati immagazzinati nei supporti di memoria secondaria: esso rappresenta quindi l’interfaccia tra i dati fisici in queste memorie ed il resto del sistema operativo, oltre che con gli applicativi che utilizzano questi dati.
In questo elaborato si analizzeranno alcune implementazioni di file system, e si andrà a vedere in che modo questi interagiscano con il resto del sistema operativo e con gli applicativi di più alto livello, tenendo conto di tutti i requisiti che un moderno software di questo tipo si trova a dover soddisfare.
I file system che saranno presi in analisi sono tre:
?? Ext3
?? ReiserFS
?? WinFS
Ext3, che assieme a ReiserFS viene utilizzato con i sistemi operativi UNIX e Linux, è un file system di larghissimo impiego, e rappresenta un ottimo esempio di file system moderno sviluppato utilizzando il meccanismo dell’open-source. ReiserFS, anch’esso software distribuito liberamente, è stato però principalmente sviluppato dai programmatori della Namesys, sua azienda produttrice, ed è un software molto più giovane del primo che presenta molte caratteristiche interessanti. WinFS è adottato dal nuovo sistema operativo della Microsoft (Longhorn), ed è ancora in fase di test, ma promette grosse innovazioni per quanto riguarda la gestione dei dati. Di tutti e tre questi file system saranno prese in analisi le principali caratteristiche, ma per problemi di disponibilità di codice sorgente e documentazione, un confronto diretto sarà fatto solo tra i primi due elencati.
Il seguente elaborato è composto di sei capitoli e tre appendici, e dopo questa breve introduzione si andranno ad analizzare nel primo capitolo le caratteristiche e i requisiti che deve fornire un moderno file system: oggi, infatti, un software di questo tipo deve risolvere tutte le problematiche che concernono la gestione dei dati immagazzinati in memorie di massa di dimensioni sempre maggiori, e quindi diventa importante poter recuperare velocemente le informazioni richieste attraverso opportune strategie di gestione della memoria secondaria. Un altro problema molto sentito oggi, è quello della sicurezza delle informazioni memorizzate: un sistema informatico deve garantire
l’integrità dei dati presenti sui propri supporti di memoria sia rispetto ad un danneggiamento fisico (che può essere dovuto a blackout, crash del sistema operativo, o altri motivi che non sono direttamente collegati con operazioni eseguite dall’utente), che rispetto all’alterazione dei dati dovuta ad accessi e modifiche effettuati su questi ultimi da utenti non autorizzati. I moderni sistemi di elaborazione si trovano spesso ad operare con dati memorizzati su supporti di diversa natura, che possono archiviare i dati con meccanismi anche molto diversi tra loro (per esempio dischi rigidi o CD); diventa quindi importante il fatto che un file system possa essere gestito dal resto del sistema operativo in modo trasparente e indipendente dal tipo di dispositivo da cui esso va a recuperare i dati. Un file-system dovrà quindi presentarsi rispetto al codice sovrastante come un insieme uniforme d’istruzioni, con le quali quest’ultimo può interagire con tutti i dati ad esso accessibili, indipendentemente dal tipo di supporto in cui sono memorizzati. Nel secondo capitolo sarà quindi presentata l’interfaccia con cui i sistemi operativi UNIX- like si relazionano con i file systems, soddisfacendo quindi la necessità di trasparenza del codice rispetto alle applicazioni di livello più alto.
I tre capitoli successivi, e cioè il terzo il quarto ed il quinto, riportano l’analisi effettuata sui tre file systems sopra elencati, mentre il sesto capitolo riporta i risultati di due benchmark eseguiti per confrontare Ext3 e ReiserFS, la cui documentazione è stata reperita sulla rete internet.
1 Requisiti di un file system moderno
In questo capitolo verranno prese in analisi le principali caratteristiche ed i requisiti che un file system deve soddisfare per rispondere alle necessità dei moderni sistemi di elaborazione.
Per fare ciò, saranno in primo luogo analizzate, in linea di massima, le caratteristiche e gli usi dei computer odierni.
Al giorno d’oggi i computer sono utilizzati per le applicazioni più svariate, ed un calcolatore general-purpose spesso viene utilizzato con programmi anche molto diversi tra loro (ad esempio video editing, gestione di database, programmi di contabilità, eccetera), enon si è quindi in grado di conoscere a priori il carico di lavoro che la macchina dovrà sopportare.
Non potendo conoscere le condizioni di lavoro in cui un computer andrà ad operare, non si è in grado neanche di conoscere quali componenti (sia hardware che software) saranno sottoposti ad un maggiore stress da lavoro. Per questo motivo i progettisti (anche in questo caso sia hardware che software), negli ultimi anni, hanno cercato di sviluppare i singoli componenti di una macchina in modo che si possano interfacciare con gli altri apparati secondo standard ben definiti, e senza così doversi preoccupare degli altri componenti con i quali andranno ad interagire. Concentrandosi sull’aspetto software, un esempio di come gli sviluppatori abbiano perseguito questa politica è rappresentato dalla stratificazione del codice: tutti i sistemi sono strutturati secondo livelli crescenti, in cui il codice di livello più basso è quello che comanda direttamente la macchina, ed il codice più alto è quello più astratto e con cui interagisce l’utente. In una struttura di questo tipo, ogni strato (layer) di software comunica con lo strato superiore mettendo a sua disposizione un certo numero di funzioni standard da esso interpretabili.
Per quanto riguarda la gestione dei dati nelle memorie secondarie, e più nello specifico i file-system, ci si accorge che anche questi imple mentano diversi meccanismi per garantire la sicurezza delle informazioni rispetto a problemi molto diversi tra loro. Nei paragrafi seguenti saranno illustrati i principali problemi, riguardanti la sicurezza dei dati, che un progettista di file-system si trova a dover risolvere.
1.1 Struttura di base e massima capacità di partizione
Per dare un’idea di base di come un file-system organizzi i dati memoria, si può affermare che esso divide quest’ultima in una serie di blocchi di dimensione finita nei quali va ad immagazzinare i dati. Le informazioni che vengono immagazzinate dentro i blocchi possono essere principalmente di tre tipi:
?? Dati archiviati dall’utente e dalle applicazioni che operano sul sistema: sono i dati generici dei quali fanno uso gli utenti ed i programmi installati (che per fare alcuni esempi possono essere il contenuto di un file di testo oppure un brano audio).
?? Dati riguardanti l’organizzazione della struttura gerarchica della memoria visibile agli occhi dell’utente: per fare un esempio sono tutte le formazioni che dicono quanti e quali file sono presenti in un direttorio, e dove questi si trovano fisicamente in memoria. Questo tipo di dati deve rappresentare un’immagine istantanea della memoria secondaria, e per questo, molte di queste informazioni vengono ricalcolate ed usate nella memoria volatile a run-time.
?? Dati riguardanti la struttura fisica del file-system (metadati): sono tutti quei dati che non sono di diretta utilità per l’utente e non sono ad esso accessibili, ma sono utilizzati dal file-system e dal sistema operativo per gestire in modo corretto tutte le informazioni immagazzinate dall’utente e dagli applicativi.
Questi dati sono ad esempio il numero di blocchi in cui è diviso il disco rigido, la dimensione d’ogni blocco, o una descrizione riassuntiva dell’utilizzo di ogni blocco, e nella maggior parte dei file-system sono memorizzati in un apposito blocco, a cui ha accesso soltanto il sistema operativo, chiamato superblocco.
Questa distinzione fatta per i tipi di dati spesso vale anche per i blocchi di memoria secondaria, in quanto questi sono utilizzati in modo diverso a seconda di dove si trovano all’interno dell’albero dei direttori. Questo albero, che rispecchia l’organizzazione in file e cartelle che appare agli occhi dell’utente, utilizza ciascun blocco o come nodo o come foglia.
I nodi sono quei blocchi che memorizzano tutte le informazioni riguardanti la strut tura gerarchica del file system: essi conterranno quindi i riferimenti ad altri nodi di livello a loro direttamente inferiore, oppure potranno contenere i riferimenti alle foglie, che sono i blocchi che vengono utilizzati per immagazzinare i dati che sono utilizzati da gli
applicativi (file). Esistono poi blocchi speciali riservati a contenere soltanto metadati (il superblocco appunto, con le eventuali sue copie), che sono al di fuori dell’organizzazione gerarchica dei direttori, e piuttosto ne gestiscono l’utilizzo.
Per ulteriori informazioni riguardanti gli alberi si faccia riferimento all’appendice A.
Il problema della massima dimensione di partizione per un file-system è un problema che viene affrontato nelle prime fasi di progetto, in quanto esso va ad influenzare parametri che difficilmente possono essere gestiti in modo automatico dal calcolatore a runtime, come la lunghezza in byte degli indirizzi fisici dei dati presenti in memoria:
decidendo per esempio che lo spazio d’indirizzamento del file system che si vuole progettare sarà di quattro byte, si va a limitare automaticamente a 232 il numero massimo di indirizzi allocabili, ma si va anche stabilire che qualunque oggetto che fa riferimento a dati presenti memoria dovrà contenere un campo di indirizzo della dimensione di 4 byte (32 bit).
Oltre allo spazio d’indirizzamento, esiste poi tutta una serie di parametri che possono andare a ridurre notevolmente lo spazio per i dati archiviati dall’utente, nel caso in cui ci si trovasse a lavorare con applicazioni che archiviano soltanto file di dimensione molto ridotta: questi parametri sono tutte le informazioni aggiuntive riguardanti i file che si vogliono memorizzare (e che non sono di diretto interesse per l’utente), come ad esempio i permessi d’accesso, la data di creazione, l’autore, gli attributi, e la stringa contenente il nome del file. Tutti questi parametri hanno una loro precisa occupazione di memoria e, nel loro insieme, in certi casi possono occupare più spazio su disco di quello occupato dai dati d’interesse per l'utente (in altre parole il contenuto del file stesso).
Un altro problema strettamente correlato con la dimensione dei dati che non sono d’interesse diretto dell’utente, è il numero massimo di file memorizzabili all’interno di un direttorio. Nei file system odierni, le informazioni aggiuntive riguardanti i file (indirizzo fisico da cui recuperare i dati) sono raggruppati in sequenze di dati chiamati
“descrittori” del file stesso; e sono questi descrittori che, memorizzati consecutivamente all’interno di un blocco direttorio, vanno a descrivere i file contenuti all’interno del direttorio stesso. Per aume ntare il numero massimo di file memorizzabili all’interno di un direttorio, il progettista può scegliere di fare due cose:
?? Aumentare la dimensione di blocchi in cui viene divisa la memoria: in questo modo viene reso disponibile più spazio in cui memorizza re i descrittori dei file ed allo
stesso tempo vengono velocizzare le operazioni di I/O, in quanto le testine del disco rigido dovranno fare meno salti tra un blocco e l’altro per accedere al contenuto di un file. D’altro canto, però, blocchi di maggiore dimensione implicano un maggiore spreco di spazio su disco. Bisogna considerare che mediamente l’ultimo blocco allocato ad un file è di solito occupato solo per la metà del suo spazio, quindi più un blocco diventa grande, maggiore sarà lo spazio sprecato ne ll’ultimo blocco d’ogni file.
?? Diminuire la dimensione delle informazioni che si vogliono memorizzare nei descrittori: questa soluzione permette sì di memorizzare un maggior numero di file all’interno di un direttorio, ma allo stesso tempo diminuisce drasticamente il numero d’informazioni aggiuntive che possono essere memorizzate come riferimento ad un file.
Bisogna però ricordare che la maggior parte dei file-system, per ovviare a questo problema, utilizza una soluzione intermedia: si sceglie in pratica di memorizzare all’interno del descrittore soltanto le informazioni che devono essere recuperate in modo più veloce, e si decide di collocare tutti i dati che sarebbero letti solo in caso d’interazione con il contenuto del file (come ad esempio i permessi d’accesso, che possono essere letti in caso di richiesta di accesso contenuto del file) assieme al contenuto del file stesso, cioè i dati generici archiviati da utente ed applicazioni.
1.2 Garanzia d’integrità dei dati
Un altro requisito che i file system devono soddisfare, è quello di garantire l’integrità dei dati anche dopo blackout o altri arresti improvvisi del sistema che possono lasciare incompiute le operazioni di I/O.
Per prima cosa bisogna osservare che in caso di riavvio dopo blackout, i dati che potrebbero risultare corrotti o danneggiati possono essere sia i dati utente sia quelli riguardanti il file system in sè; è quindi necessario provvedere a meccanismi che assicurino sia i dati dell’utente sia i dati ad uso ristretto del sistema operativo.
Nel caso in cui un arresto improvviso del sistema dovesse danneggiare il superblocco, nel migliore dei casi, il sistema operativo si troverebbe ad interpretare (se i dati danneggiati risultassero per caso interpretabili dalla macchina) informazioni che non rispecchiano l’organizzazione e l’uso della memoria, col rischio di danneggiare le
rimanenti porzioni di dati che non sono stati coinvolti in precedenza. Per ovviare a questo problema la maggior parte dei file system mantiene almeno una copia del superblocco, o comunque di tutte le informazioni sulla struttura della memoria, in settori del disco lontani dal superblocco stesso; questo per scongiurare che le testine del disco rigido, durante l’arresto, possano danneggiare le copie nel caso queste fossero posizioniate in settori adiacenti il superblocco. Una soluzione di questo tipo garantisce nella maggior parte dei casi che il sistema riesca a recuperare i dati riguardanti l’organizzazione delle informazioni su disco, ma allo stesso tempo crea un’elevata ridondanza della metadata; cosa che però non va ad influire molto sullo spazio messo a disposizione per i dati utente, viste le piccole dimensioni occupate dalle informazioni strutturali rispetto alle dimensioni dei dischi rigidi in questo momento in commercio.
Un’altra soluzione che viene utilizzata per controllare la presenza di errori all’interno dei blocchi sono le “bitmap”: esse sono dei record di dimensione variabile (dipendente dimensione del blocco stesso) che rappresentano l’utilizzo dei vari byte (oppure altra misura di memoria utilizzata dal sistema operativo) del blocco stesso; in questi record, generalmente, ogni bit rappresenta un’unità di memoria del blocco, ed il fatto che un bit sia uguale a 1 o a 0 sta ad indicare l’utilizzo o meno della relativa unità di memoria del blocco (dove per unità di memoria s’intende appunto la misura di memoria utilizzata dal S.O., qualunque essa sia). Una soluzione di questo tipo può essere adottata anche nel superblocco, per descrivere sia l’utilizzo del superblocco stesso che l’uso, nel loro complesso, di tutti gli altri blocchi di memoria.
Un metodo già da tempo adottato per garantire l’integrità delle informazioni in memoria è quello di eseguire automaticamente, al riavvio della macchina dopo un arresto non previsto, le utility per il controllo dell’integrità dei dati messe spesso a disposizione assieme dal sistema operativo (ad esempio scandisk per i sistemi Microsoft, oppure e2fsck per le partizioni formattate con Ext2): l’utilizzo di questi programmi, però, si sta rivelando sempre meno pratico per via delle dimensioni sempre maggiori dei dischi rigidi odierni. Questo tipo di programmi, generalmente, non compie ricerche mirate dei dati danneggiati, ma esegue scansioni complete della memoria, cercando blocco per blocco gli eventuali dati danneggiati, aumentando così il tempo necessario ad eseguire una scansione completa proporzionalmente alle dimensioni della memoria stessa.
Un metodo per garantire l’integrità dei dati che ha preso piede negli ultimi anni, consiste nel registrare periodicamente le operazioni di I/O eseguite su disco all’interno di un log (registro, diario), in modo da avere sempre sotto controllo quali dati sono stati realmente scritti in memoria secondaria. In linea di massima questi meccanismi funzionano tutti allo stesso modo: prima di eseguire un’operazione di scrittura su disco, il file-system registra una copia dei dati che andranno ad essere scritti nella porzione di memoria adibita a registro, dati che saranno tolti dal registro soltanto dopo che l’operazione di scrittura è stata eseguita. In questo modo, nel caso di arresti non previsti di sistema, il file-system può usare il registro per controllare quali operazioni di scrittura sono rimaste eventualmente incompiute, andando così a ripristinare integrità dei dati.
Una soluzione di questo tipo risulta essere molto più funzionale sui sistemi odierni dell’utilizzo degli appositi programmi per il controllo d’integrità, ma allo stesso tempo deve far fronte a tutti i problemi d’integrità dei dati nel registro che non riguardano tutto il resto della memoria in caso di blocchi improvvisi: il file-system deve essere quindi in grado di “capire“ quali operazioni di scrittura sono andate a buon fine, indipendentemente dal fatto che il registro sia o meno stato danneggiato durante l’arresto. Un altro problema che questo tipo di registri deve affrontare riguarda la scrittura su disco di file molto estesi: il fatto di porre sul registro tutti i file che devono essere scritti, indipendentemente dalla loro dimensione, causa uno spreco di memoria ed un rallentamento delle operazioni di scrittura (con questo meccanismo un file viene scritto due volte in memoria secondaria ) proporzionali alla dimensione del file stesso;
bisogna quindi porre un limite massimo alla dimensione dei file scrivibili in registro, ed allo stesso tempo definire una politica di trattamento della scrittura dei file di dimensioni superiori.
1.3 Problemi di occupazione del disco in sistemi multiutente
Un altro dei problemi che i file-system si trovano a dover risolvere riguarda l’utilizzo della memoria di massa da parte dei vari utenti di uno stesso sistema. Il centro della questione non è tanto quello di garantire un equo spazio a tutti gli utenti, ma principalmente è l’impedire che l’intero disco rigido venga occupato dai dati dei vari utilizzatori, impedendo così la possibilità di eseguire operazioni di manutenzione o di ripristino di informazioni su disco da parte dell’amministratore. Le soluzioni per
ovviare a questo problema sono numerose, e ciascun file-system ne adotta alcune in particolare; in questo paragrafo ci si limiterà ad elencare le caratteristiche delle principali di queste.
Il metodo più banale per ovviare a questo problema è quello di riservare permanentemente uno spazio minimo di memoria, di dimensione stabilita, all’amministratore di sistema; in questo modo si lascia ciascun utente libero di utilizzare tutte le risorse di sistema disponibili, lasciando un minimo di spazio riservato al superutente per le operazioni d’emergenza, nel caso il disco si riempisse.
Una soluzione più raffinata della precedente consiste nel riservare a ciascun utente opportune porzioni di memoria, con le quali memorizzare i propri dati personali: queste porzioni prendono il nome di “quote disco” (disk quo tas). Assieme alle quote disco può essere poi definita una serie di politiche, riguardanti l’uso di queste ultime, spesso gestite dai livelli superiori del sistema operativo, e non direttamente dal file-system:
viene spesso permesso di condividere le quote disco tra utenti dello stesso gruppo, oppure viene dato il permesso a certi utenti di poter usufruire delle quote disco di altri, ecc.
Accanto alle politiche di gestione delle quote si affiancano poi le politiche d’archiviazione dei dati: la stragrande ma ggioranza dei file-system odierni permette di definire il direttorio di lavoro e quello di partenza di ciascun utente, in modo che questi possa archiviare i propri dati soltanto in questi spazi definiti, a cui possono avere accesso soltanto altri utenti autorizzati; si può anche decidere di utilizzare le politiche in modo combinato, riservando tutta la quota disco di un singolo utente soltanto all’interno della propria cartella di lavoro, in modo che esso non abbia la possibilità di archiviare i suoi dati fuori da quest’ultima.
1.4 Preservare i dati privati da modifiche non autorizzate
Accanto al problema delle quote disco e delle politiche di gestione dello spazio utente, si affiancano tutti i problemi che riguardano la garanzia dell’integrità e della privatezza dei dati rispetto ad accessi effettuati da utenti non autorizzati; ecco perchè la maggior parte dei sistemi operativi multiutente prevede la possibilità di limitare l’accesso ai contenuti dei file.
Tutti i sistemi di sicurezza delle memorie secondarie, utilizzati dai sistemi operativi, ruotano attorno ai concetti di utente, gruppo, permesso e proprietà.
Per utente s’intende ogni singolo utilizzatore, che è automaticamente identificato attraverso un codice univoco chiamato “identificativo di protezione” (security identifier - SID); codice che viene utilizzato dal sistema anche per identificare i profili utente, che raccolgono tutte le informazioni e le impostazioni personalizzate sull’utilizzo del sistema di ogni utente. Per gruppo s’intende invece un generico insieme d’utenti, accomunato dal fatto di possedere le stesso codice identificativo di gruppo (group identifier – GID), che viene memorizzato all’interno di ciascun profilo utente. Se si definisce il termine “proprietà” come l’insieme di tutte le operazioni che sono eseguibili su un documento o, in generale, un file, il termine permesso assume il significato di relazione tra utente o gruppo, e proprietà di un documento: un permesso di lettura, per esempio, è la relazione di autorizzazione all’azione di lettura di un determinato file, concessa ad un utente oppure ad un gruppo.
I sistemi di controllo d’accesso ai dati degli odierni sistemi operativi hanno, in generale, alcune caratteristiche in comune:
?? Accesso discrezionale ad oggetti da proteggere: il proprietario di un oggetto, ad esempio un file o una cartella, è in grado di concedere o negare l’autorizzazione ai vari utenti, per controllare come e da chi l’oggetto viene utilizzato.
?? Ereditarietà delle autorizzazioni: gli oggetti possono ereditare l’autorizzazione dall’oggetto che li contiene, ad esempio un file può ereditare le autorizzazioni della cartella in cui è contenuto.
?? Privilegi di amministratore: è possibile controllare gli utenti o i gruppi che possono eseguire funzioni amministrative e apportare modifiche che influiscono sulle risorse di sistema.
?? Controllo di eventi di sistema: è possibile utilizzare delle funzionalità di controllo per individuare eventuali tentativi di elusione della protezione o per creare un itinerario di controllo.
?? Utilizzo di liste di controllo accesso (access control list – acl): le acl sono liste ordinarie di regole che vengono usate per prendere una decisione, ad esempio se permettere o meno ad un certo utente l’accesso ad un file; ciascuna regola esprime una o più proprietà dell’oggetto da valutare (ad esempio l’autore, il nome o l’indirizzo di un file), e se queste proprietà sono verificate essa indica
quale decisione prendere1. Queste strutture non trovano impiego soltanto all’interno di file system, ma sono largamente usate per la gestione degli accessi nei dispositivi di rete: esse, infatti, possono essere per esempio utilizzate nella configurazione dei firewall o come controlli di smistamento dei pacchetti passanti sui router.
1 Per una trattazione più ampia di questo tema si faccia riferimento all’appendice B.
2 Il File System Virtuale di Linux (VFS)
Prima di iniziare ad analizzare due file system utilizzabili su sistemi Linux, è necessario dare un paio di nozioni riguardo a come il sistema operativo dispone di un’unica interfaccia in grado di relazionarsi in modo trasparente con i file system che sono utilizzati sulla memoria, e in modo indipendente da questi ultimi.
In Linux, l’accesso a tutti i file avviene attraverso il Virtual Filesystem Switch, o VFS [VFS]. Questo è uno strato di codice interposto tra il file-system ed il resto del sistema operativo, che implementa le operazioni generiche di file system richieste dal sistema collegandole con lo specifico codice necessario per gestirle (codice che sarà necessariamente diverso a seconda del file system utilizzato). Per ragioni di comodità, nei seguenti capitoli, si farà riferimento al Virtual Filesystem Switch anche con i termini
“file system virtuale” e “switch virtuale”.
La figura 2.1 mostra come il Kernel di sistema operativo intercetti tutte le richieste d’accesso ai dati eseguite dalle applicazioni, le passi al VFS che, associando ad esse il corretto codice a seconda del file system su cui i dati si trovano, formula delle richieste di accesso al file system appropriate. Tutte le richieste d’accesso ai dati sono gestite utilizzando un buffer dati virtuale (buffer cache), le cui operazioni in uscita vanno ad accedere alle informazioni per mezzo dei driver che comandano le memorie fisiche.
Tutte queste operazioni sono eseguite in modo del tutto trasparente rispetto alle applicazioni di più alto livello, in quanto l’elaborazione delle richieste avviene a livello di Kernel.
Figura 2.1: Funzionamento del VFS all’interno del kernel Linux.
Per meglio chiarire il funzionamento del VFS, in questo capitolo saranno utilizzate parti di codice che lo switch usa per gestire il funzionamento del file system Ext2. Il modo con cui il VFS interagisce con il codice degli altri file system è del tutto analogo a quello riportato nei paragrafi successivi.
Tutto il VFS interagisce con i file system presenti sulle memorie secondarie utilizzando due entità diverse (e le relative strutture dati che le descrivono, dichiarate nel file linux/fs.h):
?? Il superblocco, descritto nella struttura super_block, che contiene la descrizione del superblocco (e quindi di tutto il file system) e fornisce una serie di metodi al sistema operativo per interagire con esso.
?? L’inode, definito nell’omonima struttura, che contiene la descrizione di un file o direttorio a cui si vuole accedere (in Linux le directory sono interpretate dal sistema come particolari tipi di file contenenti una serie di riferimenti, “inode number”, ad altri file). Ogni inode rappresenta un file, e contiene tutte le informazioni necessarie alla gestione del contenuto del file stesso (indirizzo fisico, nome, lunghezza, ecc.), ed è identificato da un preciso “inode number”
che permette di rintracciarlo all’interno di una tabella in cui sono memorizzati tutti gli inode presenti sul file system (e di conseguenza anche tutti i file). Un esempio di come il VFS utilizza gli inode per organizzare i dati all’interno delle directory è mostrato in figura 2.2: ogni direttorio contiene un riferimento alla tabella degli inode per ogni file in esso contenuto, e per accedere ai dati del file sarà quindi necessario andare a leggere il contenuto dello specifico inode nella tabella. L'inode table, infatti, contiene l'elenco di tutti gli inode (quindi di tutti i file) sulla partizione (questo per i file system fisici, di cui si tratta nel presente elaborato), e per ognuno di questi vengono memorizzati uno o più riferimenti alla corrispondente voce di tabella all’interno dei direttori.
Figura 2.2: Utilizzo della tabella degli inode per organizzare i file all'interno delle directory.
Assieme a queste entità entrano anche in gioco le strutture dati ad esse correlate, che forniscono le operazioni che il sistema può eseguire sulle entità stesse; strutture che sono principalmente super_operations, inode_operations e file_operations, ed altre che sono comunque contenute in linux/fs.h.
2.1 Dove reperire il codice
Il codice sorgente del VFS si trova nel sottodirettorio fs/ dei sergenti del kernel di Linux, assieme ad altre parti di codice correlate, come la buffer cache ed il codice per interagire con tutti i formati di file eseguibile. Ogni specifico file system è contenuto in una directory inferiore; per esempio, i sorgenti del file system Ext2 sono contenuti in fs/ext2/.
La tabella 2.1 riporta il nome dei file del direttorio fs/, e dà per ciascuno di essi una breve descrizione. La colonna centrale, chiamata system, vuole indicare a quale sottosistema il file è (principalmente) dedicato:
?? EXE significa che i file è utilizzato per gestire ed interagire con i file eseguibili
?? DEV significa che viene utilizzato come supporto ai driver per i vari dispositivi installati sulla macchina
?? BUF significa gestione della buffer cache.
?? VFS significa che il file è parte del file system virtuale, e delega alcune funzionalità al codice specifico di ogni file system
?? VFSg indica che il codice presente nel file è completamente generico e non delega mai parte le sue funzioni a codice specifico di ogni file system.
File system Funzione
binfmt_aout.c EXE Esecuzione degli eseguibili di tipo a.out binfmt_elf.c EXE Esecuzione dei file eseguibili di tipo ELF binfmt_java.c EXE Esecuzione dei file java e delle applets binfmt_script.c EXE Esecuzione degli script di tipo # e !
block_dev.c DEV Funzioni read(), write(), e fsync() per blocchi generici
buffer.c BUF Gestione della buffer cache, che memorizza i blocchi letti dai dispositivi.
dcache.c VFS La directory cache, che memorizza i nomi dei direttori durante le ricerche.
devices.c DEV Funzioni per il supporto di dispositivi generici, come ad esempio i registri
dquot.c VFS Supporto generico per la gestione delle quote disco.
exec.c VFSg Supporto generico per i file eseguibili. Le funzioni di call si trovano nei files binfmt_*.
fcntl.c VFSg Supporto per la gestione dei descrittori dei file con la funzione fcntl().
fifo.c VFSg Gestione del buffer FIFO per l’accesso ai dischi.
file_table.c VFSg Lista dinamicamente estensibile dei files aperti dal sistema.
filesystems.c VFS Tutti il file system precompilati sono richiamati da questo file attraverso la funzione init_name_fs().
inode.c VFSg Lista dinamicamente estensibile degli inode aperti dal sistema.
ioctl.c VFS
Primo livello per l’handling dei controlli di I/O;
successivamente l’handling viene passato al file system o al driver interessato, se necessario.
locks.c VFSg Supporto per le varie operazioni di locking dei file
namei.c VFS Riempie l’inode una volta fornito il percorso. Implementa diverse system calls collegate ai nomi dei file.
noquot.c VFS Ottimizzazione per gestire il sistema nel caso no n si usino le quote disco
open.c VFS Contiene system calls, comprese open(), close(), and vhangup().
pipe.c VFSg Implementazione delle pipes.
read_write.c VFS read(), write(), readv(), writev(), lseek().
readdir.c VFS Contiene diverse interfacce usate per la lettura delle directory select.c VFS Le basi per la system call select()
stat.c VFS Supporto per stat() e readlink()
super.c VFS Supporto per superblocco, filesystem registry, mount()/umount().
Tabella 2.1: Breve descrizione del contenuto dei file che compongono il codice del VFS Linux.
2.2 Collegare un file system al kernel
Per poter utilizzare i dati presenti in un particolare file system, in UNIX e Linux, sono necessarie due operazioni: la registrazione del file system ed il montaggio della partizione dati.
Registrare un file system significa fornire al VFS le caratteristiche del file system che si vuole utilizzare, come ad esempio il tipo di file system, in modo che lo switch virtuale sia poi in grado di reperire il codice necessario per gestire quel particolare tipo di partizione.
Se si cerca nel codice di ogni file system la funzione init_name_fs(), si vede che essa contiene poche linee di codice. Per esempio, nel file system Ext2, la funzione è come segue (da fs/ext2/super.c):
int init_ext2_fs(void) {
return register_filesystem(&ext2_fs_type);
}
Tutto quello che la funzione svolge è registrare il file system nel sistema operativo attraverso la strutturaext2_fs_type:
static struct file_system_type ext2_fs_type = { ext2_read_super, "ext2", 1, NULL
};
ext2_read_super è un puntatore a funzione che indica al sistema operativo l’indirizzo in cui si trova la funzione per la lettura del superblocco nei file system di tipo Ext2 (operazione necessaria per montare correttamente un qualsiasi file system).
“ext2” è il nome del tipo di file system, che è usato (ad esempio quando si digita il comando mount … -t ext2) per determinare quale file system utilizzare per montare un disco rigido. “1” indica che il file system richiede un dispositivo di memoria su cui operare (a differenza per esempio dei file system di rete, che non si relazionano direttamente con una memoria di massa, ma recuperano i dati, attraverso un’interfaccia di rete, da una memoria remota), e NULL è necessario per riempire lo spazio che verrà utilizzato per mantenere una linked list di tutti i file system nel registro del VFS, contenuto in fs/super.c.
2.3 Connettere un file system al disco
Il resto della comunicazione tra il codice del file system ed il Kernel non avviene finché non viene montato un dispositivo (partizione dati, o intero disco rigido) che utilizza quel tipo di file system. Quando si monta un dispositivo contenente un file system di tipo Ext2, viene chiamata la funzione ext2_read_super() che, andando a leggere i dati contenuti nel superblocco, fornisce al sistema operativo i dati riguardanti la struttura fisica della partizione. Se la lettura del superblocco avviene con successo e la funzione è in grado di collegare lo specifico file system al disco che si vuole montare, essa riempie la struttura super_block con diverse informazioni che includono un puntatore alla struttura chiamata super_operations, che a sua volta contiene puntatori a funzioni volte alla manipolazione dei superblocchi; in questo caso, puntatori a funzioni specifiche di Ext2.
Il superblocco è la parte di memoria che definisce la struttura dell’intero file system su di un dispositivo, e le operazioni che riguardano il file system nella sua interezza (al contrario delle operazioni che riguardano i singoli file) sono considerate operazioni di superblocco. La struttura dati super_operations contiene puntatori a funzione volte alla manipolazione degli inode, del superblocco, e che notificano o cambiano lo stato del file system nel suo complesso (statfs() e remount()).
Ecco com’è definita la struttura super_operations nel file system virtuale (da linux/fs.h):
struct super_operations {
void (*read_inode) (struct inode *);
int (*notify_change) (struct inode *, struct iattr *);
void (*write_inode) (struct inode *);
void (*put_inode) (struct inode *);
void (*put_super) (struct super_block *);
void (*write_super) (struct super_block *);
void (*statfs) (struct super_block *, struct statfs *, int);
int (*remount_fs) (struct super_block *, int *, char *);
};
Come si nota, tutti i dati definiti dalla struttura sono puntatori a funzione, che andranno a contenere l’indirizzo di memoria a cui reperire le funzioni che saranno usate dal VFS per interagire con i dati sulle memorie di massa. Sotto viene riportata la dichiarazione più semplice di istanza di questa struttura nel file system Ext2, che rappresenta le funzioni che questo file system fornisce allo switch virtuale associandole a super_operations (vedi in fs/ext2/super.c):
static struct super_operations ext2_sops = { ext2_read_inode,
NULL,
ext2_write_inode, ext2_put_inode, ext2_put_super, ext2_write_super, ext2_statfs, ext2_remount };
Quando un file system viene connesso al disco (ed il modulo che si prende carico di questo compito corrisponde al file sorgente fs/super.c), la funzione do_umount() chiama read_super la quale, a sua volta, termina chiamando (nel caso si stia utilizzando il file system Ext2) ext2_read_super(), funzione che ritorna il superblocco al resto del sistema operativo. Il superblocco ritornato contiene un
riferimento alla struttura ext2_super_operations; esso include anche molti altri dati, che possono essere reperiti nello specifico all’interno della definizione di struct super_block in include/linux/fs.h.
2.4 Trovare un file
Una volta che il file system è stato montato correttamente, è possibile accedere ai file che sono presenti al suo interno. I passi da compiere in questo caso sono due: utilizzare il nome del file per trovare l’inode da esso puntato, e quindi accedere all’inode.
Quando il file system virtuale cerca il nome di un file o di un direttorio, esso include nella ricerca anche il suo percorso, operazione che viene fatta automaticamente dal sistema se il nome dell’oggetto da trovare non è un nome assoluto (cioè non ha inizio col carattere ‘/’). Per trovare gli oggetti in memoria, il sistema operativo utilizza il codice specifico del file-system in cui i dati sono memorizzati; esso esamina il percorso del file un componente per volta (le varie componenti di un percorso sono separate dal carattere ‘/’). Se il componente preso in esame è una directory, allora il componente successivo sarà cercato all’interno del direttorio appena trovato. Ogni componente che viene identificato, indipendentemente dal fatto che sia un file o un direttorio, ritorna un
“inode number” che lo identifica univocamente, ed attraverso il quale sono resi disponibili i contenuti dell’oggetto.
Se eventualmente l’oggetto trovato risultasse essere un collegamento simbolico ad un altro file, allora il VFS inizierebbe una nuova ricerca di file, il cui nome è quello restituito dal collegamento simbolico. Al fine di prevenire cicli di ricerca ricorsivi infiniti, viene posto un limite alla profondità dei collegamenti simbolici: il Kernel seguirà soltanto un certo numero di collegamenti ricorsivi prima di interrompere l’operazione segnalando un errore.
Solo dopo che il VFS ed il file system hanno recuperato il numero di inode dal nome del file (compito svolto dalla routine namei(), in namei.c) è possibile accedere ai contenuti dell’inode.
La funzione iget() trova e ritorna al sistema operativo l’inode identificato dall’inode number che gli viene fornito come parametro; la funzione iput() è invece utilizzata dal sistema per rilasciare l’accesso ad un inode che non deve più essere utilizzato.
Queste funzioni, in linea di principio, sono simili a malloc() e free(), con l’unica
differenza che più processi possono mantenere simultaneamente l’accesso ad uno stesso inode, inoltre viene mantenuto un conteggio dei processi attivi che fanno uso di quest’ultimo, in modo da poter conoscere quando l’inode può essere effettivamente rilasciato dal file-system.
Il file handle2 che viene passato al codice di una generica applicazione dopo la richiesta di accesso ad un file, è in realtà un numero di tipo integer che indica l’offset (distanza dall’inizio di tabella) sulla tabella dei file per trovare la voce cercata; la voce della tabella a cui l’applicazione può accedere in questo modo, contiene l’inode number che era stato cercato dalla funzione namei() fino a quando il file non viene chiuso dal processo o è il processo stesso a terminare. Quando un qualsiasi processo fa una qualsiasi operazione su di un file utilizzando i “file handle”, essa va in realtà a manipolare ed interagire con il relativo inode.
2.5 Operazioni sugli inode
L’inode number e la struttura di inode stessa non possono essere creati dal VFS stesso, esse devono essere fornite dal file system, in quanto è questa ultima parte di codice che gestisce l’interazione del resto del sistema operativo con i dati presenti in memoria secondaria.
Di seguito viene riportato in che modo il file system virtuale ottiene il numero di inode partendo dal nome del file a cui si vuole accedere.
Il VFS inizia la ricerca della prima directory contenuta nel percorso, che dal suo nome ricava il rela tivo inode; a questo punto l’inode è utilizzato per trovare il direttorio3 successivo contenuto nel percorso, e così via fino ad esaurire i componenti del percorso.
Quando in questo modo la ricerca raggiunge la fine, il sistema ricava l’inode relativo al file o al direttorio che stava cercando. Una ricerca di questo tipo può iniziare solo se il VFS ha a disposizione un inode di partenza, cosa che viene fornita al momento del montaggio del file system dal superblocco, attraverso un puntatore ad inode contenuto in quest’ultimo chiamato s_mounted, che contiene un riferimento ad una struttura di tipo inode per l’intero file system. Questo inode è allocato quando il file system viene
2 Un file handle è, in genere, una struttura dati che permette ad un’applicazione di alto livello di accedere ed eventualmente modificare i dati presenti in un file; è il meccanismo con cui il codice del sistema operativo permette alle applicazioni di utilizzare i dati nelle memorie, ed è fornito dal sistema operativo a seguito della richiesta di accesso ad un file da parte di un’applicazione.
3 Vedi il paragrafo relativo alla gestione dei direttori nel capitolo su Ext3.
montato, e rimosso dalla memoria all’atto dello smontaggio. L’inode s_mounted rappresenta il direttorio di root nei file system Linux, e quindi anche in Ext2 ed Ext3, e partendo da questo possono essere ritrovati gli altri inode presenti in memoria.
Ogni inode ha inoltre un puntatore ad una struttura a sua volta composta di puntatori a funzione, struttura che prende il nome di inode_operations. L’elemento chiamato lookup() è quello che viene usato dal VFS per recuperare un altro inode presente sullo stesso file system. In generale un file system ha soltanto una funzione lookup(), che viene utilizzata per ogni inode presente su di esso, ma è anche possibile avere diverse funzioni di lookup() che possono sono utilizzate su un’unica partizione; il file system proc consente questa molteplicità perché su di esso esistono direttori che hanno funzioni differenti. La struttura inode_operations è la seguente (definita in linux/fs.h).
struct inode_operations {
struct file_operations * default_file_ops;
int (*create) (struct inode *,const char *,int,int,struct inode **);
int (*lookup) (struct inode *,const char *,int,struct inode **);
int (*link) (struct inode *,struct inode *,const char *,int);
int (*unlink) (struct inode *,const char *,int);
int (*symlink) (struct inode *,const char *,int,const char *);
int (*mkdir) (struct inode *,const char *,int,int);
int (*rmdir) (struct inode *,const char *,int);
int (*mknod) (struct inode *,const char *,int,int,int);
int (*rename) (struct inode *,const char *,int,struct inode *,const char *,int);
int (*readlink) (struct inode *,char *,int);
int (*follow_link) (struct inode *,struct inode *,int,int,struct inode **);
int (*readpage) (struct inode *, struct page *);
int (*writepage) (struct inode *, struct page *);
int (*bmap) (struct inode *,int);
void (*truncate) (struct inode *);
int (*permission) (struct inode *, int);
int (*smap) (struct inode *,int); };
La maggior parte di queste funzioni è direttamente riferita ad una precisa chiamata di sistema (system call).
In Ext2 e in Ext3, direttori, file e link simbolici hanno differenti istanze di inode_operations (cosa verificata anche in molti altri sistemi operativi), esse sono reperibili nei seguenti file:
?? fs/ext2/dir.c contiene la struttura ext2_dir_inode_operations
?? fs/ext2/file.c contiene la struttura ext2_file_inode_operation
?? fs/ext2/symlink.c contiene ext2_symlink_inod_operations
Esistono poi diverse system call riguardanti file (e direttori) che non sono comprese all’interno della struttura inode_operations, e si trovano invece all’interno della struttura file_operations: struttura che contiene tutte le funzioni che operano specificamente sui file e sul loro contenuto, piuttosto che sugli inode; la dichiarazione della struttura è riportata di seguito.
struct file_operations {
int (*lseek) (struct inode *, struct file *, off_t, int);
int (*read) (struct inode *, struct file *, char *, int);
int (*write) (struct inode *, struct file *, const char *, int);
int (*readdir) (struct inode *, struct file *, void *, filldir_t);
int (*select) (struct inode *, struct file *, int, select_table *);
int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
int (*mmap) (struct inode *, struct file *, struct vm_area_struct *);
int (*open) (struct inode *, struct file *);
void (*release) (struct inode *, struct file *);
int (*fsync) (struct inode *, struct file *);
int (*fasync) (struct inode *, struct file *, int);
int (*check_media_change) (kdev_t dev);
int (*revalidate) (kdev_t dev);
};
Al di là degli esempi presentati in questo capitolo, dunque, secondo il modello VFS, il ruolo di uno specifico file system è quello di fornire un superblocco, una lista di inode (uno per ogni file presente), e di fornire un’implementazione che supporti le operazioni richieste dal sistema operativo (come appunto apertura, lettura, scrittura su file), cosa che viene fatta attraverso le strutture e le routine prese in analisi in questo capitolo. Le strutture file_operations, inode_operations e super_operations, una volta che il file system viene montato, andranno a contenere tutti i riferimenti che servono al sistema operativo per reperire le funzioni che implementano le operazioni sui file per quel determinato tipo di file system.
3 Il File system Ext3
In questo capitolo sarà preso in analisi il file system ext3, diretto discendente di ext2, dal quale eredita gran parte del suo codice sorgente e lo mantiene in sostanza immutato.
Questo filesystem, infatti, rappresenta un adeguamento alle necessità odierne di un file system già molto stabile e versatile, a cui sono state aggiunte parti di codice per aumentarne le funzionalità, la più importante delle quali, come si vedrà in seguito, è l’implementazione di un journaling layer. Il modo con cui ext3 interagisce con i livelli più alti del sistema operativo è esattamente lo stesso che viene utilizzato in ext2, l’unica cosa che cambia, ovviamente, sono i direttori in cui i sorgenti dei due file system possono essere reperiti.
3.1 Struttura fisica
Il file system è costituito di tanti gruppi di blocchi (block groups) di memoria secondaria, che non hanno però necessariamente una corrispondenza diretta con i blocchi fisici sulla memoria di massa, specialmente da quando i dischi rigidi sono stati ottimizzati per le operazioni di lettura sequenziale e quindi tendono a nascondere la loro struttura fisica al sistema operativo che li gestisce[vfs/ext2].
La struttura fisica del file system è rappresentata nella figura 3.1.
Copia del Superblocco
Descrittore di gruppo
Block Bitmap
Inode Bitmap
Parte della inode Table
Blocchi Dati Superblocco Gruppo di
blocchi 1
Gruppo di blocchi 2
Gruppo di blocchi 3
Gruppo di blocchi 4
Gruppo di blocchi n 0 1024
BOOT Sector
2048
Figura 3.1: Organizzazione della memoria nei file system Ext3.
Il punto di partenza per il file system è sempre il superblocco, che è una struttura dati di 1024 bytes allocata ad una distanza di 1024 bytes dall’inizio della partizione; il resto della memoria viene diviso in vari gruppi di blocchi.
Ogni gruppo di blocchi contiene una copia delle informazioni fondamentali di controllo della memoria (superblocco ed i descrittori di file system), ed inoltre contiene una parte del file system: una block bitmap, una inode bitmap, una parte della tabella degli inode (inode table) ed i blocchi dati.
La tabella degli inode non viene quindi memorizzata tutta in un particolare settore di memoria, ma è suddivisa nei vari block groups in modo che ogni file si trovi nei limiti del possibile nello stesso gruppo di blocchi del corrispondente inode, così da ridurre al minimo gli spostamenti delle testine del disco durante le richieste d’accesso ai contenuti di un file.
L’utilizzo dei gruppi di blocchi rappresenta un vantaggio anche in termini di affidabilità del sistema, visto che la replicazione delle strutture dati di controllo in ogni block group consente un facile recupero del superblocco nel caso questo risulti essere corrotto o danneggiato. La presenza della copia del superblocco in ogni gruppo può essere impostata attraverso l’uso della flag SPARSE_SUPERBLOCK, che a seconda del suo stato notifica o meno la presenza del superblocco all’interno di un block group. In questo modo è possibile diminuire lo spreco di memoria evitando di mantenere una copia del superblocco in ogni gruppo, memorizzandola soltanto all’interno di alcuni.
Il descrittore di gruppo contiene le informazioni riguardanti la struttura del gruppo di blocchi a cui appartiene, ed è una struttura dati formata dai seguenti elementi:
Nome campo tipo di
dato commento
bg_block_bitmap ULONG
Contiene l’indirizzo del blocco in cui è immagazzinata la block bitmap per questo gruppo.
bg_inode_bitmap ULONG
Contiene l’indirizzo in cui è memorizzata l’inode bitmap per questo gruppo.
bg_inode_table ULONG
Contiene l’indirizzo in cui è memorizzata la inode table per questo gruppo.
bg_free_blocks_count USHORT Conteggio dei blocchi liberi di questo gruppo
bg_free_inodes_count USHORT Conteggio degli inode liberi di questo gruppo
bg_used_dirs_count USHORT Numero di inode del gruppo che sono directory
bg_pad USHORT padding
bg_reserved ULONG[3] padding
La dimensione del descrittore può essere calcolata come (sizeof(Ext3_group)*numero_di_gruppi)/dimensione_blocco.
La block bitmap è una serie di bit che indica quali blocchi del gruppo sono stati allocati e quali no (ogni blocco è rappresentato da un bit) ed, analogamente, l’inode bitmap rappresenta quali voci, della parte di inode table presente nel gruppo, sono state allocate ad inode e quanti “slot” rimangono liberi per l’allocazione di nuovi file. La dimensione in byte della block bitmap, per esempio, può essere calcolata nel seguente modo:
(blochi_per_gruppo/8)/dimensione_blocco arrotondando per eccesso entrambe le divisioni [spec].
In Ext3 le directory sono gestite come Linked Lists4 (liste collegate) di lunghezza variabile: ogni elemento della lista contiene l’inode number, la dimensione dell’elemento stesso, la lunghezza del nome ed il nome del file stesso (in Linux sia file che directory vengono trattati dal sistema operativo come files). Utilizzando questo meccanismo che consente elementi di lista di lunghezza variabile è possibile utilizzare lunghi nomi di file senza sprecare spazio nelle directory.
La struttura di un elemento presente in una directory (directory entry) è mostrata nella tabella 3.1:
4 Per una spiegazione esaustiva sul significato di linked list si vada all’appendice C.
Inode number Dimensione elemento Lunghezza del nome Nome del file
Tabella 3.1: Struttura di una directory entry.
Come esempio, la tabella 3.2 mostrerà la struttura di un direttorio contenente i files:
file1, long_file_name, e f2.
i1 16 05 file1
i2 40 14 long_file_name i3 12 02 f2
Tabella 3.2: esempio di directory Ext3.
La dimensione dei blocchi di memoria non è fissa, ma può essere modificata dall’amministratore di sistema utilizzando l’utility tune2fs, che permette di sceglierne la dimensione (tipicamente 1024, 2048 o 4096 bytes). L’utilizzo di grandi blocchi di memoria, come già in precedenza affermato, velocizza le operazioni di I/O ma allo stesso tempo comporta uno spreco di spazio su disco, in quanto questo file system non permette che uno stesso blocco sia utilizzato da più file, lasciando così l’ultimo blocco assegnato ad ogni file statisticamente mezzo vuoto.
3.2 Gestione delle directory
Il file system Ext3 eredita dal suo predecessore una meccanismo di gestione dei direttori basato sulle linked lists, come spiegato nel paragrafo precedente. Un sistema di questo tipo, tuttavia, non consente di utilizzare tutti gli algoritmi di bilanciamento e ottimizzazione della ricerca che sarebbero possibili utilizzando una struttura ad albero, ed allo stesso tempo non rende il file system immune da perdite di dati dovute alla possibile corruzione di nodi vicini alla radice, che potrebbero rendere irraggiungibile buona parte dei files presenti in memoria. Per ovviare a questi problemi è stato sviluppato, e reso disponibile a partire dalla release 2.4 del kernel Linux, un sistema di organizzazione ad albero bilanciato per i direttori chiamato “HTree” [HTree].
Questo sistema identifica ogni blocco con una hash key di 32 bit, ed ogni chiave fa riferimento ad una serie d’oggetti immagazzinati in una foglia dell’albero. Il fatto che i
riferimenti interni, che sono anch’essi memorizzati all’interno di blocchi di memoria, siano di lunghezza fissa di 8 byte, garantisce un elevato fanout per l’albero (utilizzando blocchi di memoria di 4KB possono essere memorizzati più di 500 riferimenti per blocco); e i due livelli di nodi, di cui è al massimo composto l’albero, sono sufficienti per poter memorizzare più di 16 milioni di file che hanno una lunghezza del nome di 52 caratteri.
Questo sistema è stato studiato in modo da garantire una perfetta compatibilità all’indietro, e funziona in modo parallelo al sistema d’indirizzamento lineare basato sulle liste dati; il sistema, infatti, utilizza la struttura HTree soltanto per ordinare ed avere la possibilità di fare ricerche veloci all’interno dell’albero, ma per eseguire le operazioni sui files esso usa il tradizionale riferimento ad inodes e blocchi di memoria.
Per rendere tutto ciò possibile, le foglie dell’albero sono state progettate in modo da essere identiche ai blocchi contenenti le directory utilizzate nel vecchio meccanismo, ed i blocchi interni contenenti strutture dati di 8 byte appaiono ai kernel che non supportano gli HTree come directory entries cancellati.
Un altro vantaggio dovuto a quest’attenzione alla compatibilità viene dal fatto che in questo modo la struttura ad albero diviene estremamente robusta: nel caso in cui uno dei nodi interni dovesse essere corrotto, il kernel potrebbe rintracciare i vari files e le directory utilizzando il sistema tradizionale basato sulle linked lists.
L’utilizzo di questo algoritmo d’ordinamento ha portato ad un aumento di prestazioni, nell’accesso a directory contenenti un gran numero di files, fino a 50 o 100 volte rispetto ai tempi impiegati dalle precedenti versioni che non utilizzano questo meccanismo; e l’unico svantaggio viene notato quando si usa il comando readdir(), che ritorna i file presenti in un direttorio ordinati secondo la propria hash key e provoca una lettura degli inode contenenti i dati dei file in ordine del tutto casuale, senza ottimizzare quindi i salti delle testine del disco rigido tra un gruppo di blocchi e l’altro.
Una soluzione a questo problema che è tuttora allo studio è quella di associare direttamente ad ogni inode la relativa hash key, e raggruppare quindi gli inodes in memoria per chiave; più nello specifico, la soluzione a cui si sta lavorando, è quella di allocare ogni nuovo inode all’interno di un possibile range di inode liberi d’ampiezza dipendente dalla dimensione del direttorio in cui il file si trova, e quindi scegliere un inode libero per l’allocazione in modo dipendente dalla hash key del file.
3.3 Attributi estesi ed ACL
In questa sezione si discuterà di come sono implementate le access control lists in Linux, ed in particolare sul file system ext3 [POSIX-ACL].
Per via di altre estensioni del kernel che traggono vantaggio dal poter associare parti di informazioni ai files, Linux e la maggior parte degli altri sistemi UNIX- like implementa le ACL sottoforma di attributi estesi (Extended Attributes, o più brevemente EAs) dei files.
Un attributo esteso è un pezzo d’informazione relativa ad un file (esterna però al file, non facente parte del suo contenuto, che è utilizzato dai processi utente) che non viene memorizzata all’interno del relativo descrittore, ma è allocata in parti ben definite del disco; più precisamente esso è una coppia nome- valore associata permanentemente ad un file, simile ad una variabile ambiente di un processo.
Per rendere disponibili i vantaggi delle ACL ai processi utente, il sistema operativo mette a disposizione delle system calls specifiche per gli attributi estesi, che fungono quindi da interfaccia tra kernel e processi.
La scelta di progetto più facile e lungimirante per implementare gli attributi estesi, è quella di associare ad ogni file una directory nascosta contenente un file per ogni attributo relativo (file che ovviamente contiene il valore dell’attributo), ma una soluzione di questo tipo comporterebbe un grande spreco di spazio su disco per l’allocazione di nuovi blocchi per file e direttori, oltre che una perdita di tempo dovuta alle operazioni di accesso ad ogni singolo file-attributo; ecco perché la maggior parte dei sistemi operativi utilizza metodi implementativi differenti.
Come definito nel kernel Linux, ogni inode contiene un campo chiamato i_file_acl; se questo campo non è uguale a zero, esso contiene allora il numero del blocco di memoria in cui sono memorizzati gli attributi estesi associati all’inode: attributi che indipendentemente dal tipo sono composti da un nome (che identifica l’attributo stesso) ed un valore associato, inoltre tutti gli attributi estesi associati ad uno stesso inode devono essere memorizzati all’interno dello stesso blocco. La figura 3.2 mostra in che modo il sistema associa agli inode gli attributi estesi: diversi inode possono condividere lo stesso blocco attributi (se hanno uguali attributi), ma i blocchi contenenti gli attributi estesi non si trovano necessariamente nello stesso gruppo di blocchi in cui è memorizzato il relativo inode.
I1: i_file_acl= 216 I2: i_file_acl=218 I3: i_file_acl=216 I4 : i_file_acl=NULL I5:….
Inode Table
Data Blocks
Blocco dati 216, che memorizza
attributi estesi
Data Block 217
Blocco dati 218, che memorizza
attributi estesi
Data Blocks
Figura 3.2: Uso di i_file_acl per memorizzare il riferimento al blocco contenente gli attributi.
Per ottimizzare l’utilizzo dello spazio su disco, il file system consente a diversi inode che hanno identici attributi estesi di condividere lo stesso blocco attributi su disco; il numero di inode che fanno riferimento ad un unico blocco è controllato attraverso un contatore di riferimenti ad inode presente nel blocco stesso. La condivisione dei blocchi attributi è implementata in modo trasparente rispetto all’utente: Ext3 tiene automaticamente traccia dei blocchi attributi recentemente aperti, ed inoltre utilizza una tabella che tiene conto dei blocchi ordinandoli per numero e per riassunto (checksum) dei contenuti (tabella che è implementata come una hash table di doppie linked lists, per numero e contenuti). Un singolo blocco attributi può essere condiviso da un numero massimo stabilito di 1024 inodes, questo per limitare il danno causato in caso di danneggiamento del singolo blocco, che si ripercuoterebbe su di un numero limitato di files. Quando vengono modificati gli attributi di un file che utilizza la condivisione del blocco, viene utilizzato un meccanismo di copy-on-write per allocare un nuovo blocco attributi da associare al file in questione; questo salvo che i nuovi attributi del file non corrispondano a quelli presenti su di un blocco già esistente che può essere condiviso.
L’implementazione corrente di questi attributi richiede che tutti quelli associati ad uno stesso file siano contenuti all’interno di un unico blocco, cosa che va ad influenzare la dimensione di un singolo attributo, visto che la dimensione dei blocchi, in ext3 può essere di 1, 2, o 4KB.
Il grosso limite di questo tipo di implementazioni viene alla luce nelle partizioni in cui tutti i file tendono ad avere set differenti di attributi, all’interno delle quali si ha un notevole spreco di spazio su disco, sia per i blocchi in sè che per memorizzare la tabella riassuntiva utilizzata dal sistema. Inoltre la memorizzazione degli attributi di un nuovo file, in un caso di questo tipo, comporterebbe un grosso carico di lavoro eseguito dal sistema per scorrere l’intera hash table per cercare un blocco corrispondente e,
