Text-Mode Missile Command
In this machine problem, you will implement a text-mode version of Missile Command, the classic arcade video game, in x86 assembly as an extension to the Linux real-time clock (RTC) driver. This assignment should provide substantial experience with the x86 ISA and provide an introduction to how drivers accomplish tasks inside the Linux kernel. This handout first explains your assignment in detail, then explains several concepts that you will need to understand and implement.
Please read the entire document before you begin.
to read these sections to familiarize yourself with the context of your code in this MP.: Missile Command
In our version of Missile Command, you control a missile silo and try to protect your cities from enemy missiles. You direct your missiles by moving the crosshairs to the intended destination and pressing the spacebar to fire. The explosion generated at that location destroys enemy missiles within a two-square radius. The game ends when enemy missiles destroy all of your cities. Your score is the number of enemy missiles that you destroy.
The implementation of this game centers around a linked list containing an element for each active missile in theEmail:
game. The game consists of two separate components: the kernel-space code, which manages this list, and the userspace code, which implements the rest of the game and processes user input. You will write a tasklet (see the section
βTaskletsβ, below) to execute on each interrupt generated by the RTC (see βRTC Overviewβ) and update the missiles in real-time. This linked list will reside inside the RTC driver in the kernel, so you will also write five ioctlβs (see βIoctl
Functionsβ) to provide the necessary interface between the kernel-space components of the game and the userspace components.
MP1 Data Structure
The main structure you will be working with is struct missile. struct missile {
struct missile* next; /* pointer to next missile in linked list */
2
int x, y; /* x,y position on screen */ int vx, vy; /* x,y velocity vector */ int dest_x, dest_y; /* location at which the missile explodes */
int exploded; /* explosion duration counter */ char c; /* character to draw for this missile */
}
This structure definition is usable only in C programs. There are constants defined for you at the top of the provided mp1.S that give you easy access to the fields in this struct from your assembly code. See the comments in mp1.S for further information on how to use them.
You must maintain a linked list of missiles with one struct missile for each active missile in the game. A variable mp1missilelist has been declared in mp1.S. You should maintain this variable as a pointer to the first element in the linked list.
The x and y fields of the structure contain the current location of the missile on the screen. The text-mode video screen is 80Γ25, i.e., there are 80 columns and 25 rows. In order to allow finer control over the missilesβ velocities, each text-mode location is subdivided into 65536Γ65536 sub-squares. The low 16 bits of the x and y fields determine which of these sub-squares the missile is in, and the high 16 bits of x and y determine the text-mode video location to draw the missile. This organization makes simultaneously updating both the βgameβ and βscreenβ coordinates easy.
The vx and vy fields contain the missileβs velocity, which you must use in your tasklet to update the x and y fields.
The destx and desty fields contain the missileβs destination, which is the screen location at which it must explode. When the missile reaches this location, it should stop moving and begin exploding, as explained below.
The exploded field specifies the current state of the missile. When exploded == 0, the missile has not exploded and should continue moving. When it explodes (either because it reached its destination or because another missile exploded nearby), this field will be set to a positive number by the provided function missileexplode (see βMP1 Taskletβ for details). While exploded is non-zero, your tasklet treats the missile differently. The missile should not move and should be drawn with the EXPLOSION character defined in mp1.S. Your tasklet should also decrement this field; when it reaches zero the explosion is over and your tasklet should remove the missile from the list and free the associated struct missile.
The c field specifies the character with which the missile should be drawn while it is in flight. This ability allows players to visually distinguish between enemy missiles and their own missiles.
MP1 Tasklet :
The first function you need to write is called mp1rtctasklet. The tasklet must update the state of the game and notify the user-level portion of the code if any cities have been destroyed or the game score has changed. Its
C prototype is:
void mp1rtctasklet (unsigned long arg);
Every time an RTC interrupt is generated, mp1rtctasklet will be called. Your tasklet must perform three different operations. We recommend that you implement each of them as a separate function, and call those functions from mp1rtctasklet.
First, your tasklet should walk down the struct missile linked list. For each missile, you should check whether it is currently exploding. If not, then you should update the x and y fields as explained above in the βMP1 Data
3
Structureβ section. There are then three cases based on the state and position of the missile.
Second, if the missile has reached its destination or is currently exploding, you must call missileexplode with a pointer to the missileβs struct missile as an argument. The missileexplode function (provided to you) checks whether this missileβs exposion causes any other missiles or any of your cities to explode. If so, it returns a non-zero value. Otherwise, it returns zero. After calling missileexplode, you must decrement the exploded field for this missile. If it reaches zero, then the missile is finished exploding and must be erased from the screen, removed from the list, and freed with mp1free. Otherwise, it should be drawn to the screen with the EXPLOSION character.
Finally, if the missile is simply moving toward its destination, is not exploding, and is still on the screen, you should check whether its screen position has changed. If so, you should erase it from its old position and re-draw it in its new position.
Note that in every case the missile should be re-drawnβit could have been over-written by another missile or the crosshairs moving through the same text-video location. For information on how to draw to the screen, see the βTextMode Videoβ section.
If any call made to missileexplode by the tasklet indicated that the status of the game changed (any non-zero return value), you must notify the user-space program once by calling mp1notifyuser before the tasklet returns.
After procesing all missiles, your tasklet must proceed with its second operation: redrawing the cities to ensure that any destroyed cities are drawn as destroyed. Also, if any missile has moved into a text-video location occupied by a city, the city should still be visible. The three cities should be drawn in the bottom row of the screen centered in columns 20, 40, and 60. There are two five-character arrays declared in mp1.S for you, basepic and deadbasepic for drawing live and destroyed cities. So, for example, the first city should be drawn in the five video locations from (18,24) to (22, 24). The basealive array indicates whether each city has been destroyed. It contains four bytes; each of the first three is zero if the corresponding base is dead and non-zero if it is alive. The fourth byte is padding.
city, and we want to ensure that it is always visible.
MP1 Ioctls
The next function you must write is called mp1ioctl. Its C prototype is:
int mp1_ioctl (unsigned long arg, unsigned long cmd);
This function serves as a βdispatcherβ function. It uses the cmd argument to determine which of the next five functions tion of what that core function does. Each of the core functions are described in the section entitled βCore Functions.β: to jump to. The table below gives a brief summary of cmd values, the corresponding core function, and a brief descripNote that you must check this cmd value; if it is an invalid command, return -1.
cmd value Core function Description
4
0
1
2
3
4 other mp1ioctlstartgame mp1ioctladdmissile mp1ioctlmovexhairs mp1ioctlgetstatus
Email:
tutmp1ioctlendgame
– nt Project Exam
ile command game
move the crosshairs get the current game status
[email protected] the
game -1 Any value other than 0-4 is an error. Return .
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 mp1ioctl is shown below.
ESPreturn address
arg command number
(previous stack)
Each of the core functions takes arg directly as its parameter. Since this parameter is passed to the mp1ioctl function as its first parameter, mp1ioctl 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 mp1ioctl must use a jump tableβsee the section βJump Tablesβ below.
Core Functions
You must implement each of the following five functions in x86 assembly in the mp1.S file. int mp1ioctlstartgame (unsigned long ignore);
This function is called when the game is about to start. The parameter passed in arg is meaningless and should be ignored. This function should initialize all of the variables used by the driverβall of the variables declared in mp1.Sβ and the crosshairs should be set to the middle of the screen: (40, 12). int mp1ioctladdmissile (struct missile* usermissile);
This ioctl must add a new missile to the game. The parameter is a pointer to a struct missile in user space. This function needs to copy the userβs missile into a dynamically allocated buffer in kernel space. If either the dynamic memory allocation (see βAllocating and Freeing Memoryβ below) or the data copy (see βMoving data to/from the kernelβ) fails, this function should return -1. If it does fail, it should be sure to free any memory it has allocated before returning. If it succeeds, it should add the new missile into the linked list and return 0.
int mp1ioctlmovexhairs (unsigned long xhairdeltapacked);
This function moves the crosshairs. The parameter is a 32-bit integer containing two signed 16-bit integers packed into change, and the high 16 bits contain the amount by which they component should change. This function should not its low and high words. The low 16 bits contain the amount by which the x component of the crosshair position should
allow the crosshairs to be moved off of the screenβthat is, it should ensure that the x component of its position stays within the range 0-79, and its y component stays within the range 0-24. If the position of the crosshairs does change, this function should redraw it at its new location. It should never fail, and always return 0. int mp1ioctlgetstatus (unsigned long* userstatus);
This function allows the user to retrieve the current score and the status of the three cities. The argument is a pointer to a 32-bit integer in user space. This function should copy the current score into the low 16-bits of that integer, and the in the mp1score variable declared in mp1.S. If a city is currently alive, the corresponding bit should be a 1; if it has status of the three cities into bits 16, 17, and 18. The missileexplode function maintains the userβs current score been destroyed, the bit should be 0. The missileexplode function maintains this information in the basealive array, as described above. This function should return 0 if the copy to user space succeeds, and -1 if it fails. int mp1ioctlendgame (unsigned long ignore);
Called when the game is over, this function must perform all the cleanup work. It should free all the memory being used by the linked list and then return success. When freeing the list, be careful to avoid accessing any memory that has already been freed.
Synchronization Constraints
The code (both user-level and kernel) for MP1 allows the tasklet to execute in the middle of any of the ioctls, so you must be careful to order the updates properly in some of the operations. Since the tasklet does not modify the list, the main constraint is that any ioctl that modifies the list does so in a way that never leaves the list in an unusable state.
In particular, mp1ioctladdmissile must fill in the newly allocated structure, including the next field, before changing the head of the list to point to the new structure.
Similarly, mp1missileremove must remove the element from the list before freeing it; copying the structureβs next pointer into a register is not sufficient, since the tasklet could try to read the structure after the call to mp1free. evelopment 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/ece391fa23/mp1<YOURNETID> and can be accessed from anywhere.
β’ Access to your Git repositories will be provisioned shortly after the MP is released. Watch your @illinois.eduemail 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/ece391fa23/mp1<YOURNETID>.git mp1
If you do have a ssh-key configured, clone your git repo inAssignment Project Exam HelpZ: drive by running the command: git clone [email protected]:ece391fa23/mp1<YOURNETID>.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
β’ 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, any object files 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.
Testing
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,
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 mp1rtctasklet or mp1ioctl 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 *mp1ioctl 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 commands in gdb: handle SIGUSR1 noprint handle SIGALRM noprint
Testing 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 yourchanges 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 testvirtual 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 KernelAssignment Project Exam Help
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. Therefore, when passing memory addresses between a user-level program and the kernel (such as in anEmail: 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 mp1copytouser and mp1copyfromuser functions, which are wrappers around the real Linux kernel functions copytouser and copyfromuser defined in
asm-i386/uaccess.h.
The declarations for these two functions are: unsigned long mp1copytouser (void *to, const void *from, unsigned long n);
unsigned long mp1copy fromuser (void *to, const voidorcs.com*from, unsigned long n);
The semantics of mp1copytouser and mp1copyfromuser 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, mp1copytouser copies data from a kernel buffer to a user-level buffer, and mp1copyfromuser 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 mp1copytouser), 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.
Allocating 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 allocation 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* mp1malloc(unsigned long size); void
mp1free(void* ptr);
mp1malloc 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. mp1free takes a pointer to a block of memory that was allocated with mp1malloc() 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.
%eax offset from the start of video memory %cl ASCII code of character to write
mp1poke then finds the correct starting address in memory and writes the character in CL to the location specified by EAX.
Note: For mp1poke, EDX is a caller-saved register (in other words, mp1poke clobbers EDX). If you need to preserve the value of EDX across a call to mp1poke, you must save its value on the stack. This preservation can be accomplished
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, mp1poke preserves their values).
Jump Tables
You must use a jump table to perform the βdispatchingβ operation in mp1ioctl. 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];
jumptable[0] (in other words, the memory location at jumptable + 0 bytes) holds the address of function0, jumptable[1] (at jumptable + 4 bytes) holds the address of function1, and jumptable[2] (at jumptable + 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
Since everything looks like a file, Linux drivers must support a certain set of standard file operations on their associated 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
RTC Overview
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 filedescriptor, int IOCTLCOMMAND, unsigned long dataargument); simply a number used by a program to reference a particular file that the program has opened. The program thenEmail: The filedescriptor parameter is returned from a call to open on a particular file, in this case /dev/rtc. It is passes this file descriptor to other functions like ioctl, indicating that it is /dev/rtc that the program wishes to operate upon.
The IOCTLCOMMAND 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 dataargument 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 timecritical 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 (mp1rtctasklet) 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.
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, andfiles. Be consistent in your naming conventions.
β’ Do NOT use magic numbers (any number that appears in your code without a comment or meaningful symbolicname). -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. Note that helper functions must obey the C calling convention.
β’ 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
MP, review your code, and ask some basic questions to test your understanding of the code.
Important Things to Note:
β’ 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.
