FAT Cluster Chains

FAT file system stores the data in units called Cluster.

• The size of the clusters changes depending on the FAT configurations.

One of the core responsibilities of the FAT file system is to manage the cluster allocation states. The FAT file system uses a File Allocation Table to keep track of the state of the clusters.

The FAT file system uses a linked list-like data structure to keep track of file-associated clusters.

• The structure is known as a Cluster Chain.

A Cluster Chain is a linked list of clusters. The head of the linked list or the starting cluster of a cluster chain is stored in file metadata. The remaining elements of the cluster chain can only be found by using the file allocation table structure.

The file allocation table format lets us easily find the next cluster in a cluster chain. As shown in the following table, an entry in the FAT table has a value that denotes the next cluster of the cluster.

Index	Value
<Cluster Number>	<Next Cluster in Chain>

We trace a FAT cluster chain by starting from the starting cluster until we find an EOF value as the next cluster number.

• The next cluster value is 0, it means the cluster has not been allocated.
• The next cluster value EOF indicates that the cluster has no next cluster which means it is the last cluster in its cluster chain.
• The next cluster value of non-zero and non-EOF value indicates a valid next cluster in a cluster chain.

Cluster Chain By Example

Let’s see an example for a FAT cluster chain. In this example, there are 3 clusters allocated. The starting cluster number is 40. The next cluster of the cluster chain can only be found by traversing the FAT table.

Index <Cluster Number>	Value <Next Cluster in Chain>
40	41
41	42
42	EOF

When we trace the cluster chain as follows:

1. Read cluster 40 FAT table value.
   • The index 40 of the FAT table is read.
   • The value of cluster 40 is found as 41.
   • Therefore, the next cluster in the chain is 41.
2. Read cluster 41 FAT table value.
   • The index 41 of the FAT table is read.
   • The value of cluster 41 is found as 42.
   • Therefore, the next cluster in the chain is 42.
3. Read cluster 42 FAT table value.
   • The index 42 of the FAT table is read.
   • The value of cluster 42 is found as EOF.
   • Therefore, cluster 42 is the last cluster in the chain.