Rescindable and Redirectable Capabilities

It is frequently necessary to offer some capability on a temporary basis.
If there is a real-time stock data base we may wish to sell access to it by the month. We may wish to sell access to a particular program on a monthly basis.

There is no single way to derive a rescindable form of a capability from a given one but there are easy ways to handle each case.
Given a segment key S one may put S into slot 0 of a new node T that is formatted as a segment node and pass a segment key to T. A node key to T may now serve to rescind access to S.

The rescindable version of a gate is provided merely by building a front end to the program that passes the parameters thru to the real node. Deleting the front end rescinds access to the program. If the program already has a front end, that front end can serve as the domain to be deleted.

The issue arises of synchronous revocation. If I operate a data base to which customers have access via start keys, it may be necessary to ensure that data placed in the data after revocation will not be delevered, even if some domain, invoked by the customer is running at the instant of the revocation. This may be accomplished by the front end keeping the customers resume key and calling the back end itself. The back end (the real data base) will hold a resume key to the front end and upon revocation the front end will either disappear or test for revocation and in either case information derived from the changes subsequent to revocation will not be returned to the customer.

A more parsimonious way to build a rescindable version of a gate is to use red segment node with a keeper {see (p2,segjump)}. Note that the rescindable version is not a gate, so you can't cascade these.
{arcane}That's too bad. It would be nice to fix this, but see (p1,segkeepkeynote).

To provide a rescindable version of a node {not used as a memory key}, merely provide a start key to a domain that owns the node and answers the calls as the node would.

In all these cases it is just as easy to redirect the access to a different object as it is to totally rescind access.

Mutual Exclusion (Semaphores)
When two or more domains are sharing data or keys, and there is a possibility that more than one domain could be running at once, there often arises a need for a "critical region" of code such that it can be guaranteed that at most one domain is executing in a critical region at a time. (For a more complete discussion, see for example "Cooperating Sequential Processes" by E. W. Dijkstra, in Programming Languages, F. Genuys, editor, Academic Press 1968.)

We give here several mechanisms for implementing this mutual exclusion. These mechanisms are not semaphores but they fulfill the most common application for semaphores. See also {(p2,semaphore)} for an impure Gnosis technique that may be useful in converting programs designed for other environments.

Isolate critical regions
This method is the most natural one to use when one can afford the overhead of a gate jump on entering and leaving a critical region. The need for a critical region arises because some shared information structure is being manipulated. The method is simply to have a domain which is in charge of that structure. All manipulations are done by calling a start key to the domain and telling it what to do.

Since there can be only one process in a domain, the Gnosis kernel ensures the mutual exclusion.

Restricted Semaphore
This method uses a domain which behaves like a semaphore that never takes on a value greater than 1. It could be useful in cases where one can afford two gate jumps on entering and leaving a critical region, but the method above is unsatisfactory (for example because the operation to be performed is too highly parameterized to permit breaking it out into a separate domain).

The domain executes the following Assembler code (see (p3,asmintf)):]
LABEL SLR 1,1]
LOADEXBL 0]
LOADENBL R1,,,,,0]
RETJUMP Here while unlocked]
SLR 1,1]
KEYCALL 0,,R1,(,,,0) Here while locked] B LABEL]
The domain is initialized by putting DK(0) in its general key slot 0 and starting it at LABEL. The domain will make itself available.

The critical region is implemented as follows. ENTRY is a slot containing a start key to the domain. EXIT is some other key slot.]
KEYCALL ENTRY,,,(,,,EXIT)]
critical region]
KEYCALL EXIT]
LOOSE END Give PL/I version.

Optimized Restricted Semaphore
This method has little to recommend it over the method in (p3,fastsema), except that it could be considered more elegant because it does not use a domain key, only gate keys. It is included here to illustrate the similarity between the methods in (p3,restsema) and (p3,fastsema).

There is a domain which executes the same code as in (p3,restsema), but initially the domain is busy, its PSW points to LABEL, and there is a return key to it in some key slot which is shared by all domains which have a critical region. There is a word variable SEMACTR in shared memory, initialized to -1. The critical region is implemented as follows.

L 1,SEMACTR increment SEMACTR] LAB1 LA 0,1(1)]
CS 1,0,SEMACTR]
BC 4,LAB1]
LTR 0,0]
BZ LAB2 got in without waiting] KEYCALL ENTRY,,,(,,,EXIT)]
move EXIT to shared slot]
LAB2 critical region]
L 1,SEMACTR decrement SEMACTR] LAB3 LR 0,1]
BCTR 0,0]
CS 1,0,SEMACTR]
BC 4,LAB3]
LTR 0,0]
BM LAB4 don't need to wake anyone up] get EXIT from shared slot]
KEYCALL EXIT]
LAB4 EQU *

Fastest method
This is the method of choice when one cannot afford a gate jump at a critical region. The method is the same as that in (p3,optsema) except for the following. There is no shared key slot. The domain executes the following code:
LABEL KEYCALL 0,,R1,(,,,0)]
B LABEL]
It is initialized as follows:]
Busy]
FR2 = X'0000081000000000' (LOADENBL R1,,,,,0)

The first KEYCALL in (p3,optsema) need not accept EXIT; it does accept a return code. The second KEYCALL is replaced by:] LA 1,65 make domain available]
KEYCALL DOMAIN,,R1 this will put 1 in R1] DOMAIN is a slot containing a domain key to the domain.

We describe here a technique that can be used to implement the common sleep/wakeup synchronization primitives. It is usually not applicable to domains whose function is to service a start key. We assume that the domain that sleeps never enters the available state, except as described here.

To sleep, a domain executes a return jump to a data key. This makes the domain available.

To wake up a domain, execute a fork jump to a start key designating the domain to be awakened. This will cause the sleeping domain to continue execution after its return jump. The fork jump can pass parameters to the sleeping domain.

Note that the result of a sleep and a wakeup is the same regardless of the order in which they are executed.

{arcane}{nonref}Note also that the technique can be used regardless of whether jump packets are implemented {(p1,stall)}. If a fork jump to a start key can stall, the wakeup operation may stall until the domain to be awakened sleeps (becomes available). By using shared variables, it can be arranged that the wakeup operation stall for a short time at most.

Forks and Joins

A common way of expressing parallelism is to say that at some point F in a program two parts (P1 & P2) of the program can proceed and after those two parts are done some other part J can proceed.

Our policy in Gnosis is to use two domains when there are two independent calculations to be done. Suppose in our case that we have a domain D available to execute P2. When our program reaches F we do a fork jump to the D and proceed to P1.

At the end of P1 we call D again (neither passing nor accepting parameters) and proceed to J. At the end of P2 we return to DK(0) (to become available) followed by another return.

If P1 finishes first it will become stalled on trying to enter D. In either case we reach code J only after P1 and P2 both have finished.

Another way to describe the join is to say that domain D sleeps {(p3,sleep)} after executing P2 and the domain executing P1 wakes it up with a call jump, and then D returns.

Another way to do it, if the P1 domain does not otherwise service a start key, would be for the P1 domain to sleep and D to wake it up.

Collections of data larger than a page can be efficiently passed by passing memory keys. More keys that 3 can be passed with an auxiliary node.
These ideas may cause trouble when it is realized that keys to the segment or node may be kept longer than was intended by their creator. Some of these problems can be circumvented by passing rescindable authority to the segment or node.

Other problems may arise if the segment or node disappears or otherwise mal-performs while the user is using the object.

See also (p3,ejp).

There are several techniques a zot creator ("zot" is a formal parameter here) can use to deal with the problem of clients who lose their zot keys.

1. Advise the client to provide a guarded space bank to the creator. If a zot key is lost, the user must call the guard to reclaim the space. Since space banks are hierarchical, there is always a sufficiently high bank to which not all keys have been lost. Disadvantages of this method: the zots may not be prompt because the space bank can be zapped at any time. Also, zots must be independent - no shared storage.

2. Accept an account and use it to charge rent for the zot. If a zot key is lost, the user can exhaust the account to destroy the zot. Since accounts are hierarchical, there is always a sufficiently high account to which not all keys have been lost. The space bank creator uses this method. Disadvantage: it is awkward or impossible for a client to specify the type of storage to be used for the zot.

3. Place a limit on the lifetime of a zot. A zot is destroyed when its lifetime expires. The user pays to receive a zot creator key good for N zot-seconds. If he loses a zot key, the zot will eventually expire. It may be possible to turn in a zot creator and get a refund. This method is useful when zot-seconds are an artificially scarce resource. The Tymnet adapter uses this method. Disadvantage: a zot does not stay around forever. It must be possible to choose a lifetime which is long enough to be useful and short enough so that paying for the zot over that lifetime (in case zot key is lost) is not terribly expensive.

4. This is a combination of 2 and 3. When a user creates a zot he supplies an account and says what he wants the lifetime of that zot to be. The account pays a one-time charge. There may be a call, using a zot key and an account, to extend the lifetime of the zot. This is like 3 except there is a separate limit for each zot instead of one for all zots created under a given zot creator.

5. Whenever a zot is created, keep a pointer (key) to it (which can be used to destroy it) in something older, like a previously existing zot. When a zot is destroyed, all the zots to which it has pointers are destroyed (recursively). Thus these pointers form a tree. The key to the oldest zot (root of the tree) is kept in a place where it is never lost.

A service that must be prompt, such as a generally available creator, must take precautions when using keys that it accepts.

If it uses a space bank, it should use the SBT to verify that the bank is official and prompt.

If necessary, it can act as a front end and create a domain to do any work that might not be prompt. This requires a prompt official space bank and a meter (which need not be verified). One other key can be accepted (in addition to a resume key).

If it needs to accept more than three keys, it can accept a node key containing the extra keys.

It can create a back end to take keys out of the node. This way there is no need to verify the promptness of the node key.

Or it can accept a key to a prompt official space bank to which the node is acceptable. After verifying the bank, the service can sever the node. This verifies the officialness of the node without destroying its contents. It incidentally also ensures the privacy of the node.

If it needs to accept more than 4096 bytes of data, it can accept keys to pages or memory trees. If the memory trees are built of node keys, the same solutions work here as above, namely back ends and severing.

There are calls and returns; there are start keys and resume keys. It might be assumed that calls go with start keys and returns go with resume keys. This is the usual arrangement. Other arrangements, however, are very powerful.

Returning to an Start Key

This is a familiar strategy used at the end of subroutines where another subroutine is required. The first subroutine hands its resume key to the second subroutine and gives up control for good. The second subroutine expects and gets a resume key; it is merely not to the caller.

Calling an Resume Key
This corresponds to co-routines. The program gives up control temporarily, expecting to regain control later at the next location in the code. The control is given back, however, to another program that earlier called the first program.

Each correspondent of a co-routine is a collection of domains. While they have control, the members of this collection must hold on to the most recent gate key received from the other correspondent. When they give up control they use this gate and pass (usually by a call) a gate to the other correspondent to be used to get back to the first correspondent.

Exceptional Cases
The entry block is free to reject any information that is not required. If fewer keys are requested than offered the remainder are not copied. If a key is requested that is not offered, a zero data key is supplied.

Becoming available
To make itself available, a domain can execute a return jump to a data key (passing no parameters). The return jump of course makes the domain available. Invoking the data key will have no other side effects.

Sometimes a domain flavor is wanted where many instances of that flavor are required and one cannot afford the three nodes that are necessary for each instance. Such a function may be had for the cost of one node per instance.

Some instances may be implemented by producing a node which holds all of the particular values {or keys to them} and also a start key to a shared domain that obeys the code that defines the logic of the flavor. This node is formatted as a segment node with the latter entry as the segment keeper and {presumably} 0 initial slots.

A segment key to the new node is produced and this can be used as a key to the instance of the module.

See (one-node-dom) for related ideas.