lazyload.md

Lazy Load

exec 映射

在 exec 的时候，需要将 ELF 文件加载到内存中。程序的 ELF 通常比较大，比如 busybox 的可执行文件大小是 1.1 MB，很多地方可能在执行过程中根本不会用到。因此，我们采用了懒加载的设计，在 exec 的时候只记录文件和程序之间的映射关系，并没有真正加载。等到运行时抛出缺页异常，再将内容从文件真正加载到用户进程中。

具体设计十分简单。每个进程维护一个 ProcessSegmentMap 链表，记录映射关系。每个映射的定义如下：

struct ProcessSegmentMap {
    struct dirent *sourceFile; // 映射文件
    u64 va; // 进程中的虚拟地址
    u64 fileOffset; // 在文件中的偏移
    u32 len; // 映射长度
    u32 flag; // 权限和种类
    struct ProcessSegmentMap *next; // 指向本进程的下一个映射
}

在 exec 的时候，需要从 ELF 文件中映射若干段的数据到进程。这时只需要向进程结构体中插入一个新映射就可以了。对于程序的 bss 段，只需设置 flag 中的 MAP_ZERO 位即可。在每次缺页异常时，如果页面没有映射过，就遍历这个页表，加载缺页页面中的部分。

Inode 设计

懒加载的目标是为了提升加载用户进程的效率。但由于 FAT32 文件系统的特性，懒加载并不能很好地发挥效果。对于 FAT32 文件系统，加载一个文件某个偏移所在的簇号，需要查询 FAT 表，从这个文件的起始簇开始一个个遍历。FAT32 对于顺序访问文件性能很好，但随机访问就非常糟糕。由于我们的懒加载破坏了原本顺序访问文件的特性，懒加载之后的性能一度还不如原先。

这是因为我们在懒加载的时候，需要确定某个特定的文件偏移在外存中对应的簇号，也就是映射： $$ offset \rightarrow cluster $$ 因为 FAT32 是链表，在检索的时候是顺序访问，所以时间复杂度是 $O(offset/512)$ ，这样的效率是很低的，我们需要随机访问特性结构。比较容易想到的是数组描述，但是因为可执行文件的大小不同，最大的可执行文件需要的数组过大，所以定长数组浪费内存。

因此，我们给每个文件设置了 Inode 记录已经遍历过的簇号。如果查询已经遍历过的簇，能通过 Inode 以 O(1) 的复杂度找到。

具体来说，我们让每个文件维护一个 Inode， 并修改了 reloc_clus 函数。Inode 定义如下：

#define INODE_ITEM_NUM 64
typedef struct Inode {
    u32 item[INODE_ITEM_NUM];
};

每个 Inode 中记录了 64 个 32 位的整数。前 8 个整数直接记录该位置的簇号，之后的 16 个整数记录一个 Inode 资源池的索引，表示二级 Inode。剩余的 40 个整数表示三级 Inode 索引。在这里，每个文件的大小最多包含 $8 + 16 \times 64 + 40 \times 64 \times 64 = 164,872$ 个簇，大约是 650 MB 大小。

在 dirmeta 结构体中，记录该文件访问过的最大簇号。如果需要读写的簇低于这个最大簇，就能实现 O(1) 查找。如果超过了这个簇，再通过 FAT 表查询，并一边查询一边更新这个 Inode。

有了 Inode 设计，懒加载的威力才真正得以发挥。