Lab File

前置知识

一、关于inode的结构

在xv6中，每一个文件(包括文件夹)对应一个inode。一个inode包含13个地址条目。前十二的地址直接指向了十二个数据块，第十三个地址指向了一个间接块，这个间接块储存了256个数据块的地址，每个地址对应一个数据块。

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+1];
};

二、阅读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;
  }

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

bmap寻找inode ip中第bn个磁盘块地址并返回，如果不存在，它就分配一个。它首先判断bn是不是属于直接条目，如果属于那么直接读取并返回。如果不属于，它会判断是否属于间接条目，属于的话便读取间接条目。因为间接条目中有顺序排列的256个地址，但bn的计数是从第一个直接块开始的，所以读取前要减去12。最后返回读取的块的地址。注意，当分配新块时，需要更新磁盘中块的数据，因此需要写入log。

三、注意

这个lab的第一个task的测试跑得非常慢，特别是对于我这种vm用户，跑20分钟也很常见，但make grade时限只有3分钟，所以请有所准备。同时，你对最大文件宏定义的修改会使usertests中的writebig耗时指数级增加，我可怜的虚拟机甚至要跑接近一个小时，因此在单独通过原始usertests的前提下，修改其参数后通过make grade是可以接受的。

Task: Large files

这个task要求我们更改inode与bmap来实现大文件写入与释放。根据提示，需要把12个直接条目减少到11个，空出一个给doubly indirect条目。这个条目指向了储存有256个间接条目的地址，而每个间接条目又指向了一个储存有256个数据块地址的块。这样把inode扩展成两层，当我们查找的时候也需要进行两层查找。

首先，修改一下宏定义与inode数组大小。(cache里也要修改)

// fs.h
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NININDIRECT (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NININDIRECT)

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];   // Data block addresses // 这里+2
};

// file.h
  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]; // 这里+2
};

修改bmap，当bn的值超过了一层间接块时，我们需要在二层间接块中查找。查找过程中，每到一层，先查看这个块是否存在，不存在就创建，然后读取data，通过加偏移量得到下一层的地址。注意，除了起始层以外，所有的层在创建后都需要写入log，因为这是对硬盘的直接修改。(这里突然发现一个问题，book中说任何对inode缓存的修改都需要立刻iupdate到硬盘，但是我发现对所有非addr的修改都是这样，但对addr的修改一个也没有iupdate，这是为什么呢？)

// bmap
  bn -= NINDIRECT;
  if (bn < NININDIRECT) {
    if ((addr = ip->addrs[NDIRECT + 1]) == 0) // 起始层分配
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    inbp = bread(ip->dev, addr);
    a = (uint*)inbp->data; // 转入第一层

    if ((addr = a[bn / NINDIRECT]) == 0){ // 第一层分配
      a[bn / NINDIRECT] = addr = balloc(ip->dev);
      log_write(inbp);
    }
    brelse(inbp);

    ininbp = bread(ip->dev, addr);
    a = (uint*)ininbp->data; // 转入第二层
    if((addr = a[bn % NINDIRECT]) == 0) { // 第二层分配
      a[bn % NINDIRECT] = addr = balloc(ip->dev);
      log_write(ininbp);
    }
    brelse(ininbp);
    return addr;
  }

  panic("bmap: out of range");

修改itrunc。在双层间接块中，需要先循环到第二层，全部释放后再释放存储第二层地址的第一层。依次类推，最后标记inode大小为0并iupdate。

if (ip->addrs[NDIRECT + 1]) {
  inbp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
  a = (uint*)inbp->data;
  for (int i = 0; i < NINDIRECT; i++) {
    if (a[i]){
      ininbp = bread(ip->dev, a[i]);
      b = (uint*)ininbp->data;
      for (int j = 0; j < NINDIRECT; j++) {
        if(b[j])
          bfree(ip->dev, b[j]);
      }
      brelse(ininbp);
      bfree(ip->dev, a[i]);
    }
  }
  brelse(inbp);
  bfree(ip->dev, ip->addrs[NDIRECT + 1]);
  ip->addrs[NDIRECT + 1] = 0;
}

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

Task: Symbolic links

这个task要求我们实现软链接。可以通过模仿硬链接的部分结构来实现。

首先，根据提示加入新的file type和O_NOFOLLOW 位。(我在设置flag的时候甚至一开始写了个0x003，后来test卡了才发现这是个二进制位)
1
2
3
4
5
// stat.h
#define T_SYMLINK 4 // symlink

// fcntl.h
#define O_NOFOLLOW 0x004

添加syscall symlink。(记得修改syscall.c, syscall.h, user.h, usys.pl)先为一个新的symlink inode创建一个名字(create不会像dir inode, 普通inode那样对symlink inode做额外操作)，然后写入目标路径。注意锁的释放和原子性。


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 = namei(path)) != 0) {
    end_op();
    return -1;
  }

  if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }

  if (writei(ip, 0, (uint64)target, 0, MAXPATH) < 0) {
    iunlockput(ip); // 因为writei写入需要持有锁，因此不管是否成功都需要释放锁
    end_op(); // 详情可见file.c中的filewrite
    return -1;
  }

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

修改open函数。在open中，如果omode的nofollow位没有被设置，我们就可以递归来跟随它的路径。每一层递归中，我们都需要读入当前层的target路径，如果存在的话就再次循环。根据提示，当循环次数大于10的时候就可以认为进入了一个软链接死循环，那么就可以直接报错跳出。

if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
  int depth = 0;
  while(ip->type == T_SYMLINK)
  {
    if (readi(ip, 0, (uint64)sympath, 0, MAXPATH) < 0) {
      iunlockput(ip);
      end_op();
      return -1;
    }
    iunlockput(ip);
    if ((ip = namei(sympath)) == 0) {
      end_op();
      return -1;
    }
    ilock(ip);
    depth ++;
    if (depth > 10) {
      iunlockput(ip);
      end_op();
      return -1;
    }
  }
}