MIT 6.S081 Lab9 file system

large files

使命

   In this assignment you’ll increase the maximum size of an xv6 file. Currently xv6 files are limited to 268 blocks, or 268*BSIZE bytes (BSIZE is 1024 in xv6). This limit comes from the fact that an xv6 inode contains 12 “direct” block numbers and one “singly-indirect” block number, which refers to a block that holds up to 256 more block numbers, for a total of 12+256=268 blocks.
  在本作业中，您将增加xv6文件的最大巨细。目前，xv6文件限制为268个块，或268*BSIZE字节(xv6中的BSIZE为1024)。这个限制来自这样一个事实，即xv6索引节点包含12个“直接”块号和一个“单间接”块号，即一个最多可容纳256个块号的块，统共12+256=268个块。
   The mkfs program creates the xv6 file system disk image and determines how many total blocks the file system has; this size is controlled by FSSIZE in kernel/param.h. You’ll see that FSSIZE in the repository for this lab is set to 200,000 blocks. You should see the following output from mkfs/mkfs in the make output:
nmeta 70 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 25) blocks 199930 total 200000
This line describes the file system that mkfs/mkfs built: it has 70 meta-data blocks (blocks used to describe the file system) and 199,930 data blocks, totaling 200,000 blocks.
If at any point during the lab you find yourself having to rebuild the file system from scratch, you can run make clean which forces make to rebuild fs.img.
  mkfs程序创建xv6文件体系磁盘映像，并确定文件体系统共有多少块；该巨细由kernel/param.h中的FSSIZE控制。您将看到该实行室存储库中的FSSIZE设置为200000个块。您应该在make输出中看到mkfs/mkfs的以下输出：
nmeta 70(引导、超等、日志块30索引节点块13、位图块25)块199930统共200000
此行描述了mkfs/mkfs构建的文件体系：它有70个元数据块(用于描述文件体系的块)和199930个数据块，统共200000个块。
假如在实行的任何时候，你发现自己必须重新开始重修文件体系，你可以运行make clean命令，强制make重修fs.img。
   The format of an on-disk inode is defined by struct dinode in fs.h. You’re particularly interested in NDIRECT, NINDIRECT, MAXFILE, and the addrs[] element of struct dinode. Look at Figure 8.3 in the xv6 text for a diagram of the standard xv6 inode.
The code that finds a file’s data on disk is in bmap() in fs.c. Have a look at it and make sure you understand what it’s doing. bmap() is called both when reading and writing a file. When writing, bmap() allocates new blocks as needed to hold file content, as well as allocating an indirect block if needed to hold block addresses.
bmap() deals with two kinds of block numbers. The bn argument is a “logical block number” – a block number within the file, relative to the start of the file. The block numbers in ip->addrs[], and the argument to bread(), are disk block numbers. You can view bmap() as mapping a file’s logical block numbers into disk block numbers.
  磁盘上inode的格式由fs.h中的布局dinode定义。你应该特别留意NDIRECT、NINDIRECT和MAXFILE以及布局dinode的addrs[]。请参阅xv6文本中的图8.3，了解标准xv6索引节点的表示图。
在磁盘上查找文件数据的代码位于fs.c中的bmap()中。请查看它，确保您了解它的功能。bmap()在读取和写入文件时都会被调用。写入时，bmap()会根据需要分配新块来生存文件内容，并在需要时分配间接块来生存块地址。
bmap()处理惩罚两种块编号。bn参数是一个“逻辑块号”，即文件中相对于文件开头的块号。ip->addrs[]中的块号和bread()的参数是磁盘块号。您可以将bmap()视为将文件的逻辑块号映射到磁盘块号。
   Modify bmap() so that it implements a doubly-indirect block, in addition to direct blocks and a singly-indirect block. You’ll have to have only 11 direct blocks, rather than 12, to make room for your new doubly-indirect block; you’re not allowed to change the size of an on-disk inode. The first 11 elements of ip->addrs[] should be direct blocks; the 12th should be a singly-indirect block (just like the current one); the 13th should be your new doubly-indirect block. You are done with this exercise when bigfile writes 65803 blocks and usertests runs successfully:
  修改bmap()，使其除了直接块和单间接块外，还实现了双间接块。你只需要11个直接块，而不是12个，就可以为你的新双间接块腾出空间；不答应更改磁盘上inode的巨细。ip->addrs[]的前11个元素应该是直接块；第12个应该是一个单独的间接块(就像当前的块一样)；13号应该是你的新双间接街区。当bigfile写入65803个块而且用户测试乐成运行时，你就完成了此训练。
提示

• 确保你理解bmap()。写出ip->addrs[]、间接块、双间接块和它所指向的单间接块以及数据块之间的关系图。确保你理解为什么添加双间接块会使最大文件巨细增加256*256个块(实际上是-1，因为你必须将直接块的数量减少一个)。
  
• 考虑一下如何用逻辑块号对双间接块及其指向的间接块进行索引。
  
• 假如更改NDIRECT的定义，则大概必须更改file.h中struct inode中addrs[]的声明。请确保struct inode和struct dinode在其addrs[]数组中具有相同数量的元素。
  
• 假如更改NDIRECT的定义，请确保创建一个新的fs.img，因为mkfs使用NDIRECT构建文件体系。
  
• 假如您的文件体系进入不良状态，大概是瓦解，请删除fs.img(从Unix中执行此操作，而不是xv6)。make将为您构建一个新的干净文件体系映像。
  
• 别忘了对每个bread()的块进行brelease()。
  
• 您应该只根据需要分配间接块和双间接块，就像原始的bmap()一样。
  
• 确保itrunc开释文件的所有块，包括双间接块。
  

根据表示图，这里一个dinode一共有13个block，其中12个直接块，一个间接块，这里一个block的巨细BSIZE是1024Bytes。前12KB(NDIRECT*BSIZE)巨细的数据可以直接从inode中列出的块直接加载，而下一个256KB(NINDIRECT*BSIZE)字节只能从间接块中加载，这里需要设计二级间接块以满足实行要求。

• bmap根据需要分配块，ip->addrs[]或间接条目为0表示为分配任何块，假如bmap遇到0应该利用balloc分配新的块替换
  
• itrunc开释文件的块，并将索引节点的巨细重置为0，首先开释直接块，然后开释间接块。
  

修改xv6

• 修改NDIRECT 宏定义，和inode布局体中的addrs
  

1. // kenerl/fs.h
2. // #define NDIRECT 12
3. #define NDIRECT 11
4. #define NINDIRECT (BSIZE / sizeof(uint))
5. // #define MAXFILE (NDIRECT + NINDIRECT)
6. #define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT*NINDIRECT)
7. // On-disk inode structure
8. struct dinode {
9.   short type;           // File type
10.   short major;          // Major device number (T_DEVICE only)
11.   short minor;          // Minor device number (T_DEVICE only)
12.   short nlink;          // Number of links to inode in file system
13.   uint size;            // Size of file (bytes)
14.   uint addrs[NDIRECT+1+1];   // Data block addresses
15. };
17. // kernel/file.h
18. // in-memory copy of an inode
19. struct inode {
20.   uint dev;           // Device number
21.   uint inum;          // Inode number
22.   int ref;            // Reference count
23.   struct sleeplock lock; // protects everything below here
24.   int valid;          // inode has been read from disk?
26.   short type;         // copy of disk inode
27.   short major;
28.   short minor;
29.   short nlink;
30.   uint size;
31.   uint addrs[NDIRECT+1+1];
32. };

复制代码

• 修改bmap()函数
  

1. // kernel/fs.c
2. static uint
3. bmap(struct inode *ip, uint bn)
4. {
5.   uint addr, *a;
6.   struct buf *bp;
8.   if(bn < NDIRECT){
9.     if((addr = ip->addrs[bn]) == 0)
10.       ip->addrs[bn] = addr = balloc(ip->dev);
11.     return addr;
12.   }
13.   bn -= NDIRECT;
15.   if(bn < NINDIRECT){ // single indirect
16.     // Load indirect block, allocating if necessary.
17.     if((addr = ip->addrs[NDIRECT]) == 0)
18.       ip->addrs[NDIRECT] = addr = balloc(ip->dev);
19.     bp = bread(ip->dev, addr);
20.     a = (uint*)bp->data;
21.     if((addr = a[bn]) == 0){
22.       a[bn] = addr = balloc(ip->dev);
23.       log_write(bp);
24.     }
25.     brelse(bp);
26.     return addr;
27.   }
29.   bn -= NINDIRECT;
30.   if(bn < NINDIRECT*NINDIRECT){ // double indirect block
31.     if ((addr = ip->addrs[NDIRECT + 1]) == 0){
32.       ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
33.     }
34.     bp = bread(ip->dev, addr);
35.     a = (uint*)bp->data;
36.     if((addr = a[bn/NINDIRECT]) == 0){
37.       a[bn/NINDIRECT] = addr = balloc(ip->dev);
38.       log_write(bp);
39.     }
40.     brelse(bp);
42.     bn %= NINDIRECT;
43.     bp = bread(ip->dev, addr);
44.     a = (uint*)bp->data;
45.     if((addr = a[bn]) == 0){
46.       a[bn] = addr = balloc(ip->dev);
47.       log_write(bp);
48.     }
49.     brelse(bp);
50.     return addr;
51.   }
53.   panic("bmap: out of range");
54. }

复制代码

• 修改itrunc()函数
  

1. void
2. itrunc(struct inode *ip)
3. {
4.   int i, j;
5.   struct buf *bp;
6.   uint *a;
8.   for(i = 0; i < NDIRECT; i++){
9.     if(ip->addrs[i]){
10.       bfree(ip->dev, ip->addrs[i]);
11.       ip->addrs[i] = 0;
12.     }
13.   }
15.   if(ip->addrs[NDIRECT]){
16.     bp = bread(ip->dev, ip->addrs[NDIRECT]);
17.     a = (uint*)bp->data;
18.     for(j = 0; j < NINDIRECT; j++){
19.       if(a[j])
20.         bfree(ip->dev, a[j]);
21.     }
22.     brelse(bp);
23.     bfree(ip->dev, ip->addrs[NDIRECT]);
24.     ip->addrs[NDIRECT] = 0;
25.   }
27.   if(ip->addrs[NDIRECT + 1]){
28.       bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
29.       a = (uint*)bp->data;
30.       for(j = 0; j < NINDIRECT; j++){
31.         if(a[j]){
32.           struct buf *bp2 = bread(ip->dev, a[j]);
33.           uint *a2 = (uint*)bp2->data;
34.           for(i = 0; i < NINDIRECT; i++){
35.             if(a2[i])
36.               bfree(ip->dev, a2[i]);
37.           }
38.           brelse(bp2);
39.           bfree(ip->dev, a[j]);
40.         }
41.       }
42.       brelse(bp);
43.       bfree(ip->dev, ip->addrs[NDIRECT + 1]);
44.       ip->addrs[NDIRECT + 1] = 0;
45.   }
47.   ip->size = 0;
48.   iupdate(ip);
49. }

复制代码

Sysmbolic links

使命

   In this exercise you will add symbolic links to xv6. Symbolic links (or soft links) refer to a linked file by pathname; when a symbolic link is opened, the kernel follows the link to the referred file. Symbolic links resembles hard links, but hard links are restricted to pointing to file on the same disk, while symbolic links can cross disk devices. Although xv6 doesn’t support multiple devices, implementing this system call is a good exercise to understand how pathname lookup works.
  在本训练中，您将向xv6添加符号链接。符号链接(或软链接)是指按路径名链接的文件；当打开符号链接时，内核会按照链接指向引用的文件。符号链接雷同于硬链接，但硬链接仅限于指向同一磁盘上的文件，而符号链接可以跨磁盘设备。虽然xv6不支持多个设备，但实现此体系调用是理解路径名查找工作原理的一个很好的训练。
   You will implement the symlink(char *target, char *path) system call, which creates a new symbolic link at path that refers to file named by target. For further information, see the man page symlink. To test, add symlinktest to the Makefile and run it. Your solution is complete when the tests produce the following output (including usertests succeeding).
  您将实现symlink(char\*target，char\*path)体系调用，该调用在引用目的命名的文件的路径处创建一个新的符号链接。有关更多信息，请参阅手册页符号链接。要进行测试，请将symlinkstest添加到Makefile中并运行它。当测试产生以下输出时(包括用户测试乐成)，您的解决方案就完成了。
提示

• 首先，为symlink创建一个新的体系调用号，在user/usys.pl、user/user.h中添加一个条目，并在kernel/sysfile.c中实现一个空的sys_symlink。
  
• 在kernel/stat.h中添加一个新的文件类型（T_SYMLINK）来表示符号链接。
  
• 在kernel/fcntl.h中添加一个新标志（O_NOFOLLOW），该标志可用于开放体系调用。请留意，转达给open的标志是使用位OR运算符组合的，因此您的新标志不应与任何现有标志重叠。这将答应您在将user/symlinktest.c添加到Makefile后对其进行编译。
  
• 实现symlink（target，path）体系调用，在引用目的的路径处创建一个新的符号链接。请留意，体系调用乐成不需要目的存在。您需要选择一个位置来存储符号链接的目的路径，比方，在索引节点的数据块中。符号链接应该返回一个表示乐成（0）或失败（-1）的整数，雷同于链接和取消链接。
  
• 修改开放体系调用以处理惩罚路径引用符号链接的情况。假如文件不存在，打开必须失败。当一个历程在要打开的标志中指定O_NOFOLLOW时，open应该打开符号链接（而不是遵照符号链接）。
  
• 假如链接文件也是符号链接，则必须递归地跟随它，直到到达非链接文件。假如链接形成循环，则必须返回错误代码。假如链接深度达到某个阈值（比方10），您可以通过返回错误代码来近似盘算。
  
• 其他体系调用（比方，链接和取消链接）不得遵照符号链接；这些体系调用对符号链接本身进行操作。
  
• 您不必处理惩罚指向此实行目录的符号链接。
  

修改xv6

• 添加体系调用symlink，符号连接和普通文件一样需要占用inode块。
  

1. // user/usys.pl
2. entry("symlink");
3. // user/user.h
4. uint symlink(const char*, const char*);
5. // kernel/syscall.h
6. #define SYS_symlink 22;
7. // kernel/syscall.c
8. extern uint64 sys_symlink(void);
9. static uint64 (*syscalls[])(void) = {
10. // ..
11. [SYS_symlink] sys_symlink,
12. };
13. // kernel/stat.h
14. #define T_SYMLINK 4   // Symbolic link
15. // kernel/sysfile.c
16. uint64
17. sys_symlink(void)
18. {
19.   struct inode *ip;
20.   char target[MAXPATH], path[MAXPATH];
21.   if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0)
22.     return -1;
24.   begin_op();
26.   ip = create(path, T_SYMLINK, 0, 0);
27.   if(ip == 0){
28.     end_op();
29.     return -1;
30.   }
32.   // use the first data block to store target path.
33.   if(writei(ip, 0, (uint64)target, 0, strlen(target)) < 0) {
34.     end_op();
35.     return -1;
36.   }
38.   iunlockput(ip);
40.   end_op();
41.   return 0;
42. }

复制代码

• 修改sys_open体系调用
  

1. // kernel/fcntl.h
2. #define O_NOFOLLOW 0x800
3. // kernel/sysfile.c
4. uint64
5. sys_open(void)
6. {
7.   char path[MAXPATH];
8.   int fd, omode;
9.   struct file *f;
10.   struct inode *ip;
11.   int n;
13.   if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
14.     return -1;
16.   begin_op();
18.   if(omode & O_CREATE){
19.     ip = create(path, T_FILE, 0, 0);
20.     if(ip == 0){
21.       end_op();
22.       return -1;
23.     }
24.   } else {
25.     // if((ip = namei(path)) == 0){
26.     //   end_op();
27.     //   return -1;
28.     // }
29.     // ilock(ip);
30.     int symlink_depth = 0;
31.     while(1) { // recursively follow symlinks
32.       if((ip = namei(path)) == 0){
33.         end_op();
34.         return -1;
35.       }
36.       ilock(ip);
37.       if(ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) {
38.         if(++symlink_depth > 10) {
39.           // aovid loop
40.           iunlockput(ip);
41.           end_op();
42.           return -1;
43.         }
44.         if(readi(ip, 0, (uint64)path, 0, MAXPATH) < 0) {
45.           iunlockput(ip);
46.           end_op();
47.           return -1;
48.         }
49.         iunlockput(ip);
50.       } else {
51.         break;
52.       }
53.     }
54.     if(ip->type == T_DIR && omode != O_RDONLY){
55.       iunlockput(ip);
56.       end_op();
57.       return -1;
58.     }
59.   }
61.   if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
62.     iunlockput(ip);
63.     end_op();
64.     return -1;
65.   }
67.   if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
68.     if(f)
69.       fileclose(f);
70.     iunlockput(ip);
71.     end_op();
72.     return -1;
73.   }
75.   if(ip->type == T_DEVICE){
76.     f->type = FD_DEVICE;
77.     f->major = ip->major;
78.   } else {
79.     f->type = FD_INODE;
80.     f->off = 0;
81.   }
82.   f->ip = ip;
83.   f->readable = !(omode & O_WRONLY);
84.   f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
86.   if((omode & O_TRUNC) && ip->type == T_FILE){
87.     itrunc(ip);
88.   }
90.   iunlock(ip);
91.   end_op();
93.   return fd;
94. }

复制代码

日志

参考Xv6-book中8.4-8.6节