IMP15 SYSTEM: SYSTEM DOCUMENTATION Hamish Dewar revised September 1977 This document provides general information about the implementation of the IMP15 system. Part 1 describes the operating system; part 2 is concerned with the IMP compiler; and part 3 covers some basic utilities. The reader is assumed to be familiar with the User's Guide for the system. Parts 1 and 2 assume familiarity with the PDP9/15 order-code and architecture, and with the basic assembly language. Parts 2 and 3 assume familiarity with the IMP language. In all cases this document requires to be read in conjunction with the relevant program source files. P A R T 1: O P E R A T I N G S Y S T E M The source files of the operating system and the components included in each are as follows: SUPER Supervisor: permanently resident kernel EXEC Executive: command language interpreter LOAD Loader: IMP program loader Reverser: IMP program reverser Background Transferror INOUT File processors The source language for the operating system is a slightly modified version of the manufacturers' MACRO-15 Assembly Language designed for system generation. The following are the main differences from the standard Assembly Language: 1. Output is in absolute code-image format onto Dectape (DT7) 2. A form of block structure is implemented allowing localisation of names to modules and providing for cross-references to global modules 3. The Assembler maintains a separate assembly location counter and storage location counter. The storage location counter determines where the modules are to be stored on DT7, addressed continuously from block 0 word 0. 4. Because assembly is one-pass, there are restrictions on the complexity of forward references (error report C) and listings show forward references as zero 5. Symbol constants (single characters within quotes) and six-bit constants (three characters within quotes) are implemented 6. Macros are not implemented The files associated with the Assembler are: SAL15: Assembler source SAL15 OBJ: Assembler object SAL15 DEF: Pre-definition file The Assembler generates the assembled system directly in code image format onto Dectape (DT7), using direct access output. To create the operating system part of a new system using an existing IMP15 system, the new system tape should be mounted on DT7. With the system source tape on DT1, the requisite command is: SAL15 SUPER+EXEC+LOAD+INOUT , SAL15 DEF / N To carry out a test assembly without output to DT7, it is necessary to alter the Assembly parameter .CONTROL; one way of doing this is to use the command: SAL15 SUPER+EXEC+LOAD+INOUT , SAL15 DEF+TT / N and type on the teletype: .CONTROL 0 followed by EOT. Provided that the interface between the operating system and IMP programs is not changed, the operating system may be modified (that is a new core image written) without changes being required to the rest of the system tape. TAPE AND STORE UTILISATION The standard paper-tape bootstrap loads the system from Dectape by reading block 0 onwards to location 100 onwards and the code thus loaded is entered at location 105 (for reasons associated with the bootstrap requirements of the manufacturers' KM9 system). In fact the requirement for the IMP system is for blocks 4:35 to be loaded to location 2100 onwards and for control to be transferred to location 2100 (the start of the Supervisor). Ad hoc code in block 0 matches the two requirements. On entry to the Supervisor, a once-only sequence copies the Supervisor to its proper position at location 0 upwards. In store, the Supervisor occupies locations 0 to 1600 approximately and the Executive starts at location 5340 and extends (including all the file-processors) to 17740 (max). File-processors forming part of a program's input/output package are relocated above the Supervisor (approx. 1600 upwards) by the Executive and input/output buffers are also allocated from low addresses upwards dynamically as the program is running. IMP programs are loaded starting at the maximum address for the system in a downwards direction. The first item to be allocated is a 40[8] word communication table containing stream assignment and similar information; then the main program; then library routines; then PERM & PRIM. Dynamic storage allocation when the program is running continues in the same direction. The two global variables .LOW and auto-index register 10 bracket free storage. The standard system runs on an 8k machine. Store in excess of 8k can be utilised by patching the global variable .MAXAD from 17777 to some larger value, subject to the following qualifications. 1. The value of .MAXAD requires to be substantially (say at least 4k) above a bank boundary, since the code of IMP programs cannot be split across banks. 2. The operating system components always execute in bank 0, so that some space limitations will not be relieved no matter how large .MAXAD is made. SYSTEM TAPE DIRECTORY Normally new systems are generated onto tapes to which an existing system has been copied, since it is usually necessary to alter only part of an old system at a time. System tapes must always have in their directory the protected files: 0SYS, 0MACRO, 0PERM, 0LIB, 0COMP, and 0SPECS. The position of the first two of these is critical; they may be created from a new-directory situation (tape assumed on DT7) as follows: S DT7 0SYS 28 1 S DT7 0MACRO 1 The position of the remaining protected files (and other system programs) is dictated by considerations of Dectape access time. The 0MACRO file may be initialised either by a block copy or by a Transfer (privileged); the soundness of its contents is vital to the operation of the Executive; it may not exceed one block in size. FILE PROCESSOR FORMAT Each File-processor is a separate module (at level 2) and each specifies an absolute start address of FPLOC (currently 16100[8]). The first three words assembled are header information and not part of the file-processor as such: the first word specifies the limit address of the file-processor (as generated by the .SIZE pseudo-op), the second is the mnemonic for the file-processor (in six-bit form), and the third is the type-word. The leftmost octal digit of the type-word specifies the type of the peripheral device (0:none, 1:Teletype, 2:dectape, 3:other), the second digit specifies whether a concatenation slot is present (0:no, 1:yes), and the rightmost digit indicates mode (1:input, 2:output). For example the first few lines of a paper-tape (binary) output processor would be: .MODULE PPB(2) .LOC FPLOC .SIZE; 'PPB'; 300002 Dynamic Relocation At the time when a file-processor is copied by the Executive into the area used for a program's input/output package, it is subjected to a process of dynamic relocation which adjusts the addresses of (what appear to be) internal references by the difference between the notional start address (FPLOC+3) and the actual start address of the area in which on this occasion the file-processor will be executed. In similar fashion certain addresses are detected as parameter references and have the actual value of the corresponding parameter substituted for them. Internal and parameter references are detected by applying a test to every value in the program (instruction, constant, etc.): the test is that the low-order thirteen bits correspond to an address in the range FPLOC to 17776 and the five high-order bits are not all ones (LAW). It follows that a file-processor cannot contain constants or other absolute formats with values which satisfy this test, as they would be subject to erroneous modification. Thus far the restriction has never caused trouble. Parameter references are distinguished from internal references simply by being in the range 17700:17776. The significance of the individual references is annotated in the Executive (parameter table). Note that the fact that parameter references in the range 17740 onwards correspond to the contents of store locations 17740 onwards (in 8k systems) is fortuitous. INPUT/OUTPUT PROTOCOL The input/output protocol defines the interface between user programs (for IMP programs, this means Perm) and the input/output system. A file-processor is called by a subroutine jump to its entry-point and exits in the usual way to the return address planted at the entry-point. File-processors are called on a character-by-character basis -- that is once for each character transferred. Although most file-processors handle the ISO character set, the basic input/output protocol is designed to permit arbitrary full-word (18-bit) values to be transmitted as characters. The protocol uses the accumulator (AC) and the link (L) to indicate different calls and different responses. For input there are two possible calls (GIVE and CLOSE) and three possible responses to the GIVE request (HERE, EOF and ERROR). For output there are two calls (TAKE and CLOSE). The CLOSE call is the same for input and output. REQUEST RESPONSE L AC L AC GIVE clear zero HERE set char EOF clear concat (neg) / zero ERROR clear positive TAKE set char -- -- -- CLOSE clear negative -- -- -- 1. There is no special call for OPEN, so that file processors must automatically initialise themselves and acquire buffers if necessary in response to the first GIVE or TAKE. 2. On end-of-file for input, the response is zero if there is no concatenated file, and the address of the new entry-point (plus sign-bit) if there is a concatenated file. When it relocates an input file-processor, the Executive replaces .SIXBT 'N', if specified as the contents of the concat slot, with the address of any concatenated file or the address of the null file (plus sign-bit). 3. An error response to the GIVE call indicates a data error (like a check-sum error). In IMP programs it causes Fault 15 to be signalled; in a Transfer operation it causes the DATA ERROR report to be made. 4. Temporary device mal-functions or mis-operations are not signalled as errors at this interface but are dealt with by the file-processor itself, using the Supervisor message-handler. 5. Lack of space for input/output buffers and lack of blocks for a Dectape output file are treated as catastrophic errors and cause an immediate CAL to the Supervisor and thence back to the Executive. This may regrettably leave other input/output operations in bad order. 6. In general it is sufficient for a file-processor to have two activation states: active and inactive. The transition from the inactive to the active state is made when the first GIVE (TAKE) call is received; for a reprocessable file this always implies starting at the beginning of the file. The transition from the active state to the inactive state is made when the CLOSE call is received or (for input) the end of file is reached. A CLOSE command received in the inactive state has no effect. Note that at the file-processor level the EOF condition is transient and does not persist until cleared. 7. Before making the transition to the inactive state, a file- processor has to ensure that any input/output operations it has invoked have terminated and relinquish any dynamically acquired buffers. 8. The standard internal character code is ISO with the single code Line Feed carrying the significance of Newline. DEVICE HANDLERS Although there is a defined interface between the user program and the file-processors, there is no change of process involved in going from one to the other. In this sense a file-processor is simply a (specially linked) subroutine of the main program. In general a file-processor will itself interface with a device handler which actually issues the input/output instructions and handles interrupts for a particular device. Device handlers for the system storage device (Dectape in the standard system) and for the user console are built into the Supervisor, while device handlers for other devices are incorporated into file-processors so that they are not a permanent overhead on the system. In either case the device handler interface is an inter-process interface. The conventions employed are specific to the particular device handler so that different units of transfer and different forms of buffering can be employed for different devices; for example the console keyboard is handled on a single-character basis (similar to the higher-level interface) while Dectape is handled on a block-transfer basis. The input/output organisation of the IMP15 system is based on a single-level interrupt system. Device-handlers run non-interruptably and after start-up operate asynchronously with respect to the user process (including its file-processors). Further information about the interrupt handling organisation of the system is given in the following section. There are mechanisms in the Supervisor for the transfer of control between a file-processor and its associated device handler and for defining WAIT conditions which enable file-processors to relinquish control while awaiting a particular event. The second mechanism is also used to prevent race conditions in accesses to the communication region shared by the file-processor and the device handler. To activate its device-handler a file-processor first carries out a GUARD operation and then jumps to the first instruction of the handler. Execution of the user process resumes at the instruction following the jump. In the simple case the code at the start of the handler consists simply of an ACCEPT instruction which serves to indicate that the call is accepted. If required, the handler can have a more complicated prologue to accept more than one concurrent call or to block off subsequent calls by executing a WAIT instead of an ACCEPT. Once activated a device-handler will carry out a fixed or variable number of input/output operations, being re-entered as a result of interrupts generated by these operations, and will then terminate its current activation. The start-up mechanism (that is GUARD followed by ACCEPT) establishes the same return information as is set up after an interrupt, so that the method by which a device-handler relinquishes control does not depend on the way in which it was entered. In some areas there is a certain amount of latitude in determining the division of work between a file-processor and its device-handler. In this respect it has to be borne in mind that the device-handler runs non-interruptably and its execution time should therefore be kept short. DEVICE CASCADE The basic interrupt processing mechanism in the Supervisor is a 'device cascade'. The takes the place of the skip chain often used in PDP systems, and has the important difference that it does not contain all the device flag skip instructions but provides a structure for despatching control (in priority sequence) to all device-handlers which have registered a service address in their slot in the device cascade. The slot for an inactive device is chained to the next slot in the cascade. Each slot occupies four consecutive locations, of which the first, third and fourth have a significance for device handlers. A device handler registers that it is waiting for an interrupt -- and simultaneously relinquishes control -- by performing a JMS on the first word of its slot. When an interrupt occurs, control is passed to the address contained in this location, that is to the code following the JMS instruction, which can test the relevant flag(s). If the tests fail, the device handler must pass control to th next device in the cascade by jumping to the fourth word of its slot. Otherwise the handler clears the interrupt condition and processes the interrupt and then relinquishes control either by means of a JMS on the first word again (if further interrupts are expected) or by means of a jump to the third word (to terminate the current activation). These operations are illustrated by a fragment of a paper-tape reader handler. The global mnemonic for this device, which is associated with the first word of its device cascade slot, is .PR L1 RSA /SELECT READER JMS .PR /WAIT FOR INTERRUPT RSF /IS IT READER? JMP .PR+3 /NO => RRB /READ CHARACTER ... /STORE CHARACTER ... /IS INTERNAL BUFFER FULL? JMP L1 /NO => ... /UPDATE STATUS INFORMATION JMP .PR+2 /=> In addition to slots for Dectape and teletype (and special code for links, printer, and clock), there are three device slots in the standard IMP15 system. (Extra slots can be added in the obvious way by modifying the Supervisor). The use of these slots in standard systems, which is reflected in the mnemonics, is as follows (priority order): Card Reader (.CR), Paper-tape Reader (.PR), Paper-tape Punch (.PP). PROCESS STRUCTURE There is a minimal multi-processing capability in the system which provides a basic mechanism for concurrency of user processes. This is barely adequate to permit simultaneous execution of a normal activity, a background transfer, and the idle process. 'Scheduling' is non-existent: following an interrupt and its servicing, control is transferred to the first process in the (fixed) process queue. When the process relinquishes control (by executing a WAIT), the next process in the queue is activated. The idle process never executes a WAIT. SUPERVISOR SERVICES Storage allocation JMS .BU (from user process) The allocation and de-allocation of buffer space for input/output is carried out by a single Supervisor routine (entry-point .BU). If called with the accumulator zero this routine allocates a standard 256-word buffer and returns the start address in the accumulator. The initial contents of the buffer are undefined. The buffer is released by calling the allocation routine with the start address in the accumulator. GUARD operation GUARD=JMS 3 (from user process) The GUARD operation has the effect of registering a process restart address and switching off interrupts. It must be used immediately before a WAIT test and immediately before a jump to a device handler. WAIT operation WAIT=JMP 2 (only after GUARD) The WAIT operation is the means by which a (user) process relinquishes control pending the occurrence of some event. The WAIT operation is normally incorporated in a WAIT test, which is an arbitrary (but short) piece of code defining a two-way branch, one outcome of which is a WAIT. The continuation path must switch interrupts on (ION). On any occasion on which the WAIT path is taken, an (unpredictable) interval will elapse and then control will return to the start of the test. On re-entry AC and L have the same values as when the GUARD operation was first performed. An example of a file-processor waiting for data to become available from its associated device handler might be .. GUARD LAC COUNT; SNA; WAIT ION .. This philosophy, sometimes termed the 'busy wait' approach, is generally regarded as undesirable, but the reasons for this are largely inapplicable in the current environment where there is no scheduling and the overhead of process entry/exit is small. ACCEPT operation ACCEPT=ISZ 3 (only after GUARD) The ACCEPT operation at the start of a handler is required to indicate that the call has been accepted. Message handler GUARD; JMP .MH (from user process) The message handler produces messages on the user console of the form *** NOT READY, where the *** is the contents of the AC on entry (six-bit). The message handler does not return control to the caller until the user has responded to this message by typing Carriage Return. Note that the call must be made from the user level (i.e. file-processor) and not from the device handler. P A R T 2 : C O M P I L E R The files relevant to the IMP compiler are the following: COMP Compiler source PERM Primitive and Permanent procedures GRAM Grammar in 'external' format TAKEON Conversion program for grammar The program TAKEON generates the tables embodied in the compiler for use in lexical encoding and parsing. It takes GRAM as input 1 and an existing compiler as input 2 and generates a revised compiler on output 1 by searching for marker comments, removing the old tables and inserting the new. Output 2 displays the generated dictionary table in interpreted form and output 3 displays the generated grammar in interpreted form. Thus, for example: C TAKEON; R GRAM,COMP/NUCOMP,LP,=2 PERM consists of primitive procedures followed by permanent procedures. The primitive procedures are those which the compiler requires to invoke (that is, generate code to invoke) explicitly in order to implement 'complex' operations, that is, operations for which in-line code would be uneconomical. To keep compiler and loader tables straight, these procedures require to have (single-letter) names, but the compiler generates calls on them by explicit tag number. They are in fact accessible by name in other primitive and permanent procedures, but not in the main program. The permanent procedures are simply pre-defined routines accessible by name in the usual way, although the compiler invokes (or intercepts) a few by explicit tag number. When compiling a main program (including itself), the compiler requires to be supplied with specs for these procedures. The way in which this is currently achieved is thoroughly unsatisfactory. It has the effect of prefixing the system file .0SPECS to the program being compiled. One unsatisfactory feature of the way this is done is that, to avoid unwanted output when the specs are being processed, there must be no newline characters in the specs file (hence it cannot be edited, among other constraints). (The obvious solution of a separate default input, treated specially by the compiler, is regrettably ruled out by considerations of space). The prefixing of the specs file is effected by Executive action in response to the C (Compile) command, as is the invocation of the process of 'reversing' the object file after compilation. When it is necessary to do a genuine compilation of PERM, the specs file is, of course, not wanted, so that in this case the Compiler must simply be run as an ordinary program. After the compilation, the object file must be 'manually' reversed. The commands for the straightforward case, would be: .0COMP PERM/S-.0PERM G 0PERM/.0PERM Note the use of the S (Strip) post-processor to get rid of newlines in the object file (which simply bulk it out unnecessarily). Things become more complicated if PERM is altered in such a way that the specs file must be changed, since this implies re-compilation of all programs (using the new specs file) including the compiler itself. In this case the newly compiled PERM must not be written directly to .0PERM, but must be held elsewhere until the compiler is re-compiled and then taken across by a Transfer.