ECE391: Computer Systems Engineering Fall 2019Machine Problem 1 Due: Monday 16 September at 6:00 PMLife or DeathPlease 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 froman aggressive virus by finding a sequence of DNA bases that enables vaccination against the virus. Your code mustbe written in x86 assembly, and will operate as extension to the Linux real-time clock (RTC) driver. This assignmentprovides substantial experience with the x86 ISA and an introduction to how drivers accomplish tasks inside the Linuxkernel. 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-modevideo. 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. Thematerial described in these background sections will be covered in lecture in the next few weeks, but it may be helpfulto read these sections to familiarize yourself with the context of your code in this MP.Life or Death, the GameIn the game, a virus has infected the human population and is spreading rapidly. Your job is to identify a 5-baseDNA sequence that can be used to generate a vaccine against the virus. Each base can take one of four possiblevalues: A(denine), C(ytosine), G(uanine), or T(hymine). The virus spreads in real time on the screen based on a slightmodification to Conway’s Game of Life. The more of the virus is on the screen, the more rapidly the human populationdecreases. 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 tothe sequence of the virus, the more virus cells are wiped out by vaccination. However, being close is not necessarily agood thing—the closer your sequence is to the correct sequence, the more likely that the virus will mutate and becomemore aggressive as a result of your vaccination attempt. You also gain hints as to which bases are correct or incorrectby 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, whichimplements the rest of the game. You must write a tasklet (see the section “Tasklets”, below) to execute in response toeach interrupt generated by the RTC (see “RTC Overview”) and update the game board in real-time. The game boardand statistics reside inside the RTC driver in the kernel, so you must also write five ioctl’s (see “Ioctl Functions”) toprovide the necessary interface between the kernel-space components of the game and the user-space components.MP1 Data StructureThe game board is a dynamically-allocated 20 × 80 array (20 rows, 80 columns) of unsigned characters. The gameuses 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 thestruct 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 providedversion 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 TaskletThe first function you need to write is called mp1 rtc tasklet. The tasklet must update the game boards and drawthe 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 shouldbe 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 frommp1 rtc tasklet.Begin by checking the value of current board. If it is 0, your tasklet should return immediately. Otherwise, performthe five steps below.First, your tasklet must use the current board to update the next board. For every cell in the current board that isnot on any of the four boundaries, determine whether the corresponding cell in the next board should be live or deadby applying a set of rules slightly modified from Conway’s Game of Life. These rules have been implemented for youusing 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 (everycell 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 runningtotal of live cells in next board. After calculating all cells in next board, multiply the total number of live cellsby 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 letpopulation 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 givento you. You may design the interface to this function however you like, but write the screen-drawing code there, thencall the function from your tasklet. See the section entitled “Text-Mode Video” for support functions, and note thatCELL LIVE and CELL DEAD character constants have been provided to you in mp1.S, but you may change them asyou like so long as the virus is visible in your implementation. The board data are organized in the same order as thescreen data: each board consists of an array of 20 rows of arrays of 80 columns of unsigned char (bytes). The firstbyte of the board should be mapped to the upper left corner of the screen, the columns should map to columns on thescreen, 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 IoctlsThe 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. Thetable on the next page gives a brief summary of cmd values, the corresponding core function, and a brief description ofwhat that core function does. Each of the core functions are described in the section entitled “Core Functions.” Notethat mp1 ioctl must check the cmd value and, if cmd is invalid, return -1.3cmd value Core function Description0 mp1 ioctl startgame start the life or death game1 mp1 ioctl endgame end the game2 mp1 ioctl keystroke handles guess modification keystrokes3 mp1 ioctl getstatus get the current game status4 mp1 ioctl vaccinate purge virus and increase aggressionother – Any value other than 0-4 is an error. Return -1.The m
ethod used to jump to one of the core functions is to use assembly linkage without modifying the stack. Apicture of the stack at the beginning of mp1 ioctl is shown below.return addressargcommand number(previous stack)ESPEach 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 withoutmodifying the stack. The arg parameter will already be the first parameter on the stack, ready to be used by the corefunction. In this way, it will appear to the core functions as if they were called directly from the RTC driver using thestandard C calling convention without the use of this assembly linkage. Your mp1 ioctl must use a jump table—seethe “Jump Tables” section for more detail.Support FunctionsTo 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 thesefunctions 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 setusing the seed generator function, after which the generate function can be used to generate unsigned 32-bitrandom numbers.The last function, init virus, places two blobs of virus into a board randomly. Your code must call init virusafter allocating and initializing the game boards, as mentioned in the next section. The function returns the number oflive virus cells placed into the board.Core FunctionsYou must implement each of the following five functions in x86 assembly in the mp1.S file. Remember that youmay 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 thevariables declared in mp1.S. The parameter passed in seed must be used to seed the random number generator bypassing the argument to the seed generator function. The two game boards should be dynamically allocated usingmp1 malloc. Refer to the “Allocating and Freeing Memory” section for information on dynamic allocation. If eitherallocation fails, be sure to free any allocated memory (from the first allocation) and leave the two board pointers setto 0. After allocating the boards, fill them both with 0 bytes, then call init virus on the current board. The returnvalue from init virus is the initial value for infection. The aggression value should initially be set to 80, andpopulation, which is measured in thousands of humans, should initially be 8,000,000. The function should return -1if 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 bothgame boards and set the two pointers (current board and next board) back to 0. The function should then return 0for 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 structureon the stack for this purpose (use the constants KA STACK and KA SIZE in mp1.c). Read the section entitled, “MovingData to/from the Kernel” for information on copying memory. If the copy fails, the function should return -1. Thedirection field specifies the direction of the keystroke: 0 for left, 1 for down, 2 for right, and 3 for up. If left/right hasbeen pressed, the function should erase the current selector (a string is provided to you in mp1.S), change the selectorvalue appropriately (cyclically around the five possible values from 0 to 4), and redraw the selector using a secondprovided string. The selector image starts at screen location (14 + 10S, 22), where S is the selector position. Be sureto write the new selector position back into the kernel’s copy of the keystroke args. The up and down directionschange the selected base. Each base value ranges from 0 to 3. The up button increases the value (cyclically), while thedown button decreases it. The resulting base must appear in the corresponding hints, which are mapped as a bit vectorfor 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 positionis found. Again, remember to write the final value back into the kernel’s keystroke args structure. Then draw thebase to the screen at position (18 + 10S, 22), where S is again the selector position (a string containing the bases inorder has been provided for your use in mp1.S). Finally, regardless of the direction of the keystroke, the function mustcopy the modified keystroke args structure from the kernel back into user space (at the same location given by theargument). 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 functionmust copy these values. We suggest that you allocate space for a structure on the kernel stack (use the constantGS SIZE in mp1.c), fill in the values, then use mp1 copy to user to copy the information to the address passed. Ifthe 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 vaccinationeliminates each live cell in the virus and increases the virus’ aggression level. The parameter packed args is a32-bit integer containing two unsigned 16-bit integers packed into its low and high words. The low 16 bits containthe percentage chance that a live cell in the current board should be killed (set to 0). For each cell in the board, yourcode must call the generate function to generate a 32-bit unsigned random number, calculate the remainder of thatnumber 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 atwhich the virus expands. You may ignore the possibility of overflow. This function should always return 0.Synchronization ConstraintsThe code (both user-level and kernel) for MP1 prevents the tasklet from executing in the middle of any of the ioctlson a uniprocessor.1 However, interrupts must be turned on for dynamic allocation and memory copies. Thus any callmade to mp1 malloc, mp1 free, mp1 copy from user, or mp1 copy to user can be interrupted by execution ofthe tasklet. Your implementation must ensure that the variables are in a state that is safe for the tasklet before callingany 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 andthat all other variables are also initialized before modifying either of the board variables. The board variables shouldonly 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 aboutpossible interleavings).5Similarly, in mp1 ioctl endgame, your code should read the two board pointers into registers, overwrite the variableswith 0, and only then call mp1 free on the boards.The other functions shouldn’t have proble
ms if implemented as described in the “Core Functions” section.Getting StartedBe sure that your development environment is set up from MP0. In particular, have the base Linux kernel compiledand 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 athttps://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.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 downloadother 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 inputgit 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 willprompt you for your NETID and AD password):git clone https://gitlab.engr.illinois.edu/ece391 fa19/mp1 .git mp1If 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 mp1In your devel machine:• Change directory to your MP1 working directory (cd /workdir/mp1). In that directory, you should find a filecalled mp1.diff. Copy the file to your Linux kernel directory withcp 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 themp1.diff patch usingcat mp1.diff | patch -p1The last argument contains a digit 1, not the lowercase letter L. This command prints the contents of mp1.diffto stdout, then pipes stdout to the patch program, which applies the patch to the Linux source. You shouldsee that the patch modified three files, drivers/char/Makefile, drivers/char/rtc.c, andinclude/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 applythe 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 outyour code take a long time. If during handin, we find the whole kernel source or the build directoryin your repository, you will lose points. We have added a .gitignore file to your initial repository. This filecontains all the Git ignore rules that tells Git to not commit the specified file types. The Linux source and kernelbuild directory are one such example of files that are ignored. Try and explore the .gitignore file to see whatother 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 accidentalloss. Preventable losses due to unfortunate events, including disk loss, will not be met with sympathy.6TestingDue 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 into 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,2SEGV, to the program. The program then terminates harmlessly with a “Segmentation fault” error. However, if thissame 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 virtualTCP connection, with one running the test kernel and the other running a debugger. In user space, all that’s necessaryis 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 additionalioctls and tasklet. This test harness compiles and runs your code as a user-level program, allowing for a much fasterdevelopment cycle, as well as protecting your test machine from crashing. Using the user-level test harness, you caniron out most of the bugs in your code from user space before integrating them into the kernel’s RTC driver. Thefunctionality 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 toensure 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 priorto 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 everyMP, and it will be up to you to design and implement effective testing methods for your code. We encourage you tolook over how the user-level test harness works for this MP, as its design may be of use to you in future MPs. Thistest harness is fully functional, and uses some advanced programming techniques to achieve a complete simulationof 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 aswell.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. Debuggingthe kernel code will be difficult. Use the disas (disassemble) command on mp1 rtc tasklet or mp1 ioctl to seethe start of your code (feel free to add more globally visible symbols), then use explicit addresses to see the rest ofit. Be sure to start any disassembly with the starting byte of an instruction rather than an address in the middle ofan instruction. With non-function symbols (such as those in your assembly code), and with addresses, you need anasterisk 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 codefinishes (correctly or otherwise), pressing the Enter key will usually return the display to normal. Note also thatgdb will return the display to its usual location, after which you will not be able to see any of the animation (whiledebugging).Note: When running the user test under gdb, the debugger stops your program whenever a signal (such as SIGUSR1or SIGALRM) occurs. To turn off this behavior and make it easier to debug your program, type the following com-mands in gdb:handle SIGUSR1 noprinthandle SIGALRM noprint2Think 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 yourchanges to the MP1 sources.• Type cp /workdir/mp1/mp1.S /workdir/s
ource/linux-2.6.22.5/drivers/char to copy yourmp1.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 makeclean 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 KernelVirtual memory allows each user-level program to have the illusion of its own memory address space, separate fromany other user-level program and also separate from the kernel. This affords each program a level of protection, suchthat 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 systemcall) a translation is needed so that the kernel can correctly reference the user-level memory address being passedto 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 inasm-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 youfamiliar with it. These functions take two pointers to memory areas, or buffers, to and from, and a length n. Eachfunction copies n bytes from the from buffer to the to buffer. As can be inferred from their names, mp1 copy to usercopies data from a kernel buffer to a user-level buffer, and mp1 copy from user copies data from a user-level bufferto the kernel. All user- to kernel- address translations are taken care of by these functions. Each of these functionsreturns the number of bytes that could not be copied, which should be 0. Bad user-level pointers can cause returnvalues greater than zero. For example, if you pass a NULL pointer in as the user-level parameter to one of thesefunctions (such as the to parameter in mp1 copy to user), it checks the pointer and memory area, sees that it pointsto 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 takesan “arg” parameter, so you will need to look at the documentation for each ioctl to figure out which ones are actuallypointers to user-level structures.One final important note: When copying data to a buffer in the kernel, you should not use statically-allocated globalbuffers. In multiprocessor systems, for example, multiple calls to your ioctl functions may be going on at the sametime. Using a statically-allocated storage area, like a global variable, is a bad idea because the separate calls to theioctl would be contending for using this same storage area. You should use either local variables on the stack ordynamically-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 MemoryUser-level C programs make use of the malloc() and free() C library functions to allocate memory needed forstoring 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 thememory allocation services provided there. To abstract the details away (for now), the MP1 distribution contains twomemory 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 backto the system. It does not return anything.Text-Mode VideoEach character on the text display comprises two bytes in memory. The low byte contains the ASCII value for thecharacter to be display. The high byte is an attribute byte, which holds information about the color of that particularcharacter 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 eachsuccessive 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 atrow 12, column 15 on the screen, you first need to calculate the row offset: row 12 × 80 characters per row × 2 bytesper character = 1920. Then, add the column offset: column 15 × 2 bytes per character = 30. So, row 12 column 15 onthe 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 isnot a constant, so writing to video memory is somewhat more complicated than using a mov instruction. To simplifythings for this MP, a function has been defined called mp1 poke. This function, defined in assembly in mp1.S, takescare 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 writemp1 poke then finds the correct starting address in memory and writes the character in CL to the location specified byEAX.Note: For mp1 poke, EDX is a caller-saved register (in other words, mp1 poke clobbers EDX). If you need to preservethe 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 thevalue back into EDX with popl %edx. All other registers are callee-saved (that is, mp1 poke preserves their values).9Jump TablesYou must use a jump table to perform the “dispatching” operation in mp1 ioctl. A jump table is a table in memorycontaining 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 ofeach function. Let’s say you have three functions in an assembly (.S) file, with labels function0, function1, andfunction2 as the names of each. You can define a jump table as follows:function0:# function 0 bodyfunction1:# function 1 bodyfunction2:# function 2 bodyjump_table:.long function0, function1, function2The jump table provides an easy way to access those three functions. If you view the jump table as a C-style array ofpointers: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 ins
ide the brackets is the “index” into thejump table.In this MP, the cmd parameter should serve as the index into the jump table, and you should be able to easily jump toeach of the five core functions by creating a table similar to that shown above.Linux Device Driver OverviewThe 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 withthe 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 isavailable for reading or writing). In addition, most device files support the ioctl operation. ioctl is short for “I/Ocontrol,” and this operation is used to perform miscellaneous control and status actions that do not easily fall into oneof the more standard file operations—things that you wouldn’t do to normal disk files. A good example of an ioctlis setting the frequency or rate of interrupts generated by the real-time clock. ioctls are discussed in more depthlater in this handout. It is also important to note that drivers need not support all these operations; they may choose tosupport only those necessary to make the device useful.10RTC OverviewA computer’s real-time clock can generate interrupts at a settable frequency. Real programs running on Linux canmake use of this device to perform timing-critical functionality. For example, a Tetris-style video game may need toupdate the positions of the falling blocks every 500 milliseconds (ms). Using the RTC, the game might set up the RTCto generate interrupts every 500 ms. Using the standard file operations above, the game can then know exactly when500 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. TheRTC driver uses the open and close operations as initialization and cleanup mechanisms for certain internal datastructures and setup routines. Once open’ed, four bytes of data become available to be read from /dev/rtc on everyRTC interrupt. Programs can use the read or poll file operations to wait for these four bytes of data to becomeavailable, thus effectively waiting for the next RTC interrupt to be generated. The ioctl operation handles manyother 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 outsideworld via their device file and the standard set of file operations described above. The internals of actually managingthe device itself are left to the driver, and are not visible to normal programs. For example, in the RTC driver, noprogram is able to directly gain control of the RTC, manage its interrupts, and so forth. Changing the frequency isaccomplished via an ioctl, and determining when an interrupt has been generated is done by waiting for the fourbytes of data to become available to be read using read or poll.Ioctl FunctionsAn 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 issimply a number used by a program to reference a particular file that the program has opened. The program thenpasses this file descriptor to other functions like ioctl, indicating that it is /dev/rtc that the program wishes tooperate upon.The IOCTL COMMAND parameter is the particular ioctl operation to be performed on the device. It is shown in capsbecause all ioctl operations are defined as constants in the header file for each device driver. All that is needed for aprogram 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 apointer to a more complex structure used by the ioctl. The MP1 testing code passes pointers to special structuresthat contain all the data necessary for your RTC driver to perform the new ioctls described below.TaskletsInterrupt handlers themselves should be as short as possible to allow the operating system to perform other time-criticaltasks. Remember, when an interrupt occurs, control is immediately handed to the operating system so it can servicethe device. All other tasks are blocked while the interrupt handler is executing. A tasklet is a way for an interrupthandler to defer work until after the kernel has finished processing time-critical tasks and is about to return to a userprogram. Normally, the interrupt handler does urgent work with the device, and then schedules a tasklet to run laterto do the heavier I/O or computation that takes much longer. The operating system can enable all interrupts while thetasklet is executing. The main reason for deferring this sort of work is to allow other interrupts to occur while thisnon-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 isabout to return from the interrupt, it calls your tasklet, which then can update the text-mode video screen, yet allowother interrupts to occur.11Coding Style and DesignIn 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, wewon’t nitpick over small things such as spaces, blank lines, or camel case, nor will we enforce any rigorous codingguidelines. However, we still do have a basic standard that we expect you to adhere to and will be enforced throughgrading. 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.• 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 commentsto explain why, not what.HandinHandin will consist of a demonstration in the 391 Lab. During the demo, a TA will check the functionality of yourMP, 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 pushto your repositories.• You are free to develop your own system of code organization, but we will STRICTLY use only the masterbranch for grading, and will only make use of your mp1.S file.A Final Note on Testing: Sanity Checks and GDBWe have included two sanity checks in life-or-death.c to help ensure that you correctly check the return valueswhen 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 andmp1 ioctl getstatus implementations are handling these issues correctly (if, for example, they pass our sanitychecks), then you may want to remove the sanity checks from the code. Until then, we suggest entering the followingcommands to start utest in gdb:handle SIGUSR1 noprinthandle SIGSEGV noprintbreak life-or-death.c:407commands 1handle SIGSEGV stopcontinueendrun
