File system preliminaries

jos实现的文件系统要比大多数文件系统简单（包括xv6），主要在分层目录结构的管理下实现文件的增删查改。
jos操作系统是单用户的，不提供多用户的保护。因此，jos文件系统不支持UNIX文件所有权和权限的概念，不支持硬链接、符号链接、时间戳或特殊设备文件。

On-Disk File System Structure

大多数unix文件系统将磁盘空间分为两种区域类型：inode regions和data regions。unix文件系统为每个文件分配一个inode，文件的inode保存了文件的关键元数据（meta-data）：如stat属性和指向data blocks的指针。data regions被分为8KB或更大的数据块data blocks，用于保存文件数据和目录元数据（directory meta-data）。目录项directory entries包含文件名和指向inodes的指针。假如有多个目录项指向了同一个文件的inodes，说明该文件被hard-linked。由于jos文件系统不支持hard links，所以不需要这种级别的“间接寻址”，jos文件系统不会使用inodes，而是在描述文件的相关目录项中保存文件/子目录的元数据。
文件和目录在逻辑上都会关联到一系列data blocks，这些data blocks可能是分散在磁盘上，就好比虚拟地址空间关联到一系列分散的物理页。文件系统隐藏了数据块分布的细节，提供在文件内任意偏移处读写字节序列的接口。对于创建和删除文件等操作，文件系统内部处理了所有相关的目录修改。jos文件系统允许用户进程直接读取目录元数据（e.g., read），用户进程可以自己实现目录浏览（e.g. 实现ls），而不必依赖于特定的文件系统调用接口。这种方法的缺点是应用程序依赖于目录元数据的格式，一旦修改了文件系统的内部布局，应用程序需要作出修改或重新编译。

Sectors and Blocks

大多数磁盘无法支持字节粒度的读写，取而代之的是sector粒度的读写，通常是512字节。文件系统分配和使用磁盘存储的单元是block。sector和block的术语区别是：sector size是磁盘硬件的一个属性，block size则是操作系统使用磁盘所使用的一个概念。文件系统的block size必须是sector size的整数倍。
xv6将block size定义为512字节。由于存储空间越来越便宜，而且更大粒度有利于存储管理，所以大多数现代文件系统使用了更大的block size。jos文件系统使用了4096字节大小的block size，方便于匹配页大小。

Superblocks

文件系统通常在磁盘某个容易寻找的位置保留特定的磁盘块，用于存储文件系统的元数据描述属性。比如：block size、disk size、查找root目录所需的元数据、文件系统上次挂载时间、上次检查磁盘错误的时间等。这些特殊的磁盘块称为superblocks。
jos文件系统有一块superblock，位于磁盘的block 1，它的定义是inc/fs.h的struct Super。block 0用于保留启动引导程序和分区表，所以文件系统没有使用它。许多现代的文件系统维护了多个superblocks，并在磁盘的多个位置进行复制，一旦某一个损坏了或其他原因，就可以使用下一个superblock。

磁盘布局如下：
disk布局

File Meta-data

inc/fs.h的struct File定义了描述文件的元数据布局。jos的文件元数据包括文件名、大小、类型（常规文件还是目录）、指向blocks的指针。jos没有inodes，所以文件元数据直接存储在磁盘的目录项中。不像其他文件系统，无论是在磁盘上还是在内存上，jos使用File数据结构来代表文件元数据。

File元数据的格式如下：

struct File的f_direct数组的前十个成员存储了文件前10个blocks的block numbers，这10个blocks被称为文件的direct blocks。对于小于10*4096 = 40KB的文件，意味着该文件所有blocks的block numbers将直接在File结构上直接匹配。对于更大的文件，则另外分配一个磁盘块以保存4096/4 = 1024个blocks的block number，该磁盘块称为文件的indirect block。因此，文件大小的上限是1034 blocks，大于4M。为了支持更大的文件，其他文件系统通常支持double-indirect和triple-indirect blocks。

Directories versus Regular Files

jos的File结构体既可以代表常规文件，也可以代表目录。文件系统以同样的方式管理常规文件和目录文件，除了：文件系统不解析常规文件相关联的数据块内容，但会将目录文件的内容解析为一系列的File结构，用于描述目录中的文件和子目录。
superblock包含了一个File结构（struct Super的root区域），用于保存root目录的元数据。该目录文件的内容是一系列File结构，用于描述root目录中的文件和子目录。

The File System

我们主要实现以下关键功能：读取blocks到block cache中、刷新block cache到磁盘中、分配磁盘块、映射文件偏移到磁盘块、实现read/write/open的IPC接口。

Disk Access

操作系统需要能够访问磁盘，传统的monolithic操作系统策略是在内核中添加IDE磁盘驱动并且提供文件系统访问磁盘所需的系统调用接口，而jos的做法是将IDE磁盘驱动作为用户级别文件系统进程的一部分。需要对内核作轻微修改，确保文件系统进程拥有实现磁盘访问所需的相关特权。
依赖轮询和基于可编程输入输出（”programmed I/O” - PIO）的磁盘访问，可以很方便在用户空间实现磁盘访问。jos不使用中断来实现磁盘访问，虽然在用户模式下也可以实现以中断驱动的设备驱动程序，但是内核必须识别设备中断并分配到正确的用户模式进程，难度更大。
x86处理器使用了EFLAGS的IOPL位来决定是否允许保护模式代码使用device I/O指令（如IN和OUT指令）。device I/O指令需要访问的所有IDE磁盘寄存器都在x86的I/O space上而不是被内存映射，为了允许文件系统可以访问这些寄存器，我们只需要提供I/O privilege即可。EFLAGS的IOPL位使得内核可以简单地使用”all-or-nothing”方法来控制用户代码是否可以访问I/O space。在jos中，我们将文件系统实现为一个用户进程，其他进程使用IPC与文件系统进程通信，并且只允许文件系统进程访问I/O space，但不允许其他进程访问I/O space。

I/O space请参考 I/O space。

1	Exercise 1. i386_init使用了ENV_TYPE_FS来标识文件系统进程，修改env.c的env_create函数，使其能根据ENV_TYPE_FS向文件系统进程给出相关的I/O权限。

//env.c的env_create函数

void
env_create(uint8_t *binary, enum EnvType type)
{
	// LAB 3: Your code here.  
	struct Env *newEnv;
	//Allocates a new env 
	int i = env_alloc(&newEnv,0);
	if(i<0) panic("env_create");
	//loads the named elf binary into
	load_icode(newEnv,binary);
	//set env_type
	newEnv->env_type = type;
	
	// If this is the file server (type == ENV_TYPE_FS) give it I/O privileges.
	// LAB 5: Your code here.
	if (type == ENV_TYPE_FS){ 
		// Give I/O privileges while in file environment. 
		newEnv->env_tf.tf_eflags |= FL_IOPL_MASK;
	}
}

1	Question. 是否需要对内核作出什么修改，确保在进行进程切换时相关的I/O权限设置能够正常地保存和恢复？

不需要。进程切换时硬件会自动保存elfags，而在执行新进程时，env_pop_tf的iret指令会恢复eflags。

本实验的GNUmakefile将obj/kern/kernel.img作为disk 0的镜像，将obj/fs/fs.img作为disk 1的镜像。在本实验中，文件系统只能访问disk 1，而disk 0用于启动内核。
disk 0,disk 1

Challenge! JOS目前用的是最简单的PIO（Programming I/O）方式与磁盘交互。请实现中断驱动的IDE磁盘访问（可借助DMA（直接存储器存取））。可以考虑该设备驱动移植到内核中，或者移植到用户空间中、与文件系统进程在一块，或者移植到单独的进程中。

???

The Block Cache

jos将借助处理器的虚拟内存实现一个简单的buffer cache（block cache），见fs/bc.c。
jos文件系统能够处理的磁盘大小被限制在3GB以内。文件系统进程的地址空间[DISKMAP,DISKMAP+DISKMAX)，即[0x10000000,0xD0000000)被保留，用于磁盘的内存映射，如：block 0映射到0x10000000，block 1映射到0x10001000。fs/bc.c的diskaddr函数实现了磁盘块到虚拟地址的映射。
由于文件系统进程的虚拟地址空间完全独立于其他进程，且文件系统进程唯一要完成的工作是实现文件访问，所以通过上述方式保留大部分进程地址空间的做法是合理的；但是对于32位机子上真正实现的文件系统而言，上述方式并不合适，因为现代磁盘大于3G。不过，类似的buffer cache管理方法仍然适用于64位地址空间的机器。
为了避免将整个磁盘读取内存，jos实现了一种请求分页demand paging的形式，当在某个磁盘映射区域发生页错误时，分配相关的页并且读取相关的block。

Exercise 2. 实现fs/bc.c的bc_pgfault和flush_block函数。
bc_pgfault用于在页错误时从磁盘中加载页，注意给定的addr可能没有对齐block边界、ide_read操作的是sectors而不是blocks。
flush_block函数根据需要将block写入到磁盘。如果block没有在block cache中（该页没被映射）或者block不是dirty的，flush_block函数什么都不做。
jos将使用VM hardware来追踪一个磁盘块自从上次读取或写入磁盘之后是否被修改过。使用PTE_D标志位标记block是否dirty。处理器写页时，设置PTE_D位；将block写入到磁盘后，清除PTE_D位。

//fs/bc.c的bc_pgfault
// Allocate a page in the disk map region, read the contents
	// of the block from the disk into that page.
	// Hint: first round addr to page boundary. fs/ide.c has code to read
	// the disk.
	//
	// LAB 5: you code here:
	addr = ROUNDDOWN(addr, PGSIZE);
	if ((r = sys_page_alloc(0, addr, PTE_P|PTE_U|PTE_W)) < 0)
		panic("in bc_pgfault, sys_page_alloc: %e", r); 
	if ((r = ide_read(blockno*BLKSECTS, addr, BLKSECTS)) < 0)
		panic("in bc_pgfault, ide_write: %e", r);


	// Clear the dirty bit for the disk block page since we just read the
	// block from disk
	if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
		panic("in bc_pgfault, sys_page_map: %e", r);

注意：flush_block函数的参数是文件系统进程中映射到磁盘块的虚拟地址。

//fs/bc.c的flush_block
	addr = ROUNDDOWN(addr, PGSIZE);
	int r; 
	if(va_is_mapped(addr) && va_is_dirty(addr)){
		if ((r = ide_write(blockno*BLKSECTS, addr, BLKSECTS)) < 0)
			panic("in flush_block, ide_write: %e", r);
		if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
			panic("in flush_block, sys_page_map: %e", r);
	}

fs/fs.c的fs_init是使用block cache的一个例子。初始化block cache之后（设置页错误处理函数，尝试读取super block的映射内存，该动作会导致页错误并最终读取super block到内存中），fs_init函数将全局结构体指针变量super指向了磁盘disk 1的内存映射区域，之后就可以读取super结构体。

Challenge! 一旦block出错，block cache将不会移除相应内容，并且会永远保存在内存中。请给block cache添加回收策略。使用PTE_A访问位，对任何页的访问，硬件都会设置该位。

1
2
3

???
包括bc_pgfault检查block是否为空的原因？
http://wenku.baidu.com/link?url=oANF8V6KZIkGoabt_gkRjWaqoq1nkOq9U7XPMxHRVaeSXjMubzS8I5bNzDCnEYNli0BPrbs0Zc0OJ7vDHBVPnsj8YZ1BHELOSOWWEI0J64i

The Block Bitmap

fs_init设置了bitmap指针指向block 2的起始位置（但不一定就是说只有block 2被用于block map），bitmap是一个uint32_t *类型的指针，用于判断磁盘块是否已被分配使用，每一个bit位代表一个block，置0代表对应的block已被用。在fs被制成镜像时已经默认将block 0、block 1以及被用于bitmap的块对应的bit位置0。

Exercise 3. 实现alloc_block，在bitmap中查找可用的block，一旦找到，更新对应的bit位，并将该bit位所在的bitmap block更新到磁盘中（注意不一定是block 2），返回对应的block number。

//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");
	uint32_t i;  
	for (i = 0; i < super->s_nblocks; i++){
		if(bitmap[i/32] & 1<<(i%32)){
			bitmap[i/32] &= ~(1<<(i%32));
			flush_block((void *) &bitmap[i / 32]);
			return i;
		}
	}
	return -E_NO_DISK;
}

File Operations

fs/fs.c提供了一系列函数用于解析和管理File结构、浏览和管理目录文件项、由根目录开始解析一个绝对路径等。

1	Exercise 4. 完成file_block_walk和file_get_block函数。

file_block_walk函数的原型是file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)，指定File f和该文件的某个逻辑block number，在f_direct[NDIRECT]或f_indirect对应的间接块中寻找对应存储磁盘block number的项，将该项地址存储到ppdiskbno，如果alloc为true则允许创建间接块（并清0）。
file_get_block函数的原型是file_get_block(struct File *f, uint32_t filebno, char **blk)，指定File f和该文件的某个逻辑block number，在f_direct[NDIRECT]或f_indirect对应的间接块中找到逻辑block number对应的磁盘block存储位置pdiskbno，如果该位置数据为空，则分配一个新的磁盘block并将磁盘block number存到pdiskbno上。将新分配的磁盘block对应的虚拟地址存储到blk中。注意到：每个磁盘块都有对应的虚拟地址，但是此时新分配的磁盘块并未读入到内存中。

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{ 
	int r;
	if(filebno < NDIRECT){
		*ppdiskbno = &f->f_direct[filebno];
		return 0;
	}
	filebno -= NDIRECT;

	if(filebno < NINDIRECT){
		if(!f->f_indirect){
			if (!alloc) return -E_NOT_FOUND;
			//alloc indirect block
			if((r=alloc_block()) < 0) return r;//-E_NO_DISK
			f->f_indirect = r;
			memset(diskaddr(f->f_indirect),0,BLKSIZE);
		} 
		*ppdiskbno = &(((uint32_t *)diskaddr(f->f_indirect))[filebno]);
		return 0;
	}
	return -E_INVAL;
}

int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{ 
	int r;
	uint32_t *pdiskbno;
	//ok to alloc indirect block
	if((r = file_block_walk(f,filebno,&pdiskbno,true)) < 0) return r;
	if(pdiskbno == NULL || *pdiskbno == 0){ // target block hasnot been allocated
		if((r=alloc_block()) < 0) return r;//-E_NO_DISK
		*pdiskbno = r;
	}
	*blk = (char *)(diskaddr(*pdiskbno));
	return 0;
}

Challenge! 如果某些文件操作执行一半的时候，由于崩溃或重启可能导致文件系统损坏。尝试实现软更新或日志文件系统，使得文件系统损坏是可恢复的。

???

The file system interface

客户端进程不能直接调用文件系统进程的函数，而是通过远程过程调用（RPC - remote procedure call）的形式，jos的RPC基于IPC机制。以读取文件为例，RPC过程如下：

      Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

read根据文件描述符号找出对应的文件描述符，然后将请求分配给正确的设备读取函数devfile_read（可以有更多的设备类型如管道）。devfile_read负责构造ipc请求参数，并调用fsipc函数发送ipc请求，解压返回结果并返回。fsipc函数负责发送ipc请求并接收响应结果。
文件系统服务代码为fs/serv.c。在serve函数循环体中，阻塞等待接收文件操作ipc请求，并分发到对应的处理函数如serve_read，然后将处理结果通过ipc回送。serve_read根据请求中的文件信息寻找对应的OpenFile结构，然后调用file_read函数读取磁盘文件，并更新文件偏移。
jos的ipc允许发送一个32-bit数和一个共享页地址。客户端发送给文件系统服务端的请求中，使用了32-bit数来传递请求类型，并将请求参数存放在union Fsipc中，该结构的数据存于ipc共享页中。在客户端进程中，固定的共享地址是fsipcbuf；在服务端进程中，固定将接收的共享页映射到fsreq(0x0ffff000)。
文件系统进程使用ipc回送结果，使用了32-bit数来传递返回码。FSREQ_READ和FSREQ_STAT会返回数据，数据将写到共享页中。进行文件读取时，客户端进程发送buffer映射页，ipc send会将该页映射到文件系统进程中，文件系统填充该页后，发送执行结果到客户端，并解除映射。文件系统进程不需要将映射页发送给客户端，因为两者已经共享内存了。而对于FSREQ_OPEN，它会向客户端共享一个新的“Fd page”，该文件描述符页地址会作为ipc结果返回。

ipc可支持并发访问文件系统，文件系统进程每次ipc recv时阻塞，假设有多个进程并发向文件系统发送请求，由于内核锁的原因，某个时刻只能有一个进程导致进入内核模式且对文件系统进程的阻塞状态进行解除；等执行下一个进程导致进入内核模式时，文件系统已经不再是阻塞状态了，因此后续所有进程都需要循环尝试ipc send直到文件系统进程再次阻塞。文件系统进程处理完一个进程的请求之后才会再次陷入阻塞。
注意到：文件操作涉及的ipc调用时，可能会出现客户端调用ipc_recv并指定期望接收到响应页的虚拟地址，而文件系统进程则是根据情况返回响应页虚拟地址或0。如果客户端指定接收的虚拟地址，文件系统进程返回的地址却为0，我们会在ipc_send中将值为0的地址重新设为一个标志”no page”的特定值，但在sys_ipc_try_send中我们又尝试对发送的地址进行页对齐检查。因此，鉴于以上情况，标志”no page”的特定值必须页对齐，可设为KERNBASE。

1	Exercise 5. 实现fs/serv.c的serve_read。serve_read调用file_read函数读取磁盘文件，serve_read本身只需要提供文件读取的RPC接口。

int
serve_read(envid_t envid, union Fsipc *ipc)
{
	struct Fsreq_read *req = &ipc->read;
	struct Fsret_read *ret = &ipc->readRet;

	if (debug)
		cprintf("serve_read %08x %08x %08x\n", envid, req->req_fileid, req->req_n);

	// Lab 5: Your code here:
	int r;
	struct OpenFile *o;
	if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0)
		return r;
	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;
}

1	Exercise 6. 实现fs/serv.c的serve_write、lib/file.c的devfile_write。

// lib/file.c的devfile_write

static ssize_t
devfile_write(struct Fd *fd, const void *buf, size_t n)
{
	// Make an FSREQ_WRITE request to the file system server.  Be
	// careful: fsipcbuf.write.req_buf is only so large, but
	// remember that write is always allowed to write *fewer*
	// bytes than requested.
	// LAB 5: Your code here
	//panic("devfile_write not implemented");
	uint32_t max = PGSIZE - (sizeof(int) + sizeof(size_t));//see fs.h
	if (n > max) n = max;

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

//fs/serv.c的serve_write

// Write req->req_n bytes from req->req_buf to req_fileid, starting at
// the current seek position, and update the seek position
// accordingly.  Extend the file if necessary.  Returns the number of
// bytes written, or < 0 on error.
int
serve_write(envid_t envid, struct Fsreq_write *req)
{
	if (debug)
		cprintf("serve_write %08x %08x %08x\n", envid, req->req_fileid, req->req_n);

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

Spawning Processes

lib/spawn.c用于创建新进程（设置进程内核空间部分的页目录、复制父进程的trapframe等，但没有映射用户地址空间），设置子进程的trapframe（如修改eip入口为程序入口），初始化子进程用户栈（分配空间、存储传递的参数），从文件系统加载程序文件到新进程中（分配新物理页存储），然后让子进程开始执行该程序。spawn类似于UNIX的fork，在子进程中直接跟进exec。

1
2

Exercise 7. spawn函数需要设置子进程的trapframe。实现sys_env_set_trapframe系统调用，需要检查给出的trapframe地址是否可写，并且需要确保子进程执行期间能够触发中断。
注意到：系统调用过程中传递struct Trapframe *地址的方式是调用前先转换为uint32_t类型，调用后再转换为struct Trapframe *。

static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{ 
	struct Env *e; 
	// check whether the current environment has permission to set envid's trapframe. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true);
	if(r<0) return r;//-E_BAD_ENV 
	// check whether the user has supplied us with a good address!
	user_mem_assert(e, tf, sizeof(struct Trapframe), PTE_U | PTE_W);//see in kern/pmap.c
	e->env_tf = *tf;
	// Enable interrupts while in user mode. 
	e->env_tf.tf_cs = GD_UT | 3;
	e->env_tf.tf_eflags |= FL_IF;
	return 0;
}

1	Challenge! 实现unix形式的exec。

xv6创建子线程并执行新程序的流程大致是：1、用户态调用fork创建子进程，包括复制物理页。2、用户态执行用户子进程，调用exec尝试执行新程序。3、内核态读取新程序内容，映射到新的地址空间中。4、内核态更换子进程的地址空间，释放旧地址空间。
jos使用spawn创建子线程并执行新程序的流程大致是：1、用户态spawn创建子线程，只设置进程内核空间部分的页目录、复制父进程的trapframe等，但没有映射用户地址空间。2、用户态spawn读取程序文件到子进程地址空间中（调用系统调用函数分配、映射物理页）。3、用户态spawn设置子进程用户栈和trapframe（包括执行入口），调用系统调用函数更新子进程trapframe。4、用户态spawn设置子进程为可执行。
jos使用exec创建子线程并执行新程序的流程大致是：1、用户态exec调用fork创建子线程，地址空间映射为写时复制。2、用户态exec读取程序文件到子进程地址空间中，但注意应该是临时的空间（如段地址都加上一段临时位移）。3、用户态exec设置子进程用户栈和trapframe（包括执行入口），调用系统调用函数更新子进程trapframe。4、用户态exec调用系统调用函数更换地址空间映射。5、用户态exec设置子进程为可执行。（此流程的正确性待验证）

1	Challenge! 实现mmap-style的内存映射文件，修改spawn，支持直接从ELF镜像文件中映射物理页。

unix文件描述符是一个综合概念，包括文件、管道、console I/O等设备类型。在jos中，每一个设备类型都有相关联的struct Dev，以及读写相关的函数指针。每一个struct Fd指明了它的设备类型，lib/fd.c的大多数函数只是负责分发处理函数到对应的struct Dev。
lib/fd.c同时负责维护每个应用进程的文件描述符表区域，该区域从FSTABLE开始，每个文件描述符对应一个页，一个进程一次最多可以打开32个文件描述符。当且仅当文件描述符被使用时，其相关的文件描述符表页才被映射。每个文件描述符还有一个可选的数据页，从FILEDATA地址开始。
我们希望通过fork和spawn来共享文件描述符状态，但是文件描述符状态是保存在用户空间中的。目前，fork将内存映射为写时复制，文件描述符状态会被复制而不是共享（意味着进程不能seek这些不是由它们本身打开的文件，也不能使用管道）；spawn则完全不处理这些相关内存，因此创建的新进程没有打开任何文件描述符。
因此，我们将标记特定部分的内存区域是共享的。采取的方法是使用页表项中的一个未使用位（如PTE_COW的做法一样）。具体使用的位是定义于inc/lib.h的PTE_SHARE位，Intel和AMD保留了三个软件可用的PTE位，这是其中之一。一旦页表项设置了PTE_SHARE位，则fork和spawn需要直接复制物理页到子进程中。

1	Exercise 8. 修改lib/fork.c的duppage和lib/spawn.c的copy_shared_pages，实现PTE_SHARE。

static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
	//panic("duppage not implemented"); 
	void *addr = (void *)(pn*PGSIZE);
	if ( (uvpt[pn] & PTE_SHARE) == PTE_SHARE ) { 
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, uvpt[pn] & PTE_SYSCALL)) < 0)
			panic("sys_page_map: %e\n", r);
	} else if( (uvpt[pn] & PTE_W) == PTE_W || 
	    (uvpt[pn] & PTE_COW) == PTE_COW){ 
 		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
 		if ((r = sys_page_map(0, (void *)addr, 0, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
	}else{
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U)) < 0){
			panic("sys_page_map: %e", r);
 		}
	}
	return 0;
}

static int
copy_shared_pages(envid_t child)
{
	// LAB 5: Your code here. 
	unsigned addr;
	int r;
	for (addr = 0; addr < USTACKTOP; addr += PGSIZE){
		if ((uvpd[PDX(addr)] & PTE_P) == PTE_P
			&& (uvpt[PGNUM(addr)] & PTE_SHARE) == PTE_SHARE
		    && (uvpt[PGNUM(addr)] & PTE_U) == PTE_U) {
		    if ((r = sys_page_map(0, (void *)addr, child, (void *)addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
				panic("sys_page_map: %e\n", r);
		} 
	}
	return 0;
}

注意：user/testpteshare.c中先在父进程的0xA0000000上分配页并设为共享页，然后调用fork创建子进程。在lab4中，我们映射的地址范围是[UTEXT,end[])，然而在user/testpteshare.c这种情况中，0xA0000000地址是大于end的，所以该共享页不会被映射到子进程中，后续子进程往0xA0000000写入数据会造成页错误，但是该页没被设为写时复制，会直接panic。因此，我们需要修正映射的地址范围，改为[0,USTACKTOP)，但需要判断是否有对应的页目录项和页表项。

The keyboard interface

QEMU显示输出到CGA和串行口，但目前为止我们只在嵌入内核监控的时候进行输入。在QEMU图形窗口中的键入表现为键盘键入，在控制台的键入表现为串行口的特性。kern/console.c包含了内核监控所使用的键盘和串行驱动。

1	Exercise 9. 在kern/trap.c中，调用kbd_intr处理IRQ_OFFSET+IRQ_KBD中断，调用serial_intr来处理IRQ_OFFSET+IRQ_SERIAL中断。

lib/console.c实现了控制台input/output文件类型，当控制台文件类型消耗缓冲区的时候（drains the buffer），kbd_intr和serial_intr将最新读取的输入填充到一个缓冲区中。（控制台文件类型默认被stdin/stdout使用，除非用户对其重定向）

The Shell

user/icode调用spawn执行init，init程序将控制台设为文件描述符0和1，然后调用spawn执行shell。注意到库函数cprintf直接向控制台输出，没有借助任何文件描述符代码。这种做法有利于debug但不利于使用管道与其他程序通信。使用类似fprintf(1, “…”, …)的形式向特定的文件描述符进行输出。printf(“…”, …)是输出到文件描述符1的简略形式。

1	Exercise 10. 在user/sh.c中添加相关内容，使之支持重定向。

void runcmd(char* s)

		case '<':	// Input redirection
			// Grab the filename from the argument list
			if (gettoken(0, &t) != 'w') {
				cprintf("syntax error: < not followed by word\n");
				exit();
			}
			// Open 't' for reading as file descriptor 0
			// (which environments use as standard input).
			// We can't open a file onto a particular descriptor,
			// so open the file as 'fd',
			// then check whether 'fd' is 0.
			// If not, dup 'fd' onto file descriptor 0,
			// then close the original 'fd'.

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

Challenge! 为shell添加更多功能，使之支持：
backgrounding commands (ls &)
multiple commands per line (ls; echo hi)
command grouping ((ls; echo hi) | cat > out)
environment variable expansion (echo $hello)
quoting (echo "a | b")
command-line history and/or editing
tab completion
directories, cd, and a PATH for command-lookup.
file creation
ctl-c to kill the running environment

fd、dev、file

jos的文件系统进程负责维护File数据结构、fd与file之间的关系，并以fd与其他进程进行交互。其他进程并不操作File数据结构，而是以fd与文件系统进程进行交互，具体是共享填充fd数据结构的页面。
jos的文件描述符包括文件、管道、console I/O三种设备dev类型，每种类型都有相应的文件读写接口，定义一致。用户进程在使用时，具体指定一种dev类型。每个类型的dev都有对应的id，并存在fd中，然后调用库函数与文件系统交互。在上述三种文件类型中，只有涉及文件类型时才会与文件系统进程进程交互。
File的定义如下：

struct File {
	char f_name[MAXNAMELEN];	// filename
	off_t f_size;			// file size in bytes
	uint32_t f_type;		// file type

	// Block pointers.
	// A block is allocated iff its value is != 0.
	uint32_t f_direct[NDIRECT];	// direct blocks
	uint32_t f_indirect;		// indirect block

	// Pad out to 256 bytes; must do arithmetic in case we're compiling
	// fsformat on a 64-bit machine.
	uint8_t f_pad[256 - MAXNAMELEN - 8 - 4*NDIRECT - 4];
} __attribute__((packed));	// required only on some 64-bit machines

fd的定义如下：

struct FdFile {
	int id;
};

struct Fd {
	int fd_dev_id;
	off_t fd_offset;
	int fd_omode;
	union {
		// File server files
		struct FdFile fd_file;
	};
};

dev的定义如下：

struct Dev {
	int dev_id;
	const char *dev_name;
	ssize_t (*dev_read)(struct Fd *fd, void *buf, size_t len);
	ssize_t (*dev_write)(struct Fd *fd, const void *buf, size_t len);
	int (*dev_close)(struct Fd *fd);
	int (*dev_stat)(struct Fd *fd, struct Stat *stat);
	int (*dev_trunc)(struct Fd *fd, off_t length);
};
 
extern struct Dev devfile;
extern struct Dev devcons;
extern struct Dev devpipe;

文件类型的交互

文件系统进程使用OpenFile关联file和fd，OpenFile定义如下：

struct OpenFile {
	uint32_t o_fileid;	// file id
	struct File *o_file;	// mapped descriptor for open file
	int o_mode;		// open mode
	struct Fd *o_fd;	// Fd page
};

OpenFile的fd关联着一个页地址，当具体分配fd时，会分配相应的物理页用于存储fd数据。进行文件读写时，fd用于保存文件的偏移、dev的id、文件id等信息，文件读写时是根据文件的偏移来计算逻辑块编号的；file则用于根据逻辑块编号查找存储的磁盘块编号。jos文件系统的磁盘块和文件系统进程的内存映射是固定的，根据file和逻辑块编号找到磁盘块编号之后，可得到对应的内存虚拟地址，在文件系统进程地址空间中读取该虚拟地址时，若发生页错误，文件系统进程注册的页错误处理函数会先读取磁盘内容到文件系统进程的地址空间中；用户进程写入内容到fd时，会在fd结构中找到对应的fileid并发送给文件系统进程，文件系统进程根据fileid找到对应的openfile，进而找到对应的file，并根据文件偏移计算逻辑块编号，再得到磁盘块编号和内存虚拟地址，最终填充数据到对应的内存空间中，支持close的时候会执行刷新动作，将脏内存内容更新到磁盘。

File数据结构既用于管理Dir，又用于管理File。File数据结构本身存储于文件系统进程的block diskmap内存空间中[0x10000000,0xD0000000)，dir关联的每一个block存储着若干直接子目录dir/file结构的数据，dir的size大小为存储直接子目录dir/file结构的所有block的总大小。

文件系统进程最多一次性支持1024个openfile，对应1024个fd，fd页地址从0xD0000000开始。用户进程发送文件open请求时，文件系统进程将寻找可用的fd并返回对应索引的openfile。open成功的情况是找到可用的fd和根据路径找到正确的file结构，然后使用ipc发送返回fd页地址，这种情况下fd页引用为2：一次是分配fd的时候，一次是ipc发送返回的时候映射到目标进程的地址空间；查找可用fd的过程中，如果fd页引用为0，会分配对应的物理页，使得fd页引用为1，此后如果出现其他错误，返回的fd页地址尚未被设置，则ipc发送返回的时候fd页不会映射到目标进程的地址空间，fd页引用保持为1；这说明，当fd页引用为0或1时，代表fd可用；下次查找可用fd的时候仍然会使用引用为1的fd，但省略分配新物理页的步骤，而只是累加fileid。

open成功时使用ipc返回fd页地址，存储着fileid、devid等信息（devid初始化为文件类型对应的id）。之后，用户进程从fd中读取fileid等信息，与文件系统进程继续进行交互，也可以编码改变文件偏移等信息，因为文件系统进程与用户进程共享该fd页。

用户进程一次最多可以打开32个fd，具体相关的库函数见lib/fd.c。用户进程的fd页地址从0xD0000000开始，file设备的open函数（见file.c）的功能是在用户进程中分配空闲的fd页虚拟地址，然后向文件系统进程发送open文件的ipc请求，表示希望在该fd页虚拟地址上接收文件系统进程共享的fd页，open函数转换为相应的fd索引返回，此后使用fd索引即可在用户进程中找到对应的fd页和数据。

库函数fd.c负责管理fd索引和fd页之间的转换，以及由小到大分配用户fd。file.c、pipe.c、console.c为具体的设备文件，三者的访问接口一致，但具体实现细节不同。用户进程调用fd.c的相关函数进行文件读写时传递fd索引参数，fd.c的函数根据fd索引找到fd实例，然后找到具体的dev并调用对应的设备函数。

关于fd的释放，用户进程调用fd.c的close函数一方面会调用相关设备的close函数（文件设备的close函数会发送请求到文件系统进程，刷新内存脏页到磁盘），并解除用户进程在fd上的页映射，该做法会导致fd页的引用变为1，从而文件系统进程可复用该fd页。

管道的交互

pipe的定义如下：

struct Pipe {
	off_t p_rpos;		// read position
	off_t p_wpos;		// write position
	uint8_t p_buf[PIPEBUFSIZ];	// data buffer
};

jos的管道大概实现是：在用户进程中分配两个fd页（权限设置为共享），fd0权限设为只读，fd1权限设为只写；这两个fd还有对应的data虚拟地址，两者映射到同一张物理页（权限设置为共享）表示管道共享这一张物理页，该物理页存储着pipe数据结构，包括读写指针和缓冲区。user/testpipe.c的大概过程是：主进程调用pipe分配两个fd，然后调用fork创建子进程，fork会将共享页之外的可写页/写时复制页映射为写时复制；此时父子进程都有相同的fd页映射和fd data页映射；之后子进程关闭fd1，解除fd1页映射，然后尝试从fd0中读取；父进程关闭fd0，解除fd0页映射，然后尝试往fd1中写入。由于父进程的fd0、fd1共享一张data物理页，fork的过程会将对应页访问权限映射到子进程中（fork中并没有将子进程对应的页权限也设为PTE_SHARE，这表示父进程共享给子进程的页不一定能共享给子进程创建的子子进程），所以子进程的fd0与父进程的fd1共享同一张data物理页。管道读写时实际上是操作data物理页，写时：对于每一个即将写入到缓冲区的字节，若写指针>=读指针+缓冲区大小，说明缓冲区已满，调用sys_yield尝试切换执行其他进程，否则写入缓冲区并写指针加1（写入时写指针取余数）；读时：循环即将读取的字节大小，若读指针=写指针，说明缓冲区为空，调用sys_yield尝试切换执行其他进程，否则从缓冲区读取一个字节，读指针加1（读取时读指针取余数）。

注意到，jos的管道没有涉及到文件系统进程。