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:

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:

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.


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.