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.