CSCI 380 -- Lab 3

File Systems

The goal of this lab is to write a simple UNIX-like file system based on the topics covered in class. The file system you will write makes the following simplifying assumptions:

The layout of your 128 KB disk is as follows

Layout

The exact structure of the super block is as follows.

struct inode {
  char name[16];        //file name
  int size;             // file size (in number of blocks)
  int blockPointers[8]; // direct block pointers
  int used;             // 0 => inode is free; 1 => in use
}

Note that each inode is 56B in size; Since you have 16 of these, the total size of occupied by the inodes is 896B. The free/used block information (mentioned above) is 128 byes. So the total space used in the super block is 1024 bytes.

You need to implement the following operations for your file system.


// open the file with the above name and initialize the fs
void fs_open(struct fs_t* fs, char diskName[16])

// close and clean up all associated things
void fs_close(struct fs_t* fs)

// create a new file with this name and with these many blocks.
//   we shall assume that the file size is specified at file
//   creation time and the file does not grow or shrink from
//   this point on
void fs_create(struct fs_t*, char name[16], int size)

// delete the file with this name
void fs_delete(struct fs_t*, char name[16])

// read the specified block from this file into the specified buffer
//   blockNum can range from 0 to 7.
void fs_read(struct fs_t*, char name[16], int blockNum, char buf[1024])

// write the data in the buffer to the specified block in this file
void fs_write(struct fs_t*, char name[16], int blockNum, char buf[1024])

// list the names of all files in the file system and their sizes
//    NOTE: use the format string "%16s %6dB" to print the files and their sizes
void fs_ls(struct fs_t*)

// enter a REPL session that adheres to the interactive requirements below
void fs_repl()

Getting Started

We will use a 128KB file to act as the "disk" for your file system.

I am providing a program to create this file for you. Download, compile, and run:

wget http://cs.millersville.edu/~wkillian/2019/spring/files/csci380/create_fs.c
make create_fs
./create_fs disk0

This will create a file with the name disk0 in your current directory.

The program also "formats" your file system --- this is done by initializing all blocks in the super block to be free and marking all 16 inodes to be free.

Here is template code for your file system.

Remember that your file system must be persistent. If you shutdown your program and then restart it at a later time, all files on your file system must be intact. Input file

You program should take input from a input file and perform actions specified in the file, while printing out the result of each action. The format of the input file is as follows.

diskName            // name of the file that emulates the disk
C fileName Size     // create a file of this size
D fileNAme          // delete this file
L                   // list all files on disk and their sizes
R fileName blockNum // read this block from this file
W fileName blockNum // write to this block in the file (use a dummy 1KB buffer)

An sample input file looks like this:

disk0
C file1 3
W file1 0
W file1 1
C lab.java 7
L
C file2 4
R file1 1
D lab.java
L

A sample input file is available. Be sure to print out what your program does after reading each line from this file. It'd also be helpful if you printed out the disk addresses of any block that you allocate, deallocate, read or write. FAQ

How do I write to a specific location on the disk?

You will need to be completely familiar with using lseek() in order to read and write to specific locations in the disk file. I strongly recommend that you read up on this before starting on this assignment. In particular, you'll need to understand how to use the seek method to move the file pointer to a specific location in the file and then you can read/write at that location.

Once you understand how seek works, all you need to do is compute the byte offset of the object you are tying to access and seek to that location before reading or writing. Remember to count from 0!

Your disk file is 128 KB in size. But (16 files * 8KB per file) plus 1 super block equals 129KB. How can all files fit? Your file system can support a maximum file size of 8 blocks (8KB). That does NOT mean that every file will be 8KB in size. In most cases, files will be smaller than the max file size. Each "create" request should check whether the disk has sufficient space for the file and if not, return a "not enough space on disk" error message.

Do I need to touch anything other than the superblock?

Most file operations will only touch the superblock (the free block list and the inode). However, the read and write calls need you to actually read and write data from the specified block on disk. In case of write, you can use a dummy buffer (e.g., with all 1s) to write to disk. Remember, what you write out is what should get read in if you use "read" at a later time.

Extra Credit

(30 pts) Write a defragmenter for the above file system. The defragmenter is invoked (by the user) whenever free space is fragmented and when files blocks are randomly scattered on the disk. Your defragmenter should attempt to place each file contiguously on disk and move all free space to the end of the disk. Any valid defragmentation algorithm will get you full credit on this question. The only restriction is that your defragmenter should not use a memory buffer of more than 17 KB (a trivial defragmentation algorithm is to read the entire disk into memory, rearrange blocks and write everything back. Things get more interesting if you assume that you have limited memory space (17KB)---in this case, you will need to repeatedly read a small number of files or disk blocks, rearrange them and then write them back.). This will be manually inspected and NOT autograded.

You can do the extra credit by implementing the following function located at the end of fs.c

void fs_defragment(struct fs_t* fs)

Submission

Upload/submit fs.c to autolab.

Grading Criteria

This lab will be graded out of 100 points.