# Playing with ext4
---
###### tags: `linux`
---
## 目錄
[TOC]
---
## 簡介
本文件記錄建立一個 ext4 檔案系統的過程和觀察其空間分配機制而進行的實驗。
使用 ubuntu 18.04 為作業系統，在 Transcend 64GB 隨身碟上建立一個 ext4 檔案系統。
---
## 建立 ext4
### 找到儲存裝置
第一步是找出用於建立 ext4 的儲存裝置，這邊使用的是隨身碟。
```bash=
$ lsblk
NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINT
sda 8:0 0 465.8G 0 disk
├─sda1 8:1 0 300M 0 part
├─sda2 8:2 0 100M 0 part /boot/efi
├─sda3 8:3 0 128M 0 part
├─sda4 8:4 0 149.5G 0 part
├─sda5 8:5 0 95.4G 0 part /
├─sda6 8:6 0 95.4G 0 part /home
├─sda7 8:7 0 3.8G 0 part [SWAP]
└─sda8 8:8 0 121.2G 0 part
...
...
sdc 8:32 1 58.8G 0 disk #用作實驗的隨身碟
```
### 建立分區
然後可以使用 gdisk 分割出所需要的大小。gdisk 提供 GPT 分割，若需要使用 MBR 分割，可以使用 fdisk，兩者使用方法基本相同。
```bash=
$ sudo gdisk /dev/sdc
GPT fdisk (gdisk) version 1.0.3
Partition table scan:
MBR: protective
BSD: not present
APM: not present
GPT: present
Found valid GPT with protective MBR; using GPT.
Command (? for help):
```
使用 n 新增磁區，為減少 ext 的 group block 數量，只提供 200MB 的空間。
```bash=
Command (? for help): n #新增磁區
Partition number (1-128, default 1): #使用預設
First sector (34-123207646, default = 2048) or {+-}size{KMGTP}:
#起始 sector ,使用預設
Last sector (2048-123207646, default = 123207646) or {+-}size{KMGTP}: +200M
#預設為使用所有空間，這邊改為使用 200MB
Current type is 'Linux filesystem'
Hex code or GUID (L to show codes, Enter = 8300):
#使用預設，8300 是 Linux 檔案系統
Changed type of partition to 'Linux filesystem'
```
設定完成後可以使用 ```p``` 預覽分割結果，確認無誤後使用 ```w``` 實際開始分割。
```bash=
Command (? for help): p#印出當前分割狀況
Disk /dev/sdc: 123207680 sectors, 58.8 GiB
Model: Transcend 64GB
Sector size (logical/physical): 512/512 bytes
...
Number Start (sector) End (sector) Size Code Name
1 2048 411647 200.0 MiB 8300 Linux filesystem
Command (? for help): w#確認進行以上操作
```
完成後再次使用```lsblk```即可發現新分割的磁區。
```bash=
$ lsblk
NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINT
sda 8:0 0 465.8G 0 disk
...
sdc 8:32 1 58.8G 0 disk
└─sdc1 8:33 1 200M 0 part #新的分割區
```
### 格式化
此時分割區尚未進行格式化，使用```mkfs```格式化並設定 block size 為 4096 bytes，以最少化 block group 的數量。
```bash=
$ sudo mkfs.ext4 -b 4096 /dev/sdc1#格式化為 ext4
mke2fs 1.44.1 (24-Mar-2018)
...
```
---
## 觀察和實驗
### 使用 dumpe2fs 吧！
此時 ext4 已建立完畢，使用 dumpe2fs 可觀察 ext4 的詳細資訊。如 Free blocks 的數量，建立時設定的 block size等。
其中 superblock, Group descriptors 等資料佔用了第 0-25 blocks，但 free blocks 並不是從 26 開始，而是 5732。
```bash=
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
Filesystem volume name: <none>
...
Errors behavior: Continue
Filesystem OS type: Linux
Inode count: 51200
Block count: 51200
Reserved block count: 2560
Free blocks: 45442
Free inodes: 51189
First block: 0
Block size: 4096 #mkfs 中設定的 4096 block size
Fragment size: 4096
Group descriptor size: 64
Reserved GDT blocks: 24
Blocks per group: 32768
Fragments per group: 32768
Inodes per group: 25600
Inode blocks per group: 800
...
Group 0: (Blocks 0-32767) csum 0x37d3
Primary superblock at 0, Group descriptors at 1-1
Reserved GDT blocks at 2-25
Block bitmap at 26 (+26), csum 0x32cade1f
Inode bitmap at 28 (+28), csum 0x004f98e0
Inode table at 30-829 (+30)
27036 free blocks, 25589 free inodes, 2 directories, 25589 unused inodes
Free blocks: 5732-32767 #並不是從 26 開始
Free inodes: 12-25600
Group 1: (Blocks 32768-51199) csum 0x360c [INODE_UNINIT]
Backup superblock at 32768, Group descriptors at 32769-32769
Reserved GDT blocks at 32770-32793
Block bitmap at 27 (bg #0 + 27), csum 0x20557c35
Inode bitmap at 29 (bg #0 + 29), csum 0x00000000
Inode table at 830-1629 (bg #0 + 830)
18406 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32794-51199
Free inodes: 25601-51200
```
### 清空檔案及資料夾
這時候先觀察一下 ext4 內的檔案，發現格式化時預留了一塊```lost+found```的空間，總共佔用 16384 bytes。
```bash=
$ ls -las
total 24
4 drwxrwxrwx 3 root root 4096 .
4 drwxr-x---+ 4 root root 4096 ..
16 drwxrwxrwx 2 root root 16384 lost+found
```
移除掉```lost+found```。
```bash=
$ rm -rf ./lost+found
$ ls -las
total 8
4 drwxrwxrwx 3 root root 4096 .
4 drwxr-x---+ 4 root root 4096 ..
```
再次使用 dumpe2fs，因為$4096 * 4 = 16384$ bytes，即```lost+found```應該佔用 4 個 blocks。移除```lost+found```後```Group 0```也空出 4 個 blocks，符合預期。
然而無法得知被佔用的 1635-5731 blocks 的具體用途，應為維持 ext4 運作的保留區域。
```bash=
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x9296 [ITABLE_ZEROED]
...
27040 free blocks, 25590 free inodes, 1 directories, 25589 unused inodes
Free blocks: 1631-1634, 5732-32767 #空出來 4 個 blocks 了
Free inodes: 11-25600
Group 1: (Blocks 32768-51199) csum 0xc745 [INODE_UNINIT, ITABLE_ZEROED]
...
18406 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32794-51199
Free inodes: 25601-51200
```
### 空間分配方式
為了得知 ext4 分配空間的方式，以下對 ext4 進行多種不同的寫入、刪除操作並進行觀察。
---
#### 排除 last freed first
為 ext4 建立檔案。
```bash=
$ echo "hello" >> ./1.txt
```
再次觀察 ext4。
新的檔案佔用了最前面的 data block 及 inode。
在使用 group 0 的 inode 的同時。
使用了 group 1 的 data block 而不是 group 0 的 data block。
```bash=
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x595d [ITABLE_ZEROED]
...
27040 free blocks, 25589 free inodes, 1 directories, 25589 unused inodes
Free blocks: 1631-1634, 5732-32767
Free inodes: 12-25600 #11 被佔用了！
Group 1: (Blocks 32768-51199) csum 0x29cc [INODE_UNINIT, ITABLE_ZEROED]
...
18405 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32795-51199 #32794 被佔用了！
Free inodes: 25601-51200
```
繼續建立檔案並觀察。系統持續使用 group 0 最前面的 inode 和 group 1 最前面的 data block。
此時可以確認並不是使用 last freed first 的空間分配機制。
```bash=
$ echo "hello" >> ./2.txt
$ echo "hello" >> ./3.txt
$ echo "hello" >> ./4.txt
$ echo "hello" >> ./5.txt
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x595d [ITABLE_ZEROED]
...
27040 free blocks, 25585 free inodes, 1 directories, 25585 unused inodes
Free blocks: 1631-1634, 5732-32767
Free inodes: 16-25600 #12-15 被佔用了！
Group 1: (Blocks 32768-51199) csum 0x29cc [INODE_UNINIT, ITABLE_ZEROED]
...
18401 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32799-51199 #32795-32798 被佔用了！
Free inodes: 25601-51200
```
---
#### 排除 least recently used first, next unused first, Last in first out
按```2.txt```, ```3.txt```, ```4.txt```的順序移除檔案，再建立```6.txt```並觀察。
此時發現，```6.txt```會佔用最前面的 inode 和 data block。而不是最後被刪除的```4.txt```所佔用的 data block (last in first out 機制)。或```5.txt```後面的空間(next unused first, least recently used first 機制)。
至此可以確認並不是使用 last freed first, least recently used first 或 next unused first 的空間分配機制。
```bash=
$ rm 2.txt
$ rm 3.txt
$ rm 4.txt
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x595d [ITABLE_ZEROED]
...
27040 free blocks, 25587 free inodes, 1 directories, 25585 unused inodes
Free blocks: 1631-1634, 5732-32767
Free inodes: 13-14, 16-25600 #13 被佔用了！
Group 1: (Blocks 32768-51199) csum 0x29cc [INODE_UNINIT, ITABLE_ZEROED]
...
18403 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32796-32797, 32799-51199 #32795 被佔用了！
Free inodes: 25601-51200
```
#### 判別 first fit, best fit
經過以上的觀察後，基本可以確定 ext4 是使用 first unused 機制。但尚未得知是根據 first fit 還是 best fit。
為此進行建立及刪除檔案的操作，產生一個 2 個連續 free data blocks 在前,1 個連續 free data block 在後的結構。
```bash=
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x595d [ITABLE_ZEROED]
...
27040 free blocks, 25586 free inodes, 1 directories, 25583 unused inodes
Free blocks: 1631-1634, 5732-32767
Free inodes: 13-14, 16, 18-25600
Group 1: (Blocks 32768-51199) csum 0x29cc [INODE_UNINIT, ITABLE_ZEROED]
...
18402 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32796-32797, 32799, 32801-51199 # 32796-32797 在前，32799 在後
Free inodes: 25601-51200
```
再次建立一個佔用 1 block size 的檔案，並觀察 data block 的使用狀況。
結果是在後方的單一 data block 被優先使用了，可見 ext4 是使用 best fit 機制。
```bash=
$ echo "hello" >> ./11.txt
$ sudo dumpe2fs /dev/sdc1
dumpe2fs 1.44.1 (24-Mar-2018)
...
Group 0: (Blocks 0-32767) csum 0x595d [ITABLE_ZEROED]
...
27040 free blocks, 25585 free inodes, 1 directories, 25583 unused inodes
Free blocks: 1631-1634, 5732-32767
Free inodes: 14, 16, 18-25600
Group 1: (Blocks 32768-51199) csum 0x29cc [INODE_UNINIT, ITABLE_ZEROED]
...
18401 free blocks, 25600 free inodes, 0 directories, 25600 unused inodes
Free blocks: 32796-32797, 32801-51199 #32799 被佔用了！
Free inodes: 25601-51200
```
## 結論
ext4 是使用 first best fit 的 data block 分配機制。
值得思考的是，ext4 是屬於索引式檔案系統，資料碎片化對效能影響較小，卻依然選擇速度較慢但資料碎片化較少的 best fit 機制，而不是速度更快但碎片化嚴重的 first fit 機制。這可能是考量 ext4 的 inode 有提供 extend 機制，可以使用單一的指標結構表示多個連續的 data block,。有較多連續的空間時，用於表示 data block 的指標數量就會減少，使用到 inode 的雙重，甚至三重指標的機率就會下降，此時理論效能則會獲得提升。
順帶一提，inode 的分配是采用單純的 first unused 機制，因為每個檔案只會使用一個 inode，因此不存在 best fit 和 first fit 的差別。
Sign in with Wallet
Connect another wallet