972
edits
FAT: Difference between revisions
m
Bot: Replace deprecated source tag with syntaxhighlight
| [unchecked revision] | [unchecked revision] |
m (Remove crappy plug to incomplete and shitty article) |
m (Bot: Replace deprecated source tag with syntaxhighlight) |
||
| (17 intermediate revisions by 9 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
== 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
=== ExFAT ===
{{Main|ExFAT}}
ExFAT is the filesystem used on SDXC cards, created by Microsoft. It is
Microsoft has published the official specification at https://docs.microsoft.com/en-us/windows/win32/fileio/exfat-specification .
Line 76:
| 0x11
| 2
| Number of root directory entries (must be set so that the root directory occupies entire sectors).
|-
| 19
Line 86:
| 0x15
| 1
| This Byte indicates the [https://
|-
| 22
Line 300:
|}
==== exFat boot record ====
For exFAT the whole boot record was recreated from scratch instead of extending the existing FAT12/16/32 boot records even further. You can recognize exFAT by noticing that in the FAT12/16/32 boot record, the "bytes per sector" is zero.
{| {{wikitable}}
|-
! Offset (decimal)
! Offset (hex)
! Size (in bytes)
! Meaning
|-
| 0
| 0x00
| 3
| The first three bytes EB 3C 90 disassemble to JMP SHORT 3C NOP. (The 3C value may be different.) The reason for this is to jump over the disk format information (the BPB and EBPB). Since the first sector of the disk is loaded into ram at location 0x0000:0x7c00 and executed, without this jump, the processor would attempt to execute data that isn't code. Even for non-bootable volumes, code matching this pattern (or using the E9 jump opcode) is required to be present by both Windows and OS X. To fulfil this requirement, an infinite loop can be placed here with the bytes EB FE 90.
|-
| 3
| 0x03
| 8
| OEM identifier. This contains the string "EXFAT ". Not to be used for filesystem determination, but it's a nice hint.
|-
| 11
| 0x0B
| 53
| Set to zero. This makes sure any FAT driver will not be able to load it.
|-
| 64
| 0x40
| 8
| Partition offset. No idea why the partition itself would have this, but it's here. Might be wrong. Probably best to just ignore.
|-
| 72
| 0x48
| 8
| Volume length.
|-
| 80
| 0x50
| 4
| FAT offset (in sectors) from start of partition.
|-
| 84
| 0x54
| 4
| FAT length (in sectors).
|-
| 88
| 0x58
| 4
| Cluster heap offset (in sectors).
|-
| 92
| 0x5C
| 4
| Cluster count
|-
| 96
| 0x60
| 4
| Root directory cluster. Typically 4 (but just read this value).
|-
| 100
| 0x64
| 4
| Serial number of partition.
|-
| 104
| 0x68
| 2
| Filesystem revision
|-
| 106
| 0x6A
| 2
| Flags
|-
| 108
| 0x6C
| 1
| Sector shift
|-
| 109
| 0x6D
| 1
| Cluster shift
|-
| 110
| 0x6E
| 1
| Number of FATs
|-
| 111
| 0x6F
| 1
| Drive select
|-
| 112
| 0x70
| 1
| Percentage in use
|-
| 113
| 0x71
| 7
| Reserved (set to 0).
|}
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).
<syntaxhighlight 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>
Note that all values in the BPB are now naturally aligned and that this code is *significantly* simpler than FAT32's BPB reading.
=== File Allocation Table ===
Line 306 ⟶ 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:
<
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 /
unsigned int ent_offset = fat_offset %
//at this point you need to read two sectors from
unsigned short table_value = *(unsigned short*)&FAT_table[ent_offset];
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
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. Index 0 is used as a value in other entries signifying that the given cluster is free, with the corresponding first entry in the table holding the value of the BPB_Media field in its low 8 bits and 0xf in its top 4 bits. For example, if BPB_Media is 0xF8, then the zeroth entry should hold the value 0xFF8. The second entry (index 1) is unused but must 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.
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.
==== 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:
<
unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster * 2;
Line 340 ⟶ 461:
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
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.
The entries under index 0 and 1 are reserved. The zeroth entry is reserved because index 0 is used as value of other entries signifying that the given cluster is free. Zeroth entry has to hold value of the BPB_Media field from in the low 8 bits, and the rest of the bits have to be set to zero. For example, if BPB_Media is 0xF8, then the zeroth entry should hold the value 0xFFF8. The first entry is reserved for the future and must to hold the value 0xFFFF.
==== 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:
<syntaxhighlight lang="C">
unsigned char FAT_table[sector_size];
unsigned int fat_offset = active_cluster * 4;
Line 354 ⟶ 477:
//remember to ignore the high 4 bits.
unsigned int table_value = *(unsigned int*)&FAT_table[ent_offset]
if (fat32) table_value &= 0x0FFFFFFF;
//the variable "table_value" now has the information you need about the next cluster in the chain.
</syntaxhighlight>
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.
The entries under index 0 and 1 are reserved. The zeroth entry is reserved because index 0 is used as value of other entries signifying that the given cluster is free. Zeroth entry has to hold value of the BPB_Media field from in the low 8 bits, and the rest of the bits have to be set to zero. For example, if BPB_Media is 0xF8, then the zeroth entry should hold the value 0xFFFFFFF8. The first entry is reserved for the future and must to hold the value 0xFFFFFFFF.
Note that on exFAT, some files are not written out into the FAT. In the case that a file is fully contiguous, exFAT allows the operating system to encode this information and not update the FAT for this file. Unlike FAT32 therefore, the FAT table is not used for allocation status of a cluster; instead there is an allocation bitmap to handle that. See below under directory entries for that.
=== Directories on FAT12/16/32 ===
A directory entry simply stores the information needed to know where a file's data or a folder's children are stored on the disk. It also holds information such as the entry's name, size, and creation time. There are two types of directories in a FAT file system. Standard 8.3 directory entries, which appear on all FAT file systems, and Long File Name directory entries which are optionally present to allow for longer file names.
Line 384 ⟶ 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 501 ⟶ 629:
Notice that each character is two bytes long and that the name is null terminated. The two FF's at the end are the padding at the end of the long file name. This is also what the other FF's in the long file name entry are.
The final important thing to notice about the long file name entry is it's attribute byte at offset 11. the 0x0F attribute allows us to verify that this is indeed a long file name entry.
=== Directories on exFAT ===
exFAT redesigned these directory entries from the ground up.
{| {{Wikitable}}
|-
! Offset (in bytes)
! Length (in bytes)
! Meaning
|-
| 0
| 1
| Entry type
|-
| 1
| 31
| Rest of entry.
|}
The base for every entry is that they are all still 32 bytes, and they all start with the type in the first byte. The types I've encountered that are relevant for reading files from disk:
==== File entry ====
{| {{Wikitable}}
|-
! Offset (in bytes)
! Length (in bytes)
! Meaning
|-
| 0
| 1
| Entry type = 0x85
|-
| 1
| 1
| Count of secondary entries.
|-
| 2
| 2
| Checksum of entry set
|-
| 4
| 2
| File attributes
|-
| 6
| 2
| Reserved
|-
| 8
| 4
| Creation date and time
|-
| 12
| 4
| Modification date and time
|-
| 16
| 4
| Access date and time
|-
| 20
| 1
| Creation time 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 time in hundredths of a second (0-199).
|-
| 22
| 1
| UTC offset for creation time
|-
| 23
| 1
| UTC offset for modification time
|-
| 24
| 1
| UTC offset for access time
|-
| 25
| 7
| Reserved.
|}
==== Stream "extension" entry ====
It's called an extension, but it's 100% required to exist directly after the "file" entry.
{| {{Wikitable}}
|-
! Offset (in bytes)
! Length (in bytes)
! Meaning
|-
| 0
| 1
| Entry type = 0xC0
|-
| 1
| 1
| Secondary flags
|-
| 2
| 1
| Reserved
|-
| 3
| 1
| Name length
|-
| 4
| 2
| Name hash
|-
| 6
| 2
| Reserved
|-
| 8
| 8
| Valid data length. When writing large files, exFAT allocates the whole file first, and then incrementally updates this as data is written. Not sure what you're supposed to do with this, if it's not dataLength yell at the user?
|-
| 16
| 4
| Reserved
|-
| 20
| 4
| First cluster.
|-
| 24
| 8
| Data length.
|}
==== File name entry ====
{| {{Wikitable}}
|-
! Offset (in bytes)
! Length (in bytes)
! Meaning
|-
| 0
| 1
| Entry type = 0xC1
|-
| 1
| 1
| flags
|-
| 2
| 30
| File name characters (15 UTF16 code units).
|}
To actually use these, they typically come in the order:
- File entry
- Stream extension entry
- File name entry
- (Additional file name entries)
The file entry has the file metadata info, the stream extension tells you how it's stored and the file name entries tell you what it's called. There is no 8.3 name any more.
When reading the file, the second bit in the stream extension secondary flags indicates if it's stored as extent, or if you need to use the FAT table. If it is set, the file is contiguous and the FAT is not up to date, if it is clear, the FAT is accurate and needs to be used (but could still say it's contiguous).
==== Long File Names ====
Long file name entries ''always'' have a regular 8.3 entry to which they belong. The long file name entries are always placed immediately before their 8.3 entry. Here is the format of a long file name entry.
{| {{Wikitable}}
|-
! Offset (in bytes)
! Length (in bytes)
! Meaning
|-
| 0
| 1
| The order of this entry in the sequence of long file name entries. This value helps you to know where in the file's name the characters from this entry should be placed.
|-
| 1
| 10
| The first 5, 2-byte characters of this entry.
|-
| 11
| 1
| Attribute. Always equals 0x0F. (the long file name attribute)
|-
| 12
| 1
| Long entry type. Zero for name entries.
|-
| 13
| 1
| Checksum generated of the short file name when the file was created. The short filename can change without changing the long filename in cases where the partition is mounted on a system which does not support long filenames.
|-
| 14
| 12
| The next 6, 2-byte characters of this entry.
|-
| 26
| 2
| Always zero.
|-
| 28
| 4
| The final 2, 2-byte characters of this entry.
|}
== Programming Guide ==
Line 509 ⟶ 844:
Here is an example of some boot sector structures in C.
<
typedef struct fat_extBS_32
{
Line 562 ⟶ 897:
}__attribute__((packed)) fat_BS_t;
</syntaxhighlight>
Important pieces of information that can be extracted from the boot sector include:
'''Total sectors in volume (including VBR):'''
<
total_sectors = (fat_boot->total_sectors_16 == 0)? fat_boot->total_sectors_32 : fat_boot->total_sectors_16;
</syntaxhighlight>
'''FAT size in sectors:'''
<
fat_size = (fat_boot->table_size_16 == 0)? fat_boot_ext_32->table_size_16 : fat_boot->table_size_16;
</syntaxhighlight>
'''The size of the root directory (unless you have FAT32, in which case the size will be 0):'''
<
root_dir_sectors = ((fat_boot->root_entry_count * 32) + (fat_boot->bytes_per_sector - 1)) / fat_boot->bytes_per_sector;
</syntaxhighlight>
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):'''
<
first_data_sector = fat_boot->reserved_sector_count + (fat_boot->table_count * fat_size) + root_dir_sectors;
</syntaxhighlight>
'''The first sector in the File Allocation Table:'''
<
first_fat_sector = fat_boot->reserved_sector_count;
</syntaxhighlight>
'''The total number of data sectors:'''
<
data_sectors =
</syntaxhighlight>
'''The total number of clusters:'''
<
total_clusters = data_sectors / fat_boot->sectors_per_cluster;
</syntaxhighlight>
This rounds down.
'''The FAT type of this file system:'''
<
if (
{
fat_type = ExFAT;
}
else if(total_clusters < 4085)
{
fat_type = FAT12;
Line 617 ⟶ 955:
fat_type = FAT16;
}
else
{
fat_type = FAT32;
}
</syntaxhighlight>
=== 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:
<
first_root_dir_sector = first_data_sector - root_dir_sectors;
</syntaxhighlight>
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.
<
root_cluster_32 = extBS_32->root_cluster;
</syntaxhighlight>
For each given cluster number we can calculate the first sector of it (relative to the partition's offset):
<
first_sector_of_cluster = ((cluster - 2) * fat_boot->sectors_per_cluster) + first_data_sector;
</syntaxhighlight>
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:
Line 661 ⟶ 995:
# Read the cluster represented by the extracted value and return for more directory parsing.
# The end of the cluster chain has been found. Our work here is finished. :)
=== Reading extents ===
On exFAT, files can have a bit set in their flags that indicate it is stored as extent-based. This means that the whole file is contiguous, and that the file size plus the first cluster indicate where the (whole) file is. The FAT entries will contain garbage and are not to be trusted.
To read this, do the same calculation as above, except you may in every step assume that the next cluster is the numerically next cluster and that enough sectors have been allocated for the file size.
== Creating a fresh FAT filesystem ==
| |||