Project 1
This project will be completed in teams of 2. Both team members will receive the same grade subject to participation. You are expected to work together, in person, at the same computer. You may choose your own team member. You and your team member must arrange to join the same Project2_Groups on Blackboard prior to submitting. Send the instructor an e-mail if you have trouble and need a manual adjustment of your group.
You will need a Linux development environment for this assignment, in particular you need to be able to boot and run the Linux kernel version 3.16.0. I recommend that you install Virtualbox and download the virtual machine (VM) available from the text book's companion site https://os-book.com/ -- You have to select the "Operating Systems Concepts" book and find the link to the Linux Virtual Machine. While you're on the site I highly recommend you browse around. The VM is a big file (almost 3 GB) so you will want to start the download immediately.
The LKD book and supplemental LDD book (available as PDF) will be helpful.
If you do use the VM from the text book web site, you need to do a little bit of system administration to add some additional hard drive space, because the hard disk it comes with is not large enough to recompile Linux. Without starting the VM, but after you download it and import it into Virtualbox, open Virtualbox, right-click on the OSC-2016 machine, and select "Settings". Go to the Storage menu, right-click on the SATA controller, and add another Hard Disk. You can select the VMDK format, and probably should use at least a 16 GiB drive. You should see "NewVirtualDisk1.vmdk" under the Controller: SATA item. Now boot the VM. The new disk should be available as /dev/sdb, but it needs to be partitioned and formatted to be usable. Run sudo gdisk and type device filename /dev/sdb to select the new disk. Type p to see the current disk information, it should show you on the first line the name "Disk /dev/sdb: ... 16.0 GiB", and further down that the "Total free space ... sectors". If not, you have the wrong disk and need to seek help elsewhere. Now you will create a partition by entering command n. Then just hit enter a few times to accept the defaults, and when you get the "Command" prompt again, type p and you should see a partition now. Write out the partition with the w command. Now you have a partition, and you need to create a filesystem on it. We will
use the ext3 file system, so just run sudo mkfs.ext3 /dev/sdb1
Note sdb1 this time, because we're making the file system on partition 1 that we just created. Congratulations, you made a file system!
Now create a mount point for it, and mount it. Let's use sudo mkdir /linux and then sudo mount /dev/sdb1
/linux followed by sudo chown -R oscreader /linux and finally cd
/linux. Eventually you will want to add this mount point to the /etc/fstab file, so open it and add the line:
/dev/sdb1 /linux ext3
Download the kernel source for 3.16.0 from https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.16.tar.gz and move it into /linux, then uncompress and untar it to get /linux/linux-3.16 directory.
Enter the linux-3.16 directory, open the Makefile in a text editor, and modify EXTRAVERSION= by adding a . and an extra version number or string, "EXTRAVERSION=.project2".
Configure the kernel:
cp /boot/config-* .config make oldconfig
You may need to answer a few questions, but the default should be OK so just hit "Enter" through all of the prompts. Now compile the kernel:
make -j2
Coffee Break.
Install the kernel and modules:
mkdir /linux/mykernels
make INSTALL_PATH=/linux/mykernels install
make INSTALL_MOD_PATH=/linux/mykernels modules_install
cd /linux/mykernels
sudo cp vmlinuz-3.16.0.project2 /boot/ sudo cp System.map-3.16.0.project2 /boot/
sudo cp -r ~/mykernels/lib/modules/3.16.0.project2 /lib/modules sudo mkinitramfs -o /boot/initrd-3.16.0.project2.img 3.16.0.project2 sudo update-grub
Reboot the machine and enter the advanced options in the grub menu and then select the newly compiled kernel to boot it.
You can check the running kernel by executing the command uname -a in the shell. You're ready to start hacking (this version of) Linux!
Part 1: Informative kernel modules
(a) The pid_info module.
You will write a simple kernel module called pid_info. The module should cleanly load and unload an unlimited number of times. The module should take a parameter of the pid of a specific process. When loaded, the module will lookup the process task_struct of the specified process and print out, using the printk() function, the following information nicely formatted.
- pid
- uid, gid of process
- parent process id and name
- all of the children processes pid and name
- any flags that are set. Make sure to translate them to readable names.
You can find the struct task_struct defined in the file linux/sched.h The LKD chapters on processes, modules and appendix A on linked lists can be helpful. There is also an example of a module and Makefile already available on the virtual machine, located at ${HOME}/osc9e-src/ch2/.
The c source file with your module should have two global variables (pid parameter and module name) and only two functions (the module init and cleanup). Use the MODULE_ macros (linux/module.h) to document the license (GPL), author, and description of your module. Your makefile should have a default target to build your modules and a clean target to remove all compiled files. Your modules should have the exact name given in the assignment.
(b) The pid_vminfo module.
Now you will write a module called pid_vminfo that creates a /proc entry file that when read, prints out the virtual memory state of a process. The virtual memory state of the process can be found by looking at the mm field of the task struct you used in the first module. You should print out at least enough information to identify the process (pid, name, ...) and all of the vm_area structs that are listed in the mmap list. Additional information that is displayed in a useful format will be a bonus.
The module should print out the state of whatever process is running when its proc file is read. So it does not need to lookup a pid like the first module. Creating and destroying /proc entries is easy; you can do it with a single function call.
Documentation on how can be found on page 11-14 of Chapter 4 Debugging of the Linux Device Drivers 3rd Edition available online.
Part 2: Implementing System Calls
You will create three new system calls and test them. You will need to implement the system call in an existing kernel source file, add the system call to the appropriate
headers, and write or use a userspace test program to verify your system calls work correctly. Your system calls will set and retrieve the value of several variables stored in kernel space. The first variable is a variable length string, call it my_string. The second variable is an integer, call it my_accumulator.
Implementing system calls requires that you add the code for the actual call (prefixed with sys_) to an existing kernel source file, add the system call to the system call table, and add the header for the call to syscalls.h.
Make sure that your system calls have exactly the same signatures as below. Otherwise our test programs will fail to call your system calls and they will appear to fail. Function and variable names are case sensitive. All system calls should return an error code of EINVAL for inputs that are invalid. All error return values should be real Linux kernel error values (such as those found in include/linux/errno.h) that most closely match the error you are reporting. We specify a few specific errors that must be used, such as EINVAL and EOVERFLOW.
System call 1: sys_my_set_state
long my_set_state(char *the_string, int accumulator) This call sets the value of an integer and one string. The accumulator integer passed as input must always be non-negative. The string can be arbitrarily long, but is always null terminated, so you must dynamically allocate memory to store it when set. If a string is already stored in the kernel string variable, the memory allocated to it must be correctly freed. Strings stored in the kernel variable must be null terminated. The return value should be 0 for success, or a negative error value.
System call 2: sys my_get_and_sum
long my_get_and_sum(int *my_value, int inc_value)
Take the value stored in the kernel variable my_accumulator and add the value passed in the inc_value parameter, which is always non-negative. Return the result in the my_value return value. The my_accumulator should store the updated value. If the resulting value is greater than MAX INT, then EOVERFLOW error should be returned. The return value should be 0 for success, or a negative error value.
System call 3: sys_my_get_string
long my_get_string(char *buf, int bsize)
Take the kernel string variable stored in the kernel and copy it into the user provided buffer buf of size bsize. If the kernel string variable is empty, an error of ENODATA should be returned. The returned string will always be NUL terminated and therefore the following rule should be followed for selecting the string length to return:
If slen is the length of the current string stored in the kernel variable, copy the leftmost copylen = min( slen, bsize -1) characters and append a NUL terminator to the end.
The system call should return the length of the string copied if successful, or a negative error value.
Because you will be modifying existing kernel source files, you will use the kernel build commands from Part 0 to re-compile your modified kernel.
Kernel Patches
It is very useful to be able to create kernel "patches" which show only the specific changes made and not all of the unchanged code. Since many modifications to the kernel are small (compared to the total kernel source size), such a patch can be many orders of magnitude smaller then the whole kernel. When you submit your changes to the kernel for assignments, you will submit a patch that we will apply to our copy of the kernel. So if you generate a bad patch, we may not get a working kernel even if you had it working yourself. So test applying your own patch before sending it. For this part of the assignment you need to generate a patch with only your changes to the kernel.
Testing
You should write your own small (less than 50 line) programs that will let you test additional system call cases, such as calling your system calls in different sequences.
You should also write test programs for using your kernel modules.
Documentation
Comment your code with /* */ style comments. Explain each function's purpose and the use of parameters. Include your name and a brief description at the top of each source file. If something doesn't work, you may get partial credit if your comments show that you were on the right track.
Write a README file that explains how to build and run your program, gives a brief description of your solutions, and contains any notes from discussions with others.
Document any places where you received help from others.
Project 3
You will need a Linux development environment for this assignment, in particular you need to be able to boot and run the Linux kernel version 3.16.0. See the instructions from Project 2 for more information.
The LKD book and supplemental LDD book (available as PDF) will be helpful.
Printing a Red-Black Tree using seq_file
Write a module called tree_traversal that creates a /proc entry file that, when read, displays your module's red-black tree. Much of the implementation has been completed, but some key aspects are missing. Comments labeled with TODO mark locations in the file where code needs to be added; the TODO statements provide additional instruction on what needs to be done.
The code that exists will create and initialize the red-black tree, and will also create and destroy the /proc entry. The functionality to display the tree in the proc file is missing. You can add any code, functions, or data structures that you think are necessary to complete the assignment.
You should first locate all of the TODO statements, so that you know what must be done. Then, look at the example seq_file implementation: https://lwn.net/Articles/22355/ and a description of how the red-black tree works: https://lwn.net/Articles/184495/ -- similar information can also be found in the Documentation/ directory inside of Linux.
Finally, you will be responsible for adding locking - the tree is exported to an in-memory file, which can be read at any time; however, the module could change the data stored in the tree at any time, so consistency must be ensured. How you choose to lock the critical data is left for you to decide.
To test your implementation, you should be able to read the file in /proc using, for example, the less command. Any number of elements in the tree should work. If an error occurs, your module should print a useful message in the log file. To further test your program, use other commands that read from files such as head and tail. Your module will be tested by a combination of such commands, and other methods.
Requirements
1. Use make. Your makefile should have a default target to build your modules and a clean target to remove all compiled files. Your modules should have the exact name given in the assignment.
2. COMMENT YOUR CODE. If something doesn't work, you may get partial credit if your comments show that you were on the right track. Remember to put a comment block at the top of every file. Document any places where you received help from anyone else.
3. Remember to use the MODULE_ macros to document your module.
4. Check return values on any function that can possibly fail. Add return values to any function that can fail.
5. Your source code must use UNIX style EOL characters \n not DOS style \n\r. You can write code on Windows, but you must convert it to Unix text files before submitting. The dos2unix command may be useful for this.
6. You must submit a README file (no extension necessary) that explains how to build
and run your program, gives a brief description of the pieces of your assignment, and contains any notes from discussions with your peer group partner.
7. Start with filling in bits and pieces of the missing implementation. Incremental development is key! Add locking after you have correctly implemented a solution.
8. When implementing locking, identify the critical data, find where the data is used, and then lock that critical section. You will have to add the lock primitives that you choose to use.
9. Be sure to address all of the TODO statements. BUT do not be afraid to add code that is not explicitly requested.