Homework3 Basic File Server

This homework has been updated. The section that is related to directory manipulation has been moved to a separate homework that is due the week after

• Written Problems
• Programming Problems

What do you need to submit in the end

At the end of the homework, you need to submit the following files

1. A text file named WRITTEN that is for the written problems
2. README file that explains what you did for the programming homework, including the test cases
3. All your source code for programming problems

General Instructions

Make sure you’ve committed all your changes

% cd homework
% git remote add upstream http://ds-git.cs.columbia.edu/sd2693/homework.git
% git fetch upstream
% git checkout hw3

Now start working on your questions

After you are done

% git push origin hw3

Written Problems ↩

1. YFS’s architecture contains two types of messages: lock server messages and extent server messages. Design and write protocol buffers for the requests and responses for each type of message. This is a design question, so please try to be as general as possible in terms of what kinds of protocols you support with these messages.

2. Ben Bitdiddle wants to implement a ping-pong service using the RPC library in yfs labs.

class PingPong {
  public:
    PingPong(int port, string dst) {
        pthread_mutex_init(&m, NULL);
        pings_sent = pongs_received = 0;
        srv = new rpcs(port);
        srv->reg(ben_protocol::ping, this, &PingPong::ping_handler);
        srv->reg(ben_protocol::pong, this, &PingPong::pong_handler);
        cl = new rpcc(dst);
        cl->bind();
    }
    void do_pingpong() {
        ScopedLock ml(&m);
        int r;
        cl->call(ben_protocol::ping, "ping", r);
        pings_sent++;
        printf("one round of ping-pong\n");
    }
    void ping_handler() {
        int r;
        cl->call(ben protocol::pong, "pong", r);
    }
    void pong_handler() {
        ScopedLock ml(&m);
        pongs_received++;
    }
  private:
    rpcc *cl;
    rpcs *srv;
    pthread_mutex_lock m;
    int pings_sent;
    int pongs_received;
};

void main(int argc, char* argv[]) {
    PingPong s(atoi(argv[1]), string(argv[2]));
    while (1) {
        s.do_pingpong();
    }
}

Ben launched two local processes to test his PingPong program.

$./a.out 8888 127.0.0.1:9999
$./a.out 9999 127.0.0.1:8888

Unfortunately, he noticed that his program is stuck with nothing being printed out on the screen. Please help Ben explain why his program behaves like this.

Your task: Help Ben fix the bug. Update Ben’s code for that.

Programming Problems ↩

• Introduction
• Getting started
• Your Job
  • CREATE/MKNOD, LOOKUP, and READDIR
  • SETATTR, OPEN, WRITE and READ
• General Guidelines
  • Implementing the extent server
  • Deciding on the file system representation
  • Implementing a FUSE file system
  • Implementing SETATTR
  • Implementing OPEN/READ/WRITE:
  • Things to watch out for
  • Misc tips

Introduction

In this homework, you will embark on the actual file system implementation. In particular, you will need to get the following FUSE operations to work:

• CREATE/MKNOD, LOOKUP, and READDIR
• SETATTR, OPEN, WRITE and READ

Recall that YFS has the following architecture.

We provide you with skeleton code for both YFS and extent server modules above.

The YFS module implements the core file system logic. This module runs as a single process called yfs_client that supports a mountpoint on the local host. The code skeleton for this module consists of two pieces:

• The FUSE interface. This code lies in fuse.cc, and serves to translate FUSE operations from the FUSE kernel modules into YFS client calls. We provide you with much of the code needed to register with FUSE and receive FUSE operations; you will be mostly responsible for calling the appropriate methods on the yfs_client class and replying back over the FUSE interface.
• The YFS client. This code lies in yfs_client.{cc,h}. Unlike a traditional network file system client, the YFS client actually implements the file system logic! For example, when creating a new file, the yfs_client must add directory entries in the directory block itself (In a traditional network file system, the server performs this task). To fetch and store data blocks that contain file data or directory entries, yfs_client communicates with the extent server. Therefore, yfs_client should know how to interpret and manipulate extents in order to perform the appropriate file system operations.

The extent server acts as a centralized storage location for all the data representing your filesystem, much like a hard disk would. You will serve the same file system contents on multiple hosts, each running its own yfs_client. The only way they can share data is by reading and writing the extent server. The extent server code skeleton consists of two pieces:

• Extent client. This code lies in extent_client.{cc,h}. This is a wrapper class for communicating with extent server using RPCs.
• Extent server. The code lies in extent_server.{cc,h} and extent_smain.cc. The extent server manages a simple key-value store. The extent server simply stores entire files as strings (std::string), without interpreting the contents of those strings. It also stores information about the attributes of files. More concretely, your extent server should support put(key,value), get(key), getattr(key), and remove(key) RPCs.

Getting started

First, use a system with FUSE and the FUSE libraries installed (see the How to test your code locally for details).

Commit your homework 2 and fetch the homework 3 from upstream.

% cd homework
% git commit -am "Finished Homework 2"
% git fetch upstream
% git checkout hw3

To use YFS in this homework, you will need to start the extent server and yfs_client(s). If you are using the clic machines, choose a high port number that other students are not using. For example, to run the extent server on port 9118 in the background, type this:

% cd homework
% ./extent_server 9118 &

Next, start the yfs_client process using three parameters: a unique mount point (just create an empty directory), the port number for the extent server, and the port number for the running lock server. The mount point must be an empty directory that already exists. To start the yfs_client using mount point ./myfs and extent_server that listens on port 9118, and lock_server that listens on port 9229 in the background, type this:

% cd homework
% mkdir myfs
% sudo ./yfs_client ./myfs 3772 3762 &

On Linux, you need to run yfs_client as root, since normal users don’t usually have mount permission.

We provide you with the script start.sh to automatically start extent_server, lock_server and yfs_client and stop.sh to kill previously started processes. start.sh starts two yfs_clients with ./yfs1 and ./yfs2 mountpoints respectively. Thus, you can simply do:

% cd homework
% ./start.sh
% <do all the testing>
% ./stop.sh

The skeleton code implements only the GETATTR and STATFS operations, and so the file system you just mounted will not be useful at all. However, once you finish this homework, you should be able to run the Homework 3 tests successfully.

Note: testing this homework on the command line using commands like touch will not work until you implement the SETATTR operation.

Your Job

CREATE/MKNOD, LOOKUP, and READDIR

You must store the file system’s contents in the extent server, so that in future homework you can share one file system among multiple servers.

On some systems, FUSE uses the MKNOD operation to create files, and on others, it uses CREATE. The two interfaces have slight differences, but in order to spare you the details, we have given you wrappers for both that calls a single common routine called createhelper(). You should implement this routine.

If your server passes our tester on the official class programming environment, you are done. If you have questions about whether you have to implement specific pieces of file system functionality, then you should be guided by the tester: if you can pass the tests without implementing something, then you do not have to implement it. For example, you don’t need to implement the exclusive create semantics of the CREATE/MKNOD operation. You may modify or add any files you like, other than the tester script.

The Homework 3 tester includes a few scripts. Run it with your YFS mountpoint as the argument. Here’s what a successful run of test-homework-3-a.pl looks like:

% ./test-homework-3-a.pl ./yfs1
create file-yyuvjztagkprvmxjnzrbczmvmfhtyxhwloulhggy-18674-0
create file-hcmaxnljdgbpirprwtuxobeforippbndpjtcxywf-18674-1
...
Passed all tests!

The tester creates lots of files with names like file-XXX-YYY-Z and checks that they appear in directory listings.

Note that if at-most-once RPC was implemented correctly, the tests should pass with RPC_LOSSY set to 5 as well. (The correct implementation is included in the upstream code)

If test-homework-3-a.pl exits without printing “Passed all tests!”, then it thinks something is wrong with your file server. For example, if you run test-homework-3-a.pl on the skeleton code we give you, you’ll probably see an error message like this:

test-homework-3-a.pl: cannot create /tmp/b/file-ddscdywqxzozdoabhztxexkvpaazvtmrmmvcoayp-21501-0 : No such file or directory

This error message appears because you have not yet assigned a method to handle the CREATE/MKNOD operation with FUSE. See the main() method in fuse.cc for examples on how to make this assignment.

SETATTR, OPEN, WRITE and READ

Your job is to implement SETATTR, OPEN, WRITE, and READ FUSE operations in fuse.cc. You must store the file system’s contents in the extent server, so that you can share one file system among multiple yfs_clients.

If your server passes the tester test-homework-3-b.pl, then you have implemented these four operations correctly. If you have questions about whether you have to implement specific pieces of FUSE functionality, then you should be guided by the tester: if you can pass the tests without implementing something, then don’t bother implementing it until it is absoultely needed.

The test-homework-3-b.pl script tests reading, writing, and appending to files, as well as testing whether files written on one yfs_client instance can be read through a second one. To run the tester, first start two yfs_clients using the start.sh script. It runs two yfs_client processes each mounting the same file system under a different name (yfs1 or yfs2).

% ./start.sh

Now run test-homework-3-b.pl by passing the yfs1 and yfs2 mountpoints. Since the script tests each yfs_client sequentially, we do not need to worry about locking for this homework.

% ./test-homework-3-b.pl ./yfs1 ./yfs2
Write and read one file: OK
Write and read a second file: OK
Overwrite an existing file: OK
Append to an existing file: OK
Write into the middle of an existing file: OK
Check that one cannot open non-existant file: OK
Check directory listing: OK
Read files via second server: OK
Check directory listing on second server: OK
Passed all tests
% ./stop.sh

If test-homework-3-b.pl exits without printing “Passed all tests!” or hangs indefinitely, then something is wrong with your file server.

General Guidelines

Implementing the extent server

You will need to implement the extent server in extent_server.cc. There are four operations: put(key,value), get(key), getattr(key), and remove(key). The put and get RPCs are used to update and retrieve an extent’s contents. The getattr RPC retrieves an extent’s attributes. The attribute consists of the file size, last modification time (mtime), change time (ctime), and last access time (atime). Tracking this data in the extent server should be straightforward in the handlers for the put(key,value) and get(key) RPCs. Wikipedia has a succinct description of when these three times should be updated.

Deciding on the file system representation

YFS should name all files and directories with a unique identifier (much like the i-node number in an on-disk UNIX file system). We have defined such an 64-bit identifier (called inum) in yfs_client.h. Since FUSE accesses each file and directory in the file system using a unique 32-bit identifier, we suggest you use the least significant 32-bits of inum as the corresponding FUSE identifier.

When creating a new file or directory, you must assign a unique inum. The easiest thing to do is to pick a number at random, hoping that it will indeed be unique. (What’s the collision probability as the number of files and directories grows?)

YFS needs to tell whether a particular inum refers to a file or a directory. To do this, you should ensure that any 32-bit FUSE identifier for a file has the most significant bit equal to one; likewise, that bit for a directory should be set to zero. The provided method yfs_client::isfile assumes this property holds for inum.

Next, you must choose the format for storing and retrieving file system meta-data (i.e. file/directory attributes and directory contents). You do not need to store or retrieve file contents in this homework yet. A file or dir’s attribute contains information such as the file’s length, modification times. A directory’s content contains a list of name to inum mappings. Thus, resolving a file’s inum involves a series of lookups starting from the file system root (The root directory has a well-known FUSE id of 0x000000001).

It is convenient to store and retrieve the entire dir content (or file content, for later homework) in the extent server using the file/dir’s inum as the key to the extent server’s put(key,value) and get(key) functions. However, since YFS must also be able to retrieve the file attribute information based on the file/dir’s inum, we ask you to implement a separate function, called extent_server::getattr(key), to retrieve a file/dir’s attribute based on its inum.

Implementing a FUSE file system

For these homework, you will be interfacing with FUSE via its low level API. We have provided you with lots of code in the main() method of fuse.cc that handles much of the low level nastiness, along with skeleton code for the operations you will need to implement. You can find details on what the methods you implement need to do at fuse_lowlevel.h. Study our getattr implementation to get a sense of how a full FUSE operation handler works, and how it communicates its results and errors back to FUSE. Every FUSE handler should either pass its successful result using one of the fuse_reply_… routines, or else call fuse_reply_err to report an error.

Sending back directory information for the READDIR operation is a bit tricky, so we’ve provided you with much of the necessary code in the dirbuf_add, reply_buf_limited, and fuseserver_readdir methods.

READDIR in fuse.cc is to get the directory listing from your yfs_client, and add it to the b data structure using dirbuf_add.

Though you are free to choose any inumber identifier you like for newly created files, FUSE assumes that the inumber for the root directory is 0x00000001. Thus, you’ll need to ensure that when YFS mounts, it is ready to export an empty directory stored under that inumber.

Implementing SETATTR

The operating system can tell your file system to set one or more attributes via the FUSE SETATTR operation. As always, see the FUSE lowlevel header file for the necessary function specifications. The to_set argument to your SETATTR handler is a mask that informs the method which attributes should be set. There is really only one attribute (the file size attribute) you need to pay attention to (but feel free to implement the others if you like), which has the corresponding bitmask, FUSE_SET_ATTR_SIZE. Just AND (i.e., &) the to_set mask value with an attribute’s bitmask to see if the attribute is to be set. The new value for the attribute to be set is in the attr parameter passed to your SETATTR handler.

Note that setting the size attribute of a file can correspond to truncating it completely to zero bytes, truncating it to a subset of its current length, or even padding bytes on to the file to make it bigger. Your system should handle all these cases correctly.

Implementing OPEN/READ/WRITE:

You are free to store the file contents however you like with the extent_server. You may, for example, treat a file’s contents as a std::string. (If so, how would you support very large files? We would not test your FS for large files, but it’s a good design exercise.)

READ/WRITE operations are straightforward. A non-obvious situation may arise if the client tries to write at a file offset that’s past the current end of the file. Linux expects the file system to return ‘\0’s for any reads of unwritten bytes in these “holes”. See the man page for lseek(2) for details.

Things to watch out for

This homework creates files using two different YFS-mounted directories. If you were not careful earlier, you may find that the components that assign inumbers for newly-created files and directories choose the same identifiers. One possible way to fix this may be to seed the random number generator differently depending on the process’s pid.

This homework writes arbitrary data to the file, rather than null-terminated C-style strings. If you used the standard std::string constructor in fuse.cc to create a string to pass to your yfs_client, (i.e., std::string(buf)), you will get odd errors when there are characters equal to ‘\0’ in the buffer. Instead, you should use a different constructor that allows for char buffers of arbitrary data: std::string(buf, size).

Misc tips

The start.sh scripts redirects the STDOUT and STDERR of the different processes to different files in the current working directory. For example, any output you make from fuse.cc will be written to yfs_client1.log. Thus, you should look at these files for any debug information you print out in your code.

If you wish to test your code with only some of the FUSE hooks implemented, be advised that FUSE may implicitly try to call other hooks. For example, FUSE calls LOOKUP when mounting the file system, so you may want to implement that first. FUSE prints out to the yfs_client1.log file the requests and results of operations it passes to your file system. You can study this file to see exactly what hooks are called at every step.

When you’re done with Homework 3, you should be able to read and write files in your file system. For example, use the start.sh script to start up two separate yfs_clients with mount points at ”./yfs1” and ”./yfs2”, which both use the same extent server for organizing its data:

% cd homework
% ./start.sh

Then, you can write files to one directory and read them from the other:

% ls -l yfs1 yfs2
yfs1:
total 0

yfs2:
total 0
% echo "Hello world" > yfs1/hello.txt
% ls -l yfs1 yfs2**
yfs1:
total 0
-rw-rw-rw- 1 root root 12 Sep  6 20:14 hello.txt

yfs2:
total 0
-rw-rw-rw- 1 root root 12 Sep  6 20:14 hello.txt
% cat yfs2/hello.txt
Hello world

Afterwards, be sure to stop your all the processes:

% ./stop.sh

If you try the above commands without implementing the required SETATTR, WRITE and READ operations, you will get an error.