Software Design Notes The Virtual Memory System SECTION 5 The Virtual Memory System 5.1 VIRTUAL MEMORY Virtual Memory is the simulation of a large fast primary memory ______________ by the use of a fast but smaller primary memory and a large but slow secondary memory. Blocks, called pages, are moved between _____ primary and secondary memory according to a page management strategy. A page management strategy that moves a page into primary memory when it is referenced but not present in primary memory (a page ____ fault) is termed demand paging. Usually, a page being moved into _____ _____________ primary memory displaces some other page. The choice of the page to remove is made by applying the page replacement policy. If the page chosen for replacement has been altered while in primary memory, it must be written to secondary memory before it can be replaced. A page in primary store that has been altered is called a dirty page. __________ Some pages are exempted from paging. These are termed wired _____ pages. Wired pages are used for interrupt handler buffers _____ because interrupts cannot take a page fault; for pages containing paging tables on which a page fault cannot be allowed; for pages involved in DMA transfers; and other pages containing critical data which must be accessed without a page fault or for which the performance penalty for taking a page fault is too great. In the Explorer, semiconductor memory is used as primary memory and disk is used as secondary memory. Pages are moved into primary memory when referenced and not present -- demand paging. Every attempt is made to replace a page which is not dirty so that a write to secondary memory is not needed. A page exception is said to occur when for some reason the ______________ virtual to physical address mapping could not be completed by the mapping hardware without microcode support. There are many reasons for this; only one of those reasons requires access to secondary storage. If a page is referenced and this reference cannot be completed without operations with secondary storage, then a page fault has occurred. This distinction is made so that page exception rates and page fault rates can be distinguished. Virtual memory references are processed below everything except interrupts in the Explorer hierarchy (they are depended on by 5-1 The Virtual Memory System Software Design Notes everything except interrupts). A virtual memory reference is considered an atomic operation on the Explorer system; that is, the time spent waiting for a virtual memory reference to complete (including time spent waiting for disk paging activity) is not available for use by any other part of the system except interrupt processing. This policy greatly simplifies the implementation of various low-level Explorer subsystems. 5.2 PHYSICAL ADDRESSES Memory is accessed by use of a physical address, a system-wide ________________ name for some storage. The Explorer is based on the NuBus, a 32- bit, high-speed bus. All NuBus addresses are byte addresses with words aligned so that the low order 2 bits are zero. Explorer physical memory, monitor screen memory and I/O peripheral control registers all reside within the same 32-bit address space. Not all bus addresses will be accessible directly mapped in the Lisp virtual address space. This is true because the 25-bit Lisp virtual address is smaller than the 32-bit NuBus address space. Data can be read and written into unmapped physical addresses using special physical I/O functions from Lisp. 5.3 VIRTUAL ADDRESSES An address in the Explorer system is the size of a pointer field, which is 25 bits. The virtual address is divided into a virtual _______ page number and a page offset. The virtual page number is the ___________ ___________ high order 16 bits of the virtual address, and page offset is the low order 9 bits of the virtual address. Thus, each virtual page contains 512 words (or 2048 bytes) of storage. The Explorer I and Explorer II both have memory mapping hardware based on a map page size of 256 word (or 1024 bytes). Therefore, there are two hardware map pages for each virtual page. When referring to these maps, the map page number is based on the high order 17 bits of the virtual address and will be called the virtual page map number. The page offset is based on the low _______________________ order 8 bits and will be called the page map offset. _______________ The Explorer has a simple memory map. I/O is not, by default, part of virtual memory, but instead is accessed by special physical I/O operations. The A-memory (the processor memory for data accessed by the microcode) has a dedicated virtual address, which is at the very top of the virtual address space, but consumes none of the physical address space. 5-2 Software Design Notes The Virtual Memory System In order to translate from a virtual to a physical address, the virtual page map number is looked up in the hardware page maps to produces a 22-bit page frame number. The page frame number is _________________ concatenated with the 10-bit page map offset to make a 32-bit physical address. This is used to address the primary memory over the system (or other) bus. The map also produces other outputs for use by the processor: 2 access bits, 2 status bits, 6 meta bits and 2 garbage collector volatility bits. These outputs are used by the microcode to help manage page aging, storage allocation attributes (on a per-region basis), garbage collection, and other functions. The Explorer microprocessor has a standard NuBus interface. In addition, The Explorer I microprocessor has a special bus to "local memory". This local memory also exists in the NuBus address space but the special high-speed dedicated bus to this memory reduces the NuBus traffic. 5.4 PHYSICAL MEMORY USE The physical memory present in the machine can be divided into two categories according to its usage. A portion of memory is set aside for use by the paging system itself and by microcode and Lisp device handlers that perform physical addressing. Data in this space is said to reside in physical memory which is not accessible in the virtual memory address space. Such physical memory is termed the permanently wired pages. The rest of the _________________ local physical memory is used as a transient page area, i.e., the virtual memory system assigns the pages of the virtual memory to physical locations as a part of its management functions. 5.5 VIRTUAL MEMORY PARTITIONING To avoid the need for a very large mapping memory, or an associative memory, both the Explorer I and Explorer II use two- level memory maps for the virtual-to-physical address translation. Several sections following this one describe the hardware maps in detail. This section, however, is meant to provide an overview and motivation for the map functions. The first level map (called the Level-1 map on the Explorer I and the Address Space Map on the Explorer II) effectively partitions the virtual address space into segments of 8K words (16 pages). The both have 4096 entries and are indexed by the top 12 bits of the virtual address. Note that there are two such entries per 32-page address space quantum. The 32-page address space quantum is the unit in which address space is allocated to regions; that 5-3 The Virtual Memory System Software Design Notes is, a region must be at least 1 address space quantum long, and must have a length evenly divisible by the address space quantum. On both Explorer I and Explorer II, a number of second level maps are allocated to the first level maps. The number of second level maps differs; but in both cases it is much less than the amount required to map in the entire 25-bit address space. If the address is not currently being mapped by the mapping hardware, the microcode consults the Page Hash Table (PHT, described later) which describes all pages in physical memory. In general terms, the first level maps can be thought of as a way of segmenting the address space into blocks of contiguous virtual pages with identical attributes in order to aid storage allocation and garbage collection functions. The second level maps can be thought of as a cache describing the most recently accessed pages. Except for special system pages, the storage- management and garbage-collection-specific information in the memory maps is initially set up from the REGION BITS associated with a virtual address. They may later be altered by the garbage collector. 5.6 EXPLORER I MAPPING HARDWARE The Explorer I Level-1 Map (Figure 5-1) is 4096 words long and is indexed by the top 12 bits of the virtual address. The first level map, if valid, produces a 7-bit index into the second level map along with several status bits. 15 14 13 12 11 10 9 7 6 0 +---------------+--+--+--+--+--+--+----+-----------+ | Unused | M| F| W| A| V| O| GCV| LVL2 INDEX| +---------------+--+--+--+--+--+--+----+-----------+ M <15> = last access mapped (not physical) F <14> = last access forced W <13> = last access write fault A <12> = last access access fault V <11> = map entry valid O <10> = oldspace meta bit; 0 = oldspace GCV <9> = Garbage Collector volatility bits LVL2 INDEX <6:0> = Level-2 block number Figure 5-1 Explorer I Level-1 Map (LVL1) The second level map (Figure 5-2) consists of 128 blocks of 32- registers each. Each set of the registers represents one map- page entry. After using the most significant 12 bits of the 5-4 Software Design Notes The Virtual Memory System virtual page map number to index into LVL1, the remaining 5 bits of the virtual page map number select a register within the LVL2 block. If both the LVL1 and LVL2 entries are valid, and if all other status indications are positive, the selected LVL2 map register produces the 22-bit physical page frame address. Note that since the LVL2 map blocks are indexed by the least significant 5 bits of the 17-bit virtual page map address, each of the 128 blocks represents 16 contiguous virtual pages. Memory Map Level 2 Control Bits 31 16 15 14 13 12 11 10 9 8 6 5 4 3 0 +-------------+---+---+--+-----+--+-+----+----+----+ | Unused |TM1|TM0| L| GCV | F|A|STAT| REP| SP| +-------------+---+---+--+-----+--+-+----+----+----+ TM1 <15> = last access TM1 TM0 <14> = last access TM0 L <13> = last access locked GCV <12:11> = Garbage Collector volatility bits F <10> = force allowed A <9> = access bit; 0 = no access STAT <8:6> = status bits (see Figure 5-4) REP <5:4> = representation type: 0 = list 1 = structure 2,3 unused Memory Map Level 2 Address Bits 31 22 21 0 +-----------------+--------------------------------+ | Unused (0) | Physical Page Number | +-----------------+--------------------------------+ Figure 5-2 Explorer I Level-2 Maps (LVL2) The second level map is read in as two separate functional sources since the data field is greater than 32 bits. The field is separated into Memory-Map-Level-2-Control-Bits and Memory-Map- Level-2-Address-Bits. To handle a page exception a check must first be made to see if the LVL1 entry is valid. A bit in the Memory-Map-Level-1 register indicates this. If the first-level map entry is not valid, a block of second level map must be allocated and initialized with "map not valid" entries. The first level map must be set up to point to it. From here the page exception is handled as a second level map miss (described later). 5-5 The Virtual Memory System Software Design Notes If the first level map entry is valid then the data in the second level memory map control register determines the action to be taken. The map status code is used to determine the processing case. 5.7 EXPLORER I REVERSE FIRST LEVEL MAP For each block of 128 Second Level Map registers, there is an entry in the Reverse First Level Map which gives the number of the First Level Map entry which points to this block, or else indicates that this blocl is unused. It contains a value which, if placed in the Virtual Memory Address register (VMA), would address that first level map entry, or else it contains -1 to indicate that this block is not currently pointed to. The Reverse First Level Map is held in A-memory and is 128 words long. It is used when allocating map level-2 blocks. 5.8 EXPLORER I MEMORY MAP ALLOCATION A simple clock scheme is used for allocation of second level memory map blocks. If a level-1 map fault occurs, the Reverse First Level Map is consulted to see if the level-2 map block is owned by this level-1 block. If so, the valid (V) bit is set and the memory reference is restarted. If not, a new level-2 map block must be allocated wo this level-1 entry. To find a level-2 map block to allocate, the Reverse First Level Map is scanned. If the value is -1 then this level-2 map block is free and can be allocated. If the value is not -1 then it contains the address of the map level-1 entry which owns this level-2 map block. If the level-1 valid (V) bit of this entry is not set then this block has not been used recently and is allocated to the new entry. If the valid (V) bit is set, then this entry is in use. The level one entry is aged by turning off the valid bit. The scan continues at the next Reverse First Level Map entry. The scan will wrap around if the end of the table is encountered. Since the aging is done during the scan, if the entire structure is scanned and no level-2 map block is found, then the scan merely continues and will choose the next entry since it was aged during the last scan. The map level-2 block is allocated by setting the index in the map level-1 entry and updating the Reverse First Level Map to reflect the new allocation. 5-6 Software Design Notes The Virtual Memory System 5.9 EXPLORER II MEMORY MAP HARDWARE The Explorer II map hardware consists of the Address Space Map (ASM), the Virtual Memory Maps Status (VMM Status), and the Virtual Memory Maps (VMM). The Address Space Map and the VMM Status replace the level-1 maps on the Explorer I and the VMM replaces both level-2 maps. The Address Space Map (see Table 5-1) contains garbage collection oldspace and volatility information. There are 4K entries in this table, one entry for every 16 pages or 8K words, which is equivalent to two entries for every address space quantum (16K words; the smallest region size). This table is addressed by the high order 12 bits of the 25 bit virtual page address. Table 5-1 Address Space Map Bits Assignment 7 6 5 4 3 0 +----+-----+----+------+ |GCVS| GCV | OS | Meta | +----+-----+----+------+ GCVS <7> : Garbage Collection volatility valid status, 0 = true GCV <6:5> : Volatility level for this address space half quantum OS <4> : Old Space bit, 0 = Oldspace Meta <3:0> : Address space Map Meta bits The Virtual Memory Map Status contains two entries for each virtual page and therefore contains 128K entries. Each table entry consists of two bits (see Table 5-2), which indicates whether the VMM table has a valid entry. It also indicates if which VMM bank, right or left, the valid entry can be found, if one exists. Table 5-2 Virtual Memory Maps Status 1 0 +---+---+ | B | V | +---+---+ V <0> : Valid bit, 1 if map is set up B <1> : Bank select, 1 if right bank, 0 if left bank 5-7 The Virtual Memory System Software Design Notes The Virtual Memory Map (VMM) consists of two banks. Each bank has 16K 32 bit maps. Each entry has the 22 bit physical frame address needed by the hardware to map from virtual memory to physical memory. The maps also contain two access bits that control the type of access to the maps. Bit 31 is the read/write access bit, and will cause a page exception if not set on any mapped cycle. Bit 30 is the write access bit, which is also the top bit of the 3 bits status field (see Table 5-3), will cause a page exception on mapped write cycles if not set. When a mapped cycle is done, the mapping hardware will first check the the Virtual Memory Map Status Ram by indexing into it with bits 8 though 24 of the virtual address used. If the valid bit is not set, then a map miss page exception occurs. If the valid bit is set, then the hardware checks the bank select bit in the Virtual Memory Map Status to see which VMM bank it should use, the right or left. It then gets the entry from the correct bank by indexing into with bits 8 through 21 of the virtual address. If the read/write bit is set in the VMM and the cycle is a read or if both the read/write access and write access is set and the cycle is a write, then it can complete the cycle by using the physical address. If the access bits are not set correctly then a page exception occurs. The 32-bit physical address is constructed from the top 22-bit physical page number along with the 8-bit map page offset from bits 0 through 7 of the virtual page address, with byte offset, the last two digits, being 0. Since the VMM banks are indexed by bits 8 through 21 of the virtual address, bits 22 thought 24 indicate the 6 different pages that will index to the same VMM index. Since there are two banks, 2 of these 8 pages can be set up at the same time. If the cache inhibit bit is not set, the hardware will use the cache if it can, and do cache fills as needed. 5-8 Software Design Notes The Virtual Memory System Table 5-3 Virtual Memory Map 31 30 28 27 26 25 24 23 22 21 0 +--+--------+-----+--+-----+--+-------------------------------------+ |A |STATUS | REP |O | GCV |CI| PHYSICAL PAGE NUMBER | +--+--------+-----+--+-----+--+-------------------------------------+ A <31> : Access bit, 0 is no access Status <30:28> : Status (see Figure 5-4) Rep <27:26> : Region representation, 0 is list space, 1 is structure space, 2 and 3 are unused O <25> : Oldspace bit, 0 = oldspace GCV <24:23> : Garbage Collection Volatility bits CI <22> : Cache Inhibit, 1 = inhibit Physical Page Number <21:0> : The top 22 bits of the 32-bit physical page address. 5.9.1 Explorer II Map Usage Table (MUT). The Explorer II Map Usage Table (MUT) resides in physical memory and contains 8192 entrues (see Table 5-4). Since there are two entries per 32 bit word, it occupies 4096 words of physical memory. Since one 2K page uses two maps, each entry has information for two left and two right VMM maps. For each pair of maps, it shows which of the 8 possible virtual memory pages is using the left bank and which is using the right bank. It also shows which bank to use next when one of the remaining 6 pages is accessed and therefore needs the maps set up. 5-9 The Virtual Memory System Software Design Notes Table 5-4 Map Usage Table (MUT) 15 14 13 8 7 2 1 0 +-----+-------+-------+-----+ | | left | right | Next| +-----+-------+-------+-----+ Next <0:1> : 00 --> wired page, always in left bank 01 --> use right bank next 10 --> use left bank next 11 --> unused Right <2:7> : The bottom 3 bits of this field indicate the top 3 bits of the page that currently has the map in the right bank. If the field is -1, then it is currently unused. Left <8:13> : The bottom 3 bits of this field indicate the top 3 bits of the page that currently has the map in the left bank. If the field is -1, then it is currently unused. <15:14> : Unused. 5.10 EXPLORER II MEMORY MAP ALLOCATION Explorer II map allocation is much easier than the Explorer I. When a map exception occurs, bits 9 through 21 are used to index into the MUT (actually, bits 10 through 21 are used to get the correct word and bit 8 is used to select the halfword). The NEXT field is accessed to see if the new map should be set up in the right or left VMM bank. If the left bank has a wired page, the right bank is always used. The appropriate RIGHT or LEFT field from the MUT entry is accessed to see who currently owns the map. If it is -1, then there is no current woner. The current user virtual address is calculated from the bottom 3 bits of the LEFT or RIGHT field from the MUT along with bits 9 through 21 of the current virtual address (i,e,m the one that needs the maps set up). This is used to invalidate the VMM Status Table for the two maps that currently are using the bank needed. The MUT is changed to reflect the new owner, the NEXT field is updated to use the other bank next time (unless it has wired status) and the table entry is rewritten. The VMM data in the correct bank is set up, and the VMM Status is set to valid with the correct bank select. The memory cycle that caused the page exception is then restarted. 5-10 Software Design Notes The Virtual Memory System 5.11 PAGE EXCEPTION HANDLING A memory reference which causes the maps to be altered, but can then complete produces a page exception. This includes ______________ references which must go to the PHT to reset the maps. A reference which cannot complete without access to disk (no valid information even in the PHT) is said to cause a page fault. This __________ section describes page exception handling. A page exception can be generated by the memory mapping hardware for a number of different reasons during the 2-level map lookup. A level-1 miss can occur if the valid bit is not set in the level-1 map. A level-2 miss occurs when a non-normal map status is found in the second level map. Examples page exceptions include inappropriate read/write access privileges; page is in the processor's PDL buffer or A-memory; page is marked as "trap on any access" (the "MAR" break feature) and others. Depending on the circumstances, some of these conditions may eventually be signalled as traps by the microcode, or the reference may continue and complete normally. The speicifc exception handling is based on the Memory Access and Memory Status fields and is described in detail below. 5.11.1 Memory Access Codes. Memory Access codes are listed in Figure 5-3. Access codes are determined by combining the access bit and the most significant bit of the status bits field. These codes specify what memory operations (read, read/write or none) are to be permitted to these pages. If the desired access is permitted the memory system performs the operation. If the desired access is inappropriate, the page fault condition is set and the page exception handler is invoked. The exception handler then uses the status code to determine what steps to take next. Access Bit MS Status Bit Code Access-Type Meaning ---------- ------------- ---- ------------------- 0 x 0,1 No Access 1 0 2 Read Only 1 1 3 Read/Write Figure 5-3 Memory Map Access Codes 5.11.2 Memory Map Status Codes In this section each memory map status code is examined in detail. The possible map status values and their interpretations 5-11 The Virtual Memory System Software Design Notes are shown in Figure 5-4. The page exception handler uses these codes to determine what action to take next. Code Meaning Access Type Action ---- -------------- ----------- ------ 0 Map Miss None (yet) Set up maps/Retry or Fault 1 Meta Bits Only None needed Set up maps 2 Read Only Read Only Force access or Trap 3 Read/Write First None (yet) Mark as dirty 4 Read/Write Any None 5 PDL Buffer Any PDL buffer or retry 6 MAR Any Possible MAR trap 7 Unused -- -- Figure 5-4 Memory Map Status Codes 5.11.2.1 Status Code 0: Map Miss. Any reference to a page with a Map Miss status code will cause a page exception. To handle the map not valid case, the following steps take place. Check to see if the page is in the A-memory map space. If so, the operation is simulated. Otherwise, consult the page hash table (PHT, see below) entry for this virtual address to get information about the page. The action taken from here depends on data in the PHT table. The data in the PHT will indicate if the page is in physical memory. The PHT contains an entry for each virtual page that is resident in physical memory. If an entry is found in the PHT for this virtual address, then the information in that entry describes the status and location in physical memory for this page. The memory maps are set up with this data and the memory reference is restarted. If there is no entry in the PHT for the virtual page referenced, then this page is not in physical memory. It must be brought in from secondary storage. The mapping of a virtual page to a disk address, the physical memory page frames to be used, and the disk operations are refered to as the swapping process. The details of this process are described later. For now, assume that the virtual page is read from the disk into physical memory, the map is set up to refer to this physical page frame, and the memory reference is restarted. 5.11.2.2 Status Code 1: Meta Bits Only. A page exception will be generated for any page that has a map status of Meta Bits Only. This code indicates that this map entry contains meta bits information but does not contain page- 5-12 Software Design Notes The Virtual Memory System location information. In other words, there is first-level map information available, but no physical mapping information. This type of map entry is created when a pointer to an object is used but the object itself is not referenced. The oldspace and region representation type bits in such a map entry are needed by the garbage collector. An attempt to access the storage associated with the object later will be treated like a map miss. 5.11.2.3 Status Code 2: Read Only. An attempt was made to write to a page that is set to read-only will cause a page exception. A special case is made for a forced write operation. In this case, the write occurs and no access fault is declared. This is needed so that the garbage collector/compactor can move data structures that ordinarily need protection. If the operation is a regular, non-garbage collection write and the special A-memory/Lisp variable SYS:%INHIBIT-READ-ONLY is NIL, then the operation is declared illegal and an error is signaled. If SYS:%INHIBIT-READ-ONLY is non-NIL, the access is allowed. 5.11.2.4 Status Code 3: Read/Write First. A page exception occurs on an attempt to write. The processing for this exception consists of changing the status in the map and the page hash table to read/write, indicating the contents of the page have been modified. The reference is restarted. This facility implements the dirty page status. If the page that is being set to dirty is currently assigned to a read-only page band, then it will be reassigned to a read/write page band (given swap space) later when the page needs to be swapped out of physical memory. 5.11.2.5 Status Code 4: Read/Write. A normal, fully mapped page. No exception should occur on this type of page. If this status occurs, the hardware is faulty, and a crash sequence will be initiated. 5.11.2.6 Status Code 5: Page might be in PDL Buffer. Certain areas which contain regular PDLs arrange to get the map set to this status for their pages (instead of read/write). The microcode has to decide, on every reference, whether the page is in the processor's PDL buffer registers or in main memory, and simulate the appropriate operation. It may be that only part, or none, of the page is in the PDL buffer on a particular reference. Thus the page exception handler must test the virtual address to see if it falls in the range which is really in the PDL buffer right now. If not, temporarily turn on read/write access, make the reference, and turn it off again. Pages may be swapped out 5-13 The Virtual Memory System Software Design Notes without regard for whether or not they are in the PDL. This works because the normal course of swapping out invalidates the second-level map. If the page is then referenced as memory, it will be swapped in normally and tis map status restored from the Region-Bits table, in the normal fashion. This will then restore the Maybe-PDL map status. Otherwise, the addressed word is in the PDL buffer. Translate the virtual address to a PDL buffer address and return the appropriate register contents. 5.11.2.7 Status Code 6: Possible MAR Trap. The memory address register (MAR) facility allows any word or contiguous set of words to be monitored constantly, and cause a trap if the words are referenced in a specified manner. The name MAR is from the similar device on the ITS PDP-10's. The MAR trap status is set for all pages that are in the range of addresses being monitored. This range is indicated in the A-memory/Lisp variables SYS:%MAR-LOW and SYS:%MAR-HIGH. When the MAR trap occurs, the virtual address is checked to see if it falls in the range. If so, a trap may be called. It should be noted that traps, since they cause sequence breaks, are not allowed during stack group switches, so if a MAR-monitored address is referenced, a sequence break flag is set, and the break will occur at the next appropriate time. If an address falls within the MAR'd range, then the action taken depends on the currently active MAR-mode (MAR-mode is actually a 2-bit field in each stack group's mode flags). The action taken for various flag word values is shown in Table 5-5. Table 5-5 MAR Status Codes Value Memory Operation MAR Mode Action 0 Read MAR disabled No trap 1 Read Read Trap Trap 2 Read Write Trap No trap 3 Read Read/Write Trap Trap 4 Write NAR disabled No trap 5 Write Read Trap No trap 6 Write Write Trap Trap 7 Write Read/Write Trap Trap 5.11.3 GCV and Oldspace Exceptions. In addition to access/status fault exception handling, exception handling is also performed for two garbage-collection- related conditions: Garbage Collection Volatility Fault and Oldspace. These two are described breifly below. More information on them 5-14 Software Design Notes The Virtual Memory System is presented in Section 9 (Garbage Collection). These exceptions are different from access/status exceptions in that the mapping hardware does not signal the page fault condition for them. Rather, the reference produces GCV and Oldspace conditions that the microcode can then selectively dispatch upon. 5.11.3.1 Oldspace. The Oldspace condition is indicated by the Oldspace Meta Bit in the first-level map being 0. It indicates that objects in these pages are currently being garbage collected. The Oldspace Meta Bit can be ORed selectively into a microcode dispatch. The TRANSPORT dispatches use this bit. The TRANSPORTER is invoked, which decides if this is an object that needs to be moved for garbage collection. For more information on the TRANSPORTER, see Section 9. 5.11.3.2 Garbage Collection Volatility Faults. The Garbage Collection Volatility Fault condition is also a 1-bit field. It is signaled whenever a younger object (contained in MD, memory data register) is written into older memory (represented by VMA, the memory address register). The GCV output is determined by a comparator which examines the 3-bit GCV field in the first-level map and the 2-bit GCV field in the second-level map. The details of the fault inputs and output, along with their interpretations in the Temporal Garbage Collection implementation, are presented in Section 9. On the Explorer I, the GCV fault is stored in an inaccessible 1- bit GCV register, and is preserved only undil the next memory reference is performed. Thus, it can only be sensed by a dispatch using GCV done immediately after the memory cycle. On the Explorer II, the GCV register can be read and written as a functional source and destination, hence can be stored across other memory references. 5.12 VIRTUAL MEMORY SYSTEM TABLES There are some additional tables associated with paging that are used by the microcode: the Page Hash Table (PHT) contains an _______________ entry for every virtual page that is currently memory resident. The physical page data table (PPD) contains an entry for every ________________________ physical page of memory. These tables are described in further detail below. 5.12.1 Page Hash Table. The page hash table (PHT) resides in physical memory and is not part of the virtual address space. It describes every virtual 5-15 The Virtual Memory System Software Design Notes page that is currently resident in physical memory. When the microcode detects a map miss, the PHT is consulted to see if the virtual page is still in physical memory. If so, the Level 2 maps (Explorer I) or VMM hardware (Explorer II) can be set up from the information stored in the PHT, and the memory reference will be restarted. Since the mapping hardware now contains valid mapping information, the reference should complete normally. If there is no valid PHT entry for a virtual address, a page fault is said to have occurred, and the page must be read in from disk. The page hash table is also used to store niformation used by the page aging and swap management functions. A full description of the role of the page hash table in these contexts is described in a later section. 5.12.2 Physical Page Data Table. The Physical Page Data Table (PPD) resides in physical memory and is not part of virtual address space. When the system is booted, the system determines the size of primary memory and allocates a suitable portion of physical memory for this table. An entry for a page in the Physical Page Data Table is shown in Table 5-6. There is one PPD entry for every 512-word page of physical memory. A PPD entry thus represents a logical page ____________ frame or page frame number (PFN) in the physical memory pool. _____ _________________ Each entry is broken into two pards. The low order 16 bits of the word contain an index into the Page Hash Table or a page allocation status. The high order 16 bits of the word contain an index into the Physical Page Data Table linking this page to the next most recently used physical memory page. All the physical pages that are allocated to hold the microcode management tables are marked #x+FFFFFFFF, to indicate that these pages are not to be used in the virtual memory page pool. The Physical Page Data Table is used to determine which virtual page is contained in a given physical page. The microcode page aging and replacement algorithms are driven by a scan of the Physical Page Data Table. 5-16 Software Design Notes The Virtual Memory System Table 5-6 Physical Page Data Area Word Format Value Meaning ----- ------- PHT INDEX FIELD: FFFF (hex) System wired or permanently wired page. Page is not available in virtual memory pool. FFFE Free page. Page is available in the virtual memory pool but is not currently in use. PHT Index Normal page. Value contains the index of the page hash table entry for this page. PPD LINK FIELD: FFFF (hex) Not available. Page is not available in virtual memory pool. FFFE Write in progress. Page is in virtual memory pool, but is currently being written to disk. FFFD End of LRU list. Page is the most recently referenced page in virtual memory pool. PPD Link Normal page. Value is index of the physical page table entry of the next most recently referenced page in the virtual memory pool. Given a page frame number, information about the virtual page associated with the physical page can be determined as follows. Use the PFN as a word index into the PPD. If the PPD index field is valid (greater than FFFE), then there is a virtual page in this page frame. Use the index field shifted left by 1 as a word index into the PHT. 5.13 A-MEMORY PAGING INFORMATION In addition to the Explorer I Reverse-First-Level-Map, other virtual-memory-specific information is kept in portions of A- memory, as described below. 5-17 The Virtual Memory System Software Design Notes 5.13.1 PDL Buffer Handling. A-memory also contains the first virtual address which currently resides in the PDL buffer (in A-PDL-BUFFER-VIRTUAL-ADDRESS), and the PDL buffer index corresponding to that address (in A-PDL- BUFFER-HEAD). Note that the valid portion of the PDL buffer can wrap around as shown in Figure 5-5. When a page exception is taken for a page that might be in the PDL Buffer, the microcode handler must check to see if the virtual memory address falls in the valid portion of the PDL Buffer. The further processing of this case is explained under the map level 2 status code for PDL Buffer (status code 5). 0 PDL Buffer 1023 +-------------+---------------------+--------------+ | | | | | valid top invalid base valid | | | | | +-------------+---------------------+--------------+ Figure 5-5 PDL Buffer Wrap-Around 5.13.2 Physical Memory Map. The Physical Memory Map (PMM) is a set of A-memory locations which describe which logical page frame numbers (PFNs) reside at which physical memory (NuBus) board addresses. Each entry in the PMM describes one or more 2MB quantums of physical memory. The number of 2MB quantums is kept in the low 10 bits, while the top 22 bits give the (NuBus) physical page frame number where the first quantum starts (see Figure 5-6). 31 10 9 0 +-----------------------------------+--------------+ | physical page frame number | # of quanta | +-----------------------------------+--------------+ Physical Memory Map Entry Figure 5-6 Physical Memory Map Entry 5-18