W4118 OPERATING SYSTEMS I

Fall 2013 -- Junfeng Yang

DUE: Thu 12/05 at 12:05am ET

The written problems are to be done individually. The programming problems are to be done in your assigned 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.

  1. MOS 4.27
  2. The performance of a file system depends upon the cache hit rate (fraction of blocks found in the cache). If it takes 1 msec to satisfy a request from the cache, but 40 msec to satisfy a request if a disk read is needed, give a formula for the mean time required to satisfy a request if the hit rate is h. Plot this function for values of h varying from 0 to 1.0.

  3. MOS 4.32
  4. A UNIX file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contains 10 direct entries, and one single, double, and triple indirect entry each?

  5. MOS 4.33
  6. How many disk operations are needed to fetch the i-node for the file /usr/ast/courses/os/handout.t? Assume that the i-node for the root directory is in memory, but nothing else along the path is in memory. Also assume that all directories fit in one disk block.

  7. Explain the advantages and disadvantages of using log-structured file systems for flash.
  8. 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.
  9. 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?
  10. In the software v.s. hardware virtualization paper, the author discussed the problem with popf in Section 4.4. What exactly is the problem?
  11. Explain how page translation works in software virutlization and with nested page tables.

Programming Assignment: Copy-on-write File Operation (60 pts)

In this assignment, you will implement a special copy operation on ext4 filesystem to support copy-on-write (COW) file copy operation. In certain scenarios, the new feature can help developers save a lot of storage space.

Recall that the copy-on-write strategy is mainly used in virtual memory management. When a process copies itself, the operating system doesn't really copy the pages in the memory until they get modified. In this way, the OS can speed up the forking time. Similarly, we would like to apply this strategy to the file copy operation, which means the file content won't get copied until the file is modified.

In this assignment, we will implement copy-on-write feature on EXT4 filesystem.

Part A: Implementing System Call sys_ext4_cowcopy() (20 pts)

In the first part of this assignment, you will implement a system call in fs/ext4/cowcopy.c with following signature:

        asmlinkage int sys_ext4_cowcopy(const char __user *src, const char __user *dest);
    

The system call has two parameters:
src: path to the file to be copied
dest: path to the copy

The system call should check following conditions:
1) src must be a regular file and it cannot be a directory, otherwise return -EPERM.
2) src must be a file in ext4 file system, otherwise return -EOPNOTSUPP.
3) src and dest should be in the same device, otherwise return -EXDEV.

After invoking the system call with proper parameters, the given source file (i.e. src) will have a copy at destination path (i.e. dest). Note that the copy is not a real copy since it is sharing all meta data and disk blocks with original file.

When we read the content of the copy, it will read the disk blocks owned by original file, just like we are reading an real copy of the original file. However, when we write/append to the copy or the original file, we will make a real copy of the file to make sure the two files can have different contents. In short, when we write to one file (the copy or the original file), we create a real copy to write into and the content of the other file should not be affected.

To trigger the real copy operation when write to a COW copied file, you need to modify open() operation of ext4 file system. Please find detailed instructions in Part B.

Part B: Copy-on-write (40 pts)

In this part, you would need to modify the EXT4 implementation of file_operation.open to handle copy-on-write case. If the file to be opened is a COW file and the caller has an intent to write file (which we can tell from the access mode flag such as O_WRONLY or O_RDWR), make a copy of this file before the open call can proceed.

For the assignment, we do not want to change the physical layout of inodes or the superblock since it adds to the complexity. To store extra data of an inode, you can use the extended attributes (xattr).

To copy the file within the kernel, you may refer to LKD16 The Page Cache and Page Writeback.

Hint: how to test your code on Android

You may find mount command useful since it can report the filesystem and mount point of each device.

Submit

Commit your source code changes using the git add and git commit commands you learned from the previous assignments. Remember to add your new file to the code repository. Then use the git diff command to get the code change. You should compare with the original version, so please do

    git diff 365a6e06
    

Here 365a6e06 refers to the initial version of the kernel source before you make any modifications. Then submit the code difference in a .patch file. The file name should be hw6-<your uni>-code.patch.