基于linux开发的实现类似unix的文件系统.zip

> 本文档于课程设计时（2016年12月）撰写，于2020年3月在电脑上发现整理，不仅怀念起当时的时光。 # 设计任务，要求 # 程序设计目标 ## 程序全局设计目标 经过小组讨论，实际的程序的功能设计除课程设计的要求之外，还额外的增加了一些必要且实用功能和设计。 一来使得整个程序的的设计结构更加模块化，更富有弹性和扩展性，还能提供友好的操作方式； 二来通过这些额外设计增进小组对操作系统和编程的理解和能力。 总的来说，程序在设计之初，规划中的功能有： 一、程序能够在多种抽象磁盘上建立文件系统。其中，抽象磁盘可以是： - 真正的磁盘 - 主操作系统中的一个大文件 但是实际上，任何能够看成一系列扇区组合的并且支持对某个扇区进行读写操作的对象，都能视为抽象磁盘，从而基于此建构整个文件系统。 二、程序能够将不同的磁盘挂载到不同盘符（类似 Windows 系统的盘符），在通过路径操作文件时，程序能自动根据盘符识别具体的文件系统类型，从而执行对应的操作。 一个磁盘可以格式化为一个文件系统，一个磁盘可以挂载到一个盘符。理论上，程序支持多种文件系统，如： - FAT32 - ext3 - ext4 - fulfs 由于此课程设计的目标是实现类 unix 文件系统（在这次课程设计里将其命名为 fulfs），因此实际上只实现了 fulfs。 但是理论上能够进行方便的扩展支持其它的各种文件系统。 三、由于第 2 点的设计需要，程序必须提供一组抽象的接口用于根据文件路径来操作文件系统而不用关心文件系统的具体类型。 因此，程序封装了一组接口，并且为了对使用者友好，其接口形式尽量模仿了 linux 系统调用。 四、程序提供了一个 shell 用于操作挂载的文件系统。并且为了提供良好的用户体验，shell 的绝大数命令都是仿照 linux 的形式。包括以下命令： - cd 切换当前目录。 - pwd 输出当前目录。 - ls 列出目录中的文件。 - rmdir 删除空目录。 - mkdir 创建目录。 - ln 创建链接，支持硬链接和符号链接。 - rm 删除文件。 - cp 复制文件。 - mv 移动文件。 - stat 输出文件的信息。 - df 输出挂载的文件系统的信息。 五、目前整个程序的实现用到且只用到了 ANSI C 和其标准库： - 不涉及任何 windows 或 linux 系统调用或其它依赖于具体操作系统的库 - 不涉及任何第三方库 - 涉及到的算法和数据结构全部由小组编码完成 - 理论上，能够跨平台执行，包括 Windows 和 linux. ## fulfs 文件系统设计目标 fulfs 是小组独立实现的并且符合题目要求的文件系统，为了方便代码编写，将其命名为 fulfs。fulfs 的总体设计目标如下： - 底层上： - 采用索引节点储存文件系统。根据课本的解释，索引节点储存另外文件控制块 FCB 中除文件名之外的内容。 - 采用混合分配方式组织文件数据。 - 采用成组链接法管理空闲的数据块。 - 功能上： - 对最基本的文件储存的支持。 - 对文件，即能够将文件当成流来读写，也能够对文件进行随机读写。 - 对路径和目录的完整支持。 - 对硬链接的完整支持。 - 对符号链接的支持。 # 原理以及算法描述 ## 程序整体设计图  ## fulfs 文件系统整体格式 首先，整个磁盘是以 盘块（block） 为单位进行划分的。将整个磁盘每 sectors_per_block 个扇区分为一组，称为盘块（block）。 整个文件系统的数据结构和算法都是以盘块为单位进行操作，读写的。 block 的大小是扇区大小的整数倍。一个 block 常用 1K，2K，4K，8K。 block 从 0 开始编号，最大到 2^32 - 1，为 uint32_t 的最大值。 假设 block 为 1K，理论上，可管理的最大磁盘容量达到 4T。 ```dot digraph structs { node [shape=record]; struct1 [shape=record, label="Superblock| <f0>inode table |<f1> Data blocks"]; } ```  在磁盘的布局上，如图所示，整个磁盘被划分成了三个部分。分别是： `superblock`：超级块存放文件系统的全局控制信息。如文件系统的 block 大小相关信息，文件系统总扇区数，根目录 inode 号等一些文件系统全局的信息。 考虑到在最开始是不知道 block 的大小的，因此为了实现方便，superblock 始终占用第 0 号 block，但是其真正储存数据只限于第 0 号扇区。 `Inode table`: 这个区域里每个 block 存放可最多存放的整数个 inode 节点。 由于 inode 节点编号是两位无符号整型数，因此理论上 inode 编号最大到 2^16 - 1，是 uint16_t 的最大值。 由此可知，fulfs 文件系统能够储存的目录和文件的总和是有限的。 `Data blocks`: 存放文件内容的空间。当文件需要储存具体的数据时，会从这里划分出一块空闲盘块，并且自己组织管理。 ## 文件和目录管理 普通文件和目录甚至符号链接在此文件系统底层都统一视为文件。 inode 节点中储存一个字段 mode 来表示此文件在上层表现为普通文件，目录，还是符号链接。 除此之外，为了实现方便，inode 空闲管理采用比较低效的方式。 mode 字段还被用来标记是否是空闲块，申请空闲块时需要遍历所有的 inode 节点以寻找空闲块。 除此之外，inode 节点还记录了文件的创建时间，最后访问时间，最后修改时间等信息，保存了丰富的文件信息。 由于此文件系统使用混合分配方式组织文件数据，因此 inode 节点中，提供 10 个直接索引，1 个一级索引，1 个二级索引，1 个三级索引。 当低级的索引满后，启用高一级的索引。 对于数据盘块（data block）的空闲管理，此文件系统使用成组链接法管理数据盘块分配和回收。具体的数据结构实现在后面的重要算法中叙述。 ## 多磁盘挂载 程序采用类似 Windows 盘符的设计，支持将一个磁盘上的文件系统挂载到某个盘符上。 之后，盘符路径即为此文件系统的根目录。 程序内部会记录盘符对应的文件系统信息，比如磁盘号，文件系统类型等。 如设计图所示，在模拟系统调用那一层，操作函数所接收到的路径是带有盘符信息的。 首先这层的操作函数抽取出路径的盘符部分，找到对应的磁盘号和文件系统类型。 之后，抽取出路径中不带盘符的部分，根据文件系统类型找到该文件系统具体的处理函数，调用之以执行对应操作。 # 开发环境 - 操作系统环境：Debian GNU/Linux 8.6 (jessie)，armv7l，2G RAM - 编译器环境：gcc version 4.9.2 (Debian 4.9.2-10) - 调试器：GNU gdb (Debian 7.7.1+dfsg-5) 7.7.1 - make 工具：cmake version 3.0.2，GNU Make 4.0 - 版本控制：git version 2.1.4 注：由于整个程序用且仅用了 ANSI C 和其标准库，因此虽然是用 linux 开发环境，但是也能无缝在 Windows 下编译执行。 # 重要算法和设计思路描述 在整个程序的实现中，涉及的几个关键而且重要的算法分别为混合分配方式中第 n 个相对盘块的定位与添加盘块以及删除盘块， 成组链接法中数据结构的实现和对应的盘块分配/回收算法， 对多个文件名引用的正确处理（此文件系统支持硬链接），以及根据文件的绝对路径定位文件的 inode 编号。 下面逐个阐述这些关键算法和其设计思路。 ### 1. 文件中第 n 个相对盘块的定位 文件中第 n 个相对盘块是指将文件储存数据的盘块从 0 开始编号，编号为