最近有操作系统的课程设计，我选题是 模拟实现一个文件系统，语言不限。

用 C 去实现很好，但是考虑到自己两年没写 C 了，加上最近 node 看得多，索性选 node 来做了。

名字想好了就叫做 nfs

https://github.com/eczn/nfs.git

# 理解文件系统 ↵

文件系统满足了我们对磁盘存储的需求，使得我们可以把数据以文件的形式存进去、也可以以文件夹的形式组织管理文件、至于命名和删除这些操作，也是它来搞定的，它是一种对硬盘的抽象。

我们的硬盘提供了底层的、供 CPU 触发的 IO 中断来读取数据。试想象一个 3.5 寸的硬盘，将其分成 100 格，CPU 可以发出请求，读取第 N 格，随后磁盘会把第 N 格读取出来，返回给处理器进行下一步处理。

也就是说，硬盘仅仅提供了读写第 N 格等等这样底层的、低级的 API，根本没有提供现代编程语言里面的那些读取文件、读取目录的API，那这些功能哪来的？

当然，说简单些，这些比较高级的存储方式是操作系统在磁盘提供的底层API的基础上，所做的一系列对硬盘的高级规划实现的，这一套实现可以称呼为 文件系统。

更进一步说，文件系统作为磁盘和应用程序的中间层，向下挖掘底层API的能力，向上提供高级 IO 接口。

# 模拟硬盘 ↵

文件系统都会占用一定的硬盘空间来维持正常使用，这也是为什么硬盘格式化之后可用空间会变少的原因。

首先既然要模拟文件系统首先要模拟磁盘，我的做法是在 Windows/OSX 下创建一个填满 0 的文件作为 磁盘 使用。

进一步的设计目标是：

一个磁盘可以分割成若干块，读取和写入都是以块为单位的
读取 / 写入数据到某一个块

# 创建这种磁盘 && 填 0 的方法

00const fs = require('then-fs')
01    , { DISK_SIZE } = require('config')
02    , void_buf = Buffer.alloc(DISK_SIZE, 0, "binary")
03
04fs.writeFile('./FAKE_DISK.nfs', void_buf).then(ok => {
05    console.log('[ Finish ] createDisk'); 
06}).catch(err => {
07    console.log('[ ERROR ] createDisk'); 
08    console.log(err);
09});

简而言之，就是创建一个空 buffer 然后存进去。

然后再在这上面模拟文件系统的操作

# 读写特定的块

00/**
01 * @description 读取磁盘上的某个块 
02 * @param {int} block_position 
03 * @return Promise<Buffer>
04 */
05Disk.prototype.read = function(block_position = 0){
06    let { BLOCK_SIZE, NFS_SIZE } = this; 
07    let buf = Buffer.alloc(BLOCK_SIZE, 0); 
08
09    return fs.read(
10        // File Descriptor 
11        this.disk_fd, 
12        // The Target 
13        buf,
14        // Offset On Buffer 
15        0, 
16        // Read Legnth 
17        BLOCK_SIZE, 
18        // Position 
19        NFS_SIZE + BLOCK_SIZE * block_position
20    ).then(count => {
21        return buf; 
22    })
23}
24
25/**
26 * @description 将 buf 写入到某个块 
27 * @param {int} block_position 
28 * @param {Buffer} block_position 
29 */
30Disk.prototype.write = function(block_position, buf){
31    // fs.write(fd, buffer[, offset[, length[, position]]], callback)
32    let { BLOCK_SIZE, NFS_SIZE } = this; 
33
34    return fs.write(
35        this.disk_fd, 
36        buf, 
37        0, 
38        buf.length, 
39        NFS_SIZE + BLOCK_SIZE * block_position
40    ); 
41}

# 模拟 nfs ↵

我准备模拟的一个文件系统 nfs 的结构如下：

我的意思是：

利用前面的 nfs 占用去管理后面的 N 个块。
文件系统的实质就是占用有限的空间高效地管理一个线性磁盘块组

# 目录树

目录树就是指这样的结构:

00var root = {
01    name: '根目录', 
02    isDirectory: true
03    files: [
04        {
05            name: '根目录下的文件 A', 
06            ext: 'txt',
07            isDirectory: false,
08            A1: '存储在第 1 个块里'
09        }, 
10        {
11            name: '根目录下的文件夹 F', 
12            isDirectory: true,
13            files: [
14                {
15                    name: '文件夹 F 下的文件 B', 
16                    ext: 'txt',
17                    isDirectory: false,
18                    A1: '存储在第 N 个块里'
19                }
20            ]
21        }
22    ]
23}

它是整个文件夹的数据描述，存储着文件和文件夹的树形结构，并且标注了每一个文件存在磁盘的第 N 块（通过 A1 字段）。

当然实际上有些文件需要多个块来存储，因此我设计的时候吧 A1 设计为数组了（表示数据存储位置，相当于索引）。

# FAT

如果前面目录树的某个文件占用了第 1 个块，那么之后的其他文件就应该避免吧数据覆盖到第 1 个块，所以必须引入某种数据结构来标志某个块是否被占用，这里我也选择了数组来做，如下：

00// 一共 N 个元素，0代表空闲，1代表被占用 
01let FAT = [1, 0, 0, ..., 0];

对了 FAT 的全写是： File Allocation Table 意思是文件分配表

# JSON Best

nfs 占用区我选用了 JSON 来存储，理由是：

抽象程度足够高，易于实现, 易于操作
表达树的结构方便，可变长

缺点相对的也很明显：

性能糟糕
冗余大，JSON 是字节 BASE 的，如果用纯二进制存储，应该可以利用到每一位
存储极为不方便，只能一口气把整个 nfs 占用覆写

# 格式化操作

在前面写的模拟磁盘在使用 nfs 前首先需要格式化，以下是我的格式化方案（假设模拟磁盘容量为 20 MB）：

前 4 MB 用于存储 nfs 占用，后 16 MB 存储真实的二进制数据

基于如上写法，先写好最小化 nfs :

00// nfs_minimum.js 
01const { BLOCK_COUNT } = require('./config'); 
02
03module.exports = {
04    // Tree 目录树  
05    root: {
06        isDirectory: true,
07        cTime: Date.now(), 
08        files: []
09    }, 
10    // File Allocation Table 
11    // 搞个数组然后填 0 
12    FAT: new Array(BLOCK_COUNT).fill(0)
13}

然后在创建磁盘的时候按照如下方法实现格式化：

00const fs = require('then-fs')
01    , nfsMinimum = require('./nfs_minimum')
02    // 转为json 然后转为 buffer 
03    , nfs_buf = Buffer.from(JSON.stringify(nfsMinimum), "binary");
04
05function createDisk(opt){
06    let { DISK_LOCATION, DISK_SIZE } = opt; 
07
08    // 空数据填 0 
09    // 20 MB 空 buffer 
10    const void_buf = Buffer.alloc(DISK_SIZE, 0, "binary"); 
11
12    // 吧最小化 nfs 覆盖到 void_buf 上 总大小是 DISK_SIZE
13    let disk_data = Buffer.concat(
14        [nfs_buf, void_buf],
15        DISK_SIZE
16    );
17
18    return fs.writeFile(DISK_LOCATION, disk_data).then(ok => {
19        // 搞定了 
20        console.log('[ Finish ] createDisk'); 
21        return 'ok'; 
22    }).catch(err => {
23        console.log('[ ERROR ] createDisk'); 
24        console.log(err);
25        return Promise.reject(err); 
26    }); 
27}

# 保存当前的 FAT 和目录树状态到虚拟磁盘

00/**
01 * @description store nfs to fake_disk
02 */
03Nfs.prototype.store2disk = function(){
04    const NFS_SIZE = this.disk.NFS_SIZE
05        , void_buf = Buffer.alloc(NFS_SIZE, 0, "binary")
06        , nfs_buf = Buffer.from(this.toJSON(), "binary");
07
08    let disk_data = Buffer.concat(
09        [nfs_buf, void_buf],
10        NFS_SIZE
11    );
12
13    // fs
14    return this.disk.writeRaw(
15        // write disk_data to position 0  
16        disk_data, 0
17    ); 
18}

每次操作完 nfs 的数据结构之后都应该吧它重新存进虚拟磁盘里

# FAT 分配和释放

这里就不贴全部了，比较杂，只贴最重要的分配：

00/**
01 * @description 申请一定数量的块
02 * @param {int} need_block 
03 */
04Nfs.prototype.fatAllocBlock = function(need_block){
05    let FAT = this.FAT; 
06    let res = []; 
07
08    for (let i = 0; i < FAT.length; i++){
09        let info = FAT[i]; 
10        if (info === 0){
11            res.push(i); 
12        }
13        // 如果收集够了就结束 
14        if (res.length === need_block){
15            break; 
16        }
17    }
18
19    // 设置 FAT 对应位置为 已占用 
20    res.forEach(i => {
21        // 已占用 
22        FAT[i] = 1; 
23    }); 
24    return res; 
25
26    // 后续还应该调用 Nfs.prototype.store2disk 做持久化 
27}

我的 FAT 的分配算法：

遍历 FAT 如果有 0 的就收集到 res 整个数组里
如果 res 的长度达到了 need_block 就结束并吧对应的 FAT 置 0

# nfs 错误处理

00// error.js
01let errorTable = {
02    "4000": "创建 $$ 的时候发现文件或目录重复", 
03    "4001": "$$ 不存在 !", 
04    "4002": "把数据写进 $$ 这个目录是非法的"
05}
06
07module.exports = function(code, args = []){
08    let tpl = errorTable[code].split('$$'); 
09
10    let msg = tpl.reduce((acc, cur, idx) => {
11        return acc + cur + (args[idx] || ''); 
12    }, ''); 
13
14    return Promise.reject({
15        code, 
16        msg: msg
17    }); 
18}

有时候会出现内部的异常，应该简单处理。

# $ ls 的实现

ls 就是列出某个目录下的文件或者某个文件

00/**
01 * @description 列出文件 
02 * @param {String} path_str
03 */
04Nfs.prototype.ls = function(path_str){
05    let path = path_str.split('/').slice(1).filter(e => e);
06
07    return path.reduce((node, cur) => {
08        if (!node) return node; 
09    
10        let remain = node.files.filter(file => file.filename === cur)[0];
11        
12        return remain; 
13    }, this.root); 
14}

树的遍历有很多实现方法。

# $ touch 的实现

创建一个空文件

00/**
01 * @description create a blank file to path_str
02 * @param {String} path_str
03 * @param {String} ext
04 */
05Nfs.prototype.touch = function(path_str, ext){
06    // let path = path_str.split('/').slice(1).filter(e => e);
07    const temp = path_str.lastIndexOf('/')
08        , path_dir = path_str.substring(0, temp)
09        , filename = path_str.split('/').pop()
10        , dir = this.ls(path_dir)
11
12    // Touch 
13    let conflict = dir.files.some(e => e.filename === filename); 
14
15    if (conflict){
16        return error(4000, [path_str]);
17    } else {
18        dir.files.push({
19            filename, 
20            ext, 
21            isDirectory: false,
22            cTime: Date.now(), 
23            size: 0, 
24            A1: []
25        }); 
26    }
27
28    return this.store2disk(); 
29}

写文件之前得先在目录树创建好文件节点

# $ mkdir 的实现

00/**
01 * @description 在 node 上创建一个文件夹 
02 * @param {Object} node 
03 * @param {String} filename 
04 */
05Nfs.prototype._mkdirOnNode = function(node, filename){
06    let dir_node = {
07        isDirectory: true,
08        cTime: Date.now(), 
09        filename: filename, 
10        files: []
11    }
12
13    node.files.push(dir_node); 
14
15    return dir_node; 
16}
17
18/**
19 * @description 在 path_str 的父级目录创建文件夹，非递归 
20 * @param {String} path_str 
21 */
22Nfs.prototype.mkdir = function(path_str){
23    const temp = path_str.lastIndexOf('/')
24        , path_dir = path_str.substring(0, temp)
25        , filename = path_str.split('/').pop()
26        , dir = this.ls(path_dir)
27
28    // Touch 
29    let conflict = dir.files.some(e => e.filename === filename); 
30
31    if (conflict) {
32        return error(4000, [path_str]);
33    } else {
34        this._mkdirOnNode(dir, filename); 
35    }
36
37    return this.store2disk(); 
38}

创建文件夹，首先找出父节点，然后在它的 files 下创建一个文件夹节点

# $ df 的实现

00/**
01 * @description 列出 nfs 磁盘信息
02 */
03Nfs.prototype.df = function(){
04    let {
05        DISK_BASE,
06        DISK_LOCATION,
07        DISK_SIZE,
08        BLOCK_SIZE,
09        BLOCK_COUNT,
10        NFS_SIZE,
11        RAW_SIZE
12    } = this.disk;
13
14    let df = {
15        DISK_BASE,
16        DISK_LOCATION,
17        DISK_SIZE,
18        BLOCK_SIZE,
19        BLOCK_COUNT,
20        NFS_SIZE,
21        RAW_SIZE
22    }
23
24    df.REMAIN_SIZE = this.FAT.reduce((sum, cur) => {
25        if (cur === 0){
26            sum = sum + BLOCK_SIZE; 
27        }
28
29        return sum; 
30    }, 0); 
31
32    df.USED_SIZE = (df.RAW_SIZE - df.REMAIN_SIZE) + df.NFS_SIZE; 
33
34    df.USER_USED_SIZE = df.USED_SIZE - df.NFS_SIZE; 
35
36    return df; 
37}

返回文件信息的方法，包括剩余空间等

# nfs 之上的读写文件

00/**
01 * @description 获取文件所在的区块 
02 * @param {Object} node 
03 */
04Nfs.prototype.getFileIndex = function(node){
05    return node.A1; 
06}
07
08/**
09 * @description 读取某个文件、或者目录 
10 * @param {String} path_str 
11 */
12Nfs.prototype.read = function(path_str){
13    let file_node = this.ls(path_str); 
14
15    if (file_node.isDirectory){
16        return file_node.files; 
17    } else {
18        // file_indexs 
19        // readList 就是 A1 
20        // 根据上面的块索引来读取文件 并且要给出文件总大小 
21        return this.disk.readList(
22            this.getFileIndex(file_node), 
23            file_node.size
24        ); 
25    }
26}
27
28/**
29 * @description 覆盖写入数据到某文件、如果是目录则会报错 4002  
30 * @param {*} path_str 
31 * @param {*} buf_data 
32 */
33Nfs.prototype.write = function(path_str, buf_data){
34    let file_node = this.ls(path_str); 
35
36    // 不是 Buffer 返回 0 
37    if (!Buffer.isBuffer(buf_data)) return Promise.resolve(0);
38    // 错误 
39    if (file_node.isDirectory) return error(4002, [path_str]); 
40        
41    let BLOCK_SIZE = this.disk.BLOCK_SIZE; 
42    let newSize = buf_data.length; 
43    let newBlockCount = Math.ceil(newSize / BLOCK_SIZE); 
44
45    let preSize = file_node.size;
46    let preBlockCount = Math.ceil(preSize / BLOCK_SIZE); 
47
48    let preA1 = file_node.A1; 
49    let deltaCount = newBlockCount - preBlockCount; 
50
51    if (deltaCount >= 0){
52        // 连接 申请 增长 
53        let inc = this.fatAllocBlock(deltaCount); 
54        file_node.A1 = preA1.concat(inc); 
55    } else {
56        // 截短 释放 缩短 
57        file_node.A1 = preA1.slice(0, cha); 
58        let toRelease = preA1.slice(cha); 
59
60        this.fatRelease(toRelease); 
61    }
62
63    file_node.size = newSize; 
64
65    /**
66     * Write Data 
67     */
68    return this.store2disk().then(ok => {
69        // 跟上面的 readList 类似 
70        return this.disk.writeList(
71            file_node.A1, 
72            buf_data
73        );
74    }).catch(err => {
75        console.log(err); 
76    }); 
77    
78}

底层到高层

# 具体的实现 ↵

请看 https://github.com/eczn/nfs