要做这个实验，首先要理解文件系统的相关概念。
阮一峰—理解Linux文件系统
从内核文件系统看文件读写过程
xv6中文指导—File System

基本原理

与 FAT 文件系统类似，xv6 文件系统中的每一个 inode 结构体中，采用了混合索引的方式记录数据的所在具体盘块号。每个文件所占用的前 12 个盘块的盘块号是直接记录在 inode 中的（每个盘块 1024 字节），所以对于任何文件的前 12 KB 数据，都可以通过访问 inode 直接得到盘块号。这一部分称为直接记录盘块。
对于大于 12 个盘块的文件，大于 12 个盘块的部分，会分配一个额外的一级索引表（一盘块大小，1024Byte），用于存储这部分数据的所在盘块号。
由于一级索引表可以包含 BSIZE(1024) / 4 = 256 个盘块号，加上 inode 中的 12 个盘块号，一个文件最多可以使用 12+256 = 268 个盘块，也就是 268KB。

image.png
Large files

在本作业中，您将增加xv6文件的最大大小。目前，xv6文件限制为268个块或268*BSIZE字节（在xv6中BSIZE为1024）。此限制来自以下事实：一个xv6 inode包含12个“直接”块号和一个“间接”块号，“一级间接”块指一个最多可容纳256个块号的块，总共12+256=268个块。

inode 结构（含有 NDIRECT=12 个直接记录盘块，还有一个一级索引盘块，后者又可额外包含 256 个盘块号）：

  1. // kernel/fs.c
  3. // note: NDIRECT=12
  4. // On-disk inode structure
  5. struct dinode {
  6.   short type;           // File type
  7.   short major;          // Major device number (T_DEVICE only)
  8.   short minor;          // Minor device number (T_DEVICE only)
  9.   short nlink;          // Number of links to inode in file system
  10.   uint size;            // Size of file (bytes)
  11.   uint addrs[NDIRECT+1];   // Data block addresses
  12. };

本 lab 的目标是通过为混合索引机制添加二级索引页，来扩大能够支持的最大文件大小。

  1. // kernel/fs.c
  3. // Return the disk block address of the nth block in inode ip.
  4. // If there is no such block, bmap allocates one.
  5. static uint
  6. bmap(struct inode *ip, uint bn)
  7. {
  8.   uint addr, *a;
  9.   struct buf *bp;
  11.   if(bn < NDIRECT){
  12.     if((addr = ip->addrs[bn]) == 0)
  13.       ip->addrs[bn] = addr = balloc(ip->dev);
  14.     return addr;
  15.   }
  16.   bn -= NDIRECT;
  18.   if(bn < NINDIRECT){ // singly-indirect
  19.     // Load indirect block, allocating if necessary.
  20.     if((addr = ip->addrs[NDIRECT]) == 0)
  21.       ip->addrs[NDIRECT] = addr = balloc(ip->dev);
  22.     bp = bread(ip->dev, addr);
  23.     a = (uint*)bp->data;
  24.     if((addr = a[bn]) == 0){
  25.       a[bn] = addr = balloc(ip->dev);
  26.       log_write(bp);
  27.     }
  28.     brelse(bp);
  29.     return addr;
  30.   }
  31.   bn -= NINDIRECT;
  33.   if(bn < NINDIRECT * NINDIRECT) { // doubly-indirect
  34.     // Load indirect block, allocating if necessary.
  35.     if((addr = ip->addrs[NDIRECT+1]) == 0)
  36.       ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
  37.     bp = bread(ip->dev, addr);
  38.     a = (uint*)bp->data;
  39.     if((addr = a[bn/NINDIRECT]) == 0){
  40.       a[bn/NINDIRECT] = addr = balloc(ip->dev);
  41.       log_write(bp);
  42.     }
  43.     brelse(bp);
  44.     bn %= NINDIRECT;
  45.     bp = bread(ip->dev, addr);
  46.     a = (uint*)bp->data;
  47.     if((addr = a[bn]) == 0){
  48.       a[bn] = addr = balloc(ip->dev);
  49.       log_write(bp);
  50.     }
  51.     brelse(bp);
  52.     return addr;
  53.   }
  55.   panic("bmap: out of range");
  56. }
  58. // Truncate inode (discard contents).
  59. // Caller must hold ip->lock.
  60. void
  61. itrunc(struct inode *ip)
  62. {
  63.   int i, j;
  64.   struct buf *bp;
  65.   uint *a;
  67.   for(i = 0; i < NDIRECT; i++){
  68.     if(ip->addrs[i]){
  69.       bfree(ip->dev, ip->addrs[i]);
  70.       ip->addrs[i] = 0;
  71.     }
  72.   }
  74.   if(ip->addrs[NDIRECT]){
  75.     bp = bread(ip->dev, ip->addrs[NDIRECT]);
  76.     a = (uint*)bp->data;
  77.     for(j = 0; j < NINDIRECT; j++){
  78.       if(a[j])
  79.         bfree(ip->dev, a[j]);
  80.     }
  81.     brelse(bp);
  82.     bfree(ip->dev, ip->addrs[NDIRECT]);
  83.     ip->addrs[NDIRECT] = 0;
  84.   }
  86.   if(ip->addrs[NDIRECT+1]){
  87.     bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
  88.     a = (uint*)bp->data;
  89.     for(j = 0; j < NINDIRECT; j++){
  90.       if(a[j]) {
  91.         struct buf *bp2 = bread(ip->dev, a[j]);
  92.         uint *a2 = (uint*)bp2->data;
  93.         for(int k = 0; k < NINDIRECT; k++){
  94.           if(a2[k])
  95.             bfree(ip->dev, a2[k]);
  96.         }
  97.         brelse(bp2);
  98.         bfree(ip->dev, a[j]);
  99.       }
  100.     }
  101.     brelse(bp);
  102.     bfree(ip->dev, ip->addrs[NDIRECT+1]);
  103.     ip->addrs[NDIRECT + 1] = 0;
  104.   }
  106.   ip->size = 0;
  107.   iupdate(ip);
  108. }


Symbolic links

首先实现 symlink 系统调用，用于创建符号链接。

要点

  • 添加符号链接(软链接)的系统调用 symlink
  • 修改 open 系统调用处理符号链接的情况, 且符号链接的目标文件仍是符号链接文件时需要递归查找目标文件.
  • 以 O_NOFOLLOW 打开符号链接不会跟踪到链接的文件.
  • 其它系统调用不会跟踪符号链接, 之后处理符号链接文件本身.

  1. 添加有关 symlink 系统调用的定义声明. 包括 kernel/syscall.h, kernel/syscall.c, user/usys.pl 和 user/user.h.

  2. 在 kernel/sysfile.c 中实现 sys_symlink() 函数.

    该函数即用来生成符号链接. 符号链接相当于一个特殊的独立的文件, 其中存储的数据即目标文件的路径.

因此在该函数中, 首先通过 create()创建符号链接路径对应的 inode 结构(同时使用 T_SYMLINK 与普通的文件进行区分). 然后再通过 writei() 将链接的目标文件的路径写入 inode (的 block)中即可. 在这个过程中, 无需判断连接的目标路径是否有效.

需要注意的是关于文件系统的一些加锁释放的规则. 函数 create() 会返回创建的 inode, 此时也会持有其 inode 的锁. 而后续 writei() 是需要在持锁的情况下才能写入. 在结束操作后(不论成功与否), 都需要调用 iunlockput() 来释放 inode 的锁和其本身, 该函数是 iunlock() 和 iput() 的组合, 前者即释放 inode 的锁; 而后者是减少一个 inode 的引用(对应字段 ref, 记录着内存中指向该 inode 的指针数, 这里的 inode 实际上是内存中的 inode, 是从内存的 inode 缓存 icache 分配出来的, 当 ref 为 0 时就会回收到 icache 中), 表示当前已经不需要持有该 inode 的指针对其继续操作了.

  1. uint64
  2. sys_symlink(void) {
  3.     struct inode *ip;
  4.     char target[MAXPATH], path[MAXPATH];
  5.     if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) {
  6.         return -1;
  7.     }
  8.     begin_op();
  9.     ip = create(path, T_SYMLINK, 0, 0);
  10.     if (ip == 0) {
  11.         end_op();
  12.         return -1;
  13.     }
  15.     // use the first data block to store target path.
  16.     if (writei(ip, 0, (uint64) target, 0, strlen(target)) < 0) {
  17.         end_op();
  18.         return -1;
  19.     }
  20.     iunlockput(ip);
  22.     end_op();
  23.     return 0;
  24. }
  1. 修改 kernel/sysfile 的 sys_open() 函数.

    该函数使用来打开文件的, 修改 sys_open，使其在遇到符号链接的时候，可以递归跟随符号链接，直到跟随到非符号链接的 inode 为止。

最后考虑这个过程中的加锁释放的规则. 对于原本不考虑符号链接的情况, 在 sys_open() 中, 由 create() 或 namei() 获取了当前文件的 inode 后实际上就持有了该 inode 的锁, 直到函数结束才会通过 iunlock() 释放(当执行成功时未使用 iput() 释放 inode 的 ref 引用, 笔者认为后续到 sys_close() 调用执行前该 inode 一直会处于活跃状态用于对该文件的操作, 因此不能减少引用). 而对于符号链接, 由于最终打开的是链接的目标文件, 因此一定会释放当前 inode 的锁转而获取目标 inode 的锁. 而在处理符号链接时需要对 ip->type 字段进行读取, 自然此时也不能释放 inode 的锁, 因此在进入 follow_symlink() 时一直保持着 inode 的锁的持有, 当使用 readi() 读取了符号链接中记录的目标文件路径后, 此时便不再需要当前符号链接的 inode, 便使用 iunlockput() 释放锁和 inode. 当在对目标文件的类型判断是否不为符号链接时, 此时再对其进行加锁. 这样该函数正确返回时也会持有目标文件 inode 的锁, 达到了函数调用前后的一致

  1. uint64
  2. sys_open(void) {
  3.     char path[MAXPATH];
  4.     int fd, omode;
  5.     struct file *f;
  6.     struct inode *ip;
  7.     int n;
  9.     if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
  10.         return -1;
  12.     begin_op();
  14.     if(omode & O_CREATE){
  15.         ip = create(path, T_FILE, 0, 0);
  16.         if(ip == 0){
  17.             end_op();
  18.             return -1;
  19.         }
  20.     } else {
  21.         int symlink_depth = 0;
  22.         while(1) { // recursively follow symlinks
  23.             if((ip = namei(path)) == 0){
  24.                 end_op();
  25.                 return -1;
  26.             }
  27.             ilock(ip);
  28.             if(ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) {
  29.                 if(++symlink_depth > 10) {
  30.                     // too many layer of symlinks, might be a loop
  31.                     iunlockput(ip);
  32.                     end_op();
  33.                     return -1;
  34.                 }
  35.                 if(readi(ip, 0, (uint64)path, 0, MAXPATH) < 0) {
  36.                     iunlockput(ip);
  37.                     end_op();
  38.                     return -1;
  39.                 }
  40.                 iunlockput(ip);
  41.             } else {
  42.                 break;
  43.             }
  44.         }
  45.         if(ip->type == T_DIR && omode != O_RDONLY){
  46.             iunlockput(ip);
  47.             end_op();
  48.             return -1;
  49.         }
  50.     }
  54.     if (ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)) {
  55.         iunlockput(ip);
  56.         end_op();
  57.         return -1;
  58.     }
  60.     if ((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0) {
  61.         if (f)
  62.             fileclose(f);
  63.         iunlockput(ip);
  64.         end_op();
  65.         return -1;
  66.     }
  68.     if (ip->type == T_DEVICE) {
  69.         f->type = FD_DEVICE;
  70.         f->major = ip->major;
  71.     } else {
  72.         f->type = FD_INODE;
  73.         f->off = 0;
  74.     }
  75.     f->ip = ip;
  76.     f->readable = !(omode & O_WRONLY);
  77.     f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
  79.     if ((omode & O_TRUNC) && ip->type == T_FILE) {
  80.         itrunc(ip);
  81.     }
  83.     iunlock(ip);
  84.     end_op();
  86.     return fd;
  87. }

自述

首先基本理解， 一个文件，我们可以把它理解成有一个inode结构体去指定它，这个里面包含了该文件的权限，创建者啊，文件实际地址等信息，主要的是还包含这文件的盘块信息，盘块是什么呢？磁盘最小单位是扇区0.5KB，一个盘块一般是8个扇区，也就是4KB。在这个inode中，有该文件所对应的多个盘块，当盘块一多了之后，就采用了索引的方式，有一级索引，二级索引，而我们要扩大文件大小，就可以再创建第三级索引。一级索引是NDIRECT个，二级索引是NDIRECT* NDIRECT，三级索引我们就是NDIRECT的3次方。 符号链接就是能访问符号对应的真实inode，但是还要去考虑陷入循环的问题，所以我们要设计最多达到几层。