perm filename FL4[1,PMP] blob sn#020615 filedate 1973-01-14 generic text, type T, neo UTF8
This document has two purposes.   It  is  intended  to  give  someone
familiar  with  existant maps on the PDP-10 some idea of the features
implemented in the SF map, and at the same time allow someone  trying
to  explore  the logic diagrams additional information to clarify the
intent behind the design.

 The  mapping  process  itself  is  tied  into  the  structure of the
cache memory. The M-box recieves at the beginning of a  cycle  an  25
bit  address  in  the  Cache  Address  Latch -CAL.   The  address  is
divided  into  3  parts  --  low 9, high 2 and middle 14 (implying  a
512 word page size). The low order bits select the place in the cache
that the addressed word may be stored. There are four possible  slots
for  any word with given address bits 27-33, and they are read out of
the cache data part while the real  addresses  corresponding  to  the
four  possibilities  is read from the cache address part. At the same
time, the middle 14 bits and  the  EXEC/USER/XUSER/ABSOLUTE  bits are
used to address a 1K memory  which produces the real (mapped) address
of the page. This mapped address is then compared with the four cache
real addresses to select the slot  that  contains  the  proper  word.
Additional bits contained in the map entry provide for  read,  write,
and execute access protection.

 Entries  are  written  into  the  MAP  on  a  demand basis. If a map
entry is not valid a MAP MISS is signaled for the current cycle and a
refill mechanism is activated to look in core and find the page entry
required. When a map is changed, the entire MAP or a  specific  entry
may be invalidated, forcing the next reference to cause a refill that
accesses the updated page table.


 There  is  a  sixteen  word  table  of  pointers (P0-P17) built into
the  map  hardware.  For access to the user page map, the page number
(CAL 18-26) plus the user pointer (P5) gives the location in the page
table  in  core  of  the  page  entry,  which  may be of three types:
private, shared, or indirect.


0   1  2 3 4  5  6            22 23                       35
| 00 | R W X | |   - - - - -    |  real address bits 14-26  |
              - access permission

 This  is  the  simplest  type.  Bits  2-4  (read, write, and execute
permission  bits)  along  with bits 23-35 are written into the MAP if
the access permission bit is on.


0   1  2 3 4  5  6       8   9               21 22    35
| 01 | R W X | |  - - - -  | shared page number|  ---   |
              - access permission

 This  entry  type  causes  a  further  reference  to the shared page
table (pointed to by P6) indexed by the shared page number. Bits  2-4
will reduce the final access permission written in the MAP.


0   1  2 3 4  5 6   8  9                          21 22         35
| 10 | R W X | |  -  |     indirect page table #    | page number |
              - access permission

 If  bits  9-17  are  not  all  one,  then  the indirect  page  table
number  is  used as an index into a table pointed to by P7. The entry
in this table is a pointer to a new page table and has the  following

0  1  2 3 4  5 6  10 11  12 13                  35
| - | R W X | | --- | type |       address        |
             - access permission

 Bits 11-35 contain a standard format address.
                         STANDARD ADDRESS FORMAT:

      BITS 11,12:
                 =0  USER      (13 TO 35 ARE 23 BIT VIRTUAL ADDRESS)
                 =1  EXEC      (18 TO 35 ARE 18 BIT VIRTUAL ADDRESS)
                 =2  XUSER     (13 TO 35 ARE 23 BIT VIRTUAL ADDRESS)
                 =3  ABSOLUTE  (14 TO 35 ARE 22 BIT ABSOLUTE ADDRESS)
      BITS 13-17:
                     EXEC. HIGH ORDER BITS OF ABSOLUTE (13 IGNORED).
      BITS 18-26:
      BITS 27-35:
             ADDRESS INTO CACHE.

                        USES OF MAP POINTERS

            0-3  EXEC:   0  FOR  000000 TO 177777
                         1  FOR  200000 TO 577777
                         2  FOR  600000 TO 637777
                         3  FOR  640000 TO 777777

            4    USER
            5    XUSER
            6    SHARED
            7    INDIRECT
                     "IMMEDIATE" MODE OF INDIRECT.

 The page  number from bits 27-35 of the indirect page entry are used
as  an  index  into this page table to fetch another page entry which
may be any of the three types.
 If bits  9-17 are one, bits 18-21 select one of the  pointers in the
map hardware in place of the page table pointer in core.


 The definitions of the first eight pointer registers are:

        0      EXEC A
        1      EXEC B
        2      EXEC C
        3      EXEC D
        4      USER
        5      XUSER
        6      Shared page table
        7      Indirect page table pointers


 The  EXEC  address  space is mapped by four possibly separate
page table segments as follows:

                                     04  EXEC A
------------                         10
|  EXEC A  |  0                      14 __
|          |                         20
------------                         24
|          |  64K                    30
|  EXEC B  |                         34  EXEC B
|          |                         40
------------                         44
|  EXEC C  |  192K                   50
------------                         54 __
|  EXEC D  |  208K                   60 __ EXEC C
------------                         64
                                     70   EXEC D
                                     74 __

 The  purpose  of  this  bletchery  is  to allow portions of the exec
space to be mapped by different page tables,  and  to  permit per-job
and per-fork portions of the map.


 The user and xuser pointers (P5&P5) have a 11 bit field (0-10) which
has the largest number which a user address, bits 13-23, can contain.
References which try to access pages outside the defined  page  table
will cause page faults.  This  is  to  avoid  using infinite core for
small page tables.


 Page  faults  are caused on an M-box cycle if the  reference type is
not permitted by the bits read out of the MAP.
 In  addition,  faults detected during  the refill cause a page entry
with 000 access bits to be written in  the  MAP.  These  errors are:

 NACK         access permission bit was off in a word fetched
 TOO DEEP     too many shared or indirect lookups or too many
              refills invoked by mapper references
 PAGE FAULT   page fault occured on mapper reference.
 DBLOV        reference to a page outside range specified
              by length field of user or xuser pointers.


 There are two other places that the real address fed  to  the  cache
comparator  may  be obtained.   If the address in the CAL is absolute
then the high order bits bypass the MAP  and  are  supplied  directly
to  the comparator.  If the address specifies the XUSER map,  another
whole  map  is   simulated  by  one  associative   register.  If  the
associative  register  is  not  valid,  the  corresponding page table
address from the P5 pointer register is  used  to  look  up  the  map
entry.  The output of the associative register  is  supplied  to  the

 The mapper accesses memory through  the  IO channel,  which supplies
four word blocks.  The MAP is organized so that four page entries may
be written at once, and in addition to the valid bit per entry  there
is a valid bit for each block of four entries. When the  initial page
table lookup is made, the desired  entry  is  written  simultaneously
with as many of the other 3 entries as are not already  there and are
valid private entries. If the desired entry is a shared  or  indirect
type,  further  references  are made and the eventual private type is
written in the corresponding single entry  in  the  MAP  leaving  the
other  three  undisturbed.  The valid-4 bits are cleared in groups of
256 pages, allowing the entire user (or exec) portion of the  MAP  to
be  cleard  in  two  cycles.  In  addition,  any  single entry may be


 An explanation of the  refill  mechanism  and  logic  implementation


 The simplest case is when the page entry is  found valid  in the MAP
and no refill is required.
 As mentioned, there are three  paths  that  produce  a  real address
for the cache comparator. If the  address is  absolute, CAL14-26  are
passed through tri-state buffers onto MAP  BIT 14-26. If the  address
specifies xuser, XUSER MATCH is true if the register is valid and the
virtual page number associates.
 In (he case of exec or user  mapping the  exec/user bit (CAL 12) and
CAL 18-26 select one of the 1024 entries. AT the same time, exec/user
and  CAL  18-25  select  one of the valid-by-four bits (VAL4) and MAP
MISS is developed. The three access bits are compared with the  cycle
type  and  PAGE  FAULT  may be asserted. If MAP MISS didn't occur, no
further action is taken by the mapper  and  the  M-box  produces  the
selected  word.  Due to the way the M-box works, all write cycles are
proceeded by STORE CHECK cycles. This allows  the  mapper  to  detect
write access violations in advance of the data being overwritten.


 The  mapper  when  idle  is in the enabled (ME) state. At the  start
of  each  cycle,  one of the pointer  registers  is  selected  at the
output  of  MAPL. This may be either  user (P4),  exec (P0, P1, P2 or
P4), or xuser (P5). The high  order  bits of the CAL  are  latched in
CALM  and  selected by MAPR.  The sum is produced in the adder (MADD)
and the resulting address latched in MAPO. This is the address of the
page entry if a MAP MISS were to occur on this cycle. Towards the end
of the cycle MAP MISS is latched (at B1C0 time) and if true, holds up
the  selected  pointer and the page number in CALM. Now if the mapper
is  not  already too deep in an indirect or shared page chain and the
mapper is not active already in refilling a  previous  map  miss,  it
advances to the fetch (MF) state.
 For  user  and  xuser maps there is an additional 11 bit  field that
contains the number of pages allowed  the page table.  While the page
table address is being computed, a comparison is made with  the  page
number in CALM.  The signal  DBLOV is  aserted if the  page is out of
 If DBLOV is not true, then the mapper causes  DEV3 IO RQ,  and holds
the  computed  address  in  MAPO  to  start  the  IO channel.  The IO
channel has a separate bus to the memories, but it will first look in
the  cache  to  check  to  see  if  the data is stored there. Now the
address in the pointer may have  been  a  mappable  address,  so  the
mapper turns on MAP BUSY and falls back into ME. If a map miss occurs
on the IO channel fetch, the mapper will abandon the original request
and  will  try  to  fill the map entry needed to reference the paging
information. The original cause for map miss (I-box  or  E-box)  will
still  be asserting its request, so that when the refill is completed
and MAP BUSY is turned off, the MAP MISS  from  the  original  source
will again start the map, this time with hopefully more success. When
MAP BUSY is true, the only MAP MISS that will cause  mapper  activity
are those caused by the IO channel servicing the mapper (MAP IO CYCLE
 If  DBLOV  was  true, this caused PAGE FAULT and not MAP MISS.
 When the IO channel cache access is  successful,  the  mapper  drops
out  of ME into  MWAIT  where it sets up  the  adder  to  follow  out
the chain in case the page entry is shared or indirect.  MAPR selects
either MWD 9-21 which is the field  that  contains  the  shared  page
number or the indirect page table number, or the latch PN  which  has
the  page  number  from  MWD 27-35 saved from the indirect type. MAPL
selects one of four sources:
      MWD  9-21        when fetching the indirect page table pointer
                       MAPR will have PN
      P6               when the page entry read is shared, MAPR has
                       MWD  9-21, the 13 bit shared page number
      P7               when the page entry is indirect, MAPR has
                       the 13 bit indirect page table number
      P(MWD 18-21)     when the page entry is indirect, and the
                       13 bit number specifies one of the pointer
                       registers directly. MAPR has PN which is
                       passing through MWD 27-35.
 When  the  IO channel finally  obtains the  four  words and  after a
synchronizing delay, IO DONE comes on and the mapper leaves MWAIT and
stores appropriate things in the map or follows the chain.