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.