本篇对应书籍第十四章14.1--14.4的内容
文件系统简介
本章内容有点长，故分为三个部分来写，这里学习的目的是了解操作系统的核心思路
inode、间接块索引表、文件控制块 FCB 简介
硬盘是低速设备，为了避免频繁访问，所以操作系统要等要读写的数据有足够大小的时候再进行访问
这个足够大小的数据就是块（Windows下叫簇），块由多块扇区组成，块大小是扇区的整数倍，是文件系统的读写单位，当一个块装不下时，会通过多个快来装
FAT（文件分配表）文件系统：在此系统存储的文件，所有文件都用链式结构来组织、跟踪文件的所有快，每个块的最后都链着下一个块的内容，如图：
但是要访问其中一个块的时候，必须得从头来索引，反而使得对硬盘的访问更加频繁了，后来微软推出了NTFS
Unix 系统的索引结构是 inode，这里我们要实现的也是 inode
inode 文件系统采用索引结构来组织文件，避免了FAT的缺点（访问某一数据块要从头把前面所有数据块都访问一遍）
文件系统为每个文件的所有块都建立一个索引表（块地址数组），数组下标是文件块索引，第n个数组元素指向文件中第n个块
inode必须为每个文件都单独配备一个这样的元信息结构，一个文件对应一个inode，结构如图：
使用索引结构会出现一个问题，就是遇到大文件的时候，索引结构也会变大，UNIX 采用了折中的方法，让索引结构固定长度却又可以扩展变大，那就是采用了多级间接索引表来实现：
inode 逻辑结构中，是用了12个直接块指针，直接指向数据块，最后三个位置分别是一级二级三级间接块索引指针：
- 一级则指向一个256个元素的索引表，索引表每个索引项指向一个数据块
- 二级则指向一个256个元素的索引表，索引表每个索引项指向下一个256个元素的索引表，然后才是指向数据块
- 三级同理
文件系统为了方便管理文件，都会给每个文件一些用于管理的辅助结构，这种用于管理控制的文件信息的数据结构称为FCB，File Control Block，文件控制块，inode也是这种结构
这里我们将要实现上图灰色的部分，关于权限就不管了
从某种意义上来说，inode就等同于文件，找到inode就能找到文件，为了方便管理，分区中的所有文件的inode通过一个大的表格来维护，inode_table，本质上是个数组，下标则是inode的编号
分区的利用率分为inode利用率和硬盘空间利用率两种，可用df -i命令查看
目录项与目录简介
只要有inode，文件系统就能找到指定的文件实体，但是用户进行操作需要通过文件名来更加直观的进行操作
由于文件在查找过程中，肯定位于某个目录，因此文件名应存储在一个与目录相关的地方
目录也是一种文件，也有inode，为了作为区分，接下来用的文件分别叫目录文件和普通文件，能作为区分的只有数据块的内容了：
- 该 inode 表示的是普通文件，此 inode 指向的数据块中的内容应该是普通文件自己的数据。
- 如果该 inode 表示的是目录文件，此 inode 指向的数据块中的内容应该是该目录下的目录项。
不管是文件还是目录，都存在与根目录下，目录文件的内容是目录项，目录项相当于是一个表格，记录该目录下的文件信息：inode编号，文件名，文件类型，一方面在这里区分开来目录和文件类型，还将inode对应上了文件名，举例如图：
有了目录项之后，通过文件名找文件数据块的流程是：
- 在目录中找到文件名所在目录项
- 从目录项中获取inode编号
- 用inode编号作为inode数组下标，找到inode
- 从该inode中获取数据块地址，读取数据块
inode是描述一个文件的元信息，存在分区中的一个大的表中，通过编号进行索引
目录项也可以称为文件控制块
查找流程图：
超级块
之前讲了inode和目录项的作用，那么inode数组存放在哪里，根目录在哪里，这里就要补充一个概念了，超级块
超级块是保存文件系统元信息的元信息，实现一个超级块至少要有这些信息：
用位图管理空闲块使用情况
超级块是文件系统元信息的“配置文件”，它是在为分区创建文件系统时创建的，所有有关文件系统元信息的配置都在超级块中，因此超级块的位置和大小不能再被“配置”了，必须是固定的，它被固定存储在各分区的第2个扇区，通常是占用一个扇区的大小，具体大小与实际文件系统类型为准。
文件系统布局
典型的文件系统布局如图所示：
到此，理论部分结束，该开始实践部分了
创建文件系统
本节在硬盘hd80M.img的各分区创建文件系统
创建超级块、i节点、目录项
首先第一件工作还是，创建基础数据结构
fs/super_block.h
#ifndef __FS_SUPER_BLOCK_H
#define __FS_SUPER_BLOCK_H
#include "stdint.h"
// 超级块
struct super_block {
uint32_t magic; // 用来标识文件系统类型
uint32_t sec_cnt; // 本分区总共的扇区数
uint32_t inode_cnt; // 本分区中inode数量
uint32_t part_lba_base; // 本分区的起始lba地址
uint32_t block_bitmap_lba; // 块位图本身起始扇区地址
uint32_t block_bitmap_sects; // 扇区位图本身占用的扇区数量
uint32_t inode_bitmap_lba; // inode位图起始扇区lba地址
uint32_t inode_bitmap_sects; // inode位图占用的扇区数量
uint32_t inode_table_lba; // inode表起始扇区lba地址
uint32_t inode_table_sects; // inode表占用的扇区数量
uint32_t data_start_lba; // 数据区开始的第一个扇区号
uint32_t root_inode_no; // 根目录所在的inode号
uint32_t dir_entry_size; // 目录项大小
uint8_t pad[460]; // 加上 460 字节, 凑够 512 字节 1 扇区大小
} __attribute__ ((packed));//防止编译器对齐而填充空隙
#endif
fs/inode.h
// inode 结构
struct inode {
uint32_t i_no; // inode 编号
uint32_t i_size;
uint32_t i_open_cnts; // 记录此文件被打开的次数
bool write_deny; // 写文件不能并行, 进程写文件前检查此标识
// i_sectors[0-11]是直接块, i_sectors[13]用来存储一级间接块指针
uint32_t i_sectors[13];
struct list_elem inode_tag; // 用于加入已打开的 inode 队列
};
#endif
这里只实现1级间接块索引表
fs/dir.h
#define MAX_FILE_NAME_LEN 16 // 最大文件名长度
// 目录结构
struct dir {
struct inode* inode;
uint32_t dir_pos; // 记录在目录内的偏移
uint8_t dir_buf[512]; // 目录的数据缓冲
};
// 目录项结构
struct dir_entry {
char filename[MAX_FILE_NAME_LEN]; // 普通文件或目录名称
uint32_t i_no; // 普通文件或目录对应的 inode 编号
enum file_types f_type; // 文件类型
};
#endif
具体是怎么用的之后再说，文件类型定义在fs.h中了
fs/fs.h
#define MAX_FILES_PER_PART 4096 // 每个分区所支持最大创建的文件数
#define BITS_PER_SECTOR 4096 // 每扇区的位数
#define SECTOR_SIZE 512 // 扇区字节大小
#define BLOCK_SIZE SECTOR_SIZE // 块字节大小
// 文件类型
enum file_types {
FT_UNKNOWN, // 不支持的文件类型
FT_REGULAR, // 普通文件
FT_DIRECTORY // 目录
};
#endif
创建文件系统
创建文件系统也就是高级格式化分区
fs/fs.c 格式化分区
代码分3部分，第1部分：
// 格式化分区, 也就是初始化分区的元信息, 创建文件系统
static void partition_format(struct partition* part) {
// 为方便实现, 一个块大小是一扇区
uint32_t boot_sector_sects = 1;
uint32_t super_block_sects = 1;
// I 结点位图占用的扇区数, 最多支持 4096 个文件
uint32_t inode_bitmap_sects = DIV_ROUND_UP(MAX_FILES_PER_PART, BITS_PER_SECTOR); // inode 位图占用的扇区数
uint32_t inode_table_sects = DIV_ROUND_UP(((sizeof(struct inode) * MAX_FILES_PER_PART)), SECTOR_SIZE); // inode_table 数组占用的扇区数
uint32_t used_sects = boot_sector_sects + super_block_sects + inode_bitmap_sects + inode_table_sects;
uint32_t free_sects = part->sec_cnt - used_sects; // 分区总扇区 - 使用的扇区 = 可用的扇区
// 简单处理块位图占据的扇区数
uint32_t block_bitmap_sects;
block_bitmap_sects = DIV_ROUND_UP(free_sects, BITS_PER_SECTOR);
// block_bitmap_bit_len 位图中位的长度, 可用块的数量
uint32_t block_bitmap_bit_len = free_sects - block_bitmap_sects;
block_bitmap_sects = DIV_ROUND_UP(block_bitmap_bit_len, BITS_PER_SECTOR);
// 超级块初始化
struct super_block sb;
sb.magic = 0x19590318;
sb.sec_cnt = part->sec_cnt;
sb.inode_cnt = MAX_FILES_PER_PART;
sb.part_lba_base = part->start_lba;
// 第 0 块是引导块, 第 1 块是超级块
sb.block_bitmap_lba = sb.part_lba_base + 2;
sb.block_bitmap_sects = block_bitmap_sects;
sb.inode_bitmap_lba = sb.block_bitmap_lba + sb.block_bitmap_sects;
sb.inode_bitmap_sects = inode_bitmap_sects;
sb.inode_table_lba = sb.inode_bitmap_lba + sb.inode_bitmap_sects;
sb.inode_table_sects = inode_table_sects;
sb.data_start_lba = sb.inode_table_lba + sb.inode_table_sects;
sb.root_inode_no = 0; // 根目录的inode编号是 0
sb.dir_entry_size = sizeof(struct dir_entry);
printk("%s info:\n", part->name);
printk(" magic:0x%x\n", sb.magic);
printk(" part_lba_base:0x%x\n", sb.part_lba_base);
printk(" all_sectors:0x%x\n", sb.sec_cnt);
printk(" inode_cnt:0x%x\n", sb.inode_cnt);
printk(" block_bitmap_lba:0x%x\n", sb.block_bitmap_lba);
printk(" block_bitmap_sectors:0x%x\n", sb.block_bitmap_sects);
printk(" inode_bitmap_lba:0x%x\n", sb.inode_bitmap_lba);
printk(" inode_bitmap_sectors:0x%x\n", sb.inode_bitmap_sects);
printk(" inode_table_lba:0x%x\n", sb.inode_table_lba);
printk(" inode_table_sectors:0x%x\n", sb.inode_table_sects);
printk(" data_start_lba:0x%x\n", sb.data_start_lba);
创建文件系统就是创建文件系统所需要的元信息，这包括超级块位置及大小、空闲块位图的位置及大小、 inode位图的位置及大小、inode数组的位置及大小、 空闲块起始地址、 根目录起始地址。 创建步骤如下：
- 根据分区part大小， 计算分区文件系统各元信息需要的扇区数及位置。
- 在内存中创建超级块，将以上步骤计算的元信息写入超级块。
- 将超级块写入磁盘。
- 将元信息写入磁盘上各自的位置。
- 将根目录写入磁盘。
第1部分代码完成了步骤中的1和2
第二部分代码：
struct disk* hd = part->my_disk;
// 1 将超级块写入本分区的 1 扇区
ide_write(hd, part->start_lba+1, &sb, 1);
printk(" super_block_lba:0x%x\n", part->start_lba+1);
// 找出数据量最大的元信息, 用其尺寸做存储缓冲区
uint32_t buf_size = (sb.block_bitmap_sects >= sb.inode_bitmap_sects ? sb.block_bitmap_sects : sb.inode_bitmap_sects);
buf_size = (buf_size >= sb.inode_table_sects ? buf_size : sb.inode_table_sects) * SECTOR_SIZE;
uint8_t* buf = (uint8_t*)sys_malloc(buf_size);
// 2 将块位图初始化并写入 sb.block_bitmap_lba
// 初始化块位图 block_bitmap
buf[0] |= 0x01; // 第 1 个块预留给根目录, 位图中先占位
uint32_t block_bitmap_last_byte = block_bitmap_bit_len / 8;
uint8_t block_bitmap_last_bit = block_bitmap_bit_len % 8;
// last_size 是位图所在最后一个扇区中, 不足一扇区的其余部分
uint32_t last_size = SECTOR_SIZE - (block_bitmap_last_byte % SECTOR_SIZE);
// 1 先将位图最后一字节到其所在的扇区的结束全置为 1, 即超出实际块数的部分直接置为已占用
memset(&buf[block_bitmap_last_byte], 0xff, last_size);
// 2 再将上一步中覆盖的最后一字节内的有效位重新置 0
uint8_t bit_idx = 0;
while (bit_idx <= block_bitmap_last_bit) {
buf[block_bitmap_last_byte] &= ~(1 << bit_idx++);
}
ide_write(hd, sb.block_bitmap_lba, buf, sb.block_bitmap_sects);
此处在做的工作是步骤3和4的内容，将超级块写入本分区的1扇区，0扇区引导扇区虽然不用，但是得空出来
后面要写入硬盘的内容很大，需要单独申请缓冲区来存放数据，缓冲区的选择由最大的元信息而定
块位图初始化并写入，块位图初始化则是将最后一个扇区中不属于空闲块的位初始化为1：
跟踪资源状态是通过位图来决定了，创建文件系统相当于创建各种资源的位图，位图在内存中创建好，然后再持久化到硬盘中去，此时创建的分区位图不是现在用，挂载分区前，内存里没有位图，挂载时就需要从分区中读取位图到内存中，因为free_sects是通过向上取整得到的，所以就难免有一些非位图资源的数据，所以将这些部位初始化为1即可
第三部分代码：
// 3 将 inode 位图初始化并写入 sb.inode_bitmap_lba
// 先清空缓冲区
memset(buf, 0, buf_size);
buf[0] |= 0x1; // 第 0 个 inode 分给了根目录
ide_write(hd, sb.inode_bitmap_lba, buf, sb.inode_bitmap_sects);
// 4 将 inode 数组初始化并写入 sb.inode_table_lba
// 准备写 inode_table 中的第 0 项, 即根目录所在的 inode
memset(buf, 0, buf_size);
struct inode* i = (struct inode*)buf;
i->i_size = sb.dir_entry_size * 2; // . 和 ..
i->i_no = 0; // 根目录占 inode 数组中第 0 个 inode
i->i_sectors[0] = sb.data_start_lba;
ide_write(hd, sb.inode_table_lba, buf, sb.inode_table_sects);
// 5 将根目录写入 sb.data_start_lba
// 写入根目录的两个目录项 . 和 ..
memset(buf, 0, buf_size);
struct dir_entry* p_de = (struct dir_entry*)buf;
// 初始化当前目录 .
memcpy(p_de->filename, ".", 1);
p_de->i_no = 0;
p_de->f_type = FT_DIRECTORY;
p_de++;
// 初始化当前目录父目录 ..
memcpy(p_de->filename, "..", 2);
p_de->i_no = 0; // 根目录的父目录依然是根目录自己
p_de->f_type = FT_DIRECTORY;
// sb.data_start_lba 已经分配给了根目录, 里面是根目录的目录项
ide_write(hd, sb.data_start_lba, buf, 1);
printk(" root_dir_lba:0x%x\n", sb.data_start_lba);
printk("%s format done\n", part->name);
sys_free(buf);
}
这里初始化inode位图，和inode数组并写入，inode位图可是刚好占据1个扇区，不存在多余的位，而inode数组数量由inode位图决定，所以inode位图不越界，inode数组就没事，不用管
然后将根目录写入第一个内存块，并初始化内容为.和..目录
到此文件系统创建就完毕了
fs/fs.c 初始化函数
接下来需要一个函数来初始化文件系统：
// 在磁盘上搜索文件系统, 若没有则格式化分区创建文件系统
void filesys_init() {
uint8_t channel_no = 0, dev_no, part_idx = 0;
// sb_buf 用来存储从硬盘上读入的超级块
struct super_block* sb_buf = (struct super_block*)sys_malloc(SECTOR_SIZE);
if (sb_buf == NULL) {
PANIC("alloc memory failed!");
}
printk("searching filesystem......\n");
while (channel_no < channel_cnt) {
dev_no = 0;
while (dev_no < 2) {
if (dev_no == 0) { // 跳过裸盘 hd60M.img
dev_no++;
continue;
}
struct disk* hd = &channels[channel_no].devices[dev_no];
struct partition* part = hd->prim_parts;
while (part_idx < 12) { // 4 个主分区 + 8 个逻辑分区
if (part_idx == 4) { // 开始处理逻辑分区
part = hd->logic_parts;
}
if (part->sec_cnt != 0) { // 如果分区存在
memset(sb_buf, 0, SECTOR_SIZE);
// 读出分区的超级块, 根据魔数是否正确来判断是否存在文件系统
ide_read(hd, part->start_lba+1, sb_buf, 1);
if (sb_buf->magic == 0x19590318) {
printk("%s has filesystem\n", part->name);
} else { // 其它文件系统不支持, 一律按无文件系统处理
printk("formatting %s's partition %s......\n",
hd->name, part->name);
partition_format(part);
}
}
part_idx++;
part++; // 下一分区
}
dev_no++; // 下一磁盘
}
channel_no++; // 下一通道
}
sys_free(sb_buf);
}
三次循环遍历分区信息，第一次循环遍历通道，第二次循环遍历硬盘，第三次循环遍历分区，通过魔数判断分区上是否有文件系统，如果没有就调用partition_format进行创建
运行 Bochs 查看文件系统创建
将初始化函数加入到init.c中，编译，运行：
因为没创建过文件系统，所以会自动创建，并显示创建信息，下一次在运行的时候：
就会显示已创建
挂载分区
挂载分区的本质就是将分区文件系统的元信息从硬盘中读取到内存中来，咱们要实现的功能是直接选择待操作的分区
fs/fs.c 挂载分区
struct partition* cur_part; // 默认情况下操作的是哪个分区
// 在分区链表中找到名为 part_name 的分区, 并将其指针赋值给 cur_part
static bool mount_partition(struct list_elem* pelem, int arg) {
char* part_name = (char*)arg;
struct partition* part = elem2entry(struct partition, part_tag, pelem);
if (!strcmp(part->name, part_name)) {
cur_part = part;
struct disk* hd = cur_part->my_disk;
// sb_buf 用来存储从硬盘上读入的超级块
struct super_block* sb_buf = (struct super_block*)sys_malloc(SECTOR_SIZE);
// 在内存中创建分区 cur_part 的超级块
cur_part->sb = (struct super_block*)sys_malloc(sizeof(struct super_block));
if (cur_part->sb == NULL) {
PANIC("alloc memory failed!");
}
// 读入超级块
memset(sb_buf, 0, SECTOR_SIZE);
ide_read(hd, cur_part->start_lba+1, sb_buf, 1);
// 把 sb_buf 中超级块的信息复制到分区的超级块 sb 中
memcpy(cur_part->sb, sb_buf, sizeof(struct super_block));
// 将硬盘上的块位图读入到内存
cur_part->block_bitmap.bits = (uint8_t*)sys_malloc(sb_buf->block_bitmap_sects*SECTOR_SIZE);
if (cur_part->block_bitmap.bits == NULL) {
PANIC("alloc memory failed!");
}
cur_part->block_bitmap.btmp_bytes_len = sb_buf->block_bitmap_sects * SECTOR_SIZE;
// 从硬盘上读入块位图到分区的 block_bitmap.bits
ide_read(hd, sb_buf->block_bitmap_lba, cur_part->block_bitmap.bits, sb_buf->block_bitmap_sects);
// 将硬盘上的 inode 位图读入到内存
cur_part->inode_bitmap.bits = (uint8_t*)sys_malloc(sb_buf->inode_bitmap_sects*SECTOR_SIZE);
if (cur_part->inode_bitmap.bits == NULL) {
PANIC("alloc memory failed!");
}
cur_part->inode_bitmap.btmp_bytes_len = sb_buf->inode_bitmap_sects*SECTOR_SIZE;
// 从硬盘上读入 inode 位图到分区的 inode_bitmap.bits
ide_read(hd, sb_buf->inode_bitmap_lba, cur_part->inode_bitmap.bits, sb_buf->inode_bitmap_sects);
list_init(&cur_part->open_inodes);
printk("mount %s done!\n", part->name);
return true; // 使 list_traversal 停止遍历
}
return false; // 使 list_traversal 继续遍历
}
// 在磁盘上搜索文件系统, 若没有则格式化分区创建文件系统
void filesys_init() {
...
// 确定默认操作的分区
char default_part[8] = "sdb1";
// 挂载分区
list_traversal(&partition_list, mount_partition, (int)default_part);
挂载分区实际上就是从硬盘的分区队列中找到该分区，找不到就返回false，找到了就读取超级块中的有用内容到内存中，读取到全局变量 cur_part 中，返回true，然后将该分区的open_inode list初始化
运行 Bochs 挂载分区
编译，运行：
文件描述符
文件描述符原理
Linux 几乎所有操作都是基于文件描述符的，文件描述符和inode不同，inode描述的是硬盘上的数据，文件描述符描述的是文件当前的状态
读写文件的本质是：先通过文件的inode找到文件的数据块的扇区地址，随后读写改扇区，从而实现文件读写。文件读写的实际上是通过文件偏移量指针指向要修改的位置然后进行操作，为了实现让同一个文件被同时多次打开，操作系统提供了“文件结构”来记录每次打开的时候的文件偏移量。文件结构是专门用于记录文件操作相关信息的，逻辑结构如图：
Linux 把所有的文件结构组织到一起，形成“文件表”
inode用于描述文件存储相关信息，文件结构用于描述文件打开后，文件读写偏移量等信息
inode与文件是一对一，文件结构与文件是多对一
Linux 中文件操作通常是先用open函数打开文件获取文件描述符，然后将文件描述符作为参数传递给write等函数进行文件读写操作
通过open打开的文件描述符返回的是一个数字，这个数字是PCB中文件描述符数组的下标，通过该文件描述符数组，获取文件描述符，通过文件描述符中断inode信息，获取文件的数据块
open操作的本质就是创建相应文件描述符的过程，这三个数据结构是提前定义好的，创建文件描述符的过程就是逐层在这三个数据结构中找空位， 在该空位填充好数据后返回该位置的地址：
- 在全局的inode队列中新建一inode（这肯定是在空位置处新建）， 然后返回该inode地址。
- 在全局的文件表中的找一空位， 在该位置填充文件结构， 使其fd_inode指向上一步中返回的inode地址， 然后返回本文件结构在文件表中的下标值。
- 在PCB中的文件描述符数组中找一空位， 使该位置的值指向上一步中返回的文件结构下标， 并返回本文件描述符在文件描述符数组中的下标值。
以上过程是我们要实现的。
文件描述符的实现
实现文件系统不仅需要单独的文件处理模块，还需要改进PCB：
thread/thread.h
#define MAX_FILES_OPEN_PER_PROC 8
// 进程或线程的 PCB
struct task_struct {
...
uint32_t elapsed_ticks; // 此任务上 cpu 运行后至今占用了多少嘀嗒数
int32_t fd_table[MAX_FILES_OPEN_PER_PROC]; // 文件描述符数组
struct list_elem general_tag; // 用于线程在一般队列中的结点
向PCB中新增一个文件描述符数组，文件描述符上限为8
thread/thread.c
// 待初始化线程指针（PCB），线程名称，线程优先级
void init_thread(struct task_struct* pthread, char* name, int prio) {
...
pthread->pgdir = NULL;
// 预留标准输入输出
pthread->fd_table[0] = 0;
pthread->fd_table[1] = 1;
pthread->fd_table[2] = 2;
// 其余的全置为 -1
uint8_t fd_idx = 3;
while (fd_idx < MAX_FILES_OPEN_PER_PROC) {
pthread->fd_table[fd_idx] = -1;
fd_idx++;
}
pthread->stack_magic = 0x19870916; // 自定义魔数
}
创建了文件描述符数组就需要进行初始化，预留标准输入0，标准输出1，标准错误2，剩下的位置置-1，-1表示为空位
文件操作相关的基础函数
为了实现文件操作，需要先把基础设施准备好
inode 操作相关的函数
文件、目录本质上都是inode，任何文件目录操作都离不开inode处理
fs/inode.c 上
// 用来存储 inode 位置
struct inode_position {
bool two_sec; // inode 是否跨扇区
uint32_t sec_lba; // inode 所在的扇区号
uint32_t off_size; // inode 在扇区内的字节偏移量
};
// 获取 inode 所在的扇区和扇区内的偏移量
static void inode_locate(struct partition* part,
uint32_t inode_no,
struct inode_position* inode_pos) {
// inode_table 在硬盘上是连续的
ASSERT(inode_no < 4096);
uint32_t inode_table_lba = part->sb->inode_table_lba;
uint32_t inode_size = sizeof(struct inode);
// 第 inode_no 号 I 结点相对于 inode_table_lba 的字节偏移量
uint32_t off_size = inode_no * inode_size;
// 第 inode_no 号 I 结点相对于 inode_table_lba 的扇区偏移量
uint32_t off_sec = off_size / 512;
// 待查找的 inode 所在扇区中的起始地址
uint32_t off_size_in_sec = off_size % 512;
// 判断此 i 结点是否跨越 2 个扇区
uint32_t left_in_sec = 512 - off_size_in_sec;
if (left_in_sec < inode_size) {
// 若扇区内剩下的空间不足以容纳一个 inode, 必然是 I 结点跨越了 2 个扇区
inode_pos->two_sec = true;
} else { // 否则, 所查找的 inode 未跨扇区
inode_pos->two_sec = false;
}
inode_pos->sec_lba = inode_table_lba + off_sec;
inode_pos->off_size = off_size_in_sec;
}
// 将 inode 写入到分区 part
void inode_sync(struct partition* part, struct inode* inode, void* io_buf) {
uint8_t inode_no = inode->i_no;
struct inode_position inode_pos;
// inode 位置信息会存入 inode_pos
inode_locate(part, inode_no, &inode_pos);
ASSERT(inode_pos.sec_lba <= (part->start_lba + part->sec_cnt));
// 硬盘中的 inode 中的成员 inode_tag 和 i_open_cnts 是不需要的
// 它们只在内存中记录链表位置和被多少进程共享
struct inode pure_inode;
memcpy(&pure_inode, inode, sizeof(struct inode));
// 以下 inode 的三个成员只存在于内存中
// 现在将 inode 同步到硬盘, 清掉这三项即可
pure_inode.i_open_cnts = 0;
pure_inode.write_deny = false;
pure_inode.inode_tag.prev = pure_inode.inode_tag.next = NULL;
// io_buf 是用于硬盘 io 的缓冲区
char* inode_buf = (char*)io_buf;
if (inode_pos.two_sec) {
// 若是跨了两个扇区, 就要读出两个扇区再写入两个扇区
// 读写硬盘是以扇区为单位, 若写入的数据小于一扇区
// 要将原硬盘上的内容先读出来再和新数据拼成一扇区后再写入
ide_read(part->my_disk, inode_pos.sec_lba, inode_buf, 2);
// 开始将待写入的 inode 拼入到这 2 个扇区中的相应位置
memcpy((inode_buf+inode_pos.off_size), &pure_inode, sizeof(struct inode));
// 将拼接好的数据再写入磁盘
ide_write(part->my_disk, inode_pos.sec_lba, inode_buf, 2);
} else {
ide_read(part->my_disk, inode_pos.sec_lba, inode_buf, 1);
memcpy((inode_buf + inode_pos.off_size), &pure_inode, sizeof(struct inode));
ide_write(part->my_disk, inode_pos.sec_lba, inode_buf, 1);
}
}
代码比较好理解
inode_position 用来存储inode所在扇区地址和扇区内偏移量，用来定位inode在硬盘上的位置
inode_locate 函数用于定位 inode 所在扇区和扇区内偏移量，并写入inode_pos中
inode_sync 函数功能是将 inode 写入到分区 part
fs/inode.c 下
// 根据 i 结点号返回相应的 i 结点
struct inode* inode_open(struct partition* part, uint32_t inode_no) {
// 先在已打开的 inode 链表中找 inode, 此链表是为提速创建的缓冲区
struct list_elem* elem = part->open_inodes.head.next;
struct inode* inode_found;
while (elem != &part->open_inodes.tail) {
inode_found = elem2entry(struct inode, inode_tag, elem);
if (inode_found->i_no == inode_no) {
inode_found->i_open_cnts++;
return inode_found;
}
elem = elem->next;
}
// 由于 open_inodes 链表中找不到, 从硬盘读入此 inode 并加入此链表
struct inode_position inode_pos;
// inode 位置信息会存入 inode_pos
// 包括 inode 所在扇区地址和扇区内的字节偏移量
inode_locate(part, inode_no, &inode_pos);
// 为使通过 sys_malloc 创建的新 inode 被所有任务共享
// 需要将 inode 置于内核空间, 故需要临时将 cur_pbc->pgdir 置为 NULL
struct task_struct* cur = running_thread();
uint32_t* cur_pagedir_bak = cur->pgdir;
cur->pgdir = NULL;
// 以上三行代码完成后下面分配的内存将位于内核区
inode_found = (struct inode*)sys_malloc(sizeof(struct inode));
// 恢复 pgdir
cur->pgdir = cur_pagedir_bak;
char* inode_buf;
if (inode_pos.two_sec) { // 跨扇区的情况
inode_buf = (char*)sys_malloc(1024);
ide_read(part->my_disk, inode_pos.sec_lba, inode_buf, 2);
} else { // 未跨扇区
inode_buf = (char*)sys_malloc(512);
ide_read(part->my_disk, inode_pos.sec_lba, inode_buf, 1);
}
memcpy(inode_found, inode_buf+inode_pos.off_size, sizeof(struct inode));
list_push(&part->open_inodes, &inode_found->inode_tag);
inode_found->i_open_cnts = 1;
sys_free(inode_buf);
return inode_found;
}
// 关闭 inode 或减少 inode 的打开数
void inode_close(struct inode* inode) {
// 若没有进程再打开此文件, 将此 inode 去掉并释放空间
enum intr_status old_status = intr_disable();
if (--inode->i_open_cnts == 0) {
// 将 inode 结点从 part->open_inodes 中去掉
list_remove(&inode->inode_tag);
// inode_open 时为实现 inode 被所有进程共享
// 已经在 sys_malloc 为 inode 分配了内核空间
// 释放 inode 时也要确保释放的是内核内存池
struct task_struct* cur = running_thread();
uint32_t* cur_pagedir_bak = cur->pgdir;
cur->pgdir = NULL;
sys_free(inode);
cur->pgdir = cur_pagedir_bak;
}
intr_set_status(old_status);
}
// 初始化 new_inode
void inode_init(uint32_t inode_no, struct inode* new_inode) {
new_inode->i_no = inode_no;
new_inode->i_size = 0;
new_inode->i_open_cnts = 0;
new_inode->write_deny = false;
// 初始化块索引数组 i_sector
uint8_t sec_idx = 0;
while (sec_idx < 13) {
// i_sectors[12] 为一级间接块地址
new_inode->i_sectors[sec_idx] = 0;
sec_idx++;
}
}
inode_open 函数：根据 i 结点号返回相应的 i 结点
- inode 队列是inode 的缓冲区，已经打开的inode会被加入该队列，所以这里先判断要打开的inode是否在缓冲区中，如果在就直接返回inode信息
- 如果不在，就创建一个内核缓冲区，来共享打开的inode，将该inode读取到内存中，加入inode队列
inode_close 函数：关闭 inode 或减少 inode 的打开数
- inode关闭，需要将inode属性中的i_open_cnts -1 表示inode的打开数少了1个，如果为0了，则表示不需要该inode了，可以从inode队列中删掉了
inode_init 函数：初始化 new_inode
- 创建inode，给inode分配初始信息
文件相关的函数
fs/file.h
// 文件结构
struct file {
uint32_t fd_pos; // 记录当前文件操作的偏移地址, 以 0 为起始, 最大为文件大小 - 1
uint32_t fd_flag;
struct inode* fd_inode;
};
// 标准输入输出描述符
enum std_fd {
stdin_no, // 0 标准输入
stdout_no, // 1 标准输出
stderr_no // 2 标准错误
};
// 位图类型
enum bitmap_type {
INODE_BITMAP, // inode 位图
BLOCK_BITMAP // 块位图
};
#define MAX_FILE_OPEN 32 // 系统可打开的最大文件数
定义了要用到的文件结构
fs/file.c
// 文件表
struct file file_table[MAX_FILE_OPEN];
// 从文件表 file_table 中获取一个空闲位, 成功返回下标, 失败返回 -1
int32_t get_free_slot_in_global(void) {
uint32_t fd_idx = 3;
while (fd_idx < MAX_FILE_OPEN) {
if (file_table[fd_idx].fd_inode == NULL) {
break;
}
fd_idx++;
}
if (fd_idx == MAX_FILE_OPEN) {
printk("exceed max open files\n");
return -1;
}
return fd_idx;
}
// 将全局描述符下标安装到进程或线程自己的文件描述符数组fd_table中
// 成功返回下标, 失败返回 -1
int32_t pcb_fd_install(int32_t globa_fd_idx) {
struct task_struct* cur = running_thread();
uint8_t local_fd_idx = 3;
while (local_fd_idx < MAX_FILES_OPEN_PER_PROC) {
if (cur->fd_table[local_fd_idx] == -1) {
cur->fd_table[local_fd_idx] = globa_fd_idx;
break;
}
local_fd_idx++;
}
if (local_fd_idx == MAX_FILES_OPEN_PER_PROC) {
printk("exceed max open files_per_proc\n");
return -1;
}
return local_fd_idx;
}
// 分配一个 inode, 返回 inode 号
int32_t inode_bitmap_alloc(struct partition* part) {
int32_t bit_idx = bitmap_scan(&part->inode_bitmap, 1);
if (bit_idx == -1) {
return -1;
}
bitmap_set(&part->inode_bitmap, bit_idx, 1);
return bit_idx;
}
// 分配 1 个扇区, 返回其扇区地址
int32_t block_bitmap_alloc(struct partition* part) {
int32_t bit_idx = bitmap_scan(&part->block_bitmap, 1);
if (bit_idx == -1) {
return -1;
}
bitmap_set(&part->block_bitmap, bit_idx, 1);
// 和 inode_bitmap_malloc 不同, 此处返回的不是位索引
// 而是具体可用的扇区地址
return (part->sb->data_start_lba + bit_idx);
}
// 将内存中 bitmap 第 bit_idx 位所在的 512 字节同步到硬盘
void bitmap_sync(struct partition* part, uint32_t bit_idx, uint8_t btmp) {
// 本 inode 索引相对于位图的扇区偏移量
uint32_t off_sec = bit_idx / 4096;
// 本 inode 索引相对于位图的字节偏移量
uint32_t off_size = off_sec * BLOCK_SIZE;
uint32_t sec_lba;
uint8_t* bitmap_off;
switch (btmp) {
case INODE_BITMAP:
sec_lba = part->sb->inode_bitmap_lba + off_sec;
bitmap_off = part->inode_bitmap.bits + off_size;
break;
case BLOCK_BITMAP:
sec_lba = part->sb->block_bitmap_lba + off_sec;
bitmap_off = part->block_bitmap.bits + off_size;
break;
}
ide_write(part->my_disk, sec_lba, bitmap_off, 1);
}
get_free_slot_in_global 函数：从文件表中找到一个空的位置，其实就是找数组元素为NULL的项，然后返回该项的数组下标
pcb_fd_install 函数：将全局描述符下标安装到进程或线程自己的文件描述符数组fd_table中，就是在PCB的fd_table中找一个空位，返回空位下标
inode_bitmap_alloc 函数：在位图中分配一个i节点，返回节点号
block_bitmap_alloc 函数：在位图中分配一个扇区，返回扇区地址
位图中进行分配本质上就是在位图中找个空位，设置为1，然后返回该空位的索引，用这个索引可以直接选中该位图所描述的空间
bitmap_sync 函数：将内存中 bitmap 第 bit_idx 位所在的 512 字节同步到硬盘
目录相关的函数
fs/dir.c 上
struct dir root_dir; // 根目录
// 打开根目录
void open_root_dir(struct partition* part) {
root_dir.inode = inode_open(part, part->sb->root_inode_no);
root_dir.dir_pos = 0;
}
// 在分区 part 上打开 inode 为 inode_no 的目录并返回目录指针
struct dir* dir_open(struct partition* part, uint32_t inode_no) {
struct dir* pdir = (struct dir*)sys_malloc(sizeof(struct dir));
pdir->inode = inode_open(part, inode_no);
pdir->dir_pos = 0;
return pdir;
}
// 在 part 分区内的 pdir 目录内寻找名为 name 的文件或目录
// 找到后返回 true 并将其目录项存入 dir_e, 否则返回 false
bool search_dir_entry(struct partition* part, struct dir* pdir, const char* name, struct dir_entry* dir_e) {
uint32_t block_cnt = 140; // 12 个直接块 + 128 个一级间接块 = 140 块
// 12 个直接块大小 + 128 个间接块, 共 560 字节
uint32_t* all_blocks = (uint32_t*)sys_malloc(48+512);
if (all_blocks == NULL) {
printk("search_dir_entry: sys_malloc for all_blocks failed");
return false;
}
uint32_t block_idx = 0;
while (block_idx < 12) {
all_blocks[block_idx] = pdir->inode->i_sectors[block_idx];
block_idx++;
}
block_idx = 0;
if (pdir->inode->i_sectors[12] != 0) { // 若含有一级间接块表
ide_read(part->my_disk, pdir->inode->i_sectors[12], all_blocks+12, 1);
}
// 至此, all_blocks 存储的是该文件或目录的所有扇区地址
uint8_t* buf = (uint8_t*)sys_malloc(SECTOR_SIZE);
// p_de 为指向目录项的指针, 值为 buf 起始地址
struct dir_entry* p_de = (struct dir_entry*)buf;
uint32_t dir_entry_size = part->sb->dir_entry_size;
// 1 扇区内可容纳的目录项个数
uint32_t dir_entry_cnt = SECTOR_SIZE / dir_entry_size;
// 开始在所有块中查找目录项
while (block_idx < block_cnt) {
// 块地址为 0 时表示该块中无数据, 继续在其它块中找
if (all_blocks[block_idx] == 0) {
block_idx++;
continue;
}
ide_read(part->my_disk, all_blocks[block_idx], buf, 1);
uint32_t dir_entry_idx = 0;
// 遍历扇区中所有目录项
while (dir_entry_idx < dir_entry_cnt) {
// 若找到了, 就直接复制整个目录项
if (!strcmp(p_de->filename, name)) {
memcpy(dir_e, p_de, dir_entry_size);
sys_free(buf);
sys_free(all_blocks);
return true;
}
dir_entry_idx++;
p_de++;
}
block_idx++;
p_de = (struct dir_entry*)buf;
memset(buf, 0, SECTOR_SIZE);
}
sys_free(buf);
sys_free(all_blocks);
return false;
}
open_root_dir 函数：打开根目录
dir_open 函数：在分区part上打开inode为inode_no的目录并返回目录指针
search_dir_entry 函数：在分区内的pdir目录寻找名为name的文件或目录，找到返回true并将其目录项存入dir_e
- 先将该目录项的数据拼凑出来，然后遍历寻找目录项，找到了就把目录项存入dir_e，并返回true
fs/dir.c 中
// 关闭目录
void dir_close(struct dir* dir) {
if (dir == &root_dir) {
// 根目录不能关闭
return;
}
inode_close(dir->inode);
sys_free(dir);
}
// 在内存中初始化目录项
void create_dir_entry(char* filename,
uint32_t inode_no,
uint8_t file_type,
struct dir_entry* p_de) {
ASSERT(strlen(filename) <= MAX_FILE_NAME_LEN);
// 初始化目录项
memcpy(p_de->filename, filename, strlen(filename));
p_de->i_no = inode_no;
p_de->f_type = file_type;
}
dir_close 函数：关闭目录，本质上是关闭inode，root目录不能被关闭
create_dir_entry 函数：初始化目录项
fs/dir.c 下
// 将目录项 p_de 写入父目录 parent_dir 中, io_buf 由主调函数提供
bool sync_dir_entry(struct dir* parent_dir, struct dir_entry* p_de, void* io_buf) {
struct inode* dir_inode = parent_dir->inode;
uint32_t dir_size = dir_inode->i_size;
uint32_t dir_entry_size = cur_part->sb->dir_entry_size;
ASSERT(dir_size % dir_entry_size == 0);
// 每扇区最大的目录项数目
uint32_t dir_entrys_per_sec = (512 / dir_entry_size);
int32_t block_lba = -1;
// 将该目录的所有扇区地址(12 个直接块 + 128 个间接块)存入 all_blocks
uint8_t block_idx = 0;
// all_blocks 保存目录所有的块
uint32_t all_blocks[140] = {0};
// 将 12 个直接块存入 all_blocks
while (block_idx < 12) {
all_blocks[block_idx] = dir_inode->i_sectors[block_idx];
block_idx++;
}
// dir_e 用来在 io_buf 中遍历目录项
struct dir_entry* dir_e = (struct dir_entry*)io_buf;
int32_t block_bitmap_idx = -1;
// 开始遍历所有块以寻找目录项空位, 若已有扇区中没有空闲位
// 在不超过文件大小的情况下申请新扇区来存储新目录项
block_idx = 0;
while (block_idx < 140) {
block_bitmap_idx = -1;
if (all_blocks[block_idx] == 0) {
block_lba = block_bitmap_alloc(cur_part);
if (block_lba == -1) {
printk("alloc block bitmap for sync_dir_entry failed\n");
return false;
}
// 每分配一个块就同步一次 block_bitmap
block_bitmap_idx = block_lba - cur_part->sb->data_start_lba;
ASSERT(block_bitmap_idx != -1);
bitmap_sync(cur_part, block_bitmap_idx, BLOCK_BITMAP);
block_bitmap_idx = -1;
if (block_idx < 12) { // 若是直接块
dir_inode->i_sectors[block_idx] = all_blocks[block_idx] = block_lba;
} else if (block_idx == 12) {
dir_inode->i_sectors[12] = block_lba;
block_lba = -1;
// 再分配一个块作为第 0 个间接块
block_lba = block_bitmap_alloc(cur_part);
if (block_lba == -1) {
block_bitmap_idx = dir_inode->i_sectors[12] - cur_part->sb->data_start_lba;
bitmap_set(&cur_part->block_bitmap, block_bitmap_idx, 0);
dir_inode->i_sectors[12] = 0;
printk("alloc block bitmap for sync_dir_entry failed\n");
return false;
}
// 每分配一个块就同步一次 block_bitmap
block_bitmap_idx = block_lba - cur_part->sb->data_start_lba;
ASSERT(block_bitmap_idx != -1);
bitmap_sync(cur_part, block_bitmap_idx, BLOCK_BITMAP);
all_blocks[12] = block_lba;
// 把新分配的第 0 个间接块地址写入一级间接块表
ide_write(cur_part->my_disk, dir_inode->i_sectors[12], all_blocks+12, 1);
} else {
all_blocks[block_idx] = block_lba;
// 把新分配的第(block_idx - 12)个间接块地址写入一级间接块表
ide_write(cur_part->my_disk, dir_inode->i_sectors[12], all_blocks+12, 1);
}
// 再将新目录项 p_de 写入新分配的间接块
memset(io_buf, 0, 512);
memcpy(io_buf, p_de, dir_entry_size);
ide_write(cur_part->my_disk, all_blocks[block_idx], io_buf, 1);
dir_inode->i_size += dir_entry_size;
}
// 若第 block_idx 块已存在, 将其读进内存, 然后在该块中查找空目录项
ide_read(cur_part->my_disk, all_blocks[block_idx], io_buf, 1);
// 在扇区内查找空目录项
uint8_t dir_entry_idx = 0;
while (dir_entry_idx < dir_entrys_per_sec) {
if ((dir_e + dir_entry_idx)->f_type == FT_UNKNOWN) {
memcpy(dir_e+dir_entry_idx, p_de, dir_entry_size);
ide_write(cur_part->my_disk, all_blocks[block_idx], io_buf, 1);
dir_inode->i_size += dir_entry_size;
return true;
}
dir_entry_idx++;
}
block_idx++;
}
printk("directory is full!\n");
return false;
}
sync_dir_entry 函数：将目录项写入父目录中
路径解析相关函数
fs/fs.c
// 将最上层路径名称解析出来
static char* path_parse(char* pathname, char* name_store) {
// 根目录不需要单独解析
if (pathname[0] == '/') {
// 路径中出现 1 个或多个连续的字符 '/', 将这些 '/' 跳过
while (*(++pathname) == '/');
}
// 开始一般的路径解析
while (*pathname != '/' && *pathname != 0) {
*name_store++ = *pathname++;
}
if (pathname[0] == 0) {
return NULL;
}
return pathname;
}
// 返回路径深度, 比如 /a/b/c, 深度为 3
int32_t path_depth_cnt(char* pathname) {
ASSERT(pathname != NULL);
char* p = pathname;
char name[MAX_FILE_NAME_LEN];
uint32_t depth = 0;
// 解析路径, 从中拆分出各级名称
p = path_parse(p, name);
while (name[0]) {
depth++;
memset(name, 0, MAX_FILE_NAME_LEN);
if (p) {
p = path_parse(p, name);
}
}
return depth;
}
实现文件检索功能
fs/fs.h
// 文件读写位置偏移量
enum whence {
SEEK_SET = 1,
SEEK_CUR,
SEEK_END
};
// 用来记录查找文件过程中已找到的上级路径
struct path_search_record {
char searched_path[MAX_PATH_LEN]; // 查找过程中的父路径
struct dir* parent_dir; // 文件或目录所在的直接父目录
enum file_types file_type; // 文件类型
};
fs/fs.c
// 搜索文件 pathname, 若找到则返回其 inode 号, 否则返回 -1
static int search_file(const char* pathname, struct path_search_record* searched_record) {
// 如果待查找的是根目录, 为避免下面无用的查找, 直接返回已知根目录信息
if (!strcmp(pathname, "/") || !strcmp(pathname, "/.") ||
!strcmp(pathname, "/..")) {
searched_record->parent_dir = &root_dir;
searched_record->file_type = FT_DIRECTORY;
searched_record->searched_path[0] = 0; // 搜索路径置空
return 0;
}
uint32_t path_len = strlen(pathname);
// 保证 pathname 至少是这样的路径 /x, 且小于最大长度
ASSERT(pathname[0] == '/' && path_len > 1 && path_len < MAX_PATH_LEN);
char* sub_path = (char*)pathname;
struct dir* parent_dir = &root_dir;
struct dir_entry dir_e;
// 记录路径解析出来的各级名称
char name[MAX_FILE_NAME_LEN] = {0};
searched_record->parent_dir = parent_dir;
searched_record->file_type = FT_UNKNOWN;
uint32_t parent_inode_no = 0; // 父目录的 inode 号
sub_path = path_parse(sub_path, name);
while (name[0]) { // 若第一个字符就是结束符, 结束循环
// 记录查找过的路径, 但不能超过 searched_path 的长度 512 字节
ASSERT(strlen(searched_record->searched_path) < 512);
// 记录已存在的父目录
strcat(searched_record->searched_path, "/");
strcat(searched_record->searched_path, name);
// 在所给的目录中查找文件
if (search_dir_entry(cur_part, parent_dir, name, &dir_e)) {
memset(name, 0, MAX_FILE_NAME_LEN);
// 若 sub_path 不等于 NULL, 也就是未结束时继续拆分路径
if (sub_path) {
sub_path = path_parse(sub_path, name);
}
// 如果被打开的是目录
if (FT_DIRECTORY == dir_e.f_type) {
parent_inode_no = parent_dir->inode->i_no;
dir_close(parent_dir);
parent_dir = dir_open(cur_part, dir_e.i_no); // 更新父目录
searched_record->parent_dir = parent_dir;
continue;
} else if (FT_REGULAR == dir_e.f_type) { // 若是普通文件
searched_record->file_type = FT_REGULAR;
return dir_e.i_no;
}
} else { // 若找不到, 则返回 -1
return -1;
}
}
// 执行到此, 必然是遍历了完整路径并且查找的文件或目录只有同名目录存在
dir_close(searched_record->parent_dir);
// 保存被查找目录的直接父目录
searched_record->parent_dir = dir_open(cur_part, parent_inode_no);
searched_record->file_type = FT_DIRECTORY;
return dir_e.i_no;
}
本篇总结
文件描述符是用来描述文件的使用状态的，文件描述符存在文件描述符表里，PCB中有文件描述符数组，数组里的值是文件描述符表的索引，而PCB中的文件描述符数组下标则是文件操作相关函数返回的值
我们要实现文件系统的各种文件操作，就需要先构建文件描述符来描述文件的使用状态。
文件系统是通过一系列元信息来描述硬盘的使用状况，这里用的是inode文件系统，通过inode描述文件的存储信息，存储的块信息等，inode近似等同于文件，分区里所有的inode信息位于分区里的inode数组里，通过inode编号进行索引，文件和目录都是inode，通过数据块内容加以区分，inode数组的位置存储在超级块里，超级块是文件系统的元信息，存储着各种用到的结构的位置，如位图信息，inode信息等。
创建文件系统的本质就是创建文件系统的元信息，也就是创建超级块和创建相关数据结构并填充地址到超级块中，不同分区可以是不同文件系统
挂载分区的本质就是将分区文件系统的元信息从硬盘中读取到内存中来，以便接下来使用该分区进行读写操作
参考资料
- 《操作系统真象还原》chapter 14.1~14.4