Project 1: Booting Your Own Operating System

In this project, you will write the code that takes a Raspberry Pi from the moment it powers on to the point where it can run a sequence of programs, one after another. By the end, you will have built a tiny operating system that performs batch processing: it loads a program into memory, runs it to completion, and then loads and runs the next one—the way the very first operating systems worked in the 1950s and 60s.

You will start with nothing. There is no operating system underneath you, no C standard library, no printf, just you and the hardware. The hardware powers on, places your code in memory, and starts executing it. Everything else is up to you.

This is called “baremetal” programming and is a different kind of programming from what you did in CS 300 or other prior systems courses. There, the operating system—and, specifically, the kernel—gave your program a stack, loaded it into memory, connected stdout to your terminal, and isolated your bugs from everyone else’s. Here, there are no other programs are running, and in the first step, there isn’t even an OS or a kernel.

Initially, your OS will do very little. Over the course of CS 1670/1690, you will build out from this primitive OS to something that approaches the feature set of a modern operating system.

Learning objectives

After completing this project, you will be able to:

1. Explain why a computer needs a boot process and what it must accomplish. You will understand that the hardware determines the machine’s physical memory layout—including where devices appear in memory for memory-mapped I/O (MMIO)—and that you must consult hardware manuals to discover this layout. You will also know what the essential steps in the bootup process are.
2. Explain why hardware needs device drivers to do anything useful, and write one: a driver for a device called a “serial console” that lets you print output.
3. Explain how an operating system loads and runs a user program. You will see that a program’s executable (a compact file of machine code and data) is a different thing from a running program (a set of memory segments), that the OS must load the executable into memory before it can run, and that the OS decides where in memory to put it.
4. Explain the role of the operating system as the layer that abstracts the hardware away from programs and as the mediator that decides which program runs.

The Raspberry Pi’s CPU uses the ARM64 architecture, which is a different hardware architecture from the x86-64 you saw in CS 300, or the architectures you may have seen in other Brown systems courses (e.g., CS 1650 uses x86-32, CS 1952-Y uses RISC-V). So, as a secondary learning objective, you will also become familiar with the ARM64 architecture, its registers, its instructions, and its conventions, and learn to read and write basic ARM64 assembly. To help you adapt your skills to ARM64, we provide a quick reference doc to help you get started – we’ll refer to this in throughout the handout.

CS 1670 vs. 1690/2670

All projects in the course are shared between CS 1670 (the basic “Operating Systems” course) and the lab, CS 1690/2670. However, students in CS 1690/2670 will work with real hardware and complete extra tasks that allow them to go deeper on the assignments.

In this project, you will mostly work in a machine emulator (QEMU) that emulates a Raspberry Pi. At the end of the project, students in 1690 will run their code on real hardware.

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

Roadmap

The project has three tasks (“quests”), which build on each other:

The next two sections describe how to get started with the assignment code. After you get set up, read the Background section next – it gives you the conceptual and ARM64 foundation you need for all three tasks. Then, work through the tasks in order.

Assignment Installation

If you have completed Project 0, you will already have created a private GitHub repository for your project work under the csci1670 organization.

While CS 1670/1690 projects have little stencil code, we do provide you with a repository structure and a build system to get started. You will need to pull this into your projects repository, as follows:

1. Open a terminal in your container environment and cd into the directory you setup as your project repo in Project 0 (e.g., cd projects).

2. Run the following command to pull the latest code from the handout remote:

   git pull handout main

   If this reports an error, run:

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

   followed by:

   git pull
   git pull handout main

This will merge our provided files with your repository.

Working on projects with VS Code

If you use VS Code (or one of its derivatives), there are two important parts of your IDE set up to check as you get started developing your OS:

How to open this repository

First, we need to make sure VS Code knows how to compile the code. This will make sure you can receive warnings on syntax errors, and can use Ctrl+Click (Windows) or Cmd+Click (macOS) to jump to where functions are defined. To do this:

1. If you have not done so already, open VS Code. If you use the container version, attach it to your container.

2. In the VS Code menus, go to File > Open Folder and navigate to your projects folder. Be sure to open this folder directly (don’t use your dev environment folder, your cs1670 folder, or your desktop).

3. Follow the instructions from project 0 to test your VS Code: native macOS version, Container version. If your initial setup worked, everything should be fine, but it’s important to check here since you’ll be using this repository all semester!

Disabling VS Code AI features (recommended)

CS 1670 has an open AI policy, and we will encourage you to use AI tools on many assignment tasks. However, we recommend disabling your IDE’s automatic AI suggestions as you work on your code, for two reasons:

1. There will be tasks where you should write the code yourself in order to understand the concept. For these tasks, an automatic AI suggestion may circumvent your learning by giving you an answer before you’ve had the chance to work it out on your own. We don’t want you to miss out on learning the concepts that are most important, so that you have these skills for later projects and outside the course.
2. Writing operating system code often differs from normal conventions in C programming, and AI can be wrong if it assumes these conventions hold. For example, our project has no system header files (e.g., stdio.h, stdlib.h), because these are part of your operating system. Similarly, AI often suggests x86-64 assembly instructions, even though our OS is written for the ARM64 architecture. Therefore, automatic AI suggestions from cheap models are likely to suggest incorrect code, especially as you’re getting started. As you work on the projects, we will provide guidance on how to prompt the AI to generate code that will work for us—so this is a skill you will learn!

To disable VS Code’s automatic AI features, do the following (example in the figure below):

1. Click on the gear menu in the bottom-left corner and select Settings
2. Search for “disable AI features” and check the first result:

For more details on AI use in CS 1670, please see our AI policy and the guidance at the end of each task in our handouts.

Code Structure

In this course, you will build your own operating system from the ground up. This means that you own every line of code, make all the key design decisions, and will really understand how key pieces of an OS work because you’ll design and implement them yourself.

Unlike other courses that provide you with stencil code in which you fill in specific functionality, in CS 1670 you write all significant code yourself. However, most operating systems’ code bases follow certain best practices and conventions, and we provide you—in this project and subsequent ones—with a skeleton of empty files that we recommend you structure your code into. We also provide a build system, so that you don’t have to wrangle the details of composing a Makefile that works with QEMU, GDB, and the somewhat arcane incantations required to build low-level OS code.

After you clone our stencil, you’ll find that it contains a build system and a skeleton layout of .c, .h, and .S files — most of them empty. You will fill these in.

.
├── Makefile
├── docs/                 ← Folder for screenshots, notes, memory layout diagrams, etc.
├── kernel/
│   ├── boot.S            ← Task 1: bootup assembly
│   ├── drivers/
│   │   ├── uart.c, uart.h   ← Task 2: the UART driver
│   │   └── gpio.h           ← Task 2: GPIO register definitions
│   ├── kernel.c          ← Task 3: the kernel's main loop
│   ├── elf.c, elf.h      ← Task 3: ELF format definitions + parsing
│   ├── init.c            ← Task 3: load + run one executable
│   ├── linker.ld         ← linker script that defines memory layout for kernel
│   ├── memlayout.h       ← physical memory layout constants
│   ├── mm.S, mm.h        ← memory-related helpers
│   ├── utils.c, utils.h  ← helper functions/macros, including for MMIO
│   └── ...
└── user/
    ├── pi.c              ← Task 3: the π-estimating program
    ├── u_klib.h          ← Task 3: the user-side library (access to printf)
    └── ...               ← more user programs for Task 3

Building and running

The build system uses make. The most important targets are:

$ make qemu        # build the image and run it in QEMU
$ make qemu-gdb    # same, but pause and wait for a debugger to attach
$ make clean       # remove build artifacts

make qemu boots your code in an emulated Raspberry Pi 3B+. The Pi’s serial console (the device you’ll write a driver for in Task 2) is connected to your terminal, so anything your code prints appears there. In a real early-days computer, this console would have been a typewriter, just like you saw in class.

Debugging bare-metal code is hard. There is no gdb running inside the machine and, until Task 2, no way to print anything. Instead you attach a debugger from outside the emulator:

# Terminal 1:
$ make qemu-gdb        # starts QEMU, paused, listening for gdb on port 1234

# Terminal 2:
$ cd YOUR_PROJECT_DIRECTORY   # important to run `gdb` from your project directory
$ gdb                  # (or `gdb-multiarch` on Linux/WSL)

Our stencil code ships a .gdbinit that connects to QEMU automatically and loads your kernel’s symbols. This is why running gdb inside your project directory is important: by doing so, you pick up the GDB configuration we provide. From there you can set breakpoints, step through instructions, and inspect registers. See Appendix C for a cheat sheet.

Quest 1: Boot into a bare-metal program

Files: kernel/boot.S, kernel/pi.c (and you’ll read kernel/memlayout.h, kernel/mm.S, kernel/linker.ld).

Overview

You will write the assembly code that runs at the very first instant the machine starts running, prepare the machine so that C code can run, and then jump into a C program—pi.c—that estimates π and spins forever. There is no kernel and no OS yet: boot.S and pi.c are linked together into one program that is the only program to run on the machine. This is the kernel “image” we referred to earlier, although there is no kernel yet: this task is purely about getting from power-on to running C code.

Why are we doing this?

Every operating system, no matter how large, begins with a few dozen instructions exactly like these. Before any C code can run, something must establish the conditions C depends on. Doing it yourself, once, demystifies the idea of “booting”, even though our example is a rather simple boot process. It also gives you a first, gentle taste of ARM64 assembly with a very small amount of code.

What you need to do

Here’s the plan for getting started. You’ll start by creating a helpful diagram of your operating system’s memory layout and will then write ARM64 assembly code for booting the machine in kernel/boot.S.

Memory Layout Diagram

One of the important roles of an OS kernel is to chop up the machine’s physical memory into different regions that will be used for different purposes. The kernel is typically the only piece of software in the computer (other than the bootloader) that deals with physical memory directly. But it has many decisions to make, and in this project alone, you’ll define four different key memory locations for your OS, with more to come in the future.

To keep track of this, OS developers use memory layout diagrams that visualize what physical address ranges are allocated for different purposes. Some allocations are dictated by the hardware (e.g., where memory used to do memory-mapped I/O with devices is), but others are yours to choose. You will also create and maintain such a diagram across your assignments in this course.

Here’s the initial physical memory layout of a Raspberry Pi 3B when it turns on:

This picture has nothing in it except for the delineation between addresses that correspond to RAM and those mapped to devices (for memory-mapped I/O; more on that later). You’ll fill in parts of this picture throughout the assignment.

Bootup Assembly Code

The file currently contains two #include statements to include headers that we will use in the future, and two lines. The first of these lines says that the assembly code should be part of the .text.boot segment of memory and .globl _start declares a global label.

#include "memlayout.h"

    .section ".text.boot"
    .globl _start

The entry point to a kernel is conventionally at a label called _start, placed first in the kernel “image” so it sits right at the address where the kernel gets loaded in memory. Your code should therefore start with a line that defines the start label, _start:. Any code you write after the _start: line in your file will run right at bootup.

The code at this label must do four things, in order:

1. Park all but one CPU core. All four CPUs on the Raspberry Pi begin executing your code simultaneously, but bootup must run on exactly one. Read the current core’s identity from the MPIDR_EL1 system register into a general-purpose register. The lowest eight bits in the register identify the core number; consider how you might extract these lowest eight bits only! On the one boot core (core 0), continue; on every other core, branch to a label that spins forever (an infinite branch-to-self). This loop is why we say bootup happens on a single CPU while the others are paused.
2. Zero the global variable segment (.bss). C assumes that uninitialized global and static variables start at zero. On bare metal, nothing has done this for you. The linker script (linker.ld) defines symbols marking the start and end of the .bss region. You can access the addresses that these symbols correspond to via the adr instruction: for example, adr x0, bss_begin puts the start address of .bss segment into the x0 register. Compute the .bss segment’s length and clear it. We provide a helper, memzero, in kernel/mm.S that you can call for this purpose. Read it, as it is a good, short example of ARM64 assembly.
3. Set up the stack. Point the stack pointer sp at the top of the region reserved for the kernel stack. We provide a constant for this in kernel/memlayout.h (INITIAL_KERNEL_STACK). You get to choose the location, since it is arbitrary and not defined by the hardware. A good choice would be an address far away from the kernel (which is at 0x8'0000) and which doesn’t overlap with any other memory regions you’re using (e.g., device registers). Without setting this constant and initializing sp, the first C function call will misbehave.
4. Jump into C. Use ARM64’s “branch with link” assembly instruction to jump to pi_main, the C entry point of the π program (kernel/pi.c), to start running it.

The π program (kernel/pi.c) is a C program that estimates π to a configurable number of digits and stores the result in memory. This is similar to the mathematical “computing” tasks that people primarily used early computers for.

Our implementation of the π estimation uses fixed-point arithmetic: early computers did not have floating point number support, and modern OS kernels still disable floating point in the kernel for simplicity. A common fixed-point arithmetic approach to computing π is to compute a scaled integer like ⌊π · 10ᵏ⌋ using an integer series.

In addition, we need to be creative about how to store the value of π, since we only have integers and no floating point data types. If we store ⌊π · 10ᵏ⌋ as a single number, the largest primitive integer type on ARM64 (a 64-bit unsigned int or uint64) can only represent 15 digits of π. To get more digits, we use a technique that was quite common on early computers: binary-coded decimal (BCD representation). In particular, pi.c uses “unpacked BCD”, which represents each digit as one byte. Representing the first 1,000 digits of π thus requires an array of 1,000 bytes (e.g., char pi_bcd[1000]), with each array element representing a number from 0 through 9.² Our program stores such an array as a global variable called pi_bcd in its data segment.

Check your work

Run make qemu-gdb and, provided it succeeds without errors, use a separate terminal to run gdb (from the same directory).

To check that everything works, you want to make sure that:

1. Your bootup assembly runs correctly. Check this by setting a GDB breakpoint at the line in assembly that jumps into C code and making sure that GDB hits that breakpoint. (Remember that in GDB, you set a breakpoint at a line number using b file:LINENUM, so, e.g., b kernel/boot.S:1 would set a breakpoint at line 1 of kernel/boot.S).
2. The value of π is computed correctly. Checking this requires inspecting the array of bytes stored in global variable pi_digits. See below for how to do this.

In GDB, set a breakpoint at the end of kernel/pi.c’s pi_main() function. This is most easily done with a line number. For example, the following sets a breakpoint at line 227:

(gdb) b pi.c:227

Then, once execution hits your breakpoint in pi.c (this could take a few seconds!), dump the computed value of π by printing global variable pi_bcd. Since this variable is an array of binary-coded decimal (BCD) digits, you’ll see one digit of π per array element.

(gdb) p/u pi_bcd    # p/u means "print as unsigned number"

$1 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, [...]

You should see your scaled estimate of π — e.g. a value close to 31415… for ⌊π·10ᵏ⌋. If the value is 0 or garbage, suspect that (a) your .bss wasn’t zeroed, or (b) your stack pointer is wrong.

Quest 2: Print output to the console with a UART driver

Files: kernel/drivers/uart.c, kernel/drivers/uart.h, kernel/drivers/gpio.h, kernel/memlayout.h; plus a printf you write.

Overview

A computed value you can only see in a debugger isn’t very satisfying, even if it matches very early computing experiences, where people read the output off a set of lightbulbs. In this task you will make the machine talk: you’ll write a device driver for the Raspberry Pi’s ARM PL011 Universal Asynchronous Receiver-Transmitter (UART), then build a printf on top of it, and use it to print your estimate of π.

The UART device is a simple input/output device, but UARTs are still critically important for systems today and used in the development and early-stage boot process for every computer and embedded device. Check out the notes from Lecture 3 for more information on the UART.

Why are we doing this?

Hardware does nothing until software activates and operates it. The code that knows how to do this—how to configure a device and move data in and out of it—is a device driver. Drivers are where the operating system meets physical reality, and writing one teaches you what the memory-mapped I/O (MMIO) actually feels like. There is no magic, just careful reads and writes to documented addresses, in a documented order. Once you have a driver, you can build a clean abstraction (printf) on top of it, which is the OS’s other job.

What you need to do

Part A: Find the hardware in the manual

When writing device drivers, the most important task for the developer is to understand the characteristics of the device they’re writing a driver for. This includes finding out where its MMIO device registers are, but also understanding what the device does when you access these registers.³ The source of this information is the “datasheet” for a device, which the manufacturer publishes for the benefit of device driver developers (or people who want to program the device directly). For us, the BCM2835 datasheet fortunately contains all the information we need.

Part B: Write the driver (kernel/drivers/uart.c)

The actual device driver is just a C program that reads from and writes to the MMIO addresses you just added to your header files. For now, we will only focus on configuring the UART device and sending output via the UART.

Before you can write driver code for the UART device itself, however, your driver will need to configure the General-Purpose Input/Output (GPIO) pins on the Raspberry Pi, which we’re using to access the UART.

On real hardware, these pins look like this (the 40 pins on a black base at the top of the picture):

You can find the so-called “pinout”, which documents the roles of these pins both in the BCM2835 datasheet and, more conveniently, on the internet.

We will only use three pins:

1. One pin, pin 8, configured to serve as a transmission (“TX”) pin for the UART.
2. One pin, pin 10, configured to serve as the receive (“RX”) pin for the UART.
3. A ground pin (e.g., pin 6) to connect the UART line to the same ground as the Pi itself.

Since there is a limited number of pins, the hardware allows reconfiguring them for different functionalities by programming special device registers for GPIO control. Hence, we must first assign the UART functionality to the relevant GPIO pins and enable them.

The GPIO configuration code is somewhat arcane, and we give it to you rather than having you write it (although you are welcome to work it out yourself if you want to).

void gpio_init() {
  // Select the right alternative function for each pin we're using
  unsigned int selector = mmio_read32(GPFSEL1);
  selector &= ~(0b111 << 12);  // clear bits for pin 14
  selector |= 0b100 << 12;     // set pin 14 to ALT0 functionality (TXD0)
  selector &= ~(0b111 << 15);  // clear bits for pin 15
  selector |= 0b100 << 15;     // set pin 15 to ALT0 functionality (RXD0)
  selector &= ~(0b111 << 18);  // clear bits for pin 16
  selector |= 0b111 << 18;     // set pin 16 to ALT3 functionality (CTS0)
  mmio_write32(GPFSEL1, selector);

  // Enable the GPIO pins
  mmio_write32(GPPUD, 0);      // disable pull-up/down for pins 14, 15, and 16
  delay_cycles(150);
  // enable clock for pins 14, 15, and 16; a clock signal is necessary so that
  // the configuration change actually gets applied
  mmio_write32(GPPUDCLK0, (0b1 << 14) | (0b1 << 15) | (0b1 << 16));
  delay_cycles(150);
  mmio_write32(GPPUDCLK0, 0);  // disable clock again
}

Now, in the next step, you can write the actual UART driver.

Some useful advice for writing device driver code, including the GPIO and UART driver code:

• Treat a device register as volatile. Wrap the raw addresses in helpers that read/write a volatile uint32 *, such as the mmio_write32 and mmio_read32 macros that we provide in kernel/utils.h, so the compiler never reorders assembly instructions that access this memory and ensures the “data” in those addresses doesn’t get stored in CPU caches. A device register is not ordinary memory.
• Most device registers are bitfields, meaning that you need to set individual bits or sequences of bits in them. You can do this in numerous ways, but we find that the easiest is to write your desired bit sequence as a binary constant (e.g., 0b110 for 110₂ = 6₁₀) and then shift it left to the right bit position (e.g., (0b110 << 7) to change bits 7, 8, and 9). To set multiple fields, you can binary OR them together: e.g., (0b110 << 7) | (0b1 << 3) sets bits 7-9 to 110 and bit 3 to 1.
• Always read and write device registers in their entirety (e.g., 32 bits for the UART registers). When using your helpers, mmio_write32 and mmio_read32, the compiler will generate the correct assembly for this.

Some UART-specific notes:

• You’ll need to configure the correct speed (a “baud rate” or data rate) for the UART. This is done by writing values to two registers that represent the integer and fractional parts of a divisor (a value that the hardware needs to divide another value by in order to produce the right baud rate). The dropdown below explains how to do this.

baud_divisor = 48,000,000 / (16 * baud_rate)

baud_divisor = IBRD + FBRD/64

• The manual’s synopsis of the CR register (page 185) notes a programming sequence for the control register (disable, then configure, then re-enable). Don’t skip the disable step: the hardware reacts funnily to being reconfigured while it’s operational.
• You’ll want to enable Clear-To-Send (CTS) flow control, which is a hardware feature that prevents the UART from sending data when the receiving device isn’t ready. This is done by setting a bit in the control register. While this doesn’t matter in QEMU (its hardware is always ready), it will matter if you connect your Raspberry Pi to a real (and slow) UART device.
• Develop your UART code in stages and test after each. First get a single known character out of uart_send (e.g. send '!' in a loop directly in the driver function). Only once one character works should you build up sending whole strings.
• If you see nothing at all: re-check the GPIO alternate-function setup and the peripheral base.
• If you see garbled characters: re-check the baud-rate divisor.

Part C: write printf

Now that you can output characters via the UART hardware, you’ll want a familiar abstraction for writing strings, numbers, and formatted text. The UART just expects ASCII characters, so to print a number (such as your value of π), some code must run that converts integers into ASCII characters. Likewise, turning a format string such as "%x" into a hexadecimal integer like 0x123abc requires code that implements this translation. On a normal system, the C standard library provides this functionality, and exposes it to your code via the printf function. But our computer so far has no C standard library or OS, so we must write it ourselves.

If you read the man page for printf, you’ll find that it supports a very complex set of format syntaxes. You won’t need all of them—for example, there is no need to print floating point numbers—but you’ll want to at least support printing numbers, strings, and pointers (i.e., hexadecimal numbers).

The basic logic behind printf is to iterate through the format string with a state machine consisting of two states:

1. When the iteration encounters a %, it enters the “inside format specifier” state, trying to parse a format specifier like %d. Once that succeeds, the function emits the data passed in the n^th argument (converting it as necessary) for the n^th format specifier and returns to the “normal character” state.
2. Otherwise, in “normal character” state, the iteration just emits the character.

“Emitting” a character means actually sending it to the output: in your case, this means calling uart_send. Your implementation should also handle error cases correctly—a printf that doesn’t do so can easily corrupt memory and is naturally hard to debug.

If you want to test your printf implementation, you can modify kernel/pi.c to print various values in the pi_main function.

Note on line endings. A serial console generally wants a carriage return and a line feed ("\r\n"), not just "\n", to start a new line cleanly. This is because early output devices like typewriters differentiated between “carriage return” (which moved the print head to the beginning of the current line) and “new line” (which moves the print head down, but not back to the start of the line).

Part D — print π

Now it’s time to use your printf to produce the output from the computation your program is doing.

Check your work

make qemu and watch your terminal. You should see your π estimate printed, e.g.:

pi ~= 3.1415926535...

(However you choose to format it.) Test printf with a few format specifiers and values to be confident it’s correct, as you’ll depend on it in Task 3.

Bonus Quests (Extra Credit)

CS 1670 projects will, on occasion, offer ✨ super fun extra credit quests ✨. These give you a chance to engage more deeply with the material and also have some fun.

Quest 3: An OS that runs programs in sequence

Files: kernel/kernel.c, kernel/elf.c, kernel/init.c, and headers and user programs in user/.

Overview

So far you have one program welded to your boot code: in other words, depending on your viewpoint, the program is either part of the “OS” or your computer has no OS and needs to restart in between different programs. A real OS runs many programs and they are ordinary executables that exist independently of the kernel. In this final task, you will build a small OS kernel that:

1. Loads several executables into memory in turn. Loading turns a compact executable file into a running program laid out in RAM (this requires you to add a loader to your OS).
2. Runs several programs in sequence. This is “batch processing”, a computing paradigm loads a program, runs it to completion, load the next, and so on.
3. Shares services with user programs. You will make your kernel’s printf function (and thus the UART driver underneath it) available to every program through a shared library, user/u_klib.h, so the programs don’t need to each re-implement the function or be compiled with the operating system.

Why are we doing this?

This is where the two roles of an OS—abstraction and mediation—become concrete. The program loader and the shared printf are abstraction: a program executable contains its machine code plus a description of how to lay it out in memory, but the loader decides on the actual memory locations for its segments. The program also gets I/O “for free” without knowing about UARTs by calling into the printf library function. The loop running programs one after another is mediation: the OS, not the programs, decides who runs and when.

In this part of the assignment, you also see the central distinction between an executable (a file) and a process (that file brought to life in memory), and see how the OS chooses where in memory to put a process.

What you need to do: loading programs

We’ll tackle this problem in three steps, each of which require very little code.

1. Boot into an actual kernel. You’ll change your bootup code to call into a shared OS kernel, rather than into pi_main.
2. Have the kernel load a program. You’ll add an ELF loader to your code base and write kernel code that calls into the ELF loader to load an executable.
3. Run a batch of programs. Once you have one program working, simply load and execute the next one after it completes.

Now, let’s write some code.

Now, we are ready to add an ELF loader and load programs that exist on storage. In our case, the “storage” will be somewhat fake, since we don’t have an SD card driver or file system yet. Instead, your kernel image (the kernel’s ELF file) will be holding the executable file’s bytes in memory, and so that the Raspberry Pi’s bootup sequence loads them into memory alongside the kernel. The program loader will then read the bytes of the executable from memory, copy them into the right place in RAM, and then jump to the program’s entry point.

Writing a program loader is a fun and educational exercise that really makes you understand the ELF executable format, but is also fiddly and time-consuming. We therefore provide you with a pre-made loader in this repository. While you’re welcome to write your own (with or without AI), we’d suggest copying over the provided loader code.

We will now change kernel_main to call into a function called init. The init function should invoke the ELF loader to load a program. For example, a typical init function might look like this:

void init(void) {
    // Load the first program
    void* entry_adr = load_elf((void *)executable_address_in_memory, (void*)start_of_process_memory);
}

Where’s the executable? You might wonder where executable_address_in_memory comes from. The answer is that we configured the linker to place each ELF executable from the user directory into a known location in the kernel’s memory image. The linker helpfully adds a label for each such executable, which you can reference in your code. For example, if you have a user program called user/hello.elf, the linker will add a label called _binary_user_hello_elf_start that points to the start of that program’s bytes in memory. We include extern declarations for these labels in kernel/init.c, so you can reference them in your init function.

Where should the program go in memory? The second argument to load_elf, the pointer start_of_process_memory, is a memory address that will serve as the start of your process’s memory region. The program loader will put your program’s segments starting at that address. You can pick any address you like, but it must not overlap with other memory regions you have already defined (e.g., the kernel memory and the initial kernel stack). A good way of going about this is to define a constant in kernel/memlayout.h that marks the start of the user program memory region (e.g., PROC_START) and another constant that defines the amount of memory to reserve for each process (e.g., PROC_SIZE). Then, in your init function, you can load the first program at PROC_START, the second at PROC_START + PROC_SIZE, the third at PROC_START + 2 * PROC_SIZE, and so on.

You might wonder what good values to pick for these are. A good starting point is to pick PROC_START to be a few megabytes above the kernel’s memory region, and PROC_SIZE to be relatively small, like 16 KiB (0x4000). For example, if your kernel starts at 0x8'0000 and you give it up to 1 MiB of memory (0x100000 bytes), you might pick 0x18'0000 as your PROC_START and reserve 16 slots for of PROC_SIZE at that address. You may need to adjust these values in the future; eventually, adding support for virtual memory to your OS will take care of no longer having to set them carefully.

What you need to do: library functions & running a program

In addition to loading the program, we need to make the library function vprintf available to it. The solution—as alluded to above—we’re going with here is to put the memory address for the function’s machine code into a known location. If you look at kernel/memlayout.h, you’ll see a constant F_BASE that defines a memory address (currently a placeholder of 0x0), and a constant F_VPRINTF that indexes into eight bytes below that address (e.g., if F_BASE was 0x1000000, then 0x0FFFFF8 corresponds to F_VPRINTF). Your kernel_main function should write the address of your vprintf function in the code segment into that location, so that user programs can call it. The code that lets user programs actually call printf to invoke the kernel’s vprintf via this mechanism is already in user/lib/u_common.c in case you’re curious.

To actually run your loaded program, you’ll need to do some C shenanigans, which we suggest placing into an exec helper function. In essence, you should cast the loaded program’s entry point to a function pointer and call it. For example, if entry_adr is the entry point of the loaded program, you can run it with:

void (*program_entry)(void) = (void (*)(void))entry_adr;
program_entry();

Finally, let’s run a “batch” of programs! You’re nearly there.

Check your work

If everything works, make qemu should boot your newly-minted, still very basic kernel and then run your programs one after another, printing the “hello world” message and any output the programs themselves produce (including, via u_klib.h, output from a program that calls your shared printf). For example:

Hello world from <YOUR_OS'S_NAME>!                              # output from your kernel
1   1   0                                                       # output from user/squares.elf
2   4   3
...
pi ~= 3.1415926535...                                           # output from user/pi.elf
...
primecheck: Found another 1000 primes; last one was 7919!       # output from user/primecheck.elf
...

And with that, you are done, except for one last task!

Congratulations, you have created your own OS that boots and runs multiple programs in sequence! You have completed the project 🎉.

Bonus Quests (Extra Credit)

Handing in & grading

You will submit your work via git, using our grading server.

Before you submit, make sure that:

• make clean && make qemu builds and runs without errors from a fresh checkout.
• Your code is formatted (make format) and free of debugging spew you didn’t intend to leave in.

Submitting your code (and checking on the grading server)

Your submission will not be graded until you configure the grading server. You should have used the grading server for Project 0 already.

To submit your work, please do the following:

1. Log into the grading server with the password you received. Once you’re logged in, enter your GitHub username (at the top).
2. Connect your repository by adding the repository URL under the “Project 1: Booting” category. Click “Project 1: Booting” to initiate a fetch of your repository from GitHub.
   • Note: If your GitHub account is not linked to your Brown email address, the grading server will give you a command to run to verify your project repository.
3. Check your code works: On the “Project 1: Booting” page, use the buttons below the commit list to test your code in our grading environment. Make sure it still works as expected!
4. Set your grading commit: finally, press the “Grade this commit” button to tell us which commit you want us to grade. Some notes about this:
   • You can reassign your grading commit at any time before the 72 late hour cutoff. If your commit is after the deadline, the grading server will tell you how many late hours it uses after selecting it from the dropdown.
5. Click the “Run submission checks” button to run a set of tests that tell you if there are any known problems with your handin. Passing this check doesn’t guarantee that everything works or is correct, but catches some common issues early.
6. After submitting your work, please sign up for a Whiteboard discussion.

Congratulations, you’ve completed the first project! 👏

Grading breakdown

Your grade comes in two parts:

• Functionality: We will run your code on the grading server and check that it works as expected (i.e., runs the three programs in turn). 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.

We will grade both components according to our honest grading scale.

Footnotes