Operating Systems

DM510, Spring 2009

Daniel Merkle

DM510 Required Assignment 1: System Call

In this assignment, your task is to add system calls to User-mode Linux (UML), that implement a message box in kernel space. Before staring working on this assignment, make sure you have a running user mode linux kernel [html], and that you followed the description of how to add a Linux system call [html]. The system calls that you have to implement are more complex and useful.

The System Call

Message passing is a method of interprocess communication. Basically, the idea is that processes send small messages / byte arrays to each other using either the operating system or in some other way (e.g., MPI). Often this way of communication is used in distributed systems or in general when shared memory is not possible. Message-passing systems in general is covered in Section 3.4 in the Operating System Concepts book.

Your task is to make two system calls that give processes access to a small message box residing in kernel-space. The system calls must make it possible to retrieve messages from the message box into the address-space (user-space) of the calling process. Also, it must be possible to write a message from the calling process into the message box.

To make things simple the message box should be implemented as a stack, i.e., incoming messages are put at the top of the stack, and outgoing messages are also read from the top of the stack. Messages are only to be read once, i.e., they are removed from the stack immediately after retrieval.

Simple user-space version

The code below is a simple user-space version of the message box system call.

Download: dm510_msgbox.h
#ifndef __DM510_MSGBOX_H__
#define __DM510_MSGBOX_H__

int dm510_msgbox_put( char*, int );
int dm510_msgbox_get( char*, int );
#endif

 

Download: dm510_msgbox.c
#include "dm510_msgbox.h"
#include <stdlib.h>
#include <string.h>

typedef struct _msg_t msg_t;

struct _msg_t{
  msg_t* previous;
  int length;
  char* message;
};

static msg_t *bottom = NULL;
static msg_t *top = NULL;

int dm510_msgbox_put( char *buffer, int length ) {
  msg_t* msg = malloc(sizeof(msg_t));
  msg->previous = NULL;
  msg->length = length;
  msg->message = malloc(length);
  memcpy(msg->message, buffer, length);

  if (bottom == NULL) {
    bottom = msg;
    top = msg;
  } else {
    /* not empty stack */
    msg->previous = top;
    top = msg;
  }
  return 0;
}

int dm510_msgbox_get( char* buffer, int length ) {
  if (top != NULL) {
    msg_t* msg = top;
    int mlength = msg->length;
    top = msg->previous;

    /* copy message */
    memcpy(buffer, msg->message, mlength);

    /* free memory */
    free(msg->message);
    free(msg);

    return mlength;
  }
  return -1;


}

int main ( void ) {
  /* test code here */
  return 0;
}

Below is an example to illustrate the use of the function.

int main(int argc, char** argv) {
  char *in = "This is a stupid message.";
  char msg[50];
  int msglen;
 
  /* Send a message containing 'in' */
  dm510_msgbox_put(in, strlen(in)+1);
 
  /* Read a message */
  msglen = dm510_msgbox_get(msg, 50);

  return 0;
}

You have to implement two separate system calls:

Both, the dm510_msgbox_put and the dm510_msgbox_get system call shall have two parameters:

The return value of the two system calls has to be implemented as follows:

dm510_msgbox_put
If the message was appended to the queue without any problems, 0 should be returned. Otherwise some negative value should be returned (more about this later).
dm510_msgbox_get
If a message was retrieved from the message box without any problems, the length of this message should be returned (note: this could be 0 in case of an empty message). Otherwise some negative value should be returned (more about this later).

Attacking the Problem

You could try to insert the dm510_msgbox_put and dm510_msgbox_get function directly into the kernel, but this would not work. In order to make it work you must address the following issues.

Note: all the functions mentioned below, can be used in your own kernel source file, if you include linux/slab.h.

Memory allocation

Memory allocation and deallocation in the Linux kernel is not done with the usual malloc and free. Instead you have to use kmalloc and kfree

For further information have a look at the corresponding linux kernel man pages for example here.

Address translation

An address from user-space does not map to the same physical address in kernel-space (cf. Operating System Concepts: Chapter 9). The Linux Kernel has special functions to translate user-space addresses in kernel-space. Three of these are particularly helpful for this assignment:

access_ok(int type, char* addr, int n)
type is either VERIFY_READ or VERIFY_WRITE. Checks whether it is safe to read (or write) n bytes from the user space address addr.
copy_to_user(char* to, char* from, int n)
Copies n bytes from the kernel address from to the user address to.
copy_from_user(char* to, char* from, int n)
Copies n bytes from the user address from to the kernel address to.

For further information, have a look at the man pages (see link abov).

Parameter checking and error handling

The simple version above is not checking its parameters at all. This means that if you call the function with invalid parameters, e.g. a wrong length < 0, the function would fail or cause unpredictable results. A system call must not be able to fail uncontrolled, because it could bring the kernel down.

For example, a system call that does not check user addresses could unintentionally overwrite parts of the kernels memory, which would leave the kernel in an invalid state. The functions described in the previous section return a non-zero value if there are problems accessing user addresses. kmalloc returns a NULL pointer, if it is unable to allocate memory.

When a system call detects an error it has to return an error code to make the caller aware of what has happened. In case of an error the function that implements the system call must return the negative value of the code that defines the error. Error codes used by other system calls are defined in include/asm-generic/errno.h and include/asm-generic/errno-base.h and these will suffice for this assignment.

man errno and man perror describes how errors are handled in user-space.

Concurrency

Unless special measures are taken any function in Linux including a system call may be interrupted. If the system call is in some critical region, this may cause problems. As an example of this, consider two processes that call the dm510_msgbox system call almost simultaneously. While the first process has partly updated the message box data structures with a new message, this process is interrupted, and the second process subsequently fails to update the data structures correctly.

To ensure that this does not happen, interrupts can be temporarily disabled using local_irq_save and local_irq_restore.

unsigned long flags;

local_irq_save(flags);
 
/* critical region */
 
local_irq_restore(flags);

local_irq_save saves the current processor state and disables interrupts, local_irq_restore restores the processor state, including enabling interrupts.

Later in the course you will learn how this could be done in a smarter way, e.g., by using semaphores. For more information, have a look at Documentation/cli-sti-removal.txt.

Report / Submisson

The report must be short and precise (maximum 10 pages, English langauge, without source code). Remember that you must prove that you have understood the problems and solutions. It must include the following:

  • A small introduction.
  • A description of the design decisions you have made.
  • A description of your implementation.
  • A description of the tests you have made and the motivation for these. The tests must be able to verify that your solution works correctly with both valid and invalid call parameters.
  • A discussion of what would happen if multiple processes simultaneously want to access the message box.
  • A small conclusion.

Furthermore, your report has to be suplemented by a recorded desktop session, in which you show that your implementation is working correctly. During the session you should also perform all or some of the tests that you described in your report. In your report you should refer to the tests you performed by giving the precise time in the video file. The session you record should start when you start UML with the command ./linux in a shell. The recorded session should be maximally 5 minutes long and have a maximal size of 20MB. If one of these constraints is not fulfilled the video file will be considered as not submitted.

For recording the desktop session you should use the tool gtk-recordMyDesktop, that is installed on all the IMADA pool machines. More information regarding the tool can be found here. Using the tool is straightforward. You define a region on your desktop and record whats happening. The tool then produces a video file that contains your recorded session. Change the "Video Quality" to 10 (using the slider), and the "Frames per Second" to be recorded to 5 (Advanced Setting / Performance) to reduce the file size. Sound recordning is not required. You can view the content of the video for example with mplayer. When pressing "o" in mplayer you can toggle the display of the time.

For submitting the report, the sources, and the desktop session, proceed as follows: Create the following directory structure

assignment1/
assignment1/report/
assignment1/sources/
assignment1/video/

Put your report, sources, and video in the corresponding directory. The sources should not include the source code of the complete Linux kernel, but only the files you changed and those files you added. The report direcory and the sources directory should not contain more than 10MB of data. Similar to the size of the video file: If this constraint is not fulfilled the submission will be not considered.

Change to the directory assignment1 and type aflever DM510.

The strict deadline for submission is Friday, March 6th, 13:00.

As this project is quite resource consuming, please take care, that you clean up your home directory and that you remove unneeded files as soon as possible.

Frequently Asked Questions (FAQ)

    Note that you will find FAQ for User Mode Linux here.

  • Are we allowed to work in groups?
  • For everything except the report and recording the desktop session, you are allowed to work in groups of at most three people. Write the members of your group on the front page of your report. The report you have to write on your own. Remember that the three required assignments are part of your final exam, i.e., you have to fully understand all parts of what you have done.

Design by 1234.info | Modified by Daniel Merkle | CSS 2.0