数据结构课程设计——EXT2文件系统（本人原版项目书）

type

status

date

slug

summary

📝 主旨内容

声明：本代码在Ubuntu20.04中实现与运行（因为需要Linux的系统库，所以无法在Windows上运行）。

一、概述

1.什么是文件系统

文件系统是操作系统中的一个核心组件，它是指在存储设备上（如硬盘或固态硬盘）用于组织和管理文件的方式。

文件系统提供了存储、检索、更新和保护文件和目录的机制，并且支持文件的创建、修改、删除和查找等操作。文件系统由三部分组成，包括文件系统的接口、对对象进行操纵和管理的软件集合，以及对象及其属性。从系统角度来看，文件系统负责文件的存储、保护和检索，同时也负责空间的管理和分配。此外，文件系统还提供了一种按名称存取文件的方法，并将逻辑文件系统与物理存储设备（如磁盘）的转换，使得用户可以更高效地使用文件和目录。

2.常见的文件系统的分类

Windows：FAT，FAT16，FAT32，NTFS等

Linux：EXT，EXT2，EXT3，EXT4等

其他：NFS，HPFS，HFS+等

3.EXT2的简单介绍

第二代扩展文件系统（英语：second extended filesystem，缩写为ext2），是Linux内核所用的文件系统。它开始由Rémy Card设计，用以代替ext，于1993年1月加入Linux内核之中。它和BSD中的Unix系统具有相同的设计标准，同时也是Linux上的第一个商业级文件系统。

我们知道，磁盘是用来储文件的，但是必须先把磁盘格式化为某种格式的文件系统，才能存储文件。文件系统的目的就是组织和管理磁盘中的文件。在 Linux 系统中，最长见的是 ext2 系列的文件系统。其早期版本为 ext2，后来又发展出 ext3 和 ext4。ext3 和 ext4 虽然对 ext2 进行了增强，但是其核心设计并没有发生变化，所以我们仍是以较老的 ext2 作为演示对象。

下图简单介绍了EXT2文件系统的基本属性：

4.EXT2和FAT的区别

5.EXT2的结构

5.1 EXT2文件系统的构造

对文件系统而言，文件仅是一系列可读写的数据块。文件系统并不需要了解数据块应该放到物理介质上什么位置。这些都是设备驱动的任务。无论何时，只要文件系统需要从包含它的块设备中读取信息或数据，它就将请求底层的设备驱动读取一个基本块大小整数倍的数据块。EXT2文件系统将它所使用的逻辑分区划分成数据块组。每个数据块组都将那些对文件系统完整性最重要的信息复制出来，同时将实际文件盒目录看做信息与数据块。

即文件系统管理的是一个逻辑空间，这个逻辑空间就像一个大的数组，数组的每个元素就是文件系统操作的基本单位——逻辑块。逻辑块是从0开始编号的，而且，逻辑块是连续的，逻辑块相对的是物理块。通常，EXT2的物理块占一个或几个连续的扇区。

正如上面的结构图所示，我们将其简化：EXT2文件系统把它所使用的磁盘逻辑分区划分为若干块组（block group），并从 0 开始依次编号。每个块组中包含若干数据块（图中数据区），其中存放文件内容。每个组中除数据块（区）之外，包括 5 种用于管理和控制的信息块：超级块（superblock）、组描述符（Group Description）、块位图（block bitmap）、inode位图（Inode bitmap）和 inode表（Inode table）。这些信息位于每个块组的前部，后面是文件的数据块（区）。

一般而言，只有块组0的超级块才读入内存，其他块组的超级块仅仅作为备份。在系统运行期间，要将超级块复制到内存系统缓冲区。

EXT2整个磁盘的逻辑结构如图所示：

5.2 EXT2超级块

超级块中包含了描述文件系统基本尺寸和形态的信息。文件系统管理器利用他们来使用和维护文件系统。EXT2超级块是用来描述EXT2文件系统整体信息的数据结构，是EXT2的核心所在。超级块经函数ext2_fill_supter读入后，又在内存中建立一个映像super_block.u.ext2_sb_info结构。

结构ext2_super_block列出如下：

逻辑块是从0开始编号的，对块大小为1KB的文件系统，s_first_data_block为1，对其他文件系统，则为0.

5.3 组描述符（Group Description）与组描述符表

组描述符：记录各个组块的描述信息（在位文件分配磁盘空间时需要使用这些信息）。这些组描述符集中在一起，就形成了组描述符表。组描述符可能占用多个物理块。和超级块一样的是：每个组块中的组描述符的内容完全相同，而且它的内容也要读入内存。

块组描述表是由一个个块组描述符组成的，有多少个块组就有多少个块组描述表。

Block bitmap, inode bitmap, inode table的起始块

Block 和 inode的剩余数量

5.4块位图和节点位图

在EXT2文件系统中，采用位图描述数据块和索引节点的使用情况，每个块组中占用两个块，即一个用来描述该数据块的使用情况，另一个描述该组索引节点的使用情况。这两个块分别称为数据位图块和索引节点位图块。数据位图块中的每一位表示该块组中的每一个块的使用情况，如果为0，则表示相应数据块空闲，如果是1，则表示已分配。

想要新增文件时总会用到 block ，当然选择空的 block 来记录新文件的数据。那你怎么知道哪个 block 是空的？这就得要透过 block bitmap 的辅助了。从 block bitmap 当中可以知道哪些 block 是空的，block bitmap中的一个bit为标记一个block。 0代表未使用，1代表使用。如果一个block的大小为1K，则一个block bitmap的大小为1024*8 = 8192，只能存放8192个block逻辑块，也就是8192*1K = 8M数据。

Inode bitmap功能和block bitmap相似，不过inode bitmap是记录inode是否可用。一个inode保存一个文件信息，所以可以保存1024byte * 8bit = 8192个inode，也就是可以保存8192个文件。

5.5 索引节点（inode）和索引节点表

在EXT2文件系统中每个文件与目录由惟一的inode来描述。每个数据块组的EXT2 inode被保存在inode表中，同时还有一个位图被系统用来跟踪已分配和未分配的inode。

EXT2文件系统使用索引节点来记录文件信息。每个普通文件盒目录都有惟一的索引节点与之对应，索引节点中含有文件或目录的重要信息。当你要访问一个文件或目录时，通过文件或目录名首先找到与之对应的索引节点，然后通过索引节点得到文件或目录的信息及磁盘上的具体的存储位置。

每个块组中的索引节点都存储在各自的索引节点表中，并且按索引节点号依次存储。索引节点表通常占好几个数据块，索引节点表所占的块使用时也像普通的数据块一样能被调入块高速缓存。

EXT2在硬盘上的索引节点的数据结构如下：

6.EXT2的目录与文件

6.1 EXT2 文件的物理结构

EXT2通过索引节点中的数据块指针数组进行逻辑块到物理块的映射。在EXT2索引节点中，数据块中数组共有15项，前12个为直接指针，后三个分别为“一次间接指针”、“二次间接指针”、“三次间接指针”。EXT2文件默认的物理块大小为1KB，块地址占4个字节，所以每个物理块可以存储256个地址。这样，文件大小最大可达12KB+256KB+64MB+16GB。但实际上，Linux是32位系统，故文件大小最大只能为4GB，及整个文件系统都被一个文件所占用。针对这两句话的解释，如下面几段所示：

由于EXT2文件默认的物理块尺寸为1K，EXT2的块地址长度4B，所以每个间接块中的索引表可以包括1024/4=256个物理地址。所以

1.直接地址：允许文件不大于12K

2.一次间接地址：当文件大于12K时采用，允许文件长达256K+12K

3.二次间接地址: 当文件大于256K+12K时采用，允许文件长达 256*256*K+256K+12K

4.三次间接地址: 当文件大于256*256K+256K+12K时采用，允许文件长达256*256*256K+256*256K+256K+12K=16G+64M+256K+12K

但是实际上linux是32位文件系统，文件尺寸最大为4G。

索引节点的物理块指针数组如图所示：

EXT2文件系统以文件的逻辑块号为索引值查找数据块（即：系统是以逻辑块号为索引查找物理块的），逻辑块从0依次编号。例如，要找到第100个逻辑块对应的物理块，因为256+12>100>12，所以要用到一次间接块，在一次间接块中查找第88项，此项内容就是对应的物理块的地址。

节点在磁盘上是经过编号的。其中，有一些节点有特殊用途，用户不能使用。这些特殊节点定义为：

6.2 EXT2 的目录结构

Linux 树型目录结构中，每个文件目录都是一个目录文件，每个目录项都是一个 ext2_dir_entry 结构体，它就是一个文件的符号目录。定义在/include/linux/ext2_fs.h。

EXT2_NAME_LEN 缺省为 255，也就是文件名最大可以用 255 个字符。另外目录项长度根据文件名长度的大小是可变的。但是必须是 4 的倍数，不用部分用\0 填充。删除文件时，将相应的 inode 号字段置 0，如果相邻有空白目录项则合并。添加文件时，找到一个长度合适的空白目录项，并写入相应信息；若空白表项使用后剩余空间大于12B，则把剩余部分仍作为空白目录项。如果找不到合适的空目录项，就在文件尾部建立这个文件的目录项。

二、数据结构

基于上述对EXT2文件系统内容的深入探究，可以看到EXT2文件系统是庞大且复杂的。虽然无法复现完整的EXT2文件系统，但基于上述思想，此次课程设计本人设计了一个简化版的EXT2文件系统，它基于Linux的inode（索引节点）与位图技术，并利用在内存中开辟的一块区域来代替硬件进行模拟。

该文件系统中的块按照超级块、组描述符、块位图、inode位图、inode table、数据库的顺序构建。使用共用体（联合）包含上述每种块的数据结构。实现中涉及的块号用16位无符号short表示，该块组中最多不会超过2^16块。该EXT2文件系统的核心数据结构详情如下表：

其中，inode_table是索引节点表，每个文件的inode使用128字节存储。Inode_table一共占用32块，每块顺序存储32个inode。因此规定，此系统最多不超过1024个文件或目录。Inode_table的结构类似于二维数组，截取一行里的不同段表示不同的字段表示inode的不同属性。为了简便这里使用了结构体数组起到相似的功能。

数据块分为目录块和文件块。目录块和文件块的头2个字节都用作指针，指向同一文件的下一数据块, 若为0表示没有下一个数据块。文件块使用余下的4094字节来存储数据。目录块稍有特殊，使用第二个字存储自身的inode（即.目录），使用第三个字存储父目录的inode（即..目录）。目录块从第四个字开始存储自身包含的子目录的inode，每个inode用一个字（2字节）存储，依次排列。

建立系统时，初始化并建立了root根目录。root目录的inode设为0，新建的文件或目录inode范围在1~1023之间。

对应到代码里面，如下所示：

1.用户和组为了实现起来方便，本代码省去了权限管理与控制。只有一个root用户和一个root用户组，即拥有所有权限（除了文件可以使用chmod修改读写权限）。即：本系统面向单用户、单任务，不考虑并发，不考虑文件属主、组等概念。

2.super_block（超级块）

3.全局变量为了方便调用一些使用频繁的变量，我们用全局变量来声明它们。（1）start/end：其类型（clock_t）定义来自<time.h>,用于表示 CPU 时间。该类型的变量通常用于衡量程序执行的时间；（2）tms：在C语言中，tms结构体是与时间和系统资源使用有关的一个结构体，针对Linux系统，其通常在<sys/times.h>头文件中定义。这个结构体通常用于获取进程的CPU时间，也就是该进程使用和管理的CPU时间；借助于clock_t 与 tms，我们使用times()函数来获取开始和结束时的CPU时间，然后通过结构体的各个字段计算出代码运行过程中各项CPU时间的变化。（3）cmd[]用于存储命令字符串；（4）cmd_s[3][]用于存储每条命令各个部分参数值（由于该文件系统一个命令最多包含三个部分，所以使用3行）；（5）full_path[]用于存储当前所在目录下，从根目录开始的的完整目录；（6）now_dir记录当前所在目录的inode。

三、函数

1.系统函数

首先介绍本系统块的划分：左边数字表示块的编号，右边代码该编号的块所属的类别。

可以看到，前面0到35（一共36个）块它们有各自的用途，从第36（实际第37）个块开始，此后的块均为数据块，用于存储文件内容。

1.1 通过inode获取文件名

通过inode获取文件名，用于后面所有需要匹配文件名的功能函数，检查用户输入的文件名是否存在。

1.2 查询数据块位，使用实际块号，范围：36~32767

1.3 启用数据块位，使用实际块号，范围：36~32767

在初始化函数（init()）中建立root根目录、创建文件夹、创建文件时，用于将获取的空数据块的位图设置为1，表明启用该数据块。

1.4 清除数据块位，使用实际块号，范围：36~32767

在删除空目录、删除文件时，将文件（或者文件夹）的数据块位图设置为0，表明释放该数据块（即：将该数据块又重新标记为未使用状态）。

1.5 查询inode是否使用，范围：0~1023

在列出目录内容（ls()）、列出目录详细内容（ll()）函数中，用于查询inode是否处于使用状态，每有一个inode处于使用状态，就表明有一个文件或者文件夹处于该文件夹中。

1.6 启用inode位，范围：0~1023

在初始化函数（init()）中建立root根目录、创建文件夹、创建文件时，用于将inode位图设为1，表明新建立了一个文件夹或者文件。

1.7 清除inode位，范围：0~1023

在删除空目录、删除文件时，恢复inode位图，表示该文件或者文件夹被删除。

1.8 获取空闲数据块，返回实际块号

在创建文件夹、创建文件时，用于检索块组，获取空闲数据块，以便新建立的文件夹或者文件能够有地方存储数据内容信息。

1.9 获取空闲inode

在创建文件夹、创建文件时，检索inode位图，获取空闲inode。如果能够得到空闲的inode，表明还可以再新建文件或者文件夹；如果不能得到空闲的inode，表明没有空闲区域用于建立新的文件或者文件夹（即存储空间满了）。

1.10 检查重名 inode:有重名 0:无重名

在进入目录（cd()）函数中，用于判断子目录是否存在。

在创建目录、创建新文件时，用于判断文件夹或者文件名是否重复。如果非重名才能够新建文件或者文件夹。

1.11 检查目录中的文件个数，判断是否为空目录

该函数用于在删除空目录（rm_dir()）函数中，检查该目录是否为空。只有空目录才能进行删除操作。

1.12 设置inode的各个属性

该函数用于在创建文件夹、创建文件时，设置文件夹或者文件的基础属性：

例如：创建文件夹或者文件时，设置其使用的inode号、文件类型（0:未知 1:普通文件 2:目录）、文件权限（0:未知 4:r 2:w 1:x）、文件大小、文件（夹）最后修改时间、文件（夹）的数据块数（注：文件夹的数据块数恒定为1，文件的数据块数根据文件大小计算得到）、首个数据块的地址、文件（夹）名。

1.13 读取inode的详细属性

该函数用于在列出目录详细内容（ll()）函数中，获取该文件夹中每个文件（夹）的详细属性，然后以固定格式打印出来。

1.14 清理一个数据块。清理工作在该块被重用时进行，而非删除时

由于本系统在删除文件、文件夹时只是恢复位图为未使用状态，但是并没有清除数据块里面的数据。所以，在创建文件夹、创建文件时，该函数用于对获取到的数据块进行清理操作，进而方便后续存储新文件、文件夹的数据。

1.15 16进制快捷转换为二进制

该数组和1.16的函数用于调试，此数组用于做16进制到2进制的快捷转换。

1.16 查看所有数据块的占用情况（便于调试，此命令隐藏）

该函数用于调试，在mian()函数中使用（在文件系统中输入dis命令），可以查看所有数据块的占用情况。

2.功能函数

2.1 记录时间

该函数用于生成创建文件时的时间，并在修改文件时，更新（修改）文件的修改时间。最后的数据存入变量“float mtime;”中。

2.2 分割命令

该函数应用在main()函数中，用于读取用户输入，并判断用户输入是否标准（以空格为分割符，以回车作为命令输入结束标志）。

3.EXT2相关命令对应的功能函数

3.1 初始化

文件系统初始化时，需要关注以下几个部分：

超级块设置索引节点总数为1024；数据块总数为32732（2^15 - 36）; 文件系统的大小为32768（2^15）。

组描述符设置该块位图的块号为2，索引节点位图的块号为3，第一个索引节点表块的块号为4；设置组中空闲块的个数为32732，因为有36个块被使用（用于存储文件系统的相关信息）；组中空闲索引节点的个数为1024（均未被使用）；组中目录的个数为0（未创建目录）。

块位图设置前36块为已使用状态。

建立根目录，进行根目录的相关设置，包括：空闲块个数减1，空闲索引节点个数减1，目录数量加1，启用第36号数据块，启用第0号inode位，索引节点类型为2表明该节点是目录，文件权限为6（w+r）。

3.2 进入目录

为了实现起来方便，这里的cd命令只针对以下情况有效：进入子目录、本目录、父目录；注意：不能指定绝对路径。

同时，为了使系统更加接近真实的文件系统，我们加入了快速回退至根目录的功能。可以使用cd /或cd root回到根目录。

并且，程序使用一个全局变量now_dir记录当前工作目录的inode。可以通过递归查找目录的..目录（父目录），直到找到根目录来拼接成完整的路径。使用cd命令时只需要在当前目录数据块内查找到相应目录的inode，将now_dir变量更新为该inode后再次递归显示路径即可。

3.3 创建目录

在创建目录时，我们需要得到要创建的目录名，同时应注意，创建的每个目录都必须有两个属性，即“.”（当前目录）和“..”（父目录），用于辅助ls命令显示目录内容，以及cd命令进行目录切换。

得到目录名后，我们需要检查索引节点和存储空间以判断是否还有空闲空间来创建目录。只有同时满足有空闲索引节点以及有空闲存储空间时，再创建目录。创建目录时，就需要进行相关设置，包括：空闲块个数减1，空闲索引节点个数减1，目录数量加1，遍历获取空inode、数据块，并清理里面的内容，然后将它们分配给该目录。

找到当前工作目录的数据块，找到所有子文件的inode。通过查询inode里存储的文件名，进行比对，确定有无重名目录。有重名文件时停止创建；无重名文件时查询组描述符，检查索引节点和存储空间是否有空闲。有空闲则开始创建该目录。查询inode位图和数据位图，找到空闲的inode和数据块。向inode写入目录信息，向数据块的前三个字分别写入0、自身的inode、父目录的inode。

3.4 删除空目录

找到当前工作目录的数据块，找到所有子文件的inode。通过查询inode里存储的文件名，进行比对，确定有要删除的目录。若能通过目录名确定inode，则将相应位置的inode位图恢复为0，表示这个inode可以被新文件申请使用。然后将相应位置的数据位图恢复为0，若有后继数据块，重复恢复过程，直到所有用到的数据块位都恢复为0。并且，将父目录数据块里记录这一个目录inode的两个字节覆盖为0，从而使父目录不能再查询到这一子目录。rm的执行并不会删除inode节点和数据块里的内容，当有新文件使用它们时，才会将其清理。

3.5 创建新文件，默认分配数据块(512B) or 修改文件时间

创建新文件方式1——默认创建，即：不指定创建的文件的大小，那么在设置文件数据块的各个属性时，默认其大小位512B。

找到当前工作目录的数据块，找到所有子文件的inode。通过查询inode里存储的文件名，进行比对，确定有无重名文件。有重名文件时修改其inode，更新文件修改时间；无重名文件时查询组描述符，检查索引节点和存储空间是否有空闲。有空闲则开始创建文件。查询inode位图和数据位图，找到空闲的inode和数据块。向inode写入文件信息。若touch命令没有指定文件大小，则不申请数据块，只填写inode。

3.6 创建新文件，分配数据块 or 修改文件大小和时间（以字节为单位）

内容大致和3.5中一样，只是在设置inode相关属性时，将默认分配的512B存储空间改成指定大小的存储空间。

3.7 删除文件

找到当前工作目录的数据块，找到所有子文件的inode。通过查询inode里存储的文件名，进行比对，确定有要删除的文件。若能通过文件名确定inode，则将相应位置的inode位图恢复为0，表示这个inode可以被新文件申请使用。然后将相应位置的数据位图恢复为0，若有后继数据块，重复恢复过程，直到所有用到的数据块位都恢复为0。并且，将父目录数据块里记录这一个文件inode的两个字节覆盖为0，从而使父目录不能再查询到这一子文件。rm的执行并不会删除inode节点和数据块里的内容，当有新文件使用它们时，才会将其清理。

3.8 列出目录内容

找到当前工作目录的数据块，每次读取两个字节，若不为0，则为一个子文件的inode，将其inode节点存储的文件名显示出来。直到该块被遍历完毕。若有后继块，则继续读取。使用-a选项时，额外打印隐藏的.和..目录。使用-l选项时，打印详细信息，将inode节点里的各个属性依次显示出来。

3.9 递归获取父级inode，拼接路径

get_full_path()函数的辅助函数，采用递归的方式，用于获取完整目录路径。

3.10 给出当前完整目录

该函数用于文件系统命令行，实时在左侧显示当前目录路径。借助get_super_inode()函数，通过递归的方式获取完整路径，再进行打印输出。

3.11 编辑文件

作为本系统最复杂的一个函数，目前版本是通过文件指针在磁盘上建立文件进行编辑，但是这样就和文件系统本身的关联性不强。下一步是参考Linux系统的vi命令进行修改，使其能够更加完美。

3.12 查看文件内容

该函数通过文件名查找文件，如果文件存在，然后再找到文件的数据块，遍历数据块里面的内容，进行输出打印。

3.13 修改文件权限

根据设定，当文件权限值为7（即wrx）时，我们才能够被修改；当文件权限值为5（rx）时，文件只读。因此，用户可以修改文件权限值，进而修改文件的读写权限。

4.主函数main

系统的主函数，文件系统的所有功能都在这里面调用。

首先，初始化文件系统。完成后，用户在命令行按“回车键”便可进入文件系统，当然也可以按“q”退出；

进入文件系统后，用户可以执行各种基础操作，相关函数的实现上面已经完成分析到。

如果用户不清楚有哪些命令，可以在命令行输入“help”，系统会输出该文件系统相关命令及其功能。

如果用户想要退出文件系统，首先输入“exit”，然后就进入选择界面，按“q”即可退出该系统；或者再按“回车键”再次进入文件系统。

5.EXT2相关命令与功能函数对照表

EXT2命令	功能函数
ls	ls()
ls -a	ls()
ls -l	ll()
cd	cd()
mkdir	mkdir()
rmdir	rm_dir()
touch	touch()/ touch_size()
rm	rm()
vi	vi()
cat	cat()
chmod	chmod()
help	help()
exit	exit()

6.EXT2文件系统结果测试截屏

🤗 总结归纳

本文由博主课程设计的项目书改编而来，方便各位参考，相关代码已上传至GitHub。

📎 参考文章

引用文章

💡

有关Linux系统与EXT2文件系统安装或者使用上的问题，欢迎您在底部评论区留言，一起交流~