Giovanna

Appearance

file system

Giovanna

About 2420 wordsAbout 8 min

2024-08-21

Lab: file system (mit.edu)

开启新实验

git fetch
git checkout fs
make clean

Large files

任务描述

在 xv6 的底层实现中，文件是由 struct dinode 来描述的，如下：

tmp746D.png

这里主要关注结构体中的 addrs 属性。其中有 addrs 的前十二个直接指向文件储存的块，最后一个是间接的块包含 256 个数据块地址，如下图所示：

本任务目的是增加 xv6 文件的最大大小，根据任务描述需要修改 bmap() 使得 ip->addrs[] 的前 11 个元素为直接块，第 12 个是一个单间接块（就像现在的一样），而第 13 个应该是新的双重间接块。大致结构如下图所示：

image.png

对比两种方法，已知一个 struct dinode 有 64B 的大小，一个磁盘块能储存 1KB 的数据。

那么原本的方案可以文件的最大大小为 12KB+256KB=268KB12KB+256KB=268KB；而改进后的方法，仅考虑这个二级间接块指针，它包含 256 个单间接块指针，每个地址最多可以包含 256 个数据块地址，所以总数就是 256×256=65536256\times 256 = 65536 个块，即 64MB。

可以看出，这样的提升的非常大的。

实现过程

  1. 因为加入了二级间接索引，所以要先对一些宏定义进行修改，直接块变为11个，最大文件大小也要进行更改。

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

  2. 修改 struct dinode ，addrs 的数量应该是 NDIRECT+2 ，直接块加上一个单间接块和一个双间接块。

    // kernel/fs.h
// 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
};

  3. 修改 struct inode。 dinode 是实际储存在磁盘上的，而 inode 在 dinode 的基础上加入了很多方便处理 inode 的元数据。修改同上。

    // kernel/file.h
// in-memory copy of an inode
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];
};

  4. 修改 bmap() ，这个函数接收 inode 指针和文件逻辑块号 bn，用于将文件逻辑块号（bn）映射到存储设备上的物理块号（addr）。我们需要在这个函数中添加对二级间接块的支持，模仿原代码进行修改。

    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);       // 分配物理块，并将地址保存在addrs[bn]中
    return addr;                                    // 返回物理块地址
  }
  
  bn -= NDIRECT;                                    // 一级间接块中的偏移

  if(bn < NINDIRECT){                               // 属于一级间接块
    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 < NDINDIRECT){                              // 属于二级间接块
    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 idx = bn / NINDIRECT;                      // 计算索引
    if((addr = a[idx]) == 0){                       // 对应索引物理块未分配
        a[idx] = addr = balloc(ip->dev);            // 分配物理块地址并更新表项
        log_write(bp);                              // 写回磁盘
    }
    brelse(bp);                                     // 释放缓存区

    bp = bread(ip->dev, addr);                      // 读取物理块
    a = (uint*)bp->data;                            // 获取间接块表
    idx = bn % NINDIRECT;                           // 计算索引
    if((addr = a[idx]) == 0){                       // 对应索引物理块未分配
      a[idx] = addr = balloc(ip->dev);              // 分配物理块地址并更新表项
      log_write(bp);                                // 写回磁盘
    }
    brelse(bp);                                     // 释放缓存区
    return addr;                                    // 返回物理块地址
  }
  panic("bmap: out of range");
}

  5. 还需要修改 itrunc() ，确保释放文件的所有块，包括双重间接块。很多地方可以参考一级间接索引的实现。

    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;                            // 地址重置为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;                        // 地址重置为0
  }

  if(ip->addrs[NDIRECT+1]){                        // 使用了二级间接块
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for (i = 0; i < NINDIRECT; i++){               // 遍历二级间接块中的一级块
      if(a[i]){                                    // 该块不空
        struct buf* bp2 = bread(ip->dev, a[i]);
        uint *a2 = (uint*)bp2->data;
        for(j = 0; j < NINDIRECT; j++){            // 遍历一级间接块中的直接块
          if(a2[j])                                // 该块不空
            bfree(ip->dev, a2[j]);                 // 释放对应磁盘块
        }

        brelse(bp2);
        bfree(ip->dev, a[i]);                      // 释放一级间接块
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT + 1]);        // 释放二级间接块
    ip->addrs[NDIRECT + 1] = 0;                    // 地址重置为0
  }
  ip->size = 0;
  iupdate(ip);
}

任务描述

向 xv6 添加符号链接。符号链接（或软链接）通过路径名引用链接的文件；当打开符号链接时，内核会跟随链接到引用的文件。

需要实现 symlink(char *target, char *path) 系统调用，该调用会在 path 处创建一个新的符号链接，该链接引用由 target 命名的文件。还需要将 symlinktest 添加到 Makefile 。

软链接的本质其实是一个文件（即 inode），我们要在 inode 中储存此链接指向的文件的路径。为了实现链接的效果，在 open() 函数中，需要去根据链接中储存的路径，递归的找到最终指向的文件（可能会有一个软链接指向另一个软链接）。

实现过程

  1. user/symlinktest.c 已经实现，将其添加到 Makefile

  2. 重复一下添加系统调用的一系列操作

    在 user/user.h 中添加声明 int symlink(char*, char*);

    在 user/usys.pl 添加 entry("symlink");

    在 kernel/syscall.h 中添加定义 #define SYS_symlink 22

    修改 kernel/syscall.c，用 extern 全局声明新的内核调用函数，并且在 syscalls 映射表中，加入从前面定义的编号到系统调用函数指针的映射

    extern uint64 sys_symlink(void);

static uint64 (*syscalls[])(void) = {
...
[SYS_symlink]   sys_symlink,
}

    接下来就是在 kernel/sysfile.c 里完成函数 sys_symlink()

  3. 向 kernel/stat.h 添加新的文件类型 T_SYMLINK 以表示符号链接。

    #define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device
#define T_SYMLINK 4   // Symlink

  4. 在 kernel/fcntl.h 中添加一个新标志 O_NOFOLLOW。

    传给 open() 的标志位用于指定打开文件描述符的一些设置。我们添加 O_NOFOLLOW 的标志位，意味不去递归打开软连接里的路径，而打开软连接本身。    注意：标志是使用按位 OR 运算符组合的，因此新标志不应与任何现有标志重叠。

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

  5. 实现 symlink(target, path) 系统调用，在引用 target 的 path 处创建一个新的符号链接。请注意，target 不需要存在，系统调用即可成功。需要在 inode 的数据块中存储符号链接的目标路径。

    uint64 sys_symlink(void)
{
  char target[MAXPATH], path[MAXPATH];
  if(argstr(0, target, MAXPATH) < 0)
    return -1;
  if(argstr(1, path, MAXPATH) < 0)
    return -1;
    
  struct inode *ip;
  begin_op();
  if((ip = create(path, T_SYMLINK, 0, 0))== 0){
    end_op();
    return 0;
  }
  if(writei(ip, 0, (uint64)target, 0, strlen(target)) < 0){
    end_op();
    return -1;
  }
  iunlockput(ip);
  end_op();
  return 0;
}

  6. 修改 open 系统调用以处理 path 引用符号链接的情况。如果文件不存在，则 open 失败。当进程在要打开的标志中指定要 O_NOFOLLOW 时，open 应打开符号链接（而不是遵循符号链接）。

    当模式不是O_NOFOLLOW的时候就对符号链接进行循环处理，直到找到真正的文件，如果循环超过了一定的次数（10），就说明可能发生了循环链接，就返回-1。

    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;
    }
  }
  
  if(!(omode & O_NOFOLLOW)){
    int cnt = 0;
    struct inode* next_file;

    while(cnt++ < 10 && ip->type == T_SYMLINK){
      if(readi(ip, 0, (uint64)path, 0, MAXPATH) == 0){
        iunlockput(ip);
        end_op();
        return -1;
      }

      if((next_file = namei(path)) == 0){
        iunlockput(ip);
        end_op();
        return -1;
      }

      iunlockput(ip);
      ip = next_file;
      ilock(ip);                   // 为什么在这里上锁？
    }
    if(cnt >= 10){
      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;
}

The End

tmp9676.png

感觉 usertests 能不能过有点玄学。