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.

```c
// 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.

```c
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.

```c
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.

```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.
	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.

![file.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/427908/9d93ce1a-ba35-c445-7e09-90fb23f0c4ac.png)

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.

```c
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.

```c
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.

```c
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.

```c
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.

```c
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).

```c
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()`.

```c
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.

```diff
@@ -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()`.

```c
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()`.

```c
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.

```diff
@@ -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
```