logo一只豆腐
  • HangX-Ma
  • Jul 10, 2023
  • Total 11038 words
  • About 31 mins
  • 0 views

rCore OS Note - Chapter 6

第六章：文件系统， 阅读 rCore tutorial book v3 的笔记以及实践部分的实现与记录。

文件系统这块的内容还是相当复杂的， 当时学 xv6 就是一知半解把 lab 草草做完了事儿了， 结果这几个月调设备的时候遇到用 SPI Nand Flash 的设备， 文件系统挂载不上等问题。 自己对 Block Device， VFS， 以及 inode 这些概念的理解都不是很到位， 调试非常痛苦到最后陷入了死胡同， 借着学习 rCore 的机会争取把这块搞懂， 毕竟从头搭一个 OS 要对细节有更好的把握。

easy-fs 自下而上大致可以分成五个不同的层次：

磁盘块设备接口层
定义了以块大小为单位对磁盘块设备进行读写的 trait 接口
块缓存层
在内存中缓存磁盘块的数据， 避免频繁读写磁盘
磁盘数据结构层
磁盘上的超级块、 位图、 索引节点、 数据块、 目录项等核心数据结构和相关处理
磁盘块管理器层
合并了上述核心数据结构和磁盘布局所形成的磁盘文件系统数据结构， 以及基于这些结构进行文件系统的创建等操作， 以及对磁盘块进行分配和回收处理
索引节点层
管理索引节点（即文件控制块）数据结构， 并实现文件创建/文件打开/文件读写等成员函数， 以向上支持文件操作相关的系统调用
Filesystem OS details, rCore
Filesystem OS Details, rCore

0. 资料汇总

1. 文件系统

文件系统交互的主要对象是磁盘这类的存储器， 这类存储器和 RAM 的管理方式不同， 这类存储器以扇区 （一般为 512 bytes） 进行读写， 以块为单位进行存储 （一个块为由多个扇区组成）。 文件系统的职责就是将逻辑上的目录树结构映射存储到这类存储器中并进行管理。 另外， 为了适配管理多个文件系统， 在此基础上抽象出一层 虚拟文件系统（VFS, Virtual File System） 提供统一的接口和目录树的通用格式方便进行管理。

2. 块设备接口层

文件系统以块为单位进行数据管理， 一般我们会通过 块设备驱动 完成对磁盘的数据的存取， 这需要文件系统提供接口对接驱动， 这种方式以二者职能为分界进行了层次化处理。 在 rCore 中提供 BlockDevice 抽象接口， 不过需要注意的是， 这个接口实现了 Send， Sync， Any 这几个 trait。 前两个见过面， 用以保证数据的线程安全， 但我目前还是不太理解下面这两句：

  • A type is Send if it is safe to send it to another thread.
  • A type is Sync if it is safe to share between threads (T is Sync if and only if &T is Send).

由于 Rust 编译器需要知道 trait 实现时的具体大小， 因而 rCore 后续使用的时候都是以 Arc<dyn BlockDevice> 表明该 trait 类型， 被 Arc 引用包裹的静态大小是已知的， 这样编译器可以保证引用指向已分配堆的 BlockDevice， 同时还需要使用 dyn 关键字。

用到 Any 与 BlockDevice 是一个 trait 类型相关。 Any 的存在实现了 Rust 语言的部分的反射功能， 获得变量的类型 TypeId， 判断变量是否是指定类型， 转换该类型， 获取类型名称等， 具体的作用后续阅读代码再补充。

// easy-fs/src/block_dev.rs
pub trait BlockDevice : Send + Sync + Any {
    fn read_block(&self, block_id: usize, buf: &mut [u8]);
    fn write_block(&self, block_id: usize, buf: &[u8]);
}

The Rustonomicon - 8.2. Send and Sync
通过例子学 Rust 中文版 - 16.2. 使用 dyn 返回 trait
Rust std-any 模块详解

3. 块缓存层

块缓存层的存在是为了减少块设备频繁读写的开销， 相较于直接从 RAM 中获取数据， 读写磁盘的速度还是太慢了， 因而我们在软件层面实现块的缓存以加快数据的读写。 但缓存还得解决缓存一致性以及同步性等问题， rCore 使用块缓存全局管理器解决这些问题， 并通过该管理器一次性让更多的块合并操作， 这是因为连续的块的操作能够加速存取速度。

// easy-fs/src/block_cache.rs
pub struct BlockCache {
    cache: [u8; BLOCK_SZ],
    block_id: usize,
    block_device: Arc<dyn BlockDevice>,
    modified: bool,
}

每个 BlockCache 缓存一个磁盘块， 这是一个最小单位， rCore 提供了一些对缓存管理的方法：

  • new： BlockCache 实现了 new 方法创建从磁盘读取一个 Block 到缓冲区。 前述所言， Block 大小和 Sector 大小一致均为 512 bytes， 这也是缓冲区 cache 被设置为 BLOCK_SZ 大小的原因。
  • addr_of_offset： 获取 cache 数组偏移 offset 大小的字节地址。
  • get_ref， get_mut： 通过调用 addr_of_offset 获取地址后， 将该地址声明为不可变或可变引用。

rCore 将 BlockCache::get_ref 和 BlockCache::get_mut 封装成了 BlockCache::read 以及 BlockCache::modify 这两个泛型， 这两个函数后续用到非常多， 后面结合具体代码进行解释。 但从代码的构成而言， read/modify 构成了传入闭包 f 的一层执行环境，让它能够绑定到一个缓冲区上执行。

// easy-fs/src/block_cache.rs

impl BlockCache {
    pub fn read<T, V>(&self, offset: usize, f: impl FnOnce(&T) -> V) -> V {
        f(self.get_ref(offset))
    }

    pub fn modify<T, V>(&mut self, offset:usize, f: impl FnOnce(&mut T) -> V) -> V {
        f(self.get_mut(offset))
    }
}

rCore 实现了很多与 BlockCache 相关的操作方法详见 Tutorial， 这里仅对个人疑难点做记录以及梳理思路。

rCore 用 FIFO 作为简单的缓存替换策略并限定了缓存区的大小， 块缓存全局管理器 完成了上述所说的缓存管理的功能。 值得注意的是缓存队列中存储的是 块编号 和 块缓存 组。 块缓存类型是 Arc<Mutex<BlockCache>>， 共享引用保证在当前 块缓存全局管理器 中保留一个引用外（FIFO 剔除缓存的依据）， 缓存请求者能够对缓存进行访问， 而 Mutex 则避免在后续多核拓展时的访存冲突。

// easy-fs/src/block_cache.rs
pub struct BlockCacheManager {
    queue: VecDeque<(usize, Arc<Mutex<BlockCache>>)>,
}

struct BlockCacheManager 实现了一个 get_block_cache 的方法， 通过将全局实例 BLOCK_CACHE_MANAGER 封装， 其他模块能够方便地调用 get_block_cache 获取 block_id 对应的缓存块， 但需要注意的是返回类型是 Arc<Mutex<BlockCache>> 调用者还需要通过 .lock() 方法获取互斥锁才能对 BlockCache 进行操作。

pub fn get_block_cache(
    block_id: usize,
    block_device: Arc<dyn BlockDevice>
) -> Arc<Mutex<BlockCache>> {
    BLOCK_CACHE_MANAGER.lock().get_block_cache(block_id, block_device)
}

4. 磁盘布局及磁盘上数据结构

前面几个部分比较好理解， 个人认为这个小节和 inode 小节最为关键且复杂。 要理解磁盘布局先得理解几个概念：

索引节点(Inode, Index Node)
Inode 编码了文件/目录的底层编号， 这个数据结构包含文件大小， 访问权限， 文件类型等信息， 还包含对数据的索引信息， 通过这些索引信息就能够找到数据块存储在磁盘上的位置。
位图(Bitmap)
位图用以标注索引节点以及数据块的分配情况， 通过位图能够方便分配和回收在磁盘上的存储资源。

rCore 中的磁盘布局如下图所示， 他们是以 Block ID 顺序排布的， 后续根据这个顺序对关键数据结构进行阐述。 这里需要注意的是， rCore 的假定内核仅管理一个块设备， 否则仅以 Block ID 作为标识， 在访问多个不同的块设备的时候会引起歧义。

Disk Layouts, HangX-Ma
Disk Layouts, HangX-Ma

4.1 Super Block

一句话可以概括， Super Block 存储了后续四个分区占用的 块数量， 并利用 MAGIC 验证文件系统的合法性。

4.2 Inode/Data Bitmap

从磁盘布局可以看出， rCore 通过 Inode Bitmap 和 Data Bitmap 分别管理索引节点和数据块。 每个 Bitmap 可以占据多个块， 在 rCore 中一个块的大小和一个扇区的大小一致都是 512 bytes， 相当于每个 Bitmap 实际上可以管理 \(4096 \times n\) 个索引节点或数据块。

// easy-fs/src/bitmap.rs

pub struct Bitmap {
    start_block_id: usize,
    blocks: usize,
}

type BitmapBlock = [u64; 64];

rCore 教程中的 struct Bitmap 存储的是 Inode Bitmap 或 Data Bitmap 在磁盘中的位置和大小的信息， 而这个数据结构本身则是存储在 RAM 中的。 rCore 另外用 BitmapBlock 数组表示每个 4096-bit 大小的数据块。 理解这个数据结构的设计原理， struct Bitmap 中的 alloc 和 dealloc 两个方法的实现就容易理解了。

            start_block_id(Start ID)
                  v
        ----------+---------------------+--------
                  |//// Bitmap Area ////|
        ----------+---------------------+--------
                                        ^
                             start_block_id + blocks(End ID)
        Block ID => 
        (increase)

这里结合 alloc 函数阐明 BlockCache 提供的 read/modify 方法。 注意 modify 函数中的闭包， 它显式声明了传入闭包的参数的类型是 &mut BitmapBlock 这样 modify 中才能将泛型 T 实例化为具体的类型 BitmapBlock。 这样通过声明的 bitmap_block， 我们实际上能对缓冲区的数据进行更改操作。 如果没有理解 read/modify 泛型的作用， 闭包中捕获的参数的数据来源就会混淆， 对后续的实验理解造成较大的阻碍。

// easy-fs/src/block_cache.rs

impl BlockCache {
    pub fn modify<T, V>(&mut self, offset:usize, f: impl FnOnce(&mut T) -> V) -> V {
        f(self.get_mut(offset))
    }
}
// easy-fs/src/bitmap.rs

const BLOCK_BITS: usize = BLOCK_SZ * 8;

impl Bitmap {
    pub fn alloc(&self, block_device: &Arc<dyn BlockDevice>) -> Option<usize> {
        for block_id in 0..self.blocks {
            let pos = get_block_cache(
                block_id + self.start_block_id as usize,
                Arc::clone(block_device),
            )
            .lock()
            .modify(0, 
            |bitmap_block: &mut BitmapBlock| {
                if let Some((bits64_pos, inner_pos)) = bitmap_block
                    .iter()
                    .enumerate()
                    .find(|(_, bits64)| **bits64 != u64::MAX)
                    .map(|(bits64_pos, bits64)| {
                        (bits64_pos, bits64.trailing_ones() as usize)
                    }) {
                    // modify cache
                    bitmap_block[bits64_pos] |= 1u64 << inner_pos;
                    Some(block_id * BLOCK_BITS + bits64_pos * 64 + inner_pos as usize)
                } else {
                    None
                }
            });
            if pos.is_some() {
                return pos;
            }
        }
        None
    }
}

4.3 Inode Blocks

Inode 存储着每个文件/目录的元数据： 文件/目录大小 size， 索引节点类型 type_， 以及对数据块的索引 direct/indirect1/indirect2。 在虚拟内存映射的章节 rCore 通过三级页表进行索引， 这里的 Inode 索引方式也很类似。 rCore 设计的单个 DiskInode 的大小是 128 bytes， 也就是 Inode Blocks 中每个块能够存储 4 个 DiskInode。

// easy-fs/src/layout.rs

const INODE_DIRECT_COUNT: usize = 28;

#[repr(C)]
pub struct DiskInode {
    pub size: u32,
    pub direct: [u32; INODE_DIRECT_COUNT],
    pub indirect1: u32,
    pub indirect2: u32,
    type_: DiskInodeType,
}

#[derive(PartialEq)]
pub enum DiskInodeType {
    File,
    Directory,
}

这里的多级索引是这样理解的， 分为直接索引 (direct) 和 间接索引 (indirect1/indirect2)。

  • 直接索引 direct 数组的每一个元素都保存着一个数据块的 Block ID， 这在文件尺寸不大于 28 * 512 bytes = 14 KiB 时使用。
Direct Index, HangX-Ma
Direct Index, HangX-Ma
  • 间接索引
    • 装满 direct 这部分内容后需要用间接索引扩大索引范围。 可以使用 indirect1 存储一个数据块的 Block ID 获取到这个数据块的内容， 而这个数据块我们不直接保存数据， 而是将其当作一个跳板用来存储其他数据块的 Block ID。 512 bytes 的数据块以 u32(4 bytes) 为单位， 这个数据块最大能存储 128 个 Block ID， 这样我们还能额外索引到 128 * 512 bytes = 64 KiB 的数据。
    • 相同的道理， 一级间接索引和直接索引总共 78 KiB 空间都不够用， 就可以再加上二级间接索引， 通过二级索引先找到一级索引块的 Block ID， 这些一级间接索引指向的每个数据块都不直接保存数据， 而是存储其他数据块的 Block ID， 这样再通过一级索引就能确定最终的数据块， 这种设计能额外索引 8 MiB 的额外内容。
Indirect Index, HangX-Ma
Indirect Index, HangX-Ma

NOTE: 关于 get_block_id 的一些疑惑和相关解释

impl DiskInode {
    pub fn get_block_id(&self, inner_id: u32, block_device: &Arc<dyn BlockDevice>) -> u32;
}

基于直接索引和间接索引， DiskInode 提供了获取数据块索引的功能的 get_block_id 函数。 这个函数的接口需要读入一个 inner_id， 这个并不是对应实际的磁盘的 Block ID 的， 而是根据这个 inner_id 的大小结合我们存储在 Inode 中的 direct， indirect1 以及 indirect2 可以获取到对应的数据块所在的 Block ID。

那这些数据又是怎么来的？ 通过 6. 索引节点， 中 struct Inode 提供了 create 方法。

对于 inner_id 可以确定是使用直接索引还是间接索引， 直接索引 direct 范围是 \([0;27]\)， indirect1 的范围是 \([28;127]\)， indirect2 的范围是 \([128;128*128-1]\)。 实际的 inner_id 和索引方式的分布值如下图所示：

Inner ID, HangX-Ma
Inner ID, HangX-Ma

后续关于 DiskInode 的各种辅助方法就不展开了。

4.4 Data Block / Directory

对 文件 而言其内容就是字节序列， 保存文件内容的数据块可以用字节数组表示。 前述的 Inode 相关的 read_at 和 write_at 方法中就是对这些字节数组进行操作。 这里我对 read_at 以及 write_at 操作的数据的位置是有疑惑的， 因为 rCore 自下而上编写的这个教学手册， 底层的内容很可能是有上层的包装的 （突然就想起李雅普诺夫判定式了）。

// easy-fs/src/layout.rs
type DataBlock = [u8; BLOCK_SZ];

对 目录 而言情况则有所不同， 我们需要建立一种树的结构进行逐级访问。 rCore 设计了 struct DirEntry 用以存储目录项结构， 其大小为 32 bytes， 这意味着每个 Data Block 可以最多存储 16 个目录项结构。 name 表示该目录下的一个文件名或子目录目录名， inode_number 则是这个文件或子目录所对应的 Inode 的节点编号。

// easy-fs/src/layout.rs
const NAME_LENGTH_LIMIT: usize = 27;

#[repr(C)]
pub struct DirEntry {
    name: [u8; NAME_LENGTH_LIMIT + 1],
    inode_number: u32,
}

pub const DIRENT_SZ: usize = 32;

5. 磁盘块管理器

在前面我们描述了磁盘的布局及其相应的数据结构， 这里就是将这些这些细节进行统筹管理， struct EasyFileSystem 中所保留的信息正好是 Disk Layouts 中描述的几个部分。 另外， 保留 block_device 指针引用是方便下层数据结构访问块设备。 可以看到这个数据结构中是不包含 superblock 的， 但是在后续计算的时候需要考虑进去。 从这里开始， 所有的数据结构都存储在内存上。

// easy-fs/src/efs.rs
pub struct EasyFileSystem {
    pub block_device: Arc<dyn BlockDevice>,
    pub inode_bitmap: Bitmap,
    pub data_bitmap: Bitmap,
    inode_area_start_block: u32, // inode 区域的起始 block id
    data_area_start_block: u32, // data 区域的起始 block id
}

6. 索引节点

服务于文件相关系统调用的索引节点层的代码在 vfs.rs 中， rCore 抽象了一层 Virtual Filesystem 方便使用者管理文件系统的文件与目录。

Inode 和 DiskInode 的区别从它们的名字中就可以看出： DiskInode 放在磁盘块中比较固定的位置，而 Inode 是放在内存中的记录文件索引节点信息的数据结构。 Inode 数据结构给使用者直接管理目录树结构中逻辑上的文件和目录的接口。 这个 Inode 在磁盘上所处的位置用 block_id 以及 block_offset 即可表示， fs 则给 Inode 提供了访问底层文件系统的接口。

// easy-fs/src/vfs.rs
pub struct Inode {
    block_id: usize,
    block_offset: usize,
    fs: Arc<Mutex<EasyFileSystem>>,
    block_device: Arc<dyn BlockDevice>,
}

rCore 后续还介绍了获取根目录 Inode, 文件索引， 文件列举， 文件创建， 文件清空， 文件读写的方式。 一直到这里把这几个函数读完， 以及将前述的所有内容再细读之后， 我才理清了 DiskInode 中的数据是如何被创建以及如何被索引管理的， 之前一直没搞懂究竟数据是如何被定位到 Data Block 的， 实际上就是 root_node 创建新的 child node 的时候 (Inode::create) 就通过 EasyFileSystem::alloc_inode 在 Inode Area 创建了一个新的 Inode， 最开始这个 Inode 是不存在任何数据的(DiskInode::initialize 返回的是个空的 DiskInode)， 只有在调用 Inode::increase_size 之后， 通过 EasyFileSystem::alloc_data 申请数据块后， 利用 DiskInode::increase_size 函数将这些数据块和 direct， indirect1， 以及 indirect2 填充并联系起来的。

// easy-fs/src/vfs.rs
/// Increase the size of a disk inode
fn increase_size(
    &self,
    new_size: u32,
    disk_inode: &mut DiskInode,
    fs: &mut MutexGuard<EasyFileSystem>,
) {
    if new_size < disk_inode.size {
        return;
    }
    let blocks_needed = disk_inode.blocks_num_needed(new_size);
    let mut v: Vec<u32> = Vec::new();
    for _ in 0..blocks_needed {
        v.push(fs.alloc_data());
    }
    disk_inode.increase_size(new_size, v, &self.block_device);
}

7. 课后练习

7.1 编程练习

  • TODO: 这部分回头再说

7.2 实验练习

硬链接

硬链接要求两个不同的目录项指向同一个文件， 在 easy-fs 中就是两个不同名称目录项指向同一个磁盘块。 需要实现三个系统调用 sys_linkat， sys_unlinkat， 以及 sys_stat。

硬链接需要新的 Inode 的 block_id 以及 block_offset 与被链接的对象是一致的， 这样才能保证链接到同一个文件数据， 而这两个数据则是通过 get_disk_inode_pos 函数获取到的， 依据是 DirEntry 中的 inode_id 这个数据。 所以 sys_linkat 的实现和 Inode::create 非常类似， 唯一不同的是 new_inode_id 不再是通过 fs.alloc_inode 获取一个新的 inode_id， 而是和需要链接的对象的完全一致。

对于 sys_unlinkat 就是和上述实现相反， 通过输入的 block_id 以及 block_offset 这两个参数， 遍历 file_count 数量的 DirEntry 并将数据读取到 buf 中查看 buf 对应的 block_id 以及 block_offset 是否和所给的参数一致， 另外实验不要求删除这个被分配的 inode。

sys_stat 这部分遇到的比较大的问题是如何将 fd_table 获取的到的 OSInode 从一个 trait 转换成实际的数据类型。 参考了 yao-jz/rCore-lab - ch6 中的实现， 需要给 File Trait 增加一个自己实现的 AnyConvertor Trait， 能够将任意类型转为 &dyn Any 再通过 downcast_ref::<OSInode>() 强制转换为 OSInode 数据类型。 这样我们再给 OSInode 增加 get_inode_id 以及 get_inode_pos 获取 inode_id 以及 block_id 和 block_offset 即可。 另外需要一个 get_nlink_num 函数获取 nlink 硬链接的数量， 思路和 unlink 的实现很类似， 也是遍历 file_count 数量的 DirEntry 只不过我们只计数。

use core::any::Any;

/// convert current type to &dyn Any
pub trait AnyConvertor {
    fn as_any(&self) -> &dyn Any;
}

impl<T: 'static> AnyConvertor for T {
    fn as_any(&self) -> &dyn Any {
        self
    }
}

具体实现可以参考 commit#1b6c70b

Search