简易文件系统 easy-fs (下)

磁盘块管理器

本层的代码在 efs.rs 中。

// 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,
    data_area_start_block: u32,
}

EasyFileSystem 包含索引节点和数据块的两个位图 inode_bitmapdata_bitmap ,还记录下索引节点区域和数据块区域起始块编号方便确定每个索引节点和数据块在磁盘上的具体位置。我们还要在其中保留块设备的一个指针 block_device ,在进行后续操作的时候,该指针会被拷贝并传递给下层的数据结构,让它们也能够直接访问块设备。

通过 create 方法可以在块设备上创建并初始化一个 easy-fs 文件系统:

 1// easy-fs/src/efs.rs
 2
 3impl EasyFileSystem {
 4    pub fn create(
 5        block_device: Arc<dyn BlockDevice>,
 6        total_blocks: u32,
 7        inode_bitmap_blocks: u32,
 8    ) -> Arc<Mutex<Self>> {
 9        // calculate block size of areas & create bitmaps
10        let inode_bitmap = Bitmap::new(1, inode_bitmap_blocks as usize);
11        let inode_num = inode_bitmap.maximum();
12        let inode_area_blocks =
13            ((inode_num * core::mem::size_of::<DiskInode>() + BLOCK_SZ - 1) / BLOCK_SZ) as u32;
14        let inode_total_blocks = inode_bitmap_blocks + inode_area_blocks;
15        let data_total_blocks = total_blocks - 1 - inode_total_blocks;
16        let data_bitmap_blocks = (data_total_blocks + 4096) / 4097;
17        let data_area_blocks = data_total_blocks - data_bitmap_blocks;
18        let data_bitmap = Bitmap::new(
19            (1 + inode_bitmap_blocks + inode_area_blocks) as usize,
20            data_bitmap_blocks as usize,
21        );
22        let mut efs = Self {
23            block_device: Arc::clone(&block_device),
24            inode_bitmap,
25            data_bitmap,
26            inode_area_start_block: 1 + inode_bitmap_blocks,
27            data_area_start_block: 1 + inode_total_blocks + data_bitmap_blocks,
28        };
29        // clear all blocks
30        for i in 0..total_blocks {
31            get_block_cache(
32                i as usize,
33                Arc::clone(&block_device)
34            )
35            .lock()
36            .modify(0, |data_block: &mut DataBlock| {
37                for byte in data_block.iter_mut() { *byte = 0; }
38            });
39        }
40        // initialize SuperBlock
41        get_block_cache(0, Arc::clone(&block_device))
42        .lock()
43        .modify(0, |super_block: &mut SuperBlock| {
44            super_block.initialize(
45                total_blocks,
46                inode_bitmap_blocks,
47                inode_area_blocks,
48                data_bitmap_blocks,
49                data_area_blocks,
50            );
51        });
52        // write back immediately
53        // create a inode for root node "/"
54        assert_eq!(efs.alloc_inode(), 0);
55        let (root_inode_block_id, root_inode_offset) = efs.get_disk_inode_pos(0);
56        get_block_cache(
57            root_inode_block_id as usize,
58            Arc::clone(&block_device)
59        )
60        .lock()
61        .modify(root_inode_offset, |disk_inode: &mut DiskInode| {
62            disk_inode.initialize(DiskInodeType::Directory);
63        });
64        Arc::new(Mutex::new(efs))
65    }
66}
  • 第 10~21 行根据传入的参数计算每个区域各应该包含多少块。根据 inode 位图的大小计算 inode 区域至少需要多少个块才能够使得 inode 位图中的每个bit都能够有一个实际的 inode 可以对应,这样就确定了 inode 位图区域和 inode 区域的大小。剩下的块都分配给数据块位图区域和数据块区域。我们希望数据块位图中的每个bit仍然能够对应到一个数据块,但是数据块位图又不能过小,不然会造成某些数据块永远不会被使用。因此数据块位图区域最合理的大小是剩余的块数除以 4097 再上取整,因为位图中的每个块能够对应 4096 个数据块。其余的块就都作为数据块使用。

  • 第 22 行创建我们的 EasyFileSystem 实例 efs

  • 第 30 行首先将块设备的前 total_blocks 个块清零,因为我们的 easy-fs 要用到它们,这也是为初始化做准备。

  • 第 41 行将位于块设备编号为 0 块上的超级块进行初始化,只需传入之前计算得到的每个区域的块数就行了。

  • 第 54~63 行我们要做的事情是创建根目录 / 。首先需要调用 alloc_inode 在 inode 位图中分配一个 inode ,由于这是第一次分配,它的编号固定是 0 。接下来需要将分配到的 inode 初始化为 easy-fs 中的唯一一个目录,我们需要调用 get_disk_inode_pos 来根据 inode 编号获取该 inode 所在的块的编号以及块内偏移,之后就可以将它们传给 get_block_cachemodify 了。

通过 open 方法可以从一个已写入了 easy-fs 镜像的块设备上打开我们的 easy-fs :

// easy-fs/src/efs.rs

impl EasyFileSystem {
    pub fn open(block_device: Arc<dyn BlockDevice>) -> Arc<Mutex<Self>> {
        // read SuperBlock
        get_block_cache(0, Arc::clone(&block_device))
            .lock()
            .read(0, |super_block: &SuperBlock| {
                assert!(super_block.is_valid(), "Error loading EFS!");
                let inode_total_blocks =
                    super_block.inode_bitmap_blocks + super_block.inode_area_blocks;
                let efs = Self {
                    block_device,
                    inode_bitmap: Bitmap::new(
                        1,
                        super_block.inode_bitmap_blocks as usize
                    ),
                    data_bitmap: Bitmap::new(
                        (1 + inode_total_blocks) as usize,
                        super_block.data_bitmap_blocks as usize,
                    ),
                    inode_area_start_block: 1 + super_block.inode_bitmap_blocks,
                    data_area_start_block: 1 + inode_total_blocks + super_block.data_bitmap_blocks,
                };
                Arc::new(Mutex::new(efs))
            })
    }
}

它只需将块设备编号为 0 的块作为超级块读取进来,就可以从中知道 easy-fs 的磁盘布局,由此可以构造 efs 实例。

EasyFileSystem 知道整个磁盘布局,即可以从 inode位图 或数据块位图上分配的 bit 编号,来算出各个存储inode和数据块的磁盘块在磁盘上的实际位置。

// easy-fs/src/efs.rs

impl EasyFileSystem {
    pub fn get_disk_inode_pos(&self, inode_id: u32) -> (u32, usize) {
        let inode_size = core::mem::size_of::<DiskInode>();
        let inodes_per_block = (BLOCK_SZ / inode_size) as u32;
        let block_id = self.inode_area_start_block + inode_id / inodes_per_block;
        (block_id, (inode_id % inodes_per_block) as usize * inode_size)
    }

    pub fn get_data_block_id(&self, data_block_id: u32) -> u32 {
        self.data_area_start_block + data_block_id
    }
}

inode 和数据块的分配/回收也由它负责:

// easy-fs/src/efs.rs

impl EasyFileSystem {
    pub fn alloc_inode(&mut self) -> u32 {
        self.inode_bitmap.alloc(&self.block_device).unwrap() as u32
    }

    /// Return a block ID not ID in the data area.
    pub fn alloc_data(&mut self) -> u32 {
        self.data_bitmap.alloc(&self.block_device).unwrap() as u32 + self.data_area_start_block
    }

    pub fn dealloc_data(&mut self, block_id: u32) {
        get_block_cache(
            block_id as usize,
            Arc::clone(&self.block_device)
        )
        .lock()
        .modify(0, |data_block: &mut DataBlock| {
            data_block.iter_mut().for_each(|p| { *p = 0; })
        });
        self.data_bitmap.dealloc(
            &self.block_device,
            (block_id - self.data_area_start_block) as usize
        )
    }
}

注意:

  • alloc_datadealloc_data 分配/回收数据块传入/返回的参数都表示数据块在块设备上的编号,而不是在数据块位图中分配的bit编号;

  • dealloc_inode 未实现,不支持文件删除。

索引节点

服务于文件相关系统调用的索引节点层的代码在 vfs.rs 中。

EasyFileSystem 实现了我们设计的磁盘布局并能够将所有块有效的管理起来。但是对于文件系统的使用者而言,他们往往不关心磁盘布局是如何实现的,而是更希望能够直接看到目录树结构中逻辑上的文件和目录。为此我们设计索引节点 Inode 暴露给文件系统的使用者,让他们能够直接对文件和目录进行操作。 InodeDiskInode 的区别从它们的名字中就可以看出: DiskInode 放在磁盘块中比较固定的位置,而 Inode 是放在内存中的记录文件索引节点信息的数据结构。

// easy-fs/src/vfs.rs

pub struct Inode {
    block_id: usize,
    block_offset: usize,
    fs: Arc<Mutex<EasyFileSystem>>,
    block_device: Arc<dyn BlockDevice>,
}

block_idblock_offset 记录该 Inode 对应的 DiskInode 保存在磁盘上的具体位置方便我们后续对它进行访问。 fs 是指向 EasyFileSystem 的一个指针,因为对 Inode 的种种操作实际上都是要通过底层的文件系统来完成。

仿照 BlockCache::read/modify ,我们可以设计两个方法来简化对于 Inode 对应的磁盘上的 DiskInode 的访问流程,而不是每次都需要 get_block_cache.lock.read/modify

// easy-fs/src/vfs.rs

impl Inode {
    fn read_disk_inode<V>(&self, f: impl FnOnce(&DiskInode) -> V) -> V {
        get_block_cache(
            self.block_id,
            Arc::clone(&self.block_device)
        ).lock().read(self.block_offset, f)
    }

    fn modify_disk_inode<V>(&self, f: impl FnOnce(&mut DiskInode) -> V) -> V {
        get_block_cache(
            self.block_id,
            Arc::clone(&self.block_device)
        ).lock().modify(self.block_offset, f)
    }
}

下面我们分别介绍文件系统的使用者对于文件系统的一些常用操作:

获取根目录的 inode

文件系统的使用者在通过 EasyFileSystem::open 从装载了 easy-fs 镜像的块设备上打开 easy-fs 之后,要做的第一件事情就是获取根目录的 Inode 。因为我们目前仅支持绝对路径,对于任何文件/目录的索引都必须从根目录开始向下逐级进行。等到索引完成之后,我们才能对文件/目录进行操作。事实上 EasyFileSystem 提供了另一个名为 root_inode 的方法来获取根目录的 Inode :

// easy-fs/src/efs.rs

impl EasyFileSystem {
    pub fn root_inode(efs: &Arc<Mutex<Self>>) -> Inode {
        let block_device = Arc::clone(&efs.lock().block_device);
        // acquire efs lock temporarily
        let (block_id, block_offset) = efs.lock().get_disk_inode_pos(0);
        // release efs lock
        Inode::new(
            block_id,
            block_offset,
            Arc::clone(efs),
            block_device,
        )
    }
}

// easy-fs/src/vfs.rs

impl Inode {
    /// We should not acquire efs lock here.
    pub fn new(
        block_id: u32,
        block_offset: usize,
        fs: Arc<Mutex<EasyFileSystem>>,
        block_device: Arc<dyn BlockDevice>,
    ) -> Self {
        Self {
            block_id: block_id as usize,
            block_offset,
            fs,
            block_device,
        }
    }
}

root_inode 中,主要是在 Inode::new 的时候将传入的 inode_id 设置为 0 ,因为根目录对应于文件系统中第一个分配的 inode ,因此它的 inode_id 总会是 0 。同时在设计上,我们不会在 Inode::new 中尝试获取整个 EasyFileSystem 的锁来查询 inode 在块设备中的位置,而是在调用它之前预先查询并作为参数传过去。

文件索引

为了尽可能简化我们的实现,所有的文件都在根目录下面。于是,我们不必实现目录索引。文件索引的查找比较简单,仅需在根目录的目录项中根据文件名找到文件的 inode 编号即可。由于没有子目录的存在,这个过程只会进行一次。

// easy-fs/src/vfs.rs

impl Inode {
    pub fn find(&self, name: &str) -> Option<Arc<Inode>> {
        let fs = self.fs.lock();
        self.read_disk_inode(|disk_inode| {
            self.find_inode_id(name, disk_inode)
            .map(|inode_id| {
                let (block_id, block_offset) = fs.get_disk_inode_pos(inode_id);
                Arc::new(Self::new(
                    block_id,
                    block_offset,
                    self.fs.clone(),
                    self.block_device.clone(),
                ))
            })
        })
    }

    fn find_inode_id(
        &self,
        name: &str,
        disk_inode: &DiskInode,
    ) -> Option<u32> {
        // assert it is a directory
        assert!(disk_inode.is_dir());
        let file_count = (disk_inode.size as usize) / DIRENT_SZ;
        let mut dirent = DirEntry::empty();
        for i in 0..file_count {
            assert_eq!(
                disk_inode.read_at(
                    DIRENT_SZ * i,
                    dirent.as_bytes_mut(),
                    &self.block_device,
                ),
                DIRENT_SZ,
            );
            if dirent.name() == name {
                return Some(dirent.inode_number() as u32);
            }
        }
        None
    }
}

find 方法只会被根目录 Inode 调用,文件系统中其他文件的 Inode 不会调用这个方法。它首先调用 find_inode_id 方法尝试从根目录的 DiskInode 上找到要索引的文件名对应的 inode 编号。这就需要将根目录内容中的所有目录项都读到内存进行逐个比对。如果能够找到的话, find 方法会根据查到 inode 编号对应生成一个 Inode 用于后续对文件的访问。

这里需要注意的是,包括 find 在内所有暴露给文件系统的使用者的文件系统操作(还包括接下来将要介绍的几种),全程均需持有 EasyFileSystem 的互斥锁(相对的,文件系统内部的操作如之前的 Inode::new 或是上面的 find_inode_id 都是假定在已持有 efs 锁的情况下才被调用的,因此它们不应尝试获取锁)。这能够保证在多核情况下,同时最多只能有一个核在进行文件系统相关操作。这样也许会带来一些不必要的性能损失,但我们目前暂时先这样做。如果我们在这里加锁的话,其实就能够保证块缓存的互斥访问了。

文件列举

ls 方法可以收集根目录下的所有文件的文件名并以向量的形式返回,这个方法只有根目录的 Inode 才会调用:

// easy-fs/src/vfs.rs

impl Inode {
    pub fn ls(&self) -> Vec<String> {
        let _fs = self.fs.lock();
        self.read_disk_inode(|disk_inode| {
            let file_count = (disk_inode.size as usize) / DIRENT_SZ;
            let mut v: Vec<String> = Vec::new();
            for i in 0..file_count {
                let mut dirent = DirEntry::empty();
                assert_eq!(
                    disk_inode.read_at(
                        i * DIRENT_SZ,
                        dirent.as_bytes_mut(),
                        &self.block_device,
                    ),
                    DIRENT_SZ,
                );
                v.push(String::from(dirent.name()));
            }
            v
        })
    }
}

文件创建

create 方法可以在根目录下创建一个文件,该方法只有根目录的 Inode 会调用:

 1// easy-fs/src/vfs.rs
 2
 3impl Inode {
 4    pub fn create(&self, name: &str) -> Option<Arc<Inode>> {
 5        let mut fs = self.fs.lock();
 6        if self.modify_disk_inode(|root_inode| {
 7            // assert it is a directory
 8            assert!(root_inode.is_dir());
 9            // has the file been created?
10            self.find_inode_id(name, root_inode)
11        }).is_some() {
12            return None;
13        }
14        // create a new file
15        // alloc a inode with an indirect block
16        let new_inode_id = fs.alloc_inode();
17        // initialize inode
18        let (new_inode_block_id, new_inode_block_offset)
19            = fs.get_disk_inode_pos(new_inode_id);
20        get_block_cache(
21            new_inode_block_id as usize,
22            Arc::clone(&self.block_device)
23        ).lock().modify(new_inode_block_offset, |new_inode: &mut DiskInode| {
24            new_inode.initialize(DiskInodeType::File);
25        });
26        self.modify_disk_inode(|root_inode| {
27            // append file in the dirent
28            let file_count = (root_inode.size as usize) / DIRENT_SZ;
29            let new_size = (file_count + 1) * DIRENT_SZ;
30            // increase size
31            self.increase_size(new_size as u32, root_inode, &mut fs);
32            // write dirent
33            let dirent = DirEntry::new(name, new_inode_id);
34            root_inode.write_at(
35                file_count * DIRENT_SZ,
36                dirent.as_bytes(),
37                &self.block_device,
38            );
39        });
40
41        let (block_id, block_offset) = fs.get_disk_inode_pos(new_inode_id);
42        // return inode
43        Some(Arc::new(Self::new(
44            block_id,
45            block_offset,
46            self.fs.clone(),
47            self.block_device.clone(),
48        )))
49        // release efs lock automatically by compiler
50    }
51}
  • 第 6~13 行,检查文件是否已经在根目录下,如果找到的话返回 None

  • 第 14~25 行,为待创建文件分配一个新的 inode 并进行初始化;

  • 第 26~39 行,将待创建文件的目录项插入到根目录的内容中使得之后可以索引过来。

文件清空

在以某些标志位打开文件(例如带有 CREATE 标志打开一个已经存在的文件)的时候,需要首先将文件清空。在索引到文件的 Inode 之后可以调用 clear 方法:

// easy-fs/src/vfs.rs

impl Inode {
    pub fn clear(&self) {
        let mut fs = self.fs.lock();
        self.modify_disk_inode(|disk_inode| {
            let size = disk_inode.size;
            let data_blocks_dealloc = disk_inode.clear_size(&self.block_device);
            assert!(data_blocks_dealloc.len() == DiskInode::total_blocks(size) as usize);
            for data_block in data_blocks_dealloc.into_iter() {
                fs.dealloc_data(data_block);
            }
        });
    }
}

这会将之前该文件占据的索引块和数据块在 EasyFileSystem 中回收。

文件读写

从根目录索引到一个文件之后可以对它进行读写,注意,和 DiskInode 一样,这里的读写作用在字节序列的一段区间上:

// easy-fs/src/vfs.rs

impl Inode {
    pub fn read_at(&self, offset: usize, buf: &mut [u8]) -> usize {
        let _fs = self.fs.lock();
        self.read_disk_inode(|disk_inode| {
            disk_inode.read_at(offset, buf, &self.block_device)
        })
    }

    pub fn write_at(&self, offset: usize, buf: &[u8]) -> usize {
        let mut fs = self.fs.lock();
        self.modify_disk_inode(|disk_inode| {
            self.increase_size((offset + buf.len()) as u32, disk_inode, &mut fs);
            disk_inode.write_at(offset, buf, &self.block_device)
        })
    }
}

具体实现比较简单,需要注意在 DiskInode::write_at 之前先调用 increase_size 对自身进行扩容:

// easy-fs/src/vfs.rs

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

这里会从 EasyFileSystem 中分配一些用于扩容的数据块并传给 DiskInode::increase_size

将应用打包为 easy-fs 镜像

在第六章中我们需要将所有的应用都链接到内核中,随后在应用管理器中通过应用名进行索引来找到应用的 ELF 数据。这样做有一个缺点,就是会造成内核体积过度膨胀。同时这也会浪费内存资源,因为未被执行的应用也占据了内存空间。在实现了我们自己的文件系统之后,终于可以将这些应用打包到 easy-fs 镜像中放到磁盘中,当我们要执行应用的时候只需从文件系统中取出ELF 执行文件格式的应用 并加载到内存中执行即可,这样就避免了上面的那些问题。

easy-fs-fuse 的主体 easy-fs-pack 函数就实现了这个功能:

 1// easy-fs-fuse/src/main.rs
 2
 3use clap::{Arg, App};
 4
 5fn easy_fs_pack() -> std::io::Result<()> {
 6    let matches = App::new("EasyFileSystem packer")
 7        .arg(Arg::with_name("source")
 8            .short("s")
 9            .long("source")
10            .takes_value(true)
11            .help("Executable source dir(with backslash)")
12        )
13        .arg(Arg::with_name("target")
14            .short("t")
15            .long("target")
16            .takes_value(true)
17            .help("Executable target dir(with backslash)")
18        )
19        .get_matches();
20    let src_path = matches.value_of("source").unwrap();
21    let target_path = matches.value_of("target").unwrap();
22    println!("src_path = {}\ntarget_path = {}", src_path, target_path);
23    let block_file = Arc::new(BlockFile(Mutex::new({
24        let f = OpenOptions::new()
25            .read(true)
26            .write(true)
27            .create(true)
28            .open(format!("{}{}", target_path, "fs.img"))?;
29        f.set_len(8192 * 512).unwrap();
30        f
31    })));
32    // 4MiB, at most 4095 files
33    let efs = EasyFileSystem::create(
34        block_file.clone(),
35        8192,
36        1,
37    );
38    let root_inode = Arc::new(EasyFileSystem::root_inode(&efs));
39    let apps: Vec<_> = read_dir(src_path)
40        .unwrap()
41        .into_iter()
42        .map(|dir_entry| {
43            let mut name_with_ext = dir_entry.unwrap().file_name().into_string().unwrap();
44            name_with_ext.drain(name_with_ext.find('.').unwrap()..name_with_ext.len());
45            name_with_ext
46        })
47        .collect();
48    for app in apps {
49        // load app data from host file system
50        let mut host_file = File::open(format!("{}{}", target_path, app)).unwrap();
51        let mut all_data: Vec<u8> = Vec::new();
52        host_file.read_to_end(&mut all_data).unwrap();
53        // create a file in easy-fs
54        let inode = root_inode.create(app.as_str()).unwrap();
55        // write data to easy-fs
56        inode.write_at(0, all_data.as_slice());
57    }
58    // list apps
59    for app in root_inode.ls() {
60        println!("{}", app);
61    }
62    Ok(())
63}
  • 为了实现 easy-fs-fuseos/user 的解耦,第 6~21 行使用 clap crate 进行命令行参数解析,需要通过 -s-t 分别指定应用的源代码目录和保存应用 ELF 的目录而不是在 easy-fs-fuse 中硬编码。如果解析成功的话它们会分别被保存在变量 src_pathtarget_path 中。

  • 第 23~38 行依次完成:创建 4MiB 的 easy-fs 镜像文件、进行 easy-fs 初始化、获取根目录 inode 。

  • 第 39 行获取源码目录中的每个应用的源代码文件并去掉后缀名,收集到向量 apps 中。

  • 第 48 行开始,枚举 apps 中的每个应用,从放置应用执行程序的目录中找到对应应用的 ELF 文件(这是一个 HostOS 上的文件)并将数据读入内存。接着需要在我们的 easy-fs 中创建一个同名文件并将 ELF 数据写入到这个文件中。这个过程相当于将 HostOS 上的文件系统中的一个文件复制到我们的 easy-fs 中。

easy-fs-fuse 不用担心块缓存中的修改没有写回磁盘,因为在 easy-fs 操作过程中实现了 block_cache_sync_all 函数用以写回每次操作的结果。