Assignment 7: System Monitor with Interrupts

Written by Philip Levis, updated by Julie Zelenski

Due: Tuesday, March 07 at 5:00 pm

Goals

With all your hard work on the previous assignments, your Raspberry Pi can now read input from a keyboard and respond to your commands by drawing to a graphical console display. For the pièce de résistance you'll upgrade your keyboard driver so that you can type as fast as the wind without dropping characters.

Conceptually, this is about concurrency and preemption. Concurrency is when a program is able to do more than one thing at once. Preemption is when one task in a program can take control of the processor from another. Both concurrency and preemption are fundamental ideas to computer systems: they let web servers handle tens of thousands of clients and your GPU to draw beautiful graphics. In this assignment, you start from the ground up, handling the root of preemption in every computer system: interrupts.

In completing this assignment you will have:

• redesigned your PS/2 driver to use GPIO interrupts so it doesn't drop scancodes, and
• used an interrupt-safe data structure to correctly share data across regular and interrupt code.

The stretch goal is to achieve the complete system bonus which attests that you have:

• bundled the collection of modules you've written into a comprehensive library for implementing a bare-metal system on the Pi
• constructed a successful and complete system of your own top to bottom: your console running on your library

This work completes the transformation of your Raspberry Pi into a standalone computer, ready to be extended and improved in your final project. Way to go!

Get starter files

Do a git pull in your $CS107E repository to ensure the courseware files are up to date.

$ cd $CS107E
$ git pull

Now cd to your local mycode repo and pull in the assignment starter code:

$ cd ~/cs107e_home/mycode
$ git checkout dev
$ git pull --allow-unrelated-histories starter-code assign7-starter

In the assign7 directory, you will find these files:

• ps2.c: library module
  • The starter code contains an empty ps2.c file. Copy/paste your existing code from assign5/ps2.c to get your starting point.
• test_interrupts.c: test program with your unit tests
• interrupts_console_shell.c: application program that runs your shell, reading input from the PS/2 keyboard via interrupts and displaying output to the console. You will use this program unchanged.
• Makefile: rules to build interrupts_console_shell application (make run) and unit test program (make test)
• README.md: edit this text file to communicate with us about your submission
• the subdirectories mylib and template show how to build and use your libpi
  • mylib has symbolic links to your module source files and a Makefile to build libmypi.a
  • template is a sample application that builds on top of your libmypi.a

The make run target builds and runs the program interrupts_console_shell.bin. This program is used to test the integration of all modules in the complete system, now using interrupts. The make test target builds and run the test program test_interrputs.bin that does simple unit tests.

Take note of the assignment 7 Makefile! Unlike previous makefiles that used your code only for the modules specific to the current assignment, this makefile assumes that you are aiming for the complete system bonus and want to use all your own code. MY_MODULE_SOURCES is set to use your code for all modules. If you need to use our reference module in place of yours, edit the Makefile to remove the faulty module. After resolving the issue, add the module back to the list of MY_MODULE_SOURCES to build your complete system.

Overview

In assignment 5, you wrote a PS/2 device driver that reads scancodes by polling. The core task for this assignment is to rework the device driver to instead be interrupt-driven.

Start by copying your code from assign5/ps2.c and pasting it into the file assign7/ps2.c. This is your starting point. You won't be editing the version in the assign5 folder further, you will preserve it as is. All the edits you are making for this assignment are on the version in the assign7 folder.

Refresh yourself on the code you wrote for assignment 5. The keyboard module calls ps2_read to get a scancode. A call to ps2_read waits for the next scancode to arrive. "Waiting" is a tight loop that repeatedly calls gpio_read on the clock GPIO until it observes the level transition from high to low, i.e. falling edge. If your code isn't reading the GPIO at the moment the edge falls, it misses the event. Furthermore, the CPU spins just waiting for this event and can't do anything else while it does. The polling implementation both misses events and is extremely inefficient.

Read over the test code in the function test_read_delay in the starter file test_interrupts.c and try it out with your existing modules. You should see that your code drops any keys typed while the test program is paused inside timer_delay. This is the expected behavior from the polling implementation.

Interrupts solve this problem. Instead of running a spin loop waiting for a falling edge, your code can configure the hardware to issue an interrupt when it sees a falling edge. The interrupt handler jumps in to immediately read the data when it is available, never missing a bit.

1) Configuring PS/2 interrupts

For a PS/2 device, the event you want to be notified of is the falling edge on the clock line, and the handler function that processes the event will read from the data line.

In your ps2 module, implement a handler function that responds to the falling edge event on the clock GPIO by reading a bit from the data GPIO. The handler function will need to know which PS/2 device received the event; we recommend that you use the handler's aux_data pointer to pass the ps2_device_t *. For now, your handler can just announce the interrupt with a quick uart_putchar('+'). (if you want to get fancy you could uart_putchar('0') or '1' based on the data bit read, but stay away from complex printf; there isn't much time). Be sure that the handler also clears the event or it will endlessly re-trigger.

Change the PS/2 module to configure GPIO interrupts and call your handler function. Configuring the gpio interrupts is done when setting up a new PS/2 device; here are the steps to take in ps2_new:

• enable detection of falling edge events on the device's clock GPIO (see header gpio_extra.h)
• configure gpio_interrupts for the events (see header gpio_interrupts.h)
  • initialize gpio_interrupts module
  • register your handler function for gpio events on the device's clock GPIO
  • enable gpio interrupts

The remaining configuration steps are to initialize the top-level interrupts module and flip the global enable switch for all interrupts. (see header interrupts.h) These steps should be done in main of test_interrupts.c.

There are several steps to configuring interrupts; your work from lab7 may be helpful to review if you're missing a step or have them out of order. Some steps are handled in local context, others managed globally, i.e. GPIO interrupts are configured within the PS/2 module and the top-level interrupts are configured in the main program. This reflects the level at which the modules interact with the interrupt systems. Interacting with GPIO interrupts is localized within PS/2 module; this is mostly a private matter of the PS/2 module implementation. The top-level interrupts module is configured in the program main function. The top-level interrupts module acts globally and use must be coordinated across the entire program.

Use the function check_interrupts_received of test_interrupts.c to confirm that your handler is correctly configured and enabled. When you type a key, the handler should output a + for each bit in the scancode. How many + correspond to one key press?

Remember, interrupt code should be simple and fast. You want to be simple because debugging interrupts is so hard. You want it to be fast because you don't want to delay/miss the next interrupt. Calling a complex printf in your handler, for example, could cause you to miss clock edges: printing a single character takes almost 100 microseconds, which is the same length as a PS/2 clock pulse.

2) Gather a PS/2 scancode

The falling edge of PS/2 clock edge indicates that right now is the time to read a bit from the data line.

Your handler function will be called 11 times, once for each falling clock edge, and each time it is called, it reads a single bit from data GPIO. Because each call to the handler has its own stack frame, you won't be able to use a stack local variable to store the accumulated scancode from call to call. Instead you will use the ps2_device_t struct. Remember that the ps2_device_t * is passed as the aux_data argument to the handler function. You can additional fields to the ps2_device_t to store whatever information is needed to track the device state between calls to the handler function.

Your assign5 version of ps2_read gathered the 8 data bits into a scancode along with verifying the validity of the start, parity and stop bits. You now need to rework that code to fit within your handler function which reads a single bit at a time. If the handler detects a bit in error, discard any partial scancode and re-start on new start bit as you did previously.

Once your handler function can gather a scancode, you're ready to enqueue those scancodes for mainline code to retrieve.

Tip: polling versus interrupt Our reference version of the ps2 module supports both reading in polling mode and reading by interrupts; the mode is configurable via an internal switch. Your ps2 module does not support this. Rather than a switchable mode, you will have two distinct ps2 modules: the original assign5/ps2.c that reads via polling and the improved assign7/ps2.c that reads by interrupt. (You will not use assign5 version going forward; but the file is preserved in your assign5 directory for review/compare if needed).

3) Use ring buffer

Your handler function gathers the data bits one at a time and forms a scancode. The last task is to safely pass that scancode from the interrupt handler to mainline code. The ring buffer queue shown in lecture is just the tool for the job! (see ringbuffer.h)

Create a new ring buffer queue in ps2_new and add it to the ps_device_t struct. Once your handler function has gathered a complete scancode, add the scancode to the queue. Edit ps2_read to dequeue from the queue. The ps2_read function blocks (spins) until there is a scancode available in the queue, then dequeues and returns it. ps2_read always returns a scancode, either a saved scancode that was previously queued or waits for the next scancode to arrive in the queue.

You should now be able to run your same console shell application as in assignment 6, and all should work as before, except this time you never miss a key. The interrupt handler immediately enqueues each typed key for later processing by the console when ready.

You now have a fully operational console that uses the full power of your hardware! What you have running is not too far from an Apple II computer.

4) Need for speed? (just for fun)

Your new interrupt-driven keyboard driver won't drop a key unless someone can type > 170 characters in between calls to ps2_read: the ring buffer is 512 elements and most keys are 3 scancodes. Unless you're doing something really CPU-intensive, this is unlikely.

However a moderately fast typist can still enqueue a decent number of keys during a slow console redraw that makes for a longish wait as the console works through the backlog. This is the expected behavior: the console receives every character that is typed and painstakingly draws and responds to that input. But, … if you caught the optimization fever from performance exploration in lab7, we'd love to see what you can do to improve the refresh performance. A few ideas to consider:

• Inner loops are the first place to look for speed-up opportunities (e.g. hoisting out redundant work, streamlining operations, loop unrolling). With a million pixels on the line, cutting just 10 instructions per pixel totals to a full second of time saved.
• Cacheing is a technique used widely in computer science. The basic gist is that you save a result to re-use rather than having to repeatedly recompute/refetch.
  • As one example: each use of gl_draw_char calls font_get_glyph to re-extract the glyph from the font bitmap. If the gl module extracted the glyph on first use and saved it, using the cached version on subsequent draw operations avoids the repeated work.
• Vertical scroll is particularly painful because of the need to redraw the entire screen. Rather than redraw all the characters, you could copy the previously drawn pixels upward. Or … how about a framebuffer variant that simply adjusts the y_offset to get scrolling for "free" and defers paying the cost of a full redraw until hit virtual bottom?
• If you do the profiler extension, you can use it to identify the hot spots in your code, which points you to the places to focus your attention to get the most impact for your efforts!

Complete system bonus

Change to the mylib directory and use make to create the build result libmypi.a. This libmypi.a packages together your battle-tested code of library modules into a complete library to support a bare-metal system on the Pi. We will test the interrupt-driven graphical console shell application on your library and if all works correctly, you earn the full system bonus!

To be considered for the system bonus, libmypi.a must use your own code for all modules (no use of reference modules). We will not re-test your individual modules to the extent that they were tested when grading each assignment, but all functionality used by shell/console must work correctly. This means, for example, your printf must handle printing padded hexadecimal numbers (which are needed for peek), but could slip by with a minor bug in formatting a large negative value (since they are not used by the shell).

The full system bonus is a big reward for a big accomplishment! You have successfully built a complete computer system from the ground up, writing your own code at every step of the way. Congratulations!

The libmypi.a library is in a form ready to be easily incorporated into any future project. The subdirectory template contains a template project that demonstrates how to build an application using your libmypi.a. To start a new project, make a copy of the template folder, add your libmypi.a, and use make run to build and run. You can now program your Pi almost like an Arduino with this high-level library you have created.

Extensions

We have two proposed extensions. Choose one OR the other (you do not need to do both).

1) Profiler

One extension is to add a profile command to your shell. A profiler is a developer tool that tracks where in the code a program is spending its execution time.

If diagnosing how to improve in a slow program, your first task would be to observe the program and measure where it spends most of its time. Speeding up those sections of the code will have the greatest effect on the overall run time.

There is a simple and clever way to find a program's hot spots using a sampling strategy. Repeatedly interrupt the program and record a sample of where the pc is currently executing. The probability of observing a given value of pc is proportional to the time spent executing that instruction. The more often that an instruction is executed, the higher the likelihood it will be observed when sampling. After gathering enough samples, those instructions that rise to the top because of their high counts are the program's hot spots. You can construct a sampling profiler using what you know about linking, memory, and interrupts.

The implementation for the profile extension is added to assign5/shell.c. You do not need to preserve the original version or make an distinct copy, edit the one copy in place. Be sure that you commit these changes when submitting your extension.

Use our provided armtimer module and configure a countdown timer for an interval of ~500 microseconds. Set the timer event to generate interrupts and write a handler for it. (Refer to header file armtimer.h or sample code from the Interrupts lecture). Recall that the first argument to the interrupt handler is the pc of the instruction that was about to execute at the time of the interruption, so you have your sample right there!

The profiler maintains an array of counters, one for each instruction address in the text (code) section. There is a known address where the text section starts (what value is that again?), but to know the extent of the text, you will need to edit the linker map to mark the end. It may help to revisit lab4 for information on linker maps.

Open the memmap file and, patterning after how symbols are used to mark the bounds of the bss section, add a symbol to identify the location of end of the text section. If you know where the text section starts and where it ends, you can compute the correct amount of space needed to have a counter for each instruction in the text section. The profile will scan the counters to find the entries with the highest counts to identify the hot spots.

Add the command profile [on | off] to your shell commands to control the profiler. profile on should initialize (zero-out) all profile counts and start profiling. profile off should stop profiling and print a list of the 20 instructions with the highest counts. These high-count instructions are the program's hot spots.

The final touch for your profiler is to provide the function name that each high-count instruction belongs to. If you remember the name_of function you wrote for assignment 4, the compiler has embedded each function's name as a string of characters before its first instruction. You can find the function's name by walking backwards in memory from the instruction to find the "magic" byte that marks where name is stored.

For each high-count instruction, report the count of samples recorded for that instruction, the name of the function it belongs to, and the instruction offset within the function. The profiler results look something like this:

  Counts  |  Function    [pc]
-----------------------------
    2331  |  gl_draw_char+204 [0x8a9c]
    2327  |  gl_draw_char+232 [0x8ab8]
    2081  |  gl_draw_char+208 [0x8aa0]
    1559  |  gl_clear+44 [0x8760]
    1049  |  keyboard_read_next+20 [0xdcc4]
    ...

Cool, you now have a profiler! Run it on your console program and learn where your hot spots are. Tag the submission assign7-extension. In your assign7 README.md, include some of your sample profiler output and share with us what you learned from writing and using this neat tool.

2) PS/2 mouse and paint application

For this extension, you'll create PS/2 mouse driver module and use it to implement a simple paint application.

Got mouse? We keep a small stash of PS/2 mice in the Gates B02 lab room for those working on this extension. Please do not take the mice with you, leave in lab for all to use. Thank you! 🐁

Communicating with a PS/2 mouse is similar to a PS/2 keyboard. First read these specifications for the PS/2 mouse and PS/2 protocol (paying particular attention to the last section labeled "Host-to-Device Communication")

Start by extending your interrupt-driven ps2 module to support the new function ps2_write. This is the symmetric operation to ps2_read that sends a scancode packet from the Pi to the device. Read the PS/2 protocol specification for how to switch between communicating from device-to-host (e.g. ps2_read) to host-to-device (e.g ps2_write). A scancode packet consists of 11 bits (start, 8 data, parity, stop) and each bit is written to the data line after observing a falling edge on the clock line.

With ps2_write in place, you're ready to create a mouse driver! The mouse module layers on the ps2 module just as keyboard does, using ps2_read (and now ps2_write) to talk to the input device. Read the header file mouse.h for the mouse interface and documentation. Create a new file mouse.c and implement the two required functions (mouse_init and mouse_read_event).

To initialize the mouse, a specific sequence of scancodes must be exchanged. The sequence below resets the mouse and enables data reporting mode:

1. Write Reset scancode 0xFF to the mouse.
2. Read ACK scancode 0xFA response from the mouse.
3. Read BAT Successful 0xAA scancode from the mouse.
4. Read Device ID scancode from the mouse. (ignore)
5. Write Enable Data Reporting scancode 0xF4 to the mouse.
6. Read ACK scancode 0xFA from the mouse.

The mouse_read_event function calls ps2_read and converts scancodes into mouse events. Consult the PS/2 mouse specification for how to interpret the raw scancodes. Be careful about the 9-bit two's complement representation of distances.

Edit the mylib/Makefile to add mouse.c to the list of LIBPI_MODULE_SOURCES and rebuild your library libmypi.a. Your library now supports interfacing with a mouse, neat!

Make a copy of the template subdirectory and name the copy paint. Copy your library libmypi.a from mylib into the paint folder. Using your shiny new mouse driver, implement a simple paint application in paint/main.c. The paint application draws a blank canvas and then loops, reading mouse events and drawing on the screen in response.

It should be possible to:

• draw by holding down the left mouse button and dragging the mouse
• when not holding down the button, move some pointer/indicator around on the screen without disrupting what's previously been painted
• Watch this short clip of our paint application in action:

Other than that, the details of the UI are up to you. Describe in your assign7 README.md how to use your paint program and add tag assign7-extension. We can't wait to try it out!

Submit

The deliverables for assign7-submit are:

• A reworked ps2.c module that uses GPIO interrupts
• Completed versions of all your previous modules to be considered for system bonus. Review code for all modules and confirm the correct contents are committed in the final submission.
• Your tests in test_interrupts.c
• README.md (possibly empty)

Submit your finished code by commit, tag assign7-submit, push to remote, and ensure you have an open pull request. The steps to follow are given in the git workflow guide.

To confirm you're eligible for the complete system bonus, double-check that you are testing with all of your modules listed in MY_MODULE_SOURCES and that latest versions of your files are added and committed. If you are submitting the paint extension, be sure all of the needed files in your paint subdirectory are committed as well.

Grading

To grade this assignment, we will:

• Verify that your submission builds correctly, with no warnings. Warnings and/or build errors result in automatic deductions. Clean build always!
• Run automated tests that exercise the functionality of your interrupts-driven ps2 module.
• Review the tests you added to test_interrupts.c and evaluate them for thoughtfulness and completeness in coverage.
• Review your code and provide feedback on your design and style choices.
• Build the interrupts_console_shell application using all of your library modules and interactively test the complete system running with a PS/2 keyboard and HDMI monitor.
  • Our test will touch on the core features of the system to confirm all is working together in integration.
  • This coverage will be more of a "once over lightly" pass and less of the "explore every nook and cranny" unit tests we used when grading each assignment individually.

Course learning goals

Three cheers for YOU! 👏👏👏 This is your computer system, the one you built yourself from the ground up. Each line of code is there because you put it there, you know what it does, and why it is needed. We are in awe of the effort you put in to arrive here and hope you are as proud of your work as we are.

Reflecting on where you started, it has been an impressive journey. Take stock of the progress you have made on mastering these course learning goals:

✔︎ To understand how computers represent information, execute programs, and control peripherals

• Binary and hexadecimal number systems, machine encoding of instructions
• Memory layout, pointers, arrays, structs
• ARM assembly, use of registers, instruction control flow
• Runtime use of stack and heap memory
• Memory-mapped I/O to access to peripherals, device drivers (keyboard, display)
• Interrupts, simple multi-processing

✔︎ To master command-line programming tools and the C programming language

• Build tools (assembler, compiler, linker, make, bootloader)
• Implementation of standard C library functions (strings, printf, malloc, graphics)
• Strategies for testing and debugging code, using gdb
• Establishing a productive and effective programming workflow

Bring these skills into the final project, mix with your creativity and initiative, and something fabulous will surely result. We're looking forward to it!