你手里有一塊硬盤(pán)，大小為 1T

 

你還有一堆文件

 

這些文件在硬盤(pán)看來(lái)，就是一堆二進(jìn)制數(shù)據(jù)而已

 

你準(zhǔn)備把這些文件存儲(chǔ)在硬盤(pán)上，并在需要的時(shí)候讀取出來(lái)。要設(shè)計(jì)怎樣的軟件，才能更方便地在硬盤(pán)中讀寫(xiě)這些文件呢?

1

首先我不想和復(fù)雜的扇區(qū)，設(shè)備驅(qū)動(dòng)等細(xì)節(jié)打交道，因此我先實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的功能，將硬盤(pán)按邏輯分成一個(gè)個(gè)的塊，并可以以塊為單位進(jìn)行讀寫(xiě)。每個(gè)塊就定義為兩個(gè)物理扇區(qū)的大小，即 1024 字節(jié)，就是 1KB 啦。硬盤(pán)太大不好分析，我們就假設(shè)你的硬盤(pán)只有 1MB，那么這塊硬盤(pán)則有 1024 個(gè)塊。

 

OK，我們開(kāi)始存文件啦!準(zhǔn)備一個(gè)文件

 

隨便選個(gè)塊放進(jìn)去，3 號(hào)塊吧!

 

成功!首戰(zhàn)告捷!

2

再存一個(gè)文件!誒?發(fā)現(xiàn)問(wèn)題了，萬(wàn)一這個(gè)文件也存到了 3 號(hào)塊，不是把原來(lái)的文件覆蓋了么?不行，得有一個(gè)地方記錄，現(xiàn)在可使用的塊有哪些，像這樣。

塊 0：未使用

塊 1：未使用

塊 2：未使用

塊 3：已使用

塊 4：未使用

...

塊 1023：未使用

那我們就用 0 號(hào)塊，來(lái)記錄所有塊的使用情況吧!怎么記錄呢?位圖!

 

那我們給塊 0 起個(gè)名字，叫塊位圖，之后這個(gè)塊 0 就專(zhuān)門(mén)用來(lái)記錄所有塊的使用情況，不再用來(lái)存具體文件了。

 

當(dāng)我們?cè)俅嫒胍粋€(gè)新文件時(shí)，只需要在塊位圖中找到第一個(gè)為 0 的位，就可以找到第一個(gè)還未被使用的塊，將文件存入。同時(shí)，別忘了把塊位圖中的相應(yīng)位置 1。完美!

3

下面，我們嘗試讀取剛剛的文件。咦?又遇到問(wèn)題了，我怎么找到剛剛的文件呢?根據(jù)塊號(hào)么?這也太蠢了，就像你去書(shū)店找書(shū)，店員讓你提供書(shū)的編號(hào)，而不是書(shū)名，顯然不合理。因此我們給每個(gè)文件起一個(gè)名字，叫文件名，通過(guò)它來(lái)尋找這個(gè)文件。那必然就要有一個(gè)地方，記錄文件名與塊號(hào)的對(duì)應(yīng)關(guān)系，像這樣。

葵花寶典.txt：3 號(hào)塊

數(shù)學(xué)期末復(fù)習(xí)資料.mp4：5 號(hào)塊

低并發(fā)編程的秘密.pdf：10 號(hào)塊

...

別急，既然都要選一個(gè)地方記錄文件名稱了，不妨多記錄一點(diǎn)我們關(guān)心的信息吧，比如文件大小、文件創(chuàng)建時(shí)間、文件權(quán)限等。這些東西自然也要保存在硬盤(pán)上，我們選擇用一個(gè)固定大小的空間，來(lái)表示這些信息，多大空間呢?128 字節(jié)吧。為啥是 128 字節(jié)呢?我樂(lè)意。

 

我們將這 128 字節(jié)的結(jié)構(gòu)體，叫做一個(gè) inode。之后，我們每存入一個(gè)新的文件，不但要占用一個(gè)塊來(lái)存放這個(gè)文件本身，還要占用一個(gè) inode 來(lái)存放文件的這些元信息，并且這個(gè) inode 的所在塊號(hào)這個(gè)字段，就指向這個(gè)文件所在的塊號(hào)。

 

如果一個(gè) inode 為 128 字節(jié)，那么一個(gè)塊就可以容納 8 個(gè) inode，我們可以將這些 inode 編上號(hào)。

 

如果你覺(jué)得 inode 數(shù)不夠，也可以用兩個(gè)或者多個(gè)塊來(lái)存放 inode 信息，但這樣用于存放數(shù)據(jù)的塊就少了，這就看你自己的平衡了。

 

同樣，和塊位圖管理塊的使用情況一樣，我們也需要一個(gè) inode 位圖，來(lái)管理 inode 的使用情況。我們就把 inode 位圖，放在 1 號(hào)塊吧!同時(shí)，我們把 inode 信息，放在 2 號(hào)塊，一共存 8 條 inode，這樣我們的 2 號(hào)塊就叫做inode 表?，F(xiàn)在，我們的文件系統(tǒng)結(jié)構(gòu)，變成了下面這個(gè)樣子。

 

注意：塊位圖是管理可用的塊，每一位代表一個(gè)塊的使用與否。inode 位圖管理的是一條一條的 inode，并不是 inode 所占用的塊，比如上圖中有 8 條 inode，則 inode 位圖中就有 8 位是管理他們的使用與否。

4

現(xiàn)在，我們的文件很小，一個(gè)塊就能容下。但如果需要兩個(gè)塊、三個(gè)塊、四個(gè)塊呢?很簡(jiǎn)單，我們只需要采用連續(xù)存儲(chǔ)法，而 inode 則只記錄文件的第一個(gè)塊，以及后面還需要多少塊，即可。這種辦法的缺點(diǎn)就是：容易留下大大小小的空洞，新的文件到來(lái)以后，難以找到合適的空白塊，空間會(huì)被浪費(fèi)。

 

看來(lái)這種方式不行，那怎么辦呢?

既然在 inode 中記錄了文件所在的塊號(hào)，為什么不擴(kuò)展一下，多記錄幾塊呢?

 

原來(lái)在 inode 中只記錄了一個(gè)塊號(hào)，現(xiàn)在擴(kuò)展一下，記錄 8 個(gè)塊號(hào)!而且這些塊不需要連續(xù)。

 

嗯，這是個(gè)可行的辦法!

但是這也僅僅能表示 8 個(gè)塊，能記錄的最大文件是 8K(記住，一個(gè)塊是 1K), 現(xiàn)在的文件輕松就超過(guò)這個(gè)限制了，這怎么辦?很簡(jiǎn)單，我們可以讓其中一個(gè)塊，作為間接索引。

 

這樣瞬間就有 263 個(gè)塊(多了 256 -1 個(gè)塊)可用了，這種索引叫一級(jí)間接索引。如果還嫌不夠，就再弄一個(gè)塊做一級(jí)間接索引，或者做二級(jí)間接索引(二級(jí)間接索引則可以多出 256 * 256 - 1 個(gè)塊)。我們的文件系統(tǒng)，暫且先只弄一個(gè)一級(jí)間接索引。硬盤(pán)一共才 1024 個(gè)塊，一個(gè)文件 263 個(gè)塊夠大了。再大了不允許，就這么任性，愛(ài)用不用。好了，現(xiàn)在我們已經(jīng)可以保存很大的文件了，并且可以通過(guò)文件名和文件大小，將它們準(zhǔn)確讀取出來(lái)啦!

5

但我們得精益求精，我們?cè)傧胂肟催@個(gè)文件系統(tǒng)有什么毛病。比如，inode 數(shù)量不夠時(shí)，我們是怎么得知的呢?是不是需要在 inode 位圖中找，找不到了才知道不夠用了?同樣，對(duì)于塊數(shù)量不夠時(shí)，也是如此。要是有個(gè)全局的地方，來(lái)記錄這一切，就好了，也方便隨時(shí)調(diào)整，比如這樣

inode 數(shù)量

空閑 inode 數(shù)量

塊數(shù)量

空閑塊數(shù)量

那我們就再占用一個(gè)塊來(lái)存儲(chǔ)這些數(shù)據(jù)吧!由于他們看起來(lái)像是站在上帝視角來(lái)描述這個(gè)文件系統(tǒng)的，所以我們把它放在最開(kāi)始的塊上，并把它叫做超級(jí)塊，現(xiàn)在的布局如下。

 

我們繼續(xù)精益求精?，F(xiàn)在，塊位圖、inode 位圖、inode 表，都是是固定地占據(jù)這塊 1、塊 2、塊 3 這三個(gè)位置。假如之后 inode 的數(shù)量很多，使得 inode 表或者 inode 位圖需要占據(jù)多個(gè)塊，怎么辦?或者，塊的數(shù)量增多(硬盤(pán)本身大了，或者每個(gè)塊變小了)，塊位圖需要占據(jù)多個(gè)塊，怎么辦?程序是死的，你不告訴它哪個(gè)塊表示什么，它可不會(huì)自己猜。很簡(jiǎn)單，與超級(jí)塊記錄信息一樣，這些信息也選擇一個(gè)塊來(lái)記錄，就不怕了。那我們就選擇緊跟在超級(jí)塊后面的 1 號(hào)塊來(lái)記錄這些信息吧，并把它稱之為塊描述符。

 

當(dāng)然，這些所在塊號(hào)只是記錄起始?jí)K號(hào)，塊位圖、inode 位圖、inode 表分別都可以占用多個(gè)塊。好了，大功告成!

6

現(xiàn)在，我們?cè)賴L試存入一批文件。

• 葵花寶典.txt
• 數(shù)學(xué)期末復(fù)習(xí)資料.mp4
• 贅婿1.mp4
• 贅婿2.mp4
• 贅婿3.mp4
• 贅婿4.mp4

低并發(fā)編程的秘密.pdf

誒?這看著好不爽，所有的文件都是平鋪開(kāi)的，能不能擁有層級(jí)關(guān)系呢?比如這樣

• 葵花寶典.txt
• 數(shù)學(xué)期末復(fù)習(xí)資料.mp4
• 贅婿
  • 贅婿1.mp4
  • 贅婿2.mp4
  • 贅婿3.mp4
  • 贅婿4.mp4
• 低并發(fā)編程的秘密.pdf

我們將葵花寶典.txt 這種稱為普通文件，將贅婿這種稱為目錄文件，如果要訪問(wèn)贅婿1.mp4，那全文件名要寫(xiě)成贅婿/贅婿1.mp4。如何做到這一點(diǎn)呢?那我們又得把 inode 結(jié)構(gòu)拿出來(lái)說(shuō)事了。

 

此時(shí)需要一個(gè)屬性來(lái)區(qū)分這個(gè)文件是普通文件，還是目錄文件。缺什么就補(bǔ)什么嘛，我們已經(jīng)很熟悉了，專(zhuān)門(mén)加一個(gè) 4 字節(jié)，來(lái)表示文件類(lèi)型。

 

如果是普通文件，則這個(gè) inode 所指向的數(shù)據(jù)塊仍然和之前一樣，就是文件本身原封不動(dòng)的內(nèi)容。但如果是目錄文件，則這個(gè) inode 所指向的數(shù)據(jù)塊，就需要重新規(guī)劃了。這個(gè)數(shù)據(jù)塊里應(yīng)該是什么樣子呢?可以是一個(gè)一個(gè)指向不同 inode 的緊挨著的結(jié)構(gòu)體，比如這樣。

 

這樣先通過(guò) 贅婿 這個(gè)目錄文件，找到所在的數(shù)據(jù)塊。再根據(jù)這個(gè)數(shù)據(jù)塊里的一個(gè)個(gè)帶有inode 信息的結(jié)構(gòu)體，找到這個(gè)目錄下的所有文件。完美!

7

不過(guò)這樣的話，你想想看，如果想要查看一下贅婿這個(gè)目錄下的所有文件(比如 ll 命令)，將文件名和文件類(lèi)型都展示出來(lái)，怎么辦呢?就需要把一個(gè)個(gè)結(jié)構(gòu)體指向的 inode 從 inode 表中取出，再把文件名和文件類(lèi)型取出，這很是浪費(fèi)時(shí)間。而讓用戶看到一個(gè)目錄下的所有文件，又是一個(gè)極其常見(jiàn)的操作。所以，不如把文件名和文件類(lèi)型這種常見(jiàn)的信息，放在數(shù)據(jù)塊中的結(jié)構(gòu)體里吧。

 

同時(shí)，inode 結(jié)構(gòu)中的文件名，好像就沒(méi)啥用了，這種變長(zhǎng)的東西放在這種定長(zhǎng)的結(jié)構(gòu)中本身就很討厭，早就想給它去掉了。而且還能給其他信息省下空間，比如文件所在塊的數(shù)組，就能再多幾個(gè)了。太好了，去掉它!

 

OK，大功告成，現(xiàn)在我們就可以給文件分門(mén)別類(lèi)放進(jìn)不同目錄下了，還可以在目錄下創(chuàng)建目錄，無(wú)限套娃!

8

現(xiàn)在的文件系統(tǒng)，已經(jīng)比較完善了，只是還有一點(diǎn)不太爽。我們?cè)L問(wèn)到一個(gè)目錄下，可以很舒服地看到目錄里的文件，然后再根據(jù)名稱訪問(wèn)這個(gè)目錄下的文件或者目錄，整個(gè)過(guò)程都是一個(gè)套路。但是，最上層的目錄下的所有文件，即根目錄，現(xiàn)在仍然需要通過(guò)遍歷所有的 inode 來(lái)獲得，能不能和上面的套路統(tǒng)一呢?答案非常簡(jiǎn)單，我們規(guī)定，inode 表中的 0 號(hào) inode，就表示根目錄，一切的訪問(wèn)，就從這個(gè)根目錄開(kāi)始!

 

好了，這回沒(méi)有然后了!我們最后來(lái)欣賞下我們的文件系統(tǒng)架構(gòu)。

 

你是不是覺(jué)得這沒(méi)啥了不起的。但這個(gè)破玩意，它就叫文件系統(tǒng)

后記

這個(gè)文件系統(tǒng)，和 linux 上的經(jīng)典文件系統(tǒng) ext2 基本相同。

下面是我畫(huà)的 ext2 文件系統(tǒng)的結(jié)構(gòu)(字段部分只畫(huà)了核心字段)

 

估計(jì)你是看不清了，我說(shuō)下主要異同點(diǎn)：

1. 超級(jí)塊前面是啟動(dòng)塊，這個(gè)是 PC 聯(lián)盟給硬盤(pán)規(guī)定的 1KB 專(zhuān)屬空間，任何文件系統(tǒng)都不能用它。

2. ext2 文件系統(tǒng)首先將整個(gè)硬盤(pán)分為很多塊組，但如果只有一個(gè)塊組的話，和我們的文件系統(tǒng)整體結(jié)構(gòu)就完全一樣了，分別是超級(jí)塊、塊描述符、塊位圖、inode 位圖、inode 表、數(shù)據(jù)塊。

3. ext2 文件系統(tǒng)的 inode 表中用 15 個(gè)塊來(lái)定位文件，其中第 13 個(gè)塊為一級(jí)間接索引、14 個(gè)為二級(jí)間接索引、15 個(gè)為三級(jí)間接索引。

4. ext2 文件系統(tǒng)的文件類(lèi)型分得更多，還有常見(jiàn)的如塊設(shè)備文件、字符設(shè)備文件、管道文件、socket 文件等。

5. ext2 文件系統(tǒng)的超級(jí)塊、塊描述符、inode 表中記錄的信息更多，但核心的和我們的文件系統(tǒng)一樣，而且這些字段在后續(xù)的 ext3 和 ext4 中不斷增加，保持向前兼容。

6. ext2 文件系統(tǒng)的 2 號(hào) inode 為根目錄，而我們的系統(tǒng)是 0 號(hào) inode 為根目錄，這個(gè)很隨意，你設(shè)計(jì)一個(gè)文件系統(tǒng)定一個(gè) 187 號(hào) inode 為根目錄也沒(méi)人攔著你。

如果你想了解 ext2 文件系統(tǒng)的全部細(xì)節(jié)，有三種方式。

1. 看源碼，linux1.0 后的源碼都有 ext2文件系統(tǒng)的實(shí)現(xiàn)，源碼是最準(zhǔn)確的。

2. 看官方文檔，這里有個(gè) pdf 連接。

https://www.nongnu.org/ext2-doc/ext2.pdf

3. 看優(yōu)質(zhì)博客，這里我推薦一個(gè)。

http://docs.linuxtone.org/ebooks/C&CPP/c/ch29s02.html

4. 用 linux 的 mke2fs 命令生成一個(gè) ext2 文件系統(tǒng)的磁盤(pán)鏡像，然后一個(gè)字節(jié)一個(gè)字節(jié)分析其格式，可以在公眾號(hào) 低并發(fā)編程 回復(fù) ext2 獲得我的鏡像分析文件。

如果看源碼和官方文檔毫不吃力，我當(dāng)然主推這兩個(gè)，因?yàn)楫吘故且皇仲Y料。

但大多數(shù)人可能無(wú)法做到，有時(shí)也沒(méi)大必要，因此也可以看一些優(yōu)質(zhì)的博客。

介紹思想的，我覺(jué)得我這一篇就算是很優(yōu)質(zhì)的一篇了，它會(huì)帶你從設(shè)計(jì)者角度了解為什么這樣來(lái)設(shè)計(jì)文件系統(tǒng)。

介紹細(xì)節(jié)的，那些連文件系統(tǒng)的格式和字段都寫(xiě)不對(duì)的，就別看了，所以我這里良心推薦一篇，就是上面的方式三，可以放心大膽，逐字逐句地食用。

最后你還可以用方式四，自己將文件系統(tǒng)鏡像導(dǎo)出來(lái)，進(jìn)行分析。

本文轉(zhuǎn)載自微信公眾號(hào)「低并發(fā)編程」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系低并發(fā)編程公眾號(hào)。本網(wǎng)站已獲得低并發(fā)編程的授權(quán)。