# 1. Hello World OS

## ENV SETUP

### 安裝一臺 Debian Workstation
0. 灌系統
1. 安裝開發環境，筆者使用的是 VIM

### 安裝測試環境：
0. 安裝 git
1. 安裝 risc-v 工具鏈

    sudo apt-get install gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

2. 安裝 qemu

    sudo apt install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev \
                     gawk build-essential bison flex texinfo gperf libtool patchutils bc \
                     zlib1g-dev libexpat-dev \
                     libglib2.0-dev libpixman-1-dev
    git clone https://github.com/qemu/qemu
    
    cd qemu
    ./configure --target-list=riscv32-softmmu,riscv64-softmmu
    make
    sudo make install

### 編譯一個現成的 OS

在安裝完 qemu 之後，我們可以嘗試編譯并且執行一個 risc-v 的程式。
筆者這邊選擇的 OS 是基於 risc-v 的教學型 OS - [xv6](https://github.com/mit-pdos/xv6-riscv)。

git clone https://github.com/mit-pdos/xv6-riscv.git
cd xv6-riscv
make qemu


可以按下 ctrl + a 后按 x 離開 qemu。

感興趣的可以去看一下 Makefile 當中他是如何呼叫 qemu 的，我們留到稍後敘述。

## 來寫我們的小小 OS

### os.c

volatile char *uart = (volatile char*) 0x10000000;

void print(const char *str) {
    while (*str) {
        *uart = *(str++);
    }
}

int os_main(void) {
    print("Hello, QEMU!\n");
    while (1) {}
    return 0;
}

### bootloader.s

.section .text.start

.globl _start
_start:
    csrr   t0, mhartid
    lui    t1, 0
    bne    t0, t1, park
    # 僅讓一核心執行我們的程式，其他進入 park 空等

    la sp, stack_top
    call os_main

park:
    wfi
    j      park

### link.ld

OUTPUT_ARCH( "riscv" )
ENTRY( _start )

MEMORY
{
  ram   (wxa!ri) : ORIGIN = 0x80000000, LENGTH = 128M
}

PHDRS
{
  text PT_LOAD;
  data PT_LOAD;
  bss PT_LOAD;
}

SECTIONS
{
  .text : {
    *(.text.start);
    PROVIDE(_text_start = .);
    *(.text.init) *(.text .text.*)
    PROVIDE(_text_end = .);
  } >ram AT>ram :text

  . = ALIGN(0x1000);
  etext = .;

  .data : {
    . = ALIGN(4096);
    PROVIDE(_data_start = .);
    *(.sdata .sdata.*) *(.data .data.*)
    PROVIDE(_data_end = .);
  } >ram AT>ram :data

  .bss :{
    PROVIDE(_bss_start = .);
    *(.sbss .sbss.*) *(.bss .bss.*)
    PROVIDE(_bss_end = .);
  } >ram AT>ram :bss

  PROVIDE(_memory_start = ORIGIN(ram));
  PROVIDE(_memory_end = ORIGIN(ram) + LENGTH(ram));
  . += 0x8000;
  stack_top = .;
  end = .;
}

### Makefile

SHELL = /bin/sh
ARCH = riscv64-linux-gnu
CC = $(ARCH)-gcc
LD = $(ARCH)-ld
OBJCOPY = $(ARCH)-objcopy
SDIR = src
BDIR = build
OBJCOPY = $(ARM)-objcopy
S_SRCS = $(wildcard $(SDIR)/*.s)
C_SRCS = $(wildcard $(SDIR)/*.c)
S_OBJS = $(S_SRCS:$(SDIR)/%.s=$(BDIR)/%_asm.o)
C_OBJS = $(C_SRCS:$(SDIR)/%.c=$(BDIR)/%.o)


all: clean kernel.img

kernel.img: kernel.elf
        $(OBJCOPY) kernel.elf -I binary kernel.img

kernel.elf: $(S_OBJS) link.ld $(C_OBJS)
        $(LD) -T link.ld -o kernel.elf $(S_OBJS) $(C_OBJS)

$(BDIR)/%.o: $(SDIR)/%.c
        $(CC) $(CFLAGS) -c $< -o $@

$(BDIR)/%_asm.o: $(SDIR)/%.s
        $(CC) $(SFLAGS) -c $< -o $@

clean:
        rm -f $(BDIR)/*_asm.o $(BDIR)/*.o kernel.elf kernel.img

run: all
        qemu-system-riscv64 -M virt -kernel kernel.img -bios none -serial stdio -display none

### 目錄圖如下


### 測試并執行

make run


## 撰寫簡單功能的 printf

### printf.h

#include <stdarg.h>

void putchar(char c);
void print_int(long long value);
void printf(const char *format, ...);

### printf.c

#include "printf.h"

volatile char *uart = (volatile char*) 0x10000000;

void putchar(char c) {
    *uart = c;
}

void print_int(long long value) {
    if (value == 0) {
        putchar('0');
        return;
    }

    if (value < 0) {
        putchar('-');
        value = -value;
    }

    char buffer[20];
    int i = 0;

    while (value) {
        buffer[i++] = (value % 10) + '0';
        value /= 10;
    }

    while (i-- > 0) {
        putchar(buffer[i]);
    }
}

void printf(const char *format, ...) {
    va_list args;
    va_start(args, format);
    while (*format) {
        if (*format == '%') {
            format++;
            switch (*format) {
                case 's': {
                    char *str = va_arg(args, char*);
                    while (*str) {
                        putchar(*str++);
                    }
                    break;
                }
                case 'd': {
                    int value = va_arg(args, int);
                    print_int(value);
                    break;
                }
                default:
                    putchar(*format);
                    break;
            }
        } else {
            putchar(*format);
        }
        format++;
    }
    va_end(args);
}

### os.c

#include "printf.h"

int os_main(void) {
    printf("%s, %d\n", "Hello World", 8964);
    while(1);
    return 0;
}

### Makefile

新增編譯 header file 的部分。

SHELL = /bin/sh
ARCH = riscv64-linux-gnu
CC = $(ARCH)-gcc
LD = $(ARCH)-ld
OBJCOPY = $(ARCH)-objcopy
IDIR = inc
SDIR = src
BDIR = build
CFLAGS = -fno-builtin -nostdlib -Wall -mcmodel=medany -g -I $(IDIR) -O0
SFLAGS = -g -I $(IDIR)
OBJCOPY = $(ARM)-objcopy
S_SRCS = $(wildcard $(SDIR)/*.s)
C_SRCS = $(wildcard $(SDIR)/*.c)
S_OBJS = $(S_SRCS:$(SDIR)/%.s=$(BDIR)/%_asm.o)
C_OBJS = $(C_SRCS:$(SDIR)/%.c=$(BDIR)/%.o)


all: clean kernel.img

kernel.img: kernel.elf
        $(OBJCOPY) kernel.elf -I binary kernel.img

kernel.elf: $(S_OBJS) link.ld $(C_OBJS)
        $(LD) -T link.ld -o kernel.elf $(S_OBJS) $(C_OBJS)

$(BDIR)/%.o: $(SDIR)/%.c
        $(CC) $(CFLAGS) -c $< -o $@

$(BDIR)/%_asm.o: $(SDIR)/%.s
        $(CC) $(SFLAGS) -c $< -o $@

clean:
        rm -f $(BDIR)/*_asm.o $(BDIR)/*.o kernel.elf kernel.img

run: all
        qemu-system-riscv64 -M virt -kernel kernel.img -bios none -serial stdio -display none

### 目錄結構

## 記憶體分配

### link.ld

將 link.ld 修改為如下：

/* reserve 0x8000 bytes for stack */
. += 0x8000;
stack_top = .;
end = .;
. += 0x200;
_heap_start = .;

PROVIDE(_heap_start = _bss_end);
PROVIDE(_heap_size = _memory_end - _heap_start);

### mem.s

因為我們在 C 是使用 void* 來存取 `_heap_start`，而我們使用的虛擬機是 64 位元的，因此需要 2 個 word（8 bytes）。

.section .rodata
.global HEAP_START
HEAP_START: .word _heap_start
            .word 0x0

.global HEAP_SIZE
HEAP_SIZE: .word _heap_size

.global TEXT_START
TEXT_START: .word _text_start

.global TEXT_END
TEXT_END: .word _text_end

.global DATA_START
DATA_START: .word _data_start

.global DATA_END
DATA_END: .word _data_end

.global BSS_START
BSS_START: .word _bss_start

.global BSS_END
BSS_END: .word _bss_end

### mem.h

#define PAGE_SIZE 4096
#include "printf.h"
#include <stddef.h>
#include <stdint.h>

extern uint32_t TEXT_START;
extern uint32_t TEXT_END;
extern uint32_t DATA_START;
extern uint32_t DATA_END;
extern uint32_t BSS_START;
extern uint32_t BSS_END;
extern void    *HEAP_START;
extern uint32_t HEAP_SIZE;

struct Page {
    int8_t flag;
    void* ptr;
};

void page_init();
void printMEM(int x);
void* malloc(size_t size);
int free(void *ptr);

### mem.c

這邊簡單實作了一個 malloc 函式，沒有用 linked-list 作優化，每次都是暴力搜索可用區段。

#include "mem.h"

static void *_alloc_start = 0;
static void *_alloc_end = 0;
static uint32_t _num_pages = 0;

void _clear(void* ptr, size_t size) {
    unsigned char* byte_ptr = (unsigned char*)ptr;
    for(size_t i = 0; i < size; i++) {
        byte_ptr[i] = 0;
    }
}

void page_init() {
    _num_pages = HEAP_SIZE / (PAGE_SIZE + sizeof(struct Page));
    printf("HEAP_START =0x%x, HEAP_SIZE = 0x%x, num of pages = %d\n", HEAP_START, HEAP_SIZE, _num_pages);

    _alloc_start = HEAP_START + _num_pages * sizeof(struct Page);
    _alloc_end = _alloc_start + (PAGE_SIZE * _num_pages);

    struct Page *page = (struct Page *)HEAP_START;
    /* printf("%x\n", page -> flag); */
    for (uint32_t i = 0; i < _num_pages; i++)
    {
        /* printf("%x\n", page->flag); */
        page->flag = 0;
        page->ptr = _alloc_start + i * PAGE_SIZE;
        page++;
    }

    printf("HEAP:   0x%x -> 0x%x\n", _alloc_start, _alloc_end);
}

void printMEM(int x) {
    struct Page *page = (struct Page *)HEAP_START;
    for(int i = 0; i < x; i++, page++) {
        printf("| %d ", page -> flag);
    }
    printf("|\n");
}

void* malloc(size_t size) {
    int N = (size + PAGE_SIZE - 1) / PAGE_SIZE; // ceil
    struct Page *page = (struct Page *)HEAP_START;
    for(int i = 0; i < _num_pages; i++, page++) {
        struct Page *start_pos = page;
        int j;
        for(j = 0; j < N; j++, i++, page++) {
            if(page->flag != 0) {
                break;
            }
        }
        if(j == N) {
            page = start_pos;
            for(int j = 0; j < N; j++, page++) {
                page->flag = 1;
            }
            page--; page->flag = 2;
            return start_pos->ptr;
        }
    }
    return 0x0;
}

int free(void* ptr) {
    struct Page *page = (struct Page *)HEAP_START;
    for(int i = 0; i < _num_pages; i++, page++) {
        if(page->ptr == ptr) break;
        if(page->ptr > ptr) return 1;
    }
    while(page->flag == 1) {
        _clear(page->ptr, PAGE_SIZE);
        page->flag = 0;
        page++;
    }
    _clear(page->ptr, PAGE_SIZE);
    page->flag = 0;
    return 0;
}

### os.c

#include "printf.h"
#include "mem.h"

int os_main(void) {
    page_init();
    int* arr1 = malloc(sizeof(int) * 4096);
    int* arr2 = malloc(sizeof(int) * 4096);

    printMEM(10);
    printf("0x%x, 0x%x\n", arr1, arr2);
    free(arr1);
    printMEM(10);
    printf("0x%x 0x%x 0x%x\n", malloc(sizeof(int) * 1024), malloc(sizeof(int) * 1024), malloc(sizeof(int) * 1024));
    printMEM(10);
    while(1);
    return 0;
}

## 參考資料

1. ChatGPT
2. [s094392/riscv-bare-metal](https://github.com/s094392/riscv-bare-metal/tree/master)
3. [10分鐘讀懂 linker scripts](https://blog.louie.lu/2016/11/06/10%E5%88%86%E9%90%98%E8%AE%80%E6%87%82-linker-scripts/)
4. [cccriscv/mini-riscv-os](https://github.com/cccriscv/mini-riscv-os/)

## GitHub

[REPO](https://github.com/LeeLin2602/lin-os-study)