TSAT User Guide

The Task Stack Analysis Tool (TSAT) is used to determine appropriate sizes for task stacks within an Ada application. It does this by analysis of the Ada library containing the compiled application. The user can apply the stack requirements reported by TSAT to the task stack specification in 'Size clauses and in the Linker option files.

TSAT consists of two parts: 1) Data Collection and 2) Analysis. Data Collection occurs during compilation of the program to be analyzed. The Data Collection phase occurs when the Ada compiler Code Generator saves information about subprogram stack use in the Ada library. The "atsat" tool implements the Analysis phase. It reads the information saved by the compiler then analyzes it and reports the results.

I. Data Collection

To collect data, the -k option must be used when compiling the units to be analyzed. The compile must be done by a TSAT instrumented compiler. Units that have not been compiled in this way will be flagged by the analysis tool, but no stack information will be known for them. The information is saved in the Ada sublibrary along with the compiled unit.

For example:

% ada -v -k arkerb.ada
TSAT Phase II Release 5/31/94
Copyright 1994, Alsys.  All Rights Reserved
RISCAda (tm) Development System for SPARCStations and Servers
Ada Compiler for Embedded 68k Targets, Version 4.1c
Copyright (c) 1992 TeleSoft. All rights reserved.

...

The stack use of each subprogram consist of four parts:

1. Parameter size: this is the stack required for parameters passed to the subprogram. This stack is consumed immediately prior to the call.
2. Return linkage size: This is the stack required for the return address and frame pointer link. This stack is consumed by the actual call.
3. Local Frame size: This is the stack used for local objects during the lifetime of the subprogram. This stack is consumed by the subprogram prologue code.
4. Optional Dynamic size: This is stack that is allocated sometime during the lifetime of the procedure. Its size is determined by the size of unconstrained objects within the program.

II. Stack Use Analysis

The analysis tool, atsat, reports stack use for all tasks in the units specified on the command line. These tasks may include:

• All tasks in the extended family of a unit;
• All tasks within a single unit; or,
• The main task of the application, which includes application elaboration.

The specified unit is typically the main unit of the program, but may be any compilation unit. For maximum information, all units within the extended family should have been compiled as described above in the "Data Collection" section. The extended family must be executable. That is, there should be no missing units, obsolete units or circular dependencies. This is the same requirement as needed to bind a program; if the program can be bound, it can be analyzed.

Atsat performs three categories of stack analysis: stack use (-s), call tree (-c), and recursion (-r). The user should select one or more of these categories on the atsat command line. If none of these options is specified, atsat only performs consistency checks and reports missing subprograms.

The atsat tool is of the form:

atsat [<options>] <compilation-unit>

where <options> are:

-c

Call Tree Analysis: perform and report call tree analysis. Default: don't perform call tree analysis.

-e

Extended Family: perform analysis on the extended family of the specified unit. Default: perform analysis only on the specified unit.

-l <library>

Library File: use the specified Ada library. Default: liblst.alb

-f <file>

Missing Data File or Input List File of Missing Data Files: supplies stack analysis information that is not present in the Ada library. This data includes:

• Stack sizes and call information for subprograms that have no saved information. Subprograms may be Ada subprograms that were not compiled with -k or non-Ada subprograms.
• Parameter size information to use in dynamic stack size analysis. <file> can be either a missing data file name or an input list file name that ends in ".ilf", which consists of one or more missing data file names, but only one per line. Default: No missing data supplied.

-m

Main Task Analysis: perform analysis of the main task including elaboration of all packages in the program and the main procedure. This is only meaningful if the compilation-unit specified is the main program. Default: don't analyze the main task.

-r

Recursion Analysis: perform and report recursion analysis. Default: don't perform recursion analysis.

-s

Stack Use Analysis: perform and report stack use analysis. Default: don't perform stack use analysis.

-v

Verbose: produce progress message during analysis. Default: don't produce progress messages.

The atsat analysis tool works in several steps:

0) Initialization.

If -v is specified on the command line, a banner is printed. The library is opened. Any errors encountered are reported.

1) Determine the extended family of the specified unit.

This results in a list of compilation units to be analyzed in subsequent steps. This list is in no particular order. No output is produced during this phase. If there are missing units, circular dependencies or obsolete units found, these are reported during this phase. If no compilation units are found to analyze, this is also reported. This step is performed even if only a single unit is specified. This is a necessary consistency check for the library.

2) Find the tasks.

If -e is not specified, only the given unit is searched for tasks. If -e is specified, each of the units found in step 1 is analyzed for tasks and task types. If -m is specified, the main task is included in further analysis. If -v is specified on the command line, a message is printed for each unit processed. This step results in a list of tasks and task types to be analyzed in subsequent steps. This list is in no particular order.

3) Analyze each task.

For each task found in step 2, atsat performs the following analysis:

a) Find the call tree for the task.

The information saved in the library by data collection is used to construct a call tree for the task. Each node in the tree represents a subprogram. Associated with each node in the tree (and hence, each subprogram), is the stack usage of the subprogram, a list of subprograms called by this subprogram (this forms the edges of the graph), and information on dynamic stack usage by this subprogram. A given subprogram will be included only once in the list of called subprograms even if it is called from multiple locations within this subprogram.

This call tree is actually a directed acyclic graph because some of the subprograms may be called from more than one location. The graph will not be strictly acyclic if recursion is present, but for analysis purposes, it is treated as acyclic.

This step prints a banner for the task. For example:

================= Analysis of task sec/unique_id.id_monitor_type =================

b) Report the subprograms for which no subprogram information exists.

Atsat traverses the call tree and reports subprogram that have no stack size information. These are Ada units which have not been compiled with -k, or non-Ada units. For example:

>>> Warning: lib/ar_activation.start_activation has no stack size information

These messages should be corrected with data in the missing data file. If the messages are not corrected, the stack size analysis will not provide a complete picture of stack use.

c) Report recursive call paths in the task.

This step is done only if -r is specified. Atsat traverses the call tree to find recursive call paths in the task. Each possible recursive path is printed. Each reported path contains and ends with the subprogram that represents the entry for the recursive path. The reported call paths are only potentially recursive. In general, it is not possible to determine by static analysis whether recursion actually occurs. These reported paths should be taken into consideration when considering total stack use. For analysis purposes, atsat assumes the recursion does not actually occur. The numbers reported in the recursive part of the path represent the stack use for one recursion of the path.

For example:

>>> Information: Recursive calls:
    sec/main.main calls
  ->lib/secondary_memory_device_driver.create calls, 40, 40
    lib/secondary_memory_device_driver.create

In this example the subprogram calls itself directly. The "->" symbol indicates the beginning of the recursive path. The recursive path requires 40 bytes of stack space for each recursion. Recursive paths that involve longer paths before the recursion takes place, e.g., A calls B calls C calls A, are also reported. Note that all recursive paths are reported, but not all ways to get to the recursive path are reported. In the above example, there may be more call paths that lead to lib/secondary_memory_device_driver.create than through sec/main.main.

d) Report stack use for each subprogram.

This step is done only if -s is specified. Atsat traverses the call tree from the leaves (those subprograms which don't call other subprograms) upward. During this traversal, it finds the stack use of the largest call path that begins with this subprogram, i.e., the largest child subtree. It then reports two values for each subprogram: the stack requirements for this subprogram and the stack requirements for the longest call path that begins with this subprogram. For example:

>>> Information: Stack use:
    lib/calendar.time_of, 76, 128
    sec/error_services.send_to_rs232.time_to_string, 276 = 252 
       + time <= 24?, 444

The first number, the stack requirements for this subprogram, consists of parameter size plus return linkage size plus local frame size as described above. If the subprogram has dynamic stack use, this is shown by the unconstrained parameter and its size as specified in the missing data file. In the above example, the parameter "time" is not specified in the missing data file, so its size is displayed as "24?". Any parameter size reported as some valve followed by "?" should be corrected by including size information in the missing data file.

The second number, the stack requirements for the largest call path that begins with this subprogram, represents the amount of additional stack that may be required for the calls from this subprogram. Thus, for the subprogram which is the body of the task, the second number shows the stack requirement for the task. This number can be compared against the stack size specified in the in the 'Size clause for the task.

e) Report all dynamic stack allocations in descending order.

This step is done only if -s is specified. For example:

>>> Information: Dynamic stack allocations:
    <Elaboration Procedure>
    sec/dynamic.dynamic.r,  32771
    sec/dynamic.dynamic.a,  32765
    sec/dynamic.dynamic.e,  4098
    sec/dynamic.dynamic.v,  9
    sec/dynamic.dynamic.b,  7

f) Report the longest call path in the task.

This step is done only if -s is specified. Atsat traverses the call tree to find the call path with the largest stack requirement. If the stack size for the task accommodates this call path, there will be sufficient stack allocated to the task (see below for additional considerations). For example:

>>> Information: Call chain with largest stack requirement:
    <unknown> calls, 0, 44
    sec/main.main calls, 16, 44
    lib/os_init.system_startup calls, 20, 28
    lib/stp_gpc_eeprom.initialize calls, 4, 8
    lib/gpc.id, 4, 4

In this example, <unknown> represents the unnamed subprogram which calls the main program.

g) Report the call tree.

This step is done only if -c is specified. Atsat traverses the call tree the list of subprograms that are called from each subprogram. A given subprogram will appear only once in the called subprogram list even if is called from more than one location, e.g., if subprogram "A" calls subprogram "B" three times, "B" will only appear once in the list of subprograms called from "A". For example:

>>> Information: Call tree:
    sec/clock_support.clock_support
    -> lib/time.time
    -> lib/calendar.time_of

    lib/time.time
    -> lib/unsigned_numbers.unsigned_64_bits_of
    -> lib/the_real_time_clock.overflow_count
    -> lib/the_real_time_clock.clock

    lib/unsigned_numbers.unsigned_64_bits_of

Each subprogram is listed with the list of called subprograms beneath it. Each of the called subprograms is preceded by the "->" symbol. In the example above, lib/unsigned_numbers.unsigned_64_bits_of, calls no other subprograms so it is listed by itself with no called subprograms beneath it.

III. Missing Data File(s)

The Missing Data File(s) are used to provide additional information to that saved in the Ada Library. This additional information includes:

• Stack use and call information for non-Ada routines;
• Stack use and call information for Ada routines that were not compiled with -k; and,
• Dynamic stack use information for unconstrained objects.

1) Missing and non-Ada subprograms.

If atsat reports that a subprogram has no saved stack information, the reported stack analysis may not reflect actual total stack requirements. This may be the case with non-Ada subprograms or third party libraries. The -f option of atsat may be used to supply information for these subprograms.

This option specifies a file, or an input list of files, whose contents are a sequence of lines of the form:

<subprogram_name>, <stack_requirement>
-> <called_subprogram_1>
-> <called_subprogram_2>

where <subprogram_name> is the name of the missing Ada or non-Ada subprogram, <stack_requirement> is the total stack requirement for this subprogram, <called_subprogram_i> is an Ada or non-Ada subprogram called from this subprogram. There should be one called subprogram line (beginning with "->") for each subprogram called from <subprogram_name>. In this fashion Ada routines can call non-Ada routines and vice versa.

The subprogram name is case insensitive. Spaces, tabs, blank lines and Ada style comments may be used for formatting. Atsat will report a warning and ignore lines that are in an incorrect format. The subprogram name specified should be the same as the one reported as missing by atsat. Atsat will ignore lines which define stack space for subprograms that already have stack information in the library. Atsat will not report subprograms as missing if they are defined in this file.

1) Dynamic stack use.

Some stack size requirements are based on the size of unconstrained objects. The size of these objects is not known until runtime. These dynamically sized objects are typically local declarations in subprograms or declare blocks. They may also be compiler generated temporary objects used for unconstrained function return values (which includes unconstrained array catenation). The user may specify the expected maximum size of these objects in the missing data file. Atsat will warn of dynamically sized objects by reporting <dynamic_object_name> <= "<maximum_size>?" in the stack size for subprograms which have dynamic stack requirements.

To correct this warning, insert a missing data file line of the form:

<dynamic_object_name>, <expected_maximum_size>

In this line, <dynamic_object_name> should be exactly the same as the name reported in the stack size, <expected_maximum_size> is the size of <dynamic_object_name> in bytes. Once the information is placed in the missing data file, the stack size report will contain

<dynamic_object_name> <= <expected_maximum_size>

For example, if atsat reports:

sec/blob_io.put, 32807 = 40 
   + sec/blob_io.put.item <= 32767?, 40

and you know that sec/blob_io.put.item is an array that will be at most 50 bytes, put the line:

sec/blob_io.put.item, 50

in the missing data file. Atsat will then report:

sec/blob_io.put, 90 = 40 
   + sec/blob_io.put.item <= 50, 90

Compiler generated objects have names of the form MP_LnnnnDmmmm. The nnnn (or possibly nnnnn) is the source file line number which caused the compiler generated object to be allocated. This object is typically an unconstrained function result. Look at line nnnn in the Ada source to determine what the maximum function result size might be.

The file runtime.tsat includes stack size information for the Ada runtime and pSOS kernel. This file is in missing data file format. The user should use this file as a starting point for the missing data file. Make a copy of runtime.tsat and add missing information for the application to this copy.

IV. Additional Considerations

These are some issues to consider to determine appropriate values for stack sizes.

1) Multiple stacks.

Atsat has no knowledge of which of several stacks (user, master, interrupt) may be in use at a given time. It is up to the user to apply the information from atsat to the correct stack.

2) Recursion.

Atsat reports possible recursive paths and the stack space consumed by one recursion of the path. The user must decide if this recursive path applies to the maximum call chain of a particular task. If so, the given size must be multiplied by the number of expected recursions and added to the stack requirements.

3) Interrupts.

The stack use for function mapped interrupt subprograms is included in the stack requirements for the task. It will be listed as one of the subprograms for the task. This subprogram may run on a different stack than non-interrupt code. There is a small amount of stack required (< 100 bytes) in addition to that reported by atsat.

4) Exceptions.

Exceptions are handled through a series of calls in the Ada runtime. The stack requirements for the Ada package cgs_exception_manager is most of the stack required to process exceptions. An additional small amount may be needed by the Board Support Package to process exceptions that originate as traps rather than calls.

5) The 'Size representation clause for tasks may need to allow more space than required for the stack. Task control blocks may be allocated from this space as well.