Lab5: User Space Paging

Posted on Edited on In

讓每個 user task 做到擁有自己的 virtual address space，簡便的作法是讓每個 task 擁有自己的 page table

include/mm.h

1
2
3
typedef struct {
    uintptr_t pgd;
} mm_struct;

include/task.h

1
2
3
4
5
6
7
8
9
10
typedef struct task_struct {
    struct task_context task_context;
    pid_t tid;
    task_state state;
    uint64_t counter;
    sigvec_t sig_pending;
    sigvec_t sig_blocked;
+   mm_struct mm;
    struct list_head node;
} task_t;

kernel/sched.S

1
2
3
4
5
6
7
8
.global update_pgd
update_pgd:
    dsb ish // ensure write has completed
    msr ttbr0_el1, x0 // switch translation based address.
    tlbi vmalle1is // invalidate all TLB entries
    dsb ish // ensure completion of TLB invalidatation
    isb // clear pipeline
    ret

並在切換到該 user task 時將 task_struct 內的 pgd 寫入 TTBR0_EL1，也就是在下列情況呼叫 update_pgd

  1. do_exec ：由 kernel task 創建 user task 時

  2. fork syscall

  3. context switch

    1
    2
    3
    4
    5
    6
    void context_switch(task_t *next)
    {
        task_t *prev = (task_t *) get_current();
        update_pgd(next->mm.pgd);
        switch_to(prev, next);
    }

Switch from kernel space to user space - do_exec

kernel/task.c

先使用 map_addr_user 取得 virtual address 對應的 page address，map_addr_user 會尋找已存在的 page 或是分配新的 page，並返回 page address。

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
void do_exec(void (*func)())
{
    /*
     * If the task was created by privilege_task_create() and hasn't initlized
     * page table, the default value of TTBR0_EL1 is 0x0
     */
    const task_t *task = get_current();
    uintptr_t sp = USER_VIRT_TOP - sizeof(uintptr_t);  // stack address grows towards lower memory address
    size_t size = PAGE_SIZE;
    uintptr_t pc = 0x0;  // start from 0x0

    // allocate page for user
    void *utext = map_addr_user((void *) pc);   // assume size < 4KB
    void *ustack = map_addr_user((void *) sp);  // assume size < 4KB
    if (!utext || !ustack) {
        // TODO: reclaim utext and ustack
        return;
    }

    // copy text
    memcpy(utext, func, size);

    // switch to el0
    update_pgd(task->mm.pgd);
    asm volatile(
        "msr     sp_el0, %0\n\t"
        "msr     elr_el1, %1\n\t"
        "msr     spsr_el1, %2\n\t"
        "eret" ::"r"(sp),
        "r"(pc), "r"(SPSR_EL1_VALUE));
    __builtin_unreachable();
}

Fork User Process - fork syscall

kernel/mm.c

將 process 的 page table 複製一份

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
42
43
44
45
46
47
int fork_page(void *dst, const void *src)
{
    if (!src || !dst)
        return -1;
    memcpy(dst, src, PAGE_SIZE);
    return 0;
}

/* return 0 if success, return -1 if fail. */
#define FORK_PAGE_TABLE(name, callback)                         \
    int name(uint64_t *dst_pt, const uint64_t *src_pt)          \
    {                                                           \
        for (uint16_t idx = 0; idx < (1 << 9); idx++) {         \
            if (src_pt[idx]) {                                  \
                const void *next_src_pt =                       \
                    (const void *) ((src_pt[idx] & ~0xfffULL) | \
                                    KERNEL_VIRT_BASE);          \
                void *next_dst_pt = create_page(dst_pt, idx);   \
                if (-1 == callback(next_dst_pt, next_src_pt))   \
                    return -1;                                  \
            }                                                   \
        }                                                       \
        return 0;                                               \
    }

FORK_PAGE_TABLE(fork_pte, fork_page)
FORK_PAGE_TABLE(fork_pmd, fork_pte)
FORK_PAGE_TABLE(fork_pud, fork_pmd)
FORK_PAGE_TABLE(fork_pgd, fork_pud)

/*
 * fork page table of user process
 * return 0 if success, return -1 if fail.
 */
int fork_page_table(mm_struct *dst, const mm_struct *src)
{
    if (!src || !dst)
        return -1;
    if (!src->pgd || dst->pgd)
        return -1;  // dst's pgd must be uninitialized

    uint64_t *src_pgd = (uint64_t *) PA_TO_KVA(src->pgd);
    uint64_t *dst_pgd = (uint64_t *) create_pgd(dst);

    // copy page table recursively
    return fork_pgd(src_pgd, dst_pgd);
}

kernel/task.c

啟用 virtual memory 後，新舊 process page table 內容、pc 和 sp 都一樣，唯一要修改的是 return value。

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
/*
 * On success, the task id of the child process is returned
 * in the parent, and 0 is returned in the child. On failure,
 * -1 is returned in the parent.
 */
int64_t do_fork(struct TrapFrame *tf)
{
    // create a new task: child
    int64_t new_task_id = privilege_task_create(NULL);
    if (new_task_id < 0)
        return -1;
    task_t *new_task = get_task_by_id(new_task_id);
    const task_t *cur_task = get_current();

    // fork page table
    if (-1 == fork_page_table(&new_task->mm, &cur_task->mm)) {
        /* TODO: reclaim page */
        return -1;
    }

    // parent process and child process have the same content of TrapFrame
    void *kstacktop_new = get_kstacktop_by_id(new_task->tid);
    struct TrapFrame *tf_new =
        (struct TrapFrame *) (kstacktop_new - sizeof(struct TrapFrame));
    *tf_new = *tf;

    // set child's return value
    tf_new->x[0] = 0;

    // set child task's task_struct
    extern void ret_to_user();
    new_task->task_context.lr = (uint64_t) ret_to_user;
    new_task->task_context.sp = (uint64_t) tf_new;
    new_task->state = TASK_RUNNABLE;
    new_task->sig_blocked = cur_task->sig_blocked;
    new_task->sig_pending = cur_task->sig_pending;

    return new_task_id;
}

User Space Page Allocation

kernel/mm.c

map_addr_user 會在找尋 page 時一邊建立 PGD, PUD, PMD, PTE

1.　建立的方式是利用 page bookkeeeping 時實作的 page_alloc_kernel()、page_alloc_user() 分配一塊新的 page，因為是在建立 user space 的 page table，所以使用 page_alloc_kernel 。

2.　將上層 page table 的 entry 指向該 page，並將 page’s physical address 加上 kernel virtual address base (0xffff000000000000) 成為 kernel virtual address 返回。

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
void *map_addr_user(void *uaddr)
{
    /*
     * virtual user address
     * | 0.....0 | pgd index | pmd index | pud index | pte index | offset |
     *      16          9           9           9          9         12
     */
    task_t *cur_task = (task_t *) get_current();
    uint32_t pgd_idx = ((uint64_t) uaddr & (PD_MASK << PGD_SHIFT)) >> PGD_SHIFT;
    uint32_t pud_idx = ((uint64_t) uaddr & (PD_MASK << PUD_SHIFT)) >> PUD_SHIFT;
    uint32_t pmd_idx = ((uint64_t) uaddr & (PD_MASK << PMD_SHIFT)) >> PMD_SHIFT;
    uint32_t pte_idx = ((uint64_t) uaddr & (PD_MASK << PTE_SHIFT)) >> PTE_SHIFT;

    void *pgd, *pud, *pmd, *pte, *page;
    pgd = create_pgd(&cur_task->mm);
    if (!pgd)
        goto err;
    pud = create_pmd_pgd_pte(pgd, pgd_idx);
    if (!pud)
        goto err;
    pmd = create_pmd_pgd_pte(pud, pud_idx);
    if (!pmd)
        goto err;
    pte = create_pmd_pgd_pte(pmd, pmd_idx);
    if (!pte)
        goto err;
    page = create_page(pte, pte_idx);
    if (!page)
        goto err;
    return page;
err:
    return NULL;
}

為何是 kernel virtual address? 因為從開機進到 EL1，我們已經啟用 virtual memory，而且切換到新的 kernel task 時，context switch 將初始化為 0x0 的 pgd 寫入 TTBR0_EL1，這將造成非 0xffff 開頭的 virtual address 存取錯誤，唯有 TTBR0_EL1 放入有效的 pgd 才能正確存取。因此雖然在 page descriptor 填的是下一級 page table/page 的 physical address，但存取時還是用 kernel virtual address。

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
42
43
44
45
46
47
/* create pgd for user space of a specific process
 * return virtual address of the pgd if success, otherwise return NULL.
 */
static void *create_pgd(mm_struct *mm)
{
    if (!mm->pgd) {
        // has't created pgd
        void *page_virt_addr = page_alloc_kernel();
        if (!page_virt_addr)
            return NULL;
        mm->pgd = KVA_TO_PA(page_virt_addr);
    }
    return (void *) PA_TO_KVA(mm->pgd);
}

/* create pud/pmd/pte for user process
 * return virtual address of the pud/pmd/pte if success, otherwise return NULL.
 */
static void *create_pmd_pgd_pte(uint64_t *page_table, uint32_t index)
{
    if (!page_table)
        return NULL;
    if (!page_table[index]) {
        void *page_virt_addr = page_alloc_kernel();
        if (!page_virt_addr)
            return NULL;
        page_table[index] = KVA_TO_PA(page_virt_addr) | PD_TABLE;
    }
    return (void *) ((page_table[index] & ~0xfffULL) | KERNEL_VIRT_BASE);
}

/* create page for user process
 * return virtual address of the page if success, otherwise return NULL.
 */
static void *create_page(uint64_t *pte, uint32_t index)
{
    if (!pte)
        return NULL;
    if (!pte[index]) {
        void *page_virt_addr = page_alloc_kernel();
        if (!page_virt_addr)
            return NULL;
        pte[index] =
            KVA_TO_PA(page_virt_addr) | PTE_NORMAL_ATTR | PD_ACCESS_PERM_1;
    }
    return (void *) ((pte[index] & ~0xfffULL) | KERNEL_VIRT_BASE);
}

Arithmetic Conversions

分配 page table 時難免要從 page descriptor 的值讀出 physical address，例如這段將 page descriptor 進行 bit masking：

1
return (void *)((page_table[index] & ~0xfff) | KERNEL_VIRT_BASE);

實際上運作時

  1. int 型態的 0xFFF，先經過 bit inverse 為 0xFFFFF000
  2. 與 uint64_t 型態的 page_table[index] 進行 bitwise operation

If the unsigned type has conversion rank greater than or equal to the rank of the signed type, then the operand with the signed type is implicitly converted to the unsigned type.

otherwise, if the target type is unsigned, the value 2^b, where b is the number of bits in the target type, is repeatedly subtracted or added to the source value until the result fits in the target type. In other words, unsigned integers implement modulo arithmetic.

  1. 0xFFFFF000 轉換成 uint64_t，所以實際上是
1
-4096(0xFFFFF000) + 2^64 = 0xFFFFFFFFFFFFF000

不過為了可讀性，其實可以寫成

1
return (void *)((page_table[index] & ~0xfffULL) | KERNEL_VIRT_BASE);

Reference: **Type of integer literals not int by default?, Implicit conversions**

Reference