Lab4: Multitasking

Posted on Edited on In

lab4 在概念上不會太難，難的是組語和 c 語言間的交替使用。例如，手動分配好 kernel stack，用 asm 寫入 sp, fp：

1
2
3
4
5
6
7
asm volatile("msr tpidr_el1, %[task]\n\t"
                 "mov x9, %[func]\n\t"
                 "mov x10, %[sp]\n\t"
                 "mov sp, x10\n\t"
                 "mov fp, #0\n\t" // arbitarary value
                 "blr x9"
                 :: [sp] "r" (p), [func] "r" (func), [task] "r" (task): "memory");

如果有需要取得特定 label 的 address(不在 c 語言規範之內)，可參考 Labels as Values。

Reference: How do I write a given address to a register using inline assembly, ARM Instruction Set

Required 1-3: context switch

目標是讓兩個 function — task1, task2 反覆執行，將一開始的 main 視為 task 0，以 privilege_task_create 初始化好 task 1 & 2 再跳躍至 task 1。因為不會跳回 main，task 0 本身的 context 不用處理。

1
2
3
4
5
6
7
8
9
10
11
12
void main()
{
    uart_init(115200, 0);
    uart_flush();
    fb_init();
    fb_showpicture();
    privilege_task_create(&task1);
    privilege_task_create(&task2);
    asm volatile("msr tpidr_el1, %0"::"r" (get_task(0)));
    context_switch(get_task(1));
    __builtin_unreachable();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static task_t task_pool[MAX_TASK] __attribute__((section(".kstack")));
static uint8_t kstack_pool[MAX_TASK][KSTACK_SIZE] __attribute__((section(".kstack")));
static int task_id = 1; // id = 0 is preserved for main()

void privilege_task_create(void (*func)())
{
    int id = get_task_id();
    task_t *task = &task_pool[id];
    task->id = id;
    task->task_context.fp = (uint64_t) 0; // arbitarary value
    task->task_context.sp = (uint64_t) &kstack_pool[id + 1][0];
    task->task_context.lr = (uint64_t) *func;
}

void context_switch(task_t *next)
{
    task_t *prev = (task_t *) get_current();
    switch_to(prev, next);
}

void task1()
{
    while (1) {
        uart_printf("1...\n");
        for (int i = 0; i < (1 << 26); ++i)
            asm("nop");
        context_switch(&task_pool[2]);
    }
    __builtin_unreachable();
}

void task2()
{
    while (1) {
        uart_printf("2...\n");
        for (int i = 0; i < (1 << 26); ++i)
            asm("nop");
        context_switch(&task_pool[1]);
    }
    __builtin_unreachable();
}

  • 觀察到 local variable 均以 sp 做定位不用 fp，故不設 fp。

  • 留給 task 的 KSTACK_SIZE一定要設足

  • 在 compile sched.S 時遇到

    1
    include/types.h:12: Error: unknown mnemonic `typedef' -- `typedef __signed char int8_t'

    是由於 cross-compiler 不支援 .S 出現 typedef，得在 header file 加上

    1
    2
    #ifndef __ASSEMBLER__
    #endif

  • 善用 online compiler 理解 assembly code 和 extended asm 之間的關係

  • extended assembly 的撰寫參考 如何撰寫 Inline Assembly

  • 關於 context switch 存的特定 general register 可參考 Parameters in general-purpose registers, AArch64 Instruction Set

Required 1-5

加入 round robin scheduler 和 run queue。原本的 main 視為 idle task 排除在 run queue 外，只有在沒有任務時才執行，避免 CPU 進入 non-deterministic state。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void schedule()
{
    task_t *current, *next, *idle = &task_pool[0];
    asm volatile("mrs %0, tpidr_el1" : "=r"(current));
    if (current != idle) {
        // push current task into runqueue except idle task
        runqueue_push(&runqueue, &current);
    }
    if (runqueue_is_empty(&runqueue)) {
        next = idle;
    } else {
        runqueue_pop(&runqueue, &next);
    }
    context_switch(next);
}

Required 2-1, 2-2

timer handler 和 scheduler 關係：

  • timer handler 主動更新 task 的執行時間，在一個 epoch 的時間用盡時設置 task 的 reschedule flag

    1
    2
    if (current->counter > 0)
    	--current->counter;

  • task 執行時檢查 reschedule flag 來呼叫 schedule() 主動讓出 cpu

在 required 2 中，要求在呼叫 schedule() 前印出訊息

Required 3

required 3 的要求是發生在 user task 的 exception 返回前檢查 reschedule flag，並適時的 schedule 到下一個 process。（kernel preemption 在 elective 5 才實作，到目前為止 kernel task 都是主動讓出 cpu。）

在 lab2 的 exception handler 其實有處理來自 el0、el1 的 exception，在前後 kernel_entry, kernel_exit 也做了存/復原對應的 stack pointer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// save
.if \el == 0
mrs x21, sp_el0
.else
add x21, sp, #S_FRAME_SIZE // x21 = sp + #S_FRAME_SIZE
												   // sp = sp + S_FRAME_SIZE
.endif /* \el == 0 */

mrs	x22, elr_el1
mrs	x23, spsr_el1

stp x30, x21, [sp, #16 * 15]
stp x22, x23, [sp, #16 * 16]

// restore
ldp	x22, x23, [sp, #16 * 16]
ldp	x30, x21, [sp, #16 * 15]

.if	\el == 0
msr	sp_el0, x21
.endif /* \el == 0 */

msr	elr_el1, x22
msr	spsr_el1, x23

在 required 3-1 實作出 kernel stack、user stack 後，實際 exception handler 運行時是使用最近運行的 sp_el1 再往下創造出的 stack frame：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
               |                     |
               |                     |
      +------  +---------------------+
      |        |                     |
      |        |  task n stack frame |
      |        |                     |
      |        +---------------------+ <-------  irq interrupt
      |        |                     |
      |        |    saved context    |  ( cpu context of user task or kernel task )
      |        |                     |
               +---------------------+ <-------  irq routine
task n stack   |                    |
               |    irq handler's    |
      |        |                     |
      |        |     stack frame     |
      |        |                     |
      |        +---------------------+
      |        |                     |
      |        |        .....        |
      |        |                     |
      +------- +---------------------+
               |                     |
               |                     |
               |                     |

saved context 可能為 kernel task 或 user task cpu context，端看 interrupt 發生時機。另外 irq stack frame 坐落在 kernel stack 上，因此從 irq routine 回到 kernel task 時不用再還原 stack pointer，只需考慮 irq routine 回到 user task 時要還原 sp_el0。

1
2
3
.if	\el == 0
msr	sp_el0, x21
.endif /* \el == 0 */

Required 3-1, 3-2: reschedule for user task

You don’t have to use another interrupt stack for ISR, but you should know interrupt context is different from task context. You should not reschedule inside ISR.

為什麼？ISR 內不適合進行 schedule 耗費時間長的工作，其次硬體 register 也會隨著時間而變。但這不意味著不能在 kernel_exit 進行 reschedule。

  1. 先考慮只有 kernel task 進入 interrupt handler 的情況：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    |           |   |           |
    |           |   |           |
    |           |   |           |
    +-----------+   +-----------+
    |  TASK 1   |   |  TASK 2   |
    |           |   |           |
    |  KERNEL   |   |  KERNEL   |
    |           |   |           |
    |   STACK   |   |   STACK   |
    |           |   |           |
    |           |   |           |
    +-----------+   +-----------+
    |   SAVED   |   |   SAVED   |
    |           |   |           |
    |  CONTEXT  |   |  CONTEXT  |
    |           |   |           |
    +-----------+   +-----------+
    |           |   |    IRQ    |
    |           |   |           |
    |           |   |STACK FRAME|
    |           |   +-----------+
    |           |   |           |

  2. 再考慮 kernel task + user task，user task 運行時進入 interrupt handler 的情況：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
                    |           |
                    +-----------+
                    |  TASK 2   |
                    |           |
                    |   USER    |
                    |           |
                    |   STACK   |
                    |           |
                    |           |
                    +-----------+ ------+
                    |           |       |
                                        |
    |           |   |           |       |
    +-----------+   +-----------+       |
    |  TASK 1   |   |  TASK 2   |       |
    |           |   |           |       |
    |  KERNEL   |   |  KERNEL   |       |
    |           |   |           |       |
    |   STACK   |   |   STACK   |       |
    |           |   |           |       |
    |           |   |           |       |
    +-----------+   +-----------+ <-----+
    |   SAVED   |   |   SAVED   |
    |           |   |           |
    |  CONTEXT  |   |  CONTEXT  |
    |           |   |           |
    +-----------+   +-----------+
    |           |   |    IRQ    |
    |           |   |           |
    |           |   |STACK FRAME|
    |           |   +-----------+
    |           |   |           |

可見 interrupt 並不會影響到 user stack。

其次 reschedule 最佳放置點是還原 saved context 前，否則等到還原後再進行 reschedule，要存的東西還得包含 sp_el0, elr_el1, spsr_el1，不如讓這一切儲存在 saved context，context switch 只要存指向 saved context 的 sp。

1
2
3
4
5
.if	\el == 0
bl  reschedule
.endif /* \el == 0 */
...
ldp	x28, x29, [sp, #16 * 14]

Constraint of extended asm

發現 extended asm 因為 constraint r 或 m 而生成 invalid syntax。

以 ldr 之類的 pseudo instruction 為例，本以為填 r 會生成 ldr + mov 組合，實際上卻是直接照填

1
2
3
4
5
6
asm("ldr x9, %0\n\t"
		"msr sp_el0, x9"
    ::"r" (var1))

ldr x9, x0 // invalid
msr sp_el0, x9

ldr 語法是這樣

1
LDR <Xt>, [<Xn|SP>, (<Wm>|<Xm>){, <extend> {<amount>}}]

填 m 才會產生合法的語法

1
2
3
4
5
6
asm("ldr x9, %0\n\t"
		"msr sp_el0, x9"
    ::"m" (var1))

ldr x9, [sp, 24] // valid
msr sp_el0, x9

所以遇到需要載入值時，不如爽快的填 r，其他的交給編譯器處理，避開操作 ldr。

1
2
asm("msr sp_el0, %0"
    ::"r" (var1))

IRQ interrupt mask is set after switching from user task

context switch 會發生在兩種情境

  1. kernel task 主動呼叫 reschedule ，切換到 kernel task
  2. user task 被 irq 中斷，從 irq handler 返回時呼叫 reschedule，切回 kernel task

第一種由於是主動呼叫 reschedule 切換，過程中不會更改到 CPSR。第二種在進入 irq handler 時 CPSR 會額外 mask D&I bit，加上下一個要切換的 kernel task 當初是主動呼叫 reschedule 讓出 CPU，自然不會經過 eret 這樣的程序，所以 masked D&I 就留下來了。

所以在 kernel task 呼叫完後，如果沒有手動 unmask I bit，task 執行中是不會觸發 IRQ 的。

1
2
3
4
5
6
7
8
// kernel task 1
while (1) {
        printk("1...\n");
        for (int i = 0; i < (1 << 26); ++i)
            asm("nop");
        reschedule();
        enable_irq();
}