搶占式多進(jìn)程處理 & 進(jìn)程間通信

作為 lab4 的最后一步，我們要修改內(nèi)核使之能搶占一些不配合的進(jìn)程占用的資源，以及允許進(jìn)程之間的通信。

Part I: 時(shí)鐘中斷以及搶占

嘗試運(yùn)行一下 user/spin 測(cè)試，該測(cè)試建立一個(gè)子進(jìn)程，該子進(jìn)程獲得 CPU 資源后就進(jìn)入死循環(huán)，這樣內(nèi)核以及父進(jìn)程都無(wú)法再次獲得 CPU。這顯然是操作系統(tǒng)需要避免的。為了允許內(nèi)核從一個(gè)正在運(yùn)行的進(jìn)程搶奪 CPU 資源，我們需要支持來(lái)自硬件時(shí)鐘的外部硬件中斷。

Interrupt discipline

外部中斷用 IRQ(Interrupt Request) 表示。一共有 16 種 IRQ，在 picirq.c中將其增加了 IRQ_OFFSET 的偏移映射到了 IDT。
在 inc/trap.h 中， IRQ_OFFSET 被定義為 32。因此，IDT[32] 包含了時(shí)鐘中斷的處理入口地址。
聯(lián)想 Lab3 中的內(nèi)容：

x86 的所有異?？梢杂弥袛嘞蛄?0~31 表示，對(duì)應(yīng) IDT 的第 0~31 項(xiàng)。例如，頁(yè)錯(cuò)誤產(chǎn)生一個(gè)中斷向量為 14 的異常。大于 32 的中斷向量表示的都是中斷

相對(duì) xv6，在 JOS 中我們中了一個(gè)關(guān)鍵的簡(jiǎn)化：在內(nèi)核態(tài)時(shí)禁用外部設(shè)備中斷。外部中斷使用 %eflag 寄存器的 FL_IF 位控制。當(dāng)該位置 1 時(shí)，開(kāi)啟中斷。由于我們的簡(jiǎn)化，我們只在進(jìn)入以及離開(kāi)內(nèi)核時(shí)需要修改這個(gè)位。

我們需要確保在用戶態(tài)時(shí) FL_IF 置 1，使得當(dāng)有中斷發(fā)生時(shí)，可以被處理。我們?cè)?bootloader 的第一條指令 cli 就關(guān)閉了中斷，然后再也沒(méi)有開(kāi)啟過(guò)。

Exercise 13.
Modify kern/trapentry.S and kern/trap.c to initialize the appropriate entries in the IDT and provide handlers for IRQs 0 through 15. Then modify the code in env_alloc() in kern/env.c to ensure that user environments are always run with interrupts enabled.

比較簡(jiǎn)單，跟 Lab3 中的 Exercise 4 大同小異。相關(guān)的常數(shù)定義在 inc/trap.h 中可以找到。
在 kern/trapentry.S 中加入：

// IRQs
TRAPHANDLER(handler32, IRQ_OFFSET + IRQ_TIMER)
TRAPHANDLER(handler33, IRQ_OFFSET + IRQ_KBD)
TRAPHANDLER(handler36, IRQ_OFFSET + IRQ_SERIAL)
TRAPHANDLER(handler39, IRQ_OFFSET + IRQ_SPURIOUS)
TRAPHANDLER(handler46, IRQ_OFFSET + IRQ_IDE)
TRAPHANDLER(handler51, IRQ_OFFSET + IRQ_ERROR)

在 kern/trap.c 的 trap_init() 中加入：

    // IRQs
    void handler32();
    void handler33();   
    void handler36();
    void handler39();
    void handler46();
    void handler51();
...
    // IRQs
    SETGATE(idt[IRQ_OFFSET + IRQ_TIMER], 0, GD_KT, handler32, 0);
    SETGATE(idt[IRQ_OFFSET + IRQ_KBD], 0, GD_KT, handler33, 0);
    SETGATE(idt[IRQ_OFFSET + IRQ_SERIAL], 0, GD_KT, handler36, 0);
    SETGATE(idt[IRQ_OFFSET + IRQ_SPURIOUS], 0, GD_KT, handler39, 0);
    SETGATE(idt[IRQ_OFFSET + IRQ_IDE], 0, GD_KT, handler46, 0);
    SETGATE(idt[IRQ_OFFSET + IRQ_ERROR], 0, GD_KT, handler51, 0);

在 kern/env.c 的 env_alloc() 中加入：

    // Enable interrupts while in user mode.
    // LAB 4: Your code here.
    e->env_tf.tf_eflags |= FL_IF;

Handling Clock Interrupts

在 user/spin 程序中，子進(jìn)程開(kāi)啟后就陷入死循環(huán)，此后 kernel 無(wú)法再獲得控制權(quán)。我們需要讓硬件周期性地產(chǎn)生時(shí)鐘中斷，強(qiáng)制將控制權(quán)交給 kernel，使得我們能夠切換到其他進(jìn)程。

Exercise 14.
Modify the kernel's trap_dispatch() function so that it calls sched_yield() to find and run a different environment whenever a clock interrupt takes place.

這個(gè)練習(xí)本身非常簡(jiǎn)單，但是我卻出現(xiàn)了一個(gè)錯(cuò)誤，即在 kern/trap.c 中的 trap() 函數(shù)中無(wú)法通過(guò)這個(gè)斷言：

    assert(!(read_eflags() & FL_IF));

這個(gè)問(wèn)題非常難查，浪費(fèi)了2天時(shí)間。最終在網(wǎng)上多方比較代碼后，發(fā)現(xiàn)其實(shí)是 Lab3 的 Exercise 4 中的遺留問(wèn)題。它雖然不影響之前的練習(xí)，但是這里卻暴露出來(lái)。實(shí)際上是對(duì) SETGATE 這個(gè)宏理解不夠?qū)е碌摹．?dāng)時(shí)我根據(jù)對(duì)注釋的理解，把 SETGATE 的第二個(gè)參數(shù)都寫成了 1。主要是被注釋中的 istrap: 1 for a trap (= exception) gate, 0 for an interrupt gate. 誤導(dǎo)。

SETGATE(idt[T_PGFLT], 1, GD_KT, handler14, 0);

但是，根據(jù) SETGATE 的注釋，其真實(shí)的區(qū)別在于，設(shè)為 1 就會(huì)在開(kāi)始處理中斷時(shí)將 FL_IF 位重新置1，而設(shè)為 0 則保持 FL_IF 位不變。根據(jù)這里的需求，顯然應(yīng)該置0。

// Set up a normal interrupt/trap gate descriptor.
// - istrap: 1 for a trap (= exception) gate, 0 for an interrupt gate.
    //   see section 9.6.1.3 of the i386 reference: "The difference between
    //   an interrupt gate and a trap gate is in the effect on IF (the
    //   interrupt-enable flag). An interrupt that vectors through an
    //   interrupt gate resets IF, thereby preventing other interrupts from
    //   interfering with the current interrupt handler. A subsequent IRET
    //   instruction restores IF to the value in the EFLAGS image on the
    //   stack. An interrupt through a trap gate does not change IF."
// - sel: Code segment selector for interrupt/trap handler
// - off: Offset in code segment for interrupt/trap handler
// - dpl: Descriptor Privilege Level -
//    the privilege level required for software to invoke
//    this interrupt/trap gate explicitly using an int instruction.
#define SETGATE(gate, istrap, sel, off, dpl)            \
{                               \
    (gate).gd_off_15_0 = (uint32_t) (off) & 0xffff;     \
    (gate).gd_sel = (sel);                  \
    (gate).gd_args = 0;                 \
    (gate).gd_rsv1 = 0;                 \
    (gate).gd_type = (istrap) ? STS_TG32 : STS_IG32;    \
    (gate).gd_s = 0;                    \
    (gate).gd_dpl = (dpl);                  \
    (gate).gd_p = 1;                    \
    (gate).gd_off_31_16 = (uint32_t) (off) >> 16;       \
}

這個(gè)最大的坑解決后，后面的就很簡(jiǎn)單了。直接在 trap_dispatch() 中添加時(shí)鐘中斷的分支即可。

    // Handle clock interrupts. Don't forget to acknowledge the
    // interrupt using lapic_eoi() before calling the scheduler!
    // LAB 4: Your code here.
    if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
        lapic_eoi();
        sched_yield();
        return;
    }

總結(jié)就是，實(shí)在太坑。異常處理的內(nèi)容實(shí)在太多，戰(zhàn)線太長(zhǎng)了。出了錯(cuò)誤非常難找。

Part II: 進(jìn)程間通信(IPC)

在之前的 Lab 中，我們一直在講操作系統(tǒng)是如何隔離各個(gè)進(jìn)程的，怎么讓程序感覺(jué)獨(dú)占一臺(tái)機(jī)器的。操作系統(tǒng)的另一個(gè)重要功能就是允許進(jìn)程之間相互通信。

IPC in JOS

我們將實(shí)現(xiàn)兩個(gè)系統(tǒng)調(diào)用：sys_ipc_recv 以及 sys_ipc_try_send ，再將他們封裝為兩個(gè)庫(kù)函數(shù)，ipc_recv 和 ipc_send 以支持通信。
實(shí)際上，進(jìn)程之間發(fā)送的信息是由兩個(gè)部分組成，一個(gè) int32_t，一個(gè)頁(yè)面映射(可選)。

發(fā)送和接收消息

進(jìn)程使用 sys_ipc_recv 來(lái)接收消息。該系統(tǒng)調(diào)用會(huì)將程序掛起，讓出 CPU 資源，直到收到消息。在這個(gè)時(shí)期，任一進(jìn)程都能給他發(fā)送信息，不限于父子進(jìn)程。
為了發(fā)送信息，進(jìn)程會(huì)調(diào)用 sys_ipc_try_send，以接收者的進(jìn)程 id 以及要發(fā)送的值為參數(shù)。如果接收者已經(jīng)調(diào)用了 sys_ipc_recv ，則成功發(fā)送消息并返回0。否則返回 E_IPC_NOT_RECV 表明目標(biāo)進(jìn)程并沒(méi)有接收消息。
ipc_send 庫(kù)函數(shù)將會(huì)反復(fù)執(zhí)行 sys_ipc_try_send 直到成功。

傳遞頁(yè)面

當(dāng)進(jìn)程調(diào)用 sys_ipc_recv 并提供一個(gè)虛擬地址 dstva (必須位于用戶空間) 時(shí)，進(jìn)程表示它希望能接收一個(gè)頁(yè)面映射。如果發(fā)送者發(fā)送一個(gè)頁(yè)面，該頁(yè)面就會(huì)被映射到接收者的 dstva。同時(shí)，之前位于 dstva 的頁(yè)面映射會(huì)被覆蓋。

當(dāng)進(jìn)程調(diào)用 sys_ipc_try_send 并提供一個(gè)虛擬地址 srcva (必須位于用戶空間)，表明發(fā)送者希望發(fā)送位于 srcva 的頁(yè)面給接收者，權(quán)限設(shè)置為 perm。

在一個(gè)成功的 IPC 之后，發(fā)送者和接受者將共享一個(gè)物理頁(yè)。

Exercise 15.
Implement sys_ipc_recv and sys_ipc_try_send in kern/syscall.c. Read the comments on both before implementing them, since they have to work together. When you call envid2env in these routines, you should set the checkperm flag to 0, meaning that any environment is allowed to send IPC messages to any other environment, and the kernel does no special permission checking other than verifying that the target envid is valid.
Then implement the ipc_recv and ipc_send functions in lib/ipc.c.

首先需要仔細(xì)閱讀 inc/env.h 了解用于傳遞消息的數(shù)據(jù)結(jié)構(gòu)。

    // Lab 4 IPC
    bool env_ipc_recving;       // Env is blocked receiving
    void *env_ipc_dstva;        // VA at which to map received page
    uint32_t env_ipc_value;     // Data value sent to us
    envid_t env_ipc_from;       // envid of the sender
    int env_ipc_perm;       // Perm of page mapping received

然后需要注意的是通信流程。

1. 調(diào)用 ipc_recv，設(shè)置好 Env 結(jié)構(gòu)體中的相關(guān) field
2. 調(diào)用 ipc_send，它會(huì)通過(guò) envid 找到接收進(jìn)程，并讀取 Env 中剛才設(shè)置好的 field，進(jìn)行通信。
3. 最后返回實(shí)際上是在 ipc_send 中設(shè)置好 reg_eax，在調(diào)用結(jié)束，退出內(nèi)核態(tài)時(shí)返回。

過(guò)程看似很簡(jiǎn)單，其實(shí)坑很多。首先從調(diào)用過(guò)程入手，這部分比較簡(jiǎn)單。

lib 部分

int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
    // LAB 4: Your code here.
    // panic("ipc_recv not implemented");

    int r;
    if (pg != NULL) {
        r = sys_ipc_recv(pg);
    } else {
        r = sys_ipc_recv((void *) UTOP);
    }
    if (r < 0) {
        // failed
        if (from_env_store != NULL) *from_env_store = 0;
        if (perm_store != NULL) *perm_store = 0;
        return r;
    } else {
        if (from_env_store != NULL) *from_env_store = thisenv->env_ipc_from;
        if (perm_store != NULL) *perm_store = thisenv->env_ipc_perm;
        return thisenv->env_ipc_value;
    }
}

void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
    // LAB 4: Your code here.
    // panic("ipc_send not implemented");

    int r;
    if (pg == NULL) pg = (void *)UTOP;
    do {
        r = sys_ipc_try_send(to_env, val, pg, perm);
        if (r < 0 && r != -E_IPC_NOT_RECV) panic("ipc send failed: %e", r);
        sys_yield();
    } while (r != 0);
}

需要注意的不多。主要的 trick 就一個(gè)，如果不需要共享頁(yè)面，則把作為參數(shù)的虛擬地址設(shè)為 UTOP，這個(gè)地址在下面的系統(tǒng)調(diào)用實(shí)現(xiàn)中，會(huì)被忽略掉。

sys_ipc_recv()

// 接收
static int
sys_ipc_recv(void *dstva)
{
    // LAB 4: Your code here.
    // panic("sys_ipc_recv not implemented");
    
    // wrong, because when we don't want to share page, we set dstva=UTOP
    // but we can still pass value
    // if ( (uintptr_t) dstva >= UTOP) return -E_INVAL;
    if ((uintptr_t) dstva < UTOP && PGOFF(dstva) != 0) return -E_INVAL;

    envid_t envid = sys_getenvid();
    struct Env *e;
    // do not check permission
    if (envid2env(envid, &e, 0) < 0) return -E_BAD_ENV;
    
    e->env_ipc_recving = true;
    e->env_ipc_dstva = dstva;
    e->env_status = ENV_NOT_RUNNABLE;
    sys_yield();

    return 0;
}

這個(gè)函數(shù)有個(gè)大坑，已經(jīng)注釋出來(lái)。

• 如果作為參數(shù)的虛擬地址在 UTOP 之上，只需要忽略，而不是報(bào)錯(cuò)退出。因?yàn)檫@種情況是說(shuō)明接收者只需要接收值，而不需要共享頁(yè)面（聯(lián)想在 lib/ipc.c 中的處理）。

sys_ipc_try_send()

這里的需求與 sys_page_map() 非常相似，我一直嘗試通過(guò)調(diào)用 sys_page_map() 解決，這樣可以避免編寫大量重復(fù)代碼。但是發(fā)現(xiàn)其中最大的區(qū)別在于，ipc 通信并不限于父子進(jìn)程之間，而 sys_page_map() 最初設(shè)計(jì)的作用就是用于 fork()，因此，需要做一些小小的改動(dòng)才能用于這里，也就是說(shuō)改變 envid2env() 的參數(shù)。
如何改動(dòng)呢？首先添加一個(gè)參數(shù)是不考慮的，因?yàn)?syscall() 目前就支持 5 個(gè)參數(shù)，如果再增加參數(shù)改動(dòng)幅度太大。而且還需要改動(dòng)之前 fork() 部分的代碼。

注意到 inc/mmu.h 中，還有可以使用的權(quán)限標(biāo)識(shí)位，那么這里是否可以借用一下呢？

// The PTE_AVAIL bits aren't used by the kernel or interpreted by the
// hardware, so user processes are allowed to set them arbitrarily.
#define PTE_AVAIL   0xE00   // Available for software use

于是，實(shí)現(xiàn)為如下

static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
    // LAB 4: Your code here.
    // panic("sys_ipc_try_send not implemented");

    envid_t src_envid = sys_getenvid(); 
    struct Env *dst_e;
    if (envid2env(envid, &dst_e, 0) < 0) {
        return -E_BAD_ENV;
    }

    if (dst_e->env_ipc_recving == false) 
        return -E_IPC_NOT_RECV;
    
    // pass the value
    dst_e->env_ipc_value = value;
    dst_e->env_ipc_perm = 0;

    // pass the page
    if ((uintptr_t)srcva < UTOP) {
        // customerize 0x200 as PTE_NO_CHECK
        unsigned tmp_perm = perm | 0x200;
        int r = sys_page_map(src_envid, srcva, envid, (void *)dst_e->env_ipc_dstva, tmp_perm);
        if (r < 0) return r;
        dst_e->env_ipc_perm = perm;
    }

    dst_e->env_ipc_from = src_envid;
    dst_e->env_status = ENV_RUNNABLE;
    // return from the syscall, set %eax
    dst_e->env_tf.tf_regs.reg_eax = 0;
    dst_e->env_ipc_recving = false;
    return 0;
}

同時(shí)，修改 sys_page_map()：

static int
sys_page_map(envid_t srcenvid, void *srcva,
         envid_t dstenvid, void *dstva, int perm)
{
    // Hint: This function is a wrapper around page_lookup() and
    //   page_insert() from kern/pmap.c.
    //   Again, most of the new code you write should be to check the
    //   parameters for correctness.
    //   Use the third argument to page_lookup() to
    //   check the current permissions on the page.

    // LAB 4: Your code here.
    // panic("sys_page_map not implemented");

    if ((uintptr_t)srcva >= UTOP || PGOFF(srcva) != 0) return -E_INVAL;
    if ((uintptr_t)dstva >= UTOP || PGOFF(dstva) != 0) return -E_INVAL;
    if ((perm & PTE_U) == 0 || (perm & PTE_P) == 0 || (perm & ~PTE_SYSCALL) != 0) return -E_INVAL;
    struct Env *src_e, *dst_e;
    // add for lab4 exercise 15 for ipc.
    // customerize 0x200 as PTE_NO_CHECK
    // and we assume 0x200 is not used elsewhere, so we restore perm here.
    bool check_perm = (perm & 0x200);
    perm &= (~0x200);
    if (envid2env(srcenvid, &src_e, !check_perm)<0 || envid2env(dstenvid, &dst_e, !check_perm)<0) return -E_BAD_ENV;
    pte_t *src_ptab;    
    struct PageInfo *pp = page_lookup(src_e->env_pgdir, srcva, &src_ptab);
    if ((*src_ptab & PTE_W) == 0 && (perm & PTE_W) == 1) return -E_INVAL;
    if (page_insert(dst_e->env_pgdir, pp, dstva, perm) < 0) return -E_NO_MEM;
    return 0;
}

另外，在系統(tǒng)調(diào)用里也新增這兩個(gè)分支：

// syscall()
    case SYS_ipc_try_send:
        retVal = sys_ipc_try_send(a1, a2, (void *)a3, a4);
        break;
    case SYS_ipc_recv:
        retVal = sys_ipc_recv((void *)a1);
        break;

至此 make grade 成功。在多核情況下 make CPUS=2 grade 也通過(guò)。
Lab 4 至此結(jié)束。