以前我们都是直接使用别人实现好的文件系统,而现在需要我们自己设计文件系统了,最先想到的文件系统设计如下
这种设计方式肯定是每个人都能想到的,然而这种设计并不具备可行性,缺陷太严重,文件名不友好,谁能通过一个数字(扇区号)来找到一个文件;文件的容量太小,一个文件只能放在一个扇区里,要是文件大小超过 512 字节了怎么办
改进思路
大致的方向有了,那么下面就要思考更多的细节问题了
带着问题继续向下
我们先来做一个文件系统的概要性设计
前面虽然对文件系统有了一个大概的认识,但是依旧迷迷糊糊的,为啥迷糊呢?因为扇区分配表与文件数据区之间的映射关系在我们脑子中还是一片空白
那么接下来的重点就是搞清楚这个映射关系
首先,我们能想到的逻辑关系是这样子的,当一个文件需要多个扇区共同存储时,只需要找到第一个扇区,之后就可以根据 next 指针依次向下寻找,直到找全所有扇区,是不是很像链表呢
逻辑上我们用链表的思维来设计映射关系很合适,但是这些映射关系是需要存储到硬盘中的,所以我们还得从物理上设计一下映射关系
// 存储与 0 号扇区,记录文件系统概要信息
typedef struct FS_HEADER
{
U08 forJmp[4]; // 预留 4 字节给跳转指令使用
U08 magic[32]; // 文件系统名字
U32 sctNum; // 可以使用的扇总数
U32 mapNum; // 扇区分配表所占的扇区数
U32 freeBegin; // 我们把空闲扇区组织成一个链表,freeBegin 为第一个空闲的扇区号
U32 freeNum; // 空闲扇区数
} FS_HEADER;
// 记录根目录相关信息,存储于 1 号扇区
typedef struct FS_ROOT
{
U08 magic[32]; // 根目录名字
U32 rootBegin; // 将根目录所涉及的所有扇区组织成一个链表,rootBegin 为第一个扇区号
U32 rootNum; // 根目录所占的扇区数
U32 lastBytes; // 最后一个扇区中的有效数据字节数
} FS_ROOT;
*
n 个扇区(文件数据区)*
n = max - 2 - n,推到得到扇区分配表的大小(所占扇区数):n = (max - 2) / ( (SEC_SIZE / 4) + 1)准备的差不多了,接下来进入主题,实现硬盘格式化功能函数
在实现功能代码之前我们先扩大一下虚拟硬盘的大小,修改后的 Build.py
hard_size = int(os.stat(kernel_bin).st_size/1024/1024) + 80
cmd_str = "bximage -func=create " + IMG + ' -hd=' + str(hard_size) + ' -imgmode="flat" sectsize=512 -q'
os.system(cmd_str)
硬盘格式化本质上就是做了三件事:将文件系统概要信息填充到扇区 0,将根目录相关信息填充到扇区 1,以及初始化扇区分配表
将文件系统概要信息填充到扇区 0 具体要做的工作是创建一个 FS_HEADER 数据结构并给其各元素赋值,然后再将 FS_HEADER 这个数据结构写入到扇区 0 中
将根目录相关信息填充到扇区 1 具体要做的工作是创建一个 FS_ROOT 数据结构并给其各元素赋值,然后再将 FS_ROOT 这个数据结构写入到扇区 1 中
以上这两个初始化工作比较好理解,最后一个扇区分配表的初始化稍微复杂了一点,用语言不容易描述,直接上图理解吧,下图即为扇区分配表初始化后的结果
初始化时扇区分配表中的所有管理单元都是空闲的,将这些管理单元挨个串联起来,每一个管理单元都指向下一个管理单元,最后然后再挂到 freeBegin 上形成一个空闲链表
完整格式化代码如下:
static E_RET FsFormat(void)
{
FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于文件概要信息(扇区 0)数据处理使用
FS_ROOT* root = (FS_ROOT *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于根目录信息(扇区 1)数据处理使用
U32* pUnit = (U32*)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于扇区分配表数据处理
U32 i = 0;
U32 j = 0;
U32 current = 0;
if(NULL == header || NULL == root || NULL == pUnit)
goto error;
// 初始化扇区 0,即将文件系统概要信息写到扇区 0 中
StrCpy(header->magic, FS_MAGIC, -1);
header->sctNum = FS_SEC_NUM;
// 计算扇区分配表所占扇区数
// header->sctNum - 2 是因为扇区 0 和 扇区 1 被特定使用,这两个扇区需要先被踢除
// + !!((header->sctNum - 2) % (SEC_SIZE / 4)) 是因为扇区分配表中最后一个扇区并不一定是满的。不足一个扇区也按一个扇区算
header->mapNum = (header->sctNum - 2) / (SEC_SIZE / 4) + !!((header->sctNum - 2) % (SEC_SIZE / 4));
// 格式化时第一个空闲的扇区号即为扇区分配表后的第一个扇区的扇区号
header->freeBegin = 2 + header->mapNum;
// 格式化时空闲扇区数等于总扇区数减去扇区 0 和 扇区 1 这两个固定的扇区,然后再减去扇区分配表所占的扇区数
header->freeNum = header->sctNum - 2 - header->mapNum;
// 写到硬盘扇区 0 中
if(E_ERR == FS_WRITE(0, (U08 *)header))
goto error;
// 初始化扇区 1,即将根目录相关信息写到扇区 1 中
StrCpy(root->magic, ROOT_MAGIC, -1);
// 格式化时根目录下为空,也可以看成是根目录这个文件没有数据,不占用一个扇区
root->rootBegin = SEC_END_FLAG;
root->rootNum = 0;
root->lastBytes = 0;
// 写到硬盘扇区 1 中
if(E_ERR == FS_WRITE(1, (U08 *)root))
goto error;
// 初始化扇区分配表
for(i = 0; (i < header->mapNum) && (current < header->freeNum); i++)
{
for(j = 0; j < MAP_UNIT_NUM; j++)
{
*(pUnit+j) = current + 1;
current++;
// 如果是最后一个扇区管理单元,则将其内数值设置为结束标志,并且跳出循环
if(current == header->freeNum)
{
*(pUnit+j) = SEC_END_FLAG;
break;
}
}
// 写到硬盘扇区分配表中
if(E_ERR == FS_WRITE(2+i, (U08 *)pUnit))
goto error;
}
FS_FREE(header);
FS_FREE(root);
FS_FREE(pUnit);
return E_OK;
error:
FS_FREE(header);
FS_FREE(root);
FS_FREE(pUnit);
return E_ERR;
}
格式化函数实现了之后并不是每次都要被调用的,想一下我们平时使用 U 盘的时候也是只有第一次格式化,之后就再也不需要格式化了
于是再实现一个函数,判断是否格式化过,如果没有格式化则格式化,如果格式化过了,就不再格式化了,函数实现如下,其中添加打印调试信息 printk("format:%d\n", ret);
E_RET FsIsFormatted(void)
{
E_RET ret = E_OK;
FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于文件概要信息(扇区 0)数据处理使用
if(NULL == header)
return E_ERR;
// 读取扇区 0 中的数据,比较 header->magic 中字符串是否等于 FS_MAGIC
// 如果相等,则证明硬盘已经被格式化过;如果不相等,则格式化硬盘
if(E_ERR == FS_READ(0, (U08 *)header))
{
FS_FREE(header);
return E_ERR;
}
if(FALSE == StrCmp(FS_MAGIC, header->magic, -1))
ret = FsFormat();
FS_FREE(header);
return ret;
}
在测试代码之前需要先提供几个接口函数,需要注意的是因为我们只虚拟化了一块硬盘,该硬盘前面被放了操作系统代码本身,所以我们规划 10M 后的空间用于文件系统
#define SYS_SEC_NUM (10*1024*1024/SEC_SIZE) // 人为规定硬盘前 10M 空间用于存放系统本身,10M 后才用于文件系统
#define FS_SEC_NUM (GetHardDiskSectors() - SYS_SEC_NUM) // 文件系统管理的硬盘扇区数 = 硬盘总扇区数 - 操作系统本身占用的扇区数
// 定义文件读写底层接口,文件读写以扇区为单位,顾 buf 大小为 SEC_SIZE
#define FS_WRITE(sn, buf) HardDiskWrite((sn)+SYS_SEC_NUM, (U08 *)(buf))
#define FS_READ(sn, buf) HardDiskRead((sn)+SYS_SEC_NUM, (U08 *)(buf))
#define FS_MALLOC(size) Malloc((size))
#define FS_FREE(p) FS_Free((p))
在 main 函数中调用 FsIsFormatted,第一次运行结果如下,可以看到格式化成功打印提示信息,退出后,再次运行,不再打印 “format” 字符串
按照我们平时的使用习惯,格式化完成之后就可以创建文件了并写入数据了,然而现在我们却无法做到,如果此时创建了文件,那么该文件需要以什么样的方式进行组织管理呢?很显然,目前我们的脑海中并没有对应的逻辑设计,换句话说就是,我们虽然有了根目录(root 文件夹),但是该文件夹下的文件具体是如何表示的我们并不清楚
所以接下来我们要做的工作就是搞清楚根目录(root)目录下是的文件是如何组织的
再次强调一个知识点,根目录就是一个文件夹,文件夹的本质是一个特殊的文件,该文件的内容包含了其目录下的其它文件的文件名,文件大小,文件起始扇区等信息,于是我们设计如下的数据结构来描述这些信息
// 记录一个文件的基本信息
typedef struct FILE_ENTRY
{
U08 name[32]; // 文件名
U32 fileBegin; // 文件的第一个扇区号
U32 fileNum; // 文件占用的扇区数
U32 lastBytes; // 最后一个扇区中的有效数据字节数
E_F_TYPE type; // 文件类型(文件/文件夹)
U32 inSecIdx; // FILE_ENTRY 这个数据结构本身也要存储在硬盘上,inSecIdx 为 FILE_ENTRY 这个数据结构本身存储在扇区号
U32 inSecOff; // FILE_ENTRY 这个数据结构本身也要存储在硬盘上,inSecOff 为 FILE_ENTRY 这个数据结构本身存储在扇区中的偏移量
U32 resered[2]; // 保留
} FILE_ENTRY;
FILE_ENTRY 这个数据结构中 inSecIdx 和 inSecOff 这两个元素需要单独说一下,由于 FILE_ENTRY 这个数据结构本身也要存储在硬盘上,inSecIdx 和 inSecOff 这两个元素就是为了找到 FILE_ENTRY 这个数据结构的位置,inSecIdx 为 FILE_ENTRY 所在的扇区,inSecOff 为 FILE_ENTRY 所在扇区中的偏移位置,于是,通过这两个元素就能准确定位出 FILE_ENTRY 这个数据结构具体处在硬盘中的哪个位置
了解了 FILE_ENTRY 这个数据结构之后,根目录的逻辑结构我们就很好理解了
root 为 FS_ROOT 这个数据结构的实例,表示根目录
File A 和 File B 其实就是 FILE_ENTRY 这个数据结构的一个个实例,表示根目录中的一个个文件
从上图可以看到 FS_ROOT.rootBegin 表示 root 到 File A 之间的箭头;FILE_INFO.fileBegin 表示 File A 到文件数据之间的箭头
假如 File A 后面的文件数据发生改变,那么对应的 File A 中的内容也是需要改变的,于是就得知道 File A 在硬盘中的位置,这也就是需要 inSecIdx 和 inSecOff 这两个成员的原因
到这里,根目录的组织结构我们也有了一定的理解,总结一下,首先,我们有 root 这个根目录,其 rootBegin 指向 root 所在的起始扇区,该扇区中存着一个个的 FILE_ENTRY 数据结构,每一个 FILE_ENTRY 数据结构代表着一个文件信息,再通过 fileBegin 找到文件的数据区
文件系统中一切的操作都要落实到具体的扇区,可以说扇区管理就是实现文件系统的基础。于是,我们进一步思考
先从扇区申请开始,首先在硬盘格式化时候,扇区都是空闲的,它们被依次相连,形成了一个空闲链表,freeBegin 是链表头,在申请扇区时,我们取出 freeBegin 后面的第一个节点(链表头取),为啥是取出第一个节点,因为效率最高呗
有了申请自然也要有归还,过程与申请完全反过来呗,示意图就不再画了,归还时我们采用链表头插的方式,即插入到 freeBegin 后第一个节点
扇区申请与归还的大方向我们应该已经清楚了,然而距离最终的扇区申请/归还函数实现还有一定的距离
扇区操作是一种外存操作,并不仅仅是在内存中操作链表就可以了,还需要写到外部硬盘中,因此需要仔细计算目标物理位置
扇区管理时使用的是相对扇区地址,扇区读写时使用绝对地址
在扇区分配表中,其内元素是从 0 地址开始,依次往后,其对应着文件数据区也是从 0 开始,依次往后,比如我们想对文件数据区的第 0 号扇区进行读写,调用硬盘读写函数接口时,要写入的扇区号肯定不是 0,我们得找到其对应的实际物理扇区号(绝对地址)
绝对地址与相对地址之间的转换关系:绝对地址 = 相对地址 + mapNum + 2
在已知绝对地址(物理扇区号) sn 的情况下:
*
)pUnit) 将绝对地址(物理扇区号) sn 对应的扇区分配表中的管理单元所在的一个扇区数据读到 pUnit 中,通过 pUnit + idxOff 才能准确访问到物理扇区号 sn 对应的扇区分配表中的管理单元好了,可以开始写代码了,直接开始写扇区申请函数,想要申请一个空闲扇区,就要找到空闲扇区的链表头,而链表头存在扇区 0 中。于是先申请一个扇区大小的内存空间,用于存放从扇区 0 中读出的信息,ret = header->freeBegin 即返回空闲链表的第一个节点,header->freeNum-- 表示空闲扇区数减 1,这也很好理解。然后空闲链表头 header->freeBegin 需要指向下一个节点,最后再把修改后的 header 写回扇区 0 中
static U32 AllocSector(void)
{
U32 ret = SEC_END_FLAG;
FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于文件概要信息(扇区 0)数据处理使用
if(NULL == header || SEC_END_FLAG == header->freeBegin)
goto error;
if(E_ERR == FS_READ(0, (U08 *)header)) // 从扇区 0 中读出 header 头信息
goto error;
ret = header->freeBegin; // 返回 freeBegin 链表后的第一个节点
// header->freeBegin = next; // header->freeBegin 指向下一个节点
header->freeNum--; // 空闲扇区数 - 1
if(E_ERR == FS_WRITE(0, (U08 *)header)) // 将 header 头信息写回扇区 0 中
goto error;
FS_FREE(header);
return ret;
error:
FS_FREE(header);
return SEC_END_FLAG;
}
我们看到上面的代码中 header->freeBegin = next; 是被注释起来的,原因就是找不到 next 节点
那么我们现在要做的就是找到下一个节点,header->freeBegin 指向的是一个绝对地址(物理扇区号),而我们的目标是要找到其在扇区分配表中的管理单元对应的位置(相对地址),为什么要找这个管理单元位置,因为这个管理单元中存的就是 next 的值,查找 next 节点的代码实现如下,此过程中扇区分配表中的数据也被改了,所以有 FS_WRITE(secOff+2, (U08 *)pUnit) 数据写回扇区分配表的操作
offset = header->freeBegin - header->mapNum - 2; // 计算 freeBegin 这个绝对地址(物理扇区号)在扇区分配表中对应的管理单元的相对偏移位置
secOff = offset / MAP_UNIT_NUM; // 计算目标扇区对应的管理单元处在扇区分配表中的第几个扇区,secOff+2 才是其绝对地址(物理扇区号)
idxOff = offset % MAP_UNIT_NUM; // 计算目标扇区对应的管理单元处在扇区分配表中某一扇区中的偏移量
if(E_ERR == FS_READ(secOff+2, (U08 *)pUnit)) // 读取目标扇区对应的管理单元所处的整个扇区数据
goto error;
next = *(pUnit + idxOff); // 得到 next 的值
*(pUnit + idxOff) = SEC_END_FLAG; // 由于 (pUnit + idxOff) 这个管理单元对应的扇区被分配出去,所以给其对应的管理单元赋一个无效值
if(E_ERR == FS_WRITE(secOff+2, (U08 *)pUnit)) // 将 pUnit 数据写回扇区分配表中对应的扇区中
goto error;
header->freeBegin = next + 2 + header->mapNum; // header->freeBegin 指向下一个节点,注意 freeBegin 存的是物理扇区号
有了申请自然也要释放归还,释放动作与申请动作正好是反着来的,传入的扇区号是绝对地址(物理扇区号),跟申请扇区中一样的做法,先通过物理扇区号找到扇区分配表中对应的管理单元,找到了这个管理单元后,把它作为一个链表节点,头插到空闲链表 freeBegin 中,以下为完整的扇区释放代码:
static E_RET FreeSector(U32 sn)
{
FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于文件概要信息(扇区 0)数据处理使用
U32 offset = 0;
U32 idxOff = 0;
U32 secOff = 0;
U32* pUnit = (U32 *)FS_MALLOC(SEC_SIZE); // 申请一个扇区大小的内存用于读取扇区分配表中的一个扇区数据
if(NULL == header || SEC_END_FLAG == header->freeBegin)
goto error;
if(E_ERR == FS_READ(0, (U08 *)header)) // 从扇区 0 中读出 header 头信息
goto error;
offset = header->freeBegin - header->mapNum - 2; // 计算 freeBegin 这个绝对地址(物理扇区号)在扇区分配表中对应的管理单元的相对偏移位置
secOff = offset / MAP_UNIT_NUM; // 计算目标扇区对应的管理单元处在扇区分配表中的第几个扇区,secOff+2 才是其绝对地址(物理扇区号)
idxOff = offset % MAP_UNIT_NUM; // 计算目标扇区对应的管理单元处在扇区分配表中某一扇区中的偏移量
if(E_ERR == FS_READ(secOff+2, (U08 *)pUnit)) // 读取目标扇区对应的管理单元所处的整个扇区数据
goto error;
*(pUnit + idxOff) = header->freeBegin - 2 - header->mapNum; // 采用头插的方式,新插入的节点指向原头结点;由于扇区分配表中存的是相对地址,故 header->freeBegin 需要转成相对地址
if(E_ERR == FS_WRITE(secOff+2, (U08 *)pUnit)) // 将 pUnit 数据写回扇区分配表中对应的扇区中
goto error;
header->freeBegin = sn; // header->freeBegin 指向新插入的节点
header->freeNum++; // 空闲扇区数 + 1
if(E_ERR == FS_WRITE(0, (U08 *)header)) // 将 header 头信息写回扇区 0 中
goto error;
FS_FREE(header);
FS_FREE(pUnit);
return E_OK;
error:
FS_FREE(header);
FS_FREE(pUnit);
return E_ERR;
}
完整代码见:fs.c
申请与归还功能函数已经实现了,肯定是要验证一下看看代码是否有问题
写个测试代码:
void FsTest(void)
{
U32 a[5] = {0};
FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE);
U32 i = 0;
// 1. 读取扇区 0 中的数据到 header 中
FS_READ(0, (U08 *)header);
// 2. 测试前先打印一下空闲扇区总数
printk("Free total sectors:%d\n", header->freeNum);
// 3. 连续申请 5 次空闲扇区
for(i = 0; i < 5; i++)
{
a[i] = AllocSector();
}
// 4. 重新读取扇区 0 中的数据到 header 中,打印此时的空闲扇区数
FS_READ(0, (U08 *)header);
printk("After 5 times alloc sectors:%d\n", header->freeNum);
// 5. 连续归还 5 次,打印出每次归还的物理扇区号
for(i = 0; i < 5; i++)
{
printk("a[%d] = %d\n", i, a[i]);
FreeSector(a[i]);
}
// 6. 重新读取扇区 0 中的数据到 header 中,打印此时的空闲扇区数
FS_READ(0, (U08 *)header);
printk("Free sectors:%d\n", header->freeNum);
FS_FREE(header);
}
测试代码运行结果如下:
从运行结果来看,申请开始前和归还后的空闲扇区总数一致,申请 5 次后空闲扇区数正好也减少 5,说明申请归还功能已经实现成功
注意到两次运行的差异了吗?红色框中的数值是反过来的,这是由于我们在申请和归还空闲扇区的时候操作的时候都是直接操作空闲链表头的,自己可以认真琢磨一下
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。