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.