[TOC]

1. 文件系统的组成部分

1.1. block块理解

硬盘的读写IO一次是一个扇区512字节, 如果要读写大量文件，以扇区为单位肯定很慢很消耗性能，所以Linux中通过文件系统控制使用"块"为读写单元
比如需要读一个或多个块时，文件系统的IO管理器通知磁盘控制器要读取哪些块的数据，硬盘控制器将这些块按扇区读取出来，再通过硬盘控制器将这些扇区数据重组返回给计算机

block的出现使得在文件系统层面上读写性能大大提高，也大量减少了碎片
可能造成空间浪费

在当下硬盘容量廉价且追求性能的时代，使用block是一定的。

1.2. inode

假如block大小为1KB，仅仅存储一个10M的文件就需要10240个block，而且这些blocks很可能在位置上是不连续在一起的(不相邻)

读取该文件时难道要从前向后扫描整个文件系统的块，然后找出属于该文件的块吗？
???
每个文件都有属性(如权限、大小、时间戳等)，这些属性类的元数据存储在哪里呢？难道也和文件的数据部分存储在块中吗？
如果一个文件占用多个block那是不是每个属于该文件的block都要存储一份文件元数据？
如果不在每个block中存储元数据文件系统又怎么知道某一个block是不是属于该文件呢？
解决方法是使用索引，通过扫描索引找到对应的数据，而且索引可以存储部分数据
在文件系统上索引技术具体化为索引节点(index node)，在索引节点上存储的部分数据即为文件的属性元数据及其他少量信息.
索引节点称为inode。在inode中存储了inode号、文件类型、权限、文件所有者、大小、时间戳等元数据信息，最重要的是还存储了指向属于该文件block的指针

可以用stat命令，查看某个文件的inode信息：

$ stat ~/.bashrc         
  File: ‘/home/local/SPREADTRUM/liguang.zhang/.bashrc’
  Size: 7829      	Blocks: 16         IO Block: 4096   regular file
Device: 821h/2081d	Inode: 39059515    Links: 1
Access: (0644/-rw-r--r--)  Uid: (1488486870/SPREADTRUM\liguang.zhang)   Gid: (1488454145/SPREADTRUM\domain^users)
Access: 2019-03-18 09:52:16.796663821 +0800
Modify: 2019-02-22 10:10:58.044537613 +0800
Change: 2019-02-22 10:10:58.044537613 +0800
 Birth: -

查看每个inode节点的大小，可以用如下命令：

1
2
3

$ sudo dumpe2fs /dev/sda1 | grep "Inode size"
dumpe2fs 1.42.9 (4-Feb-2014)
Inode size:	          256

打印文件的inode number
ls命令用于列出文件/文件夹的信息。参数 -i 说明需要显示每个文件的inode number。我们可以结合参数 -l 一起使用以列出详细信息：

$ ls -li
total 16
43650565 drwxr-xr-x 108 SPREADTRUM\liguang.zhang SPREADTRUM\domain^users 12288 Mar 15 10:10 extensions
43783364 drwxr-xr-x   2 SPREADTRUM\liguang.zhang SPREADTRUM\domain^users  4096 May 17  2018 projects

显示文件系统inode的使用信息
df命令汇总可用和已用的磁盘空间。你可以通过传递 -i 或 –inodes 选项来接收有关可用和已使用的inode报告。

$ df -i             
Filesystem                                                            Inodes   IUsed     IFree IUse% Mounted on
udev                                                                 2040313     563   2039750    1% /dev
tmpfs                                                                2043070     647   2042423    1% /run
/dev/sda1                                                            3055616  909414   2146202   30% /
none                                                                 2043070       2   2043068    1% /sys/fs/cgroup
none                                                                 2043070       5   2043065    1% /run/lock
none                                                                 2043070     119   2042951    1% /run/shm
none                                                                 2043070      38   2043032    1% /run/user
/dev/sda3                                                           25526272  276893  25249379    2% /home
/dev/sdb3                                                           56901632 6017447  50884185   11% /home/newdisk
/dev/sdc1                                                          244195328 7604192 236591136    4% /home/newdisk1
//tjnas1/data_exchange_tunnel/From_Shanghai/PLD_APPS/liguang.zhang         0       0         0     - /home/newdisk1/liguang.zhang/smb_dir/datasync

列出文件系统超级块的信息
tune2fs -l 命令来显示所有与inode相关的信息

$ sudo tune2fs -l /dev/sda1 | grep inode
Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent flex_bg sparse_super large_file huge_file uninit_bg dir_nlink extra_isize
Free inodes:              2146270
First inode:              11
Journal inode:            8
First orphan inode:       131185
Journal backup:           inode blocks

1.3. bmap出现(只对写优化)

在向硬盘存储数据时，文件系统需要知道哪些块是空闲的，哪些块是已经占用了的。
最笨的方法当然是从前向后扫描，遇到空闲块就存储一部分，继续扫描直到存储完所有数据。
位图只使用0和1标识对应block是空闲还是被占用，0和1在位图中的位置和block的位置一一对应，第一位标识第一个块，第二个位标识第二个块，依次下去直到标记完所有的block
1G的文件只需要128个block做位图就能完成一一对应(1k的block)
bmap的优化针对的是写优化，因为只有写才需要找到空闲block并分配空闲block
对于读而言，只要通过inode找到了block的位置，cpu就能迅速计算出block在物理磁盘上的地址

bmap也有瓶颈, 每次写都需要扫描以下查看哪些块未被占用, 对于100G的, 需要128k*100, 每次写需要扫描12800个块, 不连续的地址扫描时间更长, 需要进一步优化
出现里块组, 对bmap进行优化

1.4. inode表

inode存储了inode号、文件属性元数据、指向文件占用的block的指针；每一个inode占用128字节或256字节。
引入了一个问题, 每一个文件都对应一个inode, 一个inode为128或256大小, 每一个inode都要占用一个块吗?

优化出现inode表:
多个inode合并存储在block中
256字节的inode, block为4k, 则16个inode存到一个block中. 为一个inode表
在文件系统创建完成后所有的inode号都已经分配好并记录到inode table中了
- 被使用的inode号所在的行还有文件属性的元数据信息和block位置信息
- 未被使用的inode号只有一个inode号而已而没有其他信息而已

1.5. imap的出现

一个大的文件系统仍将占用大量的块来存储inode, 如何快速找到inode，这同样是需要优化的，

优化的方法是将文件系统的block进行分组划分，每个组中都存有本组inode table范围、bmap等
bmap是块位图，用于标识文件系统中哪些block是空闲哪些block是占用的。
inode也一样，在存储文件(Linux中一切皆文件)时需要为其分配一个inode号。但是在格式化创建文件系统后所有的inode号都是被事先设定好存放在inode table中的，因此产生了问题：要为文件分配哪一个inode号呢？又如何知道某一个inode号是否已经被分配了呢？
标识inode号是否被分配的位图称为inodemap简称为imap, 这时要为一个文件分配inode号只需扫描imap即可知道哪一个inode号是空闲的。
imap存在着和bmap和inode table一样需要解决的问题：
imap本身就会很大，每次存储文件都要进行扫描，会导致效率不够高。
同样，优化的方式是将文件系统占用的block划分成块组，每个块组有自己的imap范围。

1.6. 块组

前面bmap和imap inode table抛出的问题, 怎么对其快速扫描. 两个地方的优化方案都是引入块组

物理层面上的划分是将磁盘按柱面划分为多个分区，即多个文件系统
逻辑层面上的划分是将文件系统划分成块组
每个文件系统包含多个块组，每个块组包含多个元数据区和数据区：
- 元数据区就是存储bmap、inode table、imap等的数据；
- 数据区就是存储文件数据的区域。
  
  块组是逻辑层面的概念，所以并不会真的在磁盘上按柱面、按扇区、按磁道等概念进行划分。

1.6.1. 块组的划分

块组在文件系统创建完成后就已经划分完成了，也就是说元数据区bmap、inode table和imap等信息占用的block以及数据区占用的block都已经划分好了。
那么文件系统如何知道一个块组元数据区包含多少个block，数据区又包含多少block呢？
只需要一个标准:
block的大小

bmap至多只能占用一个完整的block的标准

每个block的大小在创建文件系统时可以人为指定，不指定也有默认值。
如当前文件系统的block大小一般为4k, 一个bmap完整占用一个block能标识4k8 = 32K个block(注意是元数据区和数据区一个32k个, 因元数据区的block也要通过bamp来标识)
每个block是4k, 一个块组bmap可以标识32k个block, 即块组大小为32K4K =128M, 创建1G的文件系统, 可以分为1024M/ 128M = 8个块组
每个组设定多少个inode号呢? inode table占用多少block呢？建文件系统时也可以人为指定这个指标或者百分比例
使用dumpe2fs可以将ext类的文件系统信息全部显示出来，当然bmap是每个块组固定一个block的不用显示，imap比bmap更小所以也只占用1个block不用显示。

# 360M左右的文件系统: 一共三个块组,
-rwxr-xr-x  1 SPREADTRUM\liguang.zhang SPREADTRUM\domain^users 366997504 Apr 20  2017 system.img*
#dumpe2fs system.img
dumpe2fs 1.42.9 (4-Feb-2014)
Filesystem volume name:   <none>
Last mounted on:          <not available>
Filesystem UUID:          57f8f4bc-abf4-655f-bf67-946fc0f9f25b
Filesystem magic number:  0xEF53
Filesystem revision #:    1 (dynamic)
Filesystem features:      has_journal ext_attr resize_inode filetype extent sparse_super large_file uninit_bg
Default mount options:    (none)
Filesystem state:         clean
Errors behavior:          Remount read-only
Filesystem OS type:       Linux
Inode count:              22416 #inode总数
Block count:              89599 #文件系统block总数
Reserved block count:     0  #保留的block数量
Free blocks:              32553
Free inodes:              21102
First block:              0   #第一个block号
Block size:               4096  #block大小
Fragment size:            4096
Reserved GDT blocks:      23 #保留的GDT数量
Blocks per group:         32768 #一个块组的block数
Fragments per group:      32768
Inodes per group:         7472  #一个块组的inode数, 根据制作文件系统时inode ratio计算的
Inode blocks per group:   467 #一个块组inode table所占的block数
Last mount time:          n/a
Last write time:          Thu Jan  1 08:00:00 1970
Mount count:              0
Maximum mount count:      -1
Last checked:             Thu Jan  1 08:00:00 1970
Check interval:           0 (<none>)
Reserved blocks uid:      0 (user root)
Reserved blocks gid:      0 (group root)
First inode:              11 #文件系统的第一个inode号
Inode size:	          256 #每个inode的大小为256字节
Required extra isize:     28
Desired extra isize:      28
Journal inode:            8
Default directory hash:   tea
Journal backup:           inode blocks
Journal features:         (none)
Journal size:             5596k
Journal length:           1399
Journal sequence:         0x00000001
Journal start:            0

# 一个块组标识32K个block.
Group 0: (Blocks 0-32767)
  Checksum 0xa934, unused inodes 0
  Primary superblock at 0, Group descriptors at 1-1 #superbock在0号block, 块组描述表GDT所在block 0/1/ 3/5/7幂次, 0的是主的, 0损坏再读取其他的备份
  Reserved GDT blocks at 2-24 # 保留GDT所在的block
  Block bitmap at 25 (+25), Inode bitmap at 26 (+26) #bmap和imap所在的block位置
  Inode table at 27-493 (+27) #inode table所在的block位置
  1 free blocks, 6158 free inodes, 48 directories
  Free blocks: 32767
  Free inodes: 1315-7472
Group 1: (Blocks 32768-65535) [INODE_UNINIT]
  Checksum 0x8825, unused inodes 0
  Backup superblock at 32768, Group descriptors at 32769-32769 # sb和GDT
  Reserved GDT blocks at 32770-32792
  Block bitmap at 32793 (+25), Inode bitmap at 32794 (+26)
  Inode table at 32795-33261 (+27)
  8958 free blocks, 7472 free inodes, 0 directories
  Free blocks: 56578-65535
  Free inodes: 7473-14944
# 2号中没有sb和GDT
Group 2: (Blocks 65536-89598) [INODE_UNINIT]
  Checksum 0x7e40, unused inodes 0
  Block bitmap at 65536 (+0), Inode bitmap at 65537 (+1)
  Inode table at 65538-66004 (+2)
  23594 free blocks, 7472 free inodes, 0 directories
  Free blocks: 66005-89598
  Free inodes: 14945-22416

该文件系统共89599个blocks，每个block大小为4K, 所以文件系统大小为89599*4k = 350M
块组的数量为 350M/128M = 3, 由于块组从0开始编号，所以最后一个块组编号为Group 2.

2. 文件系统的完整结构

将上文描述的bmap、inode table、imap、数据区的blocks和块组的概念组合起来就形成了一个文件系统，当然这还不是完整的文件系统。完整的文件系统如下图

除了superblock、bmap、imap能确定占用1个block，其他的部分都不能确定占用几个block。
图中指明了Superblock、GDT和Reserved GDT是同时出现且不一定存在于每一个块组中的，也指明了bmap、imap、inode table和data blocks是每个块组都有的。

2.1. 引导块

上图中的Boot Block部分，也称为boot sector。它位于分区上的第一个块，占用1024字节
并非所有分区都有这个boot sector，只有装了操作系统的主分区和装了操作系统的逻辑分区才有, 里面存放的也是boot loader
这段boot loader称为VBR(主分区装操作系统时)或EBR(扩展分区装操作系统时)
开机启动的时候，首先加载mbr中的bootloader，然后定位到操作系统所在分区的boot serctor上加载此处的boot loader。如果是多系统，加载mbr中的bootloader后会列出操作系统菜单，菜单上的各操作系统指向它们所在分区的boot sector上。它们之间的关系如下图所示。
现在通常使用grub来管理启动菜单。尽管如此，在安装操作系统时，仍然有一步是选择boot loader安装位置的步骤

2.2. 超级块(superblock) sb

既然一个文件系统会分多个块组，那么

文件系统怎么知道分了多少个块组呢？
每个块组又有多少block多少inode号等等信息呢？
文件系统本身的属性信息如各种时间戳、block总数量和空闲数量、inode总数量和空闲数量、当前文件系统是否正常、什么时候需要自检等等，它们又存储在哪里呢？
这些信息必须要存储在block中。存储这些信息占用1024字节，所以也要一个block，这个block称为超级块(superblock)
它的block号可能为0也可能为1, 如果block大小为4k, 则引导和sb同在一个block, 则block号为0,
总之sb处在第二个1024位置(1024-2047)字节
使用df命令读取的就是每个文件系统的superblock，所以它的统计速度非常快。
用du命令查看一个较大目录的已用空间就非常慢，因为不可避免地要遍历整个目录的所有文件。
superblock对于文件系统而言是至关重要的，超级块丢失或损坏必将导致文件系统的损坏。
所以ext2文件系统只在块组0、1和3、5、7幂次方的块组中保存超级块的信息, 只有当Group0上的superblock损坏或丢失才会找下一个备份超级块复制到Group0中来恢复文件系统。
ext家族的文件系统都能使用dumpe2fs -h获取。

2.3. 块组描述符表(GDT)

每个块组的信息和属性元数据又保存在哪里呢?

ext文件系统每一个块组信息使用32字节描述，这32个字节称为块组描述符，所有块组的块组描述符组成块组描述符表GDT(group descriptor table)。
虽然每个块组都需要块组描述符来记录块组的信息和属性元数据，但是不是每个块组中都存放了块组描述符?
ext文件系统的存储方式是：将它们组成一个GDT，并将该GDT存放于某些块组中，存放GDT的块组和存放superblock和备份superblock的块相同，也就是说它们是同时出现在某一个块组中的。读取时也总是读取Group0中的块组描述符表信息。

假如block大小为4KB的文件系统划分了143个块组，每个块组描述符32字节，那么GDT就需要143*32=4576字节即两个block来存放。这两个GDT block中记录了所有块组的块组信息，且存放GDT的块组中的GDT都是完全相同的。

2.4. 保留GDT(Reserved GDT)

保留GDT用于以后扩容文件系统使用，防止扩容后块组太多，使得块组描述符超出当前存储GDT的blocks。保留GDT和GDT总是同时出现，当然也就和superblock同时出现了
块组太多, 可能出现GDT的块不足以放下 32*块组大小的字节, 需要RGDT补充. 如果没有RGDT, 因分配方式已经固定好了, 增加GDT block需要为其分配block, 但备份块组中的block号占又不可能总是同0块组是一样的, 需要考虑的情况更复杂.
同时, 新增加了GDT需要修改每个块组中superblock中的文件系统属性，所以将superblock和Reserved GDT/GDT放在一起又能提升效率。

2.5. Data Block

上图中除了data block之外的都介绍了, data block是直接存储数据的block，但事实上并非如此简单。
数据所占用的block由文件对应inode记录中的block指针找到，不同的文件类型，数据block中存储的内容是不一样的。以下是Linux中不同类型文件的存储方式。

对于常规文件，文件的数据正常存储在数据块中。
对于目录，该目录下的所有文件和一级子目录的目录名存储在数据块中。
- 文件名不是存储在其自身的inode中，而是存储在其所在目录的data block中。
对于符号链接，如果目标路径名较短则直接保存在inode中以便更快地查找，如果目标路径名较长则分配一个数据块来保存。
设备文件、FIFO和socket等特殊文件没有数据块，设备文件的主设备号和次设备号保存在inode中。

常规文件的存储就不解释了，下面分别解释特殊文件的存储方式。

2.5.1. 目录文件的data block

对于目录文件，其inode记录:

这里面没有存储目录自身文件名的信息
目录的data block中保存到信息:

目录中的文件名
目录名
目录本身的相对名称”.”
上级目录的相对名称”..”
指向inode table中这些文件名对应的inode号的指针
目录项长度rec_len
文件名长度name_len
文件类型file_type

除了文件本身的inode记录了文件类型，其所在的目录的数据块也记录了文件类型
目录的data block中并没有直接存储目录中文件的inode号，它存储的是指向inode table中对应文件inode号的指针，暂且称之为inode指针
一种是inode table中每个inode记录指向其对应data block的block指针，
一个此处的inode指针

目录文件的读权限(r)和写权限(w)，都是针对目录文件的数据块本身。由于目录文件内只有文件名、文件类型和inode指针，所以如果只有读权限，只能获取文件名和文件类型信息，无法获取其他信息，尽管目录的data block中也记录着文件的inode指针，但定位指针是需要x权限的，因为其它信息都储存在文件自身对应的inode中，而要读取文件inode信息需要有目录文件的执行权限通过inode指针定位到文件对应的inode记录上。
1
2
3
4
5
ls: cannot access d/a: Permission denied
ls: cannot access d/bc: Permission denied
total 0
? -????????? ? ? ? ? ? a
? -????????? ? ? ? ? ? bc

3. inode基础知识

每个文件都有一个inode，在将inode关联到文件后系统将通过inode号来识别文件，而不是文件名。
访问文件时将先找到inode，通过inode中记录的block位置找到该文件。

3.1. 硬链接

多个文件的inode相同，也就即inode号、元数据、block位置都相同
这些文件所在目录的data block中的inode指针目的地都是一样的，只不过各指针对应的文件名互不相同而已。
硬链接文件的inode都相同，每个文件都有一个”硬链接数”的属性，使用ls -l的第二列就是被硬链接数，它表示的就是该文件有几个硬链接。

c/al --hard-link-- d/a
# 4. stat 信息一致, 硬连接数变为2
-rw-r--r-- 2 SPREADTRUM\liguang.zhang SPREADTRUM\domain^users    0 Mar 18 17:12 a
-rw-r--r-- 2 SPREADTRUM\liguang.zhang SPREADTRUM\domain^users 0 Mar 18 17:12 al

每创建一个文件的硬链接，实质上是多一个指向该inode记录的inode指针，并且硬链接数加1。
删除文件的实质是删除该文件所在目录data block中的对应的inode指针，所以也是减少硬链接次数
当硬链接次数为1时再删除文件就是真的删除文件了，此时inode记录中block指针也将被删除。

不能跨分区创建硬链接，因为不同文件系统的inode号可能会相同，如果允许创建硬链接，复制到另一个分区时inode可能会和此分区已使用的inode号冲突。
硬链接只能对文件创建，无法对目录创建硬链接。

通过mount工具的”–bind”选项，可以将一个目录挂载到另一个目录下，实现伪”硬链接”，它们的内容和inode号是完全相同的。

3.2. inode深入

3.2.1. inode大小和划分

inode大小为128字节的倍数，最小为128字节。它有默认值大小
当然inodesize、inode分配比例、blocksize都可以在创建文件系统的时候人为指定。

3.2.2. ext文件系统预留的inode号

具体的inode号对应什么文件可以使用”find / -inum NUM”查看。

Ext4的特殊inode:

inode号	用途
0	不存在0号inode
1	虚拟文件系统，如/proc和/sys
2	根目录
3	ACL索引
4	ACL数据
5	Boot loader
6	未删除的目录
7	预留的块组描述符inode
8	日志inode
11	第一个非预留的inode，通常是lost+found目录

所以在ext4文件系统的dumpe2fs信息中，能观察到fisrt inode号可能为11也可能为12。
不同文件系统之间是可能会出现使用相同inode号文件的

3.3. ext2/3的inode直接、间接寻址

inode中保存了blocks指针，但是一条inode记录中能保存的指针数量是有限的，否则就会超出inode大小(128字节或256字节)。
在ext2和ext3文件系统中，一个inode中最多只能有15个指针，每个指针使用i_block[n]表示。
前12个指针i_block[0]到i_block[11]是直接寻址指针，每个指针指向一个数据区的block。

第13个指针i_block[12]是一级间接寻址指针，它指向一个仍然存储了指针的block即i_block[12] –> Pointerblock –> datablock。
第14个指针i_block[13]是二级间接寻址指针，它指向一个仍然存储了指针的block，但是这个block中的指针还继续指向其他存储指针的block，即i_block[13] –> Pointerblock1 –> PointerBlock2 –> datablock。
第15个指针i_block[14]是三级间接寻址指针，它指向一个任然存储了指针的block，这个指针block下还有两次指针指向。即i_block[13] –> Pointerblock1 –> PointerBlock2 –> PointerBlock3 –> datablock。

对应的中间指针block, Pointerblock* 如果为4k, 对于32位系统, 则一个中间block对应4k/32=128个指针.

这里的计算只是表明一个大文件是如何寻址和分配的.
如果存放的文件大于64M，那么就继续使用三级间接指针i_block[14]，存放的指针数量为1T个, 存放的文件大小为4T左右

1
2
3

$$
(4096/4)^3 + (4096/4)^2 + 4096/4 + 12 = 1T
$$

4. 单文件系统中文件操作的原理

4.1. 读取文件

cat /var/log/messages 命令, 其中保存了inode号, 通过多级目录查找inode号

找到根文件系统的块组描述符表GDT所在的blocks，读取GDT(已在内存中)找到inode table的block号。
因为GDT总是和superblock在同一个块组，而superblock总是在分区的第1024-2047个字节，所以很容易就知道第一个GDT所在的块组以及GDT在这个块组中占用了哪些block。
其实GDT早已经在内存中了，在系统开机的时候会挂载根文件系统，挂载的时候就已经将所有的GDT放进内存中。
在inode table的block中定位到根”/“的inode，找出”/“指向的data block。
前文说过，ext文件系统预留了一些inode号，其中”/“的inode号为2，所以可以根据inode号直接定位根目录文件的data block。
在”/“的datablock中记录了var目录名和指向var目录文件inode的指针，并找到该inode记录，
inode记录中存储了指向var的block指针，所以也就找到了var目录文件的data block。
通过var目录的inode指针，可以寻找到var目录的inode记录，
但是指针定位的过程中，还需要知道该inode记录所在的块组以及所在的inode table，所以需要读取GDT，同样，GDT已经缓存到了内存中。
在var的data block中记录了log目录名和其inode指针，通过该指针定位到该inode所在的块组及所在的inode table，并根据该inode记录找到log的data block。
在log目录文件的data block中记录了messages文件名和对应的inode指针，通过该指针定位到该inode所在的块组及所在的inode table，并根据该inode记录找到messages的data block。
最后读取messages对应的datablock
将上述步骤中GDT部分的步骤简化后比较容易理解:
找到GDT–>找到”/“的inode–>找到/的数据块读取var的inode–>找到var的数据块读取log的inode–>找到log的数据块读取messages的inode–>找到messages的数据块并读取它们

4.2. 删除、重命名和移动文件(不跨越文件系统)

删除文件分为普通文件和目录文件，知道了这两种类型的文件的删除原理，就知道了其他类型特殊文件的删除方法。
- 删除普通文件
  - 找到文件的inode和data block(根据前一个小节中的方法寻找)
  - 将inode table中该inode记录中的data block指针删除
  - 在imap中将该文件的inode号标记为未使用
  - 在其所在目录的data block中将该文件名所在的记录行删除，删除了记录就丢失了指向inode的指针
  - 将bmap中data block对应的block号标记为未使用。
- 删除目录文件
  - 找到目录和目录下所有文件、子目录、子文件的inode和data block；
  - 在imap中将这些inode号标记为未使用
  - 将bmap中将这些文件占用的 block号标记为未使用
  - 在该目录的父目录的data block中将该目录名所在的记录行删除
    标记data block为未使用后，表示开始释放空间，这些data block可以被其他文件重用.
    在第(5)步之前，由于data block还未被标记为未使用，在superblock中仍然认为这些data block是正在使用中的。这表示尽管文件已经被删除了，但空间却还没有释放，df也会将其统计到已用空间中(df是读取superblock中的数据块数量，并计算转换为空间大小)。
    当一个进程正在引用文件时将该文件删除，就会出现文件已删除但空间未释放的情况。有可能出现du统计结果比df小的原因

4.3. 移动文件

同文件系统下移动文件实际上是修改目标文件所在目录的data block, 向其中添加一行指向inode table中待移动文件的inode指针,
如果目标路径下有同名文件，则会提示是否覆盖，实际上是覆盖目录data block中冲突文件的记录，由于同名文件的inode记录指针被覆盖，所以无法再找到该文件的data block，也就是说该文件被标记为删除(如果多个硬链接数，则另当别论)。
所以在同文件系统内移动文件相当快，仅仅在所在目录data block中添加或覆盖了一条记录而已。也因此，移动文件时，文件的inode号是不会改变的。

对于不同文件系统内的移动，相当于先复制再删除的动作

4.4. 存储和复制文件

对于文件存储
- 1. 读取GDT，找到各个(或部分)块组imap中未使用的inode号，并为待存储文件分配inode号；
- 1. 在inode table中完善该inode号所在行的记录；
- 1. 在目录的data block中添加一条该文件的相关记录；
- 1. 将数据填充到data block中。
  - 填充到data block中的时候会调用block分配器：一次分配4KB大小的block数量，当填充完4KB的data block后会继续调用block分配器分配4KB的block，然后循环直到填充完所有数据。也就是说，如果存储一个100M的文件需要调用block分配器100*1024/4=25600次。
  - 在block分配器分配block时，block分配器并不知道真正有多少block要分配，只是每次需要分配时就分配，在每存储一个data block前，就去bmap中标记一次该block已使用，它无法实现一次标记多个bmap位。这一点在ext4中进行了优化。
- 1. 填充完之后，去inode table中更新该文件inode记录中指向data block的寻址指针。
对于复制，完全就是另一种方式的存储文件。步骤和存储文件的步骤一样。

5. 多文件系统关联

5.1. 根文件系统的特殊性

这里要明确的是，任何一个文件系统要在Linux上能正常使用，必须挂载在某个已经挂载好的文件系统中的某个目录下，例如/dev/cdrom挂载在/mnt上，/mnt目录本身是在”/“文件系统下的。而且任意文件系统的一级挂载点必须是在根文件系统的某个目录下，因为只有”/“是自引用的。这里要说明挂载点的级别和自引用的概念。

文件系统2挂载在文件系统1中的某个目录下，而文件系统1又挂载在根文件系统中的某个目录下。

5.1.1. 自引用

自引用的只能是文件系统，而文件系统表现形式是一个目录，所以自引用是指该目录的data block中，"."和".."的记录中的inode指针都指向inode table中同一个inode记录，所以它们inode号是相同的，即互为硬链接。而根文件系统是唯一可以自引用的文件系统。

[root@xuexi /]# ll -ai /
total 102
     2 dr-xr-xr-x.  22 root root  4096 Jun  6 18:13 .
     2 dr-xr-xr-x.  22 root root  4096 Jun  6 18:13 ..

cd .和 cd ..效果是一样的.这是自引用最直接的表现形式。
根目录下的”.”和”..”都是”/“目录的硬链接，且其datablock中不记录名为”/“的条目，因此除去根目录下子目录数后的硬链接数为2。

5.2. 挂载文件系统的细节

挂载文件系统到某个目录下，例如”mount /dev/cdrom /mnt”，挂载成功后/mnt目录中的文件全都暂时不可见了，且挂载后权限和所有者(如果指定允许普通用户挂载)等的都改变了，知道为什么吗？
详细说明挂载过程中涉及的细节
当文件系统/dev/cdrom挂载到/mnt上后，/mnt此时就已经成为另一个文件系统的入口了，因此它需要连接两边文件系统的inode和data block
在根文件系统的inode table中，为/mnt重新分配一个inode记录m，该记录的block指针block_m指向文件系统/dev/cdrom中的data block。既然为/mnt分配了新的inode记录m，那么在”/“目录的data block中，也需要修改其inode指针为inode_m以指向m记录。同时，原来inode table中的inode记录n就被标记为暂时不可用。
block_m指向的是文件系统/dev/cdrom的data block，所以严格说起来，除了/mnt的元数据信息即inode记录m还在根文件系统上，/mnt的data block已经是在/dev/cdrom中的了。这就是挂载新文件系统后实现的跨文件系统，它将挂载点的元数据信息和数据信息分别存储在不同的文件系统上。
而卸载文件系统，其实质是移除临时新建的inode记录(当然，在移除前会检查是否正在使用)及其指针，并将指针指回原来的inode记录，这样inode记录中的block指针也就同时生效而找回对应的data block了

挂载点挂载时的inode记录是新分配的。
挂载后，挂载点的内容将暂时不可见、不可用，卸载后文件又再次可见、可用。
挂载点原来的inode记录暂时被标记为不可用，关键是没有指向该inode记录的inode指针了。在卸载文件系统后，又重新启用挂载点原来的inode记录，”/“目录下的mnt的inode指针又重新指向该inode记录。
挂载后，挂载点的元数据和data block是分别存放在不同文件系统上的。
挂载点即使在挂载后，也还是属于源文件系统的文件

5.3. ext3文件系统的日志功能

相比ext2文件系统，ext3多了一个日志功能。
在创建ext3文件系统时会划分三个区：数据区、日志区和元数据区。每次存储数据时，先在日志区中进行ext2中元数据区的活动，直到文件存储完成后标记上commit才将日志区中的数据转存到元数据区。当存储文件时突然断电，下一次检查修复文件系统时，只需要检查日志区的记录，将bmap对应的data block标记为未使用，并把inode号标记未使用，这样就不需要扫描整个文件系统而耗费大量时间。

5.4. ext4文件系统

ext2和ext3文件系统, 对于一个巨大的文件，扫描整个bmap都将是一件浩大的工程。另外在inode寻址方面，ext2/3使用直接和间接的寻址方式，对于三级间接指针，可能要遍历的指针数量是非常非常巨大的。
ext4文件系统的最大特点是在ext3的基础上使用区(extent，或称为段)的概念来管理。一个extent尽可能的包含物理上连续的一堆block。inode寻址方面也一样使用区段树的方式进行了改进。

以下是ext4文件系统中一个文件的inode属性示例，注意最后两行的EXTENTS。

Inode: 12   Type: regular    Mode:  0644   Flags: 0x80000
Generation: 476513974    Version: 0x00000000:00000001
User:     0   Group:     0   Size: 11
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 8
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x5b628ca0:491d6224 -- Thu Aug  2 12:46:24 2018
 atime: 0x5b628ca0:491d6224 -- Thu Aug  2 12:46:24 2018
 mtime: 0x5b628ca0:491d6224 -- Thu Aug  2 12:46:24 2018
crtime: 0x5b628ca0:491d6224 -- Thu Aug  2 12:46:24 2018
Size of extra inode fields: 28
EXTENTS: # 注意
(0):33409

EXT4的inode 结构做了重大改变，为增加新的信息，大小由EXT3的128字节增加到默认的256字节，同时inode寻址索引不再使用EXT3的”12个直接寻址块+1个一级间接寻址块+1个二级间接寻址块+1个三级间接寻址块”的索引模式，而改为4个Extent片断流，每个片断流设定片断的起始block号及连续的block数量(有可能直接指向数据区，也有可能指向索引块区)。
片段流即下图中索引节点(inde node block)部分的绿色区域，每个15字节，共60字节。

5.4.1. EXT4删除数据的结构更改

EXT4删除数据后，会依次释放文件系统bitmap空间位、更新目录结构、释放inode空间位。

5.4.2. ext4使用多block分配方式

在存储数据时，ext3中的block分配器一次只能分配4KB大小的Block数量，而且每存储一个block前就标记一次bmap。假如存储1G的文件，blocksize是4KB，那么每存储完一个Block就将调用一次block分配器，即调用的次数为10241024/4KB=262144次，标记bmap的次数也为10241024/4=262144次。

而在ext4中根据区段来分配，可以实现调用一次block分配器就分配一堆连续的block，并在存储这一堆block前一次性标记对应的bmap。这对于大文件来说极大的提升了存储效率。

5.5. ext类的文件系统的缺点

最大的缺点是它在创建文件系统的时候就划分好一切需要划分的东西，以后用到的时候可以直接进行分配，也就是说它不支持动态划分和动态分配。对于较小的分区来说速度还好，但是对于一个超大的磁盘，速度是极慢极慢的。例如将一个几十T的磁盘阵列格式化为ext4文件系统，可能你会因此而失去一切耐心。

除了格式化速度超慢以外，ext4文件系统还是非常可取的。当然，不同公司开发的文件系统都各有特色，最主要的还是根据需求选择合适的文件系统类型。

5.6. 根据inode号找到其block号

首先可以挂载手机中的system.img到本地
比如查看system/etc/recovery-resource.dat的block号

$ stat recovery-resource.dat         
  File: ‘recovery-resource.dat’
  Size: 174555    	Blocks: 344        IO Block: 4096   regular file
Device: 700h/1792d	Inode: 334         Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2017-04-20 21:53:39.000000000 +0800
Modify: 2017-04-20 21:53:39.000000000 +0800
Change: 2017-04-20 21:53:39.000000000 +0800
 Birth: -

inode号为334, dump出的信息并没有数据block相关的内容.
确定Block size

dumpe2fs system.img | grep "Block size"
$ dumpe2fs system.img | grep size 
dumpe2fs 1.42.9 (4-Feb-2014)
Filesystem features:      has_journal ext_attr resize_inode filetype needs_recovery extent sparse_super large_file uninit_bg
Block size:               4096
Fragment size:            4096
Inode size:	          256

block大小为4k, inode size为256.
根据inode号为344, 确定其所在的块组.
首先确定每个块组的inode数, 根据dumpe2fs出的信息:

1	Inodes per group: 7472

(344-1)/7472 （一个块组的inode数）= 0, 即该inode 落在第0块组内
（344-1）%7472 = 343, 该inode在某个inode Table的第343项
0×32768（一个块组共有32768块）=0，得该文件inode落在第343块组的起始块为0
从dump出的信息来看, 块组0的inode Table的起始块为27, 一个inode占256, 一个块中有8个inode

Group 0: (Blocks 0-32767) [ITABLE_ZEROED]
  Checksum 0x66c5, unused inodes 0
  Primary superblock at 0, Group descriptors at 1-1
  Reserved GDT blocks at 2-24
  Block bitmap at 25 (+25), Inode bitmap at 26 (+26)
  Inode table at 27-493 (+27)
  1 free blocks, 6158 free inodes, 48 directories
  Free blocks: 32767
  Free inodes: 1315-7472

则344号所在的块为27+343/16 = 27+ 21 = 48
在48块的 344%16=8 第8个256字节处.
334%16=14 第14个256字节处
vi查看时通过:%!xxd转换为16进制查看, 一行有16个字节, 16行代表一个256字节单位.
因此第8个256在起始于16*7+1个位置第113行位置
上面只查找到inode table为位置.

通过dump出inode table的数据块 count=512代表dump出48块开始的512个block.

1	dd if=/dev/sda5 ibs=4096 skip=48 count=512 of=inode_table

定位到0x700位置, 即7*256 转换为16进制.

0000700: 3f3f 0000 3f14 0000 593f 3f58 593f 3f58  ??..?...Y??XY??X
0000710: 593f 3f58 0000 0000 0000 0100 1000 0000  Y??X............
0000720: 3f00 0800 0000 0000 0a3f 0100 0300 0000  ?........?......
0000730: 0000 0000 0000 0000 0200 0000 6e29 0000  ............n)..
0000740: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000750: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000760: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000770: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000780: 1c00 0000 0000 0000 0000 0000 0000 0000  ................
0000790: 0000 0000 0000 0000 0000 0000 0000 023f  ...............?
00007a0: 0706 4400 0000 0000 1a00 0000 0000 0000  ..D.............
00007b0: 7365 6c69 6e75 7800 0000 0000 0000 0000  selinux.........
00007c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00007d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00007e0: 0000 0000 753a 6f62 6a65 6374 5f72 3a73  ....u:object_r:s
00007f0: 7973 7465 6d5f 6669 6c65 3a73 3000 0000  ystem_file:s0...

偏移60个字节(0000600+3C), 即可定位到数据指针(6e29 0000), 由于ext4采用了小端存储, 则其数据指针为0x296e,转换为10进制为 10606
使用debugfs验证一下

$ debugfs
debugfs 1.42.9 (4-Feb-2014)
debugfs:  open -w system.img
debugfs:  mi<344>
debugfs: Unknown request "mi<344>".  Type "?" for a request list.
debugfs:  mi <344>
                          Mode    [0100644]
                       User ID    [0]
                      Group ID    [0]
                          Size    [5375] 
                 Creation time    [1492695641] 
             Modification time    [1492695641] 
                   Access time    [1492695641] 
                 Deletion time    [0] 
                    Link count    [1] 
              Block count high    [0] 
                   Block count    [16] 
                    File flags    [0x80080] 
                    Generation    [0x0] 
                      File acl    [0] 
           High 32bits of size    [0] 
              Fragment address    [0] 
               Direct Block #0    [127754] 
               Direct Block #1    [3] 
               Direct Block #2    [0] 
               Direct Block #3    [0] 
               Direct Block #4    [2]
               #db5 为10606说明是正确的
               Direct Block #5    [10606]

334号inode 定位到0xd00位置, 即13*256转换16机制

0000d00: 3f3f 0000 dba9 0200 633f 3f58 633f 3f58  ??......c??Xc??X
0000d10: 633f 3f58 0000 0000 0000 0100 5801 0000  c??X........X...
0000d20: 3f00 0800 0000 0000 0a3f 0100 0300 0000  ?........?......
0000d30: 0000 0000 0000 0000 2b00 0000 3329 0000  ........+...3)..
0000d40: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000d50: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000d60: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000d70: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000d80: 1c00 0000 0000 0000 0000 0000 0000 0000  ................
0000d90: 0000 0000 0000 0000 0000 0000 0000 023f  ...............?
0000da0: 0706 4400 0000 0000 1a00 0000 0000 0000  ..D.............
0000db0: 7365 6c69 6e75 7800 0000 0000 0000 0000  selinux.........
0000dc0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000dd0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000de0: 0000 0000 753a 6f62 6a65 6374 5f72 3a73  ....u:object_r:s
0000df0: 7973 7465 6d5f 6669 6c65 3a73 3000 0000  ystem_file:s0...

2933 10547也是能对应上.
0xd00-0xdf0 即为system/etc/recovery-resource.dat对应的inode

blog

文件系统调研