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.
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 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.
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 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.
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 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:
INDICATE USER/EXEC ETC. AS:
=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:
COMPARED ASSOCIATIVELY FOR USER & XUSER, IGNORED FOR
EXEC. HIGH ORDER BITS OF ABSOLUTE (13 IGNORED).
BITS 18-26:
ADDRESS INTO MAP MEM FOR EXEC AND USER, COMPARED
ASSOCIATIVELY FOR XUSER, PART OF ADDRESS FOR
ABSOLUTE.
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
10 TO 17 HAVE NO ASSIGNED USE. MAY BE USED WITH THE
"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.
POINTERS
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
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 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
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.
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 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
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 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
invalidated.
LOGIC DESCRIPTION
An explanation of the refill mechanism and logic implementation
follows.
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 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.
MAP MISS
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
bounds.
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
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 and
stores appropriate things in the map or follows the chain.