CS代考 ECE391: Computer Systems Engineering Fall 2021 – cscodehelp代写
ECE391: Computer Systems Engineering Fall 2021
Machine Problem 1
Due: September 14, 5:59 PM
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.
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.
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 the game. The game consists of two separate components: the kernel-space code, which manages this list, and the user- space 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 user-space components.
MP1 Data Structure
Themainstructureyouwillbeworkingwithisstruct missile.
struct missile {
struct missile* next;
int vx, vy;
int dest_x, dest_y;
int exploded;
/* pointer to next missile in linked list */
/* x,y position on screen */
/* x,y velocity vector */
/* location at which the missile explodes */
/* explosion duration counter */
/* 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.
Youmustmaintainalinkedlistofmissileswithonestruct missileforeachactivemissileinthegame.Avariable mp1 missile list 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 dest x and dest y 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 missile explode (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 associatedstruct 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 mp1 rtc tasklet. 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 mp1 rtc tasklet (unsigned long arg);
Every time an RTC interrupt is generated, mp1 rtc tasklet 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 mp1 rtc tasklet.
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 Structure” section. There are then three cases based on the state and position of the missile.
Processing a missile requires three steps. First, if the missile has moved off of the screen (that is, its screen x coordinate is outside of the range 0-79 or its y coordinate is out of the range 0-24), then the missile should be erased from the screen, removed from the linked list, and its struct missile freed with mp1 free (see “Allocating and Freeing Memory”). Removing a missile from the list should be implemented as a separate function since you may need to perform this operation in more than one place in the code (possibly outside of the tasklet). In this document, we will refer to this function as mp1 missile remove, though you may name it whatever you chose.
Second, if the missile has reached its destination or is currently exploding, you must call missile explode with a pointertothemissile’sstruct missileasanargument.Themissileexplodefunction(providedtoyou)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 missile explode, 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 mp1 free. 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 “Text- Mode Video” section.
If any call made to missile explode 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 mp1 notify user 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, base pic and dead base pic 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 base alive 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.
The third thing your tasklet must do is to redraw the crosshairs. It may have been overwritten by a missile or by a city, and we want to ensure that it is always visible.
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 uses the cmd argument to determine which of the next five functions to jump to. The table below gives a brief summary of cmd values, the corresponding core function, and a brief descrip- tion of what that core function does. Each of the core functions are described in the section entitled “Core Functions.” Note that you must check this cmd value; if it is an invalid command, return -1.
cmd value 0
Core function
mp1 ioctl startgame mp1 ioctl addmissile mp1 ioctl movexhairs mp1 ioctl getstatus mp1 ioctl endgame
Description
starts the missile command game add a new missile
move the crosshairs
get the current game status
end the game
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.
(previous stack)
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 section “Jump Tables” below.
return address
command number
Core Functions
You must implement each of the following five functions in x86 assembly in the mp1.S file.
int mp1 ioctl startgame (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 mp1 ioctl addmissile (struct missile* user missile);
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 mp1 ioctl movexhairs (unsigned long xhair delta packed);
This function moves the crosshairs. The parameter is a 32-bit integer containing two signed 16-bit integers packed into its low and high words. The low 16 bits contain the amount by which the x component of the crosshair position should change, and the high 16 bits contain the amount by which the y component should change. This function should not 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 mp1 ioctl getstatus (unsigned long* user status);
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 status of the three cities into bits 16, 17, and 18. The missile explode function maintains the user’s current score in the mp1 score variable declared in mp1.S. If a city is currently alive, the corresponding bit should be a 1; if it has been destroyed, the bit should be 0. The missile explode function maintains this information in the base alive array, as described above. This function should return 0 if the copy to user space succeeds, and -1 if it fails.
int mp1 ioctl endgame (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, mp1 ioctl addmissile 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, mp1 missile remove 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 mp1 free.
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 fa21/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, clicktheStartbuttoninWindows,typeingit bash,thenclickonthesearchresultthatsaysGit 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 fa21/mp1
git clone fa21/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- vertall3filestotheiroriginalstateusingSVN(svn revert
• 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.
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.
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,1 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 develo
