Keys provide a simplification to system design of great scope and power because:
A basic rule of the system is that keys can only be stored in key pages or in a special system pool called the key table. A user may build hierarchies of key pages at his own discretion; in fact, a user’s files and file directories would form such a structure. From these facts follows the conclusion that any key may be found either in the key table or in some tree structure rooted in the key table.
Template keys provide an excellent compromise between these two extremes. A template page is initially shared among all users of it. It is not read-only and can be stored into by any program. When this occurs, however, a private copy of the page is created which replaces the shared copy for that user.
This capability provides for several interesting effects: first, subsystems do not have to initialize their context pages upon first entry. They can be initialized once during generation and made template pages. Each time user dependent data is stored, a page private to that user is created. Second, a partially shared file is possible. If two users start with a common file and make small changes to it, the changed parts become private and the unchanged parts remain shared.
As mentioned above, keys can only be kept in key pages or in the key table to which programs do not have direct access. In the most general situation, keys are passed between two programs in key pages. But since a key page is passed by passing a key to it, there must be a mechanism to allow the passage of single keys. This is provided through a device called a key stack which each process maintains with a stack pointer double word at locations 16 and 17. Whenever a gate call is made, the contents of the key stack are transferred to the key stack of the gate program.
Each user needs some type of mechanism to serve as the long term holder of his keys. This is essentially the function of the file directory structure. The file system is a group of routines which get and put keys between the file directories and operating programs on the basis of symbolic names. It is perfectly satisfactory, however, to keep keys in raw form within “dump” files and completely bypass the normal file system for certain types of operations.
Certain types of keys can be manufactured at will by a user program. An immediate key can be created and inserted into any blank slot in a key page. Similarly an indirect key can be created by specific request. Possession of a read or write key allows a user to create a strong key and an associated set of weak keys. Gate keys are created by a special process whose description is postponed to a more detailed discussion of gates. Events are created upon demand and their keys may be copied without restriction.
Possession of master and write keys gives the possessor the authority to delete the object of the key, which causes the space occupied by the object to be reclaimed by the system. Any other keys to the same object are unaffected but useless. A user may delete any of his keys at will. Only the deletion of a master key causes immediate reclamation of space, however. As a low-level maintenance procedure, pages with no outstanding keys to them must be identified and deleted by the system. This can be done by scanning all key pages in the system and cross checking then with the key table. It would be a simple matter to do this as part of the disc bit map building procedure.
The account supervisor can create subsidiary accounts, transfer funds into them and pass keys to them to other users. If a user wishes to limit the amount of exposure he has to a given program, or for a given time-sharing session, he can create a sub account, transfer funds into it and connect himself to it for charging purposes. If the sub account runs dry, a program trap will occur; at this point, execution may be terminated or more funds may be transferred and execution resumed. A sub account may be deleted, in which case the funds contained in it are transferred back into the higher level account.
Another type of account called an indirect account exists for special situations. Essentially, it is a pointer to a higher account, although it has its own usage and balance information. The special feature is, that the indirect account does not actually have any funds in it; thus, the indicated “balance” in a group of indirect accounts may be larger than that of the master account. However, any changes made to the indirect account are also made to the master so that the master may run dry before any of the indirect accounts. The indirect account is primarily used when it would be undesirable to pre-allocate funds to a group of sub accounts. Indirect account usage causes some extra monitor overhead since all members of an indirect account chain must be kept in core when a process is running.
A detailed discussion of the use of accounts for controlling processes is postponed to the next section.
This simple approach cannot continue if dollar amounts are to be used for direct control of processes. In this case, the cost of a unit of each resource must be known at the time and place that resource is charged for. This raises the problem of specifying all the pertinent variables about how much each resource costs. In the past, these variables have been four-dimensional:
At specified times during the execution of a process, entries are made into the accounting file by calling the accounting demon through a system gate. The accounting demon is the only program that knows the structure of the accounting files, so that this function is kept out of the monitor. Accounting records will generally be made at log-in, log-out, process creation and deletion, transitions through those gates for which accounting records are desired and at periodic intervals to protect against crashes.
To allow this function, a program will be able to withdraw funds from any account to which it has a key, causing a corresponding entry to be made in the accounting file. Among other advantages, this means that the account balances can be used to control the use of any software that makes use of system accounting, even if the charges are not being made on the basis of Tymshare resource units.
This makes it possible for a software vendor to charge a fixed price for a service routine. When the vendor’s routine is called it merely transfers the fixed fee from the caller’s account and then begins to run under one of the vendor’s own accounts.
Recall that both gates and processes have space pages. A gate is, in fact, a latent process. Jumping through a gate can be viewed in either of two ways: as the metamorphosis of a single process or as the suspension of one process and the simultaneous creation of another. Indeed, the suspension of the first process is only an option; “forking” is accomplished by not suspending the calling process. As may be expected, there are a few restrictions on the similarity between gate calls and process creation, but these must be discussed after more details on gates have been presented.
Most processes will run with their space rage in their virtual memory, as the usual memory manipulation techniques require movement of keys in and out of the space page. There is an exception to this, however. If CALs or trap conditions are being used to interface a program with an external gate (which is perhaps acting as a simulator), a write key to the space page of the caller is delivered to the gate as a parameter. The called gate may then perform its desired manipulation on the caller’s memory. Note that the system is assuming that the process which initialized the space page has implicitly authorized the passing of the write key to the gate program, which seems to be reasonable.
Given that a gate is defined by its associated space page, it becomes fairly reasonable to relate the two entities. In particular, there exists a system call which takes a write key to a space page and a few other parameters and produces a gate key. If the indicated space page is already a gate, these gates can be rendered invalid and a new gate created. Thus, the write key to the space page is more powerful than a normal gate key. In particular, a process which holds the write key to the space page of another process can stop it by this operation.
Stopping a process by this mechanism is not usually the cleanest thing to do. In particular, if the process has jumped through another gate, then it is running as if it were a third process; the stopping of the second has merely prevented the third process from restarting the second again. Nothing really disastrous has happened to the system (the orphaned process is either annihilated by the system or allowed to commit suicide gracefully). The recommended approach is to use the account controls which stop cleanly all processes running under a given account. It may happen, however, that a process created by a gate call has begun executing under another account, in which case the creator has no control over it. In this case, termination by write key is all that can be done; in such cases it would be expected that the third process is prepared for the possibility and will do the right thing.
There are three types of gate calls, the jump, the jump-return, and the fork. The fork is essentially like the straight jump call with the exception that two processes exist while before there was only one. The distinction between the jump and the jump-return lies in the fact that the jump-return creates and passes to the called gate a gate which may be used to return control to the caller. Depending on the variety of return gate executed, the new return gate may either be placed on the key stack or in a designated memory location.
The key stack is an ad hoc vehicle for passing small numbers of keys across gate calls. Locations 16 and 17 decimal of the virtual memory of a process contains a stack pointer double word used to control a key stack. When a gate call is made, the contents of the key stack in the calling process are copied by the system into the called program’s key stack.
General registers are also handled in an ad hoc manner. There are instances when no general registers should be passed, as when restarting a suspended process. Can the other hand, general registers provide an efficient method for passing arguments. The proposed mechanism is as follows: the space page of each gate contains a bit mask indicating which, registers are to be passed across the gate. Since it is within the space page, the gate program can change the conventions when it wishes.
Multiple entry points are a very desirable feature of gates, as many complex packages will be built out of functions which need to share subroutines and context. A general, yet simple, scheme is the following: a bit mask is stored in the key table position corresponding to the gate key which describes which entry points are legal for a multi-entry gate. The key to a multi-entry gate may be used in two manners: if the key is referenced through an indirect key, an index field of the indirect key determines the entry point number; if the key is referenced directly, the contents of index register 7 determine the entry point number; in either event, the gate program begins execution with the entry point number in register 7 if the bit mask makes that entry point legal.
We are now ready to compare pure and return gates. The distinction between the two is quite simple - the space page of a pure gate is a template page; at the time of the first store into it, a private copy is made for the caller. Similarly, its context pages are either originally template pages or are acquired after the first call to the gate. If the pure gate was called by a jump-return, the called gate may also execute a jump-return to the caller, giving to the caller a return gate to be used in a subsequent call.
It should be noted that when a gate is executed, the key to it is removed from the callers virtual space to prevent multiple usages. In addition, any copies of the key held by the caller or any other process, are rendered useless. (This is only true for non-pure gates; since a pure gate generates private copies for each use, it is not rendered useless to others). However, the normal practice for a called gate is to deliver another return gate key when it returns to its caller. If a program repeatedly calls the “same” gate (i.e.; keeps using the new return gate), the actual structure involved is two co-routines rather than a strict subroutine hierarchy.
The problem of protection for the user is compounded by the fact that the owner of the program may have legitimate reasons for writing some sorts of data, such as accounting information or statistical summaries. The user of the program has no way of knowing what are legitimate functions and what are merely clever ways of encoding his proprietary data.
As a protection mechanism, an agent known as the System Referee may be invoked by a user to oversee execution of a program. This option is invoked by a parameter of a gate transition. The space page of the gate is flagged in the privileged area as being under the jurisdiction of the System Referee. All gate transitions made by the program are similarly flagged.
In operational terms, the flag causes the process to be suspended whenever it detects a non-master write key (or an indirect key pointing to one), in its space page. As part of the scheme, the user supplies a gate to the System Referee which will be called when the process is suspended. The user supplied procedure is given the data image (i.e., all the bits but not the status) of the key for examination. If the key is the member of an agreed upon set, the user program may restart the process; otherwise, it may abort it.
A short consideration of the mechanisms for information transmittal shows the above scheme is sufficient. A master key causes no difficulty because of its uniqueness. If the executing process holds the master key and is eventually deleted, no other access to that page exists. Read keys also present no problems, as the read key will not allow the process to write anywhere. Hence we need only consider non-master write keys. Now, the non-master write key must be put into the space page of some process within the jurisdiction of the System Referee in order to put data into it. Hence, detecting such keys on initial gate transition or during subsequent execution is sufficient.
There can be no limitation on the types of activity the process can perform once it has established the right to write in a page. Any write access can succeed in transmitting encoded user data. However, the user does have the option of allowing no external writing. To be workable, there must be some common agreement between the two parties. The important point is that the user can enforce the agreement himself by detecting violations of it.