Homework3.5 Directory and Locking

This homework has been split from homework 3

• 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. README file that explains what you did for the programming homework, including the test cases
2. All your source code for programming problems

General Instructions

Make sure you’ve committed all your changes

% cd homework
% git checkout hw3

Now start working on your questions

After you are done

% git push origin hw3

Programming Problems ↩

• Introduction
• Your Job
  • MKDIR, REMOVE
  • Locking
• General Guidelines
  • What to lock?

Introduction

In this homework, you will need to get the following FUSE operations to work:

• MKDIR and REMOVE

You also need to add simple locking, which is required to ensure that concurrent modifications to the same file or directory occur one at a time.

Your Job

MKDIR, REMOVE

This should be straightforward. 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, unless you changed the way YFS tells files and directories apart). When you have finished implementation, the following should work:

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

If your implementation passes the test-homework-3-c.pl script, the basic implementation of these methods are done. The test script creates a directory, then 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. Here is a successful run of the tester:

% ./start.sh
% ./test-homework-3-c.pl ./yfs1
mkdir ./yfs1/d3319
create x-0
delete x-0
create x-1
checkmtime x-1
...
delete x-33
dircheck
Passed all tests!
% ./stop.sh

Locking

You are going to ensure the consistency of your file system when many clients simultaneously perform file system operations on the same file system image via different yfs_client processes. Your current implementation does not handle concurrent operations correctly. For example, your yfs_client’s create method probably reads the directory’s contents from the extent server, makes some changes or additions, and stores the new contents at the extent server. Suppose two clients issue simultaneous CREATEs for different file names in the same directory via different yfs_client processes. Both yfs_client processes might fetch the old dir contents at the same time and each inserts the newly created file for its client and writes back the new dir contents. As a result, only one of the file would be present in the dir in the end. The correct answer, however, is for both files to exist. The CREATE example is just one of the “race conditions”. Many others exist: e.g. concurrent CREATE and UNLINK, concurrent MKDIR and LOOKUP, etc.

To fix the race conditions, the yfs_client must use locks to ensure that the two operations that access the same file or directory happen one at a time. For example, a yfs_client 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. Because each yfs_client can run as a separate process on a different machine, all yfs_clients have to acquire locks from the same lock server. Now you can see why the lock server implementation from Homework 2 comes in handy!

Now implement locking for yfs_client to ensure that concurrent operations from different yfs_clients proceed correctly. The testers for this part of the homework are test-homework-3-d and test-homework-3-e (The source files are test-homework-3-d.c and test-homework-3-e.c). The testers take two directories as arguments and 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
% ./test-homework-3-d ./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-homework-3-d: Passed all tests.
% ./stop.sh
%
% ./start.sh
% ./test-homework-3-e ./yfs1 ./yfs2
Create/delete in separate directories: tests completed OK
% ./stop.sh

If you try this before you add locking, it will fail at “Concurrent creates” test in test-homework-3-d.

After you are done with locking, you should also test with test-homework-3-c.pl to make sure you didn’t break anything. You might also test with test-homework-3-d with the same directory for both arguments, to make sure you handle concurrent operations correctly with only one server before you go on to test concurrent operations in two servers.

General Guidelines

What to lock?

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 okay, 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 to acquire and release). The convention should be that any yfs_client 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. You must be careful about releasing the locks in all circumstances upon return from yfs_client 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 Homework 1. Our original template for the yfs_client constructor that we gave you in Homework 2 included the destination address of a lock server, so it should be very easy to add a lock_client object to the yfs_client and simply call its acquire and release methods.