MIT6.828 lab2 內存管理

Part A 物理頁管理

Exercise1

補全在kern/pmap.c下的幾個函數(shù)涯贞。

boot_alloc()
mem_init() (only up to the call to check_page_free_list(1))
page_init()
page_alloc()
page_free()

boot_alloc()

在JOS中枪狂，一開始的物理內存布局如下圖所示


物理內存布局

虛擬內存布局


虛擬內存布局

在代碼中，所有的變量的地址都是虛擬地址宋渔，JOS中虛擬地址到物理地址的轉換很簡單:

虛擬地址 = 物理地址 + KERNBASE(0xF0000000)

boot_alloc()中的end代表的就是內核代碼的最上端州疾，即內核代碼的末尾，此位置往上的物理內存都可以分配皇拣。當申請n字節(jié)大小空間的內存時严蓖，將當前nextfree保存在result當做函數(shù)返回值，然后將其向后移動ROUNDUP(n, PGSIZE)氧急，此時[result, nextfree)的空間就分配出來了颗胡。因為是按頁管理內存，所以分配的內存大小需要頁對齊态蒂。

static void *
boot_alloc(uint32_t n)
{
    static char *nextfree;  // virtual address of next byte of free memory
    char *result;
    // end: bss段的末尾杭措，正好是kernel的末尾的指針，第一個未使用的虛擬地址
    if (!nextfree) {
        extern char end[];
        nextfree = ROUNDUP((char *) end, PGSIZE);
    }
    // cprintf("nextfree: %x\n", nextfree);
    // LAB 2: Your code here.
    // 返回的是上一次的地址钾恢，然后再將nextfree往后移動手素，相當于分配空間
    result = nextfree;
    if(n != 0) {
        nextfree = ROUNDUP(nextfree + n, PGSIZE);
    }
    return result;
}

mem_init() 只需要完成到調用check_page_free_list(1)之前

在內核代碼中每個物理頁都由一個PageInfo的數(shù)據(jù)結構來標識鸳址，一共有npages個物理頁。所有的PageInfo組成一個pages數(shù)組泉懦。所以在mem_init需要先對pages結構進行物理內存分配稿黍。
之后所出現(xiàn)的物理頁其實是指PageInfo，代碼中對物理頁的操作其實都是操作PageInfo這個結構

struct PageInfo {
    // Next page on the free list.
    struct PageInfo *pp_link;

    // pp_ref is the count of pointers (usually in page table entries)
    // to this page, for pages allocated using page_alloc.
    // Pages allocated at boot time using pmap.c's
    // boot_alloc do not have valid reference count fields.

    uint16_t pp_ref;
};

void
mem_init(void)
{
    ...
    // Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
    // The kernel uses this array to keep track of physical pages: for
    // each physical page, there is a corresponding struct PageInfo in this
    // array.  'npages' is the number of physical pages in memory.  Use memset
    // to initialize all fields of each struct PageInfo to 0.
    // Your code goes here:
    // npages: 還有多少頁物理內存崩哩，每個頁都要有一個PageInfo
    pages = (struct PageInfo*)boot_alloc(sizeof(struct PageInfo) * npages);
    // cprintf("npages: %d\n", npages);
    memset(pages, 0, npages * sizeof(struct PageInfo));
    //////////////////////////////////////////////////////////////////////
    ...
}

page_init()

分配完內存后自然就要對數(shù)據(jù)結構進行初始化巡球，即將物理內存中的每一頁都與pageInfo關聯(lián)，其中分為可用頁和不可用頁邓嘹。物理內存頁到pages數(shù)組下標的映射關系為: 地址/PGSIZE(4k)酣栈。根據(jù)提示可知，一共有兩大塊空閑物理內存塊汹押。[1, npages_basemem)矿筝。第二塊就是從內核代碼往后，這個地址可以用boot_alloc(0)取到棚贾，即分配了pages內存之后的地址窖维。但這個地址在代碼中是虛擬地址，所以需要將其轉換成物理地址妙痹，可以用PADDR()宏來轉換铸史。所以第二塊范圍就是[PADDR(boot_alloc(0)/PGSIZE)，npages)怯伊。找出這些空閑頁后需要用page_free_list鏈表串起來琳轿。方便后續(xù)內存分配。

void
page_init(void)
{
    // The example code here marks all physical pages as free.
    // However this is not truly the case.  What memory is free?
    //  1) Mark physical page 0 as in use.
    //     This way we preserve the real-mode IDT and BIOS structures
    //     in case we ever need them.  (Currently we don't, but...)
    //  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
    //     is free.
    //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
    //     never be allocated.
    //  4) Then extended memory [EXTPHYSMEM, ...).
    //     Some of it is in use, some is free. Where is the kernel
    //     in physical memory?  Which pages are already in use for
    //     page tables and other data structures?
    //
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages!
    size_t i;
    for (i = 1; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;
        // 構成一個鏈表
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    
    size_t first_free_page = (size_t)PADDR(boot_alloc(0))/PGSIZE;
    // cprintf("npages_basemem: %d\n first_free_page: %d\n", npages_basemem, first_free_page);
    for (i = first_free_page; i < npages; i++) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    pages[0].pp_ref = 1;
    pages[0].pp_link = NULL;
    for(i = npages_basemem; i < first_free_page; i++) {
        pages[i].pp_ref = 1;
        pages[i].pp_link = NULL;
    }
}

page_alloc()

空閑物理頁的分配耿芹。在空閑物理頁鏈表中取出一個物理頁即可利赋。返回的是PageInfo*，這個怎么與物理內存中的物理頁對應呢猩系？

  • 注意: 兩個指針相減，結果并不是兩個指針數(shù)值上的差中燥，而是把這個差除以指針指向類型的大小的結果寇甸。

可以用page2pa(PageInfo*)的宏，因為pages數(shù)組是連續(xù)的物理內存疗涉，所以直接將PageInfo* pp 的地址減去pages就可以知道在數(shù)組中的下標是多少拿霉。在乘以4K就可以得到物理地址了: (pp-pages) << PGSHIFT。PGSHIFT = 1<<12 = 4096 = 4k咱扣。

struct PageInfo *
page_alloc(int alloc_flags)
{
    // Fill this function in
    if (page_free_list == NULL) {
        return NULL;
    }
    struct PageInfo* pageInfo = page_free_list;
    page_free_list = page_free_list->pp_link;
    pageInfo->pp_link = NULL;
    if (alloc_flags & ALLOC_ZERO) {
        // 內核虛擬地址空間映射到物理地址空間绽淘，直接減去kernbase
        memset(page2kva(pageInfo), 0, PGSIZE);
        // cprintf("page2kva(pageInfo): %x %x %d\n", pageInfo, page2kva(pageInfo), PGSIZE);
    }
    return pageInfo;
}

page_free()

這個比較簡單。頁面釋放闹伪，將物理頁重新插入到page_free_list中沪铭。前提是要保證該頁面沒有被引用壮池，并且也不在空閑鏈表中。

void
page_free(struct PageInfo *pp)
{
    // Fill this function in
    // Hint: You may want to panic if pp->pp_ref is nonzero or
    // pp->pp_link is not NULL. 
    // cprintf("pp->pp_ref: %d pp->pp_link: %d\n", pp->pp_ref, pp->pp_link == NULL);
    assert(pp->pp_ref == 0 && pp->pp_link == NULL);
    pp->pp_link = page_free_list;
    page_free_list = pp;
}

Part B 虛擬內存

Exercise2

閱讀Intel 80386 Reference Manual的第5第6章杀怠。

在x86結構下椰憋，使用的是分段分頁機制，虛擬地址轉換為物理地址需要中間還需要經(jīng)歷線性地址(分段的過程)赔退。


虛擬地址-線性地址-物理地址

下圖是具體的地址結構轉換過程橙依。
具體地址結構

在JOS中，虛擬地址=線性地址硕旗，為什么呢窗骑？因為在boot/boot.S中把所有的段地址都設置成了0 到0xffffffff，即段基址都等于0漆枚，相當于0+offset创译，所以就沒有分段的效果了。這樣我們就可以專注于實現(xiàn)分頁機制了浪读。

Exercise3

使用qemu-debug下的xp命令查看物理地址的內容昔榴。因為gdb只能獲取到虛擬地址，所以需要使用qemu的下的debug模式才能查看物理地址碘橘。
我覺得直接在程序中用cprintf也可以查看互订。

Exercise4

補全kern/pmap.c下的這些函數(shù)，實現(xiàn)頁表管理痘拆。

        pgdir_walk()
        boot_map_region()
        page_lookup()
        page_remove()
        page_insert()

在補全這些函數(shù)之前仰禽，需要先明白一個圖的含義。JOS采用的是二級頁表機制纺蛆，主要由五個元素組成吐葵，頁目錄表-頁目錄項(PDE, page diretory entry)，頁表-頁表項(PTE, page table entry)桥氏，物理頁温峭。PDE和PTE存儲的都是地址。
其中一個頁目錄項對應一個頁表字支，一個頁表項對應一個物理頁凤藏。頁目錄表的地址存儲在CR3寄存器中。


二級頁表機制

pgdir_walk()

根據(jù)(頁目錄表堕伪，虛擬地址揖庄，創(chuàng)建標志)找到該虛擬地址所對應的物理頁的虛擬地址。
通過PDX獲得va的頁目錄項在頁目錄表中的偏移取得PDE欠雌，如果該PDE所指向的PT是空的話且create == 1蹄梢，那就創(chuàng)建一個頁目錄表，即申請一頁的物理內存富俄。并設置為用戶可讀可寫禁炒。然后再根據(jù)PTX獲得va在頁表項在頁表中的偏移獲取PTE而咆，返回此PTE的地址。
PTE_ADDR(*pde)的作用是去掉后面的權限位齐苛。

頁表項的結構

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // Fill this function in
    
    int pde_index = PDX(va);
    int pte_index = PTX(va);
    pde_t *pde = &pgdir[pde_index];
    if (!(*pde & PTE_P)) {
        if (create) {
            struct PageInfo *page = page_alloc(ALLOC_ZERO);
            if (!page) return NULL;

            page->pp_ref++;
            *pde = page2pa(page) | PTE_P | PTE_U | PTE_W;
        } else {
            return NULL;
        }   
    }   

    pte_t *p = (pte_t *) KADDR(PTE_ADDR(*pde));
    return &p[pte_index];
}

boot_map_region()

之前的pgdir_walk是取到頁表項翘盖，但頁表項還未真正的映射到物理頁上，此函數(shù)將從va開始的大小為size的地址按頁從物理地址pa開始映射凹蜂。相當于對頁表項賦值馍驯。

static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
    // Fill this function in
    // 頁表項映射到物理地址, 頁表本身需要物理地址存儲，pgdir_walk得到頁表存儲的虛擬地址
    size_t i;
    
    for (i = 0; i < size; va += PGSIZE, pa += PGSIZE, i += PGSIZE) {
        pte_t* pte = pgdir_walk(pgdir, (void*)va, 1);
        // 不需要 *pte & PTE_P
        if (pte == NULL) {
            panic("error");
        }
        *pte = pa | perm | PTE_P;
    }
}

page_lookup()

返回頁表項所對應的物理頁的虛擬地址玛痊，并把頁表項存儲在pte_store中绍绘。**pte_store二級指針相當于傳入指針的引用永脓。

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    // Fill this function in
    pte_t* pte = pgdir_walk(pgdir, va, 0);
    if (pte == NULL || !(*pte & PTE_P)) {
        return NULL;
    }
    if (pte_store) {
        *pte_store = pte;
    }
    return (struct PageInfo*)pa2page(PTE_ADDR(*pte));
}

page_remove()

清空頁表項對應的物理頁,并把物理頁引用減減牡借。

void
page_remove(pde_t *pgdir, void *va)
{
    // Fill this function in
    pte_t* pte_store;
    struct PageInfo* pp = page_lookup(pgdir, va, &pte_store);
    if(pp == NULL || !(*pte_store & PTE_P)) 
        return;
    page_decref(pp);
    *pte_store = 0;
    tlb_invalidate(pgdir, va);
}

page_insert()

給頁表項賦值一個物理頁酵使。

int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
    // Fill this function in
    
    pte_t* pte = pgdir_walk(pgdir, va, 1);
    if (pte == NULL) {
        return -E_NO_MEM;
    }
    pp->pp_ref++;
    if (*pte & PTE_P) {
        page_remove(pgdir, va);
    }
    *pte = page2pa(pp) | perm | PTE_P;
    // cprintf("page_insert: %x\n", *pte);
    return 0;
}

Part 3 內核地址空間

JOS的內核空間為[UTOP, KERNBASE)，一共為256MB对省。
填充完整mem_init()蝗拿，將虛擬內核地址空間映射到物理地址上。

  1. [UPAGES, UPAGES+PTSIZE)這段空間是pages數(shù)組的空間蒿涎，將其映射到PADDR(pages)上哀托。
  2. [KSTACKTOP-KSTKSIZE, KSTACKTOP)是內核棧的空間，將其映射到PADDR(bootstack)
  3. [KERNBASE, 2^32-1)劳秋，其中32位系統(tǒng)無法計算 2^32仓手，但 2^32-1 == -KERNBASE。這段地址從物理地址0開始映射玻淑。
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
PTE_U);
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
boot_map_region(kern_pgdir, KERNBASE, -KERNBASE, 0, PTE_W);
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末嗽冒，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子补履，更是在濱河造成了極大的恐慌添坊，老刑警劉巖，帶你破解...
    沈念sama閱讀 216,919評論 6贊 502
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件箫锤，死亡現(xiàn)場離奇詭異帅腌，居然都是意外死亡，警方通過查閱死者的電腦和手機麻汰，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,567評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來戚篙，“玉大人五鲫，你說我怎么就攤上這事〔砝蓿” “怎么了位喂？”我有些...
    開封第一講書人閱讀 163,316評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵浪耘，是天一觀的道長。 經(jīng)常有香客問我塑崖，道長七冲，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,294評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任规婆，我火速辦了婚禮澜躺，結果婚禮上，老公的妹妹穿的比我還像新娘抒蚜。我一直安慰自己掘鄙，他們只是感情好，可當我...
    茶點故事閱讀 67,318評論 6贊 390
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布嗡髓。 她就那樣靜靜地躺著操漠，像睡著了一般。 火紅的嫁衣襯著肌膚如雪饿这。 梳的紋絲不亂的頭發(fā)上浊伙，一...
    開封第一講書人閱讀 51,245評論 1贊 299
  • 城市分裂傳說
    那天，我揣著相機與錄音长捧，去河邊找鬼嚣鄙。 笑死，一個胖子當著我的面吹牛唆姐，可吹牛的內容都是我干的拗慨。 我是一名探鬼主播，決...
    沈念sama閱讀 40,120評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼奉芦，長吁一口氣：“原來是場噩夢啊……” “哼赵抢！你這毒婦竟也來了？” 一聲冷哼從身側響起声功，我...
    開封第一講書人閱讀 38,964評論 0贊 275
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤烦却，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后先巴，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體其爵，經(jīng)...
    沈念sama閱讀 45,376評論 1贊 313
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,592評論 2贊 333
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年伸蚯，在試婚紗的時候發(fā)現(xiàn)自己被綠了摩渺。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,764評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡剂邮，死狀恐怖摇幻，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情，我是刑警寧澤绰姻，帶...
    沈念sama閱讀 35,460評論 5贊 344
  • ?日本核電站爆炸內幕
    正文 年R本政府宣布枉侧，位于F島的核電站，受9級特大地震影響狂芋，放射性物質發(fā)生泄漏榨馁。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,070評論 3贊 327
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一帜矾、第九天 我趴在偏房一處隱蔽的房頂上張望翼虫。 院中可真熱鬧，春花似錦黍特、人聲如沸蛙讥。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,697評論 0贊 22
  • 一樁弒父案灭衷，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽次慢。三九已至，卻和暖如春翔曲，著一層夾襖步出監(jiān)牢的瞬間迫像，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,846評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工瞳遍， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留闻妓，地道東北人。 一個月前我還...
    沈念sama閱讀 47,819評論 2贊 370
  • 代替公主和親
    正文 我出身青樓掠械，卻偏偏與公主長得像由缆，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子猾蒂，可洞房花燭夜當晚...
    茶點故事閱讀 44,665評論 2贊 354