第十一章
本章描述了EXT2文件系统在Linux中的历史地位以及EXT3/EXT4文件系统的当前状况；用编程示例展示了各种EXT2数据结构以及如何遍历EXT2文件系统树；介绍了如何实现支持Linux内核中所有文件操作的EXT2文件系统；展示了如何通过虚拟磁盘的mount root来构建基本文件系统；将文件系统的实现划分为3个级别，级别1扩展了基本文件系统，以实现文件系统树，级别2实现了文件内容的读/写操作，级别3实现了文件系统的挂载/装载和文件保护；描述了各个级别文件系统函数的算法。
什么是EXT2文件系统
EXT2第二代扩展文件系统second extended filesystem，缩写为ext2，是LINUX内核所用的文件系统。它开始由Rémy Card设计，用以代替ext，于1993年1月加入linux核心支持之中。ext2 的经典实现为LINUX内核中的ext2fs文件系统驱动，最大可支持2TB的文件系统，至linux核心2.6版时，扩展到可支持32TB。其他的实现包括GNU Hurd，Mac OS X ，Darwin ，BSD。ext2为数个LINUX发行版的默认文件系统，如Debian、Red Hat Linux等。
其单一文件大小与文件系统本身的容量上限与文件系统本身的簇大小有关，在一般常见的 x86 电脑系统中，簇最大为 4KB, 则单一文件大小上限为 2048GB, 而文件系统的容量上限为 16384GB。
但由于目前核心 2.4 所能使用的单一分割区最大只有 2048GB，实际上能使用的文件系统容量最多也只有 2048GB。
至于Ext3文件系统，它属于一种日志文件系统，是对ext2系统的扩展。它兼容ext2，并且从ext2转换成ext3并不复杂。
11.2 EXT2文件系统数据结构
1.通过mkfs创建虚拟磁盘
在 Linux下，命令
mke2fs [-b blksize -N ninodes] device nblocks
在设备上创建一个带有nblocks个块（每个块大小为blksize字节）和 ninodes 个索引节点的EXT2文件系统。设备可以是真实设备，也可以是虚拟磁盘文件。如果未指定blksize.则默认块大小为1KB。如果未指定ninoides，mke2fs将根据 nblocks计算一个默认的ninodes数。得到的 EXT2文件系统可在 Linux 中使用。举个具体的例子，下面的命令
dd if=/dev/zero of=vdisk bs=1024 count=1440
mke2fs vdisk 1440
可在一个名为vdisk的虚拟磁盘文件上创建一个EXT2文件系统，有1440个大小为1KB 的块。
2.Block#0：引导块 B0是引导块，文件系统不会使用它。它用来容纳一个引导程序，从磁盘引导操作系统。
3.Block#1：超级块（在硬盘分区中字节偏移量为1024） B1是超级块，用于容纳整个文件系统的信息。
struct ext2_guper_block {
u32 s_inodes_count; /* Inodes count */
u32 s_blocks_count; /* Blocks count*/
u32 s_r_blocks_count; /* Reserved blocks count */
u32 s_free_blocks_count; / * Free blocks count */
u32 s_free_inodes_count; /* Free inodes count */
u32 s_first__data_blook; /* First Data Block */
u32 s_log_block_size; /* Block size */
u32 s_log_cluster_size; /* Allocation cluster size */
u32 s_blocks_per_group; /* # Blocks per group*/
u32 s_clusters_per_group; /*# Fragments per group */
u32 s_inodes_per_group; /* # Inodes per group*/
u32 s_mtime;u32 s_wtime; /* Mount time */
u16 s_mnt_count; /* Write time */
s16 s_max_mnt_count; /_Mount_count/L
u16 8_magic; /* Magic signature */
// more non-essential fields
u16 s_inode_size; /* size of inode structure*/
}
4.Block#2∶块组描述符块（硬盘上的s first data block+1）EXT2将磁盘块分成几个组。每个组有8192个块（硬盘上的大小为32K）。每组用一个块组描述符结构体来描述。
struct ext2_group_desc {
u32 bg_block_bitmap; // Bmap block number
u32 bg_inode_bitmap; // Imap block number
u32 bg_inode_table; // Inodes begin block number
u16 bg_free_blocks_count; // THESE are OBVIOUS
u16 bg_free_inodes_count;
ul6 bg_used_dirs_count;
u16 bg_pad; // ignore these
u32 bg_reserved[3];
}；
5.Block#8∶块位图（Bmap）（bg block bitmap）位图是用来表示某种项的位序列，例如磁盘块或索引节点。位图用于分配和回收项。在位图中，0位表示对应项处于FREE状态，1位表示对应项处于IN USE状态。一个软盘有1440个块，但是 Block#0未被文件系统使用。所以，位图只有1439个有效位。无效位被视作INUSE，设置为1。
Block#9∶索引节点位图（Imap）（bg inode bitmap）一个索引节点就是用来代表一个文件的数据结构。EXT2文件系统是使用有限数量的索引节点创建的。各索引节点的状态用B9的Imap 中的一个位表示。在EXT2 FS中，前10个索引节点是预留的。所以，空 EXT2 FS的Imap 以10个1开头，然后是0。无效位再次设置为1。
6.Block#10∶索引（开始）节点（bg inode table）每个文件都用一个128字节（EXT4中是256字节）的唯一索引节点结构体表示。
struct ext2_inode {
u16 i_mode; // 16 bits=|tttt |ugs|rwx|rwx|rwxl
ul6 i_uid; // owner uid
u32 i_size; // file size in bytes
u32 i_atime; // time fields in seconds
u32 1_ctime; // since 00:00:00,1-1-1970
u32 i_mtime;
u32 i_dtime;
i_gid; // group ID u16
u16 i_links_count; // hard-link count
u32 i_blocks;u32 i_flags; // number of 512-byte sectors
u32 i_reservedl; // IGNORE // IGNORE
u32 i_block[15]; // See details below
u32 i_pad[7]; // for inode size = 128 bytes
}
直接块: block[0]至iblock[11]，指向直接磁盘块。
间接块:iblock[12]指向一个包含256个块编号（对于1KB BLKSIZE）的磁盘块，每个块编号指向一个磁盘块。
双重间接块:i block[13]指向一个指向 256个块的块，每个块指向256个磁盘块。
三重间接块:iblock[14]是三重间接块。对于"小型"EXT2文件系统，可以忽略它。
7.数据块
紧跟在索引节点块后面的是文件存储数据块。
8.目录条目
struct ext2_dir_entry_2{
u32 inode; // inode number; count from 1,NOT 0
u16 rec_len; // this entry's length in bytes
u8 name_len; // name length in bytes
u8 file_type; // not used
char name[EXT2_NAME_LEN]; // name:1-255 chars,no ending NULL ;
}；
目录包含dir_entry 结构，dir_entry 是一种可扩充结构。名称字段包含1到255个字符，不含终止NULL。所以dir entry 的 rec len也各不相同。
邮差算法
邮差算法：在计算机系统中， 经常出现下面这个问题。 一个城市有M 个街区， 编号从 0到M-1。 每个街区有N座房子， 编号从0 到 N-1。每座房子有一个唯一的街区地址， 用（街区， 房子）表示， 其中0<=街区<M, 0<=房子<N。 来自外太空的外星人可能不熟悉地球上的街区寻址方案， 倾向于采用线性方法将这些房子地址编为 0, 1, ···, N-1, N, N+1 等。 已知某个街区地址 BA= （街区， 房子）， 怎么把它转换为线性地址 LA, 反过来，已知线性地址，怎么把它转换为街区地址？如果都从0开始计数，转换就会非常简单。
标签：count,bg,EXT2,第十一章,文件系统,笔记,学习,u32,block From： https://www.cnblogs.com/luoyunfan/p/16728643.html