MIT 6s081 lab9:file system

Lab9: file system

作业地址：Lab: file system (mit.edu)

文件系统的实验，需要对提前阅读fs.c\bio.c\sysfile.c以及相关头文件

Large files (moderate)

本实验为xv6的文件系统添加大文件支持

原本的xv6文件系统的每个inode结构体，采用混合索引的方式记录数据所在的盘块号，如下图。

对于文件的前12KB数据，可以通过直接访问inode得到盘块号（每个盘块1024字节），address1~12，对于大于12个盘块的文件，会分配一个一级索引表（一个盘块，1024KB大小，用于存储这部分数据的所在盘块号。），一个一级索引表可以包含BSIZE/4 = 256个盘块号，加上直接索引的12个盘块号， 总共是268个盘块。也就是说一个文件最多268KB。

本实验实现系统的大文件，减少一个直接索引的盘块，改成二级索引表（占一个盘块，可以包含256个一级索引表，每个一级索引表又包含256个盘块号，也就是最大的文件大小变为11+256+256*256）个块，也就是65803KB。

跟前面的页表有点像

1、修改NDIRECT和MAXFILE，修改dinode和inode结构体addrs数组长度

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

// On-disk inode structure
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
};

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

2、修改bmap，使其能够识别二级索引，当查出一级块号后，需将一级块的数据读入，再次查询

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;
  // printf("bn = %d\n", bn);
  if(bn < NDIRECT){ // NDIRECT
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;
  // printf("bn = %d, NINDIRECT = %d\n", bn + NDIRECT, NINDIRECT); // 256
  if(bn < NINDIRECT) { // 第一级可以直接搞定
  
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0){
      // printf("here1\n");
      ip->addrs[NDIRECT] = addr = balloc(ip->dev); //申请一个block for indirect block
    }
      
    bp = bread(ip->dev, addr); // 从磁盘中读取数据到block中,addr是indirect的地址
    a = (uint*)bp->data; // buf中的数据头，也就是说a里面有256项
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  else{
    bn -= NINDIRECT;
    // printf("%d\n", bn);
    if(bn < NINDIRECT * NINDIRECT) {
      // printf("bn=%d\n",bn+ NDIRECT - 1+NINDIRECT);
      if((addr = ip->addrs[NDIRECT + 1]) == 0) {
        ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev); // 申请一个block for double-indirect block
        // printf("here2:addr = %d\n", addr);
      }

      int i = bn / NINDIRECT, j = bn % NINDIRECT;
      bp = bread(ip->dev, addr);
      a = (uint*)bp->data; // 此时a中存放的是二级块的地址

      if((addr = a[i]) == 0) // 如果此时一级块指向的block地址为空，则 
      {
        a[i] = addr = balloc(ip->dev); // 再申请一个block

        log_write(bp);
      } 
      brelse(bp); // 及时释放
      struct buf *bp_double = bread(ip->dev, addr); // 再次查询！
      a = (uint*)bp_double->data; // 再次查询！
      if((addr = a[j]) == 0) {
        a[j] = addr = balloc(ip->dev);
        log_write(bp_double);
      }
      brelse(bp_double);
      // printf("%p\n", addr);
      return addr;
      
    }
  }

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

3、修改itrunc，释放所有的块，包括直接、一级、二级索引的表

void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  for(i = 0; i < NDIRECT; i++){ // NDIRECT
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

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

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

测试通过

$ bigfile
...
wrote 65803 blocks
bigfile done; ok
$ usertests
usertests starting
test manywrites: OK
test execout: OK
...
test forktest: OK
test bigdir: OK
ALL TESTS PASSED

Symbolic links (moderate)

使用symlink系统调用（和lab1一样的流程创建系统调用），创建符号链接，符号链接和其他文件一样，使用inode块，使用第一个块存储符号链接指向的文件

uint64 sys_symlink(void) //symlink(char *target, char *path) 
{
  char target[MAXPATH], path[MAXPATH];

  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
    return -1;

  // printf("target = %s, path = %s\n", target, path);
  // 创建软连接 path -> target
  // 不需要判断 target是否存在

  struct inode* ip;
  begin_op();
  ip = create(path, T_SYMLINK, 0, 0);
  if(ip == 0){
    end_op();
    return -1;
  }
  if(writei(ip, 0, (uint64)target, 0, strlen(target)) < 0){ //写入target
    end_op();
    return -1;
  }
  iunlockput(ip);

  end_op();

  return 0;
}

在fcntl.h中补齐O_NOFOLLOW的定义

#define O_RDONLY   0x000
#define O_WRONLY   0x001
#define O_RDWR     0x002
#define O_CREATE   0x200
#define O_TRUNC    0x400
#define O_NOFOLLOW 0x800

修改sys_open函数，使其在遇到符号链接，并且没有O_NOFOLLOW标志时，递归地寻找直到非符号链接的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 { 
  	// add begin
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ilock(ip);
    if(ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) { // 如果是符号链接并且没有不跟随标志
      int max_depth = 10; // 定义最大递归深度
      char target[MAXPATH];
      int found = 0;
      for(int i = 0; i < max_depth; i++) {
        if(readi(ip, 0, (uint64)target, 0, MAXPATH) < 0) {
          iunlockput(ip);
          end_op();
          return -1;
        }
        iunlockput(ip);
        ip = namei(target);
        if(ip == 0) break;
        if(ip->type == T_SYMLINK) ilock(ip);
        else{
          found = 1;
          ilock(ip);
          break;
        }
      }
      if(!found){
        end_op();
        return -1;
      }
    }
    // add end
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  ...
}

测试：

$ symlinktest
Start: test symlinks
test symlinks: ok
Start: test concurrent symlinks
test concurrent symlinks: ok
$ usertests
usertests starting
test manywrites: OK
test execout: OK
test copyin: OK
test copyout: OK
...
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED