本文记录了 Lab: file system 的实验过程

Lab: file system

准备工作

阅读 xv6 book 的 “Chapter 8: File system” 和相关代码

1
2
3

git fetch
git checkout fs
make clean

Large files (moderate)

实验任务

在未修改的 xv6 系统中，最多支持 268 个 blocks，即 12 个 “direct” block 和 256 个 “indirect” block。为了支持大文件，我们需要修改 xv6 中管理 blocks 的代码，使得它支持 65803 个 blocks，即 11 个 “direct” block、256 个 “indirect” block 和 256 * 256 个 “doubly-indirect” block。

实验思路

为了支持 doubly-indirect block，我们需要重新规划 inode 的 addrs。设定 addrs[0] ~ addrs[10] 索引 “direct” block，addrs[11] 索引 “indirect” block，addrs[12] 索引 “double-indirect” block
修改相关的头文件：fs.h、file.h
参考 bmap 函数中查找 bn 在 “indirect” block 的情况，在它后面添加 bn 在 “double-indirect” block 的代码
修改 itrunc 函数，使得它可以释放 “double-indirect” block

实验测试

1
2
3

make qemu
bigfile
usertests

Symbolic links (moderate)

实验任务

实现 xv6 的 symbolic link 的系统调用。符号链接就是在文件中保存指向文件的路径名，在打开文件的时候根据保存的路径名再去查找实际文件。

实验思路

按照实验指导的提示，首先定义好 symlink 系统调用
在 kernel/stat.h 中定义符号链接文件的类型 T_SYMLINK；在 kernel/fcntl.h 中定义标志位 O_NOFOLLOW
在 kernel/sysfile.c 中实现 symlink 系统调用，该函数会取出两个参数，char target[MAXPATH], path[MAXPATH]；然后创建 inode，将 target 写入 inode 的数据区
修改 open 系统调用，处理路径引用符号链接这种情况。由于一个符号链接可能引用另一个符号链接，因此我们需要循环判断，直到文件的类型不是 T_SYMLINK；另外因为可能出现死循环，所以假定当循环次数超过 10 次时，我们也退出循环，返回错误标志。

实验测试

1
2
3

make qemu
symlinktest
usertests

Lab 评测

1	make grade

Diff

diff --git a/Makefile b/Makefile
index d8509b1..7c258af 100644
--- a/Makefile
+++ b/Makefile
@@ -175,6 +175,7 @@ UPROGS=\
 	$U/_grind\
 	$U/_wc\
 	$U/_zombie\
+	$U/_symlinktest\
 
 
 
diff --git a/kernel/fcntl.h b/kernel/fcntl.h
index 44861b9..e5e38e3 100644
--- a/kernel/fcntl.h
+++ b/kernel/fcntl.h
@@ -3,3 +3,4 @@
 #define O_RDWR    0x002
 #define O_CREATE  0x200
 #define O_TRUNC   0x400
+#define O_NOFOLLOW 0x800
diff --git a/kernel/file.h b/kernel/file.h
index b076d1d..5c4eb3a 100644
--- a/kernel/file.h
+++ b/kernel/file.h
@@ -26,7 +26,7 @@ struct inode {
   short minor;
   short nlink;
   uint size;
-  uint addrs[NDIRECT+1];
+  uint addrs[NDIRECT+2];
 };
 
 // map major device number to device functions.
diff --git a/kernel/fs.c b/kernel/fs.c
index f33553a..a501e80 100644
--- a/kernel/fs.c
+++ b/kernel/fs.c
@@ -380,6 +380,7 @@ bmap(struct inode *ip, uint bn)
   uint addr, *a;
   struct buf *bp;
 
+  // bn in direct block. (0 <= bn <= 10)
   if(bn < NDIRECT){
     if((addr = ip->addrs[bn]) == 0)
       ip->addrs[bn] = addr = balloc(ip->dev);
@@ -387,6 +388,7 @@ bmap(struct inode *ip, uint bn)
   }
   bn -= NDIRECT;
 
+  // bn in singly-indirect block. (11 <= bn <= 266)
   if(bn < NINDIRECT){
     // Load indirect block, allocating if necessary.
     if((addr = ip->addrs[NDIRECT]) == 0)
@@ -400,6 +402,34 @@ bmap(struct inode *ip, uint bn)
     brelse(bp);
     return addr;
   }
+  bn -= NINDIRECT;
+
+  // bn in double-indirect block. (267 <= bn <= 65863)
+  if(bn < NDINDIRECT){
+
+    // Load double-indirect block in inode, allocating if necessary.
+    if((addr = ip->addrs[NDIRECT + 1]) == 0)
+      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
+
+    // read first indierct block
+    bp = bread(ip->dev, addr);
+    a = (uint*)bp->data;
+    if((addr = a[bn / NINDIRECT]) == 0){
+      a[bn / NINDIRECT] = addr = balloc(ip->dev);
+      log_write(bp);
+    }
+    brelse(bp);
+
+    // read last indirect block
+    bp = bread(ip->dev, addr);
+    a = (uint*)bp->data;
+    if((addr = a[bn % NINDIRECT]) == 0){
+      a[bn % NINDIRECT] = addr = balloc(ip->dev);
+      log_write(bp);
+    }
+    brelse(bp);
+    return addr;
+  }
 
   panic("bmap: out of range");
 }
@@ -432,6 +462,29 @@ itrunc(struct inode *ip)
     ip->addrs[NDIRECT] = 0;
   }
 
+  if(ip->addrs[NDIRECT + 1]){
+    bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
+    a = (uint*)bp->data;
+    struct buf *bpn;
+    uint* an;
+    for(int i = 0; i < NINDIRECT; i++){
+      if(a[i]){
+        bpn = bread(ip->dev, a[i]);
+        an = (uint*)bpn->data;
+        for(int j = 0; j < NINDIRECT; j++){
+          if(an[j])
+            bfree(ip->dev, an[j]);
+        }
+        brelse(bpn);
+        bfree(ip->dev, a[i]);
+        a[i] = 0;
+      }
+    }
+    brelse(bp);
+    bfree(ip->dev, ip->addrs[NDIRECT + 1]);
+    ip->addrs[NDIRECT + 1] = 0;
+  }
+
   ip->size = 0;
   iupdate(ip);
 }
diff --git a/kernel/fs.h b/kernel/fs.h
index 139dcc9..4e1b332 100644
--- a/kernel/fs.h
+++ b/kernel/fs.h
@@ -24,9 +24,10 @@ struct superblock {
 
 #define FSMAGIC 0x10203040
 
-#define NDIRECT 12
-#define NINDIRECT (BSIZE / sizeof(uint))
-#define MAXFILE (NDIRECT + NINDIRECT)
+#define NDIRECT 11
+#define NINDIRECT (BSIZE / sizeof(uint)) // 256
+#define NDINDIRECT (BSIZE / sizeof(uint)) * (BSIZE / sizeof(uint)) // 256 * 256
+#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)
 
 // On-disk inode structure
 struct dinode {
@@ -35,7 +36,7 @@ struct dinode {
   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+1];   // Data block addresses
+  uint addrs[NDIRECT+2];   // Data block addresses
 };
 
 // Inodes per block.
diff --git a/kernel/stat.h b/kernel/stat.h
index 19543af..fe8ef73 100644
--- a/kernel/stat.h
+++ b/kernel/stat.h
@@ -1,6 +1,7 @@
 #define T_DIR     1   // Directory
 #define T_FILE    2   // File
 #define T_DEVICE  3   // Device
+#define T_SYMLINK 4   // Symbolic Link
 
 struct stat {
   int dev;     // File system's disk device
diff --git a/kernel/syscall.c b/kernel/syscall.c
index c1b3670..1697b62 100644
--- a/kernel/syscall.c
+++ b/kernel/syscall.c
@@ -104,6 +104,7 @@ extern uint64 sys_unlink(void);
 extern uint64 sys_wait(void);
 extern uint64 sys_write(void);
 extern uint64 sys_uptime(void);
+extern uint64 sys_symlink(void);
 
 static uint64 (*syscalls[])(void) = {
 [SYS_fork]    sys_fork,
@@ -127,6 +128,7 @@ static uint64 (*syscalls[])(void) = {
 [SYS_link]    sys_link,
 [SYS_mkdir]   sys_mkdir,
 [SYS_close]   sys_close,
+[SYS_symlink] sys_symlink,
 };
 
 void
diff --git a/kernel/syscall.h b/kernel/syscall.h
index bc5f356..13818da 100644
--- a/kernel/syscall.h
+++ b/kernel/syscall.h
@@ -20,3 +20,4 @@
 #define SYS_link   19
 #define SYS_mkdir  20
 #define SYS_close  21
+#define SYS_symlink 22
diff --git a/kernel/sysfile.c b/kernel/sysfile.c
index 5dc453b..b476ef7 100644
--- a/kernel/sysfile.c
+++ b/kernel/sysfile.c
@@ -322,6 +322,30 @@ sys_open(void)
     return -1;
   }
 
+  if(ip->type == T_SYMLINK){
+    int level = 0;
+    char name[MAXPATH];
+    if(!(omode & O_NOFOLLOW)){
+      for(; level < 10 && ip->type == T_SYMLINK; level++){
+        memset(name, 0, MAXPATH);
+        readi(ip, 0, (uint64)name, 0, MAXPATH); // fetch path name saved in symbolic link file
+        iunlockput(ip);
+        // evaluate path and return the corresponding inode
+        // namei doesn't lock inode
+        if((ip = namei(name)) == 0){
+          end_op();
+          return -1;
+        }
+        ilock(ip);
+      }
+    }
+    // the links form a cycle
+    if(level == 10){
+      iunlockput(ip);
+      end_op();
+      return -1;
+    }
+  }
   if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
     if(f)
       fileclose(f);
@@ -484,3 +508,33 @@ sys_pipe(void)
   }
   return 0;
 }
+int
+sys_symlink(void)
+{
+  char target[MAXPATH], path[MAXPATH];
+  struct inode *ip;
+
+  memset(target, 0, sizeof(target));
+  memset(path, 0, sizeof(target));
+
+  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
+    return -1;
+
+  begin_op();
+
+  // create symbolic link inode
+  if((ip = create(path, T_SYMLINK, 0, 0)) == 0)
+    goto bad;
+
+  // store the target path of a symbolic link in the inode's data blocks
+  if(writei(ip, 0, (uint64)target, 0, MAXPATH) != MAXPATH)
+    goto bad;
+
+  iunlockput(ip);
+  end_op();
+  return 0;
+
+bad:
+  end_op();
+  return -1;
+}
diff --git a/user/user.h b/user/user.h
index b71ecda..883ef48 100644
--- a/user/user.h
+++ b/user/user.h
@@ -23,6 +23,7 @@ int getpid(void);
 char* sbrk(int);
 int sleep(int);
 int uptime(void);
+int symlink(char *, char *);
 
 // ulib.c
 int stat(const char*, struct stat*);
diff --git a/user/usys.pl b/user/usys.pl
index 01e426e..bc5c22e 100755
--- a/user/usys.pl
+++ b/user/usys.pl
@@ -36,3 +36,4 @@ entry("getpid");
 entry("sbrk");
 entry("sleep");
 entry("uptime");
+entry("symlink");

Lab File System

文章目录

Lab: file system

准备工作

Large files (moderate)

实验任务

实验思路

实验测试

Symbolic links (moderate)

实验任务

实验思路

实验测试

Lab 评测

Diff