分析
使用 Java 编写这个项目。其中涉及文件系统对磁盘的操作，肯定要支持随机存取。尽管 Java 中有常用的 Stream 的概念，但很遗憾的是 Stream 并不能随机读写。固然可以通过 Stream 的 skip 方法跳过前面的内容，找到我们需要的数据，但这样的操作方式更像是磁带，而非磁盘。如果使用一个二进制文件来模仿磁盘，则可以使用 Java 对文件的随机读写支持来实现我们的目标。因此在本项目中可能需要抛弃常用且便利的流，而另辟蹊径一种模式了。
一个最简单的模式，也是本文使用的模式，就是利用 RandomAccessFile，该类可以实现对文件的随机读写：
• RandomAccessFile randomAccessFile = new RandomAccessFile("path/to/some/file", "rw");
其中 "rw" 与 C 语言类似，规定如下：
- r 只读，此时试图写会引发异常
- rw 读写，产生的修改不保证会同步写入磁盘
- rwd 读写，对数据产生的修改会同步写入磁盘
- rws 读写，对数据和元数据产生的修改会同步写入磁盘
对文件的随机读写如下示范：
• // 将文件指针移动到200 • randomAccessFile.seek(200); • // 读取文件指针 • long position = randomAccessFile.getFilePointer(); • // 读一个字节 • byte b = randomAccessFile.read(); • // 读10个字节进字节数组 • byte[] bytes = new byte[10]; • randomAccessFile.read(bytes); • // 读两个字节进字节数组，从5开始写 • randomAccessFile.read(bytes, 5, 2); • // 读一个基本类型 • int i = randomAccessFile.readInt(); • // 写一个字节 • randomAccessFile.write(b); • // 从字节数组写10个字节进文件 • randomAccessFile.write(bytes); • // 写两个字节进字节数组，从5开始读 • randomAccessFile.write(bytes, 5, 2); • // 写一个基本类型 • randomAccessFile.writeInt(i);
详细信息可以异步官方 JavaDoc
现在解决了文件随机读写的问题，现在来说一说如何模拟磁盘。
磁盘管理展开目录
实际上这个项目除了要写一个文件系统，还要模拟一个简单的操作系统来支持人机交互。因此用户信息和文件信息都要存储在磁盘上。暂定磁盘安排如下：
• |System Info|User Table|Inode Table|BitMap|Block|Block|Block|Block|...|Block|
其中各项如下解释：
- System Info 记录磁盘的元数据的元数据，即 User Table 的位置、Inode Table 的位置、BitMap 的位置
- User Table 记录用户信息，内含一个分配表和多个 User 条目。每个 User 记录用户名、密码和用户目录的 Inode 节点号
- Inode Table 记录 Inode 信息，内含一个分配表和多个 Inode 条目。每个 Inode 包含多个盘块号索引、所有者用户名和文件大小
- BitMap 记录整个磁盘的盘块分配情况。0 表示未分配，1 表示已分配。
- Block 即为盘块，用于存储一般性的数据
关于上面各数据的代码设计将在后文说明。现在有一个需要优先考虑的问题：如何将 Java 的类像 C 的结构体一样写入文件？
从 Java 对象到字节数组展开目录
Java 有一个 Serializable 接口，实现该接口的类可以通过 ObjectOutputStream 写入到文件。为了节省带宽，ObjectOutputStream 在写入时记录被写入对象，如果后续写入了同样的内容，它会偷懒不写入重复的内容，而做下一个标记，告诉读取者当前项是重复的哪一项，直接去找就是了。为了避免内存泄漏，需要定时调用 reset 方法，而这个方法同样会写入一个标志，告诉读取者也要 reset，以此避免数据不同步。这样一来我们的磁盘就会被这些标志搞得乱七八糟，而最终磁盘的模样也会因为写入方式的不同而改变，这样我们在随机读取的时候也就没办法根据类的信息直接决定去哪里找，我们还需要写入时的信息，考虑标志的问题。十分难看。
因此我想到的办法是直接抽象出一个接口，该接口直接实现 Java 数据和对象，与字节数组的相互转换：
• package info.skyblond.os.exp.experiment3.bytes; • • /** • * 类型Wrapped，用于将值转换为字节数组 • */ • public interface Wrapped { • /** • * 转换为字节数组 • */ • byte[] toBytes(); • • /** • * 占用的字节数 • */ • int byteCount(); • • /** • * 从字节数组中载入值，失败直接抛异常 • */ • void loadFromBytes(byte[] bytes); • }
如果一个类要实现该接口，需要支持三个方法：
- toBytes 负责将 this 对象转换为字节数组，转换方式由实现者自己决定
- byteCount 返回 this 对象占用多少个字节，以便其他代码在读写时按照该大小分配缓冲区
- loadFromBytes 从给定的字节数组中恢复数据，必须是就地恢复，不能返回一个新的对象。恢复方法由实现者自己决定，如果传入数据不满足要求或者恢复过程中出现异常，要不直接抛 unchecked 异常（即 RuntimeException），要不自己想办法解决
如果我们能够将 Java 的基本类型都实现了上述接口，后续一般性的对象只需要利用我们实现好的基本类就可以了。（不过有一说一，当时想的是对普通类做一个包装，因此接口名字就叫成 Wrapped 了，实践来说这并不是一个好的接口名称）
Java 基本类型到字节数组展开目录
为了方便处理，我们可以将对基本类型的处理抽象成一个基类，再针对其中不同的地方分别 Override，以此达到减少冗余代码、提高可读性与可维护性的目的：
• package info.skyblond.os.exp.experiment3.bytes.primitive; • • import info.skyblond.os.exp.experiment3.bytes.Wrapped; • import info.skyblond.os.exp.utils.CommonUtils; • • import java.io.*; • import java.util.Objects; • • /** • * Java基本类型的Wrapper • */ • public abstract class WrappedBaseType<T> implements Wrapped { • /** • * 真正的值 • */ • private T value; • • /** • * 通过默认值创建，默认值不得为空。由于只针对基本类型，因此本类不对外提供构造函数。 • */ • WrappedBaseType(T defaultValue) { • this.value = Objects.requireNonNull(defaultValue); • } • • /** • * 使用{@link DataOutputStream}写入{@link ByteArrayOutputStream}以获得字节数组 • */ • @Override • public byte[] toBytes() { • var byteArrayOutputStream = new ByteArrayOutputStream(); • var dataOutputStream = new DataOutputStream(byteArrayOutputStream); • this.baseTypeWriteIntoDataOutput(dataOutputStream); • try { • dataOutputStream.close(); • } catch (IOException e) { • throw new RuntimeException(e); • } • return byteArrayOutputStream.toByteArray(); • } • • /** • * 具体将值写入{@link DataOutput} • */ • protected abstract void baseTypeWriteIntoDataOutput(DataOutput dataOutput); • • /** • * 使用{@link DataInputStream}从{@link ByteArrayInputStream}中读取值 • */ • @Override • public void loadFromBytes(byte[] bytes) { • CommonUtils.require(Objects.requireNonNull(bytes).length == this.byteCount(), "Short supply of bytes."); • var dataInputStream = new DataInputStream(new ByteArrayInputStream(bytes)); • var result = this.baseTypeReadFromDataInput(dataInputStream); • try { • dataInputStream.close(); • } catch (IOException e) { • throw new RuntimeException(e); • } • this.value = result; • } • • /** • * 从给定{@link DataInput}中读取具体值 • */ • protected abstract T baseTypeReadFromDataInput(DataInput dataInput); • • /** • * Getter，保证返回值不为空 • */ • public T getValue() { • return Objects.requireNonNull(this.value); • } • • /** • * Setter，保证新的值不为空 • */ • public void setValue(T value) { • this.value = Objects.requireNonNull(value); • } • • /** • * 核心值相同即认定相等 • */ • @Override • public boolean equals(Object o) { • if (this == o) { • return true; • } • if (o == null || this.getClass() != o.getClass()) { • return false; • } • WrappedBaseType<?> that = (WrappedBaseType<?>) o; • return this.value.equals(that.value); • } • • @Override • public int hashCode() { • return Objects.hash(this.value); • } • • @Override • public String toString() { • return "WrappedBaseType{" + • "value=" + this.value + • '}'; • } • }
这个抽象基类带有一个泛型 T，表示其包装的真正类型，例如 WrappedBaseType<Integer> 表示包装的 int 类型，在平时调用的过程中 Java 会自动帮我们处理基本类型到封装类的封箱拆箱。
在抽象基类中有一个 private T value;，用于存储真正的值，构造函数和 Setter 保证它永远不会为 null。对于 toBytes 方法，我们借助 ByteArrayOutputStream 和 DataOutputStream 来转换。后者将被传递给一个特殊的成员方法 baseTypeWriteIntoDataOutput，实现者需要在该方法中定义如何将 value 写入到给定的 DataOutputStream 中。而 loadFromBytes 也类似，实现者需要在特殊的成员方法中决定如何从给定的 DataInputStream 中读取值并写入 value（当然，必须通过 setter 保证新的值不为 null）。
其中用到了我自己写的一个工具类：
• public static void require(boolean bool, String message) { • if (!bool) { • throw new IllegalStateException(message); • } • }
写过 Kotlin 的话应该会知道，如果该函数传入的条件不满足（bool 为 false），那就当场抛一个异常，我认为这种略带暴力的条件检查十分优雅：不需要返回什么东西，也不需要包装什么自定义异常，更不需要复杂的流程处理和打印提示信息，直接一个 Runtime 异常崩了 JVM，多好。
这样一类编写基本类型的包装类就容易多了：
• package info.skyblond.os.exp.experiment3.bytes.primitive; • • import java.io.DataInput; • import java.io.DataOutput; • • public class WrappedShort extends WrappedBaseType<Short> { • • /** • * 默认值为0 • */ • public WrappedShort() { • super((short) 0); • } • • public WrappedShort(short b) { • super(b); • } • • @Override • public void baseTypeWriteIntoDataOutput(DataOutput dataOutput) { • try { • dataOutput.writeShort(this.getValue()); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public Short baseTypeReadFromDataInput(DataInput dataInput) { • try { • return dataInput.readShort(); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public int byteCount() { • return Short.BYTES; • } • }
• package info.skyblond.os.exp.experiment3.bytes.primitive; • • import java.io.DataInput; • import java.io.DataOutput; • • public class WrappedInteger extends WrappedBaseType<Integer> { • • /** • * 默认值为0 • */ • public WrappedInteger() { • super(0); • } • • public WrappedInteger(int b) { • super(b); • } • • @Override • public void baseTypeWriteIntoDataOutput(DataOutput dataOutput) { • try { • dataOutput.writeInt(this.getValue()); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public Integer baseTypeReadFromDataInput(DataInput dataInput) { • try { • return dataInput.readInt(); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public int byteCount() { • return Integer.BYTES; • } • }
• package info.skyblond.os.exp.experiment3.bytes.primitive; • • import java.io.DataInput; • import java.io.DataOutput; • • public class WrappedLong extends WrappedBaseType<Long> { • • /** • * 默认值为0 • */ • public WrappedLong() { • super(0L); • } • • public WrappedLong(long b) { • super(b); • } • • @Override • public void baseTypeWriteIntoDataOutput(DataOutput dataOutput) { • try { • dataOutput.writeLong(this.getValue()); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public Long baseTypeReadFromDataInput(DataInput dataInput) { • try { • return dataInput.readLong(); • } catch (Exception e) { • throw new RuntimeException(e); • } • } • • @Override • public int byteCount() { • return Long.BYTES; • } • }
虽然 Java 有 8 个基本类型，但是项目实际用得上的就 Short、Integer 和 Long，分别用于存储盘块号、索引号和地址。如果使用 Integer 来存储盘块号，那么连 Short 都不用实现。对于其他的基本类型，想要拓展也很容易，只要定义好构造方法，然后 DataInput 和 DataOutput 支持，那么就直接调用对应的 read 和 write 方法即可。关于 byteCount，直接返回基本类型的封装类里面事先定义好的常量即可。
然而除了基本类型，项目里还常用一种数据结构：串。
两种串到字节数组展开目录
出于方便考虑，我没有实现变长列表（List），那样还要在数据之前存储元素个数，并且顺序存放变长数据，纯属是给自己找不痛快。因此我实现了串（数组）：在定义时说明元素个数。具体地说我实现了两种常用的数组数据：一个是字符串，用于用户名、密码和文件名的存储；另一种就是 Bit 串，用于 BitMap 和分配表的表示。
字符串展开目录
先来说说字符串吧，这个比较简单：
• package info.skyblond.os.exp.experiment3.bytes.array; • • import info.skyblond.os.exp.experiment3.bytes.Wrapped; • import info.skyblond.os.exp.utils.CommonUtils; • • import java.nio.charset.StandardCharsets; • import java.util.Objects; • • public class WrappedString implements Wrapped { • /** • * 这里的最大长度是指按UTF-8转换成字节后的长度。 • * 通常纯英文字符没有问题，其他文字一个字对应多个字节（例如中文一个字对应三个字节） • */ • private final int maxLength; • private String internalValue; • • /** • * 长度检查，将字符串转化为字节后的长度与最大长度对比 • */ • private static void lengthCheck(int maxLength, String s) { • var bytes = s.getBytes(StandardCharsets.UTF_8); • CommonUtils.require(bytes.length <= maxLength, "Max length reached. Max: " + maxLength + ", actual: " + bytes.length); • } • • public WrappedString(int maxLength) { • this(maxLength, ""); • } • • public WrappedString(int maxLength, String s) { • CommonUtils.require(maxLength > 0, "Max length must bigger than 0."); • lengthCheck(maxLength, s); • this.internalValue = s; • this.maxLength = maxLength; • } • • @Override • public byte[] toBytes() { • return CommonUtils.pad(this.maxLength, this.internalValue.getBytes(StandardCharsets.UTF_8)); • } • • @Override • public void loadFromBytes(byte[] bytes) { • var unpad = CommonUtils.unpad(bytes); • CommonUtils.require(unpad.length <= this.maxLength, "Max length reached. Max: " + this.maxLength + ", actual: " + unpad.length); • this.internalValue = new String(unpad, StandardCharsets.UTF_8); • } • • @Override • public int byteCount() { • return this.maxLength; • } • • public String getValue() { • return Objects.requireNonNull(this.internalValue); • } • • public void setValue(String value) { • lengthCheck(this.maxLength, value); • this.internalValue = Objects.requireNonNull(value); • } • • @Override • public boolean equals(Object o) { • if (this == o) { • return true; • } • if (o == null || this.getClass() != o.getClass()) { • return false; • } • WrappedString that = (WrappedString) o; • return this.maxLength == that.maxLength && • this.internalValue.equals(that.internalValue); • } • • @Override • public int hashCode() { • return Objects.hash(this.maxLength, this.internalValue); • } • • @Override • public String toString() { • return "WrappedString{" + • "maxLength=" + this.maxLength + • ", internalValue='" + this.internalValue + '\'' + • '}'; • } • }
需要额外注意的就是由于 Java 底层支持 UTF-8，因此字符串的长度在一些情况下并不严格对应写入磁盘的字节长度。因此字符串需要在一开始指定字节长度。在字节的转换上，我选择使用 UTF-8 编码进行转换，需要注意从文件读出来的字符串，以及其他代码通过 setter 设置的新字符串，都要将其转换为字节数组后再检查长度。而为了对齐设定的字节长度，我写了两个工具方法用于给字符串填充和删除 0 字符：
• /** • * 按照最大长度将空缺的部分填0 • */ • public static byte[] pad(int maxLength, byte[] data) { • CommonUtils.require(data.length <= maxLength, "The length of data is bigger than max length."); • var result = new byte[maxLength]; • int i = 0; • for (; i < data.length; i++) { • result[i] = data[i]; • } • for (; i < maxLength; i++) { • result[i] = 0; • } • return result; • } • • /** • * 删掉末尾的连续的0 • */ • public static byte[] unpad(byte[] data) { • int i = data.length - 1; • while (i >= 0 && data[i] == 0) { • i--; • } • var result = new byte[i + 1]; • for (; i >= 0; i--) { • result[i] = data[i]; • } • return result; • }
位串展开目录
由于数据都是定长的，我们必须设定一个标志位来标记当前元素是否为已分配的状态，一般来说通常是 Boolean 类型来做这个事儿，但是在写入字节的时候，单独一个 Boolean 要占用一个字节，所以通常都是将他们集中存放，这样能够节省一些空间。
实现如下：
• package info.skyblond.os.exp.experiment3.bytes.array; • • import info.skyblond.os.exp.experiment3.bytes.Wrapped; • import info.skyblond.os.exp.utils.CommonUtils; • • import java.util.Arrays; • import java.util.Objects; • • /** • * 使用Byte数组表示Bit数组 • */ • public class WrappedBitArray implements Wrapped { • /** • * 内部的字节数组表示 • */ • private byte[] internalArray; • • /** • * 总bit位数 • */ • private final int length; • • /** • * 对应的字节数量 • */ • private final int internalLength; • • /** • * 必须固定长度，且长度必须大于0 • */ • public WrappedBitArray(int length) { • CommonUtils.require(length > 0, "Length must bigger than 0."); • this.internalLength = CommonUtils.divCeil(length, Byte.SIZE); • this.internalArray = new byte[this.internalLength]; • this.length = length; • } • • public int getLength() { • return this.length; • } • • @Override • public byte[] toBytes() { • return this.internalArray; • } • • @Override • public int byteCount() { • return this.internalLength; • } • • @Override • public void loadFromBytes(byte[] bytes) { • CommonUtils.require(bytes.length == this.internalLength, "Byte array length not match. Except: " + this.internalLength + ", actual: " + bytes.length); • this.internalArray = bytes; • } • • /** • * 按bit索引获取，结果为Boolean，原Bit为1对应true • */ • public Boolean get(int index) { • CommonUtils.require(index < this.length, "Index invalid. Length: " + this.length + ", actual: " + index); • var b = this.internalArray[index / Byte.SIZE]; • var i = 0x80 >> (index % Byte.SIZE); • return (b & i) != 0; // not 0 -> 1 -> true; is 0 -> 0 -> false • } • • /** • * 按bit索引设置，传入为true，对应Bit写1 • */ • public void set(int index, boolean value) { • CommonUtils.require(index < this.length, "Index invalid. Length: " + this.length + ", actual: " + index); • var b = this.internalArray[index / Byte.SIZE]; • var i = 0x80 >> (index % Byte.SIZE); • if (value) { • // writing 1 -> XXXXXXXX | 00010000 -> XXX1XXXX • this.internalArray[index / Byte.SIZE] = (byte) (b | i); • } else { • // writing 0 -> XXXXXXXX & 11101111 -> XXX0XXXX • this.internalArray[index / Byte.SIZE] = (byte) (b & ~i); • } • } • • /** • * 获取值，将内部表示转换为boolean型数组 • */ • public Boolean[] getValue() { • var result = new Boolean[this.length]; • • for (int i = 0; i < this.length; i++) { • result[i] = this.get(i); • } • • return result; • } • • /** • * 将Boolean数组解析成内部表示，传入的数组长度必须和bit的数量一样 • */ • public void setValue(Boolean[] value) { • CommonUtils.require(value.length == this.length, "Boolean array length not match. Except: " + this.length + ", actual: " + value.length); • for (int i = 0; i < this.length; i++) { • this.set(i, value[i]); • } • } • • @Override • public boolean equals(Object o) { • if (this == o) { • return true; • } • if (o == null || this.getClass() != o.getClass()) { • return false; • } • WrappedBitArray that = (WrappedBitArray) o; • return this.length == that.length && • this.internalLength == that.internalLength && • Arrays.equals(this.internalArray, that.internalArray); • } • • @Override • public int hashCode() { • int result = Objects.hash(this.length, this.internalLength); • result = 31 * result + Arrays.hashCode(this.internalArray); • return result; • } • • @Override • public String toString() { • StringBuilder stringBuilder = new StringBuilder(); • • for (int i = 0; i < this.length; i++) { • if (this.get(i)) { • stringBuilder.append("1"); • } else { • stringBuilder.append("0"); • } • } • • return "WrappedBitList{" + • "length=" + this.length + ", " + • "value=" + stringBuilder.toString() + • '}'; • } • }
该类的核心在于使用字节数组来表示位串，并且根据位串的索引定位需要操作的字节和字节内的位数。虽然写起来繁琐，但原理一点也不复杂，没什么需要多说的，可以参考注释阅读程序。其中用到一个工具方法：
• /** • * 整数除法，结果返回向上取整的整型 • */ • public static int divCeil(int a, int b) { • if (a % b == 0) { • return a / b; • } else { • return a / b + 1; • } • } • • public static int divCeil(long a, int b) { • if (a % b == 0) { • return (int) (a / b); • } else { • return (int) (a / b + 1); • } • }
这两个方法用于计算两个整型之间的除法，并将结果向上取整。比如存储 9 个 bit，需要 ceil(9, 8) = 2 个字节才能储存。因此在余数不为 0 的情况加，自动给结果加 1。
至此 Java 中常用的基本类型已经经过包装，具备了转换到字节数组的能力，对于其他一般的类来说，我们可以利用已有的包装类组合来实现。
任意类到字节数组展开目录
为了简化这个过程，我编写了一个适用于任意类型的基类：
• package info.skyblond.os.exp.experiment3.bytes; • • import info.skyblond.os.exp.utils.CommonUtils; • • import java.io.*; • import java.util.ArrayList; • import java.util.List; • import java.util.Objects; • • /** • * Java泛型的Wrapper。限制比基本类型少需要，需要继承者处理大部分Null值和细节相关的东西。 • */ • public class WrappedGenericType implements Wrapped { • /** • * 参数列表 • */ • protected final List<Wrapped> parameters = new ArrayList<>(); • • /** • * 使用{@link DataOutputStream}写入{@link ByteArrayOutputStream}以获得字节数组 • */ • @Override • public byte[] toBytes() { • var byteArrayOutputStream = new ByteArrayOutputStream(); • var dataOutputStream = new DataOutputStream(byteArrayOutputStream); • try { • for (Wrapped w : this.parameters) { • dataOutputStream.write(w.toBytes()); • } • dataOutputStream.close(); • } catch (Exception e) { • throw new RuntimeException(e); • } • return byteArrayOutputStream.toByteArray(); • } • • @Override • public int byteCount() { • var result = 0; • for (Wrapped w : this.parameters) { • result += w.byteCount(); • } • return result; • } • • /** • * 使用{@link DataInputStream}从{@link ByteArrayInputStream}中读取值 • */ • @Override • public void loadFromBytes(byte[] bytes) { • CommonUtils.require(Objects.requireNonNull(bytes).length == this.byteCount(), "Supply bytes length not match."); • • var byteArrayInputStream = new ByteArrayInputStream(bytes); • try { • for (Wrapped w : this.parameters) { • var temp = new byte[w.byteCount()]; • CommonUtils.require(byteArrayInputStream.read(temp) == w.byteCount(), "Short supply of bytes."); • w.loadFromBytes(temp); • } • byteArrayInputStream.close(); • } catch (IOException e) { • throw new RuntimeException(e); • } • } • }
这个类的核心在于 List<Wrapped> parameters，继承者将维护这个列表，将其需要转换成字节数组的参数添加到这个列表中，在转换为字节数组的时候将会自动根据顺序依次拼接，实现了 C 语言中类似结构体写入文件的效果。而读取的时候也会根据顺序自动分配对应的字节供参数更新数据。而字节统计则自动根据提供的类型做累加。十分方便。
总结展开目录
至此我们已经完成了基础设施的构建工作。
