OSDev.wiki

FAT: Difference between revisions

[unchecked revision][unchecked revision]
← Older edit
Content deleted Content added
VisualWikitext
m →‎File Allocation Table: add information about entries 0 and 1
m Bot: Replace deprecated source tag with syntaxhighlight
 
(11 intermediate revisions by 7 users not shown)
Line 1:
{{Filesystems}}
The '''File Allocation Table''' ('''FAT''') was the native file system of MS-DOS. FAT was originally introduced by Marc McDonald in Stand-alone Disk BASIC with DOS8-bit v1.0FAT entries (and possibly16 CP/M)byte directory entries. SupposedlyThe writtenbetter byknown BillFAT12 Gatesvariant, with 12-bit FAT entries and 32 byte directory entries, was introduced with DOS. FAT is a very simple file system -- nothing more than a singly-linked list of clusters in a gigantic table. A FAT file system uses very little memory (unless the OS caches the whole allocation table in memory) and is one of, if not the, most basic file system in use today.
 
== Overview ==
Line 11:
 
=== FAT 32 ===
FAT 32 was introduced to us by Windows95-B and Windows98. FAT32 solved some of FAT's problems. No more 64K max clusters! Although FAT32 isuses slightly32 misnamed,bits asper theFAT topentry, 4 bits ofonly the 32bottom bit28 cluster numberbits are reserved,actually andused wereto neveraddress used.clusters Ifon youthe wantdisk to(top call4 itbits FAT28are instead,reserved). thenWith as28 thebits per nameFAT suggestsentry, the filesystem can handleaddress a maximum of 256Mabout 270 million clusters perin a partition. This enables very large hard disks to still maintain reasonably small cluster sizes and thus reduce slack space between files.
 
=== ExFAT ===
Line 76:
| 0x11
| 2
| Number of root directory entries (must be set so that the root directory occupies entire sectors).
|-
| 19
Line 408:
To read the filesystem, find out how big a 'sector' and a 'cluster' are. A sector is (1 << sectorshift) bytes, a cluster is (1 << (sectorshift + clustershift)) bytes. Then, find the start of the FAT and the start of the cluster heap (note that the first cluster is *still* cluster 2).
 
<sourcesyntaxhighlight lang="C">
// This allows you to zero-index clusters:
uint64_t clusterArray = clusterheapoffset * sectorsize - 2 * clustersize;
uint64_t fatOffset = fatoffset * sectorsize;
uint64_t usablespace = clustercount * clustersize;
</syntaxhighlight>
</source>
 
Note that all values in the BPB are now naturally aligned and that this code is *significantly* simpler than FAT32's BPB reading.
Line 422:
==== FAT 12 ====
FAT 12 uses 12 bits to address the clusters on the disk. Each 12 bit entry in the FAT points to the next cluster of a file on the disk. Given a valid cluster number, here is how you extract the value of the next cluster in the cluster chain:
<sourcesyntaxhighlight lang="C">
unsigned char FAT_table[sector_size * 2]; // needs two in case we straddle a sector
unsigned int fat_offset = active_cluster + (active_cluster / 2);// multiply by 1.5
unsigned int fat_sector = first_fat_sector + (fat_offset / section_sizesector_size);
unsigned int ent_offset = fat_offset % section_sizesector_size;
 
//at this point you need to read two sectors from sectordisk starting at "fat_sector" on the disk into "FAT_table".
 
unsigned short table_value = *(unsigned short*)&FAT_table[ent_offset];
 
iftable_value = (active_cluster & 0x00011) ? table_value >> 4 : table_value & 0xfff;
table_value = table_value >> 4;
else
table_value = table_value & 0x0FFF;
 
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
</source>
If "table_value" is greater than or equal to (>=) 0xFF8 then there are no more clusters in the chain. This means that the whole file has been read. If "table_value" equals (==) 0xFF7 then this cluster has been marked as "bad". "Bad" clusters are prone to errors and should be avoided. If "table_value" is not one of the above cases then it is the cluster number of the next cluster in the file.
 
The entries under index 0 and 1 are reserved. The zeroth entry is reserved because indexIndex 0 is used as a value ofin other entries signifying that the given cluster is free., Zerothwith the corresponding first entry hasin tothe holdtable holding the value of the BPB_Media field from in theits low 8 bits, and the0xf restin ofits thetop 4 bits have to be set to zero. For example, if BPB_Media is 0xF8, then the zeroth entry should hold the value 0xFF8. The firstsecond entry is(index reserved1) foris theunused future andbut must to hold the value 0xFFF.
 
FAT12 uses an entry size that is not evenly divisible by 8 bits. This has some consequences.
 
First is storage in the table. Consider successive entries with values 0x123 and 0x456. In the bytes of the table, they'll be stored 0x23 0x61 0x45. Note that if you do little-endian 16-bit loads, you get 0x6123 at offset 0 and 0x4561 at offset 1, letting you recover the original two entry values with the shifts, masks, and offsets seen in the above code block.
 
The second is that, as seen above with the offsets used being 0 and 1, those word bytes might not be 16-bit aligned. That usually just means the x86 takes a slower path to load the word if you do e.g. <tt>*(unsigned short *)bytes</tt>, but if you're use something like UBSan to avoid undefined behavior, those UB-catching routines can be triggered (usually resulting in a panic) if you don't load the two bytes separately and stick them together yourself.
Since FAT12 uses an entry size that is not evenly divisible by 8 bits, figuring out how to interpret the FAT can be slightly confusing. Consider two successive entries with values 0x123 and 0x456. The first byte of the first entry is the bottom two nibbles (0x23) and the highest nibble goes into the bottom nibble of the second byte (0x?1). Since the next entry is now starting mid-byte, only the lowest nibble can fit in the byte (0x6?) and the two highest nibbles go into the next byte (0x45). Therefore the 2 entries back-to-back look like this: 0x23 0x61 0x45.
 
The third consequence is that the word bytes might not be *sector* aligned. Which means if your code loads a single sector of the table, it needs a special case where it loads two if the entry straddles the sector-size boundary. Or you can just load two sectors every time as seen above.
This placement might be confusing, but if we consider a little-endian machine it will start make more sense. If you load the WORD value at offset zero, the resulting value will be 0x6123. Now the nibbles are in correct order, so to get the value of the first of the two entries you just have to AND the value with 0xfff. For the second entry, you have to first load WORD at offset 1, resulting in the value of 0x4561 and shifting it down by 4 bits (effectively removing the bottom nibble).
 
==== FAT 16 ====
FAT 16 uses 16 bits to address the clusters on the disk. Because of this, it is much easier to extract the values out of a 16 bit File Allocation Table. Here is how it is done:
<sourcesyntaxhighlight lang="C">
unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster * 2;
Line 460 ⟶ 461:
 
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
</source>
If "table_value" is greater than or equal to (>=) 0xFFF8 then there are no more clusters in the chain. This means that the whole file has been read. If "table_value" equals (==) 0xFFF7 then this cluster has been marked as "bad". "Bad" clusters are prone to errors and should be avoided. If "table_value" is not one of the above cases then it is the cluster number of the next cluster in the file.
 
Line 467 ⟶ 468:
==== FAT 32 and exFAT ====
FAT 32 uses 28 bits to address the clusters on the disk. The highest 4 bits are reserved. This means that they should be ignored when read and unchanged when written. exFAT uses the full 32 bit to encode sector numbers. Similar to the same operation on a 16 bit FAT:
<sourcesyntaxhighlight lang="C">
unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster * 4;
Line 480 ⟶ 481:
 
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
</source>
If "table_value" is greater than or equal to (>=) 0x0FFFFFF8 (or 0xFFFFFFF8 for exFAT) then there are no more clusters in the chain. This means that the whole file has been read. If "table_value" equals (==) 0x0FFFFFF7 (or 0xFFFFFFF7 for exFAT) then this cluster has been marked as "bad". "Bad" clusters are prone to errors and should be avoided. If "table_value" is not one of the above cases then it is the cluster number of the next cluster in the file.
 
Line 511 ⟶ 512:
| 13
| 1
| Creation time in hundredths of a second, although the official FAT Specification from Microsoft says it is tenths of a second. Range 0-199 inclusive. Based on simple tests, Ubuntu16.10 stores either 0 or 100 while Windows7 stores 0-199 in this field.
|-
| 14
Line 690 ⟶ 691:
| 20
| 1
| Creation millisecondstime in hundredths of a second (0-199) to be added to the FAT style date/time for more accuracy. See FAT12 entry for format of date/time.
|-
| 21
| 1
| Modification millisecondstime in hundredths of a second (0-199).
|-
| 22
Line 843 ⟶ 844:
 
Here is an example of some boot sector structures in C.
<sourcesyntaxhighlight lang="C">
typedef struct fat_extBS_32
{
Line 896 ⟶ 897:
}__attribute__((packed)) fat_BS_t;
</syntaxhighlight>
</source>
Important pieces of information that can be extracted from the boot sector include:
 
'''Total sectors in volume (including VBR):'''
<sourcesyntaxhighlight lang="C">
total_sectors = (fat_boot->total_sectors_16 == 0)? fat_boot->total_sectors_32 : fat_boot->total_sectors_16;
</syntaxhighlight>
</source>
 
'''FAT size in sectors:'''
<sourcesyntaxhighlight lang="C">
fat_size = (fat_boot->table_size_16 == 0)? fat_boot_ext_32->table_size_16 : fat_boot->table_size_16;
</syntaxhighlight>
</source>
 
'''The size of the root directory (unless you have FAT32, in which case the size will be 0):'''
<sourcesyntaxhighlight lang="C">
root_dir_sectors = ((fat_boot->root_entry_count * 32) + (fat_boot->bytes_per_sector - 1)) / fat_boot->bytes_per_sector;
</syntaxhighlight>
</source>
This calculation will round up. 32 is the size of a FAT directory in bytes.
 
 
'''The first data sector (that is, the first sector in which directories and files may be stored):'''
<sourcesyntaxhighlight lang="C">
first_data_sector = fat_boot->reserved_sector_count + (fat_boot->table_count * fat_size) + root_dir_sectors;
</syntaxhighlight>
</source>
 
 
'''The first sector in the File Allocation Table:'''
<sourcesyntaxhighlight lang="C">
first_fat_sector = fat_boot->reserved_sector_count;
</syntaxhighlight>
</source>
 
 
'''The total number of data sectors:'''
<sourcesyntaxhighlight lang="C">
data_sectors = fat_boot->total_sectors - (fat_boot->reserved_sector_count + (fat_boot->table_count * fat_size) + root_dir_sectors);
</syntaxhighlight>
</source>
 
 
'''The total number of clusters:'''
<sourcesyntaxhighlight lang="C">
total_clusters = data_sectors / fat_boot->sectors_per_cluster;
</syntaxhighlight>
</source>
This rounds down.
 
'''The FAT type of this file system:'''
<sourcesyntaxhighlight lang="C">
if (sectorsize == 0)
{
Line 958 ⟶ 959:
fat_type = FAT32;
}
</syntaxhighlight>
</source>
 
=== Reading Directories ===
The first step in reading directories is finding and reading the root directory. On a FAT 12 or FAT 16 volumes the root directory is at a fixed position immediately after the File Allocation Tables:
<sourcesyntaxhighlight lang="C">
first_root_dir_sector = first_data_sector - root_dir_sectors;
</syntaxhighlight>
</source>
 
In FAT32 and exFAT, root directory appears in data area on given cluster and can be a cluster chain. In exFAT it cannot be encoded as extent and will always be present in the FAT.
<sourcesyntaxhighlight lang="C">
root_cluster_32 = extBS_32->root_cluster;
</syntaxhighlight>
</source>
 
For each given cluster number we can calculate the first sector of it (relative to the partition's offset):
<sourcesyntaxhighlight lang="C">
first_sector_of_cluster = ((cluster - 2) * fat_boot->sectors_per_cluster) + first_data_sector;
</syntaxhighlight>
</source>
 
After the correct cluster has been loaded into memory, the next step is to read and parse all of the entries in it. Each entry is 32 bytes long. For each 32 byte entry this is the flow of execution:
Retrieved from "https://osdev.wiki/wiki/FAT"