xv6 Lab8 File system - MIT 6.1810 Fall 2025 Operating System
本文最后更新于 2026年8月18日 晚上
阅读
简单读一下书，让 GPT 翻译并提炼重点，然后读对应的部分。
xv6 将文件系统分为 7 层：
- Disk layer：真正向 VirtIO disk 读写 block。
- Buffer cache：把磁盘 block 缓存在内存，并保证一个 block 同一时间只有一个线程修改。
- Logging：把多个 block 的修改组成 transaction，保证 crash 后要么全部生效，要么全部不生效。
- Inode：把一个文件表示成 inode + 若干 data block。
- Directory：目录其实是一种特殊文件，内容是一系列
name -> inode number。 - Pathname：解析
/a/b/c。 - File descriptor：最终向用户提供
open/read/write/...这样的统一接口。
所谓「crash consistency 崩溃一致性」：崩溃的时候，修改 inode，记录日志等工作完成到一半，导致不一致。xv6 的实现方式是日志，不直接修改正式文件系统，先把这次 transaction 的修改写进 log。
关于日志的设计，位于磁盘的特定区域。
inode 分磁盘上的 struct dinode 和内存里的 struct inode。内存 inode 只是磁盘 inode 的缓存副本
磁盘 inode 的重要字段：
type
nlink
size
addrs[]含义：
type：普通文件、目录、device……nlink：有多少 directory entry 指向它。size：文件大小。addrs[]：文件数据所在的 disk block number。
inode number（inum）就是 inode 在磁盘 inode 区域中的编号。
内存中的 struct inode 额外拥有：
ref
lock
valid
...ref 表示当前 kernel 中有多少 C 指针正在引用这个 inode。
然后有区分 direct blocks 和 indirect 的，也就是一级索引和二级索引：
然后查询 inode 和目录也是一堆 API，比如对于一个完整的路径，依据分隔符进行分割然后递归查询逐层的 inode 的 namex() 。
Large files
根据 hints 来：
分析 bmap() 函数
代码
// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
// returns 0 if out of disk space.
static uint
bmap(struct inode *ip, uint bn)
{
uint addr, *a;
struct buf *bp;
if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0){
addr = balloc(ip->dev);
if(addr == 0)
return 0;
ip->addrs[bn] = addr;
}
return addr;
}
bn -= NDIRECT;
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0){
addr = balloc(ip->dev);
if(addr == 0)
return 0;
ip->addrs[NDIRECT] = addr;
}
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn]) == 0){
addr = balloc(ip->dev);
if(addr){
a[bn] = addr;
log_write(bp);
}
}
brelse(bp);
return addr;
}
panic("bmap: out of range");
}- 「阅读」部分的图 10.3 十分十分重要。
bn是 logical block number，即相对于文件开头而言，这个 block 是文件中的第几个 block。返回的是实际的 disk block number。- 若
bn < NDIRECT，根据图片所示，直接映射到ip->addrs[bn]处的数据块。- 但是实际实现是先检查是否存在，如果不存在还得
balloc()分配一个出来。
- 但是实际实现是先检查是否存在，如果不存在还得
- 若
bn > NDIRECT：- 先
bn -= NDIRECT，这一步是为了把原本在整个文件范围内的逻辑块号，转变为一级间接块数组内的下标- 事实上看图也能看出来进入一级块之后就又是 address 1 ~ 256 了，不过实际上应该是 0 ~ 255。
- 检查
bn < NINDIRECT，事实上就是检查之前的bn在不在最大范围内（MAXFILE = NDIRECT + NINDIRECT) - 检查通过后，检查间接块的存在性，没有就分配
- 然后，首先通过
bread()获取磁盘上的这个 block 的间接块的struct buf，获取里面的数据。- 如果数据为空，继续分配，不空就直接获得地址，可以直接返回了（不过是代码的写法上没这么写，逻辑等价）
- 确认非空之后，给
a[bn]里面映射上刚分配好的块，再记录日志 - 最后释放掉，然后返回这个地址
- 先
修改宏定义
目前 xv6 的文件最多只能有 268 blocks，分析一下原因，是因为规定了 #define NDIRECT 12，并且 dinode 和 inode 里面有 uint addrs[NDIRECT+1];。
也就是，12 个直接块号，以及 1 个一级间接块号。
又规定 BSIZE 1024（块的字节数），sizeof(uint) = 4 ，故一个间接块号至多存 256 个 block number，故 MAXFILE = 12 + 256 = 268 blocks。
这个 lab 需要实现 doubly-indirect block，变成了 $256^2 + 256 + 11 = 65803 \text{blocks}$
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NINDIRECT2 (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT2)然后，修改 struct inode 和 struct dinode 字段：
uint addrs[NDIRECT+2];思考清楚计算方式
思考：给定一个文件的 logical block number，应该怎样计算它在 doubly-indirect block 中的位置，也就是先选第几个 singly-indirect block，再选其中第几个 data block。
这边偷一张知乎上的图，画的很好：
具体而言，如果 bn 是位于二级索引的位置：
-
首先是需要先减去前面两个部分（其实计算的过程中逐步减掉了）
-
然后，2nd indirect 里面的每一个 address，都映射到了另一个 1st indirect，也就是另外的 256 个实际的 data block
-
那么，举个例子，bn = 45162（随便打的符合要求的数字）
- 经过一级和二级的判断，bn = 45162 - 11 - 256 = 44895
- 然后，整除 256，得到 175，也就是位于第 175 个一级索引
- 然后，44895 % 256 = 95，也就是位于这个一级索引指向的第 95 个 data block
这就是计算方式。
实现对 bmap() 的修改
代码
static uint
bmap(struct inode *ip, uint bn)
{
uint addr, *a;
struct buf *bp;
if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0){
addr = balloc(ip->dev);
if(addr == 0)
return 0;
ip->addrs[bn] = addr;
}
return addr;
}
bn -= NDIRECT;
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0){
addr = balloc(ip->dev);
if(addr == 0)
return 0;
ip->addrs[NDIRECT] = addr;
}
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn]) == 0){
addr = balloc(ip->dev);
if(addr){
a[bn] = addr;
log_write(bp);
}
}
brelse(bp);
return addr;
}
// 以下为实现代码
bn -= NINDIRECT;
if(bn < NINDIRECT2) {
// 这里的 addr 是二级间接块的地址
if ((addr = ip->addrs[NDIRECT + 1]) == 0) {
addr = balloc(ip->dev);
if (addr == 0) {
return 0;
}
ip->addrs[NDIRECT + 1] = addr;
}
// 这里的 bp 是二级间接块的实际 struct buf
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
// 这里的 addr 是二级间接块指向的一级间接块的地址
if ((addr = a[bn / NINDIRECT]) == 0) {
addr = balloc(ip->dev);
if (addr == 0) {
return 0;
}
a[bn / NINDIRECT] = addr;
// 记得任何对于实际 buf 的修改都要落日志，维护崩溃一致性
log_write(bp);
}
brelse(bp);
// 这里的 bp 是一级间接块的实际的 struct buf
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
// 这里的 addr 是最后实际的数据的地址
if ((addr = a[bn % NINDIRECT]) == 0) {
addr = balloc(ip->dev);
if (addr == 0) {
return 0;
}
a[bn % NINDIRECT] = addr;
log_write(bp);
}
brelse(bp);
return addr;
}
panic("bmap: out of range");
}其实很多地方是重复利用了一个变量，比如 bp 和 a 和 addr，这是因为原本的代码就是这样的重复利用，虽然不清晰，不过为了保持代码风格一致，就这样吧。
记得对每一个通过 bread() 读取的 block，都不要忘记最终调用 brelse()。
修改 itrunc()
不要忘记修改
itrunc()，确保它能够释放文件的所有 block，包括 double-indirect block 及其下层 block。
就像改了 kalloc() 加一级，那也肯定是要修改 kfree() 的。
代码
void
itrunc(struct inode *ip)
{
int i, j, k;
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(j = 0; j < NINDIRECT; j++) {
uint in1_addr;
if ((in1_addr = a[j]) != 0) {
struct buf *in1_bp = bread(ip->dev, in1_addr);
uint *in1_a = (uint*)in1_bp->data;
for(k = 0; k < NINDIRECT; k++) {
bfree(ip->dev, in1_a[k]);
}
brelse(in1_bp);
bfree(ip->dev, in1_addr);
}
}
brelse(bp);
bfree(ip->dev, ip->addrs[NDIRECT + 1]);
ip->addrs[NDIRECT + 1] = 0;
}
ip->size = 0;
iupdate(ip);
}Symbolic links
给 xv6 添加符号链接 / 软链接功能，也就是实现系统调用 symlink。
复习一下，所谓的软链接，就是一个记录目标路径名的 alias。这么理解区别：
hard link：
name → inode
symbolic link：
name → symlink inode → pathname → inode这个 lab 里面不需要处理指向目录的软链接。
以 hints 为线索：
添加和系统调用相关的基础配置
为 symlink 创建一个新的 system call number：
// kernel/syscall.h
#define SYS_symlink 22在 kernel/sysfile.c 里面实现空的 sys_symlink()：
uint64
sys_symlink(void)
{
}在 kernel/syscall.cl 下面声明、加入系统调用的数组：
extern uint64 sys_symlink(void);
static uint64 (*syscalls[])(void) = {
[SYS_fork] sys_fork,
// ...
[SYS_symlink] sys_symlink,
};在 user/usys.pl 里面加入对应的 entry：
entry("symlink");在 user/user.h 里面加入声明：
int symlink(char *target, char *path);为什么知道具体的返回值？RTFM
加入新的标识文件类型
// kernel/stat.h
#define T_DIR 1 // Directory
#define T_FILE 2 // File
#define T_DEVICE 3 // Device
#define T_SYMLINK 4 // soft link添加新的 flag
#define O_RDONLY 0x000
#define O_WRONLY 0x001
#define O_RDWR 0x002
#define O_CREATE 0x200
#define O_TRUNC 0x400
#define O_NOFOLLOW 0x20000这主要是给 open 用的（RTFM 得知这个 flag 是这个数）
不过其实自己实现一个也可以，只要遵循传给 open() 的 flags 会用 bitwise OR 组合，所以新 flag 不能和任何已有 flag 的 bit 重叠的原则即可。
根据 man：
If the trailing component (i.e., basename) of pathname is a symbolic link, then the open fails, with the error ELOOP
实现 symlink()
在 path 创建新的 symbolic link 并让它指向 target，注意 target 不需要真实存在。
这里我一开始搞不懂这些 API 和概念（读书不仔细），然后我就考虑读一下 sys_link() 的实现：
代码
// Create the path new as a link to the same inode as old.
uint64
sys_link(void)
{
char name[DIRSIZ], new[MAXPATH], old[MAXPATH];
struct inode *dp, *ip;
if(argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
return -1;
begin_op();
if((ip = namei(old)) == 0){
end_op();
return -1;
}
ilock(ip);
if(ip->type == T_DIR){
iunlockput(ip);
end_op();
return -1;
}
ip->nlink++;
iupdate(ip);
iunlock(ip);
if((dp = nameiparent(new, name)) == 0)
goto bad;
ilock(dp);
if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){
iunlockput(dp);
goto bad;
}
iunlockput(dp);
iput(ip);
end_op();
return 0;
bad:
ilock(ip);
ip->nlink--;
iupdate(ip);
iunlockput(ip);
end_op();
return -1;
}梳理出一些要点：
begin_op()和end_op()开启文件系统的事务，保证 ACIDnamei()返回路径对应的文件的inode结构体指针- 得到了
inode指针之后，如果想做修改，还需要使用ilock()进行加锁，再使用iunlock()解锁，修改之后需要使用iupdate进行落盘，把内存inode写回磁盘上的struct dinode
但其实只能知道这些，然后读书（其实是问 LLM 要点）可以得到这些额外的信息：
create()给出的 inode 是直接带锁的，不需要自己加锁- 软链接是通过创建一个类型为
T_SYMLINK的 inode，里面的 data block（实际是inode的addr所指向的buf（通过bmap()求得）的uchar data[BSIZE];） 是target来实现的。 - 因此，如果想读写，是有对应的 API 的，也就是
readi()和writei()，这个的用法直接 Ctrl + F 一下就能看懂了。
但是实际上理解也有偏颇，还需要读 create()，这里直接给出 LLM 的纠错版：
引用
为什么
namei()的结果会泄漏？
namei()返回的不只是一个普通指针，它还替调用者持有了一个 inode 引用。可以想象成：
struct inode *ip = namei(path); // ip->ref 被加了一次调用者用完后必须：
iput(ip);否则引用计数永远不会减回来。
你原来写的是：
if(namei(path) != 0){ end_op(); return -1; }如果文件存在，
namei()返回了一个带引用的 inode，但你没有把返回值保存起来：namei() 获得引用 ↓ 返回 inode 指针 ↓ 指针被直接丢弃 ↓ 无法再调用 iput() ↓ 引用泄漏它类似：
if(malloc(100) != 0) return;内存申请成功了，但指针直接丢掉，因此没办法
free()。如果真的要这样检查，至少应该：
struct inode *existing = namei(path); if(existing != 0){ iput(existing); end_op(); return -1; }不过在
sys_symlink()里，这个检查应该直接删除，因为create()已经会在父目录锁的保护下检查路径是否存在。提前
namei()再create()还有并发问题：进程 A：namei(path) 发现不存在 进程 B：创建 path 进程 A：create(path)真正可靠的“检查并创建”必须在
create()内部完成。
iunlock()和iunlockput()的区别它们控制两个不同的东西：
iunlock(ip);只释放 inode 锁，但仍然保留引用：
锁：释放 引用：保留 ip：以后还能继续使用而：
iunlockput(ip);等价于：
iunlock(ip); iput(ip);结果是：
锁：释放 引用：也释放 ip：以后不能继续使用完整状态变化可以这样看：
ip = namei(path);此时：
ref = +1 locked = no然后：
ilock(ip);变成：
ref = +1 locked = yes如果调用：
iunlock(ip);变成：
ref = +1 locked = no还可以再次使用
ip。如果调用：
iunlockput(ip);变成：
ref = 释放 locked = no不能再使用
ip。为什么
link()里使用iunlock()？
sys_link()的逻辑大致是：ip = namei(old); // 获得 old inode 的引用 ilock(ip); ip->nlink++; iupdate(ip); iunlock(ip); // 只解锁，仍保留引用它此时还没有用完
ip。后面还需要：dp = nameiparent(new, name); ilock(dp); dirlink(dp, name, ip->inum);所以必须保留
ip的引用。但又没必要继续锁住
ip，而且持有它的锁再做路径查找、获取父目录锁，会增加死锁风险。因此采用：iunlock(ip);也就是：
我暂时不需要锁住它，但这个 inode 还没用完，不能释放引用。
成功完成新目录项之后才：
iput(ip);如果中间失败，还需要重新锁定它，回滚
nlink：ilock(ip); ip->nlink--; iupdate(ip); iunlockput(ip);因此
link()的生命周期是：namei(old) 获得引用 ↓ ilock(ip) 加锁 ↓ 修改 nlink ↓ iunlock(ip) 解锁，但保留引用 ↓ 创建新目录项，期间仍需要 ip->inum ↓ iput(ip) 最后释放引用大部分地方使用
iunlockput()，是因为那些地方解锁以后就再也不需要这个 inode 了。另外两个典型的
iunlock()场景：
open()：引用转交给f->ip，等close()时释放。chdir()：引用转交给proc->cwd。判断方式就是：
解锁后还需要这个 inode 或要把引用交给别人？ 是 → iunlock() 否 → iunlockput()
上面的误会也导致了我开始的错误实现（包括 open()）
因此给出 symlink() 的实现：
代码
uint64
sys_symlink(void)
{
char path[MAXPATH], target[MAXPATH];
struct inode *ip;
if(argstr(1, path, MAXPATH) < 0 || argstr(0, target, MAXPATH) < 0) {
return -1;
}
begin_op();
// 这段代码不需要，`create()` 自己会检查目标路径是否已存在
// if (namei(path) != 0) {
// end_op();
// return -1;
// }
ip = create(path, T_SYMLINK, 0, 0);
if (ip == 0) {
end_op();
return -1;
}
int len = strlen(target) + 1;
if (writei(ip, 0, (uint64)target, 0, len) != len) {
end_op();
return -1;
}
// iupdate(ip); 不需要，writei() 有
iunlockput(ip);
end_op();
return 0;
}修改 open()
因为如果 open() 传入的 path 实际上只是一个符号链接，肯定不能直接返回符号链接的 inode 对应的 fd，而应该返回其指向的 target 所对应的。这里加上特殊处理即可。
代码
uint64
sys_open(void)
{
char path[MAXPATH];
int fd, omode;
struct file *f;
struct inode *ip;
int n;
argint(1, &omode);
if((n = argstr(0, path, MAXPATH)) < 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);
// 目录检查放在展开之后
}
// ========
int depth = 0;
while (ip->type == T_SYMLINK && omode != O_NOFOLLOW) {
char target[MAXPATH];
if (readi(ip, 0, (uint64)target, 0, MAXPATH) <= 0) {
iunlockput(ip);
end_op();
return -1;
}
iunlockput(ip);
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;
}
if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
if(f)
fileclose(f);
iunlockput(ip);
end_op();
return -1;
}
if(ip->type == T_DEVICE){
f->type = FD_DEVICE;
f->major = ip->major;
} else {
f->type = FD_INODE;
f->off = 0;
}
f->ip = ip;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
if((omode & O_TRUNC) && ip->type == T_FILE){
itrunc(ip);
}
iunlock(ip);
end_op();
return fd;
}这里可能存在的问题是不知道该在哪里插入，我的建议是分析一下 xv6 一共有的这些 flags 分别对应的情况，然后照着分支去分析
另：一开始的错误实现
代码
uint64
sys_symlink(void)
{
char path[MAXPATH], target[MAXPATH];
struct inode *ip;
if(argstr(0, path, MAXPATH) < 0 || argstr(1, target, MAXPATH) < 0) {
return -1;
}
begin_op();
if (namei(path) != 0) {
end_op();
return -1;
}
ip = create(path, T_SYMLINK, 0, 0);
if (ip == 0) {
end_op();
return -1;
}
if (writei(ip, 0, (uint64)target, 0, MAXPATH) < 0) {
end_op();
return -1;
}
iupdate(ip);
iunlock(ip);
end_op();
return 0;
}
uint64
sys_open(void)
{
char path[MAXPATH];
int fd, omode;
struct file *f;
struct inode *ip;
int n;
argint(1, &omode);
if((n = argstr(0, path, MAXPATH)) < 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);
if(ip->type == T_DIR && omode != O_RDONLY){
iunlockput(ip);
end_op();
return -1;
}
}
// ========
ip = namei(path);
if (ip == 0) {
end_op();
return -1;
}
ilock(ip);
int depth = 0;
while (ip->type == T_SYMLINK && omode != O_NOFOLLOW) {
char target[MAXPATH];
if (readi(ip, 0, (uint64)target, 0, MAXPATH) < 0) {
iunlockput(ip);
end_op();
return -1;
}
iunlockput(ip);
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_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
iunlockput(ip);
end_op();
return -1;
}
if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
if(f)
fileclose(f);
iunlockput(ip);
end_op();
return -1;
}
if(ip->type == T_DEVICE){
f->type = FD_DEVICE;
f->major = ip->major;
} else {
f->type = FD_INODE;
f->off = 0;
}
f->ip = ip;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
if((omode & O_TRUNC) && ip->type == T_FILE){
itrunc(ip);
}
iunlock(ip);
end_op();
return fd;
}