Assignment 7, Solutions

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Consider a memory management unit that operates using the following data structures, all defined in C:
    /* virtual addresses have 12 bits for the byte-in-page field */
    #define BYTE_IN_PAGE 12
    
    /* masks derived from above */
    #define BYTE_MASK ((1 << BYTE_IN_PAGE) - 1)
    #define PAGE_MASK (~BYTEMASK)
    
    /* access right bit names and the maximum number of rights bits */
    #define R_VALID 0
    #define R_EXEC  1
    #define R_WRITE 2
    #define R_READ  3
    #define R_CACHE 4
    #define R_DIRTY 5
    #define R_MAX   6
    
    /* access rights bit mask for a single right */
    #define RM(R) (1 << (R))
    
    /* masks for page-table fields */
    #define R_MASK      ((1 << R_MAX)-1)
    #define FRAME_MASK  (~BYTEMASK)
    #define UNUSED_MASK (~(R_MASK | FRAME_MASK))
    
    /* the page-table is an array of pointers to page frames */
    char * pagetable;
    
    /* access to fields of page table entries */
    #define FRAME(pt)  (void *)(((uintptr_t) pagetable[pt]) & FRAME_MASK)
    #define RIGHTS(pt) ((uintptr_t pagetable[pt]) & RIGHTS_MASK)
    #define EXTRA(pt)  ((((uintptr_t) pagetalbe[pt]) & EXTRA_MASK) >> R_MAX)
    
    /* page table entry constructor */
    #define MAKE_PT_ENTRY(f,e,r) ((void *)(((uintptr_t)f) | (e << R_MAX) | r))
    

    a) Write a C function that conforms to the following:

    void * convert( void * va );
    

    This function should take a virtual address as a parameter parameter and return the corresponding physical address, assuming that the global variable pagetable points to the current page table. (1.0 points)

    void * convert( void * va ){
            uintptr_t byte, page, frame;
            byte = BYTE_MASK \amp; (uintptr_t) va;
            page = PAGE_MASK \amp; (uintptr_t) va;
            frame = FRAME(page >> BYTE_IN_PAGE)
            return (void *) frame | byte;
    }
    

    b) Write a C function that conforms to the following:

    bool checkrights( void * va, int rm );
    

    This function should return true if the virtual address allows the indicated set of access rights rm (the or of the masks for the individual rights desired). Assume that the global variable pagetable points to the current page table. (0.5 points)

    bool checkrights( void * va, int rm ){
            uintptr_t page;
            page = PAGE_MASK \amp; (uintptr_t) va;
            return (RIGHTS(page >> BYTE_IN_PAGE) & rm) == rm;
    }
    

    c) Explain why the above two functions are likely to be needed within the operating system despite the fact that the MMU must be able to do both functions in hardware. (0.5 points)

    The MMU typically translates addresses and checks access rights only for addresses used for instruction fetches or operand loads and stores. The functions defined above are used inside the operating system in a context where the MMU may well be turned off and where the address being translated is an operand, not an address issued directly by the CPU.

  2. Background: Assume that the MMU does not have access to the entire page table. Instead, it contains a translation lookaside buffer -- a cache, where each entry in the TLB contains, on one side, the virtual address of a page va (eqivalent to a page number shifted over to accomodate a byte-in-page field that is all zero), and on the other side, the page table entry for that address pt. Code to manipulate the MMU uses the following software interface to the MMU hardware:
    void mmu_settlb( void * va, void * pt );
    /* replaces one of the less-recently used TLB entries with [va,pt];
       it is up to the hardware to decide which entry to replace */
    
    void * mmu_getva();
    /* get the virtual address that caused the most recent page fault */
    
    int mmu_getcause();
    /* get the cause of the most recent page fault;
       returns zero if cause was a TLB miss, otherwise returns a rights mask
       with one bit set for each access right that was violated */
    

    The Problem Flesh out this page fault handler so that it handles "soft page faults", that is, those associated with TLB misses.

    void page_fault_handler() {
            if --- missing code ---- {
                    --- missing code to handle soft page faults ---
            } else {
                    --- code you dont't need to write for real page faults ---
            }
    }
    
    (1 point)
    void page_fault_handler() {
            int cause = mmu_getcause();
            void * va = mmu_getva();
            if (cause == 0) { /* TLB miss */
                    void * pt;
                    uintptr_t page;
                    page = PAGE_MASK \amp; (uintptr_t) va;
                    pt = pagetable[ page >> BYTE_IN_PAGE];
                    --- missing code to handle soft page faults ---
                    mmu_settlb( va, pt );
            } else {
                    --- code you dont't need to write for real page faults ---
            }
    }