使用Rust实现一个简单的文件系统

匿名小葫芦

可能是精神分裂的多个用户 | makeflow.com

0x01 前言

你是否好奇一个文件系统是如何工作的？你是否见过 Electron 的 ASAR 文件？来试试一起根据文件系统的基本概念实现一个简单的文件系统吧！

为什么说它是一个简单的文件系统呢？因为本文中将要讲解和实现的文件系统仅仅实现了基本的读取写入和列目录操作，并且是基于内存和文件的，相对于真实世界中 NTFS、EXT系列等在内核中实现并将数据存储在磁盘上的操作系统有较大的区别。

虽然 Unix 中可以通过 FUSE 实现一个文件系统，但考虑到它将会引入许多与文件系统概念无关的信息并且不是跨平台实现，我们将不会使用它，而是选择模仿真实世界中的文件系统的构造在一个文件中存储数据，并实现基本的编程 API。

本文将一本正经的指引你设计一个类似文件系统但又类似压缩文件，基于内存并同时可以保存到单个文件中的假文件系统。

前排提示：本文并非实现一个真正的文件系统，其中的代码及其理论也未经验证和测试，仅用于展示及学习文件系统的基本概念

0x02 了解文件系统结构

以 NTFS 为例，文件系统的结构主要分为四部分，分别为: Partition Boot Sector、Master File Table、System File、User Data [1]，它们的作用如下：

Partition Boot Sector，分区引导扇区，记录了分区的基本信息如：OEM ID、BPB 等
Master File Table，主文件标，记录了分区中的目录结构、文件位置等信息
System File，系统文件，包含 NTFS 日志、配额等信息 ( NTFS 是一个日志式文件系统 )
User Data，用户数据，用户存储在分区中的文件数据

0x03 文件结构提取和设计

很幸运我们并不需要设计一个高可用并且可以商用的文件系统，所以接下来将要确定一个简单的文件系统到底要包含哪些信息，以及如何利用手上现有的技术简化以避免直接处理二进制数据。

首先我们的文件系统并不会用于安装一个操作系统，所以 Partition Boot Sector 这一部分可以去掉。

而 MFT 这一部分则是必须的，虽然平常在图形化以及命令行中可以清晰的看到目录结构和文件位置，但文件真正存储于硬盘中的时候是一个扁平化且连续的结构，所以仍然需要一个位置来记录文件系统到底包含了哪些文件，以及它们的结构和尺寸。

系统文件这一步也同样是可以省略的部分，实现一个简单的学习用途的文件系统不需要考虑到性能和安全等问题。

所以最终我们的文件系统只需要两部分信息：MFT 长度、MFT 数据和用户数据部分。

接下来需要确定的是 MFT 数据如何存储以及包含哪些信息，仍然是考虑到我们的文件系统讲仅用于学习用途，MFT 的数据格式可以定为 JSON，为了简化遍历的过程和数据结构，在存储文件时将直接使用文件的完整路径作为文件的索引，同样 MFT 中常见的偏移位置将不会被记录。

根据以上思路可以得出 MFT 中可以只包含文件路径、文件长度两个信息。

0x04 代码中的数据结构

本文的目的是演示一个最简单的，只包含读写的文件系统，所以目前将不会考虑 MFT 存储到文件后再次读取时反序列化所对应的数据结构定义。

所以只需要确定两个数据类型：存储所有文件的数据结构、存储单个文件及它的信息的数据结构

鉴于无需考虑性能，以及前文中提到过因为一些原因这个文件系统将不会出现文件树，并且一般文件系统并不会允许同一个目录中出现同名的文件，使用 HashMap 存储文件列表将会是一个方便快捷的选择。

同时为了给整体的设计增加一些趣味性以及减少加载后的内存，文件系统还加入了压缩特性，所以现在我们需要的数据类型以及基本实现看起来类这样：

// 内部使用的数据类型
#[derive(Clone)]
struct InternalFile {
    path: String,
    // Deflate 压缩后的数据
    pub data: Vec<u8>,
    // 压缩前的尺寸
    pub actual_size: usize
}
impl InternalFile {
    pub fn size(&self) -> usize {
        self.data.len()
    }
}

// API 返回给外部的数据类型
pub struct File {
    pub data: Vec<u8>,
    pub compressed_size: usize
}
impl File {
    pub fn size(&self) -> usize {
        self.data.len()
    }
}

pub struct FileSystem {
    files: HashMap<String, InternalFile>
}

0x05 实现

基于前文提到的技术，例子中使用了 JSON 和 Libflate 两个外部库来帮助我们实现功能并减少工作量。

"Talk is cheap, show me the code"，所以先来看看我们将要实现的代码，再来讲解思路吧！

extern crate libflate;
extern crate json;

use json::object;
use std::collections::HashMap;
use std::path::{Path, PathBuf};
use std::io::{Read, Write};
use std::fs;
use std::collections::hash_map::DefaultHasher;
use std::hash::Hasher;
use fs::libflate::deflate::{Encoder, Decoder};

// 内部使用的数据类型
#[derive(Clone)]
struct InternalFile {
    path: String,
    // Deflate 压缩后的数据
    pub data: Vec<u8>,
    // 压缩前的尺寸
    pub actual_size: usize
}
impl InternalFile {
    pub fn size(&self) -> usize {
        self.data.len()
    }
}

// API 返回给外部的数据类型
pub struct File {
    pub data: Vec<u8>,
    pub compressed_size: usize
}
impl File {
    pub fn size(&self) -> usize {
        self.data.len()
    }
}

pub struct FileSystem {
    files: HashMap<String, InternalFile>
}
impl FileSystem {
    pub fn new() -> FileSystem {
        FileSystem {
            files: HashMap::new(),
        }
    }

    // 写入单个文件
    pub fn write(&mut self, path: &str, data: &[u8]) {
        // 载入内存时使用 Deflate 算法压缩以便节省内存空间
        let mut encoder = Encoder::new(Vec::new());
        encoder.write_all(&data).unwrap();
        
        self.files.insert(
            calculate_hash(&path.to_string().as_bytes()),
            InternalFile {
                path: path.to_string(),
                data: encoder.finish().into_result().unwrap(),
                actual_size: data.len()
            },
        );
    }

    // 读取单个文件
    pub fn read(&self, path: &str) -> Result<File, &str> {
        let res = self.files.get(&calculate_hash(&path.to_string().as_bytes()));
        
        match res {
            Some(file) => {
                // 使用 Deflate Decoder 解压缩
                let mut decoder = Decoder::new(&file.data[..]);
                let mut buf = Vec::new();
                decoder.read_to_end(&mut buf).unwrap();
                Ok(File {
                    data: buf,
                    compressed_size: file.data.len()
                })
            },
            None => Err("No such file"),
        }
    }

    // 获取压缩后的尺寸
    pub fn get_size(&self) -> usize {
        let mut total_size = 0;
        for (_, file) in self.files.iter() {
            total_size += file.size();
        }

        total_size
    }
    
    // 获取压缩前的尺寸
    pub fn get_actual_size(&self) -> usize {
        let mut total_size = 0;
        for(_, file) in self.files.iter() {
            total_size += file.actual_size;
        }
        
        total_size
    }

    // 获取文件系统中的文件总数
    pub fn get_file_count(&self) -> usize {
        self.files.len()
    }

    // 递归列出指定目录下的文件
    pub fn dir(&self, directory: &str) -> Vec<String>{
        let directory = Path::new(directory).join("");
        let mut file = Vec::new();
        for path in self.list() {
            // 我们的文件系统并非真实的树状结构，所以只需要判断文件路径以指定路径开始即可
            if path.as_path().starts_with(&directory) {
                file.push(path.to_str().unwrap().to_string())
            }
        }
        file
    }

    // 递归列出所有文件
    pub fn list(&self) -> Vec<PathBuf> {
        let mut list = Vec::new();
        for (_, file) in &self.files {
            list.push(PathBuf::from(&file.path));
        }

        list
    }
    
    // 将文件系统数据转存到文件
    pub fn save<T: AsRef<Path>>(&self, path: T) {
        let header_bytes = b"FSDUMP";
        let mft_bytes = generate_mft(self.files.iter().map(|(_, file)| file.clone()).collect());

        let mut f = fs::File::create(&path).unwrap();
        f.write(header_bytes).unwrap();
        // MFT length, usize to bytes = 8 bytes
        f.write(&(mft_bytes.len() as u64).to_le_bytes()).unwrap();
        // MFT data
        f.write(&mft_bytes).unwrap();
        // File contnt
        for (_, file) in &self.files {
            f.write(&file.data).unwrap();
        }
    }
    
    pub fn load<T: AsRef<Path>>(&self, path: T) {
        // TODO: 尝试一下实现吧！
    }
}

fn calculate_hash<>(t: &[u8]) -> String {
    // 没有特殊需求，使用 HashMap 默认的 Hasher 即可
    let mut h = DefaultHasher::new();
    h.write(&t);
    format!("{:x}", h.finish())
}

fn generate_mft (files: Vec<InternalFile>) -> Vec<u8> {
    let mut file_list = json::JsonValue::new_array();
    for file in files.iter() {
        file_list.push(object!{
            // 加载时所有文件均会被写入内存，所以记录尺寸连续读取即可
            "length" => file.size(),
            "path" => file.path.clone()
        }).unwrap();
    }
    
    file_list.dump().as_bytes().to_vec()
}

0x06 实现中的思考

文件存储结构

为什么要使用字符串存储目录名，并使用 HashMap 作为存储所有文件的容器？这一点首先是考虑到一般文件系统使用的是 B-Tree 的方式来存储文件和目录结构，但引入 B-Tree 概念将会大幅度增加文章的概念数量、长度，以及代码复杂度。另外考虑到作为一个例子或是一个存储少量信息的文件系统，文件路径大概率是固定的，将数据扁平存储不会带来可见的性能问题和弊端，甚至有利于快速实现一个基本的列目录功能。

文件压缩算法

例子中使用的是 Deflate 算法，选择它的原因是在常见算法中解压缩速度相对较快[2]，相比于 pithy、lz4f、lzg 等冷门的算法，Deflate 是 ZIP 文件背后最常见的算法，且常见于 Apache、Nginx 等主流软件当中。

MFT 中不记录偏移

在 MFT 中仅记录文件尺寸而不记录偏移量的原因是设计时不打算为这个简单的文件系统增加大文件的支持，MFT 实现中文件的顺序是有序的，并且也没有像真实的文件系统一样提供单独修改其中一部分数据的能力，所以实际上可以在读取 MFT 时根据顺序和之前的文件尺寸总和来确定下一个文件的偏移位置。

现实世界中的应用

除了了解文件系统以及压缩文件大概的工作方式，这个例子是否还有其他意义？实际上除了尝试编译代码，运行然后删除以外还可以基于类似的思路实现更多奇妙的功能，如：将多个动态链接库文件打包成为一个文件并在启动后从内存中调用它们，甚至将这个文件附加在可执行文件的末尾实现将调用多个外部库且无法静态编译的程序转化为单个可执行程序。

虽然自解压文件也可以做到，但是为什么不尝试一下更多的技术挑战呢？

使用 Rust 而不是 Javascript

显然在不考虑性能的场景下选择 Rust 单纯只是因为作者随手选择了 Rust。

0x07 测试代码

本文中提到的所有代码可在 Rust 1.42.0 中编译通过于执行

依赖库版本:

json: 0.11.13
libflate: 0.1.18

extern crate json;

mod fs;
use std::io::{stdin, Read};
use self::fs::*;

struct FakeFile<'a> {
    path: &'a str,
    data: &'a [u8],
}

fn main() {
    let files = [
        FakeFile {
            data: b"hello, world",
            path: "/file.txt"
        },
        FakeFile {
            data: b"text file",
            path: "/folder/fileA"
        },
        FakeFile {
            data: b"another text file",
            path: "/folder/fileB"
        },
        FakeFile {
            data: b"",
            path: "/empty"
        },
        FakeFile {
            data: &std::fs::read("C:\\Windows\\explorer.exe").unwrap(),
            path: "/explorer.exe"
        }
    ];

    let mut fs = FileSystem::new();
    for file in files.iter() {
        fs.write(file.path, &file.data)
    }
    println!("FileSystem has {} files with compressed size {} bytes, actual {} bytes\n", fs.get_file_count(), fs.get_size(), fs.get_actual_size());

    for path in fs.list() {
        let path = path.to_str().unwrap();
        let file = fs.read(path).unwrap();
        let len = if file.data.len() > 10 {
            10
        } else {
            file.data.len()
        };
        let content_preview = format!("{:x?}", &file.data[..len]);
        println!("FileSystem has ({} bytes/{} bytes) file {} with content: \"{}\"", file.compressed_size, file.size(), path, &content_preview);
    }

    println!("\n");
    let dir = "/folder";
    for path in fs.dir(dir) {
        println!("Directory \"{}\" have file {}", dir, path);
    }

    println!("\n\nPress enter key to exit...");
    fs.save("./test.fsdump");
    let _ = stdin().read(&mut [0u8]).unwrap();
}

编译和运行

使用 Cargo 创建一个新的 Rust 项目
将实现章节中的代码保存为 "src/fs/mod.rs"
将测试代码章节中的代码保存为 "src/main.rs"
添加 Crates 引用
使用 "cargo run" 编译并运行测试代码

上述代码演示了如何初始化前文中实现的 FileSystem，写入文本数据与本地读取到的文件，并调用 FileSystem 对象中实现的列目录与获取文件内容等功能。

0x08 附录

[1] NTFS Basics, Active Data Recovery Software

[2] Squash Compression Benchmark, quixdb

Makeflow (makeflow.com) 是以流程为核心的项目管理工具，让研发团队能更容易地落地和改善工作流，提升任务流转体验及效率。如果你正为了研发流程停留在口头讨论、无法落实而烦恼，Makeflow 或许是一个可以尝试的选项。如果你认为 Makeflow 缺少了某些必要的特性，或者有任何建议反馈，可以通过 GitHub、语雀或页面客服与我们建立连接。

使用Rust实现一个简单的文件系统

使用Rust实现一个简单的文件系统

0x01 前言

0x02 了解文件系统结构

0x03 文件结构提取和设计

0x04 代码中的数据结构

0x05 实现

0x06 实现中的思考

文件存储结构

文件压缩算法

MFT 中不记录偏移

现实世界中的应用

使用 Rust 而不是 Javascript

0x07 测试代码

编译和运行

0x08 附录

Recommend

追踪和恢复页面访问历史

How to Keep Your JS Libraries Up to Date

How to Improve Interface Responsiveness With Web Workers

如何在 macOS 中使用 XPC 实现跨进程通讯？

带你简单了解 Android 中的 Message 机制

最新Android框架排行榜，上百项资源汇总不容错过

EFCore使用(1) - 添加创建数据库

Multi-Column UIPickerView in Xamarin Forms

Quick Start: Telling Your New React Native Install About your Existing Android T...

Adding Views and Modifiers to the Xcode Library

About Joyk