Dokuwiki中文增强版技术支持中心

目录优先使用FMTLOCAL格式的datafork，将数据以short format的格式存储在datafork空间内部。
在datafork空间不足后，目录转而使用FMTEXTENTS格式的datafork。在EXTENTS格式下有三种格式的目录组织形式，第一种是Block directory，第二种是Leaf directory，第三种是Node directory。随着数据量的逐渐增加，一步步进阶使用。

那么随着数据量的继续增加，extents越来越多，终于datafork空间不足以extent list的形式存储这些extent records，这时就要采用终极形式——B+tree。我们在前面已经讲了XFS使用过的多种B+tree格式的变种，而且也在前两篇关于目录的文章中介绍了关于目录的众多相关结构。下面我们就要用到这些预备知识来讲解目录的B+tree结构。

目录的B+tree

其实我们在前文讲到Node directory的时候已经接触到一个简单的B+tree了，那就是Node block索引Leaf blocks的时候，其实就是一个简单的以hashval为关键字的B+tree了。如果进一步扩展，Node block后面可以再接多层Node blocks，直到Leaf blocks，形成一个B+tree结构，比如如下示意图：

        +———-+—————+——+——–+—–+——+——–+
        | Node hdr | hash | before | hash | before | … | hash | before |
        +———-+—————+——+——–+—–+——+——–+
                              |               |                     |
      +———————–+               +——-+      +——+
      |                                               |      |
      V                                               |      V
+———-+—————+—————+—–+    |    +————+
	
		 Node hdr   hash   before   hash   before   …             Node block 
	

+———-+—————+—————+—–+    |    +————+
                      |                |         |    V                 |
                      |                |         |    +————+    V
    +—————–+                |         |    | Node block |   …
    |                                  |         |    +————+
    V                                  |         V               |
+———-+————-+—–+       |        +————+   +—> …
	
		 Leaf hdr   hash   addr   …                    Leaf block 
	

+———-+————-+—–+       |        +————+
                                       V
                                    +———-+————-+—–+
                                    | Leaf hdr | hash | addr | … |
                                    +———-+————-+—–+

所以这里有一个B+tree，用于组织leaf blocks。但是我们知道inode的数据终归是由extent管理，所以如何管理目录的extents是目录组织结构的首要事情。当extents list超过datafork的存储范围后就会变成B+tree结构，和之前讲过的普通文件的extents list变B+tree结构时一样（参考：醉卧沙场：XFS的on-disk组织结构(7)——Inode Datafork of regular file）。一个B+tree directory的数据组织形式大约如下：

首先是datafork变成BMapt BTree结构的头部(bmdr），通过它可以索引到很多bmbt block（上图仅画了1级bmbt）。BMap BTree结构的最终节点就是目录的data block, node block, leaf block以及freeindex block组成的extents。找到这些extents，就可以通过讲解Node directory时用到的方式，利用Node block索引Leaf Blocks，定位Data block的内容。上图画了一个2级的Node-Leaf B+tree。

也就是说B+Tree directory实际上由inode的BMap BTree以及目录特有的一个Node-leaf blocks B+tree组成。为了便于理解，我们还是举一个实例，下面我创建了一个包含20多万个文件的目录，现在我尝试定位里面一个叫"looooooooooooooooooooooooooooooooooooooooooooooooooooooooooongfile200000"的文件，比如这样：

# ls -l /mnt/test/dir0/looooooooooooooooooooooooooooooooooooooooooooooooooooooooooongfile200000
-rw-r–r–. 1 root root 0 Mar 26 15:22 /mnt/test/dir0/looooooooooooooooooooooooooooooooooooooooooooooooooooooooooongfile200000

那当我们只知道/mnt/test/dir0/下面有一个叫"looo….oongfile200000"的客体时，我怎么通过B+Tree结构的"dir0"，找到其下"looo….oongfile200000"所对应的inode号（从而才能找到其inode块）呢？

首先我们看目录dir0的datafork的内容：

xfsdb> inode 131
xfsdb> p
…
core.format = 3 (btree)
core.nblocks = 6130
core.extsize = 0
core.nextents = 2541
…
u3.bmbt.level = 1
u3.bmbt.numrecs = 11
u3.bmbt.keys[1-11] = [startoff]
1:[0]
2:[740]
3:[1498]
4:[2232]
5:[2990]
6:[3734]
7:[4455]
8:[4850]
9:[8388609]
10:[8388882]
11:[8389125]
u3.bmbt.ptrs[1-11] = 1:172 2:3713 3:10160 4:15124 5:20265 6:25313 7:30201 8:35261 9:7293 10:12884 11:24751
…

我们可以看到datafork中不是一个extents list了，而是一个level=1的BMap BTree的头部。我们首先要找的是"looo….oongfile200000"对应的Leaf block里的[hashval, address]对，前面我们知道Node/Leaf的偏移地址是32GB，我当前XFS的blocksize=4k，34359738368/4096 = 8388608，所以Node/Leaf区域的第一个block在8388608这个偏移地址处。根据bmbt.keys的内容，我们可以确定8388608在keys[8]~[9]之间，所以就在keys[8]所对应的范围里，那么我们通过bmbt.ptrs[8]来找到bmbt.keys[8]对应的block：

xfsdb> addr u3.bmbt.ptrs[8]
xfsdb> p
…
173:[5328,36124,4,0] 
174:[5332,36152,2,0] 
175:[8388608,14,1,0]

我们看到这个block里的最后一个record就是8388608偏移地址所在的位置，其在物理地址的第14个block处，并占用1个block，我们下面就去这个位置看一看其内容：

xfsdb> dblock 8388608
xfsdb> p
nhdr.info.hdr.forw = 0
nhdr.info.hdr.back = 0
nhdr.info.hdr.magic = 0x3ebe
nhdr.info.crc = 0x93bb2608 (correct)
nhdr.info.bno = 112
nhdr.info.lsn = 0x6000051ab
nhdr.info.uuid = ea53b14f-9edd-4cdd-8f37-4d825fd89590
nhdr.info.owner = 131
nhdr.count = 2
nhdr.level = 2
nbtree[0-1] = [hashval,before] 
0:[0x795666e9,8389115] 
1:[0xffe3e7df,8389114]

可以看到这是一个Node block，并且其肯定是root node，而且level=2。所以其下面还得有一级的Node blocks。到此B+Tree的关键字就变为hashval了，所以我们先计算"looo….oongfile200000"的hash值：

xfsdb> hash looooooooooooooooooooooooooooooooooooooooooooooooooooooooooongfile200000
0x69d667e0

得到0x69d667e0这个hash值，我们就可以知道应该去 0:[0x795666e9,8389115] 这个地方去找下一个Node block：

xfsdb> dblock 8389115
xfsdb> p
nhdr.info.hdr.forw = 8389114
nhdr.info.hdr.back = 0
nhdr.info.hdr.magic = 0x3ebe
nhdr.info.crc = 0x759db2e3 (correct)
nhdr.info.bno = 187104
nhdr.info.lsn = 0x800000b1a
nhdr.info.uuid = ea53b14f-9edd-4cdd-8f37-4d825fd89590
nhdr.info.owner = 131
nhdr.count = 410
nhdr.level = 1
nbtree[0-409] = [hashval,before]
…
367:[0x69b7e37f,8388875]
368:[0x69d424f1,8388890]
369:[0x69d46663,8388684]
370:[0x69d6277b,8388678]
371:[0x69d6a6fa,8388623]
372:[0x69d726e5,8388633]
…

我们看到这是一个level=1的Node block，0x69d667e0这个hash值就位于 371:[0x69d6a6fa,8388623]这个block里，因为这里已经是level=1的node了，所以下面就肯定是Leaf block了，我们去这个leaf block里继续找：

xfsdb> dblock 8388623
xfsdb> p
lhdr.info.hdr.forw = 8388633
lhdr.info.hdr.back = 8388678
lhdr.info.hdr.magic = 0x3dff
lhdr.info.crc = 0xd1116e5b (correct)
lhdr.info.bno = 6256
lhdr.info.lsn = 0x1000044fe
lhdr.info.uuid = ea53b14f-9edd-4cdd-8f37-4d825fd89590
lhdr.info.owner = 131
lhdr.count = 379
lhdr.stale = 0
…
lents[203].hashval = 0x69d6677f
lents[203].address = 0x10fa
lents[204].hashval = 0x69d667e0
lents[204].address = 0x1c9
lents[205].hashval = 0x69d667e1
lents[205].address = 0x24a
…

果然，在这里我们找到了lents[204].hashval = 0x69d667e0，其正好和我们要找的文件名的hash值相等，所以我们取其address，得到lents[204].address = 0x1c9，前面我们已经知道这里地址需要乘以8，所以 0x1c9 * 8 = 0xe48 = 3656，比一个directory blocksize还小，说明这个地址就在第0个directory block里。现在我们回到目录的datafork，去找startoff=0的extent在哪：

u3.bmbt.level = 1
u3.bmbt.numrecs = 11
u3.bmbt.keys[1-11] = [startoff] 
1:[0] 
2:[740] 
3:[1498] 
4:[2232] 
5:[2990] 
6:[3734] 
7:[4455] 
8:[4850] 
9:[8388609] 
10:[8388882] 
11:[8389125]
u3.bmbt.ptrs[1-11] = 1:172 2:3713 3:10160 4:15124 5:20265 6:25313 7:30201 8:35261 9:7293 10:12884 11:24751

所以startoff=0的extent肯定在u3.bmbt.ptrs[1]对应的地址上，我们去这个地址看一下：

xfsdb> addr u3.bmbt.ptrs[1]
xfsdb> p
magic = 0x424d4133
level = 0
numrecs = 251
leftsib = null
rightsib = 3713
bno = 1376
lsn = 0x200002ce7
uuid = ea53b14f-9edd-4cdd-8f37-4d825fd89590
owner = 131
crc = 0x4f9bc2e (correct)
recs[1-251] = [startoff,startblock,blockcount,extentflag]
1:[0,15,1,0]
2:[1,13,1,0]
3:[2,12,1,0]
…

可以看到startoff=0的extent就在1:[0,15,1,0]的位置，我们去这个位置看一下：

xfsdb> fsblock 15
xfsdb> type dir3
xfsdb> p
…
du[43].name = "looooooooooooooooooooooooooooooooooooooooooooooooooooooooooongfile200000"
du[43].filetype = 1
du[43].tag = 0xe48
du[44].inumber = 174
du[44].namelen = 73
…

果然在其内部找到了我们要找的文件，文件名完全一致，并且我们也找到了其inode号du[44].inumber = 174。根据这个inode号我们就能定位这个文件所对应的inode的位置了。

结语

到此所有和XFS目录相关的数据组织结构都讲完了，篇幅较多，且较复杂。本篇是用到了前面四篇讲解inode结构的所有知识点，虽篇幅不长，但是如果没有前面的基础是看不懂的。但是反过来说，如果你能理解到这里，前面的知识你肯定也能很容易的理解了。

文件系统最主要的两种文件——普通文件和目录的数据组织方式已经讲完，我们一直在说datafork的部分，下面是时候说一下inode结构的最后一个重要部分，也就是用于存储扩展属性的attrfork相关的内容了。扩展属性的存储结构和目录有很多相似的地方，如果你理解了目录数据的组织方式，理解扩展属性并不难，下一篇文章见。

Dokuwiki中文增强版技术支持中心

站点工具

侧边栏

dokuwiki

Learn More

Donate ❤️

Learn More

Donate ❤️

Dokuwiki中文网 | 知识库、开源知识库、免费知识库、wiki…

dokuwiki使用教程 - 相关博客 - 开发者搜索

前言

目录的B+tree

结语

页面工具