China DOS Union

### Physical Structure of the Hard Disk:



The storage of data on a hard disk is realized based on the principle of electrical-magnetic conversion. A hard disk consists of one or several disk platters coated with magnetic material on the surface, as well as read/write heads installed on both sides of the platters and corresponding control circuits (Figure 1). The platters and heads are sealed in a dust-free metal case.

When the hard disk is in operation, the platters rotate at a high speed according to the designed rotational speed. The read/write heads set on the surface of the platters move radially to the specified position under the control of the circuit and then store or read data. When the system writes data to the hard disk, the "write data" current in the heads generates a magnetic field, causing a change in the state of the magnetic material on the surface of the platter. And it can remain after the write current magnetic field disappears, so that the data is stored. When the system reads data from the hard disk, the heads pass through the specified area of the platter. The magnetic field on the surface of the platter causes an induced current in the heads or a change in the impedance of the coil. After being processed by the relevant circuit, the data is restored. Therefore, as long as the surface of the platter is made smoother, the heads are designed more precisely, and the rotational speed of the platter is increased as much as possible, a hard disk with a larger capacity and faster data reading/writing speed can be manufactured. This is because the smoother the surface of the platter and the faster the rotational speed, the closer the heads can be to the surface of the platter, improving the reading and writing sensitivity and speed. The smaller and more precise the heads are designed, the smaller the space occupied by the heads on the platter, allowing the heads to establish more tracks on one platter to store more data.

### Logical Structure of the Hard Disk.

A hard disk is composed of many platters (platter). Each surface of each platter has a read/write head. If there are N platters, there are 2N surfaces, corresponding to 2N heads (Heads), numbered starting from 0, 1, 2. Each platter is divided into several concentric circular tracks (logically, it is invisible). The division rules of each platter are usually the same. In this way, the concentric circles with a fixed radius R for each platter logically form a cylinder (Cylinders) with the motor spindle as the axis, numbered from 0, 1, 2... from the outside to the inside. Each track on each platter is further divided into dozens of sectors (Sector), usually with a capacity of 512 bytes, and numbered as 1, 2, 3... according to a certain rule to form Cylinders × Heads × Sector sectors. These three parameters are the physical parameters of the hard disk. Many of our subsequent practices need to deeply understand the meanings of these three parameters.

### Disk Booting Principle.

#### 3.1 MBR (Master Boot Record) Sector:

After the computer presses the power key, it starts to execute the motherboard BIOS program. After a series of inspections and configurations, it starts to boot the system according to the system boot sequence set in the BIOS. Assume it is the hard disk now. After the BIOS executes its own program, how does it hand over the execution power to the hard disk? After handing over to the hard disk, which program stored where is executed? In fact, a section of code called MBR plays a crucial role. MBR (Master Boot Record), that is, the master boot record, is sometimes also called the master boot sector. It is located in the 0 cylinder 0 head 1 sector of the entire hard disk (which can be regarded as the first sector of the hard disk). After the BIOS executes its own inherent program, it will jump to the first instruction in the MBR and hand over the control of the system to the MBR for execution. In the master boot record with a total of 512 bytes, the boot program of the MBR occupies the first 446 bytes (offset 0H ~ offset 1BDH). The subsequent 64 bytes (offset 1BEH ~ offset 1FDH) are the DPT (Disk Partition Table, hard disk partition table). The last two bytes "55 AA" (offset 1FEH ~ offset 1FFH) are the partition valid end mark.

The MBR is not different with different operating systems, that is, different operating systems may have the same MBR. Even if they are different, the MBR will not carry the nature of the operating system. It has the characteristic of public booting.

Let's analyze a section of MBR. The following is the MBR of a Seagate 120GB hard disk viewed with WinHex.



The MBR boot code of your hard disk may not be like this. However, even if it is different, the functions performed are generally the same. Here, find the decompilation of disk MBR by wowocock, which has been added with detailed comments. If you are interested, you can study it carefully.

Let's look at the DPT part. In order to facilitate users' management of the disk, the operating system has added the concept of disk partitioning, that is, dividing a disk logically into several parts. The number of disk partitions is only limited by the number of English letters from C to Z. How to represent the attributes of multiple partitions in the 64 bytes of the DPT in the above figure? Microsoft solves this problem by the link method. In the 64 bytes of the DPT, a partition's attributes are described with 16 bytes as a partition table entry unit. That is, the first partition table entry describes the attributes of a partition, generally the primary partition. The second partition table entry describes the remaining space except the primary partition, generally speaking, it is the extended partition we call. The general description of this part is shown in Table 1.



Note: The data exceeding 1 byte in the above table is displayed as the actual data, that is, displayed in the way from high bit to low bit. When storing, it is stored from low bit to high bit. The two are different, please see clearly. The same applies to the tables and figures that appear later.

You can also see the meaning of these parameters in WinHex:



Explanation: Each partition table entry occupies 16 bytes. Assume that the offset address starts from 0. For example, partition table entry 3 in Figure 3. Partition table entry 4 is the same as partition table entry 3.

1. The offset 0H is the active partition flag, which can only be 00H and 80H. 80H is active, and 00H is inactive. Other values are illegal values for Microsoft.

2. Re-explain (this is very important): Numbers greater than 1 byte are stored in the little endian format, also known as the reverse byte order. The little endian format is a way to store numbers, so that the lowest byte appears first in the hexadecimal number symbol. For example, the value of the relative sector number field 0x3F000000 is represented as 0x0000003F in the little endian format. The decimal number of this little endian format number is 63.

3. When the system partitions, each partition is not allowed to cross cylinders, that is, all are in units of cylinders. This is the so-called partition granularity. Sometimes when we partition, we enter the partition size as 7000M, but it turns out to be 6997M. This is the reason. In the sector and cylinder parameters of offset 2H and offset 6H, the sector occupies 6 bits (bit), and the cylinder occupies 10 bits (bit). Taking offset 6H as an example, its low 6 bits are used as the binary representation of the number of sectors. Its high two bits are used as the high two bits of the 10-bit cylinder number, and the 8 bits composed of offset 7H are used as the low 8 bits of the 10-bit cylinder number. From this, it can be seen that the partition capacity represented in this way is limited. The cylinder and head are numbered starting from 0, and the sector is numbered starting from 1. So the maximum can only represent 1024 cylinders × 63 sectors × 256 heads × 512 bytes = 8455716864 bytes. That is, the usual 8.4GB (actually it should be about 7.8GB) limit. In fact, the number of heads is usually only used up to 255 (determined by the addressing register of the assembly language). Even if these 3 bytes are linearly addressed, it is still insufficient. In later operating systems, partitions exceeding 8.4GB are no longer addressed by the C/H/S method. Instead, the 4-byte 32-bit linear sector address from offset CH ~ offset FH is used to represent the total number of sectors occupied by the partition. It can be seen that 2^32 sectors can be represented by 4 bytes, that is, 2TB = 2048GB, which is an astronomical number for most computers at present. On partitions not exceeding 8.4GB, the representation methods of C/H/S and linear sectors represent the same partition size. That is, the two representation methods are coordinated. Even if they are not coordinated, the linear addressing is used as the standard. (There may be errors prompted in some systems). The end C/H/S of partitions exceeding 8.4GB is generally filled with FEH FFH FFH. That is, the maximum value that C/H/S can represent. Sometimes it is also filled with the modulo of the cylinder to 1024. However, what these bytes are actually is irrelevant.

Although current systems all use the linear addressing method to handle the partition size, the principle of not crossing cylinders remains unchanged. The total number of sectors of this partition plus the number of reserved sectors between it and the previous partition must still be an integer multiple of the cylinder capacity. (The first sector in the reserved sectors is the sector where the partition table is stored, MBR or virtual MBR. The total number of sectors of the partition is not counted in the reserved sectors in the linear representation method. If it is the first partition, the reserved sectors are all sectors before this partition.

Attachment: Partition table type flag is shown in Figure 4



#### 3.2 Extended Partition

Each logical drive in the extended partition has an extended boot record (Extended Boot Record, EBR) similar to the MBR, which is also called virtual MBR or extended MBR, meaning the same. The extended boot record includes an extended partition table and the label of this sector. The extended boot record will record the information of the first surface of the first cylinder of each logical drive in the extended partition. The boot sector in a logical drive is generally located at relative sector 32 or 63. However, if there is no extended partition on the disk, there will be no extended boot record and logical drives. The first item in the extended partition table of the first logical drive points to its own boot sector. The second item points to the EBR of the next logical drive. If there are no further logical drives, the second item will not be used and is recorded as a series of zeros. If there are additional logical drives, then the first item of the extended partition table of the second logical drive will point to its own boot sector. The second item of the extended partition table of the second logical drive points to the EBR of the next logical drive. The third and fourth items of the extended partition table are never used.

Through a disk structure diagram of 4 partitions, the general organization form of the disk can be seen. As shown in Figure 5:



Regarding the extended partition, as shown in Figure 6, the extended boot record of the logical drive in the extended partition is a connection table. This figure shows three logical drives on an extended partition, illustrating the differences in the extended partition table between the previous logical drive and the last logical drive.



Except for the last logical drive on the extended partition, the format of the extended partition table described in Table 2 is repeated in each logical drive: the first item identifies the boot sector of the logical drive itself, and the second item identifies the EBR of the next logical drive. The extended partition table of the last logical drive will only list its own partition item. The second to fourth items of the last extended partition table are used.



The relative sector number field in the extended partition table entry shows the number of bytes of the displacement from the start of the extended partition to the first sector in the logical drive. The number in the total sector number field refers to the number of sectors composing this logical drive. The value of the total sector number field is equal to the number of sectors from the boot sector defined by the extended partition table entry to the end of the logical drive.

Sometimes there will be remaining space at the end of the disk. What is the remaining space? We mentioned earlier that the partition takes the capacity of 1 cylinder as the partition granularity. So if the total space of the disk is not an integer number of cylinders, the remaining space that is less than one cylinder is the remaining space. This part of the space is not involved in partitioning, so it is generally not available. According to reason, the physical mode of the disk determines that the total capacity of the disk should be exactly an integer number of cylinder capacities. Why is there space less than one cylinder? In my understanding, originally, in order to make better use of space, the current disks are generally not managed in the way that the sectors on the outer circle are larger than those on the inner circle at present. It is just CHS abstracted to be compatible with the operating system. Maybe its actual space capacity is not exactly an integer number of cylinder capacities. Regarding this point, if you have any opinions, please inform http://www.sjhf.net or zymail@vip.sina.com

IV. Principle of FAT Partitions.

First, let's have a structure diagram:



Now we focus on studying how data is stored in FAT - formatted partitions. The FAT partition format is the partition format first supported by MICROSOFT. It is divided into three format "variants" of fat12, fat16, and fat32 according to the number of bits occupied by each cluster chain in the FAT table (related concepts will be discussed later), but their basic storage methods are similar.
Carefully study the composition structures of fat16 and fat32 partitions in Figure 7. The concepts of DBR, FAT1, FAT2, root directory, data area, and remaining sectors are explained in turn below. The addresses mentioned are all internal offsets of the partition unless otherwise specified.

4.1 About DBR.

The DBR area (DOS BOOT RECORD) means the operating system boot record area. It usually occupies the 0th sector of the partition, a total of 512 bytes (in special cases, it also occupies other reserved sectors. Let's first talk about the 0th sector). In these 512 bytes, it is actually composed of a jump instruction, a vendor flag and an operating system version number, BPB (BIOS Parameter Block), extended BPB, an operating system boot program, and an end flag. Take FAT32, which is used the most, to illustrate the meaning of each byte in the partition DBR. See Figure 8.



The corresponding explanation of Figure 8 is shown in Table 3



Figure 9 gives the relevant parameter explanation of the DBR in Figure 8 by WinHex:



According to the above illustrations, we will discuss the meaning of the parameters of each byte in the DBR.
The MBR transfers the CPU execution to the boot sector. Therefore, the first three bytes of the boot sector must be legal executable x86 CPU instructions. This is usually a jump instruction, which is responsible for skipping the next few non - executable bytes (BPB and extended BPB) and jumping to the operating system boot code part.
After the jump instruction is an 8 - byte long OEM ID, which is a string. The OEM ID identifies the name and version number of the operating system that formatted the partition. To maintain compatibility with MS - DOS, usually Windows 2000 records "MSDOS 5.0" in this field on FAT16 and FAT32 disks, and records "NTFS" on NTFS disks (about ntfs, which will be described separately). Usually, the OEM ID field appears as "MSWIN4.0" on disks formatted by Windows 95, and "MSWIN4.1" on disks formatted by Windows 95 OSR2 and Windows 98.
Next, starting from offset 0x0B is a section of information that enables the executable boot code to find relevant parameters. It is usually called BPB (BIOS Parameter Block). The BPB generally starts at the same displacement, so the standard parameters are all in a known position. Disk capacity and geometric structure variables are enclosed in the BPB. Since the first part of the boot sector is an x86 jump instruction. Therefore, the BPB can be extended by appending new information at the end of the BPB in the future. Only a small adjustment needs to be made to the jump instruction to adapt to the change of the BPB. Figure 9 has listed the names and values of the items. For systematic research, for Figure 8, the meanings of the BPB and extended BPB of the FAT32 partition format are interpreted as tables, see Table 4 and Table 5.



The data starting from offset 0x5A of the DBR is the operating system boot code. This is pointed to by the jump instruction starting from offset 0x00. The jump instruction "EB 58 90" listed in Figure 8 clearly indicates the offset position of the OS boot code. Adding the displacement required by the jump instruction to jump 58H means starting at 0x5A. The content of this section of instructions is different on different operating systems and different boot methods. Most materials say that the DBR of win98, win2000 built on the fat basic partition, and winxp only occupies the 0th sector of the basic partition. They mention that for fat32, generally only the 0th sector of the 32 basic partition reserved sectors is useful. In fact, if the operating system built on FAT32 is win98, the system will use the 0th sector and the 2nd sector of the basic partition to store the os boot code; if the operating system built on FAT32 is win2000 or winxp, the system will use the 0th sector and the 0xC sector of the basic partition (for win2000 or winxp, the position of 0xC is indicated by the offset 0xAB of the 0th sector) to store the os boot code. Therefore, on the fat32 partition format, if the content of the DBR sector is correct but the 2nd sector (win98 system) or the 0xC sector (win2000 or winxp system) is missing, the system will not be able to boot. If you manually set up NTLDR dual - system, you must know this.
The last two bytes of the DBR sector generally store the valid flag of the DBR with the value 0x55AA. For other values, the system will not execute the relevant instructions of the DBR. The other several sectors involved in os boot mentioned above also need to use 0x55AA as a legal end flag.

FAT16 DBR:
The meaning of DBR in FAT32 is roughly like this. For FAT12 and FAT16, their basic meanings are similar, but there are small differences in the relevant offsets and parameter meanings. The differences and causes of the FAT format will be mentioned later, and no more will be said about FAT12 and FAT16 here. I will list the sector parameter meanings of FAT16. Friends who are interested can study it by themselves, which is similar to FAT32.




4.2 About Reserved Sectors

At the offset 0x0E of the above - mentioned FAT file system DBR, the number of reserved sectors is stored in 2 bytes. The so - called reserved sectors (sometimes called system sectors, hidden sectors) refer to the sectors that are only owned by the system starting from the DBR sector of the partition, including the DBR sector. In the FAT16 file system, the data of the reserved sectors is usually set to 1, that is, only the DBR sector. In FAT32, the data of the reserved sectors is usually 32. Sometimes a FAT32 partition divided by Partition Magic will set 36 reserved sectors, and some tools may set 63 reserved sectors.
In FAT32, in addition to the 0th sector of the disk used as the DBR, the 2nd sector (win98 system) or the 0xC sector (win2000, winxp) used as the extended part of the OS boot code, the remaining sectors do not participate in the operating system management and disk data management, and are usually useless. The reason why the operating system sets reserved sectors in FAT32 is to back up the DBR or for future upgrades. In FAT32, the data at offset 0x34 of the DBR occupies 2 bytes and indicates where the DBR backup sector is located, which is generally 0x06, that is, the 6th sector. When the DBR sector of the FAT32 partition is damaged and the partition cannot be accessed, the data can be retrieved by replacing the 0th sector with the original backup of the 6th sector.

4.3 Storage Principles of FAT Tables and Data.

FAT table (File Allocation Table), which is a chain structure introduced by Microsoft in the FAT file system for disk data (file) indexing and positioning. If the disk is compared to a book, the FAT table can be considered as the table of contents in the book, and the file is the content of each chapter. But the representation method of the FAT table is very different from the directory.
In the FAT file system, the storage of files is carried out according to the cluster chain data structure formulated by the FAT table. At the same time, the directory used in organizing data in the FAT file system is also abstracted as a file to simplify the management of data.

★Imagination of the storage process:
We simulate the process of storing data in a partition to illustrate the storage principle in the FAT file system.
Suppose there is an empty disk with no data stored, with a size of 100KB. We imagine it as a linear space address. For the convenience of storage management, we artificially divide this 100KB space into 100 parts, each 1KB. Let's store the following several files in turn: A.TXT (size 10KB), B.TXT (size 53.6KB), C.TXT (size 20.5KB).
At least it can be thought that we can store these 3 files in sequence in this 100KB space. At the same time, don't forget that we also need to record their sizes and starting positions, so that we can find them next time, which is like a directory. For the convenience of searching, we assume that the first 1K of space is used to store their characteristics (attributes). Also, the storage unit we designed is 1KB, so A.TXT needs 10 storage units (for the convenience of explanation, we call the storage unit a "cluster". It can also save some typing, heh heh.). B.TXT needs 54 clusters, and C.TXT needs 21 clusters. Maybe someone will say that B.TXT and C.TXT each waste less than 1 cluster of space? Why not let them be adjacent to each other, isn't it space - saving? My answer is that if stored in this way, the directory originally only needs to record the cluster number, but now it also needs to record the offset within the cluster, which will increase the storage amount of the directory, and the access is not regular, and the reading is not very convenient, which is not worth the loss.
According to the above - mentioned idea, we designed the storage method shown in Figure 4.3.1.



Let's consider how to write the directory of these three files. For each file, what must be recorded are: file name, starting cluster, size, creation date/time, modification date/time, file read/write attributes, etc. Can the size be calculated by the end cluster? It must not be, because the size of the file is not necessarily an integer multiple of the cluster size. Otherwise, the content of B.TXT would be 54KB, which is not acceptable if it is less, but also not acceptable if it is more. So how do we record it? You can imagine it. For the convenience of management, we manage our directory in the way of database management. So I divide 1KB into 10 parts again, and assume that the starting cluster number is 0, and define the representative meaning of each position in each 100B as shown in Figure 4.3.2



The structure designed in this way can definitely correctly read and write files. Then let's make the file system we designed work. Let's change a file, for example, A.TXT, and add some content! Hey? Where to put it after adding? Although there is a lot of space behind the storage block, the data of B.TXT is still there! If we move A.TXT to the back, it is a waste of processing resources, and it may not solve the problem. This problem seems to be temporarily unsolvable.
Then let's change the operation, delete B.txt, and the space of b.txt is released. At this time, the space is shown in Figure 4.3.3, and the directory is shown in Figure 4.3.4



This operation seems okay. Let's continue to do it. Store a file D.txt (size 60.3KB). A total of 100 clusters of space only use 31 clusters, and there are 68 clusters remaining. According to reason, it can be put down. But? Where to put it? There are no 61 consecutive spaces, and the directory line can't be written. It seems that it is also not possible to store without continuous blocks.
You must be able to think that we can transfer other files that affect our operations when the continuous space is not enough or when the file length is increased, so as to free up space, but I want to ask you, isn't that all day long doing nothing but moving things?

It seems that the file system we designed has a fatal flaw. How to solve it?。。。。
。。。。。。

In fact, it can be solved in this way:
First, we allow files to be stored discontinuously. The directory still only records the starting cluster and the size of the file. Then how do we record which clusters the file occupies? It is not convenient to map the file with clusters because the file name is not fixed. We change our thinking. We can map files with clusters, and leave a few clusters at the front of the entire storage space to record the relationship between data in the data area and cluster numbers. For the above example, because the total space is not very large, so use the first 1K of space to record this correspondence. Assume that 3 files are all stored, and the space allocation is shown in Figure 4.3.5, and the directory is modified, as shown in Figure 4.3.6



The first cluster is used to record the occupied situation of each cluster in the data area, temporarily called the file allocation table. Combined with the file allocation table and the file directory, the complete file reading can be achieved. We thought that making the file allocation table into a data table, and recording the correspondence between clusters and data in the form shown in Figure 4.3.7.
　 The organization method in Figure 4.3.7 can completely realize the recording of the clusters occupied by the file. But it is not efficient enough. For example, the file name is recorded too much in the file allocation table, which wastes space. In fact, the start cluster of the file has been recorded in the directory. So it can be improved. The chain method is used to store the relationship of occupied clusters, and it becomes the organization method shown in Figure 4.3.8.



Refer to Figure 4.3.8 to understand the meaning of the file allocation table. For example, for file a.txt, according to the specified first cluster of a.txt in the directory entry is 2, then find the record of the 2nd cluster in the file allocation table, and the next cluster registered above is 3, so we can determine that the next cluster is 3. Find the record of the 3rd cluster in the file allocation table, and the next cluster registered above is 4, so we can determine that the next cluster is 4...... until we point to the 11th cluster and find that the next pointer is FF, which is the end. The file is read without error.

Let's look at the third situation mentioned above, that is, after deleting b.txt, store a d.txt with a size of 60.3KB. It can be easily realized by using the cluster chain. The realized disk is shown in Figure 4.3.9, 4.3.10, 4.3.11



The above is a hypothesis about file storage, and it is time to reveal the mystery. The above idea is actually the essence of the thought of the fat file system (but it is not, especially the meaning of specific parameters is completely different from the example we gave. Please forget the above details and try to remember the following).

★FAT16 Storage Principle:

When a part of the disk space is formatted into the FAT file system, the FAT file system plans this partition as a whole allocable area for data storage. Generally speaking, its division form is shown in Figure 7. We extract the FAT16 part and describe it in detail:

FAT16 is an earlier file system launched by Microsoft, with high compatibility. It is still widely used in personal computers, especially in mobile storage devices. Simply speaking, FAT16 is composed of 6 parts as shown in Figure 4.3.12 (mainly the first 5 parts). We have already talked about the boot sector (DBR). There are no reserved sectors left after DBR in FAT16, and the FAT table follows immediately. The FAT table is used by FAT16 to record the cluster chain structure of the disk data area. Just like the example we said before, the FAT divides the disk space into units of a certain number of sectors, and such a unit is called a cluster. Usually, the principle of 512 bytes per sector remains unchanged. The size of the cluster is generally 2n (n is an integer) sectors, such as 512B, 1K, 2K, 4K, 8K, 16K, 32K, 64K. In practice, it usually does not exceed 32K. The reason why the cluster is used as the unit instead of the sector for disk allocation is that when the partition capacity is large, using the sector management with a size of 512B will increase the number of items in the FAT table, increase the consumption for large file access, and the efficiency of the file system is not high. The size of the partition is related to the value of the cluster, see Table 9



Note: In partitions with less than 32680 sectors, the cluster space size can be up to 8 sectors per cluster. Whether the user uses the disk manager to format the partition or types the format command in the command prompt to format, the formatting program creates a 12-bit FAT. For partitions with less than 16MB, the system usually formats it into a 12-bit FAT. FAT12 is the initial implementation form of FAT, which is for small media. The FAT12 file allocation table is smaller than the FAT16 and FAT32 file allocation tables because it uses less space for each entry. This leaves more space for data. All 5.25-inch floppy disks formatted with FAT12 and 3.5-inch floppy disks with 1.44MB are formatted with FAT12. Except that the number of binary bits recording the cluster link in the FAT table is different from FAT16, the rest of the principles are the same as FAT16, and no separate explanation is given...

When formatting a FAT16 partition, the formatting program determines the size of the cluster according to the size of the partition, then determines the number of sectors required for the FAT table according to the number of reserved sectors, the number of sectors of the root directory, the number of clusters that can be divided in the data area, and the space occupied by the FAT table itself, and then writes the calculated result to the relevant position of the DBR.

The offset 0x11 of the FAT16 DBR parameter records the number of sectors occupied by the root directory. Offset 0x16 records the data of the number of sectors occupied by the FAT table. Offset 0x10 records the number of copies of the FAT table. After the system obtains these parameters, it can determine the start sector offset of the data area.

The FAT16 file system processes data in clusters starting from the first sector after the 32 sectors occupied by the root directory, and still uses sectors as the unit before that. For the first cluster after the root directory, the system does not number it as cluster 0 or cluster 1 (probably because it is reserved for keywords), but numbers it as cluster 2, that is, the first cluster in the data area order is also cluster 2 in numbering.

The reason why the FAT file system has different versions of 12, 16, and 32 lies in the number of binary bits used by the FAT table to record the link of any cluster. Taking FAT16 as an example, each cluster occupies 2 bytes (16 binary bits) in the FAT table. Therefore, the maximum cluster number that FAT16 can represent is 0xFFFF (65535 in decimal). If the cluster size is 32K, the maximum disk space that FAT32 can manage is: 32KB × 65535 = 2048MB, which is why FAT16 does not support partitions larger than 2GB.

The FAT table is actually a data table, with 2 bytes as a unit. We temporarily call this unit a FAT record entry. Usually, the first and second record entries (the first 4 bytes) are used as the media description. Starting from the third record entry, the cluster chain conditions of other files and folders except the root directory are recorded. According to the performance of the cluster, FAT uses corresponding values to describe it, see Table 10



Look at a FAT16 file allocation table intercepted in WinHex, Figure 10:



As shown in the figure, the FAT table starts with "F8 FF FF FF", and these 2 bytes are the media description unit, which does not participate in the cluster chain relationship of the FAT table. The small red characters mark the cluster number corresponding to each 2 bytes in the FAT sector.

The relative offset 0x4~0x5 is cluster 2 (the first cluster in order), where it is FF, indicating that the file (directory) stored in cluster 2 is a small file and ends with only 1 cluster.

The data stored in cluster 3 is 0x0005, which is the first cluster of a file or folder. Its content is cluster 5, which means that the next cluster is in cluster 5 → The FAT table guides us to the cluster 5 pointer in the FAT table, and the data written above is "FF FF", meaning that this file has reached the end cluster.

The data stored in cluster 4 is 0x0006, which is the first cluster of another file or folder. Its content is cluster 6, which means that the next cluster is in cluster 6 → The FAT table guides us to the cluster 6 pointer in the FAT table, and the data written above is 0x0007, which means that the next cluster is in cluster 7 → The FAT table guides us to the cluster 7 pointer in the FAT table... until we read to the relative offset 0x1A~0x1B of the sector, which is cluster 13, and the data written above is 0x000E, which means pointing to cluster 14 → The content of cluster 14 is "FF FF", meaning that this file has reached the end cluster.

The subsequent FAT table data is the same as the above principle. No more analysis.

The FAT table records the storage linked list of disk data files, which is extremely important for data reading. So much so that Microsoft created a backup for the FAT table in the FAT file system it developed, which is FAT2. The content of FAT2 and FAT1 is usually synchronized in real time, that is, if changes are made to FAT1 through normal system reading and writing, FAT2 is also updated. From this perspective, this function of the system is a natural disaster during data recovery.

The directory structure of the FAT file system is actually a directed tree from the root to the leaves. The directed here means that for any file (including folders) in the FAT partition, it needs to be addressed from the root directory to find it. It can be considered that the entrance of the directory storage structure is the root directory.

The FAT file system addresses other files (including folders) according to the root directory, so the position of the root directory must be determined before the disk accesses data. The FAT file system determines it according to the relevant DBR parameters of the partition and the size of the FAT table (two copies) stored in the DBR. After formatting, the size and position of the root directory are actually determined: the position follows FAT2, and the size is usually 32 sectors. After the root directory is the second cluster of the data area.

An important idea of the FAT file system is to treat the directory (folder) as a special file. FAT32 even treats the root directory as a file (by the way: NTFS abstracts many things such as partition parameters and security permissions as files, which is an elevation of this idea). In FAT16, although the status of the root directory is not equivalent to an ordinary file or directory, its organization form is not different from an ordinary directory (folder). All folder (directory) files in the FAT partition can actually be regarded as a data table that stores the entry parameters of other files (folders). Therefore, the size of the space occupied by the directory is not equivalent to the size of all data under it, but is not equivalent to 0. It usually occupies a very small space and can be regarded as the directory file is a simple two-dimensional table file. Its specific storage principle is:

No matter how many clusters the directory file occupies and how many bytes per cluster, the system will allocate the clusters occupied by the directory file in units of 32 bytes. These 32 bytes define the attributes of a file (or folder) under this directory with a determined offset, which is actually a simple two-dimensional table.

The offsets of each byte of these 32 bytes are defined as shown in Table 11:



Some values in Table 11 are explained:

(1) For the short file name, the system stores the file name in two parts, that is, the main file name + extension. The 0x0~0x7 bytes record the main file name of the file, 0x8~0xA record the extension, and take the ASCII code value in the file name. The "." between the main file name and the extension is not recorded. The main file name is filled with blanks (20H) if it is less than 8 characters, and the extension is also filled with blanks (20H) if it is less than 3 characters. If the value at offset 0x0 is 00H, it means the directory entry is empty; if it is E5H, it means the directory entry has been used, but the corresponding file or folder has been deleted. (This is also the theoretical basis for undelete recovery). If the first character in the file name is "." or "..", it means that this cluster record is a directory entry of a subdirectory. "." represents the current directory; ".." represents the parent directory (the same meaning as in dos or windows. If the disk data is damaged, you can calculate the start position of the data area of the disk and guess the size of the cluster through the specific parameters of these two directory entries, so it is relatively important)

(2) The attribute field of 0xB: It can be regarded as the system dividing a byte of 0xB into 8 bits, and using one of the bits to represent the presence or absence of a certain attribute. In this way, each bit in the 8 bits of a byte can reflect the different values of each attribute. For example, 00000101 means this is a file, and the attributes are read-only and system.

(3) 0xC~0x15 are reserved and unused in the original FAT16 definition. In high-version WINDOWS systems, it is sometimes used to record the modification time and recent access time. In this case, the meaning of the field is the same as that of FAT32, see the following FAT32.

(4) The time in 0x16~0x17 = hour * 2048 + minute * 32 + second / 2. The result is converted into hexadecimal and filled in. That is: the 0~4 bits of the 0x16 byte are the value in units of 2 seconds; the 5~7 bits of the 0x16 byte and the 0~2 bits of the 0x17 byte are minutes; the 3~7 bits of the 0x17 byte are hours.

(5) The date in 0x18~0x19 = (year - 1980) * 512 + month * 32 + day. The result is converted into hexadecimal and filled in. That is: the 0~4 bits of the 0x18 byte are the date number; the 5~7 bits of the 0x18 byte and the 0 bit of the 0x19 byte are the month; the 1~7 bits of the 0x19 byte are the year number. In the original definition, 0~119 represent 1980~2099, and current high-version Windows allows 0~127, that is, the year number can be up to 2107.

(6) 0x1A~0x1B store the first cluster number representing the file or directory. The system finds the entry in the FAT table according to the master cluster number it has, then tracks the cluster chain until the end of the cluster, and uses the bytes at 0x1C~0x1F to determine validity, and then can read the file (directory) without error.

(7) The addressing process of the ordinary subdirectory is also specified by the directory entry in its parent directory. Different from the data file (referring to the non-directory file), the 4th position of offset 0xB of the directory entry is set to 1, and the data file is 0.

For the entire FAT partition, the allocation of clusters is not always completely clean. For example, in a FAT system with a data area of 99 sectors, if the cluster size is set to 2 sectors, there will be 1 sector that cannot be allocated to any cluster. This is the remaining sector of the partition, located at the end of the partition. Some systems use the last remaining sector to back up the DBR of this partition, which is also a good backup method.

The early FAT16 system did not have long file names. The Windows operating system has fully supported long file names on FAT16. The definition of long file names in FAT16 is the same as that in FAT32. The detailed explanation of long file names will be given in the FAT32 part.

★FAT32 Storage Principle:

FAT32 is a very meritorious file system. Microsoft successfully designed and applied it. Until today, when NTFS is overwhelming, FAT32 still occupies an important position in the Microsoft Windows file system. FAT32 was originally designed for the shortcomings of FAT16 such as not supporting large partitions and large unit cluster capacity leading to rapid space waste. In practical applications, FAT32 is still successful.

The principle of FAT32 is basically the same as that of FAT16. Figure 4.3.13 marks the basic composition of the FAT32 partition.



During the formatting process of FAT32, it builds its DBR according to the characteristics of the partition. The BPB parameters are very important. You can look back at Table 4 and Table 5. First, the number of reserved sectors in FAT32 is 32 by default, instead of just one in FAT16. The advantage of this is that it helps to extend the length of the disk DBR instruction and can leave backup space for the DBR sector. As we mentioned above, the operating system boot code built on FAT32, such as Win98 or Win2000, WinXP, does not only occupy one sector. Having extra reserved sectors can well expand the OS boot code. The BPB also records the backup sector number of the DBR sector. The backup sector can help us restore the DBR when the disk is accidentally damaged.

The data structure of the file allocation table of FAT32 is still the same as that of FAT16. The difference is that FAT32 extends the number of binary bits recording the cluster chain to 32 bits, so this file system is called FAT32. The cluster chain of 32-bit binary bits determines that the FAT table can address up to 2T clusters at most. In this way, even if the cluster size is 1 sector, theoretically, it can still address partitions within 1TB. But in practice, FAT32 cannot address such a large space. As the partition space increases, the number of records in the FAT table will become cumbersome, which seriously affects the performance of the system. Therefore, in practice, FAT32 partitions larger than 32GB are usually not formatted. OS above WIN2000 does not directly support formatting partitions larger than 32GB into FAT32, but WIN98 can still format FAT32 partitions as large as 127GB, but this is unnecessary and not recommended. At the same time, FAT32 also has a small limit. The FAT32 volume must have at least 65527 clusters. Therefore, for small partitions, FAT16 or FAT12 is still needed.

When the partition becomes larger, if the cluster is very small, the file allocation table will also become larger. The above efficiency problem still exists. To effectively read and write large files and minimize space waste as much as possible, FAT32 also specifies the corresponding cluster size for the corresponding partition space, see Table 12:



The meaning of the cluster value in FAT32 is similar to that in FAT16, but the number of bits is longer. For comparison, see Table 13:

Another major reform of FAT32 is the fileization of the root directory, that is, the root directory is equivalent to an ordinary file. In this way, the root directory is not limited by 512 directory entries in FAT16. When it is not enough, increase the cluster chain and allocate empty clusters. Moreover, the position of the root directory is no longer rigidly fixed and can be stored in any addressable cluster in the partition. However, the root directory is usually the earliest created (formatted) directory table. Therefore, the situation we see is basically that the first cluster of the root directory occupies the first cluster in the cluster area order. It is also drawn according to this situation in Figure 4.3.12.

The numbering of clusters in FAT32 is still the same as in FAT16. The first cluster in order is still numbered as cluster 2, which is usually used by the root directory (this is different from FAT16. The root directory of FAT16 does not occupy the cluster area space. The first cluster in the cluster area is after 32 sectors of the root directory)

The file addressing method in FAT32 is the same as in FAT16, but the meaning of each byte parameter in the directory entry is different from that in FAT16. On the one hand, it enables the reserved fields of the directory entry in FAT16, and at the same time fully supports long file names.

For the directory entry in the short file format. Its parameter meaning is shown in Table 14:



Instructions:

(1) This is the meaning of the directory entry in the FAT32 short file format. The algorithms for the file name, extension, time, and date are the same as in FAT16.

(2) Since the cluster number that FAT32 can address reaches 32-bit binary numbers. Therefore, when recording the start cluster address of the file (folder), the system also needs 32 bits to record. FAT32 enables the offset 0x12~0x13 of the directory entry to represent the high 16 bits of the start cluster number.

(3) The file length is still represented by 4 bytes, which means that FAT32 still only supports files (directories) smaller than 4GB. For files (directories) larger than 4GB, the system will truncate them.

An important feature of FAT32 is that it fully supports long file names. Long file names are still recorded in the directory entry. In order for low-version OS or programs to correctly read long file name files, the system automatically creates a corresponding short file name for all long file name files, so that the corresponding data can be addressed by both the long file name and the short file name. OS or programs that do not support long file names will ignore the long file name fields that they think are illegal, while OS or programs that support long file names will record and edit with the long file name as the explicit item and hide the short file name.

When creating a long file name file, the system will automatically add the corresponding short file name. The general principles are:

(1) Take the first 6 characters of the long file name plus "~1" to form the short file name, and the extension remains unchanged.

(2) If this file name already exists, the number after "~" is incremented until 5.

(3) If the number after "~" in the file name reaches 5, the short file name only uses the first two letters of the long file name. Generate the last four letters of the short file name by mathematically manipulating the remaining letters of the long file name, then add the suffix "~1" until the end (if necessary, or other numbers to avoid duplicate file names).

(4) If there are characters that cannot be read by old OS or programs, replace them with "_"

The realization of long file names depends on the attribute byte of offset 0xB of the directory entry. When the attribute of this byte is: read-only, hidden, system, volume label, that is, its value is 0FH, DOS and WIN32 will consider it illegal and ignore its existence. This is the basis for the existence of long file names. Set 0xB of the directory entry to 0F, and the rest is left to the system to define. Windows9x or Windows 2000, XP usually support long file names not exceeding 255 characters. The system cuts the long file name in units of 13 characters, and each group occupies one directory entry. Therefore, a file may need multiple directory entries. At this time, the directory entries of the long file name are arranged in reverse order in the directory table to prevent confusion with other file names.

The characters in the long file name are encoded in unicode form (a great progress), and each character occupies 2 bytes of space. Its directory entry definition is shown in Table 15.



When the system stores the long file name, it always fills the long file name directory entry in reverse order first, and then follows its corresponding short file name. As can be seen from Table 15, the long file name does not store the start cluster of the corresponding file, the file size, various time and date attributes. These attributes of the file are still stored in the short file name directory entry. A long file name always corresponds to its corresponding short file name one by one. The short file name can still be read without the long file name, but if the long file name does not have a corresponding short file name, no matter what system, it will be ignored. Therefore, the short file name is very important. Changing (including deleting, because deleting is to rewrite the first character to E5H) the file name and extension fields in the short file name in an environment that does not support long file names will make the long file name ineffective. The connection between the long file name and the short file name is obviously not enough to rely solely on their positional relationship. In fact, the checksum of the 0xD byte of the long file name plays a very important role. This checksum is obtained by a calculation method using the 11 characters of the short file name. The system determines whether the corresponding long file name and short file name match according to the corresponding algorithm. This algorithm is not easy to explain with a formula. We use a section of C program to illustrate it.

Assume that the file name is composed of 11 characters to form the string shortname, and the checksum is represented by chknum. The process is as follows:

int i, j, chknum = 0;
for (i = 11; i > 0; i--)
chksum = ((chksum & 1) ? 0x80 : 0) + (chksum >> 1) + shortname;

If the checksum calculated from the short file name is not equal to the data at offset 0xD in the long file name, the system will never match them.

According to the definition of the directory entry for the long file name and the short file name, and the numbering and linking of clusters, the data reading on FAT32 is easy.

V. End.

This article is from the Data Recovery Network (www.sjhf.net). Omissions are inevitable. I hope to be corrected. If you need to reprint, please keep this information; if you need to modify, please contact the author in the following ways
1、http://www.sjhf.net
2、zymail@vip.sina.com

Why can't the picture be displayed?

The article is relatively long, with approximately 45,000 characters. Therefore, I added a table of contents and internal links in the original text. You can download it at http://www.sjhf.net/bbs.

In addition, since it's not easy to post tables in the forum, I replaced the tables with pictures when posting in the forum, but the tables are still in the original text.

Bump!

Recommend everyone to go to www.sjhf.net to have a look

Push it up!!! Hehe

Nice post.

Although it's very long, it must be a good article... Long long long...

It's really good. There are new gains again. Strongly recommend

Thanks for the explanation~

Collected!

A bit longer, very good.

The images don't display.