MENU

【代码札记】Java模拟二级文件系统 下

December 14, 2020 • Read: 192 • 瞎折腾

本系列将记述使用Java实现一个简单的二级文件系统的过程。这个项目是本学期专业课操作系统的第三个实验。上一篇文章说明了元数据的代码描述。本文将记述如何利用已经搭建好的代码构造一个简单的文件系统。



架构

为了避免单个代码文件过于冗长,我决定将文件系统和交互界面分开。其中文件系统使用单例模式,交互界面则是以主程序的方式,与命令行交互并调用文件系统完成用户意图的操作。

文件系统模拟器的大体框架如下:

package info.skyblond.os.exp.experiment3;

import info.skyblond.os.exp.experiment3.model.*;
import info.skyblond.os.exp.utils.CommonUtils;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 文件系统模拟器,提供对磁盘基本的读写和维护操作。
 */
public class Simulator {
    private static Simulator instance;

    private Simulator() {
    }

    public static synchronized Simulator getInstance() {
        if (instance == null) {
            instance = new Simulator();
        } 
        return instance;
    }

    // TODO ....
}

如果说元数据的设计是自底向上(从底层的Inode描述到上层已打开的文件),那么文件系统的设计就是自顶向下,从便于测试的角度看,先设计用户相关的内容会比较方便,更进一步说,先是用户的创建、查询和登录,然后是修改密码和删除用户。实践中往往一个功能并不能单独做完,还需要暂时放下,把别的做完再来继续当前的功能。例如删除用户的操作涉及到删除用户的目录文件,因此也要递归的删除用户目录下的所有文件,这时候就要求文件删除的功能。在此之前还得有文件读写的功能(对文件的操作除了撤销Inode、释放盘块,还要读写目录文件)。

抛开这些不谈,我们先说说最基本的问题:如何初始化一个磁盘?

格式化

为了方便后续代码并减少代码重复,本节的铺垫代码如下:

    /**
     * 数据文件
     */
    private File dataFile = null;

    public void setDataFile(File dataFile) {
        this.dataFile = dataFile;
    }

    /**
     * 返回一个随机访问文件,mode参见{@link RandomAccessFile}
     */
    public RandomAccessFile getRandomAccessFile(String mode) {
        try {
            return new RandomAccessFile(this.dataFile, mode);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

首先使用一个File作为磁盘文件,默认为null,单例模式下可以通过setter手动指定文件位置。而之后需要随机读写,因此提供一个简单的成员方法getRandomAccessFile,根据给定模式返回一个数据文件的RandomAccessFile对象。

铺垫的代码就这么多,下面是负责初始化的代码:

    /**
     * root用户默认密码
     */
    public static String ROOT_DEFAULT_PASSWORD = "password";

    /**
     * 初始化一个数据文件,默认创建一个
     */
    public void initDataFile() {
        try {
            CommonUtils.require(this.dataFile.createNewFile(), "Cannot create new data file.");
            var randomAccessFile = this.getRandomAccessFile("rw");
            randomAccessFile.seek(0);
            // 初始化足够大的文件
            for (int i = 0; i < BitMap.BLOCK_NUM; i++) {
                randomAccessFile.write(new byte[Inode.BLOCK_SIZE]);
            }

            // SystemInfo初始化
            var systemInfo = new SystemInfo(
                    UserTable.getInstance().byteCount(),
                    InodeTable.getInstance().byteCount()
            );
            var totalBytes = 0;
            totalBytes += systemInfo.byteCount();
            totalBytes += UserTable.getInstance().byteCount();
            totalBytes += InodeTable.getInstance().byteCount();
            totalBytes += BitMap.getInstance().byteCount();
            var totalBlock = CommonUtils.divCeil(totalBytes, Inode.BLOCK_SIZE);
            // 设置被元数据占用的块为已使用
            for (int i = 0; i <= totalBlock; i++) {
                BitMap.getInstance().set(i);
            }
            // 写入磁盘
            randomAccessFile.seek(0);
            randomAccessFile.write(systemInfo.toBytes());
            randomAccessFile.write(UserTable.getInstance().toBytes());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
            randomAccessFile.write(BitMap.getInstance().toBytes());
            randomAccessFile.close();

            // 初始化root用户
            CommonUtils.require(this.createUser("root", ROOT_DEFAULT_PASSWORD), "Cannot init user.");

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

既然是初始化,就得先创建一个文件。文件已经存在的情况下直接报错,避免误删造成数据丢失,尽管这个简易磁盘也不会记录什么重要的东西。随后是初始化文件大小,我采用的方法是写空白块,原则上也可以使用RandomAccessFile#setLength来设定文件大小,但是JavaDoc说扩展后的文件内容是不保证的,因此我更偏向于空文件全0的做法。

接着就是构造元数据了。UserTable和InodeTable默认应当为空,按照语义来说初始化应该在一切操作之前发生,自然这两个表也就应该是空的。如果不为空问题也不大,原则上也是有效数据。利用两个Table的大小(byteCount())创建出SystemInfo。同时还要统计这些元数据(SystemInfoUserTableInodeTableBitMap)总大小,然后在BitMap中计算出对应的块,避免后续创建文件的时候将元数据所在的块作为空闲块分配出去。

然后就是将这些元数据写入磁盘。最后创建一个默认的root用户,该用户的默认密码硬编码到程序中。其中createUser方法会将它产生的修改写入磁盘。

实际上在编写代码时,一开始是没有创建用户的方法的,最初的做法是将创建用户的操作直接展开写在那里。后来随着程序功能的完善,代码的不断重构,变成了现在文章中展现的样子。

下面在说创建用户之前,先来写几个基础的读数据的方法。

读元数据

由于我们不能直接把整个磁盘读进内存操作,因此需要经常读写元数据。本节编写从磁盘读取元数据的代码:

    /**
     * 读磁盘的SystemInfo
     */
    public SystemInfo readSystemInfo() {
        try (var inputStream = new FileInputStream(this.dataFile)) {
            // 直接读取最开头
            var result = new SystemInfo();
            var bytes = new byte[result.byteCount()];
            CommonUtils.require(result.byteCount() == inputStream.read(bytes), "Bytes not enough");
            result.loadFromBytes(bytes);
            return result;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取BitMap
     */
    public BitMap readBitMap() {
        var systemInfo = this.readSystemInfo();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            randomAccessFile.seek(systemInfo.getBitmapAddr());
            var bitmap = BitMap.getInstance();
            var bytes = new byte[bitmap.byteCount()];
            randomAccessFile.read(bytes);
            bitmap.loadFromBytes(bytes);
            return bitmap;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取InodeTable
     */
    public InodeTable readInodeTable() {
        var systemInfo = this.readSystemInfo();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            var table = InodeTable.getInstance();
            var bytes = new byte[table.byteCount()];
            randomAccessFile.read(bytes);
            table.loadFromBytes(bytes);
            return table;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取用户表
     */
    public UserTable readUserTable() {
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            var systemInfo = this.readSystemInfo();
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            var userTable = UserTable.getInstance();
            var bytes = new byte[userTable.byteCount()];
            randomAccessFile.read(bytes);
            userTable.loadFromBytes(bytes);
            return userTable;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

首先是读取SystemInfo,因为它在文件开头,所以直接使用流读出文件即可。并且这部分数据除了初始化之外,永远都是只读不写,因此不使用单例模式。

UserTableInodeTableBitMap则是根据SystemInfo的信息从磁盘读出对应的数据,更新单例对象。这里有一个编码时的约束:只有直接被操作系统调用的函数才可以调用这三个函数,其他函数只能使用getInstance取得实例。这种约束的原因是避免修改被丢弃:假设我正在创建文件,首先我读取用户的目录文件,发现它恰好用完一个盘块,因此修改Inode申请了新的盘块并追加了目录项,后续又调用创建文件的工具方法,而该方法上来就从磁盘中读取数据更新InodeTable,而这时对于目录文件Inode的修改还未写入磁盘。这就造成了修改被丢弃,但是由于这三个方法和其他的工具方法都在一个类中,难以控制谁调用了谁没调用,因此只能采用人为约束的方式来限制调用。

另外为了使用方便,避免出现下面的情况:

readUserTable();
var userTable = UserTable.getInstance();

这样的写法,默认读方法会返回已经更新的对象。

说完了这些,下面可以说一说如何创建用户了。

创建用户

创建用户的代码如下:


    /**
     * 创建用户,true表示成功
     */
    public boolean createUser(String username, String password) {
        // 读取用户表
        var userTable = this.readUserTable();
        if (userTable.get(username) != null) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var inodeTable = this.readInodeTable();
            var iIndex = inodeTable.requestNewInode(username);
            if (iIndex < 0) {
                return false; // 无可用Inode时返回false表示创建失败
            }

            var systemInfo = this.readSystemInfo();
            // 设置用户
            var result = userTable.set(username, password, iIndex);
            // 更新变化
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            // 返回用户最终创建成功与否
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

由于用户的总数量有限制(还记得UserTable中的USER_NUM字段吗),因此创建用户不一定成功。所以使用返回值来告诉调用者是否成功,如果不成功就要报错提示用户,如果是自动化过程(例如初始化),则应该抛出异常。

由于创建用户是操作系统会调用的方法,因此可以直接上来就读取硬盘数据更新内存,因此此时上一个操作已经完成,没有未写入的数据。之后再通过UserTable的set方法直接创建一个新用户,最后将修改写入磁盘即可。

要注意的一点是set方法在用户存在的时候也会返回true,并且是更新用户。因此在操作系统中应当避免创建已存在用户的问题,否则逻辑上会出问题,在程序上也会出现不可达的Inode(原本的Inode索引被新的索引替换,而原本的Inode没有释放)。

这里要额外说一嘴测试的事情。由于一开始代码都是自己编写的,任何未经测试的代码都是不可信的。所以并不能直接在JUnit中用自己的代码写,再用自己的代码读(代码指工具方法)。虽然在编写代码的时候是一边写文件系统,一边写交互界面(充当操作系统),并且一边测试。但对于这样的基础性代码,直接查看代码执行前后数据文件的变化就能直接了当的看出问题所在。我使用的是HxD,这个程序可以直接读二进制文件,所以我可以预期代码执行时应当改动哪些值,而数据文件在执行后应该是什么样子,再将预期与现实对比,即可完成测试。这些基础测试虽然需要手动验证,但一旦通过验证,这些基础的工具代码便不再修改,后续可以直接使用。

创建完用户,按照语义应当是用户登录。但实际上文件系统并不关心这个问题,这是操作系统的事儿,因此本文也暂时先不关心这个动作,直接快进到删除用户。

删除用户

    /**
     * 删除用户,true表示成功
     */
    public boolean deleteUser(String username) {
        if (username.equals("root")) {
            return false; // 禁止删除root用户
        }

        // 读取用户
        var userTable = this.readUserTable();
        var user = userTable.get(username);
        if (user == null) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var systemInfo = this.readSystemInfo();
            // 读取Inode表、创建根文件
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            var inodeTable = this.readInodeTable();

            var homeInode = inodeTable.get(user.getHomeInodeIndex());

            // 删除用户的文件
            var entryCount = homeInode.getSize() / new IndexEntry().byteCount();
            var files = this.readSomeIndexEntry(homeInode, 0, entryCount);
            for (IndexEntry f : files) {
                // 删除文件
                this.deleteFile(username, f.getFileName());

            }

            // 删除用户目录的inode
            inodeTable.delete(user.getHomeInodeIndex());

            // 写入Inode更新
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());

            // 设置用户
            var result = userTable.delete(username);
            // 更新变化
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            // 返回最终结果
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

在删除用户上限制就比较多了。首先不能删除root账户,它作为系统的唯一管理员,不应当且不能被删除。其次便是不能删除一个不存在的账户。

如果以上两个检查都通过了,那么就读取用户表,找到用户目录Inode,删除已有的文件,最后释放用户目录文件的Inode,删除用户。

在编码时我是最后实现的文件打开关闭,在那之前实现的文件读写。因此刚开始写到删除用户的时候这些代码和方法还都不存在。这是开发中一个很常见的现象,我的解决办法就是在对应的位置上放一个TODO,先把基本的功能过了,然后继续其他功能,完善之后再来整理、融合。所以一开始跟着本文走的时候,完全可以先把删除用户文件的部分换成TODO,等后面完成了对应的代码,再回过头来加上,再测试即可。

最后对于用户部分,我们在写一个相对简单的功能:修改密码。

修改密码

这部分代码十分简单:

    /**
     * 修改密码
     */
    public boolean changePassword(String username, String newPassword) {
        // 读取用户表
        var userTable = this.readUserTable();
        var user = userTable.get(username);
        if (user == null) {
            return false;
        }
        // 设置用户
        var result = userTable.set(username, newPassword, user.getHomeInodeIndex());
        // 更新变化
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var systemInfo = this.readSystemInfo();
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            // 返回用户最终创建成功与否
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

首先要找出用户,然后修改密码,最后写入磁盘。

下面来说一说文件相关的操作。即便是最简单的创建一个空白文件,除了对Inode的操作,还有对目录文件的读(查询避免重复)写(记录新文件)。因此最基础的文件读写应当首先实现。

读文件

在读写两个操作中,读文件相对简单一些:

    /**
     * 从指定位置开始读指定个数字节
     */
    public byte[] readFile(Inode target, long offset, long length) {
        CommonUtils.require(length > 0, "Length must bigger than 0.");
        CommonUtils.require(offset >= 0, "Offset must not smaller than 0.");
        CommonUtils.require(offset + length <= target.getSize(), "Read too many bytes.");
        var byteOutputStream = new ByteArrayOutputStream();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            var currentOffset = offset;
            while (byteOutputStream.size() < length) {
                // 寻找要读的盘块号
                var blockNum = target.getBlockNumber(currentOffset);
                // 移动到盘块内要写入的位置
                randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + currentOffset % Inode.BLOCK_SIZE);
                // 计算块内剩余可用空间
                var availableSize = Inode.BLOCK_SIZE - (currentOffset % Inode.BLOCK_SIZE);
                var bytes = new byte[(int) Math.min(availableSize, length - byteOutputStream.size())];
                var readCount = randomAccessFile.read(bytes);
                byteOutputStream.write(bytes);
                // 更新当前offset
                currentOffset += readCount;
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return byteOutputStream.toByteArray();
    }

读文件的作用就是无论文件数据分布在那些盘块上,调用者最终获得的数据一定是连续的。盘块的不连续应当在这个方法中被解决。

读之前首先检查一些基础条件,诸如不能读负数个字节(读0个字节也被认为是没有意义的),不能从负数地址开始读,以及总读取的长度不能越界。通过了这些检查之后再开始读。读出来的数据使用ByteArrayOutputStream暂存。

每次读的时候需要考虑两种情况:

// 寻找要读的盘块号
var blockNum = target.getBlockNumber(currentOffset);
// 移动到盘块内要写入的位置
randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + currentOffset % Inode.BLOCK_SIZE);
// 计算块内剩余可用空间
var availableSize = Inode.BLOCK_SIZE - (currentOffset % Inode.BLOCK_SIZE);
var bytes = new byte[(int) Math.min(availableSize, length - byteOutputStream.size())];
var readCount = randomAccessFile.read(bytes);
byteOutputStream.write(bytes);
// 更新当前offset
currentOffset += readCount;

先要找到当前文件内偏移量所在的盘块号,然后要决定读多少字节。如果读取的结束点不在当前盘块,那么盘块剩下多少字节直接读多少字节就行了(availableSize);如果读取的结束点在当前盘块,那么应当根据剩余待读取的字节来(length - byteOutputStream.size())。

说完了读文件,下面我们来说一说写文件。

追加文件

写文件分成两个操作:一种是在文件后面追加,另一种则是覆盖已有数据。而一般意义上的写可以认为是先覆盖有的,再追加新的。

追加文件的代码如下:

    /**
     * 向给定Inode追加数据,对于inode的修改不会写入磁盘,需要调用者处理
     * 返回false失败时已有部分数据写入
     */
    public boolean appendFile(Inode target, byte[] data) {
        var byteInputStream = new ByteArrayInputStream(data);
        try (var randomAccessFile = this.getRandomAccessFile("rws")) {
            while (byteInputStream.available() > 0) {
                // 寻找最后一块盘块
                var blockNum = target.getBlockNumber(target.getSize());
                if (blockNum >= 0) {
                    // 移动到盘块内要写入的位置
                    randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + target.getSize() % Inode.BLOCK_SIZE);
                }

                // 计算块内剩余可用空间
                var availableSize = Inode.BLOCK_SIZE - (target.getSize() % Inode.BLOCK_SIZE);
                if (blockNum < 0) {
                    // 如果盘块号小于0,说明没分配盘块
                    availableSize = 0;
                }
                if (availableSize > 0) {
                    // 还有可用空间,先往里写
                    var bytes = new byte[(int) availableSize];
                    var readCount = byteInputStream.read(bytes);
                    randomAccessFile.write(bytes);
                    // 这里要保存实际写入的内容
                    target.setSize(target.getSize() + readCount);
                } else {
                    // 已经写满了,申请一个新盘块
                    var bitmap = this.readBitMap();
                    // 寻找一个新的可用盘块
                    int newBlock = bitmap.nextAvailable();
                    if (newBlock < 0) {
                        return false;
                    }
                    if (!target.appendBlock((short) newBlock)) {
                        return false;
                    }
                    bitmap.set(newBlock);
                    // 移动到新盘块的位置
                    randomAccessFile.seek((long) newBlock * Inode.BLOCK_SIZE);
                    // 写数据
                    var bytes = new byte[Inode.BLOCK_SIZE];
                    var readCount = byteInputStream.read(bytes);
                    randomAccessFile.write(bytes);
                    // 这里要保存实际写入的数据量
                    target.setSize(target.getSize() + readCount);
                    // 更新BitMap
                    randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
                    randomAccessFile.write(bitmap.toBytes());
                }
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return true;
    }

对于追加文件,首先就要定位到文件的最后一个盘块。例如文件大小是4B,它占用的偏移量应该是0~3,那么我们直接寻到4,应该就是新追加数据的盘块。如果这个盘块号取出来是-1,说明这个盘块没有分配,我们需要向BitMap申请一块新的盘块,然后在这个盘块上写入数据;如果这个盘块号有效,还需要根据当前文件的大小计算出最后一个盘快内的剩余可用空间。最后写入时需要注意写入的上限是min(盘块可用空间,待写入数据大小)。本次写入完成后进入下一次循环,每次循环要不写完数据,要不就写满一块盘块。最后千万不要忘了更新Inode的大小字段,要不然写了白写。

写文件

由于覆盖文件比较简单,就和写文件合并了:

    /**
     * 向给定Offset写数据,重叠的部分直接覆盖,大于原有的部分直接调用appendFile。
     * 其中Offset必须小于等于文件大小,这样超出部分才算是追加,不能跳过一段没有数据的部分直接读写
     */
    public boolean writeFile(Inode target, long offset, byte[] data) {
        CommonUtils.require(offset <= target.getSize(), "Offset must not bigger than size.");
        var byteInputStream = new ByteArrayInputStream(data);
        var result = true;
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var currentOffset = offset;
            while (byteInputStream.available() > 0) {
                if (currentOffset >= target.getSize()) {
                    // 如果大于指定的大小了,直接追加
                    result = this.appendFile(target, byteInputStream.readAllBytes());
                } else {
                    // 正常写
                    // 寻找要写入的盘块号
                    var blockNum = target.getBlockNumber(currentOffset);
                    // 这里不应该出现未分配的情况,如果offset指向未分配的地方
                    // 说明offset是不小于size的,那么应该在上面的if跳到appendFile
                    // 移动到盘块内要写入的位置
                    randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + currentOffset % Inode.BLOCK_SIZE);
                    // 计算块内剩余可用空间
                    var availableSize = Inode.BLOCK_SIZE - (currentOffset % Inode.BLOCK_SIZE);
                    // 这里需要看是否为最后一块,最后一块应该将可用空间置为size-offset
                    if (target.getSize() - currentOffset < Inode.BLOCK_SIZE) {
                        availableSize = target.getSize() - currentOffset;
                    }
                    var bytes = new byte[(int) availableSize];
                    var readCount = byteInputStream.read(bytes);
                    // 这里要限制写入的数量严格为读取的数量,避免覆盖了后面的内容
                    randomAccessFile.write(bytes, 0, readCount);
                    // 覆盖不更新文件大小,只更新当前offset
                    currentOffset += readCount;
                }
            }
            // 更新InodeTable
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return result;
    }

对于写,分成两种情况:如果是已有数据的覆盖,那么跟追加差不多,只不过不是最后一个盘块,而是文件中间的盘块。原则是一样的,每次要么把数据写完,要不只覆盖一个盘块。如果写着写着偏移量超过了文件的大小,这意味着接下来的数据要追加到文件尾部,那么直接调用上面的追加方法就是了。这里要注意的一个问题就是覆盖已有数据不修改文件的大小,只有追加才修改文件大小。

有了读写文件的工具,下面我们就可以对目录文件进行操作,就可以查询、创建、删除文件了。

查询文件

在创建文件之前,我们得先知道有什么文件,这样才能避免用户创建重复的文件:

    /**
     * 读一些目录项,从第offset个开始读,读count个
     */
    public List<IndexEntry> readSomeIndexEntry(Inode homeInode, long offset, long count) {
        CommonUtils.require(offset >= 0, "Offset must not less than 0.");
        if (count <= 0) {
            return Collections.emptyList();
        }
        var emptyIndexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / emptyIndexEntry.byteCount();
        CommonUtils.require(offset + count <= entryCount, "Accessing invalid index entry.");
        var result = new ArrayList<IndexEntry>();
        // 一次性读出所有目录项
        try (var byteInput = new ByteArrayInputStream(this.readFile(homeInode, offset * emptyIndexEntry.byteCount(), count * emptyIndexEntry.byteCount()))) {
            var bytes = new byte[emptyIndexEntry.byteCount()];
            for (int i = 0; i < entryCount; i++) {
                var indexEntry = new IndexEntry();
                byteInput.read(bytes);
                indexEntry.loadFromBytes(bytes);
                result.add(indexEntry);
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return result;
    }

利用刚刚写的读文件方法,配合WrappedloadFromBytes,目录文件的数据很容易就被转换为了IndexEntry对象。每一个对象包含Inode索引和文件名,由此我们就可以知道目录下有哪些文件了。

同时为了尽可能大的灵活性,我们可以指定从哪里开始读,读几个目录项。避免了遍历时一个一个读需要重复访问磁盘,也避免了只需要一个的时候要全部读入内存查找。

创建文件

知道了已经有什么文件,我们就可以创建文件了。在创建文件之前还要介绍一个小工具方法:

    /**
     * 判断目录内是否已经有某文件
     */
    public boolean containsFile(Inode homeInode, String filename) {
        var entryCount = homeInode.getSize() / new IndexEntry().byteCount();
        return this.readSomeIndexEntry(homeInode, 0, entryCount).parallelStream().map(IndexEntry::getFileName).anyMatch((s) -> s.equals(filename));
    }

这个函数的作用就是读取全部的目录项,看看给定的文件名是否已经存在,然后返回一个Boolean。

之后我们可以在创建文件之前利用这个方法检查重复文件名:

    /**
     * 创建空文件,true表示成功
     */
    public boolean createFile(String username, String filename) {
        var user = this.readUserTable().get(username);
        if (user == null) {
            return false;
        }
        var inodeTable = this.readInodeTable();
        var homeInode = inodeTable.get(user.getHomeInodeIndex());

        // 检测重复
        if (this.containsFile(homeInode, filename)) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var iIndex = inodeTable.requestNewInode(homeInode.getOwner());
            if (iIndex < 0) {
                return false;
            }

            // 准备新的目录项
            var indexEntry = new IndexEntry();
            indexEntry.setFileName(filename);
            indexEntry.setInodeIndex(iIndex);

            // 将新的目录项追加到用户目录文件的尾部
            var result = this.appendFile(homeInode, indexEntry.toBytes());

            // 更新Inode表
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

基本的条件检查就不说了,诸如文件名不能重复、用户名必须存在什么的。通过检查之后首先要申请一个新的Inode给待创建的文件,然后根据新Inode 的索引创建目录项,并把目录项追加到文件尾部。最后将InodeTable更新到磁盘上。

这里在插入文件的时候偷了个懒,因此也就顺势规定目录文件是连续分配的,中间不能有空隙,因此创建文件的时候总是追加到文件尾部,删除的时候则是直接用最后一个目录项覆盖被删除的那个,然后减小文件大小就行了。

删除文件

如上所述,删除文件代码如下:

    /**
     * 删除文件,true表示成功
     */
    public boolean deleteFile(String username, String filename) {
        var user = this.readUserTable().get(username);
        if (user == null) {
            return false;
        }
        var inodeTable = this.readInodeTable();
        var homeInode = inodeTable.get(user.getHomeInodeIndex());

        // 先搜索被删除文件的目录项位置
        var indexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / indexEntry.byteCount();
        var index = 0;
        IndexEntry lastEntry;
        try {
            for (; index < entryCount; index++) {
                indexEntry = this.readSomeIndexEntry(homeInode, index, 1).get(0);
                if (indexEntry.getFileName().equals(filename)) {
                    break;
                }
            }

            if (index == entryCount) {
                return false;
            }

            // 读最后一项
            lastEntry = this.readSomeIndexEntry(homeInode, (int) (entryCount - 1), 1).get(0);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }

        // 释放被删除文件占用的块
        var bitmap = this.readBitMap();
        var deleted = inodeTable.get(indexEntry.getInodeIndex());
        for (Short blockNum : deleted.getBlocks()) {
            // 在BitMap中依次更新被占用的块
            bitmap.clear(blockNum);
        }

        // 释放Inode
        inodeTable.delete(indexEntry.getInodeIndex());

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            // 被删除的不是最后一个,用最后一个替换被删除的
            var offset = index * indexEntry.byteCount();
            if (index != entryCount - 1) {
                randomAccessFile.seek(
                        homeInode.getBlockNumber(offset) * Inode.BLOCK_SIZE + offset % Inode.BLOCK_SIZE
                );
                randomAccessFile.write(lastEntry.toBytes());
            }
            // 截断文件
            homeInode.setSize(homeInode.getSize() - indexEntry.byteCount());
            // 释放截断后未占用的块
            this.trimFile(bitmap, homeInode);
            // 更新
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
            randomAccessFile.write(bitmap.toBytes());
            return true;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

删除文件首先要找两个东西:一个是被删除的目录项的位置,另一个是最后一个目录项的内容。读出被删除的目录项,找出对应的Inode,释放其占用的盘块,最后撤销Inode。文件在磁盘上就被删除了,之后还需要更新目录项,直接用最后一个目录项的内容替换被删除的一项,最后截断文件,即直接把文件长度减去一个目录项的大小,最后还要将文件整理一下:

    /**
     * 整理文件,释放没有使用的块。需要调用者更新BitMap
     */
    public void trimFile(BitMap bitmap, Inode target) {
        var blockNumNeeded = CommonUtils.divCeil(target.getSize(), Inode.BLOCK_SIZE);
        var actualBlockNum = target.getBlocks().size();
        for (int i = 0; i < actualBlockNum - blockNumNeeded; i++) {
            var blockReleased = target.releaseLastBlock();
            bitmap.clear(blockReleased);
        }
    }

整理的目的是为了释放未占用的盘块。例如当前目录项占用了2个盘块,删除一个目录项后只需要占用一个盘块就能放下,那么我们需要释放多占用的那个盘块,虽然不释放也没什么问题,分配了早晚都能用上。操作上来说,需要根据实际大小计算出需要的盘块数,再和实际占用的盘块数计算差,把差出来的部分回收即可。

最后我们的文件系统还需要支持一个操作:

截断文件

阶段文件的作用在于我想丢弃文件尾部的一部分数据时,可以直接通过修改文件长度的方法丢弃它。

    /**
     * 截断文件,新长度必须小于等于当前长度
     */
    public void cutoffFile(Inode target, long newSize) {
        CommonUtils.require(newSize <= target.getSize(), "New size must not bigger than size.");
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            target.setSize(newSize);
            this.trimFile(this.readBitMap(), target);
            // 更新InodeTable
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
            // 更新BitMap
            randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
            randomAccessFile.write(BitMap.getInstance().toBytes());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

没什么太多需要说明的,直接设定文件大小,然后整理便是了,最后把更新写入磁盘。

根据文件名查找Inode

这个对于文件的操作并不必要,但是后面我们实现人机交互界面的时候,需要处理文件打开和关闭,其中涉及到打开的文件需要持有一个Inode对象。这个方法就是给文件打开提供的:给定文件名,和用户的目录文件Inode,就可以查找到需要的文件的Inode对象。

    /**
     * 根据filename寻找Inode
     */
    public Inode findInodeByFilename(Inode homeInode, String filename) {
        var indexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / indexEntry.byteCount();
        var resultIndexEntry = this.readSomeIndexEntry(homeInode, 0, entryCount).parallelStream().filter((s) -> s.getFileName().equals(filename));
        var inodeIndex = resultIndexEntry.findFirst().orElseThrow().getInodeIndex();
        return InodeTable.getInstance().get(inodeIndex);
    }

这里简单粗暴,直接把所有目录项读入内存,然后按文件名查找,最后根据找到的索引查找Inode。如果没有找到符合的目录项,直接抛出NoSuchElementException

总结

至此我们已经完成了文件系统的代码构建。本文的内容较前文多,好在没什么复杂的,可能需要一段时间搞清楚原理,搞清原理之后再写代码就很顺畅了。

至此文件系统部分就差不多完成了,下一篇文章作为这个系列的最终篇,将构建一个简单的人机交互界面充当操作系统,让这个文件系统能够投入使用。

附录:完整代码清单

package info.skyblond.os.exp.experiment3;

import info.skyblond.os.exp.experiment3.model.*;
import info.skyblond.os.exp.utils.CommonUtils;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 文件系统模拟器,提供对磁盘基本的读写和维护操作。
 */
@SuppressWarnings("ResultOfMethodCallIgnored")
public class Simulator {
    /**
     * root用户默认密码
     */
    public static String ROOT_DEFAULT_PASSWORD = "password";

    // 使用单例模式
    private static Simulator instance;

    private Simulator() {
    }

    public static synchronized Simulator getInstance() {
        if (instance == null) {
            instance = new Simulator();
        }
        return instance;
    }

    /**
     * 数据文件
     */
    private File dataFile = null;

    public void setDataFile(File dataFile) {
        this.dataFile = dataFile;
    }

    /**
     * 返回一个随机访问文件,mode参见{@link RandomAccessFile}
     */
    public RandomAccessFile getRandomAccessFile(String mode) {
        try {
            return new RandomAccessFile(this.dataFile, mode);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读磁盘的SystemInfo
     */
    public SystemInfo readSystemInfo() {
        try (var inputStream = new FileInputStream(this.dataFile)) {
            // 直接读取最开头
            var result = new SystemInfo();
            var bytes = new byte[result.byteCount()];
            CommonUtils.require(result.byteCount() == inputStream.read(bytes), "Bytes not enough");
            result.loadFromBytes(bytes);
            return result;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取BitMap
     */
    public BitMap readBitMap() {
        var systemInfo = this.readSystemInfo();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            randomAccessFile.seek(systemInfo.getBitmapAddr());
            var bitmap = BitMap.getInstance();
            var bytes = new byte[bitmap.byteCount()];
            randomAccessFile.read(bytes);
            bitmap.loadFromBytes(bytes);
            return bitmap;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取InodeTable
     */
    public InodeTable readInodeTable() {
        var systemInfo = this.readSystemInfo();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            var table = InodeTable.getInstance();
            var bytes = new byte[table.byteCount()];
            randomAccessFile.read(bytes);
            table.loadFromBytes(bytes);
            return table;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 读取用户表
     */
    public UserTable readUserTable() {
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            var systemInfo = this.readSystemInfo();
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            var userTable = UserTable.getInstance();
            var bytes = new byte[userTable.byteCount()];
            randomAccessFile.read(bytes);
            userTable.loadFromBytes(bytes);
            return userTable;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 初始化一个数据文件,默认创建一个
     */
    public void initDataFile() {
        try {
            CommonUtils.require(this.dataFile.createNewFile(), "Cannot create new data file.");
            var randomAccessFile = this.getRandomAccessFile("rw");
            randomAccessFile.seek(0);
            // 初始化足够大的文件
            for (int i = 0; i < BitMap.BLOCK_NUM; i++) {
                randomAccessFile.write(new byte[Inode.BLOCK_SIZE]);
            }

            // SystemInfo初始化
            var systemInfo = new SystemInfo(
                    UserTable.getInstance().byteCount(),
                    InodeTable.getInstance().byteCount()
            );
            var totalBytes = 0;
            totalBytes += systemInfo.byteCount();
            totalBytes += UserTable.getInstance().byteCount();
            totalBytes += InodeTable.getInstance().byteCount();
            totalBytes += BitMap.getInstance().byteCount();
            var totalBlock = CommonUtils.divCeil(totalBytes, Inode.BLOCK_SIZE);
            // 设置被元数据占用的块为已使用
            for (int i = 0; i <= totalBlock; i++) {
                BitMap.getInstance().set(i);
            }
            // 写入磁盘
            randomAccessFile.seek(0);
            randomAccessFile.write(systemInfo.toBytes());
            randomAccessFile.write(UserTable.getInstance().toBytes());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
            randomAccessFile.write(BitMap.getInstance().toBytes());
            randomAccessFile.close();

            // 初始化root用户
            CommonUtils.require(this.createUser("root", ROOT_DEFAULT_PASSWORD), "Cannot init user.");

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 创建用户,true表示成功
     */
    public boolean createUser(String username, String password) {
        // 读取用户表
        var userTable = this.readUserTable();
        if (userTable.get(username) != null) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var inodeTable = this.readInodeTable();
            var iIndex = inodeTable.requestNewInode(username);
            if (iIndex < 0) {
                return false; // 无可用Inode时返回false表示创建失败
            }

            var systemInfo = this.readSystemInfo();
            // 设置用户
            var result = userTable.set(username, password, iIndex);
            // 更新变化
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            // 返回用户最终创建成功与否
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 删除用户,true表示成功
     */
    public boolean deleteUser(String username) {
        if (username.equals("root")) {
            return false; // 禁止删除root用户
        }

        // 读取用户
        var userTable = this.readUserTable();
        var user = userTable.get(username);
        if (user == null) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var systemInfo = this.readSystemInfo();
            // 读取Inode表、创建根文件
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            var inodeTable = this.readInodeTable();

            var homeInode = inodeTable.get(user.getHomeInodeIndex());

            // 删除用户的文件
            var entryCount = homeInode.getSize() / new IndexEntry().byteCount();
            var files = this.readSomeIndexEntry(homeInode, 0, entryCount);
            for (IndexEntry f : files) {
                // 删除文件
                this.deleteFile(username, f.getFileName());
            }

            // 删除用户目录的inode
            inodeTable.delete(user.getHomeInodeIndex());

            // 写入Inode更新
            randomAccessFile.seek(systemInfo.getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());

            // 设置用户
            var result = userTable.delete(username);
            // 更新变化
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            // 返回最终结果
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 修改密码
     */
    public boolean changePassword(String username, String newPassword) {
        // 读取用户表
        var userTable = this.readUserTable();
        var user = userTable.get(username);
        if (user == null) {
            return false;
        }
        // 设置用户
        var result = userTable.set(username, newPassword, user.getHomeInodeIndex());
        // 更新变化
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var systemInfo = this.readSystemInfo();
            randomAccessFile.seek(systemInfo.getUserIndexTableAddr());
            randomAccessFile.write(userTable.toBytes());
            // 返回用户最终创建成功与否
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 向给定Inode追加数据,对于inode的修改不会写入磁盘,需要调用者处理
     * 返回false失败时已有部分数据写入
     */
    public boolean appendFile(Inode target, byte[] data) {
        var byteInputStream = new ByteArrayInputStream(data);
        try (var randomAccessFile = this.getRandomAccessFile("rws")) {
            while (byteInputStream.available() > 0) {
                // 寻找最后一块盘块
                var blockNum = target.getBlockNumber(target.getSize());
                if (blockNum >= 0) {
                    // 移动到盘块内要写入的位置
                    randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + target.getSize() % Inode.BLOCK_SIZE);
                }

                // 计算块内剩余可用空间
                var availableSize = Inode.BLOCK_SIZE - (target.getSize() % Inode.BLOCK_SIZE);
                if (blockNum < 0) {
                    // 如果盘块号小于0,说明没分配盘块
                    availableSize = 0;
                }
                if (availableSize > 0) {
                    // 还有可用空间,先往里写
                    var bytes = new byte[(int) availableSize];
                    var readCount = byteInputStream.read(bytes);
                    randomAccessFile.write(bytes);
                    // 这里要保存实际写入的内容
                    target.setSize(target.getSize() + readCount);
                } else {
                    // 已经写满了,申请一个新盘块
                    var bitmap = this.readBitMap();
                    // 寻找一个新的可用盘块
                    int newBlock = bitmap.nextAvailable();
                    if (newBlock < 0) {
                        return false;
                    }
                    if (!target.appendBlock((short) newBlock)) {
                        return false;
                    }
                    bitmap.set(newBlock);
                    // 移动到新盘块的位置
                    randomAccessFile.seek((long) newBlock * Inode.BLOCK_SIZE);
                    // 写数据
                    var bytes = new byte[Inode.BLOCK_SIZE];
                    var readCount = byteInputStream.read(bytes);
                    randomAccessFile.write(bytes);
                    // 这里要保存实际写入的数据量
                    target.setSize(target.getSize() + readCount);
                    // 更新BitMap
                    randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
                    randomAccessFile.write(bitmap.toBytes());
                }
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return true;
    }

    /**
     * 判断目录内是否已经有某文件
     */
    public boolean containsFile(Inode homeInode, String filename) {
        var entryCount = homeInode.getSize() / new IndexEntry().byteCount();
        return this.readSomeIndexEntry(homeInode, 0, entryCount).parallelStream().map(IndexEntry::getFileName).anyMatch((s) -> s.equals(filename));
    }

    /**
     * 创建空文件,true表示成功
     */
    public boolean createFile(String username, String filename) {
        var user = this.readUserTable().get(username);
        if (user == null) {
            return false;
        }
        var inodeTable = this.readInodeTable();
        var homeInode = inodeTable.get(user.getHomeInodeIndex());

        // 检测重复
        if (this.containsFile(homeInode, filename)) {
            return false;
        }

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var iIndex = inodeTable.requestNewInode(homeInode.getOwner());
            if (iIndex < 0) {
                return false;
            }

            // 准备新的目录项
            var indexEntry = new IndexEntry();
            indexEntry.setFileName(filename);
            indexEntry.setInodeIndex(iIndex);

            // 将新的目录项追加到用户目录文件的尾部
            var result = this.appendFile(homeInode, indexEntry.toBytes());

            // 更新Inode表
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            return result;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 向给定Offset写数据,重叠的部分直接覆盖,大于原有的部分直接调用appendFile。
     * 其中Offset必须小于等于文件大小,这样超出部分才算是追加,不能跳过一段没有数据的部分直接读写
     */
    public boolean writeFile(Inode target, long offset, byte[] data) {
        CommonUtils.require(offset <= target.getSize(), "Offset must not bigger than size.");
        var byteInputStream = new ByteArrayInputStream(data);
        var result = true;
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            var currentOffset = offset;
            while (byteInputStream.available() > 0) {
                if (currentOffset >= target.getSize()) {
                    // 如果大于指定的大小了,直接追加
                    result = this.appendFile(target, byteInputStream.readAllBytes());
                } else {
                    // 正常写
                    // 寻找要写入的盘块号
                    var blockNum = target.getBlockNumber(currentOffset);
                    // 这里不应该出现未分配的情况,如果offset指向未分配的地方
                    // 说明offset是不小于size的,那么应该在上面的if跳到appendFile
                    // 移动到盘块内要写入的位置
                    randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + currentOffset % Inode.BLOCK_SIZE);
                    // 计算块内剩余可用空间
                    var availableSize = Inode.BLOCK_SIZE - (currentOffset % Inode.BLOCK_SIZE);
                    // 这里需要看是否为最后一块,最后一块应该将可用空间置为size-offset
                    if (target.getSize() - currentOffset < Inode.BLOCK_SIZE) {
                        availableSize = target.getSize() - currentOffset;
                    }
                    var bytes = new byte[(int) availableSize];
                    var readCount = byteInputStream.read(bytes);
                    // 这里要限制写入的数量严格为读取的数量,避免覆盖了后面的内容
                    randomAccessFile.write(bytes, 0, readCount);
                    // 覆盖不更新文件大小,只更新当前offset
                    currentOffset += readCount;
                }
            }
            // 更新InodeTable
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return result;
    }

    /**
     * 截断文件,新长度必须小于等于当前长度
     */
    public void cutoffFile(Inode target, long newSize) {
        CommonUtils.require(newSize <= target.getSize(), "New size must not bigger than size.");
        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            target.setSize(newSize);
            this.trimFile(this.readBitMap(), target);
            // 更新InodeTable
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(InodeTable.getInstance().toBytes());
            // 更新BitMap
            randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
            randomAccessFile.write(BitMap.getInstance().toBytes());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 从指定位置开始读指定个数字节
     */
    public byte[] readFile(Inode target, long offset, long length) {
        CommonUtils.require(length > 0, "Length must bigger than 0.");
        CommonUtils.require(offset >= 0, "Offset must not smaller than 0.");
        CommonUtils.require(offset + length <= target.getSize(), "Read too many bytes.");
        var byteOutputStream = new ByteArrayOutputStream();
        try (var randomAccessFile = this.getRandomAccessFile("r")) {
            var currentOffset = offset;
            while (byteOutputStream.size() < length) {
                // 寻找要读的盘块号
                var blockNum = target.getBlockNumber(currentOffset);
                // 移动到盘块内要写入的位置
                randomAccessFile.seek(blockNum * Inode.BLOCK_SIZE + currentOffset % Inode.BLOCK_SIZE);
                // 计算块内剩余可用空间
                var availableSize = Inode.BLOCK_SIZE - (currentOffset % Inode.BLOCK_SIZE);
                var bytes = new byte[(int) Math.min(availableSize, length - byteOutputStream.size())];
                var readCount = randomAccessFile.read(bytes);
                byteOutputStream.write(bytes);
                // 更新当前offset
                currentOffset += readCount;
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return byteOutputStream.toByteArray();
    }

    /**
     * 读一些目录项,从第offset个开始读,读count个
     */
    public List<IndexEntry> readSomeIndexEntry(Inode homeInode, long offset, long count) {
        CommonUtils.require(offset >= 0, "Offset must not less than 0.");
        if (count <= 0) {
            return Collections.emptyList();
        }
        var emptyIndexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / emptyIndexEntry.byteCount();
        CommonUtils.require(offset + count <= entryCount, "Accessing invalid index entry.");
        var result = new ArrayList<IndexEntry>();
        // 一次性读出所有目录项
        try (var byteInput = new ByteArrayInputStream(this.readFile(homeInode, offset * emptyIndexEntry.byteCount(), count * emptyIndexEntry.byteCount()))) {
            var bytes = new byte[emptyIndexEntry.byteCount()];
            for (int i = 0; i < entryCount; i++) {
                var indexEntry = new IndexEntry();
                byteInput.read(bytes);
                indexEntry.loadFromBytes(bytes);
                result.add(indexEntry);
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return result;
    }

    /**
     * 根据filename寻找Inode
     */
    public Inode findInodeByFilename(Inode homeInode, String filename) {
        var indexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / indexEntry.byteCount();
        var resultIndexEntry = this.readSomeIndexEntry(homeInode, 0, entryCount).parallelStream().filter((s) -> s.getFileName().equals(filename));
        var inodeIndex = resultIndexEntry.findFirst().orElseThrow().getInodeIndex();
        return InodeTable.getInstance().get(inodeIndex);
    }

    /**
     * 删除文件,true表示成功
     */
    public boolean deleteFile(String username, String filename) {
        var user = this.readUserTable().get(username);
        if (user == null) {
            return false;
        }
        var inodeTable = this.readInodeTable();
        var homeInode = inodeTable.get(user.getHomeInodeIndex());

        // 先搜索被删除文件的目录项位置
        var indexEntry = new IndexEntry();
        var entryCount = homeInode.getSize() / indexEntry.byteCount();
        var index = 0;
        IndexEntry lastEntry;
        try {
            for (; index < entryCount; index++) {
                indexEntry = this.readSomeIndexEntry(homeInode, index, 1).get(0);
                if (indexEntry.getFileName().equals(filename)) {
                    break;
                }
            }

            if (index == entryCount) {
                return false;
            }

            // 读最后一项
            lastEntry = this.readSomeIndexEntry(homeInode, (int) (entryCount - 1), 1).get(0);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }

        // 释放被删除文件占用的块
        var bitmap = this.readBitMap();
        var deleted = inodeTable.get(indexEntry.getInodeIndex());
        for (Short blockNum : deleted.getBlocks()) {
            // 在BitMap中依次更新被占用的块
            bitmap.clear(blockNum);
        }

        // 释放Inode
        inodeTable.delete(indexEntry.getInodeIndex());

        try (var randomAccessFile = this.getRandomAccessFile("rw")) {
            // 被删除的不是最后一个,用最后一个替换被删除的
            var offset = index * indexEntry.byteCount();
            if (index != entryCount - 1) {
                randomAccessFile.seek(
                        homeInode.getBlockNumber(offset) * Inode.BLOCK_SIZE + offset % Inode.BLOCK_SIZE
                );
                randomAccessFile.write(lastEntry.toBytes());
            }
            // 截断文件
            homeInode.setSize(homeInode.getSize() - indexEntry.byteCount());
            // 释放截断后未占用的块
            this.trimFile(bitmap, homeInode);
            // 更新
            randomAccessFile.seek(this.readSystemInfo().getInodeIndexTableAddr());
            randomAccessFile.write(inodeTable.toBytes());
            randomAccessFile.seek(this.readSystemInfo().getBitmapAddr());
            randomAccessFile.write(bitmap.toBytes());
            return true;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 整理文件,释放没有使用的块。需要调用者更新BitMap
     */
    public void trimFile(BitMap bitmap, Inode target) {
        var blockNumNeeded = CommonUtils.divCeil(target.getSize(), Inode.BLOCK_SIZE);
        var actualBlockNum = target.getBlocks().size();
        for (int i = 0; i < actualBlockNum - blockNumNeeded; i++) {
            var blockReleased = target.releaseLastBlock();
            bitmap.clear(blockReleased);
        }
    }
}

-全文完-


生活不易,一点广告


知识共享许可协议
【代码札记】Java模拟二级文件系统 下天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://www.skyblond.info/about.html 处获得。

Last Modified: December 17, 2020
Archives QR Code Tip
QR Code for this page
Tipping QR Code