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