Try   HackMD
tags: OS

Raspberry-pi-os

reference:
https://github.com/s-matyukevich/raspberry-pi-os

Bootloader before the kernel image

為了避免頻繁的插、拔 SD card 進行 image 的更新，在 image 最一開始設置一個 bootloader，監聽 UART 一定的秒數，秒數內能夠進行新的 kernel image upload

樹莓派開始接收數據，並將數據保存到 sd 卡上第一個 fat32 分區的 root，覆蓋掉原有的kernel.img

rpi bootloader

FSBL（第一階段bootloader）位於ROM，由各個hardware vendor來實現。
它會加載一個image到內存（這個image可以是第二階段bootloader，例如grub、lilo等，也可以是kernel），並將 CPU 的控制權移交

UART

  • SoC and Host communication
  • recive/put data 都是透過 register AUX_MU_IO [read/write]
  • register AUX_MU_LSR[1] 表示有無數據可讀
  • register AUX_MU_LSR[6] 表示數據是否已滿，能否繼續寫入

sd和fat32文件系统

RPI SD card spec.

sdhci 0x20300000
sdhost 0x20202000

FatFs

timer

使用 system timer

#define MMIO_BASE       0x3F000000U
#define SYSTIMER_BASE   (MMIO_BASE + 0x3000)

#define SYSTIMER_CS     (SYSTIMER_BASE+0x0)
#define SYSTIMER_CNT    (SYSTIMER_BASE+0x4)
#define SYSTIMER_CMP    (SYSTIMER_BASE+0xC)
    

uint64_t systimer_counter()
{
    return get32(SYSTIMER_CNT);
}

void systimer_sleep_one_second()
{
    uint64_t current = systimer_counter();
    while(1) if(systimer_counter() - current > 1000000) break;
}

void systimer_sleep_quarter_second()
{
    uint64_t current = systimer_counter();
    while(1) if(systimer_counter() - current > 250000) break;
}

power

#define PM_WDOG_MAGIC   0x5a000000
#define PM_RSTC_FULLRST 0x00000020

void reset()
{
    unsigned int r;
    // trigger a restart by instructing the GPU to boot from partition 0
    r = (*PM_RSTS) & ~0xfffffaaa;
    *PM_RSTS = PM_WDOG_MAGIC | r;   // boot from partition 0
    *PM_WDOG = PM_WDOG_MAGIC | 10;
    *PM_RSTC = PM_WDOG_MAGIC | PM_RSTC_FULLRST;
}

get image then save to SD card

    // Waiting
    for (int i = 0; i < 24; i++) {
        char c;
        systimer_sleep(1);

        if(uart_dataready()) {
            // get image size
            uint32_t size = 0;
            for(int i=0; i<4; ++i)
            {
                c = uart_getc();
                uart_send(c);
                size = size << 8;
                size = size + c;
            }

            // save the image data
            char* data = (char *)0x90000;
            char* bp = data;
            for(int s=0; s<size; ++s) {
                *bp = uart_getc();
                uart_send(*bp);
                bp += 1;
            }
            systimer_sleep(1);
            uart_send('#');
            
            // Overwrite the original image file 
            FIL fdst;
            FRESULT res = f_open(&fdst, "0:/kernel8.img", FA_CREATE_ALWAYS | FA_WRITE);
            if (res != FR_OK)
            {
                systimer_sleep(4);
                reset();
                return;
            }

            uint32_t sizewrite = 0;
            res = f_write(&fdst, (void *)data, size, (unsigned int*)&sizewrite);
            f_close(&fdst);
        }
    }

Kernel Initialization (mini uart & GPIO)

Processor Initialization

Exception Level

ARMv8 定義了四個例外層級。EL0-EL3，數字越大權限(privilege)越高。

  • EL0 用於應用程式。無特權模式(unprivileged)
    作業系統為了 process 的隔離，所以要負責例外層級的處理。
    user process 不應該能夠 access 到其他 process data。 為了達到上述行為，作業系統始终在 EL0 上執行每個 user porcess。
  • EL1 用於作業系統本身。作業系統核心模式(OS kernel mode)
  • EL2 用於使用虛擬機監控程式的場景。虛擬機器監視器模式(Hypervisor mode)
  • EL3 TrustZone® monitor mode

查詢當前的 Exception Level

確認 CurrentEL system register (utils.S)

.globl get_el
get_el:
    mrs x0, CurrentEL
    lsr x0, x0, #2
    ret

在尚未進行任何切換動作，當前的 Exception Level 應該為 3

int el = get_el();
printf("Exception level: %d \r\n", el);

Exception level：3

切換當前的 Exception Level

在 ARM architecture 下只有當發生異常時，才能夠更改當前的 EL。執行某些非法指令(例如: access 不存在的 address)則可以觸發。另外還有 interrupts 也被視為特殊類型的異常。
每當有異常時就會觸發下列的動作

  1. 當前指令的 address 保存在 ELR_ELn register (Exception link register)
  2. 當前處理器狀態保存在 SPSR_ELn register (Saved Program Status Register)
  3. exception handler 執行所需的任何工作
  4. exception handler 呼叫 eret 指令。該指令從 SPSR_ELn 恢復處理器狀態，並且從保存在 ELR_ELn register 中的 address 開始恢復執行

需要注意的點是 exception handler 並沒有一定要返回到異常所源自的相同位置。若有必要，exception handler 能夠對 ELR_ELn & SPSR_ELn 的內容進行修改。

切換到 EL1

EL1 層具有執行所有常見 OS 任務的正確特權(privilege)集合，所以將作業系統切換到 EL1 是很直觀的

檢視 boot.S

master:
    ldr    x0, =SCTLR_VALUE_MMU_DISABLED
    msr    sctlr_el1, x0        

    ldr    x0, =HCR_VALUE
    msr    hcr_el2, x0

    ldr    x0, =SCR_VALUE
    msr    scr_el3, x0

    ldr    x0, =SPSR_VALUE
    msr    spsr_el3, x0

    adr    x0, el1_entry        
    msr    elr_el3, x0

    eret

如上 master function 主要進行一些 system register 的設置

  • SCTLR_EL1, System Control Register (EL1), Page 2654 of AArch64-Reference-Manual.

    • SCTLR_I_CACHE_DISABLED (0 << 12) 與 SCTLR_D_CACHE_DISABLED (0 << 2) 禁用指令與數據 cache
    • SCTLR_MMU_DISABLED (0 << 0) 禁用 MMU
    ​​​​#define SCTLR_RESERVED                  (3 << 28) | (3 << 22) | (1 << 20) | (1 << 11)
​​​​#define SCTLR_EE_LITTLE_ENDIAN          (0 << 25)
​​​​#define SCTLR_EOE_LITTLE_ENDIAN         (0 << 24)
​​​​#define SCTLR_I_CACHE_DISABLED          (0 << 12)
​​​​#define SCTLR_D_CACHE_DISABLED          (0 << 2)
​​​​#define SCTLR_MMU_DISABLED              (0 << 0)
​​​​#define SCTLR_MMU_ENABLED               (1 << 0)

​​​​#define SCTLR_VALUE_MMU_DISABLED        (SCTLR_RESERVED | SCTLR_EE_LITTLE_ENDIAN | SCTLR_I_CACHE_DISABLED | SCTLR_D_CACHE_DISABLED | SCTLR_MMU_DISABLED)

  • HCR_EL2, Hypervisor Configuration Register (EL2), Page 2487 of AArch64-Reference-Manual.

    • 該 register 31 bit 控制 EL1 的執行狀態。0 為 AArch32，1 為 AArch64
    ​​​​#define HCR_RW            (1 << 31)

​​​​#define HCR_VALUE         HCR_RW

  • SCR_EL3, Secure Configuration Register (EL3), Page 2648 of Arch64-Reference-Manual.

    • 該 register 負責 security 的設置
    ​​​​#define SCR_RESERVED    (3 << 4)
​​​​#define SCR_RW          (1 << 10)
​​​​#define SCR_NS          (1 << 0)

​​​​#define SCR_VALUE       (SCR_RESERVED | SCR_RW | SCR_NS)

  • SPSR_EL3, Saved Program Status Register (EL3), Page 389 of Arch64-Reference-Manual.

    • 該 register 保存了處理器狀態，執行 eret 後會恢復該狀態。當 EL3 發生異常會自動保存 spsr_el3。而其為 writeable，所以可以透過重寫它來達成切換 EL 的目的
    • SPSR_MASK_ALL (7 << 6) 切換成 EL1 後，所有類型的中斷都將被禁用(masked)
      • 6 ~ 8 bit 分別為 FIQ mask bit, IRQ mask bit, SError interrupt mask bit
    • SPSR_EL1h (5 << 0) 設置為 EL1h 模式
      • 0 bit 用來選擇 SP。 "0 means the SP is always SP0" & "1 means the exception SP is determined by the EL"
    ​​​​#define SPSR_MASK_ALL       (7 << 6) // change EL to EL1
​​​​#define SPSR_EL1h           (5 << 0) // EL1h mode means that we are using EL1 dedicated stack pointer

​​​​#define SPSR_VALUE          (SPSR_MASK_ALL | SPSR_EL1h)

  • ELR_EL3, Exception Link Register (EL3), Page 351 of AArch64-Reference-Manual.

    • elr_el3 保存了 address，在執行 eret 後則會返回到該 address
    • 將 el1_entry (即執行任務的 function) 寫入上述 address
    ​​​​    adr    x0, el1_entry        
​​​​    msr    elr_el3, x0

​​​​    eret                

    ​​​​el1_entry:
​​​​    adr x0, bss_begin
​​​​    adr x1, bss_end
​​​​    sub x1, x1, x0
​​​​    bl memzero

​​​​    mov sp, #LOW_MEMORY
​​​​    bl kernel_main

Exercises

  1. Instead of jumping directly from EL3 to EL1, try to get to EL2 first and only then switch to EL1.
  2. Remove 'general-regs-only' flag.

Interrupt Handing

Interrupt & Exception

ARM.v8 architecture 有四種類型的異常

  • Synchronous exception
    由目前執行的指令引起(例如 str 將數據寫入不存在的記憶體位置)
  • IRQ (Interrupt Request)
    永遠是 asynchronous，意味著它與當前執行的指令無關。與 Synchronous exception 相反，它始終是由 external hardware 產生，而不是處理器本身生成的
  • FIQ (Fast Interrupt Request)
    為優先處理異常的目的而存在。能夠將部分中斷配置成 normal，其他中斷配置成 fast。Linux 中不使用 FIQ。
  • SError (System Error)
    與 IRQ, FIQ 一樣為 asynchronous，由 external hardware 產生。與 IRQ, FIQ 不同的是它永遠表示某種錯誤情況

Exception vectors

每個異常類型都需要有自己的 handler。以異常 handler 的角度來看有四種執行狀態(execution states)，以在 EL1 工作，執行狀態可以定義如下

  • EL1t Exception is taken from EL1(EL1 與 EL0 共享 stack pointer)
    • 當 SPSel register 值為 0 時會發生
  • EL1h Exception is taken from EL1
    • 當 SPSel register 值為 1 時會發生(也是我們當前使用的 mode)
  • EL0_64 Exception is taken from EL0 executing in 64-bit mode
  • EL0_32 Exception is taken from EL0 executing in 32-bit mode

總共需要定義 16 個 exception handler(4 exception levels X 4 execution states)，而一個保存所有 exception handler address 的特殊結構稱為 exception vector table (exception table)

參考 page 1876 of the AArch64-Reference-Manual，每個異常佔用 0x80 bytes

透過以下 macro ventry 建立異常 exception table 中的 entries

  • 不直接在異常向量內部處理異常，而是跳轉到 macro 所提供的標籤
  • 使用 .align 7 的目的是將所有的異常向量 offset 對齊 0x80 bytes(如上圖所示)
    .macro    ventry    label
    .align    7
    b    \label
    .endm

entry.S 定義了 16 個異常向量。目前雖然只處理 EL1h 的 IRQ，仍舊需要定義總共 16 個的 handler，目的是希望看到有意義的錯誤訊息，避免出現問題。針對目前不關注的錯誤型態透過 macro handle_invalid_entry 來處理

  • 會準備三個參數(x0 ~ x2)，然後呼叫 show_invalid_entry_message
    • x0: 主用使用 entry.h中所定義的 0 ~ 15 的編號(index)，使得能夠準確的知道執行了哪個異常 process
    • x1: 最重要的參數，ESR(Exception Syndrome Register)實際來自 esr_el1 register，它包含了有關導致異常的原因與詳細訊息
    • x2: 為在同步異常的情況下很重要的關鍵，它來自前面有提過的 elr_el1 register，其中包含生成異常時已執行的指令 address。在同步異常中，該指令也就是導致異常的指令
    • 最後透過 show_invalid_entry_message 能夠在畫面中顯示當前的異常
    .macro handle_invalid_entry type
    kernel_entry
    mov    x0, #\type
    mrs    x1, esr_el1
    mrs    x2, elr_el1
    bl    show_invalid_entry_message
    b    err_hang
    .endm

Saving register state

當 exception handler 處理完成後會希望所有 general register 保持與生成異常前相同的值，若不實現此功能可能會產生不可預測的錯誤。於是透過 macro kernel_entry 來實現

  • 將 register x0 - x30 保存到 stack
  • 有對應的 kernel_exit 從 stack 恢復先前保存的 processor 狀態
	.macro	kernel_entry   
	sub	sp, sp, #S_FRAME_SIZE
	stp	x0, x1, [sp, #16 * 0]
	stp	x2, x3, [sp, #16 * 1]
	stp	x4, x5, [sp, #16 * 2]
	stp	x6, x7, [sp, #16 * 3]
	stp	x8, x9, [sp, #16 * 4]
	stp	x10, x11, [sp, #16 * 5]
	stp	x12, x13, [sp, #16 * 6]
	stp	x14, x15, [sp, #16 * 7]
	stp	x16, x17, [sp, #16 * 8]
	stp	x18, x19, [sp, #16 * 9]
	stp	x20, x21, [sp, #16 * 10]
	stp	x22, x23, [sp, #16 * 11]
	stp	x24, x25, [sp, #16 * 12]
	stp	x26, x27, [sp, #16 * 13]
	stp	x28, x29, [sp, #16 * 14]
	str	x30, [sp, #16 * 15] 
	.endm

Setting the vector table

準備完 exception table 後需將其 address 設置於 vbar_el1 (Vector Base Address Register)

.globl irq_vector_init
irq_vector_init:
    adr    x0, vectors        // load VBAR_EL1 with virtual
    msr    vbar_el1, x0        // vector table address
    ret

Masking / Unmasking interrupts

在特定的程式碼段絕對不能被異步中斷攔截。例如 kernel_entry 中進行 general register 的狀態保存，若執行到一半被攔截中斷，processor 的狀態將會被覆蓋、遺失。因此，每當執行 exception handler 時 processor 會自動禁用所有類型的 interrupts

irq.S 中的兩個函式負則 masking & unmasking

.globl enable_irq
enable_irq:
    msr    daifclr, #2
    ret

.globl disable_irq
disable_irq:
    msr    daifset, #2
    ret

ARM processor state 有 4 位，負責控制不同類型中斷的 mask 狀態

  • D: Masks debug exceptions. 為特殊類型的 synchronous exceptions
  • A: Masks SErrors。之所以命名為 A 是因為 SError 也被稱為 asynchronous aborts
  • I: Masks IRQs
  • F: Masks FIQs

daifclr & daifset 都設置 #2 的原因是目前只設置 I 位

Configuring interrupt controller

interrupt controller 能夠啟用/禁用 hardware 發送的 interrupt。

  • 通過 ENABLE_IRQS_1 register 控制啟用/禁用 interrupts


...
#define ENABLE_IRQS_1		(PBASE+0x0000B210)
#define ENABLE_IRQS_2		(PBASE+0x0000B214)
...
#define SYSTEM_TIMER_IRQ_0	(1 << 0)
#define SYSTEM_TIMER_IRQ_1	(1 << 1)
...

void enable_interrupt_controller()
{
    put32(ENABLE_IRQS_1, SYSTEM_TIMER_IRQ_1);
}

Generic IRQ handler

在 handler 中透過 IRQ_PENDING_1 register 來獲取 0-31 的中斷狀態。透過該 register 能夠檢查當前的中斷是由 timer 產生或者其他 devices，進一步呼叫特定的中斷 handler。
多個中斷可能同時產生，因此每個中斷的 handler 必須確認是否已經完成對於中斷的處理。

void handle_irq(void)
{
    unsigned int irq = get32(IRQ_PENDING_1);
    switch (irq) {
        case (SYSTEM_TIMER_IRQ_1):
            handle_timer_irq();
            break;
        default:
            printf("Unknown pending irq: %x\r\n", irq);
    }
}

Timer(System Timer) initialization

Raspberry Pi 的 system timer 具有連接到中斷控制器的 4 條中斷線和 4 個相應的 compare register。當計數器的值等於儲存在 compare register 之一中的值時，就會觸發相對應的中斷。因此需要對 compare register 之一進行非零值的初始化。

void timer_init(void)
{
    curVal = get32(TIMER_CLO);
    curVal += interval;
    put32(TIMER_C1, curVal); // set first time of interrupt
}

Handling timer interruputs

第一步更新下一次觸發中斷的時間。
再來將 1 寫入 TIMER_CS register(稱為 "Timer Control/Status" register)，用於確認來自 4 條中斷線中第 1 條的中斷

void handle_timer_irq( void )
{
    curVal += interval;
    put32(TIMER_C1, curVal);
    put32(TIMER_CS, TIMER_CS_M1);
    printf("Timer interrupt received\n\r");
}

Exercises

  1. Use local timer instead of the system timer to generate processor interrupts.
  2. Handle MiniUART interrupts.

Processor Scheduler

Process scheduling 是核心任務之一。Scheduling 指的是一個 OS 應該要能夠實現不同 processes 共享 CPU time。其中最困難的事一個 process 不知道 scheduling 的發生，也就是説它將自己視為唯一佔用 CPU 的 process

task_struct

如果要管理 processes，首先要做的就是建立一個描述 process 的 struct，而在 Linux 中就具有這樣的 struct，它稱為 task_struct。參考與模仿 Linux 中的實現方式如下

這個 struct 具有以下內容：

  • cpu_context
    • 其為另一個獨立的 struct，其中包含正在切換的任務之間可能不同的所有 register 之值。
    • 不保存所有的 register，只保存了 x19-x30(fp: x29, pc: x30) 和 sp 的原因是根據 ARM 的調用約定，x0-x18 registers 可以被調用的函式覆蓋，所以不得假定這些 registers value 在調用結束後仍然存在
  • state
    • 當前運行任務的狀態(執行、等待…)
  • counter
    • 用於確認當前任務運行的時間，timer tick 時會減 1，到 0 時會切換其他任務
  • priority
    • 安排新任務時將 priority 複製到 counter
    • 通過優先級的設定，能夠調整、安排任務相對其他任務獲得的 processor time
  • preempt_count
    • 若該值設置為非零值，表示當前任務正在值行不可中斷的功能。或忽略該任務期間發生的 timer tick，而且不會 rescheduling
struct cpu_context {
    unsigned long x19;
    unsigned long x20;
    unsigned long x21;
    unsigned long x22;
    unsigned long x23;
    unsigned long x24;
    unsigned long x25;
    unsigned long x26;
    unsigned long x27;
    unsigned long x28;
    unsigned long fp;
    unsigned long sp;
    unsigned long pc;
};

struct task_struct {
    struct cpu_context cpu_context;
    long state;
    long counter;
    long priority;
    long preempt_count;
};

kernel 啟動後只有一個任務是執行中的狀態，也就是 kernel_main function。稱其為 "init task" ，在開啟 scheduling 之前，首先必須填充 "init task" 相對應的 task_struct

#define INIT_TASK \
/*cpu_context*/	{ {0,0,0,0,0,0,0,0,0,0,0,0,0}, \
/* state etc */	0,0,1, 0 \
}

static struct task_struct init_task = INIT_TASK;

所有任務存放在 task。另外透過一個 struct pointer current 指向 init task

#define NR_TASKS 64

struct task_struct *task[NR_TASKS] = {&(init_task), };
struct task_struct *current = &(init_task);

kernel_main function

需要關注的重點

  • copy_process() 使用兩個參數，新 thread 中要執行的函式以及傳遞給該函式的參數。copy_process 會建立新的 task_struct 使其能夠被 scheduler 調度
  • schedule() 是主要的調度 process 功能。它檢查是否有新任務需要搶佔當前的任務。timer interrupt handler 也會呼叫 schedule
void kernel_main(void)
{
    uart_init();
    init_printf(0, putc);
    irq_vector_init();
    timer_init();
    enable_interrupt_controller();
    enable_irq();

    int res = copy_process((unsigned long)&process, (unsigned long)"12345");
    if (res != 0) {
        printf("error while starting process 1");
        return;
    }
    res = copy_process((unsigned long)&process, (unsigned long)"abcde");
    if (res != 0) {
        printf("error while starting process 2");
        return;
    }

    while (1){
        schedule();
    }
}

呼叫了兩次 copy_process() 都使用 process 函式傳入。process 會不斷 print 出傳入的參數

void process(char *array)
{
    while (1){
        for (int i = 0; i < 5; i++){
            uart_send(array[i]);
            delay(100000);
        }
    }
}

Memory allocation

每個任務都應該具有屬於自己的獨立 stack，因此在建立新任務需要進行正確的記憶體分配。透過以下的方法進行記憶體分配

  • 分配器與記憶體頁面搭配使用
  • mem_map array 保存了每一個記憶體頁面的使用狀態。每當要分配新的頁面時 loop through 這個 array 獲取第一個空閒頁面
  • HIGH_MEMORY: 系統中的記憶體總量為 1 GB 減去最後的 device registers 保留位
  • LOW_MEMORY: 前 4 MB 的記憶體保留給 kernel image 和 init task。所有的 memory allocation 由此開始
  • PAGE_SIZE 定義為 4 KB
#define PAGE_SHIFT	 	12
#define TABLE_SHIFT 		9
#define SECTION_SHIFT		(PAGE_SHIFT + TABLE_SHIFT)

#define PAGE_SIZE   		(1 << PAGE_SHIFT) // 4 KB
#define SECTION_SIZE		(1 << SECTION_SHIFT)	

#define LOW_MEMORY             (2 * SECTION_SIZE)
#define HIGH_MEMORY            PBASE

#define PAGING_MEMORY          (HIGH_MEMORY - LOW_MEMORY)
#define PAGING_PAGES           (PAGING_MEMORY / PAGE_SIZE)

static unsigned short mem_map [ PAGING_PAGES ] = {0,};

unsigned long get_free_page()
{
    for (int i = 0; i < PAGING_PAGES; i++){
        if (mem_map[i] == 0){
            mem_map[i] = 1;
            return LOW_MEMORY + i*PAGE_SIZE;
        }
    }
    return 0;
}

void free_page(unsigned long p){
    mem_map[p / PAGE_SIZE] = 0;
}

Creating a new task

透過 copy_process 來建立新任務

  • preempt_diable() 禁用"搶佔"，避免在執行過程被切換到其他任務
  • 透過 get_free_page() 分配一個尚未被使用的 page。在此 page 底部放置新任務的 task_struct
  • 分配好 task_struct 後，初始化其屬性
    • priority 和 counter 根據當前任務的 priority 來設置
    • state 設置為 TASK_RUNNING，表示新任務已經準備好開始
    • preempt_count 設置為 1，表示在執行任務之後，在完成特定初始化工作之前，不進行任務的切換
  • 初始化 cpu_context
    • 將 stack 設置在新 page 的頂端 (THEAD_SIZE = PAGE_SIZE = 4 KB)
    • pc 設置為 ret_from_fork function
  • 將新創的任務加入到 task array
  • 創建完成後，將當前任務的搶佔開啟
int copy_process(unsigned long fn, unsigned long arg)
{
    preempt_disable();
    struct task_struct *p;

    p = (struct task_struct *) get_free_page();
    if (!p)
        return 1;
    p->priority = current->priority;
    p->state = TASK_RUNNING;
    p->counter = p->priority;
    p->preempt_count = 1; //disable preemtion until schedule_tail

    p->cpu_context.x19 = fn;
    p->cpu_context.x20 = arg;
    p->cpu_context.pc = (unsigned long)ret_from_fork;
    p->cpu_context.sp = (unsigned long)p + THREAD_SIZE;
    int pid = nr_tasks++;
    task[pid] = p;
    preempt_enable();
    return 0;
}
  • ret_from_fork function
    • 呼叫 schedule_tail function 來啟用搶佔
    • 然後使用保存在 x20 register 中的參數來執行 x19 register 的函式
    • ??? ??? 在呼叫 ret_from_fork 之前，從 cpu_context 恢復 x19, x20
.globl ret_from_fork
ret_from_fork:
    bl    schedule_tail
    mov    x0, x20
    blr    x19         //should never return

void schedule_tail(void) {
	preempt_enable();
}

以上過程僅僅是建立新任務到 task array，完成創建後並不會發生切換任務，待後續 schedule 才會執行新任務

Scene of calling schedule function

  1. 當前任務沒有任何事情要做(事情做完)，但仍舊不能終止時。
  2. schedule 呼叫被加入 timer interrupt handler 中，來定時執行

timer_tick 被 interrupt handler 呼叫

  • 首先將當前任務 counter 減一，若 counter 大於 0 或者當前當前任務禁用搶佔，則返回(不做任何事)，否則呼叫 schedule 並啟用中斷。
void handle_timer_irq(void)
{
    curVal += interval;
    put32(TIMER_C1, curVal); // update for next interrupt
    put32(TIMER_CS, TIMER_CS_M1);
    timer_tick();
}

void timer_tick()
{
    --current->counter;
    if (current->counter > 0 || current->preempt_count > 0) {
        return;
    }
    current->counter = 0;
    enable_irq();
    _schedule();
    disable_irq();
}

Scheduling algorithm

schedule 演算法參考 Linux kernel 第一個發行版的作法

工作原理如下

  1. 第一個內部 for loop through 所有任務，目的是找到 counter 最大處於 TASK_RUNNING 狀態的任務。若找到該條件任務則會跳出外部 while，然後切換到該任務。
  2. 若經過第一個內部 for 沒找到符合條件任務，有兩種可能
    • (1)沒有 TASK_RUNNING 狀態任務
      • e.g 所有任務都在等待中斷
    • (2)任務的 counter 皆為 0
  3. 若發生步驟 2 得情況，將會執行第二個內部 for ，對每個任務增加其 counter
    • 任務通過第二個 for 迭代次數越多，其 counter 越高
    • 任務 counter 限制不會大於 2 * priority
  4. 隨著 while 執行，
    • 若至少有一個任務處於 TASK_RUNNING 狀態，則 while 迭代的二次就會結束，因為第一次的迭代讓所有任務 counter 不為 0
    • 若沒有任務處於 TASK_RUNNING，則 while 將會不斷運行直到某個任務轉換成 TASK_RUNNING 狀態。

    需要思考的部分是若在單個 CPU 上運行，在執行這個 while 時該如何更改任務狀態？
    這就能夠理解為什麼執行 schedule 時必須啟用中斷(enable_irq)，中斷會發生執行 schedule 期間，interrupt handler 可以更改任務的狀態，更改某些在等待中斷的任務狀態

void _schedule(void)
{
    preempt_disable();
    int next,c;
    struct task_struct * p;
    while (1) {
        c = -1;
        next = 0;
        for (int i = 0; i < NR_TASKS; i++){
            p = task[i];
            if (p && p->state == TASK_RUNNING && p->counter > c) {
                c = p->counter;
                next = i;
            }
        }
        if (c) {
            break;
        }
        for (int i = 0; i < NR_TASKS; i++) {
            p = task[i];
            if (p) {
                p->counter = (p->counter >> 1) + p->priority;
            }
        }
    }
    switch_to(task[next]);
    preempt_enable();
}

Switching tasks

找到 counter 非零且處於 TASK_RUNNING 狀態的任務後，呼叫 switch_to 來切換任務

  • 首先檢查要切換的任務與當前任務是否不為同一個，不同才進行切換動作
void switch_to(struct task_struct * next)
{
    if (current == next)
        return;
    struct task_struct * prev = current;
    current = next;
    cpu_switch_to(prev, next);
}

實際的切換工作呼叫了 cpu_switch_to

  • THREAD_CPU_CONTEXT 為 task_struct 中 cpu_context 結構的偏移量，其為 constant 0
  • add x8, x0, x10
    • x0 指向第一個參數的 pointer，也就是當前任務的 task_sturct
    • x8 指向當前任務的 cpu_context
  • mov x9, sp 將 x9 register 指向當前 stack pointer
.globl cpu_switch_to
cpu_switch_to:
    mov    x10, #THREAD_CPU_CONTEXT
    add    x8, x0, x10
    mov    x9, sp
    stp    x19, x20, [x8], #16        // store callee-saved registers
    stp    x21, x22, [x8], #16
    stp    x23, x24, [x8], #16
    stp    x25, x26, [x8], #16
    stp    x27, x28, [x8], #16
    stp    x29, x9, [x8], #16
    str    x30, [x8]
    add    x8, x1, x10
    ldp    x19, x20, [x8], #16        // restore callee-saved registers
    ldp    x21, x22, [x8], #16
    ldp    x23, x24, [x8], #16
    ldp    x25, x26, [x8], #16
    ldp    x27, x28, [x8], #16
    ldp    x29, x9, [x8], #16
    ldr    x30, [x8]
    mov    sp, x9
    ret
  • 透過 stp 指令將 callee-saved registers 按照 cpu_context 的順序保存
    • stp x19, x20, [x8], #16 從 x19 開始寫回 cpu_context，依照 cpu_context 順序
    • stp x29, x9, [x8], #16 將 x9 寫回 cpu_context 的 sp (x29 為 frame pointer)
    • str x30, [x8] 從 x30 寫回 cpu_context 的 pc (保存了函式返回的 address)
    mov    x9, sp
    stp    x19, x20, [x8], #16        // store callee-saved registers
    stp    x21, x22, [x8], #16
    stp    x23, x24, [x8], #16
    stp    x25, x26, [x8], #16
    stp    x27, x28, [x8], #16
    stp    x29, x9, [x8], #16
    str    x30, [x8]
  • 透過 ldp 指令將 callee-saved registers 按照 cpu_context 的順序恢復
    • 首先從 x1 下一個任務 address 加上 THREAD_CPU_CONTEXT 保存到 x8
    • ldp x19, x20, [x8], #16 從 x19 開始讀回 cpu_context
    • 並把 sp 指向下一個任務 cpu_context 中的 sp
    add    x8, x1, x10
    ldp    x19, x20, [x8], #16        // restore callee-saved registers
    ldp    x21, x22, [x8], #16
    ldp    x23, x24, [x8], #16
    ldp    x25, x26, [x8], #16
    ldp    x27, x28, [x8], #16
    ldp    x29, x9, [x8], #16
    ldr    x30, [x8]
    mov    sp, x9
  • ret 後返回到 link register (x30) 所指向的 address
  • 若某個任務第一次被切換到，其實就是執行 ret_from_fork。
    因為在 copy_process 創建新任務時，執行了 pc 的初始化
    p->cpu_context.pc = (unsigned long)ret_from_fork
  • 第二次以後的執行(再次被切換到)，就會恢復到上次停止的 address(pc)

How scheduling works with exception entry/exit?

原本的 kernel_entry & kernel_exit 進行 registers 的保存和恢復。加入 scheduler 後能夠將 interrupt handler 視為一個 task，能夠在處理 interrupt 時切換任務，而 interrupt 的返回 eret 依賴以下兩個 registers

  • elr_el1 : 返回的 address
  • spsr_el1 : 處理器狀態

因此要在處理 interrupt 中切換任務，需要進行以上兩個 registers 和 gerneral registers 的保存與恢復

  • elr_el1 address 寫入對應 cpu_context 結構的 pc
  • spsr_el1 狀態寫入對應 task_struct 結構的 state
.macro	kernel_entry
	...
	stp	x28, x29, [sp, #16 * 14]

	mrs	x22, elr_el1
	mrs	x23, spsr_el1

	stp	x30, x22, [sp, #16 * 15] 
	str	x23, [sp, #16 * 16] 
.endm

.macro	kernel_exit
	ldr	x23, [sp, #16 * 16]
	ldp	x30, x22, [sp, #16 * 15] 

	msr	elr_el1, x22			
	msr	spsr_el1, x23

	ldp	x0, x1, [sp, #16 * 0]
	...
	add	sp, sp, #S_FRAME_SIZE		
	eret
.endm

Exercises

  1. Add printf to all main kernel functions to output information about the curent memory and processor state.
  2. Introduce a way to assign priority to the tasks.
  3. Allow user processes to use FP/SIMD registers.
  4. Allow the kernel to have an unlimited number of tasks through linked list.

User Processes System call

為了 processes 的隔離，需要將所有 user processes 移至 EL0，這能夠限制它們對 privileged processor operations 的訪問

另外提供 API(system call) 給 user processes 來 print 出相關訊息

System calls implementation

每個 system call 都是 synchronous exception。如果 user process 需要執行 system call 必須準備必要的參數，然後呼叫 svc command。
svc 會生成 synchronous exception，並由 OS 在 EL1 處理。目前實作的 OS 定義 4 個 system call:

  1. write: 使用 UART device 在畫面上顯示出訊息
  2. clone: 創建一個新的 user thread
  3. malloc: 為 user process 分配新的 memory page
  4. exit: 每個 process 執行完後必須呼叫此 system call，進行必要的清理
  • 所有在 system calls 在 sys.c
  • sys_call_table 指向所有 system calls handlers
  • 以 write 為例
    • 將 system call 的 index 存放在 w8 register
    • 透過 svc 生成 synchronous exception
    • 使用的慣例 x0 ~ x7 用於呼叫 system call 的參數， x8 or w8 用於呼叫 system call 的 index
.globl call_sys_write
call_sys_write:
    mov w8, #SYS_WRITE_NUMBER
    svc #0
    ret

Handling synchronous exceptions

產生 synchronous exception 後，會呼叫已註冊的對應 handler

  • 首先呼叫 kernel_entry
  • 檢查 esr_el1 (Exception Syndrome Register)。該 register 包含 "exception class"，如果 "exception class" == ESR_ELx_EC_SVC64 表示當前的異常由 svc 產生
  • 若符合 ESR_ELx_EC_SVC64 會進一步執行 el0_svc，否則顯示錯誤
el0_sync:
    kernel_entry 0
    mrs    x25, esr_el1                // read the syndrome register
    lsr    x24, x25, #ESR_ELx_EC_SHIFT // exception class
    cmp    x24, #ESR_ELx_EC_SVC64      // SVC in 64-bit state
    b.eq   el0_svc
    handle_invalid_entry 0, SYNC_ERROR

el0_svc 執行的工作

  • 將 system call table 加載到 stbl
  • 將呼叫的 system call index 加載到 scno
  • 起用中斷 enable_irq
  • 檢查呼叫的 index 是否合法 (< sc_nr)，若不合法則報錯
  • system call handler 存入 x16 (stbl + (scno * 8))
  • 最後執行 handler，並在完成後呼叫 ret_from_syscall
sc_nr   .req    x25                  // number of system calls
scno    .req    x26                  // syscall number
stbl    .req    x27                  // syscall table pointer

el0_svc:
    adr    stbl, sys_call_table      // load syscall table pointer
    uxtw   scno, w8                  // syscall number in w8
    mov    sc_nr, #__NR_syscalls
    bl     enable_irq
    cmp    scno, sc_nr               // check upper syscall limit
    b.hs   ni_sys

    ldr    x16, [stbl, scno, lsl #3] // address in the syscall table
                                     // [stbl, scno, lsl #3] = stbl + (scno * 8)
                                     // size of void pointer is 8
    blr    x16                       // call sys_* routine
    b      ret_from_syscall
ni_sys:
    handle_invalid_entry 0, SYSCALL_ERROR

ret_from_syscall 首先禁用中斷，然後將 x0 register value 存入 stack
(??? 因為接下來要執行的 kernel_exit 將從 stack 恢復 general register value，而希望將原 x0 value 回傳到 user code)

ret_from_syscall:
    bl    disable_irq
    str   x0, [sp, #S_X0]             // returned x0
    kernel_exit 0

Switching between EL0 and EL1

兩個 macro kernel_entry & kernel_exit 更新為能夠接受一個傳入參數

  • EL0 與 EL1 使用不同的 stack，此處 EL0 使用了原始 stack sp_el0，因此在發生異常後 stack pointe 會被覆蓋，所以需要在發生異常的前/後，保存/恢復該 register 的值
  • EL1 中獲取異常不恢復 stack pointer，原因是在異常處理過程中發生 context switch，在 kernel_exit 時， sp 已經被 cpu_switch_to 切換
  • 不需要在執行 eret 前指定需要返回的 exception level，因為相個資訊儲存在 spsr_el1 中，永遠都會返回到發生異常的 level
    //kernel_entry
    .if    \el == 0
    mrs    x21, sp_el0
    .else
    add    x21, sp, #S_FRAME_SIZE
    .endif /* \el == 0 */
    
    mrs	x22, elr_el1
    mrs	x23, spsr_el1
    
########
    
    //kernel_exit
    .if    \el == 0
    msr    sp_el0, x21
    .endif /* \el == 0 */
    
    msr	elr_el1, x22			
    msr	spsr_el1, x23

Moving a task to user mode

使用任何 system call 之前，首先需要有在 user mode 下執行的任務。能夠將 kernel task 移動至 user mode 來達成

kenel_main 函式中，創建一個新的 kernel thread，將在 scheduler 開始後，在 kernel model 執行 kernel_process 函式

    int res = copy_process(PF_KTHREAD, (unsigned long)&kernel_process, 0, 0);
    if (res < 0) {
        printf("error while starting kernel process");
        return;
    }

void kernel_process(){
    printf("Kernel process started. EL %d\r\n", get_el());
    int err = move_to_user_mode((unsigned long)&user_process);
    if (err < 0){
        printf("Error while moving process to user mode\n\r");
    }
}

先前創建新任務在 stack 頂部保留一個區域 (pt_regs 區域)，將會在這裡被使用到
pt_regs struct 的初始化 (這個區域與 kernel_exit 期望的格式相符合)

  • pc 指向需要在 user mode 下執行的工作。kernel_exit 將把 pc 複製到 elr_el1 register 確保從異常返回後回到 pc address
  • pstate 由 kernel_exit 複製到 spsr_el1，異常返回後成為處理器狀態。 PSR_MODEL_EL0t constant 將異常返回到 EL0
  • stack 為 user stack 分配一個 page，並將 sp 指到 page 頂部
  • task_pt_regs 用於計算 pt_regs 區域位置
int move_to_user_mode(unsigned long pc)
{
    struct pt_regs *regs = task_pt_regs(current);
    memzero((unsigned long)regs, sizeof(*regs));
    regs->pc = pc;
    regs->pstate = PSR_MODE_EL0t;
    unsigned long stack = get_free_page(); //allocate new user stack
    if (!stack) {
        return -1;
    }
    regs->sp = stack + PAGE_SIZE;
    current->stack = stack;
    return 0;
}

struct pt_regs * task_pt_regs(struct task_struct *tsk)
{
    unsigned long p = (unsigned long)tsk + THREAD_SIZE - sizeof(struct pt_regs);
    return (struct pt_regs *)p;
}

Forking user processes

user_process 透過 move_to_user_mode 後在 user mode 下執行
使用 clone system call 來啟用兩個任務。其中 clone 需要搭配 malloc 獲取的 stack address

  • 保存 registers value x0-x2
  • 呼叫 sys_clone
  • 檢查 sys_clone 的返回值，
    • 返回值 0，表示當前正在新創建的 kernel thread 中
    • 返回值不為 0，表示其為任務 PID，在這裡即會直接返回
.globl call_sys_clone
call_sys_clone:
    /* Save args for the child.  */
    mov    x10, x0                    /*fn*/
    mov    x11, x1                    /*arg*/
    mov    x12, x2                    /*stack*/

    /* Do the system call.  */
    mov    x0, x2                     /* stack  */
    mov    x8, #SYS_CLONE_NUMBER
    svc    0x0

    cmp    x0, #0
    beq    thread_start
    ret

thread_start:
    mov    x29, 0

    /* Pick the function arg and execute.  */
    mov    x0, x11
    blr    x10

    /* We are done, pass the return value through x0.  */
    mov    x8, #SYS_EXIT_NUMBER
    svc    0x0

copy_process 現在能夠處理 kernel or user thread，clone user thread 時會有新的處理

  • struct pt_regs * cur_regs = task_pt_regs(current) 第一件事是訪問處理器狀態，該狀態由 kernel_entry 保存
  • *childregs = *cur_regs 將當前處理器狀態複製到新任務的狀態。新狀態下 x0 設置為 0，因為調用者會將 x0 解釋為 system call 的返回值(使用此值來確定是否仍在執行原始的 thread 一部分 or 新 thread)
  • 新任務的下一個 sp 指向新 user stack 的頂部
int copy_process(unsigned long clone_flags, unsigned long fn, unsigned long arg, unsigned long stack)
{
    preempt_disable();
    struct task_struct *p;

    p = (struct task_struct *) get_free_page();
    if (!p) {
        return -1;
    }

    struct pt_regs *childregs = task_pt_regs(p);
    memzero((unsigned long)childregs, sizeof(struct pt_regs));
    memzero((unsigned long)&p->cpu_context, sizeof(struct cpu_context));

    if (clone_flags & PF_KTHREAD) {
        p->cpu_context.x19 = fn;
        p->cpu_context.x20 = arg;
+    } else {
+        struct pt_regs * cur_regs = task_pt_regs(current);
+        *childregs = *cur_regs;
+        childregs->regs[0] = 0;
+        childregs->sp = stack + PAGE_SIZE;
+        p->stack = stack;
+    }
    p->flags = clone_flags;
    p->priority = current->priority;
    p->state = TASK_RUNNING;
    p->counter = p->priority;
    p->preempt_count = 1; //disable preemtion until schedule_tail

    p->cpu_context.pc = (unsigned long)ret_from_fork;
    p->cpu_context.sp = (unsigned long)childregs;
    int pid = nr_tasks++;
    task[pid] = p;
    preempt_enable();
    return pid;
}

Exiting a task

每個任務完成後，透過 exit system call，其呼叫了 exit_process，負責停止任務

  • 依照 linux 傳統，並不會直接刪除任務，而是修改其狀態為 TASK_ZOMBIE。如此 schedule 不會在執行該任務。(這種作法使得 parent process 即使在 child process 完成後也能夠查詢相關訊息)
  • 刪除不必要的 user stack 後執行 schedule 選擇下一個待執行任務
void exit_process(){
    preempt_disable();
    for (int i = 0; i < NR_TASKS; i++){
        if (task[i] == current) {
            task[i]->state = TASK_ZOMBIE;
            break;
        }
    }
    if (current->stack) {
        free_page(current->stack);
    }
    preempt_enable();
    schedule();
}

Exercises

  1. When a task is executed in user mode, try to access some of the system registers. Make sure that a synchronous exception is generated in this case.
  2. Implement a new system call that can be used to set current task priority.
Last changed by 
 
李訓廷
0
711

Read more

CH 05 Synchronous

解決 critical section 要滿足三個條件 mutual exclusion progress bounded waiting Spinlock / Peterson solution 重點load and store 需要是 atomic operation flag and turn 被 assigned 的“順序“很重要 (不能被 compiler 優化，調整先後順序) 例子

Jun 18, 2023
Read more from 李訓廷
Published on HackMD