Lab 3: Shell and Bootloader Phase 1

Introduction

In this assignment, you will write useful utilities, libraries, and a simple shell for Raspberry Pi. This is just a single phase of this exercise and we’ll be going over the rest of them in the incoming weeks.

This is the directory structure of our repository. The directories you will be working on this lab section are marked with *.

.
├── bin : common binaries/utilities
├── ext : external files (e.g., resources for testing)
├── boot : bootloader *
├── kern : the main os kernel *
└── lib  : required libraries
    ├── pi *
    ├── shim
    ├── stack-vec *
    ├── ttywrite *
    ├── volatile *
    └── xmodem *

We recommend the following directory structure for your assignments. Confirm that your directories are properly laid out by running make inside the kern directory now. If all is well, the command will return successfully. If everything is good, feel free to explore the contents of the repository.

Phase 1: Oxidation

In this phase, you will write two libraries, one command-line utility, and review one library. You will be working in the stack-vec, volatile, ttywrite, and xmodem skeleton subdirectories located in lib directory.

All projects are being managed with Cargo. You will find the following cargo commands useful:

• cargo build - build an application or library
• cargo test - test an application or library
• cargo run - run an application
• cargo run -- $flags - run an application and pass arbitrary flags to it

For more information on using Cargo and how Cargo works, see the Cargo Book .

Subphase A: StackVec

One important facility that operating systems provide is memory allocation. When a C, Rust, Java, Python, or just about any application calls malloc() and malloc() has run out of memory from the operating system, a system call is eventually made to request additional memory. The operating system determines if there is memory available, and if so, fulfills the request for memory.

Heap-allocated structures like Vec, String, and Box internally call malloc() to allocate memory as necessary. This means that these structures require operating system support to function. In particular, they require the operating system to support memory allocation. We haven’t yet started writing our operating system, so clearly there’s no memory allocation support for our tiny bare-metal programs to make use of. As such, we can’t use heap-allocated structures like Vec until our operating system is further along.

This is a real shame because Vec is a nice abstraction! It allows us to think about pushing and poping elements without having to keep track of memory ourselves. How we can get the benefits of the Vec abstraction without supporting memory allocation?

One common technique is to pre-allocate memory and then hand that memory to a structure to abstract away. Some ways to pre-allocate memory include using static declarations to set apart memory in the static section of a binary or through stack allocations from local variable declarations. In any case, the allocations is of a fixed, predetermined size.

In this subphase, you will implement the StackVec structure, a structure that exposes a Vec-like API when given pre-allocated memory. You will use the StackVec type later in phase 2 when implementing a shell for your Raspberry Pi. You will work in the lib/stack-vec skeleton subdirectory. The subdirectory contains the following files:

• Cargo.toml - configuration file for Cargo
• src/lib.rs - where you will write your code
• src/tests.rs - tests that will run when cargo test is called

The StackVec Interface

A StackVec<T> is created by calling StackVec::new(), passing in a mutable slice to values of any type T. The StackVec<T> type implements many of the methods that Vec implements and is used in much the same way. Here’s an example of a StackVec<u8> being used:

let mut storage = [0u8; 10];
let mut vec = StackVec::new(&mut storage);

for i in 0..10 {
    vec.push(i * i).expect("can push 10 times");
}

for (i, v) in vec.iter().enumerate() {
    assert_eq!(*v, (i * i) as u8);
}

let last_element = vec.pop().expect("has elements");
assert_eq!(last_element, 9 * 9);

We’ve declared the StackVec structure for you already:

pub struct StackVec<'a, T: 'a> {
    storage: &'a mut [T],
    len: usize
}

Understanding StackVec

The following questions test your understanding about the StackVec interface:

struct StackVec<'a, T> { buffer: &'a mut [T], len: usize }

Implementing StackVec

Implement all of the unimplemented!() StackVec methods in stack-vec/src/lib.rs. Each method is documented in the source code. We have also provided tests in src/tests.rs that help ensure that your implementations are correct. You can run these tests with cargo test. You’ll also need to implement the Deref, DerefMut, and IntoIterator traits for StackVec as well as the IntoIterator trait for &StackVec for all of the cargo test tests to pass. Once you feel confident that you implementation is correct and have answered this subphase’s questions, proceed to the next subphase.

Subphase B: volatile

In this subphase, you will learn about volatile memory accesses, read the source code in the volatile skeleton subdirectory, and answer questions related to the source code. You won’t be writing any code in this subphase.

Like operating systems, compilers are masters at making things appear as if they’re doing what you think they’re doing when in reality, they’re really doing something entirely different for the sake of optimization. One such optimization is dead-access elimination: compilers remove memory accesses (reads and writes) when they can prove doing so has no observable effect on the program’s execution. For instance, consider the following program:

fn f() {
    let mut x = 0;
    let y = &mut x;
    *y = 10;
}

The compiler can completely eliminate the write to *y by reasoning that *y is never read after it’s written. The compiler concludes that as a result, the write cannot possibly effect the program, and eliminates it in the compiled binary. For the same reason, it can then proceed to eliminate the declaration for y, the declaration for x, and calls to f() entirely.

These kinds of optimizations are almost exclusively beneficial: they speed up our programs without affecting their outcome. But sometimes these optimizations can have unintended consequences. Say, for example, that y was pointing to a write-only memory-mapped register. Then, writes to *y will have observable effects without having to read *y thereafter. If the compiler is not aware of this, it will optimize away these writes, and our program will not function correctly.

How can we force the compiler to keep around reads and writes that appear to have no effects at the source code level? This is where volatile memory accesses come in: the compiler promises not to optimize away volatile memory accesses. So if we want to ensure a read or write occurs at runtime, we must perform a volatile memory access.

Rusty volatile

In Rust, we use the read_volatile and write_volatile methods to perform volatile reads and writes to a raw pointer.

Calling read_volatile and write_volatile every time we want to perform a volatile read or write is error prone and frustrating. Thankfully Rust provides us the tools to make this easier and safer. Ideally we can simply declare a pointer as volatile (as in C) and ensure that every read or write thereafter is volatile. Even better, we should be able declare a pointer as read-only, write-only (unlike in C), or read/write and ensure only the appropriate memory accesses can be made.

Introducing Volatile, ReadVolatile, WriteVolatile, and UniqueVolatile

The volatile crate in the volatile/ skeleton subdirectory implements these four types that allow us to do just this. Read the documentation for these types now by running cargo doc --open inside of the volatile/ directory.

Now open the source code in src/lib.rs, src/traits.rs, and src/macros.rs. Read through the source code to the best of your abilities. When you’re ready, answer the following questions. Once you have answered these questions, you’re ready to move on to the next subphase.

Subphase C: xmodem

In this subphase, you will implement the XMODEM file transfer protocol in the xmodem library in the xmodem/ skeleton subdirectory. You will primarily be working in xmodem/src/lib.rs.

XMODEM is a simple file transfer protocol originally developed in 1977. It features packet checksums, cancellation, and automatic retries. It is widely implemented and used for transfers through serial interfaces. Its best feature, however, is its simplicity. For more about its history, see the XMODEM Wikipedia article .

We will use the XMODEM protocol to transfer files to the Raspberry Pi. While we could use existing implementations of the XMODEM protocol to send data to the Pi, we will still need to write our own receiver. So, while we’re at it, we’ll be implementing XMODEM transmission as well.

The Protocol

The XMODEM protocol is described in detail in the Understanding The X-Modem File Transfer Protocol txt file. We describe it again here, for posterity.

XMODEM is a binary protocol: bytes are sent and received in the raw. It is also “half duplex”: at any point in time, either the sender or receiver is sending data, but never both. Finally it is packet-based: data is separated into 128 byte chunks known as packets. The protocol dictates which bytes are sent when, what they mean, and how they’re interpreted.

First, we define a few constants:

const SOH: u8 = 0x01;
const EOT: u8 = 0x04;
const ACK: u8 = 0x06;
const NAK: u8 = 0x15;
const CAN: u8 = 0x18;

To start the file transfer, the receiver sends a NAK byte while the sender waits for a NAK byte. Once the sender has received the NAK byte, packet transmission begins. The receiver only sends a NAK byte to begin the file transfer, not once for every packet.

Once file transfer has begun, each packet’s transmission and reception is identical. Packets are numbered in sequential order starting at 1 and wrap around to 0 after 255.

To send a packet, the sender:

1. Sends an SOH byte.

2. Sends the packet number.

3. Sends the 1s complement of the packet number (255 - $packet_number).

4. Sends the packet itself.

5. Sends the packet checksum.

   • The checksum is the sum of all of the bytes in the packet mod 256.

6. Reads a byte from the receiver.

   • If the byte is NAK, transmission for the same packet is retried up to 10 times.
   • If the byte is ACK, the next packet is sent.

The receive a packet, the receiver performs the inverse:

1. Waits for an SOH or EOT byte from the sender.

   • If a different byte is received, the receiver cancels the transfer.
   • If an EOT byte is received, the receiver performs end of transmission.

2. Reads the next byte and compares it to the current packet number.

   • If the wrong packet number is received, the receiver cancels the transfer.

3. Reads the next byte and compares it to the 1s complement of the packet number.

   • If the wrong number is received, the receiver cancels the transfer.

4. Reads a packet (128 bytes) from the sender.

5. Computes the checksum for the packet.

   • The checksum is the sum of all of the bytes in the packet mod 256.

6. Reads the next byte and compares it to the computed checksum.

   • If the checksum differs, sends a NAK byte and retries reception for the same packet.
   • If the checksum is the same, sends an ACK byte and receives the next packet.

To cancel a transfer, a CAN byte is sent by either the receiver or sender. When either side receives a CAN byte, it errors out, aborting the connection.

To end the transmission, the sender:

1. Sends an EOT byte.
2. Waits for a NAK byte. If a different byte is received, the sender errors out.
3. Sends a second EOT byte.
4. Waits for an ACK byte. If a different byte is received, the sender errors out.

To end the transmission, the receiver performs the following after receiving the first EOT:

1. Sends a NAK byte.
2. Waits for a second EOT byte. If a different byte is received, the receiver cancels the transfer.
3. Sends an ACK byte.

Implementing XMODEM

We have provided an unfinished implementation of the XMODEM protocol in the xmodem skeleton subdirectory. Your task is to complete the implementation by writing the expect_byte, expect_byte_or_cancel, read_packet, and write_packet methods in src/lib.rs. Your implementations should make use of the internal state of the Xmodem type: packet and started. We recommend reading over the existing code before starting.

You should begin by implementing the expect_byte and expect_byte_or_cancel methods. You should then make use of all four of the helper methods (including read_byte and write_byte) to implement read_packet and write_packet. To see how these methods are used, read the transmit and receive implementations which transmit or receive a complete data stream using XMODEM via these methods. Be mindful of the specifications in the doc-comments. You can test your implementation using cargo test. Once you are confident that your implementation is correct, proceed to the next subphase.

Subphase D: ttywrite

In this subphase, you will write a command line utility, ttywrite, that will allow you to send data to your Raspberry Pi in the raw or via the XMODEM protocol. You will use your xmodem library from the previous subphase in your implementation. You will write your code in ttywrite/src/main.rs. To test your ttywrite implementation, use the provided test.sh script.

Command-Line Interface

The skeleton code we have provided for ttywrite already parses and validates command-line arguments. To do so, it uses the structopt crate from crates.io which itself uses clap . You’ll notice that we list it as a dependency in the Cargo.toml file. structopt works through code generation. We simply annotate a structure and its fields with a declaration of our command-line arguments and structopt generates the code to actually parse the command-line flags.

To see the interface that structopt generates, call the application with --help. Remember that you can pass arbitrary flags when using cargo run: cargo run -- --help. Take a look at the interface now. Then, take a look at the Opt structure in main.rs and compare the interface with its definition.

You’ll notice that there are plenty of options. All of these correspond to settings available on a serial device. For now it’s not important to know exactly what these settings do.

Talking to a Serial Device

In main, you’ll see a call to serial::open . This is calling the open function from the serial crate, also on crates.io . This open function returns a TTYPort which allows you to read and write to the serial device (via its io::Read and io::Write trait implementations) as well as read and set settings on a serial device (via its SerialDevice trait implementation).

Writing the Code

Implement the ttywrite utility. Your implementation should set all of the appropriate settings passed in via the command-line stored in the opt variable in main. It should read from stdin if no input file is passed in or from the input file if one is passed in. It should write the input data to the passed in serial device. If the -r flag is set, it should send the data as it is. Otherwise, you should use your xmodem implementation from the previous subphase to send the data using the XMODEM protocol. You should print the number of bytes sent on a successful transmission.

To transmit using the XMODEM protocol, your code should use either the Xmodem::transmit or Xmodem::transmit_with_progress methods from the xmodem library. We recommend using transmit_with_progress so that your utility indicates progress throughput the transmission. In its simplest form, this might look as follows:

fn progress_fn(progress: Progress) {
    println!("Progress: {:?}", progress);
}

Xmodem::transmit_with_progress(data, to, progress_fn)

You can test the baseline correctness of your implementation using the test.sh script in the ttywrite directory. When your implementation is at least somewhat correct, you will see the following when the script is run:

Opening PTYs...
Running test 1/10.
wrote 333 bytes to input
...
Running test 10/10.
wrote 232 bytes to input
SUCCESS

Installing ttywrite utility

After finish writing the ttywrite utility, install the tool with cargo install --path . --locked command. This command will be used later to communicate with the bootloader.