From OSLab

Labs: HW4

File Systems

Assigned: 11/3/06 Due: 11/17/06

Objective

The goal of this lab is to write a simple UNIX-like file system. The file system you will write make the following simplifying assumptions:

• The file system resides on a disk that is 128KB in size.
• There is only one root directory. No subdirectories are allowed.
• The file system supports a maximum of 16 files.
• The maximum size of a file is 8 blocks; each block is 1KB in size.
• Each file has a unique name, the file name can be no longer than 8 characters.

The layout of your 128 KB disk is as follows

• The first 1KB block is called the super block. It stores the free block list and index nodes (inode) for each file.
• The remaining 127 1KB blocks store data blocks of the files on your file system.
• The exact structure of the super block is as follows.
  • The first 128 bytes stores the free block list. Each entry in this list indicates whether the corresponding block is free or in use (if the i-th byte is 0, it indicates that the block is free, else it is in use). Initially all blocks except the super block are free.
  • Immediately following the free block list are the 16 index nodes, one for each file that is allowed in the file system. Initially, all inode are free. Each inode stores the following information:

    char name[8]; //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 48 bytes in size; Since you have 16 of these, the total space occupied by the inodes is 768 bytes. The free/used block information (mentioned above) is 128 byes, for a total of 896 bytes used in the 1024-byte superblock. The remaining bytes are unused.

Documentation and Resources:

• The BFS filesystem in the Linux kernel source is a good example to start from, as it is a full-fledged disk-based filesystem in about 1000 lines of code. (it's for an obscure filesystem used by the SCO UnixWare boot loader, but that doesn't really matter) If you want to experiment with this filesystem, you will need to find the mkfs.bfs utility in order to create a filesystem that you can mount.
• Practical File System Design with the Be File System - http://www.nobius.org/~dbg/ Although this is written for BeOS, not Linux, it's a good guide nevertheless. In addition, I think the BSD demon book (Design and Implementation of the 4.4 BSD Operating System, McKusick et al.) has a good overview of VFS, but it's not available online.
• The VFS chapter of Linux Kernel 2.4 Internals, by Tigran Aivazian: http://www.tldp.org/LDP/lki/lki-3.html
• Both Linux Kernel Development (Love) and Understanding the Linux Kernel (Bovet & Cesati) have chapters on the VFS interface.

Implementation

• You should implement your filesystem as a loadable kernel module, registering through the proper VFS hooks.
• To create a 128KB block device to test your filesystem on, use the loopback device driver:

    dd if=/dev/zero of=/tmp/file.dat bs=1k count=128    # create a 128KB file
    losetup /dev/loop0 /tmp/file.dat                    # attach it to /dev/loop0
    mount -t myfs /dev/loop0 /mnt                       # mount it
    umount /mnt                                         # unmount it
    losetup -d /dev/loop0                               # disconnect it

Note that there is no need for a mkfs program, as a superblock of all zeros corresponds to an empty filesystem. (i.e. all blocks free, all inodes free)

You will need to implement the following:

• module_init - invoke register_filesystem
• fill_super method - read the superblock, invoked at mount time
• struct super_operations, containing the methods alloc_inode, destroy_inode, read_inode, write_inode, delete_inode, put_super, write_super, statfs.
• struct inode_operations for directory inodes, with methods create, lookup, link, unlink, rename. (note that file inodes are assigned a struct inode_operations as well, but it can be completely empty)
• struct file_operations for directory inodes, with methods read, readdir, and fsync
• struct file_operations for file inodes, with methods llseek, read, write, mmap, and sendfile. (these should point to the corresponding generic_* operations)
• struct address_space_operations, containing readpage, writepage, sync_page, prepare_write, commit_write, bmap.

Testing

• Data integrity - create several files of varying length on a different filesystem, containing random data. (e.g. head -c13016 /dev/random > /tmp/file1) Copy these files to the filesystem, and then recopy them several times. Checksum the originals and copies to verify integrity. Unmount the filesystem, remount it, and verify that the files remain unchanged.
• Functionality - verify that the file size returned by ls -l agrees with that from wc. Copy a small executable (e.g. /bin/dmesg) to the filesystem and verify that it can be executed.
• Correctness - try to overflow the filesystem, e.g. cat /dev/zero > /mnt/bigfile. Try to create a file with a name longer than 8 characters. Change the permissions of a file. Verify reasonable - or at least non-crashing - behavior.

Submission

Please submit via email the source code for the filesystem module, a test log (e.g. use script to capture the terminal session while testing manually, or put the commands in a script file and run it with sh -x), and a short (1 page is OK) writeup of your design.