Project 5a: Distributed File Server
Dec 3: you may be worried about atomicity. What if your server
crashes between a write to a directory and write to the corresponding
new inode? You need not worry about this case. When file systems
like ext2 or your file system crash, fsck needs to be run to fix such
any inconsistencies. You need not write an fsck utility.
Dec 3: don't modify udp.c or udp.h or use a different underlying
layer (e.g., tcp). We want you to build over an unreliable layer to
demonstrate the usefulness of an idempotent protocol. Furthermore, we
may replace udp.c during testing to emulate dropped packets. So if
you make any changes to that file, you may lose that code.
Dec 3: with UDP, many undesirable things may happen: messages may
be split, reordered, or dropped. Building a layer for handling
reordereing and splitting would be painful, and you'll likely do that
if you take CS 640. Thus, we only expect you to deal with dropped
messages via retry. During testing we will not split your
Dec 3: Fixed mfs.h.
In this assignment, you will be developing a working distributed file
server. We provide you with only the bare minimal UDP communication code;
you have to build the rest.
A Basic File Server
Your file server is built as a stand-alone UDP-based server. It should wait
for a message and then process the message as need be, replying to the given
Your file server will store all of its data in an on-disk file which will
be referred to as the file system image . This image contains the on-disk
representation of your data structures; you should use these system calls
to access it: open(), read(), write(), lseek(), close(), fsync() .
To access the file server, you will be building a client library. The
interface that the library supports is defined in mfs.h . The
library should be called libmfs.so , and any programs that wish to access
your file server will link with it and call its various routines.
On-Disk File System: A Simple xv6-like File System
Your on-disk file system will be similar to the file system used in xv6.
Since Project 5B involves the xv6 file system as well, studying it should help
you in both projects.
Your on-disk structures should roughly follow that of xv6. You can learn
about the structures in
fs.c in xv6. There
are some notable changes though:
- Block size in xv6 is 512 bytes. It will be 4096 bytes in this project.
- There will be only 14 direct pointers in the inode. You do not need to
implement indirect pointers.
- Directory entries in xv6 are limited to 14 characters. They can be upto
60 characters (as seen in
mfs.h) in this project.
- While xv6 has hard links, you do not need to support them in this
- There will be a maximum of 64 inodes (fitting inside one block) in the
file system. There will be a maximum of 1024 data blocks in the file
A note about inodes: these are simple structures containing a
type field (file or directory), a
size field, and an
array of direct pointers. The total size of each inode is 64 bytes, and hence
a 4096 block can store 64 inodes. The type field is 0 indicating that the inode
A note about directories: each directory has an inode, and points to one or
more data blocks that contain directory entries. Each directory entry should be
simple, and consist of 64 bytes: a name and an inode number pair. The name
should be a fixed-length field of size 60 bytes; the inode number is just an
integer (4 bytes). When a directory is created, it should contain two entries:
the name . , which refers to this new directory's inode number, and
.. , which refers to he parent directory's inode number. For directory
entries that are not yet in use (in an allocated 4-KB directory block), the
inode number should be set to -1. This way, utilities can scan through the
entries to check if they are valid.
When your server is started, it is passed the name of the file system image
file. If this file does not exist, the file server should create it, and
initialize it properly, and force it to disk. Such initialization includes
creating the super block, inodes, bitmap, and creating a single
root directory with proper . and .. entries. The root inode
number should be 0.
When booting off of an existing image, your server should read in the
super block (and keep an in-memory version of it), as well as the entire
set of inodes and keep it in-memory too.
The client library should export the following interfaces:
- int MFS_Init(char *hostname, int port): MFS_Init() takes a host name
and port number and uses those to find the server exporting the file system.
- int MFS_Lookup(int pinum, char *name): MFS_Lookup() takes the parent
inode number (which should be the inode number of a directory) and looks up
the entry name in it. The inode number of name is returned. Success:
return inode number of name; failure: return -1. Failure modes: invalid pinum,
name does not exist in pinum.
- int MFS_Stat(int inum, MFS_Stat_t *m): MFS_Stat() returns some
information about the file specified by inum. Upon success, return 0,
otherwise -1. The exact info returned is defined by MFS_Stat_t. Failure modes:
inum does not exist.
- int MFS_Write(int inum, char *buffer, int block): MFS_Write() writes a
block of size 4096 bytes at the block offset specified by block . Returns 0
on success, -1 on failure. Failure modes: invalid inum, invalid block, not a
regular file (because you can't write to directories).
- int MFS_Read(int inum, char *buffer, int block): MFS_Read() reads
a block specified by block into the buffer from file specified by
inum . The routine should work for either a file or directory; directories
should return data in the format specified by MFS_DirEnt_t. Success: 0,
failure: -1. Failure modes: invalid inum, invalid block.
- int MFS_Creat(int pinum, int type, char *name): MFS_Creat() makes a
file ( type == MFS_REGULAR_FILE) or directory ( type == MFS_DIRECTORY)
in the parent directory specified by pinum of name name . Returns 0 on
success, -1 on failure. Failure modes: pinum does not exist, or name is too
long. If name already exists, return success (think about why).
- int MFS_Unlink(int pinum, char *name): MFS_Unlink() removes the file or
directory name from the directory specified by pinum . 0 on success, -1
on failure. Failure modes: pinum does not exist, directory is NOT empty. Note
that the name not existing is NOT a failure by our definition (think about why
this might be).
- int MFS_Shutdown(): MFS_Shutdown() just tells the server to force all
of its data structures to disk and shutdown by calling exit(0). This interface
will mostly be used for testing purposes.
The key behavior implemented by the server is idempotency.
Specifically, on any change to the file system state (such as a MFS_Write,
MFS_Creat, or MFS_Unlink), all the dirtied buffers in the server are committed
to the disk. The server can achieved this end by calling fsync() on the
file system image. Thus, before returning a success code, the file system
should always fsync() the image.
Now you might be wondering: why do this? Simple: if the server crashes, the
client can simply timeout and retry the operation and know that it is OK to do
so. We'll be talking about this more when we talk about NFS, the Network File
System from the company formerly known as Sun.
Now you might be wondering: how do I implement a timeout? Simple, with the
select() interface. The select() calls allows you to wait for a reply
on a certain socket descriptor (or more than one, though that is not needed
here). You can even specify a timeout so that the client does not block
forever waiting for data to be returned from the server. By doing so, you can
wait for a reply for a certain amount of time, and if nothing is returned, try
the operation again until it is successful.
The TAs will provide some images for you to get started with, but you
should be able to create your own empty ones and populate them
accordingly. The TAs will also provide some fun tools to use your file system,
like mfsput (which will take a filename as input, and create a file in your
MFS file system based on that file) and mfscat (which will dump the contents
of a file in MFS to the screen).
Your server program must be invoked exactly as follows:
prompt> server [portnum] [file-system-image]
The command line arguments to your file server are to be interpreted as follows.
- portnum: the port number that the file server should listen on.
- file-system-image: a file that contains the file system image.
If the file system image does not exist, you should create it and properly
initialize it to include an empty root directory.
Your client library should be called libmfs.so and be built as usual. It
should implement the interface as specified by mfs.h , and in particular
deal with the case where the server does not reply in a timely fashion; the
way it deals with that is simply by retrying the operation, after a timeout of
some kind (default: five second timeout).
Some Helper Code
To get you going, we have written some simple UDP code that can used to
create a client and a server. It can be found in
Currently, the maximum size of a file is 14 * 4K = 56K. Extend the file system
to add an indirect pointer so that the maximum size of a file is 13 * 4K + 1024
* 4K = 4148K.