备注
幻灯片放映
大纲
1
文件系統
Peng Lei
2
系統功能
支持 Fat12/Fat16/Fat32
支持長文件名
底層對文件名採用到 Unicode
提供兼容當前系統的 ASCII文件名接口
提供一套使用 Unicode 文件名接口
3
設計目標
優化 Buffer﹐減少 IO 次數
優化文件訪問方式﹐提高隨機訪問速度
面嚮對象結構
增強可擴充性
增強模塊內聚
減小模塊間耦合
增加模塊可復用性
4
系統概要
最近最少使用算法
虛擬文件系統 VFS
Fat 文件系統
文件名/路徑名解析
系統初始化
5
最近最少使用算法(Lru)
實現為一個模板類 LruMap
用于需要進行 Buffer/Cache的對象。
主要接口 :
get(key, referFlag)
release(object)
6
實現
使用 Red-Black Tree通過鍵值查找對象。
使用Double-Linked List管理為最近最少使用的可換出的對象(LruList)。
如果對象被引用﹐則引用計數非零﹐此時對象不在 LruList中﹔當引用計數減至零時﹐對象進入 LruList 作為 Head﹐即最近使用的。
如果找到﹐僅增加引用計數﹐否則Load Object﹐必要時換出最近最少使用的對象。
7
VFS 的結構
內存分配
設備驅動程序(DeviceDriver)
緩沖區管理(BufferManager﹐使用Lru)
文件空間管理(ClusterManager﹐使用Lru)
文件節點管理(DirCtrlBlock﹐目錄管理)
全局文件註冊表(FileMap﹐使用Lru)
8
VFS 的結構-圖示
9
內存分配
限制文件系統使用的總內存
文件系统初始化时从系统堆申请一块固定空间作為文件系統專用Heap
FsMem_Alloc(size, flag)
如 flag 標明申請的內存是重要的﹐則在內存用量超額時將最近最少使用的Buffer換出。
FsMem_Free(mem)
10
設備驅動程序(DeviceDriver)
提供按塊讀寫的接口
塊尺寸為標準扇區尺寸(512B)
提供一個最優訪問塊數﹐VFS努力按此塊數为单位讀寫設備
提供低級格式化函數(format)
11
緩沖區管理(BufferManager)
使用Lru算法統一管理系統所有的 Buffer﹔
文件系統不顯式讀取外存﹐只向 BufferManager請求某設備某地址的數據內容。
由BufferManager通過對Buffer的換入換出﹐將數據寫入外存。
解決Buffer重迭問題。
12
BufferItem
一塊對應到外存上的內存﹐最佳情況下為設備的最佳訪問大小﹔
typedef struct tagBufferItem
{
DeviceDriver *device;
PBYTE buffer;
UINT32 size;
UINT32 first;
UINT32 count;
} BufferItem;
13
文件空間管理(Lru)
是文件系統相關的﹔
大多數文件系統為了文件空間管理的方便﹐將外存分為固定大小的Cluster﹔
為了靈活性﹐允許文件分為多個不連續的塊﹔
一般情況下﹐文件佔用的空間都是完全連續的﹐或分作數目不多的一些不連續的塊(簇組Cluster Group) ﹔
實現中解析具體文件系統的文件空間信息﹐將這些信息轉化為統一格式的﹐按文件邏輯順序的多個 Cluster Group。
14
ClusterGroup
由LruMap來管理﹔
typedef struct tagClusterGroup
{
UINT32 logFirst;// first logic No. of the node
UINT32 first; // first cluster No. of the node
UINT32 count; // count of continuous clusters
UINT32 link; // link for find next cluster group
} ClusterGroup;
一般情況下 count 的數目很大(幾百甚至幾千) 。
如在 Fat 中就可以省去 FatCache.
15
文件空間管理(Lru) 2
如果 Cluster Group 的數目太多﹐就使用 Lru算法對它們進行管理﹔
此時相當于使用動態跳表﹔
最差情況下﹐查找某分離的 Cluster Group必須從第一個Cluster Group開始﹔
因此﹐第一個 Cluster Group 不能被換出。
16
映射 –1 (僅映射﹐無引用)
17
映射 –2 (僅映射﹐無引用)
FileTable-FileBaseInfo
18
FBI-FileHandle 引用 & 映射關係
以(映射關係-1)中的 File_2 為例﹔
弧線箭頭為引用﹐直線箭頭(紅色)為映射。
19
文件節點管理(目錄管理)
是文件系統相關的﹐主要有﹕
創建文件節點(Create)
刪除文件節點(Delete)
重命名文件(Rename)
讀取文件節點(Read)
改写文件结点(Write)
查找文件節點(Find)
20
目錄是一種特殊的文件
在大多數文件系統中﹐目錄都被作為一種特殊的文件來對待。
目錄存儲文件節點﹐一個文件節點可以是一個目錄節點﹐此即多層目錄。
文件節點存儲文件的尺寸﹐起始地址﹐日期時間﹐文件屬性等。
21
全局文件註冊表(Lru)
獲取文件空間信息的開銷很大。
同一文件可能有多個文件句柄。
多個文件句柄對文件的訪問方式可能不同。
使用Lru算法管理註冊的文件﹐註冊的文件為FileBaseInfo﹐文件第一次載入時﹐即進行註冊。
一旦所有句柄關閉﹐並不立即取消註冊。
直到文件註冊表占滿﹐才換出最近最少使用的FileBaseInfo。
22
Fat文件系統
Master Boot Record (MBS)
Partition Boot Record (PBS)
Fat Entry Format
Fat Structure
Fat Directory Entry (File Node)
Long File Name Entry
Fat Directory Manager
23
Disk LayOut1(FatSize = 200Sec)
24
Disk Lay Out2
25
Fat Entry格式
Fat12﹐每個 Fat Entry占12bit﹕
Fat16﹐每個 Fat Entry占16bit。
Fat32﹐每個 Fat Entry占32bit﹐但只用到低28Bit﹐高4位保留。
26
FAT Structure is link list
27
Fat Table 的實際情況
文件的空間在在大部份情況下是連續的;
因此Fat Table的值在大部份情況下是連續的﹐如圖 (ClusterNum = FatIndex – 2);
通過掃描 Fat﹐得出 ClusterGroup.
28
取得Fat Cluster Group
從文件首地址開始,如果Cluster是相鄰的,相應 ClusterNode.count 加一
否則從鏈接地址創建新的 ClusterNode 插入文件的 ClusterTable,直到文件結束.
絕大多數情況下, 整個文件的所有Cluster都是連續的, ClusterNode.count 可以達到幾千甚至幾萬.
29
Fat Directory Entry (32 Byte)
30
File Attribute
FILE_ATTR_READ_ONLY
FILE_ATTR_HIDDEN
FILE_ATTR_SYSTEM
FILE_ATTR_VOLUME_ID
FILE_ATTR_DIRECTORY
FILE_ATTR_ARCHIVE
FILE_ATTR_LONG_NAME
31
FILE_ATTR_DIRECTORY
該屬性標明DirEntry是一個子目錄﹔
子目錄與根目錄的區別﹕
子目錄至少包含兩個DirEntry “.”和 “..” ﹔
一個分區必有且只有一個根目錄但可以有零个或多個子目錄﹔
從文件角度看目錄跟文件的不同﹕
目錄總是占有磁盤空間﹔
目錄的FileSize域總為 0﹔
目錄的實際尺寸不可超過 2 M。
32
FILE_ATTR_LONG_NAME
標明該DirEntry僅存儲長文件名﹐是個LongDirEntry﹔
兼容早期不支持長文件名的Fat系統實現﹔
長文件名存儲為Unicode﹔
一個文件的長文件名最多包含20個LongDirEntry﹔
一個文件最多可以包含259個Unicode字符﹐一個 0結束符。
33
FatLongDirEntry (32 Byte)
LongDirEntry
兼容ShortDirEntry﹔
長文件名以UniCode存儲﹔
一個長文件名可能由多個LongEntry
拼接成。
34
FatLongDirEntry規格:
合法的 LongDirEntry必有一個ShortEntry與之對應﹔
合法的LongDirEntry.bCheckSum必與從ShortName計算出來的相符﹔
從多個LongDirEntry中讀出的文件名要按Order域進行重新排列﹔
如Order有 FAT_LAST_LONG_ENTRY表明這是對應于ShortEntry最後一個LongDirEntry﹔
35
各 Fat支持的分區尺寸&常用參數
Fat Spec支持 512~4K Byte 的Sector尺寸﹐但得到廣泛支持的只有 512 Byte的Sector﹔用 ulong對sector尋址﹐最大尋址範圍是2T。
Fat支持的最大Cluster尺寸為32K﹐由此可以計算各Fat支持的最大尺寸。
Fat12支持的最小尺寸無限制﹐最大尺寸為 128 M﹐但通常不用于大于4M的盤(分區)。
Fat16支持的最小尺寸為2M﹐最大尺寸為 2G﹐但通常不用于大于512M的盤(分區) 。
Fat32支持的最小尺寸為32M﹐最大尺寸為 8T﹐但Windows限制為最大 32G。
36
文件名/路徑名解析
路徑分三類﹕
相對路徑(如 “appdata\data.bin”) ﹔
絕對路徑(如“C:\system\appdata\data.bin”) ﹔
分區根路徑(如“\system\appdata\data.bin”) 。
查找文件﹕
使用Regular Expression匹配文件名(如 c:\??*.b?n, a:\[abc]*.b[cde]t) 。
37
系統初始化
從一個 DeviceDrive創建一個ClusterManager﹔
如果成功﹐以該ClusterManager創建一個根分區﹐裝載到系統根﹔
根分區的名字不固定﹐任何合法的ClusterManager可以裝載為任何名字﹐目前按兼容當前文件系統的名字裝載﹔
設置根分區的當前目錄為根目錄。
38
系统的不足
Fat文件系统对目录无排序索引
查找每个文件都需要顺次查找每级目录
不适宜在一个目录下建立太多文件
长文件名的读写需要编码转化和校验，速度比短文件名读写慢，表现在查找文件速度比较慢
39
謝謝大家!
本文地址：http://com.8s8s.com/it/it36694.htm