Goals
For this assignment, you will design you own file system. It should be able to store up to 10,000 files on a medium up to 2GB in size. The maximum size of each file is 200MB. The file system should provide a directory tree with file names composed of arbitrary characters up to 200 bytes long. Each block is 1KB in size, which means your file system will have to handle at least 2,097,152 x 1KB blocks = 2GB.

The file system does not have to be efficient. In particular, you do not need to implement a buffer cache. Your implementation must limit itself to using a fixed size of storage, on the order of 1MB or (much) less for all the tables etc. The actual storage must be moderately efficient, so that most of the space on the “disk” should be available for storage of actual data.

Details
The file system should use the following block read and write operations which will be provided:

typedef char block [1024]; /* each block is 1KB */
int read_block (int block_num, char * block) — returns 0 if the operation is successful, and -1 otherwise
int write_block (int block_num, char * block) — returns 0 if the operation is successful, and -1 otherwise, this function actually writes the block to disk
int dev_open () — returns the device size (in blocks) if the operation is successful, and -1 otherwise
These are implemented in the supplied file, block.cPreview the document. The first block is block number 0. By design, dev_open accesses blocks in a file named my_dev in the current directory. To create the file, use the following command from the shell prompt:

dd if=/dev/zero of=my_dev bs=1024 count=x
where x is the size (in blocks) of your intended device. For example,

dd if=/dev/zero of=my_dev bs=1024 count=131072
gives you a 128MB device (128K blocks), and

dd if=/dev/zero of=my_dev bs=1024 count=250000
gives you a device large enough for the maximum file size that testp4 (described below) tries to build.

WARNING: Make sure you have enough room in your home directory to create a file that large.

Implementation
Your code must implement the following API that is based on (and a simplified version of) the POSIX file API:

int my_open (const char * path) – to open an existing file for reading or writing
int my_creat (const char * path) – to open a new file for writing only (fails if the file already exists)
int my_read (int fd, void * buf, int count) – to sequentially read from a file
int my_write (int fd, const void * buf, int count) – to sequentially write to a file
int my_close (int fd)
int my_remove (const char * path)
int my_rename (const char * old, const char * new)
int my_mkdir (const char * path) – only works if all but the last component of the path already exists
int my_rmdir (const char * path)
void my_mkfs () – checks to see if the device already has a file system on it, and if not, creates one.
A file providing this API, but not implementing it, is provided to you as prog4.cPreview the document. Please modify just this file by filling in all the implementations of the listed functions and other needed ancillary functions (see the next section). The header file, prog4.hPreview the document, is also provided for your convenience along with a simple test program, testp4.cPreview the document. This program runs all the tests unless an optional argument is provided, in which case it runs all the tests on files whose size (in bytes) is less than or equal to the argument. Please go through the code for testp4.cPreview the document to understand how it tests the implementation of the file system for correctness.

NOTE: Of the four files given to you (block.cPreview the document, prog4.cPreview the document, prog4.hPreview the document, testp4.cPreview the document), you should only modify the prog4.hPreview the document and prog4.cPreview the document. The testp4.cPreview the document should not be modified in any way (except of course if you need to make some modifications while testing). The block.cPreview the document should not need to be modified in any way, however if you feel that you can modify it to improve your implementation then you are free to.

Program Guidelines
As mentioned earlier, your program should not aim to do anything very fancy, and so, your choice of structures for i-nodes, directory entries and the superblock should be simple. For example, your code does not need to provide protection, multiple links, access times, or current directories. You also may assume that each file will be opened at most once before it is closed again; i.e. we assume that files have a single pointer for position. On the other hand, you should allow for multiple files (up to 10) to be open at the same time. Keep a simple in-memory table structure to maintain these open file descriptors.

Your code does need to handle “/”-separated paths of arbitrary depth, and so one useful function you may find yourself writing may be to parse paths. You may also want to write some routines to maintain and access block bitmaps on disk (some stubs are provided already in the file prog4.cPreview the document; add more functions as you see fit).

You may also want to implement some ancillary functions for debugging and testing your path traversal code, e.g. to produce a dump of the files under some sub-directory in the file system tree. Above all, keep it simple!

Deliverables
Please make sure that your code runs on the Linux systems in school (on the lab machines, clamshell.rutgers.edu or apps.camden.rutgers.edu). Be very careful if you develop your code on a 32bit system and then move to a 64bit system, some types (like the long are different sizes on different architectures). You can see the difference by looking at the output of sizeof(long) on both a 32bit and 64bit system, they will be different sizes. This is important when you create your structures, because they need to be exactly 1K in size, so you may need to pad your structure to make it the right size.

You should be able to compile the testp4 program, by running:
    gcc -o testp4 block.c prog4.c testp4.c
The resulting executable should run without errors. Note that the executable can be supplied with a command line argument (see the file testp4.cPreview the document for details on what it tests). Along with your implementation file, prog4.c, please submit a reasonably detailed design document (in PDF format) called README.pdf that describes your design and implementation strategy.

To read what is stored on your “device”, you may run
    od -t x1 my_dev | more
Don’t worry if the numbers come out backwards (with the least significant bit first); this will happen if you run on little-endian machines such as those using Intel architectures.