MULTICS DESIGN DOCUMENT MDD-020
To: MDD Distribution
From: Melanie Weaver
Date: March 12, 1987
Subject: The Multics Runtime Environment
Abstract:
Explanation of the runtime environment, including process
structure and initialization, ring crossing mechanisms, object
format and dynamic linking, area management, and condition
signalling and handling.
Revisions:
REVISION DATE AUTHOR
initial March 12, 1987 Melanie Weaver
_________________________________________________________________
Multics Design Documents are the official design descriptions of
the Multics Trusted Computing Base. They are internal documents,
which may be released outside of Multics System Development only
with the approval of the Director.
i
MDD-020 Runtime Environment
CONTENTS
Page
1: Overview . . . . . . . . . . . . . 1
1.1: Overview of Process Creation . . 1
1.2: Overview of Process Directory
Contents . . . . . . . . . . . . . . 1
1.3: Overview of Stack Management . . 2
1.4: Overview of Ring Crossing . . . 2
1.5: Overview of the Dynamic Linker . 3
1.6: Overview of Area Management . . 4
1.7: Overview of Condition Signalling
and Handling . . . . . . . . . . . . 4
1.8: Overview of Segment and Process
Termination . . . . . . . . . . . . . 5
1.9: Overview of the Ring 0
Environment . . . . . . . . . . . . . 5
2: Process Directory Contents . . . . 6
2.1: Ring 0 Process Segments . . . . 6
2.1.1: Descriptor Segment . . . . . . 6
2.1.2: Process Initialization Table . 6
2.1.3: The Process Data Segment . . . 7
2.1.4: The Known Segment Table . . . 7
2.2: Per-Ring Process Segments . . . 7
2.2.1: The Stack . . . . . . . . . . 8
2.2.1.1: The Stack Header . . . . . . 8
2.2.1.2: The Stack Frames . . . . . . 8
2.2.1.3: Manipulating the Stack . . . 8
2.2.1.3.1: Normal Call . . . . . . . 9
2.2.1.3.2: Push . . . . . . . . . . . 9
2.2.1.3.3: Normal Return . . . . . . 9
2.2.1.3.4: Stack Truncation . . . . . 9
2.2.1.3.5: Use of Operators . . . . . 10
2.2.1.3.6: Abnormal Returns . . . . . 10
2.2.1.4: Other Stack Segments . . . . 11
2.2.2: The User Free Area . . . . . . 12
2.2.3: Temporary Segments . . . . . . 12
3: Process Creation . . . . . . . . . 14
3.1: Preparation by the Creating
Process . . . . . . . . . . . . . . . 14
3.2: Preparation by the New Process . 15
3.2.1: Initializing the Environment . 15
3.2.2: Finding the Initial Procedure 16
ii
Runtime Environment MDD-020
CONTENTS (cont)
Page
3.2.3: Completing the User Ring
Initialization . . . . . . . . . . . 18
3.2.4: Initializer Differences . . . 18
4: Ring Crossing Mechanisms . . . . . 19
4.1: Gates . . . . . . . . . . . . . 19
4.1.1: What Gates Are . . . . . . . . 19
4.1.2: Non-Hardcore Gate Actions . . 20
4.1.3: Hardcore Gate Actions . . . . 21
4.1.3.1: bad_dir Condition Handler . 21
4.1.3.2: Metering . . . . . . . . . . 22
4.1.3.3: Checking for Ring Alarms . . 22
4.1.3.4: Obtaining the Ring Zero
Linkage Pointer . . . . . . . . . . . 22
4.1.3.5: Fast Hardcore Gates . . . . 22
4.1.4: Gate Actors . . . . . . . . . 23
4.1.5: Gate Macros . . . . . . . . . 23
4.2: Validation Level . . . . . . . . 24
4.3: The Ring Alarm Mechanism . . . . 27
4.4: Brief Summary of Fault Handling 27
4.5: Exiting a Lower Ring . . . . . . 28
4.5.1: Normal Returns . . . . . . . . 28
4.5.2: Condition Crawlouts . . . . . 28
4.5.3: Transfers to Labels in Higher
Rings . . . . . . . . . . . . . . . . 29
4.5.4: Outward Calls . . . . . . . . 29
4.5.4.1: outward_call_handler . . . . 30
4.5.4.2: call_outer_ring_ . . . . . . 31
4.5.4.3: User Coded Procedures . . . 31
5: Linking . . . . . . . . . . . . . 33
5.1: What Dynamic Linking Is . . . . 33
5.2: The Effect of Dynamic Linking on
Process Structure . . . . . . . . . . 34
5.2.1: Linking and the Object Segment
Format . . . . . . . . . . . . . . . 34
5.2.1.1: Linkage Section . . . . . . 34
5.2.1.2: Definition Section . . . . . 35
5.2.1.3: Unsnapped Links . . . . . . 35
5.2.1.4: Obsolete Feature of
Definitions in the Linkage Section . 35
5.2.1.5: Historical Note on Separate
Static . . . . . . . . . . . . . . . 36
5.2.2: The Linkage and Static Offset
Tables . . . . . . . . . . . . . . . 37
5.2.3: Name Space Issues . . . . . . 39
5.2.4: External Variables . . . . . . 40
5.2.4.1: How Allocation Is
Implemented . . . . . . . . . . . . . 41
iii
MDD-020 Runtime Environment
CONTENTS (cont)
Page
5.2.4.1.1: Historical Note on the
Allocation of External Variables . . 42
5.2.4.2: Heap Variables . . . . . . . 42
5.2.5: Traps at First Reference . . . 43
5.3: Static Linking . . . . . . . . . 44
5.3.1: The bind Command . . . . . . . 44
5.3.2: The linkage_editor Command . . 45
5.3.2.1: Object Multi-Segment Files . 45
5.3.2.1.1: External Definitions . . . 46
5.3.2.1.2: Inter-Component Links . . 46
5.3.2.1.3: External Variable
Initialization . . . . . . . . . . . 46
5.3.2.1.4: Prelink First Reference
Trap . . . . . . . . . . . . . . . . 47
5.3.3: Alternatives to Static Linking 47
5.3.3.1: set_fortran_common . . . . . 47
5.3.3.2: Run Units . . . . . . . . . 48
5.4: Description of the Dynamic
Linker . . . . . . . . . . . . . . . 49
5.4.1: link_snap . . . . . . . . . . 49
5.4.2: fs_search . . . . . . . . . . 50
5.4.3: link_man . . . . . . . . . . . 51
5.4.3.1: link_man$other_linkage . . . 51
5.4.3.2: link_man$own_linkage . . . . 51
5.4.3.3: link_man$combine_linkage . . 51
5.4.3.4: link_man$grow_lot . . . . . 51
5.4.3.5: link_man$get_initial_linkage 52
5.4.3.6: link_man$assign_linkage . . 52
5.4.3.7: link_man$set_lp . . . . . . 52
5.4.3.8: link_man$get_lp . . . . . . 52
5.4.4: get_defptr_ . . . . . . . . . 52
5.4.5: set_ext_variable_ . . . . . . 53
5.4.6: list_init_ . . . . . . . . . . 53
5.4.7: Trap Processing . . . . . . . 53
5.4.7.1: trap_caller_caller_ . . . . 54
5.4.7.2: link_trap_caller_ . . . . . 54
5.4.7.3: How First Reference Traps
Get Turned Off . . . . . . . . . . . 54
5.4.8: Error Handling . . . . . . . . 55
5.4.9: Lot Fault Handling . . . . . . 55
5.4.10: Security Issues . . . . . . . 56
5.5: The C Execution Environment . . 57
6: Area Management . . . . . . . . . 58
6.1: General Purpose Area Management 58
6.1.1: Logical System Areas . . . . . 58
6.1.1.1: User Free Area . . . . . . . 58
6.1.1.2: System Free Area . . . . . . 58
iv
Runtime Environment MDD-020
CONTENTS (cont)
Page
6.1.1.3: Combined Linkage Area . . . 59
6.1.1.4: Combined Static Area . . . . 59
6.1.1.5: hcs_$assign_linkage Area . . 59
6.1.1.6: C Heap . . . . . . . . . . . 59
6.1.1.7: RNT Area . . . . . . . . . . 59
6.1.1.8: Ring 0's Use of Areas . . . 59
6.1.2: Freeing Allocations . . . . . 60
6.1.3: Area Format . . . . . . . . . 60
6.1.3.1: Area Header Format . . . . . 60
6.1.3.1.1: The Free List . . . . . . 61
6.1.3.2: Area Block Format . . . . . 61
6.1.3.3: Area Extend Blocks . . . . . 62
6.1.4: Algorithms Used . . . . . . . 62
6.1.4.1: Standard Allocation Method . 62
6.1.4.1.1: Allocation . . . . . . . . 62
6.1.4.1.2: Freeing . . . . . . . . . 63
6.1.4.1.3: Initialization . . . . . . 64
6.1.4.1.4: Asynchronous Reinvocation
Protection . . . . . . . . . . . . . 64
6.1.4.2: No Freeing Method . . . . . 65
6.1.5: Modules Used . . . . . . . . . 65
6.1.5.1: alloc_ . . . . . . . . . . . 65
6.1.5.1.1: Entrypoints in alloc_ . . 66
6.1.5.2: Entrypoints in define_area_ 67
6.1.5.2.1: define_area_ . . . . . . . 67
6.1.5.2.2: get_next_area_ptr_ . . . . 67
6.1.5.2.3: release_area_ . . . . . . 67
6.1.6: Area Commands . . . . . . . . 68
6.2: Obsolete Buddy Block Mechanism . 68
6.3: File System Areas . . . . . . . 68
7: Condition Signalling and Handling 70
7.1: Condition Signalling . . . . . . 70
7.1.1: Static Conditions . . . . . . 70
7.1.2: Normal Condition Signalling . 71
7.1.3: Crawlouts . . . . . . . . . . 72
7.2: How signal_ Is Invoked . . . . . 72
7.2.1: Restarting a Condition . . . . 74
7.3: Condition Handling . . . . . . . 74
7.3.1: Condition Walls . . . . . . . 74
7.3.2: System Default Condition
Handling . . . . . . . . . . . . . . 75
7.3.2.1: default_error_handler_ . . . 75
7.3.2.1.1: Entry $wall . . . . . . . 76
7.3.2.1.2: Entry
$standard_default_handler_ . . . . . 77
7.3.2.1.3: Entry
$default_error_handler_ . . . . . . . 77
v
MDD-020 Runtime Environment
CONTENTS (cont)
Page
7.3.2.1.4: Entry $wall_ignore_pi . . 77
7.3.2.1.5: Entry $ignore_pi . . . . . 77
7.3.2.1.6: Entry
$condition_interpreter_ . . . . . . . 77
7.3.2.1.7: Entry
$reinterpret_condition_ . . . . . . . 77
7.3.2.1.8: Entry
$interpret_condition_ . . . . . . . . 78
7.3.2.1.9: Entry
$reprint_error_message_ . . . . . . . 78
7.3.2.1.10: Entry
$change_error_message_mode_ . . . . . 78
7.3.2.1.11: Entry $add_finish_handler 78
7.3.2.2: message_table_ . . . . . . . 78
7.3.2.3: find_pathname_ . . . . . . . 78
7.3.2.4: get_ppr_ . . . . . . . . . . 79
7.3.2.5: get_tpr_ . . . . . . . . . . 79
7.3.2.6: interpret_info_struc_ . . . 79
7.3.2.7: interpret_oncode_ . . . . . 79
7.3.2.8: linkage_error_ . . . . . . . 79
7.3.2.9: special_messages_ . . . . . 79
7.3.3: Reentering Command Level . . . 80
8: Segment and Process Termination . 81
8.1: Segment Termination . . . . . . 81
8.2: Process Termination . . . . . . 82
vi
Runtime Environment MDD-020
_1_: _O_V_E_R_V_I_E_W
The Multics runtime environment, as described in this MDD,
consists of the basic system support and conventions for running
programs in a single process. However, this MDD does not cover
in detail several aspects that are described in other MDDs, such
as name and address space management and fault/condition
processing. Conversely, several system runtime databases are
described here which are not covered elsewhere.
The topics covered include process creation, the basic support
segments used by a process, the conventions governing use of the
stack, ring crossing mechanisms and conventions, dynamic linking,
the ring 0 environment, and some system runtime databases.
This section summarizes the following sections so that the reader
can get a simpler picture of what is going on before plunging
into the details. It seems choppy because many different topics
are discussed briefly. However, the topics are connected enough
so that each later section has to assume some overview knowledge.
_1_._1_: _O_v_e_r_v_i_e_w _o_f _P_r_o_c_e_s_s _C_r_e_a_t_i_o_n
Process creation creates the environment, initializes it, and
makes the process known to the supervisor. It begins in
hphcs_$create_proc, which is generally called by the
initializer/answering service (hphcs_ stands for highly
privileged hardcore segment). create_proc creates a runtime
directory, known as the process directory, for the exclusive use
of the new process. It then creates and initializes the ring 0
data segments that are necessary for the process to run at all.
Finally it acquires and initializes an entry in the active
process table to enable the process to be scheduled on its own.
The nascent process begins life in init_proc, whose main goal is
to figure out where to go next. It determines the initial
(non-zero) ring to be used and calls makestack to set up the
environment for that ring. Then it determines the name of the
first procedure to run in the initial ring and calls
call_outer_ring_ to invoke it.
The first procedure(s) to run in the initial ring is(are)
responsible for initializing I/O switches, establishing condition
handlers including the ones for the timers, invoking the start_up
exec_com, setting the ring's working directory, and entering the
command level request loop.
1
MDD-020 Runtime Environment
_1_._2_: _O_v_e_r_v_i_e_w _o_f _P_r_o_c_e_s_s _D_i_r_e_c_t_o_r_y _C_o_n_t_e_n_t_s
The process directory is used to store three types of per-process
data:
ox data used by the hardcore supervisor
ox program activation history, program variable storage and
dynamic linking data
ox temporary files
The ring 0 segments are the process initialization table (PIT),
the process data segment (PDS), the descriptor segment (dseg),
and the known segment table (KST).
There is a set of runtime storage segments for each ring used.
Each set includes a stack, which is used for program activation
history and automatic variables, and one or more area segments,
which are used for based, controlled and heap variables, internal
and external static variables, and inter-segment links. The
beginning of the stack is reserved for per-ring process data.
The temporary files are those used by compilers, editors, etc.
Storing them in the process directory eliminates the need for
users to worry about the amount of space they require.
_1_._3_: _O_v_e_r_v_i_e_w _o_f _S_t_a_c_k _M_a_n_a_g_e_m_e_n_t
The only hardware involvement with stack management in Multics is
the choice of stack segment by the call6 instruction.
Nevertheless the system has strict protocols for passing
arguments and pushing/popping stack frames. Languages on Multics
are encouraged to use shared assembly language operator segments
to actually manipulate the stack frames.
The system provides a facility for performing nonlocal goto's
(transfers back to previous activation frames). Intervening
stack frames are deleted. Of course this depends on everyone
using the standard stack frame format.
_1_._4_: _O_v_e_r_v_i_e_w _o_f _R_i_n_g _C_r_o_s_s_i_n_g
Since rings on Multics are hierarchical, the user normally runs
in the highest (least privileged) ring being used by the process.
From time to time calls are made to programs in inner rings to
perform some service. The only way to invoke a specified program
in an inner ring is to use the call6 instruction to transfer to a
segment that has the appropriate gate ring brackets. The
2
Runtime Environment MDD-020
caller's ring of execution must be in the call bracket of the
gate.
It is possible to invoke a program that will execute in a ring
higher than the calling ring, but not with an ordinary call. The
procedure call_outer_ring_ initializes the environment in the
outer ring if necessary, links to the program using that
environment, and "transfers" to the entrypoint.
In all cases, when control moves from an inner ring to an outer
ring the inner ring's stack history is truncated so that an inner
ring program cannot be returned to from an outer ring.
Sometimes an inner ring must know the ring number it is
servicing. In these situations it uses the validation level.
Often the validation level must be temporarily changed to the
lower ring number so that inner ring segments can be accessed.
The validation level can never be set lower than the current
ring.
The ring alarm mechanism helps to ensure that certain operations
are cleaned up before returning from a ring. These include
resetting the validation level and unlocking.
_1_._5_: _O_v_e_r_v_i_e_w _o_f _t_h_e _D_y_n_a_m_i_c _L_i_n_k_e_r
A Multics process always has programs from more than one segment
in its address space at a time. The linking between segments is
done at runtime by the dynamic linker. One reason for this is
that at the hardware level segments can only be addressed via
segment numbers, and these numbers are only assigned at runtime.
A segment's number is not necessarily the same in each process.
This much could be done by just inserting segment numbers into a
load module. However dynamic linking is much more flexible.
Links are filled in only when they are referenced for the first
time in a process and search rules (a list of directories) are
used to locate the target. If the target is removed from the
process's address space, any links to it are usually reset. What
all this means in flexibility to the user is explained elsewhere.
Another effect of having the segment numbers assigned at runtime
is that each process must have its own copy of a program's links.
However the process does not need its own copy of the entire
program. The object code itself is pure and stays in a
non-writeable segment that can be shared, while the links and
internal static data are copied to the process area. The term
used for copying the links is combining the linkage section, in
the sense of putting it in the same writeable segment as the
other combined linkage sections.
3
MDD-020 Runtime Environment
The linker is usually presented with a segment name and an entry
name that it must convert to a pointer containing a segment
number and an offset. To do this it first calls the file system
to locate the segment using a set of search rules, assigning a
segment number if necessary; it copies the target segment's links
into the process area if necessary; then it looks at the target
segment's list of externally referenceable entrypoints for the
entry name and corresponding offset.
The linker is responsible for allocating and initializing
non-permanent external variables, which are also referenced
through links.
There are three main reasons for the linker to run in ring 0.
First, it does not have to link itself since ring 0 is linked
during system initialization. Second, it can snap links to gates
on behalf of rings that are within the call bracket but not
within the read/execute bracket. Third, it can find the search
rule directories much faster since it doesn't have to deal with
pathnames.
_1_._6_: _O_v_e_r_v_i_e_w _o_f _A_r_e_a _M_a_n_a_g_e_m_e_n_t
Dynamic allocation is used extensively in Multics. The system
uses two allocation routines: one for directory contents and one
for everything else. The general-purpose routine uses a
first-fit algorithm for allocation. It has options for a more
efficient but no-freeing algorithm, multi-segment areas, and a
choice of whether to initialize area contents to zero when
allocating or freeing.
_1_._7_: _O_v_e_r_v_i_e_w _o_f _C_o_n_d_i_t_i_o_n _S_i_g_n_a_l_l_i_n_g _a_n_d _H_a_n_d_l_i_n_g
All condition/fault/IPS event signalling is done via signal_ in
the ring of occurrence. Signal_ first checks the ring's list of
static handlers. If an appropriate static handler does not
exist, signal_ searches the stack for the most recent relevant on
unit. The pseudo condition any_other "matches" all condition
names. When a handler is found, signal_ invokes it.
A handler has three return options. One is to return to signal_,
causing the action that caused the condition to be restarted. A
second is to return to signal_, telling it to continue
signalling. A third is to do a nonlocal goto to a previous
invocation, unwinding the stack.
The system provides a default handler for all conditions and
establishes it as the any_other handler in the first frame of the
user ring stack.
4
Runtime Environment MDD-020
_1_._8_: _O_v_e_r_v_i_e_w _o_f _S_e_g_m_e_n_t _a_n_d _P_r_o_c_e_s_s _T_e_r_m_i_n_a_t_i_o_n
Dynamically removing a segment from the address space is done in
ring 0, but it is recommended that the user ring procedure term_
be used in order to properly clean up the user ring environment.
A process terminates itself by closing all its files (if
possible) and then signalling the answering service to unschedule
it and delete its temporary storage.
_1_._9_: _O_v_e_r_v_i_e_w _o_f _t_h_e _R_i_n_g _0 _E_n_v_i_r_o_n_m_e_n_t
The ring 0 environment has several differences from that in other
rings. Its segment numbers are assigned and its links snapped
during system initialization, which allows these to be shared by
all processes. In particular, ring 0's internal static storage
is shared by all users so ring 0 programs don't use it very much.
The stack for ring 0 does not live in the process directory, but
is one of a group of stack segments assigned only to active
processes. A few processes that are known to never leave ring 0
have no need for address space or linking support. They are
called hprocs and are created in a special way.
5
MDD-020 Runtime Environment
_2_: _P_R_O_C_E_S_S _D_I_R_E_C_T_O_R_Y _C_O_N_T_E_N_T_S
The process directory contains the per-process temporary files.
It is part of the Multics file system as a branch off
>process_dir_dir, but the storage it uses is independent of any
permanent record quota the user may have. Only the Initializer
and the process itself have access to it; all others have null
access. Its contents are what distinguish one process from
another.
The process directory segments can be classified into two major
groups. One group is writeable only in ring 0 by the hardcore
supervisor. Each segment in the other group "lives" in a single
non-zero ring and is used directly by programs running in that
ring.
_2_._1_: _R_i_n_g _0 _P_r_o_c_e_s_s _S_e_g_m_e_n_t_s
The process directory's ring 0 segments are created there by
hphcs_$create_proc, which runs in the initializer process. These
segments must be initialized before the process can run on its
own.
2.1.1: DESCRIPTOR SEGMENT
The descriptor segment, known as dseg, is an array of segment
descriptor words (SDWs). There is an SDW for each segment used
in the process, indexed by segment number. An SDW contains the
location of the segment's page table as well as the gate entry
bounds, if any, and the process's access to the segment. The
hardware uses the segment number portion of an address to find
the SDW, which will enable it to determine whether and where to
access the segment. The hardware locates the descriptor
segment's page table via the descriptor base register, which is
loaded by the privileged ldbr instruction.
It can be seen, then, that the descriptor segment defines the
address space of the process. It is the loading of the
descriptor base register by the scheduler that makes a process
run.
The ring brackets of the descriptor segment are 0,0,0. The
setting and use of the fields in an SDW are described in other
documents.
2.1.2: PROCESS INITIALIZATION TABLE
Most of the information contained in the Process Initialization
Table (PIT) relates to the process's interaction with the
6
Runtime Environment MDD-020
answering service. This includes information about such things
as the terminal being used, the user's login dialogue, how to
contact the answering service to logout, and flags that specify
the user's privileges, such as the ability to have several
processes at a time. The PIT also contains the accounting
information that is made accessible to the user, such as
month-to-date expenditures and times for several categories as
well as spending/time limits. A third major function of the PIT
is to provide a place for the answering service to put the
information for an absentee process that it received from the
submittor.
The ring brackets on the PIT are 0,N,N where N is the initial
nonzero ring, so it is directly accessible to the user. The
contents are written in the answering service's user ring by cpg_
and simply copied into the process directory by
hphcs_$create_proc.
2.1.3: THE PROCESS DATA SEGMENT
The Process Data Segment (PDS), as its name implies, contains
most of the process's static variable data needed in ring 0.
There are too many different kinds of items to describe here; it
is more appropriate to discuss each when it is relevant. The
process's security attributes and basic initial information such
as the lock ID are filled in by hphcs_$create_proc.
The ring brackets on the PDS are 0,0,0 but some of the
information is available through gates.
2.1.4: THE KNOWN SEGMENT TABLE
The Known Segment Table (KST) is the main hardcore data base used
for address space management. It maps segment numbers for
non-hardcore segments into their location within the hierarchy.
It contains a header, the KST entries themselves, the private
logical volume connection table and the KST UID hash table. It
is described in MDD006, on the Multics File System.
The ring brackets on the KST are 0,0,0.
_2_._2_: _P_e_r_-_R_i_n_g _P_r_o_c_e_s_s _S_e_g_m_e_n_t_s
These all have ring brackets of N,N,N, where N is the associated
nonzero ring.
7
MDD-020 Runtime Environment
2.2.1: THE STACK
The stack is a ring's most important runtime segment. It
consists of a header and the procedure call activation frames.
2.2.1.1: The Stack Header
The stack header contains or points to most of a ring's runtime
environment information, excluding some that needs the security
of ring 0. Since it is expected that pointer register 6 always
points to the current stack frame, everything at the beginning of
the stack can be accessed very efficiently. Most of the items
are pointers to such things as tables, call/push/return
operators, areas and condition signalling programs. The stack
header format and contents are documented in the Multics
Programmer's Reference Manual, order number AG91-04 (at this
writing; revision number may change).
Many processes also keep the linkage offset table (LOT) and
internal static offset table (ISOT) in the stack segment. These
tables each consist of one word per segment number up to a
certain limit, with a default of 512 words. However, since these
tables are not used for ring 0 segments (below about 200), the
beginning of the tables can overlay other information. Thus the
LOT logically begins at the beginning of the stack segment, which
is also the location of the stack header. Likewise, the ISOT
logically begins immediately after the LOT, which is also the
location of the System Condition Table (SCT).
2.2.1.2: The Stack Frames
The other main purpose of the stack segment is to serve as the
location of the procedure call activation frames, which contain
the procedures' automatic storage. The first frame is located
after the ISOT and is pointed to by stack_header.stack_begin_ptr.
The rest of the segment is reserved for stack frames.
stack_header.stack_end_ptr points to where the next stack frame
should be laid down, which is also the end of the most recent
valid frame being used. Each frame's header must adhere to a
standard format, which is documented in the Multics Programmer's
Reference Manual. Failure to conform can cause the process to
behave in unpredictable ways.
2.2.1.3: Manipulating the Stack
This section discusses conventions for pushing and popping stack
frames. The formats and conventions are described in the Mulitcs
Programmer's Reference Manual.
8
Runtime Environment MDD-020
2.2.1.3.1: Normal Call
The caller generally creates the argument list in its own stack
frame. The list consists of ITS or ITP pointers to the actual
arguments and to their descriptors. Negative offsets from the
beginning of the next stack frame may not be used because the
next stack frame does not always belong to the program
referencing the argument list.
After creating the argument list, the caller obtains a pointer to
the entrypoint to be called. Such pointers are stored as links
in the copied version of the object segment's linkage section.
If the referenced link has not yet been "snapped", the dynamic
linker is invoked to find the desired entrypoint (see the section
on the dynamic linking mechanism below).
Finally the caller transfers to a shared assembly language
"operator" segment to make the actual call. Because the language
of the callee is not known until dynamic linking time, it is
necessary to have certain system-wide conventions when making
calls: pointer register 0 must point to the argument list,
pointer register 2 must point to the callee's entrypoint, pointer
register 6 must point to the current stack frame, and pointer
register 7 must point to the current ring's stack header.
2.2.1.3.2: Push
The called entrypoint loads its stack frame size into an index
register (the choice of register is defined by the operators
used) and then immediately transfers to an entry/push operator.
This operator initializes several fields in the new stack frame's
header, generally loads a pointer to the segment's active linkage
section in PR4, updates stack_header.stack_end_ptr, and may do
other initialization before returning. It is also responsible
for saving the values of the machine's indicators.
2.2.1.3.3: Normal Return
When the called procedure returns, it transfers to yet another
operator. This operator updates the stack end pointer among
other things and returns to the location specified by the return
pointer in the caller's stack frame. The machine indicators and
pointer register 6 must be restored and pointer register 0 set to
stack_frame.operator_pointer,* (of the frame being returned to).
No other registers need to be restored.
9
MDD-020 Runtime Environment
2.2.1.3.4: Stack Truncation
None of the operators above touch the program's automatic storage
area. This means that uninitialized variables generally contain
garbage. However, when the process blocks, the stack segment is
truncated to the length actually being used. This cleans up
garbage that may have been left by a lot of nested calls and may
reduce paging.
2.2.1.3.5: Use of Operators
All languages on Multics are required to use operator segments
for pushing and popping stack frames. In particular, compiled
code should not automatically reference the stack frame header.
This contributes to system flexibility. (Of course there are
always some programs that are explicitly coded to reference the
stack frame header.)
The most heavily used operator segment, pl1_operators_, has
pointers to it in the stack header. However, several languages
have their own operator segments and their own conventions for
communicating with them. The entries of programs compiled by
these languages should locate their operator segments via
assigned pointers in the operator_pointers_ transfer vector,
which is pointed to by stack_header.trans_op_tv_ptr.
2.2.1.3.6: Abnormal Returns
There are times when one wants to return to a procedure
activation that precedes one's caller and throw away all the
stack frames in between. Usually an error has just occurred and
it is necessary to discard all history associated with the error.
Because the same environment will continue to be used, all
procedures with activations to be discarded should clean up any
changes they made that are no longer appropriate or would have
been cleaned up anyway if they had returned normally.
Multics provides an unwinding facility that is usually used
implicitly through language-defined constructs. It is also used
by the release mechanism at command level. It is accessed via
stack_header.unwinder_ptr by one of the operators in the operator
segment. Its argument is a label, which consists of two
pointers: one to the code location to transfer to and the other
to the stack frame to be used.
The program that the system provides for this is unwinder_.
unwinder_ determines the target stack frame from the label, calls
unwind_stack_ to "clean up" the intervening procedure
activations, and prepares for the transfer. The actual transfer
is done by nonlocal_goto_.
10
Runtime Environment MDD-020
unwind_stack_ processes every stack frame from the specified
starting frame up to, but not including, the target frame. Each
frame is searched for a handler for the cleanup condition. If
found, it is invoked. These handlers are "established" by the
frames' owners to do any environmental cleanup necessary during
an abnormal return. Before a cleanup handler is invoked, it is
unthreaded from the frame's list of condition handlers so that it
cannot be reinvoked. After a cleanup handler has returned to
unwind_stack_, the frame's entire condition list is disabled
because the frame/activation has logically ceased to exist and
should no longer be searched by the signalling mechanism.
unwind_stack_ is also called by other programs, such as signal_,
that want to clean up (logically discard) part of the stack but
that also want to make their own transfer arrangements. It is
possible to specify that the entire stack preceding and including
the starting point be processed.
After the stack frames following the target frame have been
cleaned up, unwinder_ calls nonlocal_goto_$same_ring to make the
transfer, passing it the label's pointers as separate arguments.
nonlocal_goto_ resets the stack end pointer and pointer register
6 together with interrupts inhibited, resets the few other
registers required for a return, and "returns" to the specified
location. In general, the code at a nonlocal label cannot count
on the values of any registers except pointer register 6, which
points to the stack frame, and pointer register 0, which is
restored to stack_frame.operator_ptr,*.
2.2.1.4: Other Stack Segments
It is possible for the user (least privileged) ring to have more
than one stack segment. There are several reasons for wanting to
do this.
One is that a language may want to use a nonstandard
call/push/return sequence that would confuse the system programs
that walk the stack. In this case, the original, standard stack
is still used for condition signalling and handling, and should
be used when making calls to programs that expect the standard
sequence. It is not absolutely necessary to keep pointer
register 6 pointing to the original stack since the stack pointer
is stored in pds$stacks(N) in ring 0, but one should be very
careful about reusing it.
Another reason for having multiple stacks in the user ring is the
use of Control Point Management (CPM). In this case, there are
several standard stacks and the process alternates among them,
setting pds$stacks(N) as it goes. The stack headers of each all
point to the same tables and areas, so that the main difference
between the control points is the procedure activation record.
11
MDD-020 Runtime Environment
A third (obsolete) reason for having other stack segments was to
put the stack somewhere other than in the process directory or to
make experimental changes in format or content.
Having multiple stacks in inner rings is not easy because the
hardware automatically uses the "real" stack when transferring
into an inner ring. Also it is difficult to get out of an inner
ring without having the stack truncated behind you.
2.2.2: THE USER FREE AREA
The ring's area segment contains the Reference Name Table (RNT),
ipc_'s Event Channel Table (ECT), the linker's search rules,
copies of programs' linkage and internal static sections, and
external variables such as Fortran COMMON that do not live in the
file system hierarchy. The whole segment is used as a PL/I area
managed by the Multics system area software. In addition this
area is extensible, which means that if an allocation doesn't
fit, a new segment is automatically created and threaded to the
previous one (as long as the allocation size itself is smaller
than a single segment).
The RNT is actually allocated in a separate area that is itself
allocated in the user area. This keeps the RNT more compact so
as to avoid excessive page faults while referencing it. If the
RNT area becomes too small, a new one is allocated and the old
one is copied and released.
Since the user area is accessed via a pointer in the stack
header, a user may create his own area anywhere he wants to and
is able to and then change stack_header.user_free_ptr to point to
it. All of the system-managed tables allocated in the user area
are located via pointers in the stack header so they will
continue to be used in their old locations. Any tables allocated
after the area change will be in the new area.
Of course since any information in the area can be tampered with,
the system should never assume otherwise when making security
decisions. Any malicious or accidental change to system tables
stored in a ring's area should affect only that ring or at most
the existence of the process; it should not affect the security
operation of an inner ring.
2.2.3: TEMPORARY SEGMENTS
The process directory is a good place for system programs to put
their temporary storage, since its record quota is independent of
the user's permanent hierarchy quota. Thus the user does not
need to worry about the amount of space that a compiler or editor
may require, but only about the space the completed file
12
Runtime Environment MDD-020
requires. However, there is a quota for the process directory;
although it is generous, it is not infinite.
A temporary segment may have any name as long as it includes a
unique string. The mechanism normally used is that of (get
release)_temp_segments_, which manages a pool of temporary
segments. The segments are created as needed. Releasing a
temporary segment truncates it and returns it to the free pool.
13
MDD-020 Runtime Environment
_3_: _P_R_O_C_E_S_S _C_R_E_A_T_I_O_N
Creating a process on Multics is relatively expensive since there
are several segments to create and initialize. Much of this is
due to the method of address space management, which requires
several tables and process variables for its maintenance.
The new process must do part of the work itself to ensure that
the proper non-ring-zero environment is set up. The runtime
support procedures used outside of ring zero are dynamically
linked to. Many users have the ability to specify where their
own versions are, so all of this linking must be done by the new
process. It also must be done before the process reaches command
level.
_3_._1_: _P_r_e_p_a_r_a_t_i_o_n _b_y _t_h_e _C_r_e_a_t_i_n_g _P_r_o_c_e_s_s
The creating process (usually the Answering Service) is
responsible for the identification and authentication of the user
and for obtaining the correct user attributes from tables such as
the Project Definition Table (PDT). These operations are for the
most part not done in ring 0 and are described in MDD-010 on
System/User Control.
The actual creation of the process itself is done by
hphcs_$create_proc. Access to it is highly restricted because it
fills in the process's ring 0 data fields that define the user's
access identity and authorization information. Before doing
anything else, create_proc checks the requested authorization and
max_authorization to make sure they are within the system bounds.
Then it sets up the process by creating a process directory with
its ring 0 segments and obtaining an Active Process Table (APT)
entry and filling it in.
The process directory is created in >process_dir_dir with SMA
access for the user and the creating process and null for
everyone else. It has a minimum quota of 10 directory records
and 20 segment records.
The ring 0 segments dseg, KST, PDS and PIT are created in the
process directory with REW access for the user and the creating
process and null for everyone else. The ring brackets on the PIT
are changed to 0,N,N, where N is the highest allowed ring as
obtained from create_proc's input structure. The dseg, KST and
PDS are made encacheable because they are not shared. (This
encacheability is only respected by the L68 CPUs, since all
segments are encacheable on the DPS8/M CPUs.) The parts of the
dseg and the KST that correspond to the ring 0 segment numbers
are copied from the creating process's dseg and KST respectively
since they are the same for all processes. The contents of the
PIT are copied from a template provided as input by the creating
14
Runtime Environment MDD-020
process. The PDS fields that are filled in are those that won't
change and those that must be initialized to something other than
zero. Many of these values are security-related and come from
the input structure.
The name of the home directory is stored in pds$homedir and is
normally copied from the input structure. However there is an
unused option to have create_proc create a temporary home
directory off the process directory.
It is a little tricky to work in two address spaces at the same
time. Care must be taken to always use the correct segment
number. In addition, initiating another process's ring 0 segment
is a privileged operation.
create_proc must also make the process runnable. It obtains an
Active Process Table entry (APTE) from pxss and fills it in. The
use of the APT is described in MDD-019 on the Scheduler. Two
fields in the APTE are used by ipc_ to validate channel names,
ipc_r_offset and ipc_r_factor. ipc_r_offset is set by
create_proc. ipc_r_factor is set after an indeterminate delay by
init_proc so that its value can not be determined from
ipc_r_offset.
When create_proc returns to its caller, the new process is left
waiting to be run whenever the scheduler gets around to it.
_3_._2_: _P_r_e_p_a_r_a_t_i_o_n _b_y _t_h_e _N_e_w _P_r_o_c_e_s_s
When the scheduler sees a new process that has not yet been run,
it causes execution to begin in init_proc in ring zero.
init_proc initializes some things that couldn't be initialized by
the answering service, creates an environment in the initial
(nonzero) ring, determines the name of the initial procedure, and
finally invokes it.
3.2.1: INITIALIZING THE ENVIRONMENT
The items initialized are the pathname associative memory, the
KST's numbers for the max/min non-ring-zero segment numbers
allowed in the process, and pds$stacks(0). The validation level
is set to the initial ring so that all segments being referenced
will actually be made known in that ring.
The environment in the initial ring is initialized by makestack.
It creates a stack for the initial ring in the process directory,
taking care not to create through a link. It is responsible for
filling in the stack header. Since several of the items are
procedure pointers that must be acquired through the dynamic
linker, it is necessary first to initialize the environment
15
MDD-020 Runtime Environment
needed by the linker. link_man$get_initial_linkage is called to
do this.
The linker needs a place to allocate linkage/static sections and
it needs tables to enable it to find them. To satisfy this,
link_man$get_initial_linkage creates an area, LOT and ISOT for
the ring. The area is created as a separate segment in the
process directory and the area pointers in the stack header are
set to point to it. (See the section on the area mechanism.)
The LOT and ISOT are each max(pds$lot_stack_size, 512) words long
and are located sequentially at the beginning of the stack, with
the LOT first. Neither is explicitly initialized, so their
initial entry values are zeroes. Since the first 200 (octal) or
so entries corresponding to ring zero segment numbers are not
used by the linker, that space is used for other things. The
stack header overlays the beginning of the LOT and the System
Condition Table (SCT) overlays the beginning of the ISOT.
stack_header.stack_begin_ptr, which determines the location of
the first stack frame, is set to point to the end of the ISOT.
Back in makestack, there is a little more to do for the linker,
namely to initialize the Reference Name Table (RNT). The RNT
consists of linked nodes that are dynamically allocated, so it
needs an area in which to allocate . In order to keep the RNT
from being fragmented across many pages, a separate RNT area is
created inside the linker area. Inside this area makestack
initializes the RNT header and the search rules.
Now that the linker can be used, makestack gets pointers to
various procedures such as signal_, pl1_operators_, and some
static condition handlers to put in the stack header. When
invoking the linker on behalf of an outer ring, it is necessary
to call it explicitly, rather than referencing through
compiler-generated links. The latter would already have been
prelinked during system initialization; even if they weren't,
referencing them while in ring zero would cause the linker to try
to link in the ring zero environment. The search rules used at
this point do not include the referencing directory and may or
may not include the working directory (see below).
3.2.2: FINDING THE INITIAL PROCEDURE
After the initial ring environment has been initialized,
init_proc must determine the initial procedure to be called.
There is a default for this, but some users have the ability to
specify alternatives. The mechanisms for doing this are
described below, even though they are also described elsewhere.
This will be easier to explain if the default mechanism for
getting to command level is given first. If no alternative is
specified, init_proc "calls out" to initialize_process_ in the
16
Runtime Environment MDD-020
initial ring. After doing more environment initialization,
initialize_process_ calls the procedure specified by
pit.login_responder, which is normally process_overseer_.
process_overseer_ returns the initial command line to
initialize_process_, which then calls the listener.
Now for the alternatives: Users with the vinitproc attribute can
replace the non-ring-zero procedures with their own. There are
two ways to do this. One is to specify a replacement name; the
other is to put different procedures with the same name (or links
to them) in the home directory.
A replacement name may be specified either in the PDT or in the
login line and is identified by the keyword initproc. This name
is passed to the process as the string pit.login_responder. If
the keyword direct is also used, the name replaces
initialize_process_ and is called directly by init_proc.
Otherwise when initialize_process_ calls pit.login_responder the
replacement will be invoked instead of process_overseer_.
Replacements for all the non-ring-zero procedures referenced
during process initialization can also be put in the home
directory. This includes procedures that are pointed to by stack
header variables. This works because the procedures are found by
the linker using the search rules, and the home directory is
added to the search rules (as the working directory) for users
with vinitproc. Users without vinitproc have null referencing
directory and working directory search rules until just before
the listener is called, so their processes find everything in the
system libraries.
The two mechanisms above may be used together. If a replacement
name is a pathname, it will be found in the specified directory.
But if it is just an entryname, it will be searched for first in
the home directory.
"Direct" procedures are always specified by pathname. If the
directory is not given explicitly, the home directory is assumed.
init_proc has to go to some trouble to make sure that the exact
procedure specified is invoked. The problem is that the dynamic
linker is used to find the procedure and it determines the path
from the search rules. Since the first two search rules are
initiated segments and referencing directory, init_proc actually
initiates the procedure, which causes the name to be added to the
RNT (list of initiated segments), and also passes the resulting
pointer to the linker to be used in determining the referencing
directory.
When init_proc has all the information that it can get about the
initial procedure, it calls call_outer_ring_ to invoke the linker
and to transfer to the initial procedure. This is the only time
in the process when call_outer_ring_ can be used in ring zero.
17
MDD-020 Runtime Environment
See the subsection on outward calls in the section on ring
crossing mechanisms.
3.2.3: COMPLETING THE USER RING INITIALIZATION
When the process reaches the initial ring it must do more
environment initialization, since only the minimum amount was
done in ring zero. This includes setting up more static
condition handlers such as the ones for timers, initializing the
basic I/O switches, and establishing a "default" condition
handler for the ring. Without these in place the process might
easily terminate itself.
After the environment is complete, initialize_process_ invokes
pit.login_responder to determine the initial command line and
optionally to go to command level. The login responder provided
by the system, process_overseer_, turns on the command_query_
escape mechanism to the command processor and looks for
start_up.ec, unless the user has specified -no_startup during
login. It looks first in the home directory, then in the project
directory and finally in >system_control_1. process_overseer_
lets initialize_process_ actually call the listener.
3.2.4: INITIALIZER DIFFERENCES
Process initialization is somewhat different for the initializer
(system control) process. In this case init_proc calls
system_startup_, which runs a basic command level in ring 1 to
allow the operator to do reloads, etc. The environment at this
level is quite primitive. The "stan", "mult" or "star" commands
can be used to enter a ring 4 environment that is much more
powerful. See MDD-010 on System/User Control for details.
18
Runtime Environment MDD-020
_4_: _R_I_N_G _C_R_O_S_S_I_N_G _M_E_C_H_A_N_I_S_M_S
This section discusses ways in which rings may be entered and
left, as well as other mechanisms that affect how programs serve
less privileged rings.
Rings on Multics are hierarchical with the user in direct control
of only the least-privileged (highest-numbered) ring used by the
process. Programs in lower-numbered rings are invoked only to
provide relatively short-lived services on behalf of the user's
ring. They do not do direct I/O nor do their stack histories
remain when the ring is left. This is true even under Control
Point Management (CPM), when there may be several user-ring
stacks. There is still only one stack for each inner ring, and
all control point scheduling is done when the process is running
in the user ring.
_4_._1_: _G_a_t_e_s
Gates are executable segments with special characteristics.
Because they are important for security and are implemented in
such a stylized way, they are discussed in detail.
4.1.1: WHAT GATES ARE
In order to guarantee that programs executing in lower rings
behave as they were intended, it is necessary to restrict how
they can be entered. It must not be possible to circumvent
access checks, etc. by transferring to an arbitrary location
from an outer ring. In Multics, the only ways that a user can
enter a lower ring are by calling special gate programs or by
executing certain faults. Only a few faults are actually handled
in the TCB and their processing is narrow in scope and well
defined. They will be discussed later. For all practical
purposes, calling a gate is the only way to enter a lower ring.
Gate segments have two main distinguishing features. One is that
their ring brackets usually force them to execute in a ring that
is lower than the calling ring. With ring brackets of r1,r2,r3,
r1:r2 inclusive is the read/execute bracket and r2:r3 inclusive
is the call bracket; gates are defined by having r2 < r3. In
rings > r2, only the call6 instruction may be used to reference
the segment. The second feature is an entrybound--a limit on the
text section locations that can be transferred to. Gates are
specially coded in ALM with a transfer vector at the beginning;
the entrybound is set at the end of the transfer vector so that
gate segments can be entered only through the transfer vector.
The entrybound is actually checked by the hardware when it
executes a call6 instruction that is transferring to a lower ring
19
MDD-020 Runtime Environment
via a gate segment. If the referencing offset exceeds the
entrybound, the not_a_gate condition is raised. Since all
hardware references to a segment go through the segment
descriptor word (SDW), the entrybound is kept there along with
the ring brackets. For non-hardcore gates, the entrybound in the
SDW is filled in at segment fault time, i.e., when the SDW
contents are updated. At that time the entrybound is copied from
the segment's branch in the file system hierarchy if the gate bit
in the SDW indicates a gate. Thus when installing a gate, it is
important to set the segment's entrybound attribute in the branch
before resetting the ring brackets. For hardcore gates, the
initial process's SDW entrybound field is filled in by
init_hardcore_gates during system initialization. All other
processes copy the hardcore SDWs during process creation.
The call6 instruction is the only one that recognizes the call
bracket and thus is the only instruction that can be used to
change the ring of execution. All other transfer instructions
get a not_in_execute_bracket condition if they try to transfer to
a different segment that has r2 lower than the executing ring.
The call6 instruction also sets pointer register 7 to point to
the base of the lower ring stack. The hardware obtains the stack
segment number by adding the target ring number to the ring 0
stack segment number found in the descriptor base register. Thus
the calling ring cannot affect the inner ring's choice of
environment. There are no further software mechanisms to allow
control points in inner rings, etc. The call6 instruction may
not be used to change the ring of execution to a higher ring. An
attempt to do so results in an outward_call condition.
Gate segments should do only the minimum amount of work necessary
to get control transferred to other inner-ring segments. This
work is described below, but in practice gate coders need know
nothing of the details. There are easy to use macros defined in
gate_macros.incl.alm that allow one to define a gate entry simply
by giving the entry name, target name, and number of arguments.
In general, gate source segments contain only a list of macro
calls. Exceptions include the hcs_ entries to return the virtual
cpu time used. These entries are used for metering, so
eliminating overhead is critical; they are coded in the gate
segment itself.
4.1.2: NON-HARDCORE GATE ACTIONS
A non-hardcore gate entry immediately transfers to the part of
the gate segment beyond the transfer vector, where it "calls" an
internal setup "subroutine", loads the indicator register with
zeroes, and does a short_call (no registers saved) to the target,
passing the argument list that it received. When the target
returns, the ordinary ALM return operator is used to leave the
gate.
20
Runtime Environment MDD-020
The setup "subroutine" is really a piece of common code that is
transferred into and out of. It pushes a stack frame with
prev_sp pointing to the last stack frame used by the calling
ring, loads pointer register 4 with the gate's linkage pointer
(as found in the inner ring's LOT) so that the short_call
operator can find the link to the target, and checks the number
of arguments passed to it against the number expected, which is
stored two words before the "calling" gate entry's code in the
main part of the gate. If the argument counts don't match, the
gate_error condition is signalled.
4.1.3: HARDCORE GATE ACTIONS
Hardcore gates are somewhat more complicated. In addition to the
actions taken by non-hardcore gates, they have three extra tasks:
to establish a handler for the bad_dir condition if requested, to
keep metering data for the gate entry, and on return to check for
and to try to fix impending ring alarms.
4.1.3.1: bad_dir Condition Handler
Gate entries that want a handler for the bad_dir condition
specify "bad_dir_trap" as the fifth argument to the hgate macro.
The bad_dir condition is signalled by directory control when it
encounters a defective directory, so all gate entries involved
with accessing directories should have bad_dir handlers.
When bad_dir_trap is specified, the gate entry creates an on unit
for the bad_dir condition in space reserved in the stack frame.
The handler checks the ring number in PR6 to make sure that it
was called in ring zero and then unwinds back to the original
gate entry frame, which must be the first frame on the ring zero
stack. (If it isn't, the signal is continued.) After the
nonlocal transfer, common code in the gate segment turns off the
condition handler, calls verify_lock$verify_lock_bad_dir to
invoke the salvager, and then transfers back to the original gate
entry for a retry, including resetting the condition handler.
As little of this extra code as possible is put into the transfer
vector section. What is necessary are three transfers--one to
the code that sets up the on unit, one to the handler itself that
unwinds, and one to the code that calls verify_lock. The last
two transfers, as well as all the related code in the "main" part
of the gate, are shared among all the gate entries with bad_dir
handlers. The on unit setup code stores the location of the
original gate entry in the stack frame so that the common code
will know where to transfer to after calling verify_lock.
21
MDD-020 Runtime Environment
4.1.3.2: Metering
Each hardcore gate entry keeps its own metering data in internal
static. It stores cpu time, virtual cpu time, page waits, and
number of calls. Of course this metering includes any retries
because of the bad_dir condition. The actual code used for this
is shared among all gate entries. The common setup code
initializes some variables in the stack frame and the common
return code adds the results to the variables in internal static.
The return code is passed the address of the gate entry's static
storage. This address is also stored in the word immediately
preceding the gate entry's non-transfer-vector code.
4.1.3.3: Checking for Ring Alarms
The hardcore gate common return code also checks for an impending
ring alarm. The ring alarm mechanism is discussed in more detail
in another section of this MDD; briefly, if the ring alarm
register contains a number greater than the target ring number of
a transfer instruction, a ring_alarm fault is signalled. The
reason for the ring alarm is stored in the PDS; in some cases the
problem can be corrected and the ring alarm can be reset. It is
up to the gate return code to check whether the ring alarm is
set. If it is set, the ring alarm count meter is incremented and
ring_alarm$poll is called to try to reset the alarm. Depending
on the output from ring_alarm$poll, the gate entry either does a
normal return through the alm return operator or an in-line
"short return" and transfer to the traffic controller
(pxss$pre_empt_poll). In the latter case the stack frame to
return to is stored in pds$pre_empt_poll_return.
4.1.3.4: Obtaining the Ring Zero Linkage Pointer
Hardcore gates obtain their linkage pointers from a text location
instead of from the LOT. (The pointers are initialized during
system initialization; there are external definitions for the
pointers' text locations.) This is necessary because hardcore
gates each have two segment numbers--one for ring zero and the
other for rings greater than zero--and the non-ring-zero segment
numbers, which they were called by, are not represented in the
ring zero LOT. Pointers to the gates' linkage sections are
written into the gates' text sections following the transfer
vectors by init_hardcore_gates during system initialization.
4.1.3.5: Fast Hardcore Gates
Some hardcore gate entries do only the absolute minimum to get to
their targets--load the indicators and linkage pointer and
transfer to the target. Since they do not push stack frames,
22
Runtime Environment MDD-020
they are not returned to, which means that they do not have
bad_dir handlers or meter or check for ring alarms. Therefore
they cannot be used for activities that require such support.
4.1.4: GATE ACTORS
All gate segments have a special unnamed entrypoint that returns
information about any of the other gate entrypoints. This is
helpful when one wants to see such information but is not within
the read/execute bracket. In this case, the user has a right to
know what gate entries can be called but cannot read the gate's
definitions directly. These special entypoints are called gate
actors.
A gate actor entry must be within the transfer vector and at a
known offset, since it has no external name. It is actually at
gate location 0. Its calling sequence consists of two arguments,
a PL/I varying character string and a fixed bin (35) number,
corresponding to the desired entry's name and location
respectively. If the name is null, the specified location is
used to find the name. Otherwise, the name is used to find the
location. All the work is done within the gate itself in the
non-transfer-vector section.
Gate actors in non-hardcore gates work only if the process has
already snapped a link to one of the gate's other entries. They
depend on the linkage section having been combined in the ring of
execution, which for gates is only done by the linker when it
processes a link fault.
Gate actors are not really necessary since there could be ring
zero utilities to provide the same information.
hcs_$get_defname_ does return the entry name associated with the
specified offset, but the system does not provide a general
utility for the reverse.
4.1.5: GATE MACROS
As can be seen from the discussion above, the reliability and
maintainability of gates depends on having macros to generate all
the code. It is very easy to read gate source code, which is
just a list of macro calls. It is harder to understand the
generated code and much harder to look at the macros themselves
to figure out what they do. The macros use multiple location
counters, labels with the same names in different macros, and a
lot of small "sub" macros. The following description of how the
macros work probably should be in the source, but isn't.
The gate macros use three location counters for the text section:
transfer_vector, tv_end and main, joined in that order. The code
23
MDD-020 Runtime Environment
itself is in the main part; the transfer vector contains only one
word per gate entry that transfers to the entry's code in main.
tv_end specifies the entrybound and, in hardcore gates, includes
the segdef .tv_end with the value of the entrybound. The linkage
location counter is used for the metering data in internal
static. The metering data for a gate entry has the label
<entry_name>.t.
The first statement in a gate source segment, after the name,
invokes either the gate_info or the hardcore_gate_info macro.
Both include a transfer for the gate actor and use the gate_actor
macro to put the actor code in main. They differ in the way they
obtain the linkage pointer. Both gate_info macros also include
the setup code, labelled by .setup. hardcore_gate_info
additionally includes segdefs for .tv_end and .my_lp as well as
the code for metering and ring alarm checking to be performed
when the gate entry returns. It also defines the automatic
variables to be used for metering and bad_dir condition handling.
The macros that source programs use to define gate entries are
gate, hgate and fgate. All of these use the gentry macro to
produce the transfer vector transfer and to define the transfer
target location in main. fgate uses no other macros or common
main code pieces. gate and hgate then transfer to .setup, which
in both cases pushes a stack frame and uses code from the macro
gcheck to check the argument count. gcheck code then signals the
gate_error condition if the argument count is not what was
expected. The .setup code used by hgate also stores the starting
information for the meters.
hgate macros use other pieces of common code. If the fifth
argument is "bad_dir_trap", a transfer is made to establish the
bad_dir condition handler. This code in included by the
bad_dir_handler macro, which is put in the source after the last
hgate macro. When the gate entry target returns, the hgate code
loads a pointer to the entry's internal static meter data and
transfers to the common return code. hgate also defines the
internal static space for the entry's meter data.
The code inserted by the bad_dir_handler macro has several parts:
transfers in the transfer vector so that signal_ and unwinder_
can invoke code in the gate, code labelled by .set_dir_trap to
establish the bad_dir on unit, code labelled by .handler to be
invoked as the bad_dir handler, and code labelled by
.handler_restart_point to which the handler unwinds.
_4_._2_: _V_a_l_i_d_a_t_i_o_n _L_e_v_e_l
The validation level can be thought of as the logical ring of
execution. It is a software mechanism used by inner ring
programs to determine on which ring's behalf they are acting. It
24
Runtime Environment MDD-020
is used by ips_, ipc_, ioi_, the linker, the file system access
mechanism, and the salvager, among others.
Most of the time the validation level is set to the highest ring
being used in the process since that is where the user "is". It
is set to that value by call_outer_ring_ when the ring is first
entered. A lower ring program can temporarily reduce the level,
but it must save the old value and restore it before returning.
There should be a cleanup handler to make sure that the old value
is restored.
It is important that the validation level never be lower than the
executing ring because that would allow the executing ring to get
the TCB to do things on behalf of an inner ring. In order to
enforce this, the level number itself is maintained by the TCB.
It is stored in pds$validation_level, which is directly
accessible only in ring zero. The only programs that are
supposed to reference it directly are the hardcore procedures
level and ring_alarm, so that the appropriate checks can always
be made. Non-hardcore programs can call level$set and level$get
via cu_, which is just a writearound to hcs_ in this case.
Because it is so important for the level to be restored
correctly, and because the restoration process is voluntary and
can be bypassed occasionally, it is necessary to have a fail-safe
way to make sure that the level is restored correctly when an
outer ring is returned to. The hardware ring alarm register is
used for this. It is maintained by the procedure ring_alarm and
can be set to fault when a specified ring is entered from below.
If a ring_alarm fault occurs, ring_alarm$fault has a chance to
fix certain things before the target ring is returned to. In the
case of the validation level, the pds$ring_alarm_val array is
used to determine the correct level to restore.
Of course the TCB must make sure that the ring alarm register is
turned on whenever the validation level is changed to a value
that would be wrong for a higher ring. The actual rule enforced
is more exclusive: when an inner ring is left for an outer ring,
the validation level must be the same as when the ring was
entered, unless the outer ring is being entered for the first
time. The validation level - ring alarm connection is made by
having level$set call ring_alarm$reset and by having everyone who
wants to change the level call level$set. Outside of ring zero
it is possible to change the level only by calling hcs_$level_set
(via cu_$level_set).
level and ring_alarm communicate via the pds$ring_alarm_val
array. level sets the values in the array and then ring_alarm
looks at it to determine what to do. level$set makes sure that
the only values in pds$ring_alarm_val(current_ring) are either 0
or the validation level at the time the ring was entered. It
does this by saving the old level value only when
25
MDD-020 Runtime Environment
ring_alarm_val(current_ring) is zero and by storing zero only
when the new level value is the same as the stored value.
level$set calls ring_alarm$reset, which sets the ring alarm
register to current_ring+1 if pds$ring_alarm_val(current_ring) is
not zero and which turns off the ring alarm register if
pds$ring_alarm_val(current_ring) is zero (unless there is some
other reason to turn it on). pds$ring_alarm_val(current_ring) is
always reset to zero when the current ring is returned from (see
below). level$set calls ring_alarm$reset whenever the validation
level is changed, but really only needs to call it whenever
pds$ring_alarm_val is changed.
If the ring alarm goes off, or a hardcore gate return discovers
an impending ring alarm, another entry in ring_alarm is called to
restore the validation level if necessary. The validation level
is set in turn to nonzero values of pds$ring_alarm_val(ring) for
every ring from ring 0 to target_ring - 1, thus ending up with
the correct value. ring_alarm does ensure that the final
validation level is not less than the target ring. If this
operation did indeed change the validation level, syserr is
optionally called to print a message.
Although level always runs in ring 0, it must know the ring it is
acting on behalf of. This is accomplished by having the hcs_
entries to level be fgates. fgates do not push stack frames, so
PR6 still points to a stack frame in the calling ring. This
enables level to get the "real" ring number from PR6.
If level finds that the ring number argument is invalid it calls
level_error, which is coded in PL/I, to signal the
validation_level_error condition. This condition will usually
make it out to the user ring since it is generally not handled in
lower rings. If the specified ring number is greater than 7,
level_error first calls syserr to print the address of the
caller, since there is likely to be a bug and the caller
information might otherwise get lost during the condition
signalling.
It is possible to "call" an outer ring without updating the
validation level, causing the outer ring to run with a lower
validation level. This can be done only by a non-system provided
procedure. It is unlikely that a ring would want to give a
higher ring such privilege. Also the lower level might not
stick. If the new ring is ever returned to with the ring alarm
set, ring_alarm will set the validation level to the correct
value.
level is also the keeper of pds$no_audit_ring1_fs_object_ops. It
is used by the audit mechanism to disable auditing of certain
file system operations done on behalf of the ring one part of the
TCB. It is set only by level$set_admin_gate, which can be called
only from rings 0 and 1. This entrypoint automatically turns on
26
Runtime Environment MDD-020
pds$no_audit_ring1_fs_object_ops if the initial ring is greater
than one and if active_hardcore_data$audit_ring1_fs_object_ops is
off. It also automatically sets the validation level to 1.
level$set turns off pds$no_audit_fs_object_ops when the
validation level to be set is greater than 1. ring_alarm also
turns off the flag when the target ring is greater than one.
_4_._3_: _T_h_e _R_i_n_g _A_l_a_r_m _M_e_c_h_a_n_i_s_m
The hardware ring alarm register can be used by the system to
make sure that certain things are cleaned up or checked for
before a ring is left for a higher ring. If the register
contains a nonzero number, and a transfer is made to a ring equal
to or higher than that number, the hardware signals a ring alarm
fault. This mechanism is used by level, ips_ and set_privileges.
The program ring_alarm does all the ring alarm register
management, including the fault handling. The $reset entry uses
information in the pds and apt to calculate the lowest ring that
needs the ring alarm register to be set. The $set entry just
sets the register to the specified ring, with the risk that a
lower ring might be bypassed. It is called by proc_int_handler,
which turns process interrupts into ips signals. The $fault
entry is the handler for the ring_alarm fault. It resets certain
pds fields such as validation_level and
no_audit_ring1_fs_object_ops to be correct for the target ring.
It then "calls" the reset entry, since another, higher ring may
now need a ring alarm. The $poll entry is similar to the $fault
entry but is called by the hardcore gates before they return if
they detect an impending ring alarm. This not only saves the
cost of signalling but allows the opportunity of an orderly call
to pxss (the traffic controller) if the process is supposed to be
preempted or stopped. Since the ring alarm software is available
only in ring zero, non-hardcore gates cannot use it.
_4_._4_: _B_r_i_e_f _S_u_m_m_a_r_y _o_f _F_a_u_l_t _H_a_n_d_l_i_n_g
Fault handling is discussed in detail in MDD-021 on Fault and
Interrupt Handling, but some explanation is helpful in the
context of this MDD. After all, a process does enter ring zero
when a hardware fault occurs. The procedure fim (fault intercept
module) is usually invoked when there is a hardware fault. It
decides which faults should be handled in ring zero and calls the
appropriate handlers for them. Such faults include link, segment
and page faults. In these cases the fim saves the machine
conditions as they were when the fault occurred and automatically
restores them when the called handler returns. The intended
result is to make the fault service invisible to the user
program. All faults not specifically handled in ring zero, as
well as faults whose ring zero handlers encountered errors, are
27
MDD-020 Runtime Environment
signalled by the procedure signaller in the ring in which the
fault occurred. In no case is the fault mechanism intended to be
used explicitly by non-hardcore programs to request services of
the supervisor.
_4_._5_: _E_x_i_t_i_n_g _a _L_o_w_e_r _R_i_n_g
There are several ways in which a lower ring may be left for a
higher one. The most common one by far is a return from an
inward call through a gate. However it is also possible to leave
because of an unexpected condition, to execute a nonlocal goto to
a higher ring, and even to explicitly call out. All methods use
the rtcd (return control double) instruction to make the
transfer, because that is the only instruction that makes the
ring numbers in all the pointer registers be equal to the target
ring. An attempt to run with pointer register ring numbers less
than the current ring would soon lead to faults. All methods
also result in the inner ring's stack history being truncated.
4.5.1: NORMAL RETURNS
Most of the time an inner ring is entered by calling a gate and
left by a normal return. The gate does a normal push, which
stores the value of PR6 at the time of the call in the stack
frame's prev_sp. The normal return copies prev_sp back into PR6
and calculates PR7. It then uses the return_ptr in the stack
frame pointed to by the restored PR6. There is no stack history
left on the inner ring stack after the return since the stack's
first frame was abandoned. fgate entries generally don't push
stack frames, but then they don't change PR6 either.
4.5.2: CONDITION CRAWLOUTS
The term "crawlout" is used when a condition has been signalled
in an inner ring but has no handlers in that ring. signal_ then
"crawls out" of the inner ring to continue signalling the
condition in the calling ring. (Rings between the current ring
and the ring that called it have no stack history and so can be
ignored.) Before leaving, signal_ creates a frame for itself on
the next higher ring's stack and "unwinds" the inner ring's stack
by calling unwind_stack_ to invoke any cleanup handlers. signal_
does not explicitly mask ips signals for the ring being left, but
probably should. It calls nonlocal_goto_$different_ring to
actually make the transfer.
nonlocal_goto_$different_ring is called with a pointer to the
target stack frame and a pointer to the location to be "returned
to". It completes the logical truncation of the inner ring stack
by resetting stack_header.stack_end_ptr, uses the stack frame
28
Runtime Environment MDD-020
argument to reset PR6 and PR7, resets the indicators, and does a
rtcd to the specified location.
The crawlout mechanism should not be confused with the fim
mechanism. The fim is basically a dispatcher, figuring out where
to start signalling. Crawlouts occur after a condition has
already been signalled in an inner ring but has no handler in
that ring. Sometimes several rings are crawled out of before a
handler is found.
4.5.3: TRANSFERS TO LABELS IN HIGHER RINGS
A nonlocal goto to a label in a higher ring works in much the
same way as a crawlout. In this case it is unwinder_ rather than
signal_ that creates a stack frame for itself in the calling
ring's stack and calls nonlocal_goto_$different_ring. Of course
in this case the stack being left will already have been cleaned
up.
4.5.4: OUTWARD CALLS
The Multics system provides two mechanisms for making "calls" to
procedures in outer rings: the older outward_call_handler, which
handles the outward_call condition, and the newer
call_outer_ring_, which avoids the condition. Neither one can be
used for arbitrary calls, since there are several restrictions.
Only a null argument list is passed, and it is created in a fixed
location in the target ring's stack by the call mechanism. The
calling program can never be returned to because the inner ring
stack history will be destroyed. To enforce this, PR6 is set to
null before the actual transfer. This becomes prev_sp in the
called program's stack frame and will cause a fault if a return
is attempted. The null prev_sp also means that the called
program's stack frame is not threaded to any previous stack
history in the target ring; however that stack history does
remain because the called program starts its frame at the
location specified by stack_header.stack_end_ptr.
Only one call out of ring zero is permitted during the life of
the process, to call the initial nonhardcore procedure. This is
enforced by the flag pds$first_call. It is up to configuration
management to ensure that any ring zero caller of rtcd_util_
(used by call_outer_ring_) or its equivalent checks
pds$first_call. This first transfer out of ring zero to
bootstrap the process into the initial ring is the main reason
for the existence of the call out mechanism.
Both programs truncate the stacks in all the rings between the
caller (included) and the target (not included), mask ips signals
in those rings as well, and set the validation level to the
29
MDD-020 Runtime Environment
target ring. The stack truncation is done simply by resetting
stack_header.stack_end_ptr, without executing any cleanup
handlers. The truncation has two consequences that the reader
should be aware of. One is that after the truncation, no call
should be made in the current ring to a program that might push a
stack frame. Although the stack is logically truncated, it is
still being used for automatic storage, so that a new frame
allocated at the beginning of the stack could destroy part of the
calling program's stack frame. In addition, the new frame would
be back-threaded to the calling frame, so at best the back
threads would loop, become garbage, or go off on a wild goose
chase. The restriction on calls applies to the condition
signalling mechanism as well, which is one reason that ips
signals are masked at this point. The other consequence of stack
truncation is that all on-units in the stack are wiped out. This
especially relevant when a call is being made out of the initial
ring. It is up to the first program called in a new higher ring
to establish an any_other handler and initialize the I/O
switches. Otherwise the signalling of most conditions will cause
the process to terminate because of either the lack of a handler
or because the error_output switch is unavailable. If the
initial ring still needs an any_other handler, it will have to be
reestablished each time the ring is entered.
outward_call_handler and call_outer_ring_ differ in how they
prepare the target environment and affect the registers.
4.5.4.1: outward_call_handler
outward_call_handler is invoked in ring zero by the fim when
there is an outward_call fault, i.e., when there is a non-rtcd
transfer to a higher ring. It spends most of its time adjusting
the fault machine conditions. PR6 is set to null, PR7 to the
base of the target ring's stack (calculated from the ring
number), and PR0 to the null argument list created just after the
stack header in the target ring's stack. The ring numbers in all
the pointer registers, as well as the prr and trr, are set to the
target ring. The saved instructions are both set to be straight
tra's, since a call instruction would cause the segment number in
PR6 to be set to the segment number in PR7, which we don't want
(we want PR6 to stay null). It is probable that an rtcd
instruction could not be effectively inserted into the machine
conditions at this point. Setting the prr in this case is what
will cause the process to be running in the target ring.
It is not obvious how the outer ring environment gets set up. If
the target program was linked to, the linker probably found the
target using the calling ring's search rules. But then it would
have created an environment for the target ring (if necessary)
and combined the linkage section in the target ring. If the
target program was not linked to, its linkage section will not be
30
Runtime Environment MDD-020
combined in the target ring. However, the target stack and
environment are created, if they do not already exist, when the
null argument list is created. That is when the stack segment is
first referenced. seg_fault, seeing that the segment is a
nonexistent stack, calls makestack to create and initialize it.
4.5.4.2: call_outer_ring_
call_outer_ring_ is intended to be a more desireable way to make
a call to an outer ring. It must be called intentionally. It is
given a name and invokes the linker on it to ensure that the
target program's environment is properly initialized. Because it
can run in any ring from 0 to 5, it must call the proper hcs_
interfaces to do things like changing the validation level
instead of changing the pds directly. The first four words of
the target stack are used for the null argument list. Unlike
outward_call_handler_, call_outer_ring_ allows calls to rings
inside the initial ring (e.g. from ring 2 to ring 3).
However, even call_outer_ring_ has some less than straightforward
features. If the target ring was uninitialized, the obscure
seg_fault mechanism is still used to call makestack. The linker
does call makestack explicitly if necessary but calls it after
the target stack must be referenced to obtain the search rules.
(In the outward_call_handler case, the linker would have been
invoked before the outward_call fault, if at all, and thus would
have used the search rules of the calling ring.)
call_outer_ring_ establishes an any_other handler to terminate
the process if a condition is signalled while or after the inner
rings are abandoned. However, as can be seen from the discussion
above on the effects of stack truncation, just the act of
signalling at this point can cause the process to get into
trouble.
The alm program rtcd_util_ is called to set PR6, PR7, PR0 and to
execute the rtcd instruction. It doesn't reset the indicators
although it probably should. nonlocal_goto_$different_ring is
not used in this case because it wants a pointer to an existing
stack frame in the target stack, which call_outer_ring_ does not
supply. Instead, rtcd_util_ is passed a pointer to the argument
list, which it knows is at the base of the target stack. This
pointer is used to set PR0 and PR7. Unlike outward_call_handler,
rtcd_util_ does not have to worry about the effect of changing
the machine state in the middle of instruction processing, so it
can use the rtcd instruction to reset the registers' ring
numbers.
31
MDD-020 Runtime Environment
4.5.4.3: User Coded Procedures
It is possible to code and use a non-system procedure to call out
from a nonzero ring without doing all the steps discussed above.
The basic requirements are to get an environment created in the
outer ring, to set pointer registers 0, 6 and 7 (or whatever
registers would be required there), and to execute an rtcd
instruction. The stack does not have to be truncated nor the
validation level set to the outer ring. However, ignoring these
restrictions will affect the interaction between the calling and
target rings and should be done only with extreme caution.
32
Runtime Environment MDD-020
_5_: _L_I_N_K_I_N_G
The way in which linking between procedures is done in Multics is
quite different from the methods used in most other systems.
Dynamic linking is widely used, but several forms of static
linking are available as well.
_5_._1_: _W_h_a_t _D_y_n_a_m_i_c _L_i_n_k_i_n_g _I_s
Most of this section discusses dynamic linking, which is an
important part of the Multics system. In Multics, a reference
from one compilation unit to another is linked at runtime when
the reference is first actually attempted. The system designers
wanted each program to be executed in its own segment so that it
could be shared and participate in the active access control
mechanism enforced via SDWs. In Multics, all addressing of other
segments is done through pointers that contain segment numbers,
so that the target segment's SDW can be indirected through. The
segment numbers of non-hardcore segments are allocated at runtime
as they are needed, so the actual linking must also be done at
runtime. Conversely, the dynamic linking function is one of the
ways the system knows to add a segment to the address space.
The way this feature is implemented offers the user great
flexibility. If a program is not referenced, it is not linked
to. A program can be removed from the address space and another
substituted without changing any of the other links in the
referencing program. Since per-user search rules are used to
locate procedures, it is possible for several users to be using
the same program (not copies) simultaneously and for each user to
be linked to a different set of subroutines.
Dynamic linking also offers savings of both permanent storage use
and loading time. Because subroutines can be shared (i.e.,
executed simultaneously by different users), it is not necessary
to combine a copy of a subroutine with each referencing program.
Because each program unit is then smaller, each is "combined"
into the process by itself when it is first referenced and not
removed unless explicitly requested. It and the subroutines it
calls are usually not recombined again during the login session.
Updating subroutines is easier because relinking is done
automatically. Program maintainers do not have to be notified to
relink manually.
Of course there are disadvantages as well. Because in general
programs are not recombined each time they are invoked, their
static variables (both internal and external) are not
reinitialized automatically each time. In some cases this is
useful, as when collecting cumulative meters. However, some
programs originally written on other systems expect their static
33
MDD-020 Runtime Environment
storage to be reinitialized. They must use special mechanisms
(described below) to get around the per-process scope of Multics
dynamic linking. Another possible disadvantage is that the names
of all segments linked to are added to the process's name space.
People used to Multics know not to use the same name for more
than one segment, but others may not. Again, the latter either
have to change the offending names or hide them by doing some
static linking (see the discussion of the binder and link editor
below). Still another disadvantage is that while programs that
are used often in a process have lower loading overhead, programs
used only once may have higher overhead.
_5_._2_: _T_h_e _E_f_f_e_c_t _o_f _D_y_n_a_m_i_c _L_i_n_k_i_n_g _o_n _P_r_o_c_e_s_s _S_t_r_u_c_t_u_r_e
Providing the features mentioned above has implications for the
object segment format and requires certain process tables.
Describing these at this point will make it easier to understand
the more detailed discussion of how linking is actually done.
5.2.1: LINKING AND THE OBJECT SEGMENT FORMAT
This section describes and justifies the format in general. The
reader should refer to the Multics Programmer's Reference Manual
Appendix G for declarations of the various structures in the
object segment.
5.2.1.1: Linkage Section
The main effect of dynamic linking on object segments is that the
links themselves and the internal static variables must be
writeable by anyone using the program, while the rest of the
segment, including code, constants, symbol table, etc., needs
(and should have) only read and execute access so that it can be
shared. One obvious solution would be to have the writeable
stuff in one segment and the read/execute only stuff in another,
associated segment. This was actually implemented at one time,
with the links in a segment called program_name.link, but it tied
up two segment numbers for each program, which was too wasteful
even for Multics. The links and internal static storage usually
don't take up very much space--in most processes all the
programs' links combined fit into a single segment. Also it was
a pain to always keep all the pieces together. Thus it was
decided to implement another solution, which was to put the whole
program, including the links, into a single read/execute segment
and to make a copy of the links and static for each process that
executed the program. The writeable part was put into a separate
section of the program object segment with its bounds defined in
an object map located at the end of the segment. The copy of the
object's linkage section was then combined with the other copied
34
Runtime Environment MDD-020
(active) linkage sections in a single segment in the process
directory.
5.2.1.2: Definition Section
Another effect of dynamic linking on the object segment format is
that all the names of both the outgoing link targets and the
entrypoints callable from other programs must always be kept with
the program so that the linker can find them easily at runtime.
This information is not writeable and so should not be included
in the linkage section. It also should be separated from the
code since it is not directly involved in execution. Further, it
should be threaded in a way that enables the linker to peruse it
quickly. For all these reasons, it has its own section, the
definition section, which is also defined by the object map.
The entrypoint information used to resolve incoming references is
all threaded together starting at the beginning of the definition
section. Each entrypoint's information is called a definition.
It includes the name, an offset, and a number (called the class)
indicating what object segment section the offset is relative to.
The non-writeable information for each outgoing link is also
stored in the definition section. Each link has several items of
information threaded together, with the offset of the first item
in the unsnapped link. Each link's information is logically
unconnected with either other links' information or the
definitions themselves. The link information includes the type
of link, the name, if any, of the target, an offset if the actual
target location is unnamed, and, for some links to external
variables, the variable's initialization information.
5.2.1.3: Unsnapped Links
An unsnapped link occupies two words, the same size as a snapped
link. Its main functions are to cause a fault when referenced
through and to tell the linker where to find the target
description, which is in the definition section. To cause a
fault, the link has a fault tag 2 instead of a normal pointer ITS
tag. When locating the target information, the linker starts out
with only a pointer to an active copy of the unsnapped link. The
link contains a negative offset to the base of the linkage
section header, which contains a pointer to the definition
section. The link also contains the offset in the definition
section of the beginning of the target information.
5.2.1.4: Obsolete Feature of Definitions in the Linkage Section
For those interested in history and/or more of the possibilities
of dynamic linking, the following may be of interest. It used to
35
MDD-020 Runtime Environment
be possible to have the definitions in the linkage section. They
were located after the links and found via an offset in the
linkage header. There were two main uses for this feature, but
in both the linkage section was in a different segment from the
text section. In one case, the text section contained the
storage for external variables, which were added dynamically as
they were first referenced. As a variable was added, a
definition for it was added to the definition list in the linkage
section. Needless to say, both the text and linkage sections in
this case were writeable. In the other case, the text segment
had only execute access. Since the linker would not be able to
either find or call from the segment unless it could read the
definitions and links, these were both placed in the linkage
section with read access. (Execute-only procedures were used
only on the 645. The current hardware can't read constants from
the same segment in execute-only mode.)
5.2.1.5: Historical Note on Separate Static
There is an option to have the object segment's internal static
template defined as a separate object section located directly
from the object map. This feature was invented for the
prelinker, which no longer exists. The goal of the prelinker was
to provide a preinitialized template process for the user with
limited needs. Overhead was reduced both by not having to do all
the normal process initialization and by sharing several segments
that are usually in the process directory. When creating a
template process, a driver file specified the segments to be
added to the address space and all the links between the included
segments were presnapped. As long as an active prelinked process
did not reference any unsnapped links, it could use the shared
copy of the combined linkage section. However, any attempt to
write to the linkage section would cause a copy_on_write
condition, whose handler would copy the linkage sections to the
process directory. Since there has to be a separate copy of
internal static for each process, the shared links feature would
be worthless if the static were included as part of the linkage
section. Thus it was decided to make internal static a separate
section, addressed by a different pointer, and combined in a
separate segment which would always be copied to the process
directory.
In hindsight, this problem could also have been solved by
addressing internal static as a link to a uniquely-named external
variable, presnapping the link to storage "allocated" in a
segment meant to be writeable. The main thing is for the
translators to know not to access it directly from the linkage
section pointer.
The prelinker was never really used because it never really
worked very well. More recently, more nails were nailed in its
36
Runtime Environment MDD-020
coffin because creating template descriptor segments and KSTs
from the user ring was a security hole.
Even though the original requirement for separate static has
vanished, there is still a useful function for it -- to permit
larger amounts of internal static in bound segments. The binder
(see below) refuses to reference any link beyond offset 16K in
the linkage section because of addressing limitations. Since
links are always addressed through pointer registers, there are
only fifteen bits left for the link offset, and the binder can't
start using index registers to increase the range. A bound
segment's linkage section generally consists of all the
components' internal static concatenated together followed by all
the links, so that a large amount of static would push the links
out of range. Addressing the links and static separately, as is
done for separate static, alleviates this problem. As in the
case above, addressing internal static as a uniquely-named
external variable would also have solved this problem.
5.2.2: THE LINKAGE AND STATIC OFFSET TABLES
The Linkage Offset Table (LOT) is used by each program to get a
pointer to the user's private copy of the program's linkage
section. It is also used by the dynamic linker to locate the
linkage sections of target segments quickly. The Internal Static
Offset Table (ISOT) is used similarly when the program or link
target has a separate static section.
This paragraph explains the rationale behind the LOT mechanism.
As mentioned above, dynamic linking requires that the links be
writeable, while the ability to share programs with per-user
per-segment active access control requires that the code itself
not be writeable. The solution for this was to copy the links
into a per-process writeable segment. Thus the code must use an
explicit segment number to reference its links, i.e., it must
address the links through a pointer register. Moreover, each
object segment must have a pointer directly to its own set of
links. Usually this pointer is acquired during the entry
processing, where speed is important. It is found in the LOT,
which is an array indexed by segment number and accessed through
a pointer in the stack header.
The method of accessing the LOT has two implications. The first
implication is that having the entry operator index into an array
by segment number depends on the ability of the hardware to
obtain the segment number in indexable form from a pointer
register. The original Multics hardware did not have this
ability, so the entries were actually in the linkage sections
themselves and obtained the linkage pointers directly without
referencing the LOT. (This required the combined linkage
sections to have execute access.) The second implication is that
37
MDD-020 Runtime Environment
the indirect addressing of the LOT permits the LOT to be moved
when it outgrows its allocated size. However, moving the LOT is
not always desireable, such as when a process has several control
points, all with stack headers pointing to the same LOT. The LOT
moving mechanism, which runs in ring 0, doesn't know about
control points and ignores all stack headers except the current
one. Therefore the control point manager grows the LOT to its
maximum size before creating any control points.
The LOT array consists of one-word entries that are initialized
to zero. There is one entry for each segment number. When a
segment's linkage section is combined, a packed pointer to the
active linkage section is put in the segment's LOT entry.
There is, in addition, a third type of value that a LOT entry may
have. When a segment is initiated, the entry corresponding to
the assigned segment number is set to a special faulting packed
pointer value. If this value is referenced through, it causes a
lot_fault condition to be signalled. This feature was
implemented to support the run unit mechanism (see below), which
required the ability to "stack" active linkage sections so that
programs executing inside the run unit could link to different
targets. Normally the address of a program's entry point is
first found by the linker, which makes sure that the program's
linkage section is combined and ready to use before the program
is entered. A run unit, however, may inherit from its calling
environment snapped links to segments whose linkage sections have
not been recombined. If such programs are entered without
benefit of the linker, they will raise a lot_fault condition when
attempting to obtain their linkage pointer. The system lot_fault
handler then automatically combines the linkage section so that
the reference can be completed. The reason that lot faults are
set for every segment at initiate time is that the run unit
mechanism also needs to know what segments were initiated at the
beginning of the run unit. More recently, the execution unit
mechanism invented for C also makes use of lot faults when it
stacks the program's linkage section(s).
Since initiate will work only if it can find a LOT entry to
fault, the maximum size of the LOT effectively limits the number
of segments that a process can initiate. The user can control
this somewhat by adjusting the stack header variable
max_lot_size. The KST and LOT sizes can also be adjusted in the
PMF.
The discussion above has omitted the effects of the ring
mechanism. Both initiate and the linker generally affect only
the LOT of the requesting ring, i.e., the ring of the validation
level. However, if the segment is a gate, the linker must
combine the linkage section and update the LOT in the target
ring, where the entry will actually execute. Thus a gate segment
has a lot fault in its calling ring LOT entry and a linkage
38
Runtime Environment MDD-020
section pointer in its executing ring LOT entry. Lot fault
entries in inner rings are completely ignored since they are of
interest only to run units, C execution environments, and control
point management, all of which run only in the user ring. Lot
fault entries in the user ring do not affect the address space
used by inner rings.
The Internal Static Offset Table (ISOT) is similar to the LOT,
but only segments with separate static actually use it. Isot
faults have been defined but are no longer used. They were
invented for the prelinker so that the static section would be
copied only when it was to be modified. When a segment does not
have separate static (the usual case), the segment's ISOT entry
has the same value as the LOT entry.
5.2.3: NAME SPACE ISSUES
Along with dynamic linking comes dynamic name space management.
By name space management I mean the way in which the linker finds
the segment that contains the link's target entry. A dynamic
linker must be able to find the segment quickly -- it can't look
at all the segments in a library to find the right entrypoint.
Therefore a link specifies a "segment" name as well as an
entrypoint name. This segment name does not include the
containing directory name and is actually called a reference
name. The directories to be searched for the reference name are
specified by a per-ring per-process list called the search rules.
The search rules can be modified by the user to force the linker
to find the desired versions. Flexibility is increased by
allowing some directories to be specified generically as
keywords, such as working_dir and referencing_dir. (See the
search rule commands in the Multics Commands Manual.)
The search rule commonly used first, initiated_segments, is very
different from the others. Rather than specifying a directory,
it specifies the list of reference names that the linker has
already found in the process. This list is called the Reference
Name Table (RNT) and maps reference names into segment numbers
and vice versa. It improves the linker's performance and allows
the user to bypass the other search rules by explicitly
initiating segments in order to get their reference names into
the RNT. The effectiveness of the RNT is largely due to the fact
that the same table continues to be used throughout a process --
usually the only ways that names are deleted are by translators
or occasionally explicitly by the user (through the terminate
command). The assumption is that many of the reference names are
linked to more than once, either because they are called from
many programs or because their associated segments have several
entrypoints or because they specify frequently used commands (yes
the command processor uses the linker).
39
MDD-020 Runtime Environment
The persistence of the RNT does have one disadvantage -- it does
not allow the process to use duplicate reference names. The
effect in Multics is that users tend not to reuse segment names,
except for different versions of the same program. Of course not
all users like this, and some have to deal with programs written
on other systems. There are some alternatives. The binder and
link editor provide static linking among their component
compilation units. The run command temporarily pushes a new RNT.
These are described in a later subsection since they involve
other issues as well.
It is effectively not possible to either move or remove the
initiated_segments search rule because the RNT is always updated
whenever the linker initiates a segment. The linker can be told
not to search the RNT, but it will not be able to initiate the
target it does find if the reference name is already in the RNT
and associated with a different segment.
5.2.4: EXTERNAL VARIABLES
Another aspect of dynamic linking is that external variables
(variables shared among different compilation units) should be
allocated only if they are actually used. In other words, they
are also linked to dynamically and the linker itself creates
(allocates) them. They are referenced through special types of
links (known as *system and *heap) that do not specify a
reference name and that have initialization information
associated with them. If a referenced variable does not already
exist, the linker creates (allocates) and initializes it. Every
link to an external variable has whatever initialization
information was available at compile time.
This method of supporting external variables has side effects
that some find -undesirable. Both the life span of variables and
the way they are initialized are different from most other
systems. As with other links, once the links to external
variables are snapped, they tend to stay snapped for the rest of
the life of the process. That means that the link targets -- the
external variables themselves -- also exist for the same length
of time. Generally the only way to delete an external variable
is through an explicit user command (delete_external_variable).
Since the linker initializes a variable with whatever
initialization information is associated with the variable link
referenced first in the process, it is important that the first
reference be associated with the correct initialization
information.
However many programmers, especially using Fortran or C, cannot
guarantee this. These languages expect the variables to be
defined (associated with initialization information) in one place
and then allocated and initialized before the main program
40
Runtime Environment MDD-020
begins. In Multics, if the variables are defined in a separate
segment, the linker when snapping the first reference knows
nothing about the existence of the defining segment. Multics
does provide several mechanisms for dealing with this situation.
The Multics system programs avoid the above problems with
external variable initialization by referencing the defining
modules explicitly. In this case, the variables are usually
located in the internal static section of the defining module.
The references are of the form x$y, where x is the reference name
of the defining module and y is an externally defined location
(i.e. segment x has a definition for y). The linker simply
links in the usual way, returning an error if it can't find x or
y. A side effect is that if any of a module's variables are
referenced, they are all "allocated".
Segments that exist to define external variables are usually
created by create_data_segment, though they can also be created
by alm. Such segments generally do not contain executable code
except occasionally some initialization code invoked as a trap at
first reference. However they are often bound with segments that
do contain executable code.
An interesting consequence of having external variables "belong"
to a segment is that if the segment is terminated (removed from
the address space), the variables disappear and all the links to
them are automatically reset. This allows the user to redefine
the variables in the middle of the process independently of
everything else. On the other hand, all the variables defined by
the segment are affected; it is not possible just to add one. In
practice this feature is usually used when the data segment is
statically linked to the referencing programs in a bound segment
and the whole bound segment is rebound and replaced; in this case
the variables are external to the referencing programs but
internal to the bound segment.
Of course, external variables that live in internal static
sections are limited in space, especially if the segments are
bound. It is possible to create a definition to a regular
external variable link, thus allowing both explicit references to
the defining modules and large (255K minus 50 words) variables.
Currently Pascal and the binder when binding Pascal are the only
translators that handle such a construct (for imported/exported
variables). (References to "imported" variables must know about
the extra indirection.)
5.2.4.1: How Allocation Is Implemented
External variables are generally allocated in the process's
all-purpose area for the referencing ring (the user free area).
This is an extensible (multi-segment) area, which means that if
41
MDD-020 Runtime Environment
an allocation doesn't fit into the remaining free space, a new
segment is added to the area. This means that the space
available for external variables is largely limited by the
process directory quota and that each variable may be up to
sys_info$max_seg_size minus (size of area header) in length. In
addition, if a variable requires a full segment, a separate
segment is created for it outside the area. Multi-segment
variables may also be defined (known as very large common), but
they are actually initialized by vla_manager_ rather than the
linker and they do not necessarily live in the process directory.
Links to these variables are usually snapped explicitly when the
referencing program is entered rather than at the actual first
reference in order to avoid having to trap out to vla_manager_
(in the user ring) from ring 0.
The linker must also be able to find the variables once they are
allocated, so it must keep a table that associates variable names
with locations. This is a linked list of nodes with a header
containing a hash table. The table header is pointed to by
stack_header.sys_link_info_ptr. The header and node structures
are also allocated in the ring's user free area and are declared
in system_link_names.incl.pl1.
The program responsible for creating and allocating external
variables is set_ext_variable_, which is described below.
5.2.4.1.1: Historical Note on the Allocation of External
Variables
In the days before external variables were allocated in the
extensible user free area, they were mostly allocated in a single
segment called stat_ that had its definitions dynamically
allocated in its linkage section, stat_.link. The allocation was
actually done by a program called datmk_. Originally each link
to an external variable had a trap-before-link to datmk_ so that
datmk_ would run in the referencing ring. Later, when it was
determined that datmk_ was the only program trapped to, the
relevant part of it was called directly by the linker in ring 0.
Along with this change, external variables were referenced
through type 6 (create-if-not-found) links that specified the
segment name, such as stat_ or cobol_fsb_, directly. However, if
the specified segment did not exist it was created automatically
by the linker (in the process directory). Needless to say, this
caused some unpleasant suprises. Finally the present scheme was
implemented (when the area mechanism was changed to implement
automatically extensible areas).
42
Runtime Environment MDD-020
5.2.4.2: Heap Variables
Heap variables are essentially the same as *system external
variables, but they are allocated in a separate area known as the
heap that has a different lifetime from the user free area. This
area has its own segment(s) in the process directory.
stack_header.heap_header_ptr points to the heap header, which is
allocated in the heap area. The heap header, in turn, contains
pointers to the area itself as well as to the heap variable name
list header so that set_ext_variable_ can find them.
Links to heap variables are just like links to system variables
except that they specify a "segment" class of *heap instead of
*system. They are generated by C and regenerated by the link
editor.
The purpose of having *heap variables is to keep their name space
and lifetime tied to the invocation of a [C] main program. Since
C main programs invoke other main programs including themselves,
it is necessary to be able to have several heaps around at a
time. The pointers to the heap headers are stacked, since the
main programs do not run concurrently within a process. The heap
stacking is managed by the non-hardcore procedure heap_area_mgr_
and is expected to be done at the time a C main program is
entered. In order to accomplish this on Multics, C main programs
that use the heap are expected to be link edited with a program
called main_ that pushes the heap level among other things.
main_ replaces main as the link-edited module's default external
entry point. (This is described in more detail below.)
Each heap has its own area/segment in the process directory so
that it can be simply deleted when the C main program returns.
Many Fortran and even PL/I applications could also benefit from
using *heap variables and a link edited main_ program, but these
languages have not yet been adapted for this mechanism.
5.2.5: TRAPS AT FIRST REFERENCE
Sometimes it is necessary to do some initialization before the
first time a segment is actually referenced in the process. This
is done for such things as writing the segment's segment number
into internal static and for initiating and initializing related
segments. This initialization should be done only after the
system knows that the segment is to be used but before it
actually is used, i.e., at dynamic linking time.
How the first reference trap procedures are identified and
invoked is discussed in other subsections. For now it is only
necessary to say that this is done through the linkage section,
which means that only object segments can have first reference
43
MDD-020 Runtime Environment
traps and that the traps are invoked only when the linker has a
pointer to the target linkage section. They are not invoked when
simply snapping a link to the base of the target segment. Traps
are invoked only at the time that the target linkage section is
combined, so in order to rerun the traps, one must terminate the
segment (uncombining the linkage but not necessarily making the
segment unknown) and relink to it.
Gate segments cannot have first reference traps; the trap
processor, which runs in the ring of the validation level, would
fault when trying to access the segment's linkage section, which
is combined in the target ring. Also it is not possible to
invoke first reference traps when linking in a ring below the
validation level (see trap_caller_caller_).
_5_._3_: _S_t_a_t_i_c _L_i_n_k_i_n_g
Multics does provide some methods of statically linking different
compilation units to help offset some of the disadvantages with
dynamic linking. These problems include crowding of the address
space, name space contention and how to get external variables
initialized at the right time with the correct initialization.
It is Multics policy that all translators, including the binder
and linkage editor, that produce object code produce standard
object segments that are directly linkable and executable. The
"static linkers" do not change things like calling sequences,
although they do relocations, change references from external
links to internal locations when possible, and produce a
composite object. Basically, the output of static linking looks
the same as the output of compiling except that most of the
object sections are a series of blocks derived from the
corresponding compilation units. The system tools are supposed
to work smoothly on all object segments.
The static linkers on Multics are the binder and the linkage
editor. It is necessary to have some knowledge of what they do
in order to understand what the dynamic linker does with their
output. This section also describes the set_fortran_common and
run commands, which provide ways to deal with the problems solved
by static linking without doing static linking.
5.3.1: THE BIND COMMAND
The binder was developed specifically for Multics to collect
object segments from input archives and combine them into a
single object segment. A separate control file determines which
objects are chosen to be components--objects are not chosen on
the basis of being called by a main program or one of its
descendents.
44
Runtime Environment MDD-020
The binder has the following advantages:
ox The address space required is reduced by combining several
objects into one segment.
ox Entrypoints can be made internal.
ox Initializations for external variables are consolidated.
ox Grouping objects helps to organize the system.
The output of the binder is a single segment object in the
standard format. The text section is a concatenation of all the
component text sections. The definitions are organized into
blocks, with one block per component. Each block has definitions
for the "segment" names specified for the component as well as
definitions for the externally visible entrypoints. There may
also be definitions for some entrypoints that the binder has made
internal, but these have a flag instructing the linker to ignore
them. All the definitions are linked together and in addition
there is a hash table for faster lookup. The linkage section
contains the concatenated static sections of all the components
plus regenerated versions of the links that were not satisfied
internally. The symbol section contains the concatenated symbol
sections except for the relocation bits plus a symbol block for
the bound segment itself that contains the bind map. The bound
segment itself is not relocatable. The bound segment format is
described in detail in the Multics Programmer's Reference Manual.
5.3.2: THE LINKAGE_EDITOR COMMAND
The linkage_editor command shares many of the advantages of the
binder but has the following differences/extensions:
ox The input specifications are all on the command line, rather
than in a control file. There is somewhat less control over
segment names.
ox "Libraries" can be specified to be used in resolving link
references.
ox Most importantly, the output can be an object multi-segment
file. Thus for large applications the inter-segment linking
and the choice of external variable initializations can be
handled automatically.
5.3.2.1: Object Multi-Segment Files
Object multi-segment files are described in detail in MTB-711 and
in the Reference Manual, but some of the features are mentioned
45
MDD-020 Runtime Environment
here for completeness. Basically, an object MSF is a collection
of "bound" object segments with extensions for inter-segment
references. These extensions are what is interesting here.
5.3.2.1.1: External Definitions
The way that external definitions are handled was motivated by
two main concerns. First, retained external definitions may
exist in any of the component object segments but a caller should
not have to know which; the reference name for any object MSF
entry should be that of the MSF itself. This leads to the idea
of funneling all entry address requests through component 0 to
make life easier for the linker. Second, a caller's snapped link
must point directly to the actual desired target rather than to
component 0 itself. This leads to generating definitions in
component 0 that indirect to their targets in other component
segments.
5.3.2.1.2: Inter-Component Links
It is necessary for procedures in the different component
segments to be able to reference each other. Since this requires
pointers containing segment numbers filled in at runtime, these
inter-component references should be made through links in the
normal way. However, since the only thing not known about the
targets are the segment numbers, the linker should not have to do
all its usual searching. Therefore the link editor produces
partial links, which contain a target's component number and the
offset within the component of the target entrypoint. For
efficiency, most of these links are snapped when the link-edited
module is entered rather than during individual faults, although
the linker does know how to interpret them. To make them more
obvious, unsnapped partial links contain a fault tag 3 instead of
a fault tag 2.
5.3.2.1.3: External Variable Initialization
One of the things that a link editor must do is to make sure that
the external variables referenced (and defined) in the output
module are initialized correctly. Preferably this should be done
within the dynamic linking mechanism wherein a variable is
allocated and initialized only when it is first referenced. In
an object MSF, several components could reference a variable and
the link editor has no way of knowing which component would make
the first reference, so it must somehow associate the
initialization information with all the referencing links.
Instead of actually putting a copy of the initialization in each
referencing component, the link editor generates links with
deferred initialization. In these links, the initialization
46
Runtime Environment MDD-020
information is replaced by information that enables the linker to
find the link (in another component) that does contain the
correct initialization.
5.3.2.1.4: Prelink First Reference Trap
The components of an object MSF could get themselves linked
together in the usual way if partial links had the normal
fault_tag_2 tags. However, since it is expected that all the
components of an object MSF will end up being initiated, and
since partial links are so trivial to snap, there is little
flexibility to gain and much time to lose by using the dynamic
linking faulting mechanism. Besides, this is still a statically
linked situation--links are only used because of the need for
real pointers. Even if many of the partial links are not used
during an invocation, snapping them all at once is more efficient
than taking linkage faults.
This prelinking is accomplished by having a first reference trap
to msf_prelink_ on component 0. msf_prelink_ initiates all the
components, combines their linkage sections if necessary, looks
for and snaps all the partial links, and invokes any first
reference traps for the other components (since that is the
responsibility of the linkage section combiner).
5.3.3: ALTERNATIVES TO STATIC LINKING
Multics does provide some ways to get around some of the problems
of dynamic linking without having to link statically. Basically
they involve adjusting the environment to fit the links rather
than adjusting the links themselves. In practice however, these
facilities have proved to be somewhat awkward and expensive to
use.
5.3.3.1: set_fortran_common
The set_fortran_common command allocates and initializes the
external variables that are defined in specified modules. It is
executed before the main program begins. It allows the
programmer to not have to worry about where the first reference
to a variable is made, because the first reference will not be
doing the initialization.
The disadvantages with this approach are that the user must know
which modules contain external variable initializations, that the
command must be explicitly invoked each time the main program is
run, and that all the defined variables are allocated whether
they are needed or not.
47
MDD-020 Runtime Environment
5.3.3.2: Run Units
The run unit facility is implemented by the run command and run_
subroutine. Its goal is to execute a program and then clean up
the environment so that the program leaves no lasting effects on
the process. In general, the parts of the environment that
contain temporary changes are kept separate from the rest of the
process. Thus a run unit has its own LOT, ISOT, user_free_area,
and optionally RNT/search rules. It does not run on a separate
stack, so the stack header contents have to be restored when the
run unit finishes. Segments that are initiated only in the run
unit are automatically terminated, except for segments that have
a flag indicating that their static is perprocess.
The run unit's LOT is the key to determining the run unit's use
of the address space. When it is created, the entries for the
perprocess static segments already in use are copied from the
calling environment's LOT. The entries for all the other
initiated segments are set to lot faults (see the section on lot
faults below). initiate in ring zero sets the segment's LOT
entry in the ring of the validation level to a lot fault
specifically so that the run unit mechanism can tell what
segments were initiated. LOT faults are used because a reference
through them automatically causes the associated segment's
linkage section to be combined (or recombined, as the case may
be). At the end of the run unit, run_ compares the two LOTs to
determine whether any segments have been initiated for the first
time during the run unit. Of these, any perprocess static
segments have their linkage sections copied back to the calling
environment while all the other "new" segments are terminated.
Normal dynamic linking is used within the run unit. In order to
ensure that the correct name bindings and external variable
initializations are used, the user can specify an exec_com to be
invoked before the main program. This can be used to invoke
set_fortran_common, to change the search rules for the duration
of the run unit, and to initiate segments. Changing the search
rules, etc. is only useful when the run unit has its own RNT.
(Unfortunately, at the end of the run unit, run_ ignores the fact
that every new name in the new RNT also represents an increment
in a segment's reference name count in the KST; the reference
name counts are not properly decremented.)
There are several major problems with run units.
ox It is awkward to have to have an exec_com associated with a
main program to adjust the environment.
ox The run unit mechanism cannot be used recursively, mostly
because it is too hard to track changes to perprocess static
segments. (They probably shouldn't even use the run unit's
name space.)
48
Runtime Environment MDD-020
ox Run units cannot be used in a process along with control
point management because the control points share much of
the environment that run units diddle. A run unit would
want to affect only the control point that invoked it.
_5_._4_: _D_e_s_c_r_i_p_t_i_o_n _o_f _t_h_e _D_y_n_a_m_i_c _L_i_n_k_e_r
The dynamic linker itself is relatively straightforward. The
driving program is link_snap, which calls fs_search to find the
target segment, link_man to combine the target segment's linkage
section, get_defptr_ to search the target segment's definitions
for the entry name, and set_ext_variable_ to allocate and
initialize external variables. Normally, link_snap returns
either an error code or with the link snapped. Sometimes there
is work to be done in the ring of the link before control can be
returned to the user program. In this case, link_snap calls
trap_caller_caller_ to make the "outward call".
5.4.1: LINK_SNAP
link_snap has four entrypoints. $link_fault is invoked as the
handler for the fault_tag_2 fault and so is provided with machine
conditions. The other entrypoints are called normally and are
available through hcs_. $link_force is passed a pointer to an
unsnapped link. $make_ptr and $make_entry provide a way to
invoke the linker to get a pointer to an external entry without
having a translator-generated link.
link_snap spends most of its time calling other programs to do
the real work. Each call is metered and the results are stored
in ahd (=active_hardcore_data). The total time and page faults
are stored in the PDS. link_snap snaps the link (or fills in the
return pointer) when it knows the target location and the target
is initialized/ready to run.
For most links the processing is straightforward. The link is
decoded, the target is integrated into the environment, and the
target location is obtained. However indirect definitions,
partial links and deferred initialization need special mention
because they involve extra link references.
Indirect definitions were invented for the transfer vector in
component 0 of object MSFs so that the linker would not have to
search the definitions of all the components. They point to
partial links to the real target entrypoints. Although partial
links are snapped by msf_prelink_ during the first reference
trap, the trap does not occur until after the location of the
first reference target is obtained (see the section on traps
below). Since the first reference to an object MSF is through an
indirect definition, the linker must be able to snap a partial
49
MDD-020 Runtime Environment
link in this case. When processing an indirect definition, the
linker specifically looks for a partial link (fault tag 3) and
then goes ahead and snaps it. The linker does not invoke itself
recursively in this case nor does it process partial links in
general.
Snapping a partial link involves obtaining the target component
number from the link, calling fs_search$same_directory to
initiate the segment with that number for a name in the same
directory as the segment containing the indirect definition,
combining the target linkage section, and adding the offset from
the link to the appropriate section base.
Deferred initialization also involves some extra link chasing.
The program that allocates and initializes external variables,
set_ext_variable_, expects a pointer to the variable's
initialization structure whether it needs the information or not.
The variable may already have been allocated but link_snap
doesn't know because it doesn't "do" external variables. Most of
the time no extra processing is involved. But with deferred
initialization, link_snap must first find the real initialization
info. The deferred initialization info only enables link snap to
find the link in another component that has the real
initialization info.
Deferred initialization for an external variable works in the
following way. The initialization information associated with
the variable's link includes the offset of a partial link to the
base of the target component's active linkage section and the
offset of the variable's link within the target linkage section.
This information is used to locate the unsnapped link in the
template copy of the linkage section (via the
original_linkage_ptr in the active linkage section header). The
unsnapped link found in this way is threaded to the real
initialization info to be passed to set_ext_variable_. Thus the
algorithm is completely independent of the state of the active
link that has the real init info.
5.4.2: FS_SEARCH
fs_search is called when the link type indicates that the link is
to a segment in the file system hierarchy. It locates and
intiates the target segment. $fs_search is the entry normally
called; it uses the search rules. $same_directory is called for
partial links; it looks only for a segment with the specified
number-name in the specified directory. fs_search is described
in more detail in MDD-006 on the Multics File System.
50
Runtime Environment MDD-020
5.4.3: LINK_MAN
link_man is in charge of combining linkage sections and managing
the LOT. A segment's linkage section is combined when the
segment is first linked to because the linker needs to have the
definition section pointer handy to search for the target
entrypoint. Also in most cases either the segment will soon be
executing and will need its linkage section or the target itself
is in the combined linkage section. Note that none of this
applies when the link type specifies the base of the segment or
when a null entryname is supplied to link_snap$make_ptr; in these
cases the target's linkage section is not combined.
5.4.3.1: link_man$other_linkage
The other_linkage entrypoint returns a pointer to the active
(combined) linkage section of the specified target segment,
combining it if necessary. Before link_man can combine a linkage
section, it must call object_info_$brief to find the section in
the object segment. Obviously if the segment is not an object
segment the link processing stops with an error. Once the size
of the linkage/static section is known, space for the copy is
allocated by the standard system area package in the user free
area of the target ring. After the copy has been made, pointers
to the object segment's definition section and symbol section are
put in the active linkage header so that the linker won't have to
call object_info_ again.
5.4.3.2: link_man$own_linkage
The own_linkage entrypoint returns the same information as
$other_linkage, but assumes that the segment's linkage pointer is
in the LOT in the ring of the validation level. This entry is
only called when the link is to the referencing segment itself
and the linkage section is guaranteed to be combined.
5.4.3.3: link_man$combine_linkage
This entrypoint is essentially the same as
link_man$other_linkage, but assumes that the linkage section is
to be combined in the ring of the validation level and that it is
not already combined. It is used mainly by lot_fault_handler_.
5.4.3.4: link_man$grow_lot
This entrypoint increases the sizes of the LOT and ISOT by
allocating new ones that are stack_header.max_lot_size words long
in the area pointed to by stack_header.clr_ptr in the ring of the
51
MDD-020 Runtime Environment
validation level. The old LOT and ISOT are copied but not freed,
since they may not have been allocated in an area.
5.4.3.5: link_man$get_initial_linkage
This entrypoint, along with makestack, initializes a ring's
environment.
5.4.3.6: link_man$assign_linkage
This entrypoint simply allocates the specified number of words in
the area pointed to by stack_header.assign_linkage_ptr in the
ring of the validation level. It is obsolete, a holdover from
the days when linkage sections were not allocated in areas. At
that time, allocations made by this entrypoint could not be
freed.
5.4.3.7: link_man$set_lp
This entrypoint is obsolete and apparently no longer used. It
fills in the LOT and ISOT entries for the specified segment in
the ring of the validation level, growing the tables if
necessary.
5.4.3.8: link_man$get_lp
This entrypoint is also somewhat obsolete. It returns the
linkage pointer for the specified segment. It does not assume
that the segment number is valid or that the segment's LOT entry
is filled in.
5.4.4: GET_DEFPTR_
get_defptr_ searches the target's external definitions for the
desired entry name. Since the Multics object format allows
duplicate entry names as long as they are in different component
blocks, the segment name from the link is also passed to
get_defptr_ in case it is needed to determine the correct block.
If the target has a definition hash table, get_defptr_ uses it to
find the entry name. If the hash table indicates a name
duplication, get_defptr_ must then use the segment name hash
table. If the segment name is not found, the entry name is
ambiguous and an error is returned.
If the target does not have a hash table, a different algorithm
is used involving a linear search. First the segname class
52
Runtime Environment MDD-020
definitions are searched for the segment name. If it is found,
the non-segname class definitions in that block are searched for
the entry name. If either of these two searches fails,
get_defptr_ must look at all the non-segname class definitions.
Even if it finds a definition for the entry name, it must be sure
that there are no duplicates since the segment name has already
been found to be useless in resolving ambiguity.
5.4.5: SET_EXT_VARIABLE_
set_ext_variable_ returns information about *system and *heap
external variables, allocating and initializing them if
necessary. (*system and *heap variables differ mainly in where
the variables and variable name tables are allocated.) If the
desired variable is in the name table and the allocated size is
adequate, set_ext_variable_ is done. (set_ext_variable_ used to
reallocate the variable if the new size was larger, but stopped
doing this when it was discovered that some programs had stored
the original location in static.) Allocating the variable
involves allocating and filling in a node for the name table, and
allocating and initializing the variable itself. Variables are
allocated in three ways, depending on their size. Either they
are allocated in the user area, or in a separate segment, or
fortran_storage_manager_$alloc is called to obtain a contiguous
set of segment numbers to use.
set_ext_variable_ has several entrypoints to control what it
does. $star_heap causes the allocations to be done in the heap,
creating the heap area (in a separate segment) if necessary.
*heap variables are never too large to be allocated in the heap
area. $for_linker is callable only in ring 0 and traps out to
the user ring if it has to invoke fortran_storage_manager_, which
does not run in ring 0. $set_ext_variable_ assumes that it is
called in the user ring and that it can call
fortran_storage_manager_. In fact, the trap that $for_linker
takes calls $set_ext_variable_ in the user ring. (If you can't
get in the back door, go around to the front...)
5.4.6: LIST_INIT_
list_init_ is called by set_ext_variable_ to initialize a
variable that has list init initialization information. This
type of specification consists of a list of fields to be
interpreted.
5.4.7: TRAP PROCESSING
Trap at first reference, trap before link (obsolete), and
allocatng VLA common require that a specified user ring procedure
53
MDD-020 Runtime Environment
be run before the link is snapped and/or used. Since the linker
in ring 0 cannot just call a procedure in the user ring and
expect to be returned to, it must abandon ring 0, invoke the
specified procedure in the user ring, and then arrange to return
control to the point where it (the linker) was invoked
originally, with the link snapped.
For a trap at first reference, the link is snapped in ring 0
before the trap. For other types of traps, the trap procedure is
expected to snap the link itself.
5.4.7.1: trap_caller_caller_
The linker calls trap_caller_caller_ to get out of ring 0 for a
trap. The target ring chosen is either the ring the link fault
occurred in, if there are machine conditions, or the ring of the
validation level. (If there are any active rings between 0 and
the validation level, an error is returned.) trap_caller_caller_
creates a simulated signaller frame in the stack of the target
ring, copying the machine conditions, if any, and creating an
argument list for the trap calling routine link_trap_caller_.
trap_caller_caller_ obtains a pointer to link_trap_caller_ via
link_snap$make_ptr so that its linkage section will be combined
in the target ring. signaller$for_linker is called to complete
the stack frame, exit ring 0, and invoke link_trap_caller_.
5.4.7.2: link_trap_caller_
link_trap_caller_ actually invokes the trap procedures. Its
arguments include several of the pointers that the linker
obtained during its own processing. The type of trap to be
invoked is determined by which arguments are null. (If another
type of trap is added, another argument should be added to
specify the trap type.) When the trap procedure returns,
link_trap_caller_ must make its return look like the trap was
invisible. If there are machine conditions, link_trap_caller_
simply returns to the fabricated frame for restart_fault (built
by signaller), which restores the machine conditions. If there
are no machine conditions, link_trap_caller_ returns to the
caller of the linker by doing a nonlocal goto to the return
pointer in the frame preceding that of restart_fault.
5.4.7.3: How First Reference Traps Get Turned Off
First reference traps have to be run only at the time that the
linkage section is combined, since they generally initialize
stuff in the linkage/static section. This is accomplished in the
following way. When link_man$other_linkage combines a linkage
section that has a first reference trap, it carefully leaves the
54
Runtime Environment MDD-020
first reference offset in the second word of the combined copy of
the linkage section as it fills in the definition section
pointer. link_snap checks this offset to see if it should call
trap_caller_caller_. link_trap_caller_ zeroes the offset
location before invoking the trap procedures.
5.4.8: ERROR HANDLING
If there is an error, the only information that the linker
returns is a code. A nonzero code returned during link fault
processing causes the linkage_error condition to be signalled.
In this case it may be possible to fix the problem and restart,
causing the fault to occur again and be processed successfully.
list_init_ does not have a code argument, so to communicate an
error to its caller (set_ext_variable_) it signals the
malformed_list_template_entry_ condition. set_ext_variable_
handles this condition by converting it to the code
error_table_$malformed_list_template_entry and doing a nonlocal
goto back to the calling frame. This seems convoluted, but
list_init_ is also called in situations such as initializing
automatic large arrays where signalling is the only way to
indicate an error.
link_trap_caller_ has its own way of dealing with errors that it
encounters. If it is called without machine conditions, it has a
pointer to the code argument of the call to the linker. It fills
in the code argument and returns as described above. If there
are machine conditions, it fills in the code field and signals
linkage_error itself. A restart from this linkage_error causes
link_trap_caller_ to return to the restart_fault frame, which
will restart the machine conditions. If a first reference trap
procedure aborts, unwinding link_trap_caller_'s stack frame, the
segment being linked to is terminated in a way that uncombines
its linkage section without releasing the segment number. This
enables the first reference trap procedure to be reinvoked.
Since first reference trap procedures do not have code arguments,
the only way that they can indicate an error is to signal a
condition and for link_trap_caller_ to convert the condition into
a code and do a nonlocal goto. The only such condition that is
currently handled is object_msf_damaged_.
5.4.9: LOT FAULT HANDLING
Sometimes it is necessary to recombine a segment's linkage
section without terminating the segment. This tends to happen
when the program needs fresh static storage whenever it is
invoked, such as during a run unit. It is not enough to simply
zero the segment's LOT entry because the program could be invoked
55
MDD-020 Runtime Environment
by an already snapped link and then try to access its linkage
section.
Instead, the LOT entry is set to a value that causes a lot_fault
condition to be signalled. The system handler for this,
lot_fault_handler_, calls hcs_$combine_linkage (an entry in
link_man) to combine the linkage and then calls link_trap_caller_
if there are first reference traps.
5.4.10: SECURITY ISSUES
There are three main reasons why the linker is in ring 0. First,
when linking to an inner ring gate, the linker must at least run
in the target ring in order to be able to read the definitions
and combine the linkage section. (Although in ring 0 the linkage
sections are all pre-combined.) Second, the linker itself must
be prelinked to the procedures it calls; this is already done for
everything in ring 0 during system initialization. Third, it is
much faster to process search rules in ring 0 because directories
can be located via segment numbers rather than via pathnames to
be parsed.
The extensive use of data stored in the user ring is not a
security problem because the actual access to segments is
protected by the hardware ring mechanism. The user cannot trick
the linker into doing something illegal. The linker makes its
own decisions about what ring to combine a linkage section in
based on the validation level and the ring brackets of the
target. link_man actually gets the ring brackets from the SDW of
the target segment. When locating the target segment, the linker
depends on the file system's access checks.
The linker runs on behalf of the ring of the validation level.
When there are machine conditions, the linker temporarily sets
the validation level to the ring the fault occurred in. When the
linker is called explicitly, the validation level is not changed.
In that case, it is the responsibility of the caller to make sure
that the validation level is correct.
There is an extra security issue associated with gates. They are
initiated in the calling ring but their linkage is combined in
the target ring. For a while, it was possible to call a gate to
get its linkage section combined and then to terminate it from
the calling ring, leaving the linkage section combined in the
inner ring. Needless to say, this was a security hole. The
solution was for link_man to effectively initiate the gate in the
inner ring by calling segno_usage$increment_other_ring when the
linkage section is combined. This prevents the gate from being
terminated once it is used.
56
Runtime Environment MDD-020
_5_._5_: _T_h_e _C _E_x_e_c_u_t_i_o_n _E_n_v_i_r_o_n_m_e_n_t
C main programs need much of the environment initialization done
for run units, but must also be able to be called recursively.
Since they can be reinvoked directly from command level after a
condition, they must be able to push a new environment after they
are entered. This is taken care of by a procedure called main_
that is link edited with the main program and is the entrypoint
found by the linker when no entryname is specified.
main_ detects that it is being called recursively by checking an
internal static flag. If the flag is on, main_ pushes the
environment of its own link edited module only. main_
accomplishes this by saving the values of its LOT entries in its
stack frame, resetting the entries to lot fault, and then calling
hcs_$make_ptr on itself. (The call to hcs_$make_ptr actually
uses the link in the "old" linkage section.) This linker call
recombines the linkage section and reruns any first reference
traps. In its reincarnation after the call, main_ sees that the
flag is off and so can get down to its usual business. This
involves pushing the heap level (there is a new one for each
invocation of a C main program), initializing some I/O variables,
establishing condition handlers, and invoking the "real" main
program. When the earlier incarnation of main_ is returned to,
it pops the heap level, calls term_ to dispose of the second set
of linkage sections, and restores the LOT entries to their
previous values.
57
MDD-020 Runtime Environment
_6_: _A_R_E_A _M_A_N_A_G_E_M_E_N_T
Dynamic allocation mechanisms are heavily used in Multics. There
are two major kinds--one for directories and one for everything
else. There are also two other kinds--the obsolete buddy block
mechanism and one used by Pascal. The Pascal version will not be
discussed in this MDD.
Some of the discussion in this section, particularly on
allocation, is derived from MTB-219 by Steve Webber dated 8/8/75
and titled "A New Area Management System".
_6_._1_: _G_e_n_e_r_a_l _P_u_r_p_o_s_e _A_r_e_a _M_a_n_a_g_e_m_e_n_t
General purpose areas, implemented by alloc_, are used for PL/I
language-supported areas and controlled variables, combined
linkage sections, non-permanent external variables, system calls
that return dynamically allocated information, and C's malloc
routine. Since it is a good general purpose mechanism suited to
Multics' virtual memory, alternative mechanisms are discouraged.
6.1.1: LOGICAL SYSTEM AREAS
Each non-zero ring has five logical perprocess areas that are
used by the system. However, in practice there is usually only
one system area per ring with five classes of things that are
allocated in it. As long as the allocation of each class uses a
separate logical area, it is possible to make the areas
physically separate for debugging. Each logical area is located
by its own pointer in the stack header. There is no need to have
separate areas because of size considerations, since the single
area is a multi-segment "extensible" area (see below).
6.1.1.1: User Free Area
The user free area is used for PL/I allocations when the allocate
statement does not have an "in" clause (i.e. PL/I "system"
storage), and for non-permanent external variables, including
Fortran COMMON. It is pointed to by stack_header.user_free_ptr,
which can be changed by the set_user_storage command.
6.1.1.2: System Free Area
In general, system programs other than the linker and PL/I
runtime are required to use the system free area. It is pointed
to by stack_header.system_free_ptr, but programs should use
get_system_free_area_ to get the pointer. The command
58
Runtime Environment MDD-020
set_system_storage can be used to change the pointer in the stack
header.
6.1.1.3: Combined Linkage Area
The combined linkage area is used by the linker to combine
linkage sections. It is pointed to by stack_header.clr_ptr.
6.1.1.4: Combined Static Area
The combined static area is used by the linker to combine
separate static sections. It is pointed to by
stack_header.combined_stat_ptr.
6.1.1.5: hcs_$assign_linkage Area
hcs_$assign_linkage uses stack_header.assign_linkage_ptr. This
pointer is defined to point to the original area created for the
ring and so must not be changed. System programs use this rather
than the system free area when they want to be sure that all
their allocations are in the same area.
6.1.1.6: C Heap
The C Heap (used by malloc) is not part of the general system
area since it typically has a shorter lifetime. Usually it
occupies a temporary segment. stack_header.heap_header_ptr
points to the heap header which is itself allocated in the heap
area. A process may have several heaps at once, one for each
active C execution unit. The heap headers are threaded together
and contain level numbers.
6.1.1.7: RNT Area
As mentioned in a previous section, the nodes of the reference
name table are allocated in a separate area that is itself
allocated in the user free area. stack_header.rnt_ptr points to
the RNT header which is allocated in the RNT area and contains a
pointer to the area.
6.1.1.8: Ring 0's Use of Areas
Ring 0 does not have areas of its own, but does make allocations
in other rings' areas. There are generally two ways that these
areas are located. One way is to obtain from the PDS a pointer
to the current stack for the ring of the validation level (or the
59
MDD-020 Runtime Environment
link target ring) and then to use one of the area pointers in the
stack header. The other way is for the area pointer to be given
as input during a system call.
6.1.2: FREEING ALLOCATIONS
Generally it is the responsibility of the program that allocates
space to also free it. In the case of a program that requests
ring 0 to make the allocation, the program making the request
should free the space. Linkage sections and external variables
usually remain allocated for the rest of the process. A
segment's linkage section is freed if the segment is terminated.
An external variable is freed if it is explicitly deleted by the
delete_external_variables command.
Multics does not automatically free allocations when a program
finishes because a program that is executed becomes part of the
environment until it is explicitly removed or the process ends.
Exceptions to this include run units and C execution units, whose
purpose is to provide separate environments for executing
programs. Both of these provide separate areas which are simply
deleted when the program finishes. C execution units free the
program's linkage section(s) by partially terminating the program
if it was invoked recursively.
6.1.3: AREA FORMAT
Some familiarlity with the area format will help in understanding
the allocation algorithm. Each area consists of a header, free
or allocated blocks (if the area is not empty), and unused
storage following the last block. Additionally, an extensible
area may consist of one or more segments chained together. Each
segment is itself a complete area.
6.1.3.1: Area Header Format
This subsection will attempt to describe the header format
without going into all the declaration details, etc. The header
contains the following information:
ox a version number
ox the bounds of the unused storage, relative to the area
header
ox option flags
ox allocation method indicator, which can currently represent
either standard or no freeing
60
Runtime Environment MDD-020
ox the size and location of the last block before the unused
storage
ox the free list, which partitions free blocks into classes
according to size
ox a counter used to detect asynchronous changes
ox the offset of the chaining information for extended
(multi-segment) areas
ox the number of allocated and free blocks
6.1.3.1.1: The Free List
The area header contains the offsets of fourteen separate free
lists. Each list contains the free blocks whose size is between
2**i and 2**(i+1)-1, where i ranges from 3 to 16. The blocks of
each list are threaded together forward and backward in a circle
with the free list header. When a block becomes free it is
simply added to the end of the appropriate list, so that the
blocks within a list are not ordered according to their location
in the segment. An empty area contains only empty free lists.
As an optimization, the area header information for each free
list also contains the actual size of the largest block in the
list. This is only calculated when alloc is searching the list
anyway, so it is not always set.
6.1.3.2: Area Block Format
Each block in an area contains a two word header with the
following information:
ox the size of the preceding block
ox the size of the current block
ox a field of zeroes to distinguish the block from one
allocated by an obsolete area mechanism
ox a flag indicating whether the preceding block is allocated
or not
ox the free list stratum number (when the block is free)
ox the offset of the base of the area, which is not necessarily
the beginning of the segment
61
MDD-020 Runtime Environment
In addition, the headers of free blocks have an extra word
containing:
ox the offset of the preceding block in the free list
ox the offset of the next block in the free list
6.1.3.3: Area Extend Blocks
Each header in an extensible area is immediately followed by a
pseudo block containing:
ox a pointer to the first area header
ox a pointer to the next segment, if any, in the extended area
ox the sequence number for the component
ox the name of the owner of the area
6.1.4: ALGORITHMS USED
Two basic allocation schemes are available, distinguished by
whether or not the blocks can be freed. The scheme involving
free blocks is by far the most heavily used.
6.1.4.1: Standard Allocation Method
The current allocation scheme uses a "first fit" strategy for
finding space, wherein the first free block of sufficient size is
used. (First means first to be found, not necessarily physically
first.) The searching time is reduced by having separate free
lists of different sizes, so that time is not wasted looking at
free blocks that are too small. Having multiple free lists also
improves the fit, since blocks that are much too large are not
used unless nothing closer is available. If the block chosen is
too large, the extra space is returned to the appropriate free
list.
This approach strikes a good balance between simplicity of code
and time/space efficiency. Although one can probably devise a
better strategy for any given application, this general purpose
scheme has proved to be acceptable for most dynamic allocation
needs on Multics.
62
Runtime Environment MDD-020
6.1.4.1.1: Allocation
First an attempt is made to find an existing free block of
sufficient size. Each of the free lists that contain blocks
large enough are searched, in order, until a large enough block
is found. This block is then split into two parts. The first
part is returned to the caller; the second is added to the
appropriate free list.
If no suitable free block is found, a block is created at the
beginning of the unused storage and the next_virgin field in the
area header is updated.
If there is no unused storage or if there is not enough, and if
the header's extend flag is on, a new area (segment) is created
and threaded to both the current area and the first area
component through the extend_info pseudo-block. The allocation
request is then serviced from the new area. The previous area is
still available for allocation requests, as long as they fit.
Of course, any allocation involves filling in the block header
and turning on the prev_busy flag in the header of the following
block.
If the extend flag is not on or if the allocation won't even fit
in a brand new area segment, the area (or storage) condition is
signalled. Usually it is area, but PL/I requires storage in
certain cases; our implementation indicates this case by using
the storage_ or op_storage_ entrypoints in alloc_.
The bad_area_format condition is signalled if the version or
allocation_method fields in the area header are invalid, or if a
free list thread appears to go off into space (indicated by
reaching a limit of 40000 on the number of blocks "found" in a
free list).
6.1.4.1.2: Freeing
The main job of freeing is to thread the block into the
appropriate free list. But first, in order to reduce
fragmentation, the block is merged with any adjacent free blocks.
If there is a merger, the old blocks are threaded out of their
free lists and the merged block threaded in. If the block being
freed is the last block before the unused storage, it is added to
the unused storage. This involves zeroing the header and
updating the next_virgin, last_size and last_block fields in the
area header.
63
MDD-020 Runtime Environment
6.1.4.1.3: Initialization
There are three options for initializing blocks: zero on alloc,
zero on free, and no initialization. The user free area created
by the system uses zero on alloc. Zero on free is not generally
recommended because it touches all the pages initially, many of
which will never be used. It is provided as an aid in certain
debugging situations.
6.1.4.1.4: Asynchronous Reinvocation Protection
Areas are considered process entities (they contain ITS
pointers), so the system provides no protection from simultaneous
updates. (A Multics process cannot run on two cpus at once.)
However, it is possible for an asynchronous (IPS) interrupt to
occur while the area is being updated, and for another update to
occur before the first one is returned to. alloc_ uses a
combination of detecting a change and running critical sections
inhibited to keep the area consistent.
IPS interrupts are prevented from occurring while instructions
with the inhibit bit on are executing, so a section of code that
is inhibited is atomic as far as the IPS mechanism is concerned.
alloc_ takes advantage of this feature to do all threading while
inhibited. Then it can always expect to see a consistently
threaded area.
However it is not recommended to run inhibited for very long, so
alloc_ does its searching for a suitable free block uninhibited.
Thus while the area itself is always consistent, it is possible
for a thread to change while alloc_ is following it. alloc_
detects this by saving the value of a counter before beginning
the search and comparing the value every time it thinks it has
found a new free block. If the value of the counter has changed,
alloc_ knows that the thread it was following may no longer be
valid and that it should begin the search all over again. The
counter, area_header.allocation_p_clock, is incremented in
inhibited code before beginning either an allocation or a free
operation.
Care must be taken when writing inhibited code. One should avoid
taking page faults in this state. In particular, the code in
alloc_ that zeroes out blocks runs uninhibited.
There is a flaw in the protection mechanism described above. The
inhibit bit does not prevent a process from losing eligibility.
Then before the scheduler restarts the process, it checks for and
signals any pending IPS interrupts.
64
Runtime Environment MDD-020
6.1.4.2: No Freeing Method
Areas whose blocks are never freed can be simpler, more compact
and more efficient. alloc_ simply grabs the requested space from
the current beginning of the unused storage and updates the
last_usable and next_virgin fields in the area header. There is
no block header because there is no need to thread blocks. Thus
the blocks are contiguous and in the order of allocation, which
may be useful in certain situations.
If there is no more room in the segment and the area is
extensible, a new area segment is created and threaded as in the
freeing case. In this case, however, alloc_ is interested only
in the most recent component. To simplify things, the
next_virgin and last_usable fields in the first area component
always refer to the most recent component. The current_component
field in the no-freeing header provides the desired segment
number.
No-freeing areas with the zero_on_alloc option have to be
entirely zeroed out before any allocations are made in them.
When define_area_ acquires the area segments, such as when
extending an area, it knows the segments are already zero.
However, if a pointer to the area was passed to define_area_ (and
the system flag is off), the entire area is explicitly zeroed.
The no-freeing method does have some disadvantages. No-freeing
areas cannot be used for PL/I declared areas nor can the empty
builtin function be used on them. They can very wasteful of
space if used in situations involving a lot of temporary
allocations. There is no protection against asynchronous
changes.
6.1.5: MODULES USED
The standard system area management code is divided into two
modules: alloc_, written in alm, and define_area_, written in
PL/I.
6.1.5.1: alloc_
alloc_ is basically an extension of pl1_operators_. The way the
operators transfer to and return from alloc_ depend on their
being bound into the same segment. Of course there are some
regular external entries as well.
alloc_ is used for operations that must run partly inhibited,
including the block threading operations. It calls
get_next_area_ptr_ to extend the area to another segment, and
calls signal_ to signal area or storage.
65
MDD-020 Runtime Environment
Most of the entries in alloc_ check the version field in the
header for a version of zero, which indicates the use of the
obsolete buddy block format. To process that format, alloc_
calls the corresponding buddy_XXX_ routine. This was done for
compatibility but is no longer necessary.
6.1.5.1.1: Entrypoints in alloc_
ox alloc_
external entry to allocate a block of the specified size;
signals area
ox storage_
same as alloc_ but signals storage
ox op_alloc_
segdef for operators to allocate a block of the specified
size; signals area
ox op_storage_
same as op_alloc_ but signals storage
ox freen_
external entry to free a specified block
ox op_freen_
segdef for operators to free a specified block
ox area_
copies a header template from
template_area_header$template_area_header into the specified
segment and initializes the size
ox extend (called as area_$extend)
same as area but adds an extend block
ox no_freeing (called as area_$no_freeing)
same as area_ but sets the allocation method to no freeing;
optionally adds an extend block
ox op_empty_
same as area_ except that it is a segdef called by operators
with arguments already in registers; this is used to
initialize variables declared as areas, which cannot be
extensible
ox redef (called as area_$redef)
changes the size of the area by changing the value of
area_header.last_usable; the new size must include all
allocated blocks
66
Runtime Environment MDD-020
ox area_assign_
replaces one initialized area by copying another initialized
area; refuses to assign a buddy area to a standard area or
vice versa (although an uninitialized buddy target is
allowed).
ox old_alloc_, old_area_, old_freen_
identical to the corresponding "non-old" entrypoints; these
names were originally on the buddy area modules when they
were still supported as alternatives
6.1.5.2: Entrypoints in define_area_
define_area_ is used for operations that are done once per area
and for making extension components.
6.1.5.2.1: define_area_
define_area_ creates and initializes an area. It is passed a
control structure which can specify any of the possible options,
and it can be asked to create a new segment for the area. The
new area is first initialized by the empty builtin function
(which calls alloc_$op_empty_ which copies template_area_header)
and then revised with the specified control information.
define_area_'s actions are partly controlled by the system
option. If the system flag is on and a new segment is to be
created, hcs_$make_seg rather than get_temp_segments is used to
create the segment in the process directory. Also it is assumed
that any system area is already initialized to zero.
6.1.5.2.2: get_next_area_ptr_
get_next_area_ptr_ is called by alloc_ to obtain a pointer to the
next area component. If the next component does not exist, it is
created. If the system flag is on, the new component is created
in the same directory as the previous component; otherwise a temp
segment (in the process directory) is used. In either case the
ring brackets are copied from the previous component.
define_area_ is called to initialize the area and then the extend
blocks are threaded together.
6.1.5.2.3: release_area_
release_area_ deletes or releases all the components of the
specified area that were created by the define_area_ interface
and sets any other components to empty (which usually just
67
MDD-020 Runtime Environment
reinitializes the header without zeroing pages or truncating).
IPS signals are masked during the entire operation.
6.1.6: AREA COMMANDS
There are two area commands: create_area, which is a command
interface to define_area_, and area_status, which prints
information from the area header as well as the free threads.
_6_._2_: _O_b_s_o_l_e_t_e _B_u_d_d_y _B_l_o_c_k _M_e_c_h_a_n_i_s_m
This code exists in the system to allow areas already in this
format (presumably on backup tapes) to be processed. The system
no longer creates such areas. Since this has been true for more
than ten years, it is now safe to remove the obsolete code from
the system. The modules involved are buddy_alloc_, buddy_freen_,
buddy_area_, and buddy_area_assign_.
It is not appropriate to discuss this mechanism in detail in this
MDD, but some knowledge of the pitfalls could be useful. In the
"buddy system", block sizes are powers of two and an allocation
uses the smallest size block that contains the requested amount
of storage. Any leftover space in the block is left unused.
This method does make allocations and frees very fast but it also
has many disadvantages.
First, the fixed block sizes cause a lot of wasted space.
Second, the initialization required limits flexibility. Since it
is difficult to extend an area once it has been initialized, the
maximum size of the area segment must be specified at the
beginning. Most of the pages are touched during initialization,
causing unnecessary page faults, extra pages in the process
directory, and heavier use of large AST entries. (The usual area
space used is MUCH smaller than the maximum would have to be.)
_6_._3_: _F_i_l_e _S_y_s_t_e_m _A_r_e_a_s
The file system uses a simple, efficient area mechanism for
directory contents that takes advantage of the fact that
everything to be allocated belongs to a small set of small sizes.
The header specifies the number of sizes and the value of each.
It also contains a free block thread for each size, the number of
words in the area, and the offset of the last word used.
Allocations work in the following way. If there is a free block
of the specified size, it is used. Otherwise the block is
allocated from the unused space and the lu field is updated. If
68
Runtime Environment MDD-020
there is not enough room for the block, a null pointer is
returned.
Freeing a block simply entails threading the block onto the free
list of the specified size.
For both allocating and freeing, the bad_dir_ condition is
signalled if the area does not define blocks for the size
specified.
The module that implements this mechanism is fs_alloc with three
entrypoints: init, alloc and free. The acceptable block sizes
are specified to the init entrypoint.
This mechanism with its fixed sizes and more awkward interfaces
is not suitable for general purpose use, but is well enough
suited to directory control. The salvager must also know about
this format, both to check the directories' consistency and to
compact the directories. Compaction is desirable because the
need for blocks of a particular size may decrease, leaving a lot
of unused space. It is possible because the salvager can figure
out where all the references to each block are and can relocate
them.
69
MDD-020 Runtime Environment
_7_: _C_O_N_D_I_T_I_O_N _S_I_G_N_A_L_L_I_N_G _A_N_D _H_A_N_D_L_I_N_G
The Multics fault/condition/exception mechanism is a general
system service used for hardware faults, Inter-Process Signal
(IPS) events, conditions defined by the PL/I language, and
various software-defined conditions. It is based on the model
defined for the PL/I language in that it uses PL/I terminology,
searches the procedure activation stack, and allows restarting
the operations that detected the errors. However several
extensions have been made to support system requirements. For
the most part these extensions involve the ability to pass
additional information when signalling and the ability to bypass
or alter the stack search.
_7_._1_: _C_o_n_d_i_t_i_o_n _S_i_g_n_a_l_l_i_n_g
A single signalling program, signal_, is used for all cases.
When an event is detected, signal_ is invoked with arguments
containing information about the event. Its job in turn is to
find the appropriate handler for the event and to give it the
information.
7.1.1: STATIC CONDITIONS
Some events are requests for special system services which users
cannot or should not provide. Most of these, such as segment
faults, are handled in ring zero directly by the fault intercept
mechanism without being signalled at all. However those that are
handled in the user ring, such as IPS timers and lot faults, are
funneled through signal_. Since these events are not intended to
really be signalled, signal_ finds their handlers in a static
location instead of searching the activation stack for them.
These are called static conditions.
signal_ calls sct_manager_$call_handler to invoke the static
condition handlers. Since all static conditions happen to have
machine conditions associated with them, signal_ calls
sct_manager_$call_handler for all conditions that have machine
conditions and lets it figure out whether or not there is a
static handler. If there is a static handler for the condition,
sct_manager_ invokes it. Static handlers generally do their
thing and then return, eventually causing the associated machine
conditions to be restored (see below). If there is not a static
handler for the condition, sct_manager_ returns, telling signal_
to search the stack in the regular way.
A static handler is established by calling sct_manager_$set with
a pointer to the handler's entry point and with the condition's
fault code. sct_manager_ uses the SCT (Static Condition Table),
which is indexed by fault code. (The fault code is contained in
70
Runtime Environment MDD-020
the machine conditions.) The SCT lives in the stack, so there is
one for each nonempty nonzero ring of each process. Some static
handlers are established during process initialization, but the
user is then allowed (but not encouraged) to delete, replace or
add new static handlers. They can even be "stacked" in a way by
calling sct_manager_$get to obtain the old SCT entry's value
before replacing it, and then having the new handler call the old
one when it is done.
7.1.2: NORMAL CONDITION SIGNALLING
The algorithm that signal_ uses for searching the stack is
described in section 7 of the Multics Programmer's Reference
Manual. Briefly, signal_ starts with the stack frame immediately
preceding its own, looking for an on unit for the specified
condition. If one is found, it is invoked. If the stack frame
does not have an on unit for the specific condition name but does
have one for any_other, the any_other handler is invoked.
The handler has three options when it is done. It can simply
return, causing signal_ to return to its caller to retry/continue
the operation; it can turn on its continue flag argument by
calling continue_to_signal_ and then returning, causing signal_
to continue searching the stack; or it can do a nonlocal goto,
causing all the stack frames between it and the frame specified
by the target label to be unwound.
On units are implemented as a linked list of structures within
the stack frame. A frame may not have multiple active on units
for the same condition. The on unit structure contains the
condition name (as pointer and length), a pointer to the handler,
snap and system flags, and optionally a pointer to a file
descriptor.
On units established by PL/I on statements are initialized when
the stack frame is created and activated (linked to the on unit
list) by the on statement. On units can also be created by
calling condition_, which extends its caller's stack frame in
order to append the on unit.
signal_ must also do some additional work to support all the
semantics of the PL/I condition mechanism. Before invoking a
handler, signal_ checks the on unit's snap bit and invokes
pl1_snap_ if the bit is on. (pl1_snap_ in turn calls either
trace_stack_ or probe, depending on whether the process is
absentee or interactive.) If the on unit's system bit is on,
default_error_handler_$wall_ignore_pi is invoked as the handler.
Some file-related conditions are established only in relation to
a specific file, so a stack frame may have several on units for
the same condition, each with respect to a different file (i.e.,
containing a different file pointer). In these cases the file
71
MDD-020 Runtime Environment
specified by the on unit must match the file specified by the
information passed to signal_.
7.1.3: CRAWLOUTS
If signal_ reaches the beginning of the stack without finding a
handler and there is no thread to a higher ring stack, the
process is terminated. If there is another stack, signal_ makes
one last effort to get the condition handled before resignalling
the condition in the higher ring. Some (PL/I) conditions have
well-defined default actions which the system is supposed to
provide. In the user ring they are provided by the general
condition handler established at the beginning of the stack,
normally default_error_handler_$wall. Inner rings do not have
such a handler established because their stacks are logical
extensions of the outer rings' stacks. However some conditions,
such as endpage, cannot be handled correctly in the user ring
because they require access to inner ring objects. To provide
the necessary services in inner rings, signal_ calls
crawlout_default_handler_. If the condition is then handled
successfully, signal_ returns to its caller as usual. Otherwise
(the usual case) the condition is resignalled in the ring that
called the inner ring. This is called a crawlout.
The crawlout mechanism is described in the section on exiting a
lower ring. During a crawlout, signal_'s arguments are copied to
the outer ring, including the structures the arguments point to.
In addition, if ring 0 was entered via a fault rather than a gate
call, an attempt is made to copy the machine conditions of that
fault as well (if they are relevant for the target ring). These
are termed the wall crossing conditions.
Conditions that have been resignalled cannot be restarted because
the inner ring stack has been truncated. The copied structures
contain some information about inner ring activities but cannot
be used to affect the inner ring.
_7_._2_: _H_o_w _s_i_g_n_a_l__ _I_s _I_n_v_o_k_e_d
The information in this subsection really belongs in MDD021 on
Fault and Interrupt Handling, but as of this writing that MDD has
not been written. This subsection describes how signal_ is
invoked once the decision has been made to signal a condition.
How the decision is made is beyond the scope of this MDD.
signal_ may be called just like any other subroutine. In this
case there usually are no machine conditions, so any information
to be passed to the handler is put into an info structure and a
pointer to it is passed to signal_. The structure must have a
standard header so that the default system handler can obtain
72
Runtime Environment MDD-020
basic information from all structures. However the info
structure itself is not required.
PL/I runtime routines that signal generally invoke signal_ via
pl1_signal_. There usually is a common, long info structure
involved that is best filled in by one program. Also
historically pl1_signal_ had to maintain an obsolete but parallel
mechanism for storing "ondata".
signal_ may also be invoked in the faulting ring from ring 0.
This happens for hardware faults and IPS interrupts. In this
case there are usually machine conditions but no info structure.
The trick is to get all the necessary arguments into the proper
ring so that signal_ can reference them.
The decision to signal is usually made by the fim (fault
intercept module), which then calls signaller. signaller extends
the most recent stack frame in the faulting ring in case the
fault occurred while a new frame was being constructed and sets
the signaller stack frame flag to indicate this. It then appends
a frame to that stack, copies into the frame the machine
conditions that the fim stored in pds$signal_data, and constructs
the argument list for signal_. The location of everything in
that frame is also known by restart_fault and
trap_caller_caller_. The frame is made to look as if it belongs
to return_to_ring_0_, since that program should be the target of
a return from signal_.
The signaller/return_to_ring_0_ frame also has a cleanup handler.
As long as the condition can be restarted, a copy of the machine
conditions is kept in the pds. Unwinding past the frame
indicates that the condition is not going to be restarted, so the
cleanup handler deletes the copy in the pds. Obviously this
cleanup handler must run in ring 0; it is
restart_fault$cleanup_entry, which is a gate.
Transferring to signal_ is not straightforward. signaller
obtains a pointer to the entrypoint to be called from signal_ptr
in the target stack, which means that a user can substitute a
private program for the system version of signal_. As mentioned
in the section on exiting a lower ring, only an rtcd instruction
may be used, and the address must be in the target ring. Since
the program being transferred to in this case can execute in
several rings, signaller must construct the address pointer
carefully to contain the correct ring number. The actual
transfer to signal_ is done via
return_to_ring_0_$return_to_ring_n, which just executes a few nop
instructions to allow time for the ring alarm to go off if it was
set. The ring alarm in turn may cause an IPS interrupt to be
signalled. This is pushed on the stack and handled before the
original condition even gets signalled.
73
MDD-020 Runtime Environment
7.2.1: RESTARTING A CONDITION
When a handler returns to signal_, signal_ simply returns to its
"caller". When signal_ was called as a subroutine, this is
straightforward. The caller should set the cant_restart flag in
the info structure header if it doesn't want to be returned to.
It is then the responsibility of the handler to not return to
signal_.
On the other hand, machine conditions can be restarted only by a
privileged instruction in ring 0. Since it is not possible to
return (rtcd) to ring 0, signal_ returns to return_to_ring_0_,
which calls restart_fault$restart_entry. The "links" to
restart_fault in return_to_ring_0_ and to return_to_ring_0_ in
signaller are snapped at system initialization time; the correct
link targets cannot be found by the dynamic linker.
restart_fault is an unusual gate in that it contains "real code"
and does not use the gate macros. It restarts the copy of the
machine conditions that is in the outer ring stack, but first
compares it to the copy saved in the PDS. If it is discovered
that the user made any illegal changes, the illegal_return
condition is signalled instead. This allows the user to make
some changes without allowing the execution of an arbitrary
instruction in ring 0, for example. Before actually restoring
the machine conditions, restart_fault pops the return_to_ring_0_
stack frame and removes the extension and signaller flag from the
previous frame.
Conditions that have been signalled after crawling out from a
lower ring are never restartable.
_7_._3_: _C_o_n_d_i_t_i_o_n _H_a_n_d_l_i_n_g
Condition handling usually falls into one of two general
categories: either the handler knows how to fix or ignore the
condition and does so, or the handler has to get the user
involved by printing a message and reentering command level
(where user interaction can take place). Most conditions,
although not necessarily the conditions signalled the most, are
in the second category.
7.3.1: CONDITION WALLS
Before reentering command level, it is common practice for a
handler to establish a condition wall. The condition wall
protects the programs with stack frames before the wall from
conditions that occur afterward. Theoretically, the procedures
executing afterwards are not related to those behind the wall, so
conditions raised by them have no meaning in the earlier context.
74
Runtime Environment MDD-020
The wall does allow the program_interrupt and finish conditions
to "pass through" because they are intended for the earlier
procedures.
A condition wall is simply an on unit for "any_other". The
system default handler establishes one of its entries as a wall
just before reentering command level. If the wall handler is
invoked for finish or program_interrupt it just sets the continue
flag and returns.
7.3.2: SYSTEM DEFAULT CONDITION HANDLING
As mentioned above, the system establishes at the base of the
user ring stack a condition handler that is supposed to do
something reasonable with anything it gets. This section
discusses that handler but does not cover many individual
conditions. The conditions signalled by the system are listed in
the Multics Programmer's Reference Manual, along with the
structure of the information passed to them.
The default handling described here does not take place in ring 0
and has no real security implications.
Two collections of programs are involved. One consists of a
driver, default_error_handler_, and the subroutines that it
calls. Together they try to make sense of the information passed
with the condition in the context of the environment. The other
collection is a set of routines that try to interpret various
aspects of the environment and is heavily used by the first
collection. This MDD will not attempt to describe the details of
how all the information for the message is obtained.
7.3.2.1: default_error_handler_
default_error_handler_ is the "main" program of the system
default condition handler. Although it is passed arguments from
signal_, it uses the more useful information from
find_condition_info_ instead. default_error_handler_ calls the
other routines as necessary and formats a message (unless the
default action is to return silently). When it is actually
called as a handler (as opposed to just being called to format a
message), it prints the message, sets itself up as a condition
wall, and then calls cu_$cl to reenter command level.
default_error_handler_ is more or less table-driven. Although a
few conditions are special-cased, there is a table that specifies
for most conditions such things as whether there is a valid
target reference or whether there is extra interpretation to be
done. Since it is impossible to have an exhaustive list, there
are default entries for both hardware and software generated
75
MDD-020 Runtime Environment
conditions. The table also contains the format strings for the
messages. In most cases, default_error_handler_ accumulates the
information for each piece of the message separately and then
puts the pieces together in a single call to ioa_$rs.
Programs that raise software conditions can also take advantage
of the flags defined in the standard info structure header to
direct the handler. The flags specify such actions as not to
restart or to restart without printing a message.
Extra work is necessary after a crawlout. The only information
that is available about the condition itself is whatever signal_
copied out of the inner ring. The message must include this, but
must also include the fact that there was a crawlout and a
description of how the user entered the inner ring.
The main goal of all this interpretation is to try to present a
message that is meaningful to the user. Usually this means tying
it into a source program statement in the most recent active user
program, as well as trying to use the actual segment names
referenced by the user.
default_error_handler_ has to be aware that the situation that
caused the condition may also have affected the environment in
other ways. Sometimes a fault occurs while trying to obtain
information about the original condition. To deal with this,
default_error_handler_ establishes its own any_other handler.
This handler makes fewer assumptions about the state of the
environment so it does not try to obtain as much information for
the message. In particular, it uses the arguments from signal_
directly rather than calling find_condition_info_. If the
internal handler is invoked twice recursively, it assumes that
the process is in bad shape and that the iox_$error_output switch
is probably unuseable; it then terminates the process by calling
terminate_process_. Some of the conditions that the internal
handler might get are "process control" conditions (such as quit)
unrelated to the original condition. In these cases the internal
handler simply returns so that the signalling can be continued.
(As of this writing the list of conditions checked for is out of
date.)
7.3.2.1.1: Entry $wall
This entry handles finish and program_interrupt, and establishes
a condition wall before reentering command level. It is
specified by initialize_process_ as well as other programs
ultimately responsible for handling a process' conditions.
76
Runtime Environment MDD-020
7.3.2.1.2: Entry $standard_default_handler_
This is an obsolete name for default_error_handler_$wall.
7.3.2.1.3: Entry $default_error_handler_
This entry handles finish and program_interrupt but does not
establish a condition wall. It used to be the main entry before
the condition wall was invented but is now obsolete. A few
programs still specify it.
7.3.2.1.4: Entry $wall_ignore_pi
This entry does not handle finish or program interrupt, and does
establish a wall. It is specified by default_error_handler_
itself as the any_other handler to implement the wall. This
entry is also invoked when an on unit specifies the PL/I "system"
handler.
7.3.2.1.5: Entry $ignore_pi
This entry does not handle finish or program_interrupt, and does
not establish a wall. It was the predecessor of $wall_ignore_pi
and is no longer used by the system.
7.3.2.1.6: Entry $condition_interpreter_
This entry is a subroutine interface for other condition handlers
to use. It provides all the semantics of the default system
condition handler except that it does not resignal the error
condition (defined for some PL/I conditions), establish a
condition wall or reenter command level. The error message may
be either printed by condition_interpreter_ or returned in a
specified area. In cases when the standard handler would not
print a message, this entry returns a null message. (This entry
is not always useful. It would probably be desirable to have
another entrypoint that had a simpler interface and always
returned a message.)
7.3.2.1.7: Entry $reinterpret_condition_
This entry is the same as condition_interpreter_ except that it
is supposed to return a message in lieu of actually doing
anything to the environment. The assumption is that it is called
after the condition has actually been handled but the caller
wants to see the message again. Since reinterpret_condition_ is
not just handling the most recent condition, it can interpret any
77
MDD-020 Runtime Environment
condition that has active information on the stack; it is given a
pointer to the most recent stack frame of interest.
7.3.2.1.8: Entry $interpret_condition_
This entry usually formats messages as reinterpret_condition_
does, but does not have the option of returning them to its
caller. It is the predecessor of condition_interpreter_ and is
no longer used by the system.
7.3.2.1.9: Entry $reprint_error_message_
This entry is the subroutine interface used by the reprint_error
command. It figures out the stack frames corresponding to the
specified condition depths and then invokes
reinterpret_condition_.
7.3.2.1.10: Entry $change_error_message_mode_
This entry is called by the change_error_mode command to control
somewhat the verbosity of the messages.
7.3.2.1.11: Entry $add_finish_handler
This entry is now simply a writearound to add_epilogue_handler_.
7.3.2.2: message_table_
This is a data segment that contains the format strings as well
as specific action indicators for each condition. Any conditions
not named specifically are covered by either the default entry
for conditions with machine conditions or the default entry for
conditions without machine conditions.
7.3.2.3: find_pathname_
This procedure formats the pathname of a specified location. It
is necessary do some interpretation in order to obtain a
meaningful name. For example, if the directory is the process
directory, the string "in the process directory" is inserted
instead of the real unique-string name; also if the location is
in a bound segment, the offset is given relative to the beginning
of the proper component.
78
Runtime Environment MDD-020
7.3.2.4: get_ppr_
This procedure tries to obtain the last location executed before
the condition. If that location is in a support procedure such
as a language's runtime routines, the location used is the most
recently executed one in a non-support routine. get_ppr_ then
tries to find the exact name used to invoke the procedure that
contains the location. Since the procedure's segment may have
several names, and since even the entry used may have several
names, the surest way to find the name used to invoke the
procedure is to look at the most recently referenced link in the
procedure's caller when relevant.
7.3.2.5: get_tpr_
This procedure tries to obtain the location that was being
referenced when the condition occurred. Generally this
information is available only when there are machine conditions.
7.3.2.6: interpret_info_struc_
This procedure obtains whatever part of the message there is to
obtain from the info structure (if any) that is passed with the
condition.
7.3.2.7: interpret_oncode_
If the condition is one defined by PL/I and has an oncode value
associated with it, interpret_info_struc_ calls interpret_oncode_
to find the message associated with the oncode in the segment
oncode_messages_.
7.3.2.8: linkage_error_
The machine conditions for a link fault are interpreted
differently from those of any other fault. This procedure
isolates this special case.
7.3.2.9: special_messages_
This procedure is called in cases where it not possible to obtain
a useful descriptive message from a table. For example, one may
need to interpret the machine conditions for disk addresses.
79
MDD-020 Runtime Environment
7.3.3: REENTERING COMMAND LEVEL
cu_$cl reenters command level by calling the program established
as the "cl intermediary", or get_to_cl_$unclaimed_signal by
default. The main job at this point is to reset the standard I/O
switches to their default values, again because it is likely that
subsequent procedures do not want to run in exactly the same
environment as the procedure that caused the condition. The
interfaces cu_$(get set reset)_cl_intermediary are available for
those who have to do other things before the user can interact
with the process. For example, control point management uses a
cl intermediary that suspends the current control point in favor
of the main control point.
To actually arrive at command level, get_to_cl_ calls
listen_$release_stack.
80
Runtime Environment MDD-020
_8_: _S_E_G_M_E_N_T _A_N_D _P_R_O_C_E_S_S _T_E_R_M_I_N_A_T_I_O_N
This section discusses how segments are removed from the address
space, in whole or in part, as well as what a process does when
it terminates itself normally.
_8_._1_: _S_e_g_m_e_n_t _T_e_r_m_i_n_a_t_i_o_n
Segments may be removed form the address space dynamically, just
as they are added dynamically. However removal is always done
with explicit calls, unlike addition which is often done
implicitly by the linker. Usually removal is done because either
the segment was only added temporarily, or it is about to be
deleted, and/or the segment is about to be replaced by a
different one (such as a different version of a program).
There are hcs_ interfaces for terminating programs, but they only
affect the ring 0 databases such as the KST and the descriptor
segment. Since there are often pointers to the segment, such as
snapped links, in the user ring that need to be cleaned up as
well, it is recommended that segment terminations be done via the
user ring program term_.
term_ has several entries to do various amounts of cleaning up.
The "complete job" consists of the following: The command
processor's associative memory is cleared. All links that are
snapped to the segment or to its static are unsnapped. PL/I file
state blocks that reference the segment or its static are closed.
Any Fortran static VLAs the segment was using are freed. Any
external variable initialization pointers to the segment are set
to null. The segment's active linkage and static sections are
freed. The supervisor is called to complete the termination. If
the segment is a component of an object MSF, the above actions
are automatically repeated for each component.
Some of the entries in term_ do all of the above, while other
entries are more selective. For example, term_$no_clear does not
call find_command_$clear because it is called by find_command_
itself. Some other entries only clean up the user environment
and do not call the hcs_ termination interfaces.
The hcs_ segment termination interfaces start out by removing
reference names that were associated with the segment by the
calling ring. If no reference names remain for the segment, the
segment is removed from the address space. Thus a segment cannot
be removed (except by deletion) unless each ring that was using
it terminates it explicitly.
81
MDD-020 Runtime Environment
_8_._2_: _P_r_o_c_e_s_s _T_e_r_m_i_n_a_t_i_o_n
The answering service actually terminates the process by deleting
the process directory, removing the process' scheduling
information, and disconnecting the line to the terminal. However
there often are things that the process must do itself, such as
closing files. These things are coordinated by the logout
command. Whenever the process is healthy enough to do anything
to its environment, process termination is routed through logout.
logout can be invoked in several ways. The most commonly used
are the logout and new_proc commands. sus_signal_handler_ calls
it if the user does not have the option of having the process
saved when the line is suddenly disconnected. The entry
logout$term_signal_handler_ is the (static) handler for the trm_
IPS condition, which is signalled when the process is bumped by
the answering service.
However not all programs that decide to terminate the process use
logout. The procedure that actually tells the answering service
to terminate the process is terminate_process_. Most of the
procedures that call terminate_process_ probably have little
choice but some, notably the software that runs absentee jobs,
should really have an entrypoint in logout to call.
The common code in logout does the following: First the finish
condition is signalled. Second execute_epilogue_ is called to
invoke the established epilogue handlers and then to close all
the files (by calling iox_$close on all the IOCBs). Finally
terminate_process_ is called.
There are at least two major deficiences in the current logout
algorithm. First, the stack should be unwound (i.e., any cleanup
handlers executed) after the finish condition is signalled.
Second, logout only cleans up the user ring; execute_epilogue_
should be called in inner rings as well. (Of course inner rings
do not have any stack history to worry about.)
-----------------------------------------------------------
Historical Background
This edition of the Multics software materials and documentation is provided and donated
to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc.
as a contribution to computer science knowledge.
This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology,
Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL
and BULL HN Information Systems Inc. to the development of this operating system.
Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970),
renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership
of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture
for managing computer hardware properly and for executing programs. Many subsequent operating systems
incorporated Multics principles.
Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc.,
as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. .
-----------------------------------------------------------
Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without
fee is hereby granted,provided that the below copyright notice and historical background appear in all copies
and that both the copyright notice and historical background and this permission notice appear in supporting
documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining
to distribution of the programs without specific prior written permission.
Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc.
Copyright 2006 by BULL HN Information Systems Inc.
Copyright 2006 by Bull SAS
All Rights Reserved