# Operating System Capstone - Lab2
## Basic Exercise 1 - UART Bootloader - 30%
## Advanced Exercise 1 - Bootloader Self Relocation - 10%
We do these two task at the same time.
Goal: Implement a UART bootloader that loads kernel images through UART.
#### TASK1: Set stack pointer, clear bss and start address for bootloader
> We will have two programs
> 1. Bootloader
> 2. Shell(other files)
Since in Lab1 our shell(main.c) run in 0x80000
We now run bootloader(bootloader-main.c) in 0x80000 first, so that we can run bootloader in the raspberrypi. However, if we put shell(main.c) to 0x80000, the bootloader will be replaced. So, what we do is move bootloader from 0x80000 to 0x60000(it depends), and reserve 0x80000 for shell(main.c)
Let's see our `linker.ld`
```linker=
SECTIONS
{
. = 0x60000;
__bootloader_start = .;
.text : { KEEP(*(.text.boot)) *(.text .text.* .gnu.linkonce.t*) }
.rodata : { *(.rodata .rodata.* .gnu.linkonce.r*) }
PROVIDE(_data = .);
.data : { *(.data .data.* .gnu.linkonce.d*) }
.bss (NOLOAD) : {
. = ALIGN(16);
__bss_start = .;
*(.bss .bss.*)
*(COMMON)
__bss_end = .;
}
__bootloader_end = .;
/DISCARD/ : { *(.comment) *(.gnu*) *(.note*) *(.eh_frame*) }
}
__bss_size = (__bss_end - __bss_start) >> 3;
__bootloader_size = (__bootloader_end - __bootloader_start)>>3;
```
Now we have `__bootloader_start` in 0x60000 and `__bootloader_size`. Let's continue to see `start.S`
```ams=
.section ".text.boot"
.global _start
_start:
// relocate bootloader
ldr x10, =0x80000
ldr x11, =__bootloader_start //x11=0x60000
ldr w3, =__bootloader_size
relocate:
ldr x4,[x10],#8 ---> take the value out from 0x80000
str x4,[x11],#8 ---> put the value in 0x60000
sub w3,w3,#1 ---> move bootloader size
cbnz w3,relocate --> bootloader size !=0, continue
setting:
ldr x1, =_start
mov sp, x1
ldr x1, =__bss_start
ldr w2, =__bss_size
clear_bss:
cbz w2, bootloader_main
str xzr,[x1],#8
sub w2, w2, #1
cbnz w2, clear_bss
bootloader_main:
bl main-0x20000
b bootloader_main
```
Now, we have successfully set the stack point and clear bss for bootloader.
#### TASK2: Start to implenment bootloader
```cpp=
#include "header/uart.h"
#include "header/bootloader.h"
void main()
{
// set up serial console
uart_init();
// say hello
uart_send_string("Start Bootloading\n");
load_img(); //call bootloader here.
}
```
left part is load_img(), right hand part is `uploader.py`.
When we start running rasperrypi, since the bootloader file has been manully import into raspberry pi, so the `load_img()` is running.
Then we need to have a uploader, to upload the file(shell_kernel.c is the example here.) without manually putting it into raspberry pi from USB.
As you can see, load_img() will be stuck at `uart_get_char()` twice
- First time: We get the size buffer of the `shell_kernel.img`
- Second time: Since we know the size of the img, then we put the content of the img start from 0x80000.
After loading the image, the bootloader(load_img) will move to 0x80000, and start to run shell_kernel.img
X30 is the link register (LR)
> In AArch64 state, the Link Register (LR) stores the return address when a subroutine call is made
## Basic Exercise 2 - Initial Ramdisk - 30%
An initial ramdisk is a file loaded by a bootloader or embedded in a kernel. It’s usually an archive that can be extracted to build a root filesystem.
Cpio is a very simple archive format to pack directories and files. Each directory and file is recorded as a header followed by its pathname and content.
#### Task1: create a rootfs directory and put all files inside it
```shell=
cd rootfs
find . | cpio -o -H newc > ../initramfs.cpio
cd ..
```
#### Task2: Trasverse the file in initramfs.cpio
New ASCII Format
The "new" ASCII format uses 8-byte hexadecimal fields for all numbers and separates device numbers into separate fields for major and minor numbers.
```cpp=
struct cpio_header {
// uses 8-byte hexadecimal fields for all numbers
char c_magic[6]; //determine whether this archive is written with little-endian or big-endian integers.
char c_ino[8]; //determine when two entries refer to the same file.
char c_mode[8]; //specifies both the regular permissions and the file type.
char c_uid[8]; // numeric user id
char c_gid[8]; // numeric group id
char c_nlink[8]; // number of links to this file.
char c_mtime[8]; // Modification time of the file
char c_filesize[8]; // size of the file
char c_devmajor[8];
char c_devminor[8];
char c_rdevmajor[8];
char c_rdevminor[8];
char c_namesize[8]; // number of bytes in the pathname
char c_check[8]; // always set to zero by writers and ignored by readers.
};
struct file {
struct cpio_header* file_header;
unsigned long filename_size;
unsigned long headerPathname_size;
unsigned long file_size;
char* file_content_head;
};
```
Each `sizeof(struct cpio_header)` is 110 bytes
The cpio file will be read like
```
00000010101.....0000 -> 110 byte
ABC.txt -> File1_title
This is ABC.txt -> File1_content
00000010101.....0000 -> 110 byte
DEF.txt -> File2_title
This is DEF.txt -> File2_content
TRAILER ---> END OF THE CPIO
```
in `cpio.c`
```cpp=
int file_num = 0;
struct file *f = NULL;
void allocate_file_array() {
if (f == NULL) {
f = (struct file *)simple_malloc(MAX_FILE_NUM * sizeof(struct file));
if (f == NULL) {
uart_send_string("Memory allocation error\n");
// Handle memory allocation error
}
}
}
```
```cpp=
void traverse_file()
{
allocate_file_array();
char* addr = (char *)cpio_addr;
while(utils_string_compare((char *)(addr+sizeof(struct cpio_header)),"TRAILER!!!") == 0){
struct cpio_header *header = (struct cpio_header *)addr;
unsigned long filename_size = utils_atoi(header->c_namesize, (int)sizeof(header->c_namesize));
unsigned long headerPathname_size = sizeof(struct cpio_header) + filename_size;
unsigned long file_size = utils_atoi(header->c_filesize, (int)sizeof(header->c_filesize));
utils_align(&headerPathname_size, 4);
utils_align(&file_size, 4);
f[file_num].file_header = header;
f[file_num].filename_size = filename_size;
f[file_num].headerPathname_size = headerPathname_size;
f[file_num].file_size = file_size;
f[file_num].file_content_head = (char*) header + headerPathname_size;
addr += (headerPathname_size + file_size);
file_num += 1;
}
}
```
Now, We store the needed info for each file
#### Task3: Implement `ls` and `cat`
Then, we implement `ls` first
```cpp=
void cpio_ls()
{
//beginning + 110 bytes = title location
for(int n=0;n<=file_num;n++) {
uart_send_string(((char *)f[n].file_header)+sizeof(struct cpio_header));
uart_send_string("\n");
}
}
```
Now, we implement `cat`
we need to find the header of the selected file
```cpp=
int findfile(char* filename) {
for(int n=0;n<=file_num;n++) {
if ((utils_string_compare(((char *)f[n].file_header)+sizeof(struct cpio_header), filename) != 0)){
return n;
}
}
return -1;
}
```
Then, start to print the content of the file
```cpp=
void cpio_cat(char *filename)
{
int targetfile_num = findfile(filename);
if(targetfile_num != -1) {
for (unsigned int i = 0; i < f[targetfile_num].file_size; i++)
{
uart_send_char(f[targetfile_num].file_content_head[i]);
}
uart_send_string("\n");
} else {
uart_send_string("Can not Find the file\n");
}
}
```
## Basic Exercise 3 - Simple Allocator - 10%
```cpp=
#include "header/allocator.h"
#include "header/utils.h"
#define SIMPLE_MALLOC_BUFFER_SIZE 8192
static unsigned char simple_malloc_buffer[SIMPLE_MALLOC_BUFFER_SIZE];
static unsigned long simple_malloc_offset = 0;
void* simple_malloc(unsigned long size){
//align to 8 bytes
utils_align(&size,8);
if(simple_malloc_offset + size > SIMPLE_MALLOC_BUFFER_SIZE) {
//Not enough space left
return (void*) 0;
}
void* allocated = (void *)&simple_malloc_buffer[simple_malloc_offset];
simple_malloc_offset += size;
return allocated;
}
```
## Advanced Exercise 2 - Devicetree - 30%
#### Task0: Background knowledge
A device tree is a data structure that describes the hardware components of a particular computer so that the operating system's kernel can use and manage those components, including the CPU, memory, and peripherals.
The device tree is especially important in the world of ARM and embedded systems, such as the Raspberry Pi, where there are many different possible system configurations. The idea is that a single compiled kernel can be used across multiple different hardware configurations. Instead of **hard-coding** every detail of the hardware into the kernel for each possible configuration, the kernel is designed to be hardware-agnostic and instead reads a device tree at boot time to find out what hardware it should expect to find and how to interface with it.
===Note=== In the lab, we don't need to fix the cpio address.
The structure of a device tree is a hierarchy of nodes, each of which represents a device or a piece of hardware. Nodes contain properties, which are name/value pairs that provide data about the device. Nodes can also have child nodes, which represent sub-devices or components of the device.
For example, a node for a serial port might have properties that describe its I/O address and interrupt line, and a node for a system-on-a-chip might have child nodes for its various integrated peripherals.
Here is an example of what a device tree node might look like:
```asm=
uart1: serial@101f1000 {
compatible = "arm,pl011", "arm,primecell";
reg = <0x101f1000 0x1000>;
interrupts = <1 6>;
};
```
This node describes a serial port ("uart1") at memory address 0x101f1000. The compatible property says that the device is compatible with the ARM PL011 UART and the ARM Primecell interface. The reg property gives the base address and size of the memory-mapped I/O region for the device, and the interrupts property specifies the interrupt controller (1) and line (6) that the device is connected to.
The property linux,initrd-start in a device tree is used to specify the start address of the initial RAM disk (initrd) in memory. This is a scheme employed by the Linux kernel.
---
Other example:
In Linux, the initrd is a scheme for loading a temporary root file system into memory in the boot process of the Linux kernel. Initrd and initramfs refer to two different methods of achieving this. Both are commonly used to make preparations before the real root file system can be mounted.
An example for a device tree specification for linux,initrd-start could look like this:
```asm=
chosen {
bootargs = "console=ttyAMA0";
linux,initrd-start = <0x80000000>;
linux,initrd-end = <0x80800000>;
};
```
In this example, the linux,initrd-start property is set to 0x80000000, and linux,initrd-end is set to 0x80800000. This specifies that the initial RAM disk is located in memory between addresses 0x80000000 and 0x80800000.
The chosen node in a device tree is typically used to hold configuration data, like kernel command line parameters (bootargs in this case) or the initrd location as shown above.
Please note that this is just an example, and the actual addresses for the initrd would depend on your specific system configuration.
**This is really import to know the structure of device tree**
**Goal: Use the API to get the address of initramfs instead of hardcoding it.**
#### Task1: Set the dtb to traverse for the device
in `start.S`
```asm=
.section ".text.boot"
.global _start
_start:
ldr x1, =_dtb_ptr //put _dtb_ptr into register1
str x0, [x1] //store dtb address from x0 to _dtb_ptr
.global _dtb_ptr //define a global variable _dtb_ptr
.section .data //_dtb_ptr is in data section
_dtb_ptr: .dc.a 0x0 //it defines _dtb_ptr to be a 8-byte constant with a value of 0x0
```
- The ldr instruction loads a word from memory into a register. The instruction ldr x1, =_dtb_ptr is a pseudo-instruction that loads the address of _dtb_ptr into the x1
- The str instruction stores a word from a register into memory. The instruction str x0, [x1] stores the value of the x0 register at the memory address specified by the x1 register. So, it's storing the value of x0 into _dtb_ptr.
> The x0 register is one of the general-purpose registers in the AArch64 architecture of the ARM processor. The contents of x0 will depend on the state of the system and the code that has been executed prior to these instructions.
>
> In the context of kernel booting and the code you've shown, it's typical for the bootloader to pass the address of the device tree blob (DTB) to the kernel in the x0 register when the kernel starts executing. The device tree blob contains a data structure that describes the hardware of the system to the kernel.
>
>The line str x0, [x1] is storing the contents of x0 (presumably the address of the device tree blob) into the memory location pointed to by x1 (the address of the _dtb_ptr variable). In essence, this line is saving the address of the device tree blob into the _dtb_ptr variable for later use by the kernel. This is important because the kernel needs to know the details about the system's hardware, which are provided by the device tree blob, in order to function correctly.
#### Task2: Get CPIO address
we run `fdt_traverse` in `main()` to ensure that we get needed hardware info(here we need address) in the beginning.
```cpp=
extern void *_dtb_ptr;
void main()
{
// set up serial console
uart_init();
// say hello
fdt_traverse(get_cpio_addr,_dtb_ptr);
uart_send_string("Type in `help` to get instruction menu!\n");
//echo everything back
shell();
}
```
1. Create a structure for holding the FDT header information(fdt_header)
```cpp=
struct __attribute__((packed)) fdt_header {
uint32_t magic; // contain the value 0xd00dfeed (big-endian).
uint32_t totalsize; // in byte
uint32_t off_dt_struct; // the offset in bytes of the structure block from the beginning of the header
uint32_t off_dt_strings;
uint32_t off_mem_rsvmap;
uint32_t version;
uint32_t last_comp_version;
uint32_t boot_cpuid_phys;
uint32_t size_dt_strings; // the length in bytes of the strings block section
uint32_t size_dt_struct;
};
```
2. Implement helper functions to extract the FDT header information
- uint32_t fdt_u32_le2be (const void *addr)
The function fdt_u32_le2be in the provided C code is used to convert a 4-byte sequence from little-endian order to big-endian order.
The Device Tree Blob (DTB) is represented in big-endian byte order. However, many systems (including the ARM architecture used in many embedded systems) use little-endian order. Therefore, when we need to compare the value between each two, we need to do the convertion.
```cpp=
uint32_t fdt_u32_le2be (const void *addr) {
const uint8_t *bytes = (const uint8_t *) addr;
uint32_t ret = (uint32_t)bytes[0] << 24 |(uint32_t)bytes[1] << 16 |(uint32_t)bytes[2] << 8 |(uint32_t)bytes[3];
return ret;
}
```
- void send_space(int n)
This is for the indention.
```cpp=
void send_space(int n) {
while(n--) uart_send_string(" ");
}
```
3. Implement the fdt_traverse function:
```cpp=
int fdt_traverse(fdt_callback cb,void * _dtb){
uintptr_t dtb_ptr = (uintptr_t) _dtb;
uart_send_string("\ndtb loading at: ");
uart_hex(dtb_ptr);
uart_send_char('\n');
struct fdt_header* header = (struct fdt_header*) dtb_ptr;
uint32_t magic = fdt_u32_le2be(&(header->magic));
---If we get ftb true the magic will fix in 0xd00dfeed （see step 1 fdt_header）---
if (magic != 0xd00dfeed){
uart_send_string("The header magic is wrong\n");
return -1;
}
/*
+-----------------+
| fdt_header | <- dtb_ptr
+-----------------+
| reserved memory |
+-----------------+
| structure block | <- dtb_ptr + header->off_dt_struct (struct_ptr)
+-----------------+
| strings block | <- dtb_ptr + header->off_dt_strings (strings_ptr)
+-----------------+
*/
uintptr_t struct_ptr = dtb_ptr + fdt_u32_le2be(&(header->off_dt_struct));
uintptr_t strings_ptr = dtb_ptr + fdt_u32_le2be(&(header->off_dt_strings));
uint32_t totalsize = fdt_u32_le2be(&header->totalsize);
parse_struct(cb, struct_ptr,strings_ptr,totalsize);
return 1;
}
```
> The structure block and strings block are two essential parts of the flattened device tree (FDT) format used to pass hardware information to the Linux kernel at boot time.
>
> Structure Block: The structure block contains a linearized tree of device nodes and properties. Each node in the tree represents a device or a logical part of a device, and properties are attributes of these devices. The structure block consists of a sequence of tokens that represent the structure and content of the device tree. For example, there are tokens for the start and end of a node, property definitions, and more. The structure block doesn't contain the actual property names; instead, it contains offsets into the strings block where the corresponding property names are stored.
>
> Strings Block: The strings block contains a list of null-terminated strings, which are the property names referred to in the structure block. When a property is defined in the structure block, it includes an offset that points to the location of the property's name in the strings block.
>
> Together, these blocks allow for a compact and efficient representation of the device tree. The structure block provides the structure and values, and the strings block provides the names of the properties. By separating the names and structure, the FDT format avoids repeating property names, making the overall data smaller and faster to parse.
4. Implement `parse_struct`
```cpp=
int parse_struct (fdt_callback cb, uintptr_t cur_ptr, uintptr_t strings_ptr,uint32_t totalsize) {
uintptr_t end_ptr = cur_ptr + totalsize;
while(cur_ptr < end_ptr) {
uint32_t token = fdt_u32_le2be((char *)cur_ptr);
cur_ptr += 4;
switch(token){
case FDT_BEGIN_NODE:
/*
Token type (4 bytes): Indicates that it's an FDT_BEGIN_NODE token.
Node name (variable length, NULL-terminated): Specifies the name of the node being opened.
*/
//uart_send_string("In FDT_BEGIN_NODE\n");
cb(token, (char*)cur_ptr,NULL,0);
cur_ptr += utils_align_up(utils_strlen((char*)cur_ptr),4);
break;
case FDT_END_NODE:
/*
Token type (4 bytes): Indicates that it's an FDT_END_NODE token.
*/
//uart_send_string("In FDT_END_NODE;\n");
cb(token,NULL,NULL,0);
break;
case FDT_PROP: {
/*
Token type (4 bytes): Indicates that it's an FDT_PROP token.
Data length (4 bytes): Specifies the length of the property data (len).
Name offset (4 bytes): Provides the offset of the property name within the strings block (nameoff).
Property data (variable length): Contains the property data itself, the size of which is determined by len.
*/
//uart_send_string("In FDT_PROP \n");
uint32_t len = fdt_u32_le2be((char*)cur_ptr);
cur_ptr += 4;
uint32_t nameoff = fdt_u32_le2be((char*)cur_ptr);
cur_ptr += 4;
//second parameter name here is property name not node name
cb(token,(char*)(strings_ptr + nameoff),(void*)cur_ptr,len);
cur_ptr += utils_align_up(len,4);
break;
}
case FDT_NOP:
//uart_send_string("In FDT_NOP\n");
cb(token,NULL,NULL,0);
break;
case FDT_END:
//uart_send_string("In FDT_END\n");
cb(token,NULL,NULL,0);
return 0;
default:;
return -1;
}
}
return -1;
}
```
5. Implement the initramfs_callback function:
```cpp=
void get_cpio_addr(int token,const char* name,const void* data,uint32_t size){
UNUSED(size);
if(token==FDT_PROP && utils_string_compare((char *)name,"linux,initrd-start")){
cpio_addr = (char*)(uintptr_t)fdt_u32_le2be(data);
uart_send_string("cpio address is at: ");
uart_hex((uintptr_t)fdt_u32_le2be(data));
uart_send_char('\n');
}
}
```
6. Implement print_dtb callback function:
```cpp=
void print_dtb(int token, const char* name, const void* data, uint32_t size) {
UNUSED(data);
UNUSED(size);
switch(token){
case FDT_BEGIN_NODE:
uart_send_string("\n");
send_space(space);
uart_send_string((char*)name);
uart_send_string("{\n ");
space++;
break;
case FDT_END_NODE:
uart_send_string("\n");
space--;
if(space >0) send_space(space);
uart_send_string("}\n");
break;
case FDT_NOP:
break;
case FDT_PROP:
send_space(space);
uart_send_string((char*)name);
break;
case FDT_END:
break;
}
}
```
# Other Labs
[Operating System Capstone - Lab0](https://hackmd.io/@OJo2ruXGShKdpuewtwzZcQ/S104l7ZS3)
[Operating System Capstone - Lab1](https://hackmd.io/@OJo2ruXGShKdpuewtwzZcQ/S104l7ZS3)
[Operating System Capstone - Lab2](https://hackmd.io/@OJo2ruXGShKdpuewtwzZcQ/Hy6j7lzrn)
[Operating System Capstone - Lab3](https://hackmd.io/@OJo2ruXGShKdpuewtwzZcQ/r1WP_BrX3)
[Operating System Capstone - Lab4](https://hackmd.io/@OJo2ruXGShKdpuewtwzZcQ/SJYrXgY93)
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet