EXT2文件系统

EXT2文件系统

Linux 一直使用EXT2 ( Card等1995)作为默认文件系统。

EXT2文件系统数据结构

通过mkfs创建虚拟磁盘

在Linux下，命令

mke2fs [-b blksize -N ninodes] device nblocks

在设备上创建一个带有nblocks个块(每个块大小为blksize字节)和ninodes个索引节点的EX

T2文件系统。如果未指定blksize,则默 认块大小为1KB,如果未指定ninoides, mke2fs将根

据nblocks计算一个默认的ninodes数。

虚拟磁盘布局

Block#0：引导块B0是引导块，文件系统不会使用它。它用来容纳一个引导程序，从磁盘

引导操作系统。

超级块

Block#1 :超级块(在硬盘分区中字节偏移量为1024)B1是超级块，用于容纳整个文 件系统的信息

s_first_data_block： 0表示4KB块大小，1表示1KB块大小。它用于确定块组描述符的 起始块，即 s_first_data_block + 10
s_log_block_size :确定文件块大小，为 lKB*(2**s_log_block_size),例如：0 表示 1KB块大小，1表示2KB块大小，2表示4KB块大小等。最常用的块大小是用于小文件系 统的1KB和用于大文件系统的4KB。
s_mnt_count ：已挂载文件系统的次数。当挂载计数达到max mnt count时，fsck会话 将*检查文件系统的一致性。
s_magic：文件系统类型的幻数。EXT2/3/4文件系统的幻数是0xEF53

块组描述符

Block#2：块组描述符块(硬盘上的s_first_data_block+l ) EXT2将磁盘块分成几个组。 每个组有8192个块(硬盘上的大小为32K)。每组用一个块组描述符结构体来描述。

块和索引节点位图

Block#8 :块位图(Bmap)(bg_block_bitmap)位图是用来表示某种项的位序列，例如 磁盘块或索引节点。位图用于分配和回收项。在位图中，0位表示对应项处于FREE状态， 1位表示对应项处于IN_USE状态。一个软盘有1440个块，但是Block#。未被文件系统使 用。所以，位图只有1439个有效位。无效位被视作IN_USE,设置为1。
Block#9 :索引节点位图(Imap) (bg_inode_bitmap) 一个索引节点就是用来代表一个 文件的数据结构° EXT2文件系统是使用有限数量的索引节点创建的。各索引节点的状态用 B9的Imap中的一个位表示。在EXT2 FS中，前10个索引节点是预留的。所以，空EXT2 FS的Imap以10个1开头，然后是0。无效位再次设置为1。

索引节点

Block#10：索引(开始)节点(bg_inode_table)每个文件都用一个128字节(EXT4中 是256字节)的唯一索引节点结构体表示。

直接块:i_block[0] Mi_block[ll],指向直接磁盘块」
间接块：i_block[12]指向一个包含256个块编号（对于1KB BLKSIZE）的磁盘块，每 个块编号指向一个磁盘块。
双重间接块：i_block[13]指向一个指向256个块的块，每个块指向256个磁盘块。
三重间接块：i_block[14]是三重间接块。对于“小型” EXT2文件系统，可以忽略它。
索引节点大小（128或256 ）用于平均分割块大小（1KB或4KB）,所以，每个索引 节点块都包含整数个索引节点 在简単的EXT2文件系统中，索引节点的数量是184个 （Linux默认值）。索引节点块数等于184/8-23个。因此，索引节点块为BI0至B32。每个索 引节点都有-个唯一的索引节点编号，即索引节点在索引节点块上的位置+1。注意，索引 节点位置从0开始计数，而索引节点编号从1开始计数。0索引节点编号表示没有索引节点一 根目录的索引节点编号为2。同样，磁盘块编号也从1开始计数，因为文件系统从未使用块 0。块编号0表示没有磁盘块。

数据块

邮差算法

已知 某个街区地址BA=（街区，房子），怎么把它转换为线性地址LA,反过来，已知线性地址, 怎么把它转换为街区地址？如果都从0开始计数，转换就会非常简单。
Linear_addreaa LA = N*block + house; Block_addr«B8 BA - (LA / N, LA % N)，
注意，只有都从0开始计数时，转换才有效。如果有些条目不是从。开始计数的，则不 能直接在转换公式中使用。

遍历EXT2文件系统树

遍历算法

1. 读取超级块。检査幻数s_magic ( OxEF53 ),验证它确实是EXT2 FS

2. 读取块组描述符块(1 + s_first_data_block),以访问组0描述符。从块组描述符的 bg_inode_table条目中找到索引节点的起始块编号，并将其称为InodesBeginBlock

3. 读取InodeBeginBlock,获取/的索引节点，即INODE #2

4. 将路径名标记为组件字符串，假设组件数量为恥例如，如果路径名=/a/b/c,则组 件字符串是“a”“b”“c”，其中n = 3。用name[0], namefl],…，name[n-l]来表示组件

5. 从(3)中的根索引节点开始，在其数据块中搜索name[0]。(5)。目录索引节点的每个数据块都包含 以下形式的dir entry结构体：
   (ino rec_len name_len NAME] [ino rec_len name_len NAME)
   其中NAME是一系列nlen字符，不含终止NULLO对于每个数据块，将该块读入内存 并使用dir_entry *dp指向加载的数据块。然后使用name」en将NAME提取为字符串，并与 namefO]进行比较。如果它们不匹配，贝U通过以下代码转到下一个dir_entry：
   dp * (dir_entry *)((char *)dp + dp->rec_len))
   继续搜索。如果存在name[0]，则可以找到它的dir_entry,从而找到它的索引节点号。

6. 使用索引节点号ino来定位相应的索引节点。回想前面的内容，ino从1开始计数。 使用邮差算法计算包含索引节点的磁盘块及其在该块中的偏移量。

   blk = (ino - 1)    / INODES_PER_BLOCK + InodesBeginBlock;
   offset = (ino - 1) % INODES_PER_BLOCK;
   

   然后在索引节点中读取/a,从中确定它是否是一个目录(DIR)。如果/a不是目录，则 不能有/a/b,因此搜索失败。如果它是目录，并且有更多需要搜索的组件，那么继续搜索 下一个组件name[l]o现在的问题是：在索引节点中搜索/a的name[l],与第(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
)

8. 只需调用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[i])
   if (!ino){ // canrt find name[i], exit;)
   use ino to read in INODE and let ip point to INODE
   

mount-root

mount_root.c文件：该文件包含mount_root()函数，在系统初始化期间调用该函数来挂 载根文件系统。它读取根设备的超级块，以验证该设备是否为有效的EXT2文件系统。然 后，它将根设备的根INODE (ino = 2 )加载到minode中，并将根指针设置为根minode。它 还将所有进程的当前工作目录设置为根minodeo分配一个挂载表条目来记录挂载的根文件 系统。根设备的一些关键信息，如inode和块的数量、位图的起始块和inode表，也记录在 挂载表中，以便快速访问。

#include "type.h"
#include "util.c"
// global variables
MINODE minode[NMINODES], *root;
MTABLE mtable[NMTABLE];
PROC proc[NPROCJ, *running；
int ninode, nblocks, bmap, imap, iblock;
int dev；
char gline[25], *name[16];    // tokenized component string strings
int rmame；    // number of component strings
char *rootdev = *mydisk*;    // default root_device
int fs_init()


int i,j;
for (i=0; i<NMINODES; i++) minode[i].refCount = 0； for (i=0; i<NMOUNT; i++) mtable[i].dev = 0;
for (i=0; i<NPROC; i++)( proc[i].status = READY; proc[i].pid = i; proc[i].uid = i; for (j=0; j<NFD; j++) proc[i].fd[j) = 0;
// initialize
all minodes as FREE
//
// // // //
//
initialize
mtable entries as FREE
initialize reday to run pid = 0 to NPROC-1 P0 is a superuser process
PROCs
all file descriptors are NULL








proc[i].next = &proc[i+1]；
proc[NPROC-1].next = &proc[0]； running = &proc(0];
int mount_root(char *rootdev) // mount root file system (
int i;
MTABLE *mp;
SUPER *sp；
GD *gp;
char buf[BLKSIZE];
dev = open(rootdev, O_RDWR)/
if (dev < 0)(
printf("panic : can, t open root device\n"); exit(1);
/* get super block of rootdev */ get_block(dev, 1, buf);
sp = (SUPER *)buf;
/* check magic number */
if (sp->s_magic != SUPER_MAGIC)(
printf("super magic=%x : %s is not an EXT2 filesys\n"z sp->s_magic, rootdev);
exit(0);
// fill mount table mtable[0] with rootdev information mp = suitable[0] ;    // use ratable[0]
mp->dev = dev；
// copy super block info into mtable[0] ninodes = mp->ninodes = sp->s_inodes_count; nblocks = mp->nblocks = sp->s_blocks_count; strcpy(mp->devName, rootdev);
strcpy(mp->mntName, "/");
get_block(dev, 2, buf);
gp = (GD *)buf;
bmap = mp->bmap = gp->bg_blocks_bitmap；
imap = mp->imap = gp->bg_inodes_bitmap； iblock = mp->iblock = gp->bg_inode_table； printf("bmap=%d imap=%d iblock=%d\n", bmap, imap iblock);
// call iget(), which inc minode* s refCount
root = iget(dev, 2); mp->mntDirPtr = root; root->mntPtr = mp；

return 0；
int main (int argc, char *argv[])
{
char line[128], cmd[16], pathname[64]； if (argc > 1)
rootdev = argv[1];
fs_init();
mount_root(rootdev);
while(1)(
printf("P%d running： "z running->pid); printf("input command :")；
fgets(line, 128, stdin)；
line[strlen(line)-1] = 0;
if (line[0]==0)
continue；
sscanf(line, "%s %s", cmd, pathname);
if (!strcmp(cmd, ''Is"))
Is(pathname)；
if (! strcmp(cmd,、'cd"))
chdir(pathname)；
if (!strcmp(cmd, "pwd"))
pwd(running->cwd)；
if (! strcmp (cmd, ''quit"))
quit();
int quit() // write all modified minodes to disk
(
int i；
for (i=0; i<NMINODES; i++)(
MINODE *mip = &minode[i];
if (mip->refCount && mip->dirty)(
mip->refCount = 1;
iput(mip);
}
}
exit(0);
}

基本文件系统的实现

1级文件系统函数

mkdir算法

(1). divide pathname into dirname and basename, e.g. pathname=/a/b/c, then
dirname=/a/b； basename=c;
(2). // dirname must exist and is a DIR：
pino = getino(dirname)；
pmip = iget(dev, pino);
check pmip->INODE is a DIR
(3). // basename must not exist in parent DIR：
search(pmip, basename) must return 0;
(4). call kmkdir(pmip, basename) to create a DIR;
kmkdir() consists of 4 major steps:
(4).1. Allocate an INODE and a disk block:
ino = ialloc(dev);
blk = balloc(dev),
(4).2. mip = iget(dev, ino) // load INODE into a minode
initialize mip->INODE as a DIR INODE;
mip ->INODE.i_block[0] «= blk; other i_block( ] = 0;
mark minode modified (dirty);
iput(mip)/    // write INODE back to disk
《4).3. make data block 0 of INODE to contain . and .. entries;
write to disk block blk.
(4).4. enter_child(pmip, ino, basename); which enters
(ino, basename) as a dir_entry to the parent INODE;
(5). increment: parent INODEzs links_count by 1 and mark pmip dirty；
iput(pmip);

要创建一个目录，我们需要从索引节点位图中分配一个索引 节点，并从块位图中分配一个磁盘块，分配操作依赖于测试，然后设置位图中的位。为了保 持文件系统的一致性，分配一个索引节点后，必须将超级块和组块描述符中的空闲索引节点 计数减1。同样，分配一个磁盘块后，也必须将超级块和块组描述符中的空闲块数减1。还 要注意，位图中的位从0开始计数，而索引节点和块号从1开始计数。

creat 算法、 rmdir算法、mkdir&creat算法、link算法、unlink算法readlink算法

3级文件系统

3级文件系统支持文件系统的挂载、卸载和文件保护。

挂载算法

挂载操作命令

mount filesys mount_point

可将某个文件系统挂载到mount-point目录上。它允许文件系统包含其他文件系统作为现有 文件系统的一部分。挂载中使用的数据结构是挂载表和mount_point目录的内存minode。

交叉挂载点

对于挂载，我们必须修改 getino(pathname)函数，来支持交叉挂载点。假设某文件系统newfs已被挂载到目录/a/b/c/ 上'当遍历一个路径名时，两个方向的挂载点可能会出现交叉。
(1 )向下遍历：当遍历路径名/a/b/c/x时，一旦到达/a/b/c的minode,我们就能看到 minode已经被挂载(挂载标志=1)。我们不是在/a/b/c的索引节点中搜索x,而是必须要：
,跟随minode的mntPtr指针来定位挂载表条目。
・从挂载表的设备号中，将其根索引节点(ino=2 )放入内存。
・然后，继续在挂载设备的根索引节点下搜索X。
(2)向上遍历：假设我们在目录/a/b/c/x/上，然后向上遍历，例如cd 将会与 挂载点/a/b/c交叉。当到达挂载文件系统的根索引节点时，我们就能看到它是一个根目 录(ino=2 ),但是它的设备号与实根的设备号不同，因此它现在还不是实根，我们可以使 用它的设备号，找到它的挂载表条目，它指向/a/b/c/的minode。然后，切换到/a/b/c/的 minode,继续向上遍历。因此，交叉挂载点就像一只猴子或松鼠从一棵树跳到另一棵树上， 然后又跳了回来。
由于交叉挂载点会更改设备号，因此一个全局设备号是不够的。我们必须要将getino() 函数修改为

int getino(char *pathname, int *dev)

并将getino()调用修改为

int dev;    // local in function that calls getino()
if (pathnme[0]==, / *)
dev 工 root->dev；    // absolute pathname
else
dev n running->cwd->dev; // relative pathname
int ino «= getino（pathname, &dev） : // pass &dev as an extra parameter

实验代码及截图

测试代码时遇到的问题

fatal error：ext2fs/ext2_fs.h: No such file or directory

查看/usr/include，没有ext2fs文件夹

解决办法：sudo apt-get install e2fslibs-dev e2fslibs-dev