To the Assignments

• Week #1
• Week #2
• Week #3

Overview

How this assignment differs from the others

Option #1

    You may choose to work with a partner on this assignment.  The mechanics of how you work with someone are entirely up to you and I will not mediate groups disputes, deal with partner laziness or incompetency, or give any leeway to "group excuses."  Group excuses that I particularly don't like include "my partner had another project to work on and so we didn't have time to work on it much this week."  In addition, I will ask questions on the final exam referring to the development of this program.  Despite splitting up the work, you are required to understand all of the code that your partner has written.  In addition, once you declare you are working with a partner, you may not change you mind for the duration of the assignment.

Option #2

    I am presenting this project in its entirety from the start. I have, however, broken the project into 3 logical parts each of which is due at the end of a single weeks time.  You may take the option to hand in the entire assignment at the end of the three weeks providing that: you declare you intent to do this by Wednesday on this week, and you have not missed or been tardy on a single assignment to date.  If you ever asked me, even once, for an extra 1/2 hour then you are not eligible for this option. I must approve all requests to follow this option.

Week 1 - Due May 3rd

Write Part's A and B as static functions in a class called HelperFunc

Part A:

    /** Store an integer into a byte array.
     * @param n the integer to be stored
     * @param buf the byte array into which it should be stored
     * @param offset the index of the first byte to be modified
     */
    static void intToBytes(int n, byte[] buf, int offset) {
        buf[offset] = (byte)(n >> 24);
        buf[offset+1] = (byte)(n >> 16);
        buf[offset+2] = (byte)(n >> 8);
        buf[offset+3] = (byte)n;
    }

    /** Convert a field in a byte array to an integer.
     * @param buf the byte array containing the data.
     * @param offset the location in the array where the data starts.
     * @return the integer value.
     */
    static int bytesToInt(byte[] buf, int offset) {
        return ((buf[offset] & 0xff) << 24)
            + ((buf[offset+1] & 0xff) << 16)
            + ((buf[offset+2] & 0xff) << 8)
            + (buf[offset+3] & 0xff);
    }

Part B:

 /** Check whether a particular bit is set in a bitmap.
     * @param n the bit to test
     * @param b the bitmap
     * @return true if the bit is set
     */
    static boolean bitIsSet(int n, byte[] b) {
        int whichByte = n / 8;
        int whichBit = n % 8;
        return ((b[whichByte] << whichBit) & 0x80) != 0;
    }

Part C:

Your superblock must look like this:
class Superblock {
    int totalBlocks;   // The number of blocks on this disk
    int bitmapBlocks;  // The number of blocks reserved for the bitmap
    int rootDirStart;  // The block number of the start of the root directory
    int rootDirLength; // The length of the root directory, in blocks
}

    Write functions to set and retrieve each of the individual values in the superblock.  In addition your should write each of the following functions.

    // constructors

    // set the corresponding values in the superblock
    public Superblock(int totalBlocks, int bitmapBlocks, int rootDirStart, int rootDirLength);

    // take the next 16 bytes starting at offset in the byte array and using your conversion functions, create a new superblock
    public Superblock(byte[] byteArray, int offset);

    // covert the superblock to a set of bytes, storing them in a byte array starting at offset
    public void toBytes(byte[] byteArray, int offset);

    // write a toString function so you can easily print out a superblock for your own use
    public String toString();

Part D:

A directory entry looks like this in memory:

class DirEnt {
    short type;   // type of entry -- one of the following
        static final int UNUSED = 0;    // directory entry is unused
        static final int DIRECTORY = 1; // entry points to another directory
        static final int FILE = 2;      // entry points to a non-dir file
    short start;  // block number of the first block of the dir or file
    short maxLen; // space allocated to this file or directory, in blocks
    int size;     // current size of the file in bytes
    String name;  // name of this entry (pathname component); max 22 chars
    static final int SIZE = 32; // size of a directory entry on disk.
}

Write functions corresponding to all the functions required for the superblock.

Grading:

Week #2 - Due May 10th at 5:00

Getting Started

1. When it is not being used, the Disk saves its contents to a Unix file named DISK. This will allow you simulate "turning off" the computer without losing the contents of the Disk. The DISK file may get quite large, so please delete it before you log out. When the Disk starts up, it looks for a Unix file named DISK. If it finds one, it re-initializes it with the contents of the file. Otherwise, it starts out blank (all blocks filled with null bytes).
2. This new model of disk has a buffer cache and elevator scheduling algorithm built in. (Actually, that's a lie. It just doesn't simulate any delays, but you can pretend that it has buffering and scheduling built in.) The two methods beginRead and beginWrite have been replaced with two methods that are much easier to use:

    public synchronized void readBlock(int blockNumber,
        byte[] buffer, int offset);
    public synchronized void writeBlock(int blockNumber,
        byte[] buffer, int offset);

The readBlock method asks the disk to copy the selected block into the supplied buffer at the indicated offset. For example, if offset is zero, the data will be put at the start of the buffer; if offset == 100, the data will be copyied to buffer[100], buffer[101], ... buffer[Disk.BLOCK_SIZE - 1]. It is an error if offset + Disk.BLOCK_SIZE > buffer.length. This method blocks the caller until the data has been copied from the disk to the buffer. Similarly, writeBlock copies one block of data from buffer, starting at offset, to the selected block of the disk. There is no need to do any buffering or scheduling of your own, and no need to deal with disk interrupts.
There is a new method flush that copies the contents of the disk back out to the DISK Unix file. Main.main has been modified to call this function at shutdown.

Implementation

Block zero should contain a superblock which contains global information about the file system, including the location and size of the root directory. No matter what the geometry of the disk or the size of the filesystem, the OS should be able to read block zero and know exactly how to use the disk.

After the superblock are blocks containing a free block bitmap. The bitmap should be big enough to allow one bit for every block on the disk. If the bit is a 1, the block has been allocated for some purpose. If the bit is a 0, the block is free. The format method marks as allocated the superblock and the blocks allocated to the bitmap itself.

The rest of the blocks of the disk are either free or allocated to directories or other files. In this file system, files and directories are always allocated contiguously, so that a file or directory is completely described by its starting block number and its length in blocks.

You should only keep a minimal amount of data in memory. When on-disk data needs to be changed, send it to the disk as soon as is practical. For example, each time you need to update a directory entry, read the disk block that contains the entry, modify the part of that block that corresponds to the entry, and write the block back to disk. Let the (simulated) buffer cache in the Disk optimize the reads and writes.

Use a bitmap to keep track of which blocks are allocated and which blocks are free. We recommend reading the entire bitmap into a byte array on startup and flushing it back to disk before shutdown. Use a simple first-fit strategy to find space for new files and directories. Here's some simple code for manipulating the bitmap.

File System API

You are to write the initial commands to write a tree-structured directory system.  This week you will write commands to create and manipulate directories and next week you will complete the file system by adding functions to create, read, write and manipulate files in your system. Files are identified by pathnames, which are readable character strings possibly containing slashes (/). There is a current working directory (cwd). Unlike Unix, which has a cwd for each process, there is just one cwd that applies to all system calls. Pathnames that start with a slash are absolute pathnames; they are resolved relative to the root directory. Pathnames that do not start with a slash are resolved relative to the current working directory. On startup, the cwd is the root directory.

Unlike Unix, each file and directory has a maximum size, set when the file is created, as well as a current size.

You must implement the 5 system calls format, chdir, mkdir, rmdir, and listdir described below.
Unless specified otherwise, each of the system calls returns a negative value to indicate an error and zero for success.

• int format(int rootDirSize);

This method initializes the contents of the disk with any data structures necessary to represent an "empty" file system. This method should create a new superblock, a new bitmap with all entries set to 0 initially (and then mark as used the blocks corresponding to the superblock, bitmap and rootdir). This method should create an "empty" root directory, containing only two entries, "." and ".." entries, both of which point to itself. The rootDirSize parameter is the maximum size for the root directory (see mkdir below).
• int chdir(String pathname);

Sets the current working directory to the directory identified by pathname, which may be either absolute or relative. The initial current working directory is the root directory. If pathname does not name a valid existing directory, the cwd is unchanged and an error indication is returned.
• int mkdir(String pathname, int maxSize);

Create a new directory with the indicated pathname. The parameter maxSize is the maximum size for the new directory in blocks. The directory starts out "empty," that is, it contains only two entries: . points to the new directory itself and .. points to its parent directory. In reality, I would make all the possible DirEnts that the directory can hold at the start, and mark all but the first 2 as unused, this will make later computations on the directory easier. All components of pathname other than the last component must identify existing directories. It is an error if the whole pathname identifies an existing file or directory, if there is not enough space left in the parent directory to create a new entry, or if there is not enough contiguous space on the disk for the new directory. Use a first-fit strategy to find the next available free block in memory.
• int rmdir(String pathname);

Delete the indicated directory. It is an error if pathname does not indicate an existing directory, or if the directory is non-empty (contains entries other than . and ..). Simply find the DirEnt that references this directory and change the type to UNUSED.  Be sure to free all the blocks allocated to the directory.
• int listdir(String pathname);

Display the contents of the indicated directory on System.out. This is just a kludge for debugging. A more realistic implementation would have system calls to retrieve a list of the names in a directory and to get the meta-data associated with a particular file or directory. The easiest way to do this is to examine each DirEnt in the specified directory and printout all non UNUSED entries.
Interpreting pathnames. Use a StringTokenizer to break up a pathname into its components, and write a method

    private DirEnt namei(DirEnt start, String[] path)

to simplify walking the directory tree. This method takes a pointer to a particular node in the file system tree (encoded as a DirEnt structure), and walks through the file system following the path indicated by the strings in path. The resulting DirEnt is a pointer to the end of the path (only the start and size fields are meaningful).

The Command Interpreter

The Shell of project 4 is replaced in this project with a program called FileTester, which is a command interpreter specifically designed for testing your file system. The program is started by typing

    java Main size

where size is the size of the simulated disk, in blocks. For example, you might try java Main 100. If a (Unix) file named DISK exists in the current directory, it should be the result of any earlier run with the same size parameter. Otherwise, a new DISK will be created, with all blocks filled with null bytes. In this case, you should be careful that the first command you type is format.

You can also run the program to take its commands from a script, as in

    java Main 100 test1.script

Input lines starting with ``/*'' or ``//'' are ignored (the latter are echoed to the output). Other lines have the format

    command [ args ]

The there is one command for each of the 9 system calls, plus one extra version of write called writeln, which takes its input from the lines following the command. In line with longstanding tradition, some of the commands have slightly different names from the methods they call

command	method
rm	delete
cd	chdir
ls	listdir

There are also a few special cases.
• The help command prints a list of all the commands.
• The quit command terminates the program (as does end-of-file).
• write fname offset size pattern writes size bytes to the indicated file at the indicated offset. The data is generated by repeating pattern over and over the required number of times.
• writeln file linecount Takes the next linecount lines of input to the command interpreter and writes them to the file, starting at offset 0.
• read file offset length reads the indicated number of bytes from the file starting at the indicated offset and dumps the data read to the screen.

Grading

Copy into the prog4b turnin directory a complete set of all the .java files needed to run your program. Also copy in any test scripts you created. Also include a file named README containing the names of the partners if any that worked on this project.and a brief description of your project and test program. At the least, you code should work with the test scripts that I have provided. Please include comments that will help us to correctly test your project.

---

Week 3 - Due May 17th at 5:00

Finish your file system by adding the following commands to Kernel.java.  As per the prior assignment, you need not modify any files other than Kernel.java and Library.java

You must implement the 4 system calls create, read, write, and delete described below. Note: These functions will end up looking very similar to the functions written last week.

Unless specified otherwise, each of the system calls returns a negative value to indicate an error and zero for success.

int create(String pathname, int maxSize);

Creates a new empty file with the indicated pathname and size limit (in blocks). All components of pathname other than the last component must identify existing directories. It is an error if the whole pathname identifies an existing file or directory, if there is not enough space left in the parent directory to create a new entry, or if there is not enough contiguous space on the disk for the new file. Should work similarly to mkdir.  You should search the parent directory for the first UNUSED DirEnt and use it to index your new file.

int read(String pathname, int offset, byte[] buffer);

Read buffer.length bytes from the file indicated by pathname, starting at offset (number of bytes from the start of the file). If fewer than buffer.length bytes remain between the indicated offset and the current file length, read as many bytes as possible, putting them into the beginning of buffer. (In particular, if the offset is greater than or equal to the current file size, read no bytes and leave the buffer unchanged). The return value is the number of bytes read, or error.

int write(String pathname, int offset, byte[] buffer);

Write the contents of buffer to the indicated file starting at the indicated offset. The operation may overwrite existing data in the file and/or append to the end of the file. If the write would extend the file beyond its maximum size, write only as many bytes as will fit. The return value is the number of bytes written, or error.

int delete(String pathname);

Destroy the indicated file. Make sure to change the DirEnt in the parent block to be UNUSED and be sure to release all blocks allocated to the file. It is an error if the indicated file does not exist or is a directory.

Grading: