Multics Technical Bulletin MTB-583
LAs and VLAs
To: Distribution
From: T. Oke, H. Hoover, M. Weaver, B. Westcott
Date: 07/05/83
Subject: Large Data Spaces in Fortran
Comments should be sent to the authors:
via Multics Mail:
Oke.Calgary, Weaver.Multics, Hoover.Calgary or
Westcott.Calgary on System M.
via Mail:
Tom Oke or Harold Hoover or Brian Westcott
The University of Calgary
2500 University Drive N.W.
Calgary, Alberta, Canada
T2N 1N4
(403) 284-6201
or
Melanie Weaver
Honeywell Information Systems, Inc.
Cambridge Information Systems Laboratory
575 Technology Square
Cambridge, Massachusetts 02139
1 ABSTRACT
This MTB discusses some of the issues to be addressed in the
management of large data spaces (arrays) in Fortran programs.
This MTB was originally written prior to development, but was
never published.
It has been re-written and describes the LA/VLA Fortran after
almost all development and testing. Hence it is quite
comprehensive and addresses implementation methods, problems and
benefits, and attempts to provide sufficient information to
outline both the concepts involved and associated changes to
Multics and Fortran.
________________________________________
Multics project internal working documentation. Not to be
reproduced or distributed outside the Multics project.
MTB-583 Multics Technical Bulletin
LAs and VLAs
2 PROBLEM
Present and potential future users of MULTICS Fortran desire
larger storage spaces than are currently available due to segment
size limits of 255K words.
The Fortran compiler and runtime system now permits a reduction
of these limits to permit arrays which require more than a single
segment of storage, Very Large Arrays (VLA's), and/or in which
the aggregate storage requirement are more than a single segment,
Large Arrays (LA's).
With the implementation described here individual VLA's are
permitted to be up to 2**24 words in length, with some character
and IO restrictions, and are implemented as a standard, source
transparent, feature of the language.
VLA allows Very Large Common (VLC) to be up to 2**24 words in
length. LA permits a user a great expansion upon the previous
Automatic and Static storage limits.
Users without need of LA's and VLA's will see no degradation in
their program's performance, storage requirements or speed of
unoptimized compilation.
Users of VLA's cannot expect the same kind of efficiency as the
users of small arrays either in execution or compilation speed,
although non-optimized users will see very little degradation in
switching to Very Large Arrays.
Users of LA's will see little or no degradation in their
execution speed, with the exception of an increased compilation
unit calling overhead necessary to create Automatic storage
segments. Programs retain full inter-language parameter passing
compatability using LA parameters.
Multics Technical Bulletin MTB-583
LAs and VLAs
3 TABLE OF CONTENTS
CONTENTS
Page
1 Abstract . . . . . . . . . . . . . . i
2 Problem . . . . . . . . . . . . . . ii
3 Table of Contents . . . . . . . . . iii
4 Product Description . . . . . . . . 1
5 Expanded Limits with LA/VLA . . . . 1
5.1 Character and IO Limits of
VLA's . . . . . . . . . . . . . . 2
5.2 Initialization Limits Lifted . 2
6 How to use LA/VLA . . . . . . . . . 2
6.1 Control Arguments . . . . . . . 2
6.2 GLOBAL Arguments . . . . . . . 3
6.3 Implications of Large and Very
Large Array Processing . . . . . . 4
6.3.1 Implications for
Parameters . . . . . . . . . . 4
6.3.2 LA - Restrictions and
Limitations . . . . . . . . . . 4
6.3.3 VLA - Restrictions and
Limitations . . . . . . . . . . 4
6.3.4 Performance Implications . 5
6.4 Quota and Quota Directories . . 6
7 System Performance Implications . . 7
8 Subroutine Library Implications . . 8
9 Basic Implementation Methodology . . 9
9.1 LARGE ARRAYS . . . . . . . . . 9
9.2 VERY LARGE ARRAYS . . . . . . . 10
10 Storage Allocation for LA/VLA . . . 11
10.1 Automatic and Static . . . . . 11
10.2 Very Large Array COMMON . . . 11
10.3 Program Storage Startup
(Allocation) . . . . . . . . . . . 12
10.4 New Operators . . . . . . . . 13
11 VLC Linkage Support . . . . . . . . 14
12 Initialization . . . . . . . . . . 15
12.1 Current Methods . . . . . . . 15
12.2 New List Template Method . . . 15
12.3 list_init_ . . . . . . . . . . 16
13 Externals . . . . . . . . . . . . . 16
14 Storage Cleanup . . . . . . . . . . 16
15 Fortran Storage Manager . . . . . . 17
16 fsm_info . . . . . . . . . . . . . 20
MTB-583 Multics Technical Bulletin
LAs and VLAs
CONTENTS (cont)
Page
17 fortran_storage_ . . . . . . . . . 20
18 Error Condition Signalling . . . . 23
19 binder . . . . . . . . . . . . . . 23
20 linker . . . . . . . . . . . . . . 24
21 term_ . . . . . . . . . . . . . . . 25
22 run . . . . . . . . . . . . . . . . 26
23 set_fortran_common . . . . . . . . 26
24 list_external_variables . . . . . . 26
25 delete_external_variables . . . . . 27
26 reset_external_variables . . . . . 27
27 probe (stu_$get_runtime_address . . 27
28 VLA Code Sequences . . . . . . . . 28
29 Documentation . . . . . . . . . . . 30
30 Initialization Structures for Type
5 System and Type 6 Links . . . . . . 30
31 list_fortran_storage (lfs) . . . . 32
32 set_ext_variable_ (AG93-04) . . . . 34
33 Change to Stack Header (AG91-03) . 38
34 Change to Symbol Table (AG91-03) . 40
35 Include Files . . . . . . . . . . . 42
A1 Case for Contiguous Segments . . . 45
A1.1 Summary . . . . . . . . . . . 45
A1.2 Contiguous Segments . . . . . 46
A1.3 Dope Vectors . . . . . . . . . 46
A1.4 Code Requirements for Managing
with Dope Vectors . . . . . . . . 48
A1.5 Code requirements for
Contiguous Segments . . . . . . . 49
A1.6 Conclusions . . . . . . . . . 50
Multics Technical Bulletin MTB-583
LAs and VLAs
4 PRODUCT DESCRIPTION
Multics Fortran, as with other Multics based languages, has been
limited in the amount of storage which a program may address
according to the following limits:
a. Automatic Storage was limited to an aggregate size per
compilation unit of 62000 words.
b. Static storage was limited such that the aggregate size of
the Combined Linkage section could not be more than 128K
words per compilation unit or 16K words per bound unit.
c. BLANK COMMON was limited to 261070 words (255K-50), while
NAMED COMMON could be a full 261120 words (255K) in length.
(Previously no allocation error was declared if BLANK
COMMON was defined larger than this, though references
beyond the 261070 word limit would be out-of-bounds.)
Prior to the introduction of LA/VLA features the largest single
array possible was 255K words. This could be achieved by putting
the array into its own individual NAMED COMMON block.
5 EXPANDED LIMITS WITH LA/VLA
The Multics LA/VLA Fortran product is a significant reduction of
storage limitations, and is currently the only language based on
Honeywell equipment to be able to do normal, language intrinsic,
support beyond the storage limits given above.
With the introduction of this product, size limitations are
greatly reduced:
a. Automatic and Static AGGREGATE storage limits are
essentially limited by the virtual machine address space of
up to 2**30 words.
Static aggregate limits through Large and Very Large Arrays
do not affect the ability to bind compilation units
together since overhead space in the combined linkage
section of an object is just two words per Large Array
segment required, and just one word per member of a VLC
block or VLA equivalence block.
b. Individual storage entities, i.e. arrays, are now limited
to 16,777,216 words (64-256K segments) in Automatic and/or
Static, while individual NAMED and BLANK COMMON sizes are
limited to 16,777,216 words.
MTB-583 Multics Technical Bulletin
LAs and VLAs
5.1 Character and IO Limits of VLA's
String handling in character variables and formats is restricted
by this implementation. It is not permitted to have VLA
character strings, or to use VLA numeric items for character
purposes such as formats.
Use of VLA's in binary IO is restricted by the Multics limit that
no more than about 255K words can be read or written in a single
binary record. Thus a user is limited, in doing binary block or
record IO, to array cross-sections of less than a segment. There
are no such limits imposed upon non-binary IO.
5.2 Initialization Limits Lifted
Through the LA/VLA feature initialization limits are also greatly
increased.
Where previously there was a word-for-word template of
initialization data, this is now done through initialization
lists which define a datum and replication count. Thus for
initialization replications of identical values there is only one
list item for each replication per storage entity. The end
result is reduced object size and a greatly increased size of
initializable storage. There is some degradation in the startup
overhead of programs requiring template initialization since a
program loop is entered to do the initialization.
6 HOW TO USE LA/VLA
6.1 Control Arguments
There are three command arguments for using Large and Very Large
Arrays. The first two, "la" and "vla", provide a general
facility for programs with large space requirements. The third,
"vla_parm", provides a means to optimize execution in an
environment where the user has a requirement to permit Very Large
Array parameter passing, but does not require the features or
additional space provided by the Large Array feature.
The command line arguments are:
-large_array, -la
This argument enables collection of all arrays in
Automatic or Static into collections of storage which
will be allocated in segments external to the Stack or
area.linker.
Multics Technical Bulletin MTB-583
LAs and VLAs
Large Arrays impose some startup overhead upon each
entry into a compilation unit in which Large Arrays
are defined, since storage segments must be allocated,
initialized and managed.
-very_large_array, -vla
This argument enables both Large Array features (-la)
and permits individual arrays to be up to 2**24 words
each (2**24 words for a COMMON BLOCK).
Large and Very Large Arrays impose both the startup
overhead associated with storage allocation and
initialization and the addressing overheads required
for arrays which are either passed as parameters or
are explicitly greater than a segment in length (Very
Large Arrays). Arrays passed as parameters must be
addressed through VLA addressing arithmetic, since
they could potentially be VLA's.
-vla_parm
This argument enables Very Large Array processing for
those arrays which are explicitly greater than a
segment in length and for arrays passed as parameters.
'vla_parm' does not cause 'short' arrays to be
collected into Large Array segments, and thus imposes
a minimal overhead to subroutine or compilation unit
entry. Since 'vla_parm' permits VLA addressing for
parameters which are arrays, it permits a subroutine
to accept normal or VLA parameters. This makes it
quite useful for compilation units which do not
require external storage but which must be able to
accept VLA parameters, a typical case for subroutine
libraries.
6.2 GLOBAL Arguments
The three command arguments for Large and Very Large Arrays have
been outlined above in the sub-section on Control Arguments.
The '%global' arguments corresponding to the command arguments
outlined above are: "%global la;", "%global vla;" and "%global
vla_parm;".
There are no %global arguments or command line arguments to turn
off any of the LA or VLA features, and the options are logically
additive. LA and VLA features affect the entire compilation
unit.
MTB-583 Multics Technical Bulletin
LAs and VLAs
6.3 Implications of Large and Very Large Array Processing
Only the Very Large Array feature has additional implications and
limits in its use, since Large Arrays are simply the equivalent
of using COMMON for internal code generation. The VLA feature
affects execution performance in handling array parameters and
Very Large Arrays and Common, and limits the size of binary IO
records and the use of characters.
6.3.1 IMPLICATIONS FOR PARAMETERS
If VLA addressing is selected, array parameters are addressed
through VLA address arithmetic, which is a general addressing
technique that covers normal and very large arrays. Thus there
is a performance degradation in addressing arrays passed as
parameters since any array parameter could potentially be a VLA.
This performance degradation results entirely from the dynamic
addressing characteristics of the program. There is only a
marginal increase in the routine call/exit overhead, since no
storage need be created by parameter passing. However, there
will be a creation overhead if the compilation being entered
declares its own Large or Very Large Arrays.
6.3.2 LA - RESTRICTIONS AND LIMITATIONS
There are no restrictions or limitations on the use of the Large
Arrays feature, not even those which would affect the mixing of
character and non-character information in an ANSI77 COMMON
block.
Since Large Arrays are totally within the normal pointer/offset
hardware addressing limits of the processor, variables in Large
Arrays can be passed without restriction anywhere a normal non-LA
variable could be passed.
6.3.3 VLA - RESTRICTIONS AND LIMITATIONS
The Very Large Array feature does have some limitations in the
area of IO and character handling.
Since the MULTICS IO system works through I/O Modules which can
only deal with a normal Multics segment, binary IO is limited to
a segment or less in length per record. This means that it is
not possible to do an implicit binary output or input of an
entire Very Large Array, and the binary record of a read or write
with an IO loop may be too large to be handled by the Multics DIM
Multics Technical Bulletin MTB-583
LAs and VLAs
system. This limit may require program modification for
continued operation when array sizes increase.
There is no restriction as to where a segment boundary falls
within the record being output, since fortran_io_ handles
situations in which the start and end of a record being output
are in different segments.
Normal formatted or list_directed Stream I/O does not suffer from
this record size restriction. One may use any or all of a VLA in
a single stream IO statement, since fortran_io_ does formatted
and list_directed I/O through the iox_ stream modules, and iox_
supports operations with multi-segment files.
VLAs, including VLC, may not contain characters, since the
characters may cross a segment bound and would thus be
inaccessible to the hardware EIS instructions.
The compiler does not support PERMANENT VLC blocks. This limit
has been imposed until a resolution of the support of permanent
256K hierachy segments has been resolved. At that time the limit
may be lifted and code introduced to 'fortran_storage_',
'fortran_storage_manager_' and the linker to handle the
initiation and creation of permanent 256K segments.
6.3.4 PERFORMANCE IMPLICATIONS
Although every attempt has been made to ensure the fastest
possible execution rates, Large and Very Large Array features
will impose some execution penalties.
For the most part the penalty of using Large Arrays is purely in
startup overhead of entering a compilation unit and creating
segments to hold extended storage. During execution there will
be little difference between using Common and using Large Arrays,
since they use essentially the same hardware instruction
sequences. This imposes a marginal speed degradation from the
normal use of Automatic or Static due to indirection through
static and automatic ITS pointers and even less degradation in
optimized code, which attempts to make the best possible use of
pointer registers.
Additional penalties, over those for Large Arrays, are imposed
through the addressing arithmetic necessary for Very Large
Arrays. This addressing arithmetic is essentially based upon a
logical address within the user's virtual address space, rather
than the usual segment and offset. Since this is not a normal
hardware function, it must be simulated by additional code
MTB-583 Multics Technical Bulletin
LAs and VLAs
sequences which use the A and Q registers and/or memory, and thus
affect both expression evaluation and register optimization.
The techniques used for VLA address arithmetic are fairly simple
and general and result in degradations of typically less than 10%
for un-optimized code. They also lend themselves fairly well to
optimization, and speed degradations are typically less than 50%.
6.4 Quota and Quota Directories
The LA and VLA features in Fortran now permit a user to have and
use an address space of up to 2**30 words, which can cause
problems with quota.
The amount of space that a process could conceivably have
allocated, 4096 Multics segments (1,048,576 pages), is obviously
more than a normal user would be able to allocate in the process
directory. In fact this totals roughly 28 MSU451 disk drives
worth of storage attached to a single process. Therefore
allocation of storage space, or quota, is a problem which must be
addressed as part of the total coverage of the LA/VLA feature
within Fortran and Multics.
The allocation of storage space for Large and Very Large Arrays
is done through the use of the user's VALUE SEGMENT and/or
defaults to permit 'fortran_storage_manager_' to allocate and
control storage required for Large and Very Large Arrays.
Fortran_storage_manager_ looks in the user's value_segment for a
definition for 'fsm_dir_dir_path'. If such a definition exists,
it specifies the directory within which further directories
containing QUOTA POOLS will be created. Unless otherwise
specified by the user, quota pools will be created by default
within the process directory.
To permit multiple rings of execution for programs using the
LA/VLA feature, fortran_storage_manager_ creates a quota pool per
ring, using the ring number in the name of the pool much like the
stack naming convention. For example the pool directory for ring
4 is given the name 'fsm_dir_4'.
To permit multiple users to use quota from a single pool,
fortran_storage_manager_ maintains a control file for each pool,
fsm_info, and provides full multi-process access and locking to
prevent conflicts. Minimal security and protection is provided
through the normal Multics ACL mechanism. Only the user who has
been allocated a segment within a pool is given 'rw' access. All
other users have 'null' access.
Multics Technical Bulletin MTB-583
LAs and VLAs
There is no protection from overt action, other than normal
directory ACL limits set by the project or pool administrator to
the directory named by 'fsm_dir_dir_path'.
7 SYSTEM PERFORMANCE IMPLICATIONS
The use of extremely large data spaces and vast amounts of real
and virtual memory has an impact upon total system performance.
It could easily be possible, through poor tuning or extensive use
of LA/VLA features to literally bring a Multics system to its
knees.
There are a number of possible areas of impact which must be
considered by administrative controls, both system parameter
specifications, and user quota and storage allocation.
1. AST Pool Sizes
Since Very Large Arrays are, by definition, at least 255
pages in length they draw heavily upon the 256 page AST
pool. This can cause AST contention thrashing, in which a
high demand for AST entries in this limited pool requires
demand deactivation of activated segments which have pages
in memory, to make AST entry space available to activate
other segments.
Demand deactivation looks for segments which are minimum
cost deactivations. Normally this would be segments which
have no pages in memory.
If a user is using large memory spaces on a system with
quite a bit of real memory, it could be that all 256K
segments in the pool have pages in memory. This could pose
considerable problems, since segments to be deactivated must
have ALL their modified pages written back to disk. This
can cause large disk queues and will probably result in disk
system ALLOCATION LOCKS and severely degraded system
performance.
In addition, a pathological case may occur in which a user
of Very Large Arrays causes continual demand deactivation of
other necessary system segments which are not touched by
their processes with the same frequency as the Very Large
Array pages are touched. Certain candidates, such as
compilers, very large directories, etc., may have this
situation. These could be forced into thrashing situations.
To avoid such situations requires careful monitoring and
over-allocation of 256K AST pool entries to alleviate demand
deactivation situations.
MTB-583 Multics Technical Bulletin
LAs and VLAs
2. Drive Contention
The allocation of storage to Large and Very Large Arrays is
done with segments which are not necessarily all on the same
disk drive, but which must all be on the same logical volume
if an explicit quota directory is supplied, or by default in
the process_directory (which spans logical volumes).
Unless an administrator is careful it is easy to place a
number of highly contending users on the same drive, or in a
limited logical volume. The net effect would be a saturated
disk drive, and probably the complete disk sub-system. This
will cause ALLOCATION LOCKS and may lock up the paging
system, even if it does not seriously deteriorate physical
disk service on other sub-systems. Thus a single drive or
sub-system may seriously degrade the rest of the system
through its saturation and back-pressure on page_control.
This poses a problem to the system administrator who
attempts to lighten potential paging loads on system volumes
by putting users onto a restricted set of dedicated volumes.
Even though the intent is good, and the user will not
physically impact the IO throughput of the other volumes on
the system, it may still be possible to severely impact
other system users simply by locking up the paging system
and slaving it to the throughput limits of the dedicated
volume(s).
Multics disk systems seem to work best when IO's are
balanced across most drives. If any single drive starts to
approach 20 IO's per second or more it is a potential threat
to an ALLOCATION LOCK lockup of the paging system. Thus the
best recommendation to an administrator who finds quite a
bit of VLA work, or a few very large VLA users, is to go
against the initial impulse to segregate them, and in fact
to put them into the process directory system, and spread
the process directories across the maximum possible set of
drives to evenly distribute drive and sub-system loading.
The full possible address space of 2**30 words would require up
to 28 MSU451 disk drives. Since this is beyond the resources of
most systems, an individual user is likely to be limited either
to the largest logical volume on a system or to the extent of
possible process directory space.
8 SUBROUTINE LIBRARY IMPLICATIONS
The use of subroutine libraries poses some efficiency problems
with the use of VLA's. These problems must be addressed by the
library managers of individual sites.
Multics Technical Bulletin MTB-583
LAs and VLAs
1. VLA addressing is a superset of normal hardware addressing
of the Multics processor. This permits all subroutine
libraries to be compiled with VLA addressing for parameters,
through either "-vla_parm" or "%global vla_parm;".
2. It is possible that certain programs will be noticably
impacted by the use of VLA addressing in very tight loops,
or in complex operations, such as might occur in things like
matrix multiplies or inversions. In such cases it might be
advisable to copy VLA parameters to a local area, and
re-copy the result at the end of computation.
3. It may be advisable to take internal routines of a large
libary set, such as IMSL, which are known to NEVER be passed
VLA's and to separately re-compile them so that their
internal interfaces will only expect normal arrays.
4. A final possibility would be two distinct and separate
libraries, each compiled for maximum speed in the two
calling types; VLA calls and normal calls. This poses a
management problem in making segments known, dynamic linking
and storage management, and management of user problems and
education.
9 BASIC IMPLEMENTATION METHODOLOGY
9.1 LARGE ARRAYS
Previous Static and Automatic limits were incurred in part due to
the history of Multics development, such as the stack limit of
62000 words, and the requisite packing of a number of storage
entities, simple variables and arrays, into aggregates which were
constrained to be less than a segment in length. Restrictions in
static size imposed by the binder are directly due to
pointer/offset addressing formats and are a hardware addressing
limitation.
Large Arrays are collections of storage entities, either simple
variables and/or arrays, which collections individually are less
than a segment in length, but which may total in aggregate more
than the previous permissible size of the storage type (Automatic
or Static). Such collections are within the direct hardware
addressing limits of the processor and are similar in effect to
the programmer collecting storage into COMMON BLOCKS.
The Fortran compiler, when prompted by the "-la" or "-vla"
command line argument or "%global la" or "%global vla", collects
storage entities, packs them together, and addresses them much
MTB-583 Multics Technical Bulletin
LAs and VLAs
the same as if the programmer had collected them together into
COMMON BLOCKS. These collections or Large Arrays are not
globally known externals, as a COMMON BLOCK would be, and all
previous attributes of their storage type are functionally
equivalent, including the action of stack frames and static and
the scope of storage.
Although in '-ansi77' one cannot have a mixture of character and
numeric data types within a COMMON BLOCK, this restriction DOES
NOT HOLD for Large Array Collections. This gives the programmer
more freedom than if variables were moved into COMMON BLOCKS, and
provides source level transparancy using Large Arrays.
9.2 VERY LARGE ARRAYS
Large Array techniques handle all storage entities which are
within the hardware indexed addressing capabilities of the
processor, but this limits addressing to storage entities which
are no more than a segment in length.
Very Large Arrays are storage entities which are individually
greater than a segment in length and/or cross one or more segment
boundaries, putting them beyond the direct hardware indexed
addressability of the processor. VLA's are used for addressing
single arrays, or COMMON BLOCKS, and are used for addressing
array parameters within a subroutine or function compiled with
the '-vla' or '-vla_parm' attributes.
Very Large Arrays are addressed through a mechanism which is a
superset of normal hardware addressing, and considers addresses
to be absolute logical addresses. In this addressing scheme the
word number within a segment is a low order component of the
logical address, and the segment number is a high order component
of the logical address.
This requires an allocation of storage in which contiguous
storage is allocated through a contiguous allocation of segment
numbers, permitting addressing to pass from the end of one
segment to the start of the next through the simple expedient of
incrementing the logical address and transforming it to a segment
number and offset. (See Appendix A for more details of
contiguous segment allocation.)
Very Large Array storage requests as many segments as are
necessary to encompass the size of each individual array.
Current limits place an arbitrary 16MW (64-256K segments) limit
as a maximum individual VLA size. This limit has been
aribitrarily set and is not a function of the instruction
sequences performed or the hardware.
Multics Technical Bulletin MTB-583
LAs and VLAs
10 STORAGE ALLOCATION FOR LA/VLA
10.1 Automatic and Static
The LA/VLA features of the compiler separate the allocation of
segments to each type of storage, Automatic, Static or COMMON,
providing them with their own distinct segment allocations. As
many segments of storage as are needed to hold all the storage
requirements are allocated and managed by the Fortran runtime
support routines.
Storage is acquired at runtime as compilation units are entered.
Storage creation and initialization information is stored in the
text section and associated with each external entry for LA and
VLA automatic and static. Initialization information for VLC is
associated with the ITS link in the linkage section and is held
in the definition section.
When a compilation unit is exited, its AUTOMATIC storage is
freed. If a 'release' is done, a 'cleanup' handler for each
compilation unit's stack frame releases AUTOMATIC storage.
STATIC storage is freed by term_ when the object is terminated,
operationally the same as normal STATIC. Thus the action of
LA/VLA remains in the background to the programmer, and simply
supplies the resources desired.
10.2 Very Large Array COMMON
The requirements of AUTOMATIC and STATIC storage are served by
the handling of Large and Very Large Arrays, as described above,
but the technique of Very Large Arrays also permits an increase
in the previous limits of COMMON storage, through the
introduction of Very Large Array COMMON.
Very Large Array COMMON is externally accessible Very Large Array
storage. Such a COMMON BLOCK may be addressed either as a VLA or
as a normal COMMON BLOCK. Programs addressing the COMMON block
as a Very Large Array are linked to it through the LA/VLA runtime
support routines. Programs addressing the storage as a normal
COMMON BLOCK snap a link to it using information from the linkage
and definition sections, as is currently done.
Programs addressing a VLC as a normal COMMON see only the first
segment of the COMMON block, due to the addressing limits of
normal COMMON references. Thus VLC's are fully accessible
according to the addressing limits compiled into the object.
MTB-583 Multics Technical Bulletin
LAs and VLAs
VLC storage is typically allocated or linked to through the
action of the Fortran runtime storage management routines when a
compilation unit containing VLC is entered. It can also be
allocated and linked to by the linker resolving an unsnapped
link, if an object that references it as normal COMMON is bound
with an object that references it as VLC.
10.3 Program Storage Startup (Allocation)
The Fortran compiler generates two reference forms for the new
storage types of Large and Very Large Arrays. Large Arrays are
addressed through full double-word ITS pointers. Very Large
Arrays are addressed through arithmetic operations performed on
Logical Addresses, which result in packed pointers to individual
array elements.
There is a separate ITS pointer for each Large Array segment
required by a program. This pointer exists in either the current
stack frame for automatic, or in the linkage section for static.
A VLA has one packed pointer per COMMON block or equivalence
member within the VLA, rather than addressing the members, as
with normal COMMON, through a constant offset from the base
pointer. This is done to optimize referencing and reduce
arithmetic overhead in addressing, by eliminating dynamic address
code for constant offsets. Instead constant offsets are managed
at initialization time, and are built into the packed pointers by
fortran_storage_.
Pointers to STATIC LA and VLA storage are pre-initialized to
'null' by the code generators at compile time, and runtime
storage is allocated for STATIC only if the pointer is 'null'.
Thus STATIC allocation follows the same execution pattern
expected for internal STATIC.
Packed VLC base pointers are managed in the same fashion as
static, with a pre-intialization to null. However the runtime
support routines always check the external to ensure that the
correct pointer is being used, whether the COMMON has been
deleted, etc.
LA/VLA storage space is allocated when a compilation unit is
externally called. Automatic storage is allocated at each call,
and pointers to the externally allocated space are left in the
current stack frame. Static space is allocated if the
corresponding pointer in internal static is NULL, and the pointer
is updated to indicate allocated storage. This allocation is
only done once per initiation of the object (by compilation unit,
Multics Technical Bulletin MTB-583
LAs and VLAs
not by bound unit). When the static section is terminated,
allocated storage is released.
COMMON storage is allocated when a compilation unit is externally
called and storage has not been previously allocated. If storage
has not previously been allocated, it is allocated at this time,
made exterally known, and a pointer, or pointers, to the storage
left in both the object's linkage section, and in internal
static. If the storage was previously known, a pointer to it is
returned to the object's static. COMMON storage is released
through the termination of the process or run unit (for default
quota pools in the process directory) or by the
'delete_external_variables' command.
10.4 New Operators
When a program is compiled using LA/VLA features, it utilizes
three new pl1_operators_ operators which provide the interface
necessary for allocation, initialization and control of external
storage segments.
The new operators are:
1. fort_storage
This operator is used by the entry code of a Fortran
compilation to allocate and initialize external storage.
The calling sequence is:
tsx0 pr0|fort_storage
vfd 18/create_text_offset,18/pad
Where 'create_text_offset' is a text section offset to a
storage creation and initialization table, which holds
information required for the creation and initialization of
Static and Automatic Large and Very Large Arrays, and Very
Large Common. A complete description of this table is
included in the 'fortran_storage_' section.
2. fort_return_mac
The normal 'return_mac' entry within pl1_operators_ is used
to return from a procedure call to the previous stack frame,
and to return all automatic storage which might have been
allocated to that stack frame. fort_return_mac performs the
same actions, but also calls 'fortran_storage_manager_$free'
to free any external storage segments which have been
allocated to this stack frame.
MTB-583 Multics Technical Bulletin
LAs and VLAs
3. fort_cleanup
This operator is passed the stack offset of an 8-word block
in which it builds a cleanup handler to 'fort_cleanup_'.
'fort_cleanup_' will be called by 'unwind_stack_' to handle
the 'cleanup' condition and causes automatic LA and VLA
segments for this stack frame to be freed.
In the future, the system should be changed to provide a
compatible mechanism for languages to use to establish
runtime cleanup handlers that don't interfere with cleanup
handlers established by programs and vice versa.
11 VLC LINKAGE SUPPORT
Until now, COMMON blocks, which are implemented as external
variables, have been addressed through links. This is assumed by
the system services that handle COMMON, such as print_link_info,
the binder, set_fortran_common, and the external variable
commands.
However, VLC is addressed through arithmetic operations on a base
pointer, which is never utilized directly as a pointer. Thus in
this case dynamic link snapping is impossible.
In order to remain compatible, VLC will continue to have links,
with their associated initialization information in the
definition section. But since the links cannot be snapped
dynamically, they will be snapped directly through runtime
initialization code whenever an object that references VLC is run
and the links are unsnapped. Thus VLC will always be allocated,
even if the program with the link does not reference the VLC
during the first invocation. This is different from current
Multics practice but is compatible with most other systems.
Fortran runtime calls the standard linker external variable
interface to actually create the COMMON blocks. If the link and
the static information for the VLC do not agree, the link
information is assumed to be correct.
Retaining the links also enables programs using VLC and programs
using non-VLC blocks of the same name to be bound together. The
binder merges references to the same COMMON block from different
compilation units, creating a single link. This produces
references by "normal" code to VLCs. If a "normal" COMMON
reference is made first, it will be through an unsnapped link and
will refer to a VLC which must be created and initialized by the
system linker.
Multics Technical Bulletin MTB-583
LAs and VLAs
12 INITIALIZATION
12.1 Current Methods
External storage such as COMMON and internal storage such as
Automatic or Static are currently initialized either to zero or
by a word-for-word template containing initialization settings.
When an external link is snapped the linker (set_ext_variable_)
uses the initialization information associated with the link.
Initialization of Automatic and Static is accomplished through
different methods.
Static is initialized by pre-setting the internal static area of
the linkage section of the compilation unit to the final
initialized value of its variables. This is copied to
"area.linker" when the linkage section is activated.
Initialization of automatic uses a similar template. But since a
stack frame is dynamically created each time a compilation unit
is entered, the template of an initialized automatic variable is
kept in the text section. An EIS copy of the template is done to
the stack frame as part of the entry sequence.
12.2 New List Template Method
The LA/VLA Fortran product introduces an additional
initialization form, LIST TEMPLATE INITIALIZATION. In this form
of initialization there is a list of initialization data
templates and replication counts, rather than a word-for-word
template of initialization information for a COMMON block.
Initialization is performed by copying the data item the
specified number of times, and repeating this for each item.
This only requires a template large enough to encompass the
unique section of the initialization data. For example, for an
initialization of 96000*0.5, the datum would be 0.5 and the copy
count would be 96000. This greatly reduces the size of the
initialization data area, and hence the compiled size of the
object. Thus it is possible to initialize many segments worth of
storage with the initialization information contained within a
single object segment.
MTB-583 Multics Technical Bulletin
LAs and VLAs
12.3 list_init_
list_init_ is used to perform the new 'list_template_init' form
of initialization and to ZERO-init storage.
It takes a template which has a unique datum, length
specification, and repetition count, and copies the correct
number of repetitions of the datum into the area to be
initialized. list_init_ is highly optimized for replication and
copying efficiency to speed up initialization, and is capable of
crossing segment boundaries at any bit point within the
replicated datum.
If list_init_ is supplied an initialization pointer of 'null ()',
it presumes that the area is to be set to ZERO, and
correspondingly does a very efficient EIS move with '0'b fill,
which sets pages to ZERO at the highest possible speed. On an
8/70M processor the ZERO-init executes at about 350 to 390 pages
per virtual cpu second.
There is an entrypoint, list_init_$variable_already_zero, which
skips ZERO initialization altogether. It is called by
set_ext_variable_, which allocates variables in an area that is
supposed to zero-on-free.
13 EXTERNALS
VLC externals are processed in a manner which makes them
compatible with current COMMON external usage. System support
routines fully implement allocation, initialization,
re-initialization and deletion of COMMON. A programmer does not
see any discontinuity in COMMON support, with the exception that
BLANK COMMON was always previously allocated at the maximum size
permissible, (255K - 50). With the expansion possible through
VLA BLANK COMMON such a full allocation to permit potential
future expansion of BLANK COMMON would needlessly waste system
resources which the user would have to pay for. Thus VLA BLANK
COMMON is limited to the size seen at the time of first
reference. Non-VLA BLANK COMMON will still be allocated to
255K-50 words and will be extensible to this limit.
14 STORAGE CLEANUP
Automatic storage cleanup is managed through the action of a
cleanup handler created in the stack frame of a compilation unit
which allocates extended storage. This cleanup handler releases
storage when the 'cleanup' condition is signaled either due to
termination of an object with a 'STOP', 'CALL EXIT', or the end
Multics Technical Bulletin MTB-583
LAs and VLAs
of a RUN UNIT, or when a 'release' of its stack frame is done.
This action, with the exception of the cleanup on-unit, is
invisible to the user. An LA/VLA program cannot normally create
a cleanup handler of its own without destroying the LA/VLA
handler. One exception is the cleanup processing of the
fortran_menu system, which integrates its cleanup handling with
existing cleanup handlers.
Extended internal static storage is cleaned up when the object
segment is terminated. This is accomplished by having term_ call
'fortran_storage_manager_$free' if the segment being terminated
was using extended static storage. A new linkage header flag,
static_vlas, has been defined for term_'s use. It is set by
fortran_storage_ when extended storage is allocated. If the
object segment is never explicitly terminated, storage is
released after the process terminates.
If external storage is never explicitly cleaned up, either
through cleanup handlers, 'term_' or 'delete_external_variables',
storage space is released through one of two methods.
1. If storage is allocated in the process directory, it is
removed in bulk by normal process termination cleanup when
the process directory is deleted. No code modifications are
required.
2. If extended storage is in a quota directory it is released
by the next process that needs segments from the same pool,
through the action of 'fortran_storage_manager_' checking
segments in fsm_info and finding segments assigned to dead
processes.
15 FORTRAN STORAGE MANAGER
Fortran extended storage is managed through the co-ordinated
actions of two support programs, 'fortran_storage_' and
'fortran_storage_manager_'.
Fortran_storage_manager_ is the low level routine which actually
acquires and releases storage, and manages allocation of
contiguous segment numbers.
Fortran_storage_ is the routine called to manage the total
storage requirements of the program, and it in turn calls
fortran_storage_manager_ to allocate individual storage items,
i.e. LA's and VLA's. Within an individual VLA all segment
numbers are continguous, but segment numbers between individual
LA's and VLA's do not have to follow this rule. Thus one can
MTB-583 Multics Technical Bulletin
LAs and VLAs
acquire storage without having the requirement of more than 64 or
so contiguous segment numbers available.
'fortran_storage_manager_' must solve a number of problems in the
allocation and control of extended storage:
1. Quota Management.
Extended storage requires extensive storage commitments to a
user or group of users, since it is possible to attempt to
address up to 2**30 words of storage within a process.
Quota is acquired by default from the user's process
directory, which places a limit upon the amount of storage
accessible. Most system administrators do not like, nor is
it really advisable in normal circumstances, to grant dozens
of thousands of pages quota to a user's process directory.
2. Quota Directories.
Fortran_storage_manager_ allows the user to direct that
quota is to be acquired from the resources of a specified
directory in the storage hierarchy.
This is termed an 'fsm quota directory'. Within this
directory fortran_storage_manager_ builds 'quota pools', one
per ring of execution. These quota pools will hold the
segments allocated for extended storage to programs
executing in that ring. Each pool is controlled through
information in a control and locking segment, fsm_info,
within that pool.
This quota assignment permits project and system
administrators to allocate sufficient quota in a controlled
manner to permit program execution, but without giving
carte-blanche to process directory limits (which are not
charged for).
The directory from which the user wishes to draw quota can
be specified through the user's 'value_segment' and
appropriate value segment commands. This directory is
specified by the value assigned to the variable
"fsm_dir_dir_path", which is taken as an absolute pathname.
For example:
vs fsm_dir_dir_path >udd>cg>quota_dir
3. Multi-user Access to Quota.
Fortran_storage_manager_ manages multi-user demands upon
quota pools through inter-locked quota allocation requests,
and the use of pool files within the 'quota pool'.
Multics Technical Bulletin MTB-583
LAs and VLAs
Allocation and control of files is done by a lock within a
control segment, fsm_info, maintained by
fortran_storage_manager_, while simple access protection is
done through the Multics ACL mechanism.
At this stage of development no AIM specific extensions to
storage management have been provided, nor would we consider
that fortran_storage_manager_'s management and internal
coding is finalized. It would be desirable to provide for
AIM, and even to provide storage directories at a lower ring
level to fix permissions and further enhance security and
protection mechanisms.
4. Multi-ring Access to Quota.
It is possible that programs requiring extended storage may
execute from a number of rings, either within one process or
a number of processes (if a quota directory is specified).
Avoiding ring access conflicts in pool files requires a
separation of quota pools for each ring level within quota
directories. This management is provided by
fortran_storage_manager_ creating quota pools within the
user specified directory with the name convention:
"fsm_dir_X" where the X is the ring number. This maintains
complete separation of files from one ring to another.
5. User access protection within quota directories.
Fortran_storage_manager_ attempts to maintain inter-user
protection within a quota pool by setting pool segment ACL's
to deny access to all but the assigned user.
When a segment is returned to the pool, and checked out to
another user, its ACL is changed to 'rw' for the newly
assigned user, and 'null' for all others. This prevents
accidental destruction of one user's extended storage by
another user, but does not protect against overt action.
Protection against overt action is the responsibility of the
owner of the quota directory, typically the project
administrator, who may create sub-directories within an
master directory, and set appropriate access to those
directories. The sub-directories can be used by individual
users as quota directories.
These directories may be assigned terminal directory quota
by the project administrator, or all feed from the quota of
the master directory, or the project directory.
MTB-583 Multics Technical Bulletin
LAs and VLAs
6. Dead Process Pool Storage Cleanup.
If a process leaves the system without cleaning up its
allocated storage segments in a quota pool, this storage
space will remain allocated, and charged for, until the next
time space is allocated in the pool by another process.
Dead process cleanup is done by 'fortran_storage_manager_'
when checking segments named in the pool fsm_info segment.
If it finds segments assigned to 'dead' processes it returns
them to the pool and truncates the segments. Thus it is
possible for 256K segments to hang around in the permanent
hierarchy in certain situations.
16 FSM_INFO
'fsm_info' is a structure based within the fsm_info segment, and
is defined below. Major pool locking is done through the lock
word within the structure, and locks the entire structure for
allocation and freeing. For each segment which has been
allocated in the pool there is an entry supplying a pointer which
'owns' the storage, and the process id of the process 'owning'
the storage. If the fsm_info structure data does not conform to
the contents of the pool directory, i.e. files are missing or
extra, an error condition is signalled by
'fortran_storage_manager_' to permit the user to correct the
error situation and restart, or to release and correct the error
situation. If no other users are using the quota pool, the
simplest form of correction is simply to delete all the files
within the pool and re-run the program.
dcl 01 fsm_info aligned based (fsm_info_ptr),
02 lock bit (36),
02 seg_cnt fixed bin,
02 seg (fsm_info.seg_cnt),
03 owning_process
bit (36),
03 owner ptr unal,
03 first_seg_in_group
fixed bin,
03 next_seg_in_group
fixed bin,
03 seg_num fixed bin;
17 FORTRAN_STORAGE_
This program is the major interface between the Fortran object
and allocation and initialization of external storage.
Multics Technical Bulletin MTB-583
LAs and VLAs
It is called through the 'fort_storage' pl1 operator which
creates an argument list containing a stack frame pointer, a
linkage section pointer and a pointer to the text word which
contains the creation list offset in the upper 18-bits. The
creation list is defined by the include file 'fortran_storage',
included below, and consists of a list of creation entries, each
of which may be followed by a list_template_initialization list.
The structure used by 'fortran_storage' is 'create_entry', which
defines all the information required to create a storage entity.
If the 'init' flag is set, there is an initialization list
following the creation entry which requires 'list_init_' to
complete initialization of the storage entity. The 'next' field
of each creation entry links that entry to the next in the chain,
using a text section offset, or is '0' to end the chain. Thus
'fortran_storage_' does not have to know how long the
list_template_initialization list is, since it will use 'next' as
a text section offset of the next creation entry.
The 'pointer_count' field is used to determine how many pointers
may be used to address all the sub-entities within a single VLA.
The 'pointer_offsets' array supplies the offset for each pointer
to be created.
COMMON must be created and initialized in a manner which permits
a superset of normal COMMON use. Thus fortran_storage_ has a
pointer in the creation information for COMMON to permit finding
the ITS link pointer and from the unsnapped pointer to find
definition and initialization information.
MTB-583 Multics Technical Bulletin
LAs and VLAs
The following diagram indicates the creation information.
Object Reference
tsx0 pr0|fort_storage
vfd 18/list,18/-1 ----|
|
. |
. |
. |
|
list: 01 create_entry <---------|
03 init
02 next ----------|
. |
. |
02 pointer_offsets |
|
01 create_init_entry |
01 create_init_entry |
. |
. |
0 |
|
01 create_entry <----------
03 ^init
02 next=0
/* BEGIN include file fortran_storage.incl.pl1 */
dcl 1 create_entry based,
2 location fixed bin (18) unsigned unal,
2 flags unaligned structure,
3 auto bit (1) unaligned,
3 static bit (1) unaligned,
3 common bit (1) unaligned,
3 LA bit (1) unaligned,
3 VLA bit (1) unaligned,
3 K256 bit (1) unaligned,
3 init bit (1) unaligned,
3 pad bit (2) unaligned,
3 pointer_count fixed bin (9) unsigned unal,
2 length fixed bin (24) aligned,
2 next fixed bin (18) unsigned unal,
2 name_length fixed bin (17) unaligned,
2 common_link fixed bin (18) unsigned unal,
2 block_name char (0 refer
(create_entry.name_length)),
2 pointer_offsets (0 refer
Multics Technical Bulletin MTB-583
LAs and VLAs
(create_entry.pointer_count)) aligned,
3 pad bit (12) unaligned,
3 offset fixed bin (24) unsigned unal;
dcl 1 create_init_entry based,
2 length fixed bin (35) aligned,
2 pad bit (6) unaligned,
2 repeat fixed bin (30) unsigned unal,
2 datum bit (0 refer
(create_init_entry.length));
/* END include file fortran_storage.incl.pl1 */
18 ERROR CONDITION SIGNALLING
Error conditions are signalled by 'fortran_storage_' and
'fortran_storage_manager_' in a number of situations.
Fortran_storage_manager_ signals fortran_storage_manager_error if
an error occurs in the assignment or creation of external
segments. The text which accompanies the error is descriptive of
the error cause and possible correction. Usually the condition
is restartable if the error cause is corrected.
Fortran_storage_ will signal fortran_storage_error if an error
occurs in the creation or initialization of external storage or
in the creation of a COMMON block. The text which accompanies
the error is descriptive of the error cause and possible
correction. Usually the condition is restartable if the error
cause is corrected.
Certain error causes are not restartable. If the user attempts
to restart them an error message to this effect is returned and
the restart is aborted. For such situations the user must
release and correct the error cause.
19 BINDER
The binder has been modified to permit the binding of VLC objects
with other VLC objects, and with non-VLC objects.
Two areas of the binder are affected by the requirements of VLC.
1. The binding of externals which are greater than a segment in
length but are initialized with ZERO templates.
MTB-583 Multics Technical Bulletin
LAs and VLAs
2. The binding of externals with list_init_templates, and
mixing of externals with such templates with others with
normal init templates or ZERO init templates.
The first section appears to essentially fall within the existing
capabilities of the binder, since there are no over-size
templates to handle, and the size of the external is only a
number to the binder, rather than a real area to be handled
and/or merged with others.
The second section is where the major binder modifications occur.
Here the binder must be able to understand about the
list_template_init template, and its length and size definitions.
It must be able to merge a normal template with a VLA ZERO init
template, to leave a list_template_init template with the correct
information for the init area, and to zero the remainder.
An additional feature of the binder is that the use of the
list_init_template is not restricted to only Large and Very Large
Arrays. It will also be used by the Fortran compiler as the
normal form of COMMON initialization, whether the area is large
or not, simply to reduce the size of the object segment. Thus
the binder must be able to do list_template_init manipulations
for normal COMMON externals.
When an external variable has several different initializations,
the binder chooses the longest template and the longest length.
It pads the template with zeroes if necessary to achieve the
proper length. To avoid filling the definition section with
zeroes, the padding is now always done in the list template
format. A type 3 (straight copy) template to be padded is
converted to list template form by making the original template
the first datum in the list.
Another space-saving optimization made to the binder is to have
it regenerate all the referenced initialization structures at the
end of the definition section, after all links have been
processed. Formerly it allocated every different initialization
structure it found in all the components, whether or not the
structures were referenced by links in the bound segment. The
LA/VLA Fortran changes are likely to cause even more unused
initialization structures.
20 LINKER
The linker has been modified, with modification to the routine
'set_ext_variable_' and the addition of 'list_init_' to be able
Multics Technical Bulletin MTB-583
LAs and VLAs
to handle both the list_template_init initialization form, and to
handle Very Large COMMON.
The use of the list_template_init initialization form is
completely handled by the routine list_init_ as called from
set_ext_variable_. This is independant of the size of the
variable being initialized. (fortran_storage_,
set_fortran_common and reset_external_variable also call
list_init_.)
Link snapping of a VLC link can only occur if a VLC block is
bound into a bound unit which has the same, but non-VLA, COMMON
block, and the object which 'owns' the reference to the non-VLC
is executed prior to execution of the VLA referencing object. At
this point the pointer to the COMMON in the linkage section has
not been snapped by VLA entry code, and must be snapped by the
linker (the binder has co-erced the external into a VLC
definition).
The linker accomplishes this snapping by out-calling to the
routine 'fortran_storage_$resolve_VLA_COMMON_link' to complete
the creation and initialization of a VLC reference. This
routine, the same one called through VLA entry code references to
'fortran_storage_', resolves and initializes the VLC and returns
control to the user program.
The reason the linker has to leave ring 0 for this is that
set_ext_variable_ creates VLAs by calling
fortran_storage_manager_$alloc, which cannot run in ring 0.
set_ext_variable_ knows that it is running in ring 0 when it is
called at a new entrypoint, $for_linker. The out-call uses the
same mechanism as first reference traps, i.e. invoking
link_trap_caller_ in the outer ring. In this case,
link_trap_caller_ calls fortran_storage_$resolve_VLA_COMMON_link
directly, after first making sure that it exists. If it does not
exist, a linkage_error condition is signalled with the new code
error_table_$no_vla_support
(The system does not currently support very large array common.).
21 TERM_
If 'fortran_storage_' creates any Large or Very Large static, the
flag 'linkage_header_flags.static_vlas' is set. This flag is
used by term_ and run_ to determine if it should call
'fortran_storage_manager_$free' when terminating or deleting a
segment which has a linkage section which must be freed by the
termination.
MTB-583 Multics Technical Bulletin
LAs and VLAs
22 RUN
The run unit manager has been modified to clean up any extended
storage used only within the run unit. This includes both
internal and external static storage.
Since run_ disposes of static sections without calling term_, it
also must check the static_vlas linkage header flag and must call
fortran_storage_manager_$free when the flag is set. run_ does
this while it is checking all known segments, terminating each
segment initiated only within the run unit. It is possible that
a program's static LAs and VLAs could have segment numbers that
are smaller than the program's segment number. To avoid
terminating extended segments before
fortran_storage_manager_$free is called for their owners, run_
calls fortran_storage_manager_$get_vla_segnos to get their
segment numbers. run_ then makes sure that it doesn't terminate
them itself. fortran_storage_manager_$get_vla_segnos is called
only when there are static extended segments allocated during the
run unit. This is indicated by the new stack header flag,
has_static_vlas. Its pre run unit value is saved during the run
unit and then restored.
When a run unit ends, run_ must also deallocate all VLA COMMON.
In order to avoid searching all the external variables when VLA
COMMON hasn't been used at all, there is a new flag in the header
of the external variable node list,
variable_table_header.flags.have_vla_variables. It indicates
that there are (or at least were) VLA external variables in the
run unit. (Each run unit has its own external variable node
list.)
The flags stack_header.has_static_vlas and
variable_table_header.flags.have_vla_variables take high order
space from variables that don't need all of the bits they
currently occupy.
23 SET_FORTRAN_COMMON
This program must be able to collect common references from a set
of programs and deal with the requirements of initialization
needed for both list template initialization and Very Large
COMMON. It calls set_ext_variable_ and list_init_.
Multics Technical Bulletin MTB-583
LAs and VLAs
24 LIST_EXTERNAL_VARIABLES
This program only requires a format change of the output listing
ioa string to permit the longer VLA sizes (up to 16MW) to be
printed.
25 DELETE_EXTERNAL_VARIABLES
This program calls fortran_storage_manager_$free to release VLC
segments. It uses the pointer to the variable node in the
externals list as the 'owner' of the external storage segments.
26 RESET_EXTERNAL_VARIABLES
This program has been modified to call list_init_ to reinitialize
list template initialized external variables.
27 PROBE (STU_$GET_RUNTIME_ADDRESS
A modification has been made to the symbol table utility
get_runtime_address to utilize the new VLA_based storage class
code. This class code indicates that subscript addressing for an
array found by a VLA_based pointer should be done with address
arithmetic. By using stu_$get_runtime_address probe fully
supports the LA/VLA product and permits full interactive
debugging of LA/VLA objects.
The compiler also outputs the base pointers to LA and VLA storage
segments in a form which easily permits the user to determine
their values through probe commands.
Base pointers to LA segments are of the form:
la$auto$xxxxxx or la$static$xxxxxx
where the xxxxxx string is the octal offset within the static
section or the stack to the ITS pointer to the segment. The
symbol map in the program listing will indicate the STORAGE class
of a variable placed into LA static or automatic as being:
la$auto$xxxxxx or la$static$xxxxxx.
Base pointers to VLA segments are of the form:
vla$auto$name or vla$static$name or vla$common$name
where the 'name' is the name of the array or common block being
referenced. Equivalenced variables will be found within the
MTB-583 Multics Technical Bulletin
LAs and VLAs
defining variable. The base pointer to VLA variables is
indicated in the STORAGE class section of the symbol map. Blank
common has the class name of: vla$common$_.
For example:
The command to probe:
v addr (a)
should produce the same output value as:
v vla$auto$a
and the command:
v addr (vla$auto$a)
should list the address in the stack of the packed pointer to the
VLA 'a'.
28 VLA CODE SEQUENCES
VLA segment addressing requires segments to be 256K words in
length, and treats addressing so that logical addresses to VLA's
are contiguous.
It is a function of the hardware instructions that a packed
pointer is an appropriate basis upon which to do efficient
address arithmetic. This permits 256K VLA addressing to be quite
efficient and not seriously degrade optimized or non-optimized
execution.
256K support deals with addresses as packed pointers. Addresses
are logical absolute addresses within segments which are 256K
words each.
As an example of code sequences produced we can use the following
code loop taken from a program in which all floating point
variables are double-precision. The major line of interest will
be 'if (sk (j) .eq. 0) goto 90'.
do 90 j=jdeb,jfinpg
jj=j-ii+i
if(sk(j).eq.0) go to 90
cc=sk(j)/sk(ii)
kk=lgn(jj)/10000
call triprd(sk(kk),sk(j),cc,jfin-j+1)
r1(jj)=r1(jj)-sk(j)*r1(i)
sk(j)=cc
90 continue
In the following non-optimized code sequence pr6|69 is a packed
pointer to the array 'sk', and pr6|237 is a temporary location
allocated by the compiler to hold the 'array_ref' packed pointer.
Multics Technical Bulletin MTB-583
LAs and VLAs
STATEMENT 1 ON LINE 52
if(sk(j).eq.0) go to 90
ldq pr6|149 j
qls 1
sbq 2,dl
adq pr6|69 sk
stq pr6|237
dfld 816
lprp7 pr6|237 sk
dfcmp pr7|0 sk
tnz 380
tra 465
The following code is optimized, and the extracted code, which is
moved to the head of the loop is shown. In this case the target
line is shown with the code which remains within the loop. Here
the temporary pr6|155 is compiler generated to hold the packed
pointer to sk(j). In addition the loop termination code, which
increments the packed pointer through an 'asq' is also shown, and
the specific increment noted with asterisks. If the increment
were simply by the constant '1', an aos would have been used.
EXTRACTED FROM STATEMENT 1 ON LINE 52
ldq pr6|151 j
qls 1
adq pr6|258
stq pr6|155
...
STATEMENT 1 ON LINE 52
if(sk(j).eq.0) go to 90
lprp7 pr6|155
dfld pr7|0 sk
tze 412
...
STATEMENT 1 ON LINE 58
90 continue
lcq 1,dl
asq pr6|157
MTB-583 Multics Technical Bulletin
LAs and VLAs
ldq 2,dl
asq pr6|155 ***
asq pr6|160
aos pr6|159
ldq pr6|157
cmpq pr6|262
tpl 372
Pointers are allocated with one packed pointer for each unique
entity within the array (multiple entities are due to
equivalencing or COMMON allocation) which holds the packed
pointer address of its start. Probe always utilizes the basic
non-offset packed pointer as the base.
29 DOCUMENTATION
Documentation updates have been supplied under a separate cover
to the Publications group.
30 INITIALIZATION STRUCTURES FOR TYPE 5 SYSTEM AND TYPE 6 LINKS
The following section can be considered a Reference Manual entry
for list template initialization.
These structures specify how a link target first referenced
because of a type 5 *system or a type 6 link should be
initialized. There is a common structure format supplying
variable size and initialization type information of the format:
(Structure information supplied from definition_dcls.incl.pl1)
/* initialization info for *system link */
declare (
INIT_NO_INIT init (0),
INIT_COPY_INFO init (3),
INIT_DEFINE_AREA init (4),
INIT_LIST_TEMPLATE init (5),
) fixed bin internal static options (constant);
/* for type = 0 or 4 */
declare link_init_ptr pointer;
declare 1 link_init aligned based (link_init_ptr),
2 n_words fixed bin (35), /* number to invent */
2 type fixed bin; /* see types above */
Multics Technical Bulletin MTB-583
LAs and VLAs
where:
n_words
is the number of words required by the new variable.
type
indicates what type of initialization is to be
performed. It can have one of the following values:
0 no initialization is to be performed.
3 copy the initial data into the newly defined
variable.
4 initialize the variable as an area.
5 initialize the variable according to the
appended list of templates.
When the initialization type is 3, the following structure is
used:
dcl 1 link_init_copy_info aligned based (link_init_ptr),
2 header aligned like link_init,
2 initial_data (link_init_n_words refer
(link_init_copy_info.header.n_words)) bit (36) aligned;
where:
header
is described as link_init above.
initial_data
is the image to be copied into the new variable.
When the initialization type is 5, the following structure is used:
dcl 1 link_init_list_template aligned based (link_init_ptr),
2 header aligned like link_init,
2 pad bit (18) unaligned,
2 n_words_in_list fixed bin (18) unsigned unaligned,
2 template (link_init_n_words_in_list refer
(link_init_list_template.n_words_in_list));
where:
MTB-583 Multics Technical Bulletin
LAs and VLAs
header
is described as link_init above.
n_words_in_list
is the size of the template.
template
is a list of structures of the following form:
dcl 1 list_template_entry aligned based,
2 n_bits fixed bin (35) aligned,
2 pad bit (6) unaligned,
2 repeat fixed bin (30) unsigned unaligned,
2 datum bit (link_init_n_bits_in_datum
refer (list_template_entry.n_bits));
where:
n_bits
is the bit length of the data item in the template.
A value of zero signifies the end of the list.
repeat
is the number of times the template data item needs
to be replicated to form a word-for-word template
into the initialized variable. A value of zero
signifies skipping of n_bits of the variable.
datum
is the actual data item which will be replicated into
the variable. This item may be any number of bits in
length within the limits of the object segment.
This simple initialization information is sufficient to
initialize very large areas of data, with quite complex values,
since it is all done on the basis of bit strings.
31 LIST_FORTRAN_STORAGE (LFS)
The user can obtain information about the allocation of extended
storage through the command list_fortran_storage (lfs).
List_fortran_storage provides a listing of the various storage
files assigned to a process, and groups them according to the
"owners" of the files. A file owner is the storage entity for
which the file is an extension. It is represented by a pointer.
For example, the owner of a static VLA is represented by a
pointer to the beginning of the active linkage section of the
Multics Technical Bulletin MTB-583
LAs and VLAs
program that uses the VLA. VLC is owned by the external variable
node which points to it. Automatic extended storage is owned by
the stack frame.
The output of list_fortran_storage indicates the owners of groups
of files. However, the user only gets information about the
files allocated to the current ring of execution.
A Commands and Active Functions Manual entry for lfs would be:
____________________ ____________________
list_fortran_storage list_fortran_storage
____________________ ____________________
SYNTAX AS A COMMAND:
lfs
FUNCTION: allows a user of Fortran Extended Storage (Large and
Very Large Arrays), to determine what extended storage segments
are assigned to the process and what groupings are in effect for
these storage areas.
ARGUMENTS: none.
MTB-583 Multics Technical Bulletin
LAs and VLAs
32 SET_EXT_VARIABLE_ (AG93-04)
_________________ _________________
set_ext_variable_ set_ext_variable_
_________________ _________________
NAME: SET_EXT_VARIABLE_
The set_ext_variable_ subroutine allows the caller to look up an
external variable by name. If the name is not found, the
variable is added to the list of external variables.
USAGE
declare set_ext_variable_ entry (char(*), ptr, ptr, bit(1)
aligned, ptr, fixed bin(35));
call set_ext_variable_ (ext_name, init_info_ptr, sb_ptr,
found_sw, node_ptr, code);
ARGUMENTS
ext_name
is the name of the external variable. (Input)
init_info_ptr
is a pointer to the initialization info (see "Notes" below).
(Input)
sb_ptr
is a pointer to the base of the stack of the caller. (Input)
found_sw
is set to indicate whether the variable was found or not.
(Output)
node_ptr
is a pointer to the external variable node. (see "Notes"
below) (Output)
code
is an error code. (Output)
NOTES
When a new external variable is allocated (not found), it must be
initialized. The structures that init_info_ptr may point to are |
Multics Technical Bulletin MTB-583
LAs and VLAs
described in system_link_init_info.incl.pl1 and are documented as |
part of the object segment's definition section in the Multics |
Programmer's Reference Manual, Appendix G. |
Great care should be taken when using the node_ptr. The
variable_node structure should never be modified. Modifications
to the variable_node will have unpredictable results.
STRUCTURE ELEMENTS
A pointer to the following structure is returned by the entry
points in this subroutine. It is declared in
system_link_names.incl.pl1.
dcl 1 variable_node aligned based,
2 forward_thread ptr unaligned,
| 2 vbl_size fixed bin(24) unsigned unaligned,
2 init_type fixed bin(11) unaligned,
2 time_allocated fixed bin(71),
2 vbl_ptr ptr,
2 init_ptr ptr,
2 name_size fixed bin,
2 name char (nchars refer (variable_node.name_size));
forward_thread
is used by the linker to thread this variable to the next.
vbl_size
is the size, in words, of this variable.
init_type
is the type of initialization that is performed:
0 none
3 initialize from template
4 initialize to an empty area
| 5 initialize from list template
time_allocated
is the clock reading at the time this variable was allocated.
vbl_ptr
is a pointer to the variable's storage.
init_ptr
is a pointer to the initialization template.
name_size
is the number of characters in the variable name.
MTB-583 Multics Technical Bulletin
LAs and VLAs
name
is the name of the variable.
ENTRY: SET_EXT_VARIABLE_$LOCATE
This entry point locates the specified external variable and
returns a pointer to the structure describing the variable.
USAGE
declare set_ext_variable_$locate entry (char(*), ptr, ptr,
fixed bin(35));
call set_ext_variable_$locate (ext_name, sb_ptr, node_ptr, code);
ARGUMENTS
ext_name
is the name of the external variable. (Input)
sb_ptr
is a pointer to the base of the stack of the caller. (Input)
node_pointer
is a pointer to the variable_node describing the specified
variable. This structure is defined in the
system_link_names.incl.pl1 include file. (see "Notes" above)
(Output)
code
is an error code. (Output)
ENTRY: SET_EXT_VARIABLE_$FOR_LINKER |
This entry is similar in function to the set_ext_variable_ entry |
but may only be called in ring 0. If the size of the variable is |
to be greater than sys_info$max_seg_size, this entry traps to the |
referencing ring to perform the allocation and to snap the link. |
USAGE |
declare set_ext_variable_$for_linker entry (char(*), ptr, ptr, |
bit(1) aligned, ptr, fixed bin(35),ptr, ptr, ptr, ptr); |
call set_ext_variable_$for_linker (ext_name, init_info_ptr, |
sb_ptr, found_sw, node_ptr, code, mc_ptr, def_ptr, type_ptr, |
link_ptr); |
Multics Technical Bulletin MTB-583
LAs and VLAs
| ARGUMENTS
| ext_name
| is the name of the external variable. (Input)
| init_info_ptr
| is a pointer to the initialization info (see "Notes" above).
| (Input)
| sb_ptr
| is a pointer to the base of the stack of the caller. (Input)
| found_sw
| is set to indicate whether the variable was found or not.
| (Output)
| node_ptr
| is a pointer to the external variable node. (see "Notes"
| above) (Output)
| code
| is an error code. (Output)
| mc_ptr
| is a pointer to the machine conditions for the linkage fault
| (Input)
| def_ptr
| is a pointer to the base of the definition section of the
| segment that contains the link to the variable. (Input)
| type_ptr
| is a pointer to the type pair of the link to the variable.
| (Input)
| link_ptr
| is a pointer to the (unsnapped) link to the variable. (Input)
MTB-583 Multics Technical Bulletin
LAs and VLAs
33 CHANGE TO STACK HEADER (AG91-03)
Stack Header
The stack header contains pointers (on a per-ring basis) to
information about the process, to operator segments, and to code
sequences that can be used to invoke the standard call, push,
pop, and return functions (described below). Figure H-1 gives
the format of the stack header. The following descriptions are
based on that figure and on the following PL/I declaration.
dcl 1 stack_header based aligned,
2 pad1(4) fixed bin,
2 old_lot_ptr ptr,
2 combined_stat_ptr ptr,
2 clr_ptr ptr,
2 max_lot_size fixed bin(17) unaligned,
2 main_proc_invoked fixed bin (11) unaligned, |
2 have_static_vlas bit (1) unaligned, |
2 pad4 bit (2) unaligned, |
2 run_unit_depth fixed bin(2) unaligned, |
2 cur_lot_size fixed bin(17) unaligned,
2 pad2 bit(18) unaligned,
2 system_storage_ptr ptr,
2 user_storage_ptr ptr,
2 null_ptr ptr,
2 stack_begin_ptr ptr,
2 stack_end_ptr ptr,
2 lot_ptr ptr,
2 signal_ptr ptr,
2 bar_mode_sp_ptr ptr,
2 pl1_operators_ptr ptr,
2 call_op_ptr ptr,
2 push_op_ptr ptr,
2 return_op_ptr ptr,
2 short_return_op_ptr ptr,
2 entry_op_ptr ptr,
2 trans_op_tv_ptr ptr,
2 isot_ptr ptr,
2 sct_ptr ptr,
2 unwinder_ptr ptr,
2 sys_link_info_ptr ptr,
2 rnt_ptr ptr,
2 ect_ptr ptr,
2 assign_linkage_ptr ptr,
2 pad3(8) fixed bin;
Multics Technical Bulletin MTB-583
LAs and VLAs
where:
1. pad1
is unused.
2. old_lot_ptr
is a pointer to the linkage offset table (LOT) for
the current ring. This field is obsolete.
3. combined_stat_ptr
is a pointer to the area in which separate static
sections are allocated.
4. clr_ptr
is a pointer to the area in which linkage sections
are allocated.
5. max_lot_size
is the maximum number of words (entries) that the LOT
and internal static offset table (ISOT) can have.
| 6. main_proc_invoked
| is nonzero if a main procedure was invoked in a
| currently active run unit.
| 7. have_static_vlas
| is "1"b if internal static large or very large arrays
| are being used.
| 8. pad4
| is unused and must be "0"b.
9. run_unit_depth
is the current run unit level.
10. cur_lot_size
is the current number of words (entries) in the LOT
and ISOT.
11. pad2
is unused.
12. system_storage_ptr
is a pointer to the area used for system storage,
which includes command storage and the *system link
name table.
MTB-583 Multics Technical Bulletin
LAs and VLAs
34 CHANGE TO SYMBOL TABLE (AG91-03)
18. class
contains a positive binary integer that gives the
storage class of the current identifier; the possible
classes are:
class storage class
1 automatic; L is the offset at which the
current identifier is defined in the stack
frame associated with the current block.
2 automatic adjustable; the address of the
current identifier is not known at the time
the runtime symbol table is created.
Location L in the stack frame associated
with the current block contains a pointer
to the storage for the current identifier.
3 based; location is a self-relative pointer
to the runtime_symbol for the pointer used
in the declaration of the current
identifier or is zero if a pointer was not
specified. The user must provide a
pointer, either explicitly at run time or
implicitly through the default pointer, in
order to reference the current identifier.
4 internal static; L is the offset at which
the current identifier is assigned storage
in the linkage section associated with the
current block.
5 external static; L is the offset in the
linkage section of a link that points to
the current identifier.
6 internal controlled; L is the offset of the
control block of the current identifier in
the linkage section of the current block.
7 external controlled; L is the offset in the
linkage section of a link that points to
the control block for the current
identifier.
8 parameter; at L in the stack frame
corresponding to the current block there is
a pointer to the storage for the current
Multics Technical Bulletin MTB-583
LAs and VLAs
identifier. This storage class is used
when the current identifier appears in more
than one position in procedure and/or entry
statements in the block.
9 parameter; L gives the position of the
current identifier in the argument list
provided to the current block. This class
is used when the current identifier appears
in the same position in every procedure or
entry statement in the current block.
| 10 very large array; L is a self-relative
| pointer to the runtime_symbol for the
| pointer to the beginning of the Very Large
| Array. Address arithmetic MUST be used to
| calculate offsets from this base.
11 not used
12 text reference; the current identifier is
defined at L in the text section of the
object segment.
13 link reference; the current identifier is
defined at L in the linkage section
corresponding to the current block.
14 not used
15 not used
MTB-583 Multics Technical Bulletin
LAs and VLAs
35 INCLUDE FILES
The include file 'stack_header' has already been listed above.
/* Begin include file ... system_link_init_info.incl.pl1 ... 5/6/80 MRJ */
dcl init_info_ptr ptr;
| dcl init_size fixed bin (35);
dcl 1 init_info aligned based (init_info_ptr),
| 2 size fixed bin (35),
2 type fixed bin,
2 init_template (init_size refer (init_info.size))
fixed bin (35);
dcl 1 init_info_single_word aligned based (init_info_ptr),
2 size fixed bin (19),
2 type fixed bin,
2 init_template (1) fixed bin (35);
| dcl 1 list_init_info aligned based,
| 2 size fixed bin (35),
| 2 type fixed bin,
| 2 pad bit (18) unaligned,
| 2 list_size fixed bin (18) unsigned unaligned,
| 2 template (0 refer (list_init_info.list_size))
| bit (36);
|
| /* A list template consists of a series of entries with the following
| description, concatenated together. n_bits and datum are bit items,
| to permit a wide range of inputs.
|
| 1. A 'repeat' of '0' signifies skipping of 'n_bits' bits.
| 2. A 'n_bits' of '0' signifies the last item of the list.
|
| COMMON, VLA's, and LA's are presumed to start at the base pointer
| of their particular storage section. */
| dcl 1 list_template_entry aligned based,
| 2 n_bits fixed bin (35) aligned,
| 2 pad bit (6) unaligned,
| 2 repeat fixed bin (30) unsigned unaligned,
| 2 datum bit (init_n_bits_in_datum
| refer (list_template_entry.n_bits));
|
| dcl init_n_bits_in_datum fixed bin (35);
dcl NO_INIT fixed bin static options (constant)
init (0);
Multics Technical Bulletin MTB-583
LAs and VLAs
dcl TEMPLATE_INIT fixed bin static options (constant)
init (3);
dcl EMPTY_AREA_INIT fixed bin static options (constant)
init (4);
| dcl LIST_TEMPLATE_INIT fixed bin static options (constant)
| init (5);
/* End include file ... system_link_init_info.incl.pl1 */
/* BEGIN INCLUDE FILE ... system_link_names.incl.pl1 */
dcl 1 variable_table_header aligned based,
2 hash_table (0:63) ptr unaligned,
2 total_search_time fixed bin (71),
2 total_allocation_time fixed bin (71),
2 number_of_searches fixed bin,
| 2 number_of_variables fixed bin (35),
| 2 flags unaligned,
| 3 have_vla_variables bit (1) unaligned,
| 3 pad bit (11) unaligned,
| 2 cur_num_of_variables fixed bin (24) unal,
2 number_of_steps fixed bin,
2 total_allocated_size fixed bin (35);
dcl 1 variable_node aligned based,
2 forward_thread ptr unaligned,
| 2 vbl_size fixed bin (24) unsigned unaligned,
| 2 init_type fixed bin (11) unaligned,
2 time_allocated fixed bin (71),
2 vbl_ptr ptr,
2 init_ptr ptr,
2 name_size fixed bin,
2 name char (nchars refer (variable_node.name_size));
/* END INCLUDE FILE ... system_link_names.incl.pl1 */
In linkdcl.incl.pl1 and object_link_dcls.incl.pl1,
Change the precision of run_depth in the declaration of link
from 5 to 2 to correspond to the stack header change.
Add the following:
MTB-583 Multics Technical Bulletin
LAs and VLAs
declare 1 linkage_header_flags
aligned based,
2 pad1 bit (28) unaligned,
2 static_vlas bit (1) unaligned,
2 perprocess_static
bit (1) unaligned,
2 pad2 bit (6) unaligned;
In definition_dcls.incl.pl1,
add
INIT_LIST_TEMPLATE init (5)
after
INIT_DEFINE_AREA init (4),
and add:
/* for type = 5, there is a list template to copy */
declare 1 link_init_list_template
aligned based (link_init_ptr),
2 header aligned like link_init,
2 pad bit (18) unaligned,
2 n_words_in_list fixed bin (18) unsigned unaligned,
2 template (link_init_n_words_in_list refer
(link_init_list_template.n_words_in_list));
declare link_init_n_words_in_list
fixed bin;
declare 1 list_template_entry aligned based,
2 n_bits fixed bin (35) aligned,
2 pad bit (6) unaligned,
2 repeat fixed bin (30) unsigned unaligned,
2 datum bit (link_init_n_bits_in_datum refer
(list_template_entry.n_bits));
declare link_init_n_bits_in_datum
fixed bin (35);
Multics Technical Bulletin MTB-583
LAs and VLAs
Appendix A - Case for Contiguous Segments
A1 CASE FOR CONTIGUOUS SEGMENTS
This section presents the reasons why we, as the developers,
would prefer to use Contiguous Segments, rather than a Dope
Vector approach to the implementation of Large Arrays (LA's) and
Very Large Arrays (VLA's).
It was originally put together before implementation was done, to
justify the methods to be employed and the design decisions.
Since it essentially makes its point, and this information
shouldn't be lost it is included here and has not been re-phrased
to treat the subject in the past or present tense.
A1.1 Summary
The conclusion, based upon these reasons, is that the best
implementation will be done using a contiguous segment allocation
to manage Very Large Arrays (VLA's), rather than using a dope
vector manager to manage the accessing of VLA's through a dope
vector.
The use of dope vectors would result in more code, a more
extensive subroutine/function call, and considerably more
allocated storage required for the manager of the dope vectors.
The only case for using a dope vector manager is to handle the
possible problems of finding large enough contigous holes in the
KST to use VLA's, and it is only VLA's which require contiguous
segments.
The case against a dope vector manager is considerably larger and
ranges from the intrinsic feelings of duplication of one of the
basic parts of the Multics system - segmentation tables and
hardware addressing, to the additional processor, memory, and
execution problems introduced by a dope vector manager. In
addition, the dope vector manager must be used in all cases where
an array could potentially be a VLA, with contiguous segments
this is intrinsic and falls out as a no-code general case
sub-set.
MTB-583 Multics Technical Bulletin
LAs and VLAs
A1.2 Contiguous Segments
Contiguous segment allocation for VLA's results from considering
a segment number to be an extension of the word address within a
segment. Managing the segment number can be done in one of two
methods:
1. Have a routine which splits a subscript word address and
seperately manipulates the segment number modification and
the word number modification to arrive at a final word
pointer.
2. Utlize existing arithmetic of the processor and the
characteristics of a packed pointer to do the segment and
word manipulations in one combined operation. This relies
upon the characteristics of a packed pointer having the word
number in the lower 18 bits, and the next 12 bits as the
segment number. This positioning permits a carry out of the
word number to correctly manipulate a segment number.
The requirement of this form of address management is a
contiguous allocation of segment numbers to the contiguous
segments which comprise the VLA, and the use of a packed pointer
to access the VLA.
Typical code sequences are:
<Calculate offset in A or Q>
ada array_base_pptr OR adq array_base_pptr
sta pp_temp OR stq pp_temp
lprpX pp_temp
<Pointer Register X now has pointer to array element>
A1.3 Dope Vectors
Dope vector management works through the creation of a vector of
pointers to the segments of a VLA. Instead of using the segment
portion of a word address into the array to directly access a
segment number, it is used to address an entry in the array of
pointers, then the word offset is applied to this pointer. This
results in a method which does not require a contiguous
allocation of segment numbers, since the dope vector is in effect
a translation table to arrive at a true segment number.
Multics Technical Bulletin MTB-583
LAs and VLAs
Dope vector management is however an additional stage over and
above the memory management of the Multics system, and as such
requires that all accesses to potential VLA's go through the dope
vector manager to create a dope vector for the array. It also
requires storage in the user's address space be allocated to hold
the dope vector.
Various code sequences for dope vector access can be formulated,
the following is perhaps the most optimal access, and relies upon
the hardware's ability to split the A and Q register into two
18-bit sections, thus isolating the segment portion and word
offset portion of a dope vector reference.
<Calculate offset in A or Q>
lprpX dope_vector,au OR lprpX dope_vector,qu
ldY prX|0,al OR ldY prX|0,ql
<This actually does the reference. The ldY could also be stY.>
This depends upon two characteristics of dope vectors:
1. The dope vector MUST address the base of a segment. If it
does not then the al or ql modification in the load or store
instruction will WRAP-AROUND rather than incrementing the
segment number.
2. The array to be referenced MUST start at the start of the
segment. This causes this form of code to be unusable to
address arrays within a VLC BLOCK, or to address VLA array
sub-sections.
3. The dope vector must be managed by the dope vector manager,
and since its length is unknown at compile time, the dope
vector must be accessed through a pointer, rather than simply
being found on the stack. Thus the code sequence seen above,
which implies a local known dope vector is somewhat
simplistic. Any dope vector access will require making a
pointer to the dope vector in addition to the above code.
Due to the problems noted in 2. a more extensive manipulation
must be done to utlize dope vectors, which is rather similar to
that of consectutive segment allocation.
In this case an additional word of information is necessary,
which is the offset within the segment of the start of the array,
which must be added to the calculated subscript word offset
BEFORE addressing the dope vector. This is the equivalent of
adding the subscript word offset to the packed pointer in the
case of Contiguous Segments. Elements within COMMON BLOCKS would
MTB-583 Multics Technical Bulletin
LAs and VLAs
have the array offset of the relative position of the array
within the COMMON BLOCK, while the dope vector manage would have
to have an offset array paralleling the dope vector to hold the
array offset from the base of the pointer stored within the dope
vector element.
A1.4 Code Requirements for Managing with Dope Vectors
When managing storage through the use of dope vectors we would
have a number of parts to the execution of an object.
1. Initialization. At this step the stack frame and storage
requirements of the object are initialized. The dope
vector manager is called to create all array segments and
to build dope vectors for VLA's. These dope vectors will
have to be stored in an accessible region within the
storage of the dope vector manager. This space will have
to be allocated by the dope vector manager when the array
is created.
2. Execution. At this step, which occurs in EVERY subroutine or
function call, the arguments to the subroutine and/or
function are validated by the dope vector manager. This
validation is necessry to build a dope vector for array
referencing. This validation is independant of whether
the routine is quick or not, unless we put in quite a bit
more knowledge of the global characteristics of a fortran
program.
If a VLA is passed the dope vector manager will find the
dope vector for the array and return it to the calling
routine. The calling routine will have to link to the
dope vector stored in the manager's storage areas. This
is necessary since the called routine will have no
definitive knowledge the the length of the array it is
called with and thus will not be able to set aside
sufficient storage space for a dope vector. Only the
dope vector manager knows the real length of arrays and
has the dope vector for them.
For non-VLA's there may be no dope vector, since we could
be called from other than a fortran object with a short
array. Thus we will have to create one with the dope
vector manager, and the dope vector thus created will
have to be stored in the storage area of the dope vector
manager. The dope vector created will indicate the
segment number which contains the start of the array, and
the word offset within the segment of the start of the
array.
Multics Technical Bulletin MTB-583
LAs and VLAs
Thus the dope vector manager will have to create a dope vector at
runtime for any array which is being considered to be a VLA, but
which in fact was not previously created by the dope vector
manager. Problems of garbage collection will also have to be
addressed.
In essence one will be creating within the Multics hardware
environment a simulator of Multics memory management.
A1.5 Code requirements for Contiguous Segments
Contiguous segment access has been outlined above, the complete
breakdown of the phases of code are:
1. Initialization. At this step the stack frame and storage
requirements of the program are initialized. The Array
Manager is called to create all array segments.
2. Execution. At this step, which occurs in EVERY subroutine or
function call, the pointers passed to arrays which will
be considered to be VLA's are stored in local storage as
packed pointers. This storage is allocated in the stack
frame of the routine since only a single word is
necessary, no matter how long the array is.
Arrays which are short, that is less than a segment in
length, and do not cross segment boundaries, are simply a
sub-set of the general VLA case. The pointer to such an
array is not, and need not be, considered any differently
than the pointer to a VLA.
MTB-583 Multics Technical Bulletin
LAs and VLAs
A1.6 Conclusions
As is obvious from the above there is less complex coding
required for the use of contiguous segment numbers. In addition,
dope vector management requires the existence of a dope vector
for ALL arrays which are to be considered as Very Large Arrays.
If such an array was not created by the dope vector manager, the
dope vector must still be created and storage space allocated.
In all cases the dope vector must be verified, located, and
passed to the called routine. This is a dynamic runtime
requirement.
In order to permit the general addressing features required for
the generation of compatable Fortran code, dope vector addressing
must include an additional stage in which an array offset from
the base of the segment is added to a word offset within the
array, BEFORE dope vector referencing is done. The dope vector
itself is only found through a pointer which is supplied by the
dope vector manager, thus a pointer to the dope vector must be
setup before the dope vector can be accesed. Thus the amount of
code and execution speeds of the two approaches are very close
for normal referencing.
The difference between a dope vector approach, and a contiguous
segment apprach hinges highly upon whether it is totally
unacceptable to have contiguous segments. If this is not
preceived as an unacceptable thing then the contiguous segment
allocation will certainly harbour fewer inherent complexities and
potential bugs.
Futher the difference operationally between the dope vector
approach and the contiguous segment appproach lies almost
entirely in the necessity of the dope vector approach to validate
and create dope vectors dynamically at routine entry. The code
produced to actually reference storage and to initialize arrays
is almost the same, and reference code in both cases is generated
in-line.