perm filename FL4[M,PMP] blob sn#008151 filedate 1971-09-19 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  18
bit  address  in  the  Cache  Address  Latch -CAL (see figure 1). The
address is divided into the upper and lower 9 bit halves (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 high order 9 bits and the EXEC/USER bit 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            23 24                       35
| 00 | R W X | |   - - - - -    |  real address bits 15-26  |
              - access permission

 This is the simplest type. Bits 2-4 (read, write, and execute
permission  bits)  along  with bits 24-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   9 10  12 13  15 16           35
| - | R W X | | --- | type | ---- |   address     |
             - access permission

 Bits 16-35 contain an absolute address if bit 10 is  a  zero,
otherwise bits 18-35 are an EXEC address if bit 12 = 0, or an address
in the current user map if bit 12 = 1.
 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       --
        5      USER
        6      Shared page table
        7      Indirect page table pointers

 The  other  eight  pointers  are used to reference extra user
maps (XUSER) for the IO devices, PI  channels,  and  the  XCT  mapped


 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  pointer  (P5) has a  9  bit field (0- 8) which has
the number of words in the user page table. References which  try  to
access pages outside the defined page table will cause page faults.


 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
 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 pointer (P5)


 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 an XUSER map,
an  additional  three  bits  specifies  one  of   eight   associative
registers.   If  the  selected associative register is not valid, the
corresponding  page  table  address  from  the  upper  eight  pointer
registers  is  used  to  look  up  the  map entry.  The output of the
associative register is supplied to the comparator.

 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 (if  not  locked
and  private  with  access permission) is written simultaneously with
clearing the valid bits for the other three entries. Then each of the
other  three  is examined in turn and written if it is unlocked and a
valid private entry. 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


 Referring to the logic diagrams, the flow chart (Fig 3),  and
the  data path diagram (Fig 2) an explanation of the refill mechanism
and logic implementation will be given.


 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  an  real
address  for  the  cache  comparator.   If  the  address  is absolute
(~CAL10), CAL16-26 are passed through tri-state buffers onto MAP  BIT
16-26. If the address specifies xuser (CAL10∧CAL11), CAL  6- 9 select
one of  16   associative registers, and XUSER MATCH is  true  if  the
register is valid and the virtual page number associates.
 In the case of exec or user mapping CAL 25-26 select  one  of
four  sets of 256*16 memory (QUARTER 0-3) while the exec/user bit and
CAL 18-24 select one of the 256 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
beginning of each cycle, one of the pointer registers is selected  at
the  output  of MAPL. This may be either user (P5), exec (P0,P1,P2 or
P4), or xuser (P10-P17). 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  P10 maps there is an additional 10 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 bounds.
 If DBLOV is not true, then the mapper causes DEV0 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
into one of four states. These are:
       1)        If the access permission bit (MWD5) is off then
                 MW0 is entered to write a valid entry that
                 will cause a page fault when accessed.
       2)        If the word fetched was not an indirect page table
                 pointer and VAL4 is not yet on
                 then MW4 is entered. A request is made to the M-box
                 to have a cycle to write the four entries and when
                 finished (MAP CACHE CYCLE) it is done unless
                 the desired one of the four is not a private, in which
                 case MF1 is entered to follow the rest of the chain.
       3)        If VAL4 is already true or we can't write all four
                 entries, MW1 is entered if the desired page entry is
                 simply private. The M-box request is made and the entry
                 is written. If VAL4 wasn't set however, all four entries
                 are written, but the other three will have their
                 individual valid bits off.
       4)        If the chain needs to be followed further or the word
                 fetched was the indirect page table pointer then MF1
                 is entered. This causes another DEV0 IO RQ and falls
                 back into ME. If the page entry was of the indirect
                 type, then IND is set.