首页 > *nix技术, 文件系统 > Xfs文件系统磁盘布局之六:ABTB的B+tree(续)

Xfs文件系统磁盘布局之六:ABTB的B+tree(续)

2012年1月2日 发表评论 阅读评论 4,385 次浏览

继续验证空闲块的管理,这里我们先拷贝个新的磁盘(关联到loop2),便于对比,先挂载这个loop2磁盘,并写入一个文件,然后再卸载(保证数据已经写到磁盘上),具体操作如下:

[root@localhost xfsprogs]# cd /home/lenky/loop/
[root@localhost loop]# cp xfs.img.256 xfs.img.256.new 
[root@localhost loop]# losetup /dev/loop2 xfs.img.256
[root@localhost loop]# mkdir xfs.256.new
[root@localhost loop]# mount /dev/loop2 xfs.256.new/
[root@localhost loop]# cd !$
cd xfs.256.new/
[root@localhost xfs.256.new]# ls
linux-2.6.36.1
[root@localhost xfs.256.new]# cat > lenky.xfs
1111111111111111111111111111111111111
2222222222222222222222222222222222222
3333333333333333333333333333333333333
^C
[root@localhost xfs.256.new]# cat lenky.xfs 
1111111111111111111111111111111111111
2222222222222222222222222222222222222
3333333333333333333333333333333333333
[root@localhost xfs.256.new]# cd ..
[root@localhost loop]# umount xfs.256.new/
[root@localhost loop]# 

再来看一下ABTB:

[root@localhost loop]# /home/lenky/xfs/xfsprogs/db/xfs_db /dev/loop2
xfs_db> agf 0
xfs_db> p
magicnum = 0x58414746
versionnum = 1
seqno = 0
length = 16384
bnoroot = 1
cntroot = 2
bnolevel = 1
cntlevel = 1
flfirst = 0
fllast = 3
flcount = 4
freeblks = 15652
longest = 4006
btreeblks = 0
xfs_db> fsblock 1
xfs_db> type bnobt
xfs_db> p
magic = 0x41425442
level = 0
numrecs = 49
leftsib = null
rightsib = null
recs[1-49] = [startblock,blockcount] 1:[13,1] 2:[18,1] 3:[25,3] 4:[32,4] 5:[40,4] 6:[48,6] 7:[58,2] 8:[64,2] 9:[68,4] 10:[76,4] 11:[83,3] 12:[98,2] 13:[104,77] 14:[189,40] 15:[233,36] 16:[270,9] 17:[565,63] 18:[637,62] 19:[701,2] 20:[705,32] 21:[740,40] 22:[782,100] 23:[886,13] 24:[900,8] 25:[910,4] 26:[915,3] 27:[919,2] 28:[922,4] 29:[928,132] 30:[1063,1080] 31:[2163,1528] 32:[3711,1722] 33:[5457,570] 34:[6061,74] 35:[6185,1] 36:[6194,8] 37:[6206,4006] 38:[10266,61] 39:[10369,3938] 40:[14322,304] 41:[14634,2] 42:[14640,36] 43:[14677,1] 44:[14680,21] 45:[14702,80] 46:[14784,75] 47:[14888,59] 48:[14960,57] 49:[15018,1366]
xfs_db> 

对比上一篇的ABTB数据,只有两处不同:
freeblks = 15653
freeblks = 15652

recs[1-49] = [startblock,blockcount] 1:[12,2] …
recs[1-49] = [startblock,blockcount] 1:[13,1] …
即第12(编号从0开始)块block被占用了,所以总空闲块数(freeblks)少了一块,并且空闲块链里的[12,2]变成了[13,1],看一下第12块block的具体数据是什么:

xfs_db> fsblock 12
xfs_db> type text
xfs_db> p
000:  31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31  1111111111111111
010:  31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31  1111111111111111
020:  31 31 31 31 31 0a 32 32 32 32 32 32 32 32 32 32  11111.2222222222
030:  32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32  2222222222222222
040:  32 32 32 32 32 32 32 32 32 32 32 0a 33 33 33 33  22222222222.3333
050:  33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33  3333333333333333
060:  33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33  3333333333333333
070:  33 0a 00 00 00 00 00 00 00 00 00 00 00 00 00 00  3...............
080:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
090:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
*
ff0:  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
xfs_db> 

刚好是文件lenky.xfs里的内容,这说明这块原本的空闲block被用来存放文件lenky.xfs了。一个文件还有inode信息,为什么没有看到lenky.xfs的inode占去空闲块呢?因为之前提到过inode总是以64为chunk进行分配和释放,所以lenky.xfs的inode正好利用到了之前申请的但尚未使用的inode空间。
有了上面的这些基础认识,再来看多层(即树深度不为1)的情况。要找一个多层的实例,如果有现成的使用了很久的Xfs文件系统分区就最好了,没有的话就可以这样尝试自己弄一个,我这里是先尽量把4G的磁盘写满,然后再随机的删一大部分,这样让它的Btree打乱,以形成多层结构:

[root@localhost sdb1]# cp /usr/
bin/     etc/     games/   include/ lib/     libexec/ local/   sbin/    share/   src/     tmp/     
[root@localhost sdb1]# cp -r /usr/* ./
...
[root@localhost sdb1]# find . -name "*a*" | xargs rm
...
[root@localhost sdb1]# find . -name "*b*" | xargs rm
...
[root@localhost sdb1]# du -sh
1.7G	.
[root@localhost sdb1]# cd ..
[root@localhost xfs]# umount sdb1/
[root@localhost xfs]# /home/lenky/xfs/xfsprogs/db/xfs_db /dev/sdb1
xfs_db> agf 0
xfs_db> p
magicnum = 0x58414746
versionnum = 1
seqno = 0
length = 262059
bnoroot = 5
cntroot = 472
bnolevel = 2
cntlevel = 2
flfirst = 21
fllast = 26
flcount = 6
freeblks = 165395
longest = 86535
btreeblks = 16
xfs_db> 

从上面的数据可以看出,ABTB类型的B+tree深度为2,而根节点所在的block块号为5:
bnoroot = 5
bnolevel = 2

xfs_db> fsblock 5
xfs_db> type bnobt
xfs_db> p
magic = 0x41425442
level = 1
numrecs = 8
leftsib = null
rightsib = null
keys[1-8] = [startblock,blockcount] 1:[32,3] 2:[47931,66] 3:[70425,1] 4:[75668,2] 5:[99725,12] 6:[139125,51] 7:[151459,3] 8:[153765,1]
ptrs[1-8] = 1:1 2:324 3:4 4:473 5:6 6:138 7:139 8:110
xfs_db> 

根节点的level为1,表示这是一个中间节点,前面提到过叶子节点里数据的布局,而对于中间节点,多了“指针”字段,如下,图中xfs_alloc_rec即为xfs_alloc_rec_t,xfs_alloc_key即为xfs_alloc_key_t,xfs_alloc_ptr即为xfs_alloc_ptr_t,后面说明类此:

对于中间节点,存放“指针”字段xfs_alloc_ptr的开始地址并不是紧接在xfs_alloc_key[bb_numrecs – 1]之后,如果紧接着xfs_alloc_key[bb_numrecs – 1],一旦数目增加或减少(即bb_numrecs发生改变),那么岂不是要向前或者向后移动xfs_alloc_ptr的数据?对于xfs_alloc_ptr[0]的起始地址,通过函数btblock_ptr_offset可以看出端倪。通过计算出最大可能的bb_numrecs值,即xfs_alloc_ptr前面最大可能有多少个xfs_alloc_key,预留出需要的最大的空闲地址之后,就是xfs_alloc_ptr的开始地址,具体计算是这样:
一个节点占用一个block,这里默认的block大小为4096。
减去前面xfs_btree_block所占的空间,由于ABTB为“short form block”,即是XFS_BTREE_SBLOCK_LEN=16,那么,4096-16=4080。
最大可能的bb_numrecs值为:4080/(sizeof(xfs_alloc_key)+sizeof(xfs_alloc_ptr))=4080/(8+4)=340。
xfs_alloc_ptr的开始地址(相对本block偏移)xfs_alloc_ptr[0]=16+340*8=2736=0xAB0。
看实际数据验证我们的分析:

xfs_db> type text
xfs_db> p
000:  41 42 54 42 00 01 00 08 ff ff ff ff ff ff ff ff  ABTB............
010:  00 00 00 20 00 00 00 03 00 00 bb 3b 00 00 00 42  ...............B
020:  00 01 13 19 00 00 00 01 00 01 27 94 00 00 00 02  ................
030:  00 01 85 8d 00 00 00 0c 00 02 1f 75 00 00 00 33  ...........u...3
040:  00 02 4f a3 00 00 00 03 00 02 58 a5 00 00 00 01  ..O.......X.....
050:  73 e1 75 00 01 01 00 00 77 e1 75 00 01 01 00 00  s.u.....w.u.....
060:  80 e1 75 00 01 01 00 00 84 e1 75 00 01 01 00 00  ..u.......u.....
*
ab0:  00 00 00 01 00 00 01 44 00 00 00 04 00 00 01 d9  .......D........
ac0:  00 00 00 06 00 00 00 8a 00 00 00 8b 00 00 00 6e  ...............n
ad0:  73 ec 75 00 01 01 00 00 77 ec 75 00 01 01 00 00  s.u.....w.u.....
ae0:  87 ec 75 00 01 01 00 00 8b ec 75 00 01 01 00 00  ..u.......u.....
af0:  92 ec 75 00 01 01 00 00 96 ec 75 00 01 01 00 00  ..u.......u.....
b00:  a5 ec 75 00 01 01 00 00 a9 ec 75 00 01 01 00 00  ..u.......u.....
*
xfs_db> 

转载请保留地址:http://www.lenky.info/archives/2012/01/727http://lenky.info/?p=727


备注:如无特殊说明,文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限,虽力求内容正确无误,但仍然难免出错,请勿见怪,如果可以则请留言告之,并欢迎来讨论。另外值得说明的是,Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享,特别是一些带有完全参考的文章,其后附带的链接内容也许更直接、更丰富,而我只是做了一下归纳&转述,在此也一并表示感谢。关于本站的所有技术文章,欢迎转载,但请遵从CC创作共享协议,而一些私人性质较强的心情随笔,建议不要转载。

法律:根据最新颁布的《信息网络传播权保护条例》,如果您认为本文章的任何内容侵犯了您的权利,请以Email或书面等方式告知,本站将及时删除相关内容或链接。

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.