CapROS Address Spaces

Description

This page is still under construction.

An address space provides a mapping from offsets to pages. Address spaces are the mechanism of data organization and access in the EROS system. Address spaces are constructed as a tree of nodes whose leaves are pages.

To understand virtual address translation, it is useful to think of an address as made up of a virtual page address and a page offset:

+----------------------+-------------+
| Virtual Page Address | Page Offset |
+----------------------+-------------+
	  

Both the size of the page offset portion of the address and the size of the complete virtual address are dictated by the underlying hardware.

When a program references a memory address, the virtual page address is interpreted by traversing the address space tree until the appropriate page is found. The page offset is then used to reference the appropriate object (byte, halfword, word, etc.) within the page.

Address spaces are fabricated by the Make Address Space Key order on the Node key.

An address space key conveys the authority to read and write the content of the address space. Write access can be prohibited by creating an address space key with the read only attribute.

Address spaces come in two varieties: black address spaces and red address spaces:

Black Address Spaces	A black address space contains up to 32 subaddress spaces, and act as the basic building blocks of an address space tree. Black address spaces are non-callable address spaces.
Red Address Spaces	Red address spaces serve to provide complex structuring and fault handling for address spaces by specifying keepers and background address spaces, and other complexities. An address space key that names a red address space with a keeper is callable unless the don't call attribute of the address space key is set.

As with nodes, address spaces may carry read-only, no-call, and weak access restrictions. Information on the read-only, no-call, and weak attributes can be found on the Node page.

Every access to an address space has an associated responsible keeper who will be notified in the event of an access fault. The responsible keeper is determined by walking the address space from the root to the leaves to locate the most enclosing callable keeper. The search terminates when a page is reached or a "don't call" address space key is encountered. No keeper defined within the structure of a don't call address space will be invoked by any access to that address space. If no other keeper can be found, access faults are reported to the process keeper.

Callable address spaces are red address spaces whose NC bit is 0 (permitting calls) and which identify an address space keeper. Invocations on a callable address space key are reflected to the associated keeper. Callable address spaces therefore respond to any protocol defined by their address space keeper.

All other address spaces respond only to the Check Alleged Key Type and Make Read Only operations. By convention, address space keepers are expected to respond to the Check Alleged Key Type and Make Read Only requests in a fashion that is consistent with the specification on this page; thus, these requests may be used on any address space.

Red Address Spaces

The contents of a red address space Node are interpreted according to the format key that is found in slot RedSegFormat (31). The format key is a number key whose content is as follows:

Field (Bits)	Interpretation
[0:4]	Number of initial slots (I). Describes how many of the keys in this Node should be considered valid for purposes of address space traversal. More precisely, slots in the range [0:I) will be traversed according to the usual address space traversal rules. Slots whose number is >= I will be assumed to hold void keys for purposes of ordinary traversal. This reserves these slots for use as the background key or keeper key.
[5:9]	Invocation convention. If an invocation is made on a kept address space key, the invocation is reflected to the keeper. The value of this field determines what will be passed to the keeper in the third key slot of the message: 0 A Node key to this Node will be passed as the third argument to the keeper. 1 The third argument provided by the caller will be passed unaltered other The address space is malformed.
[10:14]	Slot number of the address space keeper key. (K). If K is not equal to RedSegFormat (31), the key in slot K is a start key to the keeper for this address space.
[15:19]	Slot number of the background key. (B). If B is not equal to RedSegFormat (31), the key in slot B is an address space key to the background address space for this address space. Background address spaces are described in greater detail below.
[20:31]	Biased log address space size. The blss value of a red address space resides in the format key. This value must be greater than zero (the blss of a page), otherwise the address space is malformed.
other	All other bits of the format key are reserved for future use, and should be zero.

If the format key is not a number key, the address space is malformed, and a suitable message will be send to the responsible keeper when the address space is accessed.

PROPOSED Red Address Spaces

The problem with the existing red address space design is that it will not go to 32 slot nodes gracefully. The following describes the proposed design, which is in the process of being implemented.

The contents of a red address space Node are interpreted according to a combination of predefined slot meanings and value of the format key that is found in slot 15.

Every red address space has some number of initial slots (I) that are considered vaild for purposes of address space traversal. More precisely, slots in the range [0:I) will be traversed according to the usual address space traversal rules. Traversals that pass through slots whose number is >= I will cause invalid address exceptions.

Every red address space also has some number of reserved slots that are designated by the EROS architecture for particular purposes:

Slot	Future Slot	Use
15	31	Format Key. A number key describing various attributes of the red address space. The content of the format key is as follows: Field (Bits) Interpretation [0:7] Number of initial slots (I). [8:15] Index of first reserved slot (R). A slot is interpreted as reserved only if its index is >= R. This permits the architecture to be extended by further reserved slots in the future without breaking compatibility. [16:30] Biased log address space size. The blss value of a red address space resides in the format key. [31] Invocation convention. If an invocation is made on a kept address space key, the invocation is reflected to the keeper. The value of this field determines what will be passed to the keeper in the third key slot of the message: 0 A Node key to this Node will be passed as the third argument to the keeper. 1 The third argument provided by the caller will be passed unaltered. other All other bits of the format key are reserved for future use, and should be zero. If the format key is not a number key, the address space is malformed, and a suitable message will be sent to the responsible keeper when the address space is accessed.
14	30	Keeper Key. A start or resume key naming the keeper of this address space. If the key in this slot is a void key, no keeper is defined by this red address space. If the key in this slot is neither a void key nor a gate key, the behavior is currently undefined, but such a red address may in the future be considered malformed.
13	29	Background Key. The key in slot 13 is an address space key to the background address space for this address space. Background address spaces are described in greater detail below. If the key in this slot is a void key, no background space is defined by this red address space. If the key in this slot is neither a void key nor a suitable memory key, the behavior is currently undefined, but such a red address may in the future be considered malformed.
12	28	Working Set Key. The working set into which pages and nodes from this subsegment should be loaded. If the key in this slot is a void key, no working set is defined by this red address space. If the key in this slot is neither a void key nor a working set key, the behavior is currently undefined, but such a red address may in the future be considered malformed.

To be interpreted as a reserved slot, the value of R must be at least the value of the slot number. If R < I, the segment is malformed. If the format key is not a number key, or if the value of R does not indicate that the number key slot is reserved, the address space is malformed, and a suitable message will be send to the responsible keeper when the address space is accessed.

Because address space and node capabilities encode the size of their subspace, the algorithm for traversing the address space tree is slightly more complicated than the comparable hardware mechanism on most processors.

Address Translation

Translation of an address begins by examining the key in the address space slot of the process. In traversing an address space, a sequence of keys is examined in turn. The action taken depends on:

1. The type of the key,

2. The size of the address space named by that key,

3. The current offset relative to the start of the segment named by that key.

Sizes are measured in terms of log space size. To compute the log space size of a subspace, first determine how many pages that subspace holds. The log space size is then ciel(log_ndsz(npages)), where ndsz is the number of slots in a node. Thus, on a 32-bit address machine with 4096 byte pages and 32 slot nodes, the lss values usually associated with address translation are as follows:

Copyright 1998, 2001 by Jonathan Shapiro. Copyright 2005, 2006 by Strawberry Development Group. All rights reserved. For terms of redistribution, see the GNU General Public License