第十一章 EXT2文件系统
一.知识点归纳
（一）EXT2文件系统数据结构
1.通过 mkfs 创建虚拟磁盘
在 Linux 下，命令
mke2fs [-b blksize -N ninodes] device nblocks
在设备上创建一个带有 nblocks 个块（每个块大小为 blksize 字节）和 ninodes 个索引节点的 EXT2 文件系统。设备可以是真实设备，也可以是虚拟磁盘文件。如果未指定 blksize，则默认块大小为 1KB。如果未指定 ninodes，mke2fs 将根据 nblocks 计算一个默认的 ninodes 数。
例如：
dd if=/dev/zero of=vdisk bs=1024 count=1440
mke2fs vdisk 1440
可在一个名为 vdisk 的虚拟磁盘文件上创建一个 EXT2 文件系统，有 1440 个大小为 1KB 的块。
2.虚拟磁盘布局
- Block#0：引导块
- B0是引导块(Boot Block)，文件系统不会使用它。它用于容纳从磁盘引导操作系统的引导程序。
3.超级块
- Block#1：超级块
- 超级块(Super Block)描述整个分区的文件系统信息，如inode/block的大小、总量、使用量、剩余量，以及文件系统的格式与相关信息。超级块在每个块组的开头都有一份拷贝（第一个块组必须有，后面的块组可以没有）。
- 超级块记录的信息有：
- block 与 inode 的总量（分区内所有Block Group的block和inode总量）；
- 未使用与已使用的 inode / block 数量；
- block 与 inode 的大小 (block 为 1, 2, 4K，inode 为 128 bytes)；
- filesystem 的挂载时间、最近一次写入数据的时间、最近一次检验磁盘 (fsck) 的时间等文件系统的相关信息；
- 一个 valid bit 数值，若此文件系统已被挂载，则 valid bit 为 0 ，若未被挂载，则 valid bit 为 1 。
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：块组描述符块
- 块组描述符块(GD)由很多块组描述符组成，整个分区分成多个块组就对应有多少个块组描述符。
- 每个块组描述符存储一个块组的描述信息，如在这个块组中从哪里开始是inode Table，从哪里开始是Data Blocks，空闲的inode和数据块还有多少个等等。块组描述符在每个块组的开头都有一份拷贝。
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：块位图
- 块位图(Block Bitmap)用来描述整个块组中哪些块已用哪些块空闲。块位图本身占一个块，其中的每个bit代表本块组的一个block，这个bit为1代表该块已用，为0表示空闲可用。假设格式化时block大小为1KB，这样大小的一个块位图就可以表示1024*8个块的占用情况，因此一个块组最多可以有10248个块。
- Block#9：索引节点位图
- inode位图(inode Bitmap)和块位图类似，本身占一个块，其中每个bit表示一个inode是否空闲可用。 Inode bitmap的作用是记录block group中Inode区域的使用情况，Ext文件系统中一个block group中可以有16384个Inode，代表着这个Ext文件系统中一个block group最多可以描述16384个文件。
6.索引节点
- Block#10：索引（开始）节点块
- inode表(inode Table)由一个块组中的所有inode组成。一个文件除了数据需要存储之外，一些描述信息也需要存储，如文件类型，权限，文件大小，创建、修改、访问时间等，这些信息存在inode中而不是数据块中。inode表占多少个块在格式化时就要写入块组描述符中。 在Ext2/Ext3文件系统中，每个文件在磁盘上的位置都由文件系统block group中的一个Inode指针进行索引，Inode将会把具体的位置指向一些真正记录文件数据的block块，需要注意的是这些block可能和Inode同属于一个block group也可能分属于不同的block group。我们把文件系统上这些真实记录文件数据的block称为Data blocks。
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
}
7.目录条目
目录包含 dir_entry 结构，即
struct ext2_dir_entry_2(){
u32 inode;
u16 rec_len;
u8 name_len;
u8 file_type;
char name[EXT2_NAME_LEN];
};
dir_entry 是一种可扩充结构。名称包含 1 到 255 个字符，不含终止 NULL。所以 dir_entry 的 rec_len 也各不相同。
（二）邮差算法
邮差算法的意思是：一个城市有 M 个街区，编号从 0 到 M-1 ，每个街区又有 N 座房子，编号从 0 到 N-1。我们可以用 BA =（街区，房子）表示每一栋房子的位置，同时我们也可以使用线性方法将房子编为 0,1,...,N 等。如何进行线性地址 LA 与街区地址 BA 的相互转换？如果都从 0 开始计数，转换就会非常简单。
Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);
注意，只有都从 0 开始计数，转换才有效。如果有些条目不是从 0 开始计数的，则不能直接在转换公式中使用。为方便表述，我们将这种转换方法称为邮差算法。下面给出邮差算法的几种应用。
1.C语言中的 Test-Set-Clear 位
在标准C语言程序中，最小的可寻址单元是一个字符或字节。在一系列位组成的位图中，通常需要对位进行操作。考虑字符buf[1024]，它有1024个字节，用buf[i]表示，其中i=0,1,...，1023。它还有8192个位，编号为0，1，2，···，8191。
struct bits{
unsigned int bit0 : 1; // bit0 field is a single bit
unsigned int bit123 : 3; // bit123 field is a range of 3 bits
unsigned int otherbits :27; // other bits field has 27 bits
unsigned int bit31 : 1; // bit31 is the highest bit
}var;
2.将索引节点号转换为磁盘上的索引节点
在 EXT2文件系统中，每个文件都有一个唯一的索引节点结构。在文件系统磁盘上，索引节点从inode table块开始。每个磁盘块包含
INODES_PER_BLOCK = BLoCK_SIZE/sizeof（INODE）
个索引节点。每个索引节点都有一个唯一的索引节点号，ino=1，2，…，从1开始线性计数。已知一个ino，如1234，那么哪个磁盘块包含该索引节点，以及哪个索引节点在该块中呢?我们需要知道磁盘块号，因为需要通过块来读/写一个真正的磁盘。
blcok = (info - 1) * INODES_PER_BLCOK + inode_table;
inode = (info - 1) % INODES_PER_BLCOK
(三)编程示例
1.显示超级块
以下C程序显示了EXT2文件系统的超级块。基本方法如下。
(1) 打开虚拟磁盘读取：int fd =open(“vidsk”.O_RDONLY)。
(2) 将超级块（Block#1或1KB的1024偏移量位置）读入char buf[1024]中。
(3) 让 ext2_super_block *sp 结构体指向buf[]。然后，利用 sp->field 访问超级块结构体的各个字段。
2.显示位图
3.显示根索引节点
4.显示目录条目
（四）遍历 EXT2 文件系统树
1.遍历算法
（1）读取超级块。检查幻数 s_magic（0xEF53），验证它确实是 EXT2 FS。
（2）读取块组描述符块（1 + s_first_data_block），以访问组0描述符。从块组描述符的bg_inode_table条目中找到索引节点的起始块编号，并将其称为 InodesBeginBlock。
（3）读取 InodeBeginBlock，获取/的索引节点，即 INODE#2。
（4）将路径名标记为组件字符串，假设组件数量为n。例如，如果路径名 =/a/b/c，则组件字符串是"a""b""c"，其中n=3。用name[0]，name[1]，…，name[n-1]来表示组件。
（5）从（3）中的根索引节点开始，在其数据块中搜索 name[0]。为简单起见，我们可以假设某个目录中的条目数量很少，因此一个目录索引节点只有12个直接数据块。有了这个假设，就可以在12个（非零）直接块中搜索 name[0]。目录索引节点的每个数据块都包含以下形式的 dir_entry 结构体;
[ino rec_len name_len NAME] [ino rec_len name_len NAME]....
其中 NAME 是一系列 nlen 字符，不含终止 NULL。对于每个数据块，将该块读入内存并使用 dir_entry *dp 指向加载的数据块。然后使用 name_len将 NAME 提取为字符串，并与 name[0] 进行比较。如果它们不匹配，则通过以下代码转到下一个 dir_entry:
dp =(dir_entry*)((char *)dp + dp->rec_len);
继续搜索。如果存在 name[0]，则可以找到它的 dir_entry，从而找到它的索引节点号。
（6）使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino 从1开始计数。使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。
blk =(ino - 1) / INODE8_PER_BLOCK + InodesBeginBlock;
offset = (ino - 1) % INODES_PER_BLOCK;
然后在索引节点中读取/a，从中确定它是否是一个目录（DIR）。如果/a不是目录，则不能有/a/b，因此搜索失败。如果它是目录，并且有更多需要搜索的组件，那么继续搜索下一个组件 name[1]。现在的问题是∶在索引节点中搜索/a的 name[1]，与第（5）步完全相同。
（7）由于（5）～（6）步将会重复n次，所以最好编写一个搜索函数∶
u32 search (INODE *inodePtr, char *name)
{
// search for name in the data blocks of current DIR inode
// if found, return its ino; else return 0 )
}
然后我们只需调用 search()n次，如下所示。
Assume:n,name[0],....,name[n-1] are globals
INODE *ip points at INODE of /
for（i=0; i<n; i++）
{
ino = search(ip, name[4])
if(!ino){ // can't find name[i], exit;}
use ino to zead in INODE and let ip point to INODE
}
如果搜索循环成功结束，ip必须指向路径名的索引节点。遍历有多个组的大型 EXT2/3 文件系统也是类似操作。
4.将路径名转换为索引节点
5.显示索引节点磁盘块
（五）EXT2 文件系统的实现
1.文件系统的结构
（1）当前运行进程的PROC结构体；
（2）文件系统的根指针；
（3）一个openTable条目；
（4）内存索引节点；
（5）已挂载的文件系统表。
2.文件系统的级别
第1级别实现了基本文件系统树，以实现指定函数，第2级别实现了文件内容的读/写函数，第3级别实现了文件系统的挂载、卸载和文件保护。
（六）基本文件系统
1.type.h 文件
这类文件包含EXT2文件系统的数据结构类型，比如超块、组描述符、索引节点和目录条目结构。此外，它还包含打开文件表、挂载表、PROC结构体和文件系统常数。
2.global.c 文件
这类文件包含文件系统的全局变量。全局变量的例子有：
MINODE minode [NMINODE]; // in memory INODEs
MTABLE mtable [NMTABLE]; // mount tables
OFT oft [NOFT]; // Opened file instance
PROC proc[NPROC]PROC ] // PROC structures
PROC *running; // current executing
3.实用程序函数
（1）get_block/put_block 函数
（2）iget(dev, ino) 函数
（3）The iput（INODE *mip） 函数
（4）getino（） 函数
（5）getino（）/iget（）/iput（）的使用
4.mount-root
- 如何执行ls
5.基本文件系统的实现
（七）文件系统的级别
文件系统的实现分为三个级别。每个级别处理文件系统的不同部分。这使得实现过程模块化，更容易理解。在文件系统的实现过程中，FS目录包含实现EXT2文件系统的文件。
1. 1级文件系统函数及其原理
- 1级文件系统函数的功能是文件和路径、创建和删除等较为直接和底层的相关的操作。
mkdir：mkdir创建一个带路径名的新目录。同时将目录的权限设置为 0755 ，即 rwxr_xr_x ，所有人可以访问和读写，其他人可以访问但是只能读取。
creat：creat创建一个空的普通文件。
rmdir：删除一个路径。
link：链接文件。
unlink:解除链接文件。
2. 2级文件系统函数及其原理
- 2级文件系统函数的功能常常是打开、读取文件、写入文件等对文件进行的操作。
open：打开文件。
lseek：将打开的文件描述符在OFT中的偏移量从文件开头或当前位置开始的字节位置。
close：关闭文件描述符。
3. 3级文件系统函数及其原理
- 3级文件系统函数进行文件系统的挂载、卸载和文件保护等。
mount:挂载。使用方法：
mount filesys mount_point
卸载：卸载已经挂载的文件系统。
二.问题与解决思路
1.ext2 头文件的下载：
发现缺少必要的头文件 ext2fs/ext2_fs.h ，同时，书上给出的方法是使用 sudo apt-get install ext2fs-dev 进行安装，但发现报包不存在错误。
# 用以下命令解决
sudo apt-get install libext2fs-dev
- 若为 openEuler 系统，可能自带 ext2fs（若无，就通过共享文件夹传输一下吧，下载不了）
三.实践内容与截图
1.显示超级块
/*********** superblock.c program ************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/io.h>
#include <ext2fs/ext2_fs.h>
// Cypedef u8, ul6, u32 SUPER for convenience typedef typedef typedef
typedef unsigned char u8;
typedef unsigned short ul6;
typedef unsigned int u32;
typedef struct ext2_super_block SUPER;
SUPER *sp;
char buf[1024];
int fd, blksize, inodesize;
int print(char *s, u32 x)
{
printf("%-30s = %8d\n", s, x);
}
int super(char *device)
{
fd = open(device, O_RDONLY);
if (fd < 0)
{
printf("open %s failed\n", device);
exit(1);
}
lseek(fd, (long)1024*1, 0); // block 1 or offset 1024
read(fd, buf, 1024);
sp = (SUPER *)buf; // as a super block structure
// check for EXT2 FS magic number
printf("%-30s = %8x ", "s_magic", sp->s_magic);
if (sp->s_magic != 0xEF53)
{
printf("NOT an EXT2 FS\n"); exit(2);
}
printf("EXT2 FS OK\n");
print("s_inodes_count", sp->s_inodes_count);
print("s_blocks _count", sp->s_blocks_count);
print("s_r_blocks_count", sp->s_r_blocks_count);
print("s_free_inodes_count", sp->s_free_inodes_count);
print("s_free_blocks_count", sp->s_free_blocks_count);
print("s_first_data_blcok", sp->s_first_data_block);
print("s_log_block_s i z e", sp->s_log_block_size);
print("s_blocks_per_group", sp->s_blocks_per_group);
print("s_inodes_per_group", sp-> s_inodes_per_group);
print("s_mnt_count", sp->s_mnt_count);
print("s_max_mnt_count", sp-> s_max_mnt_count);
printf("%-30s = %8x\n", "s_magic", sp->s_magic);
printf ("s_mtime = %s\n", ctime ((const time_t *)&sp->s_mtime));
printf ("s_wtime = %s", ctime ((const time_t *)&sp->s_wtime));
blksize = 1024 * (1 << sp->s_log_block_size);
printf("block size = %d\n", blksize);
printf("inode size = %d\n", sp->s_inode_size);
}
char *device = "vdisk"; // default device name
int main(int argc, char *argv[])
{
if (argc>1)
device = argv[1];
super(device);
}
2.显示位图
/*** imap program **************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/io.h>
#include <ext2fs/ext2_fs.h>
typedef unsigned char u8;
typedef struct ext2_super_block SUPER;
typedef struct ext2_group_desc GD;
#define BLKSIZE 1024
SUPER *sp;
GD *gp;
char buf[BLKSIZE];
int fd;
// get_block() reads a disk block into a buf[]?
int get_block(int fd, int blk, char *buf)
{
lseek(fd, (long)blk*BLKSIZE, SEEK_SET);
return read(fd, buf, BLKSIZE);
}
int imap(char *device)
{
int i, ninodes, blksize, imapblk;
fd = open(device, O_RDONLY);
if (fd < 0)
{
printf("open %s failed\n", device);
exit(1);
}
get_block(fd, 1, buf); // get superblock
sp = (SUPER *)buf;
// check magic number to ensure itz s an EXT2 FS ninodes = sp->s_inodes_count //
ninodes = sp->s_inodes_count;
printf("ninodes = %d\n", ninodes);
get_block(fd, 2, buf); //
gp = (GD *)buf;
imapblk = gp->bg_inode_bitmap;
printf("imapblk = %d\n", imapblk);
get_block(fd, imapblk, buf);
for ( i = 0; i <= ninodes/8; i++)
{
printf("%02x ", (u8)buf[i]);
}
printf("\n");
}
char *dev = "vdisk";
int main(int argc, char*argv[])
{
if(argc>1) dev = argv[1];
imap(dev);
}
3.显示根索引节点
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/io.h>
#include <ext2fs/ext2_fs.h>
#define BLKSIZE 1024
typedef struct ext2_group_desc GD;
typedef struct ext2_super_block SUPER;
typedef struct ext2_dir_entry_2 DIR;
typedef struct ext2_inode INODE;
SUPER *sp;
GD *gp;
INODE *ip;
DIR *dp;
char buf[BLKSIZE];
int fd,firstdata, inodesize ,blksize, iblock;
char *dev = "vdisk";
int get_block(int fd, int blk, char *buf)
{
lseek(fd, blk*BLKSIZE, SEEK_SET);
return read(fd, buf, BLKSIZE);
}
int inode (char *dev)
{
int i;
fd = open(dev, O_RDONLY);
if(fd < 0)
{
printf("open faild\n");
exit(1);
}
get_block(fd, 2, buf);
gp = (GD *)buf;
printf("bmap_block=%d imap_block=%d inodes_table=%d \n",
gp->bg_block_bitmap,
gp->bg_inode_bitmap,
gp->bg_inode_table);
iblock = gp->bg_inode_table;
printf("----root inode information----\n");
get_block(fd, iblock, buf);
ip = (INODE *)buf;
ip++;
printf("mode = %4x ",ip->i_mode);
printf("uid = %d gid = %d\n", ip->i_uid, ip->i_gid);
printf("size = %d\n", ip->i_size);
//unsigned int tmp = ip->i_ctime;
printf("ctime = %s",ctime((const time_t *)&ip->i_ctime));
printf("links = %d\n", ip->i_links_count);
for ( i = 0; i < 15; i++)
{
if(ip->i_block[i])
{
printf("i_block[%d] = %d\n", i, ip->i_block[i]);
}
}
}
int main(int argc, char *argv[])
{
if(argc>1) dev = argv[1];
inode(dev);
}
4.实现 ls -l 命令
#include <stdio.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <pwd.h>
#include <grp.h>
#include <time.h>
#include <string.h>
int main(int argc,char * argv[]){
if(argc<2){
printf("%s need filename\n",argv[0]);
return -1;
}
struct stat st;
int ret=stat(argv[1],&st);
if(ret==-1){
perror("stat");
return -1;
}
char perms[11]={0};
switch (st.st_mode & S_IFMT){
case S_IFLNK:
perms[0]='l';
break;
case S_IFDIR:
perms[0]='d';
break;
case S_IFREG:
perms[0]='-';
break;
case S_IFBLK:
perms[0]='b';
break;
case S_IFCHR:
perms[0]='c';
break;
case S_IFSOCK:
perms[0]='s';
break;
case S_IFIFO:
perms[0]='p';
break;
default:
perms[0]='?';
break;
}
perms[1]=(st.st_mode & S_IRUSR) ? 'r':'-';
perms[2]=(st.st_mode & S_IWUSR) ? 'w':'-';
perms[3]=(st.st_mode & S_IXUSR) ? 'x':'-';
perms[4]=(st.st_mode & S_IRGRP) ? 'r':'-';
perms[5]=(st.st_mode & S_IWGRP) ? 'w':'-';
perms[6]=(st.st_mode & S_IXGRP) ? 'x':'-';
perms[7]=(st.st_mode & S_IROTH) ? 'r':'-';
perms[8]=(st.st_mode & S_IWOTH) ? 'w':'-';
perms[9]=(st.st_mode & S_IXOTH) ? 'x':'-';
int linkNum=st.st_nlink;
char * fileUser = getpwuid(st.st_uid)->pw_name;
char * fileGrp = getgrgid(st.st_gid)->gr_name;
long int fileSize = st.st_size;
char * time = ctime(&st.st_mtime);
char mtime[512]={0};
strncpy(mtime,time,strlen(time)-1);
char buf[1024];
sprintf(buf,"%s %d %s %s %ld %s %s",perms,linkNum,fileUser,fileGrp,fileSize,mtime,argv[1]);
printf("%s\n",buf);
return 0;
}
