文件系统设计与实现中-阿里云开发者社区

引言

在上一章节中，我们完成了一个扇区的申请与释放工作，这可以说是实现文件系统的最基础工作，有了这个基础，我们才能继续实现文件系统

根目录中创建文件

先找个下手的地方，现在我们只有一个根目录 root，我们先来尝试在 root 目录下创建第一个文件
再次强调一下，目录的本质就是文件，首先我们得申请一个扇区作为根目录 root 的文件数据区，不过与普通文件不的是，普通文件的文件数据区存的就是文件的数据，而文件夹的文件数据区存的是该文件夹下其它文件的基本信息，而这个基本信息指的就是一个个 FILE_ENTRY 数据结构。示意图如下：
每个 FILE_ENTRY 数据结构都代表着一个文件
以上示意图中每 3 个 FILE_ENTRY 为一组，表示一个扇区可以存放 3 个 FILE_ENTRY，当一个扇区放满后，就需要再申请一个扇区用于存放 FILE_ENTRY，实际上这只是示意图，一个扇区并不仅仅能放 3 个 FILE_ENTRY，而是能放 SEC_SIZE / sizeof(FILE_ENTRY) 这么多个。关于 FILE_ENTRY 具体数据类型可以回顾上一章节
先创建的文件就在前面，后创建的文件就放在后面，这个没啥说的，root 目录下文件数量过多时，一个扇区不够存放时，就需要再申请一个扇区继续存放，所以当我们创建一个文件时，需要先找到最后一个扇区，然后再最后一个扇区中写入新创建文件的 FILE_ENTRY 数据结构
当然了，最后一个扇区剩余空间可能不够一个 FILE_ENTRY 了，那么我们还需要再申请一个新的扇区才行
接下来将要实现的根目录下创建文件完整代码见：fs.c
让我们开始愉快的写代码吧，实现一个在根目录 root 下创建文件的函数，名为 CreatFileInRoot，函数实现框架如下，其核心功能分 3 步，第一步：查找文件是否已经存在，如果不存在，方可创建该文件；第二步：检查 root 文件数据区的最后一个扇区空间是否足够，如果不够，需再申请一个空闲扇区；第三步：找到 root 文件数据区的最后一个扇区的末尾处；第四步：创建一个 FILE_ENTRY 数据结构并初始化，并将其写到最后一个扇区的末尾处

E_RET CreatFileInRoot(const U08* name)
{
    E_RET ret = E_ERR;
    FS_ROOT* root = (FS_ROOT *)FS_MALLOC(SEC_SIZE);         // 申请一个扇区大小的内存用于根目录信息（扇区 1）数据处理使用
    if(NULL == root)
        goto error;
    if(E_ERR == FS_READ(1, (U08 *)root))                    // 将扇区 1 中数据读到 root 内存中
        goto error;
    // 1. 查找文件是否已经存在，如果不存在，方可创建该文件；
    // 2. 检查 root 文件数据区的最后一个扇区空间是否足够，如果不够，需再申请一个空闲扇区
    // 3. 找到 root 文件数据区的最后一个扇区的数据末尾处
    // 4. 创建一个 FILE_ENTRY 数据结构并初始化，并将其写到最后一个扇区的数据末尾处
error:
    FS_FREE(root);
    return ret;
}

先来实现第一步，写一个查找文件函数 FindInRoot，然而第一步也不是一下子就能实现的，这第一步中又有 ①②③④ 这 4 个子功能需要实现

static FILE_ENTRY* FindInRoot(const U08* name)
{
    FILE_ENTRY* ret = NULL;
    U32 i = 0;
    FS_ROOT* root = (FS_ROOT *)FS_MALLOC(SEC_SIZE);         // 申请一个扇区大小的内存用于根目录信息（扇区 1）数据处理使用
    if(NULL == root)
        goto error;
    if(E_ERR == FS_READ(1, (U08 *)root))                    // 将扇区 1 中数据读到 root 内存中
        goto error;
    if(0 == root->rootNum || SEC_END_FLAG == root->rootBegin)
        goto error;
    for(i = 0; i < root->rootNum-1; i++)                    // 遍历所有扇区（除最后一个扇区）
    {
        // ① 读出根目录 root 指向的文件数据区的第一个扇区中的数据
        // ② 遍历这个扇区，利用字符串比较函数查找其中是否有 name == FILE_ENTRY.name
        // ③ 如果相等，则说明找到了，返回 FILE_ENTRY 数据结构首地址，并且 break 跳出循环
        // ④ 如果没有，则读取下一个扇区，重复上面的查询动作
    }   
    if(NULL == ret)                                         // 最后一个扇区因为不满所以要单独处理，ret == NULL，说明前面没有找到
    {
        // ① 读出最后一个扇区中的数据
        // ② 遍历这个扇区，查找其中是否有 name == FILE_ENTRY.name
        // ③ 如果相等，则说明找到了，返回 FILE_ENTRY 数据结构首地址，并且 break 跳出循环
    }
    FS_FREE(root);
    return ret;
error:
    FS_FREE(root);
    return NULL;
}

第 ④ 步中需要查找下一个扇区的功能，我们先把这个功能用函数实现一下吧

static U32 NextSector(U32 sn)
{
    U32 next = SEC_END_FLAG;
    U32 offset = 0;
    U32 idxOff = 0;
    U32 secOff = 0;
    FS_HEADER* header = (FS_HEADER *)FS_MALLOC(SEC_SIZE);   // 申请一个扇区大小的内存用于文件概要信息（扇区 0）数据处理使用
    U32* pUnit = (U32 *)FS_MALLOC(SEC_SIZE);                // 申请一个扇区大小的内存用于读取扇区分配表中的一个扇区数据
    if(NULL == header || NULL == pUnit || SEC_END_FLAG == sn)
        goto error;
    if(E_ERR == FS_READ(0, (U08 *)header))                  // 从扇区 0 中读出 header 头信息
        goto error;
    // 计算物理扇区号 sn 在扇区分配表中的位置
    offset = sn - header->mapNum - 2;                       // 计算 sn 这个绝对地址（物理扇区号）在扇区分配表中对应的管理单元的相对偏移位置
    if(offset >= header->mapNum)                            // sn 范围超限
        return E_ERR;
    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);                               // 得到下一个扇区的相对地址
    if(SEC_END_FLAG == next)                                // 如果已经是最后一个扇区了，则直接返回 SEC_END_FLAG
        goto error;
    next = next + header->mapNum + 2;                       // 由相对地址计算出绝对地址（物理扇区号）
error:
    FS_FREE(header);
    FS_FREE(pUnit);
    return next;
}

有了 NextSector 函数后，其它 ①②③ 也就比较容易实现了，其实现细节如下：

static FILE_ENTRY* FindInRoot(const U08* name)
{
    ...
    next = root->rootBegin;                                 // next 指向起始扇区号
    for(i = 0; i < root->rootNum-1; i++)                    // 遍历所有扇区（除最后一个扇区）
    {
        if(E_ERR == FS_READ(next, buf))                     // 将扇区中的数据读到 buf 缓存中
            goto error;
        for(j = 0; j < SEC_SIZE/sizeof(FILE_ENTRY); j++)    // 以 FILE_ENTRY 为单位遍历
        {
            fe  = (FILE_ENTRY *)buf + j;
            if(TRUE == StrCmp(fe->name, name, -1))          // 如果有 name == FILE_ENTRY.name 则 FILE_ENTRY 返回首地址
            {
                ret = fe;
                break;
            }
        }
        if(NULL != ret)                                     // 如果已经找到了，则直接退出循环
            break;
        next = NextSector(next);                            // 指向下一个扇区
        if(SEC_END_FLAG == next)
            goto error;
    }   
    if(NULL == ret)                                         // 最后一个扇区因为不满所以要单独处理，ret == NULL，说明前面没有找到
    {
        if(E_ERR == FS_READ(next, buf))                     // 将扇区中的数据读到 buf 缓存中
            goto error;
        for(j = 0; j < root->lastBytes/sizeof(FILE_ENTRY); j++)    // 以 FILE_ENTRY 为单位遍历
        {
            fe  = (FILE_ENTRY *)buf + j;
            if(TRUE == StrCmp(fe->name, name, -1))          // 如果有 name == FILE_ENTRY.name 则返回 FILE_ENTRY 首地址
            {
                ret = fe;
                break;
            }
        }
    }
    ...
}

继续实现 CreatFileInRoot 函数，第二步：检查 root 文件数据区的最后一个扇区空间是否足够，如果不够，需再申请一个空闲扇区

if(0 == root->rootNum)                                  // 如果根目录尚未分配一个扇区，则分配一个扇区作为第一个扇区
{
    sn =  AllocSector();                                // 申请一个空闲扇区
    if(SEC_END_FLAG == sn)
        goto error;
    root->rootBegin = sn;
    root->rootNum++;
    root->lastBytes = 0;
    if(E_ERR == FS_WRITE(1, (U08 *)root))               // 将 root 数据写回扇区 1
        goto error;
}
else
{
    if(root->lastBytes + sizeof(FILE_ENTRY) > SEC_SIZE) // 如果最后一个扇区的空余数据区不够一个 FILE_ENTRY，则申请一个空闲扇区并插到末尾
    {
        sn =  AllocSector();
        if(SEC_END_FLAG == sn)
            goto error;
        if(E_ERR == AddToLast(root->rootBegin, sn))     // 将新申请的扇区号 sn 添加到根目录扇区链表末尾
            goto error;
        root->rootNum++;
        root->lastBytes = 0;
        if(E_ERR == FS_WRITE(1, (U08 *)root))           // 将 root 数据写回扇区 1
            goto error;
      }
  }

第三步：找到 root 文件数据区的最后一个扇区的数据末尾处

// 利用 NextSector 函数找到根目录 root 的最后一个扇区的扇区，并读出最后一个扇区中的数据
next = root->rootBegin;
while(next != SEC_END_FLAG)
{
    last = next;
    next = NextSector(next);
}
if(SEC_END_FLAG == last)
    goto error;
buf = (U08 *)FS_MALLOC(SEC_SIZE);
if(NULL == buf)
    goto error;
if(E_ERR == FS_READ(last, buf))                        
    goto error;

最后第四步：创建一个 FILE_ENTRY 数据结构并初始化，并将其写到最后一个扇区的数据末尾处

fe = (FILE_ENTRY *)(buf + root->lastBytes);             // fe 指向最后一个扇区的数据末尾处
StrCpy(fe->name, name, -1);
fe->fileBegin = SEC_END_FLAG;
fe->fileNum = 0;
fe->lastBytes = 0;
fe->type = E_FILE;
fe->inSecIdx = last;
fe->inSecOff = root->lastBytes;
if(E_ERR == FS_WRITE(last, buf))                        // 将 buf 中数据写回硬盘中              
    goto error;
root->lastBytes += sizeof(FILE_ENTRY);
if(E_ERR == FS_WRITE(1, (U08 *)root))                   // 将 root 中数据写回硬盘中              
    goto error;

最后肯定测试一下写的代码有没有问题

// 测试创建文件
void FsTest(void)
{
    printk("creat:%d\n", CreatFileInRoot("abc.txt"));
    printk("creat:%d\n", CreatFileInRoot("abc.txt"));
    printk("creat:%d\n", CreatFileInRoot("abc.txt"));
    printk("creat:%d\n", CreatFileInRoot("123.txt"));
    printk("creat:%d\n", CreatFileInRoot("1234.txt"));
    printk("creat:%d\n", CreatFileInRoot("123.txt"));
    FILE_ENTRY* fe = NULL;
    fe = FindInRoot("123.txt");
    if(fe)  printk("%s\n", fe->name);
    else    printk("No file\n");
    fe = FindInRoot("444.txt");
    if(fe)  printk("%s", fe->name);
    else    printk("No file\n");
    fe = FindInRoot("1234.txt");
    if(fe)  printk("%s", fe->name);
    else    printk("No file\n");
}

测试结果：从打印信息中我们可以看到，如果一个文件已经创建过，则再次创建就会失败，并且文件查找函数功能正常

根目录中删除文件

有创建文件自然就要有删除文件，于是，接下来的工作就有了，就是：如何在根目录中删除文件
在实现了创建文件的基础上，删除文件的思路我们应该比较容易想到，第一步，根据文件名在根目录数据链表中遍历查找 FILE_ENTRY.name ，第二步，当查找成功时，从数据链表中删除找到的 FILE_ENTRY 数据结构
上面的查找删除工作在内存中确实没啥毛病，感觉好像很简单，然而，FILE_ENTRY 这个数据结构是存储在硬盘上的，那么，我们如何从硬盘上抹除这块数据呢？
进一步思考，假如我们抹除了对应的 FILE_ENTRY 数据区，那么这个位置就被空出来了，这块空出来的地方又该怎么处理
硬盘的管理是以扇区为基本单位的，而空出来的 FILE_ENTRY 数据区仅仅只使用一个扇区中的一小部分这块区域位置又不怎么好标记，而且我们希望尽可能的将一个扇区全部使用完，这样也能减少扇区读写次数，于是我们想到下面的办法
将数据链表中最后一个 FILE_ENTRY 搬到被删除的 FILE_ENTRY 处，原本倒数第二个 FILE_ENTRY 此时就变成了最后一个 FILE_ENTRY，示意图如下：
开始写代码，先写出来框架思路，然后再具体实现

E_RET DeleteFileInRoot(const U08* name)
{
    // 1. 查找文件是否已经存在，只有文件存在方可删除
    // 2. 释放删除文件相关的全部扇区
    // 2. 找到最后一个 FILE_ENTRY，替换掉要删除的 FILE_ENTRY
    // 3. 检查 lastBytes 是否为 0，如果为 0，则需要删除最后一个扇区
}

先提供完整的代码：fs.c
首先实现第一步，查找文件，这个在前面的 FindInRoot 函数已经实现好了
不过删除文件还有一个前提，那就是文件关闭的状态下才能删除，然而文件打开关闭我们还没有实现，所以暂时先忽略这一点
第二步：释放删除文件的所有相关扇区，这个功能并没有什么复杂的地方，利用前面已经实现过的 NextSector 遍历所有相关扇区，利用 FreeSector 函数释放扇区

static E_RET FreeFile(U32 secBegin)
{
    U32 next = secBegin;
    while (SEC_END_FLAG != next)
    {
        if(E_ERR == FreeSector(next))
            goto error;
        next = NextSector(next);
    }
    return E_OK;
error:
    return E_ERR;
}

第三步：找到最后一个 FILE_ENTRY 的基址，将最后一个 FILE_ENTRY 拷贝到删除的 FILE_ENTRY 处

last_fe = (FILE_ENTRY *)(buf + root->lastBytes - sizeof(FILE_ENTRY));
if(E_ERR == FS_READ(last, buf))                         // 将扇区 last 中数据读到 buf 缓存中
    goto error;
buf2 = (U08 *)FS_MALLOC(SEC_SIZE);                      // 申请 SEC_SIZE 大小的内存
if(NULL == buf2)
    goto error;
if(E_ERR == FS_READ(fe->inSecIdx, buf2))                // 将 fe 所在的整个扇区数据读到 buf2 缓存中
    goto error;
tmp = (FILE_ENTRY *)(buf2+fe->inSecOff);                // tmp 指向要删除的 FILE_ENTRY 
StrCpy(tmp->name, last_fe->name, -1);
tmp->fileBegin = last_fe->fileBegin;
tmp->fileNum = last_fe->fileNum;
tmp->lastBytes = last_fe->lastBytes;
tmp->type = last_fe->type;
if(E_ERR == FS_WRITE(last_fe->inSecIdx, buf))           // 将 buf 中数据写回硬盘中  
    goto error;
if(E_ERR == FS_WRITE(tmp->inSecIdx, buf2))              // 将 buf2 中数据写回硬盘中  
    goto error;

第四步：检查 lastBytes 是否为 0，如果为 0，则需要删除最后一个扇区

root->lastBytes -= sizeof(FILE_ENTRY);
if(E_ERR == FS_WRITE(1, (U08 *)root))                   // 将 root 缓冲中数据写回硬盘中
    goto error;
if(0 == root->lastBytes)
{
    root->rootNum--;
    FreeSector(last);                                   // 释放最后一个扇区
    prev = FindPrev(root->rootBegin, last);             // 找到 last 节点的上一个节点
    if(SEC_END_FLAG == prev)
        goto error;
    // 计算物理扇区号 prev 在扇区分配表中的位置
    header = (FS_HEADER *)FS_MALLOC(SEC_SIZE);          // 申请一个扇区大小的内存用于文件概要信息（扇区 0）数据处理使用
    if(NULL == header)
        goto error;
    offset = prev - header->mapNum - 2;                 // 计算 prev 这个绝对地址（物理扇区号）在扇区分配表中对应的管理单元的相对偏移位置
    if(offset >= header->mapNum)                        // prev 范围超限
        goto error;
    secOff = offset / MAP_UNIT_NUM;                     // 计算目标扇区对应的管理单元处在扇区分配表中的第几个扇区，secOff+2 才是其绝对地址（物理扇区号）
    idxOff = offset % MAP_UNIT_NUM;                     // 计算目标扇区对应的管理单元处在扇区分配表中某一扇区中的偏移量
    pUnit = (U32*)FS_MALLOC(SEC_SIZE);                  // 申请一个扇区大小的内存用于扇区分配表数据处理
    if(NULL == pUnit)
        goto error;
    if(E_ERR == FS_READ(secOff, (U08 *)pUnit))          // 将扇区号 prev 对应的管理单元所在的整个扇区读到 pUnit 缓冲中
        goto error;
    *(pUnit + idxOff) = SEC_END_FLAG;                   // 置结束标志
    if(E_ERR == FS_WRITE(secOff, (U08 *)pUnit))         // 将 pUnit 缓冲中数据写回硬盘中
        goto error;
}
if(E_ERR == FS_WRITE(1, (U08 *)root))                   // 将 root 缓冲中数据写回硬盘中
    goto error;

功能实现完成，接下来就是测试了，我们简单看一测试代码功能：首先在根目录中创建连续创建 “1.txt”、“2.txt”、“3.txt”、“4.txt” 和 “5.txt” 共 5 个文件，然后删除文件 “2.txt”，接下来打印出根目录中全部文件名，再删除文件 “3.txt”，最后再打印出根目录下得全部文件名

void FsTest(void)
{
    printk("creat:%d\n", CreatFileInRoot("1.txt"));
    printk("creat:%d\n", CreatFileInRoot("2.txt"));
    printk("creat:%d\n", CreatFileInRoot("3.txt"));
    printk("creat:%d\n", CreatFileInRoot("4.txt"));
    printk("creat:%d\n", CreatFileInRoot("5.txt"));
    printk("---------------------\n");
    DeleteFileInRoot("2.txt");
    // 打印根目录下文件名
    FILE_ENTRY* fe = NULL;
    int i = 0;
    FS_ROOT* root = (FS_ROOT *)FS_MALLOC(SEC_SIZE);
    U08* buf = (U08 *)FS_MALLOC(SEC_SIZE);
    // 因为 root 下文件不多，只读一个扇区就可以了
    FS_READ(1, (U08 *)root);
    FS_READ(root->rootBegin, (U08 *)buf);
    for(i = 0; i < root->lastBytes/sizeof(FILE_ENTRY); i++)    // 以 FILE_ENTRY 为单位遍历
    {
        fe  = (FILE_ENTRY *)buf + i;
        printk("%s\n", fe->name);
    }
    printk("---------------------\n");
    DeleteFileInRoot("3.txt");
    // 打印根目录下文件名
    // 因为 root 下文件不多，只读一个扇区就可以了
    FS_READ(1, (U08 *)root);
    FS_READ(root->rootBegin, (U08 *)buf);
    for(i = 0; i < root->lastBytes/sizeof(FILE_ENTRY); i++)    // 以 FILE_ENTRY 为单位遍历
    {
        fe  = (FILE_ENTRY *)buf + i;
        printk("%s\n", fe->name);
    }
}

测试结果：第一次删除文件 “2.txt” 后，遍历根目录下文件打印得到 “1.txt”、“5.txt”、“3.txt”、“4.txt”，从中可以看到 “2.txt” 已被删除，最后一个 “5.txt” 替代了 “2.txt” ，符合我们的 DeleteFileInRoot 程序预期；第二次删除文件 “3.txt” 也同样符合预期

根目录中重命名文件

接下来我们来实现一个文件重命名的功能，这个功能其实没啥说的，就是找到要修改的文件的 FILE_ENTRY，然后修改其中的 name 属性即可，直接贴上完整函数

E_RET RenameFileInRoot(const U08* old, const U08* new)
{
    E_RET ret = E_ERR;
    FILE_ENTRY* fe = NULL;
    U08* buf = NULL;
    // 检查参数合法性
    if(NULL == old || NULL == new)
        goto error;
    fe = FindInRoot(new);
    if(NULL != fe)                                          // 根目录下已有名为 new 的文件了
        goto error;
    fe = FindInRoot(old);
    if(NULL == fe)                                          // 要被替换的文件名不存在
        goto error;
    // 找到 old 文件对应的 FILE_ENTRY 所在位置，从硬盘中读取整个扇区，修改其中 name，然后再写回硬盘
    buf = (U08 *)FS_MALLOC(SEC_SIZE);
    if(NULL == buf)
        goto error;
    if(E_ERR == FS_READ(fe->inSecIdx, buf))
        goto error; 
    StrCpy(((FILE_ENTRY *)(buf + fe->inSecOff))->name, new, -1);
    if(E_ERR == FS_WRITE(fe->inSecIdx, buf))
        goto error;
error:
    FS_FREE(fe);
    FS_FREE(buf);
    return ret;
}

写个代码测试一下：

void FsTest(void)
{
    printk("creat:%d\n", CreatFileInRoot("1.txt"));
    printk("creat:%d\n", CreatFileInRoot("2.txt"));
    printk("creat:%d\n", CreatFileInRoot("3.txt"));
    printk("creat:%d\n", CreatFileInRoot("4.txt"));
    printk("creat:%d\n", CreatFileInRoot("5.txt"));
    RenameFileInRoot("2.txt", "new.txt");
    // 打印根目录下文件名
    FILE_ENTRY* fe = NULL;
    int i = 0;
    FS_ROOT* root = (FS_ROOT *)FS_MALLOC(SEC_SIZE);
    U08* buf = (U08 *)FS_MALLOC(SEC_SIZE);
    // 因为 root 下文件不多，只读一个扇区就可以了
    FS_READ(1, (U08 *)root);
    FS_READ(root->rootBegin, (U08 *)buf);
    for(i = 0; i < root->lastBytes/sizeof(FILE_ENTRY); i++)    // 以 FILE_ENTRY 为单位遍历
    {
        fe  = (FILE_ENTRY *)buf + i;
        printk("%s\n", fe->name);
    }
}

从下面的测试结果中我们可以看到，“2.txt” 被成功改为了 “new.txt”

文件系统设计与实现中

引言

根目录中创建文件

根目录中删除文件

根目录中重命名文件

热门文章

最新文章

相关课程

相关电子书