REGISTER  |  SIGN IN
United States Patent4525780
Bratt , ; et al.June 25, 1985
Title
Data processing system having a memory using object-based information and a protection scheme for determining access rights to such information
Abstract
A digital data processing system has a memory organized into objects containing at least operands and instructions. Each object is identified by a unique and permanent identifier code which identifies the data processing system and the object. The system uses a protection technique to prevent unauthorized access to objects by users who are identified by a subject number which identifies the user, a process of the system for executing a user's procedure, and the type of operation of the system to be performed by the user's procedure. An access control list for each object includes an access control list entry for each subject having access rights to the object and means for confirming that a particular active subject has access rights to a particular object before permitting access to the object. The system also includes stacks for containing information relating to the current state of execution of the system.
Inventors:Bratt; Richard G. (Wayland, MA), Clancy; Gerald F.  (Saratoga, CA), Gavrin; Edward S.  (Lincoln, MA), Gruner; Ronald H.  (Cary, NC), Mundie; Craig J.  (Cary, NC), Schleimer; Stephen I.  (Chapel Hill, NC), Wallach; Steven J.  (Saratoga, CA)
Assignee:Data General Corporation (Westboro, MA)
Appl. No.:616773
Filed:May 31, 1984
Current U.S. Class:711/163 
Field of Search:364/2MSFile,9MSFile
U.S. Patent Documents
3902163August 1975Amdahl et al.
3902164August 1975Kelley et al.
4079453March 1978Dahl
4084228April 1978Dufond et al.
4130867December 1978Bachman et al.
4133038January 1979Huettner et al.
4135240January 1979Ritchie
4148098April 1979McCreight et al.
4177510December 1979Appell et al.
4205372May 1980Gruner et al.
4206503June 1980Woods et al.
4276594June 1981Morley
4325120April 1982Colley et al.
4354225October 1982Frieder et al.
4367524January 1983Budde et al.
4371925February 1983Carberry et al.
4398243August 1983Holberger et al.
4408274October 1983Wheatley et al.
4430705February 1984Cannavino et al.
4439830March 1984Chueh
4442484April 4984Childs, Jr. et al.
Primary Examiner: Zache; Raulfe B.
Assistant Examiner: Williams, Jr; A. E.
Attorney, Agent or Firm:O'Connell; Robert
Parent Case Text


This application is a continuation of application Ser. No. 266,409, filed 5/22/81 now abandoned.
Claims

What is claimed is:
1. In a digital computer system including
memory means for performing memory operations including storing and providing items of data, said items of data including instructions;
processor means connected to said memory means for performing operations in response to said instructions including processing said items of data;
memory organization means operative on said memory means for organizing said memory means into objects identified by unique identifiers and allowing the location of said items therein, each said item being associated with an object and addressable by a logical address specifying the unique identifier of the object with which said item is associated and an offset specifying the location of said item its associated object,
said memory organization means further identifying for each one of said objects a selected set of subjects representing entities for which said processor means responds to said instructions;
memory operation specifier generation means in said processor means responsive to said instructions for providing a memory operation specifier for each item processed by said processor, said memory operation specifier for a given item specifying the object in which said given item is to be located and one of said memory operations; and
memory operations means responsive to a memory operation specifier which includes a logical address and a memory command specifying a memory operation for performing the memory operation specified by the memory command on the item specified by the logical address for a current subject for which said processor means is currently executing said instructions only when said current subject is one of the subjects in the selected set of subjects identified for the object specified in said memory operation specifier.

2. In a digital computer system of claim 1 wherein
said memory operation specifier further includes a length specifier specifying the length of said item at the location specified by said logical address; and
said memory operation means performs said memory operation specified by said memory command on said item at said location specified by said logical address having the length specified by said length specifier.

3. In a digital computer system of claim 2 wherein said length specifier specifies a length in bits.

4. In a digital computer system of claim 1 wherein said offset is a bit-granular offset and may specify any bit of the items associated with the object specified in said logical address.

5. In a digital computer system of claim 1 wherein said memory organization means identifies each said object with a single unique identifier and said single unique identifier never identifies any other said object.

6. In a digital computer system of claim 1 wherein said unique identifier contains 80 bits.

7. In a digital computer system of claim 1 wherein
said memory organization means includes means for organizing said memory means into a plurality of logical allocation untis, each said object being associated with one of said logical allocation units, and
said unique identifier further includes
a logical allocation unit identifier specifying the logical allocation unit associated with the object identified by said unique identifier, and
an object serial number identifying said object in said associated logical allocation unit.

8. In a digital computer system of claim 7 wherein
said memory organization means identifies each said logical allocation unit by a single logical allocation unit identifier and said single logical allocation unit identifier never identifies any other said logical allocation unit, and
said memory organization means identifies each object associated with said logical allocation unit by a single object serial number and said object serial number never identifies any other said object associated with said logical allocation unit.

9. In a digital computer system of claim 7 wherein said logical allocation unit identifier further includes
a logical allocation unit group number specifying a logical allocation group including a plurality of said logical allocation units, and
a logical allocation unit serial number identifying one of the logical allocation units of said plurality of logical allocation units.

10. In a digital computer system of claim 9 wherein
said memory organization means identifies each of said plurality of logical allocation unit groups by a single logical allocation unit group number and said single logical allocation unit group number never identifies any other said logical allocation unit group; and
said memory organization means identifies each logical allocation unit associated with the logical allocation unit group identified by said logical allocation unit group number by a single logical allocation unit serial number and said single logical allocation unit serial number never identifies any other logical allocation unit in the logical allocation unit group specified by said logical allocation unit group number.

11. In a digital computer system of claim 9 wherein
said logical allocation unit group number contains 9 bits;
said logical allocation unit serial number contains 8 bits;
said object serial number contains 48 bits; and
said offset identifies a single bit which may be any bit in the items associated with the object identified by said unique identifier.

12. In a digital computer system of claim 1 wherein said univeral identifiers do not specify locations of objects relative to other said objects.

13. In a digital computer system of claim 1 wherein certain ones of said subjects, including said current subject, are active subjects for which said processor means is or shortly will be executing said instructions;
said memory operations means includes
means for temporarily associating each said active subject with a different active subject number, said current subject being represented in said memory operation means by the active subject number currently associated therewith and said memory operations means using the active subject number currently associated with said current subject to determine whether said current subject is one of the set of subjects identified for the object specified in said memory operation specifier.

14. In a digital computer system of claim 13 wherein said memory operation means further includes
means accessible to said processor means for storing the active subject number currently associated with said current subject.

15. In a digital computer system of claim 1 wherein
said memory organization means further identifies for each of said selected set of subjects a selected set of said memory operations which said selected set of subjects is authorized to perform on the items locatable by a said object; and
said memory operation means further performs the memory operation specified in said memory operation specifier only if said specified memory operation is identified as one of the selected set of memory operations which said current subject is authorized to perform on the items locatable by the object specified in said memory operation specifier.

16. In a digital computer system of claim 15 wherein said memory operation means further includes
protection cache means for encaching information specifying said memory operations which a current subject is authorized to perform on the objects specified in the memory operation specifiers produced in response to said instructions, said protection cache means receiving said memory operation specifier and responding thereto by producing an access violation signal when said encached information indicates that said current subject may not perform the memory operation specified by said memory operation specifier on the object specified by said memory operaton specifier; and
means responsive to said access violation signal for inhibiting the performance of said specified memory operation.

17. In a digital computer system of claim 1 wherein
said instructions are contained in procedures of said items and said processor means responds to said instructions only while executing one of said procedures;
the operations performed by said processor means further include
a call operation for suspending a current execution of one of said procedures and commencing another execution as the current execution, and
a return operation for terminating said current execution and resuming the execution which was suspended to commence the terminated current execution; and
said current subject changes as a consequence of said call opeation and said return operation.
Description
CROSS REFERENCE TO RELATED APPLICATIONS

The present patent application is related to other patent applications assigned to the assignee of the present application.

1. Field of the Invention

The present invention relates to a digital data processing system and, more particularly, to a multiprocess digital data processing system in which information, including operands and instructions, can be organized as objects each of which is identified by a unique and permanent code number and which includes protection means for preventing unauthorized access by a user to objects of another user.

2. Description of Prior Art

A general trend in the development of data processing systems has been towards systems suitable for use in interconnected data processing networks. Another trend has been towards data processing systems wherein the internal structure of the system is flexible, protected from users, and effectively invisible to the user and wherein the user is presented with a flexible and simplified interface to the system.

Certain problems and shortcomings affecting the realization of such a data processing system have appeared repeatedly in the prior art and must be overcome to create a data processing system having the above attributes. These prior art problems and limitations include the following topics.

First, the data processing systems of the prior art have not provided a system wide addressing system suitable for use in common by a large number of data processing systems interconnected into a network. Addressing systems of the prior art have not provided sufficiently large address spaces and have not allowed information to be permanently and uniquely identified. Prior addressing systems have not made provisions for information to be located and identified as to type or format, and have not provided sufficient granularity. In addition, prior addressing systems have reflected the physical structure of particular data processing systems. That is, the addressing systems have been dependent upon whether a particular computer was, for example, an 8, 16, 32, 64 or 128 bit machine. Since prior data processing systems have incorporated addressing mechanisms wherein the actual physical structure of the processing system is apparent to the user, the operations a user could perform have been limited by the addressing mechanisms. In addition, prior processor systems have operated as fixed word length machines, further limiting user operations.

Prior data processing systems have not provided effective protection mechanisms preventing one user from effecting another user's data and programs without permission. Such protection mechanisms have not allowed unique, positive identification of users requesting access to information, or of information, nor have such mechanisms been sufficiently flexible in operation. In addition, access rights have pertained to the users rather than to the information, so that control of access rights has been difficult. Finally, prior art protection mechanisms have allowed the use of "Trojan Horse arguments". That is, users not having access rights to certain information have been able to gain access to that information through another user or procedure having such access rights.

Yet another problem of the prior art is that of providing a simple and flexible interface user interface to a data processing system. The character of user's interface to a data processing system is determined, in part, by the means by which a user refers to and identifies operands and procedures of the user's programs and by the instruction structure of the system. Operands and procedures are customarily referred to and identified by some form of logical address having points of reference, and validity, only within a user's program. These addresses must be translated into logical and physical addresses within a data processing system each time a program is executed, and must then be frequently retranslated or generated during execution of a program. In addition, a user must provide specific instructions as to data format and handling. As such reference to operands or procedures typically comprise a major portion of the instruction stream of the user's program and requires numerous machine translations and operations to implement. A user's interface to a conventional system is thereby complicated, and the speed of execution of programs reduced, because of the complexity of the program references to operands and procedures.

A data processing system's instruction structure includes both the instructions for controlling system operations and the means by which these instructions are executed. Conventional data processing systems are designed to efficiently execute instructions in one or two user languages, for example, FORTRAN or COBOL. Programs written in any other language are not efficiently executable. In addition, a user is often faced with difficult programming problems when using any high level language other than the particular one or two languages that a particular conventional system is designed to utilize.

Yet another problem in conventional data processing systems is that of protecting the system's internal mechanisms, for example, stack mechanisms and internal control mechanisms, from accidental or malicious interference by a user.

Finally, the internal structure and operation of prior art data processing systems have not been flexible, or adaptive, in structure and operation. That is, the internal structure structure and operation of prior systems have not allowed the systems to be easily modified or adapted to meet particular data processing requirements. Such modifications may include changes in internal memory capacity, such as the addition or deletion of special purpose subsystems, for example, floating point or array processors. In addition, such modifications have significantly affected the users interface with the system. Ideally, the actual physical structure and operation of the data processing system should not be apparent at the user interface.

The present invention provides data processing system improvements and features which solve the above-described problems and limitations.

SUMMARY OF THE INVENTION

The digital computer system of the present invention includes a memory system comprising mass storage devices and one or more processors connected to the memory system. The memory system is organized into objects containing data items, e.g., operands and instructions, each object being identified by an object identifier. Locations of data items in the memory system are specified by means of the object identifier for the object containing the data item. The object identifier includes a code field which identifies the time of creation of the object relative to a selected initial time which is common to a plurality of digital computer systems. The system further includes a stack means which store the current state of execution of the system of the objects contain information relating to such current state of execution.

Access to the data items in objects is controlled by protection mechanisms of the system. When the digital computer system processes data in an object, it does so for a subject representing an entity using the computer system. An access control list associated with each object defines sets of subjects in a set of memory operations which a subject in a given set of subjects may perform on data items in the object. A memory operation on a data item in an object succeeds only if there is an access control list entry associated with the object which allows the subject for whom the processor is performing the memory operation to perform that operation on the data in the object.

It is thus an object of the present invention to provide an improved data processing system.

It is another object of the present invention to provide a data processing system capable of use in large, interconnected data processing networks.

It is yet another object of the present invention to provide an improved addressing mechanism suitable for use in large, interconnected data processing networks.

It is a further object of the present invention to provide an improved information protection mechanism.

It is still another object of the present invention to provide a simplified and flexible user interface to a data processing system.

It is yet a further object of the present invention to provide an improved mechanism for referring to operands.

It is a still further object of the present invention to provide an instruction structure allowing efficient data processing system operation with a plurality of high level user languages.

It is a further object of the present invention to provide data processing internal mechanisms protected from user interference.

It is yet another object of the present invention to provide a data processing system having a flexible internal structure capable of multiple, concurrent operations.

Other objects, advantages and features of the present invention will be understood by those of ordinary skill in the art, after referring to the following detailed description of the preferred embodiments and drawings wherein:

BRIEF DESCRIPTION OF DRAWINGS

FIG. 1 is a partial block diagram of a computer system incorporating the present invention;

FIG. 2 is a diagram illustrating computer system addressing structure of the present invention;

FIG. 3 is a diagram illustrating the computer system instruction stream of the present invention;

FIG. 4 is a diagram illustrating the control structure of a conventional computer system;

FIG. 4A is a diagram illustrating the control structure of a computer system incorporating the present invention;

FIGS. 5-475 and FIG. A1 inclusive, briefly described below, are diagrams all relating to the present invention;

FIG. 5 is a diagram illustrating a stack mechanism;

FIG. 6 is a diagram illustrating procedures, procedure objects, processes, and virtual processors;

FIG. 7 is a diagram illustrating operating levels and mechanisms of the present computer;

FIG. 8 is a diagram illustrating a physical implementation of processes and virtual processors;

FIG. 9 is a diagram illustrating a process and process stack objects;

FIG. 10 is a diagram illustrating operation of macrostacks and secure stacks;

FIG. 11 is a diagram illustrating detailed structure of a stack;

FIG. 12 is a diagram illustrating a physical descriptor;

FIG. 13 is a diagram illustrating the relationship between logical pages and frames in a memory storage space;

FIG. 14 is a diagram illustrating access control to objects;

FIG. 15 is a diagram illustrating virtual processors and virtual processor swapping;

FIG. 16 is a partial block diagram of an I/O system of the present computer system;

FIG. 17 is a diagram illustrating operation of a ring grant generator;

FIG. 18 is a partial block diagram of a memory system;

FIG. 19 is a partial block diagram of a fetch unit of the present computer system;

FIG. 20 is a partial block diagram of an execute unit of the present computer system;

FIGS. 21-100 are not used.

FIG. 101 is a more detailed partial block diagram of the present computer system;

FIG. 102 is a diagram illustrating certain information structures and mechanisms of the present computer system;

FIG. 103 is a diagram illustrating process structures;

FIG. 104 is a diagram illustrating a macrostack structure;

FIG. 105 is a diagram illustrating a secure stack structure;

FIGS. 106 A, B, and C are diagrams illustrating the addressing structure of the present computer system;

FIG. 107 is a diagram illustrating addressing mechanisms of the present computer system;

FIG. 108 is a diagram illustrating a name table entry;

FIG. 109 is a diagram illustrating protection mechanisms of the present computer system;

FIG. 110 is a diagram illustrating instruction and microinstruction mechanism of the present computer system;

FIGS. 111-200 are not used.

FIG. 201 is a detailed block diagram of a memory system;

FIG. 202 and 202A are a detailed block diagram of a fetch unit;

FIG. 203 is a detailed block diagram of an execute unit;

FIG. 204 is a detailed block diagram of an I/O system;

FIG. 205 is a partial block diagram of a diagnostic processor system;

FIG. 206 is a diagram illustrating assembly of FIGS. 201-205 to form a detailed block diagram of the present computer system;

FIG. 207 is a detailed block diagram of a memory interface controller;

FIG. 209 is a diagram of a memory to I/O system port interface;

FIG. 210 is a diagram of a memory operand port interface;

FIG. 211 is a diagram of a memory instruction port interface;

FIGS. 212 and 212A are a detailed block diagram of a memory system I/O, operand, and instruction ports and request multiplexer;

FIGS. 213 and 213A are a block diagram of memory port request logic, port wait flag logic, requestor priority selection logic, address path selection logic, and abort logic;

FIG. 214 is a detailed block diagram of memory request manager;

FIG. 215 is a detailed block diagram of memory trailor condition logic;

FIG. 216 is a detailed block diagram of memory miss control logic;

FIG. 217 is a detailed block diagram of memory read queue logic;

FIG. 218 is a detailed block diagram of memory load manager logic;

FIG. 219 is a detailed block diagram of memory bypass write and cache write control logic;

FIG. 220 is a detailed block diagram of memory writeback control logic;

FIG. 221 is a detailed block diagram of memory bypass write control logic;

FIG. 222 is a detailed block diagram of memory cache usage logic;

FIG. 223 is a detailed block diagram of memory byte write select logic;

FIG. 224 is a detailed block diagram of memory data path storing logic;

FIG. 225 is a detailed block diagram of memory read data handshake logic;

FIGS. 230 and 230B are a detailed block diagram of memory field interface unit logic;

FIG. 231 is a diagram illustrating memory format manipulation operations;

FIGS. 232, 232A and 232B are is a detailed block diagram of a cache;

FIG. 233 is a diagram illustrating cache operation;

FIGS. 234 and 234A are a detailed block diagram of a memory array;

FIG. 235 is a diagram illustrating memory array addressing;

FIG. 236 is a diagram illustrating memory array operation and timing;

FIGS. 237A, and 237B are a detailed block diagram of a memory bank controller;

FIG. 238 is a detailed block diagram of fetch unit offset multiplexer;

FIG. 239 is a detailed block diagram of fetch unit bias logic;

FIGS. 240 and 240A are a detailed block diagram of a generalized four way, set associative cache representing name cache, protection cache, and address translation unit;

FIG. 241 is a detailed block diagram of portions of computer system instruction and microinstruction control logic;

FIG. 242 is a detailed block diagram of portions of computer system microinstruction control logic;

FIG. 243 is a detailed block diagram of further portions of computer system microinstruction control logic;

FIGS. 244 and 244A are a diagram illustrating computer system states of operation;

FIG. 245 is a diagram illustrating computer system states of operation for a trace trap request;

FIG. 246 is a diagram illustrating computer system states of operation for a memory repeat interrupt;

FIG. 247 is a diagram illustrating priority level and masking of computer system events;

FIG. 248 is a detailed block diagram of event logic;

FIG. 249 is a detailed block diagram of microinstruction control store logic;

FIG. 250 is a diagram illustrating microinstruction formats;

FIG. 251 is a diagram illustrating a return control word stack word;

FIG. 252 is a diagram illustrating machine control words;

FIGS. 253 and 253A are a detailed block diagram of a register address generator;

FIG. 254 is a block diagram of interval and egg timers;

FIG. 255 is a detailed block diagram of execute unit control logic;

FIG. 256 is a detailed block diagram of an execute unit operand buffer;

FIG. 257 is a detailed block diagram of execute unit multiplier data paths and memory;

FIG. 258 is a detailed block diagram of execute unit multiplier arithmetic operation logic;

FIG. 259 is a detailed block diagram of execute unit exponent operation and multiplier control logic;

FIG. 260 is a diagram illustrating operation of an execute unit command queue load and interface to a fetch unit;

FIG. 261 is a diagram illustrating operation of an execute unit operand buffer load and interface to a fetch unit;

FIG. 262 is a diagram illustrating operation of an execute unit storeback or transfer of results and interface to a fetch unit;

FIG. 263 is a diagram illustrating operation of an execute unit check test condition and interface to a fetch unit;

FIG. 264 is a diagram illustrating operation of an execute unit exception test and interface to a fetch unit;

FIG. 265 is a block diagram of an execute unit arithmetic operation stack mechanism;

FIG. 266 is a diagram illustrating execute unit and fetch unit interrupt handshaking and interface;

FIG. 267 is a diagram illustrating execute unit and fetch unit interface and operation for nested interrupts;

FIG. 268 is a diagram illustrating execute unit and fetch unit interface and operation for loading an execute unit control store;

FIG. 269 is a detailed block diagram and illustration of operation of an I/O system ring grant generator;

FIG. 270 is a detailed block diagram of a fetch unit micromachine of the present computer system;

FIG. 271 is a diagram illustrating a logical descriptor;

FIG. 272 is a diagram illustrating use of fetch unit stack registers;

FIG. 273 is a diagram illustrating structures controlling event invocations;

FIG. 274 is a diagram illustrating fetch unit micromachine programs;

FIGS. 275-300 are not used.

FIG. 301 is a diagram illustrating pointer formats;

FIG. 302 is a diagram illustrating an associated address table;

FIG. 303 is a diagram illustrating a namespace overview of a procedure object;

FIG. 304 is a diagram illustrating name table entries;

FIG. 305 is a diagram illustrating an example of name resolution;

FIG. 306 is a diagram illustrating name cache entries;

FIG. 307 is a diagram illustrating translation of S-interpreter universal identifiers to dialect numbers;

FIGS. 308-400 are not used.

FIG. 401 is a diagram illustrating operating systems and system resources;

FIG. 402 is a diagram illustrating multiprocess operating systems;

FIG. 403 is a diagram illustrating an extended operating system and a kernel operating system;

FIG. 404 is a diagram illustrating an EOS view of objects;

FIG. 405 is a diagram illustrating pathnames to universal identifier translation;

FIG. 406 is a diagram illustrating universal identifier detail;

FIG. 407 is a diagram illustrating address translation with an address translation unit, a memory hash table, and a memory;

FIG. 408 is a diagram illustrating hashing in an active subject table;

FIG. 409 is a diagram illustrating logical allocation units and objects;

FIG. 410 is a diagram illustrating an active logical allocation unit table and active allocation units;

FIG. 411 is a diagram illustrating a conceptual logical allocation unit directory structure;

FIG. 412 is a diagram illustrating detail of a logical allocation unit directory entry;

FIG. 413 is a diagram illustrating universal identifiers and active object numbers;

FIG. 414 is a diagram illustrating an object manager queue and an active object manager queue;

FIG. 415 is a diagram illustrating an active object table implementation;

FIG. 416 is a diagram illustrating subject templates, primitive access control list entries, and extended access control list entries;

FIG. 417 is a diagram illustrating an active subject table entry;

FIG. 418 is a diagram illustrating a domain table;

FIG. 419 is a diagram illustrating an active non-primitive access table overview;

FIG. 420 is a diagram illustrating an active non-primitive access table entry;

FIG. 421 is a diagram illustrating an active primitive access matrix and an active primitive access matrix entry;

FIG. 422 is a diagram illustrating primitive data access checking;

FIG. 423 is a diagram illustrating object pages, memory frames, and address translation;

FIG. 424 is a diagram illustrating a conceptual overview of a virtual memory manager;

FIG. 425 is a diagram illustrating virtual memory manager components;

FIG. 426 is a diagram illustrating a memory hash table entry;

FIG. 427 is a diagram illustrating searching of a memory hash table;

FIG. 428 is a diagram illustrating a virtual memory manager queue;

FIG. 429 is a diagram illustrating detail of a memory frame table;

FIG. 430 is a diagram illustrating a conceptual overview of a virtual memory manager coordinator;

FIG. 431 is a diagram illustrating start I/O and await event counter blocks;

FIG. 432 is a diagram illustrating a finish I/O loop block;

FIG. 433 is a diagram illustrating a look for frame block;

FIG. 434 is a diagram illustrating a process virtual memory manager queue loop block;

FIG. 435 is a diagram illustrating a process object manager queue loop block and a clean frame block;

FIG. 436 is a diagram illustrating a frame allocation overview;

FIG. 437 is a diagram illustrating a detailed block 43601;

FIG. 438 is a diagram illustrating a detailed block 43602;

FIG. 439 is a diagram illustrating frame deallocation;

FIG. 440 is a diagram illustrating rearranging of a memory hash table;

FIGS. 441-446 are not used.

FIG. 447 is a diagram illustrating an overview of processes;

FIG. 448 is a diagram illustrating event counters and await entries;

FIG. 449 is a diagram illustrating an await table overview;

FIG. 450 is a diagram illustrating process synchronization with event counters and await entries;

FIG. 451 is a diagram illustrating locks;

FIG. 452 is a diagram illustrating message queues;

FIG. 453 is a diagram illustrating an overview of a virtual processor;

FIG. 454 is a diagram illustrating virtual processor synchronization;

FIG. 455 is a diagram illustrating detail of a process object;

FIG. 456 is a diagram illustrating an overview of process management;

FIG. 457 is a diagram illustrating process event table entries and lists;

FIG. 458 is a diagram illustrating an implementation of a clock event counter;

FIG. 459 is a diagram illustrating details of an outward signals object;

FIG. 460 is a diagram illustrating a process manager request queue;

FIG. 461 is a diagram illustrating messages from a kernel operating system to an extended operating system;

FIG. 462 is a diagram illustrating details of a virtual processor state block;

FIG. 463 is a diagram illustrating an overview of a virtual processor manager;

FIG. 464 is a diagram illustrating details of a virtual processor information entry;

FIG. 465 is a diagram illustrating details of virtual processor lists;

FIG. 466 is a diagram illustrating details of a virtual processor await table;

FIG. 467 is a diagram illustrating an overview of a macrostack object;

FIG. 468 is a diagram illustrating details of a macrostack object base;

FIG. 469 is a diagram illustrating details of a macrostack frame;

FIG. 470 is a diagram illustrating an overview of a secure stack;

FIG. 471 is a diagram illustrating details of a secure stack frame;

FIG. 472 is a diagram illustrating an overview of procedure object;

FIG. 473 is a diagram illustrating calls from microcode;

FIG. 474 is a diagram illustrating mediated frames;

FIG. 475 is a diagram illustrating a trace table; and,

FIG. A1 is a diagram illustrating fetch unit microinstruction formats.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The following description presents the structure and operation of a computer system incorporating a presently preferred embodiment of the present invention. As indicated in the following Table of Contents, certain features of computer system structure and operation will first be described in an Introductory Overview. Next, these and other features will be described in further detail in a more detailed Introduction to the detailed descriptions of the computer system. Following the Introduction, the structure and operation of the computer system will be described in detail. The detailed descriptions will present descriptions of the structure and operation of each of the major subsystems, or elements, of the computer system, of the interfaces between these major subsystems, and of overall computer system operation. Next, certain features of the operation of the individual subsystems will be presented in further detail, followed by a more detailed description of overall computer system operation. Finally, appendices will describe certain features of the operation of individual subsystems and of the overall system in yet further detail. Of these appendices, Appendix A presents a detailed description of the microcode operation of the present computer system. Appendix B presents a further detailed description of the overall operation of the present computer system. Appendix B is not essential for one of ordinary skill in the art to gain a complete understanding of the present invention and is provided as a supplement to the following detailed description. As such, Appendix B is provided, together with the present patent application, as a separate document to reside in the prosecution history of the present patent application and thus to be available to readers desiring additional information.

Certain conventions are used throughout the following descriptions to enhance clarity of presentation. First, and with exception of the Introductory Overview, each figure referred to in the following descriptions will be referred to by a three digit number. The most significant digit represents the number of the chapter in the following descriptions in which a particular figure is first referred to. The two least significant digits represent the sequential number of appearance of a figure in a particular chapter. For example, FIG. 319 would be the nineteenth figure appearing in the third chapter. Figures appearing in the Introductory Overview are referred to by a one or two digit number representing the order in which they are referred to in the Introductory Overview. It should be noted that certain figure numbers, for example, FIG. 208, do not appear in the following figures and descriptions; the subject matter of these figures has been incorporated into other figures and these figures deleted, during drafting of the following descriptions, to enhance clarity of presentation.

Second, reference numerals comprise a two digit number (00-99) preceded by the number of the figure in which the corresponding elements first appear. For example, reference numerals 31901 to 31999 would refer to elements 1 through 99 appearing in FIG. 319.

Finally, interconnections between related circuitry is represented in two ways. First, to enhance clarity of presentation, interconnections between circuitry may be represented by common signal names or references, rather than by drawn representations of wires or buses. Second, where related circuitry is shown in two or more figures, the figures may share a common figure number and will be distinguished by a letter designation, for example, FIGS. 319, 319A, and 319B. Common electrical points between such circuitry may be indicated by a bracket enclosing a lead to such a point and a designation of the form "A-b". "A" indicates other figures having the same common point for example, 319A, and "b" designates the particular common electrical point. In cases of related circuitry shown in this manner in two or more figures, reference numerals to elements will be assigned in sequence through the group of figures; the figure number portion of such reference numerals will be that of the first figure of the group of figures.

INTRODUCTORY OVERVIEW

A. Hardware Overview (FIG. 1)

B. Individual Operating Features (FIGS. 2, 3, 4, 5, 6)

1. Addressing (FIG. 2)

2. S-Language Instructions and Namespace Addressing (FIG. 3)

3. Architectural Base Pointer Addressing

4. Stack Mechanisms (FIGS. 4-5)

C. Procedure Processes and Virtual Processors (FIG. 6)

D. CS 101 Overall Structure and Operation (FIGS. 7, 8, 9, 10, 11, 12, 13, 14, 15)

1. Introduction (FIG. 7)

2. Compilers 702 (FIG. 7)

3. Binder 703 (FIG. 7)

4. EOS 704 (FIG. 7)

5. KOS and Architectural Interface 708 (FIG. 7)

6. Processes 610 and Virtual Processors 612 (FIG. 8)

7. Processes 610 and Stacks (FIG. 9)

8. Processes 610 and Calls (FIGS. 10, 11)

9. Memory References and the Virtual Memory Management System (FIG. 12, 13)

10. Access Control (FIG. 14)

11. Virtual Processors and Virtual Processor Swapping (FIG. 15)

E. CS 101 Structural Implementation (FIGS. 16, 17, 18, 19, 20)

1. (IOS) 116 (FIGS. 16, 17)

2. Memory (MEM) 112 (FIG. 18)

3. Fetch Unit (FU) 120 (FIG. 19)

4. Execute Unit (EU) 122 (FIG. 20)

1. Introduction (FIGS. 101-110)

A. General Structure and Operation (FIG. 101)

a. General Structure

b. General Operation

c. Definition of Certain Terms

d. Multi-Program Operation

e. Multi-Language Operation

f. Addressing Structure

g. Protection Mechanism

B. Computer System 10110 Information Structure and Mechanisms (FIGS. 102, 103, 104, 105)

a. Introduction (FIG. 102)

b. Process Structures 10210 (FIGS. 103, 104, 105)

1. Procedure Objects (FIG. 103)

2. Stack Mechanisms (FIGS. 104, 105)

3. FURSM 10214 (FIG. 103)

C. Virtual Processor State Blocks and Virtual Process Creation (FIG. 102)

D. Addressing Structures 10220 (FIGS. 103, 106, 107, 108)

1. Objects, UID's, AON's, Names, and Physical Addresses (FIG. 106)

2. Addressing Mechanisms 10220 (FIG. 107)

3. Name Resolution (FIGS. 103, 108)

4. Evaluation of AON Addresses to Physical Addresses (FIG. 107)

E. CS 10110 Protection Mechanisms (FIG. 109)

F. CS 10110 Micro-Instruction Mechanisms (FIG. 110)

G. Summary of Certain CS 10110 Features and Alternate Embodiments.

2. Detailed Description of CS 10110 Major Subsystems (FIGS. 201-206, 207-274)

A. MEM 10110 (FIGS. 201, 206, 207-237)

a. Terminology

b. MEM 10112 Physical Structure (FIG. 201)

c. MEM 10112 General Operation

d. MEM 10112 Port Structure

1. IO Port Characteristics

2. JO Port Characteristics

3. JI Port Characteristics

e. MEM 10112 Control Structure and Operation (FIG. 207)

1. MEM 10112 Control Structure

2. MEM 10112 Control Operation

f. MEM 10112 Operations

g. MEM 10112 Interfaces to JP 10114 and IOS 10116 (FIGS. 209, 210, 211, 204)

1. IO Port 20910 Operating Characteristics (FIGS. 209, 204)

2. JO Port 21010 Operating Characteristics (FIG. 210)

3. JI Port 21110 Operating Characteristics (FIG. 211)

h. MIC 20122 Structure and Operation (FIGS. 207, 212-225)

1. JOPAR 20710, JIPR 20712, IOPAR 20714 and PRMUX 20720 (FIG. 212)

2. Port Control 20716 (FIG. 213)

3. MIC 20122 Control Circuitry (FIGS. 214-237)

a.a. Request Manager 20722 (FIG. 214)

b.b. Trailer Condition Logic 21510 (FIG. 215)

c.c. Miss Control 20726 (FIG. 216)

d.d. Read Queue 20728 (FIG. 217)

e.e. Load Manager 20730 (FIG. 213)

f.f. Bypass Write and Cache Write Back Control 21910 (FIG. 219)

g.g. Write Back Control Logic 22010 (FIG. 220)

h.h. Byte Write Select Logic 22310 (FIG. 223)

i.i. Bypass Write Control 20718 (FIG. 221)

j.j. Memory Cache Usage Logic 22210 (FIG. 222)

k.k. Data Path Steering Logic 22410 (FIG. 224)

l.l. Read Data Handshake Logic 22510 (FIG. 225)

i. FIU 20120 (FIGS. 201, 230, 231)

j. Memory Cache 20116 (FIGS. 232, 233)

1. General Cache Operation (FIG. 233)

2. Memory Cache 20116's Cache 23210 (FIG. 232)

k. Memory Arrays 20112 (FIGS. 234, 235, 236)

l. Bank Controller 20114 (FIG. 237)

B. Fetch Unit 10120 (FIGS. 202, 206, 101, 103, 104, 238)

1. Descriptor Processor 20210 (FIGS. 202, 101, 103, 104, 238, 239)

a. Offset Processor 20218 Structure

b. AON Processor 20216 Structure

c. Length Processor 20220 Structure

d. Descriptor Processor 20218 Operation

a.a. Offset Selector 20238

b.b. Offset Multiplexer 20240 Detailed Structure (FIG. 238)

c.c. Offset Multiplexer 20240 Detailed Operation

a.a.a. Internal Operation

b.b.b. Operation Relative to DESP 20210

e. Length Processor 20220 (FIG. 239)

a.a. Length ALU 20252

b.b. BIAS 20246 (FIG. 239)

f. AON Processor 20216

a.a. AONGRF 20232

b.b. AON Selector 20248

2. Memory Interface 20212 (FIGS. 106, 240)

a.a. Descriptor Trap 20256 and Data Trap 20258

b.b. Name Cache 10226, Address Translation Unit 10228, and Protection Cache 10234 (FIG. 106)

c.c. Structure and Operation of Generalized Cache and NC 10226 (FIG. 240)

d.d. ATU 10228 and PC 10234

3. Fetch Unit Control Logic 20214 (FIG. 202)

a.a. Fetch Unit Control Logic 20214 Overall Structure

b.b. Fetch Unit Control Logic 20214 Operation

a.a.a. Prefetcher 20264, Instruction Buffer 20262, Parser 20264, Operation Code Register 20268, CPC 20270, IPC 20272, and EPC 20274 (FIG. 241)

b.b.b. Fetch Unit Dispatch Table 11010, Execute Unit Dispatch Table 20266, and Operation Code Register 20268 (FIG. 242)

c.c.c. Next Address Generator 24310 (FIG. 243)

c.c. FUCTL 20214 Circuitry for CS 10110 Internal Mechanisms (FIGS. 244-250)

a.a.a. State Logic 20294 (FIGS. 244A-244Z)

b.b.b. Event Logic 20284 (FIGS. 245, 246, 247, 248)

c.c.c. Fetch Unit S-Interpreter Table 11012 (FIG. 249)

d.d.d. Microinstruction Word Formats (FIG. 250)

d.d. CS 10110 Internal Mechanism Control

a.a.a. Return Control Word Stack 10358 (FIG. 251)

b.b.b. Machine Control Block (FIG. 252)

c.c.c. Register Address Generator 20288 (FIG. 253)

d.d.d. Timers 20296 (FIG. 254)

e.e.e. Fetch Unit 10120 Interface to Execute Unit 10122

C. Execute Unit 10122 (FIGS. 203, 255-268)

a. General Structure of Execute Unit 10122

1. Execute Unit I/O 20312

2. Execute Unit Control Logic 20310

3. Multiplier Logic 20314

4. Exponent Logic 20316

5. Multiplier Control 20318

6. Test and Interface Logic 20320

b. Execute Unit 10122 Operation (FIG. 255)

1. Execute Unit Control Logic 20310 (FIG. 255)

a.a. Command Queue 20342

b.b. Command Queue Event Control Store 25514 and Command Queue Event Address Control Store 25516

c.c. Execute Unit S-Interpreter Table 20344

d.d. Microcode Control Decode Register 20346

e.e. Next Address Generator 20340

2. Operand Buffer 20322 (FIG. 256)

3. Multiplier 20314 (FIGS. 257, 258)

a.a. Multiplier 20314 I/O Data Paths and Memory (FIG. 257)

a.a.a. Packed Decimal to Unpacked Decimal Conversion

b.b.b. Container Size Check

c.c.c. Final Result Output Multiplexer 20324

b.b. Multiplier 20314 Arithmetic Operation Logic (FIG. 258)

a.a.a. Multiplier 20314 Internal Data Paths and Multiply/Divide Operations (FIG. 258)

b.b.b. Multiplication, Partial Products

c.c.c. Main Working Register 20372

d.d.d. Multiplier ALU2 20374

e.e.e. Final Result Shifter 20362

f.f.f. Final Result Register 20336

c.c. Multiplier 20314 Arithmetic Operations

a.a.a. Floating Point Operations

b.b.b. Decimal Operations

4. Exponent Logic 20316 and Multiplier Control 20318--Floating Point Operations (FIG. 259)

a.a. Exponent Logic 20316 and Multiplier Control 20318 Structure (FIG. 259)

b.b. Exponent Logic 20316 and Multiplier Control 20318 Operation

5. Test and Interface Logic 20320 (FIGS. 260-268)

a.a. FU 10120/EU 10122 Interface

a.a.a. Loading of Command Queue 20342 (FIG. 260)

b.b.b. Loading of Operand Buffer 20320 (FIG. 261)

c.c.c. Storeback (FIG. 262)

d.d.d. Test Conditions (FIG. 263)

e.e.e. Exception Checking (FIG. 264)

f.f.f. Idle Routine

g.g.g. EU 10122 Stack Mechanisms (FIGS. 265, 266, 267)

h.h.h. Loading of Execute Unit S-Interpreter Table 20344 (FIG. 268)

D. I/O System 10116 (FIGS. 204, 206, 269)

a. I/O System 10116 Structure (FIG. 204)

b. I/O System 10116 Operation (FIG. 269)

1. Data Channel Devices

2. I/O Control Processor 20412

3. Data Mover 20410 (FIG. 269)

a.a. Input Data Buffer 20440 and Output Data Buffer 20442

b.b. Priority Resolution and Control 20444 (FIG. 269)

E. Diagnostic Processor 10118 (FIG. 101, 205)

F. CS 10110 Micromachine Structure and Operation (FIGS. 270-274)

a. Introduction

b. Overview of Devices Comprising FU Micromachine (FIG. 270)

1. Devices Used By Most Microcode

a.a. MOD Bus 10144, JPD Bus 10142, and DB Bus 27021

b.b. Microcode Addressing

c.c. Descriptor Processor 20218 (FIG. 271)

d.d. EU 10122 Interface

2. Specialized Micromachine Devices

a.a. Instruction Stream Reader 27001

b.b. SOP Decoder 27003

c.c. Name Translation Unit 27015

d.d. Memory Reference Unit 27017

e.e. Protection Unit 27019

f.f. KOS Micromachine Devices

c. Micromachine Stacks and Microroutine Calls and Returns (FIGS. 272, 273)

1. Micromachine Stacks (FIG. 272)

2. Micromachine Invocations and Returns

3. Means of Invoking Microroutines

4. Occurrence of Event Invocations (FIG. 273)

d. Programming the Micromachine (FIG. 274)

e. Virtual Micromachines and Monitor Micromachine

1. Virtual Mode

2. Monitor Micromachine

f. Interrupt and Fault Handling

1. General Principles

2. Hardware Interrupt and Fault Handling in CS 10110

3. Monitor Mode: Differential Masking and Hardware Interrupt Handling

g. FU Micromachine and CS 10110 Subsystems

3. Namespace, S-Interpreters and Pointers (FIGS. 301-307, 274)

A. Pointers and Pointer Resolution (FIGS. 301, 302)

a. Pointer Formats (FIG. 301)

b. Pointers in FU 10120 (FIG. 302)

c. Resolutions of Unresolved Pointers by Procedures 602

d. Descriptor to Pointer Conversion

B. Namespace and the S-Interpreters (FIGS. 303-307, 274)

a. Procedure Object 606 Overview (FIG. 303)

b. Resolution of Pointers in Procedure Objects 608

c. Namespace

1. Name Resolution and Evaluation

2. The Name Table (FIG. 304)

3. Architectural Base Pointers (FIGS. 305, 306, 274)

a.a. Resolving and Evaluating Names (FIG. 305)

b.b. Implementation of Name Evaluation and Name Resolve in CS 10110

c.c. Name Cache 10226 Entries (FIG. 306)

d.d. Name Cache 10226 Hits

e.e. Name Cache 10226 Misses

f.f. Flushing Name Cache 10226 (FIG. 274)

g.g. Fetching the Instruction Stream

h.h. Parsing the Instruction Stream

d. The S-Interpreters (FIG. 307)

1. Translating SIP into a Dialect Number (FIG. 307)

2. Dispatching

4. The Kernel Operating System

A. Introduction

a. Operating Systems (FIG. 401)

1. Resources Controlled by Operating Systems (FIG. 402)

2. Resource Allocation by Operating Systems

b. The Operating System in CS 10110

c. Extended Operating System and the Kernel Operating System (FIG. 403)

B. Objects and Object Management (FIG. 404)

a. Objects and User Programs (FIG. 405)

b. UIDs 40401 (FIG. 406)

c. Object Attributes

d. Attributes and Access Control

e. Implementation of Objects

1. Introduction (FIGS. 407, 408)

2. Objects in Secondary Storage 10124 (FIGS. 409, 410)

a.a. Representation of an Object's Contents on Secondary Storage 10124

b.b. LAUD 40903 (FIGS. 411, 412)

c.c. Operations on LAUD 40903

a.a.a. Object Creation and Deletion

b.b.b. Reading and Changing an Object's Attributes

3. Active Objects (FIG. 413)

a.a. UID 40401 to AON 41304 Translation

b.b. Active Object Manager Process 610 (FIG. 414)

c.c. AOT 10712 and Logical Address Reduction (LAR) (FIG. 415)

d.d. AOTE 41306

C. The Access Control System

a. Subjects

b. Domains

c. Access Control Lists

1. Subject Templates (FIG. 416)

2. Primitive Access Control Lists (PACLs)

a.a. Setting and Reading PACLs

b.b. Extended Access Rights and EACLs

c.c. Subjects, Domains, and Subject Templates in the Present Embodiment

d. Acceleration of Access Checking in CS 10110.

1. Subjects and ASN's (FIG. 408)

2. ASTEs 40806 (FIG. 417)

3. Domain Table 41801 and Domain Numbers (FIG. 418)

4. Pure Domains and Pure Subjects

5. Control Attribute Tables

a.a. ANPAT 10920 (FIG. 419)

b.b. ANPAT Entries 41907 (FIG. 420)

c.c. Operations Involving ANPAT 10970

d.d. APAM 10918 and Protection Cache 10234 (FIG. 421)

e.e. Protection Cache 10234 and Protection Checking (FIG. 422)

D. Virtual Memory Management (FIG. 423)

a. Components of the VMM System (FIG. 424)

b. Advantages of the VMM System

c. Detailed Overview of the VMM System (FIG. 425)

d. AON-offset Address 42305 to Frame Number-Displacement Address 42307 Translation (FIG. 426)

e. Implementation of Address Translation

1. The LAT* SIN

2. Searching MHT 10716 (FIG. 427)

3. Page Faults

a.a. VMMEC 42505 and VMMQ 42506 (FIG. 428)

b.b. Page Fault Microcode 42503 (FIGS. 426, 428)

f. VMM PROC 42405

1. MFT 10718 (FIG. 429)

2. VMM Coordinator 42512 (FIGS. 425, 426, 428, 429, 430)

a.a. Request to Send Block 43001 (FIGS. 425, 426, 428, 429, 431)

b.b. Await Event Counters Block 43002 (FIGS. 425, 426, 428, 429, 431)

c.c. Finish I/O Loop 43003 (FIGS. 425, 426, 428, 429, 432)

d.d. Look for Frame Block 43004 (FIGS. 425, 426, 428, 429, 433)

e.e. Process VMMQ Work List Loop Block 43005 (FIGS. 425, 426, 428, 429, 434)

f.f. Process OMQ Loop 43006 (FIGS. 425, 426, 428, 429, 435)

g.g. Frame Cleaner Block 43007 (FIGS. 425, 426, 428, 429, 435)

3. MEM 10112 Frame 42308 Allocation (FIGS. 425, 426, 428, 429, 436, 437, 438)

4. MEM 10112 Frame 42308 Deallocation (FIGS. 425, 426, 428, 429, 436, 439, 440)

E. Processes

a. Introduction (FIG. 402)

1. Processes 610 in CS 10110 (FIG. 447)

2. Synchronization of Processes 610 and Virtual Processors 612

a.a. Event Counters 44801, Await Entries 44804, and Await Tables (FIG. 448, 449)

b.b. Synchronization with Event Counters 44801 and Await Entries 44804

c.c. Event Counter 44801 Operations (FIG. 450)

d.d. Event Counters 44801 and Interrupts

e.e. Event Counters 44801 and System Clocks

f.f. Locks 45101 (FIG. 451)

g.g. Message Queues 45210 (FIG. 452)

3. Virtual Processors 612 (FIG. 453)

a.a. Virtual Processor Management (FIG. 453)

b.b. Virtual Processors 612 and Synchronization (FIG. 454)

b. Implementation of Processes 610

1. Process Object 901 (FIG. 455)

2. Access to Process Objects 901

3. Process Manager Event Counters 44801, Await Tables 44804, and Queues 45210 (FIG. 456)

a.a. PET 44705 (FIGS. 449, 457)

b.b. Process Manager Clock Event Counter 45615 Implementation (FIG. 458)

c.c. Outward Signals Object (OSO) 45409 and Multiplexed Outword Signals Event Counter 45407 (FIG. 459)

d.d. Process Manager Request Queue (PMRQ) 45607 (FIG. 460)

e.e. Queues for Communicating with EOS (FIGS. 456, 461)

4. Operations on Processes 610

a.a. Create Process Procedure 602 (FIG. 455)

b.b. Delete Process Procedure 602 (FIGS. 455, 457)

c.c. Procedures 602 which Set and Read Fields of Process Object 901 (FIG. 455)

d.d. Process-level Operations on Event Counters 44801 and Sequencers 45102 (FIG. 457)

a.a.a. The Process-level Await Operation PM Await (FIGS. 449, 455, 457)

b.b.b. The Process-level Advance Operation PM Advance (FIGS. 449, 455, 457)

c.c.c. Operations on Sequencers 45102

e.e. Operations on a Process Object 901's EACL

c. Implementation of Virtual Processors 612

1. VPSB 614 (FIG. 462)

2. Virtual Processor Management Data Bases (FIG. 463)

a.a. VPIA 46301 (FIG. 464)

b.b. HVPL 46305 and MVPL 45309 (VPLs) (FIG. 465)

c.c. VPAT 45401 (FIG. 466)

3. Operations on Virtual Processors 612

a.a. Request VP (FIGS. 462, 463, 464, 465)

b.b. Release VP (FIGS. 462, 463, 464, 465)

4. Operations on Processes 610 Which Involve Virtual Processors 612

a.a. The Bind Process Operation (FIGS. 455, 462, 463, 464, 465)

b.b. The Unbind Process Operation (FIGS. 455, 462, 463, 464, 465)

c.c. The Run Process Operation (FIGS. 455, 456, 462, 463, 464, 465)

d.d. The Stop Operation (FIGS. 455, 456, 462, 463, 464, 465)

e.e. Killing a Process 610 (FIGS. 455, 456, 462, 463, 464, 465)

5. Virtual Processor-level Synchronization Operations

a.a. The Advance SIN (FIGS. 459, 462, 465, 466)

b.b. The Await SIN (FIGS. 459, 462, 465, 466)

c.c. Virtual Processor-level Synchronization Using the System Clock (FIG. 458)

d.d. Begin Atomic Operation and End Atomic Operation (FIG. 462)

e.e. Suspend (FIG. 462, 465)

f.f. Resume (FIGS. 462, 465)

g.g. KOS Dispatcher Microcode (FIGS. 462, 465)

d. Process 610 Stack Manipulation

1. Introduction to Call and Return

2. Macrostacks (MAS) 502 (FIG. 467)

a.a. MAS Base 10410 (FIG. 468)

b.b. Per-domain Data Area 46853 (FIG. 468)

c.c. MAS Frame 46709 Detail (FIG. 469)

3. SS 504 (FIG. 470)

a.a. SS Base 47001 (FIG. 471)

b.b. SS Frames 47003 (FIG. 471)

a.a.a. Ordinary SS Frame Headers 10514 (FIG. 471)

b.b.b. Detailed Structure of Macrostate 10516 (FIG. 471)

c.c.c. Cross-domain SS Frames 47039 (FIG. 471)

4. Portions of Procedure Object 608 Relevant to Call and Return (FIG. 472)

5. Execution of Mediated Calls

a.a. Mediated Call SINs

b b. Simple Mediated Calls (FIGS. 270, 468, 469, 470, 471, 472)

c.c. Invocations of Procedures 602 Requiring SEBs 46864 (FIGS. 270, 468, 469, 470, 471, 472)

d.d. Cross-Procedure Object Calls (FIGS. 270, 468, 469, 470, 471, 472)

e.e. Cross-Domain Calls (FIGS. 270, 408, 418, 468, 469, 470, 471, 472)

f.f. Failed Cross-Domain Calls (FIGS. 270, 468, 469, 470, 471, 472)

6. Neighborhood Calls (FIGS. 468, 469, 472)

7. Calls from Microcode (FIGS. 270, 468, 469, 470, 471, 472, 473)

8. Terminating Several Invocations

a.a. Lists in MAS Frame 46703 (FIG. 474)

b.b. Implementation of Non-local GOTO (FIG. 474)

a.a.a. Establishing Location to Which Non-local GOTO May Transfer Control (FIG. 474)

b.b.b. Implementation of the Non-local GOTO SIN (FIG. 474)

c.c. Conditions

a.a.a. Establishing Condition Handlers (FIG. 474)

b.b.b. Signallers and the Execution of Condition Handlers (FIGS. 270, 468, 469, 470, 471, 472, 473, 474)

d.d. Crawl Outs (FIGS. 270, 468, 469, 470, 471, 472, 473, 474)

9. Interrupts

a.a. Establishing and Clearing Interrupts (FIGS. 455, 457, 468)

b.b. Interrupt Levels (FIGS. 455, 457, 468)

c.c. Processing Interrupts (FIGS. 455, 457, 468)

F. Debugging Aids in CS 10110

a. Overview of Debugging in CS 10110

b. Debugging Features Common to All CSs 10110

1. Trace Tables (FIG. 475)

2. Trace Table Pointer 47502

3. Information Returned to the Debugger by Trace Event Microcode

4. Macrostate Available to the Debugger

c. Implementation of Debugger Operations in the Present Embodiment

1. Enabling and Disabling Trace Event Signals (FIGS. 273, 475)

2. Debugging Operations (FIGS. 273, 475) Appendix A.

INTRODUCTORY OVERVIEW

The following overview will first briefly describe the overall physical structure and operation of a presently preferred embodiment of a digital computer system incorporating the present invention. Then certain operating features of that computer system will be individually described. Next, overall operation of the computer system will be described in terms of those individual features. Finally, the computer system's implementation will be described in further detail.

A. Hardware Overview (FIG. 1)

Referring to FIG. 1, a block diagram of Computer System (CS) 101 incorporating the present invention is shown. Major elements of CS 101 are I/O System (IOS) 116, Memory (MEM) 112, and Job Processor (JP) 114. JP 114 is comprised of a Fetch Unit (FU) 120 and an Execute Unit (EU) 122. CS 101 may also include a Diagnostic Processor (DP), not shown or described in the instant description.

Referring first to IOS 116, a primary function of IOS 116 is control of transfer of information between MEM 112 and the outside world. Information is transferred from MEM 112 to IOS 116 through IOM Bus 130, and from IOS 116 to MEM 112 through MIO Bus 129. IOMC Bus 131 is comprised of bi-directional control signals coordinating operation of MEM 112 and IOS 116. IOS 116 also has an interface to FU 120 through IOJP Bus 132. IOJP Bus 132 is a bi-directional control bus comprised essentially of two interrupt lines. These interrupt lines allow FU 120 to indicate to IOS 116 that a request for information by FU 120 has been placed in MEM 112, and allows IOS 116 to inform FU 120 that information requested by FU 120 has been transferred into a location in MEM 112. MEM 112 is CS 101's main memory and serves as the path for information transfer between the outside world and JP 114. MEM 112 provides instructions and data to FU 120 and EU 122 through Memory Output Data (MOD) Bus 140 and receives information from FU 120 and EU 122 through Job Processor Data (JPD) Bus 142. FU 120 submits read and write requests to MEM 112 through Physical Descriptor (PD) Bus 146.

JP 114 is CS 101's CPU and, as described above, is comprised of FU 120 and EU 122. A primary function of FU 120 is executing operations of user's programs. As part of this function, FU 120 controls transfer of instructions and data from MEM 112
and transfer of results of JP 114 operations back to MEM 112. FU 120 also performs operating system type functions, and is capable of operating as a complete, general purpose CPU. EU 122 is primarily an arithmetic and logic unit provided to relieve FU
120 of certain arithmetic operations. FU 120, however, is capable of performing EU 122 operations. In alternate embodiments of CS 101, EU 122 may be provided only as an option for users having particular arithmetic requirements. Coordination of FU 120
and EU 122 operations is accomplished through FU/EU (FUEU) Bus 148, which includes bi-directional control signals and mutual interrupt lines. As described further below, both FU 120 and EU 122 contain register file arrays referred to respectively as CRF and ERF, in addition to registers associated with, for example, ALUs.

A primary feature of CS 101 is that IOS 116, MEM 112, FU 120 and EU 122 each contain separate and independent microinstruction control, so that IOS 116, MEM 112, and EU 122 operate asynchronously under the general control of FU 120. EU 122, for example, may execute a complex arithmetic operation upon receipt of data and a single, initial command from FU 120.

Having briefly described the overall structure and operation of CS 101, certain features of CS 101 will be individually further described next below.

B. Individual Operating Features (FIGS. 2,3,4,5,6)

1. Addressing (FIG. 2)

Referring to FIG. 2, a diagramic representation of portions of CS 101's addressing structure is shown. CS 101's addressing structure is based upon the concept of Objects. An Object may be regarded as a container for holding a particular type of information. For example, one type of Object may contain data while another type of Object may contain instructions or procedures, such as a user program. Still another type of Object may contain microcode. In general, a particular Object may contain only one type or class of informtion. An Object may, for example, contain up to 2.sup.32 bits of information, but the actual size of a particular Object is flexible. That is, the actual size of a particular Object will increase as information is written into that Object and will decrease as information is taken from that Object. In general, information in Objects is stored sequentially, that is without gaps.

Each Object which can ever exist in any CS 101 system is uniquely identified by a serial number referred to as a Unique Identifier (UID). A UID is a 128 bit value comprised of a serial number dependent upon, for example, the particular CS 101
system and user, and a time code indicating time of creation of that Object. UIDs are permanently assigned to Objects, no two Objects may have the same UID, and UIDs may not be reused. UIDs provide an addressing base common to all CS 101 systems which may ever exist, through which any Object ever created may be permanently and uniquely identified.

As described above, UIDs are 128 bit values and are thus larger than may be conveniently handled in present embodiments of CS 101. In each CS 101, therefore, those Objects which are active (currently being used) in that system are assigned 14
bit Active Object Numbers (AONs). Each Object active in that system will have a unique AON. Unlike UIDs, AONs are only temporarily assigned to particular Objects. AONs are valid only within a particular CS 101 and are not unique between systems. An Object need not physically reside in a system to be assigned an AON, but can be active in that system only if it has been assigned an AON.

A particular bit within a particular Object may be identified by means of a UID address or an AON address. In CS 101, AONs and AON addresses are valid only within JP 114 while UIDs and UID addresses are used in MEM 112 and elsewhere. UID and AON addresses are formed by appending a 32 bit Offset (0) field to that Object's UID or AON. O fields indicate offset, or location, of a particular bit relative to the start of a particular Object.

Segments of information (sequences of information bits) within particular Objects may be identified by means of descriptors. A UID descriptor is formed by appending a 32 bit Length (L) field of a UID address. An AON, or logical descriptor is formed by appending a 32 bit L field to an AON address. L fields identify length of a segment of information bits within an Object, starting from the information bit identified by the UID or AON address. In addition to length information, UID and logical descriptors also contain Type fields containing information regarding certain characteristics of the information in the information segment. Again, AON based descriptors are used within JP 114, while UID based descriptors are used in MEM 112.

Referring to FIGS. 1 and 2 together, translation between UID addresses and descriptors and AON addresses and descriptors is performed at the interface between MEM 112 and JP 114. That is, addresses and descriptors within JP 114 are in AON form while addresses and descriptors in MEM 112, IOS 116, and the external world are in UID form. In other embodiments of CS 101 using AONs, transformation from UID to AON addressing may occur at other interfaces, for example at the IOS 116 to MEM 112
interface, or at the IOS 116 to external world interface. Other embodiments of CS 101 may use UIDs throughout, that is not use AONs even in JP 114.

Finally, information within MEM 112 is located through MEM 112 Physical Addresses identifying particular physical locations within MEM 112's memory space. Both IOS 116 and JP 114 address information within MEM 112 by providing physical addresses to MEM 112. In the case of physical addresses provided by JP 114, these addresses are referred to as Physical Descriptors (PDs). As described below, JP 114 contains circuitry to translate logical descriptors into physical descriptors.

2. S-Language Instructions and Namespace Addressing (FIG. 3)

CS 101 is both an S-Language machine and a Namespace machine. That is, operations to be executed by CS 101 are expressed as S-Language Operations (SOPs) while operands are identified by Names. SOPs are of a lower, more detailed, level than user language instructions, for example FORTRAN and COBOL, but of a higher level than conventional machine language instructions. SOPs are specific to particular user languages rather than a particular embodiment of CS 101, while conventional machine language instructions are specific to particular machines. SOPs are in turn interpreted and executed by microcode. There will be an S-Language Dialect, a set of SOPs, for each user languages. CS 101, for example, may have SOP Dialects for COBOL, FORTRAN, and SPL. A particular distinction of CS 101 is that all SOPs are of a uniform, fixed length, for example 16 bits. CS 101 may generally contain one or more sets of microcode for each S-Language Dialect. These microcode Dialect Sets may be completely distinct, or may overlap where more than one SOP utilizes the same microcode.

As stated above, in CS 101 all operands are identified by Names, which are 8, 12, or 16 bit numbers. CS 101 includes one or more "Name Tables" containing an Entry for each operand Name appearing in programs currently being executed Each Name Table Entry contains information describing the operand referred to by a particular Name, and the directions necessary for CS 101 to translate that information into a corresponding logical descriptor. As previously described, logical descriptors may then be transformed into physical descriptors to read and write operands from or to MEM 112. As described above, UIDs are unique for all CS 101 systems and AONs are unique within individual CS 101 systems. Names, however, are unique only within the context of a user's program. That is, a particular Name may appear in two different user's programs and, within each program, will have different Name Table Entries and will refer to different operands.

CS 101 may thereby be considered as utilizing two sets of instructions. A first set is comprised of SOPs, that is instructions selecting algorithms to be executed. The second set of instructions are comprised of Names, which may be regarded as entry points into tables of instructions for making references regarding operands.

Referring to FIG.3, a diagramic representation of CS 101 instruction stream is shown. A typical SIN is comprised of an SOP and may include one or more Names referring to operands. SOPs and Names allow user's programs to be expressed in very compact code. Fewer SOPs than machine language instructions are required to express a user's program. Also, use of SOPs allows easier and simpler construction of compilers, and facilitates adaption of CS 101 systems to new user languages. In addition, use of Names to refer to operands means that SOPs are independent of the form of the operands upon which they operate. This in turn allows for more compact code in expressing user programs in that SOPs specifying operations dependent upon operand form are not required.

3. Architectural Base Pointer Addressing

As will be described further below, a user's program residing in CS 101 will include one or more Objects. First, a Procedure Object contains at least the SINs of the user's programs and a Name Table containing entries for operand Names of the program. The SINs may include references, or calls, to other Procedure Objects containing, for example, procedures available in common to many users. Second, a Static Data Area may contain static data, that is data having an existence for at least a single execution of the program. And third, a Macro-stack, described below, may contain local data, that is data generated during execution of a program. Each Procedure Object, the Static Data Area and the Macro-stack are individual Objects identified by UIDs and AONs and addressable through UID and AON addresses and descriptors.

Locations of information within a user's Procedure Objects, Static Data Area, and Macro-stack are expressed as offsets from one of three values, or base addresses, referred to as Architectural Base Pointers (ABPs). For example, location information in Name Tables is expressed as offsets from one of the ABPs. ABPs may be expressed as previously described.

The three ABPs are the Frame Pointer (FP), the Procedure Base Pointer (PBP), and the Static Data Pointer (SDP). Locations of data local to a procedure, for example in the procedure's Macrostack, are described as offsets from FP. Locations of non-local data, that is Static Data, are described as offsets from SDP. Locations of SINs in Procedure Objects are expressed as offsets from PBP; these offsets are determined as a Program Counter (PC) value. Values of the ABPs vary during program execution and are therefore not provided by the compiler converting a user's high level language program into a program to be executed in a CS 101 system. When the program is executed, CS 101 provides the proper values for the ABPs. When a program is actually being executed, the ABP's values are stored in FU 120's GRF.

Other pointers are used, for example, to identify the top frame of CS 101's Secure Stack (a microcode level stack described below) or to identify the microcode Dialect currently being used in execute the SINs of a procedure. These pointers are similar to FP, SDP, and PBP.

4. Stack Mechanisms (FIGS. 4-5)

Referring to FIG. 4 and 4A, diagramic representations of various control levels and stack mechanisms of, respectively, conventional machines and CS 101, are shown. Referring first to FIG. 4, top level of control is provided by User Language Instructions 402, for example in FORTRAN or COBOL. User Language Instructions 402 are converted into a greater number of more detailed Machine Language Instructions 404, used within a machine to execute user's programs. Within the machine, Machine Language Instructions 404 are interpreted and executed by Microcode Instructions 406, that is sequences of microinstructions which in turn directly control Machine Hardware 408. Some conventional machines may include a Stack Mechanism 410 used to save current machine state, that is current microinstruction and contents of various machine registers, if a current Machine Language Instruction 404 cannot be executed or is interrupted. In general, machine state on the microcode and hardware level is not saved. Execution of a current Machine Language Instruction 404 is later resumed at start of the microinstruction sequence for executing that Machine Language Instruction 404.

Referring to FIG. 4A, top level control in CS 101 is by User Language Instructions 412 as in a conventional machine. In CS 101, however, User Language Instructions 412 are translated into SINs 414 which are of a higher level than conventional machine language instructions. In general, a single User Language Instruction 412 is transformed into at most two or three SINs 414, as opposed to an entire sequence of conventional Machine Language Instructions 404. SINs 414 are interpreted and executed by Microcode Instructions 416 (sequences of microinstructions) which directly control CS 101 Hardware 418. CS 101 includes a Macro-stack Mechanism (MAS) 420, at SINs 414 level, which is comparable to but different in construction and operation from a conventional Machine Language Stack Mechanism 410. CS 101 also includes Micro-code Stack Mechanisms 422 operating at Microcode 416 level, so that execution of an interrupted microinstruction of a microinstruction sequence may be later resumed with the particular microinstruction which was active at the time of the interrupt. CS 101 is therefore more efficient in handling interrupts in that execution of microinstruction sequences is resumed from the particular point that a microinstruction sequence was interrupted, rather than from the beginning of that sequence. As will be described further below, CS 101's Micro-code Stack Mechanisms 422 on microcode level is effectively comprised of two stack mechanisms. The first stack is Micro-instruction Stack (MIS) 424 while the second stack is referred to as Monitor Stack (MOS) 426. CS 101 SIN Microcode 428 and MIS 424 are primarily concerned with execution of SOPs of user's programs. Monitor Microcode 430 and MOS 426 are concerned with operation of certain CS 101 internal functions.

Division of CS 101's microcode stacks into an MIS 424 and a MOS 426 illustrates a further feature of CS 101. In conventional machines, monitor functions may be performed by a separate CPU operating in conjunction with the machine's primary CPU. In CS 101, a single hardware CPU is used to perform both functions with actual execution of both functions performed by separate groups of microcode. Monitor microcode operations may be initiated either by certain SINs 414 or by control signals generated directly by CS 101's Hardware 418. Invocation of Monitor Microcode 430 by Hardware 418 generated signals insures that CS 101's monitor functions may always be invoked.

Referring to FIG. 5, a diagramic representation of CS 101's stack mechanisms for a single user's program, or procedure, is shown. Basically, and with exception of MOS 426, CS 101's stacks reside in MEM 112 with certain portions of those stacks accelerated into FU 120 and EU 122 to enhance speed of operation.

Certain areas of MEM 112 storage space are set aside to contain Macro-Stacks (MASs) 502, stack mechanisms operating on the SINs level, as described above. Other areas of MEM 112 are set aside to contain Secure Stack (SS) 504, operating on the microcode level, as described above and of which MIS 424 is a part.

As described further below, both FU 120 and EU 122 contain register file arrays, referred to respectively as GRF and ERF, in addition to registers associated with, for example, ALUs. Referring to FU 120, shown therein is FU 120's GRF 506. GRF
506 is horizontally divided into three areas. A first area, referred to as General Registers (GRs) 508 may in general be used in the same manner as registers in a conventional machine. A second area of GRF 506 is Micro-Stack (MIS) 424, and is set aside to contain a portion of a Process's SS 504. A third portion of GRF 506 is set aside to contain MOS 426. Also indicated in FU 120 is a block referred to as Microcode Control State (mCS) 510. mCS 510 represents registers and other FU 120 hardware containing current operating state of FU 120 on the microinstruction and hardware level. mCS 510 may include, for example, the current microinstruction controlling operation of FU 120.

Referring to EU 122, indicated therein is a first block referred to as Execute Unit State (EUS) 512 and a second block referred to as SOP Stack 514. EUS 512 is similar to mCS 510 in FU 120 and includes all registers and other EU 122 hardware containing information reflecting EU 122's current operating state. SOP Stack 518 is a portion of EU 122's ERF 516 which has been set aside as a stack mechanism to contain a portion of a process's SS 504 pertaining to EU 122 operations.

Considering first MASs 502, as stated above MASs 502 operate generally upon the SINs level. MASs 502 are used in general to store current state of a process's (defined below) execution of a user's program.

Referring next to MIS 424, in a present embodiment of CS 101 that portion of GRF 506 set aside to contain MIS 424 may have a capacity of eight stack frames. That is, up to 8 microinstruction level interrupts or calls pertaining to execution of a user's program may be stacked within MIS 424. Information stored in MIS 424 stack frames is generally information from GR 508 and MCS 510. MIS 424 stack frames are transferred between MIS 424 and SS 504 such that at least one frame, and no more than 8
frames, of SS 504 reside in GRF 506. This insures that at least the top-most frames of a process's SS 504 are present in FU 120, thereby enhancing speed of operation of FU 120 by providing rapid access to those top frames. SS 504, residing in MEM 112, may contain, for all practical purposes, an unlimited number of frames so that MIS 424 and SS 504 appear to a user to be effectively an infinitely deep stack.

MOS 426 resides entirely in FU 120 and, in a present embodiment of CS 101, may have a capacity of 8 stack frames. A feature of CS 101 operation is that CS 101 mechanisms for handling certain events or interrupts should not rely in its operation upon those portions of CS 101 whose operation has resulted in those faults or interrupts. Among events handled by CS 101 monitor microcode, for example, are MEM 112 page faults. An MEM 112 page fault occurs whenever FU 120 makes a reference to data in MEM 112 and that data is not in MEM 112. Due to this and similar operations, MOS 426 resides entirely in FU 120 and thus does not rely upon information in MEM 112.

As described above, GRs 508, MIS 424, and MOS 426 each reside in certain assigned portions of GRF 506. This allows flexibility in modifying the capacity of GRs 508, MIS 424, and MOS 426 as indicated by experience, or to modify an individual CS
101 for particular purposes.

Referring finally to EU 122, EUS 512 is functionally a part of a process's SS 504. Also as previously described, EU 122 performs arithmetic operations in response to SINs and may be interrupted by FU 120 to aid certain FU 120 operations. EUS
512 allows stacking of interrupts. For example, FU 120 may first interrupt an arithmetic SOP to request EU 122 to aid in evaluation of a Name Table Entry. Before that first interrupt is completed, FU 120 may interrupt again, and so on.

SOP Stack 514, is a single frame stack for storing current state of EU 122 when an interrupt interrupts execution of an arithmetic SOP. An interrupted SOP's state is transferred into SOP Stack 514 and the interrupt begins execution in EUS 512. Upon occurrence of a second interrupt (before the first interrupt is completed) EU's first interrupt state is transferred from EUS 512 to a stack frame in SS 504, and execution of the second interrupt begins in EUS 512. If a third interrupt occurs before completion of second interrupt, EU's second interrupt state is transferred from EUS 512 to another stack frame in SS 504 and execution of the third interrupt is begun in EUS 512; and so on. EUS 512 and SS 504 thus provide an apparently infinitely deep microstack for EU 122. Assuming that the third interrupt is completed, state of second interrupt is transferred from SS 504 to EUS 512 and execution of second interrupt resumed. Upon completion of second interrupt, state of first interrupt is transferred from SS 504 to EUS 512 and completed. After completion of first interrupt, state of the original SOP is transferred from SOP Stack 514 to EUS 512 and execution of that SOP resumed.

C. Procedure Processes, and Virtual Processors (FIG. 6)

Referring to FIG. 6, a diagramic representation of procedures, processes, and virtual processes is shown. As described above, a user's program to be executed is compiled to result in a Procedure 602. A Procedure 602 includes a User's Procedure Object 604 containing the SOPs of the user's program and a Name Table containing Entries for operand Names of the user's program, and a Static Data Area 606. A Procedure 602 may also include other Procedure Objects 608, for example utility programs available in common to many users. In effect, a Procedure 602 contains the instructions (procedures) and data of a user's program.

A Process 610 includes, as described above, a Macro-Stack (MAS) 502 storing state of execution of a user's Procedure 602 at the SOP level, and a Secure Stack (SS) 504 storing state of execution of a user's Procedure 602 at the microcode level. A Process 610 is associated with a user's Procedure 602 through the ABPs described above and which are stored in the MAS 502 of the Process 610. Similarly, the MAS 502 and SS 504 of a Process 610 are associated through non-architectural pointers, described above. A Process 610 is effectively a body of information linking the resources, hardware, microcode, and software, of CS 101 to a user's Procedure 602. In effect, a Process 610 makes the resources of CS 101 available to a user's Procedure
602 for executing of that Procedure 602. CS 101 is a multi-program machine capable of accommodating up to, for example, 128 Processes 610 concurrently. The number of Processes 610 which may be executed concurrently is determined by the number of Virtual Processors 612 of CS 101. There may be, for example, up to 16 Virtual Processors 612.

As indicated in FIG. 6, a Virtual Processor 612 is comprised of a Virtual Processor State Block (VPSB) 614 associated with the SS 504 of a Process 612. A VPSB 614 is, in effect, a body of information accessible to CS 101's operating system and through which CS 101's operating system is informed of, and provided with access to, a Process 610 through that Process 610's SS 504. A VPSB 614 is associated with a particular Process 610 by writing information regarding that Process 610 into that VPSB
614. CS 101's operating system may, by gaining access to a Process 610 through an associated UPSP 614, read information, such as ABP's, from that Process 610 to FU 120, thereby swapping that Process 610 onto FU 120 for execution. It is said that a Virtual Processor 612 thereby executes a Process 610; a Virtual Processor 612 may be regarded therefor, as a processor having "Virtual", or potential, existence which becomes "real" when its associated Process 610 is swapped into FU 120. In CS 101, as indicated in FIG. 6, only one Virtual Processor 612 may execute on FU 120 at a time and the operating system selects which Virtual Processor 612 will excecute on FU 120 at any given time. In addition, CS 101's operating system selects which Processes
610 will be associated with the available Virtual Processors 612.

Having briefly described certain individual structural and operating features of CS 101, the overall operation of CS 101 will be described in further detail next below in terms of these individual features.

D. CS 101 Overall Structure and Operation (FIGS. 7, 8, 9, 10, 11, 12, 13, 14, 15)

1. Introduction (FIG. 7)

As indicated in FIG. 7, CS 101 is a multiple level system wherein operations in one level are generally transparent to higher levels. User 701 does not see the S-Language, addressing, and protection mechanisms defined at Architectural Level 708. Instead, he sees User Interface 709, which is defined by Compilers 702, Binder 703, and Extended (high level) Operating System (EOS) 704. Compilers 702 translate high-level language code into SINs and Binder 703 translates symbolic Names in programs into UID-offset addresses.

As FIG. 7 shows, Architectural Level 708 is not defined by FU 120 Interface 711. Instead, the architectural resources level are created by S-Language interpreted SINs when a program is executed; Name Interpreter 715 operates under control of S-Language Interpreters 705 and translates Names into logical descriptors. In CS 101, both S-Language Interpreters 705 and Name Interpreter 715 are implemented as microcode which executes on FU 120. S-Language Interpreters 705 may also use EU 122 to perform calculations. A Kernel Operating System (KOS) provides CS 101 with UID-offset addressing, objects, access checking, processes, and virtual processors, described further below. KOS has three kinds of components: KOS Microcode 710, KOS Software
706, and KOS Tables in MEM 112. KOS 710 components are microcode routines which assist FU 120 in performing certain required operations. Like other high-level language routines, KOS 706 components contain SINs which are interpreted by S-Interpreter Microcode 705. Many KOS High-Level Language Routines 706 are executed by special KOS processes; others may be executed by any process. Both KOS High-Level Language Routines 706 and KOS Microcode 710 manipulate KOS Tables in MEM 112.

FU 120 Interface 711 is visible only to KOS and to S-Interpreter Microcode 705. For the purposes of this discussion, FU 120 may be seen as a processor which contains the following main elements:

A Control Mechanism 725 which executes microcode stored in Writable Control Store 713 and manipulates FU 120 devices as directed by this microcode.

A GRF 506 containing registers in which data may be stored.

A Processing Unit 715.

All microcode which executes on FU 120 uses these devices; there is in addition a group of devices for performing special functions; these devices are used only by microcode connected with those functions. The microcode, the specialized devices, and sometimes tables in MEM 112 make up logical machines for performing certain functions. These machines will be described in detail below.

In the following, each of the levels illustrated in FIG. 7 will be discussed in turn. First, the components at User Interface 709 will be examined to see how they translate user programs and requests into forms usable by CS 101. Then the components below the User Interface 709 will be examined to see how they create logical machines for performing CS 101 operations.

2. Compilers 702 (FIG. 7)

Compilers 702 translate files containing the high-level language code written by User 701 into Procedure Objects 608. Two components of a Procedure Object 608 are code (SOPs) and Names, previously described. SOPs represent operations, and the Names represent data. A single SIN thus specifies an operation to be performed on the data represented by the Names.

3. Binder 703 (FIG. 7)

In some cases, Compiler 702 cannot define locations as offsets from an ABP. For example, if a procedure calls a procedure contained in another procedure object, the location to which the call transfers control cannot be defined as an offset from the PBP used by the calling procedure. In these cases, the compiler uses symbolic Names to define the locations. Binder 703 is a utility which translates symbolic Names into UID-offset addresses. It does so in two ways: by combining separate Procedure Objects 608 into a single large Procedure Object 608, and then redefining symbolic Names as offsets from that Procedure Object 608's ABPs, or by translating symbolic Names when the program is executed. In the second case, Binder 703 requires assistance from EOS 704.

4. EOS 704 (FIG. 7)

EOS 704 manages the resources that User 701 requires to execute his programs. From User 701's point of view, the most important of these resources are files and processes. EOS 704 creates files by requesting KOS to create an object and then mapping the file onto the object. When a User 701 performs an operation on a file, EOS 704 translates the file operation into an operation on an object. KOS creates them at EOS 704's request and makes them available to EOS 704, which in turn makes them available to User 701. EOS 704 causes a process to execute by associating it a Virtual Processor 612. In logical terms, a Virtual Processor 612 is the means which KOS provides EOS 704 for executing Processes 610. As many Processes 610 may apparently execute simultaneously in CS 101 as there are Virtual Processors 612. The illusion of simultaneous execution is created by multiplexing JP 114 among the Virtual Processors; the manner in which Processes 610 and Virtual Processors 610 are implemented will be explained in detail below.

5. KOS and Architectural Interface 708 (FIG. 7)

S-Interpreter Microcode 705 and Name Interpreter Microcode 715 require an environment provided by KOS Microcode 710 and KOS Software 706 to execute SINs. For example, as previously explained, Names and program locations are defined in terms of ABPs whose values vary during execution of the program. The KOS environment provides values for the ABPs, and therefore makes it possible to interpret Names and program locations as locations in MEM 112. Similarly, KOS help is required to transform logical descriptors into references to MEM 112 and to perform protection checks.

The environment provided by KOS has the following elements:

A Process 610 which contains the state of an execution of the program for a given User 701.

A Virtual Processor 612 which gives the Process 610 access to JP 114.

An Object Management System which translates UIDs into values that are usable inside JP 114.

A Protection System which checks whether a Process 610 has the right to perform an operation on an Object.

A Virtual Memory Management System which moves those portions of Objects which a Process 610 actually references from the outside world into MEM 112 and translates logical descriptors into physical descriptors.

In the following, the logical properties of this environment and the manner in which a program is executed in it will be explained.

6. Processes 610 and Virtual Processors 612 (FIG. 8)

Processes 610 and Virtual Processors 612 have already been described in logical terms; FIG. 8 gives a high-level view of their physical implementation.

FIG. 8 illustrates the relationship between Processes 610, Virtual Processors 612, and JP 114. In physical terms, a Process 610 is an area of MEM 112 which contains the current state of a user's execution of a program. One example of such state is the current values of the ABPs and a Program Counter (PC). Given the current value of the PBP and the PC, the next SOP in the program can be executed; similarly, given the current values of SDP and FP, the program's Names can be correctly resolved. Since the Process 610 contains the current state of a program's execution, the program's physical execution can be stopped and resumed at any point. It is thus possible to control program execution by means of the Process 610.

As already mentioned, a Process 610's execution proceeds only when KOS has bound it to a Virtual Processor 612, that is, an area of MEM 112 containing the state required to execute microinstructions on JP 114 hardware. The operation of binding is simply a transfer of Process 610 state from the Process 610's area of MEM 112 to a Virtual Processor 612's area of MEM 112. Since binding and unbinding may take place at any time, EOS 704 may multiplex Processes 610 among Virtual Processors 612. In FIG. 8, there are more Processes 610 than there are Virtual Processors 612. The physical execution of a Process 610 on JP 114 takes place only while the Process 610's Virtual Processor 612 is bound to JP 114, i.e., when state is transferred from Virtual Processor 612's area of MEM 112 to JP 114's registers. Just as EOS 704 multiplexes Virtual Processors 612 among Processes 610, KOS multiplexes JP 114 among Virtual Processors 612. In FIG. 8, only one Process 610 is being physically executed. The means by which JP 114 is multiplexed among Virtual Processors 612 will be described in further detail below.

7. Processes 610 and Stacks (FIG. 9)

In CS 101 systems, a Process 610 is made up of six Objects: one Process Object 901 and Five Stack Objects 902 to 906. FIG. 9 illustrates a Process 610. Process Object 901 contains the information which EOS 704 requires to manage the Process
610. EOS 704 has no direct access to Process Object 901, but instead obtains the information it needs by means of functions provided to it by KOS 706, 710. Included in the information are the UIDs of Stack Objects 902 through 906. Stack Objects 902 to
906 contain the Process 610's state.

Stack Objects 902 through 905, are required by CS 101's domain protection method and comprise Process 610's MAS 502. Briefly, a domain is determined in part by operations performed when a system is operating in that domain. For example, the system is in EOS 704 domain when executing EOS 704 operations and in KOS 706, 710 domain when executing KOS 706, 710 operations. A Process 610 must have one stack for each domain it enters. In the present embodiment, the number of domains is fixed at four, but alternate embodiments may allow any number of domains, and correspondingly, any number of Stack Objects. Stack Object 906 comprises Process 610's Secure Stack 504 and is required to store state which may be manipulated only by KOS 706, 710.

Each invocation made by a Process 610 results in the addition of frames to Secure Stack 504 and to Macro-Stack 502. The state stored in the Secure Stack 504 frame includes the macrostate for the invocation, the state required to bind Process 610
to a Virtual Processor 612. The frame added to Macro-Stack 502 is placed in one of Stack Objects 902 through 905. Which Stack Objects 902 to 905 gets the frame is determined by the invoked procedure's domain of execution.

FIG. 9 shows the condition of a Process 610's MAS 502 and Secure Stack 504 after the Process 610 has executed four invocations. Secure Stack 504 has one frame for each invocation; the frames of Process 610's MAS 502 are found in Stack Objects
902, 904, and 905. As revealed by their locations, Frame 1 is for an invocation of a routine with KOS 706, 710 domain of execution, Frame 2 for an invocation of a routine with the EOS 704 domain of execution, and Frames 3 and 4 for invocations of routines with the User domain of execution. Process 610 has not yet invoked a routine with the Data Base Management System (DBMS) domain of execution. The frames in Stack Objects 902 through 905 are linked together, and a frame is added to or removed from Secure Stack 504 every time a frame is added to Stack Objects 902 through 905. MAS 502 and Secure Stack 504 thereby function as a single logical stack even though logically contained in five separate Objects.

8. Processes 610 and Calls (FIGS. 10, 11)

In the CS 101, calls and returns are executed by KOS 706, 710. When KOS 706, 710 performs a call for a process, it does the following:

It saves the calling invocation's macrostate in the top frame of Secure Stack 504 (FIG. 9).

It locates the procedure whose Name is contained in the call. The location of the first SIN in the procedure becomes the new PBP.

Using information contained in the called procedure, KOS 706, 710 creates a new MAS 502 frame in the proper Stack Object 902 through 905 and a new Secure Stack 504 frame in Secure Stack 504. FP is updated to point to the new MAS 502. If necessary, SDP is also updated.

Once the values of the ABPs have been updated, the PC is defined, Names can be resolved, and execution of the invoked routine can commence. On a return from the invocation to the invoking routine, the stack frames are deleted and the ABPs are set to the values saved in the invoking routine's macrostate. The invoking routine then continues execution at the point following the invocation.

A Process 610 may be illustrated in detail by putting the FORTRAN statement A+B into a FORTRAN routine called EXAMPLE and invoking it from another FORTRAN routine named CALLER. To simplify the example, it is assumed that CALLER and EXAMPLE both have the same domain of execution. The parts of EXAMPLE which are of interest look like this:

SUBROUTINE EXAMPLE (C)

INTEGER X,C

INTEGER A,B

...

A=B

...

RETURN

END

The new elements are a formal argument, C, and a new local variable, X. A formal argument is a data item which receives its value from a data item used in the invoking routine. The formal argument's value thus varies from invocation to invocation. The portions of INVOKER which are of interest look like this:

SUBROUTINE INVOKER

INTEGER Z

...

CALL EXAMPLE (Z)

...

END

The CALL statement in INVOKER specifies the Name of the subroutine being invoked and the actual arguments for the subroutine's formal arguments. During the invocation, the subroutine's formal arguments take on the values of the actual arguments. Thus, during the invocation specified by this CALL statement, the formal argument C will have the value represented by the variable Z in INVOKER.

When INVOKER is compiled, the compiler produces a CALL SIN corresponding to the CALL statement. The CALL SIN contains a Name representing a pointer to the beginning of the called routine's location in a procedure object and a list of Names representing the call's actual arguments. When CALL is executed, the Names are interpreted to resolve the SIN's Names as previously described, and KOS 710 microcode to perform MAS 502 and Secure Stack 504 operations.

FIG. 10 illustrates the manner in which the KOS 710 call microcode manipulates MAS 502 and Secure Stack 504. FIG. 10 includes the following elements:

Call Microcode 1001, contained in FU 120 Writable Control Store 1014.

PC Device 1002, which contains part of macrostate belonging to the invocation of INVOKER which is executing the CALL statement.

Registers in FU Registers 1004. Registers 1004 contents include the remainder of macrostate and the descriptors corresponding to Names for EXAMPLE's location and the actual argument Z.

Procedure Object 1006 contains the entries for INVOKER and EXAMPLE, their Name Tables, and their code.

Macro-Stack Object 1008 (MAS 502) and Secure Stack Object 1010 (Secure Stack 504) contain the stack frames for the invocations of INVOKER and EXAMPLE being discussed here. EXAMPLE's frame is in the same Macro-Stack object as INVOKER's frame because both routines are contained in the same Procedure Object 1006, and therefore have the same domain of execution.

KOS Call Microcode 1001 first saves the macrostate of INVOKER's invocation on Secure Stack 504. As will be discussed later, when the state is saved, KOS 706 Call Microcode 1001 uses other KOS 706 microcode to translate the location information contained in the macrostate into the kind of pointers used in MEM 112. Then Microcode 1001 uses the descriptor for the routine Name to locate the pointer to EXAMPLE's entry in Procedure Object 1006. From the entry, it locates pointers to EXAMPLE's Name Table and the beginning of EXAMPLE's code. Microcode 1001 takes these pointers, uses other KOS 706 microcode to translate them into descriptors, and places the descriptors in the locations in Registers 1004 reserved for the values of the PBP and NTP. It then updates the values contained in PC Device 1002 so that when the call is finished, the next SIN to be executed will be the first SIN in EXAMPLE.

CALL Microcode 1001 next constructs the frames for EXAMPLE on Secure Stack 504 and Macro-Stack 502. This discussion concerns itself only with Frame 1102 on Macro-Stack 502. FIG. 11 illustrates EXAMPLE's Frame 1102. The size of Frame 1102 is determined by EXAMPLE's local variables (X, A, and B) and formal arguments (C). At the bottom of Frame 1102 is Header 1104. Header 1104 contains information used by KOS 706, 710 to manage the stack. Next comes Pointer 1106 to the location which contains the value represented by the argument C. In the invocation, the actual for C is the local variable Z in INVOKER. As is the case with all local variables, the storage represented by Z is contained in the stack frame belonging to INVOKER's invocation. When a name interpreter resolved C's name, it placed the descriptor in a register. Call Microcode 1001 takes this descriptor, converts it to a pointer, and stores the pointer above Header 1104.

Since the FP ABP points to the location following the last pointer to an actual argument, Call Microcode 1001 can now calculate that location, convert it into a descriptor, and place it in a FU Register 1004 reserved for FP. The next step is providing storage for EXAMPLE's local variables. EXAMPLE's Procedure Object 1006 contains the size of the storage required for the local variables, so Call Microcode 1001 obtains this information from Procedure Object 1006 and adds that much storage to Frame 1102. Using the new value of FP and the information contained in the Name Table Entries for the local data, Name Interpreter 715 can now construct descriptors for the local data. For example, A's entry in Name Table specified that it was offset
32 bits from FP, and was 32 bits long. Thus, its storage falls between the storage for X and B in FIG. 11.

9. Memory References and the Virtual Memory Management System (FIGS. 12, 13)

As already explained, a logical descriptor contains an AON field, an offset field, and a length field. FIG. 12 illustrates a Physical Descriptor. Physical Descriptor 1202 contains a Frame Number (FN) field, a Displacement (D) field, and a Length (L) field. Together, the Frame Number field and the Displacement field specify the location in MEM 112 containing the data, and the Length field specifies the length of the data.

As is clear from the above, the virtual memory management system must translate the AON-offset location contained in a logical descriptor 1204 into a Frame Number-Displacement location. It does so by associating logical pages with MEM 112
frames. (N.B: MEM 112 frames are not to be confused with stack frames). FIG. 13, illustrates how Macrostack 502 Object 1302 is divided into Logical Pages 1304 in secondary memory and how Logical Pages 1304 are moved onto Frames 1306 in MEM 112. A Frame 1306 is a fixed-size, contiguous area of MEM 112. When the virtual memory management system brings data into MEM 112, it does so in frame-sized chunks called Logical Pages 1308. Thus, from the virtual memory system's point of view, each object is divided into Logical Pages 1308 and the address of data on a page consists of the AON of the data's Object, the number of pages in the object, and its displacement on the page. In FIG. 13, the location of the local variable B of EXAMPLE is shown as it is defined by the virtual memory system. B's location is a UID and an offset, or, inside JP 114, an AON and an offset. As defined by the virtual memory system, B's location is the AON, the page number 1308, and a displacement within the page. When a process references the variable B, the virtual memory management system moves all of Logical Page 1308 into a MEM 112 Frame 1306. B's displacement remains the same, and the virtual memory system translates its Logical Page Number 1308 into the number of Frame 1306 in MEM 112 which contains the page.

The virtual memory management system must therefore perform two kinds of translations: (1) AON-offset addresses into AON-page number-displacement addresses, and (2) AON-page number into a frame number.

10. Access Control (FIG. 14)

Each time a reference is made to an Object, KOS 706, 710 checks whether the reference is legal. The following discusson will first present the logical structure of access control in CS 101, and then discuss the microcode and devices which implement it. CS 101 defines access in terms of subjects, modes of access, and Object size. A process may reference a data item located in an Object if three conditions hold:

(1) If the process's subject has access to the Object.

(2) If the modes of access specified for the subject include those required to perform the intended operation.

(3) If the data item is completely contained in the Object, i.e., if the data item's length added to the data item's offset do not exceed the number of bits in the Object.

The subjects which have access to an Object and the kinds of access they have to the Object are specified by a data structure associated with the Object called the Access Control List (ACL). An Object's size is one of its attributes. Neither an Object's size nor its ACL is contained in the Object. Both are contained in system tables, and are accessible by means of the Object's UID.

FIG. 14 shows the logical structure of access control in CS 101. Subject 1408 has four components: Principal 1404, Process 1405, Domain 1406, and Tag 1407. Tag 1407 is not implemented in a present embodiment of CS 101, so the following description will deal only with Principal 1404, Process 1405, and Domain 1406.

Principal 1404 specifies a user for which the process which is making the reference was created;

Process 1405 specifies the process which is making the reference; and,

Domain 1406 specifies the domain of execution of the procedure which the process is executing when it makes the reference.

Each component of the Subject 1408 is represented by a UID. If the UID is a null UID, that component of the subject does not affect access checking. Non-null UIDs are the UIDs of Objects that contain information about the subject components. Principal Object 1404 contains identification and accounting information regarding system users, Process Object 1405 contains process management information, and Domain Object 1406 contains information about per-domain error handlers.

There may be three modes of accessing an Object 1410: read, write, and execute. Read and write are self-explanatory; execute is access which allows a subject to execute instructions contained in the Object.

Access Control Lists (ACLs), 1412 are made up of Entries 1414. Each entry has two components: Subject Template 1416 and Mode Specifier 1418. Subject Template 1416 specifies a group of subjects that may reference the Object and Mode Specifier
1418 specifies the kinds of access these subjects may have to the Object. Logically speaking, ACL 1412 is checked each time a process references an Object 1410. The reference may succeed only if the process's current Subject 1408 is one of those on Object 1410's ACL 1412 and if the modes in the ACL Entry 1414 for the Subject 1408 allow the kind of access the process wishes to make.

11. Virtual Processors and Virtual Processor Swapping FIG. 15)

As previously mentioned, the execution of a program by a Process 610 cannot take place unles EOS 704 has bound the Process 610 to a Virtual Processor 612. Physical execution of the Process 610 takes place only while the process's Virtual Processor 612 is bound to JP 114. The following discussion deals with the data bases belonging to a Virtual Processor 612 and the means by which a Virtual Processor 612 is bound to and removed from JP 114.

FIG. 15 illustrates the devices and tables which KOS 706, 710 uses to implement Virtual Processors 612. FU 120 WCS contains KOS Microcode 706 for binding Virtual Processors 612 to JP 114 and removing them from JP 114. Timers 1502 and Interrupt Line 1504 are hardware devices which produce signals that cause the invocation of KOS Microcode 706. Timers 1502 contains two timing devices: Interval Timer 1506, which may be set by KOS 706, 710 to signal when a certain time is reached, and Egg Timer
1508, which guarantees that there is a maximum time interval for which a Virtual Processor 612 can be bound to JP 114 before it invokes KOS Microcode 706. Interrupt Line 1504 becomes active when JP 114 receives a message from IOS 116, for example when IOS 116 has finished loading a