Filesystem

Un filesystem è orientato ai record quando contiene dei file composti da molteplici record, ovvero più insiemi di campi ognuno dei quali è composto da un gruppo di caratteri.

Si dice orientato ai byte invece, quando i file sono una sequenza di singoli byte e non di record.

Il compito del filesystem è di organizzare e gestire il contenuto e lo spazio della memoria secondaria, rendendolo indipendente dal dispositivo hardware e prevenendo la perdita delle informazioni.

Nel disco salva anche copie ridondanti non modificabili dagli utenti del super blocco, contenente metadati, cioè informazioni critiche come la posizione della radice e dei blocchi liberi.

I tempi del disco sono riducibili prevedendo i blocchi da leggere, sfruttando la cache e deframmentandolo.

File

Il filesystem permette un accesso ai file in modo:

• Sequenziale, se i record sono letti dall'inizio alla fine del file
• Causale (o diretto), se ammette salti nella lettura del file

Ogni record fisico può contenere più record logici, cioè dei dati trattati come record dal software. Quando ne contiene molteplici i record sono detti bloccati, altrimenti vengono detti non bloccati (o sbloccati).

Directory

Le directory sono dei file contenenti una lista di nomi e posizioni di altri file nel filesystem.

Ogni nome può essere salvato a lunghezza fissa come una sequenza di caratteri, oppure variabile salvando sia la lunghezza che il nome o salvando l'indirizzo a lunghezza fissa del nome a lunghezza variabile sull'heap.

Possono avere ruoli diversi a seconda del filesystem:

• Piatto: contiene una sola directory, ogni file ha un nome distinto e la ricerca dei file è lineare
• Gerarchico: contiene una radice per la directory principale che punta alle varie directory contenenti file

Link

Nelle directory si possono inoltre creare dei link, che fanno da riferimento a file in locazioni diverse:

• Soft: contiene il percorso del file e perde il suo riferimento quando viene spostato
• Hard: punta allo stesso blocco fisico del file e perde il riferimento se viene riallocato

Mount

Fare il mount di un altro filesystem permette di accederci da un'unica radice su una directory che fa da punto di mount, le cui informazioni vengono salvate dentro tabelle di mount del filesystem.

Supportano i soft link tra dispositivi, ma non gli hard link dato che i dati dovrebbero essere altrimenti copiati.

Allocazione

Come per la memoria principale, si presenta il problema dell'allocazione dello spazio, che può essere:

• Contigua

  Alloca i dati su indirizzi contigui, disponendo i record adiacenti tra loro.

  Questo conviene su unità read-only come i CD-R, ma peggiora le prestazioni se il file cambia di dimensioni e aumenta la frammentazione esterna.

• Con liste collegate

  Alloca il file in maniera non contigua attraverso una linked list di settori, ognuno dei quali punta al successivo e l'indirizzo del primo viene salvato all'interno della directory.

  Durante l'allocazione del primo blocco, il sistema sceglie un'area di memoria contigua.

  Utilizzare grandi blocchi permette di ridurre l'I/O ma al costo di aumentare la frammentazione interna, mentre blocchi piccoli sprecano più spazio per la grande quantità di puntatori salvati.

  Per trovare un record però, la ricerca deve partire dal primo blocco, e può essere molto lenta se i blocchi sono sparsi nell'unità perchè vanno trovati e copiati in memoria principale.

• Tabellare

  Come FAT32, salva i riferimenti ai blocchi in una tabella globale a parte, assieme all'indice del blocco successivo. L'indice del primo blocco di ogni file sarà poi salvato nella directory in cui risiede.

  Questo evita di dover caricare ogni blocco in memoria per la ricerca, migliorando i tempi di accesso. Nel caso contenga molti blocchi però, può diventare molto grande e ridurre le prestazioni del filesystem.

• Indicizzata

  Come l'allocazione tabellare, ma ogni file ha la sua tabella chiamata blocco indice che oltre ai blocchi contiene anche il puntatore ad una possibile tabella successiva.

  Su Linux i blocchi indice sono detti inode.

Gestione spazio

Normalmente la dimensione dei blocchi è costante, ma più sono grandi meno tempo sarà occupato a passare ai successivi, al costo di maggior frammentazione interna e di conseguenza possibile spreco di spazio.

Il disco può anche essere suddiviso in quote assegnate ai diversi utenti, limitando i file memorizzabili.

Spazio libero

Lo spazio libero può essere gestito usando una lista libera, cioè una linked list contenente i blocchi liberi che verranno allocati partendo dalla testa e liberati aggiungendoli in coda.

Questo porta ad un overhead molto basso, ma per evitare di allocare blocchi sparsi andrà forzato il filesystem ad effettuare una ricerca di blocchi vicini dentro la lista.

Un'alternativa è usare una bitmap di ogni blocco, in cui i singoli bit indicano se il blocco è libero o occupato. Peggiora però l'overhead associato alla ricerca di blocchi liberi.

Backup

Una tecnica per salvare copie ridondanti di dati è l'esecuzione di backup periodici, che possono essere:

• Fisici: duplicano i dati bit per bit, semplificando il processo ma riducendo la portabilità
• Logici: memorizzano i dati e la loro struttura nel filesystem, spesso comprimendoli

Un esempio di backup logico sono i backup incrementali, che copiano i file modificati dall'ultimo backup.

Integrità

Una tecnica dei filesystem per mantenere la consistenza dei dati è effettuare modifiche con le transazioni, cioè un gruppo atomico di più operazioni di cui viene fatto il rollback in caso di errori.

Sono realizzati scrivendo lo stato delle operazioni in un file di log, e prendendo nota del completamento della transazione. Il rollback avverrà quindi all'ultimo checkpoint, cioè all'ultimo stato consistente del disco.

Inoltre alcuni filesystem implementano la paginazione shadow, che effettua le operazioni su un blocco libero, per poi copiarle sul blocco originale alla fine della transazione.

Un esempio sono i log structured filesystem come NTFS e ext3, che rendono l'intero disco il file di log e scrivono i nuovi dati in sequenza nello spazio libero, causando però scarse prestazioni in lettura.

La ricerca sull'intero disco è evitabile salvando le posizioni dei file nella cache o dedicando un log ai metadati.

Inoltre il filesystem, essendo frammentato, dovrà compattare i dati alla fine del file log per ricavare spazio.

Controllo accessi

Un altro compito è quello di proteggere i dati dagli utenti, attraverso privilegi come Read, Write e Execute. Nel filesystem, l'insieme dei privilegi e il relativo file è detto dominio di protezione.

La gestione dei vari domini avviene quindi con meccanismi come:

• Access control matrix

  Salva i privilegi in una matrice contenente gli utenti sulle righe e i file sulle colonne.

  Può diventare inefficiente con l'aumento dei file e degli utenti, ed è critico mantenerla protetta.

• Access control list

  Salva i privilegi all'interno di liste di utenti (per ogni file), oppure liste di file (per ogni utente).

  Risparmia spazio rispetto alla matrice perchè non possiede elementi vuoti, ma rallenta la ricerca.

• Capability list

  Salva nella lista dei capability, cioè identificatori che permettono l'accesso agli utenti che li possiedono. Ogni capability sarà quindi creato per un oggetto e assegnato ai vari utenti.