操作系统MIT 6.S081 xv6内核（十）：File System实验

前置提醒

fs分支的文件系统布局和常规xv6布局是不一样的，常规情况下，文件系统的磁盘布局是：46个元数据块（boot、super、30 log、13 inode 、1 bitmap）、954个数据块；fs分支下：70个元数据块（boot、super、30 log、13 inode 、25 bitmap）、199930个数据块；因为它需要支持二级Inode索引，知晓这点再去看代码（指系统代码，不是实验代码）才会理解。

Large files实验

实验目的

看过Inode层理论或者我的基础理论一文，就知道xv6文件大小的限制是每个Inode只能存放256+12个块大小，因此这里需要我们牺牲一个Direct Number，用于创建二级Indirect Number，这种提升是明显的，因为每个Indirect Number指向256个，二级的Indirect Inode存储的块是11+256+256*256；

具体实现

这个实现比较简单，只要看一下kernel/fs.c哪些代码涉及间接Indirect inode设计即可，即bmap函数和itrunc函数，前者负责将块映射到十三个Inode Number，后者负责逐级释放这些Inode Number；

修改Inode Number设计，十三个inode Number，前11个用作Direct Number，第十二个用作一级InDirect Number，第十三个用作二级Indirect Number,修改头文件kernel/fs.h

#define NDIRECT 11  //11个Direct Number
#define N2INDIRECT ((BSIZE/sizeof(uint))*(BSIZE/sizeof(uint))) //2级Indirect Inode，可以存放256×256个块
#define MAXFILE (NDIRECT + NINDIRECT + N2INDIRECT)  //所有Inode Number能容纳的字节数

uint addrs[NDIRECT+1+1];   //dinode 仍是13

kernel/file.h：inode和dinode同步：

1	uint addrs[NDIRECT+1+1]; //inode 仍是13

修改bmap函数：将Inode映射到Inode Number=bn的数据块上，返回的是Inode->dev的数据块号；注意，对于这个fs分支，文件系统布局是扩展了，包括199930个数据块，这个数据块数量大于我们索引分配的数据块号（65803个），足以支撑这个实验；

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;  
  struct buf *bp;
  if(bn < NDIRECT){  //Direct Inode的处理
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;  //减去直接处理的序号

  
  if(bn < NINDIRECT){  //一级Direct Inode的处理
    // 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;
  }
  //新增二级Inode处理，逻辑和一级差不多
  bn -= NINDIRECT;   //减去一级的256个序号

  struct buf*b2p;
  uint* a2;
  if(bn<N2INDIRECT){  //二级处理
    uint bn1 = bn/NINDIRECT;   //在1级Inode的编号
    uint bn2 = bn%NINDIRECT;  //在2级Inode的编号
    if((addr = ip->addrs[NDIRECT+1]) == 0)  //第13个Indirect Number没有分配块
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev); 
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr=a[bn1])==0){   //对应一级Inode不存在应该为其分配块
      a[bn1] = addr = balloc(ip->dev);
      log_write(bp);
    }
    b2p=bread(ip->dev,a[bn1]); //读取一级块指向的二级块
    a2=(uint*)b2p->data;
    if((addr=a2[bn2])==0){
      a2[bn2] = addr =balloc(ip->dev);  //分配二级块
      log_write(b2p);
    }
    brelse(bp);
    brelse(b2p);
    return addr;
  }
  panic("bmap: out of range"); //超过65803部分，就无法通过Inode索引了，需要采用三级Inode等；
}

修改itrunc函数：读取第12个Inode Nmber，如果被使用了说明有块映射到二级Inode了，bread得到一级Inode的块起始地址，然后通过随机访问的特性就可以遍历不为0的一级Inode，bread一下就可以得到二级Inode所在的块，找到不为0的项将其释放，然后回溯回来继续释放即可；

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

  //新增二级Indirect inode释放函数
  struct buf* b2p;
  uint* a2;
  if(ip->addrs[NDIRECT+1]){  //二级Indirect inode被使用了
    bp=bread(ip->dev,ip->addrs[NDIRECT+1]); //读取其指向的一级inode的起始位置
    a=(uint*)bp->data;
    for(int i =0;i<NINDIRECT;i++){   
      if(a[i]){  //某个一级inode存在二级inode
        b2p=bread(ip->dev,a[i]);               
        a2=(uint*)b2p->data;
        for(int j=0;j<NINDIRECT;j++){ //逐级释放二级inode
          if(a2[j])
            bfree(ip->dev,a2[j]);
        }
        brelse(b2p);
        bfree(ip->dev,a[i]); //然后释放这个一级inode
      }
    }
    brelse(bp);
    bfree(ip->dev,ip->addrs[NDIRECT+1]);  //释放这个序号12的二级Indirect inode
    ip->addrs[NDIRECT+1]=0;
  }
  ip->size = 0; 
  iupdate(ip);
}

至此，整个实验就做完了，验证：

1
2
3

make clean&&make qemu
bigfile
usertests

完整Commit参考：Large files Done

Q&A

嘿，实验简单，但是问题全出在这个实验，我做完这个实验只测试了bigfile没测试usertests去做第二个，发现存在问题还得回溯回来，主要问题有：

bigfile测试bigfile: file is too small

说明没有正确配置二级Inode Number，系统不支持65803个块，而是267个块（256+11）；我的错误比较粗心，没有更新MAXFILE。。。

bigfile测试出现bigfile: read the wrong data (%d) for block %d\n

这个我也找了蛮久，居然是一个括号逻辑错了，我在bmap函数中模仿一级分配写法if((addr = ip->addrs[NDIRECT]+1) == 0)，写成了if((addr = ip->addrs[NDIRECT+1] == 0))，这里会先判断再赋值，逻辑就完全不对了，告诉我们有时候对着抄不如直接ctrl+c;

usertests测试出现freeing free blocks

这个大概率是因为itrunc的逻辑不对，我犯的错误也比较狗血，例如在j循环用了i......；

Symbolic links实验

实验目的

在xv6中实现一个“软链接”功能，这里的软链接就是我们理解的软链接，特殊就特殊在，这个实验不要求我们实现目录的软链接；软链接的原理就是在某个路径下创建一个符号链接文件（假设这个文件是linkpath），新建一个inode，在这个inode存储目标文件target的路径；

其次，软链接是可能成回环的，例如访问linkpath符号链接，它指向的是一个a符号链接，a符号链接指向的是linkpath，这样点击访问linkpath就是访问a，a又跳回linkpath，这样我们永远无法跳出循环，系统在这两个文件反复横跳，导致一点击就无法控制，因此需要设置访问深度，单次访问不要出现无限的循环；

再者，该实验定义了一种O_NOFOLLOW的open方式，当出现这种方式open文件时，不要跟随符号链接（我不是很明白它的具体目的是什么，不跟随说明直接以文件方式打开即可），也即我们在处理open函数时还需要排除带有这个标记的文件处理；

具体实现

Makefile加入$U/_symlinktest\，and run your system，这个步骤完全就是系统调用的步骤了，主要是定义用户接口、系统调用入口（寄存器a7的赋值），系统调用号、系统调用函数与系统调用号的映射、系统调用函数的空实现；具体参考我的commit或者之前系统调用的lab步骤，不赘述；

完成系统调用搭建，发现此时make是会报错的，因为symlinktest使用了我们没有定义的字段，需要我们添加定义：

//kernel/stat.h
#define T_SYMLINK 4  #标志文件类型，符号链接文件

//kernel/fcntl.h
#define O_NOFOLLOW 0x010 #标志O_NOFOLLOW的open方式，0x010是自定义的，只要转换成二进制不和其他几种方式冲突即可
//已经使用的有：
#if 0
    #define O_RDWR    0x002
    #define O_CREATE  0x200
    #define O_TRUNC   0x400
#endif

此时就可以通过系统编译了，剩下的任务就是将系统调用函数的空实现给实现完；这里也没什么函数可以参考的，我们要做的是分配一个新inode，将符号链接文件linkpath关联到这个inode，然后addr数据写入target的路径即可，xv6最长路径名是MAXPATH=128字节，addr现在支持65803×1024字节，也不用担心越界问题；

系统调用函数的实现：在写这个lab我还没看到create函数，还想着用ialloc分配新块，如何将新块关联到文件困扰了我一会，后面发现create函数已经写好了，create函数在路径path下创建一个文件类型为type的文件，返回这个文件的Inode，然后我们将路径名写入inode的数据即可，因此kernel/sysfile.c：

uint64 sys_symlink(void){ //int symlink(const char *target, const char *linkpath);
  char target[MAXPATH],linkpath[MAXPATH];
  if(argstr(0,target,MAXPATH)<0) //参数target
    return -1;
  if(argstr(1,linkpath,MAXPATH)<0) //参数linkpath
    return -1;

  struct inode *new_ip;
  begin_op();  
  new_ip=create(linkpath,T_SYMLINK,0,0); //返回符号链接Inode,在linkpath创建（create有nameiparent机制，确保从末级目录创建，因此我们不用在这里对linkpath是目录还是文件检查），0，0是主从设备，针对设备文件的
  if(new_ip==0){
    end_op();
    return -1;
  }
  if(writei(new_ip,0,(uint64)target,0,MAXPATH)!=MAXPATH){  //将字符target写入Inode，第一个0是数据来自内核，第二个内核是数据偏移位置0，因为此时的Inode是新的
    iunlockput(new_ip);  //commit忘掉加了，在这里加一下好一点
      end_op();
    return -1;
  }
  iunlockput(new_ip);  //这个进程不再使用，ref--
  end_op();
  return 0;
}

我们会在open定义打开符号链接的方式，open是sys_open的用户接口，因此需要修改sys_open，具体逻辑上，我们在Inode存储了一个路径，这时候我们就需要通过这个这个路径，找到这个文件的Inode，这个功能也已经在kernel/fs.c的namex函数实现了，不懂的可以参考我的基础理论namex和namei函数解析，这个Inode的数据存储在磁盘，因此我们需要通过ilock函数(inode加锁，并从bcache的dinode读取数据，可以理解成从磁盘读取)获取它的数据，此时就完成了数据的访问，实际上就打开了符号链接对应的target文件，如果这个文件是符号文件，就继续深入（定义不超过10层），直到文件不是符号文件，就跳出，此外不要忘记处理不跟随标志O_NOFOLLOW，在kernel/sysfile.c的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);
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
    //新增T_SYMLINK处理部分
    if(ip->type==T_SYMLINK&&((omode&O_NOFOLLOW)==0)){ //T_SYMLINK且没有O_NOFOLLOW才跟随链接
      int depth=10;  //循环深度
      while(depth&&ip->type==T_SYMLINK){ //下一个也是符号文件才需要循环打开，否则直接跳出这个处理即可（注意在跳出之前，我们已经通过ilock打开了这个普通文件）
        if(readi(ip,0,(uint64)path,0,MAXPATH)!=MAXPATH){  //从符号链接Inode读入target路径path
          iunlockput(ip);
          end_op();
          return -1;
        }
        iunlockput(ip);  
        ip=namei(path);  //此时的ip变成是target的Inode
        if(ip==0){
          end_op();
          return -1;
        }
        ilock(ip); //读入target的Inode，如果target的Inode还是符号文件，则会继续循环，如果是普通文件，就跳出
          depth--; //层数--
      }	
      if(depth==0){  //递归10次，放弃这次访问
        iunlockput(ip);
          end_op();
        return -1;
      }
    }
  }
//.......设备文件等代码忽略
}

验证：

1 2	symlinktest usertests

完整Commit参考：Symbolic links Done

总结

这个lab实验设计得并不很困难，实验的代码量也不多，关键是理解文件系统的逻辑；xv6简化了文件系统的很多细节，很多地方的处理都采用了最简单的逻辑，例如随机的顺序查找遍历等，也有挺多别出心裁的设计，例如让我羞愧难当的balloc、bfree函数，前一秒觉得它“逻辑混乱”，后面发现“理所应当”，这也告诉我们如果是一个复杂的文件系统，需要考虑的地方更加多，它的内容不会比内存管理少，毕竟文件系统在教材也是独占一章。