Spring 2009 -- Junfeng Yang

Homework 6 is due 05/05 at 11:59pm 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, Operating System Concepts. Each problem is worth 5 points.

  1. Ch 10 Exercise 10

  2. Ch 10 Exercise 14

  3. Ch 11 Exercise 11

  4. Ch 11 Exercise 14

  5. Ch 11 Exercise 15

  6. Ch 11 Exercise 16

  7. Ch 12 Exercise 24

  8. Ch 12 Exercise 27

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: EXT2 File System with Tags (60 pts)

Programming problems are to be done in your assigned groups using copies of the virtual machine (VM) image already provided. For all programming problems you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. In addition, you should submit a cover sheet using either homework_work.txt or homework_nonwork.txt, depending on whether or not the programming assignment is completely working or not. For source code submissions, you only need to submit new source code files that you created and kernel source code files that you changed. You should clearly indicate your names, email addresses, and assigned group number on your submission. Each group is required to submit one writeup for the programming assignment.

You will build your own Linux kernel for this class. The image of the kernel you build for this assignment should be vmlinuz.hmwk6. Grading for this assignment will be done based on vmlinuz.hmwk6. You will base your changes on the 2.6.11 kernel that you installed for Homework 2, but without the modifications you made for the new systems calls you wrote for Homework 2. In particular, submitted kernel patches should be patched against your modified KDB-enabled kernel from Homework 2, i.e. do not include KDB code in your patch.


In this assignment, you will add a new feature to the Linux Second Extended Filesystem (EXT2) to allow users to tag files with arbitrary keywords 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 EXT2 that applies to all file types.

The tagging mechanism you add should allow users to attach arbitrary keywords to arbitrary files in an EXT2 file system. You should not constraint the file types: users can tag normal files, executable, symbolic links, or even directories. These tags should be stored persistently on disk, together with the corresponding file. They can also be retrieved or removed by users.

You are strongly advised to read Understanding Linux Kernel Chapter 12 Virtual Filesystem, Chapter 18 The Ext2 and EXt3 Filesystems before starting the programming assignment. Besides, you may find more information about Ext2 in http://www.nongnu.org/ext2-doc/.

  1. (5 pts.) Create a new virtual disk and mount the EXT2 filesystem.

    1) Create a new virtual disk: in your vmware software, select "Add Hardware" to add a new virtual SCSI disk. You should be able to see this new disk in the "Hardware" column if the operation succeed. This disk should be recognized as /dev/sdb in the system.

    2) Create a partition for the new disk: run the command "fdisk /dev/sdb". In the following menu, select n to create a new partition, then p for the primary partition, and 1 as the partition number. Specify the first and the last blocks as the starting and the end blocks respectively for the partition, so that it occupies the whole disk. At last select w to write the partition table and exit fdisk.

    3) Format the new partition: run the command "mkfs -t ext2 /dev/sdb1". It creates a new ext2 filesystem on the new partition /dev/sdb1 that we just created. By default this command should create a file system with block size 4096.

    4) Mount the new partition: create a mounting point by making a new directory, then run "mount -t ext2 /dev/sdb1 /[mounting point]" to mount the partition. Use "df -T" to show the details of all mounted file systems.

  2. (50 pts.) Design and implement the tag mechanism for EXT2

    Add three new system calls. Their system call numbers should be 289, 290, and 291 respectively.

    int addtag(char *path, char *word, size_t len);

    int rmtag(char *path, char *word, size_t len);

    size_t gettags(char *path, char *buffer, size_t size);

    addtag() will attach the tag word with length len to the file specified in path; rmtag() will delete the tag word with length len from the list of tags for file path; gettags() will get all the tags attached to the file, copy them to the buffer and return the bytes copied (the argument "size" specifies the size of buffer, if the size is not big enough to hold all the keywords or the size is 0, gettags() should do nothing but simply return the bytes needed).

    Since Linux uses a layered structure to implement file systems, you'll need to modify both the Virtual File System (VFS) layer and EXT2 in order to add the above system calls. You may want to start by understanding an existing file system call (e.g., mkdir)

    You should understand the data structures corresponding to different file system layers. There are three kinds of relevant data structures: (1) the data structures for the VFS layer, (2) EXT2 in-memory data structures, and (3) EXT2 on-disk data structures. Take inode for an example. The VFS inode is struct inode, which is in memory. It has a pointer to EXT2-specific in-memory inode information struct ext2_inode_info. When writing an in-memory EXT2 inode to disk, we must convert it into on-disk EXT2 inode struct ext2_inode.

    To give you more time to study for your final exams, we simplified things for you as follows. A file can have up to 16 tags. All tags and their lengths of a file can be stored in a single 4KB disk block.

    The tags user add should be persistent. That is, you must store them to disk so that after rebooting, users can still get them back. Thus, to make tags persistent, you'll need to figure out how to allocate disk blocks, read them into buffer cache, modify them and write them back to disk. EXT2 and the kernel have provided us a list of functions to allocate and write disk blocks already. You should understand the following functions: ext2_new_block(allocate a new disk block), ext2_free_blocks(free a disk block), sb_bread and sb_getblk(get the buffer head of the disk block for reading), mark_buffer_dirty and sync_dirty_buffer(submit a block for disk write, also see submit_bh() and wait_on_buffer()). You can find plenty of examples in kernel for using these functions for disk I/O. In particular, the extended attribute implementation provides a good example.

    In order to locate the tag block of a file, you should store its location in this file's inode. You will use the field i_reserved1 in struct ext2_inode for this purpose. It is actually a macro defined as osd1.linux1.l_i_reserved1.

    Note normally when you change the on-disk representation of a file system, you must change all utility programs of this file system that depend on this representation. These programs include at least mkfs (create a new file system) and fsck (repair a file system). For this assignment, however, we do not require you to change any utility programs. We can get away without changing mkfs because mkfs sets field i_reserved1 to 0. However, fsck does create a problem: it will set i_reserved1 to 0 and reclaim the tag block of a file as a free block. When you see this occurs, don't panic; just ignore the error messages fsck emits.

    Your solution should have the appropriate synchronization mechanisms. It should also correctly handle normal file system operations (like creating/deleting files, umount/mount filesystem).

    You should properly handle errors that may occur and report meaningful error codes. As always, you are encouraged to look for existing kernel code that performs similar tasks and follow the conventions and practices it provides.

  3. (5 pts.) Write a test program for the tag mechanism

    Your test program should try to tag some files and then read back the tags.

Additional Information

  • Backup your kernel changes outside your VM often. Sometimes your virtual disk can get corrupted, and you may lose all changes you've made.
  • Remember, as a safety measure, you are strongly encouraged to backup your VMware image from time to time.
  • printk statements in system calls will print their output to the console whenever they are invoked. To request printk messages be sent to a log file, insert the following line into the /etc/syslog.conf file:
    kern.* /var/kern.log
    This will cause printk messages to be written to /var/kern.log. You can send a signal to request the syslog daemon re-read the updated /etc/syslog.conf file, with the command "kill -1 pid" where pid is the pid of the syslogd process.
  • A lot of your problems will come from system administration issues. If nobody in your group in familiar with unix, you might want to pick up a book on Unix/Linux system administration.
  • You can find some Linux programming tips at the course resources page.