天衣有縫

第8課：內(nèi)存管理    下載源代碼

聲明：轉(zhuǎn)載請(qǐng)保留：

譯者：http://www.shnenglu.com/jinglexy

原作者：xiaoming.mo at skelix dot org

MSN & Email: jinglexy at yahoo dot com dot cn

目標(biāo)

抱歉，其實(shí)還沒(méi)有實(shí)現(xiàn)。在任務(wù)分配獨(dú)立的4G地址空間上調(diào)試失敗了，現(xiàn)在只使能了分頁(yè)機(jī)制，頁(yè)異常。大量的工作未實(shí)現(xiàn)，有興趣的同學(xué)可以搜索buddy和slab的相關(guān)資料，經(jīng)典的內(nèi)存管理算法。

分頁(yè)

386處理器的內(nèi)存管理單元可以實(shí)現(xiàn)任務(wù)獨(dú)立地址空間，任務(wù)間內(nèi)存保護(hù)。每個(gè)任務(wù)可以擁有獨(dú)立的4G虛擬地址空間。內(nèi)存映射是內(nèi)存管理很重要的一步，可以分為兩部分：分段和分頁(yè)。前面的課程中已經(jīng)討論過(guò)分段機(jī)制了，通過(guò)分段可以隔開(kāi)不同的代碼，數(shù)據(jù)，堆棧等；分頁(yè)單元把虛擬地址映射成物理地址，還可以用來(lái)實(shí)現(xiàn)虛擬內(nèi)存（和硬盤分區(qū)進(jìn)行交換），現(xiàn)在我們來(lái)了解一下它。

對(duì)于每個(gè)任務(wù)，我們無(wú)法分配4G的物理內(nèi)存，所以使用了一些機(jī)制來(lái)管理內(nèi)存：及虛擬內(nèi)存機(jī)制。該機(jī)制有處理器的分頁(yè)部分來(lái)實(shí)現(xiàn)，首先我們將內(nèi)存分成一些塊，每個(gè)塊大小為4k，通常我們稱之為一個(gè)頁(yè)幀。操作系統(tǒng)通過(guò)頁(yè)目錄和頁(yè)表來(lái)管理這些頁(yè)幀。頁(yè)目錄是相當(dāng)于第一級(jí)頁(yè)表，其中的每一項(xiàng)再管理一個(gè)下級(jí)頁(yè)表。（更詳細(xì)過(guò)程請(qǐng)參考intel的IA 32/64手冊(cè)）

當(dāng)分頁(yè)機(jī)制開(kāi)啟時(shí)，處理器把任務(wù)中的虛擬地址轉(zhuǎn)換成物理地址，步驟如下：
1.查找段選擇子在GDT 或 LDT 中的描述符，做一些權(quán)限檢查，看看能否訪問(wèn)

2.以描述符中的基址相加頁(yè)目錄基址得到一個(gè)線性地址

3.在頁(yè)表中索引虛擬地址所對(duì)應(yīng)的頁(yè)表項(xiàng)，得到頁(yè)地址

4.查找偏移得到實(shí)際物理地址。

如果實(shí)際物理頁(yè)不存在（可能交換到硬盤中去了），則引發(fā)異常，可以在這個(gè)異常里面做想要做的事情（加載硬盤中的交換頁(yè)，或者kill這個(gè)程序：Segment Fault，等等）

處理器使用的頁(yè)目錄或者頁(yè)表，都是由32 位的項(xiàng)組成：

頁(yè)目錄項(xiàng)：

 31                    12    11    9    876   5   43    2     1     0

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓

┃   指向頁(yè)表的物理地址  ┃ 用戶定義 ┃  X  ┃ A┃ X ┃ U/S┃ R/W┃ P ┃

┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

頁(yè)表項(xiàng)：

 31                    12    11    9   87  6  5   43    2     1     0

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓

┃   指向頁(yè)幀的物理地址  ┃ 用戶定義 ┃ X┃D┃ A┃ X ┃ U/S┃ R/W┃ P ┃

┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

從上面可以知道，頁(yè)目錄項(xiàng)和頁(yè)表項(xiàng)的結(jié)構(gòu)很類似，下面逐個(gè)說(shuō)明一下其中的域：

頁(yè)目錄的每一項(xiàng)：即頁(yè)表的物理地址，它的高20 位地址表示有個(gè)頁(yè)幀的起始地址，正好和4k對(duì)齊。2^20可以表示1M范圍，每個(gè)頁(yè)幀大小是4k，所以可以索引1M * 4K地址空間。頁(yè)目錄項(xiàng)中還有一個(gè)D 位，它用來(lái)表示一個(gè)頁(yè)幀是否已修改，linux用它來(lái)表示一個(gè)頁(yè)面釋放是臟頁(yè)面，這個(gè)位非常有用，當(dāng)一個(gè)頁(yè)幀交換到硬盤上后，如果該頁(yè)幀還沒(méi)有被修改，而且是已經(jīng)從硬盤交換出來(lái)的，則簡(jiǎn)單取消以后的交換。

為了將邏輯地址轉(zhuǎn)換成物理地址，邏輯地址被分成3 部分：

舉例來(lái)說(shuō)，我們有一個(gè)邏輯地址：0x3E837B0A。前提條件：CR3寄存器指向的頁(yè)目錄地址是 0x0005C000，這個(gè)寄存器存儲(chǔ)了當(dāng)前頁(yè)目錄所使用的頁(yè)幀的物理地址，通常也叫做 PDBR。

先取它的高10位， 就是0x0FA，由它可以索引到頁(yè)目錄的第0x0FA項(xiàng)，我們?nèi)〉眠@一項(xiàng)的值，假設(shè)得到的地址值是0x0003F000。然后我們?nèi)√摂M地址的中間10位，就是0x037，再取出0x0003F000指向頁(yè)幀的第0x037項(xiàng)的值，假設(shè)是0x0001B000。這個(gè)地址就是我們要找的虛擬地址對(duì)應(yīng)的物理地址的頁(yè)幀的起始地址，最后加上偏移值（低12位），即0xB0A，得到實(shí)際的物理地址是：0x0001BB0A。

相關(guān)的知識(shí)可以參考 Intel 的IA 32/64手冊(cè)。

CR3寄存器必須在分頁(yè)機(jī)制開(kāi)啟前就裝載好，可以使用MOV 指令或者在任務(wù)切換時(shí)使用TSS中的CR3域的值。當(dāng)處理器訪問(wèn)不存在的頁(yè)幀時(shí)，發(fā)生一個(gè)異常，CR2 寄存器存引發(fā)異常的邏輯地址，同時(shí)錯(cuò)誤碼也會(huì)壓入到堆棧中，錯(cuò)誤碼格式如下：

 31                                                 3   2     1     0

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓

┃                    未使用                         ┃ U/S┃ R/W┃ P ┃

┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

異常處理例程通常采取如下的步驟：

查找一個(gè)空閑的頁(yè)幀或從硬盤中將頁(yè)幀交換出來(lái)，重新設(shè)置正確的頁(yè)目錄項(xiàng)或頁(yè)表項(xiàng)的值，刷新TLB。處理器通常保存最近最多訪問(wèn)的頁(yè)目錄或頁(yè)表項(xiàng)到一個(gè)cache中，以避免每次都進(jìn)行虛擬地址到物理地址的轉(zhuǎn)換，這個(gè)cache就叫做TLB。只有我們改動(dòng)了頁(yè)目錄或頁(yè)表項(xiàng)，就應(yīng)當(dāng)刷新TLB。方法很簡(jiǎn)單，就是重新加載CR3 寄存器。

現(xiàn)在我們來(lái)看看代碼段，內(nèi)存管理通常少不了大量的宏定義：

08/include/kernel.h

#define PAGE_DIR    ((HD0_ADDR+HD0_SIZE+(4*1024)-1) & 0xfffff000)

物理內(nèi)存安排：IDT（在0x40000），接下來(lái)是GDT，接下來(lái)是HD0使用，然后才是頁(yè)目錄，

所以這個(gè)宏看起來(lái)有點(diǎn)長(zhǎng)。

08/include/mm.h
#define PAGE_SIZE    (4*1024)                    /* 頁(yè)幀粒度 */
#define PAGE_TABLE    (PAGE_DIR+PAGE_SIZE)       /* 頁(yè)表物理地址 */
#define MEMORY_RANGE (4*1024)                    /* skelix只管理4M 內(nèi)存暫時(shí) */

08/mm.c

/* 物理內(nèi)存使用情況的位圖表 */

static char mmap[MEMORY_RANGE/PAGE_SIZE] = {PG_REVERSED, };

void
mm_install(void) {
    unsigned int *page_dir = ((unsigned int *)PAGE_DIR);
    unsigned int *page_table = ((unsigned int *)PAGE_TABLE);
    unsigned int address = 0;
    int i;
    for(i=0; i<MEMORY_RANGE/PAGE_SIZE; ++i) {
        /* 頁(yè)表項(xiàng)屬性設(shè)置為: kernel, r/w, present */
        page_table[i] = address|7;
        address += PAGE_SIZE;
    };

    // 上面循環(huán)初始化了0~4M對(duì)應(yīng)的所有頁(yè)表項(xiàng)

    page_dir[0] = (PAGE_TABLE|7);

    // 頁(yè)目錄項(xiàng)只需要第一個(gè)就可以了，因?yàn)橹挥?span lang="EN-US">4M內(nèi)存

    for (i=1; i<1024; ++i)
        page_dir[i] = 6;

    // 其他的1023個(gè)頁(yè)目錄項(xiàng)設(shè)置為空，如果這1024項(xiàng)都設(shè)置，可訪問(wèn)4G內(nèi)存空間

    // 設(shè)置0～1M內(nèi)存為已使用。
    for (i=(1*1024*1024)/PAGE_SIZE-1; i>=0; --i)
        mmap[i] = PG_REVERSED;

    // 因?yàn)閮?nèi)核只用到了低于1M的內(nèi)存，所以保留它們，這樣就不會(huì)被交換出去了

    __asm__ (
        "movl    %%eax,    %%cr3\n\t"        // 加載頁(yè)目錄基址到寄存器
        "movl    %%cr0,    %%eax\n\t"
        "orl    $0x80000000,    %%eax\n\t"
        "movl    %%eax,    %%cr0"::"a"(PAGE_DIR));    // 開(kāi)啟分頁(yè)機(jī)制，CR0的最高位
}

通過(guò)mmap位圖，我們可以清楚的知道內(nèi)存的使用情況，這樣就可以分配空閑頁(yè)幀了，如下：
08/mm.c

unsigned int
alloc_page(int type) {
    int i;

    for (i=(sizeof mmap)-1; i>=0 && mmap[i]; --i)
        ;

    if (i < 0) {
        kprintf(KPL_PANIC, "NO MEMORY LEFT");
        halt();
    }
    mmap[i] = type;
    return i;            // 返回頁(yè)幀號(hào)
}

void *
page2mem(unsigned int nr) {            // 轉(zhuǎn)換為虛擬地址
    return (void *)(nr * PAGE_SIZE);
}

void
do_page_fault(enum KP_LEVEL kl,
              unsigned int ret_ip, unsigned int ss, unsigned int gs,
              unsigned int fs, unsigned int es, unsigned int ds,
              unsigned int edi, unsigned int esi, unsigned int ebp,
              unsigned int esp, unsigned int ebx, unsigned int edx,
              unsigned int ecx, unsigned int eax, unsigned int isr_nr,
              unsigned int err, unsigned int eip, unsigned int cs,
              unsigned int eflags,unsigned int old_esp, unsigned int old_ss) {
    unsigned int cr2, cr3;
    (void)ret_ip; (void)ss; (void)gs; (void)fs; (void)es;
    (void)ds; (void)edi; (void)esi; (void)ebp; (void)esp;
    (void) ebx; (void)edx; (void)ecx; (void)eax;
    (void)isr_nr; (void)eip; (void)cs; (void)eflags;
    (void)old_esp; (void)old_ss; (void)kl;
    __asm__ ("movl %%cr2, %%eax":"=a"(cr2));
    __asm__ ("movl %%cr3, %%eax":"=a"(cr3));
    kprintf(KPL_PANIC, "\n  The fault at %x cr3:%x was caused by a %s. "
            "The accessing cause of the fault was a %s, when the "
            "processor was executing in %s mode, page %x is free\n",
            cr2, cr3,
            (err&0x1)?"page-level protection voilation":"not-present page",
            (err&0x2)?"write":"read",
            (err&0x4)?"user":"supervisor",
            alloc_page(PG_NORMAL));
}

頁(yè)異常函數(shù)，它什么也沒(méi)有做，知識(shí)顯示一些錯(cuò)誤信息。

現(xiàn)在我們來(lái)動(dòng)態(tài)的分配一些內(nèi)存，我們修改一下任務(wù)函數(shù)：
08/init.c

static void
new_task(unsigned int eip) {
    struct TASK_STRUCT *task = page2mem(alloc_page(PG_TASK));
    memcpy(&(task->tss), &(TASK0.tss), sizeof(struct TSS_STRUCT));

    task->tss.esp0 = (unsigned int)task + PAGE_SIZE;
    task->tss.eip = eip;
    task->tss.eflags = 0x3202;
    task->tss.esp = (unsigned int)page2mem(alloc_page(PG_TASK))+PAGE_SIZE;
    task->tss.cr3 = PAGE_DIR;
    task->priority = INITIAL_PRIO;
    task->ldt[0] = DEFAULT_LDT_CODE;
    task->ldt[1] = DEFAULT_LDT_DATA;

    task->next = current->next;
    current->next = task;
    task->state = TS_RUNABLE;
}

自己分配的任務(wù)數(shù)據(jù)結(jié)構(gòu)和任務(wù)堆棧，是不是很有成就感：）

最后在init.c中添加初始化代碼：
08/init.c

void
init(void) {
    char wheel[] = {'\\', '|', '/', '-'};
    int i = 0;

    idt_install();
    pic_install();
    mm_install();      /* 初始化函數(shù)調(diào)用 */
    kb_install();
    timer_install(100);
    set_tss((unsigned long long)&TASK0.tss);
    set_ldt((unsigned long long)&TASK0.ldt);
    __asm__ ("ltrw    %%ax\n\t"::"a"(TSS_SEL));
    __asm__ ("lldt    %%ax\n\t"::"a"(LDT_SEL));

    kprintf(KPL_DUMP, "Verifing disk partition table....\n");
    verify_DPT();
    kprintf(KPL_DUMP, "Verifing file systes....\n");
    verify_fs();
    kprintf(KPL_DUMP, "Checking / directory....\n");
    verify_dir();

    sti();
    new_task((unsigned int)task1_run);
    new_task((unsigned int)task2_run);
    __asm__ ("movl %%esp,%%eax\n\t" \
             "pushl %%ecx\n\t" \
             "pushl %%eax\n\t" \
             "pushfl\n\t" \
             "pushl %%ebx\n\t" \
             "pushl $1f\n\t" \
             "iret\n" \
             "1:\tmovw %%cx,%%ds\n\t" \
             "movw %%cx,%%es\n\t" \
             "movw %%cx,%%fs\n\t" \
             "movw %%cx,%%gs" \
             ::"b"(USER_CODE_SEL),"c"(USER_DATA_SEL));
    __asm__ ("incb 0xeeffeeff");         /* 測(cè)試：觸發(fā)一個(gè)異常 */
    for (;;) {
        __asm__ ("movb    %%al,    0xb8000+160*24"::"a"(wheel[i]));
        if (i == sizeof wheel)
            i = 0;
        else
            ++i;
    }
}

異常處理例程中什么也沒(méi)做，訪問(wèn)內(nèi)存出錯(cuò)則死機(jī)：

08/exceptions.c

void
page_fault(void) {
    __asm__ ("pushl    %%eax;call    do_page_fault"::"a"(KPL_PANIC));
    halt();
}

最后把mm.o 添加到 Makefile 的KERNEL_OBJS 中去：

08/Makefile

KERNEL_OBJS= load.o init.o isr.o timer.o libcc.o scr.o kb.o task.o kprintf.o hd.o exceptions.o fs.o mm.o