用户态进程的简单实现及调度(一)

update: 在写这篇的时候, 我发觉我很难在这短短一篇博文里把进程的实现将清楚, 并且可能存在一些理解的偏差, 因此本篇仅供参考, 更加准确的表述, 还请参考第五章调度 | xv6 中文文档

特权级转换
GDT
IDT
TSS
两个上下文
- 中断上下文
- 进程上下文
虚拟内存映射
第一个进程
- 构造
- 运行
调度
E.N.D.

自从上次完成了 Minix 文件系统之后, 就开始看 xv6 中进程相关的代码, 并把它抄进 OS67 中, 到今天为止, 总算是完成地差不多了.

进程的实现可能是 xv6 中耦合度最高的一部分, 在完成大部分的代码 (GDT,TSS 的设置, 上下文保存和切换, 虚拟内存映射, 系统调用)之前, 你很难让你的内核跑起来.

xv6 已经尽量使用容易理解的方式来书写这些代码了, 不过有些地方仍然比较晦涩(对我来说). 希望再这篇文章里能稍微梳理一下.

注意: OS67 并不打算支持多核 CPU, 这极大地降低了实现进程的难度, 不需要考虑由于多核导致的进程间的竞争和同步, 因此 xv6 中关于锁的代码都可以忽略.

特权级转换

几个关于特权级的概念:

intel 8086 的特权级分为 0 1 2 3 四级, 这里只使用 0 和 3
DPL: Descriptor Privilege 描述符特权级, 储存在 GDT 或 IDT 描述符中
CPL: Current Privilege 当前特权级, 储存在 cs 寄存器的低二位
RPL: Request Privilege 请求特权级, 请求访问的段的描述符的特权级

GDT

这里使用的用户态的特权级为 3, 因此用户态的程序, 其所在的数据段代码段的 DPL, 段寄存器低 2 位的 RPL 都得是 3, 因此设置的全局段描述符表(GDT) 如下:

// OS67/kern/gdt.c
gdt_install(0, 0, 0, 0, 0);
/* kernel code segment type: code addr: 0 limit: 4G gran: 4KB sz: 32bit */
gdt_install(SEL_KCODE, 0, 0xfffff, AC_RW|AC_EX|AC_DPL_KERN|AC_PR, GDT_GR|GDT_SZ);
/* kernel data segment type: data addr: 0 limit: 4G gran: 4KB sz: bit 32bit */
gdt_install(SEL_KDATA, 0, 0xfffff, AC_RW|AC_DPL_KERN|AC_PR, GDT_GR|GDT_SZ);
/* user code segment type: code addr: 0 limit: 4G gran: 4KB sz: 32bit */
gdt_install(SEL_UCODE, 0, 0xfffff, AC_RW|AC_EX|AC_DPL_USER|AC_PR, GDT_GR|GDT_SZ);
/* user data segment type: data addr: 0 limit: 4G gran: 4KB sz: 32bit */
gdt_install(SEL_UDATA, 0, 0xfffff, AC_RW|AC_DPL_USER|AC_PR, GDT_GR|GDT_SZ);

第一二个描述符定义了内核的代码段和数据段, 第三四个描述符定义了用户的代码段和数据段.

注意: 代码段必须是非一致性代码段, 因为一致性代码段对特权级的处理方式不同.

当 GDT 初始化后, 第一二个描述符被使用, 内核跑在特权级为 0 的段上. 那如何让代码从特权级为 0 的段(内核态)转移到特权级为 3 的段(用户态)呢? 用中断.

IDT

为了让用户空间的程序顺利进入内核态, 需要对中断描述符表(IDT) 做一些设置.

(以下内容摘自 xv6 中文文档, 有小改动)

我们假设一个用户态程序执行int n指令触发中断, 则 CPU 会取得中断号 n, 进行如下步骤: (由 PIC 或者异常触发的中断不一定如此)

从中断描述符表(IDT) 获得第 n 个描述符
检查描述符的特权级 DPL 是否 数值上大于等于 当前的特权级 CPL (即当前段的级别至少要高于要执行的中断的特权级), 是则继续, 否则触发一个通用保护中断(General Protection Fault, int 13)

通过设置 DPL, 可以限制用户态能用 int 指令触发的中断号, 系统调用的实现即是如此

如果目标段描述符的 RPL < CPL, 则在 CPU 内部保存esp和ss的值. 这个时候意味这特权级转换要发生了.
从一个任务状态段(TSS)加载ssX和espX, X 是 RPL 的值, 所以对于系统调用, 取出的会是 ss0和esp0
将ss esp eflags cs eip压栈
清除eflags中的某些位
设置cs和ip为 IDT[n] 中指定的值. (执行中断服务例程)

对于普通的中断, 其中断返回地址是发生中断时的执行的那条指令的地址 (需要将 IDT 的类型设置为中断门(Interrupt gate)) 因为这种中断通常和当前进程没有什么关系.

idt_install(0, (uint32_t)fault0, SEL_KCODE << 3, GATE_INT, IDT_PR|IDT_DPL_KERN);

对于系统调用, 我们需要主动执行 int 指令, 并让其返回到下一条指令处. 因此要将处理系统调用的 IDT 设置为陷阱门(Trap gate), 并且 DPL 为IDT_DPL_USER(3). 如下:

idt_install(ISR_SYSCALL, (uint32_t)_syscall, SEL_KCODE << 3, GATE_TRAP, IDT_PR | IDT_DPL_USER);

TSS

在特权级转换的时候, 需要从任务状态段取出ss0和esp0, 因此在转换之前需要设置 TSS.

CPU 会从寄存器tr获得 TSS 的选择子, 然后从 GDT 表里面找出对应的描述符, 由描述符就可以获得 TSS 的基址了.

TSS 的选择子放在 GDT 里, 但是其AC_RE(ACCESS_REVERSE)位为 0 来表示它是一个 TSS 描述符而不是 GDT 描述符.

因此 TSS 的初始化是这样的:

void tss_init(){
    gdt_install(SEL_TSS, (uint32_t)&tss, sizeof(tss),AC_PR | AC_AC | AC_EX, GDT_GR);
    /* for tss, access_reverse bit is 1 */
    gdt[5].access &= ~AC_RE;
}

在从进程的内核态回到用户态的时候, 要设置一次 TSS, 以下函数在uvm_switch里面被调用:

void tss_set(uint16_t ss0, uint32_t esp0){
    memset((void *)&tss, 0, sizeof(tss));
    tss.ss0 = ss0;
    tss.esp0 = esp0;
    tss.iopb_off = sizeof(tss);
}

两个上下文

中断上下文

从上面关于中断过程的解释可以看到, 从用户态执行中断转入内核态是可能的, 重点在与设置一个 DPL = 3 的 IDT 和一个 TSS 段.

那如何从内核态返回用户态呢? iret 指令会按 int 压栈的顺序逆序将寄存器们出栈, 程序就会从内核态又返回到用户态了.

有意思的地方就是, 要从内核态到用户态, 我们可以构造一个栈, 然后执行 iret 指令, iret 就会将我们特地安排的值覆盖到寄存器上, 这个工作由proc_alloc完成, 每个新建的进程都通过这种方式”假装回到”用户空间.

为了方便地构造栈, 我们需要定义出中断时保存的上下文, int 指令保存的信息还不够, 我们需要自己保存更多的寄存器:

struct int_frame{
    /* segment registers */
    uint32_t gs;    // 16 bits
    uint32_t fs;    // 16 bits
    uint32_t es;    // 16 bits
    uint32_t ds;    // 16 bits

    /* registers save by pusha */
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp;
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;

    uint32_t int_no;

    /* save by `int` instruction */
    uint32_t err_code;
    uint32_t eip;
    uint32_t cs;    // 16 bits
    uint32_t eflags;
    uint32_t user_esp;
    uint32_t ss;    // 16 bits
};

只要完整地保存了以上信息并正确还原, 就能确保从中断返回时, 程序依然正常运行. 注意的是我们不必显式地建立以上的一个结构体(构建第一个进程的时候除外), 在中断发生时, 这个结构体会在进程的内核栈上被建立.中断返回时, 这些信息又会从栈里被弹出.

中断上下文的err_code到ss部分由 int 指令压入, 之后跳转到OS67/kern/loader.asm 中的由汇编编写的中断服务例程(ISR)入口. 有的中断不产生err_code, 就由该中断入口压入一个假的err_code. 这些入口代码有两个宏生成, 分别是m_fault和m_irq, 负责处理异常中断和硬件中断. 另外还有_syscall和_isr_unknown处理系统调用和未定义的中断.

每个入口都会压入自己的中断号, 然后统一跳转到_isr_stub, 压入上下文的剩余部分, 再调到由 C 编写的isr_stub, 由此再根据入口压入中断号调用真正的 ISR. 关于这些 ISR 的详情…太长了表示扯不下去了… :(

进程上下文

中断上下文已经让程序能够程序成功进入内核并从内核中返回, 接下来通过切换进程上下文来实现进程的切换.

进程上下文看起来比中断上下文简单许多, 不过更富技巧性.

struct context{
    uint32_t edi;
    uint32_t esi;
    uint32_t ebx;
    uint32_t ebp;
    uint32_t eip;
};

这个上下文同样是建立在进程的内核栈上的,但是内核原来的栈也保存了一个.

我们用下面这个函数来切换进程上下文:

; context_switch(struct context **old, context *new)
; 当你调用这个函数时, 会依次 压入 new, old 和 eip
[global context_switch]
context_switch:
    mov eax, [esp + 4]  ; 把 old 放到 eax
    mov edx, [esp + 8]  ; 把 new 放到 edx

    ; 这里已经隐式地保存了 eip
    push ebp
    push ebx
    push esi
    push edi
; 此时的栈结构就是一个 `strcut context`

    mov [eax], esp      ; 把 esp 保存到 old 指向的地址
    mov esp, edx        ; 切换到 new 指向的地址作为栈

    pop edi
    pop esi
    pop ebx
    pop ebp
    ; 还剩下一个 eip 未弹出, 刚好由 ret 弹出, 这样就切换到了 new 里面的 eip
    ret

这里的 eip 和 esp 的保存都非常巧妙, eip 在执行 context_switch 时被压入, 又在 ret 的时候被弹出. 而 esp 则直接作为 context 的地址被保存.

可以看到这个函数可以切换当前的执行流到另一个执行流, 进程的切换就是这样实现的, 当然要切换的不止这个, 页表也要切换, 代表当前执行进程的 proc 变量也要更新. 页表的切换由 uvm_switch 执行, proc 的更新则在 scheduler 执行.

虚拟内存映射

由于之前的思路问题, 因此 OS67 的内存管理方式不得不和 xv6 不太一样.

OS67 的内存分配实现在 OS67/mm/pmm.c, 使用一个简单的栈来存放未分配的内存页, malloc 就是 pop 而 mfree 就是 push. 这么做简单明了, 虽然申请多个页的时候效率不高, 不过我们不考虑这种需要大量内存的情况.

对于虚拟内存映射, 策略是这样的: 内核以及未分配的内存的虚拟地址和物理地址一一对应, 用户地址映射到 0xc0000000 上. 内核在初始化页表的时候, 建立一个映射所有物理内存的页表, 之后建立的进程页表中的内核部分就复用内核页表的页表项, 避免内存浪费, 同时在特权级转换时也不必切换页表, 亦能很方便地从内核空间访问到用户空间的内存.

将用户地址映射到 0xc0000000 的好处是不需要在建立正式页表前建立临时页表来把内核映射到高处, 另外 malloc 出来的是物理地址, 可以直接对其读写而不必做转换. 缺点则是程序必须经过重定位(链接时使用参数 -Ttext 0xc0000000)才能运行在高地址, 也许有更多的缺点还没发现.

第一个进程

构造

结构体 proc 用来储存一个进程的信息, 内核中有一个数组struct ptable[NPROC]来管理所有的进程. 结构体proc定义如下:

struct proc{
    volatile uint8_t pid;
    uint32_t size;
    uint8_t state;
    uint8_t killed;
    char name[NAME_LEN];

    // context
    struct int_frame *fm;       // 中断上下文
    struct context *context;    // 进程上下文

    pde_t *pgdir;               // 进程页表
    char *kern_stack;           // 内核栈

    void *chan;

    struct file *ofile[NOFILE];
    struct inode *cwd;
    struct proc *parent;
};

这里主要关注的是两个上下文, 进程页表以及内核栈.

这里涉及的代码都在OS37/proc/proc.c中.

第一个进程需要手动创建, 由proc_init完成.

proc_inint首先调用proc_alloc从ptable获得一个空的进程结构体槽位, proc_alloc做了一些必要的初始化操作.

proc_alloc为新进程申请了内核栈, 并对他进行了一定的构造:

为中断上下文fm留出空间, 并把proc->fm指向该空间.
在fm之后放置了指向中断返回函数_isr_stub_ret的指针
为进程上下文context留出空间, 并把proc->content改空间, 把proc->context-eip指向了函数fork_ret.

在 xv6 中fork_ret被用来处理锁, 这 OS67 中, 这个函数碰巧被用来解决一个 奇怪的 bug . 因此, 正常 alloc 出来的新进程都会返回到fork_ret. 从fork_ret返回后, 又会跳转到_isr_stub_ret准备从中断返回. 接下来就会逐步把fm弹出, 尽管此时的fm还没有初始化.

之后proc_init为第一个进程申请了一个页目录proc->pgdir, 调用kvm_init建立到内核的一对一的地址映射. 为之前的内核栈也建立地址映射.

再接着, 通过声明在用户程序OS67/proc/init.asm中的全局变量__init_start __init_end 的地址获得编译进内核里的用户程序的位置, 调用uvm_init_fst把程序复制到一个新的页中, 并把该页映射到USER_BASE(0xc0000000).

然后开始手动构建一个fm, 为各个段寄存器设置正确的段选择子, 为 eflags 寄存器加上 IF 标志(允许中断), 设置用户栈, 最后把eip设定为USER_BASE.

最后把进程的状态proc->state设置为可运行 P_RUNABLE.

以上是比较关键的步骤, 现在可以准备运行第一个进程了.

运行

执行了proc_init之后, scheduler紧接其后, 它在ptable中寻找第一个state为P_RUNABLE的进程, 调用uvm_switch切换到该进程的页表并设置好 TSS.

接着更新proc变量, 把proc->state设置为P_RUNNING. 最后调用context_switch切换到进程. 不出意外的话, context_switch会弹出proc->context中设定好的寄存器, 新进程返回到fork_ret之后返回到_isr_stub_ret中, 又把proc->fm弹出. 于是第一个进程就成功运行在 0xc0000000 的用户空间上了.

调度

这里使用非常简单的轮转法, 每次触发时钟中断都会执行sched, sched把当前进程状态由P_RUNNING变更为P_RUNABLE. 接着执行context_switch. 这样 CPU 执行流就回到了刚才scheduler中的循环, scheduler继续寻找一个P_RUNABLE的进程并切换到它.

E.N.D.

至此, 用户级进程已经成功实现并且被调度. 但是没有有效的接口来启动更多的进程. 我们需要实现一些系统调用比如fork和exec来做这些事情. :( 但是我已经写不下去了… 如果可以话下次再写吧.

~~不一定有下次~~

Comment box 兴歇消长琐事多，邮件才是永恒的沟通方式。如果你有不得不说的话，请到我的主页发邮件给我吧。

14 Sep 2015

上 • 立 Flag 下 • 2015 华山杯 CTF Reverse 300

谷月轩