Assignment 8 Solutions

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

  1. Background: Consider a virtual memory system for a 32-bit computer. Both virtual and physical addresses are 32-bits each. The virtual address is organized as follows:
        segment    
    10 bits
    page in seg
    10 bits
       byte in page   
    12 bits

    The physical address is organized as follows:
                    frame                
    20 bits
       byte in page   
    12 bits

    The segment table is exactly 4K 32-bit words, and the page table for each segment is also exactly 4K 32-bit words. These are stored in RAM. The entries in these tables have the following format, with the access rights being vrwx (valid, read, write, execute):
                    frame                
    20 bits
      unused  
    8 bits
    rights
    4

    The operating system keeps a pointer to the segment table in a global varialbe called segtab. The access rights permitted for a page are the logical and of the rights in the segment table entry and the rights in the page table entry. If a segment is marked as invalid, there is no corresponding page table. If a page table entry is marked as invalid, there is no corresponding page.

    The MMU has no knowledge of the existence of the segment table, frame table or the structure of the table entries. Instead, the MMU operates in terms of a translation lookaside buffer. Each TLB entry has the following format, with the access rights vrwx as in the page table:
        page    
    20 bits
      unused  
    8 bits
    rights
    4
                    frame                
    20 bits
    unused
    12 bits

    When there is a page-fault, which is to say, when the MMU finds that there is no entry in the TLB with the requested page field, or when there is such an entry but the rights do not permit the requested operaiton, the hardware forces a page fault trap. Entry to the trap service routine saves the entire state of the user program and turns off the MMU so the system is running with direct addressing of physical memory. On entry to the trap service routine, the following information is available in global varialbes: trapaddress the virtual address that caused the trap, and trapcause an indication of the cause of the trap. The least significant 4 bits of the cause are vrwx, as in the page table, indicating an attempt to use an invalid TLB entry, to read a non-readable page, to write a non-writable page, or to execute from a non-executable page. Exactly one of these bits will be set when there is a TLB entry for the indicated page. None of these bits will be set if no TLB entry is defined for the page.

    The trap service routine may update the TLB by calling tlbupdate(e) where e is the 64-bit TLB entry. The TLB will replace some TLB entry, probably one of the less recently used entries, using a policy known only to the hardware designers. On return from the trap service routine, the state of the user program will be restored and the MMU will be turned on.

    a) Write a trap service routine that only handles updating the TLB from the segment and page tables. In the event that the page fault results from an attempt to perform an operation that is illegal according to the page table in RAM, your code should call the real_page_fault() service routine. (1.5 points)

    page_fault_trap(){
        /* in the following, trapaddress and trapcause are data from the MMU */
        if ((trapcause & 0xF) == 0) { /* missing TLB entry */
            int seg = trapaddress >> 22;
            int page = (trapaddress >> 12) & 0x3FF; /* 10 bits */
            uint32_t segtabentry = segtab[ seg ];
            int segrights = segtabentry & 0xF;
            if ((segrights & 0x8) != 0) ( /* valid segment */
                int page = (trapaddress >> 12) & 0x3FF; /* 10 bits */
    	    uint32_t * pagetab = (uint32_t *) segtabentry & 0xFFFFF000;
                uint32_t pagetabentry = pagetab[ page ];
                int pagerights = pagetabentry & 0xF;
                if ((pagerights & 0x8) != 0) ( /* valid page */
    	        uint32_t page  = (uint32_t *) trapaddress  & 0xFFFFF000;
    	        uint32_t frame = (uint32_t *) pagetabentry & 0xFFFFF000;
                    int rights = segrights & pagerights;
                    update_tlb_entry( page | rights, frame );
                } else { /* page is invalid */
                    real_page_fault()
                }
            } else { /* segment is invalid */
                real_page_fault()
            }
        } else { /* trapcause was not missing TLB entry */
            real_page_fault();
        }
    }
    

    b) Suppose the hardware designers decided they wanted to support physical memory with more than 32-bit addresses. Given the details presented above, are there spare bits in the TLB, segment table and page table entries that would allow support for a physical address space larger than 32-bits? What is the upper bound on the number of bits in the physical address, using these bits. (0.5 points)

    There are 20 spare bits in each TLB entry, a block of 8 and a block of 12. These could be considered extra bits of the frame field in the TLB, producing a 40 bit frame number -- corresponding to a 52-bit physical address (one petabyte). Less awkward schemes would use just the 12 unused bits adjacent to the frame field in order to create a 44-bit physical address (16 terabytes).

    The software data structures handled by the page fault service routine given in part a) would need significant modification to use the above answer. However, both the segment-table entry format and the page-table entry format each include 8 extra bits. These bits could be used to enlarge the physical memory at a relatively low price, expanding the 32-bit physical address to a 40 bit physical address, one terabyte.

    A surprising number of students wanted to enlarge the virtual address correspondingly, but this is an awful prospect. It is easy to build a new MMU supporting a larger physical address, because this requires no change to the CPU, just changes to the page-fault service routine. It is very difficult to enlarge the virtual address because the structure of every memory-reference instruction must be rethought.

    c) Suppose the hardware designers wanted to leave the MMU turned on at all times during the processing of page faults. To do this, they add one extra bit to the access rights field of the TLB entry, the lock bit L. The TLB will not replace entries marked as locked.

    What is the minimum set of TLB entries that must be locked to make this system work. Your answer should be state in terms of the TLB entries for the pages containing X, where X is some set of operating system components, either specific routines or specific data. (0.5 points)

    The pages holding the page-fault service code used to handle TLB faults must be locked. This includes all the code written for part a), and it also includes the rest of the page-fault service routine, unless we allow traps during the execution of trap service routines (recurisve traps) -- that can be arranged! In addition, we need to lock the page holding the segment table, and if we do not allow recursive traps, the pages holding all of the page tables. The register save area and any additional stack used for trap service must also be locked (this is slightly more complex if recursive traps are permitted).

Note: A free 0.5 points was given to every solution submitted because the assignment was 0.5 points short of the standard 3 points per homework.