A Guide to coremap.c

Overview

The coremap is the heart of physical-memory management in OS/161. It maintains information about every physical page (a.k.a. frame) of memory in the system through an array of coremap_entry structures. The coremap handles both allocation requests and page-replacement decisions.

Key Data Structures

Coremap Entry

struct coremap_entry {
        struct lpage *cm_lpage; /* logical page we hold, or NULL */

        volatile
        int cm_tlbix:7;         /* tlb index number, or -1 */
        unsigned cm_cpunum:5;   /* cpu number for cm_tlbix */

        unsigned cm_kernel:1,   /* true if kernel page */
                cm_notlast:1,   /* true not last in sequence of kernel pages */
                cm_allocated:1; /* true if page in use (user or kernel) */
        volatile
        unsigned cm_pinned:1;   /* true if page is busy */

        /* other fields as needed */
};

Important fields to understand:

• cm_lpage: Points to the logical page currently using this physical page
• cm_kernel: Distinguishes kernel pages (which can't be evicted) from user pages
• cm_allocated: Indicates if the page is in use
• cm_pinned: Indicates the page is busy (e.g., being read from disk)

Key Functions You'll Interact With

The header file kern/arch/mips/include/coremap.h contains the coremap interface and is worth reading over. The implementation is in kern/arch/mips/vm/coremap.c.

Page-Replacement Interface

/*
 * page_replace: Choose a page to evict.
 * Returns: index into coremap of chosen page
 *
 * This is where you'll implement both clock and random algorithms
 */
static
uint32_t
page_replace(void)
{
    /* Your implementation goes here */
}

TLB Invalidation

The function tlb_invalidate is used to invalidate a TLB entry. The TLB only has a small number of entries, so sometimes pages are removed from the TLB to make room for others. Being removed from the TLB does not necessarily mean the page is evicted from memory.

Important Helper Functions

/* Check if a page is pinned */
int coremap_pageispinned(paddr_t paddr);

/* Convert between physical addresses and coremap indices */
#define COREMAP_TO_PADDR(i)  (((paddr_t)PAGE_SIZE)*((i)+base_coremap_page))
#define PADDR_TO_COREMAP(page) (((page)/PAGE_SIZE) - base_coremap_page)

Key Operations and Their Flow

Page Allocation

static
paddr_t
coremap_alloc_one_page(struct lpage *lp, int dopin)
{
    /* ... */
    if (num_coremap_free == 0) {
        /* No free pages - calls page_replace() to choose victim */
        candidate = do_page_replace();
    }
    /* ... */
}

Page Replacement

When memory is full and a new page is needed,

1. coremap_alloc_one_page() detects no free pages
2. Calls do_page_replace()
3. do_page_replace() calls page_replace() to choose a victim
4. Selected page is evicted if necessary
5. Page is allocated to new use

Implementation Hints

For Page-Replacement Algorithms

1. The clock algorithm needs to track page usage. Consider:
   • What information needs to be stored per page?
   • How will you update this information?
   • When should information be updated?
2. Random replacement needs to
   • Use the random() function appropriately
   • Ensure chosen pages are valid candidates
   • Handle cases where chosen page isn't suitable
3. Both algorithms must
   • Never choose kernel pages (cm_kernel == true)
   • Never choose pinned pages (cm_pinned == true)
   • Keep trying until finding a suitable page

Common Pitfalls

1. Synchronization
   • The coremap spinlock protects the coremap
   • Be careful about lock ordering
   • Watch for deadlocks
2. Page Selection
   • Always verify page can be evicted
   • Handle case where all pages are pinned
   • Consider efficiency (especially for clock algorithm)
3. State Management
   • Track algorithm state correctly
   • Handle wraparound properly
   • Consider all edge cases

Debugging Tips

1. Use coremap_print_short() to visualize memory state

   • K indicates kernel page
   • * indicates allocated user page
   • . indicates free page
   • & indicates pinned page

2. Common issues:

   • Infinite loops in page selection
   • Selecting invalid pages
   • Missing synchronization
   • Memory leaks

Testing Strategy

1. Test basic functionality:
   • Does algorithm select valid pages?
   • Does it avoid kernel pages?
   • Does it handle pinned pages?
2. Test edge cases:
   • Nearly full memory
   • Many pinned pages
   • All pages pinned
   • Multiple consecutive allocations
3. Test efficiency:
   • For clock algorithm: Is it using history effectively?
   • For random: Is distribution reasonable?

Additional Notes

• The coremap is initialized during boot in coremap_bootstrap()
• Page replacement only happens for user pages
• Understanding the relationship between physical addresses and coremap entries is crucial
• Remember to handle the case where no pages can be evicted

Remember: Good page-replacement algorithms balance efficiency (quick decisions) with effectiveness (good choices). The clock algorithm should perform better than random replacement in most cases, but both need to be robust and reliable.

(When logged in, completion status appears here.)