MIT 6.828 labs walkthroughs: Lab 5 File system, Spawn and Shell

Exercise 1

What we need to do is to add this simple line to env_create(). Here we can also set FL_IOPL_3 since the file system environment is a special user environment.

// If this is the file server (type == ENV_TYPE_FS) give it I/O privileges.
if (type == ENV_TYPE_FS) {
	env->env_tf.tf_eflags |= FL_IOPL_MASK;
}

Now it will pass the fs i/o test in make grade.

Question 1

No. The I/O privilege is stored in eflags register. It will be saved and restored automatically when switching between environments.

Exercise 2

Both functions are easy to implement. The part we need to implement in bc_pgfault() allocates a new page and then read content from disk. The address should be rounded down to page boundary. Here, we can use 0 as the envid of the current environment and remember that disk driver APIs like ide_write() always takes sector as a unit, not page.

addr = ROUNDDOWN(addr, PGSIZE);
if ((r = sys_page_alloc(0, addr, PTE_W | PTE_U | PTE_P)) != 0) {
	panic("bc_pgfault: %e", r);
}
if ((r = ide_read(blockno * BLKSECTS, addr, BLKSECTS)) != 0) {
	panic("bc_pgfault: %e", r);
}

And flush_block() flushes the block cache at addr if it exists.

void
flush_block(void *addr)
{
	uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;
	int r;

	if (addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))
		panic("flush_block of bad va %08x", addr);
	if (!va_is_mapped(addr) || !va_is_dirty(addr)) {
		return;
	}
	addr = ROUNDDOWN(addr, PGSIZE);
	if ((r = ide_write(blockno * BLKSECTS, addr, BLKSECTS)) != 0) {
		panic("flush_block: %e", r);
	}
	if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) != 0) {
		panic("flush_block: %e", r);
	}
}

Now it will pass the check_bc, check_super and check_bitmap tests in make grade.

Exercise 3

alloc_block() allocates a new block on the file system. As the file system uses an array of bits called bitmap to record if a block is used or not, we need to update the corresponding part of bitmap and flush its cache.

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.
	int i;

	for (i = 0; i < super->s_nblocks; i++) {
		if (block_is_free(i)) {
			bitmap[i / 32] &= ~(1 << (i % 32));
			flush_block(&bitmap[i / 32]);
			return i;
		}
	}
	return -E_NO_DISK;
}

Now it will pass the alloc_block test in make grade.

Exercise 4

Before taking on this exercise, we'd better take a look at how a file is stored in the file system in File Meta-data of the lab page. The File structure holds the file's information as well as pointers to the first 10 blocks. If the file takes more space, the indirect block pointer will point to a block which holds pointers to the following blocks, and it can hold up to 1024 pointers.

With the information above and the comment, these two functions can be implemented easily. file_block_walk() finds the specified block of a file, which is quite similar to pgdir_walk(). If we allocate a new block as an indirect block, since the new block might be dirty, we should fill it with 0.

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
	if (filebno >= NDIRECT + NINDIRECT) {
		return -E_INVAL;
	}
	if (filebno < NDIRECT) {
		*ppdiskbno = &f->f_direct[filebno];
	} else {
		if (!f->f_indirect && !alloc) {
			return -E_NOT_FOUND;
		}
		if (!f->f_indirect && alloc) {
			uint32_t newbno;

			if ((newbno = alloc_block()) < 0) {
				return -E_NO_DISK;
			}
			f->f_indirect = newbno;
			memset(diskaddr(newbno), 0, BLKSIZE);
		}
		*ppdiskbno = &((uint32_t *)diskaddr(f->f_indirect))[filebno - NDIRECT];
	}
	return 0;
}

And file_get_block() reads the specified block and allocates a new one if it does not exist. If a new block is allocated, it should also be filled with 0.

int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
	uint32_t *pdiskbno;
	int r;

	if ((r = file_block_walk(f, filebno, &pdiskbno, 1)) != 0) {
		return r;
	}
	if (!*pdiskbno) {
		uint32_t newbno;

		if ((newbno = alloc_block()) < 0) {
			return -E_NO_DISK;
		}
		*pdiskbno = newbno;
		memset(diskaddr(newbno), 0, BLKSIZE);
	}
	*blk = diskaddr(*pdiskbno);
	return 0;
}

Now it will pass the file_open, file_get_block, file_flush/file_truncated/file rewrite and testfile tests in make grade.

Exercise 5

Since the file system environment is a special user environment, other user environments need to use the IPC(Inter-Process Communication) mechanism to perform file operations, so the file system provides a server.

Like other *nix systems, user applications on JOS uses a file descriptor to access a file, and it is created by sending open request to the file server. The file server uses struct OpenFile to record an opened file, and these records are saved in opentab[]. Before performing file operations like read or write, the file should be opened first.

The server also uses a union Fsipc to hold the IPC message for file operation requests. It is defined in inc/fs.h.

Now we can implement the serve_read(). It checks if the file requested is opened, read the file, update the seek position, and sends a response.

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

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

	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) {
		o->o_fd->fd_offset += r;
	}
	return r;
}

Now it will pass the serve_open/file_stat/file_close and file_read tests in make grade.

Exercise 6

serve_write() is similar to serve_read(), except its response only contains a value.

int
serve_write(envid_t envid, struct Fsreq_write *req)
{
	struct OpenFile *o;
	int r;

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

	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) {
		o->o_fd->fd_offset += r;
	}
	return r;
}

devfile_write() prepares the write request, and sends it to the server. Here the request and response both need to be checked. The req_buf should never exceed PGSIZE - (sizeof(int) + sizeof(size_t)) as the definition of struct Fsreq_write indicates, and the response value should above 0.

static ssize_t
devfile_write(struct Fd *fd, const void *buf, size_t n)
{
	int r;

	fsipcbuf.write.req_fileid = fd->fd_file.id;
	fsipcbuf.write.req_n = n;
	assert(n <= PGSIZE - (sizeof(int) + sizeof(size_t)));
	memmove(fsipcbuf.write.req_buf, buf, n);
	if ((r = fsipc(FSREQ_WRITE, NULL)) < 0)
		return r;
	assert(r <= n);
	return r;
}

Now it will pass the file_write, file_read after file_write, open, and large file tests in make grade.

Exercise 7

sys_env_set_trapframe() sets the environment's trap frame with the one provided. The trap frame should be modified to run at Ring 3 (the lowest 2 bits of CS and SS register should set to 3), interrupts enabled (set the IF bit in EFLAGS), and IOPL of 0 (clear the 2-bit IOPL field in EFLAGS).

static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{
	struct Env *e;
	int r;

	if ((r = envid2env(envid, &e, 1)) != 0) {
		return r;
	}
	user_mem_assert(e, tf, sizeof(struct Trapframe), PTE_W);
	tf->tf_cs |= 3;
	tf->tf_ss |= 3;
	tf->tf_eflags |= FL_IF;
	tf->tf_eflags &= ~FL_IOPL_3;
	e->env_tf = *tf;
	return 0;
}

And don't forget to add its dispatcher in syscall().

case SYS_env_set_trapframe:
	return sys_env_set_trapframe(a1, (struct Trapframe *)a2);

Now it will pass the spawn via spawnhello and Protection I/O space tests in make grade.

Exercise 8

To handle shard pages in duppage(), as the exercise description says, copy the mapping directly and mask out the perm with PTE_SYSCALL. So a new condition should be added.

@@ -64,7 +64,11 @@ duppage(envid_t envid, unsigned pn)
        void *va = (void *)(pn * PGSIZE);
        int r;
 
-       if ((uvpt[pn] & PTE_W) == PTE_W || (uvpt[pn] & PTE_COW) == PTE_COW) {
+       if ((uvpt[pn] & PTE_SHARE) == PTE_SHARE) {
+               if ((r = sys_page_map(parent_envid, va, envid, va, uvpt[pn] & PTE_SYSCALL)) != 0) {
+                       panic("duppage: %e", r);
+               }
+       } else if ((uvpt[pn] & PTE_W) == PTE_W || (uvpt[pn] & PTE_COW) == PTE_COW) {
                if ((r = sys_page_map(parent_envid, va, envid, va, PTE_COW | PTE_U | PTE_P)) != 0) {
                        panic("duppage: %e", r);
                }

copy_shared_pages() loops through all PTEs and copy the mappings of shared pages to the child, very similar to fork().

static int
copy_shared_pages(envid_t child)
{
	envid_t parent_envid = sys_getenvid();
	uint32_t addr;
	int r;

	for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
		if ((uvpd[PDX(addr)] & PTE_P) == PTE_P && (uvpt[PGNUM(addr)] & PTE_P) == PTE_P && (uvpt[PGNUM(addr)] & PTE_SHARE) == PTE_SHARE) {
			if ((r = sys_page_map(parent_envid, (void *)addr, child, (void *)addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) != 0) {
				panic("copy_shared_pages: %e", r);
			}
		}
	}
	return 0;
}

Now it will pass the PTE_SHARE [testpteshare] and PTE_SHARE [testfdsharing] tests in make grade.

Exercise 9

Simply add two cases in trap_dispatch().

case IRQ_OFFSET + IRQ_KBD:
	kbd_intr();
	return;
case IRQ_OFFSET + IRQ_SERIAL:
	serial_intr();
	return;

Exercise 10

To handle input redirection, as the comment says, we need to open t for reading as file descriptor 0. Since t is for input, it should be opened with O_RDONLY flag. And if file descriptor 0 exists, t should replace it, and the original file descriptor for t should be closed.

@@ -56,3 +56,9 @@ again:
-                       // 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;

Now run make grade we shall pass all the tests and get 150 points like this:

internal FS tests [fs/test.c]: OK (2.4s) 
  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 (3.4s) 
  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 (2.1s) 
Protection I/O space: OK (3.0s) 
PTE_SHARE [testpteshare]: OK (3.0s) 
PTE_SHARE [testfdsharing]: OK (2.8s) 
start the shell [icode]: Timeout! OK (30.5s) 
testshell: OK (4.9s) 
primespipe: OK (10.5s) 
Score: 150/150