My Avatar

Shilong ZHAO

Jos Lab2 Notes

2016-06-28 00:00:00 +0200

In case you have any questions or suggestions, you can leave comments HERE . Thanks!


Get a Virtual Memory layout like

Auxiliary Data Structures

struct PageInfo

An array of struct PageInfo named pages records the information of corresponding physical pages, the relation is shown as following

Inline function page2pa in kern/pmap.h translates a struct PageInfo *pp to the physical page address. The information about that physical page, e.g. reference count, is stored in *pp. In other words, pages[i] stores information about the ith physical page.

static inline physaddr_t
page2pa(struct PageInfo *pp)
    return (pp - pages) << PGSHIFT;

And the virtual address of the struct PageInfo *pp can be calculated with page2kva(pp).

Array pages is create with boot_alloc in mem_init

Auxiliary Functions


Get number of total pages npages in memory, which is sum of base memory npages_basemem and extended memory npages_extmem (if available). It is called inside mem_init.


it allocates a memory area, whose size is a multiple of PGSIZE. boot_alloc is only called inside mem_init and page_init before establishment of page table. After page tables are created, only page_alloc should be used for memory allocation.


function page_init initializes the pages array. That is, setting the structure members to appropriate values. The physical pages which is not occupied, i.e. pp_ref field being value 0, are added to page_free_list. Function page_alloc will allocate pages from page_free_list .


Take the first physical page which is represented by the first struct PageInfo element in page_free_list. If the flag is set to clean the page with value zeros, memset should be called, but note that in memset the virtual address of the page is used, not the physical one.


For a physical page represented by struct PageInfo *pp , check the number of references and if it is zero, put it back into the page_free_list.


Decrease the reference count of a physical page, and call page_free if pp_ref reaches zero.


To understand this function, it is crucial for one to have understood the paging mechanism and the difference between virtual and physical addresses.

The value stored in each pde is the physical address of the page table with permission control bits. The page table physical address can be obtained with

PTE_ADDR(*pde) where pde is type pde_t *, a pointer to a PDE.

However to access this page table, its virtual address is needed, this is because, after the PE bit is set in control register cr4 the CPU will always do the address translation. So if we feed PTE_ADDR(*pde) to the CPU, it will, in our case, treat this as an virtual address (although we know it is physical) and access PTE_ADDR(*pde) - KERNBASE which does not exist actually.

So we need to get the virtual address of the page table by KADDR(PTE_ADDR(*pde)).

If the page table is not present or if the PTE is not set yet, then use page_alloc to allocate one page, which returns a struct PageInfo *, and get the virtual address of the newly allocated page with page2kva(pp). And this newly allocated page should be recorded by the PTE, which again, the physical address of the page together with the permission bit should be stored *pte = PADDR(pp)| PTE_T | PTE_W| PTE_U.

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
    pde_t *pde; // pde address virtual
    pte_t *pt; // page table address virtual

    pde= pgdir + PDX(va);
    if ((*pde) & PTE_P)  // NOTE: the address stored in pgdir is physical mem
        pt = KADDR(PTE_ADDR(*pde)); // but what we need is virtual
    else {
        if (create) { // if page table does not exist, create and insert to page directory
            struct PageInfo *pp = page_alloc(ALLOC_ZERO);
            if (pp == NULL) return NULL;
            pt = page2kva(pp); // pt equals the new page table physical address
            // PTEs inside pt are not initialized yet
            *pde = PADDR(pt) | PTE_P | PTE_W | PTE_U;
            return NULL;
    return pt + PTX(va); 


Return a pointer to the PageInfo struct given the virtual address. Called by page_remove


Given a virtual address, unmaps the corresponding physical page. First get the PageInfo struct by page_lookup then decrease the reference count.


Map the physical region starts from pa in size of multiple of PGSIZE or size to the virtual address va with permission perm. This requires to set the PTEs.

static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
    int i, npages;
    pte_t *pte;
    size =  ROUNDUP(size, PGSIZE);
    npages = size/PGSIZE;
    for (i = 0; i < npages; i++) {
        pte = pgdir_walk(pgdir, (const void *)(va + i*PGSIZE), true);
        if (pte == NULL) 
            panic("cannot create page!\n"); 
        *pte = PTE_ADDR(pa + i*PGSIZE) | perm | PTE_P;

Main function

the main function is mem_init, it create the page directory kern_pgdir and maps it to virtual address UVPT, create the pages array, initialize the PageInfo structs in pages with page_init and finally call the boot_map_region to map the physical address to the desired virtual memory layouts.