ECE391: Computer Systems Engineering Fall 2019
Machine Problem 1 Due: Monday 16 September at 6:00 PM
Life or Death
Please read the entire document before you begin.
In this machine problem, you will implement a text-mode game in which a player tries to save the human race from
an aggressive virus by finding a sequence of DNA bases that enables vaccination against the virus. Your code must
be written in x86 assembly, and will operate as extension to the Linux real-time clock (RTC) driver. This assignment
provides substantial experience with the x86 ISA and an introduction to how drivers accomplish tasks inside the Linux
kernel. Specifically, you will be implementing and using argument checking, bit manipulation, dynamic allocation,
copying between user and kernel memories, double buffering, jump tables, multi-dimensional arrays, and text-mode
video. This handout explains the assignment in detail, then explains some of the concepts that you must understand,
use, and implement.
Your work must be confined to the mp1.S file to receive credit.
A Note On This Handout: The sections entitled “Linux Device Driver Overview,” “RTC Overview,” “Ioctl Func-
tions,” and “Tasklets” contain background Linux knowledge which is not critical for you to complete this MP. The
material described in these background sections will be covered in lecture in the next few weeks, but it may be helpful
to read these sections to familiarize yourself with the context of your code in this MP.
Life or Death, the Game
In the game, a virus has infected the human population and is spreading rapidly. Your job is to identify a 5-base
DNA sequence that can be used to generate a vaccine against the virus. Each base can take one of four possible
values: A(denine), C(ytosine), G(uanine), or T(hymine). The virus spreads in real time on the screen based on a slight
modification to Conway’s Game of Life. The more of the virus is on the screen, the more rapidly the human population
decreases. If the population reaches zero, you lose the game.
You can at any time try to vaccinate the population using your current DNA sequence. The closer your sequence is to
the sequence of the virus, the more virus cells are wiped out by vaccination. However, being close is not necessarily a
good thing—the closer your sequence is to the correct sequence, the more likely that the virus will mutate and become
more aggressive as a result of your vaccination attempt. You also gain hints as to which bases are correct or incorrect
by vaccination; in this case, the more widespread the virus, the more hints you receive.
The implementation of the game centers around a two-dimensional game board of virus cells and the two DNA se-
quences (the virus’ and the player’s guess). The game consists of two separate components: the kernel-space code,
which manages two copies of this board, statistics about the virus, and some user input; and the user-space code, which
implements the rest of the game. You must write a tasklet (see the section “Tasklets”, below) to execute in response to
each interrupt generated by the RTC (see “RTC Overview”) and update the game board in real-time. The game board
and statistics reside inside the RTC driver in the kernel, so you must also write five ioctl’s (see “Ioctl Functions”) to
provide the necessary interface between the kernel-space components of the game and the user-space components.
MP1 Data Structure
The game board is a dynamically-allocated 20 × 80 array (20 rows, 80 columns) of unsigned characters. The game
uses two such boards to simplify the process of calculating the next generation of the virus from the current generation.
You must also use two additional structures to pass information into and out of the Linux kernel safely. These are the
struct keystroke args and struct game status structures, which are given in mp1.h.
The structure definitions are usable only in C programs. There are constants defined for you at the top of the provided
version of mp1.S that give you easy access to the fields of these structures from your assembly code. See the com-
ments in mp1.S for further information on how to use them.
2MP1 Tasklet
The first function you need to write is called mp1 rtc tasklet. The tasklet must update the game boards and draw
the screen, then notify the user-level code that the boards have been updated. Its C prototype is:
void mp1 rtc tasklet (unsigned long arg);
Every time an RTC interrupt is generated, mp1 rtc tasklet is called. The parameter arg is meaningless and should
be ignored. If current board is defined, your tasklet must perform a sequence of five operations. We recom-
mend that you implement the functionality using two or more additional functions, then call those functions from
mp1 rtc tasklet.
Begin by checking the value of current board. If it is 0, your tasklet should return immediately. Otherwise, perform
the five steps below.
First, your tasklet must use the current board to update the next board. For every cell in the current board that is
not on any of the four boundaries, determine whether the corresponding cell in the next board should be live or dead
by applying a set of rules slightly modified from Conway’s Game of Life. These rules have been implemented for you
using two C functions:
int neighbor count (unsigned char* cell);
int tick result (unsigned char cur, int neighbors);
Call neighbor count with a pointer to the cell (in current board) to obtain the number of live neighbors (every
cell in each board must contain either 0 for dead or 1 for live). Then call tick result with the cell’s current value
(again from current board) and the number of neighbors to obtain the cell’s value (0 or 1) in the next generation,
which can be stored into the corresponding cell in next board. As you compute each cell’s value, keep a running
total of live cells in next board. After calculating all cells in next board, multiply the total number of live cells
by 10 and store the product as the current infection value.
The second step for your tasklet is to swap the two board pointers (to implement double-buffering).
Next, subtract the new infection value from the population; treat these values as unsigned, and be sure not to let
population drop below 0 (set it to 0 if it does).
Fourth, your tasklet must redraw the screen. We have left a placeholder for a draw screen function in the code given
to you. You may design the interface to this function however you like, but write the screen-drawing code there, then
call the function from your tasklet. See the section entitled “Text-Mode Video” for support functions, and note that
CELL LIVE and CELL DEAD character constants have been provided to you in mp1.S, but you may change them as
you like so long as the virus is visible in your implementation. The board data are organized in the same order as the
screen data: each board consists of an array of 20 rows of arrays of 80 columns of unsigned char (bytes). The first
byte of the board should be mapped to the upper left corner of the screen, the columns should map to columns on the
screen, and the rows should map to rows on the screen.
Finally, your tasklet must notify the user-space program by calling mp1 notify user before the tasklet returns:
void mp1 notify user (void);
MP1 Ioctls
The next function you must write is called mp1 ioctl. Its C prototype is:
int mp1 ioctl (unsigned long arg, unsigned long cmd);
This function serves as a “dispatcher” function. It jumps to one of five functions based on the cmd argument. The
table on the next page gives a brief summary of cmd values, the corresponding core function, and a brief description of
what that core function does. Each of the core functions are described in the section entitled “Core Functions.” Note
that mp1 ioctl must check the cmd value and, if cmd is invalid, return -1.
3cmd value Core function Description
0 mp1 ioctl startgame start the life or death game
1 mp1 ioctl endgame end the game
2 mp1 ioctl keystroke handles guess modification keystrokes
3 mp1 ioctl getstatus get the current game status
4 mp1 ioctl vaccinate purge virus and increase aggression
other - Any value other than 0-4 is an error. Return -1.
The method used to jump to one of the core functions is to use assembly linkage without modifying the stack. A
picture of the stack at the beginning of mp1 ioctl is shown below.
return address
arg
command number
(previous stack)
ESP
Each of the core functions takes arg directly as its parameter. Since this parameter is passed to the mp1 ioctl func-
tion as its first parameter, mp1 ioctl can simply jump directly to the starting point of one of the core functions without
modifying the stack. The arg parameter will already be the first parameter on the stack, ready to be used by the core
function. In this way, it will appear to the core functions as if they were called directly from the RTC driver using the
standard C calling convention without the use of this assembly linkage. Your mp1 ioctl must use a jump table—see
the “Jump Tables” section for more detail.
Support Functions
To reduce the amount of assembly code that you must write, and to focus your effort on a fairly diverse set of oper-
ations (rather than repetition), we have provided five support functions for use by your assembly code. Two of these
functions were described for use with the tasklet. The remaining three are to be used by your ioctl functions:
void seed generator (unsigned long val);
unsigned long generate ();
int init virus (unsigned char* board);
The first two functions above provide a simple pseudo-random number generator. The seed for the generator is set
using the seed generator function, after which the generate function can be used to generate unsigned 32-bit
random numbers.
The last function, init virus, places two blobs of virus into a board randomly. Your code must call init virus
after allocating and initializing the game boards, as mentioned in the next section. The function returns the number of
live virus cells placed into the board.
Core Functions
You must implement each of the following five functions in x86 assembly in the mp1.S file. Remember that you
may ONLY modify mp1.S in this MP.
int mp1 ioctl startgame (unsigned long seed);
This function is called when the game is about to start in order to initialize the variables used by the driver—all of the
variables declared in mp1.S. The parameter passed in seed must be used to seed the random number generator by
passing the argument to the seed generator function. The two game boards should be dynamically allocated using
mp1 malloc. Refer to the “Allocating and Freeing Memory” section for information on dynamic allocation. If either
allocation fails, be sure to free any allocated memory (from the first allocation) and leave the two board pointers set
to 0. After allocating the boards, fill them both with 0 bytes, then call init virus on the current board. The return
value from init virus is the initial value for infection. The aggression value should initially be set to 80, and
population, which is measured in thousands of humans, should initially be 8,000,000. The function should return -1
if either allocation fails, or 0 if both succeed.
4int mp1 ioctl endgame (unsigned long ignore);
This function is called when the game is over to clean up the driver state. In particular, the function must free both
game boards and set the two pointers (current board and next board) back to 0. The function should then return 0
for success.
int mp1 ioctl keystroke (struct keystroke args* keystroke args);
This ioctl handles direction keystrokes, which move the base selector left and right and change the selected base. First,
the function must copy the arguments from user space into kernel memory—we suggest that you allocate a structure
on the stack for this purpose (use the constants KA STACK and KA SIZE in mp1.c). Read the section entitled, “Moving
Data to/from the Kernel” for information on copying memory. If the copy fails, the function should return -1. The
direction field specifies the direction of the keystroke: 0 for left, 1 for down, 2 for right, and 3 for up. If left/right has
been pressed, the function should erase the current selector (a string is provided to you in mp1.S), change the selector
value appropriately (cyclically around the five possible values from 0 to 4), and redraw the selector using a second
provided string. The selector image starts at screen location (14 + 10S, 22), where S is the selector position. Be sure
to write the new selector position back into the kernel’s copy of the keystroke args. The up and down directions
change the selected base. Each base value ranges from 0 to 3. The up button increases the value (cyclically), while the
down button decreases it. The resulting base must appear in the corresponding hints, which are mapped as a bit vector
for each selector position (bit 0 is A/0, bit 1 is C/1, bit 2 is G/2, and bit 3 is T/3)—bits that are 1 in the hint are allowed.
If the base is not in the hints, keep changing the base in the same direction until a base in the hints for that position
is found. Again, remember to write the final value back into the kernel’s keystroke args structure. Then draw the
base to the screen at position (18 + 10S, 22), where S is again the selector position (a string containing the bases in
order has been provided for your use in mp1.S). Finally, regardless of the direction of the keystroke, the function must
copy the modified keystroke args structure from the kernel back into user space (at the same location given by the
argument). If the copy fails, return -1. Otherwise, return 0.
int mp1 ioctl getstatus (unsigned long* user status);
This function allows the user code to retrieve the current population and virus infection count from the kernel variables
(population and infection). The argument provides a pointer to a structure in user space into which the function
must copy these values. We suggest that you allocate space for a structure on the kernel stack (use the constant
GS SIZE in mp1.c), fill in the values, then use mp1 copy to user to copy the information to the address passed. If
the call fails, return -1, or 0 if the call succeeds.
int mp1 ioctl vaccinate (unsigned long packed args);
This function handles the work necessary for vaccination. In particular, the function checks whether a vaccination
eliminates each live cell in the virus and increases the virus’ aggression level. The parameter packed args is a
32-bit integer containing two unsigned 16-bit integers packed into its low and high words. The low 16 bits contain
the percentage chance that a live cell in the current board should be killed (set to 0). For each cell in the board, your
code must call the generate function to generate a 32-bit unsigned random number, calculate the remainder of that
number when divided by 100, then compare with the given percentage to determine whether or not to kill that cell.
The high 16 bits contain an unsigned amount that must be added to the aggression variable, increasing the rate at
which the virus expands. You may ignore the possibility of overflow. This function should always return 0.
Synchronization Constraints
The code (both user-level and kernel) for MP1 prevents the tasklet from executing in the middle of any of the ioctls
on a uniprocessor.1 However, interrupts must be turned on for dynamic allocation and memory copies. Thus any call
made to mp1 malloc, mp1 free, mp1 copy from user, or mp1 copy to user can be interrupted by execution of
the tasklet. Your implementation must ensure that the variables are in a state that is safe for the tasklet before calling
any of these functions from an ioctl function (a tasklet cannot interrupt itself in Linux).
For example, in mp1 ioctl startgame, your code should ensure that both boards are allocated and initialized and
that all other variables are also initialized before modifying either of the board variables. The board variables should
only be changed immediately before returning 0 (success).
1If you for some reason try to use this code on a multiprocessor, we suggest that you strengthen the critical sections (or think carefully about
possible interleavings).
5Similarly, in mp1 ioctl endgame, your code should read the two board pointers into registers, overwrite the variables
with 0, and only then call mp1 free on the boards.
The other functions shouldn’t have problems if implemented as described in the “Core Functions” section.
Getting Started
Be sure that your development environment is set up from MP0. In particular, have the base Linux kernel compiled
and running on your test machine. Begin MP1 by following these steps:
• We have created a Git repository for you to use for this project. The repository is available at
https://gitlab.engr.illinois.edu/ece391 fa19/mp1
and can be accessed from anywhere.
• Access to your Git repositories will be provisioned shortly after the MP is released. Watch your @illinois.edu
email for an invitation from Gitlab.
• To use Git on a lab computer, you’ll have to use Git Bash on Windows, not the VM. You are free to download
other Git tools as you wish, but this documentation assumes you are using Git Bash. To launch Git Bash,
click the Start button in Windows, type in git bash, then click on the search result that says Git Bash.
• Run the following commands to make sure the line endings are set to LF (Unix style):
git config --global core.autocrlf input
git config --global core.eol lf
• Switch the path in git-bash into your Z: drive by running the command: cd /z
• If you do NOT have a ssh-key configured, clone your git repo in Z: drive by running the command (it will
prompt you for your NETID and AD password):
git clone https://gitlab.engr.illinois.edu/ece391 fa19/mp1 .git mp1
If you do have a ssh-key configured, clone your git repo in Z: drive by running the command:
git clone [email protected]:ece391 fa19/mp1 .git mp1
In your devel machine:
• Change directory to your MP1 working directory (cd /workdir/mp1). In that directory, you should find a file
called mp1.diff. Copy the file to your Linux kernel directory with
cp mp1.diff /workdir/source/linux-2.6.22.5
• Now change directory to the Linux kernel directory (cd /workdir/source/linux-2.6.22.5). Apply the
mp1.diff patch using
cat mp1.diff | patch -p1
The last argument contains a digit 1, not the lowercase letter L. This command prints the contents of mp1.diff
to stdout, then pipes stdout to the patch program, which applies the patch to the Linux source. You should
see that the patch modified three files, drivers/char/Makefile, drivers/char/rtc.c, and
include/linux/rtc.h. Do NOT try to re-apply the patch, even if it did not work. If it did not work, re-
vert all 3 files to their original state using SVN (svn revert ). After that, you may try to apply
the patch again.
• Change directory back to /workdir/mp1. You are now ready to begin working on MP1.
• Do not commit the Linux source or the kernel build directory. The number of files makes checking out
your code take a long time. If during handin, we find the whole kernel source or the build directory
in your repository, you will lose points. We have added a .gitignore file to your initial repository. This file
contains all the Git ignore rules that tells Git to not commit the specified file types. The Linux source and kernel
build directory are one such example of files that are ignored. Try and explore the .gitignore file to see what
other file types are ignored.
Be sure to use your repository as you work on this MP. You can use it to copy your code from your development ma-
chine to the test machine, but it’s also a good idea to commit occasionally so that you protect yourself from accidental
loss. Preventable losses due to unfortunate events, including disk loss, will not be met with sympathy.
6Testing
Due to the critical nature of writing kernel code, it is better to test and debug as much as possible outside the kernel.
For example, let’s say that a new piece of code has a bug in it where it fails to check the validity of a pointer passed in
to it before using it. Now, say a NULL pointer is passed in and the code attempts to dereference this NULL pointer.
When running in user space, Linux catches this attempt to dereference an invalid memory location and sends a signal,2
SEGV, to the program. The program then terminates harmlessly with a “Segmentation fault” error. However, if this
same code were run inside the kernel, the kernel would crash, and the only recourse would be to restart the machine.
In addition, debugging kernel code requires the setup you developed in MP0—two machines, connected via a virtual
TCP connection, with one running the test kernel and the other running a debugger. In user space, all that’s necessary
is a debugger. The development cycle (write-compile-test-debug) in user space is much faster.
For these reasons, we have developed a user-level test harness for you to test your implementation of the additional
ioctls and tasklet. This test harness compiles and runs your code as a user-level program, allowing for a much faster
development cycle, as well as protecting your test machine from crashing. Using the user-level test harness, you can
iron out most of the bugs in your code from user space before integrating them into the kernel’s RTC driver. The
functionality is nearly identical to the functionality available if your code were running inside the kernel.
The current harness tests some of the functionality for all the ioctls, but it is not an exhaustive test. It is up to you to
ensure that all the functionality works as specified, as your code will be graded with a complete set of tests.
Note: For this assignment, a test harness is provided to you that can test some of the functionality of your code prior
to integration with the actual Linux kernel. Future assignments will place progressively more responsibility on you,
the student, for developing test methods. What this means is that a complete test harness will not be provided for every
MP, and it will be up to you to design and implement effective testing methods for your code. We encourage you to
look over how the user-level test harness works for this MP, as its design may be of use to you in future MPs. This
test harness is fully functional, and uses some advanced programming techniques to achieve a complete simulation
of how your code will execute inside the Linux kernel. You need not understand all of these techniques; however,
understanding the important ideas is useful. Questions on Piazza as to how this test harness works are welcome as
well.
Running the user-level test program: To run the user-level test program, follow these steps:
• Type cd /workdir/mp1 to change to your MP1 working directory.
• Type make to compile your code and the test harness.
• Type su -c ./utest to execute the user-level test program as root (you will need to type root’s password).
You can also type su -c "gdb utest" to run gdb on the user-level test harness to debug your code. Debugging
the kernel code will be difficult. Use the disas (disassemble) command on mp1 rtc tasklet or mp1 ioctl to see
the start of your code (feel free to add more globally visible symbols), then use explicit addresses to see the rest of
it. Be sure to start any disassembly with the starting byte of an instruction rather than an address in the middle of
an instruction. With non-function symbols (such as those in your assembly code), and with addresses, you need an
asterisk when identifying a breakpoint. For example, break *mp1 ioctl or break *0x12345678.
The test code changes the display location to the start of video memory. If you do not see a prompt after the code
finishes (correctly or otherwise), pressing the Enter key will usually return the display to normal. Note also that
gdb will return the display to its usual location, after which you will not be able to see any of the animation (while
debugging).
Note: When running the user test under gdb, the debugger stops your program whenever a signal (such as SIGUSR1
or SIGALRM) occurs. To turn off this behavior and make it easier to debug your program, type the following com-
mands in gdb:
handle SIGUSR1 noprint
handle SIGALRM noprint
2Think of a signal as a user-level (unprivileged) interrupt for now.
7Testing your code in the kernel: Once you are confident that your code is working, you need to build it in the kernel.
• If you logged in as root to test, log out and back in again as user. If you have not already done so, commit your
changes to the MP1 sources.
• Type cp /workdir/mp1/mp1.S /workdir/source/linux-2.6.22.5/drivers/char to copy your
mp1.S file to your kernel source directory.
• Type cd ∼/build to change to the Linux build directory.
• Type make to build the kernel with your changes. If you have applied the mp1.diff file as described in the
“Getting Started” section of this handout, the kernel will build and link properly.
• Follow the procedure described in MP0, “Preparing Your Environment,” to install your new kernel onto the test
virtual machine and run it. We suggest that you execute the test kernel under gdb when debugging.
• In the test machine, navigate to your mp1 directory using the command cd /workdir/mp1, then type make
clean and make.
• Type su -c ./ktest to execute the kernel test program as root (you will need to type root’s password).
Both test programs should produce the exact same behavior.
Moving Data to/from the Kernel
Virtual memory allows each user-level program to have the illusion of its own memory address space, separate from
any other user-level program and also separate from the kernel. This affords each program a level of protection, such
that user-level programs cannot write to memory owned by other programs, or worse, owned by the kernel. There-
fore, when passing memory addresses between a user-level program and the kernel (such as in an ioctl system
call) a translation is needed so that the kernel can correctly reference the user-level memory address being passed
to it to get at the data. This translation is performed by the mp1 copy to user and mp1 copy from user func-
tions, which are wrappers around the real Linux kernel functions copy to user and copy from user defined in
asm-i386/uaccess.h.
The declarations for these two functions are:
unsigned long mp1 copy to user (void *to, const void *from, unsigned long n);
unsigned long mp1 copy from user (void *to, const void *from, unsigned long n);
The semantics of mp1 copy to user and mp1 copy from user are similar to those of memcpy, for those of you
familiar with it. These functions take two pointers to memory areas, or buffers, to and from, and a length n. Each
function copies n bytes from the from buffer to the to buffer. As can be inferred from their names, mp1 copy to user
copies data from a kernel buffer to a user-level buffer, and mp1 copy from user copies data from a user-level buffer
to the kernel. All user- to kernel- address translations are taken care of by these functions. Each of these functions
returns the number of bytes that could not be copied, which should be 0. Bad user-level pointers can cause return
values greater than zero. For example, if you pass a NULL pointer in as the user-level parameter to one of these
functions (such as the to parameter in mp1 copy to user), it checks the pointer and memory area, sees that it points
to an invalid buffer, and returns n, since it could not copy any data.
You’ll need these functions in any of the core functions which take pointers to user-level structures. Each ioctl takes
an “arg” parameter, so you will need to look at the documentation for each ioctl to figure out which ones are actually
pointers to user-level structures.
One final important note: When copying data to a buffer in the kernel, you should not use statically-allocated global
buffers. In multiprocessor systems, for example, multiple calls to your ioctl functions may be going on at the same
time. Using a statically-allocated storage area, like a global variable, is a bad idea because the separate calls to the
ioctl would be contending for using this same storage area. You should use either local variables on the stack or
dynamically-allocated memory. Refer to the Course Notes for information on allocating local variables on the stack.
The section below has information on dynamic memory allocation in the Linux kernel.
8Allocating and Freeing Memory
User-level C programs make use of the malloc() and free() C library functions to allocate memory needed for
storing dynamic structures such as linked list elements. Linux kernel code uses a number of different memory allo-
cation functions that you will learn later in the semester. Since your code must run in the kernel, you must use the
memory allocation services provided there. To abstract the details away (for now), the MP1 distribution contains two
memory allocation functions that behave similarly to malloc() and free(). Their prototypes are:
void* mp1 malloc(unsigned long size);
void mp1 free(void* ptr);
mp1 malloc takes a parameter specifying the number of bytes of memory to allocate. It returns a void*, called a
“void pointer,” which is the memory address of the newly-allocated memory.
mp1 free takes a pointer to a block of memory that was allocated with mp1 malloc() and releases that memory back
to the system. It does not return anything.
Text-Mode Video
Each character on the text display comprises two bytes in memory. The low byte contains the ASCII value for the
character to be display. The high byte is an attribute byte, which holds information about the color of that particular
character on the screen.
The screen is divided into rows and columns, with the upper-left character position referred to as row 0, column 0.
Each row is 80 characters wide, and there are 25 rows. The screen is stored linearly in video memory, with each
successive row stored directly after the one above it. For example, row 1, column 0 immediately follows row 0,
column 79 in memory, row 2, column 0 immediately follows row 1, column 79, and so forth. Thus, to write a pixel at
row 12, column 15 on the screen, you first need to calculate the row offset: row 12 × 80 characters per row × 2 bytes
per character = 1920. Then, add the column offset: column 15 × 2 bytes per character = 30. So, row 12 column 15 on
the screen is 1920 + 30 = 1950 bytes from the start of video memory.
mp1 poke: Due to Linux’s virtualization of the screen buffer and of video memory, the start of video memory is
not a constant, so writing to video memory is somewhat more complicated than using a mov instruction. To simplify
things for this MP, a function has been defined called mp1 poke. This function, defined in assembly in mp1.S, takes
care of finding the starting address of video memory and writing a single byte to an offset from that starting address.
mp1 poke does not make use of the C calling convention discussed in the Course Notes. Instead, to use mp1 poke,
make a function call with the following parameters:
%eax offset from the start of video memory
%cl ASCII code of character to write
mp1 poke then finds the correct starting address in memory and writes the character in CL to the location specified by
EAX.
Note: For mp1 poke, EDX is a caller-saved register (in other words, mp1 poke clobbers EDX). If you need to preserve
the value of EDX across a call to mp1 poke, you must save its value on the stack. This preservation can be accom-
plished by pushing the register’s value onto the stack with pushl %edx before making the call, and then popping the
value back into EDX with popl %edx. All other registers are callee-saved (that is, mp1 poke preserves their values).
9Jump Tables
You must use a jump table to perform the “dispatching” operation in mp1 ioctl. A jump table is a table in memory
containing the addresses of functions (called function pointers). Each function pointer is a 32-bit memory address,
just like any other pointer. The memory addresses that you want to put in the jump table are the labels of the start of
each function. Let’s say you have three functions in an assembly (.S) file, with labels function0, function1, and
function2 as the names of each. You can define a jump table as follows:
function0:
# function 0 body
function1:
# function 1 body
function2:
# function 2 body
jump_table:
.long function0, function1, function2
The jump table provides an easy way to access those three functions. If you view the jump table as a C-style array of
pointers:
void* jump_table[3];
jump table[0] (in other words, the memory location at jump table + 0 bytes) holds the address of function0,
jump table[1] (at jump table + 4 bytes) holds the address of function1, and jump table[2] (at jump table
+ 8 bytes) holds the address of function2. In these examples, the number inside the brackets is the “index” into the
jump table.
In this MP, the cmd parameter should serve as the index into the jump table, and you should be able to easily jump to
each of the five core functions by creating a table similar to that shown above.
Linux Device Driver Overview
The first important concept in Linux device drivers is the fact that Linux makes all devices look like regular disk files.
If you list the files in the /dev directory (using ls), you can see some devices that may be present on the machine.
Each device is associated with one of the files. For example, the first serial port is associated with the device file
/dev/ttyS0. For this MP, you will be dealing with the /dev/rtc device file, which is the device file associated with
the real-time clock.
Since everything looks like a file, Linux drivers must support a certain set of standard file operations on their asso-
ciated device files. These operations should seem familiar, as they are the operations available for normal disk files:
open, close, read, write, lseek (to move to arbitrary locations within the file), and poll (to determine if data is
available for reading or writing). In addition, most device files support the ioctl operation. ioctl is short for “I/O
control,” and this operation is used to perform miscellaneous control and status actions that do not easily fall into one
of the more standard file operations—things that you wouldn’t do to normal disk files. A good example of an ioctl
is setting the frequency or rate of interrupts generated by the real-time clock. ioctls are discussed in more depth
later in this handout. It is also important to note that drivers need not support all these operations; they may choose to
support only those necessary to make the device useful.
10
RTC Overview
A computer’s real-time clock can generate interrupts at a settable frequency. Real programs running on Linux can
make use of this device to perform timing-critical functionality. For example, a Tetris-style video game may need to
update the positions of the falling blocks every 500 milliseconds (ms). Using the RTC, the game might set up the RTC
to generate interrupts every 500 ms. Using the standard file operations above, the game can then know exactly when
500 ms has elapsed, and update its internal state accordingly.
We now use the RTC driver to illustrate how the standard file operations given above map to a real device. The
RTC driver uses the open and close operations as initialization and cleanup mechanisms for certain internal data
structures and setup routines. Once open’ed, four bytes of data become available to be read from /dev/rtc on every
RTC interrupt. Programs can use the read or poll file operations to wait for these four bytes of data to become
available, thus effectively waiting for the next RTC interrupt to be generated. The ioctl operation handles many
other functions: setting the interrupt rate, turning RTC interrupts on and off, setting alarms, and so forth.
The important concept to glean from this discussion is that drivers provide a uniform file-like interface to the outside
world via their device file and the standard set of file operations described above. The internals of actually managing
the device itself are left to the driver, and are not visible to normal programs. For example, in the RTC driver, no
program is able to directly gain control of the RTC, manage its interrupts, and so forth. Changing the frequency is
accomplished via an ioctl, and determining when an interrupt has been generated is done by waiting for the four
bytes of data to become available to be read using read or poll.
Ioctl Functions
An ioctl call from a user-mode program looks like the following:
ioctl(int file descriptor, int IOCTL COMMAND, unsigned long data argument);
The file descriptor parameter is returned from a call to open on a particular file, in this case /dev/rtc. It is
simply a number used by a program to reference a particular file that the program has opened. The program then
passes this file descriptor to other functions like ioctl, indicating that it is /dev/rtc that the program wishes to
operate upon.
The IOCTL COMMAND parameter is the particular ioctl operation to be performed on the device. It is shown in caps
because all ioctl operations are defined as constants in the header file for each device driver. All that is needed for a
program to do is select the proper predefined ioctl command and pass that command to the ioctl call.
Finally, the data argument parameter is an arbitrary value passed to the ioctl. It can be a numeric value or a
pointer to a more complex structure used by the ioctl. The MP1 testing code passes pointers to special structures
that contain all the data necessary for your RTC driver to perform the new ioctls described below.
Tasklets
Interrupt handlers themselves should be as short as possible to allow the operating system to perform other time-critical
tasks. Remember, when an interrupt occurs, control is immediately handed to the operating system so it can service
the device. All other tasks are blocked while the interrupt handler is executing. A tasklet is a way for an interrupt
handler to defer work until after the kernel has finished processing time-critical tasks and is about to return to a user
program. Normally, the interrupt handler does urgent work with the device, and then schedules a tasklet to run later
to do the heavier I/O or computation that takes much longer. The operating system can enable all interrupts while the
tasklet is executing. The main reason for deferring this sort of work is to allow other interrupts to occur while this
non-critical work is being done. This improves the responsiveness of the system.
In MP1, the RTC hardware interrupt handler schedules your tasklet (mp1 rtc tasklet) to run. When the kernel is
about to return from the interrupt, it calls your tasklet, which then can update the text-mode video screen, yet allow
other interrupts to occur.
11
Coding Style and Design
In general, being able to write readable code is a skill that’s just as important as being able to write working code.
People and industry teams have their own preferences and rules when it comes to coding style. In this class, we
won’t nitpick over small things such as spaces, blank lines, or camel case, nor will we enforce any rigorous coding
guidelines. However, we still do have a basic standard that we expect you to adhere to and will be enforced through
grading. Our expectations are outlined below:
• Give meaningful and descriptive (but not too long) names to your variables, labels, constants, functions, and
files. Be consistent in your naming conventions.
• Do NOT use magic numbers (any number that appears in your code without a comment or meaningful symbolic
name). -1, 0, and 1 are usually OK when used in obvious ways.
• Keep programs and functions relatively short. Don’t write spaghetti code that jumps back and forth everywhere.
Create helper functions instead and make it easy to follow the flow of the program.
• Use comments to explain the interfaces to all functions or subroutines, lengthy segments of code, and any non-
obvious line of code. However, do NOT overdo it. Too many comments is just as bad as too little. Use comments
to explain why, not what.
Handin
Handin will consist of a demonstration in the 391 Lab. During the demo, a TA will check the functionality of your
MP, review your code, and ask some basic questions to test your understanding of the code.
Important Things to Note:
• Regardless of your assigned demo day, the deadline is the same for everyone!
• Once the deadline hits, your GitLab write access to the project will be revoked and you will not be able to push
to your repositories.
• You are free to develop your own system of code organization, but we will STRICTLY use only the master
branch for grading, and will only make use of your mp1.S file.
A Final Note on Testing: Sanity Checks and GDB
We have included two sanity checks in life-or-death.c to help ensure that you correctly check the return values
when copying memory into and out of the Linux kernel. Unfortunately, doing so makes debugging the user-level ver-
sion of the game slightly more difficult. If you are confident that your mp1 ioctl keystroke and
mp1 ioctl getstatus implementations are handling these issues correctly (if, for example, they pass our sanity
checks), then you may want to remove the sanity checks from the code. Until then, we suggest entering the following
commands to start utest in gdb:
handle SIGUSR1 noprint
handle SIGSEGV noprint
break life-or-death.c:407
commands 1
handle SIGSEGV stop
continue
end
run