Large files (moderate)

要求

在此作业中，您将减少 xv6 文件的最大大小。目前 xv6 文件限度为 268 个块，或 268*BSIZE 字节（在 xv6 中 BSIZE 为 1024）。此限度来自这样一个事实，即 xv6 inode 蕴含 12 个“间接”块号和一个“单间接”块号，它指的是最多可包容 256 个块号的块，总共 12+256=268 个块。

bigfile 命令创立它所能创立的最长文件，并报告该大小：

$ bigfile..wrote 268 blocksbigfile: 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 blocksdone; 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 更大，文件更大。

实现

思路

  1. 关系图

  2. bmap()本来的逻辑：

    • 判读索引是否小于NDIRECT。若小于阐明是间接索引，因而可间接返回addrs[]中的地址（若该地址为0则须要先调配balloc()）
    • 若大于则阐明是间接索引。将本来的索引减去间接索引数量后失去在间接索引表中的索引。而后通过addrs[]获取间接索引表地址（若地址为0则须要调配），该地址须要bread()读取后存入struct buf b中。通过读取到的内容和之前失去的间接表索引能够失去真正的地址（若该地址为0则须要调配）。最初不要遗记brelse()开释读取的缓存。

  3. bigfile后该当减少的逻辑：

    • 若索引比一级间接索引的范畴（256）还要大，阐明到了二级索引的范畴中。而后须要仿照一级索引读取形式通过bread()读取二级索引表，进而读取真正地址。
  4. itrunc()开释函数须要减少对二级间接索引的开释逻辑：仿照一级索引开释，但在开释真正地址之前再通过bread()读取开释....

实现

  1. 因为间接索引数量和最大数量变了，更改一下原来定义的宏：

    #define NDIRECT 11  // 本来12#define NINDIRECT (BSIZE / sizeof(uint))#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT) // 本来没第三项

    扭转索引后须要扭转一些申明和定义：

    1. struct dinode中addrs[]大小由 NDIRECT + 1 变为 NDIRECT + 2
    2. struct inode中addrs[]大小由 NDIRECT + 1 变为 NDIRECT + 2

  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");}

  3. 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并运行它。当测试生成以下输入（包含用户测试胜利）时，您的解决方案就实现了。
$ symlinktestStart: test symlinkstest symlinks: okStart: test concurrent symlinkstest 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必须失败。当过程在标记中指定要open O_NOFOLLOW时，open应关上符号链接（而不是遵循符号链接）。
  • 如果链接的文件也是符号链接，则必须递归地追随它，直到达到非链接文件。如果链接造成循环，则必须返回错误代码。如果链接深度达到某个阈值（例如10），您能够通过返回错误代码来近似这一点。
  • 其余零碎调用（例如，link和unlink）不得遵循符号链接; 这些零碎调用在符号链接自身上运行。
  • 本试验中您不用解决指向目录的符号链接。

实现

  1. 定义symlink零碎调用

    • 在user.h中申明
    • 在usys.pl中增加条目
    • 在syscall.h中定义零碎调用序号
    • 在syscall.c中申明sys_symlink()并将其指针放入数组
    • 最初在sysfile.c中实现sys_symlink()的定义

  2. 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;}

  3. 在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;        }    }}

  4. 通过迭代获取实在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

集体播种

  1. xv6的文件系统包含七层，从底层的磁盘层到顶层的描述符层，别离负责不同的性能
  2. 文件系统通过struct inode组织每个文件（在磁盘中为struct dinode）。该构造体包含文件品种、大小、链接数量以及文件保留数据的数据块地址。具体构造如图
  3. Unix所有皆文件。无论是设施、目录、链接还是真正的文件，都能够示意为inode，只是在拜访和读写时操作有所区别。