MIT-6.828-JOS 笔记 - Lab 5: File system, Spawn and Shell

本实验将引入一个文件系统、建立文件描述符并支持从磁盘加载程序并运行。

本实验代码：https://github.com/epis2048/MIT_6.828_2018/tree/lab5

一、文件系统预备知识

我们将要实现的文件系统会比真正的文件系统要简单，但是能满足基本的创建，读，写，删除文件的功能。但是不支持多用户权限管理，链接，符号链接，时间戳等特性。

磁盘上的文件系统

大多数Unix文件系统分为inode和data两个区域，而JOS不适用inode，所有文件的元数据存储在direction entry中。
文件和目录逻辑上都是由一系列数据blocks组成，这些blocks分散在磁盘中，文件系统屏蔽blocks分布的细节，提供一个可以顺序读写文件的接口。JOS文件系统允许用户读目录元数据，这就意味着用户可以扫描目录来像实现ls这种程序，UNIX没有采用这种方式的原因是，这种方式使得应用程序过度依赖目录元数据格式。
简单来讲，我们文件系统就只有一个数据结构保存文件，没有索引。

1. Sectors and Blocks

大部分磁盘都是以Sector为粒度进行读写，JOS中Sectors为512字节。文件系统以block为单位分配和使用磁盘。注意区别，sector size是磁盘的属性，block size是操作系统使用磁盘的粒度。JOS的文件系统的block size被定为4096字节。
简单来讲，我们文件系统就只有一个数据结构保存文件，没有索引。

2. Superblocks

文件系统使用一些特殊的block保存文件系统属性元数据，比如block size, disk size, 根目录位置等。这些特殊的block叫做superblocks。
我们的文件系统使用一个superblock，位于磁盘的block 1。block 0被用来保存boot loader和分区表。很多文件系统维护多个superblock，这样当一个损坏时，依然可以正常运行。
简单来讲，磁盘默认512字节是一个扇区，我们系统4096字节一个块，也就是8个扇区一个块。

3. File Meta-data

我们的文件系统使用struct File结构描述文件，该结构包含文件名，大小，类型，保存文件内容的block号。struct File结构的f_direct数组保存前NDIRECT（10）个block号，这样对于10*4096=40KB的文件不需要额外的空间来记录内容block号。对于更大的文件我们分配一个额外的block来保存4096/4=1024 block号。所以我们的文件系统允许文件最多拥有1034个block。
简单来讲，块0我们用了，在前面讲过，块1就是保存了一些磁盘布局，尤其是根目录。中间可能会有一些块用于磁盘恢复，还有位图。

4. Directories versus Regular Files

File结构既能代表文件也能代表目录，由type字段区分，文件系统以相同的方式管理文件和目录，只是目录文件的内容是一系列File结构，这些File结构描述了在该目录下的文件或者子目录。
超级块中包含一个File结构，代表文件系统的根目录。
简单来讲，储存文件我们用 struct File，小于10个块我们直接储存，超过10个块开一个间接块标记那几个块。

5. Directories versus Regular Files

我们的文件系统中的struct File可以表示常规文件或目录;这两种类型的“文件”通过struct File中的类型字段进行区分。文件系统以完全相同的方式管理常规文件和目录文件，除了它不解释与常规文件相关联的数据块的内容，而文件系统将目录文件的内容解释为一系列描述目录中的文件和子目录的struct File。
我们的文件系统中的超级块包含一个struct File（其实struct Super中的根字段），它保存文件系统根目录的元数据。根目录文件的内容是描述位于文件系统根目录下的文件和目录的struct File序列。根目录中的任何子目录可以依次包含表示子子目录的更多的struct File，依此类推。
简单来讲，没啥可讲，够简单了。

二、文件系统

本lab的目标不是实现整个文件系统，而是仅实现某些关键组件。特别是，需要实现将块读入块高速缓存并将其刷新回磁盘;分配磁盘块;将文件偏移映射到磁盘块;并在IPC接口中中实现读，写和打开。

1. Disk Access

到目前为止内核还没有访问磁盘的能力。JOS不像其他操作系统一样在内核添加磁盘驱动，然后提供系统调用。我们实现一个文件系统进程来作为磁盘驱动。
x86处理器使用EFLAGS寄存器的IOPL为来控制保护模式下代码是否能执行设备IO指令，比如in和out。我们希望文件系统进程能访问IO空间，其他进程不能。

Exercise 1
修改env_create()的代码，如果进程的type为文件系统，则给他IO权限。

// kern/env.c
void
env_create(uint8_t *binary, enum EnvType type)
{
struct Env * e;
int r = env_alloc(&e, 0);
if(r < 0){
	panic("env_create: Create Env failed: %e", r);
}
if (type == ENV_TYPE_FS) {
	e->env_tf.tf_eflags |= FL_IOPL_MASK;
}
e->env_type = type;
load_icode(e, binary);
}

2. The Block Cache

在我们的文件系统中，我们将在处理器的虚拟内存系统的帮助下实现一个简单的“缓冲区缓存”（实际上只是块缓存）。块缓存的代码在fs/bc.c中。
我们的文件系统最大支持3GB，文件系统进程保留从0x10000000 (DISKMAP)到0xD0000000 (DISKMAP+DISKMAX)固定3GB的内存空间作为磁盘的缓存。比如block 0被映射到虚拟地址0x10000000，block 1被映射到虚拟地址0x10001000以此类推。
如果将整个磁盘全部读到内存将非常耗时，所以我们将实现按需加载，只有当访问某个bolck对应的内存地址时出现页错误，才将该block从磁盘加载到对应的内存区域，然后重新执行内存访问指令。
简单来讲，我们保留了一个3GB 的内存用来做磁盘映射，因为读取整个磁盘要很长的时间，所以我们就用分页形式。

Exercise 2
补充bc_pgfault()和flush_block()。
bc_pgfault()是FS进程缺页处理函数，负责将数据从磁盘读取到对应的内存。

// fs/bc.c
// LAB 5: you code here:
addr = ROUNDDOWN(addr, PGSIZE);
if ((r = sys_page_alloc(0, addr, PTE_SYSCALL)) < 0){
	panic("bc_pgfault: error when page_alloc!\n");
}
ide_read(blockno * 8, addr, 8);

flush_block()将一个block写入磁盘。flush_block()不需要做任何操作，如果block没有在内存或者block没有被写过。可以通过PTE的PTE_D位判断该block有没有被写过。

// fs/bc.c
// LAB 5: Your code here.
// panic("flush_block not implemented");
addr = ROUNDDOWN(addr, PGSIZE);
int r;
// 如果addr还没有映射过或者该页载入到内存后还没有被写过，不用做任何事
if (!va_is_mapped(addr) || ! va_is_dirty(addr)) return;
// 写回到磁盘
if ((r = ide_write(blockno * BLKSECTS, addr, BLKSECTS)) < 0) {
	panic("flush_block: ide_write(): %e", r);
}
// 清空PTE_D位
if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0) {
	panic("flush_block: sys_page_map: %e", r);
}

fs/fs.c中的fs_init函数是如何使用块缓存的主要例子。在初始化块缓存之后，它将指针存储在super全局变量的磁盘映射区域中。此后，我们可以简单地从struct Super中读取，就像它们在内存中一样，我们的页面错误处理程序将根据需要从磁盘读取它们。

3. The Block Bitmap

fs_init()中已经初始化了bitmap，我们能通过bitmap访问磁盘的block 1，也就是位数组，每一位代表一个block，1表示该block未被使用，0表示已被使用。我们实现一系列管理函数来管理这个位数组。

Exercise 3
完成alloc_block()，该函数搜索bitmap位数组，返回一个未使用的block，并将其标记为已使用。

// fs/fs.c
int
alloc_block(void)
{
// The bitmap consists of one or more blocks.  A single bitmap block
// contains the in-use bits for BLKBITSIZE blocks.  There are
// super->s_nblocks blocks in the disk altogether.

// LAB 5: Your code here.
// panic("alloc_block not implemented");
for (int i = 0; i < super->s_nblocks; i++) { // 遍历
	if (block_is_free(i)) { // 空块
		bitmap[i/32] ^= (1<<(i%32)); // 异或即可
		flush_block(diskaddr(i)); // 刷新缓存
		return i;
	}
}
return -E_NO_DISK;
}

4. File Operations

我们在fs/fs.c中提供了各种函数，以实现解释和管理struct File，扫描和管理目录条目所需的基本功能，并从文件系统的根目录开始遍历以解析绝对路径名。阅读fs/fs.c中的所有代码，并确保您了解每个函数执行的操作。
基本的文件系统操作：

1. file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)：查找f指向文件结构的第filebno个block的存储地址，保存到ppdiskbno中。如果f->f_indirect还没有分配，且alloc为真，那么将分配要给新的block作为该文件的f->f_indirect。类比页表管理的pgdir_walk()。
2. file_get_block(struct File *f, uint32_t filebno, char **blk)：该函数查找文件第filebno个block对应的虚拟地址addr，将其保存到blk地址处。
3. walk_path(const char *path, struct File **pdir, struct File **pf, char *lastelem)：解析路径path，填充pdir和pf地址处的File结构。比如/aa/bb/cc.c那么pdir指向代表bb目录的File结构，pf指向代表cc.c文件的File结构。又比如/aa/bb/cc.c，但是cc.c此时还不存在，那么pdir依旧指向代表bb目录的File结构，但是pf地址处应该为0，lastelem指向的字符串应该是cc.c。
4. dir_lookup(struct File *dir, const char *name, struct File **file)：该函数查找dir指向的文件内容，寻找File.name为name的File结构，并保存到file地址处。
5. dir_alloc_file(struct File *dir, struct File **file)：在dir目录文件的内容中寻找一个未被使用的File结构，将其地址保存到file的地址处。

文件操作：

1. file_create(const char *path, struct File **pf)：创建path，如果创建成功pf指向新创建的File指针。
2. file_open(const char *path, struct File **pf)：寻找path对应的File结构地址，保存到pf地址处。
3. file_read(struct File *f, void *buf, size_t count, off_t offset)：从文件f中的offset字节处读取count字节到buf处。
4. file_write(struct File *f, const void *buf, size_t count, off_t offset)：将buf处的count字节写到文件f的offset开始的位置。

Exercise 4
实现file_block_walk()和file_get_block()。
file_block_walk()在f文件里面找到第filebno块对应的地址，储存到*ppdiskbno，可能在f->f_direct[]里面或者间接块里面，如果我们分配位置设置了，就分配一个。

// fs/fs.c
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
   // LAB 5: Your code here.
   // panic("file_block_walk not implemented");
// 文件块数超出最大值限制
if (filebno >= NDIRECT + NINDIRECT) return -E_INVAL;
// 如果在直接块里面，就直接返回
if (filebno < NDIRECT) {
	*ppdiskbno = &(f->f_direct[filebno]);
}
// 如果在间接块里面
else {
	if (f->f_indirect) {
		*ppdiskbno = &(((uint32_t *)diskaddr(f->f_indirect))[filebno-NDIRECT]);
	}
	else { // 都没有则根据要求判断是否创建
		if (alloc) {
			int r = alloc_block();
			if (r < 0) return -E_NO_DISK;
			f->f_indirect = r; // 间接块号
			memset(diskaddr(f->f_indirect), 0, BLKSIZE); // 初始化0
			flush_block(diskaddr(f->f_indirect)); // 刷新缓存
			*ppdiskbno = &(((uint32_t *)diskaddr(f->f_indirect))[filebno-NDIRECT]);
		}
		else {
			return -E_NOT_FOUND;
		}
	}
}
return 0;
}

file_get_block()设置*blk为在f文件的第fileno的地址,要用到上一个函数。

// fs/fs.c
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
   // LAB 5: Your code here.
   // panic("file_get_block not implemented");
uint32_t *ppdiskbno, blockno;
int r=0; // 首先得知道对应磁盘中的块号是多少，
// 通过这个函数ppdiskbno就是指向对应磁盘块号的地址，也就是*ppdiskbno存的是块号。
if ((r = file_block_walk(f, filebno, &ppdiskbno, true)) < 0)
   	return r;
   if ((*ppdiskbno) == 0) { // 块号是 0 说明还没有分配块
   	if ((r = alloc_block()) < 0) // 分配一个块
       	return r;
       blockno = r;
       *ppdiskbno = blockno; // 指向那个块
       flush_block(diskaddr(*ppdiskbno)); // 刷新缓存
   }
   if (blk) {
   	*blk = (char *)diskaddr(*ppdiskbno); // 块号在磁盘中的地址 是*blk存的是虚拟地址指针
}
return 0;
}

5. The file system interface

到目前为止，文件系统进程已经能提供各种操作文件的功能了，但是其他用户进程不能直接调用这些函数。我们通过进程间函数调用(RPC)对其它进程提供文件系统服务。
本质上RPC还是借助IPC机制实现的，普通进程通过IPC向FS进程间发送具体操作和操作数据，然后FS进程执行文件操作，最后又将结果通过IPC返回给普通进程。

Exercise 5
实现serve_read()，这是服务端也就是FS进程中的函数。直接调用更底层的fs/fs.c中的函数来实现。

// fs/serv.c
// Lab 5: Your code here:
struct OpenFile * o;
// 通过fileid找到Openfile结构
int r = openfile_lookup(envid, req->req_fileid, &o);
if (r < 0) return r;
// 调用fs.c中函数进行真正的读操作
if ((r = file_read(o->o_file, ret->ret_buf, req->req_n, o->o_fd->fd_offset)) < 0)
	return r;
o->o_fd->fd_offset += r;
return r;

Exercise 6
实现serve_write()和devfile_write()。
serve_write()：与read类似。

// fs/serv.c
// LAB 5: Your code here.
// panic("serve_write not implemented");
struct OpenFile *o;
int r;
if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0) {
	return r;
}
if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0)
	return r;
int total = 0;
while (1) {
	r = file_write(o->o_file, req->req_buf, req->req_n, o->o_fd->fd_offset);
	if (r < 0) return r;
	total += r;
	o->o_fd->fd_offset += r;
	if (req->req_n <= total)
		break;
}
return total;

devfile_write()：客户端进程函数，包装一下参数，直接调用fsipc()将参数发送给FS进程处理。

// lib/file.c
// LAB 5: Your code here
// panic("devfile_write not implemented");
fsipcbuf.write.req_fileid = fd->fd_file.id;
fsipcbuf.write.req_n = n;
memmove(fsipcbuf.write.req_buf, buf, n);
return fsipc(FSREQ_WRITE, NULL);

三、加载进程

lib/spawn.c中的spawn()创建一个新的进程，从文件系统加载用户程序，然后启动该进程来运行这个程序。spawn()就像UNIX中的fork()后面马上跟着exec()。
spawn()：做了以下一系列动作：

1. 从文件系统打开prog程序文件
2. 调用系统调用sys_exofork()创建一个新的Env结构
3. 调用系统调用sys_env_set_trapframe()，设置新的Env结构的Trapframe字段（该字段包含寄存器信息）。
4. 根据ELF文件中program herder，将用户程序以Segment读入内存，并映射到指定的线性地址处。
5. 调用系统调用sys_env_set_status()设置新的Env结构状态为ENV_RUNNABLE。

Exercise 7
实现sys_env_set_trapframe()系统调用。
sys_env_set_trapframe()系统调用函数，供spawn初始化新创建的进程状态。

// kern/syscall.c
static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{
// LAB 5: Your code here.
// Remember to check whether the user has supplied us with a good
// address!
// panic("sys_env_set_trapframe not implemented");
struct Env * e;
if (envid2env(envid, &e, 1) < 0) {
	return -E_BAD_ENV;
}
e->env_tf = *tf;
e->env_tf.tf_cs |= 0x3; // 修改一下提示要求的值
e->env_tf.tf_eflags &=  (~FL_IOPL_MASK); // 普通进程不能有IO权限
e->env_tf.tf_eflags |= FL_IF;
return 0;
}

增加系统调用时候记得在syscall中添加他。

// kern/syscall.c
	case SYS_env_set_trapframe:
		ret =  sys_env_set_trapframe((envid_t)a1,(struct Trapframe*)a2);
		break;

Sharing library state across fork and spawn

UNIX文件描述符是一个大的概念，包含pipe，控制台I/O。在JOS中每种设备对应一个struct Dev结构，该结构包含函数指针，指向真正实现读写操作的函数。
lib/fd.c文件实现了UNIX文件描述符接口，但大部分函数都是简单对struct Dev结构指向的函数的包装。
我们希望共享文件描述符，JOS中定义PTE新的标志位PTE_SHARE，如果有个页表条目的PTE_SHARE标志位为1，那么这个PTE在fork()和spawn()中将被直接拷贝到子进程页表，从而让父进程和子进程共享相同的页映射关系，从而达到父子进程共享文件描述符的目的。

Exercise 8
修改lib/fork.c中的duppage()，使之正确处理有PTE_SHARE标志的页表条目。

// lib/fork.c
// 增加一句if即可
static int
duppage(envid_t envid, unsigned pn)
{
int r;
// LAB 4: Your code here.
void* vaddr=(void*)(pn*PGSIZE);
if(uvpt[pn]&PTE_SHARE){ // Lab5: 对于标识为PTE_SHARE的页，拷贝映射关系，并且两个进程都有读写权限
	if((r = sys_page_map(0, vaddr, envid, vaddr, uvpt[pn] & PTE_SYSCALL)) < 0)return r;
}
else if((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)){
	if ((r = sys_page_map(0, vaddr, envid, vaddr, PTE_P | PTE_U | PTE_COW)) < 0)
           return r;//映射当前页为写时符合
       if ((r = sys_page_map(0, vaddr, 0, vaddr, PTE_P | PTE_U | PTE_COW)) < 0)
           return r;//把自己当前页页标记成写时复制。
}
else if((r = sys_page_map(0, vaddr, envid, vaddr, PTE_P | PTE_U)) < 0) {
	return r;//如果当前页已经是写时复制  就不需要更改了
}
//panic("duppage not implemented");
return 0;
}

完成函数copy_shared_pages()，将共享页的映射复制到子地址空间。

// lib/spawn.c
static int
copy_shared_pages(envid_t child)
{
// LAB 5: Your code here.
// 直接暴力找即可
int r;
for (uintptr_t addr = 0; addr < UTOP; addr += PGSIZE){
	if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) &&
			(uvpt[PGNUM(addr)] & PTE_U) && (uvpt[PGNUM(addr)] & PTE_SHARE)) {
		if ((r = sys_page_map(0, (void*)addr, child, (void*)addr, (uvpt[PGNUM(addr)] & PTE_SYSCALL))) < 0)
			return r;
	}
}
return 0;
}

四、键盘接口

QEMU一直在显示我们在CGA显示器和串行端口的输出内容，但到目前为止，我们只能在内核监视器中输入。在QEMU中，在图形窗口中的输入显示为从键盘输入到JOS，从控制台的输入显示为串行端口上的字符。kern/console.c包含键盘和串行驱动程序，从lab1开始内核监视器就一直在使用，但现在你需要将它们附加到系统的其余部分。

Exercise 9
在trap_dispatch()中添加处理键盘事件的代码即可。

// kern/trap.c
// Handle keyboard and serial interrupts.
// LAB 5: Your code here.
if (tf->tf_trapno == IRQ_OFFSET + IRQ_KBD) {
	// lapic_eoi();
	kbd_intr();
	return;
}

if (tf->tf_trapno == IRQ_OFFSET + IRQ_SERIAL) {
	// lapic_eoi();
	serial_intr();
	return;
}

五、Shell

运行make run-icode或make run-icode-nox命令。这将运行您的内核并启动user/icode。
你应该能够运行以下命令：

echo hello world | cat
cat lorem |cat
cat lorem |num
cat lorem |num |num |num |num |num
lsfd

Exercise 10
目前shell还不支持IO重定向，修改user/sh.c中的runcmd()，增加该功能。

// user/sh.c
		// LAB 5: Your code here.
		// panic("< redirection not implemented");
		if ((fd = open(t, O_RDONLY)) < 0) {
			cprintf("open %s for write: %e", t, fd);
			exit();
		}
		if (fd != 1) {
			dup(fd, 0);
			close(fd);
		}
		break;

总结

本次实验主要干了以下几件事：

1. 构建文件系统，引入一个文件系统进程的特殊进程，该进程提供文件操作的接口。具体实现在fs/bc.c，fs/fs.c，fs/serv.c中。
2. 建立RPC机制，客户端进程向FS进程发送请求，FS进程真正执行文件操作。客户端进程的实现在lib/file.c，lib/fd.c中。
3. 更高级的抽象，引入文件描述符。通过文件描述符这一层抽象就可以将控制台，pipe，普通文件，统统按照文件来对待。
4. 支持从磁盘加载程序并运行。实现spawn()，该函数创建一个新的进程，并从磁盘加载程序运行，类似UNIX中的fork()后执行exec()。