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.