中文题目翻译

Large files(moderate)

实现二级间接块

题目理解

原始文件的data block分布

  • 12个直接块
  • 1个一级间接块–>指向256个数据块

image-20250625190532206

目标的data block分布

  • 11个直接块
  • 1个一级间接块–>指向256个数据块
  • 1个二级间接块–>指向 256*256 个数据块

image-20250625190549223

lab实现的原理很简单——添加二级间接块

代码实现

修改关于数据块数目宏定义

1
2
3
4
#define NDIRECT 11 // 直接块数目
#define NINDIRECT (BSIZE / sizeof(uint)) // 一级间接块数目
#define NDINDIRECT (NINDIRECT * NINDIRECT) // 二级间接块数目
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT) // 最大块数

修改disk inode

1
2
3
4
5
6
7
8
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 11个直接块和一个一级间接块、一个二级间接块
};

修改inode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number inode编号
  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; // link计数
  uint size;
  uint addrs[NDIRECT + 2]; // 此处改为+2
};

修改bmap：将逻辑块号映射到磁盘的物理块地址

  • 原始bmap理解
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    // 将逻辑块号映射到磁盘的物理块地址
    // ip: 文件inode
    // bn: 该文件的指定数据块号
    static uint
    bmap(struct inode *ip, uint bn)
    {
      uint addr, *a;
      struct buf *bp;

      if(bn < NDIRECT){ // 当bn指向直接块
        if((addr = ip->addrs[bn]) == 0) // 检查bn指定的块是否已经分配
          ip->addrs[bn] = addr = balloc(ip->dev); // 没有分配则在文件对象所在设备分配一个块
        return addr; // 返回块地址
      }

      bn -= NDIRECT;
      if(bn < NINDIRECT){ // 当bn指向间接块
        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){ // 检查bn指定的块是否已经分配
          a[bn] = addr = balloc(ip->dev); // 没有分配则在文件对象所在设备分配一个块
          log_write(bp); // 分配块更改了间接块的数据，需要log写回
        }
        brelse(bp); // 释放缓存
        return addr; // 返回块地址
      }
      panic("bmap: out of range");
    }
  • 需要增加的二级间接块
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
     if(bn < NINDIRECT){ // 当bn指向间接块
     // ...
     }

     bn -= NINDIRECT;
     if (bn < NDINDIRECT){
       if((addr = ip->addrs[NDIRECT + 1]) == 0) // 看二级间接块L1是否分配
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    // L1
    bp = bread(ip->dev, addr); // 读取L1间接块
    a = (uint*)bp->data; // 获取L1间接块存放的地址列表
    if ((addr = a[bn / NINDIRECT]) == 0){ // 看二级间接块L2是否分配
      a[bn / NINDIRECT] = addr = balloc(ip->dev); // 没有分配则在文件对象所在设备分配一个块
      log_write(bp); // 分配块更改了间接块的数据，需要log写回
    }
    brelse(bp); // 释放

       // L2
       bp = bread(ip->dev, addr); // 读取L2间接块
       a = (uint*)bp->data; // 获取L2间接块存放的地址列表
       if ((addr = a[bn % NINDIRECT]) == 0){ // 看二级间接块L2指向数据块是否分配
         a[bn % NINDIRECT] = addr = balloc(ip->dev); // 没有分配则在文件对象所在设备分配一个块
         log_write(bp); // 分配块更改了间接块的数据，需要log写回
       }
       brelse(bp); // 释放
       return addr;
     }
     panic("bmap: out of range");
     // ...

修改itrunc

  • 原始itrunc理解
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    // 截断inode对应文件对象
    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; // addrs数组指定位置 置为零
        }
      }

      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); // 释放bp cache
        bfree(ip->dev, ip->addrs[NDIRECT]); // 释放间接块本身
        ip->addrs[NDIRECT] = 0;
      }

      ip->size = 0;
      iupdate(ip); // 同步inode到dinode
    }
  • 需要增加的二级itrunc截断过程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
      if(ip->addrs[NDIRECT]){
        // ...
      }
      struct buf* bp1;
      uint* a1;
      if(ip->addrs[NDIRECT + 1]){ // 是否分配了二级间接块
        bp = bread(ip->dev, ip->addrs[NDIRECT + 1]); // 分配了，则读取二级间接块
        a = (uint*)bp->data; // 读取二级间接块L1记录的地址列表
        for(i = 0; i < NINDIRECT; i++){
          if(a[i]){
            bp1 = bread(ip->dev, a[i]); // 读取二级间接块L2
            a1 = (uint*)bp1->data; // 读取二级间接块L2记录的地址列表
            for(j = 0; j < NINDIRECT; j++){
              if(a1[j]){
                bfree(ip->dev, a1[j]); // 释放L2指向的block
              }
            }
            brelse(bp1);
            bfree(ip->dev, a[i]); // 释放L1指向的block
          }
        }
        brelse(bp); // 释放bp cache
        bfree(ip->dev, ip->addrs[NDIRECT + 1]); // 释放二级间接块本身
        ip->addrs[NDIRECT + 1] = 0;
      }
      ip->size = 0;
      iupdate(ip);
    // ...

Symbolic links(moderate)

实现symlink系统调用

题目理解

实现的函数声明

  • 为target创建一个符号链接
    1
    int symlink(char *target, char *path);

代码实现

通用的需要添加的

  • user/usys.pl

    1
    entry("symlink");

  • user/user.h

    1
    int symlink(char *target, char *path);

  • kernel/sysfile.c

    1
    2
    3
    4
    5
    uint64
    sys_symlink(void) {
        // 待补充
        return 0;
    }

  • kernel/syscall.c

    1
    2
    3
    extern uint64 sys_symlink(void);

    [SYS_symlink] sys_symlink,

  • kernel/syscall.h

    1
    #define SYS_symlink 22

  • kernel/stat.h

    1
    #define T_SYMLINK 4   // Symlink

  • kernel/fcntl.h

    1
    #define O_NOFOLLOW 0x800

  • Makefile

    1
    $U/_symlinktest\

symlink实现

符号链接的内容就是目标路径字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
uint64
sys_symlink(void) {
    struct inode* ip;
    char target[MAXPATH], path[MAXPATH];
    if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) // 获取系统调用的两个参数
        return -1;

    begin_op();

    ip = create(path, T_SYMLINK, 0, 0); // 创建一个新的inode，类型为T_SYMLINK
    if (ip == 0) {
        end_op();
        return -1;
    }

    if (writei(ip, 0, (uint64)target, 0, strlen(target)) < 0) { // 将target路径写入inode
        end_op();
        return -1;
    }

    iunlockput(ip);
    end_op();

    return 0;
}

open修改

原始sys_open

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

  argint(1, &omode); // 获取omode
  if((n = argstr(0, path, MAXPATH)) < 0) // 获取path
    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){ // 查找path对应的inode
      end_op();
      return -1;
    }
    ilock(ip);
    if(ip->type == T_DIR && omode != O_RDONLY){
      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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// ...
  if(omode & O_CREATE){
    // ...
  } else {
    int symlink_depth = 0; // 记录软链接引用深度
    while (1) {
        if ((ip = namei(path)) == 0) {    // 解析路径，获取对应的inode
            end_op();
            return -1;
        }

        ilock(ip);
        if (ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) { // 如果当前指向的仍是软链接，则继续循环
            if (++symlink_depth > 10) { // 链接深度超过10层就退出
                iunlockput(ip);
                end_op();
                return -1;
            }
            if (readi(ip, 0, (uint64)path, 0, MAXPATH) < 0) { // 读取链接的目标路径
                iunlockput(ip);
                end_op();
                return -1;
            }
            iunlockput(ip);
        }
        else
            break;
    }

    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }
// ...