Address translation

Nachos processor supports VM through either a single linear page table or a software-managed TLB (but not both). The mode of address translation is actually used is determined by nachos.conf, and is returned by hasTLB().

In both cases, the TranslationEntry class is the data structure in Nachos to store information related to a page. Each TranslationEntry object contains the physical page number, the virtual page number, whether the page is ready only, whether it has been used recently (e.g., to implement the CLOCK algorithm), and whether the entry is valid (if not, accessing it will result in a page fault). The Processor.translate method translates virtual address into a physical address, using either a page table or a TLB.

1   private int translate(int vaddr, int size, boolean writing)
2   throws MipsException {
3   ...
4
5   // calculate virtual page number and offset from the virtual address
6   int vpn = pageFromAddress(vaddr);
7   int offset = offsetFromAddress(vaddr);
8
9   TranslationEntry entry = null;
10
11   // if not using a TLB, then the vpn is an index into the table
12   if (!usingTLB) {
13   if (translations == null || vpn >= translations.length
14   || translations[vpn] == null || !translations[vpn].valid) {
15   privilege.stats.numPageFaults++;
16   Lib.debug(dbgProcessor, "\t\tpage fault");
17   throw new MipsException(exceptionPageFault, vaddr);
18   }
19
20   entry = translations[vpn];
21   }
22   // else, look through all TLB entries for matching vpn
23   else {
24   for (int i = 0; i < tlbSize; i++) {
25   if (translations[i].valid && translations[i].vpn == vpn) {
26   entry = translations[i];
27   break;
28   }
29   }
30   if (entry == null) {
31   privilege.stats.numTLBMisses++;
32   Lib.debug(dbgProcessor, "\t\tTLB miss");
33   throw new MipsException(exceptionTLBMiss, vaddr);
34   }
35   }
36
37   // check if trying to write a read-only page
38   if (entry.readOnly && writing) {
39   Lib.debug(dbgProcessor, "\t\tread-only exception");
40   throw new MipsException(exceptionReadOnly, vaddr);
41   }
42
43   // check if physical page number is out of range
44   int ppn = entry.ppn;
45   if (ppn < 0 || ppn >= numPhysPages) {
46   Lib.debug(dbgProcessor, "\t\tbad ppn");
47   throw new MipsException(exceptionBusError, vaddr);
48   }
49
50   // set used and dirty bits as appropriate
51   entry.used = true;
52   if (writing)
53   entry.dirty = true;
54
55   int paddr = (ppn ⋆ pageSize) + offset;
56
57   if (Lib.test(dbgProcessor))
58   System.out.println("\t\tpaddr=0x" + Lib.toHexString(paddr));
59   return paddr;
60   }

6.2.1 Software-managed TLB

The default TLB size is 4. The kernel can query the size of the TLB by calling getTLBSize(), and the kernel can read and write TLB entries by calling readTLBEntry() and writeTLBEntry(). TLB is used to cache recently used page table entries and to expedite address translation. If TLB is enabled (usingTLB = true),

In Line 24 – 34 of Processor.translate, the input vpn will be looked up among the TLB entries. If not found, a exceptionTLBMiss exception is generated and handled by the exception handler (to be implemented). Otherwise, the associated page entry will be checked for validity and the respective dirty and used bits will be set accordingly.

In the case of TLB misses, an appropriate TLB replacement policy shall be implemented to substitute existing TLB entries with new ones.

TLB can be used in conjunction with per-process page table or a global inverted page table for address translation.

6.2.2 Per-process page table

If the processor does not have a TLB, Processor.translate (Line 13 – 20) looks up the page table in translations and retrieves the entry corresponding to the virtual address. If the page table is null, the respective entry is null or invalid then a page fault exception will be generated.

Per-process page table is set up by calling Processor.setPageTable() by the user process. On a real machine, the page table pointer would be stored in a special processor register. The user process is responsible for populating the per-process page table initially.

1   public UserProcess() {
2   int numPhysPages = Machine.processor().getNumPhysPages();
3   pageTable = new TranslationEntry[numPhysPages];
4   for (int i = 0; i < numPhysPages; i++)
5   pageTable[i] = new TranslationEntry(i, i, true, false, false, false);
6   }

As indicated in Line 5, in uni-programming, it is sufficient to initialize the page table with one-to-one mapping between the physical and virtual memory.

6.2 Address translation

6.2.1 Software-managed TLB

6.2.2 Per-process page table