文件系统设计与实现上

// 存储与 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;

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)

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;
}

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;
}

#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))

// 记录一个文件的基本信息
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;

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;
}

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 存的是物理扇区号

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;
}

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);
}