ECE391: Computer Systems Engineering Spring 2022 Machine Problem 1 Due: in Gitlab repository by 6 PM CST Monday 7 February
Text-Mode Fish Animation
Demo on Monday 7 February, 6 PM CST: Last name starts with A-L
Demo on Tuesday 8 February, 6 PM CST: Last name starts with M-Z
Copyright By PowCoder代写 加微信 powcoder
Note: Must commit to the master branch in your provided GitLab repository by assignment deadline, NOT YOUR DEMO TIME. Queue will open up 15 minutes before start time on demo days. Demos will last until there are no more students on the queue.
In this machine problem, you will modify the Linux real-time clock (RTC) driver to toggle characters on the text-mode video console from one ASCII character to another, with a user-settable toggle rate. This will serve a dual purpose: first, it will be an exercise in writing x86 assembly, allowing you to gain experience with the x86 ISA. Second, it will provide an introduction into how drivers accomplish tasks inside the Linux kernel.
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.
MP1 Assignment
You will add four new ioctls to the existing RTC driver, as well as a tasklet that will update the text-mode video screen on every RTC interrupt.
Your code will reside in mp1.S, a GNU-style assembly file. Assembly files with a capital-S extension (.S) are prepro- cessed using the standard C preprocessor before being assembled, so things like #include and #define are OK to use. Your code must be implemented using GNU x86 assembly.
Please be aware that the preprocessor will catch anything that looks like a directive and may prevent your code from assembling. Use of # to denote comments is problematic, especially for those who like to begin comments with “if.” The assembler accepts both C-style /* comments */ and C++-style // comments.
MP1 Data Structure
The main structure you will be working with is mp1 blink struct. struct mp1_blink_struct {
unsigned short
unsigned short
unsigned short
unsigned short
unsigned short
struct mp1_blink_struct
on_length;
off_length;
countdown;
/* Linear offset on text-mode buffer */ /* Char to put during “on” period */ /* Char to put during “off” period */ /* Length of on period
* in number of RTC interrupts */
/* Length of off period */
/* Number of RTC interrupts left in period */ /* Status word (on=1/off=0) */
/* pointer to next item in linked list */
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.
To implement characters “blinking” on the text-mode video console, a linked list will be created by your modified RTC driver that will allow any location on the text-mode video console to be toggling characters from off char to
on char and back, with toggle rates determined by on length and off length. A pointer to the first element in the linked list (the head of the list) is defined in the mp1.S file as a global variable, mp1 list head. mp1 list head is initialized to NULL (the value it holds is zero) to indicate that there are currently no blinking locations on the screen. The tail element of the list will have its next field equal to NULL to indicate that it is the last element. A diagram of this singly-linked list layout for a three-item list is shown on the following page. Example memory addresses of structures and variables are shown in parentheses.
mp1_list_head (0x804a1b0)
(0x804b008) (0x804b020) (0x804b038)
MP1 Tasklet
next = 0x804b020
next = 0x804b038
The first function you need to write is called mp1 rtc tasklet. The tasklet must update the state of the game. Its C prototype is:
void mp1 rtc tasklet (unsigned long);
Every time an RTC interrupt is generated, mp1 rtc tasklet will be called. Your tasklet will walk down the mp1 list head list, examining each mp1 blink struct structure. The function first decrements the countdown field of the structure. If the countdown field has reached zero after the decrement, the tasklet will examine the status field. If this field is equal to 1, that location currently has the on char character; if this field is 0, that loca- tion currently has the off char character. The tasklet should put the opposite character (i.e. interchange the status between on/off) out to video memory with a call to mp1 poke. For information on how to draw to the screen, see the “Text-Mode Video” section. Finally, the tasklet updates the countdown field by copying the value from the opposite length field to countdown. For example, if the character was currently off and you just turned it on, copy on length to countdown. In this way, the toggle rate for each character is controlled by the length fields. The tasklet then must move on to the next list element. The function returns when it reaches the end of the list.
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 four 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.
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.
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
next = 0x0
Core function
Description
mp1 ioctl add mp1 ioctl remove mp1 ioctl find mp1 ioctl sync
add a blinking location
remove a blinking location
get information about a location
synchronize a new blink location with an existing one Any value other than 0-3 is an error. Return -1.
the section “Jump Tables” below.
Core Functions
(previous stack)
You must implement each of the following four functions in assembly in the mp1.S file.
Note: A common task across these four ioctls is searching a linked list for a specific element that matches a particular location. You must implement a separate function that performs a linked list search, and call this function from the mp1 ioctl remove, mp1 ioctl find, and mp1 ioctl sync core functions. Designing the interface to this function (in other words, what parameter(s) is/are passed to it, what value(s) is/are returned from it, and so forth) is up to you.
int mp1 ioctl add(unsigned long arg)
The add ioctl takes as its argument a user-level pointer to a mp1 blink struct structure. First, dynamically allocate memory using the mp1 malloc function to store a copy of the structure. Copy the entire mp1 blink struct from the user-space structure to the newly-allocated memory (use mp1 copy from user). Then set the countdown field to be equal to the on length field, and set the status field to 1. Then insert this structure at the head of the linked list using the mp1 list head pointer. Finally, make a call to mp1 poke with the correct register parameters to immediately display the character on the text-mode video screen. This effectively turns the location “on.” After countdown RTC interrupts have elapsed, your mp1 rtc tasklet will turn the location “off.” This function should return 0 if a successful add was performed.
Your function must handle errors. If there is a memory allocation error (in which case mp1 malloc returns NULL), return -1. Remember the semantics of mp1 copy from user. If it could not copy all the bytes requested, it will return the number of bytes it was not able to copy. If this function returns anything other than 0, the copy has failed, and the function should return -1. If the location is outside the valid range of 0 to 80*25-1, this function should return -1. Finally, your error handling must prevent memory leaks. If you have allocated any memory using mp1 malloc, and you find that there is an error condition, you must free the memory using mp1 free.
int mp1 ioctl remove(unsigned long arg)
The remove ioctl takes an integer location as its parameter. Traverse the mp1 list head list, looking for an element whose location field matches the argument given to this function. If there is such an element, remove it from the linked list and free its memory with a call to mp1 free, and return 0. If there is no element whose location matches, return -1.
int mp1 ioctl find(unsigned long arg)
The find ioctl takes a pointer to a mp1 blink struct, like add. The only parameter it is concerned with as an input is the location parameter, but you must validate that the pointer refers to a valid structure before reading from the struc- ture. After extracting the location parameter from the user-level structure, search the mp1 list head list for an ele- ment that matches the location. Then copy the entire element, which is a mp1 blink struct, to the user-level structure pointed to by the parameter that was passed in (use mp1 copy to user). In this way it uses the parameter as both an input and an output. If there is no matching location in the list, return -1, otherwise return 0. Similar error conditions apply to this function as in the previous two.
int mp1 ioctl sync(unsigned long arg)
The sync ioctl’s unsigned long argument is really two two-byte unsigned short integers, packed into one four-byte argument. The first integer is stored in the upper 16 bits of arg, and the second integer is stored in the lower 16 bits. You must extract these two integers from the single argument.
The sync ioctl synchronizes two existing locations on the screen. The first integer represents the location of the first blinking character, and the second integer represents the location of the second blinking character that will become
return address
command number
synchronized with the first. Search the mp1 list head list, looking for elements with locations that match the two integers, respectively. Then copy the timing information (the on length, off length, countdown, and status fields) from the first element to the second element. After copying these fields, call mp1 poke to immediately update the display using the correct character (that is, either the on char or the off char, depending on status) to the screen for the second location. This function should return 0 on success, and -1 on failure. Similar failure cases apply.
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 add 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 ioctl 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. Updates in the other calls can not lead to major problems.
Suggested Order of Writing Functions
Below is our suggested order of writing functions. If you write the functions in this order, you can test them as you go along and the expected output should be what is described. This way, you can have some confidence in the portions of code you write instead of writing everything all at once and then testing it only to find out something does not work and you have to look through every single line of every single function to track the bug. Feel free to deviate from this list if it is more convenient. And of course, do write your own test cases that individually test the functions you have written (formally called unit testing).
1. IOCTL dispatcher – There won’t be any output when this is finished. This is just to set up the calls to the core functions.
2. ADD – An ASCII picture of a fish should appear if this is working correctly
3. Tasklet – The ASCII fish should blink between the two frames
4. FIND/SYNC – An I/M should appear after a few seconds and the “I/M” blinks should sync up with the rest of the fish background after some time.
5. REMOVE – After the “I/M” have synced with the rest of the fish background, the “M” will be removed and so the blinking will stop and the “I” will be left over
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 sp22/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.
• TouseGitonalabcomputer,you’llhavetouseGitBashonWindows,nottheVM.Youarefreetodownload 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
• Switchthepathingit-bashintoyourZ:drivebyrunningthecommand: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 sp22/mp1
git clone sp22/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
• 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 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 h
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com