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)

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 247−1.
  KC (PRANGE,PRANGE_Allocate) STRUCTFROM(cda) KEYSTO(page)
  KC (PRANGE,PRANGE_Sever) KEYSFROM(page)
  KC (PRANGE,PRANGE_Identify) KEYSFROM(page) STRUCTTO(cda)
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)
  KC (SB,SB_DestroyPage) KEYSFROM(page)
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)
  KC (DC,DC_DestroyDomain) KEYSFROM(sb,domain)
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)
  KC (Node,Node_Fetch+slot) KEYSTO(x)
  KC (Node,Node_MakeMeterKey) KEYSTO(meter)
  KC (Node,Node_MakeSegmentKey) STRUCTFROM(byte) KEYSTO(segment)

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)
  KC (Domain,Domain_MakeResume)  KEYSTO(x)
  KC (Domain,Domain_PutControl) STRUCTFROM(domaindescriptor)

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)
  KC (Page,Page_WriteData+address) STRUCTFROM(data)

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)
  KC (DATAKEY,DATAKEY_ReadLarge) STRUCTTO(data)

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)
  KReturn (Returner,returncode) KEYSFROM(k1,k2,k3,Resume) STRUCTFROM(reply)

DISCRIM

Discrim is used to determine major Key types and to compare Keys.
  KC (Discrim,Discrim_Type) KEYSFROM(key) RCTO(type)
  KC (Discrim,Discrim_Compare) KEYSFROM(key1,key2) RCTO(eq)

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)
  KC (BWAIT,BWAIT_WAIT) 

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)

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)

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)
  KC (FactoryB,FactoryB_InstallComponent+n) KEYSFROM(x)
There are three classes of components: 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)
  KC (FactoryR,oc) KEYSFROM(SB,M,SB) KEYSTO(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)
  KC (CLOCK,CLOCK_ConvertTodValue) [STRUCTFROM(tod)] STRUCTTO(asciitime)

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)
  KC (WAIT,WAIT)

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)
  KC (SN,SN_Fetch) STRUCTFROM(slot) KEYSTO(x)

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)
  KC (RCol,RCol_AddNameWithKey) STRUCTFROM(nameanddata) KEYSFROM(key)
  KC (RCol,RCol_GetName) STRUCTFROM(name) STRUCTTO(nameanddata) KEYSTO(key)

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)
  KC (Domain,Domain_SwapMemory) KEYSFROM(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)

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)
  KC (SIA,SIA_Allocate) RCTO(number)
  KC (SIA,number) RCTO(rc)