1 Large files

在这个任务中你将要去增大xv6文件的最大值。现在xv6文件被限制到最多只能由268个块。这个限制源于xv6的inode包含12个直接块号，以及一个间接块号，这指向一个持有256个块号的块，所以最大值为12 + 256 = 268.

bigfile命令会创建一个最长的文件，并且报告它的大小：

$ bigfile
..
wrote 268 blocks
bigfile: file is too small
$

这个测试会失败，因为bigfile期待的最大数是65803，但是未经修改的xv6的文件最大是268块。

你将要去改变xv6文件系统代码来支持双间接块的inode，这会包含256个单间接块的地址，而每个单间接块会包含256个数据块的地址。这回使得最后一个文件最大可承受限制达到65803块，或者说256*256+256+11 块。（是11而不是12，是因为有个直接数据块会被填充为双间接块）。

预备知识

mkfs程序会创建一个xv6文件系统磁盘映像并且决定文件系统的总的块数；这个大小取决于FSSIZE。该实验中的FSSIZE被设置为200000块。mkfs/mkfs会有以下的输出：

nmeta 70 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 25) blocks 199930 total 200000

改行描述了mkfs/mkfs构建的文件系统：由70块元数据（用于描述文件系统）以及199930数据块，总共是200000块。

在任何时间点，你需要去重建文件系统，你需要make clean，这回重建fs.img

需要关注什么

磁盘上inode的格式是由fs.h中的struct dinode定义的。你对NDIRECT, NINDIRECT, MAXFILE和addrs[]元素的struct dinode特别感兴趣。查看xv6文本中的图8.3，了解标准xv6节点的图。

在fs.c中的bmap()中可以找到磁盘上的文件数据。看一看，确保你明白它在做什么。在读写文件时调用Bmap()。当写入时，bmap()会根据需要分配新的块来保存文件内容，如果需要，还会分配一个间接块来保存块地址。

Bmap()处理两种类型的块号。参数bn是一个“逻辑块号”——文件中相对于文件开头的块号。ip->addrs[]中的块号和bread()的参数都是磁盘块号。您可以将bmap()看作是将文件的逻辑块号映射到磁盘块号。

你的工作

修改bmap()，使它除了实现直接块和单间接块外，还实现了一个双间接块。你必须只有11个直接块，而不是12个，为新的双间接块腾出空间;不允许更改磁盘上索引节点的大小。ip->addrs[]的前11个元素应为直接块;第12个应该是一个单间接块(就像当前的那个);13号应该是你新的双间接块。当bigfile写入65803块并且usertests成功运行时，这个练习就完成了:

$ bigfile
...................................................................................................................
wrote 65803 blocks
done; ok
$ usertests
...
ALL TESTS PASSED
$ 
bigfile 至少会花费一分半来执行。

提示：

• 确保您理解bmap()。写出ip->addrs[]、它所指向的间接块、双间接块和单间接块和数据块之间的关系图。确保您理解为什么添加双间接块会使最大文件大小增加256*256个块(实际上是-1，因为您必须减少一个直接块的数量)。
• 考虑一下如何用逻辑块号索引双间接块及其指向的间接块。
• 如果你改变了NDIRECT的定义，你可能不得不改变file.h中struct inode中addrs[]的声明。确保struct inode和struct dinode在addrs[]数组中有相同数量的元素。
• 如果您更改了NDIRECT的定义，请确保创建一个新的fs。因为mkfs使用NDIRECT来构建文件系统。
• 如果您的文件系统处于糟糕的状态，可能是由于崩溃，请删除fs.img(从Unix而不是xv6执行此操作)。Make将为您构建一个新的干净的文件系统映像。
• 不要忘记用brelse()来处理那些你bread()过的块。
• 您应该只在需要时分配间接块和双间接块，就像原始的bmap()一样。
• 确保itrunc释放文件的所有块，包括双间接块。

修改相关宏

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

修改bmap()

这个逻辑已经说的很清楚了，类似于多级页表。只要添加对于第二级的处理即可。不要忘记brelse。

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);return addr;}bn -= NDIRECT;if(bn < NINDIRECT){// Load indirect block, allocating if necessary.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 < NDOUBLEINDIRECT){uint64 lev_1 = bn / NINDIRECT,lev_2 = bn % NINDIRECT;// Load double-indirect block, allocating if necessary.if((addr = ip->addrs[NDIRECT + 1]) == 0)ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);bp = bread(ip->dev,addr);a = (uint*)bp->data;// First layer.if((addr = a[lev_1]) == 0){a[lev_1] = addr = balloc(ip->dev);log_write(bp);}brelse(bp);// Second layer.bp = bread(ip->dev,addr);a = (uint*)bp->data;if((addr = a[lev_2]) == 0){a[lev_2] = addr = balloc(ip->dev);log_write(bp);}brelse(bp);return addr;}panic("bmap: out of range");
}

修改itrunc()

// Truncate inode (discard contents).
// Caller must hold ip->lock.
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;}}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;}if(ip->addrs[NDIRECT+1]){bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);a = (uint*)bp->data;for(j = 0; j < NINDIRECT; j++){if(a[j]){struct buf *second_bp;uint *second_a;second_bp = bread(ip->dev,a[j]);second_a = (uint*)second_bp->data;// Second layer.for(int k = 0;k < NINDIRECT; k++){if(second_a[k]){bfree(ip->dev, second_a[k]);}}brelse(second_bp);bfree(ip->dev,a[j]);}}brelse(bp);bfree(ip->dev, ip->addrs[NDIRECT + 1]);ip->addrs[NDIRECT + 1] = 0;}ip->size = 0;iupdate(ip);
}

2 Symbolic links

在这部分的测试中，你需要在xv6中添加符号链接。符号链接（软连接）会通过路径名指向一个被连接的文件；当一个符号链接打开时，内核需要随着连接抵达被指向的文件。符号连接类似于硬链接，但是硬链接更加严格的指向在同一磁盘位置的文件，而且符号连接可以跨设备。虽然xv6不支持多设备，实现总共系统调用是一个理解路径名查找如何工作的好的机会。

你的工作

你将要实现 symlink(char *target, char *path) 系统调用，这会在path处创建一个新的符号引用，指向target。更深的内容，可以查看符号引用的手册。为了测试，需要把symlinktest添加到Makefile，并且执行它。当测试产生如下输出时（包括usertests），你的题解才是正确的。

$ symlinktest
Start: test symlinks
test symlinks: ok
Start: test concurrent symlinks
test concurrent symlinks: ok
$ usertests
...
ALL TESTS PASSED
$ 

提示：

• 首先，为symlink创建一个新的系统调用号，向user/usys.pl、user/user.h添加一个条目，并在kernel/sysfile.c中实现一个空的sys_symlink。
• 在kernel/stat.h中添加一个新的文件类型(T_SYMLINK)来表示符号链接。
• 在kernel/fcntl.h中添加一个可以与open系统调用一起使用的新标志(O_NOFOLLOW)。注意，传递给open的标志使用位或操作符组合，因此新标志不应与任何现有标志重叠。这将允许您在将user/symlinktest.c添加到Makefile后编译它。
• 实现符号链接(目标，路径)系统调用，在指向目标的路径上创建一个新的符号链接。注意，系统调用成功不需要target存在。您需要选择某个地方来存储符号链接的目标路径，例如，在inode的数据块中。Symlink应该返回一个表示成功(0)或失败(-1)的整数，类似于link和unlink。
• 修改open系统调用，以处理路径指向符号链接的情况。如果文件不存在，打开一定会失败。当进程在打开标志中指定O_NOFOLLOW时，open应该打开符号链接(而不是跟随符号链接)。
• 如果链接的文件也是一个符号链接，则必须递归地跟随它，直到到达一个非链接文件。如果链接形成一个循环，则必须返回一个错误代码。如果链接深度达到某个阈值(例如，10)，你可以通过返回一个错误代码来近似这个值。
• 其他系统调用(例如，link和unlink)不能跟随符号链接;这些系统调用对符号链接本身进行操作。
• 在本实验中，您不需要处理指向目录的符号链接。

硬链接就是新建一个dirent，这个dirent指向的就是旧的inode。而软连接则是创建一个新的inode，这个新的inode的data部分要存储连接对象的路径。

添加sys_symlink()

可以根据sys_link()去实现它，但是要注意它们的不同点。

首先需要打开新的路径的父目录，并且查看需要创建的软连接是否已经存在，如果不存在就创建一个新的inode来存放软连接，并且在父目录中创建一个dirent指向该inode。

修改软连接的内容为旧路径。

uint64
sys_symlink(void){char name[DIRSIZ], new[MAXPATH], old[MAXPATH];struct inode *dp, *newip;int newFlag = 0;if(argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)return -1;begin_op();// Link the dirent to the newip.if((dp = nameiparent(new, name)) == 0){end_op();return -1;}ilock(dp);// Alloc a new inode for symlink,and write the old path in.if((newip = dirlookup(dp,name,0)) == 0){newFlag = 1;newip = ialloc(dp->dev,O_NOFOLLOW);ilock(newip);newip->nlink = 1;newip->major = 0;newip->minor = 0;iupdate(newip);}else{ilock(newip);}writei(newip,0,(uint64)old,0,MAXPATH);iunlock(newip);if(dirlink(dp, name, newip->inum) < 0){iunlockput(dp);goto bad;}iunlockput(dp);iput(newip);end_op();return 0;bad:ilock(newip);if(newFlag)newip->nlink--;iupdate(newip);iunlockput(newip);end_op();return -1;
}

添加递归查询软连接路径函数

在没有设置O_NOFOLLOW时，open需要打开的文件是最底层的文件，所以需要添加一个查询函数。

返回值1表示成功，0表示失败。

最终的路径还是存在path中。

用cnt来表示查询深度，如果超过10，就认为有环。

如果打开的inode的type不是T_SYMLINK，就表示为真实文件路径，返回。

否则，就读取数据到path中，进入下层递归。

static int rec_symlink_find(char* path,int cnt){// Represent if it is a cycle.if(cnt > 10)return 0;cnt++;char newpath[MAXPATH];struct inode *ip;if((ip = namei(path)) == 0)return 0;ilock(ip);// If it is the true inode,return;if(ip->type != T_SYMLINK){iunlockput(ip);return 1;}if(readi(ip,0,(uint64)&newpath,0,MAXPATH) != MAXPATH){iunlockput(ip);return 0;}iunlockput(ip);memmove(path,newpath,MAXPATH);return rec_symlink_find(path,cnt);
}

修改sys_open()

open只需要在预处理阶段，当flag没有O_NOFOLLOW时，通过上述递归函数修改路径即可。

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 {// Make sure that it's a true file,if NOT O_NOFOLLOW.if((omode & O_NOFOLLOW) == 0){if(rec_symlink_find(path,0) == 0){end_op();return -1;}}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(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;
}