Project 3: Input, Output, and Sharing the Screen

At the end of Project 2, your operating system could hold several processes in memory and switch the CPU between them, whether they cooperated or not. But look at what your OS can actually do for you: it can print. It can show you text scrolling past on a serial UART connection or a printer.

In this project you will give your OS the ability to support more interactive computer use. We’ll approach this in two parts. First, you will extend your kernel to take a hardware interrupt when it receives data on the UART (e.g., because the user pressed a key), and hand that data to whichever process is waiting for it. This first step will get you to mid-1960s “time sharing”: a single, centralized and multiprogrammed computer can talk to many remote, dumb terminals that provide text-based input and output to the user’s processes on the computer. Second, you will add support for graphical output to the screen. Your kernel will ask the Raspberry Pi’s GPU for a framebuffer, a rectangle of memory that corresponds to what is on the screen, and let your processes draw pixels on it—and then, once several of them want to draw at once, give each process a private canvas of its own and combine them onto the screen itself. This gets us to where 1980s “personal computing” was, and to the genesis of the ancestors of popular modern OSes like Windows and macOS.

Putting these components together, you’ll get several programs on screen that seem to run at the same time. They are not actually running at the same time, of course. There is one CPU and one screen, and your kernel is time-slicing the CPU and partitioning the screen. This illusion of simultaneity is one that we take for granted on every computer we use.

Here’s an example of what the output to the screen might look like after you finish this project:

Learning objectives

After completing this project, you will be able to:

1. Explain how hardware interrupts let a kernel handle incoming data without waiting for it. Instead of spinning in a loop asking a device “do you have anything for me yet?”, your kernel will be interrupted by the device the instant data arrives, do the minimum work needed to not lose it, and go back to whatever it was doing.
2. Explain that an input device is a shared resource, and how a kernel routes input to the right process. There is one keyboard and several processes. Something must decide who gets each keystroke, and you will implement that decision.
3. Explain what it means for a process to “block”, and implement blocking. You will add a process state that is neither running nor ready-to-run but waiting for an event, and the sleep/wakeup mechanism that moves processes in and out of it. You will also discover why an OS with blocking needs an idle process.
4. Explain what a framebuffer is and how a two-dimensional image is stored in one-dimensional memory. You will understand that a screen takes pixels, not text, and that everything you have ever seen on a screen—including every letter of this sentence—is software turning something else into pixels.
5. Explain how an operating system partitions a shared output device between processes, and implement it: your kernel will give each process a private canvas to draw on, and decide where on the screen that canvas appears.
6. Explain why drawing on a screen that is being displayed simultaneously goes wrong, and how a compositor fixes it. You will see “tearing”, and fix it with double-buffering and by adding a compositor that never shows output in the middle of being redrawn. (In CS 1690/2670 you will then make it fast enough for real hardware.)
7. Explain why concurrent processes look simultaneous. You’ll see how one CPU, time-sliced a hundred times a second, and one screen, carved into four rectangles, can create the impression of an interactive desktop environment.

As a secondary objective, you will get more experience of writing a device driver against a vendor manual—this time for the PL011 UART’s receive path and the VideoCore GPU’s framebuffer.

CS 1670 vs. 1690/2670

As in Projects 1 and 2, all students share the same core project, but students in CS 1690/2670 complete extra work and run their code on real hardware.

Here is a summary of the quests you must complete for this project, based on which course you’re enrolled in:

Roadmap

The project has five quests, which build on each other. Quests 1–4 are required for everyone; quest 5 is for CS 1690/2670 only.

Read the Background section before you start: it gives you the conceptual foundation that all five quests build on. Each quest then opens with its own background material. Work through the quests in order; each one depends on the one before it.

Assignment Installation

You will keep working in the same private GitHub repository you used for Projects 1 and 2.

To pull in the new files for this project (new empty source files, the provided code, and an updated build system), run the following in your project directory:

git pull handout main

If this reports an error about an unknown remote, run:

git remote add handout git@github.com:csci1670/cs1670-f26-projects.git

and then git pull handout main again.

Code Structure

As in Projects 1 and 2, you write all the significant code yourself; we provide a build system, a skeleton of (mostly empty) files, and a few pieces that are pure plumbing. Here is what is new or changes in this project:

.
├── Makefile
├── kernel/
│   ├── ringbuf.c, ringbuf.h   Quest 1: a byte ring buffer
│   ├── drivers/
│   │   ├── uart.c, uart.h     Quest 1: add interrupt-driven receive
│   │   ├── mbox.c, mbox.h     Quest 3: GPU mailbox protocol (we provide this)
│   │   ├── fb.c, fb.h         Quests 3-4: the framebuffer driver
│   │   └── timer.c, timer.h   (yours, from Project 2; Quests 3--4 change it)
│   ├── console.c, console.h   Quests 1-2, 5: where keystrokes go
│   ├── compositor.c, .h       Quests 4-5: combine every process's canvas onto the screen
│   ├── interrupts.c, .h       Quests 1, 4: dispatch the UART interrupt; drive the compositor
│   ├── scheduling.c, .h       Quest 2: BLOCKED, block(), wakeup()
│   ├── proc.h                 Quests 2, 4-5: BLOCKED state; input buffer; window and canvas
│   ├── proc.c                 Quests 2, 4: initialize the new process fields
│   ├── klib.c, klib.h         Quests 2-4: a suggested home for the kernel-side
│   │                          trampoline functions. You have been installing these
│   │                          in kernel_main; moving them is optional, and we
│   │                          give you the (empty) files.
│   ├── init.c                 Quests 2-4: load the idle process; lay out the windows
│   ├── kernel.c               Quests 1-4: kernel_main initializes the new subsystems
│   ├── memlayout.h            Quests 2-4: new F_... slots, FB_INFO_BASE, bigger processes
│   ├── utils.c, utils.h       Quest 5: a faster memcpy
│   └── ...
└── user/
    ├── font8x8.h              Quest 3: an 8x8 bitmap font (we provide this)
    ├── lib/                   code compiled once and linked into every program
    │   ├── u_common.c, .h     Quests 2-4: user-side wrappers for the new kernel calls
    │   ├── u_fb.c, u_fb.h     Quests 3-5: your drawing library
    │   ├── u_string.c, .h     Quests 3, 5: strlen/strcmp/sprintf and friends
    │   └── u_vterm.c, .h      Quests 3, 5: a text console (your terminal's drawing half)
    └── ...                    you will also create idle.c (Quest 2), keytest.c
                               (Quest 2), logo.c and term.c (Quest 3) yourself

Building and running

We have added the commands make quemu-fb and make qemu-ws into the build system.

The targets that turn the display on now also need to connect your terminal to the emulated machine’s serial port, so that you can type into your OS. (Until now nothing read input, so it did not matter.)

$ make qemu        # serial console only, in your terminal (as in Projects 1 and 2)
$ make qemu-fb     # ...plus a graphical display window   (native macOS)
$ make qemu-ws     # ...plus a graphical display in your browser (container, or macOS)
$ make qemu-gdb    # serial only, paused, waiting for gdb
$ make qemu-fb-gdb # window display + paused, waiting for gdb
$ make qemu-ws-gdb # browser display + paused, waiting for gdb
$ make clean

You met make qemu-fb and make qemu-ws back in Project 0, where you used them to run our demo OS and change its background color. Go back and re-read those instructions now if you don’t remember which one is right for your environment—you will be using it constantly for the second half of this project.

Remember that to quit QEMU you type Ctrl-a then x, and that make kill gets rid of stray QEMU instances.

void uart_send(char c) {
  while (/* the transmit FIFO is full */) {
    // spin
  }
  /* write the byte */
}

0xAABBGGRR
  AA       - unused ("alpha") (1 byte)
    BB     - blue channel     (1 byte)
      GG   - green channel    (1 byte)
        RR - red channel      (1 byte)

pixels[y * pitch_in_pixels + x] = color;

Quest 1: Hear the keyboard

Files: kernel/drivers/uart.c, kernel/drivers/uart.h, kernel/drivers/timer.c, kernel/interrupts.c, kernel/interrupts.h, kernel/ringbuf.c, kernel/ringbuf.h, kernel/console.c, kernel/console.h, kernel/kernel.c.

Overview

In this quest you will make the UART device interrupt your kernel when a character arrives. You will:

1. Find the PL011’s interrupt-related registers in the manual, and the registers of a second interrupt controller you have not used before.
2. Enable the UART’s receive interrupt, route it to your CPU core, and extend your Project 2 interrupt dispatch to recognize it. As a first step, your handler will just print the character it received.
3. Replace the print with a ring buffer that the interrupt handler fills and that the rest of the kernel drains.

At the end of the quest, typing on your keyboard will produce characters inside your operating system.

Why are we doing this?

A network card, a disk controller, a mouse, and a keyboard all share this same exact pattern. The device raises an interrupt, a very short handler moves data out of the hardware into memory, and ordinary code deals with it later.

It is also the first time you will handle an interrupt that is not the timer. In Project 2 your dispatch code had exactly one case, so it did not really have to dispatch. Now it does, and your kernel will have to answer the question of which device just triggered an interrupt.

  key pressed on your keyboard
        |
        v
  [ PL011 UART ]  raises RXI, if unmasked in its IMSC register
        |
        v
  [ BCM2835 interrupt controller ]  forwards it, if enabled in ENABLE_IRQS_2
        |
        v
  [ ARM local interrupt controller ]  reports "a peripheral IRQ is pending"
        |                             in bit 8 of Core 0 interrupt source
        v
  [ your CPU core ]  takes an IRQ exception -> your vector table -> handle_interrupt()

What you need to do

Part A: find the registers

Part B: take the interrupt

Now wire it up.

1. In the device: unmask RXI in the UART’s IMSC register, at the end of uart_init(), after the UART itself is enabled.
2. In the interrupt controller: set the UART’s bit in ENABLE_IRQS_2. The natural home for this is your enable_interrupt_controller() function from Project 2, next to the line that enables the timer.
3. In your kernel: extend handle_interrupt() to recognize the new source, and write a uart_interrupt() function in your driver to handle it.

Your uart_interrupt() should drain the whole receive FIFO, not just one byte. Loop while RXFE is clear, reading a character each time. Then acknowledge the interrupt by writing to ICR.

    restore_context(context);   // the context you were passed; never returns

Part C: a ring buffer

Printing in the handler works, but it is the wrong design in two ways: it does slow work at interrupt time, and it throws the data away. What you actually want is to move the byte somewhere safe as fast as possible, and let ordinary kernel code deal with it later.

The “somewhere safe” is a ring buffer: a fixed-size array plus two pieces of bookkeeping that say where the unread data starts and how much of it there is. Writing wraps around to the beginning when it reaches the end. You may recall ring buffers from CS 300/1310’s “bounded buffer” example in the concurrency part of the course. This is where the same idea of a bounded buffer shows up again!

Ring buffers are a very common kernel data structure, but they’re finicky to implement and get right. Therefore, we allow you to generate the code with AI (see below).

Check your work

Run make qemu and type some characters. With the temporary drain from Part C step 4 in place, you should see something like:

Hello world from MyOS!
...
console: got 'h'
console: got 'e'
console: got 'l'
console: got 'l'
console: got 'o'

We recommend that you check these three things:

1. Type a burst. Paste a long line, or hold a key down. Every character should come through in order. If characters go missing, either you are not draining the FIFO in a loop, or your ring buffer’s wrap-around is wrong, or you are overflowing 512 bytes (which your dropped counter will tell you).
2. Type nothing for a while. Your other processes should keep running exactly as they did at the end of Project 2. If the machine has become sluggish or stopped, you are probably taking interrupts you aren’t acknowledging.
3. Look at it in gdb. Set a breakpoint on uart_interrupt, press a key, and inspect: p/x $sp (you are on some process’s stack), p input_buf, and your ring buffer’s indices. Confirm that the process that got interrupted is an arbitrary one—press keys a few times and watch your current-process pointer change.

Bonus Quests (Extra Credit)

Quest 2: Blocking, idling, and sharing the keyboard

Files: kernel/proc.h, kernel/proc.c, kernel/scheduling.c, kernel/scheduling.h, kernel/console.c, kernel/console.h, kernel/klib.c, kernel/kernel.c, kernel/limits.h, kernel/memlayout.h, kernel/init.c, user/lib/u_common.c, user/lib/u_common.h, user/idle.c, user/keytest.c, user/basic.c (provided).

Overview

Your kernel now collects keystrokes. In this quest you will give processes a way to read them, and—much more importantly—a way to wait for them without wasting the CPU. You will:

1. Expose a getc() function to user programs through the same trampoline mechanism you used for printf and yield, in a first version that spins.
2. Add a BLOCKED process state and a block()/wakeup() pair, and rewrite getc() to use them. Along the way you will meet a race condition that has cost real kernel developers a great deal of sleep.
3. Discover that your scheduler now panics, and fix it by adding an idle process.
4. Give every process its own input, and let the user choose which process the keyboard is talking to.

At the end of the quest you will be able to run a BASIC interpreter on your operating system, type programs into it, and switch between it and another program with a keystroke.

Why are we doing this?

Preemption, which you built in Project 2, lets a process be taken off the CPU against its will. Blocking lets a process step aside voluntarily and indefinitely when they have nothing to do until an event occurs. This allows a machine to have many processes, most of which are currently waiting for something.

It is also the last piece of the process state machine that you will need for a long time: RUNNING, RUNNABLE, and BLOCKED are the three main process states in an OS kernel.

  process calls getc()  ──►  kernel code runs on the process's stack
                                      │
                             no input available
                                      │
                                      ▼
                        mark the process BLOCKED, save its context,
                        run the scheduler  ──►  some other process runs
                                                        ⋮
                                              a key is pressed; the UART
                                              interrupt handler wakes the
                                              process
                                                        ⋮
                        restore_context()  ──►  execution resume *inside getc()*,
                                                loop around, find the byte,
                                                and return it to the caller

if (buffer_is_empty()) {
    block(&input_buf);
}
c = pop();

What you need to do

Part A: getc(), the wasteful version

In the next step, you will add functionality that allows your user programs to read input. We will build this in two steps, so that you can see a key problem before you fix it.

Run it. It works! But it’s rather expensive: waiting for a keystroke burns a lot of CPU time. You can see this in the QEMU window: the timer interrupt is firing, the scheduler is running, and every time it picks your keytest process it discovers there is no pending input and immediately gives up the CPU again.

Part B: real blocking

Now run it again. The process blocks once and is woken exactly once, when the key arrives! You can verify this with some debug prints or in GDB.

Part C: the process that does nothing

Now try running only the blocking programs. Remove primecheck from your init() and load just keytest (plus anything else that blocks). Press a key, let keytest block again, and watch:

PANIC: pick_next: no runnable process

This is correct behavior from your scheduler: every process is blocked and there is nothing to run. Your pick_next() is quite right to panic!

Part D: run a real program

You now have enough of an operating system to run something that was written for a real one. We provide user/basic.c: an implementation of Tiny BASIC, a descendant of the interpreter published in Dr. Dobb’s Journal in 1976 for machines with a few kilobytes of memory. It reads with getc() and writes with printf(), and it needs nothing else from your kernel.

10 PRINT "HELLO FROM MY OS"
20 GOTO 10
RUN

Part E: who gets the keystroke?

You can now run BASIC—but not BASIC and anything else that reads the keyboard, because two readers take turns stealing each other’s bytes. Every OS that runs more than one interactive program has had to solve this, and all solutions turn out to be variants of the same basic approach.

Check your work

With idle and basic loaded—and nothing that never blocks, such as counter—make qemu should give you a machine that:

1. Sits quietly when you are not typing. To test this, add a printf to your idle process (rate-limited—say, every 100,000 iterations). This should become the only thing that runs once everything else has blocked.
2. Responds instantly when you do type. If a program never reacts at all, you are not calling wakeup from the interrupt handler: a BLOCKED process is never picked again on its own, so it stays asleep forever. Note that up to one quantum of lag is normal and correct even when everything works—wakeup only marks the process RUNNABLE, and the handler then resumes whoever it interrupted. Making the keystroke act immediately would mean rescheduling from inside the interrupt handler, which is a different design than what we recommend above (though it can also be made to work).
3. Never panics with “no runnable process”. Try to make your OS panic: block everything you can, hold keys down, and paste large amounts of text.

Then load keytest alongside basic, and check that:

4. Focus switching works both ways. Press Shift+Tab until you are back where you started. Type into each program in turn and confirm that the characters go where you expect—and, crucially, that a line you half-typed into one program is still there when you come back to it.
5. Everything else still gets through. In keytest, an arrow key should still arrive as its three bytes, and the idle process should never be offered the focus.

We recommend two checks in gdb to see this is working correctly:

(gdb) break wakeup
(gdb) continue
# ...now press a key...
(gdb) p current_process->name   # who got interrupted? (whoever happened to be running)
(gdb) p processes[1].state       # the blocked process: BLOCKED before...
(gdb) finish
(gdb) p processes[1].state       # ...and RUNNABLE after

And, to see the shape of the whole thing:

(gdb) break block
(gdb) continue
(gdb) bt                        # a stack trace through getc, through the trampoline,
                                # and into the user program

That backtrace should show kernel code and user code interleaved on a single stack. This is because kernel code is invoked as library code from user programs here; this will stop being true in Project 4.

Bonus Quests (Extra Credit)

Quest 3: Pixels

Files: kernel/drivers/mbox.c, kernel/drivers/mbox.h, kernel/drivers/fb.c, kernel/drivers/fb.h, kernel/drivers/timer.c, kernel/drivers/timer.h, kernel/memlayout.h, kernel/kernel.c, kernel/klib.c, kernel/init.c, user/font8x8.h, user/lib/u_common.c, user/lib/u_common.h, user/lib/u_fb.c, user/lib/u_fb.h, user/lib/u_string.c, user/lib/u_string.h, user/lib/u_term.c, user/lib/u_term.h, user/logo.c, user/term.c, user/pong.c (provided).

git pull handout main

git remote add handout git@github.com:csci1670/cs1670-f26-projects.git

Overview

Time to make your OS visible. In this quest you will:

1. Ask the Raspberry Pi’s GPU for a framebuffer, using a message-passing protocol called the mailbox, and publish where it lives so that user programs can find it.
2. Write a user program that draws something—your OS’s logo—and see it on a screen.
3. Build a bitmap font renderer, discover that text is nothing but a small array of bits per character, and design a character of your own.
4. Write a text console—the code that turns a stream of characters into text on the screen—and a terminal application on top of it: an ordinary user program that reads your keyboard and draws what you type, with a few built-in commands.
5. Run a provided graphical program—a bouncing box—and watch it tear.

This is the longest quest in the project, but also the one with the most immediate feedback: from Part B onward, you can see whether your code works.

Why are we doing this?

A framebuffer is a simple, but powerful piece of output hardware and also the foundation of every display you use today. Beneath the window system, the GPU driver and the font engine on your laptop, there is a region of memory that just contains pixel values that make up what appears on screen. It works exactly like the framebuffer you are about to set up!

There is also a specific way of interacting with hardware in this quest that the UART did not teach you. The PL011 is a device you talk to by reading and writing registers. The Raspberry Pi’s VideoCore GPU is a different processor, running its own code, that you talk to by sending it messages. Increasingly much modern hardware works this way—GPUs, network cards, storage controllers, and the management processors inside server CPUs—and requires a shift from thinking about I/O as “poke a device register” to “compose a request and wait for a reply”.

  [0]  total size of the whole buffer, in bytes
  [1]  request/response code   (0 on the way out; `0x8000'0000` means success on the way back)
  [2]  tag identifier                           ─┐
  [3]  size of this tag's value buffer, in bytes │  one tag
  [4]  request/response code                     │
  [5..] the value words                         ─┘  (the GPU overwrites these with its response)
  ...  more tags ...
  [n]  0x00000000              terminates the list

What you need to do

Part A: ask for a framebuffer

We provide you with the transport layer for sending messages to the GPU in the form of mbox_call() in kernel/drivers/mbox.c. This function takes a 16-byte-aligned buffer, sends it on channel 8, and returns whether the GPU reported success. You write the part that builds the request and, more importantly, the part that makes the result usable by user programs.

The result of fb_init() is a handful of numbers—where the pixels are, how big the screen is, how many bytes a row takes—and every program that wants to draw needs all of them. You already have a mechanism for handing things to user programs: the fixed-address convention you built in Project 1 for printf. Do the same thing here, with a whole struct rather than a function pointer. Define a struct fb_info, agree on an address for it (FB_INFO_BASE in kernel/memlayout.h), have the kernel write it there at boot, and have user programs read it from there.

A reasonable struct fb_info for this quest:

struct fb_info {
  uint32  width;    // visible width in pixels
  uint32  height;   // visible height in pixels
  uint32  pitch;    // bytes from the start of one row to the start of the next
  uint32  pitch_w;  // the same thing in units of uint32 (pitch / 4), for convenience
  uint32  depth;    // bits per pixel
  uint32* pixels;   // where to draw. NULL means "no framebuffer"
};

// Must be 16-byte aligned: the low 4 bits of its address encode the channel.
static volatile uint32 __attribute__((aligned(16))) mbox_buf[36];  // 35 used

int fb_init(void) {
  mbox_buf[0]  = 35 * 4;               // total size of this buffer, in bytes
  mbox_buf[1]  = MBOX_REQUEST;         // 0 == "this is a request"

  mbox_buf[2]  = MBOX_TAG_SET_PHYS_WH; // set the display resolution
  mbox_buf[3]  = 8;                    // value buffer is 2 x uint32
  mbox_buf[4]  = 0;
  mbox_buf[5]  = FB_WIDTH;
  mbox_buf[6]  = FB_HEIGHT;

  mbox_buf[7]  = MBOX_TAG_SET_VIRT_WH; // set the in-memory buffer size
  mbox_buf[8]  = 8;                    // (identical, for now; Quest 4 changes this)
  mbox_buf[9]  = 0;
  mbox_buf[10] = FB_WIDTH;
  mbox_buf[11] = FB_HEIGHT;

  mbox_buf[12] = MBOX_TAG_SET_VIRT_OFFS;  // no panning
  mbox_buf[13] = 8;
  mbox_buf[14] = 0;
  mbox_buf[15] = 0;                    // x offset
  mbox_buf[16] = 0;                    // y offset

  mbox_buf[17] = MBOX_TAG_SET_DEPTH;
  mbox_buf[18] = 4;
  mbox_buf[19] = 0;
  mbox_buf[20] = FB_DEPTH;             // 32 bits per pixel

  mbox_buf[21] = MBOX_TAG_SET_PIX_ORDER;
  mbox_buf[22] = 4;
  mbox_buf[23] = 0;
  mbox_buf[24] = 1;                    // 1 == RGB

  mbox_buf[25] = MBOX_TAG_GET_FB;      // allocate the framebuffer
  mbox_buf[26] = 8;
  mbox_buf[27] = 0;
  mbox_buf[28] = 4096;                 // request 4 KiB alignment;
  mbox_buf[29] = 0;                    // ...the GPU replaces [28] with the bus address
                                       //    and [29] with the size in bytes

  mbox_buf[30] = MBOX_TAG_GET_PITCH;   // ask how many bytes a row takes
  mbox_buf[31] = 4;
  mbox_buf[32] = 0;
  mbox_buf[33] = 0;                    // ...the GPU replaces [33] with the pitch

  mbox_buf[34] = MBOX_TAG_LAST;        // end of tag list

  if (!mbox_call(mbox_buf)) {
    // TODO: zero the struct at FB_INFO_BASE (in particular, pixels = NULL)
    //       before returning, so that user programs can tell there is no display.
    return 0;   // the GPU said no
  }

  // TODO: mbox_buf[28] is a *bus* address; mbox_buf[33] is the pitch.
  //       Turn them into a struct fb_info at FB_INFO_BASE.
}

Part B: draw something

Now, let’s put a program on the screen! Our first program will just be one that shows the OS logo.

Part C: text is pixels

You have a screen and can draw graphics! But how would you display text? The hardware takes pixels and nothing else, so something has to turn a character into a shape, since the display doesn’t know anything about text. What controls text appearance is a font. (Note that on a terminal like the VT100, the font is in the terminal hardware itself, not on the computer. This is why a VT100 can only show text and only in a limited set of styles.)

   font8x8_basic['A'] = { 0x0C, 0x1E, 0x33, 0x33, 0x3F, 0x33, 0x33, 0x00 }

     byte        binary        pixels drawn
                             (bit 0 is on the LEFT)
     0x0C      0b0000'1100      . . # # . . . .
     0x1E      0b0001'1110      . # # # # . . .
     0x33      0b0011'0011      # # . . # # . .
     0x33      0b0011'0011      # # . . # # . .
     0x3F      0b0011'1111      # # # # # # . .
     0x33      0b0011'0011      # # . . # # . .
     0x33      0b0011'0011      # # . . # # . .
     0x00      0b0000'0000      . . . . . . . .

Part D: a terminal

You have input (Quest 2) and you have text output (Part C). Put them together and you have the oldest interactive program in computing: a terminal emulator. (It’s an emulator because it’s a program on your computer, rather than a hardware terminal attached to it.)

The terminal emulator is the program that reads characters from the keyboard, interprets them, and draws them on the screen. In a modern computer, the terminal emulator is host to a “shell” (e.g., Bash or Fish), which is a program that knows how to read and run commands.

We’ll build our terminal emulator in two parts:

• You’ll make a console library for drawing text (user/lib/u_vterm.h, user/lib/u_vterm.c): that is, starting at the top and printing line by line, and then scrolling up once you reach the bottom. You’ve probably always taken this for granted when using a terminal app—now you’ll build it!
• You’ll write the actual terminal emulator in user/term.c that reads the input from the keyboard, and uses your text console library to draw what you typed and the output of the commands to the screen

Why make a separate library? The text console part (e.g., printing text to a canvas, wrapping it at the edge of the screen, and scrolling up) will be useful in any program that draws text to the screen. Therefore, we ask that you write this code as a library (i.e., a struct and a series of helper functions) so you can reuse it. We will provide some example programs that you’ll adapt to use your library–for example, in Quest 4, you’ll modify your BASIC interpreter so you can use it on the screen!

Step D-1: start the library

To get a feel for what this all means, here’s an example for how we’d suggest starting your terminal emulator (user/term.c)—imagine that you started by writing this code, which just writes two lines of text to the screen:

term_t term;      // a struct from user/lib/u_vterm.h

// Set up the terminal struct, given info from the framebuffer (height, width, etc.)
term_init(&term, fb_info);

// write some lines of text
term_printf(&term, "hello world!\n");
term_printf(&term, "hello again!\n");

To display both lines, each call to term_printf should draw the characters at different coordinates in the framebuffer. However, when we write the application we don’t want to think about (x,y) screen coordinates or pixel values—we just want to draw text. Therefore, the goal of our terminal library (i.e., the term_ functions, and the term_t struct) is to abstract these items away from the application, so you can just focus on deciding what to print.

What is term_t? This is a struct to keep some metadata about the screen and the state of your terminal. Consider: after drawing one character, how do you know where to draw the next one? Terminals usually keep track of a cursor, which defines the next place to write—this, among other things, might be part of your metadata!

Why pass in the term_t struct to every call? In the next quest, we’ll run multiple graphical processes at the same time, each drawing to different parts of the screen. If multiple processes need to draw text, they’ll have different cursor positions, and other metadata! Therefore, we need to make the functions operate on different terminal info, instead of, e.g., using a bunch of global variables.

Here’s how we recommend starting:

Step D-2: scrolling up

The next fundamental part of a terminal is handling scrolling: when you print too much text, the terminal prints to the next line, and everything else scrolls up. To think about implementing this, modify your user/term.c to continually print some text that changes every line, using your shiny new term_printf:

// . . .
int count = 0;

while (true) {
   term_printf(&term, "count:  %d\n", count);
   count++;

   // Loop that spins for a bit (increase max if it's printing too fast)
   // (remove this for the next step)
   for (uint64 i = 0; i < 1000000; i++) {
       // do nothing
   }
}

Step D-3: make the terminal emulator

Now it’s time to make the terminal emulator actually read input and run commands. In this part, you’ll remove the test code we’ve been writing in user/term.c and replace it with the logic and commands to behave like a terminal. Broadly, this has two parts:

1. Adding the logic to read in characters from the user, write them to the terminal, and then run the command the user typed when they press Enter.
2. Implementing some commands to make your terminal display some useful info about your system!

Part E: something that moves

So far, our output to the screen has been text and static graphics. Let’s see something that moves!

What you should see is the box tearing. This may not be terribly visible on QEMU, but it is very evident when running on hardware—recall our demo in class. Several times a second, the box looks wrong for a moment: cut short at the top or the bottom, or with a step in one of its sides, as if its top half and its bottom half had been drawn in slightly different places. The problem here is that the display reads the framebuffer from top to bottom, over and over, and pong moves the box whenever it likes—so a picture on the screen can easily consist of some rows read before pong moved the box and some rows read after. What you see is neither frame, but a splice of the two!

This is not a bug in your code. It is the natural consequence of the design you have: every process writes straight into the one piece of memory the display is reading from, whenever it feels like it. We’ll fix this in Quest 4. For now, note the symptom—you will want to compare against it later.

Check your work

Run make qemu-fb (or make qemu-ws) with idle, and one of logo, term, and pong loaded. Depending on which one you run, you should see:

• your logo and your OS’s name, drawn by logo;
• a box bouncing (and tearing), drawn by pong;
• a prompt that responds to your typing, drawn by term;
• and, on the serial console, everything your kernel prints, as before.

Now load all of idle, logo, term, and pong at once, and run them. You should see a bouncing box, a prompt, and your logo…

…all overlapping and drawing on top of each other, because nobody has told them where they may draw: the box erases whatever it passes over, and whichever program cleared the screen last wins (you may not see your logo at all). That is the subject of Quest 4. Before you go on, take a screenshot of the mess; it makes the comparison at the end of Quest 4 much more satisfying.

We also recommend that you check the following:

1. Your OS copes without a display. Note that you cannot test this with make qemu: QEMU emulates the GPU whether or not it shows you a window, so you get a framebuffer either way—you just cannot see it. Test it by pretending instead: make fb_init() give up straight away, after setting pixels to NULL. Your programs should notice and say so, rather than writing to address zero.
2. The pitch is respected. Draw a single-pixel-wide vertical line from the top of the screen to the bottom, at x = 0. If it is straight, your row stride is right. If it walks diagonally, it isn’t. (Appendix B has a table of the other things that can go wrong—a black screen, mirrored text, swapped colors—and what they mean.)
3. ps in your terminal agrees with gdb. Run ps, then break in the kernel and print the process table in GDB. The same PIDs should have the same states and metadata.

Bonus Quests (Extra Credit)

Quest 4: Many processes, one screen

Files: kernel/memlayout.h, kernel/limits.h, kernel/elf.c, kernel/proc.h, kernel/proc.c, kernel/init.c, kernel/compositor.c, kernel/compositor.h, kernel/drivers/fb.c, kernel/drivers/fb.h, kernel/drivers/timer.c, kernel/drivers/timer.h, kernel/interrupts.c, kernel/klib.c, kernel/kernel.c, user/lib/u_common.c, user/lib/u_common.h, user/lib/u_fb.c, user/lib/u_fb.h, user/term.c, user/logo.c, user/basic.c, user/pong.c, user/clock.c (provided).

Overview

At the end of Quest 3 you had several programs drawing on one screen, all over each other, and a box that tears whenever it moves. Let’s fix this!

In this quest you will:

1. Give each process a private canvas inside its own memory, and decide—in the kernel—where on the screen each canvas appears.
2. Move every program onto its canvas, including BASIC, which gets a window of its own.
3. Write a compositor: kernel code that, sixty times a second, copies the canvases onto the screen. It will draw into a hidden half of the framebuffer and then flip it into view, so the display never shows a half-drawn picture.
4. Let programs wait for the next frame with wait_for_vsync(), and make sure a frame that a program is halfway through drawing never reaches the screen.
5. Deliberately break the illusion of simultaneity, and then put it back.

At the end, you will have four programs visible and running at once, none of them able to draw over another, nothing tearing, and the keyboard going to whichever one you pick. This is a simple version of the desktop computing environment you have on your laptop.

Why are we doing this?

This quest is where the two halves of this project meet the theme of the whole course. Your kernel already mediates the CPU, which it divides in time, and in Quest 2 it learned to hand the keyboard to one owner at a time. The screen forces a third pattern: it is divided in space.

Those three patterns—time-slice it, partition it, hand it to one owner at a time—cover most of what an operating system does with hardware. It is also, almost exactly, how the screen you are reading this on works. No program on your laptop draws on the screen. Each one draws into a buffer of its own, and a compositor—Quartz on macOS, the Desktop Window Manager on Windows, and, e.g., the Wayland compositor on Linux—decides where each buffer goes and combines them into what you see.

      0                     320                   640
    0 ┌──────────────────────┬──────────────────────┐
      │ ┌──────────────────┐ │ ┌──────────────────┐ │
      │ │ PID 1's canvas   │ │ │ PID 2's canvas   │ │
      │ │ (316 x 236)      │ │ │ (316 x 236)      │ │
      │ └──────────────────┘ │ └──────────────────┘ │
  240 ├──────────────────────┼──────────────────────┤
      │ ┌──────────────────┐ │ ┌──────────────────┐ │
      │ │ PID 3's canvas   │ │ │ PID 4's canvas   │ │
      │ │                  │ │ │                  │ │
      │ └──────────────────┘ │ └──────────────────┘ │
  480 └──────────────────────┴──────────────────────┘
          the 2-pixel gap around each canvas is a border,
          drawn by the kernel

   scanout position          what pong is doing
   ───────────────────────────────────────────────────────
   row 0 .. 200      ────►   (nothing yet)
   row 201           ────►   pong erases the box at its old position
   row 202 .. 300    ────►   pong draws the box at its new position
   row 301 .. 479    ────►   (done)

      GPU framebuffer (virtual: 640 x 960)

      ┌──────────────────────┐  ─┐
      │                      │   │  half 0   (rows 0..479)
      │                      │   │
      ├──────────────────────┤  ─┤  ◄── virtual y offset selects
      │                      │   │       which half is displayed
      │                      │   │  half 1   (rows 480..959)
      └──────────────────────┘  ─┘

   process ──draws──►  [ its canvas ]  ──compositor copies──►  [ GPU buffer ]  ──display reads──►  screen
                     (in its own memory)                       (hidden half)
            race 2: the compositor copies             race 1: the display reads
            a canvas the process is halfway           a buffer the compositor is
            through drawing                           halfway through writing

What you need to do

Part A: a window and a canvas for every process

A canvas is big: at 316 x 236 pixels and 4 bytes per pixel it is about 300 KiB, which is nearly five times the 64 KiB of memory we recommended for each process in Project 2. It also belongs to the process, so we will put it in the process’s memory. That means we must make room first.

Part B: programs draw on their canvases

Part C: a compositor

Your kernel now has to copy every canvas onto the screen, regularly, and the obvious place to do that is the timer interrupt. But your timer still runs at Project 2’s rate of a few interrupts a second, and to drive a display at 60 frames a second the kernel has to get control at least that often—and still have ticks left over for scheduling.

Part D: frame boundaries

Your screen no longer tears, but look closely at pong, especially while something else is busy: every so often the box is cut short, or missing entirely, for a frame. That is race 2. The timer fired while pong had erased its box and not yet redrawn it (or was in the process of redrawing it). The compositor then copies an unfinished frame from the process’s canvas, and the display shows it for a short period of time.

The fix is to detect whether a process is still drawing, and to never copy a canvas while it is actively being modified. There is also a second problem we’ll fix along the way: pong and the clock pace themselves by spinning on yield() until enough time has passed, which costs CPU and is unrelated to when the screen is actually redrawn by the compositor.

Part E: break the illusion

Everything is now running. Four programs are animating and responding at once, and it looks like four things happening simultaneously on one machine. But in reality, they aren’t happening truly simultaneously—it’s just that humans can’t perceive the switches between them.

You can prove it to yourself in two minutes!

Check your work

make qemu-fb with idle, term, basic, clock and pong should give you something like this on the serial console:

Hello world from MyOS!

Process table:
  pid 0  idle   (no window)
  pid 1  term   window 2,2  316x236  canvas at 0x0000000002180040
  pid 2  basic  window 322,2  316x236  canvas at 0x0000000002280040
  pid 3  clock  window 2,242  316x236  canvas at 0x0000000002380040
  pid 4  pong   window 322,242  316x236  canvas at 0x0000000002480040

[console: keyboard input now goes to pid 1 (term)]

(your addresses will differ) and, on the display, four programs in four bordered windows, with the focused one highlighted.

Things you should check for:

1. No tearing, and no half-drawn frames. The box in pong should be whole, always, at every position, and the clock’s hands should never flicker. Look hard, for a minute, and then again while a BASIC loop is running. A seam that appears every few seconds means one of your two races is still open; check, in this order, which half you copy into, and whether you hold back windows whose programs are mid-frame. (Under QEMU, a very occasional torn frame—one every half a minute or so—can be the emulator’s fault rather than yours: QEMU’s display is not synchronized with your flips.)
2. Focus switching moves the highlight. Press Shift+Tab and watch the border move, and the announcement appear on the serial console. Type into each program in turn and confirm that the characters go where you expect.
3. BASIC runs in its window, and a BASIC program printing in an endless loop scrolls its window without freezing anybody else’s. Ctrl-C still stops it.
4. Nobody draws outside their window. Watch the borders for a minute. A single stray pixel in a border or a neighbor’s window means somebody has a pointer they should not have.
5. Your OS still copes without a display. Pretend again, as in Quest 3, by making fb_init() give up: every drawing program should say it has nowhere to draw, and nothing should block for ever.

Congratulations—you have built a machine that several programs share, in space and in time, and that you can talk to, and whose screen never shows a frame that is not finished. If you are in CS 1670, that completes the project, modulo hand-in. If you are in CS 1690/2670, there is one quest to go: making all of this fast on the real hardware.

Bonus Quests (Extra Credit)

Quest 5: Faster graphics (CS 1690/2670)

Files: kernel/utils.c, kernel/compositor.c, kernel/compositor.h, kernel/console.c, kernel/proc.h, kernel/proc.c, kernel/init.c, kernel/drivers/timer.c, kernel/drivers/timer.h, user/lib/u_string.c, user/lib/u_fb.c, user/lib/u_term.c, user/pong.c, user/clock.c.

Overview

At the end of Quest 4 your desktop is correct: four windows, nothing tearing, nothing half-drawn. Under QEMU it is also quick. On a real Raspberry Pi, it is not quick at all. In this quest, you will make it fast enough to be pleasant on the hardware. You’ll apply techniques that cover the two ways that almost every performance problem is solved through: by doing the work you cannot avoid more cheaply, and by not doing the work you do not need to do.

You will:

1. Run your Quest 4 desktop on the Pi, and look at where the time goes.
2. Make memcpy copy data faster, which speeds up the work you cannot avoid.
3. Make the compositor copy only the windows whose canvases have changed, which avoids unnecessary work.

In addition, we give you the freedom to go further and improve performance even more!

Why are we doing this?

Having a desktop that is laggy is no fun. In addition, the two techniques in this quest are the ones you will reach for again and again! Damage detection in particular is one instance of a very general idea—remember what is already up to date, and redo only what changed—and your file system’s cache, your build system, and every incremental algorithm you will ever write work the same way.

It is also the first time in this course that you will make something faster rather than making it work, and the discipline is different: before you change anything, have a theory of where the time is going, and afterwards, a way to tell whether you were right.

What you need to do

Part A: look at the problem

Part B: a faster memcpy

The memcpy we gave you back in Project 1—look at kernel/utils.c—is a wrapper around a memmove that copies one byte at a time. That was simple and works fine when copying small numbers of bytes. But your compositor now calls this code on buffers of hundreds of kilobytes, sixty times a second!

Part C: copy only what changed

Check your work

1. Your output should still be correct. Everything in Quest 4’s checks still holds: there must be no tearing, no half-drawn frames, focus switching must work, BASIC must work in its window, and no process must draw outside its window.
2. Unchanged windows are not copied. With your DEBUG() line, you should see that pong is copied about once per refresh (many times per second), the clock twice a second, and the terminal and BASIC are only copied when you type.
3. Your copies are right. Your memcpy test passes, for both copies, and nothing on the screen ever shows garbage!
4. On the Pi, it is visibly better than what you saw in Part A: pong moves more smoothly, and your typing appears promptly.

Bonus Quests (Extra Credit)

Open-ended extra credit: impress us!

Beyond the per-quest bonus quests above, we are happy to give extra credit for anything that makes your OS more interesting, more usable, or more fun, as long as you can explain how it works. Some directions, in no particular order:

• A game. You have a screen, a keyboard, a timer and preemption. Snake, Tetris, Breakout, and Conway’s Game of Life are all comfortably within reach, and all of them make good demonstrations.
• Start and stop programs from your terminal. A run <name> command that allocates a process descriptor, loads one of the embedded ELF executables into it, assigns it a window, and marks it runnable—plus a kill <pid> that marks a process UNUSED and reclaims its window. This is the closest thing to a real shell you can build before Project 4.
• A screensaver, which requires knowing how long it has been since the last keystroke, which requires the kernel to notice.
• Better input: support arrow keys and implement a proper line editor, a scrollback buffer in your terminal, or copy and paste between windows (the latter is much harder than you’d think!).
• Mouse support, if you are feeling brave and have a serial mouse or are willing to invent a protocol over the UART. Some people have managed to connect PS/2 mice to the Pi’s GPIO pins, and there are USB-to-serial adapters that work with a USB mouse. (We do not provide a mouse, so you’ll need your own.)
• Something we haven’t thought of. Surprise us!

Handing in & grading

You will submit your work via git, using our grading server, exactly as for Projects 1 and 2.

Before you submit, make sure that:

• make clean && make qemu builds and runs without errors from a fresh checkout, and that your OS still copes if fb_init() fails.
• make clean && make qemu-fb (or make qemu-ws) shows your windowed desktop.
• Your code is formatted (make format) and free of debugging spew you did not intend to leave in—in particular, remove the temporary drain from Quest 1 and any per-frame prints from your compositor. (Lines inside DEBUG() can stay: they cost nothing unless you build with DEBUG_LVL=1.)
• Your memory layout diagram is up to date and committed as docs/memlayout-physical.pdf.
• Your screenshot from Quest 4 is committed as docs/desktop.png (or .jpg).

Submitting your code (and checking on the grading server)

1. Log into the grading server with the password you received.
2. Connect your repository under the “Project 3: Input and Output” category, if you have not already, and click it to fetch your repository from GitHub.
3. Check your code works: use the buttons below the commit list to test your code in our grading environment.
4. Set your grading commit with the “Grade this commit” button. You can reassign it at any time before the 72 late hour cutoff.
5. After submitting your work, sign up for a whiteboard discussion.

Congratulations—your operating system now has a screen and a keyboard. It is, for the first time, a computer you can actually use! 🎉

Grading breakdown

Your grade is based on:

• Functionality: We will run your code on the grading server and check that it works as expected (i.e., you can provide keyboard input to programs, and the screen shows output from multiple programs). This is worth 50% of your grade and impacts the “Projects” part of the course grade.
• Whiteboard Discussion: You will meet with a course staff member in a small group to discuss the concepts in this project for 45 minutes. The discussion is worth 50% of your grade and impacts the “Whiteboard Discussions” part of the course grade.
• If you are in CS 1690/2670, the additional work you must complete will contribute 1/5 of your overall grade (i.e., the contributions of functionality and whiteboard discussion will be scaled to 40% of your grade each, and the extra work will be another 20%).

We will grade according to our honest grading scale.