# File Allocation Table

La File Allocation Table, in sigla FAT, è un file system sviluppato inizialmente da IBM e Digital Equipment Corporation prima, e poi da Bill Gates e Marc McDonald per il MS-DOS. È il file system primario per diversi sistemi operativi e Microsoft Windows fino alla versione Windows Me. Windows NT e le successive versioni hanno introdotto l'NTFS e mantenuto la compatibilità con la FAT così come molti altri sistemi operativi moderni.

## Storia

La FAT inizialmente debutta sul sistema CP/M della Digital e IBM per i floppy disk; l'idea fu presa da come la versione stand-alone di Microsoft BASIC utilizzava i floppy disk fino al 1976 copiata dalla IBM. Nel maggio del 1979, un anno prima di decidere di scrivere il QDOS, Tim Paterson aiutò Bob O'Rear a portare il loro linguaggio nella nuova architettura 8086. La FAT poi viene utilizzata nell'agosto del 1980 con la prima versione di QDOS (derivazione del modulo DOS del CP/M) di Tim Paterson, il predecessore del PC-DOS e di MS-DOS della Microsoft, anzi, il solo supporto FAT fu proprio la principale differenza tra il QDOS e il CP/M, di cui il QDOS era un clone.
Con l'annuncio della Microsoft del cessato supporto a MS-DOS nel 1994 e l'introduzione del NTFS in tutti i sistemi operativi prodotti, è improbabile che venga sviluppata una nuova versione del FAT. Vista però l'estrema diffusione del FAT nei floppy disk, nelle memorie flash o nei drive USB ed essendo molto limitato il supporto del NTFS nei sistemi operativi non Microsoft, probabilmente questo file system verrà utilizzato ancora a lungo. Con la commercializzazione di Windows Vista SP1 e Windows CE 6.0, la Microsoft presenta l'exFAT detta anche FAT64 utilizzato prevalentemente per memorie flash.

### Cronologia delle versioni

Esistono varie versioni di questo file system, in base a quanti bit sono allocati per numerare i cluster del disco: FAT12, FAT16, FAT32. Esiste anche una versione del FAT16 detta VFAT, che è virtuale cioè non registrato fisicamente sull'hard disk, ma gestito da un software specifico.

#### FAT12

La prima versione del FAT fu la FAT12, un file system per floppy disk i cui indirizzi per i cluster erano appunto a 12 bit (lunghezza non standard, quindi manipolare il FAT era un po' più complicato) e per questo poteva gestire dischi grandi al massimo 32 MiB. Ma visto che i dischi dell'epoca erano grandi al massimo 160 KB questi limiti non vennero mai sentiti. La prima versione del FAT12 non supportava le directory ad albero, che vennero introdotte con l'MS-DOS 2.0 e i dischetti da 360KB.
Nel 1984 la IBM mise sul mercato i PC AT, con un hard disk di 20 MB. In parallelo Microsoft introdusse l'MS-DOS 3.0 ed una versione del FAT con indirizzi per i cluster a 16 bit, permettendo fino a 65.536 cluster e portando il limite di grandezza teorico a 512MB. Comunque il numero massimo di settori e la dimensione massima (di una partizione, non più di un disco) non cambiò e rimase di 32 MB.

#### FAT16

Nel 1987 arrivò il formato che ora viene chiamato FAT16: introdotti dal Compaq DOS 3.31, nel 1988 i miglioramenti arrivarono anche con l'MS-DOS 4.0. La dimensione delle partizione venne limitata dalla dimensione di 8-bit dei settori per cluster, che potevano avere fino a 64 settori, dando cluster di 32 KB con la solita dimensione di 512 byte per settore, fissando il limite "definitivo" per una partizione FAT16 a 2 GB. Più tardi, Windows NT aumentò la dimensione massima dei cluster a 64K (considerando il contatore come unsigned, senza segno), ma il risultato non era compatibile con le altre implementazioni del FAT del tempo, e cluster di tale grandezza portavano a sprecare molto spazio per la frammentazione interna.

#### VFAT

Per supportare i nomi dei file lunghi, venne introdotto in Windows 95 il VFAT (Virtual FAT), che prende il nome dal driver della periferica. L'implementazione modificava il modo in cui il file system organizzava i contenuti di una directory. L'uso delle specifiche VFAT permette di usare sia nomi lunghi (fino a 255 caratteri UTF-16) che nomi brevi (8+3 caratteri) in maniera trasparente alle diverse versioni di Windows.

#### FAT32

Per superare i limiti sulla dimensione dei volumi imposta dal FAT16, Microsoft decise di creare un nuovo FAT chiamato FAT32, con numeri per i cluster da 32 bit, anche se in realtà ne vengono utilizzati solo 28.
In teoria questo dovrebbe permettere 268435456 (2$^{28}$) cluster, cioè una dimensione totale dell'ordine dei 2 TiB con cluster di 8 KiB, ma a causa delle limitazioni da alcune versioni dell'utility scandisk non è permesso al FAT di superare i 4177920 (< 2$^{22}$) cluster, riducendo la dimensione massima a 124,55 gigabyte. Le utility di formattazione e partizionamento di Windows 2000 e XP hanno un limite di 32 GB per le partizioni FAT32, ma è un limite arbitrario: avviando un computer con un floppy disc di boot basato su sistema operativo FAT32 (es.: Windows 98) è infatti possibile partizionare in FAT32 oltre i 32 gigabyte, inoltre utility di terze parti possono tranquillamente creare e gestire partizioni FAT32 fino a 1 TB; esistono in commercio hard disk esterni di 1 TB formattati in FAT32. Con il FAT32 la dimensione del singolo file non può essere superiore ai 4 GB. Questo perché esiste una voce a 32 bit che indica la grandezza del file in byte.
L'ultima versione di Microsoft Windows che usa questo file system è Windows Me (Millennium Edition). Le versioni successive lo supportano in aggiunta al file system NTFS, più che altro per la formattazione di pendrive, schede di memoria e altri dispositivi mobili.

#### ExFAT

ExFAT è un file system introdotto da Microsoft nel 2006 con Windows Embedded CE 6.0, pensato appositamente per memorie flash e, in generale, per dispositivi di archiviazione dalle dimensioni fino a 16 exabytes. Subito dopo, nel 2008, il supporto di Microsoft alla exFAT è stato incluso nel Service Pack 1 di Windows Vista e in Windows XP SP2 ed SP3, grazie a uno specifico aggiornamento (KB955704-x86-ENU).

## Descrizione

La FAT in sé mantiene la traccia delle aree del disco disponibili e di quelle già usate dai file e dalle directory: la differenza fra FAT12, FAT16 e FAT32 consiste appunto in quanti bit sono allocati per numerare i cluster del disco. Con 12 bit, il file system può indirizzare al massimo 2$^{12}$ = 4096 cluster, mentre con 32 bit si possono gestire 2$^{32}$ = 4.294.967.296 cluster; l'aumento del numero di bit di indirizzo dei cluster si è reso necessario per gestire unità a disco sempre più grandi e capienti.
La FAT è relativamente semplice ed è supportata da moltissimi sistemi operativi dato che è Open Source. Queste caratteristiche la rendono adatta ad esempio per i Floppy Disk e le Memory Card. Può anche essere utilizzata per condividere dati tra due sistemi operativi diversi e molto altro. Il più grande problema del File System FAT della Microsoft è la frammentazione. Quando i file vengono eliminati, creati o spostati, le loro varie parti si disperdono sull'unità, rallentandone progressivamente la lettura e la scrittura. Una soluzione a questo inconveniente è la deframmentazione, un processo che riordina i file sull'unità. Questa operazione può durare anche diverse ore e deve essere eseguita periodicamente per mantenere le prestazioni dell'unità.

### Supporto nei sistemi operativi

Data la grande diffusione del FAT file system, praticamente tutti i sistemi operativi non Microsoft hanno supportato sia il FAT16, che il VFAT ed infine il FAT32 (questo con meno limitazioni di quelle previste ufficialmente).
Con le prime distribuzioni GNU/Linux venne creato un file system chiamato UMSDOS, un FAT con gli attributi Unix (permessi, proprietario ecc.), che altrimenti non sono supportati in FAT; il suo sviluppo si fermò con l'arrivo del VFAT, ma è tuttora supportato. Il sistema operativo macOS può utilizzare il FAT per i volumi non avviabili oppure per il volume di Bootcamp nei MacIntel.

## Struttura

Il file system FAT è un file system classificato tra quelli con allocazione concatenata. Una partizione FAT è strutturata in quattro sezioni diverse:
| | Area riservata | Area riservata | Area riservata | FAT | FAT | Root directory (solo FAT12/16) | Regione dati |
| | Settore di avvio | Informazioni FS (solo FAT32) | Riservati (opzionale) | FAT #1 | FAT #2 | Root directory (solo FAT12/16) | Regione dati |
| Dimensione in settori | Variabile | Variabile | Variabile | (# FAT)*(settori per FAT) | (# FAT)*(settori per FAT) | 32 * (# voci root) / bytes per settore | (# cluster) * (settori per cluster) |
* I settori riservati, che si trovano proprio all'inizio. Il primo settore riservato (settore zero) è il settore di avvio, seguito dal BIOS Parameter Block (con alcune informazioni di base del FS, in particolare il suo tipo, e puntatori alla posizione delle altre sezioni). Contiene di solito il codice del boot loader del sistema operativo. La dimensione dei settori riservati è indicata in un campo all'interno del settore di avvio. Nel FAT32 le informazioni si trovano nel settore 1, mentre nel settore 6 vi è una copia di backup del settore di avvio.
* La Regione FAT: Contiene almeno due copie della FAT (per motivi di sicurezza). Rappresentano la mappa della regione dati.
* La Regione della ROOT directory: è una tabella che memorizza le cartelle e i file presenti nella directory di root. È presente solo nella FAT12 e nella FAT16 ed impone una dimensione massima prefissata per la root; nella FAT32 ciò è fatto direttamente nella regione dati, eliminando così il vincolo dimensionale sulla root.
* L'area dati: è dove file e cartelle sono realmente memorizzati e occupa la maggior parte della partizione
FAT utilizza il formato little endian per le voci nell'intestazione e la/le FAT.

### Settore di avvio

È importante notare che il primo settore su un dispositivo non necessariamente è il settore di avvio. Per i dispositivi partizionati (per es. gli hard disk), il primo settore è detto Master Boot Record (abbreviato: MBR); nei dispositivi non partizionati (come i floppy disk) il primo settore è il Volume Boot Record (abbreviato: VBR). Tutte le versioni FAT hanno in comune i primi 36 bytes:
| Byte Offset | Lunghezza (byte) | Descrizione |
| 0x00 | 3 | Salta istruzione. Questa istruzione verrà eseguita e salterà oltre il resto dell'intestazione (non-eseguibile) se la partizione è avviabile (cfr. VBR). Se il salto è pari a due byte l'istruzione JMP vicina è seguita da un'istruzione NOP |
| 0x03 | 8 | Nome OEM (riempito da spazi). Determina come il disco è stato formattato. MS-DOS controlla questo campo per determinare quali altre parti del record di avvio devono essere valutate. I valori comuni sono IBM 3.3" (con due spazi intermedi), MSDOS5.0, MSWIN4.1 e mkdosfs. |
| 0x0B | 2 | Bytes per settore. Solitamente il valore è 512. È l'inizio del BIOS Parameter Block. |
| 0x0D | 1 | Settori per cluster. I valori ammessi sono potenze di due da 1 a 128. Tuttavia, il numero totale di byte per cluster dev'essere inferiore a 32KiB. |
| 0x0E | 2 | Numero dei settori riservati. È il numero di settori prima della prima FAT nell'immagine del file system. Solitamente vale 1 per FAT12/16, 32 per FAT32. |
| 0x10 | 1 | Numero di tabelle di allocazione dei file. Solitamente vale due. |
| 0x11 | 2 | Numero massimo di voci nella directory root. Per il FAT12/16 questo valore dev'essere multiplo della dimensione di un settore. Per il FAT32 vale 0. |
| 0x13 | 2 | Settori totali. Se vale 0 allora si fa riferimento ai 4 byte all'offset 0x20. |
| 0x15 | 1 | Tipo di descrittore. Tipicamente vale 0xF8 per un hard disk. |
| 0x16 | 2 | Settori per FAT (per FAT12/16) |
| 0x18 | 2 | Settori per traccia. |
| 0x1A | 2 | Numero di testine. |
| 0x1C | 4 | Settori nascosti. |
| 0x20 | 4 | Totale settori. Se minore di 65.535 vale il contenuto all'offset 0x13. |

### Settore informazioni FS

Introdotto con la FAT32 per accelerare i tempi di accesso di alcune operazioni (i.e. la quantità di spazio libero), occupa generalmente il settore 1, nel record di avvio 0x30. Ha dimensione pari a 512 byte.

### Tabella dei files

Una partizione è divisa in cluster contigui dalle dimensioni variabili tra 2 e 32 KB. Ogni file è strutturato sul disco come una lista concatenata di cluster non necessariamente contigui: questa è la ragione principale per cui si parla di frammentazione del disco nei filesystem FAT.
Ogni record della FAT è composto da 5 campi:
* il numero del cluster successivo
* una speciale EOC (end of clusterchain), che indica la fine di una catena
* cluster danneggiato
* cluster riservato
* cluster libero
I valori possibili sono:
| FAT12 | FAT16 | FAT32 | Descrizione |
| 0x000 | 0x0000 | 0x00000000 | Cluster libero |
| 0x001 | 0x0001 | 0x00000001 | Valore riservato |
| 0x002-0xFEF | 0x0002-0xFFEF | 0x00000002-0x0FFFFFEF | Cluster dati |
| 0xFF0-0xFF6 | 0xFFF0-0xFFF6 | 0x0FFFFFF0-0x0FFFFFF6 | Valori riservati |
| 0xFF7 | 0xFFF7 | 0x0FFFFFF7 | Cluster danneggiato |
| 0xFF8-0xFFF | 0xFFF8-0xFFFF | 0x0FFFFFF8-0x0FFFFFFF | Ultimo cluster |
Da notare che nella FAT32 sono disponibili solo 28 dei 32 bit disponibili; il bit più significativo è riservato. La regione dati parte dal cluster #2; le altre voci sono riservate alla FAT ed a utilizzo interno.

### Tabella delle directory

È un tipo speciale di file che rappresenta una directory; ogni file o cartella memorizzata all'interno è rappresentato da una voce nella tabella secondo il seguente schema:
| Byte offset | Lunghezza | Descrizione |
| 0x00 | 8 | Nome del file (riempito da spazi). Il primo byte se vale 0 significa che la voce è disponibile, il valore 0x05 è riservato per la codifica kanji, il valore 0x2E indica il valore '.' o '..' |
| 0x08 | 3 | Estensione del file (riempita con spazi) |
| 0x0B | 1 | Attributi del file. Segue il seguente schema: BitMascheraDescrizione 00x01Sola lettura 10x02Nascosto 20x04Di sistema 30x08Etichetta volume 40x10Sottodirectory 50x20Archivio 60x40Device (solo per uso interno, in realtà non si trova sul disco) 70x80Inutilizzato |
| 0x0C | 1 | Riservato, generalmente vale 0 (tranne in Windows NT e successivi) |
| 0x0D | 1 | Ora di creazione. Risoluzione: 10ms, valori da 0 a 199. |
| 0x0E | 2 | Ora di creazione in ore, minuti e secondi. Le ore sono codificate nei bit 15-11, i minuti nei bit 10-5, i secondi nei bit 4-0 |
| 0x10 | 2 | Data di creazione. L'anno è codificato nei bit 15-9, il mese nei bit 8-5, i giorni nei bit 4-0. L'anno è calcolato a partire dal 1980. |
| 0x12 | 2 | Ultima data di accesso |
| 0x14 | 2 | EA-Index in OS/2 e NT per FAT12/16; in FAT32 sono riportati i 2 byte alti del primo cluster |
| 0x16 | 2 | Ora ultima modifica |
| 0x18 | 2 | Data ultima modifica |
| 0x1A | 2 | Puntatore al primo cluster in FAT12/16; in FAT32 sono riportati i 2 byte bassi del primo cluster. |
| 0x1C | 4 | Dimensione del file in byte |
Nel caso in cui si tratta di un file di tipo etichetta di volume o directory padre (..) i 6 byte all'offset 0x1A sono impostati a zero.