TARTAN, INC. ADA 9X PROJECT: USER/IMPLEMENTER DEMONSTRATION PROGRAM IMPLEMENTATION REPORT OCTOBER 20, 1992 This document was prepared by Tartan, Inc., 300 Oxford Drive, Monroeville, PA 15146, for the Department of the Air Force, Kirtland AFB, NM 87117, as part of CDRL A004 of Contract F08635-91-C-0135. APPROVED FOR PUBLIC RELEASE; DISTRIBUTION IS UNLIMITED Copyright 1992, Tartan, Inc. All rights reserved. Reprinting permitted if accompanied by this statement. Tartan, Inc. 300 Oxford Drive Monroeville, PA 15146 DEC, VAX, VMS, MicroVAX, and MicroVMS, are trademarks of Digital Equipment Corporation. Intel, i960MC, and ICE are trademarks of Intel Corporation. o Other brand and product names appearing in this documentation are trademarks or registered trademarks of their respective holders. This report has been produced under the sponsorship of the Ada 9X Project Office. Printed in the U.S.A. ADA 9X PROJECT: USER/IMPLEMENTER DEMONSTRATION PROGRAM PART 1: IMPLEMENTATION OCTOBER 20, 1992 EXECUTIVE SUMMARY The overall goal of the Ada 9X Project is to revise and refine Ada 83 [5] to satisfy critical revision requirements from the Ada community while at the same time minimizing any negative impact and maximizing the benefits to this community. The objective of the User/Implementer (UI) Teams is to provide a testbed for the Ada 9X proposals developed by the Mapping Revision Team (MRT) as solutions to the aforementioned critical requirements. Each UI Team evaluated several proposals for ease of implementation and use, and reported their findings to the MRT. This UI Team, comprising the Military Electronics and Avionics Division of TRW and Tartan, evaluated the affects of the language changes on embedded avionics applications. Tartan implemented the language changes into an existing compilation system and provided feedback on this process. TRW evaluated the proposals from the Ada user's perspective by revising their Ada Avionics Real-Time System (AARTS) to make use of the language changes. The real-time proposals that were studied include the protected type, the requeue operation, asynchronous transfer of control and multi-way entry calls, task scheduling and queuing policies, and protected procedure interrupt handlers. In addition, the team investigated the hierarchical library and type extension proposals. Preliminary evaluations of the Ada 9X real-time features by Tartan and TRW have shown noticeable performance improvements over comparable tasking constructs. The hierarchical libraries have enhanced the development of subsystems within large Ada systems, as shown in the revised AARTS. The study of the Ada 9X proposal for type extension has indicated that it follows on naturally from the Ada 83 type structure. The Ada 9X User/Implementer Program has assisted the Ada 9X Project in determining the impact of proposed language changes on the user and implementer communities. It has also provided considerable feedback to the Mapping Revision Team on the feasibility of their proposals and the interactions of language changes with existing language features and implementations. The Implementer teams will continue their evaluation and feedback on the proposals and the language reference manual. The Implementer teams are sharing their experiences with other implementers in technical discussions on the electronic vendors bulletin board. The Implementer teams are contributing to the work of the ACVC team in the development of an Ada 9X test suite. TARTAN ADA 9X IMPLEMENTATION REPORT EXECUTIVE SUMMARY TABLE OF CONTENTS 1. Introduction 1-1 1.1. Configuration 1-1 1.2. Compiler Architecture 1-2 1.3. Protected Architectures 1-2 1.3.1. Protected Architecture Definition 1-3 1.4. ACVC Tests 1-4 1.5. Reference Notation 1-5 2. Protected Types and Requeue 2-1 2.1. Scope 2-1 2.2. Definitions 2-1 2.3. Requirements 2-2 2.4. Protected Type Design and Implementation 2-8 2.4.1. Data Structures 2-8 2.4.2. Algorithms 2-12 2.4.3. Requeue 2-18 2.4.4. Integration with the RTS and Ada 83 2-18 2.5. Performance 2-19 2.6. Architectural Issues 2-19 2.6.1. Task Stack 2-20 2.6.2. Protected Region 2-20 2.6.3. Low-Level Locks 2-20 2.7. Optimizations 2-20 2.7.1. Procedure Optimizations 2-21 2.7.2. Barrier Optimizations 2-21 2.8. Conclusions and Recommendations 2-21 3. Asynchronous Transfer of Control 3-1 3.1. Introduction 3-1 3.2. Design Constraints 3-1 3.2.1. Queue Algorithms and Elements 3-2 3.2.2. Multi-Way Select Statement 3-3 3.2.3. Asynchronous Transfer of Control 3-4 3.2.4. Delay Expiration 3-5 3.3. Cost of Implementation 3-5 3.3.1. Runtime System Maturity 3-6 3.3.2. Distributed Overhead 3-6 3.3.3. Non-Deterministic Time 3-6 3.3.4. Non-Deterministic Space 3-6 3.3.5. Compilation Costs 3-6 3.3.6. Hard Real-Time versus Soft Real-Time 3-7 4. Interrupts 4-1 4.1. Scope 4-1 4.2. Definitions 4-1 4.3. Requirements 4-1 4.4. Interrupt Handler Procedures Design and Implementation 4-4 4.4.1. Data Structures 4-4 4.4.2. Algorithms 4-4 4.5. Architectural Issues 4-6 4.5.1. Protected Memory 4-6 4.5.2. Interrupt Table 4-7 4.5.3. Interrupt Stack 4-7 4.6. Performance 4-7 4.7. Conclusions and Recommendations 4-7 TARTAN ADA 9X IMPLEMENTATION REPORT i 5. Entry Queuing Policies 5-1 5.1. Scope 5-1 5.2. Requirements 5-1 5.3. Entry Queuing Policies Design and Implementation 5-2 5.3.1. Data Structures 5-2 5.3.2. Algorithms 5-3 5.4. Performance 5-5 5.5. Conclusions and Recommendations 5-5 6. Hierarchical Program Libraries 6-1 6.1. Scope 6-1 6.2. Requirements 6-1 6.2.1. Subunits within a library unit are not required to 6-1 have distinct simple names 6.2.2. Library units may form a hierarchy 6-2 6.3. General Discussion 6-4 6.3.1. Compiler 6-4 6.3.2. Librarian 6-5 6.4. Implementation 6-6 6.4.1. Implementation of HL-FE-1 6-6 6.4.2. Implementation of HL-L-1 6-6 6.4.3. Implementation of HL-L-2 6-7 6.4.4. Implementation of HL-L-3 6-7 6.4.5. Implementation of HL-FE-2 6-7 6.4.6. Implementation of HL-FE-3 6-9 6.4.7. Implementation of HL-FE-4 6-9 6.4.8. Implementation of HL-FE-5 6-10 6.4.9. Implementation of HL-FE-6 6-11 6.4.10. Implementation of HL-FE-7 6-12 6.4.11. Implementation of HL-FE-8 6-13 6.4.12. Implementation of HL-FE-9 6-13 6.4.13. Implementation of HL-FE-10 6-14 6.4.14. Implementation of HL-FE-11 6-15 6.4.15. Implementation of HL-FE-12 6-15 6.4.16. Implementation of HL-FE-13 6-16 6.4.17. Implementation of HL-L-5 6-16 6.4.18. Implementation of HL-L-6 6-17 6.4.19. Implementation of HL-L-7 6-18 6.4.20. Implementation of HL-L-8 6-19 6.4.21. Implementation of HL-L-9 6-20 6.4.22. Implementation of HL-L-10 6-20 6.4.23. Implementation of HL-L-7 6-20 6.4.24. Implementation of HL-L-12 6-21 6.4.25. Implementation of HL-L-13 6-21 6.5. Conclusions 6-23 7. Tagged Types and Type Extension 7-1 7.1. Scope 7-1 7.2. Requirements 7-1 7.3. Implementation 7-6 7.3.1. Compile-time Representation 7-7 7.3.2. Fundamental Primitives 7-13 7.3.3. Overload Resolution 7-15 7.3.4. Run-time Representation 7-17 7.4. Conclusions 7-19 TARTAN ADA 9X IMPLEMENTATION REPORT ii References 0-1 Index I-1 TARTAN ADA 9X IMPLEMENTATION REPORT iii LIST OF FIGURES FIGURE 1-1: 1750A Extended Memory Architecture 1-3 FIGURE 1-2: i960MC Architecture 1-4 FIGURE 2-1: Protected Type Data Structure (PRTS) 2-10 FIGURE 2-2: Protected Data Record (PRD) 2-10 FIGURE 2-3: Protected Object Control Block (PRCB) 2-12 FIGURE 2-4: User Defined Protected Type Example Code 2-13 FIGURE 2-5: Protected Type Elaboration Code 2-14 FIGURE 2-6: Protected Object Elaboration Code 2-15 FIGURE 5-1: Priority Subtypes 5-3 FIGURE 7-1: Extended Record Type Representation 7-18 FIGURE 7-2: Tag Representation 7-19 TARTAN ADA 9X IMPLEMENTATION REPORT iv CHAPTER 1 INTRODUCTION This report describes several prototype designs and implementations of features proposed by the Ada 9X Mapping Revision Team (MRT) to be included in the Ada 9X standard language definition. 1.1. CONFIGURATION The Tartan Ada i960MC-Targeted Compilation System, Version 4.1 FVM, is the production quality Ada Compilation System used as the baseline in this project. This host computer for this system can be any DEC VAX, MicroVAX, VAXStation, or Vax-Server computer. The host operating system for the Tartan Ada compiler is the VAX/VMS environment, versions 5.2 through 5.4. The target processor for this exercise is the i960MC, Intel's high-performance, 32-bit military embedded processor. The i960MC is designed to support Ada in high-performance, embedded systems and to directly support Ada tasking models [4]. The target system does not require or provide an operating system. Instead, the Tartan Full-Virtual Mode (FVM) Runtime System provides the equivalent functionality. The Tartan Ada compilation systems are designed to fully utilize and enhance the i960MC features, including the following: - Ada tasks are mapped to i960MC processes. - Ada task priorities are mapped directly to i960MC process priorities. - The processor memory management unit is used to provide interapplication protection and zero execution overhead stack checks. - The on-chip floating point unit is used to perform floating-point operations. - Processor hardware is used to provide automatic dispatching and preemptive scheduling of Ada tasks. - Most processor data structures are generated automatically by the linker. The i960MC hardware ensures that the highest priority task is always the one that is running. It also switches to a higher priority task should one become ready to run. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 1-1 The Tartan Full-Virtual Mode (FVM) Runtime System is composed of five subsystems: - Execution Environment - Exception Management - Tasking Support - Storage Management - Attribute Support Each subsystem is designed to be a relatively independent functional unit. The Execution Environment and the Exception Management subsystems are required for any application. If the features provided by the remaining runtime subsystems are not required by an application, the subsystem may be excluded from the application's executable image. The entire runtime system is stored in supervisor space of the i960MC. The runtime system routines execute in supervisor mode on the processor. 1.2. COMPILER ARCHITECTURE Viewed at a high level, the Tartan Ada compiler has a traditional architecture composed of the following components: - The Librarian manages the database representing the Ada program library. - The Front End performs the lexical, syntactic and static semantic analysis of the source program producing an abstract parse tree decorated with information required by the later compiler phases. - The Middle Pass determines run-time representations of both the declarative and imperative portions of the source code and generates an intermediate form used by the Code Generator. - The Optimizer performs many traditional compiler optimizations on the intermediate form and gathers information that allows the Code Generator to emit high quality object code. - The Code Generator produces the object code for the target computer system. 1.3. PROTECTED ARCHITECTURES There is no such thing as a typical architecture for an Ada application given the various domains in which Ada is used. Even in the embedded application domain, architectures are far from typical. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 1-2 The architecture of concern in this discussion is the protected architecture. A protected architecture restricts the user's application from directly accessing the supervisor, executive, or kernel. The limitation of the boundary between these memory regions is processor specific. The runtime portions of this document (see Chapters 2, 3, and 4) include some discussion on issues related to implementing some of the proposed Ada 9X features on protected architectures. This section is included to provide some definition and background information on such architectures. Two examples of embedded protected architectures that are targets of Ada systems are the 1750A extended mode architecture and the Intel i960MC processor. On the i960MC, the user can "see" into the supervisor space but may not "touch". On the 1750A (extended mode), a user may not "see" or "touch" the executive space. 1.3.1. Protected Architecture Definition 1.3.1.1. 1750A Extended Mode On the 1750A, the user cannot see into the protected region. This means that the user cannot touch any of the data structures or procedures which reside in this area. A user call to one of the routines which reside in the protected space is trapped at the boundary into the protected space. Special trap routines then map the call to the appropriate executive routine. This strict boundary between the protected space and the user space restricts the amount of data which may be shared between the two regions. There are mechanisms available whereby a user area can be mapped to coincide with a protected area. However, there is a limited amount of memory available on the processor. Each shared region consumes a page of memory from each side of the boundary, consuming all of the available memory in a very short amount of time. Additionally, this sharing must be specified prior to execution. +--------------+ |X| +--------------+ | | |X| | | | Supervisor | |X| | User | | Space | |X| | Space | | | |X| | | +--------------+ |X| +--------------+ FIGURE 1-1: 1750A Extended Memory Architecture 1.3.1.2. i960MC The i960MC processor provides a two-state protection model called the user-supervisor protection model. With this model, access to selected procedures and data structures can be restricted by means of page protection and mode switching between the two execution modes: user and supervisor. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 1-3 This protection model allows a system to be designed in which the runtime data structures and routines reside in the same address space as user code and data, but access to the runtime routines is only allowed through a supervisor procedure table. This forms a tightly controlled and protected interface. The user-supervisor protection model also allows runtime procedures to be executed using a different stack (the supervisor stack) than the one used to execute application program procedures. The ability to switch stacks helps maintain the integrity of the runtime system. When the processor is executing in supervisor mode, it has the following additional privileges: - It may access pages that have supervisor-only rights. A process cannot access these pages when executing in user mode. - It may use additional instructions which control process management and runtime functions. When using the user-supervisor mechanism, the processor maintains separate stacks in the address space, one for procedures executed in the user mode (local procedures) and another for procedures executed in the supervisor mode (runtime procedures). When in the user mode, the local procedure stack is used. When a supervisor call is made, the processor switches to the supervisor stack. It continues to use the supervisor stack until a return is made to the user mode. Unlike the 1750A, no trap routine is required to call a routine in supervisor mode. The i960MC provides a supervisor call instruction, CALLS, which switches the processor from user mode to supervisor mode and sets the return status field to indicate that a mode and stack change has occurred. +-------------------------------+ | || | | Supervisor || User | | Space || Space | | -------- | | | calls | | -------- | | || | +-------------------------------+ FIGURE 1-2: i960MC Architecture 1.4. ACVC TESTS For each of the Ada 9X features described in this report the Implementer Team prepared sample ACVC tests. These tests are presented in [10]. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 1-4 1.5. REFERENCE NOTATION Throughout this report we use the notation adopted by the Ada 9X Mapping Team for referencing the various versions of the Mapping Specification. The notation "MS-ss.ss(pp);v.v" refers to section number ss.ss, paragraph number pp, of version v.v of the Mapping Specification. References to the Reference Manual for the Ada Programming Language [5] will appear as "RM-ss.ss(pp)", where ss.ss is the section number and pp is the paragraph number. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 1-5 CHAPTER 2 PROTECTED TYPES AND REQUEUE 2.1. SCOPE There have been requests from the real-time user community for more support for common real-time paradigms within Ada. The protected type has been proposed for inclusion in Ada9X to provide a language construct which supports mutually exclusive access to shared data. It can be used to define critical regions or to implement common real time paradigms such as semaphores, mutexes, and more elaborate communication and synchronization mechanisms. The protected type is composed of protected operations (see Section 2.2) and data components. Data which is shared between multiple tasks may be declared as components of a protected type; and the protected operations of this type may define the operations available on the shared data. The objective of this report is to evaluate a prototype implementation of the protected type. This evaluation begins with a definition of some common terms used throughout the document. The list of protected type implementation requirements follows. These requirements are then incorporated into the discussion of the design and implementation of the protected type construct. These requirements are also referenced in Chapters 4 and 5. Issues associated with the target hardware architecture will be addressed when appropriate; often the final design of the implementation was the result of architectural requirements. The report concludes with some protected type performance data. This data is compared with similar data for tasks, and Tartan's special purpose runtime enhancement routines. 2.2. DEFINITIONS Several definitions aid in understanding the discussion of protected types: - A protected operation is a function, procedure, or entry declared in a protected type, or a task entry. - A protected action is a synchronized operation on a protected object. - A barrier expression is the conditional expression specified in a protected entry body after the reserved word when. - A TRUE barrier is a barrier expression that can be determined to be statically TRUE at compile time. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-1 - The protected type prologue is a sequence of statements that is executed prior to accessing a protected operation. - The protected type epilogue is a sequence of statements that is executed after the completion of a protected operation that (potentially) changes the state of the components of a protected type; e.g. a protected procedure or a protected entry. - The common epilogue is a sequence of statements that is executed at the completion of any protected operation. - A protected type specification without the reserved word type defines a singleton. - Each instance of a protected type will be associated with a single lock which will be used to control access to the protected operations and components. - Each instance of a protected type will be associated with a ceiling priority which will be used to control access to the protected operations and components. 2.3. REQUIREMENTS The implementation requirements for protected types and requeue were derived from a review of Implementation Module I [1], Implementation Module II [2], and the Mapping Specification [6, 7, 8]. If these documents did not define a requirement succinctly, electronic mail was sent to the Mapping Revision Team (MRT) for clarification. Responses to electronic inquiries were regarded as the final word when conflicting definitions were provided. The following is the list of protected type and requeue implementation requirements: Compile-Time Requirements - PR-1 A protected unit consists of a protected specification and a protected body. - PR-2 A protected specification that starts with the reserved words protected type declares a protected type. - PR-3 A protected specification without the reserved word type defines a single protected object. - PR-4 Each protected specification must have a corresponding protected body. - PR-5 Each protected operation must have a corresponding body. PAGE 2-2 TARTAN ADA 9X IMPLEMENTATION REPORT - PR-6 A protected type is a limited composite type. - PR-7 A protected object is an object whose type is a protected type. - PR-8 For all parameter modes, protected types are passed and returned by reference. - PR-9 Prior to the beginning of a protected action, the operation name and the actual parameters are evaluated. - PR-10 A function which returns an object of a protected type may only return, by reference, such an object if it is declared outside the function. - PR-11 The protected operation specifications which precede the reserved word private in the protected specification are the visible part of the protected specification. - PR-12 The protected operation specifications which succeed the reserved word private in the protected specification and the data components are the private part of the protected specification. - PR-13 The protected operations declared in the visible part of the protected specification may be named with selected component notation both inside and outside the protected unit. - PR-14 The discriminants of an object of a protected type may be named with selected component notation anywhere the object may be named. - PR-15 The non-discriminant data components of a protected type may only be named within the protected unit. - PR-16 Expressions appearing within pragmas and default expressions in a protected specification are reevaluated for each object of the protected type. - PR-17 The body of a protected unit may contain declarations for local subprograms. - PR-18 Within a protected type, the name of a protected operation is the protected operation's simple name. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-3 - PR-19 Every protected entry body must include an entry barrier. - PR-20 The entry barrier may not reference any formal parameters to the entry. - PR-21 The protected entry body is optional. - PR-22 Protected entry families are specified using the iterator syntax, for in , where the denotes the entry family. - PR-23 The object introduced to name the entry family index is treated like a formal parameter from a scope point of view, and may not have the same identifier as any other parameter, or other declaration which occurs immediately within the declarative region consisting of the entry specification and the declarative part of the entry body. - PR-24 The COUNT attribute is only available within the body of the protected unit. - PR-25 The parameter profile of a requeue entry must match the parameter profile of the entry issuing the requeue; or the requeue entry must be parameterless. - PR-26 A protected type declaration is treated like a task declaration with respect to where it may appear. - PR-27 The declaration of a task object within a protected subprogram is "incorrect" and should be detected at compile-time, because it implies suspension of the activator. Compile-Time and Runtime Requirements - PR-28 Protected functions have the protected type data components as implicit in parameters. - PR-29 Protected procedures and protected entries have the protected type data components as implicit in out parameters. - PR-30 It is a bounded error for a protected operation to directly or indirectly perform a potentially suspending operation; including an entry call, an accept, a select, a delay statement, task PAGE 2-4 TARTAN ADA 9X IMPLEMENTATION REPORT activation, task termination, task abortion, a call on a language-defined I/O package, or a call on an implementation- defined subprogram that is defined to potentially suspend the calling task. - PR-31 It is a bounded error for a protected operation on a protected object to call, directly or indirectly, a protected subprogram with a prefix identifying an object that is the same protected object. - PR-32 A conditional protected entry call will execute the else part if the protected entry barrier evaluates to FALSE; e.g. the calling task will not be queued on the protected entry. - PR-33 Parameters for entries will be passed in memory rather than in registers. - PR-34 Only procedures in library-level protected types may be associated with interrupts. - PR-35 A runtime (or compile-time) error, LOCK_ERROR, will result if a task requests a lock on a protected object when its active priority exceeds the ceiling priority of the protected object. - PR-36 A requeue within a protected entry body may only be to a protected entry (not a task entry). - PR-37 A requeue within an accept statement may be to a task or protected entry. Runtime Requirements - PR-38 Each instance of a protected type will be associated with a single lock. - PR-39 The caller of a protected entry will not proceed until the corresponding barrier expression evaluates to TRUE. - PR-40 When a protected entry barrier expression evaluates to TRUE, the protected entry body is performed under mutual exclusion. - PR-41 Protected procedures and protected entries of the same protected object are mutually exclusive with all other protected operations. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-5 - PR-42 Protected functions of the same protected object may proceed concurrently. - PR-43 A protected object is locked while executing one of its operations; possibly read-write locked for protected procedures and protected entries, and write locked for protected functions. - PR-44 The barrier expression is always evaluated under the protection of the lock. - PR-45 Protected operations are non-preemptable. - PR-46 Barrier evaluation is non-preemptable. - PR-47 The value of the COUNT attribute is updated when an entry call is removed from the entry queue or the call is selected. - PR-48 If any callers are queued at the completion of a protected procedure or a protected entry operation, the barrier conditions are reevaluated. If the barrier of an entry with a queued caller no longer evaluates to FALSE, one caller on such a queue is selected as the next protected operation to be performed on the protected object. If more than one caller is eligible, an implementation-defined rule is used to select among them. - PR-49 On the completion of the protected function epilogue, the protected object is unlocked. - PR-50 On the completion of the protected procedure or the protected entry epilogue (when there are no more non-empty queues or TRUE barriers), the protected object is unlocked. - PR-51 If an exception is raised while evaluating a barrier, PROGRAM_ERROR is propagated to all callers currently on any entry queue of the protected object. - PR-52 An exception which is raised while executing the body of a protected entry is propagated to the calling task (if a task is executing the entry body on the behalf of another task, the exception is delivered to the task on whose behalf the execution is taking place). - PR-53 Entry calls on protected entries are allowed in conditional and timed entry call constructs. PAGE 2-6 TARTAN ADA 9X IMPLEMENTATION REPORT - PR-54 A timed protected entry call will be placed on both the protected entry queue and the delay queue. - PR-55 All internal operations on protected data components should be performed under the protection of the associated lock. - PR-56 Removing a canceled protected entry caller from its queue is a protected operation. - PR-57 Upon completing the removal of a canceled caller, the entry queues whose barriers depend on the COUNT attribute are serviced. - PR-58 Calling a protected subprogram from another protected operation within the same protected object does not require additional synchronization, and upon return from the subprogram, the entries are not serviced. - PR-59 Calling a protected subprogram from a protected operation in a different protected object must be synchronized with other operations on the protected object. - PR-60 A requeue statement may be used to complete the execution of an entry body or accept statement, and at the same time commence a new entry call. - PR-61 If the target object of a requeue statement is identified implicitly as being the current task or protected object, the caller is simply added to that entry's queue. - PR-62 If the target object of a requeue statement is specified explicitly in the entry name, the requeue is handled like a normal entry call up until the point when the requeued call is complete or queued. - PR-63 Having queued or completed the requeued call, the entry body or accept statement containing the requeue statement is exited. - PR-64 If the requeue statement includes the reserved words with abort, abort is not deferred while the task is waiting on the new entry queue. - PR-65 The default ceiling priority of an instance of a protected type will be the maximum non-interrupt priority level. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-7 - PR-66 The active priority of the calling task is raised to the ceiling priority of the protected object only while the task holds the protected object's lock. - PR-67 A task which calls a protected entry with a FALSE barrier will be placed on the entry queue followed by the release of the protected object's lock with the task suspended. - PR-68 The default service order of callers on an entry queue is in order of arrival. - PR-69 Each queued call will be processed independently. - PR-70 When the entry body and corresponding epilogue code is completed, the calling task is resumed with appropriate information to check for exceptions, timeouts, aborts, etc. - PR-71 Each task whose entry call is completed during the execution of protected procedure or entry epilogue code is able to resume once the protected object is unlocked. - PR-72 Barriers which contain global data may be re-evaluated on the next change of the protected data components. 2.4. PROTECTED TYPE DESIGN AND IMPLEMENTATION Implementation Module I [1] provided the foundation for the implementation of the protected type feature. Several of the revisions to the protected type proposal were incorporated into the design. The runtime support for protected types was incorporated into the existing Tartan runtime system. To avoid possible corruption of the runtime system, the support for protected types was designed as a new runtime subsystem which interacts with the existing runtime subsystems (see Section 1.1). The protected type runtime subsystem facilitates most of the support for protected types and protected operations. The following sections describe the design of the runtime data structures and routines. 2.4.1. Data Structures Several runtime data structures are required to support the execution of programs containing protected types and protected objects. The following list is a summary of the new runtime data structures: PAGE 2-8 TARTAN ADA 9X IMPLEMENTATION REPORT PRTS - Protected Type Structure Describes a protected type or singleton. It contains the runtime specific information such as the ceiling priority, barrier function addresses, and protected entry addresses. PRD - Protected Data Record Contains the data fields of the protected object. PRCB - Protected Object Control Block Contains the runtime specific information as- sociated with an instance of a protected type. This includes the lock, protected entry queues, and scheduling information. When a protected type is encountered, a set of data structures must be constructed. These structures are used by the runtime system to implement the protected operations and to access the protected data. 2.4.1.1. Protected Type Structure - PRTS The compiler generates a protected type structure (PRTS) for each protected type or singleton. The runtime system uses this structure to determine the scheduling characteristics, interrupt mask, and the ceiling priority of the protected type. If the protected type includes protected entries, the PRTS will include an entry array. Each element in this array is a protected entry record. The address of the entry barrier function and the address of the entry body are the components of the protected entry record. The barrier address field will be null if the barrier is known to be statically TRUE at compile-time. An array element will be allocated for each protected entry within the protected type. Thus, the actual upper bound of this entry array is dependent on the number of entries in the protected type declaration. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-9 The Ada declarations for the PRTS and its component types are presented in Figure 2-1. The type PR_Type_Rec is a pointer to a PRTS structure. type PR_Entry_Record is record Barrier_Address : System.Address; Operation_Address : System.Address; end record; -- PR_Entry_Record type PR_Entry_Array is array(1..Arbitrary_Upper_Bound) of PR_Entry_Record; type PR_Type_Rec_Block is record Ceiling : Target_Priorities; IMask : Interrupt_Mask; Entries : PR_Entry_Array; end record; -- PR_Type_Rec_Block type PR_Type_Rec is access PR_Type_Rec_Block; FIGURE 2-1: Protected Type Data Structure (PRTS) When a protected type or a singleton is elaborated, the PRTS is constructed. It may be statically constructed if there are no discriminants on the type which affect the number of entry families. 2.4.1.2. Protected Data Components - PRD The compiler will generate a protected data record (PRD) when a protected object is elaborated. The PRD is statically allocated for protected objects that are declared globally, it is allocated on the stack for locally declared objects, and it is allocated from the heap for an access protected object. The PRD will contain a pointer to its corresponding protected object control block (see Section 2.4.1.3). The remainder of the PRD contains the discriminant information and the data components defined in the specification of the protected type or singleton. Figure 2-2 presents the general template for a PRD. type PR_Data is record PR_CB_Ptr : PR_CB; <> <> <> end record; -- PR_Data type PR_Data_Ptr is access PR_Data; FIGURE 2-2: Protected Data Record (PRD) PAGE 2-10 TARTAN ADA 9X IMPLEMENTATION REPORT 2.4.1.3. Protected Object Control Block - PRCB When a protected object or singleton is elaborated, a protected object control block (PRCB) is constructed by the compiler. On protected architectures, such as the i960MC, the runtime system and associated data structures are maintained in the protected region of memory. Since the PRCB contains fields that are accessed by the runtime system, it is always allocated from the runtime system heap. Figure 2-3 contains the Ada specification of the PRCB. The Lock field is used to ensure that only one task can gain control of the protected object. This field is required in multiprocessor implementations; uniprocessor implementations using priorities do not require the lock. The Lock_Owner field is used to keep a record of the task which is actually executing. The Current_Thread is the task which should be executing; during the epilogue, this field will be the task on whose behalf the Lock_Owner task is executing. One use of this field is to post exceptions raised during execution to the correct task. The Previous_Priority field is a linked list of priorities. This field is needed to maintain task priority during requeue operations. The Type_Desc field points to the corresponding PRTS. This field is used to access the entry barrier functions and the entry bodies. Given the intended use of the protected type, it is believed that there will be few callers waiting in protected entry queues. Hence, a single queue of callers is maintained as opposed to a queue per entry. The Total_Callers field records the total number of callers currently enqueued on any queue of the protected object. The Caller_Queue field maintains the list of callers blocked on the entries of this protected record. The default organization of this queue is FIFO (First-In First-Out). Both of these fields are accessed as part of the protected procedure or protected entry epilogue. The PRCB maintains the number of callers on each entry queue in the Entry_Queue(N).Queue_Count field. The mapping of family indexes to actual entry body indexes is maintained in the Entry_Queue(N).Operation_Index field. The Operation_Index is used along with the Type_Desc to find the barrier function and entry body address which are stored in the PRTS. The Data_Address field contains a pointer to the PRD. This address is passed to barrier functions and entry bodies. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-11 If the PRCB is associated with an access protected type object, it will be linked through its Access_Chain field. When the access type passes out of scope, the corresponding list of PRCBs will be deallocated. type Protected_Object_Control_Block; type PR_CB is access Protected_Object_Control_Block; type Entry_Record is record Queue_Count : Natural; Operation_Index : Natural; end record; -- Entry_Record type Queue_Array is array (1..Arbitrary_Upper_Bound) of Entry_Record; type Protected_Object_Control_Block is record Lock : Integer; Lock_Owner : Client_Support.TCB; Current_Thread : Client_Support.TCB; Previous_Priority : Client_Support.TCB_Priority; Type_Desc : PR_Type_Rec; Data_Address : PR_Data_Ptr; Total_Callers : Natural; Caller_Queue : Client_Support.TCB; Entry_Queues : Queue_Array; Access_Chain : PR_CB; end record; -- Protected_Object_Control_Block FIGURE 2-3: Protected Object Control Block (PRCB) The abortability of a task accessing a protected object is stored in the task's TCB since this is a characteristic of the task not the protected object. Similarly, data relevant to asynchronous transfers of control is also part of the task's TCB. 2.4.2. Algorithms The general requirements for initiating a protected operation and accessing protected data are that the protected object must be acquired before any protected actions may occur. The sections that follow describe the algorithms used to synchronize access to a protected object. PAGE 2-12 TARTAN ADA 9X IMPLEMENTATION REPORT 2.4.2.1. Creating a Protected Object During the elaboration of a protected type, the compiler constructs the PRTS (see Section 2.4.1.1) for the type. For example, the elaboration of the type User_PR in Figure 2-4 will result in the code in Figure 2-5 being generated by the runtime system. protected type User_PR is pragma Interrupt_Priority(20); procedure P1; procedure P2; function F1 return Some_Type_A; entry E1(A : Some_Type_A); entry E2; private entry E3(1..4); -- an entry family entry E4(A : Some_Type_A); record Item_1 : Some_Type_A := Some_Type_A'FIRST; Item_2 : Some_Type_B := Some_Type_B'FIRST; Item_3 : Some_Type_C := Some_Type_C'FIRST; end User_PR; protected body User_PR is procedure P1 is ...; procedure P2 is ...; function F1 return Some_Type_A is ... entry E1(A : Some_Type_A) when TRUE is ... entry E2 when Item_2 >= Some_Type_B'FIRST ... entry E3(for F in 1..4) when Item_1 /= Some_Type_A'FIRST is ... entry E4(A : Some_Type_A) when Item_3 = Some_Type_C'FIRST is ... end User_PR; FIGURE 2-4: User Defined Protected Type Example Code TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-13 Notice that the runtime system does not take any noticeable action for the private entries. The restricted access to the private entries is handled by the compiler. -- -- The barrier conditions for entries E2, E3, and E4 have been -- converted into boolean functions named B2, B3, and B4. -- type PR_Entry_Array is array (1..3) of PR_Entry_Record; type PR_Type_Rec_Block is record Ceiling : Client_Support.TCB_Priority; Entries : PR_Entry_Array; end record; User_PR_Type_Info : constant PR_Type_Rec_Block ( Ceiling => System.Interrupt_Priority'(20), Entries => ( 1 => ( Barrier_Address => null, Operation_Address => E1'ADDRESS), 2 => ( Barrier_Address => B2'ADDRESS, Operation_Address => E2'ADDRESS), 3 => ( Barrier_Address => B3'ADDRESS, Operation_Address => E3'ADDRESS), 4 => ( Barrier_Address => B4'ADDRESS, Operation_Address => E4'ADDRESS))); FIGURE 2-5: Protected Type Elaboration Code When the compiler is elaborating a declaration of a protected object it will construct a PRD (see Section 2.4.1.2) for the object on the user stack. As part of this process, the compiler will generate a call to a runtime system routine to construct the PRCB (see Section 2.4.1.3) for the object. The parameters to this runtime routine will include a pointer to the PRTS, the number of protected entries, and a pointer to the PRD. The runtime system will construct the PRCB and return a pointer to this structure. The compiler will insert this pointer into the PRD to be used in all runtime calls associated with this protected object. PAGE 2-14 TARTAN ADA 9X IMPLEMENTATION REPORT Figure 2-6 shows these structures for the elaboration of an object of type User_PR. -- For the user declaration: User_PR_Object : User_PR; -- The following data structures are created: type PR_Data is record PR_CB_Ptr : PR_CB; <> Item_1 : Some_Type_A; Item_2 : Some_Type_B; Item_3 : Some_Type_C; end record; User_PR_Object : PR_Data := ( PR_CB_Ptr => null, <> Item_1 => Some_Type_A'FIRST, Item_2 => Some_Type_B'FIRST, Item_3 => Some_Type_C'FIRST); FIGURE 2-6: Protected Object Elaboration Code When the compiler is elaborating a declaration of a protected access type, an access collection must be allocated for the protected data. The compiler will create a variable to keep a list of all of the instances of this type. This variable will be passed to the runtime system as part of the call to construct the PRCB when an access object of this type is elaborated. The value will be stored in the Access_Chain field of the PRCB. The PRD for the access object will be allocated from the access collection in the user heap. 2.4.2.2. Finalizing a Protected Object When protected objects which are not access objects passed out of scope, the runtime system is called to deallocate the runtime data structures for the protected object. When a protected access type passes out of scope, the runtime system will be called to deallocate the runtime data structures associated with any corresponding access objects. 2.4.2.3. Protected Prologue The protected prologue is a set of actions which must occur prior to the execution of a protected operation. In particular, the protected operation must be protected from preemption during execution. On the i960MC this functionality is part of the processor. When the priority of a task is altered the change in priority is reflected in the priority at which that process executes on the processor. Hence, when the priority of a task calling a protected operation is raised to the ceiling priority of the protected object, the protected operation will TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-15 be executed at the ceiling priority of the protected object. The processor will block all equal and lower priority tasks from executing while the protected operation is executing. 2.4.2.3.1. Protected Functions and Procedures A protected function call or a protected procedure call is executed in user space. Prior to the execution of this call, the runtime system is called with the address of the protected object as a parameter to execute the prologue for the protected object. The prologue compares the priority of the calling task with the ceiling priority of the protected object. If the calling task has a priority which is greater than the protected object, PROGRAM_ERROR is raised. Otherwise, the task's old priority is saved and its active priority is set to the ceiling priority of the protected object. If necessary, the scheduling characteristics of the processor are adjusted to prevent interrupts from equal or lower priority events. If necessary, the task will contend for the protected object lock. Once the protected object has been acquired and the calling task's priority has been adjusted, the no-suspend level in the task's TCB is incremented to indicate no suspending operations may be executed. Then the runtime system returns to the call on the protected procedure or function. 2.4.2.3.2. Protected Entries Protected entries bodies are executed in the executive space. When a protected entry call is executed, the runtime system is called with the address of the protected object, the entry number, the entry family index, and the address of the entry parameter block. The runtime system will execute the protected entry prologue, entry body, and entry epilogue code. At the completion of the protected epilogue, control returns to user space. As with procedures and functions, the protected entry prologue must acquire the protected object in order to execute the entry. After adjusting the calling task's priority and no-suspend level, the entry prologue passes control to the entry barrier evaluation. 2.4.2.4. Protected Entry Barriers and Bodies The evaluation of the entry barrier follows the protected entry prologue without returning to the user space. The runtime system passes two parameters to the barrier function: the address of the PRD and the queue index for the entry or entry family. For entry families, the barrier function will map the queue index onto the appropriate family member. If an exception is raised during the evaluation of the barrier function, the exception PROGRAM_ERROR will be recorded as pending in the task's TCB and control will be passed to the entry epilogue. If the barrier function returns FALSE, the task is placed on the PAGE 2-16 TARTAN ADA 9X IMPLEMENTATION REPORT protected object entry queue, the fields of the PRTS are updated, and the entry epilogue is executed. If the barrier function returns TRUE, the TCB of the calling task is examined to determine if the entry call is the triggering event for an asynchronous transfer of control. If so, the sequence of statements in the abortable part is marked as aborted. Then the entry body is executed. Every entry body is enclosed in a runtime procedure with three parameters: the address of the protected data, a pointer to the entry's formal parameters, and a queue index for the entry or entry family. For entry families, the entry body routine will map the queue index onto the appropriate family member. 2.4.2.5. Protected Procedure and Protected Entry Epilogue The components of a protected object may be changed as the result of the execution of a protected procedure or protected entry body. At the completion of these operations, if there are any tasks waiting on entries of the protected object whose barrier condition is now TRUE, these tasks must be dequeued and the corresponding entry body executed. This is the function of the protected procedure and protected entry epilogue. The queue of tasks waiting on entries in the protected object is traversed in search of a task to execute. The barrier for each waiting task is evaluated until a barrier evaluates to true or a barrier evaluation raises an exception. If the barrier raises an exception, the waiting task is dequeued and the exception PROGRAM_ERROR is posted in its TCB. The dequeued task is then resumed. The recent changes to the mapping specification will require that the entire list of waiting tasks be traversed, dequeuing each task, posting the exception PROGRAM_ERROR in its TCB, then resuming the task. If the barrier evaluates to TRUE, the waiting task is dequeued, and the entry body is executed on its behalf. Upon completion of the execution of the entry body, the task that was dequeued is resumed. If an exception was raised during the execution of the entry body, the exception is posted in the TCB of the dequeued task prior to resuming it. The controlling task returns to the head of the waiting queue list and begins the search for a task waiting on an entry with a TRUE barrier. When the waiting task queue is empty or the barriers of all waiting tasks evaluate to FALSE, control is passed to the common epilogue. 2.4.2.6. Common Epilogue This phase of the processing of a protected operation releases the protected object and resets the priority of the task and the scheduling characteristics. If a lock was needed to implement the protected object, it is released at this time. The original scheduling mode of the processor is reset. The active priority of the task is restored. If the calling task has a pending exception, it TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-17 will propagate the exception to the user code. If the calling task is still queued on an entry of the protected object, it will block at this time. 2.4.2.7. The COUNT Attribute The COUNT attribute is implemented by a runtime function. The COUNT attribute function interface includes a pointer to the protected object and the entry number corresponding to the entry for which the COUNT attribute applies. The entry number is used as an index into the protected object's PRTS.Entry_Queues array. The function returns the queue count. 2.4.3. Requeue A requeue operation may be used to complete the execution of a protected entry or a task entry. The current implementation only supports a requeue from a protected entry to another protected entry. The support for requeue from a task entry to another task entry or to a protected entry remains to be done. Completing a protected entry with a requeue may pass control to another protected entry within the same protected object, or to a protected entry in a different protected object. The implementation of these two cases is different. 2.4.3.1. Requeue to Self The implementation of a requeue to the same protected entry is trivial. The entry queue information stored in the protected object's PRCB is updated to include a new task in the entry queue for the appropriate entry. The task's TCB is modified to record the entry which is the target of the requeue. After these data structures have been updated, control is passed to the entry epilogue where the task may be dequeued if the target entry's barrier evaluates to TRUE. 2.4.3.2. Requeue to Other A requeue to a different protected object's entry is the same as a nested entry call to the new protected object. The new object's prologue must be executed. Then the appropriate entry barrier is evaluated and the entry body is either executed or the task is enqueued. Finally the new object's epilogue code is executed and control returns to the protected object that issued the requeue. This object then proceeds with its epilogue code. After all protected epilogue code has been completed, control will return to the user code. 2.4.4. Integration with the RTS and Ada 83 The protected type support and the requeue operation for protected objects have been implemented as a separate runtime subsystem. The integration of this subsystem with the Ada 83 compilation system has PAGE 2-18 TARTAN ADA 9X IMPLEMENTATION REPORT been through a set of well defined subroutine interfaces. The integration with the existing runtime system has been through runtime data structures and routines. The implementation of the requeue operation for tasks will require more interaction between the tasking subsystem and the protected type subsystem. There may come a time when these two subsystems are merged. The requeue with abort operation has not been implemented. This construct requires modifications to the timer code, the conditional entry code, along with the changes to the TCB and the state of the TCB. 2.5. PERFORMANCE The protected type is designed to improve the performance of synchronized access to shared data. Preliminary tests have shown a significant improvement over Ada tasking in this area. To evaluate the performance of protected objects, several PIWG tasking tests were modified to replace a task entry call with a protected entry call. The results of these tests are given in Table 2-1.Note a TRUE barrier was used in all of the protected entry calls in these tests. ---------------------------------------------------- | Test Name | Task | Protected Object | CPU Savings| |-----------|------|------------------|------------| | T000001 | 1.0 | 1.0 | 65.1% | |-----------|------|------------------|------------| | T000002 | 0.99 | 0.96 | 66.3% | |-----------|------|------------------|------------| | T000003 | 1.02 | 1.01 | 65.5% | |-----------|------|------------------|------------| | T000004 | 1.34 | 1.01 | 73.7% | |-----------|------|------------------|------------| | T000005 | 1.01 | 0.96 | 66.5% | ---------------------------------------------------- Table 2.1 PIWG Task vs Protected Object Entry Call Results The User portion of this report (see Implementation Report Part 2) contains a summary of these preliminary results. 2.6. ARCHITECTURAL ISSUES Several issues related to the protected architecture of the i960MC needed to be resolved during the design and implementation of the protected type and requeue operation. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-19 2.6.1. Task Stack Each task in the system is allocated a task control block during its lifetime. In addition, the task has a stack that it uses during execution. The user may specify at link time how much task space is to be allocated to tasks in a given application. This method of task stack allocation uncovered an interesting behavior when protected objects containing entries with queued waiters were encountered. Very simple tasks began to exceed their stack space quota. The problem was that this task was executing the epilogue of a protected object where it was executing entry bodies on the behalf of enqueued tasks. The obvious solution to this problem was to recommend to the user to increase their task stack space when using protected objects. 2.6.2. Protected Region The runtime system is stored in the protected region of the i960MC. Some components of the protected type runtime support data structures are stored in this region as part of the protected type runtime subsystem. As a result of this design, there is some additional performance overhead associated with calling runtime routines and modifying runtime data structures. The call into the runtime system requires a change of stack from the user stack to the supervisor stack, as well as a change of the heap, from the user heap to the runtime heap. The user memory is visible and accessible from the runtime system as long as the processor is not idle. The return to the user's code requires returning to the user stack and heap. The performance costs on architectures where the runtime system coexists with the user code should be less than that of the protected architectures. A call into the runtime system is still required to execute system level functions, such as masking interrupts, which are more costly than simple procedure calls. 2.6.3. Low-Level Locks In a single processor 960 system, the scheduling semantics and non-preemption are sufficient to ensure the safety of the protected operations. However, in a multi-processor system a hardware lock will be required. To remain upward compatible with the multi-processor system, each protected object is associated with a lock on which each processor may contend. Each task on a separate processor that is attempting to acquire the lock will spin in a set and test loop until it gains control of the lock. 2.7. OPTIMIZATIONS The implementation described was developed as a prototype. When the final product version of the protected type is implemented it will include optimizations to improve the overall performance of the construct. A few of the possible optimizations are described in this section. PAGE 2-20 TARTAN ADA 9X IMPLEMENTATION REPORT 2.7.1. Procedure Optimizations If a protected procedure does not affect any data used in any of the barrier functions within the protected record object, the protected procedure call may be optimized to use the protected function protocol. Similarly, the calls to protected procedures which are components of a protected record object, in which no protected entries are declared, may be optimized to use the protected function protocol. 2.7.2. Barrier Optimizations Considerations were given to using a bit vector to represent the elements of the protected record which were used in barrier expressions. Then this vector could be examined in the protected procedure and entry epilogue to determine if any of the barriers need to be re-evaluated. The initial view of this optimization was that it would be more trouble than it is worth. Particularly if a protected record object contains few entries and there are few callers waiting in an entry queue. More analysis is needed to determine the true value of this type of optimization. A protected entry call to an entry with a TRUE barrier may be optimized to a procedure call with finalization. A queue for this entry must be maintained to allow for requeue operations from within the protected record object. 2.8. CONCLUSIONS AND RECOMMENDATIONS Using a hardware lock and the set-and-test instruction impedes the implementation of both read-write locks and read-only locks. Hence, the current implementation does not permit multiple functions to access the protected object simultaneously. The support needed to implement the complete semantics of requeue with abort affects a large portion of the tasking runtime subsystem. The net result may be to replace the mature tasking subsystem and the protected subsystem with a new subsystem that supports both. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 2-21 CHAPTER 3 ASYNCHRONOUS TRANSFER OF CONTROL 3.1. INTRODUCTION One of the tasks that Tartan is responsible for in the U/I demonstration program is the design of an implementation of the multi-way select statement and the asynchronous transfer of control structure. There are at least two approaches which can be taken to implement the asynchronous transfer of control construct and the multi-way select statement in Ada 9X. The first method will require a significant change to the runtime system. The second method has a high overhead associated with it which may not be worth the cost. The first method involves a redesign of the queue structures which are to be used to keep track of tasks waiting for a delay to expire or an entry to be accepted. The idea here is that a linked list will be maintained in the task's control block (TCB) which points to all of the queues on which the task is waiting. When one of the events which dequeues the task occurs, the runtime will be responsible for removing the task from all other queues in which it is currently waiting. In addition, the runtime must mark the TCB for the task as currently executing in rendezvous with the acceptor or move the TCB to the appropriate ready queue (dispatch port) if a delay has expired. Simultaneously the runtime must abort the execution sequence of the then abort part of the asynchronous transfer of control. The alternative method is to have the task that is executing the asynchronous transfer of control or multi-way entry call to spawn child processes to wait on the appropriate queues. When any one of these tasks becomes executable, this child task must abort its siblings. It must then inform its parent that the parent is to stop what it is doing and join the child. When the parent joins the child, the child is aborted and the parent begins executing where the child was ready to begin. Our initial approach was to minimize the changes to our existing runtime system. We began to work out a solution using child processes. This led to a complex and awkward design. We decided to begin again with the new guideline that any component of the runtime system may be dramatically changed or redesigned to support these features. The result has been a complete redesign of the tasking and protected record subsystems of the runtime system. 3.2. DESIGN CONSTRAINTS As we were working through the design, several issues were uncovered which constrained the design and implementation. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 3-1 3.2.1. Queue Algorithms and Elements The first change occurred in the type of elements in the delay queue or entry queues. As we were working through the design using agent tasks we realized that runtime queues were now composed of heterogeneous elements. This is a result of the multi-way select statement, were a task may be waiting on several queues simultaneously. The management of queues with heterogeneous elements motivated us to reexamine our choice of using agent tasks. We decided to revise our approach. We converted our designs to use queue elements for all queuing within the runtime system. Hence, all of our queuing algorithms had to be modified to work with queue elements instead of task control blocks. Next, we investigated the effect of this decision on queue element storage management. On the target processors that have protected memory, the runtime system and its corresponding data structures are kept in the protected region. The entry queues, delay queues, queue elements and select headers are runtime data structures. These structures must be allocated and deallocated from the runtime storage area. In particular, the runtime system will allocate and deallocate queue elements as needed. This means that the runtime system will be responsible for the storage management of queue elements. The exception STORAGE_ERROR will be raised when the runtime system does not have sufficient resources to allocate a queue element. This introduces an interesting timing issue. Suppose that the queue elements used are initially allocated from the runtime heap. However, when these queue elements are deallocated they are put into a queue element pool instead of being returned to the heap. This means that the first allocations will come from the heap, but later allocations will come from the queue element pool. The result is different timing behaviors based upon when the queue element allocation occurs. Now, one may suggest that the queue element pool be allocated at system start-up time. The problem here is two fold: - a) if tasking and protected records are never used then there is no need to allocate the queue element pool; - b) it may be difficult to know at system start-up time how large the queue element pool needs to be. This may lead to the need for heap allocation sometime later in the program execution. The compilation time allocation of queue elements and similar structures introduces a different interesting issue. The user may specify how much stack space should be allocated for each task in the system. The user must now allow for these data structures to be allocated from the task stack. In addition, runtime routines will be needed to initialize these structures. PAGE 3-2 TARTAN ADA 9X IMPLEMENTATION REPORT Similar storage management issues exist for task control blocks, protected record control blocks, and select headers. A task control block pool is allocated statically at link time. A protected record control block pool and a select header pool are created dynamically similar to the method used for queue elements. 3.2.2. Multi-Way Select Statement The next step was to evaluate the various issues associated with implementing the multi-way select statement. These include select alternative guard evaluation, task entry call support, else-part resolution, and asynchronous transfer of control support. To determine which model to use with respect to the evaluation of select alternative guards, parameters, and expressions, we decided to keep as much of the existing runtime structure as possible. Hence, first we evaluate all of the alternative guards, constructing a list of those that are open (TRUE). This open list will be used when sequencing through the alternatives looking for a call that is immediately accepted. Since an entry alternative in a multi-way select statement can be a task entry call or a protected entry call, the existing code for task entry calls must be modified to check for calls that are associated with a multi-way select statement. This means that prior to a rendezvous the accepting task must determine if the call has been generated from a multi-way select statement. If so, the appropriate actions must be taken including: checking the select header to determine if this is the first entry call to be accepted; adjusting the select header when necessary to indicate that one of the select alternatives has been selected; canceling all other pending entry calls including protected entry dequeuing; initiating the abortion of the abortable final part when appropriate. Similarly, the protected entry code must include the multi-way select statement test and associated clean-up activities. Note that these tests will be part of the rendezvous and protected entry code regardless of whether the multi-way select statement is actually used. The addition of the else-part generates more design decisions. A major issue here is whether or not the queue element associated with a pending entry call is actually placed into the corresponding entry queue. If none of the entry calls can execute immediately, the else part is to be executed. By eliminating the entry queuing operation when there is an else-part, the else-part can begin execution without any dequeuing. If this model is chosen, the interface to the entry call code will include a flag that indicates whether this call is a branch in a select statement containing an else-part. The protected entry call code will then check this flag whenever the barrier evaluates to false to determine if the caller should be enqueued. Similarly, the task entry call will need to check this flag if the called task is not ready to accept the call. Note that these tests will become part of the entry call code regardless of whether the user ever uses a multi-way select statement. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 3-3 The alternative is to queue each entry call and then select the else-part. In this case, each pending entry call must be canceled prior to the execution of the else-part. The queue elements must be removed from the corresponding entry queue. Each dequeue from a protected entry queue is a protected operation, hence the protected record lock must be obtained (if one is used), the queue element dequeued, and some form of epilogue code must be executed prior to releasing the lock. This procedure must occur for each pending entry call prior to starting the execution of the else part. We believe that our users will be more willing to pay the price associated with not queuing an entry call when an else part exists. So, this is the mechanism that we will use. 3.2.3. Asynchronous Transfer of Control The primary issues here are determining where, when and what checks for abortion are needed. Additionally, what internal support is needed to make these checks. The task control block will be modified to include a field that indicates whether the task is suspendable and/or abortable, a field that contains the number of nested abortable regions (then-abort parts) that the task encounters, and a field to indicate the level to which an abort is effective. This information will be used to manage the abortion of either a sequence of statements or a complete task. The select header for each multi-way select statement will also need to include a field for the nested abortable regions. The prologue and epilogue code for all protected operations will need to include support for asynchronous transfer of control and deferring abortion. The prologue will modify the TCB's suspendable/abortable field to indicate that a new protected region has been entered. The epilogue code will need to modify the TCB's suspendable/abortable field to indicate that a protected region has been exited. Additionally, the epilogue code will need to examine this field to determine if any deferred abortion can be serviced. If so, further action needs to be taken to determine if any deferred aborts need to be handled. The epilogue will initiate abortion including self-abortion. The suspendable/abortable field will also be modified when a task executes an accept statement and when a task enters and exits its finalization code. These checks will be done even if an asynchronous transfer of control statement is not used throughout the entire system. They are required to support the requeue with abort structure as well as the asynchronous transfer of control structure. When the execution of a task enters an abortable region it updates the nested abortable region field in the TCB and in the appropriate select header. Execution continues until one of the select-alternatives PAGE 3-4 TARTAN ADA 9X IMPLEMENTATION REPORT initiates the abortion of this sequence of statements or the sequence of statements completes. In the later case, all of the pending calls associated with the multi-way select must be canceled including delays. This includes dequeuing and deallocating all of the queue elements. Additionally, the select header will be deallocated. The TCB nested abortable region field will be adjusted to indicate that an abortable region has been exited. Some concern has also been raised about the impact of asynchronous transfer of control on the code generated by the compiler. In Ada 83, it is the case that a task context is left asynchronously either to be resumed (e.g., time-sliced scheduling) or never to be returned to (abort). With asynchronous transfer of control, code generation must be resilient to an asynchronous transfer of control within the same task context at any time. This means that the code generation protocol must not contain situations where an asynchronous transfer of control can corrupt the task context. Otherwise, the code generation protocol will disable asynchronous transfer of control for the duration of any temporary inconsistency. An example would be a temporarily incorrect stack pointer that is set to a correct value shortly thereafter (this is an implementation alternative to handle unconstrained function results). Another would be a temporary use of task-wide heap storage to be deallocated soon after its allocation. There is a fairly heavy cost associated with ascertaining that the code generation protocol does not contain any such situations, and, if it does, to eliminate them. 3.2.4. Delay Expiration The Ada 83 support for delay expiration only needs to be concerned with whether the delay has expired for a task that is executing a timed-entry call. With the introduction of the multi-way select statement and the asynchronous transfer of control construct, the complexity of the support for delay expiration increases. A check must be made to determine if the delay has expired for a task that is executing a multi-way select statement. Does the multi-way select have an asynchronous part, and if so, can that part be terminated at this time? 3.3. COST OF IMPLEMENTATION The Ada 9X proposals for asynchronous transfer of control and the multi-way select statement introduce two new and complex features to Ada. A major concern regarding these new capabilities is the cost incurred by the implementer to support the feature. Another is the overhead a user will experience regardless of whether either of the proposed constructs are actually used. This section enumerates several contributors to the cost (implementer cost, user cost or both). TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 3-5 3.3.1. Runtime System Maturity A large amount of time and effort has been expended developing a runtime system that provides the necessary services efficiently. For example, one of the features of the current Tartan runtime system is a rendezvous accelerator. Under certain conditions, the time to execute a rendezvous can be reduced to one third. With the proposed changes to the runtime system, features like the rendezvous accelerator must be redesigned. Until the necessary tuning of the 9X runtime is done, the state of the tasking subsystem will be similar to the 1983 version with addition of the protected record support system. 3.3.2. Distributed Overhead For every 9X feature that is incorporated into the runtime system, there are several additional tests that need to be made in the protected operation prologue and/or epilogue code and in several of the tasking operations. One or two little tests may be acceptable to some of our users, however, the number of tests introduced is not small and is not isolated to the introduced features. 3.3.3. Non-Deterministic Time The selection of an accept alternative or an else part may require the cancellation of other entry calls. If it is a protected entry call, the corresponding queue element is to be removed from the protected entry queue. This is a protected operation and has protected epilogue associated with it. This may result in the dequeuing of all of the waiting callers, the number of these may be non-deterministic. 3.3.4. Non-Deterministic Space The nesting of multi-way select statements together with the dynamic behavior of the entry calls leads to non-deterministic space requirements. 3.3.5. Compilation Costs The asynchronous transfer of control feature introduces complexity and cost in generating code. Code generation must be resilient to an asynchronous transfer of control within the same task context at any time. This means that the code generation protocol must not contain situations where an asynchronous transfer of control can corrupt the task context. Otherwise, it will disable asynchronous transfer of control for the duration of any temporary inconsistency. There is a fairly heavy cost associated with ascertaining that the code generation protocol does not contain any such situations, and, if it does, to eliminate them. PAGE 3-6 TARTAN ADA 9X IMPLEMENTATION REPORT 3.3.6. Hard Real-Time versus Soft Real-Time The overhead associated with the structures examined here may be acceptable to a large portion of the soft real-time community. This group may be willing to pay the time and space costs for these expressive and portable solutions. However, the hard real-time community will not be in favor of the costs associated with these structures. Hence, these features will not be used and the current special purpose capabilities provided by various vendors will continue to be used. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 3-7 CHAPTER 4 INTERRUPTS 4.1. SCOPE The protected procedure has replaced the task entry as the language defined mechanism for interrupt handlers. To maintain upward compatibility, task entry interrupt handlers are still legal. However, the recommended mechanism for interrupt handlers is the protected procedure. This chapter presents the design and implementation of a prototype of this feature. The contents of the proposal for this feature were changing throughout the development of this prototype. The end result is an implementation that is nearly compliant with the current version of the proposal. 4.2. DEFINITIONS Several definitions aid in understanding the discussion of protected procedures as interrupt handlers. - An interrupt represents a class of events that is detected by the hardware or system software. - The generation of the occurrence of an interrupt is an event in the underlying hardware or system. - The delivery of the occurrence of an interrupt is the event that initiates the execution of the interrupt handler procedure. - Between generation and delivery, the interrupt occurrence is pending. - When an interrupt is blocked, all occurrences are prevented from being delivered. - A particular attachment of a handler to an interrupt is called an interrupt handler binding. - An interrupt is reserved if it is one of an implementation- defined set of interrupts for which user-defined handlers are not supported, or if the interrupt is currently attached to a task entry by means of an address clause. 4.3. REQUIREMENTS The implementation requirements for interrupts were derived from a review of Implementation Module II [2] and the Mapping Specification [6, 7, 8]. If these documents did not define a requirement succinctly, electronic mail was sent to the Mapping Revision Team (MRT) for clarification. Responses to electronic inquiries were TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 4-1 regarded as the final word when conflicting definitions were provided. The following is the list of interrupt handler implementation requirements: - IH-1 Interrupts may be attached to parameterless procedures of library-level protected procedures. - IH-2 While a binding is in force, the handler is invoked once for each delivered occurrence of the interrupt. - IH-3 The handler that is executed for the delivery of an interrupt is the most recent binding for that interrupt at the time the interrupt is delivered. - IH-4 Multiple interrupts may be attached to the same handler. - IH-5 In a system that supports priorities, the dispatching of an interrupt handler is as if it were called by a task whose base priority is the hardware priority of the interrupt. - IH-6 Assignment and equality operations must be available for the INTERRUPT_ID type. - IH-7 The ATTACH_HANDLER operation installs the specified protected procedure as the handler for the specified interrupt. - IH-8 An interrupt attached to a protected procedure is blocked during the execution of any protected operation on that protected object. - IH-9 If a protected procedure is already attached to an interrupt when an attach operation is called on that interrupt, the previously attached procedure is first detached. - IH-10 In a system that supports priorities, PROGRAM_ERROR is raised if the ceiling of the protected object is lower than the priority of the interrupt. - IH-11 If the ATTACH_HANDLER operation is called with a null handler, the exception CONSTRAINT_ERROR is raised. - IH-12 If the ATTACH_HANDLER operation attempts to attach a protected procedure handler to a reserved interrupt, the exception RESERVED_INTERRUPT is raised. PAGE 4-2 TARTAN ADA 9X IMPLEMENTATION REPORT - IH-13 The DETACH_HANDLER operation restores the default treatment for the specified interrupt. - IH-14 If the DETACH_HANDLER operation attempts to detach a handler from a reserved interrupt, the exception RESERVED_INTERRUPT is raised. - IH-15 The IS_RESERVED operation returns TRUE if and only if the specified interrupt is reserved. - IH-16 The IS_ATTACHED operation returns TRUE if and only if there is an application interrupt handler binding in effect for the specified interrupt. - IH-17 If the interrupt specified in the IS_ATTACHED operation is reserved, the exception RESERVED_INTERRUPT is raised. - IH-18 The CURRENT_HANDLER operation returns a value that designates the currently attached handler procedure for the specified interrupt. - IH-19 The CURRENT_HANDLER operation returns null if there is no user-defined handler binding in effect. - IH-20 If the interrupt specified in the CURRENT_HANDLER operation is reserved, the exception RESERVED_INTERRUPT is raised. - IH-21 The handler specified in the ATTACH_HANDLER pragma is attached as part of the elaboration of the protected object. - IH-22 The handler specified in the ATTACH_HANDLER pragma is detached as part of the protected object's finalization on exit from its scope. - IH-23 If the system supports priority locking of protected objects, a check is made during elaboration of the protected object to insure that the ceiling priority of the protected object is in INTERRUPT_PRIORITY range; raising the exception PROGRAM_ERROR when the check fails. - IH-24 If the system supports priority locking of protected objects, a check is made during elaboration of the protected object to insure that the ceiling priority of the protected object is at least as high as the highest priority at which the interrupt may be delivered; raising the exception PROGRAM_ERROR when the check fails. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 4-3 4.4. INTERRUPT HANDLER PROCEDURES DESIGN AND IMPLEMENTATION The initial design was to incorporate protected procedure interrupt handling support into the existing runtime code for task entry interrupt handling support within the tasking subsystem. As the development of this proposal progressed it was found to be an inappropriate technique (see Section 4.5). A new approach was put forth with the facilities to support protected procedure interrupt handlers integrated into the protected type subsystem. The following sections describe the design and implementation of the runtime data structures and routines developed for the later model. 4.4.1. Data Structures The protected procedure code as well as some of the supporting data structures, such as the PRDs (see Section 2.4.1.2), reside in the user space in the i960. Interrupt handlers and the data they manipulate must reside in executive space. Protected procedures are mapped to interrupts on the i960MC using runtime system code to bridge the gap between user space and executive space. To use the i960's interrupt handling facilities, the initial memory image loaded onto the processor must provide the interrupt table, the interrupt handler routines, and the interrupt stack. Pointers to these structures must be entered into the system data structures before the processor can handle interrupts automatically. The processor uses the interrupt table to deliver an interrupt to a handler. The initial interrupt table contains instruction pointers to static interrupt handler procedures and default interrupt handlers. New handlers are mapped to interrupts by inserting the interrupt handler instruction pointer into the appropriate entry in the interrupt table. In the case of the protected procedures, the interrupt table will contain a pointer to a special purpose runtime routine which will use a software interrupt table to deliver the interrupt to the protected procedure. A copy of the initial interrupt table is made to preserve the default values for the runtime system to access when detaching an interrupt from a protected procedure. Each interrupt on the i960MC is assigned a priority. The range of priorities corresponding to hardware interrupts is defined in the Ada system using the subtype System.Interrupt_Priority (see Section 5.3.1.1). The INTERRUPT_ID type is derived Integer with its range corresponding to the i960MC interrupt values [Requirement,IH-6]. 4.4.2. Algorithms On the i960MC, interrupt handlers execute in supervisor mode on the interrupt stack. The processor blocks interrupts of equal or lower priority while executing an interrupt handler by executing at the priority of the interrupt [Requirements IH-5, IH-8]. Up to 8 PAGE 4-4 TARTAN ADA 9X IMPLEMENTATION REPORT interrupts per priority level equal or lower are kept pending by the processor while servicing the current interrupt. When an interrupt occurs on the processor, the processor looks at the hardware interrupt table and transfers control to the corresponding handler, this handler must reside in executive space. As mentioned earlier, when the interrupt is attached to a protected procedure, the processor passes control to a special purpose runtime handler. The runtime handler uses the interrupt vector number as an index into the software interrupt table to find the protected procedure to handle the interrupt. As part of delivering the interrupt to the protected procedure, the runtime handler executes the protected object's prologue. The prologue will test to see if the ceiling priority of the protected object is greater than or equal to the interrupt priority, raising PROGRAM_ERROR if the check fails [Requirement IH-10]. Execution of the protected procedure handler will be conducted at the ceiling priority of the protected object [Requirement IH-8]. Upon completion of the protected object's prologue, the runtime handler calls the protected procedure to handle the interrupt [Requirements IH-1, IH-2, IH-3]. The protected object's epilogue code is executed at the completion of the protected procedure. The runtime handler and the protected operations are executed using the interrupt stack. Upon completion of the epilogue, if the processor returns from interrupt to the user space, any process which was dequeued as a result of the interrupt may be eligible for execution. If there are pending interrupts, these are serviced before returning to the user. A runtime routine is used to attach an interrupt to a protected procedure. This routine first checks the contents of the hardware interrupt table entry corresponding to the specified interrupt to determine if the interrupt is attached to a reserved interrupt. If so, the exception RESERVED_INTERRUPT is raised [Requirement IH-12]. If the handler to be attached to the interrupt is null, the exception CONSTRAINT_ERROR is raised [Requirement IH-11]. Otherwise, the hardware interrupt table is updated to insert a pointer to special purpose runtime handler for the specified interrupt. In addition, the software runtime table which the runtime handler accesses is updated to include the address of the protected object and routine to use to service the interrupt [Requirement IH-4]. If there is an entry in the software runtime table for the interrupt, the runtime routine to detach an interrupt is call for the entry [Requirement IH-9]. Upon return from the detach operation, the new data is written in the software runtime table entry. The detach runtime routine first checks the entry in the interrupt table to determine if the specified interrupt is attached to a user defined procedure. If the specified interrupt is reserved, the runtime routine will raise the exception RESERVED_INTERRUPT [Requirement IH-14]. Otherwise, the runtime routine will remove the protected procedure data from the software interrupt table. It will TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 4-5 then replace the entry in the hardware interrupt table with the default value stored in the runtime copy of the initial interrupt table [Requirement IH-13]. Several existing special purpose runtime routines were used as the basis for the implementation of IS_RESERVED, IS_ATTACHED, and CURRENT_HANDLER operations. Each runtime routine supporting these operations uses the value in the hardware interrupt table. The runtime routine corresponding to the IS_RESERVED operation returns TRUE if the hardware interrupt entry corresponds to a reserved interrupt, otherwise it returns FALSE [Requirement IH-15]. The IS_ATTACHED runtime routine uses the hardware interrupt table entry to determine if the specified interrupt is reserved, attached to a default handler, or attached to a user defined handler. It raises the exception RESERVED_INTERRUPT, returns FALSE, or returns TRUE, respectively [Requirements IH-16, IH-17]. The CURRENT_HANDLER runtime routine will raise the exception RESERVED_INTERRUPT if the specified interrupt is reserved; return null if the specified interrupt is not attached to a handler or attached to a default handler, or return the handler_id corresponding to the user defined handler attached to the interrupt [Requirements IH-18, IH-19, IH-20]. 4.5. ARCHITECTURAL ISSUES Protected architectures introduce some problems when attempting to attach user defined handlers to interrupts. 4.5.1. Protected Memory In some protected architectures, more work will be required to execute the user defined protected procedure as an interrupt handler because the user space is not visible when an interrupt is being serviced. When the i960MC processor is idle the user space is not visible to the processor. This means that either the protected object associated with an interrupt handler must be stored in executive throughout the execution of the application or a mechanism must exist to access the user space when an interrupt occurs and the processor is idle. The initial design was to encapsulate the protected procedure within a task at the corresponding interrupt level. Then whenever an interrupt occurred the existing runtime routines were used in the mapping interrupt to the task entry. This approach had a considerable amount of unnecessary overhead; e.g., a special purpose task per interrupt priority. The alternative solution was to keep an idle task ready to run at the lowest priority level whenever the processor would normally be idle. Then if an interrupt which is handled by a protected procedure occurred while this task is executing, the active priority of the idle task would be elevated to the interrupt level and the protected procedure could execute. PAGE 4-6 TARTAN ADA 9X IMPLEMENTATION REPORT 4.5.2. Interrupt Table The implementation of protected procedure interrupt handlers does not directly attach the handler to the interrupt table. Doing so would allow the user to execute code in the executive mode, effectively giving the user the potential to corrupt runtime data structures. If a direct attachment were to be permitted, the following issues and changes would need to be considered by the users: 1. Integrity of the runtime data structures may be compromised. 2. Privileged operations would be possible. 3. All code and data that is referenced by the protected procedure must be migrated to the executive space. 4. The code and data must be segregated in the executive space so that non-interrupt operations may access it without a supervisor execution mode change. 5. An attach operation may not be performed by user code unless a pragma is used at compile-time to cause the actions in 3 and 4 to take place at image build time. 4.5.3. Interrupt Stack The i960MC processor uses the interrupt stack when executing interrupt handlers. This stack is used during the execution of the protected procedure. The same stack problem discussed in Section 2.6.1 was experienced when testing protected procedure handlers; the interrupt stack was exceeded while processing the protected epilogue. Hence, the user needs to increase the interrupt stack size when using protected procedures to handle interrupts. 4.6. PERFORMANCE Preliminary tests have shown that the protected procedure interrupt handlers execute more efficiently than task entry handlers and library-level interrupt procedures out perform protected procedure interrupt handlers. 4.7. CONCLUSIONS AND RECOMMENDATIONS The suggested solution to the binding of interrupts to protected procedures is not possible on all protected architectures. In particular, when an interrupt occurs the processor services the interrupt in executive modes. In some instances this means that none of the user data space is visible -- not global data nor the protected record itself. This may be partially resolved by moving the protected object associated with the interrupt handler into the executive space. However, at least two problems remain: first is that the interrupt procedure may only touch components of the protected object (e.g. no TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 4-7 global data, no pointers outside of the object, etc.); second is the epilogue associated with the protected procedure. All of the barriers which must be evaluated during the execution of this epilogue must not access anything except the protected object's components. Addition- ally, none of the protected operations may access anything other than the protected components. An alternative solution when implementing protected procedure interrupt handlers on very restrictive architectures would be to allow the implementer to impose additional restrictions on the behavior of the protected object. It may then be possible to move these objects into the protected memory and use the supervisor trap for the interrupt to call into the protected procedure. Dynamic interrupt binding complicates this model somewhat. Perhaps it would be advisable to restrict dynamic binding in such architectures. PAGE 4-8 TARTAN ADA 9X IMPLEMENTATION REPORT CHAPTER 5 ENTRY QUEUING POLICIES 5.1. SCOPE In Ada 9X, the entry queuing policy defines the order in which tasks are placed in an entry queue. It also defines the choice among open select alternatives and the choice between tasks queued in protected entry queues. The default entry queuing policy for Ada 9X is first-come first-serve (FIFO). In some applications an alternative queuing mechanism is needed. The configuration pragma QUEUING_POLICY [8] provides the application programmer with the ability to specify the entry queuing policy to be used via a parameter. The priority queuing policy is defined in the Real-Time Annex. This policy is specified in the pragma with the name PRIORITY_QUEUING. The default policy is named FIFO_QUEUING. The annex permits an implementer to define additional queuing policies and encourages that they be named with the _QUEUING suffix. This chapter describes the implementation of the pragma QUEUING_POLICY for FIFO_QUEUING and PRIORITY_QUEUING. 5.2. REQUIREMENTS The implementation requirements for the entry queuing policies were derived from a review of Implementation Module III [3] and the Mapping Specification [6, 7, 8]. If these documents did not define a requirement succinctly, electronic mail was sent to the Mapping Revision Team (MRT) for clarification. Responses to electronic inquiries were regarded as the final word when conflicting definitions were provided. The following is the list of queuing policy implementation requirements: - QP-1 Calls to an entry are serviced in an order consistent with the active priorities of the calling task. - QP-2 Changes to the active priority of a task after it has been queued, do not affect the priority of the call, unless the base priority of the task is set. - QP-3 Setting the base priority of a task causes the priority of any queued calls from that task to be updated to the new active priority of the task and the calls to be requeued at the new priority. - QP-4 Calling tasks of equal priority are queued in FIFO order within the priority. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 5-1 - QP-5 When there are more than one open select alternatives with queued callers, the alternative with the highest priority caller is selected. - QP-6 When there are two or more open select alternatives with queued callers of equal priority which may be selected, the alternative that is first in textual order within the select statement is selected. - QP-7 When a protected object has more than one entry with queued callers and TRUE barriers, the entry with the highest priority caller is selected. - QP-8 When a protected object has two or more entry queues with callers of equal priority ready to be serviced, the entry that is first in textual order within the protected specification is selected. - QP-9 The full range of task priorities supported by an implementation must contain at least 31 values. - QP-10 The following relationship must always be true: SYSTEM.ANY_PRIORITY'FIRST = SYSTEM.PRIORITY'FIRST SYSTEM.ANY_PRIORITY'LAST = SYSTEM.INTERRUPT_PRIORITY'LAST SYSTEM.PRIORITY'LAST+1 = SYSTEM.INTERRUPT_PRIORITY'FIRST 5.3. ENTRY QUEUING POLICIES DESIGN AND IMPLEMENTATION The original design and implementation of the protected type followed the recommendations in the Implementation Module I [1]. In this module, the tasks in a protected entry queue were enqueued in priority order. Since this was a prototype implementation, when the Mapping Specification [6] revised the order of this queue to be FIFO, we did not modify the prototype. Hence, as part of the implementation of this module, the queue order for protected entries needed to be updated to be FIFO. Whereas, since the task queuing was originally organized as FIFO, they needed to be changed for priority. The affect of the queuing policy pragma is controlled by the runtime library which is linked with the application program. When the user specifies a queuing policy, the appropriate runtime library must be used. 5.3.1. Data Structures PAGE 5-2 TARTAN ADA 9X IMPLEMENTATION REPORT 5.3.1.1. Priority Subtypes The range of values used for the subtype System.Any_Priority corresponds to the range of priorities on the i960MC, with 31 being the highest priority [Requirement QP-9]. The integer subtype System.Any_Priority subsumes the subtypes System.Priority and System.Interrupt_Priority. These subtypes are defined as ranges of i960MC priorities as shown in Figure 5-1 [Requirement QP-10]. SUBTYPE Any_Priority IS Integer RANGE 0 .. 31; SUBTYPE Priority IS Any_Priority RANGE Any_Priority'FIRST .. 17; SUBTYPE Interrupt_Priority IS Any_Priority RANGE Priority'LAST+1 .. 31; FIGURE 5-1: Priority Subtypes 5.3.1.2. Entry Queues In the existing tasking runtime subsystem, rendezvous queuing is implemented using a separate queue for each task entry. In the new protected type runtime subsystem, protected entry queues are implemented using a single queue for all entries within a protected object. This decision was made because it was believed that there would be few tasks enqueued on a protected object simultaneously. 5.3.2. Algorithms 5.3.2.1. Dynamic Priorities The support for dynamically setting a task's base priority and retrieving a task's current base priority was derived from existing special purpose runtime routines. 5.3.2.2. Entry Queuing Algorithms The FIFO queuing policy requires the task entry queues and the protected object entry queue be maintained in FIFO order, while the PRIORITY_QUEUING policy maintains these queues in priority order. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 5-3 The use of a separate queue for each task entry optimizes the accept cases: * ACCEPT x; * SELECT ACCEPT x; OR DELAY time; END SELECT; * SELECT ACCEPT x; ELSE ... END SELECT; These cases can immediately select a caller from the queue, or determine that waiting for a call is necessary. The separate queue implementation slows the select-multiple-accept case, since a "two-dimensional" structure of queued calls is available. All the queues for selectable alternatives must be examined, and the highest priority task chosen. The single queue for protected entries removes the need for a two-dimensional array of TCBs. Originally, this structure was thought to be more efficient since the number of queue callers was expected to be low. However, protected objects with multiple entries and complex barriers may be more efficiently implemented using a queue per entry. More analysis is underway to determine the best choice. Very little modification was made to the existing tasking runtime subsystem to support this feature. The routine which enqueues a calling task was modified to place the calling task in the appropriate priority order, keeping the order FIFO within priority [Requirement QP-4]. The routine which chooses the accept alternative from a list of open accept statement was modified to choose the alternative with the highest priority caller waiting [Requirement QP-5]. A parameter was added to the call to determine if an alternative is empty to return the position of the accept statement within the select statement. This is used by the routine that chooses the alternative when there are two or more candidates with the same priority [Requirement QP-6]. For the protected entry implementation, the procedure that enqueues a calling task was modified from priority order to FIFO order. The algorithm which was implemented as part of the protected type implementation enqueued the tasks in priority order and FIFO within priority [Requirement QP-4]. Since a single queue is used for all protected entries, the highest priority task is always at the head of the queue. The queue is traversed until the corresponding entry barrier evaluates to TRUE, this entry body is then executed [Requirement QP-7]. Requirement QP-8 is not satisfied by this implementation; if two equal priority tasks PAGE 5-4 TARTAN ADA 9X IMPLEMENTATION REPORT are enqueued on different protected entries and both are candidates to execute, the task which called the protected object first will be dequeued prior to the other regardless of the position of the entry specification. 5.4. PERFORMANCE The cost of queuing a FIFO entry call is constant. The cost of queuing a priority entry call is linear, of the form: C1 + C2 * number_of_tasks_queued_on_entry Where C1 is larger than the FIFO constant, and C2 reflects the cost of searching down the existent sorted queue of tasks. Other more complicated sorting techniques were not used, since for small numbers of queued tasks the order of the complexity (linear vs. log) is less important than the size of the constant C2. The cost of a FIFO accept is linear, of the form: C1 + C2 * number_of_open_accepts Where C2 also reflects the probability of finding a caller without examining all open entries. The cost of a priority accept is also linear, of the form: C1 + C2 * number_of_open_accepts Now the C2 constant is larger, since it is not possible to terminate the search prior to examining all open entries. Moreover, each step in the search is more expensive, since existence of a caller is not sufficient to determine the action to be taken. The User portion of this report (see Implementation Report Part 2) contains a summary of preliminary results from tests using priority and FIFO queuing. 5.5. CONCLUSIONS AND RECOMMENDATIONS The ability to specify priority queuing instead of FIFO queuing is a useful mechanism for many applications. The definition of which alternative is selected when multiple alternatives are open is also quite helpful. However, the specification of the textual order being used to break ties between alternatives is a nuisance to implement. This requirement may also place unnecessary restrictions on optimizers. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 5-5 CHAPTER 6 HIERARCHICAL PROGRAM LIBRARIES 6.1. SCOPE The Ada 9X Hierarchical Program Libraries proposal set forth in Implementation Module I [1] consists of two changes that affect separate compilation: - Subunits within a library unit are not required to have distinct simple names. - Library units may form a hierarchy. This report describes the effort expended in implementing these two items in an existing Ada product. The effort is discussed in terms of the functional requirements deduced from the version 4.0 of the Mapping Specification [7]. The requirements are divided into two basic categories: syntax/semantic requirements and database require- ments. The implementation of these requirements impacted two compiler subsystems, the Front End and the Librarian. There was no effect on the code generator, linker or runtime system. In a production quality implementation the code generator would have to be modified to produce better debug directives. It is assumed that the reader is familiar with the Ada 9X Mapping Specification [7]. 6.2. REQUIREMENTS The requirements that follow are specifically geared to the integration of the language changes introduced by the Hierarchical Program Libraries proposal into a functional compiler and librarian. That is to say, some emphasis is placed here on what has to be changed in terms of previous assumptions about compilation unit names, visibility and database items that made use of those assumptions. The following is a list of the Hierarchical Program Libraries Requirements: 6.2.1. Subunits within a library unit are not required to have distinct simple names This requirement has no impact on the Front End of the compiler. The only enforcement of subunit name uniqueness done by the Front End has not been affected (see HL-FE-1 below). - HL-FE-1 Units stubbed within the same compilation unit must still have unique identifiers. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-1 - HL-L-1 Database lookups by name must allow multiple units with the same ancestor and simple name. - HL-L-2 Files created for a compilation unit cannot depend only upon the ancestor and simple name for determining uniqueness of their names. - HL-L-3 Linknames created for a compilation unit cannot depend only upon the ancestor and simple name for determining uniqueness. 6.2.2. Library units may form a hierarchy - HL-FE-2 The name of a child unit is in the form of an expanded name. A WITH clause mentioning the parent unit is not necessary when declaring a child unit. - HL-FE-3 A library unit may be declared PRIVATE. - HL-FE-4 In addition to a visible and private part, a library unit package is considered to have a child part, where the declaration of child units are considered to occur. The child part occurs at the end of the package specification, following the visible part and private part (if any). - HL-FE-5 The visible part of a visible or private child unit has direct visibility to the visible part of the parent library unit(s), all the way up the hierarchy to the root library unit. - HL-FE-6 The private part of a visible child unit and the visible and private parts of a private child unit have direct visibility to the visible and private parts of the parent library unit(s), all the way up the hierarchy to the root library unit. - HL-FE-7 The restrictions on the use of private types (RM-7.4.1(4)) or deferred constants (RM-7.4.3(2)) do not apply to uses in child units, because they follow the full declaration. - HL-FE-8 When the parent package is mentioned in a USE clause, the simple names of the currently WITH'd child units are made directly visible. - HL-FE-9 When a parent body WITH's its own child, the simple name of the child is directly visible and the parent body may not declare a homograph of that child. PAGE 6-2 TARTAN ADA 9X IMPLEMENTATION REPORT - HL-FE-10 The expanded name used in a WITH clause must be a full expanded name of the library unit. - HL-FE-11 The WITH of a child library unit includes an implicit WITH of the parent unit. This is transitive, i.e., all ancestor units are also WITH'd. - HL-FE-12 Selection via dot-qualification must be supported for types and objects declared in child units. - HL-FE-13 Visible child subprograms are not derivable subprograms, because they are not declared within the same list of declarations as the type. - HL-L-5 A library unit with a dot-qualified name is the child of the parent unit. A child depends upon its parent library unit. - HL-L-6 The parent of a child unit must be a non-generic library unit package. - HL-L-7 A root private library unit is treated like a child of standard, and thus is only visible to secondary units and other private root units (and their children). - HL-L-8 A private unit may only be WITH'd by the compilation units within the hierarchy of library units rooted at that private unit's parent unit. - HL-L-9 A visible child unit may have a private parent. - HL-L-10 A visible child library unit must not depend on a private child of the same parent package. - HL-L-11 A child library unit must be elaborated after the specification of its parent package. - HL-L-12 A child subprogram must be allowed as a main unit if it meets all other requirements for main unit status. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-3 - HL-L-13 Only one secondary unit can exist in a given library with a given name. This prohibits having a subunit with the same name as a child unit body where both are consistent at the same time. It allows the database search key of tuple (name:string, is_library_unit:boolean) to uniquely determine one unit. 6.3. GENERAL DISCUSSION 6.3.1. Compiler The modifications for Hierarchical Libraries were confined to the Front End of the compiler. The majority of the modifications were in the areas of importing library unit context and visibility processing. Existing data structures were used for the majority of the parse tree representation of child units. Instead of representing child units as nested packages, they were represented as root units, and the relationship between parent and child was represented in a manner similar to the relationship between a specification and secondary unit. During the compilation of a child unit, the parse tree resembles the tree that results from compiling a secondary unit. The visibility of a child into parent is similar to the visibility of a secondary unit into its specification with a few differences as discussed in requirements HL-FE-5 through HL-FE-9. As a result, much of the Front End processing could be left unchanged. Any special processing that is required for child units is done as a result of attributes that only they have. We feel that this approach allows the maximum reuse of existing compiler code and represents the status of child units accurately. One additional compiler data structure was introduced, and is described in the implementation of requirement HL-FE-2. Importing the context for child units is similar to importing context for any unit, with the addition that child units include context from their ancestor units. The context importing algorithms had to be modified to take into account the parse tree representation for child units. Changes to visibility processing are discussed in detail in the implementation of requirements HL-FE-5 through HL-FE-9. The most difficult visibility changes were those that involved allowing the correct amount of visibility into the visible and private parts of the ancestor units, based on the privateness of the child unit and the current location within the child unit. PAGE 6-4 TARTAN ADA 9X IMPLEMENTATION REPORT 6.3.2. Librarian Tartan uses a library database to manage compilations units. Each compilation unit has an entry with certain attributes in the database. The attributes include items such as name, time-stamp, and the keys for all dependencies. Symbol table information and semantic information for the unit is stored in a separate file that is in the library directory. Each unit in the library may have up to three files associated with it, the symbol table file, an internal source file, and an object file. The librarian ensures that no two units expect to have the same file name. In Ada 83, the librarian used the subunit name uniqueness constraint to determine the file name, as well as link name. These names were determined by applying a compression algorithm to the ancestor name and simple name of the subunit (e.g., A.D for subunit A.B.C.D). It would append a hash value at the end of the name if necessary, i.e., if it had been compressed. For subunits, the file name might have the period in the name translated to a different character if the host does not support multiple periods. For instance, on VMS a subunit A.B.C.D would have an object file named A$D.OBJ associated with it. Closure during compilation is determined by calling the librarian via a procedural interface. If any closure errors occur, the compilation reports those errors and stops. This avoids the extra overhead of reading in all of the valid symbol table files, and the cascading semantic errors that would result because certain files could not be read. The perspective that Tartan took with child units, from a library database perspective, was that they are no different than any other kind of unit. The only change that had to be made to the data stored on disk was to add an Is_Private boolean, which is a trivial change for our librarian. Adding fields to compilation unit records can always be accomplished in an upward compatible way. The files associated with a child unit are in no way connected to the parent unit anymore than any other unit dependency. Also, generation of filenames for child units and linknames for objects declared within a child unit would be independent of the linknames and filenames generated for the parent unit. One problem introduced with the hierarchical library units concerned the new possibility of having two secondary units with the same name where both have consistently compiled defining units. A child unit for a given parent unit can be consistent at the same time as the secondary unit for that parent unit, where that secondary unit declared a stub with the same simple name as the child unit. Without a major overhaul of our database structures, we cannot allow two secondary units with the same name to exist in a library. Requirement HL-L-13 allows us to implement hierarchical library units without restructuring all of our database code. We took the position that a child unit's body with the same name as a subunit could not be added to a library if the subunit's parent was consistent. With our tree-structured derived libraries, one could indeed have the subunit in one partition and the child unit in another, but there must still be a link time failure if both are to be included in a link, as only TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-5 one is allowed according to the Mapping Specification. We have separated this into two cases: in the first case, when linking from one library partition, there can only be one secondary unit with the same name. If both are needed for linking, the linking routines will find one of them missing and it will be an error. In the second case, where the subunit is in one partition, and the child unit is in another, the link still fails, for only one secondary unit with the given name will be brought into the link, so it will not be consistent with regard to one of the relationships, i.e., it cannot be both a subunit and a child unit body. We stored the attribute Is_Private in the library database for two reasons. First, the ability to WITH a private unit was decided to be a librarian closure issue, where an illegal WITH of a private child is considered a closure error, and the compilation ends. Second, this allowed our facilities for displaying a compilation unit to the user to indicate that a unit is private. 6.4. IMPLEMENTATION 6.4.1. Implementation of HL-FE-1 Units stubbed within the same compilation unit must still have unique identifiers. 6.4.1.1. Issues No changes were necessary for this requirement. In the Tartan compiler, the visibility processing algorithms are used to identify declarations that are homographs and reject them if they do not meet the requirements in RM-8.3(17). Subunits stubs declared in the same declarative region are considered the same as any declaration where homographs are not permitted. The declaration of the second stubbed unit is identified as a homograph and rejected. 6.4.2. Implementation of HL-L-1 Database lookups by name must allow multiple units with the same ancestor and simple name. 6.4.2.1. Issues This was not a problem for our database. We have never required this to be a unique key. The compilation of a subunit with the same simple name as another subunit always caused the deletion of the previous subunit. This was possible because Tartan's implementation of subunits reserved the name of the subunit at the point of the body stub. For example, if subunit "a.b" contains a body stub "c," subunit "a.d" cannot declare a subunit "c" if "a.b" is consistent. If, on the other hand, the unit containing the body stub is not consistent, the new compilation ("a.d" PAGE 6-6 TARTAN ADA 9X IMPLEMENTATION REPORT with body stub "c") can be allowed. When compiling subunit "a.d.c," it is not possible to have any other subunit with the same ancestor and simple name in the database that could be consistent, because at the very least it cannot be consistent with respect to its parent unit. We therefore delete any previous subunit with the same ancestor and simple names when the current subunit is entered into the library. So, although the database was designed to allow two subunits to exist concurrently with the same ancestor and simple names, this feature was never exercised. Testing and code review of this aspect found that we could indeed allow units with the same ancestor and simple name, but that we would have to resolve HL-L-2 and HL-L-3. 6.4.3. Implementation of HL-L-2 Files created for a compilation unit cannot depend only upon the ancestor and simple name for determining uniqueness of their names. 6.4.3.1. Issues Previously, any subunit entered into the library had a special record associated with it that held the file name and link name attributes. This record was keyed on the ancestor and simple name, i.e., all subunits with the same ancestor and simple name had the same link name and file name. This concept was used to limit the loss of potential link names and file names, and guarantee the lower bound on the maximum number of subunits that could be stored in a library. This lower bound was 1.6 million. By contrast, the maximum number of uniquely named compilation units allowed to be compiled into a library over the life of a library was SYSTEM.MAX_INT. It was relatively trivial to eliminate the subunit maximum, and let it be determined solely by the compilation unit maximum. Instead of needing to append four unique characters to a file name for uniqueness, we now allowed for six. We now could key the file name and link name to the fully qualified name, and thus allow units to be retained in the database even when a new unit with the same simple name was entered. Previously, we could not allow them to be retained, because the new unit would overwrite the old unit's files. 6.4.4. Implementation of HL-L-3 Linknames created for a compilation unit cannot depend only upon the ancestor and simple name for determining uniqueness. 6.4.4.1. Issues This problem was resolved with the resolution of HL-L-2. 6.4.5. Implementation of HL-FE-2 The name of a child unit is in the form of an expanded name. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-7 6.4.5.1. Issues Previously, compilation units (including subunits) were treated as having a simple name, stored in the symbol table. The expanded name notation of child units complicated this slightly and two approaches were considered: - Modifying algorithms throughout the compiler to deal with expanded names for library units. - Processing child units, knowing only their simple names. Tartan chose a mixture of the two approaches. The parse tree is built with child units having expanded names. After the name is registered with the librarian, the name of a child unit is reduced to the simple name. (i.e. unit A.B becomes B). Since child units are considered to be inside the child part of the parent unit, they are at the same scope level as the declarative parts of the parent unit. Depending on context, the name of a child unit may be referenced with or without the parent unit name. In cases where the child unit name is referenced without the parent name, the visibility of the child name is handled the same as that of any object declared inside the parent. This type of processing is discussed in requirements HL-FE-5 and HL-FE-6. Where the parent's name is used as a qualifier, it is treated the same as selection via dot-qualification. This process is discussed in requirement HL-FE-12. Semantic analysis (including visibility processing) and code generation are achieved with child units having only their simple names, which are at the same scope level as declarations in the parent unit. 6.4.5.2. Data Structures There were several changes to the existing language grammar. Several rules were restructured in order to avoid shift-reduce conflicts in Tartan's LALR parser generator due to the increased use of expanded names. The expanded names for child units are initially represented in the parse tree with the same data structures used to represent dot-qualified names. After reduction to simple names, the name of a child unit is represented the same as any root unit. An additional data structure was chosen to represent the relationship of parent library units to child library units. In this report, this simple structure will be called the LIBRARY UNIT LIST. The purpose of this structure is to identify the child units that are included in the child part of any parent unit currently imported. Any algorithm in the compiler that requires the fully expanded name for a child unit (i.e., during linkname generation) can get the full name from this data structure. This data structure could have been implemented directly in the parse tree or in the librarian, but it was kept separate so that it may be developed simply and independently from both the parse tree and librarian. PAGE 6-8 TARTAN ADA 9X IMPLEMENTATION REPORT 6.4.5.3. Algorithms The parser was modified slightly to facilitate the building of parse trees for child library units. The semantic actions that deal with library unit names had to be modified for the expanded name space (e.g. checking the name on the END statement against the name of the unit). The new routines written to manipulate the library unit list include: procedure Add_Unit (unit: node; parent: node); function Is_Child (unit: node) return Boolean; function Is_Parent (unit: node) return Boolean; function Parent_Of (unit: node) return node; function Child_List_Of (unit: node) return iterator; function Full_Name_Of (unit: node) return Ada_Name; 6.4.6. Implementation of HL-FE-3 A library unit may be declared PRIVATE. 6.4.6.1. Issues The 'privateness' of a unit must be maintained and be known when the unit is compiled or when it is being imported. The compiler must be able to communicate to the librarian that the current unit being compiled is a private unit. 6.4.6.2. Data Structures The parse tree was expanded to include a private attribute. The compiler/librarian interface was extended to allow marking units PRIVATE. 6.4.6.3. Algorithms Privateness is detected by the parser and the private attribute in the parse tree is set there. The librarian is informed that the submitted unit is private when the request is made to check closure prior to semantic analysis. 6.4.7. Implementation of HL-FE-4 In addition to a visible and private part, a library unit package is considered to have a child part, where the declaration of child units are considered to occur. The child part occurs at the end of the package specification, following the visible part and private part (if any). TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-9 6.4.7.1. Issues While it is true that the child part follows the visible and private parts of the parent, the child part does not have the visibility that ARM (Chapter 8) describes for normal declarative regions. There are separate rules for the visibility of the child part into the parent's visible and private parts, described in MS-10.1(13). Tartan believes that MS-10.1(13) should be expanded to also define the visibility of the child part of child subprograms, child generic declarations and child instantiations. The child part is not physically represented Tartan's data structures, except that the library unit list maintains the list of currently loaded children (and therein the child parts) of all compilation units currently being processed. 6.4.7.2. Data Structures In Tartan's representation, the declarations in a library unit package are organized in groups (visible and private). In addition, each declaration also has an attribute such that, even out of context, it can be determined whether the declaration occurred in a visible or private part. 6.4.7.3. Algorithms Visible and private parts are key to correct visibility processing. More detail is given on their use in the implementation of requirements HL-FE-5 and HL-FE-6. 6.4.8. Implementation of HL-FE-5 The visible part of a visible or private child unit has direct visibility to the visible part of the parent library unit(s), all the way up the hierarchy to the root library unit. 6.4.8.1. Issues Visibility processing is a recursive process. The hierarchical structure of child library units fits well into this model. Tartan's representation of child units as root units allows the ancestor units to be treated as imports, and processed as such by existing code. 6.4.8.2. Data Structures The library unit list is useful during visibility processing for querying the parent/child relationships. 6.4.8.3. Algorithms The visibility processing of a unit begins by making the context for this unit visible. For root secondary units, this would include making all the declarations from the corresponding library unit visible. Child units are handled in much the same manner. For a PAGE 6-10 TARTAN ADA 9X IMPLEMENTATION REPORT visible child unit, it is necessary to make visible all the declarations from the visible parts of the ancestors of the child unit. The declarations from the visible part of package specifications are grouped together in Tartan's representation, so making visible each declaration from each ancestor's visible part requires only an iteration over this group. To satisfy this requirement, this call may be made to the algorithm given below: Make_Parent_Context_Visible (declaration => child_unit, visible_part => TRUE, private_part => FALSE); Algorithm used for visibility processing: procedure Make_Parent_Context_Visible (declaration: node; visible_part: Boolean; private_part: Boolean) is begin if Is_Child_Unit (declaration) then parent := Parent_Of(declaration); -- make visible the declarations from the -- ancestors. (parents of parent) Make_Parent_Context_Visible (parent, visible_part, private_part); -- make the visible part of parent visible -- at correct scope level if visible_part then Make_Visible (Visible_Part (parent)); end if; -- make the private part of parent visible -- at correct scope level if private_part then Make_Visible (Private_Part (parent)); end if; end if end; 6.4.9. Implementation of HL-FE-6 The private part of a visible child unit and the visible and private parts of a private child unit have direct visibility to the visible and private parts of the parent library unit(s), all the way up the hierarchy to the root library unit. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-11 6.4.9.1. Issues From a visibility perspective, processing of references from child units to items in the private part of parent units is similar to the processing of references in package bodies to items in the private part of package specifications. 6.4.9.2. Data Structures The library unit list is useful during visibility processing for querying the parent/child relationships. 6.4.9.3. Algorithms For private child units, it is necessary to make visible both the visible and private parts of the ancestors of the child unit. In Tartan's representation, declarations in the private part of package specifications are grouped together. After making visible the visible portion of the ancestor units as described in requirement HL-FE-5, declarations in the private part of the ancestor units are made visible in the same manner. Using the algorithm from requirement HL-FE-5, this can be done via: Make_Parent_Context_Visible (declaration => child_unit, visible_part => TRUE, private_part => TRUE); For a visible child unit, visibility processing must consider the location of the entity being processed. In the existing Tartan compiler, declarations and objects have an attribute that determines their location within the package (visible part, private part, body). This attribute was used as-is to determine whether the processing of an entity in a child package should consider the private part of ancestor units as well as the visible part. The algorithm from requirement HL-FE-5 may be used as follows: -- Before processing the visible part of the -- visible child Make_Parent_Context_Visible (declaration => child_unit, visible_part => TRUE, private_part => FALSE); -- Before processing the private part of the -- visible child -- Have already made visible part visible (see above) Make_Parent_Context_Visible (declaration => child_unit, visible_part => FALSE, private_part => TRUE); 6.4.10. Implementation of HL-FE-7 The restrictions on the use of private types (RM-7.4.1(4)) or deferred constants (RM-7.4.3(2)) do not apply to uses in child units, because they follow the full declaration. PAGE 6-12 TARTAN ADA 9X IMPLEMENTATION REPORT 6.4.10.1. Issues After implementation of requirement HL-FE-4, no modification was necessary for this requirement. This is a natural consequence of the logical placement of child units in the child part of the parent units. The visible and private parts of a child unit are considered to follow the parent units visible and private parts. As a result, for any private type that has a completion the completion would be 'seen' before any use in the child unit. Tartan's overload resolution algorithms will correctly match the reference in the child to the completed declaration. 6.4.11. Implementation of HL-FE-8 When the parent package is mentioned in a USE clause, the simple names of the currently WITH'd child units are made directly visible. 6.4.11.1. Issues This requirement was the impetus for the library unit list. When library unit A is WITH'd, the child part of A is empty. If any of A's children are WITH'd, then those children are logically considered to reside in the child part of A. Issuing a USE A clause should make all the declarations in A directly visible, including any child units currently in the child part of A (i.e. A.B is visible as B). As a result of this requirement, the child part of each imported unit must be dynamically maintained. 6.4.11.2. Algorithms When unit A is imported, it is inserted into the library unit list. If unit A.B is imported, it is inserted also into the library unit list and it is noted that A.B resides in the child part of A. If a USE clause mentions A, then this requirement may be met by iterating through the list of children currently in the A's child part, making the simple names of the children visible. 6.4.12. Implementation of HL-FE-9 When a parent body WITH's its own child, the simple name of the child is directly visible and the parent body may not declare a homograph of that child. 6.4.12.1. Issues This requirement can be considered a result of requirement HL-FE-4: - A child unit is logically considered to reside in the child part of the parent unit, after the visible and private parts. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-13 When the parent body WITH's its own child, the child appears in the child part of the parent (the specification for this body). The declarations in the body are at the same scope level as the child part of the package specification, therefore homographs of the simple names of child units currently in the child part may not be declared. 6.4.12.2. Algorithms This was a small change to the general visibility processing algorithms when dealing with WITH clauses. 6.4.13. Implementation of HL-FE-10 The expanded name used in a WITH clause must be a full expanded name of the library unit. 6.4.13.1. Issues The result of this requirement is that processing WITH clauses for expanded names is no harder than processing WITH clauses for simple names. Without this requirement, the following code would have multiple interpretations. WITH A.B; -- includes a with of A USE A; -- makes B visible as a simple name WITH D; -- Is this a WITH of A.D or D ? package foo is ... end; 6.4.13.2. Data Structures An expanded name in a WITH clause is represented using the same parse tree representation as a dot-qualified reference. The grammar for Tartan's LALR parser generator was modified to allow expanded names in WITH clauses. 6.4.13.3. Algorithms In the Tartan compiler, WITH clauses are handled as follows: - Inform the librarian of the name(s) in the WITH clause, so that closure may be checked. - Read in the representation for the imported units. - Do visibility processing for the unit being compiled in the context of the imported unit(s). To allow expanded names in WITH clauses, the compiler needed only to be able to communicate the expanded name to the librarian. Tartan's compiler/librarian interface was already capable of dealing with expanded names for compilation units. PAGE 6-14 TARTAN ADA 9X IMPLEMENTATION REPORT 6.4.14. Implementation of HL-FE-11 The WITH of a child library unit includes an implicit WITH of the parent unit. 6.4.14.1. Issues Tartan agrees that the implicit WITH of parent units on the WITH of a child unit is a useful feature. This requirement was not difficult to implement in the Tartan compiler. 6.4.14.2. Algorithms The symbol tables for the parent unit are brought in automatically by the existing context importing algorithms. The only additional work was to make the name of the parent units directly visible. 6.4.15. Implementation of HL-FE-12 Selection via dot-qualification must be supported for types and objects declared in child units. 6.4.15.1. Issues This requirement is an extension to the processing of dot-qualified references. Tartan's processing considers only one level of the reference at a time. For example, in a reference to A.B.C, the reference A.B is considered, followed by the reference B.C. As a result, child units present two new interesting cases: - A reference to A.B where B is a child unit of A - A reference to A.P where P is in the private part of A 6.4.15.2. Data Structures The library unit list is useful here to determine parent/child relationships. 6.4.15.3. Algorithms Dot-qualification resolution is considered as part of general overload resolution in the Tartan compiler. In the references to A.B and A.P above, the attempt is made to find these items in the 'normal' Ada 83 places (e.g. find B in the visible part of A). We add to the above the following interpretations resulting from child units: - For A.B, check the child part of A, to see if the child unit B currently resides there. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-15 - For A.P, the compiler determines whether the current context is allowed visibility into the private part of A. For child units, the cases where this is allowed are: * Reference to A.P from a private child of A. * Reference to A.P from the private part of a visible child of A. * Reference to A.P from the body of a visible or private child of A. - This is similar to the processing of dot-qualified references from inside a secondary unit to the private part of a specification. 6.4.16. Implementation of HL-FE-13 Visible child subprograms are not derivable subprograms, because they are not declared within the same list of declarations as the type. 6.4.16.1. Issues This requirement was met by the choice of the representation of the child part - requirement HL-FE-4. The choice of the child part separate from the visible and private part of a library unit package meant that the algorithms determining derivability never considered child subprograms. 6.4.17. Implementation of HL-L-5 A library unit with a dot-qualified name is the child of the parent unit. A child depends upon its parent library unit. 6.4.17.1. Issues The interface between the compiler and the librarian requires that the dependencies for that unit be passed to the librarian in a data structure called a CONTEXT_CLAUSE. Our current algorithms treat the first dependency in the list as special. The first dependency in the list is: - the parent unit for subunits - the library unit for proper bodies - not defined for root library units, i.e., any dependency So, it was a natural to extend the first dependency to: - the parent library unit for child units PAGE 6-16 TARTAN ADA 9X IMPLEMENTATION REPORT One way to look at this is that the attribute "parent" is attached to the parent unit so that privacy and type issues may be explored. In our implementation, if a closure check is requested for a library unit, and that unit has a qualified name, we know it is a child unit, and that the first dependency in the context clause list is the parent unit. This dependency could have been created by the librarian itself, but we decided against that approach. Since our current algorithm has our front end communicating to the librarian what the direct dependencies are, we saw no need to reverse that flow of communication by having the librarian attach this dependency. We do not need to have the entire parent chain expanded in the context clause, nor do we need this for imports of child units. The semantics of the WITH of a child unit allow the parents to be visible. We did not need to see this in terms of a closure dependency, as the transitive nature of dependencies adequately covers this. 6.4.17.2. Data Structures type Context_Clause_Element is record Name : Ada_Name; elaborate : boolean; -- indicates presence of pragma elaborate Id : Comp_Unit_Key; [...] end record; type Context_Clause_Type is array (positive range <>) of Context_Clause_Element; 6.4.18. Implementation of HL-L-6 The parent of a child unit must be a non-generic library unit package. 6.4.18.1. Issues This is relatively straight forward. When the parent unit of a child unit is read from the database, its type is checked for compliance. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-17 6.4.18.2. Algorithms procedure Check_Closure (For_Unit : COMPILATION_UNIT) is [...] procedure Process_Child_Library_Unit is parent : COMPILATION_UNIT := Fetch (For_Unit, PARENT_RELATIONSHIP); begin if (parent.Type_Unit /= PACKAGE_SPECIFICATION) then Report_Error (PARENT_NOT_PACKAGE); end if; end Process_Child_Library_Unit; [...] begin [...] if Is_A_Child (For_Unit) then Process_Child_Library_Unit; end if; [...] end Check_Closure; 6.4.19. Implementation of HL-L-7 A root private library unit is treated like a child of STANDARD, and thus is only visible to secondary units and other private root units (and their children). 6.4.19.1. Issues This requirement is stated explicitly because this "child to STANDARD" concept is implicit and must be handled differently than other child relationships. The rationale states that implementations might use private root units to limit visibility of units between libraries. Our experience is that for most subsystems, that would mean all but a few root units would be private. It would seem that in defining subsystem on a library basis, it would be better to introduce a different token that states this unit is available for import as opposed to this one that says it is not available. PAGE 6-18 TARTAN ADA 9X IMPLEMENTATION REPORT 6.4.19.2. Algorithms We present the algorithm for HL-L-7, HL-L-8, HL-L-9, and HL-L-10 together, since the basic rules for the use of PRIVATE are: if you WITH a private child you must be rooted at the library unit's parent unit if you are a library unit you must be private or a descendant of the with'd unit fi fi procedure Check_Closure (For_Unit : COMPILATION_UNIT) is [...] procedure Check_Privacy (Of_Unit : COMPILATION_UNIT) is begin if not (Is_Rooted (For_Unit, Parent_Of (Of_Unit)) or else Is_Root_Unit (Of_Unit)) then Report_Error (NOT_ROOTED_CHILD); elsif not ( For_Unit.Is_Private or For_Unit.Type_Unit in Secondary_Unit_type or Is_Rooted (For_Unit, Of_Unit)) then Report_Error (NOT_PRIVATE_CHILD); end if; end if; end Check_Privacy; [...] begin [...] for index in For_Unit.Context_Clause'range loop Dependency := fetch (For_Unit.Context_Clause (index)); if Dependency.Is_Private then Check_Privacy (Of_Unit => Dependency) then end if; [...] end loop; [...] end Check_Closure; 6.4.20. Implementation of HL-L-8 A private unit may only be WITH'd by the compilation units within the hierarchy of library units rooted at that private unit's parent unit. 6.4.20.1. Issues This rule states that in order to WITH a private child unit, the current unit must have the private child unit's parent as an ancestor. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-19 6.4.20.2. Algorithms The algorithm for this is presented in 6.4.19.2. 6.4.21. Implementation of HL-L-9 A visible child may have a private parent. 6.4.21.1. Issues This allows one to have a child unit that has the same visibility as the parent unit. If a private parent could only have a private child, the rules would limit the visibility of the child to the descendants of the parent. Allowing the visible child allows us to extend the parent, i.e., this visible child would be WITHable everywhere the parent can be WITHed. If we restate this requirement along with HL-L-10, the two requirements translate into "a visible child library unit must not depend on any private child unit, unless that private unit is an ancestor." 6.4.21.2. Algorithms The algorithm for this is presented in 6.4.19.2. 6.4.22. Implementation of HL-L-10 A visible child library unit must not depend on a private child of the same parent package. 6.4.22.1. Issues This requirement was resolved in HL-L-2. 6.4.22.2. Algorithms The algorithm for this is presented in 6.4.19.2. 6.4.23. Implementation of HL-L-7 A child library unit must be elaborated after the specification of their parent package. 6.4.23.1. Issues No implementation work was required to do this. Since a child library unit has a dependency on their parent package, this is no departure from the rules of Ada 83. PAGE 6-20 TARTAN ADA 9X IMPLEMENTATION REPORT 6.4.24. Implementation of HL-L-12 A child subprogram must be allowed as a main unit if it meets all other requirements for main unit status.) There was no directly stated requirement for this in any of the documents, but there did not seem to be any reason to assume a child unit cannot be a main unit. 6.4.24.1. Issues Only one difficulty needed to be resolved to implement this requirement. Some operating systems do not allow multiple "." characters in a file name. There are many solutions to this, such as requiring a legal output file name to be provided as input by the user, transform "." to another character, etc. We chose to allow the user to optionally supply an output file name, as we always have, or if not provided, the output file name would be the simple name of the child unit, truncated if necessary. 6.4.25. Implementation of HL-L-13 Only one secondary unit can exist in a given library with a given name. This prohibits having a subunit with the same name as a child unit body where both are consistent at the same time. It allows the database search key of tuple (name:string, is_library_unit:boolean) to uniquely determine one unit. 6.4.25.1. Issues The rationale for this requirement may be found in Section 6.3.2. Implementation required modification to code in four places: - When compiling a subunit, check for name collisions with child units. (warning) - When compiling a child unit body, check for name collisions with subunits. (error) - When compiling a parent unit, check for name collisions with stubs. (warning) - When linking, ensure that there are no name collisions of secondary units at link time. (error) 6.4.25.2. Algorithms The algorithms for the implementation of HL-L-13 are presented in a more general pseudo-code than before, because to present any more detail for these algorithms gets us quickly into proprietary code. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-21 case when compiling a child unit: fetch body of parent unit foreach stub in parent unit body if stub.simple_name = unit.simple_name then if Is_Consistent (parent) report_error (name_conflict) else report_warning (name_conflict) fi fi rof when compiling a subunit: fetch library unit with same fully expanded name if unit exists then report_warning (name_conflict) fi when compiling a unit with subunits: foreach stub in current unit fetch library unit with same fully expanded name if unit exists then report_warning (name_conflict) fi rof when linking a program: if elaborating a child unit body then ensure body is not a subunit elsif elaborating a subunit ensure unit is not a child unit body fi -- current algorithms would find only one secondary unit -- with a given name, so there is no check necessary to -- see if two units with the same name are included. esac The latter algorithm addresses the problems that occur when a library unit exists with the same name as a subunit. The unit containing the body stub and the library unit can exist together, but there can only be one secondary unit with a given name. So, either we do not have the subunit body, or we do not have the proper body of the library unit. When linking a program that was fully consistent, except there was a missing subunit or child unit body due to the name collision, our Ada 83 algorithm did not detect the loss. PAGE 6-22 TARTAN ADA 9X IMPLEMENTATION REPORT Our algorithm was: function Build_Elaboration_Closure_Graph (For_Unit : Compilation_Unit) return CU_Graph is [...] procedure elaborate (Current_Unit : Compilation_Unit) is [...] begin Check_Consistency_of_Context_Clause; [...] for i in Current_unit.Subunits'range loop subunit := fetch (Current_Unit.Subunits(i).ID) -- Need check here: is this my subunit elaborate (subunit); end loop; [...] if Current_Unit.Type_Unit in Library_Unit_Types then Body_Unit := fetch (Body_Of (Current_Unit); -- Need check here: is this my body elaborate (Body_Unit) [...] end if; begin [...] elaborate (main) [...] end Build_Elaboration_Closure_Graph; The structure of this check only checked consistency in an upwards direction, i.e., that everything a given unit depends upon has not changed. There was no downward check of the form, is this my body, is this my subunit. This was never a problem before because it was not possible to have a uniquely named secondary unit that could have two possible defining units. 6.5. CONCLUSIONS Changes to visibility processing were the bulk of the modifications to the compiler. In most cases, existing data structures could be used as-is, or extended in straightforward ways. Existing algorithms for Ada 83 visibility processing were utilized to perform the additional visibility processing of hierarchical units. No new low-level visibility algorithms were needed. The changes to the program librarian were roughly equal in scope to the compiler changes. New attributes for compilation units were added and algorithms written or modified to deal with these attributes. The expressiveness available with hierarchical library units is tremendous. We found ourselves constantly thinking of how we could restructure our code (the librarian and compiler are written in Ada) to take advantage of these features. The child unit concept would allow us to maintain our information hiding, while allowing us to expand the functionality of our packages without recompiling all the TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 6-23 code dependent upon the root package. The concepts are a natural extension of the current language, i.e, they have a nice intuitive feel to them. PAGE 6-24 TARTAN ADA 9X IMPLEMENTATION REPORT CHAPTER 7 TAGGED TYPES AND TYPE EXTENSION 7.1. SCOPE A cornerstone of the Ada 9X proposals has been the effort to support object-oriented programming (OOP) as a means for the development of reuseable software components and extendable systems. Central to the OOP support in Ada 9X is the introduction of user-defined classes of types, class-wide types, tagged types and type extension. The proposals of the Mapping Team in this important area have changed dramatically during the course of the work of the User/Implementer Teams. Progressively cleaner and tighter formulations of these concepts have been proposed and adopted. The basis of the work reported here is primarily version 4.0 of the Mapping Specification [7] with additional insight and clarification gained via electronic mail from the Mapping Team. Version 4.6 of the Mapping Specification [9] appeared as our work was being documented. References to 4.6 have been included in this report when it seemed useful or important to do so. The dynamic nature of the language proposals in this area has meant that Tartan's work has consisted of tracking the various proposals, designing and discussing possible implementations, and providing feedback to the Mapping Team as appropriate. No implementation of these features has been included in any of our prototype Ada 9X compilers. This work on tagged types is far from complete. In this report we document mainly the issues of compile-time representation and overload resolution, briefly discussing run-time representations. The requirements list does include most of the requirements for static semantic checking although we do not provide any implementation for these requirements. Anyone familiar with the problems of compiling the Ada programming language will be able understand the implementation issues discussed in this chapter of the report. 7.2. REQUIREMENTS The implementation requirements for type extension were derived from versions 4.0 and 4.6 of the Mapping Specification [7, 9]. Electronic mail from the Mapping Team provided additional information. As mentioned above, the primary baseline for this report is version 4.0. However, when a requirement derived from version 4.0 is changed by the rules of 4.6, two forms, both an old and a new, are given. Requirements that are new in version 4.6 of the Mapping Specification are not included. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-1 The requirements for type conversions have been left out entirely. We have not studied the 4.6 rules for conversion in detail and, due to the extensive changes, the 4.0 rules would not be merely obsolete, but would be misleading. The following is the list of implementation requirements for tagged types and type extension: TE-01: (VERSION 4.0) For each specific type T, there is an associated class-wide type, which is implicitly declared immediately after T, and which is denoted by the attribute T'CLASS. The root type of T'CLASS is T; the root type of a specific type is the type itself. (VERSION 4.6) When a tagged type T is declared, an associated class-wide type, denoted by T'CLASS, is implicitly declared. ... types are grouped into derivation classes, each formed by the root type for the class and its derivatives ... TE-02: A type definition for a record type may include the reserved word tagged. TE-03: The syntax for a private type declaration is now augmented to allow the specification of a tagged private type. TE-04: A record or private type is tagged ... if it is derived from a tagged type. TE-05: A [derived] tagged type may be extended with ... a record extension part ... A derived type defined in this way is called a type extension of its parent type. TE-06: A [derived] tagged type may be extended with ... a private extension part ... A derived type defined in this way is called a type extension of its parent type. TE-07: (VERSION 4.0) A [derived] tagged type may be extended with ... a ... discriminant part ... A derived type defined in this way is called a type extension of its parent type. (VERSION 4.6) A discriminant part may only be specified in a type declaration for a composite type that is not an array type [which includes tagged types]. For a tagged type, the discriminants specified in a derived type declaration need not be used to contrain the parent subtype. TE-08: For a tagged type, the primitive operations are called dispatching operations ... TE-09: The syntax for subprogram declarations is revised to allow "is <>", which means that the subprogram is abstract. TE-10: A subprogram with a formal parameter or result of a class-wide type may be explicitly declared. PAGE 7-2 TARTAN ADA 9X IMPLEMENTATION REPORT TE-11: A type T1 includes type T2 if and only if the set of values of T1 includes the values of T2. Two types overlap if one includes the other. TE-12: A specific type T includes only itself. A class-wide type T'CLASS includes the specific types T and its derivatives, and the associated class-wide type for each specific type in the class. TE-13: For a membership test of the form "X in S" where S is a subtype of type T, the type of X must overlap with T. TE-14: (VERSION 4.0) The ancestor of a type T is defined to be the type T itself, or any type from which T is derived, directly or indirectly. (VERSION 4.6) The ancestor of a specific type T or class-wide type T'CLASS is defined to be the type T itself, or any type from which T is derived, directly or indirectly. TE-15: Similar to Ada 83, a conversion between types is generally permitted if their root types share a common ancestor. TE-16: For overloadable entities, the definition of homograph is revised as follows: Two declarations of overloadable entities are homographs if they have the same identifier, operator symbol, or character literal, the same number of parameters and results, and if, according to the operand matching rules (see MS-3.3.3;4.0): - the result types (if any) could both match the same specific type; and - for each parameter position, a single specific type could match both formal parameters. [Note: This rule makes two declarations homographs if they are unresolvable even in a context that determines all specific operand and result types.] TE-17: If a formal parameter is not an access parameter, the type of the actual parameter matches the formal parameter if their types overlap, and if tagged, the formal type includes the root of the actual type. TE-18: The type of the operand of a qualified expression must match the base type of the type mark, as defined by the operand matching rules (see MS-3.3.3;4.0). TE-19: For an assignment, the assignment operation that is used is that of the root of the type of the left-hand side. In addition, the normal matching rules are used (see MS-3.3.3;4.0). TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-3 TE-20: For a type T, an allocator "new T" is overloaded on all access types designating types that include T. TE-21: If a formal is an access parameter (see MS-3.9;4.0), then the type of the actual parameter matches the formal if their designated types have the same root type, or, if tagged, the formal designated type includes the root of the actual designated type. TE-22: It is illegal to apply a constraint to a tagged class-wide type ... TE-23: A type extension part is allowed only for tagged types. TE-24: If a derived type declaration includes a discriminant part, then the parent subtype must be constrained, and the discriminants of the derived type are those given in the new discriminant part. TE-25: If a derived type declaration does not include a discriminant part, then the derived type has the same discriminants as the parent type, if any. TE-26: If a derived type declaration includes a type extension part, then the parent subtype must be constrained, and the values consist of the discriminants (if any), followed by the non-discriminant components of the parent type, followed by the components of the type extension part. TE-27: (VERSION 4.0) A derived type inherits the primitive operations of its parent type if that parent type is either the type of a formal parameter or the designated type of an access parameter. (VERSION 4.6) A derived type inherits the primitive operations of its parent type that are declared prior to the derivation, if that parent type is either the type of a formal parameter or the designated type of an access parameter. TE-28: If an explicitly declared primitive operation of a derived type is a homograph of an inherited operation, then the explicitly declared operation overrides the inherited one. TE-29: (VERSION 4.0) If a primitive operation of a parent type returns the parent type as a result, then if the parent type is not convertible to the derived type or if the conversion requires specifying additional components, then the inherited operation is abstract. (VERSION 4.6) If a dispatching operation returns the type as a result, then that operation must be overridden if it is inherited by a derived type. This is because conversion from the parent type to the derived type is undefined (see MS-4.6;4.6). PAGE 7-4 TARTAN ADA 9X IMPLEMENTATION REPORT TE-30: The parent type in a derived type definition must not be a class-wide type. TE-31: If a tagged type's parent is not limited, then any extension part must not be limited. TE-32: The scope level of a derived tagged type declaration must be the same as that of its parent type. TE-33: A primitive operation of a derived tagged type that overrides an inherited operation must be subtype conformant with the inherited operation. TE-34: Each object of a tagged class-wide type must be explicitly initialized, and is constrained thereafter to hold only values with tag and any discriminants matching those of its initial value. TE-35: (VERSION 4.0) It is illegal to declare an operation that is a primitive operation of more than one tagged type. (VERSION 4.6) If a single operation is a primitive for more than one tagged type, then in a given call, only one of the types may have actual controlling operands that are class-wide. TE-36: If a dispatching operation has a controlling result, but has no operand that determines a tag, then its controlling tag is chosen to match that required by its context, in order to avoid CONSTRAINT_ERROR. TE-37: If a tagged type has any primitive operations that are abstract, then it is called an abstract type, and it is illegal to create an object of that type, and a value of the type must only be produced via a "view" conversion (see MS-4.6(7);4.0). [Note: This disallows, for example, object declarations, allocators, aggregates, and return statements returning a conversion to the type.] TE-38: Overriding the components of a visible record type in the extension part is illegal. TE-39: In a record extension of a private type, a component in the extension part may have the same name as a component of the private parent part. TE-40: If T is a tagged class-wide type, then an allocator "new T" must specify an initial value. TE-41: A record aggregate for a type must not be used in a place where any extension part of the type is private (see MS-3.4.1). TE-42: An abstract subprogram must not have a body. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-5 TE-43: (VERSION 4.0) An abstract subprogram that is not a dispatching operation is not visible, and hence may not be called. (VERSION 4.6) Only a primitive operation of a tagged type may be declared abstract. TE-44: A formal parameter specified by an access parameter definition is an in parameter of an access parameter type (see MS-3.9;4.0). TE-45: If a private type declaration has a discriminant part, then the full type declaration must be a composite or derived type declaration with a conforming discriminant part (see MS-6.3.1;4.0). TE-46: If a private type declaration includes the modifier tagged, then the full type declaration must be tagged. TE-47: The declaration of a private type extension of a tagged parent type is allowed in the visible part of a package [only]. TE-48: (VERSION 4.0) For each private extension declared in the visible part of a package, a corresponding record extension (see MS-3.8.2;4.0) must be defined in the private part. (VERSION 4.6) For each private extension declared in the visible part of a package, a corresponding full type declaration must appear in the private part for a type derived (directly or indirectly) from the tagged parent type. 7.3. IMPLEMENTATION The changes to the Tartan Ada compiler necessary to support tagged types and type extension are contained in the Front End and Middle Pass portions of the existing compiler. When considering implementation schemes for tagged types it is useful to think in terms of their similarities to existing Ada features. This often allows existing compiler algorithms to be used with little or no modification for handling tagged types. Every tagged type is, underneath any hiding (privateness), a record type. The tag acts like a hidden discriminant. Layout and processing of tagged types may be handled in the compiler as a record type with an extra discriminant. There are differences of course; once set, the tag can never change since there is no equivalent of a whole-value assignment. The class-wide type associated with a tagged type is similar to an unconstrained array type. Such types cannot be used as the type of an uninitialized variable, an array element or a record component. Variables and heap-allocated objects of these types must be PAGE 7-6 TARTAN ADA 9X IMPLEMENTATION REPORT "constrained" (i.e. have the tag set) at creation. The tag/constraint is set at creation and may not be changed. The tag/constraint determines the object's size although it may not be known until run-time. On the other hand, there is no analog of a slice, so for class-wide types there is no construct which allows more than one tag/constraint to be applied to the same data. Thus, it is acceptable to store the tag as part of the value; only a single tag will ever apply to the value. 7.3.1. Compile-time Representation The introduction of tagged types and type extension into Ada means several new forms of abstract parse tree node are required, as well as new information to be stored in the nodes. (The word "node" will be used in the following implementation descriptions in place of the lengthier phrase "abstract parse tree node".) New node forms are generally associated with the new syntactic constructs. It is advantageous to have the new nodes mimic existing nodes that require similar processing in order to minimize the impact on existing processing routines. Some general comments about the internal structures of the Front End may be useful at this point. The compiler's symbol table is represented within the abstract parse tree. It exists as threads through the abstract parse tree. The node representing the declaration of an entity acts as the entity's representative in the symbol table. Strings used as identifiers are translated to more-easily-handled tokens (small integers) with the lexical table providing a translation between tokens and strings. The semantic checking and decoration of a tree node will be referred to as "semanticizing" the node. 7.3.1.1. Implementation of TE-01 (VERSION 4.0) For each specific type T, there is an associated class-wide type, which is implicitly declared immediately after T, and which is denoted by the attribute T'CLASS. The root type of T'CLASS is T; the root type of a specific type is the type itself. (VERSION 4.6) When a tagged type T is declared, an associated class-wide type, denoted by T'CLASS, is implicitly declared. ... types are grouped into derivation classes, each formed by the root type for the class and its derivatives ... The abstract parse tree node which represents type T'CLASS is constructed by the tree builder when the tree node for type T is constructed. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-7 The type declaration for T'CLASS is represented as a "dependent" type declaration: the type declaration node for T'CLASS is attached to the declaration node for type T. The declaration node for T'CLASS is only accessible via the declaration for type T. T'CLASS is not in the symbol table; it is looked up via T. It does not exist in the list of declarations that contains the declaration for T. The declaration for the class-wide type T'CLASS refers back to its corresponding specific type T so that, given a class-wide type, one can easily locate its root type declaration. No token need exist for T'CLASS in the lexical table. The name of the T'CLASS type declaration can simply be "T". Since it is not placed in the symbol table, no homograph conflicts will result. The fact that no token exists for T'CLASS saves space and time. If a token were created, then such a token would have to be created for every type that has a corresponding class-wide type. The additional tokens would use space and would slow symbol table lookups even for programs which do not refer to a class-wide types. This potential cost is somewhat reduced now that version 4.6 of the Mapping Specification defines class-wide types to exist only for tagged types (MS-3.4.1;4.6). When a type declaration is semanticized, the class-wide type associated with that type declaration is also semanticized. A class-wide type is a normal type declaration as far as semantic processing is concerned and is handled as such. In conjunction with the choice of representation for the type declaration T'CLASS, it was decided that a reference to type T'CLASS would be represented as an attribute node: a node for the attribute 'CLASS which has a child node referencing T. Since no token for type T'CLASS exists, a reference to type T'CLASS could not be represented as a simple name (as would a reference to other type declarations). Since references to T'CLASS are not likely to be abundant in application programs (they mostly occur in access type declarations, formal parameter type marks, and variable declarations), the small additional node space taken up by an attribute representation should not be detrimental. The semanticizing of the expression T'CLASS is similar to T'BASE in that both attributes denote a type. 7.3.1.2. Implementation of TE-02 A type definition for a record type may include the reserved word tagged. This is indicated by the following syntax: type_definition ::= . . . as in Ada 83 | [tagged] [limited] record_type_definition PAGE 7-8 TARTAN ADA 9X IMPLEMENTATION REPORT An example of a tagged record type is: package TAG_REC_PKG is type TAG_REC is tagged record -- tagged record type FIELD_1: integer; end record; end TAG_REC_PKG; Since all record type processing is applicable to tagged record types, tagged record types are represented using the same node type as record types, but with a flag set to indicate that the node is tagged. 7.3.1.3. Implementation of TE-03 The syntax for a private type declaration is now augmented to allow the specification of a tagged private type. This is indicated by the following syntax: private_type_declaration ::= type identifier [discriminant_part] is [tagged] [limited] private; An example of a tagged private type is: package TAG_PRIV_PKG is type TAG_PRIV is tagged private; -- tagged private type private type TAG_PRIV is ...; end TAG_PRIV_PKG; Tagged private types behave as other private types, therefore these nodes are represented as private type nodes with a flag set to indicate that they are tagged. 7.3.1.4. Implementation of TE-04 A record or private type is tagged ... if it is derived from a tagged type. A derived type that is derived from a tagged type but does not include a type extension part, is represented as a regular derived type node with a flag set to indicate that it is tagged. An example of such a type is: with TAG_REC_PKG; -- see implementation of TE-02 use TAG_REC_PKG; package PKG is type TAG_DER is new TAG_REC; -- tagged derived type with -- no extension end PKG; TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-9 7.3.1.5. Implementation of TE-05 A [derived] tagged type may be extended with ... a record extension part ... A derived type defined in this way is called a type extension of its parent type. A derived type whose parent type is tagged may include a record extension part. These types are referred to as "record extensions" or "record type extensions" (see MS-3.8.2;4.0 and MS-7.4.2;4.0). This type is a combination of a derived type and a record type, which is indicated by the syntax: derived_type_definition ::= new subtype_indication [type_extension_part] type_extension_part ::= with record_type_definition As a result, all derived type and record type processing must be done on these nodes. An example of a record type extension is: with TAG_REC_PKG; -- see implementation of TE-02 use TAG_REC_PKG; package REC_EXT_PKG is type REC_EXT is new TAG_REC with record -- record extension FIELD_2: integer; end record; end REC_EXT_PKG; A new kind of node is used to represent these types. The node is a copy of a derived type node, but with an additional field that points to a record type node representing the record extension part. Since the node representation is structurally similar to that of derived types, all of the compiler routines which process derived types can be utilized. The use of a standard record type node for the extension allows the normal record layout routines to process the extension with only slight modification. 7.3.1.6. Implementation of TE-06 A [derived] tagged type may be extended with ... a private extension part ... A derived type defined in this way is called a type extension of its parent type. A derived type whose parent type is tagged may include a private extension part. Such a type is referred to as "private extension" or "private type extension" (see MS-7.4.2;4.0). This type is a combination of a derived type and a private type and is indicated by the syntax: PAGE 7-10 TARTAN ADA 9X IMPLEMENTATION REPORT derived_type_definition ::= new subtype_indication [type_extension_part] type_extension_part ::= with [limited] private An example of a private extension is the following: with TAG_REC_PKG; -- see implementation of TE-02 use TAG_REC_PKG; package PRIV_EXT_PKG is type PRIV_EXT is new TAG_REC with private; -- private extension private type PRIV_EXT is new TAG_REC with record -- record extension FIELD_2: boolean; end record; end PRIV_EXT_PKG Like a derived type, a private extension has a parent type. Like a private type, it is only allowed in the visible parts of packages, and must have a corresponding full type declaration in the private part of the package (which must be a record extension (see requirement TE-48)). As a result, this node must have all derived type and private type processing done on it. A new kind of node was chosen to represent these types. It is a copy of a derived type node, with an additional field that points to the corresponding full type declaration in a manner similar to a private type node. 7.3.1.7. Implementation of TE-07 (VERSION 4.0) A [derived] tagged type may be extended with ... a ... discriminant part ... A derived type defined in this way is called a type extension of its parent type. (VERSION 4.6) A discriminant part may only be specified in a type declaration for a composite type that is not an array type [which includes tagged types]. For a tagged type, the discriminants specified in a derived type declaration need not be used to contrain the parent subtype. A derived type whose parent type is tagged may include a discriminant part. Discriminant parts are applicable to all derived types: "plain" derived types, those with record extensions, and those with private extensions. A discriminant part does not introduce a new node type. A field to hold a discriminant is available in all nodes for which a discriminant is allowed. Discriminant parts on derived types with record extensions require a special action. Recall that the node for such a type contains a record type declaration for the extension part. Since record type processing expects any discriminants to be part of the record type TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-11 declaration, the field in the record type declaration which normally holds the discriminant part must be made to refer to the discriminant part of the derived type node. Since Ada 83 already allows discriminants on private types, derived types with private extensions will have any discriminant processing done automatically since they are treated as private types. However, discriminants are not permitted in derived (record) types in Ada 83. Discriminant processing is new for derived types. Derived types and derived types with record extensions must be included in all discriminant processing. An example of a discriminant part in a record extension is: with TAG_REC_PKG; -- see implementation of TE-02 use TAG_REC_PKG; package PKG is type TAG_DER (DISC: natural) is -- record extension with new TAG_REC with record; -- new discriminant part FIELD_2: STRING(1..DISC); end record; end PKG; 7.3.1.8. Implementation of TE-08 For a tagged type, the primitive operations are called dispatching operations ... Every tagged type node contains a pointer to a list of its dispatching operations. This list only contains user-defined primitive operations, not basic or predefined. This list is created at the end of the declarative region which contains the declaration of the tagged type (or, using the Mapping Specification version 4.6 definition of "primitive operation", at the end of the package specification where the tagged type is declared). 7.3.1.9. Implementation of TE-09 The syntax for subprogram declarations is revised to allow "is <>", which means that the subprogram is abstract. Abstract subprograms are represented using the same node types as regular subprogram declarations, but a flag is set on the nodes to denote that they are abstract. As a result of this representation, no additional code is necessary for overload resolution. 7.3.1.10. Implementation of TE-10 A subprogram with a formal parameter or result of a class-wide type may be explicitly declared. The declaration of a subprogram must now allow a formal parameter's type mark to be a class-wide type. PAGE 7-12 TARTAN ADA 9X IMPLEMENTATION REPORT 7.3.2. Fundamental Primitives 7.3.2.1. Implementation of TE-11, TE-12, TE-13, TE-14, TE-15 A type T1 includes type T2 if and only if the set of values of T1 includes the values of T2. Two types overlap if one includes the other. A specific type T includes only itself. A class-wide type T'CLASS includes the specific types T and its derivatives, and the associated class-wide type for each specific type in the class. For a membership test of the form "X in S" where S is a subtype of type T, the type of X must overlap with T. (VERSION 4.0) The ancestor of a type T is defined to be the type T itself, or any type from which T is derived, directly or indirectly. (VERSION 4.6) The ancestor of a specific type T or class-wide type T'CLASS is defined to be the type T itself, or any type from which T is derived, directly or indirectly. Similar to Ada 83, a conversion between types is generally permitted if their root types share a common ancestor. In order to implement efficiently the includes and overlaps predicates, and hence type conversion and membership legality tests, two fields were added to all derived types: Level_Array and Level_Count. Level_Array is an array containing all ancestor types from which the type has been derived. Level_Count is the total number of ancestor types in the Level_Array. Level(0) contains the root ancestor type (i.e. the type from which the derived type is derived, but which is not itself a derived type). Level(1) contains the type derived from the root ancestor type; and so forth. Level(Level_Count-1) contains the parent type of the derived type. Type declarations which are not derived types do not contain a Level_Array since they do not have any ancestors. They do have a Level_Count which is always zero. Primitives to fetch the root and root ancestor of a type T are defined as follows: Root_Type(T) == if Is_ClassWide_Type(T) then T.Root else T end if Root_Ancestor(T) == if Is_Derived_Type(T) then T.Level_Array(0) else T end if TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-13 Useful predicates corresponding to the technical terms of the Mapping Specification are written as follows: Is_Ancestor_Of(T1, T2) == -- Is T1 an ancestor of T2 Is_Derived_Type(T2) and then T2.Level_Count > T1.Level_Count and then T1 = T2.Level_Array(T1.Level_Count) Is_Included_In(T1, T2) == -- Is T1 included in T2 if Is_Specific_Type(T2) then (T1 = T2) elsif Is_ClassWide_Type(T2) then Is_Ancestor_Of(Root_Type(T2), Root_Type(T1)) end if Overlaps(T1, T2) == Is_Included_In(T1, T2) or else Is_Included_In(T2, T1) Conversion between two types T1 and T2 is generally permitted if: Root_Ancestor(Root_Type(T1)) = Root_Ancestor(Root_Type(T2)) A membership test of the form "X in S", where S is a subtype of type T, is legal if: Overlaps(Type_Of(X), T) 7.3.2.2. Implementation of TE-16 For overloadable entities, the definition of homograph is revised as follows: Two declarations of overloadable entities are homographs if they have the same identifier, operator symbol, or character literal, the same number of parameters and results, and if, according to the operand matching rules (see MS-3.3.3;4.0): - the result types (if any) could both match the same specific type; and - for each parameter position, a single specific type could match both formal parameters. [Note: This rule makes two declarations homographs if they are unresolvable even in a context that determines all specific operand and result types.] As a result of this new definition, class-wide operations and primitive operations of the corresponding specific type can be homographs. Given a tagged type T, the following two declarations are homographic: procedure P(X: T); procedure P(X: T'CLASS); PAGE 7-14 TARTAN ADA 9X IMPLEMENTATION REPORT The routine in the compiler which determines if two declarations are homographs must be modified to detect this new case. With this change in place, the semantic check that disallows homographs in the same declarative region will flag the above example as being in error. 7.3.3. Overload Resolution A primary function of the Semantic Analyzer is to link each reference to an identifier to the node representing the declaration of the denoted entity as determined by the overload resolution rules of Ada. 7.3.3.1. Implementation of TE-17 If a formal parameter is not an access parameter, the type of the actual parameter matches the formal parameter if their types overlap, and if tagged, the formal type includes the root of the actual type. This new matching rule now allows a class-wide type to appear as the type of a formal parameter or as the type of an actual parameter. This dictates a change to the routine in the overload resolution algorithm which, given an actual parameter and a formal parameter, determines if the types of the two match. In Ada 83, the types matched if they were the same (RM-6.4.1(1)). In Ada 9X, the types match if they overlap, and if tagged, if the root of the type of the actual is included in the type of the formal. 7.3.3.2. Implementation of TE-18 The type of the operand of a qualified expression must match the base type of the type mark, as defined by the operand matching rules (see MS-3.3.3;4.0). In Ada 83, the rule was given by RM-4.7(3): The operand must have the same type as the base type of the type mark. The difference between the Ada 83 rule and the Ada 9X rule is that now the types do not have to be the same, they just have to "match". In terms of the Ada 9X matching rules (MS-3.3;4.0), this means that operand is the actual parameter, and the type mark is the formal parameter. Thus, the type of the operand and the base type of the type mark must overlap, and, if tagged, the base type of the type mark must include the root of the operand type. This permits qualified expressions with a type mark that denotes a class-wide type. In this case the expression must be another qualified expression in order to indicate the tag; it cannot be an aggregate. Overload resolution will process the expression with the expected type being the class-wide type and the new matching rules will do the right thing. Once the routine that determines if an actual matches a formal is modified according to the new matching rules (MS-3.3.3(4);4.0), TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-15 overload resolution of qualified expressions requires no additional changes. 7.3.3.3. Implementation of TE-19 For an assignment, the assignment operation that is used is that of the root of the type of the left-hand side. In addition, the normal matching rules are used (see MS-3.3.3;4.0). Electronic mail from the Mapping Team clarified the above. The mail stated that MS-5.2(1);4.0 is an overload resolution rule only and suggested that a better way of saying it might be to say the type of the right-hand side of an assignment operation must "match" (in the sense of MS-3.3.3;4.0) the root of the type of the left-hand side. This replaces the Ada 83 rule in RM-5.2(1): The named variable and the right-hand side expressions must be of the same type. The matching rule in MS-3.3.3(4);4.0 says that an actual parameter "matches" a formal parameter if their types overlap, and if tagged, the formal type includes the root of the actual type. In the following "left-hand side" is abbreviated as LHS, and "right-hand side" as RHS. The new rule states that the type of the RHS must match the root of the type of the LHS. In terms of the matching rule the type of the RHS is the actual parameter type, and the root of the type of the LHS is the formal parameter type. Thus, the root of the type of the LHS must include the root of the type of the RHS. Stated more specifically, this means that the LHS can be of a specific type or the class-wide type associated with that specific type, and the RHS can be of the same specific type or of the class-wide type associated with that specific type. This results in 4 possible combinations: 1. T := T 2. T := T'CLASS 3. T'CLASS := T 4. T'CLASS := T'CLASS Notice that this means that if the LHS is of a class-wide type, the RHS need not be a conversion to the class-wide type. Also notice that an expression of a class-wide type can be assigned to a variable of a specific type. (The controlling tag rules in MS-3.4.2;4.0 will ensure that the tag of the class-wide type on the RHS is the tag of the specific type on the LHS.) PAGE 7-16 TARTAN ADA 9X IMPLEMENTATION REPORT In overload resolution of assignment statements, for each possible binding of the LHS, it must be determined if there is a matching binding for the RHS. Each possible binding for the LHS is used as the desired type when looking for a possible RHS binding. This processing has to be modified to use the root type of the LHS binding as the expected type of the RHS. This is due to the fact that the assignment operation is defined for the specific type; class-wide actuals are permitted via the matching rules in MS-3.3.3;4.0. 7.3.3.4. Implementation of TE-20 For a type T, an allocator "new T" is overloaded on all access types designating types that include T. In Ada 83, this rule would read: An allocator "NEW T" is overloaded on all access types designating type T. The difference between the Ada 83 rule and the Ada 9X rule is that the access type can designate not only T, but all types that include T. In Ada 83, overload resolution of allocators considered all possible access types with T as the designated type and that were visible at the point of the allocator. Now, overload resolution must consider all visible access types which designate a type that includes the type T. 7.3.4. Run-time Representation The several reformulations of tagged types and type extension that have taken place during the mapping process have mostly dealt with changing the way the semantic rules are described. The run-time representation of objects and values of tagged types has been largely unaffected by these changes. The basic scheme is to treat a tagged type as a record type with a special discriminant, the tag. A tag is stored in every value of a tagged type. A value of a tagged type is the tag followed by "extension records", that is, records containing the fields defined in each extension part. The layout of an extension record is computed the same way as the layout of an Ada 83 record. On certain target architectures, pad fields may or must be added to force a desirable or required memory alignment. An extension with a dynamic size causes a level of indirection in accessing the fields of additional extensions. Figure 7-1 provides an example. A tag value for a type T is the address of a block containing a transfer vector for the dispatching operations of T plus information about ancestor types. The transfer vector contains entries for inherited dispatching operations plus entries for the dispatching operations defined for T. Entries are also made for two implicit dispatching operations, 'ASSIGN and 'SIZE. Dispatching to the 'SIZE TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-17 +---------------+ -+ -+ -+ type Arr is | Tag | | | | array (Integer range <>) of Integer; |---------------| | | | | Size of T0 | | | | subtype D_Size is Integer range 1 .. 100; |---------------| | | | | DISC | | | | type T0(DISC: D_Size := 0) is tagged |---------------| T0 | | record | A offset | | | | A: Arr(1 .. DISC); |---------------| | | | B: Integer; | B | | T1 | end record; |---------------| | | | | Data | | | | type T1 is new T0 with | for A | | | | record |---------------| | | T2 C: Arr(1 .. FUNC(23)); | Pad (optional)| -+ | | D: Integer; |---------------| | | end record; | C offset | | | |---------------| | | type T2 is new T1 with | D | | | record |---------------| | | E, F: Integer; | Data | | | end record; | for C | | | |---------------| | | | Pad (optional)| ----+ | |---------------| | | E | | |---------------| | | F | -------+ +---------------+ FIGURE 7-1: Extended Record Type Representation of a class-wide object computes the current size of the value of the object. This is useful for, among other things, implementing the equality and inequality operations. The additional information in a tag consists of an integer, called the level, indicating the number of ancestor types and a vector containing the tags of the ancestor types, if any. Figure 7-2 shows this representation graphically. PAGE 7-18 TARTAN ADA 9X IMPLEMENTATION REPORT +---------------+ | N | Level |---------------| T'TAG: | T0'TAG | -+ |---------------| | | T1'TAG | | Ancestors (0 .. N) |---------------| | | ... | -+ |---------------| | 'ASSIGN | |---------------| | 'SIZE | |---------------| | OP1'ADDRESS | -+ |---------------| | T0'CLASS Operations | OP2'ADDRESS | -+ |---------------| | OP3'ADDRESS | -+ |---------------| | T1'CLASS Operations | OP4'ADDRESS | -+ |---------------| | ... | |---------------| | OPk'ADDRESS | +---------------+ FIGURE 7-2: Tag Representation One of the interesting operations defined for tagged types is a new form of membership test. The following code fragment shows how these tests may be implemented using the representation for tags described above: -- Consider the following declarations: type T0 is tagged record ... ; type T1 is new T0 with ... ; X: T0'CLASS := ... ; -- X in T1 translates to the following: X'TAG = T1'TAG -- X in T1'CLASS translates to the following: (X'TAG = T1'TAG) or else ((X'TAG.Level > T1'TAG.Level) and then (X'TAG.Ancestors(T1'TAG.Level) = T1'TAG)) 7.4. CONCLUSIONS The changes necessary to support tagged types and type extension are confined to the Front End and Middle Pass portions of the compiler. The impact of the matching rules for class-wide types on overload resolution algorithms is pleasantly small. TARTAN ADA 9X IMPLEMENTATION REPORT PAGE 7-19 The implementation of tagged types and related constructs can often share processing with similar constructs in Ada 83. The Ada 9X OOP proposals have shown steady improvement during the mapping and revision process. It is clear that Ada 9X will offer state-of-the-art support for object-oriented programming. PAGE 7-20 TARTAN ADA 9X IMPLEMENTATION REPORT REFERENCES 1. Ada 9X Implementation Modules, Volume I. Intermetrics, Inc., January, 1991. 2. Ada 9X Implementation Modules, Volume II. Intermetrics, Inc., April, 1991. 3. Ada 9X Implementation Modules, Volume III. Intermetrics, Inc., May, 1991. 4. i960MC Microprocessor Reference Manual. Intel Corporation, 1991. 5. Reference Manual for the Ada Programming Language. ANSI/MIL-STD-1815A, United States Department of Defense, 1983. 6. Ada 9X Mapping Document, Volume I, Mapping Rationale. Version 4.1, Office of the Under Secretary of Defense for Acquisition, March, 1992. 7. Ada 9X Mapping Document, Volume II, Mapping Specification. Version 4.0, Office of the Under Secretary of Defense for Acquisition, December, 1991. 8. Ada 9X Mapping Document, Volume II, Mapping Specification Annexes. Version 4.1, Office of the Under Secretary of Defense for Acquisition, March, 1992. 9. Ada 9X Snapshot of Mapping Specification Prior to Revision. Version 4.6, Intermetrics, Inc., April, 1992. 10. ACVC and ACEC Test Recommendations. Tartan, Inc., June, 1992. INDEX INDEX ACVC Tests 1-4 Current_Handler 4-6 Asynchronous Transfer of Control Data Structures 4-4 3-1 Definitions 4-1 Compilation Costs 3-6 Delivery 4-1, 4-5 Cost of Implementation 3-5 Design and Implementation Delay Expiration 3-5 4-4 Design Constraints 3-1, 3-4 Detach 4-5, 4-6 Distributed Overhead 3-6 Generation 4-1 Hard Real-Time versus Soft Hardware Interrupt Table 4-4 Real-Time 3-7 Initial Interrupt Table 4-4 Introduction 3-1 Interrupt 4-1 Non-Deterministic Space 3-6 Interrupt Handler Binding Non-Deterministic Time 3-6 4-1 Queue Algorithms and Elements Interrupt Id 4-4 3-2 Interrupt Priority 4-4 Runtime System Maturity 3-6 Interrupt Stack 4-7 Interrupt Table 4-7 Entry Queuing Policies 5-1 Is_Attached 4-6 Algorithms 5-3 Is_Reserved 4-6 Conclusions and Recommen- Pending 4-1 dations 5-5 Performance 4-7 Data Structures 5-2 Protected Memory 4-6 Design and Implementation Requirements 4-1 5-2 Reserved 4-1 Dynamic Priorities 5-3 Scope 4-1 Entry Queues 5-3 Software Interrupt Table 4-4 Entry Queuing Algorithms 5-3 Introduction 1-1 Performance 5-5 pragma QUEUING_POLICY 5-1 Librarian 1-2 Priority Subtypes 5-3 Impact of Hierarchical Requirements 5-1 Libraries 6-1, 6-5 Scope 5-1 Mapping Team 1-1, 1-5, 2-2, Front End 1-2 4-1, 5-1, 7-1, 7-16 Impact of Hierarchical Middle Pass 1-2 Libraries 6-1, 6-4 Impact of Tagged Types 7-6 Impact of Tagged Types 7-6 Multi-Way Select Statement 3-1 Internal Structures 7-7 Compilation Costs 3-6 Cost of Implementation 3-5 Hierarchical Program Libraries Delay Expiration 3-5 6-1 Design Constraints 3-1, 3-3 Conclusions 6-23 Distributed Overhead 3-6 Implementation 6-6 Hard Real-Time versus Soft Requirements 6-1 Real-Time 3-7 Introduction 3-1 Interrupts 4-1 Non-Deterministic Space 3-6 Algorithms 4-4 Non-Deterministic Time 3-6 Architectural Issues 4-6 Queue Algorithms and Elements Attach 4-5 3-2 Blocked 4-1 Runtime System Maturity 3-6 Conclusions and Recommen- dations 4-7 Object-Oriented Programming (OOP) 7-1, 7-20 Overload Resolution 6-13, 6-15, Reference Notation 1-5 7-12, 7-15 Language Reference Manual 1-5 Protected Architectures 1-2 Mapping Specification 1-5 1750A Extended Mode 1-3 Requeue 2-1, 2-18 i960MC 1-3 Definitions 2-1 Protected Types 2-1 Requirements 2-2 Algorithms 2-12 Scope 2-1 Barrier Expression 2-1 To Other 2-18 Common Epilogue 2-2, 2-17 To Self 2-18 COUNT Attribute 2-18 Creation 2-12 Tagged Types 7-1 Data Structures 2-8 Conclusions 7-19 Definitions 2-1 Implementation 7-6 Design and Implementation Requirements 7-1 2-8 Tartan Ada Compiler Entry Barriers 2-16 Compiler Architecture 1-2 Entry Bodies 2-16 Front End 1-2, 6-1, 6-4, Entry Epilogue 2-17 7-6, 7-7 Epilogue 2-2 Librarian 1-2, 6-1, 6-5 Finalization 2-15 Middle Pass 1-2, 7-6 Lock 2-2 Targeted to i960MC 1-1 PRCB 2-11 Type Extension 7-1 PRD 2-10 Conclusions 7-19 Procedure Epilogue 2-17 Implementation 7-6 Prologue 2-2, 2-15 Requirements 7-1 Protected Operation 2-1 Protected Action 2-1 Protected Data Components - PRD 2-10 Protected Object Control Block - PRCB 2-11 Protected Type Structure - PRTS 2-9 PRTS 2-9 Requirements 2-2 Scope 2-1 Singleton 2-2 TRUE Barrier 2-1 Protected Types and Requeue Algorithms 2-12 Architectural Issues 2-19 Barrier Optimizations 2-21 Conclusions and Recommen- dations 2-21 Data Structures 2-8 Integration with the RTS and Ada 83 2-18 Low-Level Locks 2-20 Optimizations 2-20 Performance 2-19 Procedure Optimizations 2-21 Protected Region 2-20 Task Stack 2-20 ADA 9X PROJECT: USER/IMPLEMENTER DEMONSTRATION PROGRAM PART 2: USER REPORT OCTOBER 20, 1992 Change Evaluation Report for the Ada 9X User/Implementer Subproject Contract No. 91-9X-001 SDRL Sequence No. S005 June 1992 Prepared for: Tartan Inc. 300 Oxford Drive Monroeville, PA 15146 Prepared by: TRW Avionics & Surveillance Group Dayton Engineering Laboratory 4021 Executive Drive Beavercreek, Ohio 45430 D.L. Nichols P.C. Handorf TABLE OF CONTENTS PAGE 1. Introduction .......................................................... 1 2. User Evaluation/Feedback .............................................. 1 2.1 Application Benchmarking ............................................. 2 2.1.1 Benchmark Origin ................................................... 2 2.1.1.1 Digital Avionics Information System (DAIS) ....................... 2 2.1.1.2 Ada Avionics Real-Time Software (AARTS) .......................... 3 2.1.2 Benchmark Description .............................................. 5 2.1.3 Benchmark Version #1 ............................................... 7 2.1.3.1 Baseline ......................................................... 7 2.1.3.2 Re-Engineering ................................................... 11 2.1.3.3 Results .......................................................... 11 2.1.4 Benchmark Version #2 ............................................... 15 2.1.4.1 Baseline ......................................................... 15 2.1.4.2 Re-Engineering ................................................... 16 2.1.4.3 Results .......................................................... 16 2.1.5 Benchmark Version #3 ............................................... 17 2.1.5.1 Baseline ......................................................... 17 2.1.5.2 Re-Engineering ................................................... 18 2.1.5.3 Results .......................................................... 20 2.1.6 Benchmark Version #4 ............................................... 22 2.1.6.1 Baseline ......................................................... 22 2.1.6.2 Re-Engineering ................................................... 22 2.1.6.3 Results .......................................................... 23 2.1.7 Benchmark Version #5 ............................................... 23 2.1.7.1 Baseline ......................................................... 23 2.1.7.2 Re-Engineering ................................................... 24 2.1.7.3 Results .......................................................... 24 2.1.8 Benchmark Version #6 ............................................... 25 2.1.8.1 Baseline ......................................................... 25 2.1.8.2 Re-Engineering ................................................... 25 2.1.8.3 Results .......................................................... 26 2.2 Other Benchmarking ................................................... 27 2.2.1 Device Communication Benchmark ..................................... 27 2.2.2 Semaphore Comparison ............................................... 31 2.2.2.1 Description ...................................................... 31 2.2.2.2 Results .......................................................... 34 3. ACEC .................................................................. 35 3.1 Baseline Development ................................................. 35 3.2 Test Descriptions .................................................... 37 3.2.1 PROT_REC_NEW1 ...................................................... 37 3.2.2 PROT_REC_NEW2 ...................................................... 37 3.2.3 PROT_REC_NEW3 ...................................................... 37 3.2.4 PROT_REC1 .......................................................... 42 3.2.5 PROT_REC2 .......................................................... 42 3.2.6 PROT_REC3 .......................................................... 42 3.2.7 PROT_REC4 .......................................................... 42 3.2.8 CRITICAL_REGION_TEST_NEW1 .......................................... 42 3.2.9 DYN_PRI_NEW1 ....................................................... 48 3.2.10 EVENT_TEST_NEW1 ................................................... 48 3.2.11 EVENT_TEST_NEW2 ................................................... 48 3.2.12 EVENT_TEST_NEW3 ................................................... 53 3.2.13 LOCK_TEST_NEW1 .................................................... 53 3.2.14 QUEUING_NEW1 ...................................................... 53 3.2.15 QUEUING_NEW2 ...................................................... 53 3.2.16 INTRPT_NEW1 ....................................................... 53 3.2.17 INTRPT_NEW2 ....................................................... 62 3.2.18 Results ........................................................... 62 3.3 Recommendations ...................................................... 62 4. Conclusions ........................................................... 68 4.1 Application Benchmark Analysis ....................................... 68 4.2 Semaphore Implementation Analysis .................................... 70 4.3 General Protected Record Analysis .................................... 70 LIST OF FIGURES FIGURE TITLE PAGE 1 Application Benchmark Data Flow................................. 6 2 Sequencing of Periodic Applications............................. 9 3 Scheduler Specification for Benchmark Version #1................ 9 4 Scheduler Body for Baseline Benchmark Version #1................ 10 5 Re-Engineered Portions of Scheduler Body - Variation #1......... 12 6 Re-Engineered Portions of Scheduler Body - Variation #2......... 13 7 Re-Engineered Portions of Scheduler Body - Entry Families....... 14 8 Lock Implemented with Ada 83 Tasking............................ 15 9 Lock Implemented as a Protected Record.......................... 16 10 Event Implementation Using Tasking.............................. 17 11 INS Application Code Template................................... 18 12 Baseline Implementation of the GUIDANCE Application............. 19 13 Event Implementation Using Protected Records.................... 20 14 Re-Engineered Portions of the GUIDANCE Application.............. 21 15 Benchmark Version #4 Task Type Declaration...................... 22 16 INTERRUPT_EVENT Implemented as a Task Type...................... 25 17 SIMULATION_CONTROL Loop Modified to Raise Interrupt............. 25 18 INTERRUPT_EVENT Implemented as a Protected Type................. 26 19 PI-Bus CRITICAL_SERVICES Protected Record Type.................. 29 20 Counting Semaphore Implemented Using Protected Records.......... 31 21 Counting Semaphore Implemented Using Rendezvous................. 32 22 Counting Semaphore Implemented Using Direct Runtime Calls....... 33 23 ACEC Test "PROT_REC_NEW1"....................................... 38 24 ACEC Test "PROT_REC_NEW2"....................................... 39 25 ACEC Test "PROT_REC_NEW3"....................................... 40 26 ACEC Test "PROT_REC1"........................................... 43 27 ACEC Test "PROT_REC2"........................................... 44 28 ACEC Test "PROT_REC3"........................................... 45 29 ACEC Test "PROT_REC4"........................................... 46 30 ACEC Test "CRITICAL_REGION_TEST_NEW1"........................... 47 31 ACEC Test "DYN_PRI_NEW1"........................................ 49 32 ACEC Test "EVENT_TEST_NEW1"..................................... 50 33 ACEC Test "EVENT_TEST_NEW2"..................................... 52 34 ACEC Test "EVENT_TEST_NEW3"..................................... 54 35 ACEC Test "LOCK_TEST_NEW1"...................................... 56 36 ACEC Test "QUEUING_NEW1"........................................ 57 37 ACEC Test "QUEUING_NEW2"........................................ 59 38 ACEC Test "INTRPT_NEW1"......................................... 61 39 ACEC Test "INTRPT_NEW2"......................................... 63 LIST OF TABLES TABLE TITLE PAGE I Application Benchmark Version Summary........................... 7 II Period/Phase Examples........................................... 8 III Benchmark Version #1 Results.................................... 14 IV Benchmark Version #2 Results.................................... 16 V Benchmark Version #3 Results.................................... 21 VI Benchmark Version #4 Results.................................... 23 VII Benchmark Version #5 Results.................................... 24 VIII Benchmark Version #6 Results.................................... 26 IX Semaphore Comparison Results.................................... 34 X ACEC Execution Results.......................................... 64 LIST OF APPENDIXES APPENDIX TITLE PAGE A Compile Times for Benchmark Version #1...................... 73 B Compile Times for Benchmark Version #2...................... 75 C Compile Times for Benchmark Version #3...................... 77 D Compile Times for Benchmark Version #4...................... 79 E Compile Times for Benchmark Version #5...................... 81 F Compile Times for Benchmark Version #6...................... 83 1. Introduction This report describes the work performed by TRW under subcontract to Tartan in support of the Ada 9X Project: User/Implementer Demonstration Program. It provides user feedback to proposed Ada 9X language features and recommends enhancements to the Ada Compiler Evaluation Capability (ACEC) for testing these features. Feedback is provided from the perspective of an Ada user in the real-time embedded Avionics and Space application domain. Data in this report is based primarily on our hands-on evaluation of proposed language changes implemented by Tartan. This report contains four sections. This introduction is Section 1. Section 2 describes our approach to evaluating the proposed language changes, including discussions of the application benchmarks and other noteworthy benchmarks used in the evaluation. Section 2 also contains evaluation results. Section 3 contains our recommendations for ACEC enhancement. Concluding remarks are provided in Section 4. The focus of the evaluation addressed by this report is on the language features implemented by Tartan and provided to TRW. These include protected records, interrupts, child libraries, queuing policies (priority and FIFO) and dynamic priorities. The implementations of these features are based on the descriptions provided in the Ada 9X Mapping Document [1]. 2. User Evaluation/Feedback The evaluation approach used by TRW incorporates benchmarking as the primary method of evaluating proposed language features. We concentrated our efforts on adapting software from existing embedded computer systems for use as an application benchmark. A few other benchmarks were also used to help evaluate more specific aspects of the language. The application and other benchmarking activities, their results, and supporting software are described in the following paragraphs. The target processor used for our benchmarking is a bare-board (no operating system) Intel EXV-960MC single board computer which is based on an i960MC microprocessor running at 25 MHz. The board is configured with 256K bytes of high-speed Static Random-Access Memory (SRAM) and 4M bytes of Dynamic Random- Access Memory (DRAM). A RS-232C interface connects the target to a VAX 3900 host computer controlled by the VMS operating system. Software is built on the host using the Tartan Ada VMS/960MC Ada tool set and then downloaded and executed on the target using AdaScope, Tartan's interactive debugger. Various releases of Tartan's tool sets were used as they became available during the evaluation, including Version 4.1 Pre-Release, Ada 9X Modified Compilers #1, #2, #3 and #4 as well as several maintenance updates. Timing of benchmarks was accomplished using various self-timing techniques that use CALENDAR.CLOCK as the time source. All the Ada 9X timing results published in this report were collected against the Ada 9X Modified Compiler #4. 2.1 Application Benchmarking 2.1.1 Benchmark Origin Our application benchmark was derived from an Operational Flight Program (OFP) developed for the Air Force Wright Research and Development Center (WRDC) for execution in the Integrated Test Bed (ITB) laboratory located at Wright Patterson Air Force Base, Ohio. This OFP was first developed as part of the Digital Avionics Information System (DAIS) and later adapted for use in the Ada Avionics Real-Time Software (AARTS) system. Both of these systems support a laboratory environment where technologies are developed, integrated, evaluated, and transitioned to "real-world" development and retrofit programs. They are not flight qualified nor tailored to any specific aircraft but rather derived from generic application functions of existing aircraft implementations. To support our application benchmarking activities, we ported a subset of the OFP to the EXV-960MC target processor. Once porting was completed, we re-engineered the benchmark to take advantage of language changes proposed by Ada 9X. The primary emphasis in our re-engineering activities has been on the real-time language features, most notably protected records and the binding of protected procedures to hardware interrupts. The Ada 83 and Ada 9X implementations of this benchmark provide a basis for comparing proposed language features against existing ones. 2.1.1.1 Digital Avionics Information System (DAIS) The DAIS OFP uses proven technologies and is representative of many embedded computer systems currently in use. It performs the functions of system control, navigation, steering, weapon delivery, and control of sensors, controls, and displays. It was was developed in JOVIAL during the late 1970's and early 1980's for execution in a target environment containing MIL-STD-1750 processors using a MIL-STD-1553B bus for external communications. The system is controlled by a custom executive that provides real-time task control, interprocessor communication, remote terminal communication and mass memory services. The DAIS system uses the MIL-STD-1553B bus for communication between processors and with external devices. The MIL-STD-1553B bus is a serial data bus which uses command/response protocol directed by a static bus controller. In the ITB laboratory, the MIL-STD-1553B bus serves as an interface to a simulated avionics environment consisting of sensor systems and a cockpit equipped with pilot controls and displays. Control of DAIS is provided by a real-time executive that implements periodic deadline scheduling as its primary scheduling policy. Statically defined sets of periodic tasks and bus commands are executed within rigid cyclic frames. A small number of aperiodic tasks and bus commands also exist. These are statically defined also. All periodic tasks and bus commands are expected to complete within the time frame in which they are scheduled. Failure to do so constitutes a missed deadline and causes the remaining processing for the frame to be canceled and a new frame started. Missed deadlines are considered fault conditions and may occur frequently during testing of new or modified software configurations until the timing intricacies are worked out. By executing tasks in rigid time frames, the interactions between tasks, data access, and I/O are minimized. Software takes advantage of this inherent synchronization to reduce the need to explicitly enforce mutual exclusion. A scheduling sequence is established which insures that tasks do not access data concurrently and that tasks do not access data which is being updated from external devices. Strict sequencing also enhances the system predictability and repeatability. 2.1.1.2 Ada Avionics Real-Time Software (AARTS) The Ada Avionics Real-Time Software (AARTS) system implements much of the same functionality as DAIS and additionally satisfies many of the advanced requirements placed on modern embedded computer systems. The AARTS system supports the PAVE PILLAR avionics architecture [2], employing the concepts of common modules, pooled spares, fault tolerance, and dynamic reconfiguration of software and hardware resources. Control is provided by a custom executive that supports interprocess communication, communication with remote avionics devices, mass memory services, status monitoring, fault detection, isolation and recovery, error logging, and dynamic reconfiguration. The AARTS executive is implemented mostly in Ada with several design trade-offs made to achieve performance at the expense of portability. The application programs used for demonstrating the AARTS system are a subset of the DAIS OFP that have been translated to Ada and for compatibility with the AARTS executive. The target environment supported by AARTS consists of multiple distributed Very High Speed Integrated Circuit (VHSIC) MIL-STD-1750A processors configured into processing clusters. A redundant PI-Bus backplane is used as the primary bus for communicating within each cluster and two redundant High Speed Data Buses (HSDB's) are used for communicating between clusters and to the rest of the avionics environment. A MIL-STD-1553B bus is also supported to provide access to a larger variety of devices. This target architecture supports the dynamic nature of the AARTS system. Communication services are provided by the executive to enable applications to communicate with each other without regard to their current mapping to processors and clusters, and to communicate with external devices such as sensor systems and cockpit displays. The communication interface is message based. Applications identify messages to the executive using logical message identifiers which are used to make dynamic message routing decisions based on the system configuration in effect. This eliminates the need for application programs to be aware of physical locations of the sources and destinations of their messages. This is important because these locations are subject to change as a result of dynamic reconfiguration. Application functions are partitioned into multiple, loosely coupled Ada programs which may be distributed among processors residing in one or more clusters. Ada programs are used as the elementary unit for reconfiguration purposes. Multiple Ada programs may co-exist in a single processor, which enables the software configuration of a processor to be partially changed without having to reconfigure the entire processor. Loading and unloading of Ada programs is performed during system startup and shutdown and dynamically in response to mission mode changes and fault conditions. Scheduling of tasks and bus transfers in AARTS is substantially different from DAIS. Unlike the MIL-STD-1553B bus used as the primary bus for DAIS, mastership of the PI-Bus and HSDB is dynamically passed among nodes. The AARTS system takes advantage of this to implement a communication capability where messages are transferred upon request rather than at predefined time intervals. Application programs contain Ada tasks which are scheduled by the Ada runtime, often in response to requests by the executive. Typical application tasks in AARTS are data driven, suspending at an executive service call until a requested message arrives, processing the message, transmitting the processed data in another message, and then requesting a service to await the next message arrival. In some instances, data arrivals are periodic and these result in periodic task executions. However, the executive makes scheduling decisions based on the arrival of the message rather than on pre- defined time frames as in DAIS. The DAIS and AARTS systems support similar functionality but do so using the substantially different control strategies described above. The control strategies used for DAIS are not readily adapted to dynamic reconfiguration, which is a severe drawback for some modern embedded computer systems. However, they do provide strict control of task sequencing which produces systems that are repeatable and consequently easier to verify. The control strategies used in the AARTS system, on the other hand, were designed to support dynamic reconfiguration. The implementation of the AARTS application functions as discrete, separately linked Ada programs consisting of tasks that compete based on their priority simplifies the process of modifying or adding application functions. In DAIS, such changes may require re-mapping of a large number of tasks and bus traffic to new cyclic frames due to their impact on the delicate timing dependencies. This is especially prevalent when applications depend on the inherent synchronization attributable to the periodic deadline scheduler. Both of these system approaches offer their own advantages and disadvantages and are representative of many systems within the real-time Avionics and Space application domain. 2.1.2 Benchmark Description The application benchmark is a subset of the DAIS/AARTS OFP that performs Navigation and Guidance computations based on inputs from sensors. It consists of five primary processing elements which are assigned the following names: SIM, AD, INS, NAV, and GUI. The relationships of the five processing elements are shown in Figure 1. The SIM element is a software simulation of sensors that provide Air Data (AD) and Inertial Navigation System (INS) data. It was not part of the OFP but rather implements the interfaces necessary to execute the benchmark outside the ITB laboratory environment. The other four processing elements were all adapted from the OFP. The AD and INS elements accept the raw sensor data from SIM and convert it from a scaled-integer format into appropriate units (e.g. REAL data types). The NAV component uses the INS values to compute data such as current aircraft position, directions, and velocities. The GUI component computes the steering and command data (command roll, command pitch, indicated air speed) necessary to guide the aircraft along a flight path defined by a set of waypoints. Each waypoint is expressed in terms of its latitude, longitude, and altitude and represents a location on the flight path. The results of GUI are provided back to SIM which simulates the effects their implementation would have on the sensors. This sequence repeats continually while the computed aircraft position, and other state information, is modified following the flight path. The CPU utilization observed during application benchmark execution is measured and used as a basis for comparing versions implemented exclusively with Ada 83 language features against those incorporating Ada 9X features. Measurement of CPU utilization is performed by a self-calibrating task called FREE_TIME which executes at the lowest priority and consumes all CPU time not used by the rest of the benchmark. Time spent executing in this task is considered unused CPU time for the purposes of this measurement. The FREE_TIME task first establishes a calibration value by timing a specific instruction sequence. Next, it repeatedly executes this instruction sequence in background mode keeping an iteration count of the number of times the sequence is completed. This iteration count is used in conjunction with the calibration value to calculate CPU utilization for a given benchmark execution period. The results are reported using package TEXT_IO. The interpretation of this data is straightforward. As the benchmark software is implemented in a more efficient manner, the percent of CPU utilized to perform the same set of processing decreases. Hence, the efficiency of the code in the simulation is maximized when the percent of CPU utilized is minimized. INS +---> Sensor ---> INS ---> INS ------------------+ | Data Data | | | | | | | | | | | V NAV V | NAV ---> State ---> GUIdance | ^ | ^ | | | | | AD | | | SIM ---> Sensor ---> AD ---> AD ---------------+ | +--- Waypoint ^ Data Data | Data | | | | | Command/ | +------------------------- Steer <-------------+ Data Figure 1. Application Benchmark Data Flow Adapting a subset of the OFP for execution as a benchmark on the i960MC target hardware required several changes to the software. Due to architectural differences between the ITB laboratory environment which serves as the target for the OFP and the target processor used for Ada 9X, neither the DAIS nor AARTS executives were incorporated into the executable benchmark. Instead, executive functionality was either eliminated or replaced by portable Ada code. The applications, originally distributed across multiple Ada programs in the AARTS version of the OFP, were collapsed into a single program. An i960-specific math library was developed to replace the MIL-STD-1750A math library used in the original OFP. Once the benchmark was adapted for execution on the i960 target, multiple versions were constructed to support evaluation of the Ada 9X language features. These versions are summarized in Table I. Each version consists of a baseline implementation, which is limited to only Ada 83 language features, and a re-engineered implementation which takes advantage of Ada 9X language features as implemented by Tartan. Version #1 is based on DAIS concepts including a periodic deadline approach to scheduling application tasks. Version #2 is similar to Version #1 but includes asynchronous tasks in addition to the periodic deadline scheduled tasks. Version #3 is based on concepts from the AARTS system including the use of data arrival as the primary event for scheduling application tasks. Versions #4, #5 and #6 are similar to Versions #1, #2 and #3 respectively but use hardware interrupts to signal the start of a new cycle or, in the case of Version #6, the availability of new sensor data. Each of these versions are described in more detail in the following paragraphs along with their evaluation results. Version Concept Model Primary Scheduling Approach 1 DAIS Periodic Deadline 2 DAIS Periodic Deadline w/ Async. 3 AARTS Data Driven 4 DAIS Periodic Interrupt w/ Deadline 5 DAIS Periodic Interrupt w/ Deadline and Async. 6 AARTS Data and Interrupt Driven Table I. Application Benchmark Version Summary 2.1.3 Benchmark Version #1 The purpose of Benchmark Version #1 is to evaluate the benefit of protected records in a DAIS-like environment where periodic deadline scheduling is used. This benchmark depends on the scheduling of tasks within strict time frames to enforce mutually exclusive access to critical data structures shared between application tasks. 2.1.3.1 Baseline The baseline implementation of Application Benchmark Version #1 contains a periodic task scheduler implemented using task entries. For the purpose of scheduling periodic tasks, time is divided into frames which are further subdivided into cycles. The number of cycles in a frame is static and defined as a power of two. Frames are duplicated one after another. Periodic tasks are mapped to one or more cycles within a frame by defining their period and phase. The period of a task is the number of cycles between desired dispatches and must be a power of two between one and the number of cycles in the frame. A task's phase is the cycle number, relative to the start of the frame, of the first cycle when the task is to be dispatched. The legal phases corresponding to a given period consist of the integer values from zero to one less than the period. Examples of legal period and phase combinations are provided in Table II. Period Phase Dispatched 1 0 Every cycle 2 0 Every 2nd cycle starting with the 1st cycle of each frame 1 Every 2nd cycle starting with the 2nd cycle of each frame 4 0 Every 4th cycle starting with the 1st cycle of each frame 1 Every 4th cycle starting with the 2nd cycle of each frame 2 Every 4th cycle starting with the 3rd cycle of each frame 3 Every 4th cycle starting with the 4th cycle of each frame Table II. Period/Phase Examples Our benchmark contains a task called DEADLINE_DATA that advances cycles, schedules periodic applications within cycles, and enforces deadlines to ensure tasks are only executed within the cycles identified by their period and phase. The DEADLINE_DATA task relies on an Ada delay statement to suspend until it is time to start a new cycle, which occurs every 15.625 milliseconds (1/64 second). This rate was selected because it is the value implemented for SYSTEM.TICK in the evaluated compilers and represents the smallest usable value for this delay approach. A more realistic approach would use a periodic interrupt as the basis for advancing cycles. In our benchmark, frames consist of four cycles and periodic applications are scheduled in these cycles as shown in Figure 2. Periodic application scheduling is supported by a package called SCHEDULER which exports two procedures: SUSPEND and ADVANCE_CYCLE. Source code for the specification of this package is provided in Figure 3. The SUSPEND procedure suspends its caller until a specified cycle. Each periodic application is executed from the context of a task that performs its application processing and then calls SUSPEND to await the next cycle that corresponds to the period and phase specified for the application. The ADVANCE_CYCLE procedure advances the scheduler to the next cycle, awaking the periodic tasks scheduled for execution in that cycle. The ADVANCE_CYCLE procedure is called by DEADLINE_DATA each time it initiates a new cycle to schedule the periodic tasks for the cycle. In the baseline implementation of this benchmark, the SCHEDULER package body contains a task with an entry for each cycle in a frame. When a task calls SUSPEND at the completion of its processing for a cycle, it is queued on the entry corresponding to its next desired execution cycle. The source code for the body of this package is provided in Figure 4. <-------------- 1/16 sec.--------------> +---------+---------+---------+---------+ | | | | | | | INS | | | | | | | | o o o | SIM +---------+ NAV | GUI | o o o | | | | | | | AD | | | | | | | | +---------+---------+---------+---------+ <--1/64--><--1/64--><--1/64--><--1/64--> sec. sec. sec. sec. Figure 2. Sequencing of Periodic Applications package SCHEDULER is CYCLES_PER_FRAME : constant := 4; subtype CYCLE_TYPE is INTEGER range 0..CYCLES_PER_FRAME-1; procedure SUSPEND (WAKEUP_CYCLE : in CYCLE_TYPE); -- Suspends the calling task until the specified cycle procedure ADVANCE_CYCLE; -- Advances to the next cycle and wakes up all tasks waiting for the cycle end SCHEDULER; Figure 3. Scheduler Specification for Benchmark Version #1 package body SCHEDULER is task type SCHEDULER_TYPE is entry ADVANCE_CYCLE; -- initiates a new cycle entry SCHEDULE_IN_CYCLE_0; -- tasks to execute in cycle 0 entry SCHEDULE_IN_CYCLE_1; -- tasks to execute in cycle 1 entry SCHEDULE_IN_CYCLE_2; -- tasks to execute in cycle 2 entry SCHEDULE_IN_CYCLE_3; -- tasks to execute in cycle 3 end SCHEDULER_TYPE; THE_SCHEDULER : SCHEDULER_TYPE; task body SCHEDULER_TYPE is CURRENT_CYCLE : CYCLE_TYPE := CYCLE_TYPE'LAST; begin loop select accept ADVANCE_CYCLE do CURRENT_CYCLE := (CURRENT_CYCLE+1) mod (CYCLE_TYPE'LAST+1); loop select when CURRENT_CYCLE = 0 => accept SCHEDULE_IN_CYCLE_0; or o o o or when CURRENT_CYCLE = 3 => accept SCHEDULE_IN_CYCLE_3; else exit; end select; end loop; end ADVANCE_CYCLE; or terminate; end select; end loop; end SCHEDULER_TYPE; procedure SUSPEND(WAKEUP_CYCLE : in CYCLE_TYPE) is begin -- Queue caller on the entry associated with the desired wakeup-cycle case WAKEUP_CYCLE is when 0 => THE_SCHEDULER.SCHEDULE_IN_CYCLE_0; when 1 => THE_SCHEDULER.SCHEDULE_IN_CYCLE_1; when 2 => THE_SCHEDULER.SCHEDULE_IN_CYCLE_2; when 3 => THE_SCHEDULER.SCHEDULE_IN_CYCLE_3; when others => null; end case; end SUSPEND; procedure ADVANCE_CYCLE is begin THE_SCHEDULER.ADVANCE_CYCLE; end ADVANCE_CYCLE; end SCHEDULER; Figure 4. Scheduler Body for Baseline Benchmark Version #1 2.1.3.2 Re-Engineering Re-engineering of Application Benchmark Version #1 included replacing the task in the SCHEDULER package body with a protected record. The interface to SCHEDULER package was preserved by using the same package specification as used in the baseline implementation. The DEADLINE_DATA task and the periodic applications were also unchanged. Two variations of the protected record used to replace the task were developed. Limitations in the use of the first, which is shown in Figure 5, prompted the development of the second, which is shown in Figure 6. The problem with the first variation stems from a conflict between our use of the requeue statement and the Ada 9X interrupt feature enabling protected records to be attached to interrupts. The presence of the requeue statement forces "ADVANCE_CYCLE" to be declared as a protected entry rather than a protected procedure, even though it is coded in such a way that it is not a suspending operation. To eliminate this problem, the second variation implements ADVANCE_CYCLE as an protected procedure which can be used as an interrupt handler. Both variations of the protected record were implemented using discrete entries for each cycle of a frame. Discrete entries were used because protected entry families were not implemented in the evaluated compilers. Using protected entry families, the protected record could be re-written as shown in Figure 7. 2.1.3.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #1 are provided in Table III. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix A. protected type SCHEDULER_TYPE is entry ADVANCE_CYCLE; -- Transitions to the next cycle entry SCHEDULE_IN_CYCLE_0; -- Queue of tasks to execute in cycle 0 entry SCHEDULE_IN_CYCLE_1; -- Queue of tasks to execute in cycle 1 entry SCHEDULE_IN_CYCLE_2; -- Queue of tasks to execute in cycle 2 entry SCHEDULE_IN_CYCLE_3; -- Queue of tasks to execute in cycle 3 private entry RESET; -- ADVANCE_CYCLE calls are requeued here record CURRENT_CYCLE : CYCLE_TYPE := CYCLE_TYPE'LAST; CYCLE_STARTED : BOOLEAN := TRUE; end SCHEDULER_TYPE; . . . protected body SCHEDULER_TYPE is entry RESET when (CURRENT_CYCLE = 0 and then SCHEDULE_IN_CYCLE_0'COUNT = 0) or else (CURRENT_CYCLE = 1 and then SCHEDULE_IN_CYCLE_1'COUNT = 0) or else (CURRENT_CYCLE = 2 and then SCHEDULE_IN_CYCLE_2'COUNT = 0) or else (CURRENT_CYCLE = 3 and then SCHEDULE_IN_CYCLE_3'COUNT = 0) is begin CYCLE_STARTED := TRUE; end RESET; entry ADVANCE_CYCLE when TRUE is begin CURRENT_CYCLE := (CURRENT_CYCLE + 1) mod CYCLE_TYPE'LAST; CYCLE_STARTED := FALSE; requeue RESET; end ADVANCE_CYCLE; entry SCHEDULE_IN_CYCLE_0 when CURRENT_CYCLE = 0 and not CYCLE_STARTED; entry SCHEDULE_IN_CYCLE_1 when CURRENT_CYCLE = 1 and not CYCLE_STARTED; entry SCHEDULE_IN_CYCLE_2 when CURRENT_CYCLE = 2 and not CYCLE_STARTED; entry SCHEDULE_IN_CYCLE_3 when CURRENT_CYCLE = 3 and not CYCLE_STARTED; end SCHEDULER_TYPE; Figure 5. Re-Engineered Portions of Scheduler Body - Variation #1 type SWITCH_ARRAY is array (CYCLE_TYPE) of BOOLEAN; protected type SCHEDULER_TYPE is procedure ADVANCE_CYCLE; entry SCHEDULE_IN_CYCLE_0; -- tasks to execute in cycle 0 entry SCHEDULE_IN_CYCLE_1; -- tasks to execute in cycle 1 entry SCHEDULE_IN_CYCLE_2; -- tasks to execute in cycle 2 entry SCHEDULE_IN_CYCLE_3; -- tasks to execute in cycle 3 private entry CYCLE_0_WAIT_A; entry CYCLE_0_WAIT_B; entry CYCLE_1_WAIT_A; entry CYCLE_1_WAIT_B; entry CYCLE_2_WAIT_A; entry CYCLE_2_WAIT_B; entry CYCLE_3_WAIT_A; entry CYCLE_3_WAIT_B; record CURRENT_CYCLE : CYCLE_TYPE := CYCLE_TYPE'LAST; CYCLE_SWITCH : SWITCH_ARRAY := (others => FALSE); end SCHEDULER_TYPE; protected body SCHEDULER_TYPE is procedure ADVANCE_CYCLE is begin CURRENT_CYCLE := (CURRENT_CYCLE + 1) MOD (CYCLE_TYPE'LAST+1); CYCLE_SWITCH(CURRENT_CYCLE) := not CYCLE_SWITCH(CURRENT_CYCLE); end ADVANCE_CYCLE; entry SCHEDULE_IN_CYCLE_0 when TRUE is begin if CYCLE_SWITCH(0) then requeue CYCLE_0_WAIT_A; else requeue CYCLE_0_WAIT_B; end if; end SCHEDULE_IN_CYCLE_0; . . . entry SCHEDULE_IN_CYCLE_3 when TRUE is begin if CYCLE_SWITCH(3) then requeue CYCLE_3_WAIT_A; else requeue CYCLE_3_WAIT_B; end if; end SCHEDULE_IN_CYCLE_3; entry CYCLE_0_WAIT_A when not CYCLE_SWITCH(0); . . . entry CYCLE_3_WAIT_A when not CYCLE_SWITCH(3); entry CYCLE_0_WAIT_B when CYCLE_SWITCH(0); . . . entry CYCLE_3_WAIT_B when CYCLE_SWITCH(3); end SCHEDULER_TYPE; Figure 6. Re-Engineered Portions of Scheduler Body - Variation #2 type SWITCH_ARRAY is array (CYCLE_TYPE) of BOOLEAN; protected type SCHEDULER_TYPE is procedure ADVANCE_CYCLE; entry SCHEDULE_IN_CYCLE(for CYCLE in CYCLE_TYPE); private entry A_CYCLES(for CYCLE in CYCLE_TYPE); entry B_CYCLES(for CYCLE in CYCLE_TYPE); record CURRENT_CYCLE : CYCLE_TYPE := CYCLE_TYPE'LAST; CYCLE_SWITCH : SWITCH_ARRAY := (others => FALSE); end SCHEDULER_TYPE; . . . protected body SCHEDULER_TYPE is procedure ADVANCE_CYCLE is begin CURRENT_CYCLE := (CURRENT_CYCLE + 1) mod (CYCLE_TYPE'LAST+1); CYCLE_SWITCH(CURRENT_CYCLE) := not CYCLE_SWITCH(CURRENT_CYCLE); end ADVANCE_CYCLE; entry SCHEDULE_IN_CYCLE(for CYCLE in CYCLE_TYPE) when TRUE is begin if CYCLE_SWITCH(CYCLE) then requeue A_CYCLES(CYCLE); else requeue B_CYCLES(CYCLE); end if; end SCHEDULE_IN_CYCLE; entry A_CYCLES(for CYCLE in CYCLE_TYPE) when not CYCLE_SWITCH(CYCLE); entry B_CYCLES(for CYCLE in CYCLE_TYPE) when CYCLE_SWITCH(CYCLE); end SCHEDULER_TYPE; . . . procedure SUSPEND (WAKEUP_CYCLE : in CYCLE_TYPE) is begin SCHEDULER.SCHEDULE_IN_CYCLE(WAKEUP_CYCLE); end SUSPEND; Figure 7. Re-Engineered Portion of Scheduler Body - Entry Families Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 1924 V4.1 12:38.89 n/a Ada 9X 12:02.21 13.0 Re-Engineered 1953 Ada 9X 11:55.52 11.4 Table III. Benchmark Version #1 Results 2.1.4 Benchmark Version #2 The purpose of Benchmark Version #2 is to evaluate the benefit of protected records in a DAIS-like environment where a small amount of asynchronous processing occurs in a system where periodic deadline scheduling is used as the primary method for scheduling application tasks. This benchmark uses the scheduling of tasks within strict time frames to enforce mutually exclusive access to some data structures and explicit locks for others. 2.1.4.1 Baseline While most tasks in the DAIS system are periodic, there are a few tasks scheduled upon aperiodic events such as cockpit inputs (e.g. key hits). Aperiodic processing is simulated using tasks whose executions are not tied to any time period cycles. Such tasks delay for a random duration and then awaken and perform a random amount of processing that may include contending for resources also used by periodic tasks. This introduces variability to the system that may occasionally cause missed deadlines. The aperiodic tasks compete with other tasks based on their Ada priority. Data structures accessed by both periodic and aperiodic tasks are guarded against simultaneous access. Exclusive access to other data structures can still be guaranteed by the inherent sequencing of the periodic tasks. The baseline implementation of this benchmark uses the same periodic deadline scheduler used in the baseline implementation of application benchmark #1. In addition, instances of a task type called LOCK are used to enforce mutually exclusive access to data structures shared by asynchronous tasks and between periodic and asynchronous tasks. These are required since the asynchronous tasks are not tied to specific time cycles and may execute at any time, possibly preempting a periodic task or a lower priority asynchronous task. The LOCK tasks are implemented using rendezvous as shown in Figure 8. task type LOCK is entry ACQUIRE; entry RELEASE; end LOCK; . . . task body LOCK is begin loop accept ACQUIRE; accept RELEASE; end loop; end LOCK; Figure 8. Lock Implemented with Ada 83 Tasking 2.1.4.2 Re-Engineering The re-engineered implementation of application benchmark #2 uses a periodic deadline scheduler identical to the one used in the re-engineered implementation of application benchmark #1. In addition, the task type LOCK used to enforce mutually exclusive access to data structures shared between applications was replaced by the protected type shown in Figure 9. protected type LOCK is entry ACQUIRE; procedure RELEASE; record LOCKED : BOOLEAN := FALSE; end LOCK; . . . protected body LOCK is entry ACQUIRE when not LOCKED is begin LOCKED := TRUE; end ACQUIRE; procedure RELEASE is begin LOCKED := FALSE; end RELEASE; end LOCK; Figure 9. Lock Implemented as a Protected Record 2.1.4.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #2 are provided in Table IV. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix B. Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 2143 V4.1 14:04.13 n/a Ada 9X 13:28.40 29.9 Re-Engineered 2202 Ada 9X 13:15.99 18.9 Table IV. Benchmark Version #2 Results 2.1.5 Benchmark Version #3 The purpose of Benchmark Version #3 is to evaluate the benefit of protected records in an AARTS-like environment where the primary event used for scheduling application tasks is data arrival. This benchmark depends on "event" tasks to schedule applications as updated data becomes available. 2.1.5.1 Baseline The applications in this benchmark version are scheduled by asynchronous events rather than the periodic scheduler used in Benchmark Versions #1 and #2. These asynchronous events are signalled as new data becomes available for application processing. The benchmark contains several databases which are accessed by more than one application. In most cases, such databases are updated by one task and used by others to revise the values they compute. By convention, these databases include an instance of a task that is used to synchronize the users of the data with the completion of the update. This task has two entries: WAIT and SIGNAL. The WAIT entry is called by the consumers of the data to suspend until the next update. The SIGNAL entry is called by the producer of the data whenever a significant update has been completed. The implementation of this "event" task using Ada 83 language features (rendezvous) is provided in Figure 10. task type EVENT is entry SIGNAL; entry WAIT; end EVENT; task body EVENT is begin loop accept SIGNAL do loop select accept WAIT; else exit; end select; end loop; end SIGNAL; end loop; end EVENT; Figure 10. Event Implementation Using Tasking The databases INS_SENSOR_DATA, AD_SENSOR_DATA, INS_DATA, AD_DATA, and NAV_STATE_DATA include instances of this task. Each of these instances are named UPDATE. Most of the applications in this benchmark execute upon the update of one of these databases. For example, the INS application executes upon the arrival of new sensor data and generates INS data for access by the NAVIGATION and GUIDANCE applications. The INS task includes the code segment shown in Figure 11, which is a representative template of most of the other applications in this benchmark. loop INS_SENSOR_DATA.UPDATE.WAIT; . . processing performed upon the arrival of updated INS sensor data . . update the INS data base . . INS_DATA.UPDATE.SIGNAL; end loop; NOTE: INS_SENSOR_DATA.UPDATE and INS_DATA.UPDATE are instances of the EVENT task type described above. Figure 11. INS Application Code Template One application that does not adhere closely to the template used by the INS application is GUIDANCE. The GUIDANCE application relies on three databases as inputs to its computations and only performs these computations when all three of these databases have been updated. The source code fragments shown in Figure 12 control when the guidance computations are performed. Three tasks, named AD_DETECTOR, INS_DETECTOR and NAV_DETECTOR, await the signalled update of their respective databases and then notify the GUIDANCE_CONTROL task when such updates occur. The GUIDANCE_CONTROL task performs the guidance processing whenever it has been notified of the update of all three databases. One advantage of this approach is that the interaction between the producers and consumers of data is minimized. The producers simply signal the completion of a database update which allows all the consumers awaiting the data to become eligible for execution. The producers do not need to be aware of which or even how many applications are consuming the data they generate. New database consumers can be added without changing the producers or the databases. 2.1.5.2 Re-Engineering Re-engineering of Benchmark Version #3 included re-implementation using protected records. The task type EVENT was replaced by the protected type shown in Figure 13. This protected type provides operations analogous to those provided by the EVENT task type. task AD_INPUT_DETECTOR; task INS_INPUT_DETECTOR; task NAV_INPUT_DETECTOR; task GUIDANCE_CONTROL is entry AD_INPUT; entry INS_INPUT; entry NAV_INPUT; end GUIDANCE_CONTROL; task body AD_INPUT_DETECTOR is begin loop AD_DATA.UPDATE.WAIT; GUIDANCE_CONTROL.AD_INPUT; end loop; end AD_INPUT_DETECTOR; task body INS_INPUT_DETECTOR is begin loop INS_DATA.UPDATE.WAIT; GUIDANCE_CONTROL.INS_INPUT; end loop; end INS_INPUT_DETECTOR; task body NAV_INPUT_DETECTOR is begin loop NAV_STATE_DATA.UPDATE.WAIT; GUIDANCE_CONTROL.NAV_INPUT; end loop; end NAV_INPUT_DETECTOR; task body GUIDANCE_CONTROL is AD_UPDATED, INS_UPDATED, NAV_UPDATED : BOOLEAN; begin loop -- Wait for updates to all three inputs AD_UPDATED := FALSE; INS_UPDATED := FALSE; NAV_UPDATED := FALSE; while not (AD_UPDATED and INS_UPDATED and NAV_UPDATED) loop select accept AD_INPUT do AD_UPDATED := TRUE; end AD_INPUT; or accept INS_INPUT do INS_UPDATED := TRUE; end INS_INPUT; or accept NAV_INPUT do NAV_UPDATED := TRUE; end NAV_INPUT; end select; end loop; . . guidance processing (using INS_Data, NAV_State_Data, & AD_Data) . . end loop; end GUIDANCE_CONTROL; Figure 12. Baseline Implementation of the GUIDANCE Application protected type EVENT is entry SIGNAL; entry WAIT; private entry WAIT_A; entry WAIT_B; record SWITCH : BOOLEAN := FALSE; end EVENT; . . . protected body EVENT is procedure SIGNAL is begin SWITCH := not SWITCH; end SIGNAL; entry WAIT when TRUE is begin if SWITCH then requeue WAIT_B; else requeue WAIT_A; end if; end WAIT; entry WAIT_A when SWITCH; entry WAIT_B when not SWITCH; end EVENT; Figure 13. Event Implementation Using Protected Records The impacts of re-engineering this application to use protected records were not difficult. No changes to the INS application code template shown in Figure 11 were necessary. The GUIDANCE_CONTROL portion of the GUIDANCE application shown in Figure 12 was changed from a task to a protected record. A new task, called GUIDANCE_MAIN was created which calls a protected entry to wait on the three required inputs and then performs the guidance processing. The GUIDANCE_CONTROL protected record and the GUIDANCE_MAIN task are shown in Figure 14. No other changes to the GUIDANCE application were necessary. 2.1.5.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #3 are provided in Table V. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix C. task GUIDANCE_MAIN; protected type GUIDANCE_CONTROL is procedure AD_INPUT; procedure INS_INPUT; procedure NAV_INPUT; entry WAIT; record AD_UPDATED, INS_UPDATED, NAV_UPDATED : BOOLEAN := FALSE; end GUIDANCE_CONTROL; . . . protected body GUIDANCE_CONTROL is procedure AD_INPUT is begin AD_UPDATED := TRUE; end AD_INPUT; procedure INS_INPUT is begin INS_UPDATED := TRUE; end INS_INPUT; procedure NAV_INPUT is begin NAV_UPDATED := TRUE; end NAV_INPUT; entry WAIT when (AD_UPDATED and INS_UPDATED and NAV_UPDATED) is begin AD_UPDATED := FALSE; INS_UPDATED := FALSE; NAV_UPDATED := FALSE; end WAIT; end GUIDANCE_CONTROL; task body GUIDANCE_MAIN is begin loop -- Wait for updates to all required inputs GUIDANCE_CONTROL.WAIT; . . guidance processing (using INS_Data, NAV_State_Data, & AD_Data) . . end loop; end GUIDANCE_MAIN; Figure 14. Re-Engineered Portions of the GUIDANCE Application Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 1786 V4.1 10:50.30 n/a Ada 9X 10:14.11 44.8 Re-Engineered 1785 Ada 9X 10:04.44 35.9 Table V. Benchmark Version #3 Results 2.1.6 Benchmark Version #4 Application Benchmark Version #4 is simply a re-implementation of Benchmark Version #1 using an interrupt to signal the start of each new cycle. 2.1.6.1 Baseline The baseline implementation of this benchmark is identical to the baseline implementation of Benchmark Version #1 with the following exceptions: * The declaration of the task type "SCHEDULER_TYPE" was updated to specify ADVANCE_CYCLE as an interrupt entry. The updated declaration is shown in Figure 15. * The task DEADLINE_DATA was modified to periodically signal an interrupt in lieu of calling ADVANCE_CYCLE. The following procedure call is used to signal the interrupt: SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT (INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_144); Note the CAUSE_IAC_INTERRUPT procedure uses the i960MC interagent communication (IAC) mechanism to signal an interrupt. Each time the above call is executed, interrupt vector #144 is signaled by the processor. The software processing performed in response to an interrupt signaled this way is identical to the processing performed in response to a hardware generated interrupt. The effect of these changes is that the task entry "ADVANCE_CYCLE" is invoked by signaling an interrupt rather than by direct call. task type SCHEDULER_TYPE is entry ADVANCE_CYCLE; -- initiates a new cycle entry SCHEDULE_IN_CYCLE_0; -- tasks to execute in cycle 0 entry SCHEDULE_IN_CYCLE_1; -- tasks to execute in cycle 1 entry SCHEDULE_IN_CYCLE_2; -- tasks to execute in cycle 2 entry SCHEDULE_IN_CYCLE_3; -- tasks to execute in cycle 3 end SCHEDULER_TYPE; Figure 15. Benchmark Version #4 Task Type Declaration 2.1.6.2 Re-Engineering The re-engineered implementation of Application Benchmark #4 includes a modified copy of the periodic deadline scheduler used by the re-engineered implementations of Application Benchmarks #1 and #2. The modified periodic deadline scheduler uses the following call to dynamically bind the protected procedure "ADVANCE_CYCLE" to the interrupt signaled by "DEADLINE_DATA": INTERRUPT_MANAGEMENT.ATTACH_INTERRUPT_HANDLER ( HANDLER => INTERRUPT_MANAGEMENT.TICK_ACCESS_PROTECTED_PROCEDURE ( INSTANCE => THE_SCHEDULER'ADDRESS, PROTECTED_PROCEDURE=> THE_SCHEDULER.ADVANCE_CYCLE'ADDRESS), INTERRUPT => INTERRUPT_MANAGEMENT.INTERRUPT_NAMES.VECTOR_144); The function TICK_ACCESS_PROTECTED_PROCEDURE was provided by Tartan as an interim solution pending implementation of access-to-subprogram types. The pragma ATTACH_HANDLER is another alternative that supports static binding of an interrupt to a protected procedure. 2.1.6.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #4 are provided in Table VI. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix D. Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 1927 Ada 9X 12:08.28 13.0 Re-Engineered 1957 Ada 9X 12:11.42 11.5 Table VI. Benchmark Version #4 Results 2.1.7 Benchmark Version #5 Application Benchmark Version #5 is a re-implementation of Benchmark Version #2 that uses an interrupt to signal the start of each new cycle. 2.1.7.1 Baseline The baseline implementation of Application Benchmark #5 uses a periodic deadline scheduler identical to the one used in the baseline implementation of Application Benchmark #4. This scheduler specifies the task entry "ADVANCE_CYCLE" as an interrupt entry to be invoked whenever the interrupt is signaled by "DEADLINE_DATA". The remaining portions of this implementation are identical to the baseline implementation of Application Benchmark #2, including the use of the task type LOCK to enforce mutually exclusive access to the data structures shared by asynchronous tasks and between periodic and asynchronous tasks. 2.1.7.2 Re-Engineering The re-engineered implementation of Application Benchmark #5 uses a periodic deadline scheduler identical to the one used in the re-engineered implementation of Application Benchmark #4. This scheduler uses the ATTACH_INTERRUPT_HANDLER procedure in package INTERRUPT_MANAGEMENT to dynamically bind the protected procedure "ADVANCE_CYCLE" to the interrupt signaled by "DEADLINE_DATA". The remaining portions of this implementation are identical to those of the re-engineered implementation of Application Benchmark #2, including the use of the protected type LOCK to enforce mutually exclusive access to the data structures shared by asynchronous tasks and between periodic and asynchronous tasks. 2.1.7.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #5 are provided in Table VII. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix E. Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 2146 Ada 9X 13:36.67 29.9 Re-Engineered 2176 Ada 9X 13:38.07 19.1 Table VII. Benchmark Version #5 Results 2.1.8 Benchmark Version #6 Application Benchmark Version #6 is a re-implementation of Benchmark Version #3 that uses an interrupt to signal when it is time to start a new iteration of simulation processing. In all other respects, these two versions are identical. 2.1.8.1 Baseline The baseline implementation of this benchmark was adapted from the baseline version of Application Benchmark Version #3. This adaptation included the addition of a new task type named INTERRUPT_EVENT and the use of an object of this type in place of the EVENT object used to indicate when the SIM application is to generate a new set of raw sensor data. The declaration of the INTERRUPT_EVENT task type is shown in Figure 16. Implementation of the task body is identical to the EVENT task body shown previously in Figure 10. The interrupt associated with the task entry "SIGNAL" is raised periodically at 64 hz. using the code fragment shown in Figure 17. This causes the SIM application to be executed at the same rate as it was in Application Benchmark #3. task type INTERRUPT_EVENT is entry WAIT; entry SIGNAL; for SIGNAL use at 144; pragma PRIORITY (SYSTEM.PRIORITY'LAST); end INTERRUPT_EVENT; for INTERRUPT_EVENT'storage_size use 16#400#; task body INTERRUPT_EVENT is -- same as task body of EVENT shown in Figure 10 end INTERRUPT_EVENT; Figure 16. INTERRUPT_EVENT Implemented as a Task Type loop delay NEXT_CYCLE - CALENDAR.CLOCK ; SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT (INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_144); CUR_CYCLE := NEXT_CYCLE; NEXT_CYCLE := CUR_CYCLE + CYCLE_DUR; end loop; Figure 17. SIMULATION_CONTROL Loop Modified to Raise Interrupt 2.1.8.2 Re-Engineering The re-engineered implementation of this benchmark was adapted from the re- engineered implementation of Application Benchmark Version #3. Similar to the baseline implementation, this adaptation included the addition of a new type named INTERRUPT_EVENT and the use of an object of this type in place of the EVENT object used to indicate when the SIM application is to generate a new set of raw sensor data. The difference is this INTERRUPT_EVENT type is coded as a protected record type. The protected type declaration and the code used to dynamically bind an instance of this type to an interrupt is shown in Figure 18. Implementation of the protected body is identical to the EVENT protected body shown previously in Figure 13. The interrupt is signaling at a 64 hz rate using the same code used for the baseline implementation. protected type INTERRUPT_EVENT is pragma INTERRUPT_PRIORITY(18); procedure SIGNAL; entry WAIT; private entry WAIT_A; entry WAIT_B; record SWITCH : BOOLEAN := false; end INTERRUPT_EVENT; protected body INTERRUPT_EVENT is -- same as protected body of EVENT shown in Figure 13 end INTERRUPT_EVENT; . . . NEXT_ITERATION : INTERRUPT_EVENT; . . . INTERRUPT_MANAGEMENT.ATTACH_INTERRUPT_HANDLER ( INTERRUPT_MANAGEMENT.TICK_ACCESS_PROTECTED_PROCEDURE ( INSTANCE => NEXT_ITERATION'ADDRESS, PROTECTED_PROCEDURE => NEXT_ITERATION.SIGNAL'ADDRESS), INTERRUPT_MANAGEMENT.INTERRUPT_NAMES.VECTOR_144); Figure 18. INTERRUPT_EVENT Implemented as a Protected Type 2.1.8.3 Results The results of the baseline and re-engineered implementations of Benchmark Version #6 are provided in Table VIII. These results include statement counts, compilation times and the percent CPU utilization observed during execution of the benchmark implementations on the target processor. The compilation times for each of the individual source files are provided in Appendix F. Benchmark Lines-Of-Code Compiler Compile % CPU Implementation (Semicolons) Release Time Utilization Baseline 1788 Ada 9X 10:19.22 44.8 Re-Engineered 1787 Ada 9X 10:18.00 36.2 Table VIII. Benchmark Version #6 Results 2.2 Other Benchmarking 2.2.1 Device Communication Benchmark An important requirement levied on the software of real-time embedded systems is the interface and control of various types of hardware devices. To help evaluate ways that Ada 9X features might contribute to this type of software, TRW re-engineered a subset of the AARTS executive. This exercise did not lead to an executable benchmark, since this software is highly dependent on custom hardware that is not available in our target environment, but it did provide examples of how Ada 9X features might be applied to this type of software. One of the capabilities provided by the AARTS executive is communication on a dual Processor Interconnect Bus (PI-Bus) backplane. This is accomplished by interfacing to an intelligent Bus Interface Unit (BIU). The processor-to-BIU communication is performed using: * status registers - enable the processor to obtain bus state information, * control registers - enable the processor to command and acknowledge BIU operations, * data structures - (resident in processor memory) tell the BIU how it is to participate in PI-Bus sequences, and * interrupts - notify the processor of asynchronous events. The BIU uses direct memory access (DMA) to access processor memory. In the AARTS executive, all direct interfaces to the BIU are implemented in a library unit named PI_BUS. While this package is written in Ada, it has several drawbacks for which Ada 9X offers help. These drawbacks are discussed separately along with how Ada 9X features were used to improve the implementation. The first, and possibly the most serious, drawback of the PI-Bus package implementation is its dependence on non-standard interfaces to the Ada runtime. Such non-standard interfaces were necessary to implement efficient interrupt handlers and to control code re-entrancy. In Ada 83, the interrupt entry mechanism is offered as a solution but proved inadequate in this case due to its high execution overhead. This forced the developers to interface directly with the runtime which required understanding of vendor-specific implementation details. The resulting software is not easily ported to other tool sets. Using Ada 9X, interrupt handlers can be coded as protected procedures providing a much lower overhead solution than task entries. Furthermore, the protected record lock can be used to control code re-entrancy by placing the critical sections of code, that must be protected from preemption by the interrupt, in the same protected type as the procedure serving as the handler. Figure 19 shows how this approach was applied in the re-engineered version of this benchmark. Another drawback of the original PI_BUS package implementation is the use of a type-unsafe call-back capability where the address of the subprogram to be called is specified using SYSTEM.ADDRESS with the actual call-back implemented as an assembly-language routine. This call-back capability was used to notify the client when there is activity on a specific PI-Bus label which occurs (asynchronously) when the BIU participates as a slave in a PI-Bus message sequence. The approach supports different call-back routines for the various labels and enables new clients to be added without any impact to PI_BUS or its clients. This approach is also much more efficient than tasking alternatives. A type-safe call-back capability can be implemented using the Ada 9X access- to-subprogram types. The re-engineered version of this benchmark declares the following access-to-subprogram types and objects: type LABEL_ACTIVITY_ACTION is access procedure(LABEL : in LABEL_TYPE); type LABEL_ERROR_ACTION is access procedure(REPORT : in SLAVE_ERROR_REPORT); procedure NO_ACTION (LABEL : in LABEL_TYPE); procedure NO_ACTION (REPORT : in SLAVE_ERROR_REPORT); The protected procedure CRITICAL_SERVICES.ENABLE_LABEL accepts access-to- subprogram values as input parameters and stores them away to be called when there is label activity or an error condition associated with the label. This approach offers the advantages of type-safe programming and portability over our Ada 83 implementation. The third drawback to our original implementation is the use of a package with an assembly-language body to implement unsigned integer operations which are useful for interfacing with hardware defined data structure formats. This could have alternatively been implemented using package machine code. In Ada 9x, the standard package UNSIGNED_INTEGERS offers the operations required for this type of processing. Defining this as a standard package provides the opportunity for compilers to generate efficient in-line code for these types of operations and eliminates the need for users to develop these types of packages themselves. In addition to resolving the above drawbacks, the child-library feature of Ada 9X was used during the re-engineering process to gain better visibility control of a private type CCB_TYPE, declared in the PI_BUS package. CCB_TYPE is a record type declaring the format of the Communication Control Blocks (CCBs) used to command the BIU to perform master-mode operations. When the protected type CRITICAL_SERVICES ( THE_PRIORITY : SYSTEM.ANY_PRIORITY; INTER_ID_A : INTERRUPT_MANAGEMENT.INTERRUPT_ID; INTER_ID_B : INTERRUPT_MANAGEMENT.INTERRUPT_ID) is pragma INTERRUPT_PRIORITY (THE_PRIORITY); -- -- IMPORTANT!!! Mutually exclusive execution of the following operations -- must be enforced. -- -- -- Service routines for PI-Bus interrupts -- procedure HANDLER_A; -- Handles interrupt generated by BIU -- connected to PI-Bus "A" pragma ATTACH_HANDLER(HANDLER_A, INTER_ID_A); procedure HANDLER_B; -- Handler interrupt generated by BIU -- connected to PI-Bus "B" pragma ATTACH_HANDLER(HANDLER_B, INTER_ID_B); -- -- PI-Bus Control Operations: -- procedure ENABLE_BIU (FOR_BUS : in WHICH_BUS := PI_BUS_A; WITH_LIDS : in LID_ARRAY := (others => FALSE)); -- Setup required for BIU to participate as a slave; identify -- alias (logical) slave identifiers procedure DISABLE_BIU (FOR_BUS : in WHICH_BUS := PI_BUS_A); -- Cease participation as a slave module function IS_ENABLED (BUS : in WHICH_BUS := PI_BUS_A) return BOOLEAN; -- Determine whether bus is setup for slave operations procedure START_MASTER (ON_BUS : in WHICH_BUS := PI_BUS_A); -- Setup required for BIU to initiate master mode operations procedure STOP_MASTER; -- Suspend processing of master mode operations function CURRENT_MASTER return WHICH_BUS_OR_NONE; -- Identify which BIU is setup for master mode operations -- -- PI-Bus Slave Operations: -- procedure ENABLE_LABEL ( LABEL : in LABEL_TYPE; DATA_BUFFER : in SYSTEM.ADDRESS UPON_ACTIVITY_CALL : in LABEL_ACTIVITY_ACTION := NO_ACTION; UPON_ERROR_CALL : in LABEL_ERROR_ACTION := NO_ACTION ); -- Associate a label with a memory buffer thereby providing -- access to external nodes on the bus procedure DISABLE_LABEL (LABEL : in LABEL_TYPE); -- Disassociate a label and its memory buffer function IS_ENABLED (LABEL : in LABEL_TYPE) return BOOLEAN; -- Determine whether a label is enabled -- -- PI-Bus Master-Mode Operations: -- procedure EXECUTE_CCB (CCB : in out CCB_TYPE); procedure ABORT_CCB (CCB : in CCB_TYPE); function STATE_OF (CCB : in CCB_TYPE) return CCB_STATE_TYPE; private record null; end CRITICAL_SERVICES; Figure 19. PI-Bus CRITICAL_SERVICES Protected Record Type PI_BUS package was first implemented, a visible procedure CREATE_CCB was provided to create and initialize a CCB based on input parameters. Other visible procedures enabled users to execute (queue for processing by the BIU), abort (dequeue prior to processing by the BIU), and delete CCBs. These operations initially supported all the PI_BUS clients, however, later in development two new clients were added that had special requirements to dynamically update fields of their CCBs. Our solution, using Ada 83, was to add a visible procedure UPDATE_CCB to meet the needs of these two clients. This solution worked but all the clients of PI_BUS had to be recompiled and re-linked and the UPDATE_CCB procedure is generally available even though we wanted to limit its use to these two special clients. While re-engineering this benchmark, we decided to implement the two special case clients as Child Units, both dependents of the PI_BUS package. This eliminates the need for the UPDATE_CCB procedure because the two special clients have visibility to the full type declaration of CCB_TYPE, allowing them to update their CCBs through assignment. Had this feature been available when these two clients were first added during the original development, the existing clients of PI_BUS would have been unaffected, eliminating the need to re-compile and re-link. An added benefit is the re-engineered approach offers a performance improvement in those cases where calls to UPDATE_CCB are not generated as in-line code. Collectively, these re-engineering steps substantially improved the PI_BUS package. These steps eliminated dependence on vendor-specific runtime features and assembly-language implementations of a call-back feature and unsigned integers. They also resulted in a call-back that is type-safe. The child library feature will enable future enhancements to have less impact on the PI_BUS package and its clients. 2.2.2 Semaphore Comparison In addition to application benchmarking activities, TRW implemented three versions of a counting semaphore capability to provide raw data useful for assessing the performance of protected records relative to two other synchronization approaches. 2.2.2.1 Description The source code for the three versions of semaphore are provided in Figures 14, 15 and 16. The first version was extracted from section 9.6 of [1] and uses protected records to implement the counting semaphore. Similar capabilities were implemented using Ada 83 features (rendezvous) and calls to a direct runtime interface provided with the Tartan tool sets (ART_Semaphore). Obviously, the approach using the direct runtime interface is not portable since it depends on a runtime interface package provided only with Tartan tool sets. protected type Semaphore (Initial_Count : INTEGER := 1) is entry Acquire; -- Acquire a resource, suspend if none procedure Release; -- Release a resource function Count return INTEGER; -- Return count of available resources private record Current_Count : INTEGER := Initial_Count; -- Count of available resources end Semaphore; protected body Semaphore is entry Acquire when Current_Count > 0 is begin Current_Count := Current_Count - 1; end Acquire; procedure Release is begin Current_Count := Current_Count + 1; end Release; function Count return INTEGER is begin return Current_Count; end Count; end Semaphore; Figure 20. Counting Semaphore Implemented Using Protected Records package Semaphore_Ada83 is function Count return INTEGER; task Semaphore is entry Acquire; -- Acquire a resource, suspend if none entry Release; -- Release a resource end Semaphore; end Semaphore_Ada83; package body Semaphore_Ada83 is Initial_Count : INTEGER := 1; -- number of resources Current_Count : INTEGER := Initial_Count; function Count return INTEGER is begin return Current_Count; end Count; task body Semaphore is begin loop select when Current_Count > 0 => accept Acquire do Current_Count := Current_Count - 1; end Acquire; or accept Release do Current_Count := Current_Count + 1; end Release; or terminate; end select; end loop; end Semaphore; end Semaphore_Ada83; Figure 21. Counting Semaphore Implemented Using Rendezvous with ART_Semaphore; package Semaphore_RTS is Initial_Count : INTEGER := 1; -- Resource count procedure Acquire; -- Acquire a resource, suspend if none procedure Release; -- Release a resource function Count return INTEGER; -- Return count of available resources end Semaphore_RTS; package body Semaphore_RTS is Current_Count : INTEGER := Initial_Count; The_Semaphore : ART_Semaphore.Semaphore_Type; Clear_Status : ART_Semaphore.Call_Status_Type; function Count return INTEGER is begin return Current_Count; end Count; procedure Release is Signal_Status : ART_Semaphore.Call_Status_Type; begin Current_Count := Current_Count + 1; if Current_Count <= Initial_Count then ART_Semaphore.Signal_Semaphore ( Semaphore_Id => The_Semaphore, Return_Status => Signal_Status); end if; end Release; procedure Acquire is Wait_Status : ART_Semaphore.Call_Status_Type; begin Current_Count := Current_Count - 1; if Current_Count < Initial_Count then ART_Semaphore.Wait_On_Semaphore ( Semaphore_Id => The_Semaphore, Wait_Time => DURATION'LAST, Return_Status => Wait_Status ); end if; end Acquire; begin ART_Semaphore.Clear_Semaphore ( Semaphore_Id => The_Semaphore, New_Count => Initial_Count, Return_Status => Clear_Status ); end Semaphore_RTS; Figure 22. Counting Semaphore Implemented Using Direct Runtime Calls 2.2.2.2 Results Performance measurements were collected for the three semaphore implementations by executing them on the EXV-960MC target processor. The acquire and release operations were timed as a pair. Table IX(a) provides acquire/release timing data collected while the semaphore was available each time acquire was called. Table IX(b) provides similar data collected when the semaphore was not available when acquire was called forcing the caller to wait. Acquire/Release Overhead Rela- Savings Rela- Comparison Implementation Time (MicroSecs) tive to Ada 83 tive to Ada 83 Factor Ada83 Tasking 459.2 100.0% 0.0% 1.0 Ada9X Protected Rec 78.3 17.1% 82.9% 5.9 Runtime Calls 36.0 7.8 92.2% 12.8 Table IX(a). Semaphore Results - Semaphore Available When Acquire Called Acquire/Release Overhead Rela- Savings Rela- Comparison Implementation Time (MicroSecs) tive to Ada 83 tive to Ada 83 Factor Ada83 Tasking 531.9 100.0% 0.0% 1.0 Ada9X Protected Rec 83.3 15.7% 84.3% 6.4 Runtime Calls 38.9 7.3% 92.7% 13.7 Table IX(b). Semaphore Results - Semaphore Not Available When Acquire Called As one would expect, the protected record implementation of a semaphore provides a vast performance improvement over the equivalent rendezvous implementation. Specifically, a pair of calls to "acquire" and "release" the semaphore in the protected record implementation executes more than five times faster than the equivalent rendezvous implementation. While this is a substantial improvement, it does not compare favorably with the semaphore implementation employing direct runtime calls which executes roughly twelve times faster than the rendezvous implementation. Furthermore, it should be noted that the ART_Semaphore package provided with the Tartan runtime implements a timeout feature which accounts for part of its execution overhead. Thus, a less-capable implementation using direct runtime calls could be developed providing even better execution efficiency. 3. ACEC 3.1 Baseline Development The ACEC Version 2.1 was used as the basis for the ACEC development efforts performed by TRW. A version of the ACEC baseline was created that is compatible with the Tartan Ada 9X compilation system and the EXV-960MC target processor. This required development of a math library package body, customization of script files for building and executing the test suite, and selection of "include" files that contain the code that replaces "pragma INCLUDE" statements embedded in the ACEC tests. A small number of the existing ACEC tests were built and executed to test the customized baseline and provide a basis for comparison. New tests were developed for the purpose of evaluating Ada 9X language features, specifically protected records. Now that the baseline has been established, more tests can be easily created. The ACEC test suite requires a math library of elementary functions. To fulfill this requirement, TRW built a customized body for the MATH package provided with the ACEC that is compatible with the i960MC target. A portable math package is provided with the ACEC distribution but the ACEC documentation recommends the use of other alternatives when available. The package built by TRW uses the "intrinsics" package provided by the Tartan tool set to gain access to many of the floating point operations provided by the i960MC processor, including trigonometric, logarithmic, exponential and scale functions. This produced a package that is much faster and more accurate than the generic math library provided with the ACEC release. The ACEC Version 2.1 implements a standardized facility for building timing loops into the tests and TRW used this facility for all new tests developed. Each timing loop is coded to adhere to a template that includes several "pragma INCLUDE" statements surrounding the code to be measured. A pre- processor program, called INCLUDE.EXE, is executed prior to compilation to replace these pragmas with code that measures and reports timing and sizing of the subject code. This pre-processor simply replaces the pragma with the file identified as the parameter. Various versions of the include files are provided that support collection of time measurements based on CPU time or elapsed time. We used the elapsed time measurement version (denoted by file type .CLOCK) for the i960MC target processor. Script files were developed to support compiling, linking, and executing the Ada 9X ACEC tests developed by TRW. These script files are compatible with the script files provided with the ACEC Version 2.1 distribution. The script files include: ACEC_Init.com - Performs setup initialization required to build and execute tests. CMP.com - Creates an expanded Ada source file (i.e. processes the pragma INCLUDE statements), and then compiles and links the test. Compile_ACEC.com - Builds the ACEC baseline and all the Ada 9X ACEC tests from scratch using the Ada 9X version of the Tartan VMS/960MC compilation system. Compile_Baseline.com - Performs setup of the ACEC baseline, including selection of the proper "include" files, and compilation of the math library and the other library units upon which it depends. Compile_Test_Suite_9X.com - Compiles and links the Ada 9X ACEC tests developed by TRW. Compile_Tools.com - Compiles the ACEC tools including the "INCLUDE" preprocessing utility. Run_ACEC_9X.com - Executes all the Ada 9X ACEC tests on the EXV- 960MC target processor. Run_i960.com - Executes a specified ACEC test on the EXV-960MC target processor. The user that chooses to build and execute all the Ada 9X ACECs as a set need only invoke the Compile_ACEC and the Run_ACEC_9X scripts respectively. These scripts invoke the other scripts as needed. Further detail on ACEC Version 2.1 is provided in [3], [4], and [5]. 3.2 Test Descriptions A total of fifteen ACEC tests were developed for evaluating the Ada 9X language features implemented by Tartan. This is certainly not intended as an exhaustive set and development of a suitably comprehensive ACEC is beyond the scope of this effort. The fifteen tests are named: PROT_REC1, PROT_REC2, PROT_REC3, PROT_REC4, PROT_REC_NEW1, PROT_REC_NEW2, PROT_REC_NEW3, INTRPT_NEW1, INTRPT_NEW2, QUEUING_NEW1, QUEUING_NEW2, EVENT_TEST_NEW1, EVENT_TEST_NEW2, EVENT_TEST_NEW3, CRITICAL_REGION_TEST_NEW1, and DYN_PRI_NEW1. The first four tests are equivalent to the ACEC Version 2.1 tests named TASK1 through TASK4 except they are implemented using protected records instead of task entries. The other three tests are unique. Each test is described individually in the following paragraphs. 3.2.1 PROT_REC_NEW1 The PROT_REC_NEW1 test is shown in Figure 23. It is useful for evaluating the overhead of protected procedure and entry calls when there are no tasks queued at the entries of the protected record. Timing of a normal (unprotected) procedure is also performed for comparison purposes. This test includes a protected record object that contains a simple protected procedure and entry. The barrier of the entry always evaluates to true. An unprotected procedure, identical to the protected procedure is also provided. Calls to each of these three operations are timed individually using separate timing loops. 3.2.2 PROT_REC_NEW2 The PROT_REC_NEW2 test is shown in Figure 24. It is useful for evaluating the combined overhead associated with a protected procedure call, entry body execution, and a protected entry call. In this test, a high priority task is used that queues a call to a protected entry causing it to be suspended, thereby allowing the main test procedure to execute. The main test procedure issues a call to a protected procedure of the same protected record that simply changes the state of a component causing the barrier expression of the queued task to evaluate to true. The entry body is then executed on behalf of the high priority task which resets the record component to its original value. Control is returned to the high priority task which queues a new call to the protected entry. This process is repeated by the single timing loop enough times to collect measurable timing data. 3.2.3 PROT_REC_NEW3 The PROT_REC_NEW3 test is shown in Figure 25. This test is useful for evaluating the performance impact that queued calls have on calls to protected operations. The test includes a protected record having sixteen entries. At procedure PROT_REC_NEW1 is task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'(SYSTEM.PRIORITY'FIRST+1)); end MAIN; protected PROT_REC is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry E1; procedure P1; private record COMPONENT1 : BOOLEAN := FALSE; end PROT_REC; protected body PROT_REC is entry E1 when not COMPONENT1 is begin PROC0; end E1; procedure P1 is begin PROC0; end P1; end PROT_REC; procedure PROC1 is begin PROC0; end PROC1; task body MAIN is begin pragma INCLUDE("INITTIME"); . . . pragma INCLUDE("STARTIME"); PROC1; -- Normal procedure call pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . pragma INCLUDE("STARTIME"); PROT_REC.P1; -- Protected procedure call pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . pragma INCLUDE("STARTIME"); PROT_REC.E1; -- Protected entry call pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); end MAIN; begin null; end PROT_REC_NEW1; Figure 23. ACEC Test "PROT_REC_NEW1" procedure PROT_REC_NEW2 is . . . DONE : BOOLEAN := FALSE; pragma SHARED (DONE); task TASK1 is pragma PRIORITY (SYSTEM.PRIORITY'LAST); end TASK1; protected PR1 is procedure PROC1; entry ENTRY1; private record VALUE : BOOLEAN; end PR1; protected body PR1 is procedure PROC1 is begin VALUE := TRUE; end PROC1; entry ENTRY1 when VALUE is begin VALUE := FALSE; end ENTRY1; end PR1; task body TASK1 is begin while not DONE loop PR1.ENTRY1; end loop; exception when others => TEXT_IO.PUT_LINE (">>> Task1 - Unhandled Exception"); end TASK1; begin pragma INCLUDE("inittime"); pragma INCLUDE("startime"); PR1.PROC1; pragma INCLUDE("stoptime0"); . . . pragma INCLUDE("stoptime2"); end PROT_REC_NEW2; Figure 24. ACEC Test "PROT_REC_NEW2" procedure PROT_REC_NEW3 is type BIT_ARRAY is array (INTEGER range <>) of BOOLEAN; protected PROT_REC is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry E00; entry E01; entry E02; entry E03; entry E04; entry E05; entry E06; entry E07; entry E08; entry E09; entry E10; entry E11; entry E12; entry E13; entry E14; entry E15; entry E16; procedure P1; -- does not cause any entry callers to be dequeued procedure P2; -- causes callers of entries e09-e16 to be dequeued procedure P3; -- causes callers of entries e05-e08 to be dequeued procedure P4; -- causes callers of entries e03-e04 to be dequeued procedure P5; -- causes callers of entries e02 to be dequeued procedure P6; -- causes callers of entries e01 to be dequeued private record FLAGS : BIT_ARRAY (1..16) := (others => FALSE); end PROT_REC; task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'FIRST+1); end MAIN; task T01 is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end T01; task T02 is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end T02; task T03 is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end T03; . . . task T16 is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end T16; protected body PROT_REC is entry E00 when TRUE is begin PROC0; end E00; entry E01 when FLAGS(01) is begin PROC0; end E01; entry E02 when FLAGS(02) is begin PROC0; end E02; . . . entry E16 when FLAGS(16) is begin PROC0; end e16; procedure P1 is begin PROC0; end P1; procedure P2 is begin PROC0; FLAGS(9..16) := (others => TRUE); end P2; procedure P3 is begin PROC0; FLAGS(5..8) := (others => TRUE); end P3; procedure P4 is begin PROC0; FLAGS(3..4) := (others => TRUE); end P4; procedure P5 is begin PROC0; FLAGS(2) := TRUE; end P5; procedure P6 is begin PROC0; FLAGS(1) := TRUE; end P6; end PROT_REC; Figure 25. ACEC Test "PROT_REC_NEW3" task body T01 is begin PROT_REC.E01; end T01; task body T02 is begin PROT_REC.E02; end T02; task body T03 is begin PROT_REC.E03; end T03; . . . task body T16 is begin PROT_REC.E16; end T16; task body MAIN is begin . . . pragma INCLUDE("STARTIME"); PROT_REC.P1; -- Protected procedure call with 16 callers Q'ed pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); pragma INCLUDE("STARTIME"); PROT_REC.E00; -- Protected entry call with 16 callers Q'ed" pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); PROT_REC.P2; -- Dequeue 8 protected record callers ------------------------------------------------------------------------- pragma INCLUDE("STARTIME"); PROT_REC.P1; -- Protected procedure call with 8 callers Q'ed pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); pragma INCLUDE("STARTIME"); PROT_REC.E00; -- Protected entry call with 8 callers Q'ed pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); PROT_REC.P3; -- Dequeue 4 protected record callers ------------------------------------------------------------------------- . . . ------------------------------------------------------------------------- pragma INCLUDE("STARTIME"); PROT_REC.P1; -- Protected procedure call with no callers Q'ed pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); pragma INCLUDE("STARTIME"); PROT_REC.E00; -- Protected entry call with no callers Q'ed pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); end MAIN; begin null; end PROT_REC_NEW3; Figure 25. ACEC Test "PROT_REC_NEW3" (continued) most one caller is queued at each entry and entry body execution is not performed as part of the timing loops. Protected procedure and entry calls are individually timed with calls queued at 16, 8, 4, 2, 1 and 0 of the entries. 3.2.4 PROT_REC1 The PROT_REC1 test, shown in Figure 26, is useful for evaluating the overhead of protected record creation. This test simply calls a procedure that declares a local protected record object from within a loop that is executed ten times. This test is similar to the TASK1 test provided with the ACEC distribution. 3.2.5 PROT_REC2 The PROT_REC2 test, shown in Figure 27, is useful for evaluating the overhead associated with the declaration of multiple protected records within the same declarative part. It contains a procedure that declares ten objects of the same protected record type. This test is similar to the TASK2 test provided with the ACEC distribution. 3.2.6 PROT_REC3 The PROT_REC3 test, shown in Figure 28, measures the overhead of a protected record implementation enforcing mutually exclusive access to a "resource". The protected record contains two protected entries with barrier expressions that are the logical negations of each other. This test is similar to the TASK3 test provided with the ACEC distribution. 3.2.7 PROT_REC4 The PROT_REC4 test, shown in Figure 29, measures the overhead of a protected record implementing a buffer of objects of type STRING. A protected record is used that contains two entries called READ and WRITE. The barrier expression for READ causes calls to be queued when the buffer is empty and the barrier for WRITE causes calls to be queued when the buffer is full. The timing loop contains two calls to WRITE followed by two calls to READ, for a total of four protected entry calls. This test is similar to the TASK4 test provided with the ACEC distribution. 3.2.8 CRITICAL_REGION_TEST_NEW1 The CRITICAL_REGION_TEST_NEW1 test, shown in Figure 30, measures the overhead of a critical region implemented using task entries and protected records. In the tasking implementation, the critical code is executed in an accept body. procedure PROT_REC1 is procedure MAKE_PROTECTED_RECORD is protected SIMPLE_PROTECTED_RECORD is private record null; end SIMPLE_PROTECTED_RECORD; protected body SIMPLE_PROTECTED_RECORD is -- this is a very very simple protected record ! end SIMPLE_PROTECTED_RECORD; begin null; -- this is a very simple procedure also end MAKE_PROTECTED_RECORD; begin pragma INCLUDE("INITTIME"); pragma INCLUDE("STARTIME"); for I in 1 .. 10 loop MAKE_PROTECTED_RECORD; -- invoke procedure which declares a protected rec end loop; pragma INCLUDE("STOPTIME0"); . . . pragma INCLUDE ("STOPTIME2"); end PROT_REC1; Figure 26. ACEC Test "PROT_REC1" procedure PROT_REC2 is procedure MAKE_PROTECTED_RECORD is protected type SIMPLE_PROTECTED_RECORD is private record null; end SIMPLE_PROTECTED_RECORD; PR1,PR2,PR3,PR4,PR5,PR6,PR7,PR8,PR9,PR10 : SIMPLE_PROTECTED_RECORD; protected body SIMPLE_PROTECTED_RECORD is -- this is a very very simple protected record ! end SIMPLE_PROTECTED_RECORD; begin null; end MAKE_PROTECTED_RECORD; begin pragma INCLUDE("STARTIME"); for C in 1 .. 10 loop MAKE_PROTECTED_RECORD; end loop; pragma INCLUDE("STOPTIME0"); . . . pragma INCLUDE("STOPTIME2"); end PROT_REC2; Figure 27. ACEC Test "PROT_REC2" procedure PROT_REC3 is task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'(2)); end MAIN; protected RESOURCE is entry REQUEST; entry RELEASE; private record IN_USE : BOOLEAN := FALSE; end RESOURCE; protected body RESOURCE is entry REQUEST when not IN_USE is begin IN_USE := TRUE; end REQUEST; entry RELEASE when IN_USE is begin IN_USE := FALSE; end RELEASE; end RESOURCE; task body MAIN is begin pragma INCLUDE("INITTIME"); pragma INCLUDE("STARTIME"); for I in 1 .. 10 loop RESOURCE.REQUEST; RESOURCE.RELEASE; end loop; pragma INCLUDE("STOPTIME0"); . . . end MAIN; begin null; end PROT_REC3; Figure 28. ACEC Test "PROT_REC3" package P4 is subtype IMAGE is STRING(1 .. 10); X1 : IMAGE := "abcdefghij"; X2 : IMAGE := "0123456789"; Y : IMAGE; end P4; package body P4 is null; end P4; procedure PROT_REC4 is . . . N : constant := 10; -- # of images to be buffered type IMAGE_LIST is array (INT range INT'(1) .. INT'(n)) of IMAGE; protected BUFFER is entry READ (X : out IMAGE); entry WRITE (X : in IMAGE); private record LIST : IMAGE_LIST; -- image storage buffer I : INT range 1 .. N := 1; -- i = write index J : INT range 1 .. N := 1; -- j = read index C : INT range 0 .. N := 0; -- count of images in buffer end BUFFER; protected body BUFFER is entry READ (X : out IMAGE) when C > 0 is begin X := LIST(J); J := J mod N + 1; C := C - 1; end READ; entry WRITE (X : in IMAGE) when C < N is begin LIST(I) := X; I := I mod N + 1; C := C + 1; end WRITE; end BUFFER; task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'(2)); end MAIN; task body MAIN is begin pragma INCLUDE("INITTIME"); pragma INCLUDE("STARTIME"); BUFFER.WRITE(P4.X1); BUFFER.WRITE(P4.X2); BUFFER.read(P4.Y); BUFFER.read(P4.Y); pragma INCLUDE("STOPTIME0"); . . . pragma INCLUDE("STOPTIME2"); end MAIN; begin -- main program null; end PROT_REC4; Figure 29. ACEC Test "PROT_REC4" procedure CRITICAL_REGION_TEST_NEW1 is . . . protected CRITICAL_REGION_PR is procedure COMPUTE_VALUE; private record null; end CRITICAL_REGION_PR; task CRITICAL_REGION_T is entry COMPUTE_VALUE; end CRITICAL_REGION_T; protected body CRITICAL_REGION_PR is procedure COMPUTE_VALUE is begin -- Code to be executed as an atomic operation null; end COMPUTE_VALUE; end CRITICAL_REGION_PR; task body CRITICAL_REGION_T is begin loop select accept COMPUTE_VALUE do -- Code to be executed as an atomic operation null; end COMPUTE_VALUE; or terminate; end select; end loop; end CRITICAL_REGION_T; begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); CRITICAL_REGION_PR.COMPUTE_VALUE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . pragma INCLUDE("startime"); CRITICAL_REGION_T.COMPUTE_VALUE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); end CRITICAL_REGION_TEST_NEW1; Figure 30. ACEC Test "CRITICAL_REGION_TEST_NEW1" A protected procedure is used in the protected record implementation. Two timing loops are used. One issues a call to the task entry and the other calls the protected procedure. 3.2.9 DYN_PRI_NEW1 The DYN_PRI_NEW1 test, shown in Figure 31, is designed to measure the overhead of a changing the priority of a task using the Ada 9X procedure SET_PRIORITY provided in package DYNAMIC_PRIORITY_SUPPORT. Two timing loops are implemented. The first loop executes while no other tasks are eligible. It contains two calls to SET_PRIORITY, one that assigns the executing task a new priority and the other that sets it back to its original value. This does not cause any context switches since no other tasks are ready to run. The second timing loop executes while one other (initially lower priority) task is eligible to execute. The timing loop calls SET_PRIORITY to decrease its own priority. The test design assumes this would cause a context switch to the other task which simply resets the priority of the main task back to its original value, making it the highest priority of tasks eligible for execution. Execution of this and other tests revealed that the compiler being evaluated did not cause immediate re-evaluation of the task to execute based on calls to SET_PRIORITY. At the time of this report, Tartan is seeking clarification from the Mapping Team on the relationships of base and active priorities. As a result, timing data for this test is not provided. 3.2.10 EVENT_TEST_NEW1 The EVENT_TEST_NEW1 test, shown in Figure 32, measures the overhead of a tasking implementation of an event capability. This event is implemented such that all callers queued at the time of a "SIGNAL" operation are dequeued. Two variations are implemented, one that is signaled by direct call and another that is signaled by an interrupt. Two timing loops are used. One contains a direct call to "signal" the event and the other calls CAUSE_IAC_INTERRUPT to raise an interrupt which in turn invokes the "signal" operation. A single task wakes up each time the event is signaled and re-issues its call to "WAIT". 3.2.11 EVENT_TEST_NEW2 The EVENT_TEST_NEW2 test, shown in Figure 33, measures the overhead of a protected record implementation of an event capability implemented in "EVENT_TEST_NEW1". This particular implementation uses protected entries for both the "SIGNAL" and "WAIT" operations. Since protected entries cannot be procedure DYN_PRI_NEW1 is . . . task MAIN is pragma PRIORITY(8); end MAIN; task OTHER is pragma PRIORITY(6); entry GO; end OTHER; MAIN_TCB : CLIENT_SUPPORT.TCB; -- Tartan Specific (interim) OTHER_TCB : CLIENT_SUPPORT.TCB; -- Tartan Specific (interim) protected PRIORITY_CONTROL is procedure SET_MAIN_HIGHER; procedure SET_MAIN_LOWER; pragma PRIORITY (SYSTEM.PRIORITY'LAST); private record null; end PRIORITY_CONTROL; protected body PRIORITY_CONTROL is procedure SET_MAIN_HIGHER is begin DYNAMIC_PRIORITY_SUPPORT.SET_PRIORITY ( T => MAIN_TCB, PRIORITY => 9); end SET_MAIN_HIGHER; procedure SET_MAIN_LOWER is begin DYNAMIC_PRIORITY_SUPPORT.SET_PRIORITY ( T => MAIN_TCB, PRIORITY => 5); end SET_MAIN_LOWER; end PRIORITY_CONTROL; task body OTHER is begin OTHER_TCB := USER_CLIENT.MY_TCB; accept GO; loop PRIORITY_CONTROL.SET_MAIN_HIGHER; end loop; end other; task body MAIN is begin pragma INCLUDE("inittime"); main_tcb := user_client.my_tcb; . . . pragma INCLUDE("startime"); for I in 1..10 loop PRIORITY_CONTROL.SET_MAIN_LOWER; PRIORITY_CONTROL.SET_MAIN_HIGHER; end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . OTHER.GO; -- start other task pragma INCLUDE("startime"); for I in 1..10 loop PRIORITY_CONTROL.SET_MAIN_LOWER; END LOOP; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); end MAIN; begin null; end DYN_PRI_NEW1; Figure 31. ACEC Test "DYN_PRI_NEW1" procedure EVENT_TEST_NEW1 is . . . task EVENT is entry WAIT; entry SIGNAL; pragma PRIORITY (SYSTEM.PRIORITY'LAST); end EVENT; task INTERRUPT_EVENT is entry WAIT; entry SIGNAL; for SIGNAL use at 144; pragma PRIORITY (SYSTEM.PRIORITY'LAST); end INTERRUPT_EVENT; task WAITER is pragma PRIORITY(SYSTEM.PRIORITY'LAST-1); end WAITER; task INTERRUPT_WAITER is pragma PRIORITY(SYSTEM.PRIORITY'LAST-1); end INTERRUPT_WAITER; task body WAITER is begin loop EVENT.WAIT; end loop; end WAITER; task body INTERRUPT_WAITER is begin loop INTERRUPT_EVENT.WAIT; end loop; end INTERRUPT_WAITER; task body EVENT is begin loop accept SIGNAL do loop select accept WAIT; else exit; end select; end loop; end SIGNAL; end loop; end EVENT; task body INTERRUPT_EVENT is begin loop accept SIGNAL do loop select accept WAIT; else exit; end select; end loop; end SIGNAL; end loop; end INTERRUPT_EVENT; Figure 32. ACEC Test "EVENT_TEST_NEW1" begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); EVENT.SIGNAL; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . pragma INCLUDE("startime"); SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT(INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_144); pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . end EVENT_TEST_NEW1; Figure 32. ACEC Test "EVENT_TEST_NEW1" (continued) procedure EVENT_TEST_NEW2 is . . . protected EVENT is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry WAIT; entry SIGNAL; private entry RESET; record OCCURRED : BOOLEAN := FALSE; end EVENT; task WAITER is pragma PRIORITY(SYSTEM.PRIORITY'LAST-1); end WAITER; protected body EVENT is entry WAIT when OCCURRED; entry SIGNAL when TRUE is begin OCCURRED := TRUE; requeue RESET; end SIGNAL; entry RESET when WAIT'COUNT = 0 is begin OCCURRED := FALSE; end RESET; end EVENT; task body WAITER is begin loop EVENT.WAIT; end loop; end WAITER; begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); EVENT.SIGNAL; USER_CLIENT.RESCHEDULE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . end EVENT_TEST_NEW2; Figure 33. ACEC Test "EVENT_TEST_NEW2" bound to interrupts, a single timing loop is provided that measures direct calls to "SIGNAL". 3.2.12 EVENT_TEST_NEW3 The EVENT_TEST_NEW3 test, shown in Figure 34, measures the overhead of another protected record implementation of the event capability implemented in "EVENT_TEST_NEW1". Two timing loops are provided and are functionally equivalent to those described for "EVENT_TEST_NEW1". 3.2.13 LOCK_TEST_NEW1 The LOCK_TEST_NEW1 test, shown in Figure 35, measures the overhead of a protected record and tasking implementation of a simple lock. Both implementations provide "ACQUIRE" and "RELEASE" operations. Two timing loops are used, one calls ACQUIRE and RELEASE of the tasking implementation and the other calls ACQUIRE and RELEASE of the protected record implementation. The test is designed such that the calls are not queued. 3.2.14 QUEUING_NEW1 The QUEUING_NEW1 test, shown in Figure 36, measures the overhead of FIFO and PRIORITY queuing to protected record entries. This is accomplished using a protected record implementing a task queue with operations SUSPENDME, WAKEUP_HEAD and RESET. A variable number of tasks queue themselves on the task queue. Separate timing loops, each issuing a call to WAKEUP_HEAD, are used to measure overhead with 0, 1, 2, 4, 8, and 14 queued callers. Separate versions of this test were built using the FIFO-queuing and priority-queuing runtime. 3.2.15 QUEUING_NEW2 The QUEUING_NEW2 test, shown in Figure 37, measures the overhead of FIFO and PRIORITY queuing of calls to task entries. This is accomplished using a task implementing a task queue with operations SUSPENDME, WAKEUP_HEAD and RESET. A variable number of tasks queue themselves on the task queue. Separate timing loops, each issuing a call to WAKEUP_HEAD, are used to measure overhead with 0, 1, 2, 4, 8, and 14 queued callers. This test is analogous to the QUEUING_NEW1 test for protected records. Separate versions were built using the FIFO-queuing and priority-queuing runtime. 3.2.16 INTRPT_NEW1 The INTRPT_NEW1 test, shown in Figure 38, measures the overhead associated with interrupt (task) entries. The first timing loop measures the overhead of package EVENT_TEST_NEW3_HANDLER is protected INTERRUPT_EVENT is pragma INTERRUPT_PRIORITY(18); entry WAIT; procedure SIGNAL; private entry WAIT_A; entry WAIT_B; record SWITCH : BOOLEAN := FALSE; end INTERRUPT_EVENT; end EVENT_TEST_NEW3_HANDLER; package body EVENT_TEST_NEW3_HANDLER is protected body INTERRUPT_EVENT is procedure SIGNAL is begin SWITCH := not SWITCH; end SIGNAL; entry WAIT when TRUE is begin if SWITCH then requeue WAIT_B; else requeue WAIT_A; end if; end WAIT; entry WAIT_A when SWITCH; entry WAIT_B when not SWITCH; end INTERRUPT_EVENT; HANDLER : INTERRUPT_MANAGEMENT.HANDLER_TYPE := INTERRUPT_MANAGEMENT.TICK_ACCESS_PROTECTED_PROCEDURE ( INSTANCE => EVENT_TEST_NEW3_HANDLER. INTERRUPT_EVENT'ADDRESS, PROTECTED_PROCEDURE => EVENT_TEST_NEW3_HANDLER. INTERRUPT_EVENT.SIGNAL'ADDRESS); begin INTERRUPT_MANAGEMENT.ATTACH_INTERRUPT_HANDLER ( HANDLER, INTERRUPT_MANAGEMENT.INTERRUPT_NAMES.VECTOR_145); end EVENT_TEST_NEW3_HANDLER; . . . procedure EVENT_TEST_NEW3 is . . . protected EVENT is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry WAIT; procedure SIGNAL; private entry WAIT_A; entry WAIT_B; record SWITCH : BOOLEAN := FALSE; end EVENT; task WAITER is pragma PRIORITY(SYSTEM.PRIORITY'LAST-1); end WAITER; task INTERRUPT_WAITER is pragma PRIORITY(SYSTEM.PRIORITY'LAST-1); end INTERRUPT_WAITER; Figure 34. ACEC Test "EVENT_TEST_NEW3" protected body EVENT is procedure SIGNAL is begin SWITCH := not SWITCH; end SIGNAL; entry WAIT when TRUE is begin if SWITCH then requeue WAIT_B; else requeue WAIT_A; end if; end WAIT; entry WAIT_A when SWITCH; entry WAIT_B when not SWITCH; end EVENT; task body WAITER is begin loop EVENT.WAIT; end loop; end WAITER; task body INTERRUPT_WAITER is begin loop EVENT_TEST_NEW3_HANDLER.INTERRUPT_EVENT.WAIT; end loop; end INTERRUPT_WAITER; begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); EVENT.SIGNAL; USER_CLIENT.RESCHEDULE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . pragma INCLUDE("startime"); SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT(INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_145); USER_CLIENT.RESCHEDULE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . end EVENT_TEST_NEW3; Figure 34. ACEC Test "EVENT_TEST_NEW3" (continued) procedure LOCK_TEST_NEW1 is . . . protected LOCK_PR is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry ACQUIRE; procedure RELEASE; record LOCKED : BOOLEAN := false; end LOCK_PR; protected body LOCK_PR is entry ACQUIRE when not LOCKED is begin LOCKED := true; end ACQUIRE; procedure RELEASE is begin LOCKED := false; end RELEASE; end LOCK_PR; task LOCK_T is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry ACQUIRE; entry RELEASE; end LOCK_T; task body LOCK_T is begin loop accept ACQUIRE; accept RELEASE; end loop; end LOCK_T; begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); LOCK_T.ACQUIRE; LOCK_T.RELEASE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . pragma INCLUDE("startime"); LOCK_PR.ACQUIRE; LOCK_PR.RELEASE; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . end LOCK_TEST_NEW1; Figure 35. ACEC Test "LOCK_TEST_NEW1" procedure QUEUING_NEW1 is . . . protected type TASKQ is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry SUSPENDME; procedure WAKEUP_HEAD; procedure RESET; private record WAKEUP_PENDING : BOOLEAN := FALSE; end TASKQ; . . . task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end MAIN; -- NOTE! The following task types can be replaced with a single task type -- with a discriminant used to vary the priority (once this feature -- is implemented). task type T01TYPE is pragma PRIORITY(SYSTEM.PRIORITY'FIRST+1); entry GO; end T01TYPE; for T01TYPE'STORAGE_SIZE use 16#400#; . . . task type T14TYPE is pragma PRIORITY(SYSTEM.PRIORITY'FIRST+14); entry GO; end T14TYPE; for T14TYPE'STORAGE_SIZE use 16#400#; T01 : T01TYPE; . . . T14 : T14TYPE; TQ : TASKQ; protected body TASKQ is procedure WAKEUP_HEAD is begin WAKEUP_PENDING := TRUE; end WAKEUP_HEAD; procedure RESET is begin WAKEUP_PENDING := FALSE; end RESET; entry SUSPENDME when WAKEUP_PENDING is begin WAKEUP_PENDING := FALSE; end SUSPENDME; end TASKQ; task body T01TYPE is begin accept GO; loop TQ.SUSPENDME; end loop; end T01TYPE; . . . task body T14TYPE is begin accept GO; loop TQ.SUSPENDME; end loop; end T14TYPE; Figure 36. ACEC Test "QUEUING_NEW1" task body MAIN is begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- protected procedure call USER_CLIENT.RESCHEDULE; -- workaround; ensure rescheduling end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); TQ.RESET; . . . T01.GO; -- place a caller on entry queue USER_CLIENT.RESCHEDULE; -- workaround; ensure caller(s) get Q'ed pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue/requeue a caller USER_CLIENT.RESCHEDULE; -- workaround; ensure rescheduling end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . T02.GO; -- place another caller on entry queue USER_CLIENT.RESCHEDULE; -- workaround; ensure caller(s) get Q'ed pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue a caller USER_CLIENT.RESCHEDULE; -- workaround; ensure rescheduling end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . T09.GO; -- place another caller on entry queue T10.GO; -- place another caller on entry queue T11.GO; -- place another caller on entry queue T12.GO; -- place another caller on entry queue T13.GO; -- place another caller on entry queue T14.GO; -- place another caller on entry queue USER_CLIENT.RESCHEDULE; -- workaround; ensure caller(s) get Q'ed pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue a caller USER_CLIENT.RESCHEDULE; -- workaround; ensure rescheduling end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . end MAIN; begin null; end QUEUING_NEW1; Figure 36. ACEC Test "QUEUING_NEW1" (continued) procedure QUEUING_NEW2 is . . . task type TASKQ is pragma PRIORITY(SYSTEM.PRIORITY'LAST); entry SUSPENDME; entry WAKEUP_HEAD; entry RESET; end TASKQ; task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'FIRST); end MAIN; -- NOTE! The following task types can be replaced with a single task type -- with a discriminant used to vary the priority (once this feature -- is implemented). task type T01TYPE is pragma PRIORITY(SYSTEM.PRIORITY'FIRST+1); entry GO; end T01TYPE; for T01TYPE'STORAGE_SIZE use 16#400#; . . . task type T14TYPE is pragma PRIORITY(SYSTEM.PRIORITY'FIRST+14); entry GO; end T14TYPE; for T14TYPE'STORAGE_SIZE use 16#400#; T01 : T01TYPE; . . . T14 : T14TYPE; TQ : TASKQ; task body TASKQ is WAKEUP_PENDING : BOOLEAN := FALSE; begin loop select accept WAKEUP_HEAD; WAKEUP_PENDING := TRUE; or when WAKEUP_PENDING => accept SUSPENDME; WAKEUP_PENDING := FALSE; or accept RESET; WAKEUP_PENDING := FALSE; or terminate; end select; end loop; end TASKQ; Figure 37. ACEC Test "QUEUING_NEW2" task body T01TYPE is begin accept GO; loop TQ.SUSPENDME; end loop; end T01TYPE; . . . task body T14TYPE is begin accept GO; loop TQ.SUSPENDME; end loop; end T14TYPE; task body MAIN is begin pragma INCLUDE("inittime"); . . . pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- protected procedure call end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); TQ.RESET; . . . T01.GO; -- place a caller on entry queue pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue a caller end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . T02.GO; -- place another caller on entry queue pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue a caller end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); . . . T09.GO; -- place another caller on entry queue T10.GO; -- place another caller on entry queue T11.GO; -- place another caller on entry queue T12.GO; -- place another caller on entry queue T13.GO; -- place another caller on entry queue T14.GO; -- place another caller on entry queue pragma INCLUDE("startime"); for I in 1..10 loop TQ.WAKEUP_HEAD; -- dequeue a caller end loop; pragma INCLUDE("stoptime0"); pragma INCLUDE("stoptime2"); end MAIN; begin null; end QUEUING_NEW2; Figure 37. ACEC Test "QUEUING_NEW2" (continued) package ENTRY_HANDLER is INTERRUPT_OCCURRED : BOOLEAN := FALSE; end ENTRY_HANDLER; . . . package body ENTRY_HANDLER is task INTERRUPT_EVENT is entry SIGNAL; for SIGNAL use at 146; pragma PRIORITY(17); end INTERRUPT_EVENT; task body INTERRUPT_EVENT is begin loop select accept SIGNAL do PROC0; INTERRUPT_OCCURRED := TRUE; end SIGNAL; or terminate; end select; end loop; end INTERRUPT_EVENT; end ENTRY_HANDLER; . . . procedure INTRPT_NEW1 is . . . task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'(SYSTEM.PRIORITY'FIRST)); end MAIN; task body MAIN is begin . . . pragma INCLUDE("STARTIME"); for I in 1..10 loop SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT(INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_144); end loop; pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . pragma INCLUDE("STARTIME"); for I in 1..10 loop SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT (INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_146); loop exit when ENTRY_HANDLER.INTERRUPT_OCCURRED; end loop; ENTRY_HANDLER.INTERRUPT_OCCURRED := FALSE; end loop; pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . end MAIN; begin null; end INTRPT_NEW1; Figure 38. ACEC Test "INTRPT_NEW1" the interrupt delivery mechanism. It assumes that interrupt 144 is vectored to i960MC "RET" instruction which simply returns from the interrupt. The second timing loop measures the overhead required to signal an interrupt for which an interrupt entry has been specified. 3.2.17 INTRPT_NEW2 The INTRPT_NEW2 test, shown in Figure 39, measures the overhead of signaling an interrupt bound to a protected procedure. The first timing loop measures the overhead of the interrupt delivery mechanism. It assumes that interrupt 144 is vectored to i960MC "RET" instruction which simply returns from the interrupt. The second timing loop measures the overhead required to signal an interrupt for which an interrupt entry has been specified. This test is analogous to the INTRPT_NEW1 test. 3.2.18 Results The timing results obtained by executing the protected record tests on the EXV-960MC target processor are provided in Table X. For comparison purposes, timing results for the ACEC Version 2.1 tests "Task1", "Task2", "Task3", and "Task4" are also included. The Tartan Ada 9X.4.0 version of their VMS/960MC tool set was used to build, download, and execute all the tests. All tests were performed with both the FIFO-queuing and priority-queuing runtimes. 3.3 Recommendations Enhancement of the ACEC to support comprehensive evaluation of protected records will require many tests in addition to those developed by TRW on this effort. Such tests should provide potential users with insight into performance as well limits imposed by the tool sets. They should also help potential users assess the adequacy of solutions to the implementation-defined parts of the language. A few issues, related to evaluating protected records, that should be addressed by the ACEC are: * Identify stack requirement implications of protected record usage. For example, "are entry bodies for queued entry calls executed from the context of the original caller of the entry or from that of the caller of the protected operation that causes the call to be dequeued?". * Performance tests for entry calls, conditional entry calls, timed entry calls, and selective entry calls to protected record entries. * Performance tests for the requeue statement used to requeue calls to entries of the same and different protected records. * Tests to ensure storage space for protected record control structures is reclaimed when no longer needed. For example, ensure space for Protected package PROT_PROC_HANDLER is INTERRUPT_OCCURRED : BOOLEAN := FALSE; end PROT_PROC_HANDLER; . . . package body PROT_PROC_HANDLER is . . . protected INTERRUPT_EVENT is pragma INTERRUPT_PRIORITY(18); procedure SIGNAL; private record null; end INTERRUPT_EVENT; protected body INTERRUPT_EVENT is procedure SIGNAL is begin PROC0; INTERRUPT_OCCURRED := TRUE; end SIGNAL; end INTERRUPT_EVENT; HANDLER : INTERRUPT_MANAGEMENT.HANDLER_TYPE := INTERRUPT_MANAGEMENT.TICK_ACCESS_PROTECTED_PROCEDURE ( INSTANCE => PROT_PROC_HANDLER.INTERRUPT_EVENT'ADDRESS, PROTECTED_PROCEDURE => PROT_PROC_HANDLER.INTERRUPT_EVENT. SIGNAL'ADDRESS); begin INTERRUPT_MANAGEMENT.ATTACH_INTERRUPT_HANDLER ( HANDLER, INTERRUPT_MANAGEMENT.INTERRUPT_NAMES.VECTOR_145); end PROT_PROC_HANDLER; . . . procedure INTRPT_NEW2 is . . . task MAIN is pragma PRIORITY(SYSTEM.PRIORITY'(SYSTEM.PRIORITY'FIRST)); end MAIN; task body MAIN is begin . . . pragma INCLUDE("INITTIME_INTRPT"); -- customized to avoid problem -- with tool set -- NOTE: The address of a "RET" instruction must be placed in interrupt -- vector #144 (e.g. using the debugger) prior to this point. pragma INCLUDE("STARTIME_INTRPT"); -- customized to avoid problem -- with tool set for I in 1..10 loop SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT(INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_144); end loop; pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . pragma INCLUDE("STARTIME_INTRPT"); -- customized to avoid problem -- with tool set for I in 1..10 loop SOFTWARE_INTERRUPTS.CAUSE_IAC_INTERRUPT(INTERRUPT_MANAGEMENT. INTERRUPT_NAMES.VECTOR_145); loop exit when PROT_PROC_HANDLER.INTERRUPT_OCCURRED; end loop; PROT_PROC_HANDLER.INTERRUPT_OCCURRED := FALSE; end loop; pragma INCLUDE("STOPTIME0"); pragma INCLUDE("STOPTIME2"); . . . end MAIN; begin null; end INTRPT_NEW2; Figure 39. ACEC Test "INTRPT_NEW2" Execution Times (Micro Seconds) Test Timing Loop Fifo-Qing Pri-Qing ------------- ----------------------------------- --------- -------- PROT_REC_NEW1 Normal (Unprotected) Procedure Call 0.7 0.7 Protected Procedure Call 31.0 31.0 Protected Entry Call 48.0 47.9 PROT_REC_NEW2 Protected Procedure Call, Entry 230.7 229.6 Body Execution and Protected Entry Call PROT_REC_NEW3 Protected Procedure Calls: with 16 Callers Q'ed 144.6 143.0 with 8 Callers Q'ed 81.9 78.8 with 4 Callers Q'ed 62.4 62.0 with 2 Callers Q'ed 48.0 48.3 with 1 Callers Q'ed 41.6 41.4 with 0 Callers Q'ed 34.7 34.1 Protected Entry Calls: with 16 Callers Q'ed 157.5 157.5 with 8 Callers Q'ed 97.5 95.6 with 4 Callers Q'ed 72.8 71.5 with 2 Callers Q'ed 57.2 56.4 with 1 Callers Q'ed 53.2 53.0 with 0 Callers Q'ed 44.7 44.5 PROT_REC1 Declare a protected record 408.9 408.9 object (repeat 10 times) TASK1 (ACEC V2.1) Declare a task object (repeat 3042.8 3042.8 10 times PROT_REC2 Declare 10 protected record obj- 4132.8 4132.8 ects in a single declarative part (repeat 10 times) TASK2 (ACEC V2.1) Declare 10 task objects in a 15972.6 15983.8 single declarative part (repeat 10 times) PROT_REC3 Request/release a simple resource 939.1 937.6 implemented as a protected record (repeat 10 times) Time per protected entry call 46.9 46.9 TASK3 (ACEC V2.1) Request/release a simple resource 2833.1 2826.6 implemented using task entries (repeat 10 times) Time per rendezvous 141.6 141.3 Table X. ACEC Execution Results Execution Times (Micro Seconds) Test Timing Loop Fifo-Qing Pri-Qing ------------- ----------------------------------- --------- -------- PROT_REC4 Two calls each to the write and read 217.0 219.4 protected entries (4 entry calls) Time per protected entry call 54.3 54.9 TASK4 (ACEC V2.1) Two calls each to the write and read 795.7 806.9 task entries (4 rendezvous) Time per rendezvous 198.9 201.7 INTRPT_NEW1 Interrupt entry accepted using a 2118.6 2128.9 selective-accept with terminate; Includes overhead of signaling interrupt via software (repeat 10 times) Overhead of signaling interrupt vectored to a "null" instruction 180.6 180.6 INTRPT_NEW2 Protected procedure attached to an 618.6 623.7 interrupt; includes overhead of signaling interrupt via software (repeat 10 times) QUEUING1 Wakeup head of a task queue imple- mented as a protected record: with 1 Caller Q'ed 2217.3 2151.3 with 2 Callers Q'ed 2396.2 2375.3 with 4 Callers Q'ed 2574.6 2571.5 with 8 Callers Q'ed 2817.1 2782.4 with 14 Callers Q'ed 3248.8 3175.3 Includes prot. procedure call, protected entry call, entry body execution, and call to "user_client.reschedule"; (repeat 10 times) QUEUING2 Wakeup head of a task queue imple- mented using task entries: with 1 Caller Q'ed 4122.7 4082.6 with 2 Callers Q'ed 3949.0 3925.0 with 4 Callers Q'ed 3950.8 3921.0 with 8 Callers Q'ed 4111.6 4124.9 with 14 Callers Q'ed 4204.6 4161.6 Includes two entry calls and a 3-way selective-accept with terminate (repeat 10 times) Table X. ACEC Execution Results (continued) Execution Times (Micro Seconds) Test Timing Loop Fifo-Qing Pri-Qing ------------- ----------------------------------- --------- -------- EVENT_TEST_NEW1 Signal an event implemented using task entries with one caller q'ed. Caller places itself back on the queue by calling "wait": EVENT.SIGNAL (direct call) 343.6 349.4 CAUSE_IAC_INTERRUPT 334.7 345.1 EVENT_TEST_NEW2 Signal an event implemented as a protected record with one caller q'ed. Caller places itself back on the queue by calling "wait": EVENT.SIGNAL/RESCHEDULE 281.0 296.0 EVENT_TEST_NEW3 Signal an event implemented as a protected record with one caller q'ed. Caller places itself back on the queue by calling "wait": EVENT.SIGNAL/RESHCHEDULE 239.8 236.2 CAUSE_IAC_INTERRUPT/RESCHEDULE 256.1 256.7 CRITICAL_REGION_ Perform processing protected as a TEST_NEW1 critical region: Prot. Procedure Implementation 29.6 29.5 Tasking Implementation 224.4 224.1 Table X. ACEC Execution Results (continued) Record Control Blocks is reclaimed upon exiting the scope where the protected record object is declared. * Tests to evaluate the timing and limits of protected entry families. * Performance test for the COUNT attribute. * Performance tests for the various options defined in the real-time annex for queuing calls to protected entries. Should address performance implications of various queue sizes. * Performance tests for interrupts attached to protected procedures. Should address attaching multiple interrupts to the same protected record. * Tests to expose hard limits on the number of protected records and the number of callers queued at a protected entry. * Duplicate tests using pragma INLINE. * Duplicate tests sharing protected records across multiple processors. * Determine overhead associated with attaching interrupts to protected procedures. Extra context created? Stack Requirements imposed on user stack vs. interrupt stack? Etc. * Determine the overhead of both FIFO and Priority queuing policies as they apply to task entries and protected record entries. Vary the number of callers queued as well as the order of the callers with respect to their priorities and determine how this impacts performance. 4. Conclusions Our evaluation of the Ada 9X language features consisted of the creation and evaluation of an application benchmark adapted from an avionics software set. In addition, other benchmarks including a device communication benchmark adapted from an avionics real-time executive and a semaphore benchmark were developed to give additional insight into the usefulness of these features. 4.1 Application Benchmark Analysis Six versions of the application software benchmark were developed. Version #1 employs a simple deadline scheduling approach, Version #2 performs some asynchronous processing in combination with deadline scheduling, and Version #3 is based on event-driven scheduling. Each of these benchmarks versions were enhance to process hardware interrupts, yielding benchmark versions #4, 5 and 6. All six versions were first developed using Ada 83 language constructs and later re-engineered to incorporate Ada 9X constructs, with strong emphasis on the use of protected records. Statistics were collected for each variation including lines of code, compilation times, and CPU utilization. The Ada 9X implementations were compared to their Ada 83 counterparts. In all six versions, the re-engineered implementations which use Ada 9X language features, demonstrate better performance than their baseline implementations which were limited to Ada 83 language constructs. These performance gains are primarily attributable to the replacement of task entries with protected records. Benchmark Version #1 uses a periodic deadline scheduler and does not rely on a high frequency of explicit task/data synchronization. Re-engineering this benchmark realized a reduction in overall CPU utilization from 13.0% to 11.4% for an improved throughput of approximately 12%. Benchmark Version #2 incorporates some asynchronous activity and uses locks to ensure mutually exclusive access to key databases which significantly increases the amount of rendezvous compared to Version #1. Re-engineering of this benchmark yielded an overall reduction in CPU utilization from 29.9% to 18.9%, which equates to approximately 37% of improved throughput. The third benchmark version does not implement explicit locks but does use tasking/protected records to signal the availability of updated data. Re-engineering of Benchmark Version #3 reduced CPU utilization from 44.8% to 35.9% which equates to a throughput improvement of approximately 20%. Similar performance gains were observed in the interrupt versions of this benchmark. The fourth version realized a reduction in overall CPU utilization from 13.0% to 11.5% (12% throughput improvement), the fifth version realized a reduction from 29.9% to 19.1% (36% throughput improvement), and the sixth version realized a reduction from 44.8% to 36.2% (19% throughput improvement). These data points represent performance gains realized from re- engineering application that use task entries to use protected records. However, it should should be noted that some real-time embedded systems make limited use of Ada tasking and rendezvous. Such systems use a real-time executive or direct runtime calls to implement low overhead solutions to scheduling and synchronization. Three sets of compile time statistics were collected during this activity. The first set was obtained by compiling the baseline implementation using the 4.1 Pre-Release Version of the Tartan tool set. The second and third sets were collected using the Ada 9X.4.0 version of the tool set to compile the baseline and the re-engineered implementations respectively. Comparison between these compiler versions show that the Ada 9X compiler provides better overall performance than the version 4.1 Pre-Release compiler. This improvement may be attributable to the fact that portions of the Ada 9X compiler are based on a more recent baseline than the one used to build the version 4.1 Pre-Release compiler. The lines of code statistics collected on the baseline and re-engineered implementations of each benchmark version indicate modest differences in the required lines of code (semicolons). These differences are not large enough to be significant. Conclusions to be drawn from the use of protected records in our applications are fairly simple. As can be seen in all examples presented, the use of protected records in place of tasks results in greater efficiency. In all cases, the CPU utilization percentage is reduced when protected records are used. It must be noted, however, that the CPU utilization reduction shown for Version #1 is quite a bit less than that shown for Versions #2 and #3. Our conclusion from these results is that although protected records are more efficient across the board, significant improvements are only to be found in systems using a high rate of rendezvous. In the two versions showing large increases in execution efficiency, the rate of rendezvous was much larger than in Version #1. Hence, when tasks are replaced by protected records in those systems, we see a marked increase in efficiency. It must also be noted that tasking has been avoided in some embedded real-time systems in order to meet stringent timing requirements. In many cases, vendor supplied runtime interfaces and real-time operating systems have been used in place of Ada tasking to improve performance. These choices have been made despite negative impacts on cost, portability, maintenance, and training. As indicated by the results of the semaphore example, even though protected records show a great improvement over tasking, it is doubtful they will ever meet the performance of specialized vendor supplied alternatives. However, the increased efficiency provided by protected records will make it possible for more systems to be developed without the use of such alternatives. 4.2 Semaphore Implementation Analysis A comparison was performed between counting semaphore implementations using Ada 83 tasking, Ada 9X protected records, and direct runtime calls to the ART_Semaphore package provided with the Tartan tool set. The results of executing these three versions on the EXV-960MC target processor indicate that the protected record implementation is approximately 5 times faster than the equivalent tasking implementation. In addition, the protected record semaphore does not require the separate execution stack or task control block required by the tasking semaphore. While the protected record implementation showed vast improvements over tasking, it is 2 to 3 times slower than the implementation using direct runtime calls. 4.3 General Protected Record Analysis A potential problem with the protected record definition lies in the flexibility with which the context for executing entry bodies on behalf of suspended tasks is defined. The entry bodies are allowed to be executed on behalf of the suspended tasks either in the context of the task which modifies the entry barrier for the suspense entry or in the context of the suspended task. The problem is in determining stack requirements for tasks calling protected entries or procedures if they can cause suspended tasks to become eligible for execution by modifying guard conditions which block them. If those entry bodies are executed in the context of the liberating task, and if those bodies contain local declarations for which stack space must be allocated, then differing execution conditions will generate different requirements for stack space for the liberating task. Moreover, if the entry bodies in turn call other protected procedures or entries in other protected records, then the potential stack requirement for the liberating task is even further distorted. These conditions are especially limiting if the protected record is being accessed directly via an interrupt or an interrupt handler, since interrupt stack space is typically quite limited and minimal stack space is essential. In this environment where special cases may arise quite infrequently, it is conceivable that a particular entry body may be executed quite infrequently, potentially placing severe requirements on stack space. Since these cases could be very infrequent, testing for them could be especially difficult. In addition to these objections, the mapping document allows for the flexibility of these entry bodies being executed in the context of the liberating task or the original calling task. If they are executed in the context of the originally calling task, stack requirements become much easier to determine, although this approach may be more inefficient because it may require more context switches. Regardless of the chosen method, the implementation flexibility is cause for concern both during development and when porting across tool sets. What may work quite nicely using a runtime which executes entry bodies in the context of the original calling task may fail when using a runtime in which the bodies are executed in the context of the liberating task, simply due to the largely differing potential for stack requirements. We found the evaluated language features to be a natural extension to Ada 83 and did not encounter any serious problems becoming proficient in their use. As more software is written using these features, more examples will become available that will make it even easier for newcomers. A case in point: we had several situations where we needed to dequeue all the callers queued at a protected record entry as a result of a call to another protected operation of the same protected record. A simple case of this is an "event", where multiple callers queue on a "WAIT" entry pending a call to "SIGNAL" the event. Once we had an example of how this can be accomplished, solutions to other similar problems were easily developed. The interface defined for the protected record has been found to be very easy to use. Since protected records were used as replacements for tasks in our applications, it was quite important for ease of transition for the interface to the protected record to be quite similar to that of the task. In fact, we found it to be exactly compatible. This compatibility made it quite easy to replace tasks with protected records during our re-engineering. All that was required was the replacement of the package defining the task with the package defining the protected record. All packages which accessed the construct remained intact. This compatibility of the interfaces will be especially useful as applications are modified to replace tasks with protected records. In addition, even reusable code, the implementation of which may be unknown by the user, will be able to undergo modifications which are transparent to the user. One of the major challenges encountered in implementing embedded applications in Ada is a severely restricted memory space. The use of tasks in an embedded application is made quite difficult by the data requirements for task stacks and data structures such as TCBs. In systems using large numbers of data queues and in heavily synchronized systems, major problems are introduced as the required number of tasks explodes. Each task requires a separate stack and TCB. Some compilers require the minimum size of the stack to be as large as 1K, with no ability to request smaller stack sizes. The ability to use protected records for data access synchronization and task synchronization dramatically improves this situation because protected records do not require stacks. This improvement will considerably enhance the usability of Ada in embedded systems. References [1] Draft Ada 9X Project Report; Ada 9X Mapping Document Volume II; Mapping Specification, August 1991, Office of the Under Secretary of Defense for Acquisition [2] Architecture Specification for PAVE PILLAR AVIONICS, Document SPA90099001A, January 1987, USAF WRDC/AAAS [3] Ada Compiler Evaluation Capability (ACEC) Technical Operating Report (TOR) User's Guide, D500-12470-1, Release 2.0, 30 April 1990, USAF WRDC/AAAF [4] Ada Compiler Evaluation Capability (ACEC) Technical Operating Report (TOR) Reader's Guide, D500-12471-1, Release 2.0, 24 April 1990, USAF WRDC/AAAF [5] Ada Compiler Evaluation Capability (ACEC) Version Description Document, D500-12472-1, Release 2.0, 26 April 1990, USAF WRDC/AAAF Appendix A. Compilation Times for Benchmark Version #1 (Periodic) Re-Engineered Baseline Baseline File (Ada 9X Compiler) (Ada 9X Compiler) (V4.1 Compiler) SCHEDULER_.ADA 6.47 6.47 6.57 OFP_CONSTANTS_.ADA 13.59 13.59 15.70 APPLICATION_STRUCTURE_.ADA 6.78 6.78 11.25 SIZED_INTEGER_.ADA 33.59 33.59 37.30 AD_DATA_.ADA 9.92 9.92 11.24 AD_SENSOR_DATA_.ADA 17.19 17.19 20.75 COMMAND_DATA_.ADA 8.59 8.59 10.16 FLY_TO_DATA_.ADA 9.56 9.56 11.11 INS_DATA_.ADA 10.36 10.36 12.30 INS_SENSOR_DATA_.ADA 19.33 19.33 23.61 NAV_STATE_DATA_.ADA 10.88 10.88 13.11 STEERING_DATA_.ADA 10.77 10.77 13.31 MATH_LIB1_.ADA 13.61 13.61 14.42 OFP_UTIL_.ADA 8.06 8.06 8.26 MATH_LIB1.ADA 23.35 23.35 23.63 OFP_UTIL.ADA 40.44 40.44 41.56 HIST_LOG_.ADA 8.37 8.37 8.52 DEADLINE_DATA_.ADA 8.44 8.44 8.72 HIST_LOG.ADA 21.88 21.88 21.74 SIMULATION_.ADA 6.49 6.49 6.60 SIMULATION.ADA 70.36 70.36 72.97 SENSOR_.ADA 6.15 6.15 6.54 SENSOR.ADA 37.06 37.06 36.43 NAVIGATION_.ADA 6.57 6.57 6.89 NAVIGATION.ADA 33.53 33.53 35.71 GUIDANCE_.ADA 7.39 7.39 7.58 GUIDANCE.ADA 61.84 61.84 62.84 SIM_PERIODIC_.ADA 8.07 8.07 8.05 AD_PERIODIC_.ADA 8.12 8.12 8.05 INS_PERIODIC_.ADA 7.74 7.74 8.02 NAV_PERIODIC_.ADA 8.01 8.01 8.15 GUI_PERIODIC_.ADA 8.02 8.02 8.02 SIM_PERIODIC.ADA 12.67 12.67 12.05 AD_PERIODIC.ADA 12.42 12.42 12.05 INS_PERIODIC.ADA 12.67 12.67 12.15 NAV_PERIODIC.ADA 12.51 12.51 11.99 GUI_PERIODIC.ADA 12.20 12.20 12.03 FREE_TIME_.ADA 7.50 7.50 8.17 FREE_TIME.ADA 13.38 13.38 12.85 DEADLINE_DATA.ADA 33.96 33.96 33.51 COCKPIT.ADA 11.96 11.96 11.52 SCHEDULER.ADA 35.72 42.41 43.46 Total 715.52 722.21 758.89 Appendix B. Compilation Times for Benchmark Version #2 (Periodic w/Async) Re-Engineered Baseline Baseline File (Ada 9X Compiler) (Ada 9X Compiler) (V4.1 Compiler) SCHEDULER_.ADA 6.64 6.64 6.84 OFP_CONSTANTS_.ADA 14.13 14.13 15.90 APPLICATION_STRUCTURE_.ADA 9.76 9.76 11.87 SIZED_INTEGER_.ADA 33.78 33.78 37.53 MATH_LIB1_.ADA 13.76 13.76 14.50 MATH_LIB1.ADA 23.38 23.38 24.21 HIST_LOG_.ADA 8.08 8.08 8.34 DEADLINE_DATA_.ADA 8.65 8.65 8.71 HIST_LOG.ADA 21.74 21.74 21.05 SIMULATION_.ADA 6.30 6.30 6.43 SENSOR_.ADA 6.46 6.46 6.51 NAVIGATION_.ADA 6.61 6.61 6.75 GUIDANCE_.ADA 7.39 7.39 7.74 SIM_PERIODIC_.ADA 8.12 8.12 8.39 AD_PERIODIC_.ADA 7.98 7.98 8.17 INS_PERIODIC_.ADA 7.94 7.94 8.06 NAV_PERIODIC_.ADA 8.29 8.29 8.47 GUI_PERIODIC_.ADA 8.22 8.22 8.39 SIM_PERIODIC.ADA 12.23 12.23 11.93 AD_PERIODIC.ADA 12.82 12.82 12.11 INS_PERIODIC.ADA 12.46 12.46 11.84 NAV_PERIODIC.ADA 12.58 12.58 12.05 GUI_PERIODIC.ADA 12.25 12.25 12.13 FREE_TIME_.ADA 7.93 7.93 8.05 FREE_TIME.ADA 13.74 13.74 13.08 DEADLINE_DATA.ADA 33.82 33.82 34.11 ASYNC_.ADA 8.80 8.80 8.49 LOCKS_.ADA 10.58 11.36 10.97 AD_DATA_.ADA 10.34 11.37 12.98 AD_SENSOR_DATA_.ADA 17.59 18.12 22.24 COMMAND_DATA_.ADA 10.55 10.75 12.93 FLY_TO_DATA_.ADA 9.61 9.81 11.38 INS_DATA_.ADA 10.98 11.11 14.13 INS_SENSOR_DATA_.ADA 20.34 20.60 24.82 NAV_STATE_DATA_.ADA 11.41 11.81 14.11 STEERING_DATA_.ADA 11.89 12.75 15.96 OFP_UTIL_.ADA 8.48 8.42 8.54 OFP_UTIL.ADA 40.66 41.09 40.01 SIMULATION.ADA 73.05 72.52 75.90 SENSOR.ADA 37.95 37.68 37.77 NAVIGATION.ADA 33.73 34.28 36.30 GUIDANCE.ADA 63.98 64.15 65.26 SCHEDULER.ADA 34.14 42.63 43.38 ASYNC.ADA 44.19 43.14 43.45 COCKPIT.ADA 12.66 12.95 12.35 Total 795.99 808.40 844.13 Appendix C. Compilation Times for Benchmark Version #3 (Event) Re-Engineered Baseline Baseline File (Ada 9X Compiler) (Ada 9X Compiler) (V4.1 Compiler) OFP_CONSTANTS_.ADA 13.59 13.59 15.60 SIZED_INTEGER_.ADA 33.98 33.98 37.85 COMMAND_DATA_.ADA 9.02 9.02 10.20 FLY_TO_DATA_.ADA 9.80 9.80 11.16 STEERING_DATA_.ADA 10.92 10.92 13.33 MATH_LIB1_.ADA 13.82 13.82 14.33 MATH_LIB1.ADA 23.21 23.21 23.92 HIST_LOG_.ADA 8.22 8.22 8.30 SIMULATION_CONTROL_.ADA 7.70 7.70 7.92 HIST_LOG.ADA 21.79 21.79 21.77 SENSOR_.ADA 7.91 7.91 8.09 NAVIGATION_.ADA 8.07 8.07 8.30 FREE_TIME_.ADA 7.71 7.71 7.65 FREE_TIME.ADA 13.51 13.51 12.91 EVENTS_.ADA 7.46 8.27 8.09 EVENTS.ADA 12.33 10.69 9.99 AD_DATA_.ADA 10.74 11.31 13.08 AD_SENSOR_DATA_.ADA 17.82 18.32 22.28 INS_DATA_.ADA 11.31 11.89 13.99 INS_SENSOR_DATA_.ADA 20.28 20.52 25.52 NAV_STATE_DATA_.ADA 11.92 12.49 15.40 GUIDANCE_.ADA 9.07 8.69 8.81 OFP_UTIL_.ADA 8.43 8.25 8.40 OFP_UTIL.ADA 39.95 40.68 41.59 SENSOR.ADA 39.04 37.46 39.44 NAVIGATION.ADA 33.93 35.00 36.02 GUIDANCE.ADA 67.24 67.20 68.36 SIMULATION_.ADA 8.63 8.38 8.49 SIMULATION.ADA 76.73 74.10 77.28 SIMULATION_CONTROL.ADA 17.09 27.61 28.25 COCKPIT.ADA 23.22 24.00 23.98 Total 604.44 614.11 650.30 Appendix D. Compilation Times for Benchmark Version #4 (Periodic w/Interrupt) Re-Engineered Baseline File (Ada 9X Compiler) (Ada 9X Compiler) SCHEDULER_.ADA 6.47 6.47 OFP_CONSTANTS_.ADA 13.59 13.59 APPLICATION_STRUCTURE_.ADA 6.78 6.78 SIZED_INTEGER_.ADA 33.59 33.59 AD_DATA_.ADA 9.92 9.92 AD_SENSOR_DATA_.ADA 17.19 17.19 COMMAND_DATA_.ADA 8.59 8.59 FLY_TO_DATA_.ADA 9.56 9.56 INS_DATA_.ADA 10.36 10.36 INS_SENSOR_DATA_.ADA 19.33 19.33 NAV_STATE_DATA_.ADA 10.88 10.88 STEERING_DATA_.ADA 10.77 10.77 MATH_LIB1_.ADA 13.61 13.61 OFP_UTIL_.ADA 8.06 8.06 MATH_LIB1.ADA 23.35 23.35 OFP_UTIL.ADA 40.44 40.44 HIST_LOG_.ADA 8.37 8.37 DEADLINE_DATA_.ADA 8.44 8.44 HIST_LOG.ADA 21.88 21.88 SIMULATION_.ADA 6.49 6.49 SIMULATION.ADA 70.36 70.36 SENSOR_.ADA 6.15 6.15 SENSOR.ADA 37.06 37.06 NAVIGATION_.ADA 6.57 6.57 NAVIGATION.ADA 33.53 33.53 GUIDANCE_.ADA 7.39 7.39 GUIDANCE.ADA 61.84 61.84 SIM_PERIODIC_.ADA 8.07 8.07 AD_PERIODIC_.ADA 8.12 8.12 INS_PERIODIC_.ADA 7.74 7.74 NAV_PERIODIC_.ADA 8.01 8.01 GUI_PERIODIC_.ADA 8.02 8.02 SIM_PERIODIC.ADA 12.67 12.67 AD_PERIODIC.ADA 12.42 12.42 INS_PERIODIC.ADA 12.67 12.67 NAV_PERIODIC.ADA 12.51 12.51 GUI_PERIODIC.ADA 12.20 12.20 FREE_TIME_.ADA 7.50 7.50 FREE_TIME.ADA 13.38 13.38 DEADLINE_DATA.ADA 33.96 33.96 COCKPIT.ADA 11.96 11.96 SCHEDULER.ADA 51.62 48.48 Total 731.42 728.28 Appendix E. Compilation Times for Benchmark Version #5 (Periodic w/Async w/Interrupt) Re-Engineered Baseline File (Ada 9X Compiler) (Ada 9X Compiler) SCHEDULER_.ADA 6.64 6.64 OFP_CONSTANTS_.ADA 14.13 14.13 APPLICATION_STRUCTURE_.ADA 9.76 9.76 SIZED_INTEGER_.ADA 33.78 33.78 MATH_LIB1_.ADA 13.76 13.76 MATH_LIB1.ADA 23.38 23.38 HIST_LOG_.ADA 8.08 8.08 DEADLINE_DATA_.ADA 8.65 8.65 HIST_LOG.ADA 21.74 21.74 SIMULATION_.ADA 6.30 6.30 SENSOR_.ADA 6.46 6.46 NAVIGATION_.ADA 6.61 6.61 GUIDANCE_.ADA 7.39 7.39 SIM_PERIODIC_.ADA 8.12 8.12 AD_PERIODIC_.ADA 7.98 7.98 INS_PERIODIC_.ADA 7.94 7.94 NAV_PERIODIC_.ADA 8.29 8.29 GUI_PERIODIC_.ADA 8.22 8.22 SIM_PERIODIC.ADA 12.23 12.23 AD_PERIODIC.ADA 12.82 12.82 INS_PERIODIC.ADA 12.46 12.46 NAV_PERIODIC.ADA 12.58 12.58 GUI_PERIODIC.ADA 12.25 12.25 FREE_TIME_.ADA 7.93 7.93 FREE_TIME.ADA 13.74 13.74 DEADLINE_DATA.ADA 33.82 33.82 ASYNC_.ADA 8.80 8.80 LOCKS_.ADA 10.76 11.72 AD_DATA_.ADA 10.43 10.71 AD_SENSOR_DATA_.ADA 17.61 18.32 COMMAND_DATA_.ADA 10.38 10.84 FLY_TO_DATA_.ADA 9.67 9.68 INS_DATA_.ADA 11.19 11.53 INS_SENSOR_DATA_.ADA 19.95 20.41 NAV_STATE_DATA_.ADA 11.61 12.25 STEERING_DATA_.ADA 12.40 12.99 OFP_UTIL_.ADA 8.22 8.34 OFP_UTIL.ADA 40.58 40.92 SIMULATION.ADA 73.39 73.05 SENSOR.ADA 38.60 38.38 NAVIGATION.ADA 35.04 34.42 GUIDANCE.ADA 64.61 63.90 SCHEDULER.ADA 52.37 48.42 ASYNC.ADA 44.86 43.85 COCKPIT.ADA 12.54 13.08 Total 818.07 816.67 Appendix F. Compilation Times for Benchmark Version #6 (Event w/Interrupt) Re-Engineered Baseline File (Ada 9X Compiler) (Ada 9X Compiler) OFP_CONSTANTS_.ADA 13.59 13.59 SIZED_INTEGER_.ADA 33.98 33.98 COMMAND_DATA_.ADA 9.02 9.02 FLY_TO_DATA_.ADA 9.80 9.80 STEERING_DATA_.ADA 10.92 10.92 MATH_LIB1_.ADA 13.82 13.82 MATH_LIB1.ADA 23.21 23.21 HIST_LOG_.ADA 8.22 8.22 SIMULATION_CONTROL_.ADA 7.70 7.70 HIST_LOG.ADA 21.79 21.79 SENSOR_.ADA 7.91 7.91 NAVIGATION_.ADA 8.07 8.07 FREE_TIME_.ADA 7.71 7.71 FREE_TIME.ADA 13.51 13.51 EVENTS_.ADA 7.26 8.11 EVENTS.ADA 12.22 10.46 AD_DATA_.ADA 10.90 11.04 AD_SENSOR_DATA_.ADA 18.01 18.16 INS_DATA_.ADA 11.18 11.71 INS_SENSOR_DATA_.ADA 20.27 20.65 NAV_STATE_DATA_.ADA 11.62 12.23 GUIDANCE_.ADA 9.00 8.79 OFP_UTIL_.ADA 8.19 8.27 OFP_UTIL.ADA 41.16 40.86 SENSOR.ADA 38.43 37.38 NAVIGATION.ADA 34.96 34.87 GUIDANCE.ADA 66.10 67.78 SIMULATION_.ADA 7.89 8.27 SIMULATION.ADA 73.63 73.87 SIMULATION_CONTROL.ADA 34.09 33.37 COCKPIT.ADA 23.84 24.15 Total 618.00 619.22