Homework 6 is due 05/02 at 12:01am EDT
The written problems are to be done individually. The programming problems are to be done in your assigned programming groups. All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.
Written Assignment (40 pts)
Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.
- MOS 4.27
- MOS 4.32
- MOS 4.33
- Describe when you run an unlink() operation to remove a file on the ext3 file system. Be specific about what disk blocks have to be written where in what order. State your assumptions.
- The ext3 fsck program recovers a crashed ext3 file system by scanning the journal of this file system and replaying each record in the journal. The ext3 fsck program also clears the journal to save space for new journal records. Is there a strict order between the two steps? Why or why not?
- In the software v.s. hardware virtualization paper, the author discussed the problem with popfl in Section 4.4. What exactly is the problem?
- As the number of cores keeps increasing, the probability that some cores fail at any given moment also increases. What are the implications of this trend on Barrelfish?
- Write pseudo code to implement the pthread_create wrapper of the Tern memoizer. Note you need to describe your data structure for maintaining deterministic thread IDs. In addition, think of what may go wrong when the child thread calls self().
Please complete and submit a private group programming assignment evaluation. The evaluation should be in a separate file called evaluation.txt that is submitted with your individual written assignment submission.
Programming Assignment: Tagging The Files (60 pts)
Programming assignments are to be done in your assigned groups in xv6. For the programming problems, you are required to write README documenting your files and codes. In this programming assignment, you'll implement a mechanism to tag files in xv6.
The files needed for this assignment are distributed using the Git distributed version control software. To learn about Git, take a look at the Git user's manual, or, if you are already familiar with other version control systems, you may find this Git overview useful.
To get started, run the following commands
$ git clone http://repair.cs.columbia.edu/git/xv6 xv6
$ cd xv6
$ git checkout -b hw6 origin/hw6
Submission instructions
When you are ready to hand in your solution, put your UNI in conf.mk, commit all your changes, and run make handin in the xv6 directory. This will generate hw6-<your uni>.tar.gz for you, which you can then upload via courseworks. This tar ball includes a snapshot of all xv6 source code and a patch generated using git diff origin/hw6 hw6. Thus, be sure you commit all your changes (including the new files you add) before running make handin. Double-check the patch in the generated tar ball. It should contain all your changes in the source code.
We will be grading your solutions with a grading program. You can run make grade to test your solutions with the grading program. Note that it takes a while to run the test programs, so please be patient.
Description
In this assignment, you will add a new feature to the xv6 file system to allow users to tag files with arbitrary key-value pairs they define. This tagging feature can be very useful. (I'm sure you can come up with many applications of this feature, e.g., desktop search.) It actually exists in many applications already. For example, you can add tags to PDF, JPG, MP3 and many other media files. However, these application-specific implementations are ad hoc and must be re-implemented for new applications. In this assignment, you'll provide a general implementation in the xv6 file system so that it applies to all file types.
You'll need to implement the following three system calls:
- int ftag(int fd, char *key, char *buf, int len);
- int funtag(int fd, char *key);
- int gettag(int fd, char *key, char *buf, int len);
System call ftag() tags a file identified by file descriptor fd with a new key-value pair, with the key being key and value buf. Argument key is a null-terminated string with a maximum length of 10 and minimum length of 2, counting the ending null byte. Argument buf specifies the value in the key-value pair, and len specifies the length of buf. If key already exists in file fd's tags, this system call should overwrite the old tag with the new one.
System call funtag() removes a tag with key key from the file fd. If there is no key-value pair matching key, funtag() should return an error.
System call gettag() retrieves the value mapped to key from the file fd. The retrieved value is stored in buf whose length is specified via len. gettag() should return the length of the value if it exists and -1 otherwise. If the value is longer than len, gettag should return an error.
To implement these system calls, you'll need to change the on-disk representation of an inode and add code to fs.c. You also need to change mkfs.c so that the new file system layout created by mkfs is consistent with the file system layout expected by fs.c.
Your implementation should consider different corner cases and return errors correspondingly.
To give you more time to study for your final exams, we've decided to simplify things for you: all tags of a file fit within one 512-byte disk block. That is, you never have to allocate more than one disk block to store the tags for each file.