Large files (moderate)
要求
在此作业中，您将减少 xv6 文件的最大大小。目前 xv6 文件限度为 268 个块，或 268*BSIZE 字节（在 xv6 中 BSIZE 为 1024）。此限度来自这样一个事实，即 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 文件系统磁盘映像，并确定文件系统总共有多少块; 此大小由 kernel/param.h 中的 FSSIZE 管制。你将看到此试验存储库中的 FSSIZE 设置为 200,000 个块。您应该在 make 输入中看到以下来自 mkfs/mkfs 的输入：nmeta 70 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 25) blocks 199930 total 200000
这一行形容了 mkfs/mkfs 构建的文件系统：它有 70 个元数据块（用于形容文件系统的块）和 199,930 个数据块，总计 200,000 个块。
如果在试验期间的任何时候，您发现自己必须从头开始重建文件系统，则能够运行 make clean，哪些强制重建 fs.img。
磁盘索引节点的格局由 fs.h 中的 struct dinode 定义。你应该对 NDIRECT、NINDIRECT、MAXFILE 和 struct dinode 的 addrs[] 元素特地感兴趣。查看 xv6 文本中的图 8.3，理解规范 xv6 索引节点的示意图。
在磁盘上查找文件数据的代码位于 fs.c 的 bmap() 中。看看它，确保你明确它在做什么。bmap() 在读取和写入文件时都会被调用。写入时，bmap() 依据须要调配新块来保留文件内容，如果须要保留块地址，还会调配间接块。
bmap() 解决两种块号。bn 参数是一个“逻辑块号”——文件中绝对于文件结尾的块号。ip->addrs[] 中的块号和 bread() 的参数是磁盘块号。您能够将 bmap() 视为将文件的逻辑块号映射到磁盘块号。
你的工作
批改
bmap()，使其实现一个双间接块，以及间接块和一个单间接块。您只有 11 个间接块，而不是 12 个，因为须要为您的新双间接块腾出空间; 不容许更改磁盘上 inode 的大小。ip->addrs[]的前 11 个元素应该是间接块; 第 12 个应该是一个单间接块（就像以后的块一样）; 第 13 个应该是您的新双间接块。当bigfile写入 65803 个块并且usertests -q胜利运行时，您就实现了本练习：
$ bigfile
..................................
wrote 65803 blocks
done; ok
$ usertests -q
...
ALL TESTS PASSED
$ bigfile至多须要运行一分半钟能力。
提醒
- 确保您理解
bmap()。画出ip->addrs[]、间接块、双间接块和它指向的单间接块与数据块之间的关系图。确保您理解为什么增加双间接块会使最大文件大小减少 256*256 个块（实际上是 -1，因为您必须将间接块的数量缩小 1）。 - 思考如何应用逻辑块号为双间接块及其指向的间接块编制索引。
- 如果你更改了
NDIRECT的定义，你可能不得不在file.h的struct inode中更改addrs[]的申明。确保struct inode和struct dinode在其addrs[]数组中具备雷同数量的元素。 - 如果更改
NDIRECT的定义，请确保创立一个新的fs.img，因为mkfs应用NDIRECT来构建文件系统。 - 如果您的文件系统进入谬误状态，可能是解体，请删除
fs.img（从 Unix 而不是 xv6 执行此操作）。make将为您构建一个新的洁净文件系统映像。 - 不要遗记
brelse()你bread()的每个块。 - 您应该仅依据须要调配间接块和双重间接块，就像原始的
bmap()一样。 - 确保
itrunc开释文件的所有块，包含双间接块。 usertests的运行工夫比以前的试验更长，因为对于此试验，FSSIZE更大，文件更大。
实现
思路
- 关系图
-
bmap()本来的逻辑：- 判读索引是否小于
NDIRECT。若小于阐明是间接索引，因而可间接返回addrs[]中的地址（若该地址为 0 则须要先调配balloc()） - 若大于则阐明是间接索引。将本来的索引减去间接索引数量后失去在间接索引表中的索引。而后通过
addrs[]获取间接索引表地址（若地址为 0 则须要调配），该地址须要bread()读取后存入struct buf b中。通过读取到的内容和之前失去的间接表索引能够失去真正的地址（若该地址为 0 则须要调配）。最初不要遗记brelse()开释读取的缓存。
- 判读索引是否小于
-
bigfile后该当减少的逻辑：- 若索引比一级间接索引的范畴（256）还要大，阐明到了二级索引的范畴中。而后须要仿照一级索引读取形式通过
bread()读取二级索引表，进而读取真正地址。
- 若索引比一级间接索引的范畴（256）还要大，阐明到了二级索引的范畴中。而后须要仿照一级索引读取形式通过
itrunc()开释函数须要减少对二级间接索引的开释逻辑：仿照一级索引开释，但在开释真正地址之前再通过bread()读取开释 ….
实现
-
因为间接索引数量和最大数量变了，更改一下原来定义的宏：
#define NDIRECT 11 // 本来 12 #define NINDIRECT (BSIZE / sizeof(uint)) #define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT) // 本来没第三项扭转索引后须要扭转一些申明和定义：
struct dinode中addrs[]大小由NDIRECT + 1变为NDIRECT + 2struct inode中addrs[]大小由NDIRECT + 1变为NDIRECT + 2
-
bmap()增加二级索引映射：static uint bmap(struct inode* ip, uint bn) { uint addr, *a; struct buf* bp; // 间接索引不变 if (bn < NDIRECT) {...} bn -= NDIRECT; // 一级间接索引也不变 if (bn < NINDIRECT) {...} // 若超出一级索引范畴则须要减去一级索引数量才失去二级索引 bn -= NINDIRECT; // 二级索引逻辑 if (bn < NINDIRECT * NINDIRECT) { // 获取索引表地址，若没有则调配 if ((addr = ip->addrs[NDIRECT + 1]) == 0) {addr = balloc(ip->dev); if (addr == 0) return 0; ip->addrs[NDIRECT + 1] = addr; } // 通过地址读取索引表 bp = bread(ip->dev, addr); a = (uint*)bp->data; // bn/NINDIRECT 失去在第一个索引表中的索引，若没有则调配 if ((addr = a[bn / NINDIRECT]) == 0) {addr = balloc(ip->dev); if (addr) { // 调配胜利后将地址写入该缓存中 a[bn / NINDIRECT] = addr; log_write(bp); } else { // 失败后开释，而后返回 0 地址 brelse(bp); return 0; } } brelse(bp); // 失去第二个索引表地址后能够开释第一个索引表了 // 通过第二个索引表获取真正的地址 bp = bread(ip->dev, addr); a = (uint*)bp->data; // 可通过 bn%NINDIRECT 获取在第二个索引表中的索引 if ((addr = a[bn % NINDIRECT]) == 0) { // 若没有则调配。调配胜利就写入缓存，不胜利之后返回 0 地址 addr = balloc(ip->dev); if (addr) {a[bn % NINDIRECT] = addr; log_write(bp); } } brelse(bp); return addr; } panic("bmap: out of range"); } -
itrunc()增加开释二级间接索引的逻辑代码：void itrunc(struct inode* ip) { int i, j; // 增加定义用于开释二级间接索引 struct buf *bp, *bpp; uint *a, *aa; // 开释间接索引 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 (i = 0; i < NINDIRECT; ++i) {if (a[i]) { // 本来间接开释的一级间接索引，// 此时须要再次读取、判断并开释 bpp = bread(ip->dev, a[i]); aa = (uint*)bpp->data; for (j = 0; j < NINDIRECT; ++j) {if (aa[j]) bfree(ip->dev, aa[j]); } brelse(bpp); bfree(ip->dev, a[i]); } } brelse(bp); bfree(ip->dev, ip->addrs[NDIRECT + 1]); } ip->size = 0; iupdate(ip); }
后果
- 运行后果
- 测试后果
Symbolic links (moderate)
在本练习中，您将向 xv6 增加符号链接。符号链接（或软链接）按路径名援用链接的文件; 关上符号链接时，内核会追随指向援用文件的链接。符号链接相似于硬链接，但硬链接仅限于指向同一磁盘上的文件，而符号链接能够跨磁盘设施。只管 xv6 不反对多个设施，但实现此零碎调用是理解路径名查找工作原理的好练习。
要求
您将实现符号
symlink(char *target，char *path)零碎调用，该调用在path处创立一个新的符号链接，该链接援用target文件。无关更多信息，请参见手册页symlink。要进行测试，请将符号链接测试增加到Makefile并运行它。当测试生成以下输入（包含用户测试胜利）时，您的解决方案就实现了。
$ symlinktest
Start: test symlinks
test symlinks: ok
Start: test concurrent symlinks
test concurrent symlinks: ok
$ usertests -q
...
ALL TESTS PASSED
$ 提醒
- 首先，为
symlink创立一个新的零碎调用序号，在user/usys.pl，user/user.h中增加一个条目，并在kernel/sysfile.c中实现一个空sys_symlink。 - 将新的文件类型（
T_SYMLINK）增加到kernel/stat.h以示意符号链接。 - 向
kernel/fcntl.h增加一个新标记（O_NOFOLLOW），该标记可用于open零碎调用。请留神，传递给open的标记是应用按位或运算符组合的，因而新标记不应与任何现有标记重叠。这将容许您在将user/symlinktest.c增加到Makefile后对其进行编译。 - 实现
symlink(target, path)零碎调用，以在path处创立指标为target的新符号链接。请留神，target不须要存在，零碎调用就会胜利。您须要抉择某个地位来存储符号链接的指标门路，例如，在 inode 的数据块中。symlink应返回一个整数，示意胜利（0）或失败（-1），相似于link和unlink。 - 批改
open零碎调用以解决门路援用符号链接的状况。如果该文件不存在，则open必须失败。当过程在标记中指定要openO_NOFOLLOW时，open应关上符号链接（而不是遵循符号链接）。 - 如果链接的文件也是符号链接，则必须递归地追随它，直到达到非链接文件。如果链接造成循环，则必须返回错误代码。如果链接深度达到某个阈值（例如 10），您能够通过返回错误代码来近似这一点。
- 其余零碎调用（例如，
link和unlink）不得遵循符号链接; 这些零碎调用在符号链接自身上运行。 - 本试验中您不用解决指向目录的符号链接。
实现
-
定义
symlink零碎调用- 在
user.h中申明 - 在
usys.pl中增加条目 - 在
syscall.h中定义零碎调用序号 - 在
syscall.c中申明sys_symlink()并将其指针放入数组 - 最初在
sysfile.c中实现sys_symlink()的定义
- 在
-
sys_symlink()的定义。该零碎调用的性能是在path生成一个类型为T_SYMLINK的文件，并在文件内容中写上target指标门路。由此可分为三步：（1）获取参数；（2）生成文件；（3）写入内容。uint64 sys_symlink(void) {char target[MAXPATH], path[MAXPATH]; struct inode *ip; int len; // (1) 获取字符参数 if ((len = argstr(0, target, MAXPATH)) < 0 || argstr(1, path, MAXPATH) < 0) {return -1;} // (2) 创立 symlink 文件 begin_op(); if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) {end_op(); return -1; } // (3) 写入指标门路 // ilock(ip); 加上就会死锁，因为 create 中曾经获取🔒 len = writei(ip, 0, (uint64)target, 0, len); iunlockput(ip); end_op(); return len > 0 ? 0 : -1; } -
在
sys_open()中增加对 symlink 文件的解决逻辑：sys_open()本来的解决是：如果是O_CREATE模式就创立在path处的 inode，否则就获取path处 inode。一个 symlink 文件肯定是在后者的抉择分支中，因而可在获取 inode 后增加对 symlink 文件解决的代码。uint64 sys_open() { ... if (omode & O_CREATE) { // 创立 inode ... } else { // 关上 inode if((ip = namei(path)) == 0) {end_op(); return -1; } ilock(ip); // 增加迭代读取 symlink 文件的逻辑代码 if (ip->type == T_SYMLINK && (omode & O_NOFOLLOW) == 0) { // opensymlink 函数迭代读取直到获取实在 inode 或获取失败 if ((ip = opensymlink(ip)) == 0) {end_op(); return -1; } } if(ip->type == T_DIR && omode != O_RDONLY) {iunlockput(ip); end_op(); return -1; } } } -
通过迭代获取实在 inode 的函数
struct inode* opensymlink(struct inode*)struct inode* opensymlink(struct inode* ip) {char target[MAXPATH]; const int max_times = 10; // 最大链接次数 int i, times, nums[max_times]; // 通过循环 max_times 次来管制最大链接次数 for (times = 0; times < max_times; ++times) {nums[times] = ip->inum; // 保留 inode num 用于判断是否曾经迭代过 // 读取 target 的门路，若失败开释🔒后返回 0 if (readi(ip, 0, (uint64)target, 0, MAXPATH) < 0) {iunlockput(ip); return 0; } iunlockput(ip); // 若胜利读取，就能够开释该 inode。且下一步要切换 ip // 关上 target 门路文件，若失败则返回 0 if ((ip = namei(target)) == 0) {return 0;} // 通过 inode num 判断是否曾经被迭代过，若有则阐明形成环要及时返回 for (i = 0; i < times; ++i) {if (nums[i] == nums[times]) {printf("links form a cycle!\n"); return 0; } } // 函数进来和循环开始时是上🔒状态，因而这里也须要上锁后再退出函数或下一轮循环 ilock(ip); // 若新关上的 inode 非 T_SYMLINK 类型阐明获取了真正的 inode，返回 if (ip->type != T_SYMLINK) {return ip;} } printf("open: too deep!\n"); return 0; }
后果
- 运行后果
- 测试后果
总结
make grade
集体播种
- xv6 的文件系统包含七层，从底层的磁盘层到顶层的描述符层，别离负责不同的性能
- 文件系统通过
struct inode组织每个文件（在磁盘中为struct dinode）。该构造体包含文件品种、大小、链接数量以及文件保留数据的数据块地址。具体构造如图 - Unix 所有皆文件。无论是设施、目录、链接还是真正的文件，都能够示意为
inode，只是在拜访和读写时操作有所区别。