The FAT filesystem

1. Introduction

This page doesn't give a full description of the FAT filesystem. It only gives some details you need to understand because they are used in some of my programs.
A good description of the FAT filesystem is given in The Indispensable PC Hardware Book.

2. The original FAT filesystem

There are several versions of the FAT filesystem. The one I describe in this chapter is the first one. Later versions include VFAT and FAT32. In this version, the files can only have a name of 8 bytes maximum plus an extension of 3 bytes maximum.

2.1. Logical sectors

From a physical viewpoint, the data on floppy disks or hard disks is organized in tracks, heads and sectors. You can find the data on the disk if you know the track, the head and the sector where it is. The number of tracks, heads and sectors is dependent on the type of disk. FAT hides theses differences between disks by using the concept of logical sector. The physical sectors are assigned a serial number. This serial number is the logical sector number corresponding to the physical sector.

2.1.1. Floppy disks

For floppy disks, the serial numbers of the physical sectors are assigned as follows :

• The first physical sector (track 0, head 0, sector 1) is assigned the logical sector number 0.
• The sectors on the same side and on the same track are now assigned the following numbers.
• When we have reached the end of the track, we continue with the sectors that are on the same track but under the next head. We assign a number to each of these sectors and when we have reached the end of the track under the current head, we proceed with the next head.
• When we have counted the sectors under the last head, we go to sector 1, head 0 of the next track and we apply the same procedure.

• To convert track, head and physical sector numbers into a logical sector number :
  lsn = S-1 + (T*nh + H) * spt
  
  
• To convert a logical sector number into a track, head and sector number :
  S = (lsn mod spt) + 1
H = (lsn / spt) mod nh
T = lsn / (spt*nh)

2.1.2. Hard disks

Hard disk can be divided in several partitions. Each partition is treated as an individual FAT volume. This introduces a minor change to the assignment of the logical sector numbers. The logical sector number 0 is not assigned to the first physical sector of the disk but to the first sector of the partition. The rules for assigning the next serial number remains unchanged.

2.2. General organization of a FAT disk

1. Boot sector and other reserved sectors
2. File Allocation Table (FAT)
3. One or more copies of the FAT
4. Root Directory
5. Data area for the files and the subdirectories

2.3. The boot sector

The boot sector is the name for the first sector of a floppy disk (head 0, track 0, sector 1) or for the first sector of a partition in the case of a hard disk. This location is accessible without knowing the exact type of the disk. This makes it appropriate for storing the disk parameters, which will then give enough information to access the other parts of the disk.

The following table shows the structure of the boot sector :

Jump instruction to the boot routine :
The first three bytes of the boot sector are either a near jump instruction (E9xxxxh) or a short jump followed by a NOP instruction EBxx90h. This instruction makes a jump to the boot code located somewhere in the boot sector. This instruction is necessary because the execution of a PC starts with the first bytes of the boot sector (see Boot sequence of a PC).

OEM name and number :
This field contain an identity that caracterizes the manufacturer and operating system.

Bytes per sector :
This word gives the number of bytes per sector. In the PC world, this seems to be always 512.

Sectors per cluster :
This byte gives the number of sectors per cluster. You'll learn what is a cluster later.

Reserved sectors :
This word gives the number of reserved sectors. The boot sector is included in this count. This value is usually 1. DOS disks always use 1 reserved sector : the boot sector. However, there doesn't seem to be any problem to handle other values.

Number of FATs :
This bytes gives the number of FATs (File Allocation Table). Only one FAT is needed but, as the data in it is very sensitive, one or more copies are written on the disk. The number of FATs is usually two.

Number of root directory entries :
This word gives the number of root directory entries available. The number of root directory entries is fixed. This explains why you can't have more than a certain amount of files and/or subdirectories in the root directory.

Number of logical sectors in the volume :
This word gives the number of logical sectors on the disk or in the partition in the case of a hard disk. The maximum number of sectors in the volume is therefore 65535*512 for a disk with 512 bytes per sector. This gives a maximum of about 33 Mb. This is not enough for the currently available hard disks. This is the reason why the new field Big number of logical sectors in the volume has been added. If the word at offset 13h is 0, this means that Big number of logical sectors in the volume gives the number of sectors of the volume.

Medium descriptor byte :
The BIOS and DOS use this entry to determine the disk type. See Appendix A for a table with the valid values for this byte. As some values are used for several disk geometries, it is better to use the detailed information of the boot sector than the medium descriptor byte.

Sectors per FAT :
This word gives the number of sectors per FAT.

Sectors per track :
This word gives the number of sectors per track.

Number of heads :
This word gives the number of read/write heads.

Number of hidden sectors :
This word gives the number of hidden sectors.

2.4. The File Allocation Table and clustering

The File Allocation Table or FAT is the structure used by the filesystem to know where the files have been saved on the disk. The FAT links a file to the sectors of the disk where its content has been stored.
There are two versions of FAT, one with entries of 12 bits and another with entries of 16 bits. If the entries where used to store a logical sector number, the maximum number would be 65535 and if the sectors have 512 bytes, this leads to a maximum disk capacity of 33Mb. To overcome this limitation, sectors have been grouped into clusters.

2.4.1. Clusters

A cluster is a set of 1 or more sectors and it is the smallest storage unit. A cluster is either free or used, it can't be shared by several files. Clustering allows the increase of storage space because the FAT refers to cluster numbers instead of logical sector numbers. For instance, if you put 4 sectors into each cluster, each cluster will hold 2048 bytes, the maximum cluster number is 65535 for FAT16 and this gives a capacity of about 120 Mb.
The drawback to this method is waste of storage space. If a cluster is only partially used by a file, the remaining part of the cluster contains no useful data but is unusable for other files. If you use clusters of 1 sector and the sector size is 512 bytes, this leads to a waste of maximum 511 bytes (when the file uses 1 byte of the cluster). But when the cluster size is 4 sectors with the same sector size, this leads to a waste of maximum 2047 bytes. The more sectors you group into one cluster, the more space you waste. This is especially annoying when you have a lot of small files.

2.4.2. Structure of the FAT

The FAT is a large array of cluster numbers. Each entry of this array is assigned a cluster : cluster number 2 is assigned to FAT entry number 2, cluster number 3 is assigned to FAT entry number 3 and so on. The enumeration starts with 2 because the first two entries are reserved. They are occupied by a copy of the Medium Descriptor Byte followed by 2 bytes (12-bit FAT) or 3 bytes (16-bit FAT) with the value FFh. As a consequence, the number of the first cluster is 2 and not 0.
The value stored in an entry of the table indicates the current use of the related cluster. The following table shows the possible values of an entry and their meanings.

12-bit	16-bit	Meaning
000h	0000h	free
FF0h to FF6h	FFF0h to FFF6	reserved
FF7h	FFF7h	bad sector, unusable
FF8h to FFFh	FFF8h to FFFFh	last cluster of a file/directory
Any other value	Any other value	next cluster of a file/directory

A file occupies a given number of clusters. The question is which ones and in what order. The solution is to build an ordered list whose elements are the clusters occupied by the file.
The FAT allows to build such a list. If you know the number of a cluster of the file (we'll call this cluster the current cluster), the next cluster of the file is found by looking at the value of the FAT entry relative to the current cluster. As indicated by the above table, if this value is not a value with a special meaning, it is the number of the next cluster. In the FAT entry relative to this next cluster, the number of the following cluster will be found and so on. Using the FAT entries, we build an ordered list of all the clusters occupied by the file. This ordered list is called a cluster chain. We know when we have reached the end of the chain when we encounter the value FF8h or FFF8h in a FAT entry, which means that the current cluster is the last of the chain.
An info is still missing to allow us to build the chain : the first cluster of the file. Whithout it, we don't know where to start. It's the Root Directory (see Root Directory later) that keeps the number of the starting cluster of the file.

Example :
This example shows what the FAT looks like for the storage of a 1200 bytes file with 1 sector per cluster and 512 bytes per sector. The FAT is supposed to be a 12-bit FAT and the first cluster of the file is cluster number 2.
The values of the first bytes of the FAT are : F0 FF FF 03 40 00 FF 0F 00 00 00 ...
We must group these bytes into entries of 12 bits. This gives :

F0 FF FF	The medium descriptor byte followed by two bytes with value FFh.
003	Entry relative to second cluster : the cluster following cluster 2 is cluster 3.
004	Entry relative to third cluster : the cluster following cluster 3 is cluster 4.
FFF	Entry relative to fourth cluster : the cluster 4 is the last of the chain.

The file is thus stored in clusters 2, 3 and 4.

Note : The byte ordering is assumed to be little endian. This is why the three bytes 03 40 00 give the two entries of 12 bits : 003 and 004. In little endian, the most significant bits are stored at the higher memory addresses. Therefore the memory representation of these three bytes is : 11000000 00000010 00000000. This gives the first 12 bits : 1100 0000 0000. In little endian, this is the number 3. The next 12 bits are : 0010 0000 0000. In little endian, this is the number 4.

2.4.3. Location of the FATs and the clusters

To access a file, you still need to learn where to find the FAT and a given cluster.
The first FAT is right after the last reserved sector. The following formula gives the logical sector number where the first FAT starts.

lsnFAT = hs + rs
where
lsnFAT is the number of the logical sector where the FAT starts,
hs is the number of hidden sectors and
rs is the number of reserved sectors.
These two values can be found in the boot sector.

There are N copies of the FAT on the disk. N is given by the boot sector. The following formula gives the number of the logical sector where the i^th copy starts.

lsnFAT[i] = hs + rs + i*spf
where
lsnFAT[i] is the number of the logical sector where the i^th FAT starts (0 =< i < N).
hs is the number of hidden sectors
rs is the number of reserved sectors
spf is the number of sectors per FAT

Each copy occupies the number of sectors given by the boot sector.

To obtain the logical sector number of the first sector of a cluster, the following formula can be used :

lsn = hs + rs + N*spf + nsird + (cln - 2)*spc
where
lsn is the number of the logical sector where the cluster starts
hs is the number of hidden sectors
rs is the number of reserved sectors
N is the number of FATs
spf is the number of sectors per FAT
nsird is the number of sectors occupied by the root directory
cln is the cluster number
spc is the number of sectors per cluster

The formula is obvious when you know that the first cluster has number 2 and that it comes right after the Root Directory. The clusters follow eachother on the disk.
Only the term nsird in the above formula is not straightforward to compute. The following formula gives an easy way to do so.

nsird = (nerd*32 + bps - 1) / bps
where
nsird is the number of sectors occupied by the Root Directory
nerd is the number of entries in the Root Directory
bps is the number of bytes per sector

Once you've got the number of the logical sector of the first sector of a cluster, the other sectors of the cluster are obtained by incrementing the logical sector number because the sectors of a cluster follow eachother. As a consequence, the following formula gives the logical sector number of the i^th sector of cluster cln.

lsn = hs + rs + N*spf + nsird + (cln - 2)*spc + i
where
lsn is the number of the logical sector of the i^th sector of the cluster (0 =< i < spc)
hs is the number of hidden sectors
rs is the number of reserved sectors
N is the number of FATs
spf is the number of sectors per FAT
nsird is the number of sectors occupied by the root directory
cln is the cluster number
spc is the number of sectors per cluster

2.5. The Root Directory

Example of a boot sector

40-49 :
The code disables the interrupts while it initializes the segment registers. ss = es = 0 and sp = 7BFCh. The boot code is loaded by the bootstrap at 0000:7C00, the stack begins 4 bytes before this position. These 4 bytes, at 0000:7BFC will be used later.

4A-4D :
The pointer at 0000:0078 is loaded into ds:si. This is the pointer to the drive parameter table.

50-53 :
ds, si, ss and bp are pushed onto the stack. They don't seem to be popped afterwards so I don't know what this is used for.

54-5A :
The address of the drive parameter table is now 0000:0522.

5D-60 :
The drive parameter table, whose length is 12 bytes, is moved from its old location to its new location (0000:0522).

62-64 :
ds = 0 and bp = 7C00h. bp points to the start of the image of the boot sector. The value of bp won't change anymore, so you can keep in mind that bp points to the boot sector.

67-6E :
This portion of the code sets the parameters of the drive parameters table in function of the data of the boot sector of the disk.
Due to the rep movsb instruction, di points to the end of the drive parameters table.
di-02 points to the 11^th byte of the table, this is the head settle time. The head settle time is set to 15 milliseconds.
bp+18 points to the number of sectors per track. di-07 points to the 4^th byte of the parameter table, this is the number of sectors per track. This number is set to the number given by the boot sector.

71 :
This reenables the interrupts.

72-75 :
This code is a mystery for me. Anyway, for a floppy, [bp+24h] should be 0 and ah too, and the jump shouldn't be made.

77-79 :
As ah and dl are equal to 0, the call to interrupt 13h recalibrates the floppy drive. If the recalibration fails, a jump is made to the code at B7.

Note : the code that follows is particularly interesting as it shows how to find the start of the Root Directory and the start of the space where the files are stored.

7B-7F :
The number of FATs is transferred into al. al is then sign-extended and ax is multiplied by the number of sectors per FAT. dx:ax is now the number of sectors used to store all the FATs.

82-85 :
The number of hidden sectors is added to dx:ax. The number of hidden sectors occupies 4 bytes because the byte at offset 26h of the boot sector is 29h. Otherwise, it would be only 2 bytes long.

88-92 :
The number of reserved sectors is added to dx:ax. At this stage, dx:ax is the number of the first logical sector of the Root Directory.
ax and dx are pushed onto the stack. They are also stored at 0000:7BFC and 0000:7BFE, the 4 bytes between the bottom of the stack and the boot code.

95-A8 :
ax is loaded with the value 20h (32) because an entry of the Root Directory is 32 bytes long. si is loaded with the number of entries of the Root Directory. After ax has been multiplied by si, dx:ax is the length of the Root Directory measured in bytes.
bx is loaded with the number of bytes per sector.
bx is then added to ax and then ax is decremented by one. This is a little trick. The number of bytes used for the Root Directory is not required to be a multiple of the number of bytes per sector. If it's not a multiple, the last sector is not completely used. But even if the Root Directory only uses one byte of the last sector, this sector must be reserved. By adding the number of bytes per sector - 1 to the number of bytes of the Root Directory, you are sure to get the correct number of sectors after a division by the number of sectors per byte. In our case, the number of entries in the Root Directory is 224 and the number of bytes per sector 512. 7168 bytes are used to store the Root Directory. 7168 is exactly 14*512. 14 sectors are thus needed. If we add 511 (number of bytes per sectors - 1) to 7168, we get 7679. A division by 512 gives 14, which is the result expected. Now imagine we have 225 entries instead of 224. 7200 bytes are needed for the Root Directory. 14 full sectors are used and 32 bytes of the last sector, this means 15 sectors. We add 511 to 7200, this gives 7711. We divide this result by 512 and we get the correct answer :15.
Now let's get back to our code.
We divide dx:ax by bx. ax is now the number of sectors used by the Root Directory.
We add this value to the value stored at 0000:7BFC. The value stored there is now the number of the first logical sector that can be used to store the content of a file.

AB-B7 :
The function at 14Bh loads a logical sector of the disk. dx:ax is the number of the sector, bx is the memory location where the sector will be written and cx is the number of sectors to read.
In this case, we pop ax and dx. If you remember, this is the number of the first logical sector of the Root Directory. bx is set to 0700h. di is also set to 0700h but it is not used by the function at 14Bh. It's for a future use. cl is set to 1. One sector will thus be read from the disk.
If the carry is set, it means there was an error. The code at offset 100h handles this situation. This is why we have the instruction jc 100.

B9-BB :
We go through the Root Directory entries to find a given file. To do so, we use the register di which points to the current position in the Root Directory. Initially, it is 0700h, the start of the Root Directory in memory.
As the content of register ch is 0, we compare [di] to 0. For the FAT filesystem, an entry starting with 0 means the end of the Root Directory. If we encounter a 0, it means that we have gone through all the directory without finding the file. The code at offset 0D6h handles this situation hence the instruction je D6.

BD-C6 :
If the entry doesn't start with 0, we compare it with the filename. We compare the 11 first bytes of the entry with the filename because these are the bytes which hold the filename.
The comparison is made by the repe cmpsb instruction. As a consequence, the registers si and di must hold the start addresses of the strings to compare. di is already pointing to the current entry of the Root Directory and si is loaded with the content of [bp+3E]. This is the word at offset 3Eh of the boot sector. si is thus equal to 1DF7h. This value corresponds to the offset 1F1h of the boot sector because 7DF1h - 7C00h = 1F1h. And at offset 1F1h of the boot sector, we find the string "WINBOOT.SYS". The file we are looking for is thus "WINBOOT.SYS". The register cl must hold the length of the strings : 11 bytes in the present case.
If we have found the file, we jump at offset 112h.
The content of tbe register si saved on the stack and then restored.

C8-C9 :
si is the number of entries in the Root Directory that have not been examined yet. We decrement it by 1 as we have just tested one entry. If si reaches 0, then there are no more entries and the file has not been found. The code at offset D6h handles this situation.

CB-D4 :
The result of the 2 additions is that di now points to the next entry of the Root Directory. di is then compared to bx. This is to make sure that we have not reached the end of the sector of the Root Directory that was loaded into memory by the call to the function at offset 14Bh. As a result of this call, bx points to the end of the loaded sector. If we are not at the end of the loaded sector, we return to offset BDh, where a new comparison is made between the file name and the entry where the new di points to.
If we are at the end of the loaded sector, we must load the next sector. Therefore we return at offset ADh. The registers dx and ax have not been modified since the last call to the function at 14Bh. As a consequence, they hold the number of the next logical sector to load.

D6-E0 :
This code is called when we reach the end of the Root Directory. cx is reset to 0. The word at offset 3Eh of the boot sector is set to 7DD8h. Remember that the offset 3Eh holds the pointer to the file name. We are now looking for another filename. This file name is located at offset 7DD8h - 7C00h = 1D8h of the boot sector. This is the string "IO.SYS".
We compare the old value of offset 3Eh with the new one. If they are the same, it means that we have already done the previous procedure before. We have looked for "IO.SYS" but we haven't found it, so we are here for the second time.
If they are not the same, then we must look for "IO.SYS" in the Root Directory. To do so, we return to the code at offset 7Bh. This means that we are almost doing everything again but with another value of the word at offset 3Eh of the boot sector.

E2 :
We reach this point if the files "WINBOOT.SYS" and "IO.SYS" haven't been found. The register si is loaded with the value 7D80h. This is a pointer to offset 7D80h - 7C00h = 180h of the boot sector. The value stored there is 3.

E5-F9 :
The register ax is loaded with the content of the memory location indicated by si. ax is then added to si. ax is again loaded with the content of [si].
al is tested. If it is equal 0, the code at offset 105h is executed. If it is equal to FFh, the code at offset FBh is executed. If it is not equal to one of these values the content of al is displayed by a call to interrupt 10. After that, we return to offset E9h. The instruction lodsb loads the next character which will then be displayed. This loop only stops when al is loaded with 0 or FFh.

• If this code part is executed right after the instruction at E2, the content of register si is initially 7D80, the lodsb instruction increments it by 1 while it loads al with 3 (the content of the boot sector at offset 180h). After the addition, si is equal to 7D84. This is a pointer to the string "Disque non systeme". The result of the code is the display of a warning message saying that the disk is not a system disk. This happens when the boot code doesn't find "WINBOOT.SYS" or "IO.SYS". The string ends with FFh, the code at FBh is thus executed.
• If this code is executed after the code at FBh, the content of si is initially 7D83h and after the addition it is 7DABh. This is a pointer to the string which ask the user to replace the disk by a system disk and to hit a key. The string ends by 0 so the code at offset 105h is executed.
• If this code is executed after the code at 100h, the content of si is initially 7D81h and after the addition it is 7D9Ah. This is a pointer to the string which indicates that an I/O error has occured. The string ends by FFh so the code at offset FBh is executed.

Appendix A