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.
M-BOX MAPPING
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.
PAGE TABLE FORMATS
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.
PRIVATE PAGE
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.
SHARED PAGE
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.
INDIRECT PAGE
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
format:
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.
POINTERS
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
instructions.
EXEC MAPPING
The EXEC address space is mapped by four possibly separate
page table segments as follows:
__
00
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.
USER MAP LENGTH
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
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 pointer (P5)
ABSOLUTE AND XUSER MAPPING
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.
FOUR WORDS WIDE
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
invalidated.
LOGIC DESCRIPTION
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.
NO MAP MISS
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.
MAP MISS
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
true).
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.