The Domain/Process Creator should be merged with the space bank.


This essay argues that the Domain/Process creator and the space bank are essentially not independent and should be merged.

(Note: The syntax "A/B" refers to the concept of which A is the KeyKOS name and B is the EROS name.)
 

Design criteria.

Any design in KeyKOS/EROS that involves the kernel must be validated on three levels.

Obviously the design must meet the usual engineering criteria; it must provide a useful function, and its implementation must be efficient. That is one level, the level of the kernel implementation.

On a more abstract level, the design must meet certain criteria that ensure that the security model etc. are consistent with the design philosopy of KeyKOS/EROS. This is the theoretical level. (I'm working on writing more about this level.)

On a more practical level, the design must be extensible. It is not possible to provide all possible functionality in the kernel. The design of KeyKOS/EROS provides a means for ordinary users to extend the functionality of the system by writing their own objects that can replace the basic kernel objects. These user objects can have the same interface as the kernel objects. This is the extensible level. I will call the kernel-implemented objects "real" objects, to distinguish them from "extended" objects.

An extended space bank.

Consider how a user might extend the space bank to provide nodes with slightly different semantics from the real kernel nodes. Its specs might be as follows. When you ask for a node from this bank, it gives you a key to an object that behaves like a node when invoked to fetch or store a key in the node. But, using a transparent intermediary, it also logs all the invocations of the node. Let's call this object an extended node, and this bank an extended bank.
 

Differences between official space banks and extended space banks.

Potential clients of a space bank can determine whether or not it is an official bank. (In KeyKOS this is done by asking the official Space Bank Transformer; a design note mentions that a similar operation could be added to the space bank. In EROS this is done by an official space bank; documentation mentions that another object, the Bank Verifier, can also do this, but it does not seem to be implemented.)

Normally, it is unnecessary, and poor design, to verify that an offered key is what you expect it to be; greater flexibility and orthogonality are achieved when programs accept a key based on what it does rather than what it is. But there are three legitimate reasons for verifying a space bank: discretion, promptness, and use in domains.

Discretion.

A program will obtain nodes and pages from the bank and will store its private data into them. If the program needs to ensure that its private data remain private, it needs assurance that the nodes and pages to be obtained from the bank will be discreet. More specifically, the need arises when the program has data that it wants to keep private from the agent who supplied the space bank.

For example, suppose an object provides a compilation service using a compiler whose algorithms are secret. The client provides the program to be compiled, and provides a space bank which the compiler uses for temporary storage. Suppose the client provided the audited extended space bank described above. From the logs of what was stored in the nodes and pages, detailed information about the operation of the compiler could be obtained. To prevent this, the compilation service verifies that the proffered bank is official and therefore known to be discreet.

Promptness.

Many objects, including the factory, accept requests in a single domain/process, then create a new domain/process to service the request. This allows the single domain to accept new requests before the previous request has finished. The new domain/process is created from space provided by the client.

Most servers want assurance that the creation of space for the new domain/process is reasonably prompt, so one client can't make the service unavailable to subsequent clients. Clearly an extended bank might simply never return. To avoid this, the server verifies that the proffered bank is official and known to be prompt.

Using nodes in domains.

The Domain/Process creator has a special requirement. It can only use real nodes to build domains/processes. That is because the kernel has a mechanism for caching domain state from nodes into special kernel structures (the DIB/Process context) that allow the domain/process to execute efficiently. The kernel writes this cache back to the nodes when taking a checkpoint. Only real nodes work with this mechanism. Extended nodes can't be cached because there is no mechanism for them to inform the kernel that their contents are being changed or read. Even if such a mechanism could be invented, the fact remains that auditing all operations on the node is fundamentally incompatible with running domains/processes efficiently, since each instruction executed modifies data, such as the program counter, that is logically stored in the nodes.

Thus, the official Domain/Process Creator is fundamentally interrelated with the official space bank.

Note that this essay does not discuss any unofficial domain/process-like objects that do not enjoy special treatment by the kernel.
 

A proposal that increases extensibility.

The existing design does not maximize extensibility. The issues of discretion and promptness are fundamental issues of trust, and I do not see a way to avoid them. But the issue about using nodes in domains can be avoided. Essentially this proposal is to merge the DC/PC functionality into the space bank, making it possible to create extended domains using an extended space bank.

A space bank would have a new operation, "Create a domain/process". It would return a domain/process key to a domain/process made from space of this bank.

The "Create a domain/process" operation would take a key to be used as the "brand" of the domain. Normally a bank is obligated to not give out the same domain/process key to anyone else, but the "brand" provides an exception, as detailed below.

Another operation is "rights amplification". It takes a key to be amplified and a brand key. If the key to be amplified is a start key to a domain created out of space recognized by this bank, with a brand equal to the passed brand, then the operation returns a domain key to that domain, and the dataByte/capabilityInformation of the start key.

This operation is compatible with the theoretical foundations of KeyKOS/EROS. The space bank can in principle save a copy of each domain key it has given out. It can create all possible start keys from those domain keys. It can compare the key to be amplified with all of those keys, and if there is a match, check the brand and return the corresponding information.

I assert that rights amplification can be efficiently implemented by the real space bank, using the domain tool, which it would closely hold.

The above phrase "space recognized by this bank" is a recognition of the likely implementation(s), both real and extended (see below), and is compatible with theory if we assume that the bank can communicate with its related banks.

Similar operations provide rights amplification for return, fault, and domain keys. I need to think more about rights amplification for segments and meters whose keeper is one of the keys whose rights can be amplified.

Normally, the creator of a domain would provide as a brand a key that no one else can obtain (such as a key to a private object, or a key from the unique key creator). Otherwise, others could perform rights amplification on the domain, and it would have little privacy. But, there is no requirement that the brand be private.

Another benefit.

Making the space bank directly responsible for creating domains also enables the possibility that the bank might actually store domains differently than as a set of nodes. There could be efficiencies gained: data could be stored as data of the necessary size rather than number keys (or pages), and the possibility of strange relationships between component nodes, which requires awkward kernel code to detect and handle, could perhaps be eliminated. In fact I think Jonathan Shapiro may have proposed this once. Of course any new type of storage object would need to be made persistent by the kernel.

How extension would work under the proposal.

An extended space bank would provide extended nodes as outlined above, and in addition would need to provide extended domains. We have already said that auditing every change to a domain register is impractical, but our goal is only to provide the maximum extensibility that is practical. Here is a sketch of how extended domains could be provided.

Part of an extended domain is a real domain, which will execute at full speed except when invoking keys. An extended domain key could be a start key to an intermediary domain that implements the domain operations and also (for example) audits calls. An extended start key could be a start key to another intermediary domain that audits calls to the extended domain. Likewise an extended resume key would be a resume key to another intermediary domain. These intermediary domains can implement any desired policies. They must insert additional intermediaries in front of keys given to the extended domain, in order that an intermediary can be inserted in front of the resume keys that are produced when the domain executes call invocations.

How would rights amplification work? The intermediary domains have a brand that is private to the extended space bank. (This is necessary so the extended space bank can maintain the integrity of its illusion.) When asked to amplify rights, the extended space bank first uses its real underlying space bank to amplify rights, using the extended bank's private brand. If this succeeds, it tells the extended space bank that the proffered key is to an object recognized by this bank. Then, using internal structures, the extended space bank checks the proffered brand.
 

Similar arguments apply to Meters/SchedClasses and Segments/Address spaces.

A plain node can be used in a segment, so it can be viewed as a segment node. An extended (segment) node can be implemented using a segment with an intermediary keeper.

Meters present a problem similar to domains. Since EROS SchedClasses don't use space from a bank, this discussion applies to KeyKOS; it may apply to a future EROS design.

In the current design, it is possible to allocate a node from a space bank, use that node as a segment node in the address space of a process, create a meter key from the node, and simultaneously use the meter in the process. The kernel, let alone an extended space bank, doesn't support this properly. (The node can't be simultaneously prepared as a segment and a meter, so the process will make no progress.)

Here again the solution is to define a new type of object supported by the space bank, a meter object. The space bank would support a new operation to allocate a meter object and return a strong key to it, capable of controlling the meter. From the strong key one could create a meter key that can be used to run. The NODE_MAKE_METER_KEY operation on a KeyKOS node key would be eliminated. Again, extension is by means of an intermediary keeper.

The kernel could associate the type of a node (segment, meter, or domain component) with the node, because a given node could have only one type. This might simplify some delicate kernel logic that checks for nodes with multiple roles.
 

Practical effect.

As a practical matter, extended space banks will still have very limited usefulness. (None has ever been written.) The distinction between official and non-official space banks is still needed. The factory and most servers will still require an official bank because they require promptness.

Nevertheless, this proposal is important because it eliminates two unnecessary object types (the DC/PC and DCC/PCC), merges objects that have no theoretical or practical reason to be separate, and enables more efficient storage of domains/processes.

Copyright 2000 Charles Landau