Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. The deadline for group programming problems applies to both CVN and non-CVN students. All homework submissions are to be made via the submit programs. Refer to the homework policy page on the class web site for further details.

Individual Written Problems:

Exercise numbers refer to the course textbook, Applied Operating System Concepts. Each problem is worth 5 points.

1. Exercise 3.1

2. Exercise 3.7

3. On all current computers, at least part of the interrupt handlers are written in assembly language. Why?

4. Describe what happens in the Linux kernel when a timer interrupt occurs. Be sure to list the procedures that are called and explain the function of each.

5. Describe what happens in the Linux kernel when a fork system call occurs. Be sure to list the procedures that are called and explain the function of each.

6. Read the Linux source code and construct a state diagram to represent the relevant states that a process may be in at any given time. For each state, give the exact name used for the state in the source code.

7. Exercise 4.1

8. Exercise 4.4

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.

Group Programming Problems:

Programming problems are to be done in your assigned groups using the VM that has been assigned to your group. 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. For each homework assignment, you will build a new Linux kernel. The image of the kernel you build for this assignment should be vmlinuz.hmwk2. Grading for this assignment will be done based on vmlinuz.hmwk2. Note that the version of Linux running as the Host OS on the CLIC machines is different from that of the Guest OS that you will modify running in VMware.

1. (5 pts.) Compile and install your own Linux kernel on your VM. The Linux Kernel HOWTO describes how to do this in some detail. Note that there are several issues that we must address:
   • Though kernel sources have already been installed in your VM, you will use your own sources for the linux kernel and should download them from ftp://ftp.kernel.org/pub/linux/kernel/v2.4/linux-2.4.2.tar.gz.
     Make sure you download the new sources as the Linux kernel currently installed in your VM is version 2.4.2-2 and will not work for this assignment. You should put your kernel sources into the /usr/src directory and unpack them, which will automatically create a directory /usr/src/linux. Once the code is on your guest VM, the steps you should follow are:
     1. cd /usr/src
     2. mv /[your download directory]/linux-2.4.2.tar.gz .
     3. tar -xzvf linux-2.4.2.tar.gz
   • To compile the kernel so that it recognizes your hardware, you need to set up a config file. Setting it up is a long process prone to error. We have saved you this trouble and generated a sample config file that you may use within the vmware environment. This config file is confirmed to work with your recently downloaded kernel version, as well as with the patched one you will be building for part 2 of this assignment. In order to use this config file, simply copy it to /usr/src/linux/.config and type make oldconfig. Hopefully some configuration announcements will run by the screen, without prompting you for any information. This will replace the steps involved in manually configuring your kernel.
   • Be sure to enter the appropriate information into your /etc/lilo.conf file. The Kernel HOWTO explains how to do this.
   • Your documentation states that you should always run lilo after recompiling your kernel. Heed this warning. A number of you will complain of an unbootable kernel - in many cases this can be identified as a failure to rerun lilo.

2. (8 pts) Install the KDB kernel debugger from ftp://oss.sgi.com/projects/kdb/download/ix86/old/kdb-v1.8-2.4.2.gz. Note again that you will have to ftp this code from your host computer to your guest VM. Move the patch into /usr/src/linux and apply it with the following commands:
   1. cd /usr/src/linux
   2. gunzip kdb-v1.8-2.4.2.gz
   3. patch -p1 < kdb-v1.8-2.4.2 > /tmp/patchres
   Then look at the file /tmp/patchres. There should be one small error in there. Ignore this. If you have several errors (and are sure you're using the correct kernel and patch versions) let the TA staff know immediately. Otherwise, recompile the kernel with the patch.

   After you have patched the kernel, the Documentation/ subdirectory will contain man pages on kdb. Read them to familiarize yourself with its operation. You can also read a summary of kernel debugging techniques (which include kdb) at: http://www.xml.com/ldd/chapter/book/ch04.html. At any time you may press the pause button to enter the debugger and, once in the the debugger, type go to exit to the ordinary command prompt. Though we won't require you to use the debugger for this assignment, we will be testing to make sure it is installed!

3. (30 pts.) The Linux kernel maintains state for each process as it executes. A process is identified by a process id number called a PID. Write a new system call in Linux that takes a PID as an argument, and returns the process state information for that process. Note that you will be adding this system call to the kernel based on the 2.4.2 kernel you previously built with kernel debugging installed.

   The prototype for your system call will be:

   	int pinfo(pid_t pid, struct pinfo *info);
   

   pid_t is defined in /usr/include/sys/types.h. You should define struct pinfo as

   struct pinfo {
   	int pid;			/* process id */
   	long state;			/* current state of process */
   	long priority;			/* process priority */
   	int parent_pid;			/* process id of parent */
   	int youngest_child_pid;		/* pid of youngest child */
   	int younger_sibling_pid;	/* pid of younger sibling */
   	int older_sibling_pid;		/* pid of older sibling */
   	unsigned long start_time; 	/* process start time */
   	long user_time;			/* CPU time spent in user mode */
   	long sys_time;			/* CPU time spent in system mode */
   	long cutime;			/* total user time of children */
   	long cstime;			/* total system time of children */
   	long uid;			/* user id of process owner */
   	char comm[16];			/* name of program executed */
   };
   

   in /usr/src/linux/include/linux/pinfo.h as part of your solution.

   Your system call should return 0 if it is able to locate the process information for the target pid. At a minimum, your system call should detect the following conditions and respond as described:

   • If the process with the given PID does not exist, return -3.
   • If the given PID is less than 1 or the address for the pinfo structure is null, return -22.
   • If a value to be set in pinfo is accessible through a pointer which is null, set the value in pinfo to -1. For example, the youngest_child_pid should be set to -1 if the process does not have a child.

   The referenced error codes are defined as ESRCH and EINVAL, respectively, in /usr/src/linux/asm/errno.h

   You should start by reviewing the "How System Calls Work in Linux/i86" section of the Linux Kernel Hacker's (LKH) Guide. Note that because the Linux kernel changes over time, the procedure is no longer exactly correct. However, there are messages appended at the end of the section that will help significantly. Two more recent articles that discuss how to add system calls can be found here and here.

   You will also want to review Chapter 3 on "Processes" in the class linux reference book, Understanding the Linux Kernel.

   As explained in the LKH guide, each system call must be assigned a number. Your system call should be assigned number 222.

   Big Hint: Linux maintains a list of all processes in a doubly linked list. Each entry in this list is a task_struct structure, which is defined in /usr/src/linux/include/linux/sched.h. In /usr/src/linux/include/asm/current.h, current is defined to inline a function which returns the address of the task_struct of the currently running process. All of the information to be returned in the pinfo structure can be determined by starting with current.

   Bigger Hint: In order to learn about system calls, you may also find it helpful to search the Linux kernel for other system calls and see how they are defined. The file kernel/sched.c might give some useful examples of this. The getpid and getuid system calls might be useful starting points. The system call sys_getpid defined in /usr/src/linux/kernel/sched.c uses current and provides a good reference point for defining your system call.

   FINAL NOTE: Your kernel has partially reserved a slot in the syscall table for ni_syscall (when you see it, you will know what we are talking about). Since ni_syscall means "not implemented", do not be afraid to commandeer that slot.

4. (17 pts.) To test your system call, write a C program that takes a PID as an argument and finds all the ancestors of that process. Your program should print the process state information for the specified process and for each of the ancestors of the specified PID. The information for the process and its ancestors should be printed in generational order, starting with the oldest ancestor.

   NOTE: Although system calls are generally accessed through a library (libc), your test program should access your system call directly. This is accomplished by utilizing the appropriate _syscall macro in /usr/include/asm/unistd.h. As explained in LKH, which _syscall macro you use is determined by the number of arguments passed to your system call.

   The output of the program should be easy to read, and the program should check for errors such as invalid input or too many/few arguments, and invalid PID. The ps command will provide valuable help in verifying the accuracy of information printed by your program. You can access detailed information on the ps command by entering man ps.

   Your writeup should include the program output from the following two testcases:

   • Find all ancestors of your login shell
   • Find all ancestors of the kupdate process

   Additional Information:

   • As a safety measure, you are strongly encouraged to copy the source files you plan to modify to your home directory on the host system, make your modifications and then FTP your version of the source file to the guest system for the build. Obviously, you still do your builds on the guest system, this procedure is just to ensure your work is not lost in the event of a failure.

   • 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 system administration or consult some of the guides at The Linux Documentation Project.
   • To extend upon the sys-admin issue, some people are often confused by the virtual network connection between the host and guest vms. Usually for all ftping, sshing and telneting, you must specifically identify the target machine's ip. Usually the host sees the vm as 172.16.156.128 and the vm sees the host ([cityname].clic.cs) as 172.16.156.1. If these numbers do not work, type /sbin/ifconfig to see what numbers have been assigned (they should be pretty close to these). In cases where more than one vm is running simultaneously, different network numbers might be establishes.
   • To add to the previous point, your group should not, under any circumstances, be running two or more vms simultaneously. This often happens through the use of vnc. View the vm itself as a critical section and use some method (e.g. emailing your fellow group members) to enforce mutual exclusion.