UNIX核心（6）：inode與目錄項、資料塊

大部分的Linux檔案系統（如ext2、ext3）規定，一個檔案由目錄項、inode和資料塊組成：

目錄項：包括檔案名和inode節點号。

Inode：又稱檔案索引節點，包含檔案的基礎資訊以及資料塊的指針。

資料塊：包含檔案的具體内容。

了解inode，要從檔案儲存說起。檔案儲存在硬碟上，硬碟的最小存儲機關叫做"扇區"（Sector），每個扇區儲存512位元組（相當于0.5KB）。

作業系統讀取硬碟的時候，不會一個扇區一個扇區地讀取，這樣效率太低，而是一次性連續讀取多個扇區，即一次性讀取一個"塊"（block）。這種由多個扇區組成的"塊"，是檔案存取的最小機關。"塊"的大小，最常見的是4KB，即連續八個 sector組成一個 block。

檔案資料都儲存在"塊"中，那麼很顯然，我們還必須找到一個地方儲存檔案的元資訊，比如檔案的建立者、檔案的建立日期、檔案的大小等等。這種儲存檔案元資訊的區域就叫做inode，中文譯名為"索引節點"。

inode包含檔案的元資訊，具體來說有以下内容：

檔案的位元組數。

檔案擁有者的User ID。

檔案的Group ID。

檔案的讀、寫、執行權限。

檔案的時間戳，共有三個：ctime指inode上一次變動的時間，mtime指檔案内容上一次變動的時間，atime指檔案上一次打開的時間。

連結數，即有多少檔案名指向這個inode。

檔案資料block的位置。

可以用stat指令，檢視某個檔案的inode資訊：

總之，除了檔案名以外的所有檔案資訊，都存在inode之中。至于為什麼沒有檔案名，下文會有詳細解釋。

當檢視某個檔案時，會先從inode表中查出檔案屬性及資料存放點，再從資料塊中讀取資料。

請看檔案存儲結構示意圖：

inode也會消耗硬碟空間，是以硬碟格式化的時候，作業系統自動将硬碟分成兩個區域。一個是資料區，存放檔案資料；另一個是inode區（inode table），存放inode所包含的資訊。

每個inode節點的大小，一般是128位元組或256位元組。inode節點的總數，在格式化時就給定，一般是每1KB或每2KB就設定一個inode。假定在一塊1GB的硬碟中，每個inode節點的大小為128位元組，每1KB就設定一個inode，那麼inode table的大小就會達到128MB，占整塊硬碟的12.8%。

檢視每個硬碟分區的inode總數和已經使用的數量，可以使用df -i 指令。

檢視每個inode節點的大小，可以用如下指令：

由于每個檔案都必須有一個inode，是以有可能發生inode已經用光，但是硬碟還未存滿的情況。這時，就無法在硬碟上建立新檔案。

每個inode都有一個号碼，作業系統用inode号碼來識别不同的檔案。

這裡值得重複一遍，Linux系統内部不使用檔案名，而使用inode号碼來識别檔案。對于系統來說，檔案名隻是inode号碼便于識别的别稱或者綽号。表面上，使用者通過檔案名，打開檔案。實際上，系統内部這個過程分成三步：首先，系統找到這個檔案名對應的inode号碼；其次，通過inode号碼，擷取inode資訊；最後，根據inode資訊，找到檔案資料所在的block，讀出資料。

使用ls -i指令，可以看到檔案名對應的inode号碼，例如：

Linux系統中，目錄（directory）也是一種檔案。打開目錄，實際上就是打開目錄檔案。

目錄檔案的結構非常簡單，就是一系列目錄項（dirent）的清單。每個目錄項，由兩部分組成：所包含檔案的檔案名，以及該檔案名對應的inode号碼。

ls指令隻列出目錄檔案中的所有檔案名：

ls -i指令列出整個目錄檔案，即檔案名和inode号碼：

如果要檢視檔案的詳細資訊，就必須根據inode号碼，通路inode節點，讀取資訊。ls -l指令列出檔案的詳細資訊。

一般情況下，檔案名和inode号碼是"一一對應"關系，每個inode号碼對應一個檔案名。但是，Linux系統允許，多個檔案名指向同一個inode号碼。這意味着，可以用不同的檔案名通路同樣的内容；對檔案内容進行修改，會影響到所有檔案名；但是，删除一個檔案名，不影響另一個檔案名的通路。這種情況就被稱為"硬連結"（hard link）。

ln指令可以建立硬連結，文法為：

運作上面這條指令以後，源檔案與目标檔案的inode号碼相同，都指向同一個inode。inode資訊中有一項叫做"連結數"，記錄指向該inode的檔案名總數，這時就會增加1。反過來，删除一個檔案名，就會使得inode節點中的"連結數"減1。當這個值減到0，表明沒有檔案名指向這個inode，系統就會回收這個inode号碼，以及其所對應block區域。

這裡順便說一下目錄檔案的"連結數"。建立目錄時，預設會生成兩個目錄項："."和".."。前者的inode号碼就是目前目錄的inode号碼，等同于目前目錄的"硬連結"；後者的inode号碼就是目前目錄的父目錄的inode号碼，等同于父目錄的"硬連結"。是以，任何一個目錄的"硬連結"總數，總是等于2加上它的子目錄總數（含隐藏目錄）,這裡的2是父目錄對其的“硬連結”和目前目錄下的".硬連結“。

除了硬連結以外，還有一種特殊情況。檔案A和檔案B的inode号碼雖然不一樣，但是檔案A的内容是檔案B的路徑。讀取檔案A時，系統會自動将通路者導向檔案B。是以，無論打開哪一個檔案，最終讀取的都是檔案B。這時，檔案A就稱為檔案B的"軟連結"（soft link）或者"符号連結（symbolic link）。

這意味着，檔案A依賴于檔案B而存在，如果删除了檔案B，打開檔案A就會報錯："No such file or directory"。這是軟連結與硬連結最大的不同：檔案A指向檔案B的檔案名，而不是檔案B的inode号碼，檔案B的inode"連結數"不會是以發生變化。

ln -s指令可以建立軟連結，文法為：

在inode裡存放了檔案資料所在磁盤資料塊号，檔案越大，所需要的塊号就越多，這是因為檔案在磁盤上的存放是不連續的。那為什麼不用連續存放？這樣隻需要一個起始塊号以及檔案大小就可以描述整個檔案的資料位置了。這回帶來一些問題，包括很難增長檔案大小，以及很容易産生磁盤碎片。

是以，還是采用存儲每個塊号的方式來存放檔案資料在磁盤上的索引。當然，要想允許大檔案且保持inode足夠小，可以采用分級機制。在inode中有13個整數用來存放塊号。前10個數是直接指向檔案資料的塊号，第11個數單級間接指向檔案資料，即在第11個塊号所指向的的資料塊存放的是一個塊号表。第12個數雙級間接指向檔案資料，即第12個塊号指向一個單級間接塊号表。第13個塊号指向的是一個指向雙級間接塊号表。如下圖所示：

－－－－－－－－

｜ｄｉｒｅｃｔ｜－－－－－＞ｄａｔａ　ｂｌｏｃｋ

－－－－－－－－－－

｜ｓｉｎｇｌｅ　　｜－－－＞－－－－－－－－－－

｜ｉｎｄｉｒｅｃｔ｜　　　　｜ｄｉｒｅｃｔ　０｜－－－＞ｄａｔａ　ｂｌｏｃｋ

－－－－－－－－－－　　　　｜ｄｉｒｅｃｔ　１｜－－－＞ｄａｔａ　ｂｌｏｃｋ

　　　　　　　　　　　　　　｜．．．　　　　　｜　　　　．．．

　　　　　　　　　　　　　　｜ｄｉｒｅｃｔ　ｎ｜－－－＞ｄａｔａ　ｂｌｏｃｋ

　　　　　　　　　　　　　　－－－－－－－－－－

｜ｄｏｕｂｌｅ　　｜－－－＞－－－－－－－－－－－－－－－－－｜ｉｎｄｉｒｅｃｔ｜　　　　｜ｓｉｎｇｌｅ　ｄｉｒｅｃｔ　０｜－－－＞．．．

－－－－－－－－－－　　　　｜ｓｉｎｇｌｅ　ｄｉｒｅｃｔ　１｜－－－＞．．．

　　　　　　　　　　　　　　｜．．．　　　　　　　　　　　　｜　　　　．．．

　　　　　　　　　　　　　　｜ｓｉｎｇｌｅ　ｄｉｒｅｃｔ　ｎ｜－－－＞．．．

　　　　　　　　　　　　　　－－－－－－－－－－－－－－－－－

……

這種方式能夠存放多少資料呢？計算一下。假設一個磁盤塊能存放1K位元組，一個塊号占用4個位元組，那麼：

10 direct blocks: 10 * 1K = 10K

1 indirect block with 256 direct blocks: 256 * 1K = 256K

1 double indirect block with 256 indirect blocks: 256 * 256K = 64M

1 triple indirect block with 256 double indirect blocks:　256 * 64M = 16G。

然而一個4位元組整數能尋址的最大空間為4G，是以inode的這種塊号組織方式足夠用了，除非使用的是64位系統。

程序通過位元組偏移量來通路檔案中的資料，那麼就需要将偏移量轉換成磁盤塊号。這裡需要考慮分級層次，是以在實作起來會有一定的麻煩。核心提供bmap()函數來将偏移量轉換成磁盤塊号。處理如下：

struct Location

{

BlockNo blkNo;

ByteOffset off;

Bytes nIO;

BlockNo readAheadNo;

};

Location * bmap(INode * anINode, ByteOffset off)

根據偏移量計算邏輯塊号;

計算塊中的起始位元組;

計算要拷貝給使用者的位元組數;

檢查是否要預讀，标記inode;

确定間接索引的等級;

while (不是在一個需要的等級)

根據邏輯塊号來計算inode或間接塊的索引;

擷取磁盤塊号;

brelse(未釋放的磁盤塊);

若沒有更多的間接索引等級則傳回塊号;

讀取間接索引磁盤塊;

根據間接索引的等級調整邏輯塊号;

}

這個算法在實作起來比較複雜，在Linux的實作當中比較分散，此處就不列舉代碼。

将路徑名映射到inode

目錄與普通檔案類似，隻不過目錄中資料存放的是目錄項，該項包含的是inode号以及在該目錄中的一個檔案名（可以是目錄）。路徑名是一個以“/”分割的字元串。每個被“/”分開的部分稱為一個元件。在UNIX system V中，元件最長為14個位元組。

那麼，如何将路徑名映射到inode呢？每個程序都有一個u area，存放一個指向目前目錄的指針。另外有一個全局變量存放根目錄的inode。有了兩個inode，映射就很簡單了。

若一個程序要打開“/etc/passwd”檔案，核心解析該路徑名時，發現“/”，這樣就将根目錄作為工作目錄，然後從該目錄中（inode所包好的資料塊中）查找etc，找到了比對後得到了etc的inode号，然後讀取etc的内容，在其中查找passwd，找到之後就可以傳回對應的inode。處理過程如下：

INode * namei(String pathName) // 傳回的是鎖住的inode

INode * cwINode = NULL;

if (pathName[0] == '/')

cwINode = iget(rootINodeNO);

else

cwINode = iget(currentDirINode);

while (pathName中還有元件)

從pathName中讀取下一個元件component;

ISDIR(component) && 程序對該inode有對應的權限（否則傳回權限錯誤）;

if (*cwINode is root INode && component == "..")

continue;

while (cwINode的資料還沒有結束)

bmap()得到資料塊号; bread()讀取資料塊;

if (在cwINode的資料中找到component)

從該項中讀取inode号matchINodeNo;

iput(cwINode);

cwINode = iget(matchINodeNo);

brelse()釋放資料塊;

break;

return (no inode);

return (cwINode);

在Linux 0.99.15的實作中，namei采用了遞歸的方式，有興趣的可以參考其代碼。

參考：

The Design of The UNIX Operation System, by Maurice J. Bach

Linux Kernel Source Code v0.99.15, by Linus Torvalds

Linux Kernel Source Code v2.6.22, by Linus Torvalds and Linux community.

Understanding The Linux Kernel, 3rd edition, by Daniel P. Bovet, Marco Cesati

Copyleft (C) 2007 raof01. 本文可以用于除商業用途外的所有用途。若要用于商業用途，請與作者聯系。