OS161 Coremap

The first concern of OS161 virtual memory system is how to manage physical pages. Generally, we can pack a physical page's information into a structure (called struct coremap_entry) and use this struct to represent a physical page. We use an array of struct coremap_entry to keep all physical pages information. This array, aka, coremap, will be one of the most important data structure in this lab.

What should we store in coremap entry structure?

For each physical page, we want to know:

  • Where is this page mapped? (For swapping)
  • What's this pages status? (free, fixed, clean, dirty...)
  • Other info (e.g. need by paging algorithm)

A page can have for different states, as shown below.

This diagram is quite clear. Several points to note:

  • When a physical page is first allocated, its state is DIRTY, not CLEAN. Since this page do not have a copy in swap file (disk). Remember that in a virtual memory system, memory is just a cache of disk.

  • For some reason, we may want to always keep a certain page in memory, e.g.

    • kernel pages, since these pages are direct mapped.
    • user stack and code segment pages which we already knew will be frequently accessed.

So we have a special state called "fixed", means that we'll never swap out these pages to disk.

Coremap Initialization

We need to initiate our coremap in vm_bootstrap. First, we need to find out how many physical pages in system. We can do this using ram_getsize. There is a big trick here. Since we will only know the physical page number, i.e. coremap array length at runtime, so we'd better just define a struct coremap_entry pointer and allocate the actually array at runtime after we got the physical page number, rather than use a statically defined array with some MACRO like MAX_PHY_PAGE_NUM. So at first glance, we may write:

But the above code will definitly fail.

Take a look at ram_getsize, we can see that this function will destroy its firstaddr and lastaddr before return. So after that, if we call kmalloc, which call alloc_kpage, get_ppages and ram_stealmem to get memory, ram_stealmem will fail. The contradiction is: we need to call ram_getsize to get physical page number so that we can allocate our coremap(pages), but once we call ram_getsize we will not be able allocate any pages!

To resolve this contradiction, on one hand, we should initialize all other data structures, e.g., locks, before we call ram_getsize. Then we call ram_getsize to get firstaddr and lastaddr. After that, instead of using kmalloc, we must allocate our coremap manually, without invoking any other malloc routines. A possible solution may be:

Now we allocated our core map just between firstaddr and freeaddr, and [freeaddr, lastaddr] will be system's free memory.

Then we initialize the coremap array, we need to mark any pages between [0, freeaddr) as fixed, since this memory contains important kernel code and data, or memory mapped I/Os. And we just mark pages between [freeaddr, astaddr] as free.

At the end of vm_bootstrap, we may want to set some flags to indicate that vm has already bootstrapped, since functions like alloc_kpages may call different routines to get physical page before and after vm_bootstrap.