VMEM, a virtual memory package for the Alto ***** Note: there has been a change in the division of VMEM procedures among the .BR files. See the last section of this writeup for details. ***** The VMEM package provides a virtual memory facility for Alto programs. The virtual address space is 2↑24 words; the page size is 2↑8 (256, 400b) words. The package uses several data structures for which you (the user) must supply storage, as follows: 1) A hash map, whose size is 2P+1 words, where P is the largest number of 256-word paging buffers you will ever have allocated at one time, rounded up to a power of 2 (e.g. if you have 20K for paging buffers, this is 80 buffers, so P=128). 2) An optional logging area, located just below the hash map. If desired, VMEM will make an entry in this area each time you make a reference to a virtual address, and call a procedure when the area fills up. 3) A buffer pointer table of 256 words. 4) Paging buffers, as many as you want, located anywhere in core (not necessarily contiguous). Each group of buffers is truncated if necessary so that it starts at an address which is a multiple of the page size (400b) and is a multiple of the page size long. 5) A locked cell list of 2N+2 words, where N is the largest number of cells you will ever want to use as locks (see below). VMEM is designed to use special microcode loaded into the Alto microinstruction RAM, although it will run properly without such microcode. Unfortunately, there is no straightforward procedure for getting the relevant microcode into the RAM and getting it properly hooked up to the Nova emulator, if it is to share the RAM with any other special microcode. People wishing to use the RAM with VMEM should be prepared to include the microcode source in their own microprograms. 1. Initialization VmemRam() VmemSoft() Before calling InitializeVmem, you must call one of these two procedures to tell VMEM whether or not you are using the RAM. After calling InitializeVmem, you may call either of these procedures at any time if you want. InitializeVmem(HMAP, HMAPSIZE, BPTAB, LCL, LLCL, MSBASE, MSPROC[, NBPROC]) HMAP is the address of the hash map; HMAPSIZE is 2P (256 in the example of 80 buffers.) (VMEM will clear the hash map.) BPTAB is the address of the buffer pointer table. LCL is the address of the locked ------------ Copyright Xerox Corporation 1979 Virtual Memory package August 1, 1977 2 cell list, and LLCL is its length. MSBASE is the base of the logging area (below HMAP), or 0 if no logging is desired. MSPROC is the procedure to call when the logging area fills up (see below). NBPROC is an optional procedure to call when VMEM cannot find enough unlocked buffers to handle a page fault or a SnarfBuffer call (see below): VMEM will call NBPROC and then try again, indefinitely. If NBPROC is not supplied, VMEM will call Swat instead. AddBuffers(FIRST, LAST) In order for VMEM to function, you must give it space for page buffers with AddBuffers. FIRST and LAST are the bounds of a core area to be used for this purpose. FIRST will be rounded up to the next multiple of the page size if necessary, and LAST+1 rounded down; thus AddBuffers(7700b, 10077b) followed by AddBuffers(10100b, 10377b) will NOT result in the space from 10000b through 10377b being made into a page buffer. 2. Mapping functions A 24-bit address: $-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$ | high part | low part | $-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$ | virtual page part | word part | $-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$-+-+-+-+-+-+-+-$ "The virtual address (HI, LO)" means a virtual address whose high part is bits 8-15 of HI (bits 0-7 being zero) and whose low part is LO. For implementation reasons, virtual pages -8 through -1 are not legal. If you try to read from page -1, you will get back unspecified data. If you try to read from pages -8 through -2, or write in any of these pages, VMEM will call Swat. All of the mapping functions described in this section are declared global (page zero), so you must declare them external with @- sign. VRR2(HI, LO) Returns a core address corresponding to the virtual address (HI, LO), having read the page into a buffer if necessary. VWR2(HI, LO) Same as VRR2, but assumes you are about to write into the page, so marks it as needing to be rewritten onto the disk. VRR1(LO) Same as VRR2(0, LO). If you only have a 2↑16-word virtual space, you can save a small amount of code by using VRR1 instead of VRR2. VWR1(LO) Virtual Memory package August 1, 1977 3 Same as VWR2(0, LO). VRR(PTR) Same as VRR2(PTR!0, PTR!1). Useful if you are carrying around addresses in vectors, as Lisp does. VWR(PTR) Same as VWR2(PTR!0, PTR!1). VRRP(VP) Same as VRR2(VP RSHIFT 8, VP LSHIFT 8), i.e. converts a virtual address whose virtual page number is VP and whose word part is zero. Useful if you are only using the virtual memory package to manage buffers, and doing your own data scanning. VWRP(VP) Same as VWR2(VP RSHIFT 8, VP LSHIFT 8). 3. Statistics MSPROC(ARG, N[, VP]) [MSPROC from InitializeVmem] If N<0, ARG is a core page number (i.e. a core address divided by 400b), and the type of event depends on N as follows: N=-1: page ARG is being freed because it is needed for some other purpose than holding its current page of data. VP is the virtual address currently in the page. N=-2: page ARG, formerly not available to VMEM, has now become available (through AddBuffers or UnsnarfBuffer). N=-3: page ARG, formerly available to VMEM, has now become unavailable (through SnarfBuffer). If N>=0, ARG is the MSBASE argument to InitializeVmem or InitSoftVmem, and N words (N/2 entries) starting at ARG contain 2-word entries representing calls on the address mapping functions. Each entry consists of a 24-bit virtual address with the top 8 bits unused: no distinction is currently made between reads and writes. If you are not using the RAM, VMEM will start reusing the area starting at MSBASE; however, if you are using the RAM, VMEM cannot determine the correct value of N (and will call MSPROC with N=0), so MSPROC must return this value and reset the R or S register itself. 4. Other facilities REHASHMAP(VP) Looks up the virtual address VP*400b in the hash map, returning 0 if present, or the address of an appropriate empty slot in the hash map if not present. Used by the page fault routine to reconstruct the hash map, but also useful for determining quickly whether a page is in core. VirtualPage(CPAGE) Virtual Memory package August 1, 1977 4 Returns the virtual page currently occupying core page CPAGE. Returns -2 if CPAGE is currently empty, or -3 if CPAGE is unavailable to VMEM. If CPAGE is not in the range 0 to 377b inclusive, returns garbage. SnarfBuffer(BUFPTR[, NBUFS, ALIGN]) BUFPTR must be the address of a buffer (i.e. a multiple of the page size) within the scope of some previous call to AddBuffers, or 0 meaning any buffer(s) will do and SnarfBuffer should find it (them). The effect of SnarfBuffer is to remove NBUFS (default is 1) buffers starting with that buffer from use by VMEM. A typical application of SnarfBuffer is to acquire space for display data or Ethernet buffers. If BUFPTR is non-zero and some buffer in the specified range is locked (see below), SnarfBuffer returns 0; normally SnarfBuffer returns the address of the buffer. If you need a group of buffers aligned as described under PageGroupAlign below, you may also supply an ALIGN argument, which works the same way as the value returned by PageGroupAlign. UnsnarfBuffer(BUFPTR) Reverses the action of SnarfBuffer. If you acquired a range of buffers, you must return them one at a time with UnsnarfBuffer. LockCell(LVLOCK, PROC) Declares that the cell whose address is LVLOCK holds a core address which must remain valid across page faults, i.e. the buffer in which it lies must not be re-used. Note that the extra level of indirection means that your program can store into the lock cell freely. As a consequence, if you store some arbitrary bit pattern into a lock cell, it will function as a lock if it happens to constitute an address within some buffer. When the virtual memory system wants to change the contents of a buffer, it goes through the lock list and calls PROC(LVLOCK, NEWADDR, false) for each lock cell which contains a pointer into the buffer, where NEWADDR is the proposed new core address for the page (if it is just being moved around in core, e.g. to make room for a page group) or 0 (if it is being written out). If any PROC returns false, the system will refrain from the proposed action. If all PROCs return true, the system calls PROC(LVLOCK, NEWADDR, true) for each appropriate lock cell, and updates the contents of the lock cell (zeroing it if the page is being written out) in the process. Note that in the latter case, the lock cell will NOT be restored automatically if the page is read back in at some future time. The number of different lock cells is limited to the parameter LLCL supplied to InitializeVmem, divided by 2, minus 1. If the lock list is full, LockCell calls Swat. The system provides the procedures LockOnly, LockReloc, and LockZero, described below, simply because they are useful default actions: the user may provide an arbitrary procedure for PROC. LockOnly(LVLOCK, NEWADDR, FLAG) Virtual Memory package August 1, 1977 5 If the PROC parameter of LockCell is LockOnly, the system will not move or write the page. LockReloc(LVLOCK, NEWADDR, FLAG) If the PROC parameter of LockCell is LockReloc, the system may move the page in core (updating the lock cells), but will not write it out. LockZero(LVLOCK, NEWADDR, FLAG) If the PROC parameter of LockCell is LockZero, the system may move or write the page whenever necessary, zeroing the lock cell in the latter case. UnlockCell(LVLOCK) Undoes the action of LockCell. Returns true if LVLOCK was actually in the lock cell list, or false if it was not. IsLocked(PTR, FLAG) If PTR is a pointer into a locked buffer, returns true, otherwise returns false. If FLAG=true, IsLocked returns true even if there are locked pointers into the same buffer as PTR, provided that the relocation procedures are willing to have the buffer swapped out; if FLAG=false or FLAG is absent, IsLocked only returns true if there are no locked pointers to the buffer whatever. Note that if the page addressed by PTR itself is not locked, IsLocked will return false even if there exist locked pointers to other pages in a page group which PTR points into. FlushBuffers() Rewrites all dirty pages from buffers onto the disk, including locked pages, and generally tidies things up in preparation for quitting. (It is OK to go on using the virtual memory after this, you just have to do another FlushBuffers before quitting eventually.) 5. User routines The VMEM package does not assume any particular correspondence between virtual addresses and disk pages, or indeed that you are using the disk at all: for example, you can use the Ethernet for paging if this suits your fancy, or store the data in some compressed form on the disk. Consequently, you must supply a number of routines to establish the correspondence between virtual page addresses and stored data. CleanupLocks() This routine is called on every page fault, and at other times when VMEM needs to know that the contents of the lock cells are correct. Normally, CleanupLocks need not do anything; however, if you have pointers in microcode registers or other non-standard places which point into page buffers, CleanupLocks should copy them into lock cells known to VMEM. PageType(VPAGE, WFLAG) Virtual Memory package August 1, 1977 6 This routine is called on a page fault to determine if a page has never been referenced, already exists, or is invalid. VPAGE is a virtual page number (the high 16 bits of a 24-bit address); WFLAG is true if the fault was from a write reference, false if from a read reference. PageType must return 1 if the page is an existing page, or -1 if a new page. If VPAGE is invalid, PageType can do whatever it wants, but it should not return. PageGroupBase(VPAGE) PageGroupSize(VPAGE) These routines are for applications where it is necessary to cause a group of pages, rather than a single page, to always be transferred into and possibly out of core at the same time and to occupy consecutive page buffers. PageGroupBase must return the virtual page number of the first page in the group; PageGroupSize must return the size of the group. If you are not using page groups, PageGroupBase should return its argument, and PageGroupSize should return 1. VMEM distinguishes between read groups, in which individual pages may be rewritten if they become dirty, and write groups, in which the entire group must be rewritten if any page becomes dirty. For write groups, PageGroupSize must return the negative of the size of the group. PageGroupAlign(VPAGE) Occasionally it is necessary to align a page or group of pages so that some of the bits of the core address are zero; for example, if you want to get the effect of 1000b-word pages, it is necessary to align each group so that the 400b-bit of its core address is zero. PageGroupAlign should return a mask which specifies which of the high- order 8 bits of the core address must be zero; in the example, PageGroupAlign should return 1. For pages which do not require alignment (the usual case), PageGroupAlign should return 0. DOPAGEIO(VPAGE, CORE, NPGS, WFLAG) This routine must transfer NPGS 256-word pages, starting at virtual page VPAGE and core address CORE, to or from the swapping medium, depending on WFLAG: false means read, true means write. 6. Standard use The standard use of VMEM is to do swapping on a standard disk file in which virtual page N corresponds to file page N+2 (page 1 is reserved for use as an index, and page 0 is the leader page), using the ISF package (described elsewhere) to obtain rapid random access to the file. The following program fragment will accomplish this, assuming you are just using 400b-word pages in the most straightforward way. external // entries for VMEM [ CleanupLocks PageType PageGroupSize PageGroupBase PageGroupAlign DOPAGEIO Virtual Memory package August 1, 1977 7 ] external // links to ISF [ InitFmap IndexedPageIO ] static [ MyFmap // pointer to work area for ISF ] // To initialize ISF, set MyFmap to point to a work area // of size MyFmapLength, and then call // InitFmap(MyFmap, MyFmapLength, FilePtr, true) // where FilePtr is a FP (see the O.S. manual) // for the paging file. A reasonable value for // MyFmapLength is 80 -- see the ISF writeup. let CleanupLocks() be [ ] let PageType(vp) = 1 let PageGroupSize(vp) = 1 let PageGroupBase(vp) = vp let PageGroupAlign(vp) = 0 let DOPAGEIO(vp, core, np, wflag) be [ IndexedPageIO(MyFmap, vp+2, core, np, (wflag? -1, 1)) ] 7. Packaging The VMEM package actually consists of several files: VMEM.BR - the code required to process page faults, plus LockCell and UnlockCell VMEMAUX.BR - all the other entries to VMEM, except InitializeVmem VMEMINIT.BR - InitializeVmem VMEMA.BR - a small amount of assembly-language code VMEMSOFT.BR - a software version of the VMEM microcode VMEM.USE - the program fragment listed above VMEM.MU - the VMEM microcode. You must load VMEM, VMEMAUX, VMEMINIT, and VMEMA with your program, and also VMEMSOFT if (as is normally necessary) you are not using the RAM. In addition, you must load the ISF package (files ISF.BR and ISFINIT.BR) if you are using VMEM in the standard manner described above. Once you have called InitializeVmem, you may throw away VMEMINIT; once you have done all your calls on AddBuffers, etc., you may throw away VMEMAUX.