讀取 FAT32 檔案系統

本文在 2013/07/11 23:41 發表於 Yahoo!奇摩部落格
因Yahoo!奇摩部落格將於2013年12月26日終止服務故遷移至此

新玩具開發中, 中間產物釋放
在三年前寫了篇 讀取 SD 卡 的文章, 現在又拖出來鞭屍(?)
時代在變, 尤其科技業, 變得很快 !
以前的 SD 卡讀法又要改了
以前的卡多以 MB 為單位, 現在都 GB 的, 想買 2GB 以下的還找不到哩
有這麼大的空間當然要跑檔案系統的囉, 放靜態資料多浪費啊
所以就有了這個實驗 : 讀取 FAT32 檔案系統

FAT 檔案系統大概是當前受支援最廣的檔案系統了
幾乎沒有作業系統不認, 而且行動裝置記憶卡都是用這系統
就算它年紀很大了還是有研究的價值
它雖然縮寫是 FAT 可是卻一點也不肥, 反而非常得緊實(?)XD
畢竟數十年前硬碟只有幾 MB 的時代, 不可能容許浪費空間
因此設計上是非常緊密的使用儲存空間, 如果損壞了會很難找回資料

這裡先簡單的描述 FAT 的設計原理
如果要進行實作務必閱讀微軟寫的白皮書 :
Microsoft Extensible Firmware Initiative FAT32 File System Specification
否則會不知道自己在做啥, 在寫啥



整個檔案系統可分為三部分
第一區為標頭, 紀錄分割區資訊以及這檔案系統的相關資訊
第二區為檔案配置表, File Allocation Table, 標記各磁簇使用狀況
第三區為資料區, 實際放檔案的地方
FAT 將空間分割成磁區 (Sector) 和磁簇 (Cluster)
有些儲存裝置, 尤其以碟盤形式的還會有磁軌等單位, 這裡都先忽略
因為 SD 卡上沒有這種東西XD
數個磁區會組成一個磁簇, 而 FAT 在定位時主要以磁簇為主
通常磁區是固定的, 以新的 SD 卡來說一定是 512-byte
舊的 SD 卡則可以 byte 去定位, 一樣暫時先不考慮, 減低複雜度XD
磁簇大小是可調整的, 以我的 4GB 卡來說格式化後是 8 個磁區為一磁簇
也就是一磁簇有 512 * 8 = 4KB 的空間
磁簇越大, 越不利於存小檔案, 如果你的文件只有 50-byte
那在 FAT32 中以磁簇來定位的情況下它會佔去 4KB, 沒得妥協
然而, 如果儲存空間加大, 磁簇必須越大
因為 FAT32 用 32-bit 來標記磁簇位址, 而前 4-bit 保留, 實際為 28-bit
以 4KB 磁簇來說最多就是 4KB * 2^28 = 1TB
如果你的硬碟是 2TB, 那就只能加大磁簇空間來擴充, 例如 : 8KB * 2^28
這樣的話最小檔案就變成 8KB, 不管存多少 bytes, 只要低於 8KB 都佔用 8KB

FAT 有 FAT12, FAT16, FAT32 三種
區分這三種的唯一指標就是儲存空間大小 (精確的說是儲存空間中磁簇的總數量)
白皮書裡有寫臨界點, 小於幾個磁簇就是 FAT12, 超過了就是 FAT16, 然後再上去就是 FAT32
不管是 FAT 多少都算是 FAT 檔案系統, 我想區分的目的應是在於有效使用空間
例如: 如果空間只有 1MB, 用 32-bit 的數字去定位區塊不是很浪費嗎?
32-bit 可以有四億多種可能, 可你卻拿去定位只有 1MB 的空間, 這不像話吧
就算以 byte 去定位也只有 1048576 個位址, 這太浪費了
依據不同大小去做不同的位址分配, 這樣才可以有效使用空間


上圖方塊代表一筆資料, 每區域代表不同意義, 不是相同的東西
第一區 Header 沒什麼, 就一塊資料依據白皮書定義各個 byte 代表的意義而已
第二區, FAT, 可以把它當成一個表格來看
每個格子的大小會依據檔案系統版本而異, 這裡一律以 FAT32 為主
畢竟我要寫的是 SD 卡, 而且也買不到低於 2GB 的卡了XD
以 FAT32 來說, 每個單元是 32-bit, 也就是四個 byte
每個 4-byte 儲存的是三種標記 : 空白, 損毀, 最後磁簇, 或是下一個磁簇
就像 ArrayList 一樣, 用一個表格儲存多條 "List"
例如有一個檔案從第 10 磁簇開始, 那麼要讀取這檔案就是 :

1. 到第三區資料區的第 10 磁簇讀取一磁簇資料 (例 : 4KB)
2. 查詢第二區 FAT, 讀取第 10 筆資料, 看看下一個磁簇在哪, 假設 25
3. 同 1., 前往資料區第 25 磁簇再讀取 4KB 資料, 不斷重複, 直到看到最後磁簇標記為止

這是一個單向的串列 (signle linked list), 亦即, 如上面範例
如果現在讀的是第 25 磁簇資料, 我只能往後走, 並沒有資訊紀錄前一磁簇位置
除非從頭讀, 或是把表格存入記憶體, 不然我並不知道磁簇 25 的前一個是磁簇 10
所以如果這串列有一個節點斷了, 這資料就回不來了
而且由於 FAT 裡是標記為使用中空間, 這不見的資料會佔用儲存空間, 無法刪除
只能另外用修復軟體使用各種策略去偵測並修正

上一段寫的是單一檔案的讀取方式, 然而, 檔案系統裡可不單只有檔案
而是有層層資料夾結構, 資料夾中有檔案, 那麼資料夾如何表示?
在 FAT 檔案系統中, 資料夾和檔案一樣都存放在第三區
和檔案一樣, 每個資料夾最少佔用一個磁簇的空間
在第一區的標頭資訊中會紀錄檔案系統中第一個目錄, 也就是根目錄存放的磁簇
讀取該磁簇可以看到像這樣的內容 :

在資料夾存放的磁簇中可分成一群檔案單元 (entity, 不知如何翻^^b)
上圖大方塊代表磁簇, 大方塊中的小方塊代表檔案單元
每個單元是 32 個 byte, 裡面紀錄短檔名, 檔案大小, 屬性, 以及所在磁簇
短檔名是一個 11 bytes 的名稱, 早期 DOS 時代還夠用
現在檔名都在比長的, 還中文 ! XD
所以這 11 bytes 絕對不夠用, 因此在資料夾裡有另一種檔案單元
它一樣是 32 個 byte, 不過用來存檔名, 檔案單元的屬性會標示為長檔名
因此紀錄一個檔案就有兩種方式 :

1. 單一組 32-byte
2. 連續數個 32-byte 檔名加上一個 32-byte 檔案單元

檔案單元指向檔案存放的磁簇, 這磁簇裡可以是存檔案的資料, 也可以是另一個資料夾
所以才會有 "檔案和資料夾是相同的東西" 這種說法
當資料夾中的檔案量越來越多, 會產生越來越多的 32-byte 檔案單元
最終會填滿一個磁簇的空間, 若要在加入檔案, 就是存到另一個磁簇裡, 然後在第二區 FAT 裡標記
把這個目錄的第一個磁簇在 FAT 中寫上第二個磁簇的編號
所以要列出所有資料夾中的檔案就要像讀檔案一樣
先讀一個磁簇, 列出檔案單元, 然後到第二區 FAT 看看有沒有下一個磁簇
若有, 讀取下一個磁簇, 再列出檔案單元, 再查下一個磁簇, 如此循環, 直到看到最後磁簇標記

整個 FAT 檔案系統就是兩群單向的串列
在第二區的串列標記每個單一檔案的磁簇分佈狀況
在第三區的串列標記資料夾和檔案的組織排列狀況
由於都是單向的串列, 斷了就很難尋回
而且需要定期重組, 當檔案分佈的磁簇串列不連續時
若是傳統磁盤硬碟就會不斷的甩動讀取頭到處找磁簇, 速度自然就慢
不過對於任何區塊存取時間都固定的 flash 記憶體可能就比較沒有差了
SD 卡, 各類記憶卡, 或是 SSD 硬碟都是類似 flash 的記憶體, 擁有固定的區塊存取時間

了解了 FAT32 的規格, 我們就可以把它做到微控制器上去執行
在微控制器上讀取 FAT32 是可以實現的, 前篇 "讀取 SD 卡" 文章中有連結
就是這個 :

SD/SDHC Card Interfacing with ATmega8 /32 (FAT32 implementation)

用麵包板接線讀, 超猛XD
不過如果全程都用一顆 AVR 去除錯是會死人的
因為 printf 功能要自己寫, 那會非常頭痛
比較建議的方法是先在桌上型電腦寫好, 然後移植到 AVR 上
由於考慮到要移植 AVR, 寫程式時禁止使用 malloc 以及過大的陣列
都用固定大小的陣列加上迴圈來讀
這裡放出我的桌上型電腦用測試程式 :

fat32.zip

使用方法 (ubuntu 專用, windows 請自理XD) :
先將 SD 卡插上讀卡機後接放電腦, 假設電腦上產生的節點是 sdd
用 disk copy 指令複製出一段區塊

sudo dd if=/dev/sdd of=sdd bs=1024 count=40960

如果是剛格式化過的 SD 卡且裡面只放幾個檔案, 只要複製個 40-50 MB 出來就可以了
接著編譯程式並執行

gcc fat32.c -o fat32
./fat32

以我的卡可以看到這樣 :

first sector for first partition : 800
FAT[2] = 0x0ffffff8
FAT[3] = 0x00001bac
FAT[4] = 0x00000000
4 file & dir!
01____~1MP3 2518878 B @ 00001515
TESTFO~1    0 B @ 00000003
FBS     APK 277248 B @ 000000d5
ANTUTU  APK 10376116 B @ 0000011b

程式從 SD 卡第一個磁區開始看, 裡面放 MBR, 先讀取它找到分割區
分割區相關的紀錄方式可參考 wiki : http://en.wikipedia.org/wiki/Master_boot_record
找到分割區所在的磁區後就可以開始分析 FAT32 檔案系統
若遇到問題可使用 16 進位編輯器, 例如 mc, hexedit 等工具開啟複製出的檔案尋找問題點



最後, demo:



線挺亂的, 該合體了(?)