Large files

思路

xv6 文件系统的 inode 中地址域 addrs[] 由 12 个直接地址和 1 个一级间接地址组成，本实验要求将地址域更改为 11 个直接地址、1 个一级间接地址和 1 个二级间接地址组成，以支持更大文件的存储。

代码的实现有了直接地址和一级间接地址做参考，就很简单了，直接查看代码部分即可。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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 40c9bd4..4c00ab5 100644
--- a/kernel/fs.c
+++ b/kernel/fs.c
@@ -400,6 +400,33 @@ bmap(struct inode *ip, uint bn)
     brelse(bp);
     return addr;
   }
+  bn -= NINDIRECT;
+
+  if (bn < NINDIRECT2) {
+    if ((addr = ip->addrs[NDIRECT + 1]) == 0) {
+      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
+    }
+
+    uint i = bn / NINDIRECT, j = bn % NINDIRECT;
+    
+    bp = bread(ip->dev, addr);
+    a = (uint *)bp->data;
+    if ((addr = a[i]) == 0) {
+      a[i] = addr = balloc(ip->dev);
+      log_write(bp);
+    }
+    brelse(bp);
+
+    bp = bread(ip->dev, addr);
+    a = (uint *)bp->data;
+    if ((addr = a[j]) == 0) {
+      a[j] = addr = balloc(ip->dev);
+      log_write(bp);
+    }
+    brelse(bp);
+
+    return addr;
+  }
 
   panic("bmap: out of range");
 }
@@ -432,6 +459,29 @@ itrunc(struct inode *ip)
     ip->addrs[NDIRECT] = 0;
   }
 
+  struct buf *bp2;
+  uint *a2;
+  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]) {
+        bp2 = bread(ip->dev, a[i]);
+        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;
+  }
+
   ip->size = 0;
   iupdate(ip);
 }
diff --git a/kernel/fs.h b/kernel/fs.h
index 139dcc9..cd5de8a 100644
--- a/kernel/fs.h
+++ b/kernel/fs.h
@@ -24,9 +24,10 @@ struct superblock {
 
 #define FSMAGIC 0x10203040
 
-#define NDIRECT 12
+#define NDIRECT 11
 #define NINDIRECT (BSIZE / sizeof(uint))
-#define MAXFILE (NDIRECT + NINDIRECT)
+#define NINDIRECT2 (NINDIRECT * NINDIRECT)
+#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT2)
 
 // 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.

Symbolic links

思路

本实验要求为 xv6 实现符号链接（软链接）机制，符号链接本质上也是一个文件，只不过它的数据内容为该链接指向的文件路径，这其实与 Windows 系统的快捷方式十分类似。实现方案如下：

首先依照 Lab System call 中的方法，添加系统调用 symlink：添加 symlink() 声明，添加系统调用号，添加系统调用 entry，添加 sys_symlink() 声明。

在理解了符号链接的本质后，就可以着手实现 sys_symlink 了。首先明确一下 symlink 的作用，它包含两个参数：target 和 path，作用是创建一个目录为 path 的符号链接，该符号链接指向目录为 target 的文件。实现思路应该比较清晰：使用 create() 创建一个文件类型为符号链接（需要自行定义）的文件，再使用 writei() 将字符串 path 写入该文件中。

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
uint64 sys_symlink(void) {
    int n1, n2;
    char target[MAXPATH], path[MAXPATH];
    struct inode *ip;

    // get arguments of symlink
    if ((n1 = argstr(0, target, MAXPATH)) < 0 || (n2 = argstr(1, path, MAXPATH)) < 1) {
        return -1;
    }

    begin_op();
    // create symbol link in the path
    if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
        end_op();
        return -1;
    }
    // write target to file that ip points to
    if (writei(ip, 0, (uint64)target, 0, n1) < n1) {
        end_op();
        return -1;
    }
    iunlockput(ip);
    end_op();

    return 0;
}

实现了符号链接的创建之后，还需要修改 sys_open()，实现对符号链接的特殊处理：当该文件是一个符号链接并且需要以跟随（follow）的方式打开时，就不断向下递归，将当前的 inode 指针指向符号链接指向文件的 inode，直到 inode 指针对应的文件类型不是符号链接，此时该 inode 指针指向的文件才是本次 sys_open() 系统调用实际需要打开的文件。

这里要用到两个关键函数 readi() 和 namei()。其中 readi() 能够根据 inode 指针，从该 inode 指针对应的文件中读取数据；而 namei() 能够根据指定的路径，返回该路径对应文件的 inode 指针。“跟随”的基本流程就是先使用读取当前 inode 中的数据，即目标文件路径 path，再将当前 inode 指针指向 path 目录对应的文件，以此往复。

最后还有一个小细节，就是当多个符号链接形成一个环时，这样的“跟随”过程就可能会导致死循环，因此必须加以限制，这里为了实现的方便，只是设定了一个最大递归深度，当递归深度超过该设定最大值时，文件打开就会失败。

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
if (!(omode & O_NOFOLLOW)) {
    int depth = 10;     // max recursive depth
    struct inode *next; // next inode

    while (depth > 0 && ip->type == T_SYMLINK) {
        // read data from file that ip points to to path
        if (readi(ip, 0, (uint64)path, 0, MAXPATH) == 0) {
            iunlockput(ip);
            end_op();
            return -1;
        }

        // get inode of file in the path
        if ((next = namei(path)) == 0) {
            iunlockput(ip);
            end_op();
            return -1;
        }
        iunlockput(ip);
        ip = next;
        --depth;
        ilock(ip);
    }

    if (depth <= 0) {
        iunlockput(ip);
        end_op();
        return -1;
    }
}

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
diff --git a/Makefile b/Makefile
index 7a7e380..37a202c 100644
--- a/Makefile
+++ b/Makefile
@@ -188,6 +188,7 @@ UPROGS=\
 	$U/_grind\
 	$U/_wc\
 	$U/_zombie\
+	$U/_symlinktest\
 
 
 
diff --git a/kernel/fcntl.h b/kernel/fcntl.h
index 44861b9..b42df18 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
\ No newline at end of file
diff --git a/kernel/stat.h b/kernel/stat.h
index 19543af..46ba47f 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   // Symbol 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..0fbf6ed 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
\ No newline at end of file
diff --git a/kernel/sysfile.c b/kernel/sysfile.c
index 5dc453b..ae342c8 100644
--- a/kernel/sysfile.c
+++ b/kernel/sysfile.c
@@ -15,6 +15,7 @@
 #include "sleeplock.h"
 #include "file.h"
 #include "fcntl.h"
+#include "buf.h"
 
 // Fetch the nth word-sized system call argument as a file descriptor
 // and return both the descriptor and the corresponding struct file.
@@ -316,6 +317,35 @@ sys_open(void)
     }
   }
 
+  if (!(omode & O_NOFOLLOW)) {
+    int depth = 10;
+    struct inode *next;
+
+    while (depth > 0 && ip->type == T_SYMLINK) {
+      if (readi(ip, 0, (uint64)path, 0, MAXPATH) == 0) {
+        iunlockput(ip);
+        end_op();
+        return -1;
+      }
+
+      if ((next = namei(path)) == 0) {
+        iunlockput(ip);
+        end_op();
+        return -1;
+      }
+      iunlockput(ip);
+      ip = next;
+      --depth;
+      ilock(ip);
+    }
+
+    if (depth <= 0) {
+      iunlockput(ip);
+      end_op();
+      return -1;
+    }
+  }
+
   if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
     iunlockput(ip);
     end_op();
@@ -484,3 +514,28 @@ sys_pipe(void)
   }
   return 0;
 }
+
+uint64 sys_symlink(void) {
+  int n1, n2;
+  char target[MAXPATH], path[MAXPATH];
+  struct inode *ip;
+
+  if ((n1 = argstr(0, target, MAXPATH)) < 0 || (n2 = argstr(1, path, MAXPATH)) < 1) {
+    return -1;
+  }
+  
+  // create symbol link in the path
+  begin_op();
+  if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
+    end_op();
+    return -1;
+  }
+  if (writei(ip, 0, (uint64)target, 0, n1) < n1) {
+    end_op();
+    return -1;
+  }
+  iunlockput(ip);
+  end_op();
+
+  return 0;
+}
\ No newline at end of file
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..65a8d6b 100755
--- a/user/usys.pl
+++ b/user/usys.pl
@@ -36,3 +36,4 @@ entry("getpid");
 entry("sbrk");
 entry("sleep");
 entry("uptime");
+entry("symlink");
\ No newline at end of file