Apr 15, 2026

6.s081 Lab8 file system 实现

~/ 6.s081#OS#MIT courses

文件系统是操作系统中最复杂的组件之一，它需要管理磁盘块的分配、维护文件层级结构、处理并发访问，最重要的是：必须能够从系统崩溃中安全恢复。在这个 Lab 中，我们将深入 xv6 的文件系统内部，完成两个扩展任务：增加文件最大容量（支持大文件）以及实现软链接（Symbolic links）。

此 Lab 包含两个任务，涉及修改 Inode 结构和路径解析逻辑。

xv6-book Chapter 8 部分内容

一、文件系统的七层架构

xv6 的文件系统实现被优雅地划分为了七个层次，从下到上依次为：

Disk (磁盘层)：直接与硬件（virtio 驱动）交互，读写物理磁盘块。
Buffer cache (缓存层)：在内存中缓存磁盘块，并保证同一时刻只有一个内核线程能修改特定的块（Lab 7 优化的就是这里）。
Logging (日志层)：文件系统崩溃恢复的核心。通过将多个相关的磁盘更新打包成一个原子事务（Transaction），保证系统在断电时不会留下损坏的内部数据结构。
Inode (索引结点层)：将无序的磁盘块抽象为一个个独立的文件，每个文件由一个唯一的 i-number 标识，包含文件大小和数据块的物理位置。
Directory (目录层)：一种特殊的 Inode，其内容是一系列目录项（目录名与 i-number 的映射）。
Pathname (路径层)：提供层级化路径的解析（例如将 /usr/bin/sh 递归解析为对应的 Inode）。
File descriptor (文件描述符层)：将许多 Unix 资源（文件、管道、设备）统一抽象，供用户进程操作。

二、崩溃恢复与 Logging 层

磁盘的不一致性问题

假设我们在删除一个文件，需要进行两步磁盘写操作：

在 Inode 结构中清空数据块指针。
在 Bitmap（位图）中将该数据块标记为空闲。

如果系统在执行完第一步后断电崩溃，重启后就会出现：一个块在 Bitmap 中显示“已分配”，但没有任何 Inode 指向它。这个块变成了“幽灵块”，永远无法被回收（空间泄露）。更糟的是，如果先执行第二步后崩溃，可能导致两个文件同时指向同一个数据块，产生严重的安全问题。

xv6 的解决办法：Write-Ahead Log

为了保证多步磁盘写操作的原子性，xv6 引入了日志：

写日志：内核不直接修改目标磁盘块，而是先将所有想做的修改写入磁盘上预留的 Log 区。
提交 (Commit)：当所有修改都安全写入 Log 区后，向 Log Header 写入一个计数，表示事务完成。这是决定操作生死的唯一界限。
安装 (Install)：将 Log 区的数据真正拷贝到目标位置。
清理 (Clean)：清空 Log Header。

如果重启时发现 Log Header 中有完整的提交记录，就重放（Replay）安装过程；如果没有，则直接丢弃，仿佛操作从未发生。

三、Inode 的两种形态

Inode 是文件系统的核心枢纽，它分为磁盘上 (on-disk) 和内存中 (in-memory) 两种形态：

磁盘上的 dinode：持久化存储，包含文件类型、大小、以及指向数据块的 addrs 数组。
内存中的 inode：是磁盘形态的缓存副本，但多了内核运行时急需的信息：ref（引用计数）和一根保护该文件内容的睡眠锁（sleep-lock）。

6.s081 Lab8: file system 实现

一、Large files (moderate)

在 xv6 原生的实现中，一个 Inode 的 addrs 数组包含 12 个直接索引（Direct blocks）和 1 个一级间接索引（Indirect block）。一个块大小为 1024 字节，一个块号占 4 字节，因此一级索引表可以容纳 256 个块号。原生最大文件体积：(12+256)×1024=268 KB。

我们的任务是修改数据结构，将 12 个直接索引减少为 11 个，腾出一个位置作为二级间接索引（Double-indirect block）。改造后的最大文件体积跃升为：(11+256+256×256)×1024≈64 MB。

1. 修改 Inode 结构与 bmap

在 kernel/fs.h 中，将 NDIRECT 改为 11，并定义二级索引的相关宏：

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDOUBINDIRECT (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NDOUBINDIRECT)

bmap(struct inode *ip, uint bn) 负责将文件的逻辑块号 bn 映射到物理磁盘块号。我们需要为其增加第三段逻辑：处理落入二级间接索引范围内的块。

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 < NDOUBINDIRECT){
    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 nindirect_bn = bn / NINDIRECT;
    bn %= NINDIRECT;

    if((addr = a[nindirect_bn]) == 0){
      a[nindirect_bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    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;
  }

  panic("bmap: out of range");
}

2. 修改 itrunc (释放大文件)

能分配还得能释放，否则会导致严重的磁盘空间泄露。我们需要在 itrunc 中增加三层嵌套循环，来递归释放二级间接块占用的所有空间。

踩坑记录 ：释放错了指针导致 freeing free block Panic

在最初写三层循环释放二级间接块时，我的最内层循环长这样： bfree(ip->dev, a[k]); 跑测试时直接内核崩溃。仔细 Debug 后发现，a 是一级表的数据，我本意是要释放二级表 a_2 中的数据块 a_2[k]。一字之差，导致我反反复复释放存索引的元数据块，当第二次释放同一个已经为空的块时，Bitmap 校验失败直接 panic。 PS：在 C 语言中操作嵌套数据结构时，临时指针的命名和使用必须极其严谨。

修改后的正确释放逻辑如下：

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(int j = 0; j < NINDIRECT; j++){
      if(a[j]){
        struct buf *bp_2;
        uint *a_2;
        bp_2 = bread(ip->dev, a[j]);
        a_2 = (uint*)bp_2->data;
        for (int k = 0; k < NINDIRECT; k++){
          if(a_2[k])
            bfree(ip->dev, a_2[k]);
        }
        brelse(bp_2);
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }

  ip->size = 0;
  iupdate(ip);
}

二、Symbolic links (moderate)

硬链接（Hard links）是通过多个名字指向同一个 Inode 来实现的，不能跨越文件系统。而软链接（Symbolic links）本质上是一个独立的全新文件，它的 Inode 类型为 T_SYMLINK，其数据块中存放的是目标文件的路径字符串。当内核 open 遇到软链接时，会自动读取该字符串并进行路径的跳转。

1. 创建 sys_symlink

这个系统调用的核心逻辑非常简单：就是新建一个文件，并把 target 字符串写进它的数据块。值得注意的是，软链接不关心目标文件是否存在，只要把“纸条”（目标路径）塞进“空瓶子”（软链接文件）即可。

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();
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0){
    end_op();
    return -1;
  }

  int target_len = strlen(target);
  if (writei(ip, 0, (uint64)target, 0, target_len) != target_len){
    iunlockput(ip);
    end_op();
    return -1;
  }

  iunlockput(ip);
  end_op();
  return 0;
}

2. 修改 sys_open 支持Symbolic link

这是本 Lab 最容易引发**死锁（Deadlock）**的地方。当用户通过 open 打开文件时，我们需要拦截 T_SYMLINK 类型，并开始循环追踪（最大深度设为 10 以防止软链接环路 A -> B -> A 导致内核死循环）。

踩坑记录：带着锁找锁的死锁问题

第一次写 sys_open 追踪逻辑时，我读出了 target 路径，然后直接调用 ip = namei(target);。系统瞬间卡死。回顾 Lab 7 对锁的领悟才突然意识到：此时原软链接的 ip 还被 ilock 锁着！如果新路径的解析过程中恰好又要访问父目录或产生资源竞争，就会引发典型的“持有并等待”死锁。必须先解锁当前 Inode，再去解析新路径。

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);
    if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)){
      int depth = 0;

      while (depth < 10){
        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);
        if(ip->type == T_SYMLINK){
          depth++;
        } else {
          break;
        }
      }

      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;
}

经历过 Lab 7 对锁的深度折磨后，在 Lab 8 中看到文件系统随处可见的 ilock、iunlockput 时，感觉亲切了许多。在这个 Lab 中，我真切地体会到了：

多级索引分配机制并不是课本上干巴巴的公式，而是 bmap 里严密的指针偏移计算。
锁的粒度与周期：在路径解析、文件读写的过程中，锁什么时候加、什么时候放，差一条指令都会带来灾难性的死锁或数据毁坏。
事务机制的伟大：begin_op 和 end_op 完美地包裹了所有对磁盘数据的脏修改，极大地降低了编写文件系统上层业务逻辑时的心智负担。

至此，xv6 的核心子系统已尽收眼底，收获颇丰！