Course OS - Laboratory Session on Linux Kernel

Course on Operating Systems - Project of Fall 2007

Starting on November, 19^th, 2007

Ludovic Apvrille

Information on the project

Individual project. Similar approaches or source code are not allowed. You may use source code and information provided on the Internet (or else), but if you do so, do mention it in your report.
Graded (35% of you final grade)
Due for the 20th of January, midnight.
You must send me by the 20th of January a report (in pdf). This report should explain me your work: your overall approach, your implementation work, and answers to various questions provided below. Do mention difficulties you have encountered, and how you have solved them. I do not expect a long report (maximum of 5 pages), I just expect relevant information to be provided. Provide all references you have used to perform your project (websites, books, etc.).
Your backup directory located on /archives/kernel_project/<mylogin>/ should contain the 20th of January the last version of your work. This directory will be closed on that date, and your grade will be provided according to it (and according to your report).

If you have problems to make this project, you may come to my office to get help and advices. Also, do not start working on your project the 19th of January ;-) You should have completed a subsequent part - if not all parts - of the project before the end-of-year's vacations.

Information about the computer system

The project should be realized using a "vmwared" Linux. The starting vmware machine is the one provided in /home/Admin_Data/Tp_Apvrille/TP_Kernel.tar. Information on the use of this machine is provided in lab session on Linux kernel. This lab session also contains information on the system (edition, compilation, and various functions that may be useful).

We provide a backuped disk space for your project. Thus, the first time you use your machine, do:

Copy the virtual machines information into a work directory:
$ cd /home/Local_Data
$ cp /home/Admin_Data/TP_Kernel.apvrille.tar .

Extract all data necessary to start your linux running inside the virtual machine
$ tar -xof TP_Kernel.tar

Then, you may start the virtual machine. When you have finished working on it, do as follows:

Stop the system, in the virtual machine

$halt

Wait for the Linux to be halted, and then, close vmware. Come back to the main Linux, and do:

$ cd /home/Local_Data
$ tar -cvf <mylogin_vm>.tar TP_Kernel/

And save it in you project directory:
$cp <mylogin_vm>.tar /archives/kernel_project/<mylogin>/

Next time you want to access it, do:
$ cd /home/Local_Data
$cp /archives/kernel_project/<mylogin>/<mylogin_vm>.tar .

You may need to use Linux manual pages, section 9 (kernel). I recommend using:

Work to do

Basically, your work is to program a system call that is a bit more complex than the one made during the lab session.

At first, you have to finish the lab session on kernel programming i.e. your final virtual machine should contain the implementation of exercises 1 to 3. You don't have to provide information on theses system calls in your report.

In this project, the objective is to design a system call that can handle a specific message queue (To simplify the work, only one message queue is handled). This message queue has two specific parameters: a delay, and a loss rate. This delay represents the duration between the time at which a message is written and the time at which it could be read by another process, or the same. The loss rate is given as a percentage of lost messages. Each time a message is written, it has loss rate % of being immediately deleted i.e. it will never be read.

This kind of message queue is particularly useful for simulating communication networks.

1) At first, implement a basic message queue called mmq (for my message queue), i.e. at first, your message queue does not handle any delay nor loss rate.

The interface of the mmq is as follows:

int mmq(int config, int*data)

mmq returns a status: -1 in case of error, and the size of the message queue otherwise
config: if set to 0, this is a write operation. If set to 1, this is a read operation.
data. If this is a write operation, this points to an int value that need to be added to the queue. If this is a read operation, it points to a place where you wish the read data to be put.

This system call is assumed to be never blocking i.e. if a read operation is performed and if the queue contains no data, 0 is returned and the data at specified address is not set.

Program this system call, recompile the kernel and test it.

A test program should look like this:

…

int x;
int y;
int res;

x = 3;
y = 5;

res = mmq(0, &x);
printf("res = %d x=%d y=%d\n", res, x, y);
res = mmq(1,&y);
printf("res = %d x=%d y=%d\n", res, x, y);

You may also try to run a program that adds n samples to the queue, and another one that reads those n samples, or other more complex examples.

2) We now wish to add delay and loss rate information. Modify mmq as follows:

config parameter = 3: configuration of the delay (in ms). The delay is stored in the data parameter.
config=4: configuration of the loss rate (in percentage). This percentage is stored in the data parameter.

For example, the following test program configures the message queue:

…

int x;
int y;
int res;

x = 3;
y = 5;

res = mmq(3, 50); // delay of 50ms
printf("res = %d x=%d y=%d\n", res, x, y);

res = mmq(4, 10); // loss rate of 10%
printf("res = %d x=%d y=%d\n", res, x, y);

res = mmq(0, &x);
printf("res = %d x=%d y=%d\n", res, x, y);

res = mmq(3, 10); // delay of 10ms
printf("res = %d x=%d y=%d\n", res, x, y);

x = 6;
res = mmq(0, &x);
printf("res = %d x=%d y=%d\n", res, x, y);

// Warning: value 6 may be received before value 3 since message 6 has a delay of only 10ms.
res = mmq(1,&y);
printf("res = %d x=%d y=%d\n", res, x, y);

res = mmq(1,&y);
printf("res = %d x=%d y=%d\n", res, x, y);

Do implement this new system call, and make heavy tests to be sure it works correctly. More particularly, you have to make sure that you do not waste memory (i.e. allocate too much memory: do check out the manual page of kmalloc), and that you don't have memory leakage i.e. that you don't forget to disallocate the allocated memory that is no more usefull.

3) Is your system call re-entrant i.e. can it be executed at the same time by several processes? Do justify your answer.

4) Now assume that the message queue contains strings and not int values. What does it change to your program? I do not ask you to modify your code, but rather to explain me what would be the major and minor modifications to be lead on your code.

5) At last, we wish to develop a blocking version of your system call, that is, we have a new config mode in (config = 2 for example) which represents a blocking read. That is now, when the system call is performed with a "2" mode, the system call returns only when a data has been read. What would you have to change to your implementation? Once again, I do not ask you to modify your code, but rather to explain me what would be the major and minor modifications to be lead on your code.