Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!ncar!zaphod.mps.ohio-state.edu!usc!snorkelwacker!bloom-beacon!jfc From: jfc@athena.mit.edu (John F Carr) Newsgroups: comp.arch Subject: Re: Paging page tables Message-ID: <1990Jun30.093611.12248@athena.mit.edu> Date: 30 Jun 90 09:36:11 GMT References: <4137@taux01.nsc.com> <1990Jun29.213236.4888@cbnewsh.att.com> <3341@goanna.cs.rmit.oz.au> Sender: news@athena.mit.edu (News system) Organization: Massachusetts Institute of Technology Lines: 68 In article <3341@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >One really beautiful idea is to stand the whole thing on its >head and have your page tables map from *physical* pages to >*virtual*, so that the space taken up by page tables is a >fixed fraction of the size of *physical* memory. This is the >technique used on the IBM RT PC. >(1) Would someone who really understands the technique care to post > a short description? A 32 bit address on the IBM RT is treated by hardware as a 4 bit segment number/17 bit virtual page number/11 bit byte address. When an address is presented to the memory management unit, the segment number is extracted. Unless this segment is marked "not present" (for example, segment 15 on the RT is dedicated to I/O devices; there is a bit to tell the MMU to let another system handle references to this segment), it is replaced in the virtual address with a 12 bit segment ID to create a 40 bit virtual address. The MMU has a 32 entry TLB; when a virtual address is not found in the TLB, the hardware needs to consult the page tables. The page table is called the "HAT/IPT" -- "Hash Anchor Table/Inverted Page Table". This refers to the two ways of indexing it to perform virtual to physical and physical to virtual address translation. The MMU servicing a TLB miss starts with a HAT lookup: 1. compute an index into the HAT. This is the exclusive OR of the low bits of the virtual page number and the segment number (number of bits depends on memory size). 2. check the "empty" bit; if it is set than page fault 3. extract from the table entry a 13 bit index Then it continues with a search of a chain of IPT entries: 4. read the table entry corresponding to the index a. if the virtual address matches, load this entry into the TLB; end of processing b. if the "last" bit is not set, extract a 13 bit index to the next table entry in the chain; repeat 4 c. if the "last" bit is set then this is the end of the chain and no match has been found, so page fault This takes 5 cycles + 3 cycles per IPT entry searched (cycle time is 80ns to 170 ns depending on CPU model). Ideally, search length should be very close to 1 (this is a hash table with as many buckets as objects). I ran some tests a few days ago and found that in reality the average is between 2 and 3; due to the software implementation most segment numbers and virtual page numbers are small so the high bits of the hash index are predictable. Searching for the virtual page mapped to a physical page is constant time -- just index into the table by the physical page number in question. Each table entry is 16 bytes. When using 2K pages, the overhead is 16/2048 = 1/128 memory dedicated to page tables. >(4) Does the RS/6000 use inverted page tables or paged page tables? The RS/6000 memory management unit is a slightly newer version of the RT MMU. It has longer segment IDs to give more virtual address bits (56, I think). -- --John Carr (jfc@athena.mit.edu)