论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2012-02-11 19:58 |只看该作者 |倒序浏览

本帖最后由 splendid12 于 2012-02-11 21:37 编辑

接上部分。。
原文在我的博客
http://lizeaaaa.blog.163.com
《ext2 / ext3 结构分析  》
-------------------------------------------------------------------------

Other 1. Directory Structure
下面我们来看看 inode 2 中所指向的 block 中的信息：

inode 2
0000080: ed41 0000 0004 0000 b1ae 354f 65b5 344f  .A........5Oe.4O
0000090: 65b5 344f 0000 0000 0000 0400 0200 0000  e.4O............
00000a0: 0000 0000 0000 0000 0001 0000 0000 0000  ................
00000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

# dd if=/dev/sda1 count=1 bs=1024 skip=256 | xxd | less
（这个 100H 是 data block 所在的第一个block）
0000000: 0200 0000 0c00 0102 2e00 0000 0200 0000  ................
0000010: 0c00 0202 2e2e 0000 0b00 0000 1400 0a02  ................
0000020: 6c6f 7374 2b66 6f75 6e64 0000 b10f 0000  lost+found......
0000030: 0c00 0402 6772 7562 0d00 0000 1800 0a01  ....grub........
0000040: 6d65 7373 6167 652e 6a61 3235 3262 3031  message.ja252b01
0000050: 0c00 0000 1000 0701 6d65 7373 6167 6500  ........message.
0000060: 1200 0000 1800 0f01 636f 6e66 6967 2d32  ........config-2
0000070: 2e34 2e32 302d 3831 0e00 0000 1000 0601  .4.20-81........
0000080: 626f 6f74 2e62 0000 0f00 0000 1000 0701  boot.b..........
0000090: 6368 6169 6e2e 6200 1000 0000 1000 0701  chain.b.........
00000a0: 6f73 325f 642e 6200 1300 0000 2400 1401  os2_d.b.....$...
00000b0: 6d6f 6475 6c65 2d69 6e66 6f2d 322e 342e  module-info-2.4.
00000c0: 3230 2d38 3262 3031 3262 3031 1100 0000  20-82b012b01....
00000d0: 1c00 1301 5379 7374 656d 2e6d 6170 2d32  ....System.map-2
00000e0: 2e34 2e32 302d 3800 1600 0000 1000 0707  .4.20-8.........
00000f0: 766d 6c69 6e75 7a2d 1700 0000 1400 0a07  vmlinuz-........
0000100: 5379 7374 656d 2e6d 6170 6230 1400 0000  System.mapb0....
0000110: 1800 1001 766d 6c69 6e75 782d 322e 342e  ....vmlinux-2.4.
0000120: 3230 2d38 1500 0000 1800 1001 766d 6c69  20-8........vmli
0000130: 6e75 7a2d 322e 342e 3230 2d38 1800 0000  nuz-2.4.20-8....
0000140: 1400 0b07 6d6f 6475 6c65 2d69 6e66 6f00  ....module-info.
0000150: 1900 0000 1000 0801 6b65 726e 656c 2e68  ........kernel.h
0000160: 1a00 0000 1c00 1301 696e 6974 7264 2d32  ........initrd-2
0000170: 2e34 2e32 302d 382e 696d 6700 1b00 0000  .4.20-8.img.....
0000180: 8402 0101 3100 0000 0000 0000 0000 0000  ....1...........
all 0s
00003f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
右边的是 ascii 的翻译，总算看到了点文字啊。

# df
文件系统             1K-块       已用    可用已用% 挂载点
/dev/sda2          13322104 1860548  10784820  15% /
/dev/sda1             93309    9427    79065  11% /boot
none                   127632       0 127632 0% /dev/shm

可以看到那些 acsii 刚好就是 /boot 下的文件，而 /boot 就是 /dev/sda1 的根目录

对于一个目录，在 data block 中存放的格式为：
struct ext3_dir_entry_2 {
__u32 inode; /* Inode 号数 */
__u16 rec_len;  /* Directory entry length */
__u8  name_len; /* Name length */
__u8  file_type;  char  name[EXT3_NAME_LEN]; /* File name */
};
这是一个变长的格式，长度由 rec_len 指定。

0.
我们来分析这些的 16进制数：
0000000: 0200 0000 0c00 0102 2e00 0000  0200 0000  ................
0000 0002  表示这个文件所连接到的 inode 号码，这个号码就是2，就是 /boot 的 inode
000c  表示这个结构体的长度，12。这个数值是 4字节的倍数，注意：如果有一个 ext3_dir_entry_2 存不下了，它不会被截断，而是往下一个 block 存
01  表示表示 name 有多少字节。
02  表示是一个目录。文件类型看下表：

2e00 0000 就是文件名了，字符串是不按照小端格式翻过来的，也就是 . \0 \0 \0，后面的 \0 是填充到 4B 倍数。

1.
查看内容
0000000: 0200 0000 0c00 0102 2e00 0000 0200 0000  ................
0000010: 0c00 0202 2e2e 0000 0b00 0000 1400 0a02  ................
0000 0002  inode 号码
00c0  12B
02  name is 2B
02  是个目录
2e2e 0000  目录名 ..
可以看出，根目录下的 2 个目录 . 和 .. 都指向相同的 inode 2

                                             0b00 0000 1400 0a02  ................
0000020: 6c6f 7374 2b66 6f75 6e64 0000 b10f 0000  lost+found......
0000030: 0c00 0402 6772 7562 0d00 0000 1800 0a01  ....grub........
0000040: 6d65 7373 6167 652e 6a61 3235 3262 3031  message.ja252b01
0000050: 0c00 0000 1000 0701 6d65 7373 6167 6500  ........message.
0000060: 1200 0000 1800 0f01 636f 6e66 6967 2d32  ........config-2
0000070: 2e34 2e32 302d 3831 0e00 0000 1000 0601  .4.20-81........
0000080: 626f 6f74 2e62 0000 0f00 0000 1000 0701  boot.b..........
0000090: 6368 6169 6e2e 6200 1000 0000 1000 0701  chain.b.........
00000a0: 6f73 325f 642e 6200 1300 0000 2400 1401  os2_d.b.....$...
00000b0: 6d6f 6475 6c65 2d69 6e66 6f2d 322e 342e  module-info-2.4.
00000c0: 3230 2d38 3262 3031 3262 3031 1100 0000  20-82b012b01....
00000d0: 1c00 1301 5379 7374 656d 2e6d 6170 2d32  ....System.map-2
00000e0: 2e34 2e32 302d 3800 1600 0000 1000 0707  .4.20-8.........
00000f0: 766d 6c69 6e75 7a2d 1700 0000 1400 0a07  vmlinuz-........
0000100: 5379 7374 656d 2e6d 6170 6230 1400 0000  System.mapb0....
0000110: 1800 1001 766d 6c69 6e75 782d 322e 342e  ....vmlinux-2.4.
0000120: 3230 2d38 1500 0000 1800 1001 766d 6c69  20-8........vmli
0000130: 6e75 7a2d 322e 342e 3230 2d38 1800 0000  nuz-2.4.20-8....
0000140: 1400 0b07 6d6f 6475 6c65 2d69 6e66 6f00  ....module-info.
0000150: 1900 0000 1000 08 01 6b65 726e 656c 2e68  ........kernel.h
.....

2.
再举一例
下面我们分析一个一般的文件而不是文件夹：
0000150: 1900 0000 1000 08 01 6b65 726e 656c 2e68  ........kernel.h
1900 0000，19H，25，inode 25
1000，10H，16，结构体 16 字节
08，name 8 B
01，Regular File，一般文件
6b65 726e 656c 2e68，kernel.h

3.
进入一个 inode 中
我们已经看到上面的 inode 25，所以只要进入 inode 25，查看其 block 号码，就能找到文件了
我们要进入 inode 25，就要算出来 inode 25 在那个 block 中：
/dev/sda1 按照顺序排：
1024 B ，什么也不做，为了可移植
1 个 Super block，占用 1 block_size
1 个 Desc table，占用 1 block_size
1 个 Block bitmap，占用 1 block_size
1 个 Inode birmap，占用 1 block_size
接下来就是 n 个 block_size 的 Inode table，一个 block 中能能存放 numOfIno = block_size / 128B 个 inode
inode 25 所在 block 号码 = 1024B / 1024B + 4 + 25/8 + 1 = 9
在该block 中的 offset：128B * （1-1） = 0 B

我们 dd 一下
# dd if=/dev/sda1 count=1 bs=1024 skip=8 | xxd | less
# #因为 inode 25 在 block 9，所以跳过 8 个 1024字节
0000000: a481 0000 d901 0000 3ed1 354f 5a2b 254f  ........>.5OZ+%O
0000010: 5a2b 254f 0000 0000 0000 0100 0200 0000  Z+%O............
0000020: 0000 0000 0000 0000 1c25 0000 0000 0000  .........%......
0000030: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000040: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000050: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000060: 0000 0000 aa04 7138 0000 0000 0000 0000  ......q8........
0000070: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0000080: a481 0000 d6e0 0300 5c2b 254f 5c2b 254f  ........\+%O\+%O
.......
00003f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

我们只关心 offset = 0 处，然后往下数 128 字节，用红色标记，
看到 inode 25 只使用了 251c 这 1 个 1级block指向。

我们打开，inode 25：
# dd if=/dev/sda1 count=1 bs=1024 skip=9500 | xxd | less

0000000: 2f2a 2054 6869 7320 6669 6c65 2069 7320  /* This file is
0000010: 6175 746f 6d61 7469 6361 6c6c 7920 6765  automatically ge
0000020: 6e65 7261 7465 6420 6174 2062 6f6f 7420  nerated at boot
.......
00001c0: 524e 454c 5f55 5020 310a 2365 6e64 6966  RNEL_UP 1.#endif
00001d0: 0a0a 2365 6e64 6966 0a00 0000 0000 0000  ..#endif........
00001e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
all 0s
00003f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
全部都是 C 语言，因为那是一个 kernel.h 文件嘛！

4.
我们看到，inode 25 所指向的 block 9500 没有用完，里面还有很多 0 的空间
这就是内部碎片，是所有文件系统都无法避免的。

5.
一个总结
这说明了，对于一个文件inode，其所指向的 block 中直接存放数据
而对于一个目录inode，其所指向的 block 实际上存放的一个 ext3_dir_entry_2 的结构体数组，这个数组中存放了文件名了其指向的 Inode。
再次说明，文件名是包含在 ext3_dir_entry_2 结构体中的。

至此，我们从从文件系统一直追更溯源到一个文件。

显然，文章里面罗列的都是数据结构，算法能把这个结构体真正地“活”起来，
虽然明白了 ext2/ext3 的基本结构，但是组织这些数据结构的算法的学习，仍然是任重道远啊。

参考资料
1）http://blog.chinaunix.net/link.p ... ilesystem%2Fext2%2F
2）The Second Extended File System: Internal Layout. Dave Poirier