零、写在前面
可以读一下《xv6 book》第八章：File System
xv6文件系统提供类似于Unix的文件、目录和路径名，并将其数据存储在virtio磁盘上以便持久化。文件系统解决了几个难题：
- 文件系统需要磁盘上的数据结构来表示目录和文件名称树，记录保存每个文件内容的块的标识，以及记录磁盘的哪些区域是空闲的。
- 文件系统必须支持崩溃恢复（crash recovery）。也就是说，如果发生崩溃（例如，电源故障），文件系统必须在重新启动后仍能正常工作。风险在于崩溃可能会中断一系列更新，并使磁盘上的数据结构不一致（例如，一个块在某个文件中使用但同时仍被标记为空闲）。
- 不同的进程可能同时在文件系统上运行，因此文件系统代码必须协调以保持不变量。
- 访问磁盘的速度比访问内存慢几个数量级，因此文件系统必须保持常用块的内存缓存（上一节实验已经见过块缓存了）。
xv6 文件系统层级
块0，boot：它保存引导扇区，里面存储的代码负责 加载内核并启动系统
块1，super：它包含有关文件系统的元数据（文件系统大小（以块为单位）、数据块数、索引节点数和日志中的块数）
struct superblock { uint magic; // Must be FSMAGIC uint size; // Size of file system image (blocks) uint nblocks; // Number of data blocks uint ninodes; // Number of inodes. uint nlog; // Number of log blocks uint logstart; // Block number of first log block uint inodestart; // Block number of first inode block uint bmapstart; // Block number of first free map block };
log：保存日志，大小由
LOGSIZE常量决定，它主要负责文件操作的 原子性 和 一致性，系统挂了也可以通过磁盘上的日志区可以恢复磁盘状态inodes：索引节点，每个块有多个索引节点。
// On-disk inode structure struct dinode { short type; // File type short major; // Major device number (T_DEVICE only) short minor; // Minor device number (T_DEVICE only) short nlink; // Number of links to inode in file system uint size; // Size of file (bytes) uint addrs[NDIRECT+1]; // Data block addresses };
bit map：位图块，跟踪正在使用的数据块，bit=1：使用；bit=0：空闲。最大可管理 1024 * 8 = 8192个块
data：数据块它用来存储 文件的数据 或者是 目录的内容（dirent 数组）
关于inode
inode 是一种 索引-链接结构或者说多级索引 的文件物理组织形式
磁盘上的inode结构体struct dinode包含一个size和一个块号数组
前面的NDIRECT个数据块被列在数组中的前NDIRECT个元素中；这些块称为直接块（direct blocks）。接下来的NINDIRECT个数据块不在inode中列出，而是在称为**间接块（indirect block）**的数据块中列出。
这样组织的好处？
大多数文件较短，在零级索引、一级索引访问很快。大文件较长，访问二、三级索引虽然略慢，但是缓冲相应索引块到内存后，还是比较快的。
在本次实验中，你将向 xv6 文件系统中添加大文件和符号链接（symbolic links）。
记得切换分支到 fs
一、Large files
1.1 说明
在这个实验中，你将增加 xv6 文件的最大大小。目前，xv6 的文件大小限制为 268 个块，或 268×BSIZE 字节（在 xv6 中 BSIZE 是 1024）。这个限制来自于 xv6 的 inode 结构：它包含 12 个“直接”块编号和 1 个“一级间接”块编号，这个编号指向一个块，该块最多可存储 256 个块号，因此总共是 12+256=268 个块。
你将修改 xv6 的文件系统代码，为每个 inode 增加一个“双重间接”块。这个块包含 256 个一级间接块的地址，而每个一级间接块又可以包含最多 256 个数据块地址。最终，一个文件最多可以包含 65803 个块，即：
256 × 256 + 256 + 11 块（注意是 11 而不是 12，因为我们要牺牲一个直接块的位置来存放双重间接块的地址）。
前置知识
mkfs 程序用于创建 xv6 文件系统磁盘镜像，并决定文件系统的总块数；这个大小由 kernel/param.h 中的 FSSIZE 控制。你会看到这个实验的代码仓库中，FSSIZE 被设为了 200000 块。在执行 make 命令的输出中，你应该看到如下信息：
nmeta 70 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 25) blocks 199930 total 200000
这行输出描述了 mkfs 构建的文件系统：它有 70 个元数据块（用于描述文件系统的块），以及 199930 个数据块，总共 200000 个块。
在实验过程中如果需要重建文件系统，可以执行 make clean 来强制重新生成 fs.img。
查看内容
磁盘上的 inode 格式由 fs.h 中的 struct dinode 定义。你特别需要关注的包括：NDIRECT、NINDIRECT、MAXFILE，以及 struct dinode 中的 addrs[] 成员。
查阅 fs.c 中的 bmap() 函数，这个函数的作用是找到文件对应的磁盘数据块，理解它的具体逻辑。bmap() 函数既用于读文件，也用于写文件。在写操作中，bmap() 会在需要时分配新的块来存放文件内容，并在需要时分配一级间接块用于存储块地址。
bmap() 涉及两种块编号：
- 参数
bn是“逻辑块号”，即相对于文件起始处的块编号； ip->addrs[]中的值以及bread()的参数是磁盘块编号。
你可以将 bmap() 理解为将文件的逻辑块号映射为磁盘块号的函数。
你的任务
修改 bmap()，在保留直接块和一级间接块的基础上，加入对“双重间接块”的支持。由于不允许改变磁盘上 inode 的大小，你必须将直接块的数量从 12 减少为 11，来腾出一个槽位用于存放双重间接块的地址。
因此：
ip->addrs[]的前 11 项为直接块；- 第 12 项为一级间接块（和现有实现一样）；
- 第 13 项为新的双重间接块。
官网提示：
- 一定要理解
bmap()的实现原理。建议画出ip->addrs[]、一级间接块、双重间接块和数据块之间的关系图。理解为什么增加一个双重间接块能将最大文件大小增加256×256个块（实际上是少 1 个块，因为直接块减少了 1 个）。 - 思考如何用逻辑块号索引双重间接块以及它所指向的所有一级间接块。
- 如果你修改了
NDIRECT的定义，可能也要修改file.h中struct inode中的addrs[]的声明。确保struct inode和struct dinode中的addrs[]数组元素数量一致。 - 如果更改了
NDIRECT，务必重新生成新的fs.img，因为mkfs使用了NDIRECT构建文件系统。 - 如果文件系统状态异常，例如崩溃了，可以删除
fs.img文件（在 Unix 环境中删除，而不是在 xv6 中），然后重新执行make构建一个干净的文件系统。 - 不要忘记在使用
bread()读取块之后使用brelse()释放块。 - 和原本的
bmap()一样，只有在确实需要时才分配间接块和双重间接块。 - 确保
itrunc能够正确释放一个文件的所有块，包括双重间接块。
1.2 实现
先根据要求修改 dinode 的结构：
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDINDIRECT (NINDIRECT * NINDIRECT) // size for 2-lev indirect
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)
// On-disk inode structure
struct dinode {
short type; // File type
short major; // Major device number (T_DEVICE only)
short minor; // Minor device number (T_DEVICE only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+2]; // 11 direct, 1 indirect, 1 2-lev indirect
};
然后把 file.h 中的inode 的addrs 的数组长度也进行相应修改：
// in-memory copy of an inode
struct inode {
uint dev; // Device number
uint inum; // Inode number
int ref; // Reference count
struct sleeplock lock; // protects everything below here
int valid; // inode has been read from disk?
short type; // copy of disk inode
short major;
short minor;
short nlink;
uint size;
uint addrs[NDIRECT+2];
};
- 然后修改下bmap逻辑
- 主要是增加对于二级间接块的处理逻辑
// Inode content
//
// The content (data) associated with each inode is stored
// in blocks on the disk. The first NDIRECT block numbers
// are listed in ip->addrs[]. The next NINDIRECT blocks are
// listed in block ip->addrs[NDIRECT].
// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
static uint
bmap(struct inode *ip, uint bn)
{
uint addr, *a;
struct buf *bp;
if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0)
ip->addrs[bn] = addr = balloc(ip->dev);
return addr;
}
bn -= NDIRECT;
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0)
ip->addrs[NDIRECT] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn]) == 0){
a[bn] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr;
}
bn -= NINDIRECT;
if(bn < NDINDIRECT){
if((addr = ip->addrs[NDIRECT + 1]) == 0)
ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
uint index = bn / NINDIRECT;
if((addr = a[index]) == 0){
a[index] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
index = bn % NINDIRECT;
if((addr = a[index]) == 0){
a[index] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr;
}
panic("bmap: out of range");
}
- 类似的，修改释放逻辑
// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
int i, j;
struct buf *bp;
uint *a;
for(i = 0; i < NDIRECT; i++){
if(ip->addrs[i]){
bfree(ip->dev, ip->addrs[i]);
ip->addrs[i] = 0;
}
}
if(ip->addrs[NDIRECT]){
bp = bread(ip->dev, ip->addrs[NDIRECT]);
a = (uint*)bp->data;
for(j = 0; j < NINDIRECT; j++){
if(a[j])
bfree(ip->dev, a[j]);
}
brelse(bp);
bfree(ip->dev, ip->addrs[NDIRECT]);
ip->addrs[NDIRECT] = 0;
}
if(ip->addrs[NDIRECT+1]){
bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
a = (uint*)bp->data;
for(i = 0; i < NINDIRECT; i++){
if(a[i]){
struct buf *bp2 = bread(ip->dev, a[i]);
uint *a2 = (uint*)bp2->data;
for(j = 0; j < NINDIRECT; j++){
if(a2[j])
bfree(ip->dev, a2[j]);
}
brelse(bp2);
bfree(ip->dev, a[i]);
}
}
brelse(bp);
bfree(ip->dev, ip->addrs[NDIRECT+1]);
ip->addrs[NDIRECT+1] = 0;
}
ip->size = 0;
iupdate(ip);
}
测试一下：
bigfile
usertests
二、Symbolic links
2.1 说明
在本练习中，你将为 xv6 添加**符号链接（symbolic link）**功能。**符号链接（也叫软链接）**通过路径名引用另一个文件；当一个符号链接被打开时，内核会跟随该链接打开所指向的目标文件。符号链接类似于硬链接，但硬链接只能指向同一个磁盘上的文件，而符号链接可以跨磁盘设备。虽然 xv6 不支持多个设备，但实现该系统调用是理解路径名查找机制的一个很好练习。
你的任务
你需要实现一个新的系统调用：
int symlink(char *target, char *path);
该系统调用将在路径 path 处创建一个符号链接，指向名为 target 的文件。关于该系统调用的更多信息，可参考 man symlink。
提示：
- 添加系统调用框架：
首先为symlink分配一个新的系统调用号，并将其添加到：user/usys.pluser/user.h- 然后在
kernel/sysfile.c中实现一个空的sys_symlink函数。
- 添加符号链接文件类型：
在kernel/stat.h中添加一个新的文件类型标志T_SYMLINK，用于表示符号链接。 - 添加
O_NOFOLLOW标志：
在kernel/fcntl.h中添加一个新的打开标志O_NOFOLLOW，可以用于open系统调用。
注意，传递给open的标志使用按位或组合，所以你添加的新标志必须和已有标志不冲突。
添加后你就可以编译user/symlinktest.c并在Makefile中启用测试。 - 实现
symlink(target, path)系统调用：
实现该系统调用时，它应该在path位置创建一个新的符号链接，指向target。
注意：target文件不需要存在，系统调用也能成功。
你需要选择一个地方来存储符号链接的目标路径，例如可以将目标路径保存在 inode 的数据块中。
symlink应该像link和unlink一样，返回 0 表示成功，返回 -1 表示失败。 - 修改
open系统调用以处理符号链接的情况：- 如果指定路径所指向的文件不存在，则
open必须失败。 - 如果打开时设置了
O_NOFOLLOW，则open应打开符号链接本身，而不是跟随它。 - 如果符号链接的目标也是另一个符号链接，则你必须递归地跟随链接，直到找到非符号链接的文件。
- 如果符号链接形成了循环引用，你必须返回错误码。你可以用限制链接深度（例如不超过 10）的方法来近似处理这种情况。
- 如果指定路径所指向的文件不存在，则
- 其他系统调用（如
link和unlink）在处理路径时不应跟随符号链接；它们应仅操作符号链接本身。 - 无需支持目录的符号链接：
本实验不要求你处理符号链接指向目录的情况。
2.2 实现
在 kernel/syscall.h 添加 系统调用号：
// ...
#define SYS_close 21
#define SYS_symlink 22
kernel/syscall.c 中添加声明，修改系统调用表
extern uint64 sys_uptime(void);
extern uint64 sys_symlink(void);
static uint64 (*syscalls[])(void) = {
//...
[SYS_close] sys_close,
[SYS_symlink] sys_symlink,
};
在 kernel/stat.h 添加 符号链接标识：
#define T_DIR 1 // Directory
#define T_FILE 2 // File
#define T_DEVICE 3 // Device
#define T_SYMLINK 4 // symbolic link
分别在user.h 和 user.pl 中添加：
// ...
int sleep(int);
int uptime(void);
int symlink(const char*, const char*);
// ...
entry("sleep");
entry("uptime");
entry("symlink");
Makefile 也添加
UPROGS=\
...
$U/_zombie\
$U/_symlinktest\
在 kernel/fcntl.h 中添加一个新的打开标志 O_NOFOLLOW
#define O_RDONLY 0x000
#define O_WRONLY 0x001
#define O_RDWR 0x002
#define O_CREATE 0x200
#define O_TRUNC 0x400
#define O_NOFOLLOW 0x800 // not follow symbolic link
然后就是 修改 sys_open 的逻辑了：
uint64
sys_open(void)
{
char path[MAXPATH];
int fd, omode;
struct file *f;
struct inode *ip;
int n;
if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
return -1;
begin_op();
if(omode & O_CREATE){
ip = create(path, T_FILE, 0, 0);
if(ip == 0){
end_op();
return -1;
}
} else {
if((ip = namei(path)) == 0){
end_op();
return -1;
}
ilock(ip);
// symbolic link
int depth = 0; // depth limit
char target[MAXPATH];
// try to trace
while(depth < 10 && ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
// get path
if(readi(ip, 0, (uint64)target, 0, MAXPATH) <= 0) {
iunlockput(ip);
end_op();
return -1;
}
iunlockput(ip);
// not exists
if((ip = namei(target)) == 0) {
end_op();
return -1;
}
ilock(ip);
depth++;
}
if(depth >= 10) {
iunlockput(ip);
end_op();
return -1;
}
if(ip->type == T_DIR && omode != O_RDONLY){
iunlockput(ip);
end_op();
return -1;
}
}
if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
iunlockput(ip);
end_op();
return -1;
}
// ...
}
// ...
return fd;
}
然后实现一下 sys_symlink
uint64
sys_symlink(void)
{
char target[MAXPATH], path[MAXPATH];
struct inode *ip;
if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
return -1;
begin_op();
// create a symbolic link file
ip = create(path, T_SYMLINK, 0, 0);
if(ip == 0){
end_op();
return -1;
}
// write path to inode
if(writei(ip, 0, (uint64)target, 0, strlen(target)) != strlen(target)){
iunlockput(ip);
end_op();
return -1;
}
iunlockput(ip);
end_op();
return 0;
}
测试一下：
