# Training Mission 2
###### tags: `PHISON 訓練課程` `7/13` `3-Day`

## Request
### Study the structure of MBR, FAT16/FAT32 and exFAT

---
# Note

## MBR （Master Boot Record）

### MBR 介紹
**MBR為Master Boot Record（主開機記錄）的縮寫**，它是IBM公司在1983年提出的分割表格式（Partition Table）。是位於硬碟開始部分的一個特殊磁區（Cylinder-0，Head-0，Sector-1），磁區內部包含**已安裝系統的啟動載入器**以及**硬碟內邏輯分割區的資訊**。在啟動Windows時，會從磁區內使用一段代碼來啟動系統，因此如果MBR的啟動資訊損壞，Windows就無法正常啟動。

MBR最多只能分割出4個磁碟分割區（Primary Partition），在MBR分割區表中，一個分割區最大的容量為2TB，且每個分割區的起始柱面必須在這個disk的前2TB內，$2^{32}（個磁區，見磁碟分割區表）$ x $512（Bytes/磁區）=2$ TB，但皆可藉由特殊設定提高，見[MBR & GPT Partition Table](https://www.youtube.com/watch?v=ZOjicsRClic&list=PL1l78n6W8zyoZx3mMUyeOuczV_zWRM12J&index=1)。

> 由於MBR中只包含64 Bytes的主要磁碟分割區，故最多只能分割出4個主要磁碟分割區，若要分割出更多主要磁碟分割區則需引入*擴充分割區*。

> 另外的Partition Table還有GPT，最多可分割出超過128個主要磁碟分割區，分割區容量支援可達ZettaByte，但相容性較差，例如需要UEFI、64位元系統等。

### MBR 組成 （32-bit）
==MBR為開機後所讀取的首個磁區==，故共有512 Bytes，其中前446 Bytes為Master Boot Code或稱Bootstrap Code Area，接著是4個16 Bytes的磁碟分割區表（DPT，Disk Partition Table），最後再加上2 Bytes的結束標誌（0x55AA）。
> 對於硬碟而言，一個磁區可能的位元組數為128×2n（n=0,1,2,3）。大多情況下，取n=2，即一個磁區（sector）的大小為512位元組。


### 磁碟分割區表 （Partition Table）

硬碟分割區表占據主啟動磁區的64個位元組（0x01BE~0x01FD），可以對四個分割區的資訊進行描述，其中每個分割區的資訊占據16個位元組。具體每個位元組的定義可以參見硬碟分割區結構資訊。

##  如果某一分割區在硬碟分割區表的資訊如下
80 01 01 00 0B FE BF FC 3F 00 00 00 7E 86 BB 00

"80"是一個分割區的啟用標誌，表示系統可啟動。
"01 01 00"表示分割區開始的磁頭號為1，開始的磁區號為1，開始的柱面號為0。
"0B"表示分割區的系統類型是FAT32，其他比較常用的有04（FAT16）、07（NTFS）。
"FE BF FC"表示分割區結束的磁頭號為254，結束的磁區號為63、結束的柱面號為764。
"3F 00 00 00"表示首磁區的相對磁區號為63。
"7E 86 BB 00"表示總磁區數為12289662。


> Partition type為檔案系統標誌，"0B"表示FAT32，"04"表示FAT16，"07"表示NTFS。

> LBA為Logic Block Address，LBA可以意指某個資料區塊的位址或是某個位址所指向的資料區塊。對於空間大於8.4G的硬碟，傳統CHS已無法表示，對於超出的部分則使用LBA來轉換描述。

### 磁碟資料分配示意圖

## FAT 12/16/32 （File Allocation Table）

### FAT 介紹
File Allocation Table是一個被發展出來應用於個人電腦的檔案系統，其相容性極高，同時支援個人電腦、移動式裝置、嵌入式系統等，也能支援不同系統間的檔案交換，衍伸版本有FAT12、FAT16、FAT32、exFAT等（根據FAT中元素bit數來命名）。

### FAT 概念
- **<font color="#2F94E0">將檔案或資料透過Linked List的方式串聯在一起</font>**，並設置一個檔案配置表（File Allocation Table），透過查表來讀取下一筆資料。
- **<font color="#056F0A">檔案配置表（File Allocation Table）</font>**，元素包含此空間是否使用（Busy）、下一個指向的空間編號（Next），其中編號$（-1）$代表為串列節點的最後一個元素。
- 上述做法單純將同個檔案的資料連結在一起，但卻無法知道串列節點的起始位置，因此必須再引入 **<font color="#C46404">路徑表（Directory Table Format）</font>**。
- **<font color="#C46404">路徑表（Directory Table Format）</font>**，元素包含檔案名稱、起始位置及其他與檔案相關的資料（例如：權限），圖中顯示由/root開始搜尋，找到/foo，才能找到File.txt（/root/foo/File.txt）。

> 圖片來源：
> - https://www.youtube.com/watch?v=V2Gxqv3bJCk
> - https://www.youtube.com/watch?v=mgQtlXBxH0c
:::warning
**結論：**
- **檔案配置表**將==cluster連結在一起==。
- **路徑表**負責處理==路徑階層==及==檔案起始方塊==。

**優點：**
- 不會有記憶體破碎的問題（External Fragmentation），空間使用效率較高，cluster切越小越高。

**缺點：**
- 若要讀取中心方塊或結束方塊，則必須從頭讀到尾，Ramdom Access效率較差。
:::

### FAT 12
==FAT12中的每個cluster address皆以12位元來表示==，因此每個分割區的最大cluster數量也被限制在$2^{12}-reserved=4078$，每個cluster的大小為4096 Bytes（$2^{12}$），因此硬碟容量可達16MB，且為了節省空間，12位元的FAT元素會兩兩成群，並使用3個連續的8位元空間來儲存，對於磁碟（floppy disk）及32MB以下的小型裝置是足夠的。
> $reserved$ 是保留來為了其他用途，例如：資料鏈的結束標記、標記磁碟中尚未使用的區塊，或是其他用途等等。

### Initial FAT 16
==在初始的FAT16中，每個cluster address皆改以16位元來表示==，因此每個分割區的最大cluster數量也提高到了$2^{16}-reserved=65524$（一個cluster大小為512 Bytes），但是最大分割區容量為32MB依然沒有改善，**優點則是使用了更小的cluster，使空間運用效率更高**。

### Final FAT 16
在後來的FAT16中，每個cluster的空間可達到32KB（但是很浪費空間），因此每個分割區的容量可達到$65536（2^{16}個cluster）*32KB（每個cluster空間）=2GB$，如下表：
|最大分割區容量|cluster大小|
|:---:|:---:|
|32MB|512B|
|64MB|1KB|
|128MB|2KB|
|256MB|4KB|
|512MB|8KB|
|1GB|16KB|
|2GB|32KB|

### FAT 32
為了克服FAT16的分割區容量限制問題，==FAT32中的每個cluster address皆使用32位元來表示，目前使用到28個位元數==，因此若將cluster大小維持在512 Bytes，分割區容量仍可達到$2^{32}（個cluster）*512 Bytes（每個cluster空間）=2TB$，與FAT16相比同時提高了分割區容量限制、空間使用效率。

### FAT 12/16/32 整理表格
||FAT 12|FAT 16|FAT 32|
|:---:|:---:|:---:|:---:|
|最大分割區容量|32 MB|2 GB|2 TB|
|最大檔案數量 （最大cluster數）|$2^{12}-19$|$2^{16}-19$|$2^{28}-19$|
|最大檔案大小|32 MB|2 GB|4 GB|

## FAT 主磁碟結構
### FAT 主磁碟結構

**一個FAT檔案系統包括四個不同的部分。**
1. **<font color="#E01E2C">保留磁區</font>**。第一個保留磁區是啟動磁區（Boot Sector/Volume Boot Record），包括一個稱為基本輸入輸出參數塊的區域（包括一些基本的檔案系統資訊尤其是它的類型和其它指向其它磁區的指標），通常包括作業系統的啟動呼叫代碼。保留磁區的總數記錄在啟動磁區中的一個參數中。
> 詳細格式、位元偏移、說明，請見[保留磁區](https://zh.wikipedia.org/wiki/%E6%AA%94%E6%A1%88%E9%85%8D%E7%BD%AE%E8%A1%A8)。
2. **<font color="#1E5AE0">FAT區域</font>**，紀錄cluster是如何儲存的。此區塊包含有兩份完全相同的檔案配置表（第二份是備份用），但很少使用，即使是磁碟修復工具也很少使用它。
|FAT12|FAT16|FAT32|說明|
|:---:|:---:|:---:|:---|
|0x000|0x0000|0x?0000000|Unused cluster|
|0x001|0x0001|0x?0000001|Reserved cluster|
|0x002 ~ 0xFEF|0x0002 ~ 0xFFEF|0x?0000002 ~ 0x?FFFFFEF|Used cluster, point to next cluster|
|0xFF0 ~ 0xFF6|0xFFF0 ~ 0xFFF6|0x?FFFFFF0 ~ 0x?FFFFFF6|Reserved value|
|0xFF7|0xFFF7|0x?FFFFFF7|Bad cluster|
|0xFF8 ~ 0xFFF|0xFFF8 ~ 0xFFFF|0x?FFFFFF8 ~ 0x?FFFFFFF|Last cluster|


3. **<font color="#C46404">根目錄區域</font>**，是在根目錄中儲存檔案和目錄資訊的目錄表，包含名字、副檔名、屬性（檔案、目錄、隱藏、唯讀）、建立的日期和時間...等等。在FAT32下它可以存在<font color="#2FE024">資料區域</font>中的任何位置，但是在早期的版本中通常跟FAT12/16一樣接在<font color="#1E5AE0">FAT區域</font>之後。
==目錄元素（Directory Entry，32 Bytes）如下：==

> 詳細格式、位元偏移、說明，請見[目錄表](https://zh.wikipedia.org/wiki/%E6%AA%94%E6%A1%88%E9%85%8D%E7%BD%AE%E8%A1%A8)。

4. **<font color="#2FE024">資料區域</font>**，是實際的檔案和目錄資料儲存的區域，占據分割區的絕大部分。通過簡單地在FAT中添加檔案連結的個數可以任意增加檔案大小和子目錄個數。每個檔案都需要佔有至少一個cluster，因此如果在32KB大小的cluster中只有一個1KB大小的檔案，那麼31KB的空間就浪費掉了。

## exFAT （Extended File Allocation Table）
### exFAT 介紹
==exFAT（Extended File Allocation Table），是微軟公司（Microsoft）開發的一種較適合於快閃記憶體（Flash Memory）的檔案系統==。由於FAT32檔案系統有單一檔案大小不能超過4GB的限制，在無法使用NTFS的情況下，exFAT將是最佳的解決方案。

### exFAT 特色
- 可拓展至更大磁碟大小，理論上可達64ZiB，推薦最大512TiB，相較32位元限制的FAT32分割區的2TB（每磁區512 Bytes）。
- 單一路徑檔案數量限制達到2,796,202個，Windows對FAT32的檔案限制為$2^{16}$左右，其他OS則無限制。
- 分割區最大檔案數量限制達$2^{32}$個左右，而FAT32則為$2^{28}$個。
- 單一檔案檔案大小限制達到$2^{64} - 1$ Bytes，而FAT32檔案系統中單一檔案限制大小為$2^{32} - 1$ Bytes（4 GB）。對於單檔超過4 GB的使用者來說，exFAT提供了很好的解決方案。
- Cluster大小最大可達到32 MB。
- 採用了空餘空間尋址(Free-Space Bitmaps)，空間分配和刪除的效率更高。
> 其餘特色可詳見[exFAT Features](https://en.wikipedia.org/wiki/ExFAT)。

|Features|FAT32|exFAT|
|:---|:---:|:---:|
|Maximum Volume Size|8 TB|128 PB|
|Maximum File Size|4 GB|16 EB|
|Maximum Cluster Size|32 KB|32 MB|
|Maximum Cluster Count|228|232|
|Maximum File Name Length|255|255|
|Date/Time resolution|2 s|10 ms|
|MBR Partition Type Identifier|0x0B, 0x0C|0x07|

## exFAT 主磁碟結構

### Boot Sector
Boot Sector中紀錄所有啟動硬碟所需要的參數，包含：分割區偏移（PartitionOffset）、分割區大小（VolumeLength）、FAT偏移（FatOffset）...等等，格式及說明可見[Boot Sector](http://elm-chan.org/docs/exfat_e.html)

### Extended Boot Sector
Extended Boot Sector是Boot Sector的延伸，除了最後4個Bytes是作為結束標記之外（0x55AA0000），其他空間皆可用來記錄Boot code資料。

### OEM Parameters
儲存OEM參數，詳見[OEM Parameters & OEM Parameter Record](https://www.ntfs.com/exfat-OEM-parameters.htm)

### Checksum
Checksum會重複計算前11個磁區（sector）的32位元資料，計算時間則取決於sector大小。

UNIT32 BootChecksum(const unsigned char data[], int bytes)
{
    UINT32 checksum   =   0; 
    for (inti = 0; i < bytes; i++)
    {
        if (i == 106 || i == 107 || i == 112)
            continue;
        checksum = (checksum << 31) | (checksum >> 1) + data[i];
    }
    return checksum;
}

### FAT Region
跟FAT32相同，exFAT的第一個cluster從 0x00000002 開始，由於在exFAT中，所有32位元都被拿來表示cluster address，為了表示cluster的使用狀態（used/free），==exFAT另外引入了Allocation Bitmap==，以1個位元1/0來表示cluster的使用狀態，詳見下表：
|Bitmap|exFAT|Cluster Status|
|:---:|:---:|:---:|
|0|0x00000000|Free|
|1|0x00000001|Reserved|
|1|0x00000002 ~ ClusterCount+1|In-use（value is linked to next）|
|1|ClusterCount+1 ~ 0xFFFFFFF6|Reserved|
|1|0xFFFFFFF7|Bad cluster|
|1|0xFFFFFFF8 ~ 0xFFFFFFFE|Reserved|
|1|0xFFFFFFFF|In-use（end of chain）|

### Allocation Bitmap
==Allocation Bitmap位於Data Region中，其cluster位置與Size則視為一個特殊的目錄元素（Directory Entry）記錄在根目錄（Root Directory）中==，由許多8-bit元素組成（可被視為一連串的位元），其中每個位元皆對應至一個Cluster。

> $Allocation Bitmap Size=（ClusterCount+7）/ 8$

### Up-case Table
Up-case Table是用來將英文字母全部轉換為大寫字母的對照表（其他字符保持不變），通常會緊鄰在Allocation Bitmap後面，同樣視為一個特殊的目錄元素（Directory Entry），並記錄在根目錄（Root Directory）中。

### Directory Entry
根目錄（Root Directory）儲存在資料區域中（Data Area），每個目錄元素（Directory Entry）的大小則跟FAT32一樣為==32 Bytes==，最長的路徑可達256 MB（8M entries，FAT32是2M），==第一個Bytes（又稱EntryType Byte）定義此元素的類別如下：==
|Field|Meaning|
|:---:|:---:|
|In-Use（bit 7）|0：Free entry，1：Entry is in-use|
|TypeCategory（bit 6）|0：Primary entry，1：Secondary entry attached to primary entry|
|TypeImportance（bit 5）| 0：Critcal entry，1：Benign entry|
|TypeCode（bit 4~0）|0~31：Type code|

|EntryByte|Description|
|:---|:---|
|0x81|Allocation bitmap|
|0x82|Up-case table|
|0x83|Volume label|
|0x85| File and directory（file attribute and timestamp）|
|0xC0|Stream extension（file allocation information）|
|0xC1|File name（name of the file）|
|0xC2|Windows CE access control list|
|0xA0| Volume GUID|
|0xA1| TexFAT Padding|
|0xA2|Windows CE access control table|
> 在exFAT中，若要刪除一個Entry，只需直接將Bit 7設為0。
> FAT則須將整個EntryType Byte設為0xE5。

> 上表中所有類型的元素，詳細格式定義可見[Directory Entry](http://elm-chan.org/docs/exfat_e.html)。

### Directory Operations
:::success
**Creating File**
- 先找一塊空的Directory Entries並創造一個Entry Set，設定Entry Set有`Archive`（存檔屬性）且`DataLength`初始化為 0，`AllocationPossible Bit`設為1，`NoFatChain`設為0。
- 寫進資料並配置一個新的Cluster，此Cluster編號將被設為`FirstCluster`，`NoFatChain`設為1：
- 如果Cluster一直是連續的，則不會更新到FAT Entry上。
- 如果出現不連續的Cluster，則`NoFatChain`將設為0，並更新新的Cluster位置到FAT上。
> 只有File、Sub-Directory會這樣，其他資料如Root Directory、Allocation Bitmap、Up-Case Table則會詳細記錄cluster chain到FAT上。
:::
:::info
**Creating Sub-Directory**
- 先找一塊空的Directory Entries並創造一個Entry Set，設定Entry Set有`Directory`（目錄屬性）並將內部所有Entries都初始化為0，且`NoFatChain`設為0（`NoFatChain`的操作跟File相同）。
- 若塞滿了就再重複上述動作，目錄的最長長度可達256 MB（8M Entries）。
:::
:::warning
**Deleting File**
- 刪除檔案，需要將檔案所有Entry中的In-Use（bit 7）設為 0，並在FAT中刪掉Cluster Chain（將對應的 Bitmap 改成 0 即可，不用動FAT Entry）。
:::
:::danger
**Deleting Sub-Directory**
- 刪除子目錄則須將目錄下的所有Node都做一遍Deleting File的動作，須注意要從最下面開始刪，不然上層的Cluster會壞掉（找不到Next Cluster/End Cluster）。
:::

# 參考連結
- [MBR wiki（ch）](https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%BC%95%E5%AF%BC%E8%AE%B0%E5%BD%95)
- [MBR wiki（en）](https://en.wikipedia.org/wiki/Master_boot_record)
- [DataCadamia](https://datacadamia.com/data_storage/mbr)
- [FAT wiki（ch）](https://zh.wikipedia.org/wiki/%E6%AA%94%E6%A1%88%E9%85%8D%E7%BD%AE%E8%A1%A8)
- [FAT wiki（en）](https://en.wikipedia.org/wiki/File_Allocation_Table)
- [Difference Between FAT32, exFAT and NTFS](https://www.youtube.com/watch?v=rz4cj1nO_kU)
- **[Paul's 8051 Code Library](https://www.pjrc.com/tech/8051/ide/fat32.html)**
- [FAT 16 structure explained](https://www.youtube.com/watch?v=DITMdLALZao)
- [Active File Recovery](https://www.file-recovery.com/recovery-understanding-file-system-fat.htm)
- [exFAT(ch)](https://zh.wikipedia.org/wiki/ExFAT)
- [exFAT(en)](https://en.wikipedia.org/wiki/ExFAT)
- **[NTFS.com(exFAT)](https://www.ntfs.com/exfat-overview.htm)**
- [NTFS vs FAT32 vs exFAT - Everything You Need To Know](https://www.youtube.com/watch?v=qsP_sBUbmZM)
- **[exFAT Filesystem](http://elm-chan.org/docs/exfat_e.html)**