Description of the KeyTECH Programming Interface

The programming interface consists of Keys. A description of these Keys, the functions they provide, and the mechanism for invoking keys to send messages completely describes the programming interface. Some of the Keys are implemented by the Microkernel and others are implemented by objects outside the Microkernel.

The invocations described here are a subset of the invocations possible. A complete description of the invocations is available in KeyKOS Object Reference (KL230), also known as the KOR.

The key invocation description used here is the C language macro form. Kathena Technology supplies a preprocessor which interprets these macros and generates function calls to a Kathena Technology supplied library routine to invoke keys. Keys are specified by a name which has been “defined” as a number using a “KEY” declaration understood by the Kathena preprocessor. The Key name refers to one of the 16 key registers available to the domain.

  KC (Key,Order_code) STRUCTFROM(arg_structure)
  KEYSFROM(arg_key_slots) STRUCTTO(reply_structure)
  KEYSTO(reply_key_slots) RCTO(return_code)

Key - specifies the register number of the key to be called

Order_code - the numeric ordercode

STRUCTFROM - specifies the data included in the message

KEYSFROM - specifies the key registers (up to 3) from which keys are copied into the message

STRUCTO - specifies the structure to receive the data from the reply message

KEYSTO - specifies the key registers to receive the keys from the reply message

RCTO - specifies the variable to receive the return code.

NRANGE, PRANGE, and Spacebanks

These Keys are Microkernel Keys that allocate Page keys and Node keys. Each Node or Page in the system is known to the RANGE keys by its CDA (coded disk address), which is a number in the range 0 - MAXCDA. The current implementation sets MAXCDA to 2⁴⁷−1.

  KC (PRANGE,PRANGE_Allocate) STRUCTFROM(cda) KEYSTO(page)

This invocation of the PRANGE Key returns a Page key to the Page designated by the offered CDA. Each time this Key invocation is made with the same CDA value, the same Page key is returned.

  KC (PRANGE,PRANGE_Sever) KEYSFROM(page)

This invocation invalidates all copies of the Page key offered.

  KC (PRANGE,PRANGE_Identify) KEYSFROM(page) STRUCTTO(cda)

This invocation allows the holder of the PRANGE key to identify the CDA of a page key. The same invocations apply to the NRANGE key, which allocates and de-allocates Node keys.

Some ranges may be n-plexed. If this is so, the Microkernel will update all copies when the Page or Node is written to the disk and will choose the “best” copy to read when the Page or Node must be brought into memory.

Clearly the NRANGE and PRANGE keys do not enforce any allocation strategy and would allow several domains to allocate the same page. For this reason there is an Object called the Spacebank which holds the RANGE keys and enforces allocation strategies.

  KC (SB,SB_CreatePage) KEYSTO(page)

Allocates a Page key and guarantees that there are no other copies of this Page key. The Spacebank may allocate pages sequentially on the disk or may scatter the pages across several disks depending on the strategy programmed into the Object.

  KC (SB,SB_DestroyPage) KEYSFROM(page)

Frees the page and invalidates all copies of the Page key. There are other calls on the Range keys and Spacebank Object that are not required for understanding of the basic programming environment.

A Spacebank key is required to create any new Object. A Domain that does not have a Spacebank key cannot cause the allocation of any disk resources though it may call other Objects that do have a Spacebank key. There can be several Spacebanks with differing allocation strategies using the same RANGE keys so long as they do not allocate the same CDAs. Some spacebanks may attempt to distribute the allocation of space over a wide range of CDAs in order to increase I/O performance (striping). Throughout the rest of the description of the programming environment it is often assumed that a Spacebank key is available.

DOMAINTOOL and DOMCRE

The DOMAINTOOL key is a Microkernel implemented Key that creates a Domain from three nodes. The Domain Creator Object is the only Object that holds this Key and is, therefore, the only Object that knows the structure of a Domain. The structure of a Domain may change on some hardware implementations and only the Domain Creator needs to know the new structure.

The Domain Creator is passed a Spacebank key and returns a Domain key. The current Domain Creator allocates three nodes from the Spacebank, links them together properly, invokes the Domain tool key to create a Domain key, and returns that key to the caller.

  KC (DC,DC_CreateDomain) KEYSFROM(sb) KEYSTO(domain)

Allocates the necessary resources from the offered Spacebank and creates a Domain. Returns the Domain Key.

  KC (DC,DC_DestroyDomain) KEYSFROM(sb,domain)

Destroys the domain and returns the resources to the offered Spacebank. Each Domain Creator in the system brands the Domains it creates so that issues of “ownership” can be resolved in an orderly fashion. There are calls on the Domain Creator to identify the products of the Domain Creator. These calls fall under the category of rights amplification and are important in specifications of the security properties of KeyTECH.

NODE

Nodes are storage objects for sixteen Keys. Many Nodes are used by applications to store Keys that are only used occasionally by the Domain. A Domain has sixteen Key Registers which can be used in any Key invocation. If the Domain needs to manipulate more than sixteen Keys, it will use a Node or Nodes to store the extra Keys.

Nodes are also used to describe higher level Objects. As we have seen, a Domain is described by the Keys stored in three Nodes. A Segment is described by a tree of Nodes that store Page Keys at the leaves of the tree. A Node is also used as a Meter. Each of these Objects is represented by a particular type of Key to a Node. A Domain key is a Key to the root Node of a Domain. A Segment key is a Key to the root Node of the segment tree. A Meter key is a Key to the meter node.

There are two basic classes of invocations of Node Keys. The most common are the invocations that store and retrieve a Key from one of the sixteen slots of the Node. The other class of invocations creates the other node key types, such as Segment and Meter. Note that there is no invocation of the Node key to create a Domain key. This may only be done through the use of a Domaintool key.

There are two reasons why there is a Domaintool key and a Domain Creator instead of a call on a Node to create a Domain key. First, the structure of a Domain is likely to change from implementation to implementation. For some hardware architectures, a Domain may be represented by four nodes; in others, by two nodes and a page. It is important to hide this architectural difference from the designer of software for a KeyTECH system. Once the Domain structure is hidden, it is necessary to separate the authority to create Domains from the Node key so that a Node key cannot be used to create a Domain.

Second, in a system with security as a fundamental design, it seems appropriate to make the assumption that security is desired. The Domain Creator applies a brand to a Domain while another holder of the Domaintool key may not. If Domains are not branded, there are limitations on the possible security policies that can be implemented.

Now one might ask why the preceding argument does not apply to Segments and Meters (that there are no Segmenttool or Metertool keys). The short answer is that it could. However, it was not thought necessary to hide the Segment and Meter structures as it is unlikely that they will change. There are alternate implementations that might have the regularity of a tool key for each of the Primary Objects (Domain, Segment, Meter) and a creator Object that uses the took key to create each of these objects, but these implementations seem to lead to non-regularities somewhere else.

  KC (Node,Node_Swap+slot) KEYSFROM(x) KEYSTO(x)

Swap is a useful atomic operation and can be used as a store operation if one simply does not specify KEYSTO(). “Slot” is a number from 0 to 15.

  KC (Node,Node_Fetch+slot) KEYSTO(x)

“Slot” is a number from 0 to 15.

  KC (Node,Node_MakeMeterKey) KEYSTO(meter)

A new Key to the Node is generated and returned. The Node key is still used if one wants to alter the contents of the Node. The Meter Key cannot be used to change the keys in the Meter. The Meter key is installed in a Domain to allow the Domain to run.

  KC (Node,Node_MakeSegmentKey) STRUCTFROM(byte) KEYSTO(segment)

The contents of “byte” is used to describe the characteristics of the resulting Segment key (such as Read-Only, or with or without a Keeper).

DOMAIN

There are several types of Key that designate an Object. Each of these Keys is simply a different type of Key to the root Node of the Domain. The first Key designating a Domain that ever exists is the Domain key. The Domain key is returned by the Domain Creator.

A Domain is in one of three states: Available, Waiting, or Busy.

Available: In this state a Domain may receive a message via any of the Keys that designate the Domain, regardless of the key type.
Waiting: The Domain has invoked a Key and is waiting for the reply. The only Key that can be used to send a message to the Domain is a Resume key. All other Keys that designate the Domain will stall.
Busy: The Domain is computing. No Resume keys exist for this Domain. Any invocation of any Start key designating this Domain will stall. The Microkernel will cause the invoker to retry the invocation when the Domain becomes Available.

There are three basic Keys that designate a Domain: Domain, Start, Resume.

Domain: This Key can only be used to alter the state or description of the Domain. This Key cannot be used to send a message to the program running in the Domain.
Start: This is a permanent Key that designates the Domain. The only way this Key can become invalid is for the Domain to be destroyed. An invocation of this Key will send a message only if the invoked Domain is Available. If the invoked Domain is Busy or Waiting the invocation stalls until the Domain is Available.
Resume: This Key exists only when the Domain is Waiting. As soon as the Key is used to send a reply message to the Waiting Domain, all copies of this Key become Data keys with the value zero.

There are three forms of Resume key.

Fault-Resume key: The Key that a Segment Keeper receives. It allows the Keeper to restart the Domain without passing any parameters but does allow a return code. A non-zero return code becomes the trap code to the Domain Keeper.
Restart-Resume key: The Key a Domain Keeper and Meter Keeper receive. It allows only a restart without parameters or a return code.
Return-Resume key: The fourth Key passed as the result of a CALL instruction. The invoker of a Return-Resume (often referred to as Resume key) may pass both parameters and a return code.

There are three ways to invoke a Key: Call, Fork, Return. The invokee has no way of knowing which of the three ways the Key was invoked.

Call: This invocation usually is used with Start keys though it may be used with Resume keys as well. The invoking Domain is put into the Waiting state and a Resume key to the invoking Domain is put into the fourth slot of the message.
Return: This invocation usually is used with Resume keys to send replies to messages. A Return invocation may, however, be used with any Key and puts the invoking domain into the Available state.
Fork: This invocation leaves the invoking Domain in the Busy state and continues computing without waiting for a reply. No Resume key is put into the fourth slot of the message so the invoker may pass four keys using a Fork instruction.

Calls on the Domain key are used to change its state.

  KC (Domain,Domain_MakeStart) STRUCTFROM(databyte) KEYSTO(x)

There are 256 different Start keys to a domain. The databyte value is part of the Start key and is presented to the Domain when the Start key is used to send a message to the Domain. This mechanism allows the designer to partition authority and determine the authority of the caller. It would be possible to accomplish the same effect by partitioning the order code used on the invocation of the Start key but doing so would imply trusting the caller to behave correctly. Use of the databyte allows an unambiguous method for distributing partitioned authority to untrusted invokers.

The databyte mechanism is used widely. A single domain may behave as several objects that share common data by using different databytes for each “object”. The major difference between this mechanism and actually having separate objects is the avoidance of shared memory interlocks. The disadvantage is of course that the different “objects” may have undesired interactions.

  KC (Domain,Domain_MakeResume)  KEYSTO(x)

Make a Resume key to the Domain. The Domain’s state is changed to Waiting. If the domain was Busy at the time, the process in the Domain is lost. The invoker of this Key with this order code is responsible for recovering the lost process (presumably by using the Resume key in the Domain’s Keys Registers).

  KC (Domain,Domain_PutControl) STRUCTFROM(domaindescriptor)

Alter the starting address of the Domain. This invocation is architecturally dependent.

PAGE

Pages are storage objects for data. A Page key is a Segment key. Page keys are stored in Nodes to build larger Segments. The holder of a Page key can also send data to the Page for storage. At this time there is no invocation of a Page key to retrieve stored data from the Page.

  KC (Page,Page_MakeReadOnly) KEYSTO(page)

Makes a read only version of the Page key.

  KC (Page,Page_WriteData+address) STRUCTFROM(data)

Stores data at the specified address within the page.

DATA/DATAKEYCREATOR

Data keys are Keys to immutable data objects. Because the data object is immutable, there is in fact no Object to represent the data. The data is actually part of the Key. There are two types of Data keys, large (88 bits at this time) and small (48 bits) and Key to create new Data keys.

  KC (DKC,DKC_MakeLargeKey) STRUCTFROM(data) KEYSTO(datakey)

Make a large Data key (88 bits) from the offered data.

  KC (DATAKEY,DATAKEY_ReadLarge) STRUCTTO(data)

Read a large Datakey into the designated structure.

DEVICEIO

DEVICEIO keys are very machine specific. Even within a particular machine there may be several types of I/O devices. Most modern workstations use memory mapped I/O in which the device control registers appear at special addresses. Even with this style of I/O the DEVICEIO key serves an important function.

A DEVICEIO key may allow the reading and writing of single characters to a UART, may specify a complete SCSI operation for a particular unit, or may simply wait for an interrupt from a memory mapped I/O device.

  KC(DeviceKey,Operation) STRUCTFROM(description) KEYSFROM(memory)

RETURNER

Returner is a Key that never stalls. An invocation of Returner always completes promptly. The Returner key is used to move keys from some Key Registers to other Key Registers and to allow a public server to return safely at the end of providing a service. The latter function is implemented by RETURNing to the Returner key passing the alleged Return key to the caller in the fourth slot of the message. If the fourth slot is not a Resume key, then the invocation of the Returner completes (the Domain becomes available) but the fourth Key is treated as a Data key with the value 0 (A zero Data key).

  KC (Returner,number) KEYSFROM(k1,k2,k3,k4) KEYSTO(k1,k2,k3,k4)

Move Keys from slot to slot.

  KReturn (Returner,returncode) KEYSFROM(k1,k2,k3,Resume) STRUCTFROM(reply)

Reply promptly.

DISCRIM

Discrim is used to determine major Key types and to compare Keys.

  KC (Discrim,Discrim_Type) KEYSFROM(key) RCTO(type)

Return the Key type.

  KC (Discrim,Discrim_Compare) KEYSFROM(key1,key2) RCTO(eq)

Compare keys for equality.

BWAIT

There are a small number of BWAIT objects available. These Objects are implemented in the kernel and provide the basis for supporting a large number of WAIT objects outside the kernel. A BWAIT object delays the invoker until the time specified by the invoker arrives. Only one invoker may wait at a time. A wait multiplexer uses a single BWAIT object to provide a large number of WAIT objects.

  KC (BWAIT,BWAIT_SetTOD) STRUCTFROM(tod)

Set the wake up time of the BWAIT object. The units of “tod” is 1/4096 microseconds since January 1, 1900. The precision of the wait interval depends on the precision of the hardware timer interrupt.

  KC (BWAIT,BWAIT_WAIT)

Delay until preset time arrives.

BWAIT

The CHECKPOINT key is used any time that the holder wishes to take a checkpoint. Doing this at a high rate can degrade the system performance, so this Key is often only given to applications that need it. A transaction application would need to force a checkpoint when its journal log started to overflow.

The Checkpoint Driver object invokes the CHECKPOINT key at preset intervals.

  KC (CHECKPOINT,CHECKPOINT_TakeCheckpoint) STRUCTFROM(tod)

Return when all state before time “tod” has been checkpointed. If “tod” is in the future, return is immediate. The “tod” value is in units of 1/4096 microseconds since January 1 1900.

SYSTIME/CALTIME

The KeyTECH Microkernel keeps a System time value that is guaranteed to continually advance no matter what happens to the hardware clock. The SYSTIME key returns the current System time. The CALTIME key returns the value represented in the hardware calendar clock.

The CALTIME return value is often not as precise as the SYSTIME return value. Many workstations use an alarm clock chip with 1 second precision for the calendar time. The SYSTIME value is as precise as the fastest hardware timer interrupt. High precision calendar times must combine the SYSTIME and CALTIME values. Specifically at an IPL of KeyTECH, the SYSTIME and CALTIME values are compared and an offset is generated for the SYSTIME value. Any time after an IPL (until the next IPL) the offset is added to the SYSTIME value to obtain a high precision calendar time. The CLOCK object performs this and other functions.

  KC (SYSTIME,SYSTIME_ReadTOD) STRUCTTO(tod)

Read the current SYSTIME value. The “tod” value returned is in the same format and units as the “tod” values for BWAIT. At this time the “tod” value is a 64 bit number which counts 1/4096 microseconds since January 1, 1900. The precision of the SYSTIME value depends on the hardware.

FACTORYC/FACTORY

The creation and use of a Factory has two major motivations.

First, new Objects are created quite frequently in a KeyTECH system. While straightforward, the construction of a new object using the Spacebank, Domain Creator, Node, and Page keys is at best tedious, particularly when done repeatedly. A Factory is an Object that produces instances of a new Object at each invocation. Thus a Factory makes the definition of a new Object easier and makes instantiation of this new Object trivial.

Second, the Factory produces Objects with predetermined and testable communication paths. It is possible to test a Factory to determine the nature of the Keys it holds (for use in the construction of the new Object) with respect to the ability of those Keys to communicate with other Objects in the KeyTECH system. It is this Factory technology that is at the heart of the security policy enforcement mechanism.

A Factory Creator is used to produce a new nascent Factory. The Factory is then tailored to produce a particular new Object by repeated invocations of the Factory Builder key. The final invocation of the Factory Builder key seals the Factory and produces a Factory Requestor key. The Factory Requestor key is invoked to produce an instance of the new Object.

  KC (FC,FC_Create) KEYSFROM(Spacebank) KEYSTO(FactoryB)

Create a new nascent factory. This new Factory is not capable of producing Objects. The FactoryB key is used to describe the factory product.

  KC (FactoryB,FactoryB_InstallComponent+n) KEYSFROM(x)

There are nineteen (19) components. Sixteen (16) of the components are available to the factory product in a components Node. The remaining three (3) components describe the “program” Segment, the Keeper, and the “symbol” Segment (used by the Keeper for debugging). There are three classes of components:

Sensory—this class of keys is guaranteed not to accept messages,
Factory Requestor keys,
Unvouched for keys (“holes”).

The rules covering the significance and installation of these three classes of Keys can be found in the KeyKOS Object Reference(KL230).

  KC (FactoryB,FactoryB_MakeRequestor) KEYSTO(FactoryR)

The Factory is “sealed”. A sealed factory cannot be altered in any way that would add an unvouched for Key (hole). The FactoryR key may now be used to create instances of the factory product.

  KC (FactoryR,oc) KEYSFROM(SB,M,SB) KEYSTO(object)

An instance of the factory product is created from the space provided by the invoker. The Key “object” is usually a Start key to some Domain. Often the factory product is a single Domain. When returned by the FactoryR invocation, there are no copies of the Key “object”.

CLOCKF/CLOCK

The CLOCK Factory produces Clock objects. Each Clock object may have a different time zone offset. Separate Clock objects are also necessary for limiting the exchange of information through covert channels.

Clock objects are responsible for providing the highest precision calendar time that is possible in addition to being able to convert TOD values to ASCII.

  KC (CLOCK,CLOCK_ReadTOD) STRUCTTO(tod)

This invocation reads the current TOD value from the “system clock”. The CLOCK object combines information from CALTIME and SYSTIME keys to obtain the most precise TOD value available. The TOD value is in 1/4096 microseconds since January 1, 1900.

  KC (CLOCK,CLOCK_ConvertTodValue) [STRUCTFROM(tod)] STRUCTTO(asciitime)

If a TOD value is not supplied, then the “system clock” is used as the base for the time conversion. The string MM/DD/YYHH:MM:SS.HHHZZZwwwwwwwww is returned representing the printable version of the date and time.

WAITF/WAIT

The WAITF Factory produces instances of WAIT objects. WAIT objects behave like BWAIT objects. Unlike BWAIT objects, there can be many WAIT objects instead of just a few.

  KC (WAIT,WAIT_SetTOD) STRUCTFROM(tod)

Set the WAIT object’s wake up time. The offered time is in TOD units.

  KC (WAIT,WAIT)

Delay until the wake up time. This delay includes any time that the system is not running because the power is turned off (wall clock time). If the wake up time passes while the power is turned off, the invocation will return immediately when the power is turned on.

SNF/SN

It is quite common to want to store a large number of Keys. While one could arrange to do this using a tree or chain of Nodes, the SuperNode object implements this function. A SuperNode uses a 32 bit number to name the Key slot. The 32 bit slot number is passed as the data portion of the message.

  KC (SN,SN_Swap) STRUCTFROM(slot) KEYSFROM(x) KEYSTO(y)

As in Node_Swap except that the “slot” value is a 32 bit integer.

  KC (SN,SN_Fetch) STRUCTFROM(slot) KEYSTO(x)

As in Node_Fetch except that the “slot” value is a 32 bit integer.

RCOLF/RCOL

A Record Collection is an Object that stores named records consisting of data and a Key. Each record can have a 256 byte name, 4057 bytes of data (the name is part of the data), and 1 key. Records can be added, updated, deleted and read. Record Collections make handy directories of named Keys.

  KC (RColF,RColF_Create+type) KEYSFROM(sb,m,sb) KEYSTO(RCol)

Create a Record Collection. RCol is either a Named Sequence Record Collection or an Entry Sequenced Record Collection.

  KC (RCol,RCol_AddNameWithKey) STRUCTFROM(nameanddata) KEYSFROM(key)

A record is added to the collection. The record consists of a name, some data, and a Key. The name is the first part of the data and both the name and the data are of variable length.

  KC (RCol,RCol_GetName) STRUCTFROM(name) STRUCTTO(nameanddata) KEYSTO(key)

A record is read from the collection. Only the name is supplied but the return message contains the name, data, and key portions of the record.

FSF/FS

Segments may have Keepers. The Keeper of a Segment is responsible for implementing the appropriate policy for handling Segment Faults. The Fresh Segment Keeper’s policy is to provide a zero read/write page any time that a reference is made to a non-existent page. This form of memory allocation is appropriate for sequential files, the memory of a Domain (assuming that the Domain’s program is read into the Segment), and dynamically allocated memory structures.

  KC (FSF,FSF_Create) KEYSFROM(sb,m,sb) KEYSTO(segment)

A new empty Fresh Segment is created. This segment can by used to store data for a file or serve as the memory of a Domain. The only way that data is written into or read from the Segment is if the Segment is part of the memory of a Domain. The Segment can be a sub-Segment of a larger Segment.

  KC (Domain,Domain_SwapMemory) KEYSFROM(segment)

In this simple case the Segment is made the entire address space of a Domain. In order for this operation to be useful, the Segment must have previously been a sub-Segment of some loader function that wrote the Domain’s program into the Segment.

FORKF/FORK

The Microkernel does not queue messages. However, the logic of some operations requires that the sender of a message continue running even if the receiver of the message is busy. The most obvious case where this is important is when the receiver might be sending the sender a message. This situation is occasionally unavoidable and must be handled by some form of queue of messages.

The FORK object is a small object that holds a message for delivery. The sender of the message creates a FORK object by calling the FORKF factory. It then uses the FORK instruction to send a Key and a message for delivery to the FORK object. The FORK object attempts to deliver the message to the offered Key on behalf of the original sender. It may stall, but the original sender of the message proceeds. The Microkernel is queuing the sender of the message while the sender holds the actual message.

  KFORK (FORK,oc) KEYSFROM(k1,k2,receiver,return) STRUCTFROM(data) STRUCTTO(data) KEYSTO(k1,k2,k3,k4)

The FORK object is sent a message via a FORK instruction. The sender of the message continues to run while the FORK object attempts to deliver the message. In this case the receiver of the message is designated by one of the Keys in the message to the FORK object. Likewise the message reply is sent to the fourth Key included in the message to the FORK object.

SIAF/SIA

A Small Integer Allocator is an Object that allocates and de-allocates small (32 bit) numbers. These numbers are useful for the allocation of slots in a Supernode, the allocation of memory with fixed block sizes, and any other application that requires a tag to uniquely identify a small number of Objects.

  KC (SIAF,SIAF_Create) KEYSFROM(sb,m,sb) KEYSTO(SIA)

Create an SIA.

  KC (SIA,SIA_Allocate) RCTO(number)

Allocate a small number.

  KC (SIA,number) RCTO(rc)

De-allocate a small number