0%

MIT6.828 Lab5

发表于

Exercise 1

当是ENV_TYPE_FS的时候提供读写的权限，对于普通的Env则不提供权限。

1
2
3
4
// 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)
	e->env_tf.tf_eflags |= FL_IOPL_MASK;

Exercise 2

为block分配一个页面，并且将block的内容读入。首先将addr进行对齐，这里由于page的大小和block的大小相同，所以怎样对齐都是可以的。之后利用sys_page_alloc()系统调用来进行页面分配，然后利用ide_read()进行内容的读取。注意的是ide_read()是以sector为单位进行读取的，是512个byte，同block的大小是8倍的关系，所以需要进行一个小小的处理。

1
2
3
4
5
6
7
8
9
10
11
// 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, BLKSIZE);
if((r = sys_page_alloc(0, addr, PTE_U | PTE_P | PTE_W)) < 0)
	panic("in bc_pgfault, sys_page_alloc: %e", r);
if((r = ide_read(blockno << 3, addr, 8)) < 0)
	panic("in_bc_pgfault, ide_read: %e", r);

当必要的时候，需要将Block写回磁盘，而必要的时候就是可写页面被修改的时候，所以这里首先的判断条件就应当是当前所对应的block是被映射了的，并且是dirty的。在调用ide_write()写回之后，需要重新进行一次映射来消除掉dirty位。这样可以避免多次进行flush，访问磁盘占用大量的时间。

1
2
3
4
5
6
7
8
9
// LAB 5: Your code here.
int r;
addr = ROUNDDOWN(addr, BLKSIZE);
if(va_is_mapped(addr) && va_is_dirty(addr)){
	if((r = ide_write(blockno << 3, addr, 8)) < 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);
}

Exercise 3

首先观察free_block()函数，可以发现每一位标志着一个block的状态，其中1表示为空闲，0表示为忙碌。访问的方式如第八行所示。

1
2
3
4
5
6
7
8
9
// Mark a block free in the bitmap
void
free_block(uint32_t blockno)
{
	// Blockno zero is the null pointer of block numbers.
	if (blockno == 0)
		panic("attempt to free zero block");
	bitmap[blockno/32] |= 1<<(blockno%32);
}

那么仿照就可以完成alloc_block()，对所有的block进行一个遍历，如果发现free的就进行分配，在bitmap中标志为0，之后立即利用flush_block()将将修改写回磁盘，并且返回blockno。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Search the bitmap for a free block and allocate it.  When you
// allocate a block, immediately flush the changed bitmap block
// to disk.
//
// Return block number allocated on success,
// -E_NO_DISK if we are out of blocks.
//
// Hint: use free_block as an example for manipulating the bitmap.
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.
	int blockno;
	for(blockno = 1; blockno < super->s_nblocks; blockno++){
		if(block_is_free(blockno)){
			bitmap[blockno/32] &= ~(1<<(blockno%32));
			flush_block(&bitmap[blockno/32]);
			return blockno;
		}
	}
	return -E_NO_DISK;
}

Exercise 4

这里的寻址实际上类似于lab2当中虚拟内存的寻址，不过在这里的设计上只有一个indirect的链接，所以实现起来相对简单很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block
// if necessary.
//
// Returns:
//	0 on success (but note that *ppdiskbno might equal 0).
//	-E_NOT_FOUND if the function needed to allocate an indirect block, but
//		alloc was 0.
//	-E_NO_DISK if there's no space on the disk for an indirect block.
//	-E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.
// Hint: Don't forget to clear any block you allocate.
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
       // LAB 5: Your code here.
	int r;

	if(filebno >= NDIRECT + NINDIRECT)
		return -E_INVAL;
	
	if(filebno < NDIRECT){
		*ppdiskbno = (f->f_direct) + filebno;
	}
	else{
		if(alloc && (f->f_indirect == 0)){
			if((r = alloc_block()) < 0)
				return r;
			memset(diskaddr(r), 0, BLKSIZE);
			f->f_indirect = r;
		}
		else if(f->f_indirect == 0){
			return -E_NOT_FOUND;
		}
		*ppdiskbno = ((uint32_t *)diskaddr(f->f_indirect)) + filebno - NDIRECT;
	}
	return 0;
}

通过file_block_walk()找到对应的pdiskbno，如果为0，那么就进行分配，否则的话利用diskaddr()转换成地址。成功就返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Set *blk to the address in memory where the filebno'th
// block of file 'f' would be mapped.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_NO_DISK if a block needed to be allocated but the disk is full.
//	-E_INVAL if filebno is out of range.
//
// Hint: Use file_block_walk and alloc_block.
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
       // LAB 5: Your code here.
	uint32_t * pdiskbno;
	int r;
	if((r = file_block_walk(f, filebno, &pdiskbno, true)) < 0)
		return r;
	if(*pdiskbno == 0){
		if((r = alloc_block()) < 0)
			return r;
		*pdiskbno = r;
	}
	*blk = (char *)diskaddr(*pdiskbno);
	flush_block(*blk);
	return 0;
}

Exercise 5

实际上就是针对于file_read()的一层封装，首先利用openfile_lookup()找到对应的文件，然后调用file_read()进行读入，之后调整文件的指针，并返回读入的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Read at most ipc->read.req_n bytes from the current seek position
// in ipc->read.req_fileid.  Return the bytes read from the file to
// the caller in ipc->readRet, then update the seek position.  Returns
// the number of bytes successfully read, or < 0 on error.
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:
	struct OpenFile * o;
	int r;
	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;
}

Exercise 6

serve_write()的逻辑类似于serve_read()，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 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.
	struct OpenFile *o;
	int r;
	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;
}

devfile_write(0)同样可以仿照devfile_read()进行完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Write at most 'n' bytes from 'buf' to 'fd' at the current seek position.
//
// Returns:
//	 The number of bytes successfully written.
//	 < 0 on error.
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
	int r;
	fsipcbuf.write.req_fileid = fd->fd_file.id;
	fsipcbuf.write.req_n = n;
	memmove(fsipcbuf.write.req_buf, buf, n);
	if((r = fsipc(FSREQ_WRITE, NULL)) < 0)
		return r;
	assert(r <= n);
	assert(r <= PGSIZE);
	return r;
}

Exercise 7

首先判断得到env，然后从18~20行依次为，开启中断，设置IOPL为0，将保护权限设置为3(CPL 3)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Set envid's trap frame to 'tf'.
// tf is modified to make sure that user environments always run at code
// protection level 3 (CPL 3), interrupts enabled, and IOPL of 0.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if environment envid doesn't currently exist,
//		or the caller doesn't have permission to change envid.
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!
	struct Env* env;
	if(envid2env(envid, &env, 1))
		return -E_BAD_ENV;
	env->env_tf = *tf;
	env->env_tf.tf_eflags |= FL_IF;
	env->env_tf.tf_eflags &= ~FL_IOPL_MASK;
	env->env_tf.tf_cs |= 3;
	return 0;
	panic("sys_env_set_trapframe not implemented");
}

Exercise 8

关于duppage()的修改，可以注意到直接只需要在可写页面修改为COW的时候进行PTE_SHARE的标志位判断就可以了，只在第11行处添加一个判断，其余内容同lab4中完全相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
	pte_t pte = uvpt[pn];
	void * addr = (void *)(pn * PGSIZE);

	uint32_t perm = pte & PTE_SYSCALL;
	if(perm & (PTE_W | PTE_COW) && !(perm & PTE_SHARE)){
		perm &= ~PTE_W;
		perm |= PTE_COW;
	}
	if((r = sys_page_map(0, addr, envid, addr, perm & PTE_SYSCALL))<0)
		panic("duppage: %e", r);
	if((r = sys_page_map(0, addr, 0, addr, perm & PTE_SYSCALL))<0)
		panic("duppage: %e", r);
	return 0;
}

从UTEXT到UXSTACKTOP的所有共享页面将其映射复制到子进程的地址空间即可，代码类似于lab4里面的fork()

1
2
3
4
5
6
7
8
9
10
11
// Copy the mappings for shared pages into the child address space.
static int
copy_shared_pages(envid_t child)
{
	// LAB 5: Your code here.
	uint8_t* addr;	
	for(addr = (uint8_t *)UTEXT; addr <(uint8_t *)UXSTACKTOP; addr += PGSIZE)
		if((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_SHARE))
			sys_page_map(0, (void *)addr, child, (void *)addr, (uvpt[PGNUM(addr)] & PTE_SYSCALL));
	return 0;
}

Exercise 9

添加对应的分发入口即可：

1
2
3
4
5
6
7
8
9
10
11
// Handle keyboard and serial interrupts.
// LAB 5: Your code here.
if(tf->tf_trapno == IRQ_OFFSET + IRQ_KBD){
	kbd_intr();
	return;
}

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

Exercise 10

重定向输出流的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
case '>':	// Output redirection
	// Grab the filename from the argument list
	if (gettoken(0, &t) != 'w') {
		cprintf("syntax error: > not followed by word\n");
		exit();
	}
	if ((fd = open(t, O_WRONLY|O_CREAT|O_TRUNC)) < 0) {
		cprintf("open %s for write: %e", t, fd);
		exit();
	}
	if (fd != 1) {
		dup(fd, 1);
		close(fd);
	}
	break;

仿照就可以完成输入流的重定向：

1
2
3
4
5
6
7
8
9
10
// LAB 5: Your code here.
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;

到这里可以达到150/150的满分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
internal FS tests [fs/test.c]: OK (1.0s)
  fs i/o: OK
  check_bc: OK
  check_super: OK
  check_bitmap: OK
  alloc_block: OK
  file_open: OK
  file_get_block: OK
  file_flush/file_truncate/file rewrite: OK
testfile: OK (1.6s)
  serve_open/file_stat/file_close: OK
  file_read: OK
  file_write: OK
  file_read after file_write: OK
  open: OK
  large file: OK
spawn via spawnhello: OK (1.8s)
Protection I/O space: OK (1.6s)
PTE_SHARE [testpteshare]: OK (0.9s)
PTE_SHARE [testfdsharing]: OK (1.4s)
start the shell [icode]: Timeout! OK (31.5s)
testshell: OK (2.4s)
    (Old jos.out.testshell failure log removed)
primespipe: OK (7.2s)
Score: 150/150

Challenge 1

Challenge的要求即为清空掉所有的没有被访问的页面。那么对于单个页面，只需要调用flush_block()，之后通过系统调用unmap就可以了。evict_policy()即对于所有的block做一个便利，清除所有从未被访问过的页面。具体代码内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// challenge
void
evict_block(void *addr){
	uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;
	if(addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))
		panic("evict_block of bad va %08x", addr);
	
	int r;
	addr = ROUNDDOWN(addr, BLKSIZE);
	flush_block(addr);
	if((r = sys_page_unmap(0, addr)) < 0)
		panic("in evict block, sys_page_unmap: %e", r);
}

void
evict_policy(){
	uint32_t blockno;
	for(blockno = 3; blockno < DISKSIZE / BLKSIZE; ++blockno){
		if(!(uvpt[PGNUM(diskaddr(blockno))]&PTE_A)){
			evict_block(diskaddr(blockno));
		}
	}
}