{tentative}Segment Fault Actions

When a domain references its segment at an address for which storage is not defined by its segment, or a write reference is made to a read-only portion of that segment, a fault occurs. Two simultaneous actions occur:
A trap code is placed in the domain describing the virtual address produced by the domain and whether the fault was caused by lack of write access. {(fault-act-one)}

A message is sent to the segment keeper providing information and authority sufficient to change the segment so as to conform to the requirements of the memory access {which will presumably be repeated when the domain is restarted}. {(segkeepcall)}

There is always a segment keeper even if it is provided by the kernel {(seg-keep)}.

When the segment keeper is done it uses a fault key to report back. If it was successful then it sends 0 as the return code which results in the action described at (f31). In this case the domain's trap code does not cause a trap to the domain's keeper because there is never a process in the domain while the trap code is nonzero.

If the keeper didn't repair the segment then the keeper sends back a seven-bit nonzero excuse as its return code, which is incorporated in the trap code as a message to the domain's keeper by the logic described at (f32). The kernel-supplied keeper always returns the error code.

This {new} fault handling allows a program to more easily establish which sub segment caused an unanticipated trap by the program running in the domain.

Gnosis departs from the standard segmentation-paging ideas exemplified by Multics where the virtual address is conceptually divided into a segment indication and a word-within-segment indication. The primary reason for this departure is that the 370 hardware virtual addresses are too short to be permanently divided into two portions: segment specifier and byte specifier. 24 bits is certainly not enough and 32 would be marginal.

The Gnosis memory tree logic partly overcomes the limitations of the small address. A Gnosis style memory tree can be built, for example, with three 1 meg segments and fifty 64K segments. This could not be done if the 24 bit virtual address had been permanently divided into segment and byte portions.

With window keys, segments with sizes such as 2 & 3 meg can be placed directly in the virtual memory, {impossible with Multics}.

With much larger segments windowing must be dynamically managed by the program.

The read-only and no-call bits in segment keys are to prevent information from passing from the key holder to the object designated by the key {the segment and its keeper}. The holder of the key may wish to impose these restrictions in order to keep a secret. The holder may be constructing a discreet object {(p3,do)} where an untrusted program will run that needs access to a segment. The object builder is unaware of the origin of the segment. If the holder turns these bits on, the segment key can be given to that program without fear that the key can be used to export information from the object.

The owner of the segment has even more obvious reasons for turning on these bits -- to keep the segment from being influenced.

Here are two applications which seems to require the NO_CALL bit.

Slow Keepers Repriced
Program P wants access to segment S. S has segment keepers. Speculator X believes that S's segment keepers are fairly prompt, and wants to provide to P a segment S' with the property that P's meter will not {appear to} coast {(p1,coast)} when P makes a reference that results in a segment keeper of S being called.

X constructs a segment node S' with LSS = 12 and with segment keeper X1. A segment key to S with the NO_CALL bit on is placed in S'. Everything works fine until P references an address A relative to S with no page behind it. In that case X1 gets control and is told A. X1 runs under the same meter and charge set as P {the contract meter perhaps} so that meter is not coasting. {X should be able to transfer the CPU charge that X1 runs up from P's meter to some other meter.} X1 notes the coasting counter in P's meter then references address A in S {using a key to S without the NO_CALL bit}. This causes the segment keeper in S to be called, and P's meter is {may be} now coasting. When S's segment keeper returns to X1, X1 resets the coasting counter in P's meter to its former value {transferring the difference to X's meter} and then returns to P. This solution probably requires S to be consistent.

Insulating Domains from Memory Traps
When more than one segment keeper is encountered in the memory tree path to the page the kernel calls the keeper nearest the page.

If the kernel called the first keeper, the domain designer could insulate his domain from memory traps by installing a keeper next to the domain that would provide pages for addresses that other segment keepers trapped on. This intermediate keeper first probes the lower segment keeper to see if it will provide the page.

But this effect can be had in the current design by the use of the no-call bit. The domain designer installs a segment node with a keeper for his memory tree root. In this node he places a segmode key with the no-call bit to a node that holds the original memory tree root. The keeper is given direct access to this latter root.

There are reasons to regret the no-call bit. Segment keepers can't hide their strategies. They must count on the segment user to accede to the illusion.

If the kernel always called the first segment keeper in the memory tree path it would be possible to program keepers so that they could provide the virtual address as the trap code that they returned when they used the fault key to the accessing domain. See (p1,which-keep) for other reasons why it might be preferable to call the first keeper.

Background keys solve the following problem: Suppose that we wish to make a virtual copy of a segment S to which we lack a modular segment key {(p2,modularseg)}. Some 16 page sub-segment has had just one page modified. Without background keys we would have to build a node with a window key and a copy of S for each of the other 15 pages {that we want to share}. This seems gross.

Once, the design of Gnosis did not allow a node key to serve in the role of a segment key. The next paragraph tells why. The paragraph after that tells how we get around the problem.

Gnosis once prohibited node keys from serving the function of segment keys in segment nodes so that synthetic node keys might be supported. If this were not the case a synthetic node key {really a gate} would fail when used in the position of a node key in a segment node.

It turns out that a segment key can model a node key in the role of either a place to put keys or, in its other function, as a memory key.

Here is a design proposal. This will not be implemented soon.

If a start key is found in a memory tree slot which the program is accessing the start key is called as if it were a segment keeper key except that no node key {to a segment node} is passed. This is to provide an archive service where a page key has been replaced by a tape block entry, which is a program that knows how to get the real page back. This mechanism does not provide for access to the segment node; to do so would create Trojan Horses in the form of alleged pages that were entries. The archiver must resort to some other {god?} license to replace these entries with the new page keys.

The holder of a segment key may call the segment keeper with order code -1. The segment keeper has no way of distinguishing this case from the implicit call due to a reference.

An alternative to the described memory tree architecture would have permitted or required the user to provide segment valued entries {gates} in the memory tree. This might have permitted removal of other portions of the memory tree architecture and yet provided more function. The difficulty with this scheme is that the kernel must invoke such gates as a result of real storage management considerations. This leads to a difficult recursion: congestion leads to paging; paging leads to invoking the segment valued gates; these gates lead to congestion. It is possible to imagine the system reaching 100% overhead and making no headway; merely invoking these gates. With the current design I believe that a strict upper bound can be placed on overhead.

Red & Black Segments

It seems strange perhaps that there are two formats for segment nodes, red & black {(p1,segnode)}. We provide a common application that requires both at once.

How shall we build a 50 page segment with a segment keeper? We first build three 16 page segments and a two page segment. The segment nodes defining the 16 page segments must be black in order hold the 16 page keys for the constituent pages. We then make segmode keys to these four segment nodes and place them in a new node that we format as a red segment node. Also in the new node is the start key for the segment keeper. If the new node were not red there would be no room for the segment keeper key.

If the top node were black, segment keys to the node would specify an lss of 4 and the segment would be forever limited to 256 pages because there is no general way to find and access all of those segment keys. With a red segment node the lss can be increased to meet future requirements because the only record of the lss is in the red segment node to which we may retain access.

{ni}Getting Key Argument Two

The format key could hold a four bit number designating a slot that would accept key argument two of any message to the segment keeper. See (p3,qrn) about related ideas.

Background
Section (p3,facilities) says that the machine that we run on must suppress or nullify instructions where the 370 Principles of Operations says that they may be terminated. Indeed we make a great deal of use of this.

Specifically we are vulnerable to instruction termination due to protection exceptions caused by mismatch of storage key and PSW key. We seek here the minimum kernel architecture change to support programs in coping with machines that terminate upon protection exceptions when those programs are expected to run thru ports to machines with such behavior.

The bit in the data byte that we define here may also be of use in machines that sport memory mapped IO.

The Scheme
Bit 2 of the memory key data byte is allocated as the TP (Termination Protections) bit. There is no convenient place for the bit in window keys. We will allocate an inconvenient place if that becomes profitable. "Need Write" would have also had appropriate connotations as a name for this bit. Write access is needed to any page accessed by this key. Memory keys with both TP and RO cause RO faults even on machines that do not terminate.

Consider a state machine M that travels down the memory tree from the domain to the page. Call the states A, B, C, W and F just now. As a domain performs a read access, M is initialized to state A. The initial state is W for a domain that performs a write operation. Four stimuli drive M's state. Encounters with TP (Termination Protection) bits, encounters with RO (read-only) bits on a CPU that does not terminate, encounters of RO on CPUs that do (ROT), and page keys.

State A - Write access OK

State B - Need write access if CPU terminates

State C - Need read only access

State W - Need write access

State F - Futile, will fault, but how?

input TP RO ROT page]
A B C C rw access to page] B B C fault or F rw access to page] C C C C ro access to page] W W fault fault rw access to page] F F F F fault

An entry "fault" in this table indicates that the state machine stops at that point in the tree and a fault in reported to the appropriate keeper. Non read-only faults are not shown above. State B, encountering a RO bit on a CPU that terminates (ROT) may either fault or go into state F depend on the model of the kernel. If a non-memory key should occur subsequent to the RO bit then some other access fault would be reported to the segment keeper.

I find the above information much clearer as a state diagram.

An alternate state diagram

input TP RO page]
A AB C rw access to page] AB AB CF rw access to page] CF CF CF if machine terminates, fault,] else ro access to page ] B B fault rw access to page] C C C ro access to page

The TP bit is never ignored. This state machine has the advantage, I think, in the following case. If the memory tree has a TP bit, then a RO bit, then a bad key, it will complain about the key regardless of what kind of machine you run on. Another advantage is that the test for the kind of machine is done only once, just before filling in the page table entry.

The meaning of the message to the segment keeper in this latter case is: "Someone tried to access a page in your segment. He only has read access but does not want read access unless he can have write access." How is the keeper to respond?

Other changes to kernel definition
The definition of "sensory version" must be changed and the operation of fetching via a sense key.

{ni}Define a way to get a page key with the TP bit. The kernel is coded to interpret bit but not to produce it.

Use of the Termination Protection bit
The only effect of the TP bit is to modify the meaning of the RO bit. Before encountering any TP bits, the RO bit means "any write here is an error; I don't need to recover from it". After a TP bit, the RO bit means "I need to be notified (in a way that allows recovery) before any write here".

An application that intends to write into an area of storage that may be kept by a segment keeper that is designed to respond to write faults, interposes a memory key with the termination protection bit set. This has the effect of signaling the segment keeper with a write fault upon first read of a given page of the segment. There are two interesting cases. (1) The real write is nearly as early as the first read, in which case there is little extra cost. (2) The real write comes never or much later. In this case an extra page is required for this duration that would not otherwise have been needed on machines that do not terminate instructions.

See (p2,callsegx) concerning mods to CALLSEG.