Sample Homework Assignment

(60 points) Extend the Linux kernel with a file snapshot facility using copy-on-write using VirtualPC. Instead of a commercial snapshot facility, where user files are automatically copied on a fixed schedule (say hourly), we want to use a copy-on-write semantics to keep an automatic backup of recently modified files. The idea is simple: When a write operation to a file is performed, a copy of the files (without the write modification) is created with a unique name. Of course, if a copy was created for each write, we soon would run out of disk space.
A first refinement is modeled after the periodic snapshot facility. Snapshots are kept for 1, 2 and 4 hours, 1, 2 and 4 days, 1, 2 and 4 weeks. On the first write to an existing file, a copy of its old content becomes the 1 hour snapshot. Consecutive writes during the next 59 minutes do not result in a copy-on-write. If, after 60 or minutes (but less than 120 minutes), another write occurs, the 1 hour snapshot is promoted to be the 2 hour snapshot, and the new 1 hour snapshot becomes the copy-on-write before the current change takes effect. And so on. (Notice that, in the absence of a second write, the first snapshot may remain in the 1 hour slot. This is intentional to simplify the problem.)
Specifically, snapshots should be created only for user directories (identified by a path name with a leading "/home/" string) and are put in directories
```
$home/.snapshot/hour.1
$home/.snapshot/hour.2
$home/.snapshot/hour.4
$home/.snapshot/day.1
etc.
```
No snapshots are generated for the .snapshot subdirectory. (Why?) Snapshots are put under the same relative paths into the proper directory, e.g.
```
$home/.snapshot/hour.1/Mail/inbox
```
is a snapshot of the file
```
$home/Mail/inbox
```
where $home may be /home/guest for a guest account.
The assignment contains two parts. The first part is a simulation environment, which helps to identify problems without having to deal with the Linux kernel. The second part integrates the first part into the Linux kernel.
- a) (10 points) Using your Solaris unity account, write a C program named "snapshot.c" that takes an absolute path name and an absolute file name and creates a copy of the file in the 1 hour snapshot directory. (Substitute g/guest with your home directory.) If subdirectories (including .snapshot) do not exist, create the subdirectories first. For example,
```
snapshot /afs/unity.ncsu.edu/users/g/guest /afs/unity.ncsu.edu/users/g/guest/Mail/inbox
```
  creates a copy in
```
/afs/unity.ncsu.edu/users/g/guest/.snapshot/Mail/inbox
```
  (Substitute g/guest with your account name.)
  Hints:
  - system calls and man pages for open, close, read write. (Do NOT use fopen, fclose, fread, fwrite!)
  - system calls / man pages for stat, mkdir
  - man string
- b) (50 points) Using the OS lab, integrate your solution as a copy-on-write functionality to the system call write for Linux. Notice that /afs/unity.ncsu.edu/users/g in part a) is equivalent to /home in part b).
  - Lab instructions:
    1. Select the machine assign to your group (see group assignment page).
    2. Log in under Windows 2000 using your unity user name. Your initial password is your student ID number (social), please change this password right away (Ctrl-Alt-Del Change-password).
    3. copy s:\csc501\linux.vhd c:\Documents and Settings\\My Documents
      (The file is also available for download.)
    4. Choose VirtualPC (from start menu or desktop).
    5. First time only: Select NewPC, Next, Linux (as a PC name), GuideMe, Linux, No, existing image, browse to select the c:linux.vhd file you copied above, check enable undo support, finish.
    6. Select the Linux guest in VirtualPC and start (it) up.
    7. In the boot loader grub, choose the custom.ext3 kernel. This is the kernel that you will modify. Notice that you can choose just the plain ext3 kernel in case the custom kernel does not work, which will happen from time to time after you make changes to the kernel and break it.
    8. Wait for Linux to boot up completely, i.e., wait for the KDE login (blue screen).
    9. To focus on the guest OS, you simply left-click your mouse in the VirtualPC window. The cursor and mouse pointer are then taken over by the guest. You can switch back to the host (Windows) with the RIGHT-ALT key. (Try it, then refocus on the guest.)
    10. Now, hit RIGHT-ALT-ENTER (hold ALT, press enter). This will put the guest in full-screen mode. To return to Windows, press RIGHT-ALT-ENTER again, to try it out. Then, go back to the full-screen guest mode.
    11. Log in as "root" password "nothing".
    12. Wait for KDE to come up, then start a console (terminal/shell symbol).
    13. Create a new user (with your login name): useradd user
    14. Become the new user: su user
      Set a password for the user: passwd
      This is where you could solve the assignment (in graphics mode). If you were to log out (left-bottom KDE menu, logout), you could choose to "shutdown" or "reboot" Linux. Linux,
    15. Alternatively, you may sometimes find it convenient to work in text mode. Press CTRL-ALT-F1 to get a login on tty1, login as root. (You can switch back to graphics mode with CTRL-ATR-F7 later.) You could now solve the assignment in text mode.
    16. You can reboot by switching to Windows (RIGHT-ALT-ENTER) and selecting Type Ctrl-Alt-Del from the PC menu of VirtualPC.
    17. You can Shut Down the guest on the VirtualPC menu and Save Changes. This is useful if your modifications to the Linux guest were successful and you want to save them. Alternatively, you can Turn Off the virtual PC and undo the changes. Hint: You may want to save a stable state of Linux every time that you are about to make drastic changes to the kernel. If you want to reboot after the changes and you broke the kernel, you can simply revert to the saved state (by choosing "turn off and undo"). If you forgot to do this and the custom kernel is broken, you can always select a different kernel in grub upon boot-up.
  - Compiling the Linux kernel:
    1. Log in as root.
    2. cd /usr/src/linux
    3. make bzImage (this takes a while and only recompiles changed files)
    4. cp arch/i386/boot/bzImage /boot/vmlinuz-2.4.9-13custom
    5. cp System.map /boot/System.map-2.4.9-13custom
    6. sync
    7. reboot as described above
    8. Choose the custom.ext3 kernel, and you are running your own kernel.
  - Hints for this assignment:
    - Find the implementation for the system call write. System calls are named sys_xxx in Linux. The kernel maintains a virtual file system (VFS) for high-level file operation, which is device independent. This is the level you should perform your work at.
    - Modify the the write syscall to print out a message with printk, the kernel equivalent of printf. (Notice that you cannot make calls to the C library or the OS while you are in the kernel. But similar functionality is provided under similar names, see the kernel API on the Linux documentation page.) Reboot and watch your printk's go into the system log file /var/log/messages.
    - The currently running task in Linux (process or thread, almost the same in Linux) is named "current", a global variable (see sched.h, struct task_struct in /usr/include/linux/). Restrict your printk's to user tasks with a uid >= 500 (user id as in /etc/passwd).
    - Extend the write system call with your snapshot functionality from part a).
    - Use kmalloc/kfree to allocate larger data structures (e.g., PAGE_SIZE).
    - You can obtain the pathname of a "struct file" with d_path (see sched.h).
    - You can obtain references to function pointers for file manipulation from the "file" structure, e.g., file->f_op->write is the kernel-internal write call specific to the file system of the open file (see fs.h, struct file, struct file_operations) -- except for filp_open and filp_close.
    - Take a look at the mkdir equivalent system call sys_mknod.
    - lookup_create() in namei.c may come in handy, make it global by removing the "static" declaration.
    - path_init (with a) LOOKUP_PARENT / b) LOOKUP_DIRECTORY / c) LOOKUP_POSITIVE | LOOKUP_FOLLOW), path_walk (and a matching path_release later), lookup_create and vfs_mkdir can be used to create directories (see dcache.c). Notice: A dcache entry obtained by lookup_create needs to be released again with dput(). Also, as a side-effect of lookup_create, a semaphore is obtained (down()), which needs to be released later through a corresponding up() call on the semaphore or the inode in the dcache entry.
    - To copy a file, it is best to open another file descriptor in read mode wrt. the file that the write syscall was invoked for. Then, you can copy the file contents (before the actual write syscall is performed) to the snapshot file.
    - before the copy operations, you need to save the old data segment with get_fs() and set the current segment to get_ds() to ensure proper address range checking (see /usr/include/asm/uaccess.h and binfmt_elf.c). Afterwards, you need to restore the original segment with set_fs().
    - You should create the snapshot with the access time (i_atime) and modification time (i_mtime) in the inode of the original file (see notify_change() in attr.c.
    - On a copy-on-write, age existing copies as required (hour.i, day.i etc.). This item has been dropped.
    - To test your modifications, remember to log in as root in one terminal and then as a user in another one. Perform only one simple write, preferably in a special test program, and check out the effect: kernel panic (bad), printk's in /var/log/messages, newly created directories and copied files. Remember: Every write results in a copy right now.
  - Helpful pointers:
  Turn in the following files: The modified files of the Linux kernel (with only minimal changes), copy_on_write.c, which should contain the bulk of the implementation, README2, possibly Makefile (if modified) and snapshot.c (from part a).