《Linux原理與結(jié)構(gòu)》課件第12章

第十二章物理文件系統(tǒng)12.1塊設(shè)備管理12.2EXT文件系統(tǒng)虛擬文件系統(tǒng)雖然功能強(qiáng)大，但卻僅僅是一個框架，并不真正管理外存中的文件。事實(shí)上，物理文件系統(tǒng)才是文件的真正管理者。

早期的物理文件系統(tǒng)都建立在真實(shí)的塊設(shè)備之上，主要負(fù)責(zé)邏輯塊的分配與釋放、文件內(nèi)容的組織與管理(文件塊到邏輯塊的轉(zhuǎn)換)、文件的組織與管理(文件名到控制塊的轉(zhuǎn)換)等。物理文件系統(tǒng)的管理信息記錄在塊設(shè)備中，即使掉電也不會丟失。

隨著Linux的發(fā)展，人們逐漸認(rèn)識到文件是一種通用的抽象手段，文件系統(tǒng)是一種定義良好的操作接口。除了可以表示存儲在塊設(shè)備中的真實(shí)實(shí)體之外，還可以用文件描述動態(tài)生成的信息，如內(nèi)核中各子系統(tǒng)的狀態(tài)等。這類動態(tài)生成的文件可以稱為虛文件，用于管理虛文件的系統(tǒng)可以稱為虛文件系統(tǒng)。將虛文件系統(tǒng)插入到VFS框架之后，用戶可以用常規(guī)的文件操作接口查看、修改虛文件，進(jìn)而查看內(nèi)核的狀態(tài)、修改內(nèi)核的參數(shù)等。為此Linux開發(fā)了多種不需要物理塊設(shè)備支持的虛文件系統(tǒng)，如proc、sysfs等，極大地提高了內(nèi)核的透明度和管理質(zhì)量。

在近期的發(fā)展中，開發(fā)者們開始借助虛文件系統(tǒng)的管理機(jī)制來管理Linux的其它子系統(tǒng)，如管道、消息隊(duì)列、共享內(nèi)存等。這種純粹在內(nèi)核中使用、用戶無法看到的虛文件系統(tǒng)可稱為偽文件系統(tǒng)，如pipefs、mqueue、shm等。

從虛擬文件系統(tǒng)的角度看，不管文件系統(tǒng)能否為用戶所見，不管其信息是否駐留在物理塊設(shè)備之上，只要實(shí)現(xiàn)了VFS的下層接口，它就是一個物理文件系統(tǒng)。

除了用于特殊目的的偽文件系統(tǒng)和虛文件系統(tǒng)之外，主流的物理文件系統(tǒng)都建立在塊設(shè)備之上。塊設(shè)備與字符設(shè)備和網(wǎng)絡(luò)設(shè)備一道，構(gòu)成了Linux的三大外部設(shè)備。12.1塊?設(shè)?備?管?理塊設(shè)備的典型代表是磁盤、光盤、U盤等。一個完整的塊設(shè)備又可以分成多個分區(qū)，每個分區(qū)上都可以建立一個物理文件系統(tǒng)。與字符設(shè)備和網(wǎng)絡(luò)設(shè)備相比，塊設(shè)備具有自己的特點(diǎn)，如總是被抽象成塊的數(shù)組、總可利用序號對其中的塊進(jìn)行隨機(jī)訪問、基本訪問單位是塊而不是字節(jié)、I/O操作一般要經(jīng)過緩存等。

由于塊設(shè)備的上述特點(diǎn)，Linux定義了較為復(fù)雜的塊設(shè)備管理層來專門管理系統(tǒng)中的塊設(shè)備。塊設(shè)備管理層用結(jié)構(gòu)gendisk描述塊設(shè)備的物理特征，用結(jié)構(gòu)block_device描述塊設(shè)備的邏輯特征。前者所描述的設(shè)備可稱為物理塊設(shè)備，后者所描述的設(shè)備可稱為邏輯塊設(shè)備。物理塊設(shè)備的操作單位是扇區(qū)，邏輯塊設(shè)備的操作單位是塊。12.1.1塊設(shè)備的用戶表示

Linux把自己的每個塊設(shè)備看成是一個特殊的數(shù)據(jù)文件，稱為塊設(shè)備特殊文件，并在/dev目錄中給每個塊設(shè)備特殊文件指派了一個文件名，如/dev/hda1、/dev/sda2等。一個塊設(shè)備特殊文件代表的是系統(tǒng)中的一個特定塊設(shè)備(如/dev/sde代表的是一塊U盤)或特定塊設(shè)備中的一個特定分區(qū)(如/dev/hda1代表的是第一塊IDE磁盤的第一個分區(qū))。塊設(shè)備特殊文件中的第i塊對應(yīng)著塊設(shè)備中的第i塊。與普通文件一樣，塊設(shè)備特殊文件也可以被打開并被讀寫。向塊設(shè)備特殊文件的第i塊寫入的數(shù)據(jù)實(shí)際被寫入到了塊設(shè)備的第i塊中，從塊設(shè)備特殊文件的第i塊中讀出的數(shù)據(jù)實(shí)際是塊設(shè)備第i塊中的數(shù)據(jù)。

Linux的用戶用塊設(shè)備特殊文件的文件名來標(biāo)識塊設(shè)備，Linux內(nèi)核卻用設(shè)備號來標(biāo)識塊設(shè)備。設(shè)備號的類型為dev_t，由兩部分組成，其中的主設(shè)備號(major)標(biāo)識的是塊設(shè)備整體，如整塊磁盤，次設(shè)備號(minor)標(biāo)識的是塊設(shè)備中的分區(qū)。一個塊設(shè)備號可以唯一地標(biāo)識一個塊設(shè)備，正如一個PID可以唯一地標(biāo)識一個進(jìn)程一樣。為了實(shí)現(xiàn)文件名與塊設(shè)備號之間的轉(zhuǎn)換，Linux復(fù)用了塊設(shè)備特殊文件的VFSinode結(jié)構(gòu)，將實(shí)體的類型(塊設(shè)備)和訪問權(quán)限記錄在i_mode域中，將塊設(shè)備的大小記錄在i_size域中，將塊設(shè)備的設(shè)備號記錄在i_rdev域中。

解析一個特定的塊設(shè)備特殊文件名，可以得到它的VFSinode結(jié)構(gòu)，從中可以獲得塊設(shè)備的設(shè)備號，據(jù)此可找到它的邏輯和物理表示結(jié)構(gòu)。打開一個塊設(shè)備特殊文件實(shí)際上打開的是與之對應(yīng)的塊設(shè)備，為該文件指定的操作集不同于普通的文件操作集，其中的read、write操作讀寫的是塊設(shè)備本身而不是塊設(shè)備特殊文件。由此可見，塊設(shè)備特殊文件僅僅是塊設(shè)備的一種用戶態(tài)表示，它在系統(tǒng)中僅有一個inode結(jié)構(gòu)，并無實(shí)際的數(shù)據(jù)塊。塊設(shè)備特殊文件的主要作用是實(shí)現(xiàn)文件名與設(shè)備號之間的轉(zhuǎn)換。12.1.2塊設(shè)備的物理表示

在物理上，每個塊設(shè)備都有自己特殊的屬性，如大小、操作方法等。為了統(tǒng)一管理系統(tǒng)中所有的塊設(shè)備，Linux抽象出了各類塊設(shè)備的共同屬性和操作方法，定義了結(jié)構(gòu)gendisk用于描述整體的物理塊設(shè)備(如整塊磁盤)，定義了結(jié)構(gòu)hd_struct用于描述塊設(shè)備中的單個分區(qū)。

結(jié)構(gòu)gendisk中包含一個物理塊設(shè)備的主要描述信息，如圖12.1所示。

(1)每個物理塊設(shè)備都有一個唯一的主設(shè)備號，記錄在major中。其中的每個分區(qū)都擁有同樣的主設(shè)備號，但卻有不同的次設(shè)備號。一個物理塊設(shè)備可以擁有多個次設(shè)備號，從first_minor開始，共minors個。

(2)分區(qū)表part_tbl用于記錄物理塊設(shè)備的分區(qū)情況，實(shí)際是一個指針數(shù)組，其中的每個指針都指向一個hd_struct結(jié)構(gòu)。物理塊設(shè)備的第0號分區(qū)part0具有特殊的意義，它從分區(qū)的角度描述物理塊設(shè)備自身，因而總是存在的。第0號分區(qū)是整個物理塊設(shè)備的代表。

(3)雖然一個物理塊設(shè)備可能包含多個分區(qū)，但各個分區(qū)的操作方式應(yīng)該是相同的。Linux要求它的每個物理塊設(shè)備驅(qū)動程序都提供一個操作集block_device_operations，用于實(shí)現(xiàn)物理塊設(shè)備特定的操作，如open、release、ioctl、media_changed等。

(4)與字符設(shè)備不同，對塊設(shè)備的讀寫操作通常不會立刻實(shí)施，而是被包裝成請求并被掛在物理塊設(shè)備的請求隊(duì)列中排隊(duì)。物理塊設(shè)備可按某種調(diào)度策略對等待的請求進(jìn)行合并、重組、排序等，以期盡量減少塊設(shè)備操作的次數(shù)，提高塊設(shè)備操作的性能。顯然，一個物理塊設(shè)備僅需要一個請求隊(duì)列(域queue)，對該塊設(shè)備的所有操作請求，不管是對哪個分區(qū)的，都應(yīng)被掛在同一個隊(duì)列上排隊(duì)。當(dāng)時機(jī)成熟時，Linux會按照某種特定的順序，一次性地處理掉隊(duì)列中的所有請求。

(5)結(jié)構(gòu)gendisk僅定義了物理塊設(shè)備的通用屬性，塊設(shè)備特殊的描述信息可以被包裝在專門的結(jié)構(gòu)中，記錄在private_data域內(nèi)。

圖12.1單個物理塊設(shè)備的描述結(jié)構(gòu)結(jié)構(gòu)hd_struct中包含一個分區(qū)的主要描述信息，如圖12.1所示。

(1)物理塊設(shè)備的基本訪問單位是扇區(qū)，可將一個物理塊設(shè)備抽象成一個扇區(qū)的數(shù)組，將一個分區(qū)抽象成該數(shù)組中的一塊連續(xù)區(qū)間，從start_sect扇區(qū)開始，共nr_sects個扇區(qū)。第0號分區(qū)的start_sect是0，nr_sects是整個物理塊設(shè)備的扇區(qū)總數(shù)。

(2)結(jié)構(gòu)hd_struct中的_

_dev是一個內(nèi)嵌的device結(jié)構(gòu)，其中包含分區(qū)的名稱、類型、所屬總線和一個kobject結(jié)構(gòu)。系統(tǒng)中所有的分區(qū)被它們的device結(jié)構(gòu)組織成一棵拓?fù)錁?，用于描述塊設(shè)備的拓?fù)浣Y(jié)構(gòu)，見圖3.11。第0號分區(qū)代表整個物理塊設(shè)備，是拓?fù)錁渲衅溆喾謪^(qū)的父節(jié)點(diǎn)。

系統(tǒng)中所有物理塊設(shè)備的gendisk結(jié)構(gòu)被組織在Hash表bdev_map[]中，Hash值是主設(shè)備號。數(shù)組bdev_map[]中的每個指針指向一個probe結(jié)構(gòu)，擁有同樣Hash值的probe結(jié)構(gòu)被串成一個單向鏈表，如圖12.2所示。結(jié)構(gòu)probe的定義如下：

structprobe{

structprobe *next; //擁有同樣Hash值的下一個probe結(jié)構(gòu)

dev_t dev; //開始設(shè)備號，包括主設(shè)備號和次設(shè)備號

unsignedlong range; //物理設(shè)備所擁有的次設(shè)備號數(shù)量

structmodule *owner; //模塊

kobj_probe_t *get; //特定操作，用于獲得物理設(shè)備的kobject結(jié)構(gòu)

int(*lock)(dev_t,void*); //特定操作，用于獲得設(shè)備相關(guān)的鎖，常為NULL

void *data; //指向物理設(shè)備的gendisk或字符設(shè)備的cdev

}

缺省情況下，數(shù)組bdev_map[]中的指針全都指向同一個缺省的probe結(jié)構(gòu)。圖12.2物理塊設(shè)備組織結(jié)構(gòu)當(dāng)物理塊設(shè)備被它的驅(qū)動程序檢測到時，它的gendisk結(jié)構(gòu)會被創(chuàng)建，塊設(shè)備中存儲的分區(qū)表會被分析，與之相關(guān)的分區(qū)結(jié)構(gòu)hd_struct會被逐個創(chuàng)建并加入到gendisk的分區(qū)表中。初始化之后的gendisk先被包裝在probe結(jié)構(gòu)中，再被注冊到數(shù)組bdev_map[]中(替換掉缺省的probe)。根據(jù)主設(shè)備號查數(shù)組bdev_map[]可以方便地找到設(shè)備的gendisk結(jié)構(gòu)。當(dāng)然，分區(qū)結(jié)構(gòu)的建立時機(jī)也可推遲到塊設(shè)備第一次被打開之時。除了gendisk和hd_struct之外，不同種類的物理塊設(shè)備還定義了自己專用的管理結(jié)構(gòu)(記錄在gendisk結(jié)構(gòu)的private_data域中)，如SCSI磁盤的scsi_device和scsi_disk結(jié)構(gòu)、IDE磁盤的ide_drive_t和ide_disk_obj結(jié)構(gòu)等。特定物理塊設(shè)備的管理工作需依賴它們自己的私有管理結(jié)構(gòu)。12.1.3塊設(shè)備的邏輯表示

結(jié)構(gòu)gendisk和hd_struct主要是給塊設(shè)備驅(qū)動程序使用的，所描述的是塊設(shè)備的物理特征。每類塊設(shè)備驅(qū)動程序都會在自己的gendisk結(jié)構(gòu)中注冊操作集和請求隊(duì)列。對驅(qū)動程序來說，以扇區(qū)為單位操作塊設(shè)備是方便而靈活的，因而gendisk和hd_struct中的基本單位都是扇區(qū)。但對塊設(shè)備的上層用戶(如物理文件系統(tǒng))來說，扇區(qū)的尺寸過小，通常無法滿足它們的需求。事實(shí)上，物理文件系統(tǒng)通常以塊(由若干連續(xù)的扇區(qū)組成)為單位操作塊設(shè)備。即使操作的是同一個物理塊設(shè)備，不同物理文件系統(tǒng)所使用的塊尺寸也可能不同。為了實(shí)現(xiàn)不同操作單位(塊與扇區(qū))之間的轉(zhuǎn)換，需要再為塊設(shè)備定義一種邏輯表示方式。

Linux用結(jié)構(gòu)block_device描述塊設(shè)備的邏輯特征。對塊設(shè)備的用戶來說，一個block_device結(jié)構(gòu)唯一地標(biāo)識了一個邏輯(或虛擬)塊設(shè)備，雖然它實(shí)際上可能只是某個物理塊設(shè)備中的某個分區(qū)。邏輯塊設(shè)備的用戶看到的是一個邏輯塊的數(shù)組而不再是扇區(qū)的集合。結(jié)構(gòu)block_device中的主要內(nèi)容有以下幾個，如圖12.3所示。

(1)邏輯塊設(shè)備的設(shè)備號bd_dev，等價于某個物理分區(qū)的設(shè)備號。

(2)邏輯塊設(shè)備所對應(yīng)的物理塊設(shè)備bd_disk(指向結(jié)構(gòu)gendisk的指針)。

(3)邏輯塊設(shè)備所對應(yīng)的物理分區(qū)bd_part(指向結(jié)構(gòu)hd_struct的指針)。

(4)邏輯塊的尺寸bd_block_size。

(5)邏輯塊設(shè)備的持有者bd_holder。內(nèi)核的某個組件，如物理文件系統(tǒng)。

(6)所屬邏輯塊設(shè)備bd_contains(代表物理分區(qū)的邏輯塊設(shè)備從屬于代表整個物理塊設(shè)備的邏輯塊設(shè)備)。

圖12.3邏輯塊設(shè)備與物理塊設(shè)備之間的關(guān)系系統(tǒng)中所有的block_device結(jié)構(gòu)被其中的節(jié)點(diǎn)bd_list串聯(lián)成一個雙向鏈表，表頭是all_bdevs。搜索鏈表all_bdevs可以找到任何一個block_device結(jié)構(gòu)，但效率較低。為了便于block_device結(jié)構(gòu)的管理，Linux將一個block_device結(jié)構(gòu)與一個VFSinode結(jié)構(gòu)包裝在一起，定義了一種新的容器結(jié)構(gòu)bdev_inode，如下：

structbdev_inode{

structblock_device bdev;

structinode vfs_inode;

};定義結(jié)構(gòu)bdev_inode的目的是為了借用VFS的管理結(jié)構(gòu)(如inode緩存、超級塊操作集等)來管理系統(tǒng)中的邏輯塊設(shè)備，即block_device結(jié)構(gòu)。事實(shí)上，在系統(tǒng)初始化時，Linux創(chuàng)建了一個偽文件系統(tǒng)bdev，專門用于組織它的bdev_inode結(jié)構(gòu)。在打開塊設(shè)備時，Linux為其創(chuàng)建的實(shí)際是一個bdev_inode結(jié)構(gòu)，其中的vfs_inode會被插入到VFS的管理結(jié)構(gòu)之中。以邏輯塊設(shè)備的設(shè)備號為索引查VFS的inode緩存可獲得該塊設(shè)備的inode結(jié)構(gòu)，通過container_of()函數(shù)可算出包含它的bdev_inode結(jié)構(gòu)，進(jìn)而可得到與之綁定的block_device結(jié)構(gòu)。雖然一個物理塊設(shè)備可以有多個特殊文件，但它僅擁有一個設(shè)備號，因而僅能有一個block_device結(jié)構(gòu)。

當(dāng)然，在與block_device綁定的VFSinode結(jié)構(gòu)中還可以記錄邏輯塊設(shè)備的其它管理信息，如邏輯塊設(shè)備的大小、訪問權(quán)限、塊尺寸等，直接從邏輯塊設(shè)備中讀取的頁被緩存在該VFSinode的地址空間中。用戶在使用物理塊設(shè)備之前需通過打開操作創(chuàng)建或獲得它的block_device結(jié)構(gòu)。如果塊設(shè)備曾經(jīng)被打開過，通過塊設(shè)備號可以找到它的block_device結(jié)構(gòu)；如果塊設(shè)備未被打開過，則需為其創(chuàng)建新的block_device結(jié)構(gòu)。一個塊設(shè)備可以被多次打開，但僅會為其創(chuàng)建一個block_device結(jié)構(gòu)。塊設(shè)備被打開的過程如下：

(1)解析塊設(shè)備特殊文件的路徑名，獲得它的VFSinode結(jié)構(gòu)，進(jìn)行必要的權(quán)限檢查，從中取出塊設(shè)備的設(shè)備號rdev。

(2)如果塊設(shè)備曾被打開過，那么它的block_device結(jié)構(gòu)應(yīng)該已被創(chuàng)建并被記錄在塊設(shè)備特殊文件的VFSinode結(jié)構(gòu)的i_bdev域中，可以直接得到。

(3)即使塊設(shè)備特殊文件的VFSinode結(jié)構(gòu)的i_bdev為空，它的block_device結(jié)構(gòu)也可能在緩存中。以設(shè)備號rdev為Hash值在inode_hashtable中查bdev文件系統(tǒng)中的VFSinode，如果能在其中找到與之對應(yīng)的bdev_inode結(jié)構(gòu)，那么其中的bdev就是所需的block_device結(jié)構(gòu)，可以直接得到。

(4)如果設(shè)備號為rdev的VFSinode結(jié)構(gòu)不在inode緩存中，則需為其新建一個：

①創(chuàng)建一個新的bdev_inode結(jié)構(gòu)，初始化其中的inode和block_device結(jié)構(gòu)，如block_device結(jié)構(gòu)中的bd_dev和bd_block_size等。

②將bdev_inode中的VFSinode結(jié)構(gòu)插入到bdev文件系統(tǒng)的管理隊(duì)列中。

③將bdev_inode中的block_device結(jié)構(gòu)插入到all_bdevs鏈表中。④建立塊設(shè)備特殊文件的VFSinode與塊設(shè)備的容器結(jié)構(gòu)bdev_inode之間的鏈接關(guān)系，如圖12.4所示。

圖12.4塊設(shè)備特殊文件與塊設(shè)備bdev_inode結(jié)構(gòu)間的關(guān)系⑤為邏輯塊設(shè)備(即block_device結(jié)構(gòu))指派物理塊設(shè)備和分區(qū)：

●如果要打開的是整個塊設(shè)備(第0號分區(qū))，則根據(jù)主設(shè)備號從數(shù)組bdev_map[]中找出物理塊設(shè)備的gendisk結(jié)構(gòu)，從其分區(qū)表中找出第0號分區(qū)的hd_struct結(jié)構(gòu)，將它們分別記錄在block_device結(jié)構(gòu)的bd_disk和bd_part域中，并執(zhí)行g(shù)endisk中的open操作，完成物理塊設(shè)備硬件的初始化。

●如果要打開的是塊設(shè)備的非0號分區(qū)，則先打開整個塊設(shè)備，再根據(jù)塊設(shè)備的主、次設(shè)備號找出與之對應(yīng)的gendisk和hd_struct結(jié)構(gòu)，并將它們分別記錄在block_device結(jié)構(gòu)的bd_disk和bd_part域中。打開非0號分區(qū)時不需要執(zhí)行g(shù)endisk中的open操作。

(5)創(chuàng)建一個file結(jié)構(gòu)，將其填入當(dāng)前進(jìn)程的文件描述符表中。新file結(jié)構(gòu)的操作集為def_blk_fops。

當(dāng)塊設(shè)備特殊文件的VFSinode被釋放時，VFS會斷開它與bdev_inode結(jié)構(gòu)的鏈接。當(dāng)引用block_device的最后一個塊設(shè)備特殊文件的VFSinode被釋放時，整個bdev_inode結(jié)構(gòu)才會被釋放。12.1.4請求隊(duì)列

在打開之后的塊設(shè)備上可以進(jìn)行正常的讀寫操作。與字符設(shè)備不同，對塊設(shè)備的操作請求一般不會立刻交給設(shè)備的硬件，而會被稍稍延遲。Linux的塊設(shè)備管理層會收集對各個物理塊設(shè)備的操作請求，直到時機(jī)成熟時再對其進(jìn)行批量處理。延遲并批量處理塊設(shè)備請求會帶來許多好處，如可以將相鄰的操作合并在一起，從而減少操作的次數(shù)；可以對收集到的操作進(jìn)行適當(dāng)?shù)闹亟M、排序，從而使操作方式更加合理等。為了收集物理塊設(shè)備操作請求，Linux采取了兩項(xiàng)措施，一是為每個物理塊設(shè)備都準(zhǔn)備了一個請求隊(duì)列，二是將對物理塊設(shè)備的每一次讀寫操作都包裝成一個請求結(jié)構(gòu)并掛在設(shè)備自身的請求隊(duì)列中排隊(duì)。

Linux用結(jié)構(gòu)request描述物理塊設(shè)備操作請求。一個請求表示在物理內(nèi)存和物理塊設(shè)備之間的一次數(shù)據(jù)傳送。從內(nèi)存到塊設(shè)備的數(shù)據(jù)傳送稱為寫操作，從塊設(shè)備到內(nèi)存的數(shù)據(jù)傳送稱為讀操作。一個request結(jié)構(gòu)僅能表示一類操作，要么讀，要么寫，且所操作的邏輯塊在設(shè)備上必須是連續(xù)的。

描述請求的參數(shù)主要有三類，一是數(shù)據(jù)在塊設(shè)備上的位置和長度，二是數(shù)據(jù)在內(nèi)存中的位置和長度，三是數(shù)據(jù)傳送的方向。數(shù)據(jù)在物理塊設(shè)備上的位置由扇區(qū)號標(biāo)識，在內(nèi)存中的位置由物理頁的page結(jié)構(gòu)和在頁中的偏移量標(biāo)識，傳送方向由操作命令標(biāo)識(讀或?qū)?。在早期的版本中，一次請求描述的是塊設(shè)備上的一塊連續(xù)扇區(qū)與物理內(nèi)存中的一塊連續(xù)區(qū)間之間的數(shù)據(jù)傳送。在新的實(shí)現(xiàn)中，Linux不再要求這種連續(xù)性，一次請求可以對應(yīng)多個不連續(xù)的內(nèi)存緩沖區(qū)，并允許在一個請求中包裝多個數(shù)據(jù)傳送。為此，在request之外，Linux又引入了結(jié)構(gòu)bio，用于描述物理塊設(shè)備和物理內(nèi)存之間的一次數(shù)據(jù)傳送，如圖12.5所示。

圖12.5一個bio結(jié)構(gòu)所描述的數(shù)據(jù)傳送在bio結(jié)構(gòu)中，bi_bdev是參與此次數(shù)據(jù)傳送的邏輯塊設(shè)備，bi_sector是數(shù)據(jù)在塊設(shè)備中的開始扇區(qū)號，bi_size是數(shù)據(jù)的長度(單位是字節(jié))，bi_io_vec是一個結(jié)構(gòu)數(shù)組，記錄著數(shù)據(jù)在物理內(nèi)存中的位置，bi_vcnt是數(shù)組中的結(jié)構(gòu)數(shù)，bi_rw和bi_flags是數(shù)據(jù)傳送的方向和特殊要求，它們共同描述了一次完整的數(shù)據(jù)傳送。另外，bi_end_io指向一個善后處理函數(shù)，用于數(shù)據(jù)傳送完畢后的清理；bi_private是驅(qū)動程序?qū)Ｓ玫男畔ⅰ?/p>

一個request中可以包含多個bio結(jié)構(gòu)，它們被串成一個雙向鏈表。在一個request中，所有的bio按bi_sector排序(從小到大)，它們所操作的扇區(qū)必須是連續(xù)的，所請求的傳送方向也必須是一致的，如圖12.6所示。針對一個物理塊設(shè)備的所有未處理的請求都被組織在該設(shè)備的請求隊(duì)列中。每個物理塊設(shè)備都有一個請求隊(duì)列，結(jié)構(gòu)gendisk中的queue指向該隊(duì)列，如圖12.1所示。圖12.6物理塊設(shè)備的請求隊(duì)列請求隊(duì)列由結(jié)構(gòu)request_queue描述，其中包含如下信息：

(1)請求隊(duì)列的隊(duì)頭queue_head。用于組織待處理的操作請求，即request結(jié)構(gòu)。

(2)

I/O調(diào)度器elevator。將請求掛在隊(duì)列queue_head中的主要目的是為了對其進(jìn)行合并、排序、重組等，也就是調(diào)度。不同的物理塊設(shè)備可以采用不同的請求調(diào)度策略，域elevator中記錄著物理塊設(shè)備選用的I/O調(diào)度器，俗稱電梯算法。目前Linux提供的I/O調(diào)度器有先來先服務(wù)調(diào)度器(noop)、死線調(diào)度器(deadline)、預(yù)估調(diào)度器(as)、完全公平調(diào)度器(cfq)等。用戶可根據(jù)需要為各物理塊設(shè)備選擇I/O調(diào)度器，目前缺省的調(diào)度器是cfq。I/O調(diào)度器的主要內(nèi)容是一個操作集，其中包括bio合并操作、請求合并操作、請求插入操作、請求分發(fā)操作等。

(3)空閑請求池rq。在系統(tǒng)運(yùn)行過程中，結(jié)構(gòu)request的使用十分頻繁，需要不斷地創(chuàng)建和釋放。如果因?yàn)槲锢韮?nèi)存緊張而無法創(chuàng)建request結(jié)構(gòu)，系統(tǒng)對塊設(shè)備的操作請求將無法遞交，嚴(yán)重時會影響物理內(nèi)存回收，甚至?xí)?dǎo)致系統(tǒng)崩潰。為解決上述問題，Linux為每個請求隊(duì)列都準(zhǔn)備了一個空閑請求池，在其中預(yù)留了一些(至少4個)空閑的request結(jié)構(gòu)，以備急需。

(4)隊(duì)列上限nr_requests。雖然適當(dāng)?shù)厥占埱罂商岣邏K設(shè)備操作的性能，但收集的請求數(shù)也不宜太多。當(dāng)隊(duì)列中的請求數(shù)超過nr_congestion_on時，說明該隊(duì)列出現(xiàn)了擁塞，需降低請求產(chǎn)生的速度；當(dāng)隊(duì)列中的請求數(shù)超過上限nr_requests(缺省值為128)時，說明隊(duì)列已滿，應(yīng)將新的請求者進(jìn)程掛在請求池rq的隊(duì)列中等待。

(5)請求隊(duì)列管理操作，主要包括如下幾個：

①新請求創(chuàng)建操作make_request_fn。該操作用于將新的請求加入到請求隊(duì)列中，常用的是函數(shù)_

_make_request()。②物理塊設(shè)備拔出操作unplug_fn。當(dāng)物理塊設(shè)備處于插入(或凍結(jié))狀態(tài)時，它接收但不處理請求，新到達(dá)的請求被掛在隊(duì)列中排隊(duì)；當(dāng)物理塊設(shè)備被拔出(或激活)時，它執(zhí)行隊(duì)列中的unplug_fn操作，一次性地處理完隊(duì)列中的所有請求。設(shè)備被拔出的條件很多，如隊(duì)列滿、等待超時、設(shè)備同步等。

③請求處理操作request_fn。操作request_fn是物理塊設(shè)備驅(qū)動程序必須提供的核心操作，用于驅(qū)動塊設(shè)備硬件，處理針對塊設(shè)備的操作請求。當(dāng)物理塊設(shè)備被拔出時，該操作被執(zhí)行，在設(shè)備上等待的請求會被該操作逐個處理，各請求所要求的操作(讀、寫塊設(shè)備)會被逐個執(zhí)行。

④塊設(shè)備軟中斷處理操作softirq_done_fn。如果隊(duì)列中的請求過多，對它們的處理時間就可能很長，嚴(yán)重時會影響其它工作的處理。為解決這一問題，Linux將大量的操作請求交給塊設(shè)備軟中斷BLOCK_SOFTIRQ(具體的處理方法由softirq_done_fn定義)。

(6)定時器unplug_timer、定時間隔unplug_delay、隊(duì)列上限unplug_thresh等用于控制物理塊設(shè)備的拔出時機(jī)。

當(dāng)物理塊設(shè)備被發(fā)現(xiàn)時，系統(tǒng)會為其建立私有的管理結(jié)構(gòu)，如SCSI的scsi_device，其中肯定包括一個請求隊(duì)列。在物理塊設(shè)備被初始化的同時，它的請求隊(duì)列也會被初始化，其中的I/O調(diào)度器和請求隊(duì)列管理操作都會被指定。當(dāng)物理塊設(shè)備被驅(qū)動程序發(fā)現(xiàn)時，它的gendisk結(jié)構(gòu)會被建立，其中的queue域就被設(shè)成私有管理結(jié)構(gòu)中的請求隊(duì)列。由于該隊(duì)列已被初始化，因而可以直接使用。12.1.5請求遞交

請求隊(duì)列中的request結(jié)構(gòu)是動態(tài)創(chuàng)建并加入的。物理文件系統(tǒng)將自己的數(shù)據(jù)傳送需求包裝在bio結(jié)構(gòu)中，而后通過函數(shù)generic_make_request()遞交給塊設(shè)備管理層。物理文件系統(tǒng)每次僅遞交一個bio，它所表示的邏輯塊在設(shè)備上是連續(xù)的(由若干個連續(xù)的扇區(qū)組成)。若物理文件系統(tǒng)要讀寫不連續(xù)的邏輯塊，它需要創(chuàng)建多個bio結(jié)構(gòu)。特別地，讀、寫bio的善后處理函數(shù)分別是mpage_end_io_read()和mpage_end_io_write()。函數(shù)generic_make_request()完成如下的處理工作：

(1)對請求的大小、位置等進(jìn)行合法性檢查。

(2)如果bio是對物理分區(qū)的操作請求，那么其中的bi_bdev指向的是代表分區(qū)的邏輯塊設(shè)備，bi_sector是相對于分區(qū)開始位置的扇區(qū)號，需要將bi_bdev改成代表整個物理塊設(shè)備的block_device結(jié)構(gòu)，將bi_sector改成相對于物理塊設(shè)備開始位置的扇區(qū)號，從而將對物理分區(qū)的操作請求轉(zhuǎn)化為對物理塊設(shè)備的操作請求。

(3)執(zhí)行物理塊設(shè)備請求隊(duì)列中的make_request_fn操作，完成新請求的遞交。

一般情況下，系統(tǒng)為請求隊(duì)列指定的make_request_fn操作都是_

_make_request()。函數(shù)

_

_make_request()是塊設(shè)備I/O調(diào)度器的對外接口，其基本的思路是將新到來的bio結(jié)構(gòu)交給物理塊設(shè)備的I/O調(diào)度器，由I/O調(diào)度器根據(jù)自己的調(diào)度策略決定下一步的處理方法，大致有以下三種：

(1)將bio結(jié)構(gòu)合并到某request的隊(duì)尾。如果I/O調(diào)度器發(fā)現(xiàn)新bio的開始位置與隊(duì)列中某個request結(jié)構(gòu)的終止位置在物理上是鄰接的且它們的傳送方向一致，則可將新bio插入到該request結(jié)構(gòu)的隊(duì)尾(域biotail指向隊(duì)尾)。

如果新bio的加入使該request與其后的request變成鄰接的，且它們的傳送方向也一致，則可以將后一個request中的bio合并到該request中，并將后一個request釋放。

(2)將bio結(jié)構(gòu)合并到某request的隊(duì)頭。如果I/O調(diào)度器發(fā)現(xiàn)新bio的終止位置與隊(duì)列中某個request結(jié)構(gòu)的開始位置在物理上是鄰接的且它們的傳送方向一致，則可將新bio插入到該request結(jié)構(gòu)的隊(duì)頭(域bio指向隊(duì)頭)。

如果新bio的加入使該request與前一個request變成鄰接的，且它們的傳送方向也一致，則可以將該request中的bio合并到前一個request中，并將該request釋放。

(3)為bio創(chuàng)建一個全新的request結(jié)構(gòu)。如果I/O調(diào)度器發(fā)現(xiàn)新bio不與隊(duì)列中任何request鄰接，或雖然鄰接但傳送方向不一致，無法將新bio合并到已有的request結(jié)構(gòu)中，則必須為其新建一個request。新request結(jié)構(gòu)的內(nèi)容大都來自bio結(jié)構(gòu)，且會被I/O調(diào)度器插入到隊(duì)列中的合適位置。

由于隊(duì)列中加入了新的請求，因而需要調(diào)整物理塊設(shè)備的狀態(tài)。如果隊(duì)列此前是空的，一般應(yīng)將塊設(shè)備置為插入(或凍結(jié))狀態(tài)；如果請求者特別指定或塊設(shè)備不需要按批量方式處理操作請求，則應(yīng)立刻將其拔出。其它情況下不需要對塊設(shè)備的狀態(tài)做特別處理，新請求將一直留在請求隊(duì)列中等待，直到物理塊設(shè)備被拔出。12.1.6請求處理

不管引起拔出的原因是什么，一旦物理塊設(shè)備被拔出，它的unplug_fn操作就會被執(zhí)行。雖然不同種類的物理塊設(shè)備可能為自己指定不同的unplug_fn操作，但它們最終都會執(zhí)行隊(duì)列中的request_fn操作。

操作request_fn由底層的塊設(shè)備驅(qū)動程序提供，用于批量處理請求隊(duì)列中的塊設(shè)備操作請求，即處理隊(duì)列中的各個request結(jié)構(gòu)。如果請求隊(duì)列中有多個request結(jié)構(gòu)，各結(jié)構(gòu)的處理順序由物理塊設(shè)備自己的I/O調(diào)度器決定。不同種類的物理塊設(shè)備對操作請求的處理方法也不同。IDE類磁盤的驅(qū)動程序會將一個request結(jié)構(gòu)翻譯成對DMA控制器和磁盤控制器的設(shè)置操作，從而啟動一到多次數(shù)據(jù)傳送。SCSI類磁盤的驅(qū)動程序會將一個request結(jié)構(gòu)翻譯成一組SCSI命令，并通過SCSI總線將其發(fā)送給SCSI目標(biāo)器(target)，從而啟動一次數(shù)據(jù)傳送。

總之，物理塊設(shè)備的底層驅(qū)動程序會將一個request結(jié)構(gòu)翻譯成一組硬件操作，從而控制底層的硬件設(shè)備完成預(yù)定的數(shù)據(jù)傳送操作，即將數(shù)據(jù)由物理內(nèi)存寫到指定的扇區(qū)中，或?qū)⒅付ㄉ葏^(qū)中的數(shù)據(jù)讀到物理內(nèi)存的預(yù)定位置。

處理后的request結(jié)構(gòu)會被從隊(duì)列中摘下，其中各個bio中的善后處理程序bi_end_io會被執(zhí)行，request及其中的bio結(jié)構(gòu)會被釋放，等待者進(jìn)程也會被喚醒。

雖然Linux已可支持?jǐn)?shù)十種物理文件系統(tǒng)，但EXT(ExtendedFileSystem)系列的文件系統(tǒng)一直是它的核心。EXT是多種Linux發(fā)布中的缺省文件系統(tǒng)，是Linux物理文件系統(tǒng)的典型代表。

在開發(fā)之初，Linux的文件系統(tǒng)是從Minix中借來的。由于Minix的文件系統(tǒng)是為教學(xué)設(shè)計(jì)的，容量小、名字短，不大適合在正式系統(tǒng)中使用，因而在1992年發(fā)布的0.96c版中，Linux引入了虛擬文件系統(tǒng)VFS和擴(kuò)展文件系統(tǒng)EXT。EXT是專門為Linux設(shè)計(jì)的第一個物理文件系統(tǒng)，12.2EXT文件系統(tǒng)其最初的設(shè)計(jì)靈感來源于UFS(UnixFileSystem)，后又從FFS(FastFileSystem)中借鑒了大量的設(shè)計(jì)理念，形成了EXT2文件系統(tǒng)。在2001發(fā)布的2.4.15版中，Linux又在EXT2中集成了日志機(jī)制以便提高系統(tǒng)的可靠性，由此形成了EXT3文件系統(tǒng)。2008年，受CFS(ClusterFileSystem)的啟發(fā)，EXT3的容量被擴(kuò)展、塊管理算法被改善，形成了EXT4文件系統(tǒng)。

物理文件系統(tǒng)的設(shè)計(jì)比較復(fù)雜，其設(shè)計(jì)工作大致包括三個方面，一是確定物理文件系統(tǒng)在塊設(shè)備上的布局并定義物理文件系統(tǒng)的管理結(jié)構(gòu)，二是設(shè)計(jì)邏輯塊和inode的管理算法，三是實(shí)現(xiàn)VFS的底層接口，包括超級塊操作集、inode操作集、文件操作集、地址空間操作集等。12.2.1EXT文件系統(tǒng)布局

EXT文件系統(tǒng)建立在塊設(shè)備之上，它的每個實(shí)例可用于管理塊設(shè)備的一個分區(qū)。為了管理方便，EXT將一個分區(qū)看成一個大的邏輯塊數(shù)組，并將該數(shù)組劃分成一系列等尺寸的塊組(BlockGroup)。一個塊組中包含一組連續(xù)的邏輯塊。塊組中的邏輯塊除用于存儲文件數(shù)據(jù)之外，還需要存儲塊組自身的管理信息，如塊位圖、inode位圖、inode表等，并需要備份全文件系統(tǒng)的管理信息，如超級塊、塊組表等。

在圖12.7所示的EXT文件系統(tǒng)布局中，超級塊和塊組表屬于冗余信息，不需要在每個塊組中備份。事實(shí)上僅有幾個塊組中含有備份信息，如塊組1、塊組3n、塊組5n、塊組7n等。塊組自身的管理信息是獨(dú)立的，沒有備份。圖12.7EXT文件系統(tǒng)在塊設(shè)備上的布局超級塊中記錄著EXT文件系統(tǒng)的總體描述信息，其長度雖只有1024字節(jié)，卻占用1個完整的邏輯塊。第0塊組的超級塊中可能有一個引導(dǎo)扇區(qū)，備份的超級塊中都沒有引導(dǎo)扇區(qū)。圖12.8所示是三類塊組的布局結(jié)構(gòu)。

塊組表是一個結(jié)構(gòu)數(shù)組，其中的一個結(jié)構(gòu)描述一個塊組的狀態(tài)。單個塊組結(jié)構(gòu)的長度為32字節(jié)，塊組表的大小=塊組個數(shù)×32字節(jié)，占用一到多個邏輯塊。

塊位圖占用1個邏輯塊，其中的每一位描述塊組中一個邏輯塊的使用情況，是邏輯塊分配與回收的依據(jù)。若邏輯塊的大小為4KB，那么一個塊組中可含4096

×

8

=

0x8000個邏輯塊，大小可達(dá)128MB，第m塊組的第n位描述的是塊設(shè)備中第m

×

0x8000

+

n個邏輯塊的使用情況。

EXT的inode位圖占用1個邏輯塊，其中的每一位描述塊組中一個EXTinode的使用情況，是EXTinode管理的依據(jù)。若邏輯塊的大小為4KB，那么一個塊組中最多可定義0x8000個EXTinode。在實(shí)際系統(tǒng)中，單個塊組中定義的EXTinode數(shù)通常遠(yuǎn)小于0x8000，如0x3f40。第m塊組的第n位描述的是整個EXT中第m

×

0x3f40

+

n

+

1個inode的使用情況。

圖12.8不同類型的塊組布局

inode表是一個EXTinode結(jié)構(gòu)的數(shù)組，其中的一個結(jié)構(gòu)描述一個EXT實(shí)體的狀態(tài)。inode表是在EXT文件系統(tǒng)創(chuàng)建時建立的，其中的inode數(shù)是固定的。EXT的每個inode占用0x80字節(jié)，單個塊組中的inode表會占用多個邏輯塊。不管一個EXT文件系統(tǒng)管理多少個塊組，它的inode都是統(tǒng)一編號的(從1開始)，如第0塊組中的inode號從1到0x3f40，第1塊組中的inode號從0x3f41到0x7e80等。

inode表后面的數(shù)據(jù)塊表是一個邏輯塊的數(shù)組，其中的邏輯塊可分配給任意一個文件，用于保存文件的內(nèi)容或索引表。12.2.2EXT管理結(jié)構(gòu)

與VFS不同，EXT文件系統(tǒng)的管理信息永久地駐留在塊設(shè)備之中。為了便于使用，EXT將自己的管理信息包裝在多個結(jié)構(gòu)中，包括超級塊結(jié)構(gòu)、塊組結(jié)構(gòu)、inode結(jié)構(gòu)、目錄項(xiàng)結(jié)構(gòu)等。隨著EXT的升級，它的管理結(jié)構(gòu)也在不斷變化，但維持了向后的兼容性。事實(shí)上，在設(shè)計(jì)之初，EXT就在其管理結(jié)構(gòu)中留出了足夠的空閑空間，利用這些空間可以定義許多新的特性，如日志等。所有版本的EXT使用的是同樣的管理結(jié)構(gòu)，新版本增加的特性全都位于老版本的填充部分。下面列出的管理結(jié)構(gòu)來源于EXT2文件系統(tǒng)，是EXT管理結(jié)構(gòu)的基礎(chǔ)與核心。

在EXT管理結(jié)構(gòu)中，類型_le32和_u32是32位無符號整數(shù)、_le16和_u16是16位無符號整數(shù)、_u8是8位無符號整數(shù)。

1.超級塊結(jié)構(gòu)

超級塊結(jié)構(gòu)描述整個EXT文件系統(tǒng)的狀態(tài)，包括邏輯塊的大小、總塊數(shù)和空閑塊數(shù)、總inode數(shù)和空閑inode數(shù)、標(biāo)識、版本號、安裝時間、修改時間等。EXT2用結(jié)構(gòu)ext2_super_block定義其超級塊，其主要內(nèi)容如下：

structext2_super_block{

_le32 s_inodes_count; //EXTinode結(jié)構(gòu)的總數(shù)

_le32 s_blocks_count; //邏輯塊總數(shù)

_le32 s_r_blocks_count; //預(yù)留的邏輯塊數(shù)

_le32 s_free_blocks_count; //空閑的邏輯塊數(shù)

_le32 s_free_inodes_count; //空閑的EXTinode數(shù)

_le32 s_first_data_block; //第一個邏輯塊的編號

_le32 s_log_block_size; //邏輯塊的大小

_le32 s_log_frag_size; //片段的大小

_le32 s_blocks_per_group; //每個塊組中的邏輯塊數(shù)

_le32 s_frags_per_group; //每個塊組中的片段數(shù)

_le32 s_inodes_per_group; //每個塊組中的EXTinode數(shù)

_le32 s_mtime; //安裝時間

_le32 s_wtime; //最后一次寫操作的時間

_le16 s_mnt_count; //安裝次數(shù)

_le16 s_max_mnt_count; //最大安裝次數(shù)

_le16 s_magic; //魔數(shù)

_le16 s_state; //狀態(tài)，上次是否被正常卸載

_le16 s_errors; //發(fā)生錯誤時的處理方式，如只讀重裝

_le16 s_minor_rev_level; //次版本號

_le32 s_lastcheck; //上一次檢查的時間

_le32 s_checkinterval; //兩次檢查間的最大時間間隔

_le32 s_creator_os; //創(chuàng)建該實(shí)例的操作系統(tǒng)

_le32 s_rev_level; //主版本號

_le16 s_def_resuid; //可使用預(yù)留塊的用戶UID

_le16 s_def_resgid; //可使用預(yù)留塊的用戶GID

_le32 s_first_ino; //第一個非預(yù)留的EXTinode號

_le16 s_inode_size; //EXTinode結(jié)構(gòu)的長度

_le16 s_block_group_nr; //該超級塊所在的塊組號

_le32 s_feature_compat; //兼容特性集

_le32 s_feature_incompat; //非兼容特性集

_le32 s_feature_ro_compat; //只讀的兼容特性集

_u8 s_uuid[16]; //128位的uuid

char s_volume_name[16]; //卷名

char s_last_mounted[64]; //上一次安裝時的安裝點(diǎn)

_le32 s_algorithm_usage_bitmap; //壓縮算法專用位圖

_u8 s_prealloc_blocks; //預(yù)分配塊數(shù)

_u8 s_prealloc_dir_blocks; //為目錄預(yù)分配的塊數(shù)

};魔數(shù)s_magic是EXT文件系統(tǒng)的標(biāo)識，其值為0xEF53。

邏輯塊的大小s_log_block_size是個指數(shù)，真正的塊大小為2s_log_block_sizeKB。邏輯塊的大小是在文件系統(tǒng)創(chuàng)建時決定的，可選的值有三個，分別是1KB、2KB和4KB。塊大小是EXT文件系統(tǒng)的核心參數(shù)，是所有管理結(jié)構(gòu)建立的基礎(chǔ)，不允許動態(tài)修改。

為了便于管理，EXT文件系統(tǒng)預(yù)留了幾個inode結(jié)構(gòu)，其中第1號為壞塊inode、第2號為根inode、第4號為ACLDATA、第8號為JOURNAL等?？煞峙浣o用戶使用的第一個EXTinode號記錄在s_first_ino中。

EXT文件系統(tǒng)在不斷變化，新的特征不斷被引入。為了維護(hù)系統(tǒng)的兼容性，需要記錄本EXT實(shí)例適用與不適用的特征，為此EXT在其超級塊中定義了三個位圖，其中s_feature_compat是可在本實(shí)例上使用的特征(如日志、擴(kuò)展屬性等)、s_feature_incompat是不可在本實(shí)例上使用的特征(如壓縮、恢復(fù)等)、s_feature_ro_compat是只可在本實(shí)例上以只讀方式使用的特征(如超大文件、BTREE目錄等)。圖12.9所示是超級塊結(jié)構(gòu)的一個實(shí)例片段，其意義可對照定義解析出來，如總EXTinode數(shù)為0x000BDC00、總塊數(shù)為0x0017AF90、空閑塊數(shù)為0x000EB2C4、空閑EXTinode數(shù)為0x000977A4、塊大小為4KB、單個塊組中的邏輯塊數(shù)為0x8000、單個塊組中的EXTinode數(shù)為0x3f40、第一個可分配的EXTinode號為0x0000000B等。

圖12.9EXT超級塊結(jié)構(gòu)的一個實(shí)例

2.塊組結(jié)構(gòu)

塊組負(fù)責(zé)邏輯塊和EXTinode的實(shí)際管理，如分配、回收等，因此需在其中記錄各邏輯塊和EXTinode結(jié)構(gòu)的狀態(tài)。EXT2用結(jié)構(gòu)ext2_group_desc定義單個塊組的管理信息。塊組表實(shí)際是一個ext2_group_desc結(jié)構(gòu)的數(shù)組。

structext2_group_desc{

_le32 bg_block_bitmap; //塊位圖所在的邏輯塊號

_le32 bg_inode_bitmap; //EXTinode位圖所在的邏輯塊號

_le32 bg_inode_table; //EXTinode表所在的邏輯塊號

_le16 bg_free_blocks_count; //組中當(dāng)前空閑的邏輯塊數(shù)

_le16 bg_free_inodes_count; //組中當(dāng)前空閑的EXTinode數(shù)

_le16 bg_used_dirs_count; //組中當(dāng)前包含的目錄數(shù)

_le16 bg_pad[7]; //填充

};圖12.10所示是塊組結(jié)構(gòu)的一個實(shí)例，其意義可對照定義解出，如塊位圖在第2塊上、EXTinode位圖在第3塊上、EXTinode表從第4塊開始，塊組中剩余的空閑塊數(shù)為0x2578、空閑EXTinode數(shù)為0x3D12，其中有0x0019個目錄。

圖12.10EXT塊組結(jié)構(gòu)的一個實(shí)例

3.?EXTinode結(jié)構(gòu)

EXT的inode結(jié)構(gòu)就是所謂的文件控制塊，用于記錄文件系統(tǒng)中一個實(shí)體的所有管理信息，如屬主、權(quán)限、大小、修改時間、存儲位置等。

用戶看到的文件是一組連續(xù)的字節(jié)，但物理文件系統(tǒng)看到的文件卻是一組邏輯塊，可能連續(xù)，也可能不連續(xù)。物理文件系統(tǒng)的一個主要管理工作是記錄各文件塊的存儲位置，或者說記錄各文件塊與邏輯塊之間的映射關(guān)系。記錄映射關(guān)系的方法很多，如串聯(lián)結(jié)構(gòu)、索引結(jié)構(gòu)等，最直觀的方法是為每個文件建立一個類似于頁表的索引表，在其中記錄文件塊與邏輯塊之間的映射關(guān)系，如圖12.11所示。

圖12.11文件塊與邏輯塊之間的映射顯然，文件索引表應(yīng)該是動態(tài)可調(diào)的，其大小應(yīng)與文件大小一致。由于EXT所管理的文件可能很大，因而其索引表也可能很大，而且可能會動態(tài)地?cái)U(kuò)展與收縮，所以定義連續(xù)的、單級大索引表是不現(xiàn)實(shí)的，應(yīng)該借鑒進(jìn)程虛擬內(nèi)存的管理經(jīng)驗(yàn)，為文件建立多級索引表，類似于頁目錄/頁表。然而目前的計(jì)算機(jī)系統(tǒng)都未對文件索引表的查找提供硬件支持，因而隨著索引級數(shù)的增加，文件訪問的性能必然會直線下降。為了提高文件訪問的性能，應(yīng)該盡可能降低索引表的級數(shù)。為了兼顧文件大小和訪問性能，EXT為每個文件都定義了一個索引表集合，其中包括一個三級索引表、一個二級索引表和一個一級索引表，還包含若干個直接索引，如圖12.12所示。

圖12.12EXT的文件索引表集合缺省情況下，EXT的索引表集合由15個指針構(gòu)成，每個指針都指向一個邏輯塊(內(nèi)容為邏輯塊號)。第0～11個指針?biāo)傅倪壿媺K中存儲的是文件內(nèi)容，這12個指針被稱為直接指針；第12個指針?biāo)傅倪壿媺K中存儲的是一個一級索引表，其中的每個指針都指向一個用于存儲文件內(nèi)容的邏輯塊，第12個指針被稱為一次間接指針；第13個指針?biāo)傅倪壿媺K中存儲的是一個二級索引表，其中的每個一次間接指針都指向一個一級索引表，第13個指針被稱為二次間接指針；第14個指針?biāo)傅倪壿媺K中存儲的是一個三級索引表，其中的每個二次間接指針都指向一個二級索引表，第14個指針被稱為三次間接指針。

當(dāng)文件的長度少于或等于12塊時，可以通過索引表集合中的前12個直接指針記錄它的文件塊與邏輯塊的映射關(guān)系。當(dāng)文件長度超過12塊時，可通過索引表集合中的一級、二級或三級索引表記錄它的文件塊與邏輯塊的映射關(guān)系。除前12個直接指針之外，索引表集合中的一級、二級和三級索引表都是在文件擴(kuò)張的過程中逐步建立的。

若邏輯塊的大小為4KB，指針的長度為4字節(jié)，則理論上一個索引表集合所描述的文件長度可達(dá)4TB(12

×

4KB

+

1024

×

4KB

+

1024

×

1024

×

4KB

+

1024

×

1024

×

1024

×

4KB)。給出一個文件塊號m，查它的索引表集合，可找到與之對應(yīng)的邏輯塊號。

如果m<12，則索引表集合中的第m個指針的內(nèi)容就是邏輯塊號。

如果m<1024

+

12，則一級索引表中第m-12指針的內(nèi)容就是邏輯塊號。

如果m<10242

+

1024

+

12，則用m-1024-12查二級索引表可得邏輯塊號。

④

如果m<10243

+

10242

+

1024

+

12，則用m-10242-1024-12查三級索引表可得邏輯塊號。多級索引表的查找方法與多級頁表的查找方法相同。

EXT的索引表集合是一種較好的文件描述方式，既可表示大文件，又照顧到了小文件。由于大部分文件的長度都比較小，可用直接指針描述其映射關(guān)系，無需建立索引表，節(jié)約了存儲空間。利用索引表集合，EXT2定義了它的inode結(jié)構(gòu)，稱為ext2_inode。塊組中的EXTinode表實(shí)際就是一個ext2_inode結(jié)構(gòu)的數(shù)組。下面是ext2_inode結(jié)構(gòu)的一種簡化版本。

structext2_inode{

_le16 i_mode; //文件模式，如圖11.3所示

_le16 i_uid; //屬主UID的低16位

_le32 i_size; //文件大小，單位為字節(jié)

_le32 i_atime; //最近一次存取時間

_le32 i_ctime; //最近一次修改EXTinode結(jié)構(gòu)的時間

_le32 i_mtime; //最近一次修改文件內(nèi)容的時間

_le32 i_dtime; //文件刪除的時間

_le16 i_gid; //屬主GID的低16位

_le16 i_links_count; //文件的硬鏈接數(shù)

_le32 i_blocks; //文件實(shí)際占用的扇區(qū)數(shù)

_le32 i_flags; //文件標(biāo)志

_le32 i_reserved1; //填充

_le32 i_block[15]; //文件索引表集合

_le32 i_generation; //文件版本

_le32 i_file_acl; //文件存取控制表

_le32 i_dir_acl; //目錄存取控制表

_le32 i_faddr; //文件片段地址

_u8 i_frag; //文件片段數(shù)

_u8 i_fsize; //片段大小

_u16 i_pad1; //填充

_le16 i_uid_high; //屬主UID的高16位

_le16 i_gid_high; //屬主GID的高16位

_u32 i_reserved2; //填充

};

在普通文件的ext2_inode結(jié)構(gòu)中，i_block[]用于記錄各文件塊的存儲位置。在設(shè)備特殊文件的ext2_inode結(jié)構(gòu)中，i_block[]用于記錄設(shè)備號。在符號鏈接的ext2_inode結(jié)構(gòu)中，i_block[]用于記錄目標(biāo)實(shí)體的路徑名。圖12.13所示是EXTinode結(jié)構(gòu)的一個實(shí)例，所表示的實(shí)體為系統(tǒng)的根目錄，其意義可對照定義解出，如它的UID和GID都是0(根用戶)、大小為1塊(8扇區(qū))、存儲位置為0x000001FE。

圖12.13EXTinode結(jié)構(gòu)的一個實(shí)例片段

4.目錄項(xiàng)結(jié)構(gòu)

有了EXTinode表之后，只要知道實(shí)體的EXTinode號(在表中的索引)，就可找到它的EXTinode結(jié)構(gòu)，也就是說可用EXTinode號唯一地標(biāo)識實(shí)體。用EXTinode號標(biāo)識實(shí)體對操作系統(tǒng)內(nèi)核是方便的，但卻難以被用戶接受。用戶更希望用名稱標(biāo)識實(shí)體，并希望能夠根據(jù)需要對實(shí)體進(jìn)行分類、組織，因而EXT引入了目錄。

目錄是一種特殊類型的文件，其正文是一組目錄項(xiàng)。目錄項(xiàng)的主要內(nèi)容有兩個，一是實(shí)體的名稱，二是實(shí)體的EXTinode號。給出一個實(shí)體名，可從目錄文件中找到與之對應(yīng)的目錄項(xiàng)，從中可獲得實(shí)體的EXTinode號，進(jìn)而可找到實(shí)體的EXTinode結(jié)構(gòu)。因而目錄項(xiàng)所描述的實(shí)際是實(shí)體名稱與EXTinode之間的映射關(guān)系，稱為硬鏈接。一個EXTinode號可以出現(xiàn)在多個目錄項(xiàng)中，從而可為實(shí)體定義多個硬鏈接，或多個路徑名。結(jié)構(gòu)ext2_inode中的域i_links_count記錄著實(shí)體的硬鏈接數(shù)或路徑名數(shù)。EXT2用結(jié)構(gòu)ext2_dir_entry_2定義其目錄項(xiàng)。

structext2_dir_entry_2{

_le32 inode; //EXTinode號

_le16 rec_len; //目錄項(xiàng)長度

_u8 name_len; //名稱長度

_u8 file_type; //實(shí)體類型

char name[255]; //實(shí)體名稱

};缺省情況下，實(shí)體名稱的長度可達(dá)255個字符。若按最大長度定義各目錄項(xiàng)，目錄文件就是一個目錄項(xiàng)的數(shù)組，雖然實(shí)現(xiàn)簡單，但卻會浪費(fèi)存儲空間，原因是大部分實(shí)體的名稱都比較短。為了節(jié)省存儲空間，EXT允許按名稱的實(shí)際長度定義目錄項(xiàng)，因此才有了結(jié)構(gòu)中的目錄項(xiàng)長度rec_len和名稱長度name_len域。由于各目錄項(xiàng)的長度可能不等，因而目錄文件不是嚴(yán)格意義上的結(jié)構(gòu)數(shù)組，而是目錄項(xiàng)的集合，對實(shí)體名稱的搜索必須順序進(jìn)行。

另外，出于對齊的需要，目錄項(xiàng)長度rec_len常被規(guī)約成4的倍數(shù)。域file_type中記錄的是實(shí)體的類型，應(yīng)該與ext2_inode結(jié)構(gòu)中的i_mode一致，其中1為普通文件、2為目錄文件、3為字符設(shè)備特殊文件、4為塊設(shè)備特殊文件、5為命名管道、6為Socket、7為符號鏈接。

圖12.14所示是根目錄文件的一個片段，其意義可對照定義解出，如第一個目錄項(xiàng)的名稱是“.”、EXTinode號是2(根目錄)，第二個目錄項(xiàng)的名稱是“..”、EXTinode號是2，第三個目錄項(xiàng)的名稱是“mnt”、EXTinode號是0x00007E81等。

圖12.14EXT目錄文件的實(shí)例片段

5.?EXT專用管理結(jié)構(gòu)

上述四類結(jié)構(gòu)可描述EXT在塊設(shè)備上的所有管理信息。當(dāng)EXT文件系統(tǒng)被安裝時，VFS會請求EXT讀入其超級塊，以構(gòu)造通用的super_block結(jié)構(gòu)。當(dāng)EXT中的實(shí)體名稱被解析時，VFS會請求EXT讀入其目錄項(xiàng)和EXTinode，以構(gòu)造通用的dentry和VFSinode結(jié)構(gòu)。然而VFS的管理結(jié)構(gòu)中僅包含一些通用的信息，EXT專用的管理信息，如塊組結(jié)構(gòu)、文件索引表集合等，無法填入其中卻又會被經(jīng)常使用，因而需要再定義一些專用結(jié)構(gòu)，并將它們與VFS的通用結(jié)構(gòu)綁定在一起，以方便EXT的管理。EXT主要定義了兩個專用管理結(jié)構(gòu)，一是ext2_sb_info，二是ext2_inode_info。結(jié)構(gòu)ext2_sb_info的內(nèi)容來源于EXT的超級塊和塊組表，包括每塊組中的EXTinode數(shù)、每塊組中的塊數(shù)、EXTinode結(jié)構(gòu)的大小、第一個非預(yù)留的EXTinode號、空閑塊數(shù)、空閑EXTinode數(shù)、塊組結(jié)構(gòu)數(shù)組、預(yù)分配窗口紅黑樹等，另有一個指向超級塊結(jié)構(gòu)ext2_super_block的指針。VFSsuper_block與ext2_sb_info的綁定方法比較直接，讓super_block中的指針s_fs_info指向ext2_sb_info即可。在EXT文件系統(tǒng)活動期間，它的super_block和ext2_sb_info會常駐內(nèi)存。結(jié)構(gòu)ext2_inode_info的內(nèi)容來源于EXT的inode結(jié)構(gòu)，主要是文件的索引表集合。VFSinode結(jié)構(gòu)中預(yù)留了一個指針i_private，可用于綁定文件的ext2_inode_info結(jié)構(gòu)。但EXT采用了另一種綁定方法，它直接將VFSinode嵌入在ext2_inode_info中。只要文件的VFSinode存在，它的ext2_inode_info就會存在。12.2.3EXT邏輯塊管理

在格式化剛完成之時，EXT在塊設(shè)備上僅建立了超級塊、塊組表、inode表、inode位圖、塊位圖等管理結(jié)構(gòu)，數(shù)據(jù)塊表中的邏輯塊大都處于空閑狀態(tài)。在向文件寫入數(shù)據(jù)的過程中，若發(fā)現(xiàn)某文件塊所對應(yīng)的邏輯塊為空，EXT會自動為其分配邏輯塊，并在文件的索引表集合中記錄文件塊與邏輯塊的映射關(guān)系。在文件收縮長度或被刪除時，EXT會釋放它所占用的邏輯塊。邏輯塊的分配與釋放是EXT的核心管理工作之一。

EXT所管理的邏輯塊只能分配給文件，包括普通文件、目錄和符號鏈接。設(shè)備特殊文件、命名管道文件和Socket文件中沒有任何數(shù)據(jù)，不需要邏輯塊。由于EXT用索引表描述文件塊與邏輯塊之間的映射關(guān)系，因而文件在塊設(shè)備上可以不連續(xù)。但若文件的存放過于散亂，對它的存取，尤其是順序存取，必然會引起過多的磁頭移動，會影響文件的訪問性能。因而邏輯塊分配的基本原則是盡力維持文件在塊設(shè)備上的連續(xù)性。

大部分文件會在寫操作過程中順序地、逐步地增長，所以可以以塊為單位逐步為其分配邏輯塊，分配的步驟大致如下：

(1)確定搜索的起點(diǎn)，如與前一個文件塊鄰接的邏輯塊。

(2)確定搜索起點(diǎn)所在的塊組，讀入其塊位圖。

(3)從起點(diǎn)開始，順序搜索塊位圖，找一個標(biāo)志為0的位，將其置1，將與之對應(yīng)的邏輯塊分配給文件。如所選塊組中沒有空閑塊，則搜索下一個塊組。

上述分配方法雖然簡單，但當(dāng)多個文件并發(fā)增長時，很難保證文件在塊設(shè)備上的連續(xù)性。為解決這一問題，EXT引入了預(yù)分配(pre-allocation)機(jī)制，其思路是為啟用該機(jī)制的每個文件都預(yù)定一個邏輯塊的分配區(qū)間，稱為預(yù)分配窗口。EXT保證各文件的預(yù)分配窗口互不重疊，但不保證其中的邏輯塊都是空閑的。當(dāng)需要為文件按序分配邏輯塊時，EXT會首先在它的預(yù)分配窗口中尋找空閑塊。當(dāng)預(yù)分配窗口中的邏輯塊全被用完之后，EXT會為文件再尋找新的預(yù)分配窗口。

顯然，預(yù)分配窗口是提供給邏輯塊分配算法的一種暗示。即使有多個文件并發(fā)地申請邏輯塊，只要依照預(yù)分配窗口的暗示，EXT就能盡力保證單個文件的連續(xù)性，如圖12.15所示。值得注意的是，預(yù)分配窗口中的邏輯塊并未真正分配給文件。圖12.15EXT的文件預(yù)分配窗口為了實(shí)現(xiàn)預(yù)分配機(jī)制，EXT為每個文件定義了一個ext2_block_alloc_info結(jié)構(gòu)。文件ext2_inode_info結(jié)構(gòu)中的域i_block_alloc_info指向它的ext2_block_alloc_info結(jié)構(gòu)。

structext2_reserve_window{

ext2_fsblk_t _rsv_start; //窗口的開始塊號

ext2_fsblk_t _rsv_end; //窗口的終止塊號

};

structext2_reserve_window_node{

structrb_node rsv_node; //紅黑樹節(jié)點(diǎn)

_u32 rsv_goal_size; //期望的窗口尺寸

_u32 rsv_alloc_hit; //窗口的命中率

structext2_reserve_window rsv_window;

};

structext2_block_alloc_info{

structext2_reserve_window_node rsv_window_node;

_u32 last_alloc_logical_block; //上次分配的文件塊號

ext2_fsblk_t last_alloc_physical_block; //上次分配的邏輯塊號

};

屬于一個EXT文件系統(tǒng)的所有ext2_block_alloc_info結(jié)構(gòu)被組織成一棵紅黑樹，樹根記錄在結(jié)構(gòu)ext2_sb_info的s_rsv_window_root域中，如圖12.16所示。

圖12.16預(yù)分配窗口管理結(jié)構(gòu)結(jié)構(gòu)ext2_block_alloc_info是動態(tài)建立的，其值不需要保存到文件中。初始情況下，域rsv_goal_size的值是8(期望的窗口尺寸是8個邏輯塊)，其余各域的值都是0。

當(dāng)下列情況下之一發(fā)生時，EXT會為文件建立新的預(yù)分配窗口：

(1)需要為文件分配邏輯塊但還未為其建立預(yù)分配窗口(_rsv_end為0)。

(2)已無法從文件的預(yù)分配窗口中分配出新的邏輯塊。

(3)

EXT建議的分配位置不在當(dāng)前的預(yù)分配窗口之內(nèi)。在建立預(yù)分配窗口之前，EXT已確定了窗口所在的塊組(其中肯定有空閑塊)和在塊組中的建議開始位置(新窗口應(yīng)在該位置之后)。如果老窗口的命中率超過了50%，可將新窗口的期望尺寸rsv_goal_size擴(kuò)大一倍，但擴(kuò)展后的尺寸不應(yīng)超過1027個邏輯塊。在創(chuàng)建新窗口時需要搜索紅黑樹s_rsv_window_root，以保證新窗口不會與已有的窗口重疊，同時還要搜索塊位圖，以保證新窗口中有空閑塊。如果創(chuàng)建成功，需要調(diào)整新窗口在紅黑樹中的位置。如果創(chuàng)建失敗，需要將老窗口關(guān)閉(EXT在為文件選定新塊組之后會再次為其創(chuàng)建預(yù)分配窗口)。如果文件當(dāng)前使用的預(yù)分配窗口過小，不能滿足分配需求，則要將其向后擴(kuò)展。當(dāng)然，擴(kuò)展后的窗口不能與系統(tǒng)中其它的預(yù)分配窗口重疊。

即使為文件創(chuàng)建了預(yù)分配窗口，在為其分配邏輯塊時也要搜索和設(shè)置塊位圖，預(yù)分配窗口的作用僅僅是限定了搜索的范圍。如果未為文件創(chuàng)建預(yù)分配窗口，搜索范圍將擴(kuò)展到塊組的右邊界。每次成功分配之后，都要將分配的塊數(shù)累加到窗口的域rsv_alloc_hit中(用于計(jì)算命中率，新窗口的rsv_alloc_hit為0)。為文件分配邏輯塊的目的是為了保存其文件塊，因而在分配之前應(yīng)該已經(jīng)知道文件塊的塊號。在一次分配中，可以僅為一個文件塊分配邏輯塊，也可以同時為多個連續(xù)的文件塊分配邏輯塊。當(dāng)然，一次分配的多個邏輯塊可能是不連續(xù)的。在成功分配邏輯塊之后，需要修改文件的索引表集合，以反映文件塊與邏輯塊間的映射關(guān)系。當(dāng)文件塊號大于12時，由于需要修改的一級、二級或三級索引表可能還未建立，因而可能還需要申請額外的邏輯塊以便建立文件索引表。在一次分配中，額外申請的邏輯塊數(shù)不會超過3塊(當(dāng)?shù)谝淮问褂萌壦饕頃r，需為其建立一個三級表、一個二級表和一個一級表)。

EXT的邏輯塊分配過程如下：

(1)根據(jù)文件塊號，算出新文件塊在各級索引表中的位置。如果索引表已分配但不在內(nèi)存，還要將其從塊設(shè)備中讀入。

(2)如果申請邏輯塊的文件是普通文件且還未為其創(chuàng)建預(yù)分配窗口，則臨時為其創(chuàng)建一個ext2_block_alloc_info結(jié)構(gòu)，并將其初始化。

(3)搜索索引表，確定需要分配的邏輯塊數(shù)，包括用于建立索引表的邏輯塊數(shù)。

(4)為新文件塊確定一個建議的分配位置(或定一個建議的邏輯塊號)。①如果已為文件建立了預(yù)分配窗口且文件在順序增長(新文件塊號等于last_alloc_logical_block+1)，那么最佳的分配位置應(yīng)該是窗口中的下一個邏輯塊(last_alloc_physical_block+1)。

②如果未為文件建立預(yù)分配窗口或文件不是順序增長的，那么最佳的分配位置應(yīng)該是與新文件塊之前的文件塊鄰接的邏輯塊。

③如果新文件塊在某個索引表中，但新文件塊之前的文件塊在該表中都是空的(文件有空洞)，那么較佳的分配位置應(yīng)該是與索引表鄰接的邏輯塊。④如果新文件塊的塊號是0，或它所在的索引表還未建立，那么應(yīng)將分配位置定在文件EXTinode所在塊組