Linux Kernel: Ext2

super block 和 group descriptors 在每个 group 都有一个, 但平时只有 group 0 的 super block 会被使用, 其它 group 的都是备份, 和 fsck 有关

super block 的主要成员:

1. s_inodes_count

   文件系统能容纳的最大的 inode 个数

2. s_block_count

   文件系统的大小

3. s_r_blocks_count

   reserved 的 block 数目

4. s_groups_count

   group 数目

5. s_free_inodes_count

   可用的 inode 数, s_free_inodes_count/s_groups_count 可计算出每个 group 平均的 inode 数, 后续创建 inode 时会根据这个值选择相应的 group

6. s_free_blocks_count

   可用的 block 数

7. s_log_block_size

   block 大小

8. s_blocks_per_group

   每个 group 的 block 数

9. s_inodes_per_group

   每个 group 的 inode 数

10. s_mtime/s_wtime

    最近的 mount 时间和修改时间

11. s_mnt_count

    mount 次数

12. s_def_resuid/s_def_resgid

    可用使用 reserved block 的 uid/gid

13. s_last_mounted

    最近一次被挂载到哪

super block 的这些成员大多是运行时的统计信息, 但有一些是需要用户通过 mkfs 或 tune2fs 指定的:

1. s_r_blocks_count

   默认的 reserved block 数目是 s_block_count 的 5%

2. s_log_block_size

   block 大小默认为 1024B

3. s_blocks_per_group

   大小和 block 大小有关: 因为一个 group 只用一个 block 来保存 block bitmap, 所以对于 1024B 的 block 来说, block bitmap 最多只能表示 1024*8*1024=8MB 的大小, 即 1024*8 = 8192 个 block

4. s_inodes_per_group

   和磁盘大小有关, 默认情况下, 每个 inode 需要至少 8KB, 所以假设 block size 为 1K, 若磁盘大小为 256K, 则 inode 总数是 256/8 = 32, group 为 1, s_inodes_per_group 为 32.

5. s_def_resuid/s_def_resgid

group descriptors 是一系列的 group descriptor 的集合, 占用多个 block, 每个 group descriptor 的成员包括:

1. bg_block_bitmap

   block bitmap 对应的 block number

2. bg_inode_bitmap

   inode bitamp 对应的 block number

3. bg_inode_table

   inode table 起始 block 对应的 block number, 因为有 s_inodes_per_group, 所以这里不需要记录 inode table 的大小

4. …

block bitmap 占用一个 block, 记录的是 group 所有 data block 是否已经分配, 这个 block 的大小决定了每个 group 能容纳多少 data block.

占用一个 block, 记录 group 的某个 inode 是否已经被使用.

占用多个 block, 这个 table 中每一项都是一个 128B 的 inode 结构, 所以 inode table 占用的 block 数 = (128 / s_log_block_size ) * s_inodes_per_group

由于每个 group 的 inode table 大小都是相同的, 所以 Ext2 的 inode number 是这样实现的: 对 group x 的 inode table 中的第 y 个 inode, 其 inode number 为: x * s_inodes_per_group + y, 反之, 根据 inode number 可以很快找到对应的 group 和 inode table 中对应的 inode

创建 inode 的过程主要是需要分配一个 inode number, 或者说找到一个合适的 group, 并且在这个 group 的 inode table 中找到某一个 entry.

大约的函数调用为:

ext2_new_inode:
  inode = new_inode(sb);
  // 找一个合适的 group
  if (S_ISDIR(mode)):
    group = find_group_orlov(sb, dir);
  else:
    group = find_group_other(sb, dir);
  bitmap_bh = read_inode_bitmap(sb, group);
  // 通过 inode bitmap 找一个可用的 inode table entry
  ino = ext2_find_next_zero_bit((unsigned long *)bitmap_bh->b_data, EXT2_INODES_PER_GROUP(sb), ino);
  ext2_set_bit_atomic(sb_bgl_lock(sbi, group),ino, bitmap_bh->b_data)
  mark_buffer_dirty(bitmap_bh);
  // 计算 inode number
  ino += group * EXT2_INODES_PER_GROUP(sb) + 1;
  inode->i_ino = ino;
  inode->i_uid = current->fsuid;
  inode->i_mode = mode;
  inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME_SEC;
  // ...
  return inode

创建 inode 最主要的过程是查找一个`合适`的 group (find_group_xxx), 该过程使用如下的 heuristic:

1. 若新建的 inode 对应一个目录:
   1. 若 parent 是 root inode, 则 inode 会尽量平均分布在各个 group: 选择 free inode 和 free block 大于平均值的 group
   2. 对于 parent 不是 root 的 inode, 会尽量选择 parent inode 所在的 group, 除非这个 group 有太多的目录或者 free inode 已经很少
   3. 做为 1 和 2 的 fallback, 如果 1 和 2 没有找到合适的 group, 则从 parent inode 所在的 group 开始, 找一个 free inode 大于平均值的 group

2. 若新建 inode 是一个文件:

   从 parent inode 所在的 group 开始 (假设为 i), 跳跃式的查找一个可用的 inode, 大约是这样跳的: i, i+1, i+1+2, i+1+2+4 …, 代码如下:

   for (i = 1; i < ngroups; i <<= 1) {
       group += i;
       if (group >= ngroups)
           group -= ngroups;
       desc = ext2_get_group_desc (sb, group, &bh);
       if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
           le16_to_cpu(desc->bg_free_blocks_count))
           goto found;
   }
   

   若上面的查找失败, 进行线性查找:

   group = parent_group;
   for (i = 0; i < ngroups; i++) {
       if (++group >= ngroups)
           group = 0;
       desc = ext2_get_group_desc (sb, group, &bh);
       // 这里并不需要 group 有 free block ..., 因为极有可能找不到这样的
       // group
       if (desc && le16_to_cpu(desc->bg_free_inodes_count))
           goto found;
   }
   
   

总的来说, find group 主要的逻辑是:

1. inode 尽量与 parent inode 位于同一个 group
2. inode 尽量的分散到不同的 group

ext2_free_inode 负责删除 inode 本身 (修改 inode bitmap), 至于 unlink 和 rmdir 相关的其它逻辑, 比如通过 link count 决定是否需要真正删除 inode, 修改 parent directory 的 dentry, 删除 inode 的 data block, 以及判断目录是否为空等由其它函数实现, ext2_free_inode 被调用时可以认为之前的动作已经完成.

ext2_free_inode:
  block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);
  bit = (ino - 1) % EXT2_INODES_PER_GROUP(sb);
  bitmap_bh = read_inode_bitmap(sb, block_group);
  ext2_clear_bit_atomic(sb_bgl_lock(EXT2_SB(sb), block_group),bit, (void *) bitmap_bh->b_data))
  ext2_release_inode(sb, block_group, is_directory);
    desc = ext2_get_group_desc(sb, group, &bh);
    desc->bg_free_inodes_count = cpu_to_le16(le16_to_cpu(desc->bg_free_inodes_count) + 1);
    if (dir):
      desc->bg_used_dirs_count = cpu_to_le16(le16_to_cpu(desc->bg_used_dirs_count) - 1);
    mark_buffer_dirty(bh);
  mark_buffer_dirty(bitmap_bh);

unlink 调用 ext2_free_inode 的逻辑为:

sys_unlink:
  path_lookup(name, LOOKUP_PARENT, &nd);
  vfs_unlink(nd.dentry->d_inode, dentry);
    ext2_unlink ()
      ext2_delete_entry (de, page);
      ext2_dec_count(inode);
  iput(inode);  /* truncate the inode here */
    iput_final(inode)
    generic_drop_inode(inode)
      if (!inode->i_nlink):
        generic_delete_inode(inode);
          ext2_delete_inode(inode)
            // ext2_truncate 释放 inode 的 data blocks (定位 inode 所
            // 有的 block 并修改 block bitmap)
            if (inode->i_blocks):
              ext2_truncate (inode);
            ext2_free_inode (inode);

#> dd if=/dev/zero of=hole bs=4096 count=1 seek=5

~@dell-work> sudo debugfs /dev/sda2
debugfs 1.42.13 (17-May-2015)
debugfs:  cd sunway
debugfs:  bmap hole 0
0
debugfs:  bmap hole 1
0
debugfs:  bmap hole 2
0
debugfs:  bmap hole 3
0
debugfs:  bmap hole 4
0
debugfs:  bmap hole 5
86016417

通过 chattr/lsattr 可以修改/查看文件的 attribute, 这里的 attribute 包括:

• S_IMMUTABLE, 文件不可更改, 删除, 改名等
• S_APPEND, 文件只能追加
• …

attribute 与 ext2 的 extended attribute 并没有关系, 它是 VFS 定义的 (inode->i_flags 保存了文件的 attribute), ext2 通过如下代码支持 attribute:

ext2 的目录的 data block 保存着一系列的 ext2_dir_entry_2:

struct ext2_dir_entry_2 {
    __le32      inode;                  /* Inode number */
    __le16      rec_len;                /* Directory entry length */
    __u8        name_len;               /* Name length */
    __u8        file_type;
    char        name[EXT2_NAME_LEN];    /* File name */
};

Ext2 支持 inode 扩展属性, 扩展属性并不像普通 inode 属性那样保存在 128B 的 inode table entry 中, 而是通过一个单独的 block 保存, ext2_inode_info->i_file_acl 指向这个 block, 从 i_file_acl 名字也能猜到 extended attribute 主要用来实现 ACL (例如 user1, user2 可以访问这个文件), 另外, selinux 也使用 extended attr 来保存 file context

从 fsync 代码可以看到 inode 对应的 data 部分 (address_space) 和 inode 部分 (实际对应于 inode table) 最终会通过 writepage 写到磁盘 (), 但 superblock, inode bitmap 以及 block bitmap 如何被写到磁盘?

从代码上猜测是通过 block device file:

sys_sync:
  sync_inodes(); /* All mappings, inodes and their blockdevs */
    while ((sb = get_super_to_sync()) != NULL):
      // sb 记录的所有 dirty inode 及其 mappings 被写回
      sync_inodes_sb(sb, 0);
      sync_blockdev(sb->s_bdev);
        // 由于文件系统内部对设备的读写都是通过 bd_inode 的 pagecache
        // (_bread), 所以 sync bd_inode 的 address_space 会导致文件系统
        // 内部的这样修改(包括对 bitmap 的修改)被写回
        filemap_fdatawrite(bdev->bd_inode->i_mapping);
  sync_supers(); /* Write the superblocks */
    // sync_supers 只是修改 superblock 并置相应 block 为 dirty,
    // 后续的 sync_inodes 会保证它被写回
  sync_inodes(); /* sync inodes again? */

新建的 ext2 文件系统占用的磁盘空间, 主要依赖于 groups 的个数和 inode 的个数.

以一个 128GB 的磁盘为例, 假设 ext2 block size 为 1KB

1. 一个 group 能索引的空间大小为 1K*8*1K = 8M, 则一共需要 128G/8M = 16384 个 group, 这些 group 的 block bitmap 和 inode bitmap 一共需要占用 16384 * 2K = 32MB
2. 默认配置下, 每 8 KB 分配一个 inode, 则一共 128G/8K = 16777216 个 inode, 每个 inode 占 128B, 一共需要 2G

可见, 占用空间的主要是 inode table, 不考虑 inode table 与 block size 的对齐的话, 比例大约是 128/8K = 1.6%, 这个比例和 ext2 的 block size 基本没关系, 和 mkfs.ext2 是指定的 bytes_per_inode 有关.