关于c:MIT-6181068286S081-操作系统工程-Lab9-file-system

在此作业中，您将减少 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() 读取二级索引表，进而读取真正地址。
itrunc()开释函数须要减少对二级间接索引的开释逻辑：仿照一级索引开释，但在开释真正地址之前再通过 bread() 读取开释 ….

因为间接索引数量和最大数量变了，更改一下原来定义的宏：
```
#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

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

运行后果
测试后果

在本练习中，您将向 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 必须失败。当过程在标记中指定要 open O_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，只是在拜访和读写时操作有所区别。

关于c:MIT-6181068286S081-操作系统工程-Lab9-file-system

Large files (moderate)

要求

筹备工作

你的工作

提醒

实现

思路

实现

后果

Symbolic links (moderate)

要求

提醒

实现

后果

总结

`make grade`

集体播种

Just My Socks（注册教程内含优惠码）

关于c:MIT-6181068286S081-操作系统工程-Lab9-file-system

Large files (moderate)

要求

筹备工作

你的工作

提醒

实现

思路

实现

后果

Symbolic links (moderate)

要求

提醒

实现

后果

总结

make grade

集体播种

Just My Socks（注册教程 内含优惠码）

`make grade`

Just My Socks（注册教程内含优惠码）