Here we generalize Classic Memory Maps.
We abstract a general pattern that spans classic maps and a few other real and proposed mapping architectures, such as Page Table Structures For Fine-Grain Virtual Memory and Power PC.
All of these schemes are compatible with the TLB idea from the classic design.
We will thus ignore the TLB here.
These general patterns also cover the semantics of Keykos segment which are exposed to some Keykos applications.
Mapping a virtual address to a physical address proceeds in several sequentially dependent steps which are somewhat like each other.
Between steps there is a goal and a concomitant state of the hardware that consults the mapping tables; we describe that goal and state here.
The state includes:
- An address Addr under consideration.
Addr is commonly part of the original virtual address, but not always.
It may be larger than any virtual address.
- The address TA of the next table to be used to further process this translation.
TA may be real or virtual as in virtual linear page tables.
- There is an optional permission state that indicates whether a write operation to the original address is to be allowed.
- There are other optional states that determine data cache strategy.
- There is a level counter or other finite state set S which prevents infinite recursion or otherwise governs behavior.
- An indication of just which contiguous bits from Addr will serve to index into the table TA to fetch the descriptor to process the next step of translation.
The table is generally an array of items usually called entries if they are simple, or descriptors if they are not.
The full translation begins with the following state:
Addr is produced by program logic and perhaps ASID from a privileged register.
TA is provided by a privileged register.
All permissions are present.
S is initialized according to its internal logic.
The initial bits to be used from Addr are determined from another privileged register.
(The 68K map is the only machine I know that implemented this.
It was useful.)
At each step:
- The map hardware selects the indicated bits from Addr and fetches the descriptor from table located by TA and indexed by the selected bits.
- Depending on bits from the descriptor parts of all of Addr are replaced.
- TA is replaced by a field from the descriptor.
Permissions are decreased by descriptor bits (or at least not increased).
- Indexing bits indication is from the descriptor.
- Fault conditions are specified in descriptor which may depend on translation state.
- End of translation steps may be specified.
After the last step TA becomes the real translation of the original virtual address.
In most systems it is required that the real address be valid and the behavior is unspecified otherwise.
Ramifications
This pattern leads to an external behavior where segments can be composed of other segments.
Each composition is defined by a descriptor.
This composition is recursive.
The kernel which spans the semantic gap may overcome limitations on the hardware segment size by concatinating smaller segments.
These patterns provide aliasing where a page or a span of pages (segment) may appear at once at different virtual addresses i the same or different address spaces.