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

Xfs文件系统磁盘布局之五:ABTB的B+tree

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

关于B+tree数据结构不是本系列文章讨论的内容,其基本概念可以参考:http://en.wikipedia.org/wiki/B%2Btree。我们仍然先直接把实例数据给弄出来,这样便于分析和理解。新建一块磁盘并格式化,然后弄些数据上去:

[root@localhost xfsprogs]# cd /home/lenky/loop/
[root@localhost loop]# dd if=/dev/zero of=xfs.img.256 bs=512 count=524288
524288+0 records in
524288+0 records out
268435456 bytes (268 MB) copied, 10.1262 s, 26.5 MB/s
[root@localhost loop]# losetup /dev/loop1 xfs.img.256 
[root@localhost loop]# mkfs.xfs /dev/loop1
meta-data=/dev/loop1             isize=256    agcount=4, agsize=16384 blks
         =                       sectsz=512   attr=2, projid32bit=0
data     =                       bsize=4096   blocks=65536, imaxpct=25
         =                       sunit=0      swidth=0 blks
naming   =version 2              bsize=4096   ascii-ci=0
log      =internal log           bsize=4096   blocks=1200, version=2
         =                       sectsz=512   sunit=0 blks, lazy-count=1
realtime =none                   extsz=4096   blocks=0, rtextents=0
[root@localhost loop]# mkdir xfs.256
[root@localhost loop]# mount /dev/loop1 xfs.256/
[root@localhost loop]# cp -r /usr/src/linux-2.6.36.1 xfs.256/
cp: cannot create regular file `xfs.256/linux-2.6.36.1/net/core/dev_addr_lists.o': No space left on device
cp: cannot create regular file `xfs.256/linux-2.6.36.1/net/core/.skbuff.o.cmd': No space left on device
...
[root@localhost loop]# cd xfs.256/
[root@localhost xfs.256]# du -sh
238M	.
[root@localhost xfs.256]# find . -name "*a*" | xargs rm 
rm: cannot remove `./linux-2.6.36.1/Documentation': Is a directory
rm: cannot remove `./linux-2.6.36.1/Documentation/pcmcia': Is a directory
...
[root@localhost xfs.256]# find . -name "*b*" | xargs rm 
...
[root@localhost xfs.256]# find . -name "*c*" | xargs rm 
...
[root@localhost xfs.256]# find . -name "*d*" | xargs rm 
...
[root@localhost xfs.256]# find . -name "*e*" | xargs rm 
...
[root@localhost xfs.256]# find . -name "*f*" | xargs rm 
...
[root@localhost xfs.256]# du -sh
139M	.
[root@localhost xfs.256]# cd ..
[root@localhost loop]# umount xfs.256/
[root@localhost loop]# cd /home/lenky/xfs/xfsprogs
[root@localhost xfsprogs]# ./db/xfs_db /dev/loop1
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 = 15653
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:[12,2] 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>

这是一个树深度为1的B+tree,就先分析它吧。ABTB类型的B+tree对应的结构体为xfs_btree_block,而ABTB其中的union是使用的“short form pointers”,这从全局静态变量btrees可以看出,另一侧面也说明了块号都是相对本AG而言的:

struct xfs_btree_block {
	__be32		bb_magic;	/* magic number for block type */
	__be16		bb_level;	/* 0 is a leaf */
	__be16		bb_numrecs;	/* current # of data records */
	union {
		struct {
			__be32		bb_leftsib;
			__be32		bb_rightsib;
		} s;			/* short form pointers */
		struct	{
			__be64		bb_leftsib;
			__be64		bb_rightsib;
		} l;			/* long form pointers */
	} bb_u;				/* rest */
};

#define XFS_BTREE_SBLOCK_LEN	16	/* size of a short form block */
#define XFS_BTREE_LBLOCK_LEN	24	/* size of a long form block */

/*
 * Definition of the possible btree block layouts.
 */
struct xfs_db_btree {
	size_t			block_len;
	size_t			key_len;
	size_t			rec_len;
	size_t			ptr_len;
} btrees[] = {
	[/*0x424d415*/0] = { /* BMAP */
		XFS_BTREE_LBLOCK_LEN,
		sizeof(xfs_bmbt_key_t),
		sizeof(xfs_bmbt_rec_t),
		sizeof(__be64),
	},
	[/*0x4142544*/2] = { /* ABTB */
		XFS_BTREE_SBLOCK_LEN,
		sizeof(xfs_alloc_key_t),
		sizeof(xfs_alloc_rec_t),
		sizeof(__be32),
	},
	[/*0x4142544*/3] = { /* ABTC */
		XFS_BTREE_SBLOCK_LEN,
		sizeof(xfs_alloc_key_t),
		sizeof(xfs_alloc_rec_t),
		sizeof(__be32),
	},
	[/*0x4941425*/4] = { /* IABT */
		XFS_BTREE_SBLOCK_LEN,
		sizeof(xfs_inobt_key_t),
		sizeof(xfs_inobt_rec_t),
		sizeof(__be32),
	},
};

分析对应的字段数据:
xfs_db> fsblock 1
xfs_db> type bnobt
xfs_db> p
magic = 0x41425442
魔术数,即是‘ABTB’。
level = 0
0表示这是一个叶子节点,1表示为中间节点。
numrecs = 49
本叶子节点实际所跟踪的“空闲block块”,这些跟踪数据通过一个数组的形式链接起来,所以这个字段指定该数组的实际大小。
leftsib = null
叶子节点会以双向链表的形式链接起来,这里左节点为空。
rightsib = null
叶子节点会以双向链表的形式链接起来,这里右节点也为空。
recs[1-49] = [startblock,blockcount] 1:[12,2] 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]
本叶子节点实际所跟踪的“空闲block块”,这些跟踪数据通过一个数组的形式链接起来,这个字段指定该数组的实际值。
xfs_db>
布局图示如下:

可以直接hexdump磁盘对比一下:

[root@localhost xfsprogs]# hexdump -C -s 4096 -n 512 /dev/loop1
00001000  41 42 54 42 00 00 00 31  ff ff ff ff ff ff ff ff  |ABTB...1........|
00001010  00 00 00 0c 00 00 00 02  00 00 00 12 00 00 00 01  |................|
00001020  00 00 00 19 00 00 00 03  00 00 00 20 00 00 00 04  |........... ....|
00001030  00 00 00 28 00 00 00 04  00 00 00 30 00 00 00 06  |...(.......0....|
00001040  00 00 00 3a 00 00 00 02  00 00 00 40 00 00 00 02  |...:.......@....|
00001050  00 00 00 44 00 00 00 04  00 00 00 4c 00 00 00 04  |...D.......L....|
00001060  00 00 00 53 00 00 00 03  00 00 00 62 00 00 00 02  |...S.......b....|
00001070  00 00 00 68 00 00 00 4d  00 00 00 bd 00 00 00 28  |...h...M.......(|
00001080  00 00 00 e9 00 00 00 24  00 00 01 0e 00 00 00 09  |.......$........|
00001090  00 00 02 35 00 00 00 3f  00 00 02 7d 00 00 00 3e  |...5...?...}...>|
000010a0  00 00 02 bd 00 00 00 02  00 00 02 c1 00 00 00 20  |............... |
000010b0  00 00 02 e4 00 00 00 28  00 00 03 0e 00 00 00 64  |.......(.......d|
000010c0  00 00 03 76 00 00 00 0d  00 00 03 84 00 00 00 08  |...v............|
000010d0  00 00 03 8e 00 00 00 04  00 00 03 93 00 00 00 03  |................|
000010e0  00 00 03 97 00 00 00 02  00 00 03 9a 00 00 00 04  |................|
000010f0  00 00 03 a0 00 00 00 84  00 00 04 27 00 00 04 38  |...........'...8|
00001100  00 00 08 73 00 00 05 f8  00 00 0e 7f 00 00 06 ba  |...s............|
00001110  00 00 15 51 00 00 02 3a  00 00 17 ad 00 00 00 4a  |...Q...:.......J|
00001120  00 00 18 29 00 00 00 01  00 00 18 32 00 00 00 08  |...).......2....|
00001130  00 00 18 3e 00 00 0f a6  00 00 28 1a 00 00 00 3d  |...>......(....=|
00001140  00 00 28 81 00 00 0f 62  00 00 37 f2 00 00 01 30  |..(....b..7....0|
00001150  00 00 39 2a 00 00 00 02  00 00 39 30 00 00 00 24  |..9*......90...$|
00001160  00 00 39 55 00 00 00 01  00 00 39 58 00 00 00 15  |..9U......9X....|
00001170  00 00 39 6e 00 00 00 50  00 00 39 c0 00 00 00 4b  |..9n...P..9....K|
00001180  00 00 3a 28 00 00 00 3b  00 00 3a 70 00 00 00 39  |..:(...;..:p...9|
00001190  00 00 3a aa 00 00 05 56  00 00 3a aa 00 00 05 56  |..:....V..:....V|
*
00001200
[root@localhost xfsprogs]# 

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


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

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

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