CS 39 -- Assignment 3

Adding a filesystem

For this assignment, we will be adding filesystem support to the kernel. In order for the kernel to provide a filesystem, the virtual machine must include a block device that persistently stores data. Such a block device is provided with the new version of the virtual machine.

In order to get started with this project, you must download the latest version of the virtual machine, version 0.3. You can find the tarball for this code in the expected place:

~sfkaplan/cs39/assignment-3-code.tar.gz

This tarball will include code for the virtual machine, the MMU, and the block device that will serve as the persistent storage on which you will build a filesystem. Note, as always, that these components may not be changed.

One update to the virtual machine itself: You should modify your kernel's halt function by calling stopVMachine, which is a new virtual machine function that takes the opportunity to synchronize the block device before terminating. This approach to synchronization is a somewhat ill-fitting hack, as the CPU would not normally be responsible for such a thing. Since we do not have device drivers, this workaround will do.

The block device

The block device has a simply interface that allows the kernel to querry the number of bytes in each block (a.k.a. sector), and the number of total blocks available. It also allows the kernel to read and write particular blocks. The functions provided by the block device are as follows:

• vMachineWord_t getBytesPerBlock ()

  Return the number of bytes stored in each block in the block device.

• vMachineWord_t getNumberBlocks ()

  Return the total number of blocks available in the block device. Notice that if the block device contains n blocks, then the lowest block index is 0, and the highest block index is n-1.

• bool readBlock (vMachineWord_t blockNumber, vMachineWord_t bufferAddress)

  The block number specified by the first argument is read from the block device, and its data copied into the address specified by the second argument. This function returns true if the read operation succeeded, and false if it failed for any reason. It is the responsibility of the caller to ensure that the allocated space at the buffer address is sufficiently large to hold a block.

• bool writeBlock (vMachineWord_t blockNumber, vMachineWord_t bufferAddress)

  The block of data contained at the buffer address specified by the second argument is written into the block number specified by the first argument. The function returns true if the write operation succeeded, and false if it failed for any reason. It is the responsibility of the caller to ensure that the allocated space at the buffer address contains a complete block of data to be written.

New system calls

There are six new system calls that the filesystem must support. These allow any process to perform the basic manipulations of a file.

1. OPEN: 0xF0000000

   This system call should attempt to open a specified file in the filesystem. The register operand-1 should contain the virtual address of a null-terminated string that stores the requested filename.

   If the requested file exists, the filesystem should record that the file has been opened in the open-file table of that process. This table should contain one entry for each open file, and each entry should contain at least the following information:

   • Filename
   • File ID number, which the process will use to access this open file.
   • Current byte offset within the file, which initially should be 0 to indicate that the beginning of the file is the current location for reads and writes.

   Once this entry is created, the kernel should place the file ID number in register operand-2. The calling process should know to look in that register to obtain the file ID that it is to be used to refer to this open file.

   If the requested file does not exist, then a value of 0x0 should be placed in register operand-2. Therefore, this value is reserved as the "null file ID", and the calling process should identify it as such.

2. CLOSE: 0xF0000001

   This system call should close the file specified by the file ID provided by the caller in register operand-1. If the file ID is not a legitimate one for the given process, then this system call should do nothing.

   Closing the file implies removing the appropriate entry from the open file table for the given process.

3. CREATE: 0xF0000002

   This system call should attempt to create a specified file in the filesystem. The register operand-1 should contain the virtual address of a null-terminated string that stores the requested filename. The file should be added to the metadata of the filesystem, making it a valid file that can be opened, and that has an initial length of 0 bytes.

   If the filename is valid, and the file can be created, then the high-order bit of register operand-2 should be set to 0, as an indication of success. If the filename is invalid, or for some other reason cannot be create, or it already exists, then the high-order bit of register operand-2 should be set to 1.

4. DELETE: 0xF0000003

   This system call should delete the file specified by the file ID provided by the caller in register operand-1. If the file ID is not a legitimate one for the given process, then this system call should do nothing.

   If it is legitimate, this system call should close the given file and then remove it from the set of files stored by the filesystem. Note that a process must open a file before deleting it.

5. READ: 0xF0000004

   This system call should read the byte number specified in register operand-2 from the open file specified by the file ID in register operand-1. The byte that has been read should be placed in the low-order byte of register 0x1F.

   If the requested byte number is valid for the given file, and the read operation succeeds, then the highest-order bit of the word placed in register 0x1F should be 0, as an indication of a successful read. Otherwise, the high-order bit should be set to 1, as an indication of failure.

6. WRITE: 0xF0000005

   This syetm call should write the byte number specified in register operand-2 to the open file specified by the file ID in register operand-1. The byte to be written to that location should be taken from the low-order byte of register 0x1F.

   If the requested byte number already exists for the given file, then the byte previously held at that position should be replaced with this one. If the requested byte number is exactly one byte beyond the current end of the file, then append this new byte to the file. Otherwise, the specified byte number is invalid.

   If the byte number is valid for the given file, and the write operation succeeds, then the highest-order bit of register 0x1F should be set to 0, as an indication of a successful write. Otherwise, the high-order bit should be set to 1, as an indication of failure.

Buffer space for the filesystem

When blocks are read by the kernel, they must be read into some memory space. Because a process may read or write only particular bytes within a block, it is up to the filesystem to load the whole block into its buffer space, and then serve the requested bytes from that block.

In real systems, there is a separate pool of page frames in main memory that are allocated for the caching of filesystem blocks. The system must arbitrate between the needs of the filesystem and the needs of virtual memory in allocating those page frames.

1. The simple version: The kernel may allocate, in the kernel space (that is, not in the virtual machine's main memory), space for one cached filesystem block at a time. This block of space would allow the kernel to read and write any requested blocks, but would also require that every single request result in an access to the block device.
2. The more complex version: If you would like the filesystem to be able to cache a number of blocks, then those blocks should be stored in the virtual machine's main memory. However, such a decision implies some change to the virtual memory system. What is possible is that the filesystem be given its own context, just as each process is given its own context. The block numbers can be translated by the filesystem into virtual memory addresses, thus allowing the virtual memory system to manage the task of mapping bytes within blocks to locations in the main memory. However, the virtual memory system should not swap pages from filesystem cache to the backing store -- that would be redundant. Those filesystem cache pages should be handled differently, contacting the filesystem and allowing it to write those pages back to the block device.

Note that the more complex version has much to recommend it: Caching is more effectively used, the virtual memory mapping capabilities are used, and this interaction is much like what real kernels do. However, the simplicity of the first version may allow you a quicker implementation of a filesystem that works and performs the services needed by processes.

Submitting your work

All of your work should be done in your project directory. More specifically, within your project directory, be sure to create a new subdirectory for this assignment -- Don't clobber your old work!

When your group has completed its project, it should gather all of the files that are part of the completed project, and place a copy of those files in a directory named assignment-3 within your group's project directory. I will go and find them there.

Please note the submission time! This due date (and time) is the very last possible moment in the semester that I can accept course work. There will be no extensions!