W4118 OPERATING SYSTEMS I

Homework 5 is due 04/15 at 12:01am EDT

The test program is due 04/08 at 12:01am EDT

Chia-che will be holding a TA session on this homework at CSB 477 (the open area) from 2-4 on Monday, April 5.

Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. All homework submissions and discussions are to be made via Courseworks.

Individual Written Assignment (40 pts)

Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 4 points. Make your answers concise. You'll lose points for verbosity.

1. MOS 3.7
2. MOS 3.9
3. MOS 3.10
4. MOS 3.11
5. MOS 3.15
6. MOS 3.21
7. MOS 3.28
8. MOS 3.29
9. MOS 3.35
10. Describe how the Linux kernel implements copy-on-write for fork(). Be sure to list the relevant procedures, data structures, and variables; explain the meaning of each.

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: Adding a Per-Thread Page Access Tracing Mechanism to Linux (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.hmwk5. Grading for this assignment will be done based on vmlinuz.hmwk5. 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.

Description

In previous homework, you have built a Race-Averse Scheduler that can make intelligent scheduling decisions to avoid possible races in multithreaded applications. This sounds all nice, except that users of your scheduler have to specify race probabilities manually, which is lame. Wouldn't it be nicer if you can develop a mechanism to infer race probabilities automatically?

In this assignment, you'll augment the Linux kernel to support per-thread page access tracing, which can trace approximately how often a page is accessed by a particular thread. Once we know the page access frequency for all threads, computing race probabilities is easy. For example, if two threads access disjoint set of pages all the time, the race probability between the two threads should be 0.

How do we trace page accesses? Although the hardware uses a R bit and a M bit to track if a page has been referenced or modified, it does not maintain access frequency for each thread. Thus, we'll have to track the access frequency by ourselves in software. We'll do so using the page protection mechanism, similar to how COW is implemented for fork(). We'll use a per-thread access counter array that keeps track of approximately how many times a thread has accessed a particular page. To trace page P for thread T, we first modify T's page table to protect page P so that the next access to P by T will cause a page fault. Then, in the page fault handler, we increment thread T's access counter for page P, change the page protection bits back to normal, and let T continue with the access.

The above method can detect only a single access to a page. Once the page protection bits are set back to normal, we'll no longer be able to detect future accesses. To solve this problem, we'll re-protect traced pages periodically.

To simplify the assignment, you only have to track page writes and maintain a per-thread write counter for each page; you don't have to worry about page reads. In addition, to help you get started, we provide you skeleton code in the form of a patch. Please download it and apply it to your kernel tree.

You are strongly advised to read Understanding Linux Kernel Chapter 8 Memory Management, Chapter 15 The Page Cache, Chapter 17 Page Frame Reclaiming before starting the programming assignment. Linux uses page cache to denote the memory region for storing pages. The directory mm/ contains majority of code that deals with paging and virtual memory. You will find the struct mm_struct, struct vm_area_struct data structure in linux/mm.h and pgd_t, pmd_t, pud_t, pte_t in asm/pgtable.h helpful.

1. (50 pts.) Implement a per-thread page access tracing mechanism in Linux Kernel

   Add three new system calls, sys_start_trace, sys_stop_trace, and set_get_trace, with syscall number 293, 294, and 295 respectively. These syscalls should have the following prototypes:

   asmlinkage long sys_start_trace(unsigned long start, size_t size);

   asmlinkage long sys_stop_trace();

   asmlinkage long sys_get_trace(pid_t tid, int *wcounts);

   sys_start_trace should tell the kernel to start tracing page writes to virtual address range [start, start+size) for all threads in current process. sys_stop_trace should tell the kernel to stop tracing page writes. Each process can have only one active tracing session at a time. If sys_start_trace is called twice without sys_stop_trace being called in between, the second call to sys_start_trace should return -EINVAL.

   sys_gettrace should return the write counters for all traced pages for thread tid. The write counters should be returned in wcounts, which is an array of integers. The caller of this syscall should make sure that wcounts is large enough to hold the write counters of all traced pages.

   Your implementation of the three syscalls should handle error cases appropriately and return corresponding error codes.

2. (10 pts.) Write user-space program to test the page tracing mechanism you implement.

   Your user-space program should contain testcases that create a number of threads, each making a number of memory references. You should use your tracing mechanism to trace these references and make sure that the trace results are correct.

Hints on the assignment:

• You will find macros defined in asm/pgtable.h useful, especially those dealing with flag bits in table entries, for example, pte_wrprotect, pte_write, and pte_offset_map.

• You'll need to distinguish what pages are traced and what are not in page tables. You can do so by setting or clearing a bit in a page table entry. There are three unused bits in a page table entry, and you should pick one of these unused bits as the tracing bit.

• To learn how to set up protection for a virtual address range, check out syscall sys_mprotect.

• Your implementation must re-protect pages periodically. We've created an empty function page_protect_tick in the skeleton patch. You should write code to call this function every 10 2 timer interrupts. You should also write code within this function to re-protect pages.

• When a new page mapping is created, you'll need to check if the mapping falls within an active tracing range and set up the page entries accordingly. We've created an empty function do_pte_trace and inserted calls to this function where new page mappings are added. You should fill in the appropriate code for this function.

• You must be very careful to avoid interfering with COW, because a COW page is also write protected.

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.