6.824 - Fall 2007

6.824 Lab 4: MKDIR, REMOVE, and Locking

Last change: $Date: 2007/10/02 02:12:52 $

Due: Friday, Oct 5th, 5:00pm.


In this lab, you will continue to add functionality to your file server. You will: The locking is required will ensure that concurrent modifications to the same file or directory occur one at a time.

Getting Started

Since you are building on the past labs, ensure the code in your Lab 3 directory passes all tests for Labs 1, 2, and 3 before starting in on this lab.

Begin by initializing your Lab 4 directory with your implementation from Lab 3 and then updating it with the testers from http://pdos.csail.mit.edu/6.824/labs/yfs-lab4.tgz for Lab 4.

$ wget -nc http://pdos.csail.mit.edu/6.824/labs/yfs-lab4.tgz
$ rsync -av l3/* l4
$ tar xzvf yfs-lab4.tgz

Note that this will write over Makefile in the l4 directory, in order to link lock_client.o in with yfs_server. This means if you modified the Lab 3 Makefile, you will need to redo those changes in l4/. This also writes over start.sh and stop.sh.

The rest of this lab has two parts.

Part 1: Your Job

Your job in part 1 is to handle the MKDIR and REMOVE FUSE operations. This should be a straightforward extension of your Lab 3 code. Make sure that when you choose the inumber for a new directory created with MKDIR, that inumber must have its most significant bit set to 0 (as explained in Lab 2, unless you changed the way YFS tells files and directories apart).

If your server passes the tester (see below), then you are done.

When you're done with Part 1, the following should work:

% ./start.sh
% mkdir yfs1/newdir
% echo hi > yfs1/newdir/newfile
% ls yfs1/newdir/newfile
% rm yfs1/newdir/newfile
% ls yfs1/newdir
% ./stop.sh

Part 1: Testing

You can test your file server using the test-lab-4-a.pl script. The script creates a directory, creates and deletes lots of files in the directory, and checks file and directory mtimes and ctimes. Note that this is the first test that explicitly checks the correctness of these time attributes. A create should change both the parent directory's mtime and ctime.

If the tester is happy, it will say "Passed all tests!". Here's a successful run:

% ./start.sh
% ./test-lab-4-a.pl ./yfs1
mkdir ./yfs1/d3319
create x-0
delete x-0
create x-1
checkmtime x-1
delete x-33
Passed all tests!
% ./stop.sh

If you're unsure about what FUSE operations this tester will produce, check out this sample fuse2yfs1.log (101 KB) for one possible sequence.

Part 2: Your Job

Your server's CREATE handler probably reads the directory's contents from the extent server, makes some changes or additions, and writes the new extent. If two clients were to issue simultaneous CREATEs for different file names in the same directory to two YFS servers sharing the same file system, chances are that only one file would be exist in the end. The correct answer, however, is for both files to exist.

A convenient way to fix this "race condition" is for the file servers to use locks to force the two CREATE operations to happen one at a time. That is, a server would acquire a lock before starting the CREATE, and only release the lock after finishing the write of the new information back to the extent server. If there are concurrent operations, the locks force one of the two operations to delay until the other one has completed.

You must choose what the locks refer to. At one extreme you could have a single lock for the whole file system, so that operations never proceed in parallel. At the other extreme you could lock each entry in a directory, or each field in the attributes structure. Neither of these is a good idea! A single global lock prevents concurrency that would have been OK, for example CREATEs in different directories. Fine-grained locks have high overhead and make deadlock likely, since you often need to hold more than one fine-grained lock.

Your best bet is to associate one lock with each file handle. Use the file or directory's inumber as the name of the lock (i.e. pass the inumber, as a std::string to acquire and release). The convention should be that any YFS server operation should acquire the lock on the file or directory it uses, perform the operation, finish updating the extent server (if the operation has side-effects), and then release the lock on the inumber. Make sure to release the lock even when returning an error from a yfs_server operation. You may find adding these acquire and release calls a bit tedious. It's okay to do things the tedious way, but feel free to look for ways to make things a bit easier on you. Hint: goto is not always considered harmful.

You'll use your lock server from Lab 1. Our original template for the yfs_server constructor that we gave you in Lab 2 included the destination address of a lock server, so it should be very easy to add a lock_client object to the yfs_server and simply call its acquire and release methods.

Part 2: Testing

Test your locking with test-lab-4-b and test-lab-4-c. The testers take two directories as arguments. They issue concurrent operations in the two directories and check that the results are consistent with the operations executing in some serial order. Here's a successful execution of the testers:

% ./start.sh
% cc -o test-lab-4-b test-lab-4-b.c
% ./test-lab-4-b ./yfs1 ./yfs2
Create then read: OK
Unlink: OK
Append: OK
Readdir: OK
Many sequential creates: OK
Write 20000 bytes: OK
Concurrent creates: OK
Concurrent creates of the same file: OK
Concurrent create/delete: OK
Concurrent creates, same file, same server: OK
test-lab-4-b: Passed all tests.
% ./stop.sh
% cc -o test-lab-4-c test-lab-4-c.c
% ./start.sh
% ./test-lab-4-c ./yfs1 ./yfs2
Create/delete in separate directories: tests completed OK
% ./stop.sh

If you try this before you add locking, your server will probably fail the "Write 20000 bytes" test or the "Concurrent creates" test in test-lab-4-b.

You might want to test your solution to Part 2 with test-lab-4-a.pl first, to make sure you didn't break anything. You might then test with test-lab-4-b, but giving it the same directory twice, to make sure you handle concurrent operations in one server before you go on to concurrent operations in two servers.

If you're unsure about what FUSE operations these two testers will produce, check out the following FUSE trace logs:


This is the first lab that creates files using two different YFS-mounted directories. If you were not careful in earlier labs, 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 is also the first lab that 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).

Collaboration policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assigment. You are not allowed to look at anyone else's solution (and you're not allowed to look at solutions from previous years). You may discuss the assignments with other students, but you may not look at or copy each others' code.

Handin procedure

You will need to email your completed code as a gzipped tar file to 6.824-submit@pdos.csail.mit.edu by the deadline at the top of the page. To do this, execute these commands:
% cd ~/yfs/l4
% make clean
% rm core*
% rm *log
% cd ..
% tar czvf `whoami`-lab4.tgz l4/
That should produce a file called [your_user_name]-lab4.tgz in your yfs/ directory. Attach that file to an email and send it to the 6.824 submit address.
For questions or comments, email 6.824-staff@pdos.csail.mit.edu.
Back to 6.824 home.