Lab 5实验过程点此处
File system preliminaries(序言)
您将使用的文件系统比大多数“实际”文件系统(包括xv6 UNIX)要简单得多，但是它的功能足够强大，可以提供基本特性:创建、读取、写入和删除按
层次(hierarchical )目录结构
组织的文件。
我们(至少目前)只开发一个
单用户操作系统
，它提供了足够的保护来捕获bug，但不能保护多个相互怀疑的用户。因此，我们的文件系统不支持
UNIX文件所有权或权限
的概念。我们的文件系统目前也不像大多数UNIX文件系统那样支持
硬链接、符号链接、时间戳或特殊设备文件
。
On-Disk File System Structure
大多数UNIX文件系统将可用磁盘空间划分为两种主要区域类型:
inode regions and data regions
。UNIX文件系统为文件系统中的每个文件分配一个inode;
文件的inode
包含关于文件的关键元数据(
meta-data
)，比如它的
stat属性
和指向数据块的
指针
。数据区域被划分为比inode更大的数据块(通常为8KB或更多)，文件系统在其中存储
文件数据
和
目录元数据
。
目录项
包含文件名和指向inode的指针;如果文件系统中的多个目录条目引用该文件的inode，则该文件被称为
硬链接的
。由于我们的文件系统
不支持硬链接
，所以我们不需要这种间接级别，因此可以方便地简化:我们的文件系统根本
不使用inode
，而只是在描述该文件的(唯一的)
目录条目
中存储文件(或子目录)的
所有元数据
。
文件和目录
在逻辑上都由一系列
数据块
组成。它可以
分散在磁盘上
，就像environment的虚拟地址空间的页面可以分散在物理内存中一样。
文件系统环境
隐藏了块布局的细节，显示了在文件中任意偏移量处读取和写入字节序列的
接口
。文件系统环境在内部处理对目录的所有修改，作为执行文件创建和删除等操作的一部分。我们的文件系统允许
用户环境直接读取目录元数据
(例如，使用read)，这意味着用户环境可以自己执行
目录扫描操作
(例如，实现ls程序)，而不必依赖于对文件系统的额外特殊调用。这种目录扫描方法的缺点(也是大多数现代UNIX变体不支持这种方法的原因)是，它使应用程序
依赖于目录元数据的格式
，使得在不更改或至少重新编译应用程序的情况下更改文件系统的内部布局非常困难。
Sectors and Blocks
大多数
磁盘
不能按字节粒度执行读写，而是按
扇区的单位
执行读写。在JOS中，每个扇区是
512字节
。
文件系统
实际上是
以块为单位
分配和使用磁盘存储的。注意这两个术语之间的
区别
:扇区大小是
磁盘硬件
的属性，而块大小是使用磁盘的操作系统的一个方面。文件系统的块大小必须是基础磁盘扇区大小的
数倍
。
UNIX xv6文件系统使用512字节的块大小，与底层磁盘的扇区大小相同。然而，大多数现代文件系统使用更大的块大小，因为存储空间变得更便宜，而且在更大粒度上管理存储更有效。我们的JOS文件系统将使用
4096字节的块大小
，方便地匹配处理器的页面大小。
Superblocks(超级块)
文件系统通常将某些磁盘块保留在磁盘上某个"
容易找到
"的地方(例如最开始或者最末端)去保存
描述整个文件系统属性的元数据
，比如block size、disk size、查找root directory所需的任何元数据、最后一次挂载文件系统的时间、最后一次检查文件系统是否出错的时间等等。这些特殊的块就是
superblocks
。
我们的文件系统将只有一个超级块，它总是在磁盘上的block 1(第二块)。它的布局是由
struct Super
在inc/fs.h中定义的。block 0通常保留用于保存
boot loaders
和
partition tables
(分区表)，因此文件系统通常不使用第一个磁盘块。许多“real”文件系统有多个超级块，这些超级块复制到磁盘的多个widely-space(宽间距)区域，因此，如果其中一个超级块损坏了，或者磁盘在该区域出现了media错误，仍然可以找到其他超级块，并使用它们访问文件系统。
File Meta-data
文件系统中
描述文件的元数据
的布局由inc/fs.h中的
struct file
描述。这个元数据包括文件的名称、大小、类型(常规文件或目录)和指向组成文件的块的指针。如上所述，我们没有inode，所以这个元数据存储在磁盘上的
目录条目
中。与大多数“real”文件系统不同，为了简单起见，我们将使用这个
File structure
来表示文件元数据，因为它同时出现在磁盘和内存中。
struct File中的
f_direct
数组包含存储文件
前10个(NDIRECT)块
的块号的空间，我们称之为文件的
直接块
。对于大小高达10*4096B = 40KB的小文件，这意味着所有文件块的块号将直接适合File structure 本身。但是，对于较大的文件，我们需要一个地方来保存文件的其余块号。因此，对于任何大于40KB的文件，我们分配一个额外的磁盘块，称为文件的
间接块
，以容纳
4096/4 = 1024
个额外的块号。
因此，我们的文件系统允许文件的大小最多为
1034块
，即超过
4MB
一点点。为了支持更大的文件，“真正的”文件系统通常还支持双间接块和三间接块。
Directories vs Regular Files
文件系统中的
File structure
既可以表示
普通文件
，也可以表示
目录
;这两种类型的“files”由文件结构中的
type字段
来区分。文件系统以完全
相同的方式管理
常规文件和目录文件,除了它
不解释
与常规文件相关联的数据块的内容,而文件系统将目录文件的内容
解释
为该目录中的一系列描述文件和子目录的File structure。
我们的文件系统中的
superblock
含一个File structure(struct Super中的
root字段
)，它保存文件系统
根目录的元数据
。这个目录文件的内容是描述文件系统根目录中的文件和目录的File structure序列。根目录中的任何子目录都可能包含更多表示子-子目录的文件结构，依此类推。
File system
我们依赖于
polling
(轮询)、基于
“programmed I/O”(PIO)
的磁盘访问，并且
不使用磁盘中断
，就很容易在
用户空间
中实现磁盘访问。
x86处理器使用
EFLAGS寄存器
中的
IOPL位
来确定是否允许
保护模式代码
执行特殊的
设备I/O指令
，比如IN和OUT指令。即如果为新创建的环境设置了
env_tf.tf_eflags的IOPL位
，那该环境就能访问磁盘，属于
文件系统环境
。
我们的文件系统将仅限于处理
3GB
或更小的磁盘。我们保留
文件系统environment
的地址空间的一个大的、固定的3GB区域，从
0x10000000 (DISKMAP)
到
0xD0000000 (DISKMAP+DISKMAX)
，作为磁盘的“内存映射”版本。下面是文件系统环境的虚拟内存空间：非常感谢 bysui的图
将整个磁盘读取到内存中要花很长时间，所以只有在发生
页面错误
时，我们才在磁盘映射区域
分配页
和从磁盘
读取相应的块
(
ide_read函数
)。
superblocks在fs/fsformat.c/opendisk初始化。super指向block 1，s_magic=FS_MAGIC，s_nblocks=nblocks，s_root.f_name="/"，s_root.f_type=FTYPE_DIR;
文件系统环境的内存空间
文件系统环境的
0x10000000到0xD0000000
作为
磁盘的内存映射区域
，是
一一对应
的，只是一个块对应磁盘8个扇区。但要注意两点，
一、仅文件系统环境的该区域才是这样，普通环境可不这样，这是
虚拟内存
的强大之处。
二、并不是一开始就把整个磁盘内容都加载进该区域，而是等想要访问文件了，读取对应块时
引发页面错误
，然后通过
bc_pgfault()函数
再去加载内容到内存中，好优秀
文件系统环境对磁盘文件的访问
文件系统环境对磁盘文件的访问其实是对
磁盘文件在内存中的映射内容
进行访问，如果需要对其进行修改，则一定
将修改内容借助ide_*函数刷新回磁盘
，保证磁盘跟内存映射区域的
一致性
。
regular 环境访问磁盘的流程，以open文件为例
普通环境想访问磁盘文件，首先都得找到
文件描述符fd
(在FDTABLE即0xD0000000以上映射着Fd page对应的物理页)，如果是open()，就分配一个fd，如果是其他，就根据fdnum找到fd。
根据fd的内容，选择对应的设备(我认为指的是方式)，
dev
，然后进入dev下的相应处理函数
然后设置好
fsipcbuf
，表明你想请求的操作。然后调用
fsipc()
，找到一个文件系统环境
fsenv
，请求其帮忙，通过
IPC机制
，向其发送操作类型type，以及共享页面fsipcbuf。
fsenv
接收到请求之后，根据
type
进入相应的处理函数，将处理结果又写入到
共享页面fsreq
，再通过
IPC发送结果
给
普通环境
，即完成一次访问磁盘文件
注：如果在处理请求的过程中，对磁盘文件在内存中的映射内容进行了修改，一定要
刷新回磁盘
，借助
ide_*函数
盗用下Gatsby123的图：
具体流程如下：
lib/file.c，在'普通环境下':
open(path, mode)
->fd_alloc(&fd) 每个OpenFIle都有'文件描述符fd'，这里只是在当前env的FDTABLE(0xD0000000)以上，
找一个未映射物理页的虚拟地址，到时候会将OpenFile对应的'Fd page'映射在此处
->fsipcbuf.open设好值，path跟mode
->fsipc(FSREQ_OPEN, fd)
->fsenv 找个文件系统环境来帮忙
->ipc_send(fsenv, type, &fsipcbuf, PTE_P | PTE_W | PTE_U);
想fsenv发送ipc请求，value='FSREQ_OPEN'作为type，
并将fsipcbuf映射的物理页以perm权限映射到fsenv->env_ipc_dstva(即fsreq)处
fs/serv.c: 此时运行的是'文件系统环境'，会在serv.c/umain()下完成serve_init、fs_init、fs_test然后调用serve()
serv()
->req = ipc_recv((int32_t *) &whom, fsreq, &perm);
whom应该指'普通env'，'fsreq'作为dstva，req=type='FSREQ_OPEN'
->serve_open(whom, (struct Fsreq_open*)fsreq, &pg, &perm); 返回0或者error
以fsreq->req_omode模式打开fsreq->req_path处的文件，并将其Fd page (映射好了物理页的虚拟地址)赋给pg
->r=openfile_alloc(&o) 从'opentab[]'中选一个o_fd对应物理页的ref<=1的OpenFile给o，r为其o_fd
->if(设置了O_CREAT位)
->file_create(path, &f) 创建"path"，成功的话f指向被创建的file
->r=walk_path(path, &dir, &f, name)
此时应该r == -E_NOT_FOUND，证明当前环境映射着磁盘的内存区域找不到目标文件
从s_root开始，找到path对应的File，此时'dir!=0'，证明不会出现中间path就找不到的情况，否则直接返回error
所以name肯定指向final path，dir指向其上一级目录。否则返回error
这里的找就是在磁盘的"内存映射区域"(0x10000000~0xD0000000)找
->r=dir_lookup(dir, name, &f) 找到dir下名为name的File，让f指向它，这里应该是f=0，返回r==-E_NOT_FOUND
->dir_alloc_file(dir, &f) 在dir下找一个'free File structure '(其实就是找个'空闲块')给f
->else file_open(path, &f);
->简单调用walk_path(path, 0, pf, 0)只要根据path找到f就行了
->为打开的文件设置好相应的数据。'Openfild->o_file、o_mode、o_fd'等
->回到serve()，调用ipc_send(whom,r,pg,perm) 此时whom是普通env，r是serve_open的结果，pg是Fd page，perm=PTE_P|PTE_U|PTE_W|PTE_SHARE
->sys_page_unmap(0,fsreq)请求处理完了，自然要接触对之前发过来的共享页面的映射fsreq
lib/file.c,这里又是在'普通环境'了，回到fsipc()：
->ipc_recv(NULL,dstva,NULL); //将发过来的Fd page映射在之前分配好的虚拟地址fd上
->回到open()，return fd2num(fd);
感觉总是ipc_send方准备好分配了物理页的共享页面
Fd page是什么时候设置好的？
答：在
openfile_alloc()
函数中，就是是从opentab[]中选出引用值
ref<=1的o_fd页面
，如果ref == 0，就为该OpenFile分配一个Fd page，如果ref==1，就将其Fd page初始化为0
opentab[].o_fd跟普通环境件描述符fd都是在0xD0000000以上，只是一个在文件系统环境的该区域，一个在普通环境的该区域，虚拟内存真是强啊！
由于如果file_create()中，如果中间某一级path就找不到，dir会被设成0，然后返回error，所以我认为整个磁盘上的文件都已经被映射在那块内存区域了，不然应该是从磁盘读取缺少的path，而不是直接返回error
Spawn的流程，以icode.c为例
Spawn(prog, argv)会根据
路径prog
打开文件，从文件中获取二进制映像
elf header
，然后根据elf header完成其
内存空间的加载
。
主要是要设好
agrv[]数组
，这样可以设好子环境的
用户栈
，方便子环境执行时从中获得
所需参数
。
Spawn跟fork的区别是，fork出的子环境跟父环境除了返回值外，
上下文跟内存空间
都几乎
一模一样
。而Spawn出的子环境会从文件中加载
内存空间，跟父环境完全不一样
，而且
eip、esp、用户栈都不一样
，但是
SHARE权限页面
是共享的
进入流程解说
输入
make run-icode
，执行完1386_init()中的那些初始化，创建好
icode环境
，开始make_run -> env_pop_tf -> lib/entry.s/_start ->libmain ->
user/icode.c/umain
，至于为什么可以准确调用user/icode.c/umain，同学说是在ENV_CREATE时，根据对应二进制映像文件
obj/user/icode.img
，
加载到环境内存
中的就是fs/serv.c/umain这个程序，所以可以准确调用到。
同理，后面的文件系统环境运行到libmain后，也可以准确调用到
fs/serv.c/umain
，因为创建时根据
obj/fs/fs.img
加载的就是fs/serv.c/umain。
我们就从进入user/icode.c/umain()开始说起吧。(简单的复制以及输入输出就省略了)
user/icode.c/umain():
->binaryname = "icode";
->fd = open("/motd", O_RDONLY) 具体见上方'普通环境访问磁盘的流程'
->fsipc()->ipc_send()->sched_yield() 让出CPU资源并等待结果
完成FS环境创建，并进入fs/serv.c/umain():
->serve_init() 初始化'opentab[]'数组
->fs_init() 选择一块合适的磁盘，优先第二块磁盘disk 1
->bc_init() 设好bc_pgfault,检查bc的superblock是否可用，将第二个磁盘块(指的FS环境内存空间DISKMAP以上的第二个虚拟页)内容给super
->让super指向diskaddr(1),并check_super()
->让bitmap指向diskaddr(2)，但是bitmap并不只有一个块，JOS中最多可以有24块，然后check_bitmap()
->fs_test() 检查block_alloc、file_open、file_set_size、file_flush、file_get_block、file_rewrite等，本身就是文件系统环境，可以直接访问
->serve()
->ipc_recv()->serve_open()->ipc_send()主要是发回Fd page->sched_yield()->sys_page_unmap()具体见上一个流程
打开文件成功，回到icode环境，Fd page对应的物理页映射在fd上，user/icode.c/umain():
->n = read(fd, buf, sizeof buf-1) 再次向FS环境发送请求，从fd代表的OpenFile保存的文件File中读sizeof(buf-1)个字节到buf
->devfile_read()->fsipc()->ipc_send()->sched_yield()
又切换到FS环境处理read请求。
->serve() 一直在while(1)看是否有ipc_send过来
->ipc_recv()->serve_read()->ipc_send()读出的内容就存在共享页面fsreq中->sched_yield()->sys_page_unmap()
再次回到icode环境，sys_cputs输出读到的内容
->close(fd) // 解除fd上对Fd page的映射
->r = spawnl("/init", "init", "initarg1", "initarg2", (char*)0) 将后面4个参数都存到argv[]中，然后调用spawn(prog,argv)
->spawn("/init",argv) 返回的是生成的子环境的id
->fd = open(prog, O_RDONLY)
->readn(fd, elf_buf, sizeof(elf_buf)) 根据fd读出elf healder
->child = sys_exofork() 创建一个子进程，与父进程有着几乎一样的上下文，状态NOT_RUNNABLE
->r = init_stack(child, argv, &child_tf.tf_esp) 将argv[]放入子环境用户栈中，这也是个充满智慧的函数
->根据elf healder将程序段读入子环境内存空间
->close(fd)
->copy_shared_pages(child) 将父环境中映射权限为SHARE的页面都映射着子环境内存中相同位置。主要是那些文件描述符页
->r = sys_env_set_trapframe(child, &child_tf) 对child_tf做一定的修改后再赋值给envs[child]->env_tf
->设置子环境状态为ENV_RUNNABLE
->icode : exiting
FS环境还在serve()中循环等待ipc_send，所以内核的sched_yield()会选择刚才spawn的'子环境init'运行
我认为elf->e_entry应该直接是 user/init.c/umain()， 因为参数都以及存在栈中了，直接进umain取参数
-> 具体运行见下方Shell的流程
init_stack()真的是一个很有智慧的函数：(以icode中的调用为例)
首先在父环境下选个页面设置好，然后直接把
对应物理页映射
到子环境用户栈页，
间接
实现对子环境内存空间的控制
对用户栈页内容的设置也是充满了智慧，平常参数如果是字符串，只需要
字符串首地址入栈
就行，具体的字符串内容是不用入栈的，但是映射到
子环境用户栈
后，整个内存空间都变了，为了还能
根据首地址找到内容
，所以这里把内容也一起入栈，很优秀
//下面的argv[n]指的是字符串首地址，也是这个栈中对应条目的虚拟地址
argv[2] --> | "initarg2" | <-- USTACKTOP
argv[1] --> | "initarg1" |
argv[0] --> | "init" |
| 0(NULL) |
| argv[2] |
| argv[1] |
addr x --> | argv[0] |
| addr x |
child->esp(往上是出栈) --> | 3 |
为什么我没看到给
磁盘的内存映射区域
赋初始值，却总可以从该区域读到正确的磁盘内容？
答：就是因为
在bc_init
中设置了page fault处理程序
bc_pgfault
，所以当读取
磁盘的内存映射区域
时会引发页面错误，就会及时通过
ide_read()
函数从磁盘读取内容到错误处，这样就解释清了，哈哈哈！
一定要区分文件系统环境的内存空间跟普通环境的内存空间内容是不一样的，都是虚拟内存的强大之处，不要混淆
OpenFile是从opentab[]数组中分配的一个元素，最多只能有1024个OpenFile。用来
保存打开的File的信息
的，o_fileid、o_file等等，不要混淆
Shell的流程。shell是个用户程序，只是有着很多系统调用接口
shell其实就是一个
用户程序
。不停循环，每次将
"$"之后回车之前输入的内容
读到buf，然后
fork()一个子环境
去调用
runcmd(buf)
。而runcmd会把buf中每个
token提取
出来，是word就存入argv[]数组，是操作符完成相应操作，然后
Spawn一个名为argv[0]的子环境
去执行命令。注意，子环境执行期间父环境会一直等待直到该子环境exit后才继续
上回spawn的流程说到进入
user/init.c/umain()
，接着往下看看是如果运行起来Shell的吧，很有意思。
user/init.c/umain(argc, argv): 此时argc=3, argv={ "init", "initarg1", "initarg2"}
->sum(data)、sum(bss) 这个sum有点看不懂，但是知道这是在检验data、bss是否Okey
->close(0) (注释)因为是从内核直接开始运行的，所以还未打开任何文件描述符?
->r = opencons() 打开控制台，对应文件描述符fd=0，并设置fd_dev_id=devcons.dev_id，fd->fd_omode=O_RDWR
->dup(oldfdnum=0,newfdnum=1)
将fd=1关闭，然后将刚分配到fd=0的物理页映射给fd=1，注意完成后fd=0并未关闭
我感觉这里是在把输入输出都定向到控制台上
->fd_lookup(oldfdnum, &oldfd)
->close(newfdnum)
->newfd = INDEX2FD(newfdnum) 找到newfdnum在FDTABLE(0xD0000000)上对应页的虚拟地址
->ova = fd2data(oldfd);nva = fd2data(newfd);在FILEDATA=FDTABLE+32*PGSIZE以上，每个fd都保留有一个数据页，很贴心
->sys_page_map(ova->nva, oldfd->newfd)，把数据页跟文件描述符页都映射给newfd
->while(1) {
r=spawnl("/sh", "sh", (char*)0);为sh设好的栈可读出argc=1, argv={"sh"}，而r则是sh环境id
wait(r); wait就是不停调用sys_yield()直到子环境r状态变为'ENV_FREE'为止
}
很明显，'init环境'调用sys_yield()后，内核选择sh环境，假装从user/sh.c/umain()开始：
user/sh.c/umain(argc, argv): 同样，此时argc=1, argv={"sh"}
->根据argv的内容设置好debug、interactive、echocmds。由于这里argv里只有个"sh"，
所以我认为debug=0, interactive="?"即=1, echocmds=0
->while(1){
->buf = readline("$"); 调用getchar()获取输入，一边存入buf，一边cputchar()，
遇到'\b''\x7f'(ASCII中是DEL)所以这两个是'回退'的意思，遇到'\n''\r'停止
->r = fork() 现在又有了个一模一样的子环境，且同样相当于运行到这里，这个fork()有意思
->很明显还在父环境中，wait(r) 不断sys_yield()等待子进程运行成ENV_FREE才能继续
}
父环境sh被wait(r),父父环境init被wait(sh)，所以现在子环境r开始运行，同样从r=fork()下一句开始
->runcmd(buf) buf此时存着用户从见到"$"开始到输入'\n'或'\r'之前的所有输入
->gettoken(s,0) 主要是依靠四个静态变量np1, np2，c, nc。
这里是取第一个token给np1，剩下的给np2，nc可以是0 < > | w，代表token的类型
->while(1){
->c = gettoken(0, &t); t就等于前一个token，c代表t的类型，np1会是下一个token，np2则是剩下部分
->switch(c)
c==w 代表t是个word存到argv[argc++]
c==< 就再gettoken(0,&t)，将标准输入由0变成名为t的文件
c==> 也再gettoken(0,&t)，将标准输出由1变成名为t的文件
c==| 这个就有点意思，详细说说
->r=pipe(p) 分配两个空文件描述符页，num给p[0]与p[1]，并为两个文件描述符分配同一个数据页(优秀!)
->r = fork()
->将父进程的标准输出设成p[1]，将子进程的标准输入设成p[0]，别忘了p[0]、p[1]有个同一个数据页哦!
如果是父进程，则goto runit，子进程则argc=0,再重新gettoken()
c== 0 代表s中token已经全部取完，goto runit
}
->runit:
->argc=0证明是空命令，直接返回就行，不然补充argv[argc]=0，设好终结位置
->spawn(argv[0], (const char**) argv)
->close_all() 关闭父进程的所有文件描述符
->wait(r) 等待子进程运行结束
->如果child_pipe!=0，证明还只执行完了管道左边部分，接着wait(pipe_child)等待管道右边部分结束
->exit()
然后再去执行spawn出的子环境。等到子环境结束，父环境r也exit()，就会回到sh环境中继续while循环
管道有意思，int p[2]; pipe( p )，会分配两个
文件描述符页
，且
共享一个数据页
shell跟管道可参考我这篇博客