RISC-V & Rust 4: Loading kernel image

Table of contents

• 1. Introduction
• 2. Kernel image stub
• 3. Loading kernel image with ZMODEM
  • 3.1 ZMODEM overview
  • 3.2 Receiving and sending headers
  • 3.2 Receiving data subpackets
  • 3.3 The whole picture
  • 3.4 Sending file from the host
• 4. Jumping to kernel
  • 4.1 Loading ELF image
  • 4.2 Transfering control
• 5. What's next?

1. Introduction

In this article, we will conclude our work on the bootloader and finally start working on the kernel (even if just for a bit). Before we get to practical matters, let's take a moment to think about the kernel loading process:

1. Where should we store our kernel image and how do we load it into memory?
2. What format will we use for the kernel image, and how do we transfer control to it?

For the first question, the obvious approach is to flash the kernel image to the SD card alongside the bootloader. However, this would require implementing a minimal SD card driver to read the kernel image into DRAM. Sounds a bit complicated. Plus, it would necessitate re-flashing the kernel for every minor change, which is frustrating. To avoid this, a better option is to load the kernel from a host PC. The simplest solution is to transfer the kernel image over UART. It's not that fast, but we're not expecting our kernel to grow more than a few hundred kilobytes in the near future.

There are numerous ways to transfer files over UART, but I've opted for ZMODEM. It offers error detection, built-in means for transferring multiple files, which may come handy when we'll start working on RAM disks, and is simple enough to implement in a couple of evenings. We also won't need to build a custom sender tool, as there are a lot of ZMODEM implementations already (namely lrzsz, which you can find in any Linux distribution).

For the second question, we'll load our kernel as a plain ELF executable to make things simple. This eliminates the need for post-build steps like extracting sections and inserting custom headers. Implementing a basic ELF loader would take only a few dozen lines of code, so why not?

With both questions sorted out, let's get our hands dirty with code.

2. Kernel image stub

Let's create a new crate called kernel, where all our kernel code will live. For this article, the kernel only needs to print something to the UART0 port to confirm that we've successfully handed control over from the bootloader.

Here's our entire kernel code base so far:

#![no_std]
#![no_main]

const UART0_BASE: u64 = 0x02500000;
const UART_USR: u64 = 0x7c;
const UART_THR: u64 = 0x00;

#[panic_handler]
fn panic(_info: &PanicInfo) -> ! {
    loop {}
}

fn uart_write(b: u8) {
    unsafe {
        while core::ptr::read_volatile((UART0_BASE + UART_USR) as *mut u32) & (1 << 1) == 0 {}

        core::ptr::write_volatile((UART0_BASE + UART_THR) as *mut u32, b as u32);
    }
}

fn puts(s: &[u8]) {
    for &b in s {
        uart_write(b);
    }
}

#[unsafe(no_mangle)]
pub unsafe extern "C" fn _start() -> ! {
    puts(b"hello from kernel\r\n");
    loop {}
}

For simplicity, we're not reusing the bootloader's UART driver code here. We'll be introducing a proper driver model later anyway, so why bother?

We'll keep using the bootloader's stack in SRAM for now, avoiding the need to set up kernel stack yet. The ELF loader handles everything else, which means we can skip writing an assembly prologue this time.

Here's a linker script for our kernel. Nothing fancy.

SECTIONS
{
    . = 0x40100000; /* DRAM BASE + 1MB */
    . = ALIGN(1);

    .text : { *(.text .text.*) }

    . = ALIGN(16);
    .rodata : { *(.rodata .rodata.* .srodata.*) }

    . = ALIGN(16);
    .data : { *(.data .data.* .sdata) }

    . = ALIGN(4);
    __bss_start = .;
    .bss : {
        bss = .;
        *(.bss .bss.*)
    }
    . = ALIGN(4);
    __bss_end = .;

    __end = .;
}

One thing to note is that we've changed the starting address from SRAM to a 1MB offset from DRAM base as our kernel will now run directly from DRAM, while the first megabyte will be reserved by the bootloader as scratch space to load the kernel image over UART.

I don't include the Makefile here, as it is trivial.

Basically, that's all with the kernel -- very boring. Now let's move to somewhat more interesting stuff and implement kernel image transfer over UART.

3. Loading kernel image with ZMODEM

Every protocol implementation usually boils down to blindly tinkering with the code until it passes some standard tests carefully reading the documentation, so let's do that.

The protocol dates back to 1986, so we don't expect a fancy PDF with diagrams and tables, just some old school hardcore teletype ASCII formatting. For reference, here are two versions of the spec:

• The original document: gallium.inria.fr/~doligez/zmodem/zmodem.txt
• Modernish wikified version: wiki.synchro.net/ref:zmodem that is slightly nicer to read.

We will implement only a minimal subset of the protocol required to receive a single file. ZMODEM has many features and can be tedious to implement fully: window management, explicit ACKs/NACKs, multi-file transfer, command execution, and so on.

Here's exactly what we'll need to implement:

1. Sender-initiated transfer.
2. Single file transfer (might want to extend later).
3. Streaming mode (no window management).
4. lrzsz compatablility (don't care about other implementations yet).
5. No retransmissions (fail immediately on CRC errors).
6. CRC16 only

3.1 ZMODEM overview

Every ZMODEM transaction starts with a frame header possibly followed by data (one or more subpackets). There are four subpackets variants, classified by their acknowledgment requirements (whether they demand ACK/NACKs from the receiver). ZMODEM uses ZDLE (0x18) control character to delimit headers and subpackets. Any ZDLE (and also some other control characters) appearing in header/data must be escaped.

There are 15 possible frame types, but we only care for a small subset (ZRQINIT, ZRINIT, ZFILE, ZDATA, ZEOF, ZFIN) required to transfer a file in streaming mode.

A frame can be encoded in one of three styles:

• HEX -- frame header and data are encoded as ASCII HEX string. Receiving side is required to always use this form.
• BIN16 -- frame header and data are encoded as binary sequence protected with CRC16
• BIN32 -- same as above, but protected with CRC32

We can always instruct the sender to use CRC16, so we will only need to implement HEX and BIN16 styles.

Here's how file transfer will look like in full streaming mode:

3.2 Receiving and sending headers

HEX header has the following format:

* * \x18 (ZDLE) B (ZHEX) TYPE HEADER[4] CRC[2] \r \n \x11 (XON)

BIN16 header format:

* \x18 (ZDLE) A (ZBIN) TYPE HEADER[4] CRC[2]

Here:

• TYPE is one byte header type
• HEADER[4] is a 4-byte header payload
• CRC[2] is a CRC16 for the packet header

Both header type and payload are protected by the CRC.

Here's how our header reading code will look like:

const ZRQINIT: u8 = 0;
const ZRINIT: u8 = 1;
const ZACK: u8 = 3;
const ZFILE: u8 = 4;
const ZFIN: u8 = 8;
const ZRPOS: u8 = 9;
const ZDATA: u8 = 10;
const ZEOF: u8 = 11;

#[derive(Clone, Copy)]
struct Header {
    typ: u8,
    data: [u8; 4],
}

pub struct ZModem {
    rx: fn() -> u8,
    tx: fn(u8),
}

impl ZModem {
    fn rx_header(&self) -> Header {
        while self.rx_ascii() != b'*' {}
        while self.rx_ascii() != ZDLE {}
    
        match self.rx_ascii() {
            ZHEX => self.rx_hex_header(),
            ZBIN => self.rx_bin16_header(),
            c => boot_panic!("unexpected header type: %d", c),
        }
    }
    
    fn rx_hex_header(&self) -> Header {
        let mut buf = [0u8; 7];
        let mut crc = Crc16::default();
    
        for c in &mut buf {
            *c = self.rx_hex_byte();
            crc.update(*c);
        }
        let crc = crc.finish();
    
        if crc != 0 {
            boot_panic!(/* ... */);
        }
    
        if self.xx_ascii() == b'\r' {
            self.rx_ascii(); // LF
        }
    
        Header {
            typ: unsafe { *buf.get_unchecked(0) },
            data: unsafe { buf.get_unchecked(1..5).try_into().unwrap_unchecked() },
        }
    }
    
    fn rx_bin16_header(&self) -> Header {
        let mut buf = [0u8; 7];
        let mut crc = Crc16::default();
 
        for c in &mut buf {
            *c = self.rx_bin().as_u8();
            crc.update(*c);
        }
        let crc = crc.finish();

        if crc != 0 {
            boot_panic!(/* ... */);
        }

        Header {
            typ: unsafe { *buf.get_unchecked(0) },
            data: unsafe { buf.get_unchecked(1..5).try_into().unwrap_unchecked() },
        }
    }
}

To make testing and debugging simpler, I abstracted the "send byte" and "receive byte" primitives into self.tx(c) and c = self.rx(). This makes is easy to run code on the host by plugging it to stdin and stdout.

Sending headers is even simpler than receiving, since we're only supposed to send HEX headers:

    fn tx_hex_header(&self, typ: u8, data: [u8; 4]) {
        let mut crc = Crc16::default();
        crc.update(typ);
        for b in data {
            crc.update(b);
        }
        let crc = crc.finish();

        (self.tx)(b'*');
        (self.tx)(b'*');
        (self.tx)(ZDLE);
        (self.tx)(b'B');
        self.tx_hex(&[typ]);
        self.tx_hex(&data);
        self.tx_hex(&crc.to_be_bytes());
        self.tx_bin(b"\r\n\x11");
    }

Some things are omitted here for brevity:

• rx_ascii() -- reads a character in ASCII mode
• rx_bin() -- reads a byte in binary mode, handling escape sequences
• rx_hex_byte() -- receives and decodes a byte as ASCII HEX
• tx_hex() -- encodes and sends bytes as ASCII HEX
• tx_bin() -- encodes and sends bytes as ASCII HEX
• boot_panic! -- a simple macro that prints an error message over UART and falls into the endless loop.
• Crc16 -- CRC16 implementation, mostly adapted from lrzsz.

3.2 Receiving data subpackets

Data subpackets follow the header and have the following format:

{DATA} \x18 (ZDLE) {TYPE} {CRC}

Where:

• DATA -- subpacket data (up to 1024 bytes). Subpacket data starts immediately after the header.

• TYPE -- subpacket type, tells receiver how to respond upon subpacket reception. There are four subpacket types, but we are only interested in ZCRCG (b'i') and ZCRCE (b'h'):

  • ZCRCW -- requires a response from the receiver after each frame;
  • ZCRCE -- indicates an EOF, response is required only if error is encountered.
  • ZCRCQ -- receiver expects ZACK response, but the next subpacket continues immediately. Used in full duplex mode.
  • ZCRCG -- elicit response only if error is encountered.

• CRC -- either CRC16 or CRC32, depending on header type.

Here's our packet receive function:

fn rx_subpacket<'a>(&self, data: &'a mut [u8]) -> Subpacket<'a> {
    let mut len = 0;
    let mut crc = Crc16::default();
    let mut typ = 0;

    for b in &mut *data {
        match self.rx_bin() {
            Sym::Esc(c) => {
                // incoming ZDLE + TYPE, stop reading data bytes
                crc.update(c);
                typ = c;
                break;
            }
            Sym::Chr(c) => {
                // incoming data byte
                crc.update(c);
                *b = c;
                len += 1;
            }
        }
    }

    if ![ZCRCE, ZCRCG, ZCRCQ, ZCRCW].contains(&typ) {
        boot_panic!("invalid subpacket type: 0x%x", typ);
    }

    // read CRC16
    crc.update(self.rx_bin().as_u8());
    crc.update(self.rx_bin().as_u8());

    if crc.finish() != 0 {
        boot_panic!("invalid subpacket CRC (subpacket 0x%x)", typ);
    }

    Subpacket {
        typ,
        data: unsafe { data.get_unchecked(..len) },
    }
}

We're going to receive two types of subpackets: regular file data and file metadata, which is part of ZFILE transaction.

• File data subpackets contain a block of file content that should be written directly into the output buffer.

• Metadata subpackets contain file information encoded (as ASCII text). The metadata consists of several space-separated fields, with only the first field—the file name—being mandatory. The metadata string is null-terminated.

3.3 The whole picture

Now let's put everything together. Here's our top level file transfer function that receives a file and copies it into the given buffer, returning the file size:

pub fn recv_file(self, buffer: &mut [u8]) -> usize {
    crate::uart::printf!("Receiving boot image via ZMODEM...\r\n");

    let header = self.rx_header();
    if header.typ != ZRQINIT {
        boot_panic!(
            "unexpected response header: %d (expected ZRQINIT)",
            header.typ
        );
    }

    self.tx_hex_header(ZRINIT, [0, 0, 0, 0]);

    let zfile = self.rx_header();
    if zfile.typ != ZFILE {
        boot_panic!("unexpected response: %d (expected ZFILE)", header.typ);
    }

    let mut data = [0u8; 64];
    let subpacket = self.rx_subpacket(&mut data);

    let fileinfo = {
        let len = subpacket.data.iter().position(|&c| c == 0).unwrap_or(0);
        unsafe { data.get_unchecked(..len) }
    };

    self.tx_hex_header(ZRPOS, [0, 0, 0, 0]);

    let header = self.rx_header();
    if header.typ != ZDATA {
        boot_panic!("unexpected header: %d (expected ZDATA)", header.typ);
    }

    let mut offset = 0usize;

    loop {
        let packet = self.rx_subpacket(unsafe { buffer.get_unchecked_mut(offset..) });

        offset += packet.data.len();

        if packet.typ == ZCRCE {
            break;
        } else if packet.typ == ZCRCG {
            continue;
        } else {
            boot_panic!("unsupported subpacket type: 0x%x", packet.typ);
        }
    }

    let header = self.rx_header();
    if header.typ != ZEOF {
        boot_panic!("unexpected header: %d (expected ZEOF)", header.typ);
    }

    self.tx_hex_header(ZRINIT, [0, 0, 0, 0]);

    let header = self.rx_header();
    if header.typ != ZFIN {
        boot_panic!("unexpected header: %d (expected ZFIN)", header.typ);
    }

    self.tx_hex_header(ZFIN, [0; 4]);

    crate::uart::printf!("\r\nFile metadata: %s\r\n", fileinfo.as_ptr());

    return offset;
}

Here's how it's called in the _main():

let zmodem = zmodem::ZModem::new(crate::uart::uart_read, crate::uart::uart_write);
let mut buffer =
    unsafe { core::slice::from_raw_parts_mut(dram::dram_base(), 1024 * 1024 * 32) };
let file_size = zmodem.recv_file(&mut buffer);

uart::printf!("Received file of size %d\r\n", file_size as u64);

3.4 Sending file from the host

After the bootloader starts, we can send the kernel image using lrzsz-sz ./kernel/kernel.elf. The only problem here is that we won't see the kernel output this way. A more convenient approach is to send the file via picocom using the C-a C-s keystroke. This way, we can immediately see the bootloader and kernel output.

Here's how the kernel loading process looks like using picocom.

sudo picocom -b 115200 -s lrzsz-sz /dev/ttyUSB0

*** file: ./kernel/kernel.elf
$ lrzsz-sz ./kernel/kernel.elf
Sending: kernel.elf
Bytes Sent:   5584   BPS:10600

Transfer complete

*** exit status: 0 ***

4. Jumping to kernel

With our kernel transfered into the SBC's DRAM, we're almost done. The only remaining thing is prepare the kernel for execution and hand over control.

We need to:

1. Parse the ELF file
2. Properly initialize ELF segments and place them at designated addresses.
3. Transfer control to the address specified in the e_entry field.

4.1 Loading ELF image

A comprehensive description of the ELF64 format is beyond the scope of this article, as there are many good resources available on the topic. But whatever, let's go over a brief overview.

ELF files provide two views into a program's code and data structure: the runtime view (represented by segments) and the link-time view (represented by sections).

Segments define the parts of the program relevant at runtime. They specify the segment's purpose, whether it should be loaded into memory, and where it should be loaded. If the ELF file contains a statically linked executable, the segment information alone is sufficient to load and run the program.

Sections represent the program structure from the linker's perspective and are more fine-grained. A single segment often contains data from multiple sections. For example, program code might be spread across several sections but represented by a single segment. Sections can also include debugging information, symbol tables, and other metadata.

Structure of an ELF file:

1. ELF header serves as the entry point for parsing the rest of the file, providing offsets and sizes of the program header table and the section table. It also contains some vital information about the program: ABI, target ISA, endianness, entry point address and so on.

2. Program header table describes the program's segments. Each entry specifies segment type (e.g. PT_LOAD), offset into the file image, virtual/physical load address, size, alignment information and possibly access flags (RWX).

3. Section header table describes the program's sections. The structure of the section header entry is quite similar to the program header entry. We won't need to deal with sections just now, so we won't get into detail here. One notable difference is that sections can have names, which are in turn stored in .shstrtab section.

Let's get to practice and write the simplest possible ELF loader. To keep things minimal, we'll skip various checks that would normally be required in production-grade code, such as checking the e_ident field and do just a bare minimum to load and run the kernel image.

const EI_NIDENT: usize = 16;

const PT_NULL: u32 = 0;
const PT_LOAD: u32 = 1;

#[repr(C)]
struct Elf64EHdr {
    /// ELF magic number
    /// Also encodes 32 or 64 bit flavour, endianness, ABI and ELF version
    e_ident: [u8; EI_NIDENT],

    /// Object file type. Should be ET_EXEC = 0x02 (executable file) in our case
    e_type: u16,

    /// Encodes ISA, should be 0xF3
    e_machine: u16,

    /// ELF version, should be 1
    e_version: u32,

    /// Entry point address (DRAM BASE + 1MB in our case)
    e_entry: u64,

    /// File image offset of the program header
    e_phoff: u64,

    /// File image offset of the section header
    e_shoff: u64,

    /// Flags (for which we don't care)
    e_flags: u32,

    /// Size of this header (64 bytes)
    e_ehsize: u16,

    /// Size of the program header table entry (should be 0x38)
    e_phentsize: u16,

    /// Number of program header table entries
    e_phnum: u16,

    /// Size of the section header entry (should be 0x40)
    e_shentsize: u16,

    /// Number  of the section header entries
    e_shnum: u16,

    /// .shstrtab section index
    e_shstrndx: u16,
}

#[repr(C)]
struct Elf64Phdr {
    /// Segment type. We only need to check for loadable segments with type PT_LOAD = 0x01
    p_type: u32,

    /// Segment-dependent flags. For loadable segments, denote RWX bits.
    p_flags: u32,

    /// File image offset of the segment
    p_offset: u64,

    /// Virtual address this segment should be loaded to
    p_vaddr: u64,

    /// Physical address this segment should be loaded to (irrelevant in our case)
    p_paddr: u64,

    /// Size of the segment in the file image
    p_filesz: u64,

    /// Size of the segment in memory
    p_memsz: u64,

    /// Segment alignment in memory (currently don't care)
    p_align: u64,
}

pub unsafe fn execute(binary: *const u8) -> ! {
    unsafe {
        let ehdr = binary as *const Elf64EHdr;
        let phentsize = (*ehdr).e_phentsize;
        let phnum = (*ehdr).e_phnum;

        for i in 0..phnum as usize {
            let offset = i * phentsize as usize;
            let phdr = binary.add((*ehdr).e_phoff as usize + offset) as *const Elf64Phdr;

            if (*phdr).p_type != PT_LOAD {
                continue;
            }

            let addr = (*phdr).p_vaddr as *mut u8;
            core::ptr::write_bytes(addr, 0, (*phdr).p_memsz as usize);

            if (*phdr).p_filesz != 0 {
                core::ptr::copy_nonoverlapping(
                    binary.add((*phdr).p_offset as usize),
                    addr,
                    (*phdr).p_filesz as usize,
                );

                crate::uart::printf!(
                    "Loading segment %i of size %d at %x\r\n",
                    i,
                    (*phdr).p_filesz,
                    (*phdr).p_vaddr
                );
            }
        }

        // TBD: jump to kernel

        loop {}
    }
}

Things are very straightforward here:

1. We iterate over the entries in the program header table.
2. Non-loadable segments are skipped, since we don't care about them at this point.
3. We zero-initialize the memory region where the segment will be loaded, just in case. This also handles segments that contain .bss section, which typically have p_memsz > 0 and p_filesz == 0.
4. If the segment has associated data in the file image, we copy it into memory.

4.2 Transfering control

We're now just six LOCs away from running our kernel. We already have the kernel entry point in the e_entry field of the ELF header, we just need to branch to it. Since the kernel is responsible for setting up its own stack (or actually it will be using bootloader's stack in SRAM for now), no additional preparation is needed on our end.

Let's plug this into our execute() function and we're done:

crate::uart::printf!("Jumping to kernel at 0x%x\r\n", (*ehdr).e_entry);

core::arch::asm!(
    "jalr x0, t0, 0",
    in("t0") (*ehdr).e_entry
);

core::hint::unreachable_unchecked();

This code loads the address from e_entry into temporary registers, and performs an absolute unconditional jump. unreachable_unchecked() tells the compiler that the code following the asm! block is unreachable.

Here's how loading and executing our kernel looks from the terminal:

*** file: ./kernel/kernel.elf
$ lrzsz-sz ./kernel/kernel.elf
Sending: kernel.elf
Bytes Sent:   5584   BPS:10600                           

Transfer complete

*** exit status: 0 ***

File name: kernel.elf
Received file of size 5584
Loading segment  of size 348 at 40100000
Jumping to kernel at 0x40100000
hello from kernel

Nice.

5. What's next?

In the next article, we'll begin working on the kernel itself. We'll set up timer interrupts and implement a simple time-slice scheduler.

Sources for this article are available on GitHub as usual: github.com/alexeyden/os5/tree/pt3-4-dram-zmodem