Introduction to FAT
FAT file system was first implemented in the year 197? by a student Bill
Gates. Then it grew into the most used file system among IBM PC computers.
I will explain the FAT idea in this paper. FAT implementations will be
described in later documents.
In FAT file system, storage device is of a fixed size. It is logically
divided into chunks of data of equal size called clusters. Any file
takes up a natural number of clusters. Disk map, called File Allocation
Table (FAT), is located at a known position on disk. FAT is an array
of the entries of equal size. Number of entries is equal to number of clusters
on disk, so there exists a unique relationship between FAT entries and
clusters. FAT entry is one of the following:
||End of File
||Next Cluster In Chain
Free clusters are those free for allocation. The cluster marked
as EOF (End Of File) is the last cluster for the file chain. Although
several values may serve as EOF, only -1 is used by DOS. Bad
clusters are physically damaged clusters. They cannot contain any data.
Reserved clusters are reserved for DOS file system usage. They should
not be used by anyone but their creator. In every FAT, the very first entry
If FAT entry is none of the above values, it should contain the number
of the next cluster for this file. As you see, FAT is just a
variation of a linked list.
Another FAT file system concept is directory, or folder.
Directory is a file that contains file descriptions. File description consists
of file name, date, flags, size, and the first cluster in the file's
cluster chain. Directory itself is stored just like a normal file.
It also has a FAT chain. Directory entry may point to a nested directory,
which leads to directory hierarchy. But where does this all start? Most
FAT variations expect the first-level, or root, directory at a certain
fixed location on disk.
To make things clear, let us read 512 bytes of the file "C:\DOC\INTEL\INTEL386.TXT"
starting from offset 2048 relative to the beginning of this file.
Filename should first be split into meaningful tokens. They are "C:",
"DOC", "INTEL", and "INTEL386.TXT" in this order.
The first token tells us to select the first primary partition on the first
hard drive for reading. "DOC" is name of the directory that is
in the root directory of "C:". Since we know where the root directory
is on disk (and root directory size too), let us look through it and find
the entry named "DOC". As I said earlier, one of the fields of
this entry is FirstCluster. Now we know where the FAT chain for
the directory "DOC" starts.
Let us read the first cluster of this chain. Now let us assign the
value of FirstCluster to NextCluster - you will later
understand why. We should now scan the cluster that we have read for the
entry with the name "INTEL". If we have not found it, let us read
the next cluster in the chain.
Hopefully, we have found the subdirectory "INTEL". We know the
first cluster of this subdirectory, so let us look for the entry "INTEL386.TXT"
in the same manner as we have just looked for subdirectory.
To do it, we look at the value at FAT[NextCluster]. If it is
EOF, there are no more clusters in the chain. If it contains any
other special value, FAT chain has been corrupted. Otherwise, it contains
the next cluster, so we write NextCluster=FAT[NextCluster]. Let
us read NextCluster into memory and scan it for "INTEL".
We repeat reading next cluster in the chain and scanning it for "INTEL"
until we either find it, or reach EOF or any other reserved value
in the FAT chain.
Now we should know FirstCluster of our file. Let's imagine
that cluster size for our disk is 1024 bytes. Thus, to reach offset
2048 we must skip two 1024-byte blocks, or two clusters.
You know how to do it, don't you? Hint: look through the FAT chain. Finally,
let's read our 512 bytes.
The example was intentionally oversimplified, but I hope, it showed
the idea. As I said, implementation will be discussed in later documents.
Limitations of FAT
If you carefully followed the example, you noticed that I cheated. I did
not check all possible error conditions, and some errors in FAT might have
caused troubles, up to infinite loops. Let us take a closer look at FAT
First of all, FAT system is terribly inefficient for large files. You
can imagine how many FAT entries I will have to scan to access some file
at offset 96 MB. Even if I have all FAT cached, time to look through the
chain in memory is not acceptable. This situation can be somewhat corrected
by keeping current position in FAT, but this will only help for sequential
Secondly, FAT may create high file fragmentation. Because today's storage
devices are slow to move heads across the disk surface, space for files
should be allocated carefully. This is especially seen under multitasking
systems, when many files are written to at the same time. So, when the
file is being expanded, it is wise to allocate a number of clusters for
it in advance.
Thirdly, FAT clustering eats off space. If cluster size is 8 KB, it
is reasonable to expect that each file will take up 4 KB more of disk space
than it actually needs. If there are 10,000 files on disk, 40 MB of space
is waisted. However, FAT32 increased the number of available clusters and
reasonably reduced cluster size.
Fourthy, FAT is very sensitive to errors. It is almost impossible to
restore the file whose chain was corrupted. Consider the following examples:
Correcting any of these problems will likely corrupt the file, but leaving
them uncorrected will sooner or later hang the system. FAT provides no
ways for insuring data integrity, compression, encryption, or any other
nice perversions. With FAT you cannot even detect that a file was corrupted
- forget about correction. Besides the problems that are related to the
FAT concept itself, there exists a large group of problems related to specific
FAT implementations. For example, earlier FAT systems expected much vital
data at fixed disk addresses, which made disks unusable because of corruption
of just a few sectors. FAT32 finally made root directory floating and gave
a choice of selecting the working copy of FAT, but File Allocation Tables
are still at fixed physical addresses. Besides, directory format of FAT,
especially of VFAT, is a mess. This mess is even hard to handle normally
- any error handling becomes nightmare.
The easiest to diagnose error is the chain that contains some reserved
value other from EOF. Unless you are a special disk analyzer, the best
solution is to set the previous chain entry to EOF, thus truncating the
The variation of the above error is a valid FAT entry which points to the
physically defective or out of bounds cluster. File system should allocate
another cluster and plug it in the chain, replacing the invalid one. If
any data can be retrieved from the invalid cluster, it should be copied
to the new cluster.
A FAT chain that will throw my above algorithm into endless loop is a self-linked
chain. Consider the following chain: (2->3->4->8->7->4-..). The
last node points to the cluster already in chain. Some caution should be
taken to avoid looping infinitely in this case. Note that the following
simple sanity check will identify this kind of problem. Let us go through
the chain and compare each new entry with all entries that we have already
passed. If any of them equal, the chain is self-linked. But this check
is extremely expensive. If the chain contains n clusters, the order of
the number of comparisons is n squared. The situation can be improved by
allocating a bitmap, each bit representing a cluster, and setting bits
for the clusters we have passed. If the corresponding bit is already set,
then the chain is self-linked. The order of such a check is n, but it demands
extra memory. In any case, it is impractical to do sanity check after each
step through the chain. Norton Disk Editor did it after a fixed number
of steps, and this is the best technique I can suggest. After all, let
us hope that 4G file size limitation won't make it terribly slow. If this
is a file we are accessing (not a directory), sanity check may be performed
only when file size via the cluster chain becomes larger than file size
in directory (rounded up to the nearest multiple of cluster size). Once
the self-linked chain is identified, the entry that is pointing back should
be set to EOF, thus truncating the file.
Two or more FAT chains may be cross-linked. This happens when FAT chain
entries for different files point to the same cluster. In this case files
share the tail. It is even worse when a file is cross-linked with directory.
The latter case will have a fairly strange outcome, especially if the cross-linked
directory was cached. The order of checking for cross-linked files is at
best number of clusters on disk. This is achieved by using the bitmap for
all clusters, much like described above. But the problem is, you also have
to go through all directory structure to retrieve starting clusters for
all files. This makes checking for cross-linked files the privilege of
special analyzing programs. When this problem is detected, separate tails
are saved for each of the cross-linked files. There is no easy and quick
way of detecting cross-linked files, so if you have this problem, expect
weird results from accessing such files at the same time. The results are
usually unpredictable because of caching.
Next documents will describe FAT implementations in detail. I had a choice
of either describing them separately from each other, or merging together.
I will use the later method for several reasons. First of all, there are
many similarities between different types of FAT. Most structures are transferred
without any modifications or with minor extensions to next versions. Secondly,
implementing all types of FAT at once is probably more productive than
implementing them separately. And thirdly, I will try to build a base for
integrating different file systems under common protocols. This base will,
hopefully, save you much time for coding in future.
Author: Alex Verstak