gcc/ada/libgnat/s-secsta.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --               S Y S T E M . S E C O N D A R Y _ S T A C K                --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 1992-2023, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- GNAT was originally developed  by the GNAT team at  New York University. --
  28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  29 --                                                                          --
  30 ------------------------------------------------------------------------------
  31
  32 with System.Parameters;
  33 with System.Storage_Elements;
  34
  35 package System.Secondary_Stack is
  36    pragma Preelaborate;
  37
  38    package SP  renames System.Parameters;
  39    package SSE renames System.Storage_Elements;
  40
  41    use type SP.Size_Type;
  42
  43    type SS_Stack (Default_Chunk_Size : SP.Size_Type) is private;
  44    --  An abstraction for a heap structure maintained in a stack-like fashion.
  45    --  The structure is comprised of chunks which accommodate allocations of
  46    --  varying sizes. See the private part of the package for further details.
  47    --  Default_Chunk_Size indicates the size of the static chunk, and provides
  48    --  a minimum size for all dynamic chunks.
  49
  50    type SS_Stack_Ptr is access all SS_Stack;
  51    --  A reference to a secondary stack
  52
  53    type Mark_Id is private;
  54    --  An abstraction for tracking the state of the secondary stack
  55
  56    procedure SS_Init
  57      (Stack : in out SS_Stack_Ptr;
  58       Size  : SP.Size_Type := SP.Unspecified_Size);
  59    --  Initialize or reuse a secondary stack denoted by reference Stack. If
  60    --  Stack is null, create a new stack of size Size in the following manner:
  61    --
  62    --    * If Size denotes Unspecified_Size, allocate the stack from the binder
  63    --      generated pool as long as the pool has not been exhausted.
  64    --
  65    --    * Otherwise allocate the stack from the heap.
  66    --
  67    --  If Stack is not null, reset the state of the stack. No existing chunks
  68    --  are freed because they may be reused again.
  69
  70    procedure SS_Allocate
  71      (Addr         : out Address;
  72       Storage_Size : SSE.Storage_Count;
  73       Alignment    : SSE.Storage_Count := Standard'Maximum_Alignment);
  74    --  Allocate enough space on the secondary stack of the invoking task to
  75    --  accommodate an allocation of size Storage_Size. Return the address of
  76    --  the first byte of the allocation in Addr, which is a multiple of
  77    --  Alignment. The routine may carry out one or more of the following
  78    --  actions:
  79    --
  80    --    * Reuse an existing chunk that is big enough to accommodate the
  81    --      requested Storage_Size.
  82    --
  83    --    * Free an existing chunk that is too small to accommodate the
  84    --      requested Storage_Size.
  85    --
  86    --    * Create a new chunk that fits the requested Storage_Size.
  87
  88    procedure SS_Free (Stack : in out SS_Stack_Ptr);
  89    --  Free all dynamic chunks of secondary stack Stack. If possible, free the
  90    --  stack itself.
  91
  92    function SS_Mark return Mark_Id;
  93    --  Capture and return the state of the invoking task's secondary stack
  94
  95    procedure SS_Release (M : Mark_Id);
  96    --  Restore the state of the invoking task's secondary stack to mark M
  97
  98    function SS_Get_Max return Long_Long_Integer;
  99    --  Return the high water mark of the invoking task's secondary stack, in
 100    --  bytes.
 101
 102    generic
 103       with procedure Put_Line (S : String);
 104    procedure SS_Info;
 105    --  Debugging procedure for outputting the internals of the invoking task's
 106    --  secondary stack. This procedure is generic in order to avoid a direct
 107    --  dependence on a particular IO package. Instantiate with Text_IO.Put_Line
 108    --  for example.
 109
 110 private
 111    SS_Pool : Integer;
 112    --  Unused entity that is just present to ease the sharing of the pool
 113    --  mechanism for specific allocation/deallocation in the compiler.
 114
 115    ------------------
 116    -- Introduction --
 117    ------------------
 118
 119    --  The secondary stack is a runtime data structure managed in a stack-like
 120    --  fashion. It is part of the runtime support for functions that return
 121    --  results of caller-unknown size.
 122    --
 123    --  The secondary stack is utilized as follows:
 124    --
 125    --    * The compiler pushes the caller-unknown size result on the secondary
 126    --      stack as part of return statement or build-in-place semantics.
 127    --
 128    --    * The caller receives a reference to the result.
 129    --
 130    --    * Using the reference, the caller may "offload" the result into its
 131    --      primary stack, or use it in-place while still on the secondary
 132    --      stack.
 133    --
 134    --    * Once the caller has utilized the result, the compiler reclaims the
 135    --      memory occupied by the result by popping the secondary stack up to
 136    --      a safe limit.
 137
 138    ------------
 139    -- Design --
 140    ------------
 141
 142    --  1) Chunk
 143    --
 144    --  The secondary stack is a linked structure which consist of "chunks".
 145    --  A chunk is both a memory storage and a linked-list node. Addresses of
 146    --  allocated objects refer to addresses within the memory storage of a
 147    --  chunk. Chunks come in two variants - static and dynamic.
 148    --
 149    --  1.1) Static chunk
 150    --
 151    --  The secondary stack has exactly one static chunk that is created on the
 152    --  primary stack. The static chunk allows secondary-stack usage on targets
 153    --  where dynamic allocation is not available or desirable. The static chunk
 154    --  is always the "first" chunk and precedes all dynamic chunks.
 155    --
 156    --  1.2) Dynamic chunk
 157    --
 158    --  The secondary stack may have zero or more dynamic chunks, created on the
 159    --  heap. Dynamic chunks allow the secondary stack to grow beyond the limits
 160    --  of the initial static chunk. They provide a finer-grained management of
 161    --  the memory by means of reuse and deallocation.
 162    --
 163    --  2) Mark
 164    --
 165    --  The secondary stack captures its state in a "mark". The mark is used by
 166    --  the compiler to indicate how far the stack can be safely popped after a
 167    --  sequence of pushes has taken place.
 168    --
 169    --  3) Secondary stack
 170    --
 171    --  The secondary stack maintains a singly-linked list of chunks, starting
 172    --  with the static chunk, along with a stack pointer.
 173    --
 174    --  4) Allocation
 175    --
 176    --  The process of allocation equates to "pushing" on the secondary stack.
 177    --  Depending on whether dynamic allocation is allowed or not, there are
 178    --  two variants of allocation - static and dynamic.
 179    --
 180    --  4.1) Static allocation
 181    --
 182    --  In this case the secondary stack has only the static chunk to work with.
 183    --  The requested size is reserved on the static chunk and the stack pointer
 184    --  is advanced. If the requested size will overflow the static chunk, then
 185    --  Storage_Error is raised.
 186    --
 187    --  4.2) Dynamic allocation
 188    --
 189    --  In this case the secondary stack may carry out several actions depending
 190    --  on how much free memory is available in the chunk indicated by the stack
 191    --  pointer.
 192    --
 193    --    * If the indicated chunk is big enough, allocation is carried out on
 194    --      it.
 195    --
 196    --    * If the indicated chunk is too small, subsequent chunks (if any) are
 197    --      examined. If a subsequent chunk is big enough, allocation is carried
 198    --      out on it, otherwise the subsequent chunk is deallocated.
 199    --
 200    --    * If none of the chunks following and including the indicated chunk
 201    --      are big enough, a new chunk is created and the allocation is carried
 202    --      out on it.
 203    --
 204    --  This model of operation has several desirable effects:
 205    --
 206    --    * Leftover chunks from prior allocations, followed by at least one pop
 207    --      are either reused or deallocated. This compacts the memory footprint
 208    --      of the secondary stack.
 209    --
 210    --    * When a new chunk is created, its size is exactly the requested size.
 211    --      This keeps the memory usage of the secondary stack tight.
 212    --
 213    --    * Allocation is in general an expensive operation. Compaction is thus
 214    --      added to this cost, rather than penalizing mark and pop operations.
 215    --
 216    --  5) Marking
 217    --
 218    --  The process of marking involves capturing the secondary-stack pointer
 219    --  in a mark for later restore.
 220    --
 221    --  6) Releasing
 222    --
 223    --  The process of releasing equates to "popping" the secondary stack. It
 224    --  moves the stack pointer to a previously captured mark, causing chunks
 225    --  to become reusable or deallocatable during the allocation process.
 226
 227    ------------------
 228    -- Architecture --
 229    ------------------
 230
 231    --      Secondary stack
 232    --
 233    --      +------------+
 234    --      | Top.Byte  ------------------------+
 235    --      | Top.Chunk ------------------+     |
 236    --      |            |                |     |
 237    --      |            |                v     |
 238    --      +------------+   +--------+   +-----|--+   +--------+
 239    --      | Memory     |   | Memory |   | Memo|y |   | Memory |
 240    --      | #########  |   | #####  |   | ####|  |   | #####  |
 241    --      |            |   |        |   |        |   |        |
 242    --      | Next      ---> | Next  ---> | Next  ---> | Next  ---> x
 243    --      +------------+   +--------+   +--------+   +--------+
 244    --
 245    --       Static chunk     Chunk 2      Chunk 3      Chunk 4
 246
 247    --------------------------
 248    -- Memory-related types --
 249    --------------------------
 250
 251    subtype Memory_Size_With_Invalid is SP.Size_Type;
 252    --  Memory storage size which also includes an invalid negative range
 253
 254    Invalid_Memory_Size : constant Memory_Size_With_Invalid := -1;
 255
 256    subtype Memory_Size is
 257      Memory_Size_With_Invalid range 0 .. SP.Size_Type'Last;
 258    --  The memory storage size of a single chunk or the whole secondary stack.
 259    --  A non-negative size is considered a "valid" size.
 260
 261    subtype Memory_Index is Memory_Size;
 262    --  Index into the memory storage of a single chunk
 263
 264    type Chunk_Memory is array (Memory_Size range <>) of SSE.Storage_Element;
 265    for Chunk_Memory'Alignment use Standard'Maximum_Alignment;
 266    --  The memory storage of a single chunk
 267
 268    --------------
 269    -- SS_Chunk --
 270    --------------
 271
 272    type SS_Chunk (Size : Memory_Size);
 273    --  Abstraction for a chunk. Size indicates the memory capacity of the
 274    --  chunk.
 275
 276    type SS_Chunk_Ptr is access all SS_Chunk;
 277    --  Reference to the static or any dynamic chunk
 278
 279    type SS_Chunk (Size : Memory_Size) is record
 280       Next : SS_Chunk_Ptr;
 281       --  Pointer to the next chunk. The direction of the pointer is from the
 282       --  static chunk to the first dynamic chunk, and so on.
 283
 284       Size_Up_To_Chunk : Memory_Size;
 285       --  The size of the secondary stack up to, but excluding the current
 286       --  chunk. This value aids in calculating the total amount of memory
 287       --  the stack is consuming, for high-water-mark update purposes.
 288
 289       Memory : Chunk_Memory (1 .. Size);
 290       --  The memory storage of the chunk. The 1-indexing facilitates various
 291       --  size and indexing calculations.
 292    end record;
 293
 294    -------------------
 295    -- Stack_Pointer --
 296    -------------------
 297
 298    --  Abstraction for a secondary stack pointer
 299
 300    type Stack_Pointer is record
 301       Byte : Memory_Index;
 302       --  The position of the first free byte within the memory storage of
 303       --  Chunk.all. Byte - 1 denotes the last occupied byte within Chunk.all.
 304
 305       Chunk : SS_Chunk_Ptr;
 306       --  Reference to the chunk that accommodated the most recent allocation.
 307       --  This could be the static or any dynamic chunk.
 308    end record;
 309
 310    --------------
 311    -- SS_Stack --
 312    --------------
 313
 314    type SS_Stack (Default_Chunk_Size : SP.Size_Type) is record
 315       Freeable : Boolean;
 316       --  Indicates whether the secondary stack can be freed
 317
 318       High_Water_Mark : Memory_Size;
 319       --  The maximum amount of memory in use throughout the lifetime of the
 320       --  secondary stack.
 321
 322       Top : Stack_Pointer;
 323       --  The stack pointer
 324
 325       Static_Chunk : aliased SS_Chunk (Default_Chunk_Size);
 326       --  A special chunk with a default size. On targets that do not support
 327       --  dynamic allocations, this chunk represents the capacity of the whole
 328       --  secondary stack.
 329    end record;
 330
 331    -------------
 332    -- Mark_Id --
 333    -------------
 334
 335    type Mark_Id is record
 336       Stack : SS_Stack_Ptr;
 337       --  The secondary stack whose mark was taken
 338
 339       Top : Stack_Pointer;
 340       --  The value of Stack.Top at the point in time when the mark was taken
 341    end record;
 342
 343    ------------------
 344    -- Testing Aids --
 345    ------------------
 346
 347    --  The following section provides lightweight versions of all abstractions
 348    --  used to implement a secondary stack. The contents of these versions may
 349    --  look identical to the original abstractions, however there are several
 350    --  important implications:
 351    --
 352    --    * The versions do not expose pointers.
 353    --
 354    --    * The types of the versions are all definite. In addition, there are
 355    --      no per-object constrained components. As a result, the versions do
 356    --      not involve the secondary stack or the heap in any way.
 357    --
 358    --    * The types of the versions do not contain potentially big components.
 359
 360    subtype Chunk_Id_With_Invalid is Natural;
 361    --  Numeric Id of a chunk with value zero
 362
 363    Invalid_Chunk_Id : constant Chunk_Id_With_Invalid := 0;
 364
 365    subtype Chunk_Id is
 366      Chunk_Id_With_Invalid range 1 .. Chunk_Id_With_Invalid'Last;
 367    --  Numeric Id of a chunk. A positive Id is considered "valid" because a
 368    --  secondary stack will have at least one chunk (the static chunk).
 369
 370    subtype Chunk_Count is Natural;
 371    --  Number of chunks in a secondary stack
 372
 373    --  Lightweight version of SS_Chunk
 374
 375    type Chunk_Info is record
 376       Size : Memory_Size_With_Invalid;
 377       --  The memory capacity of the chunk
 378
 379       Size_Up_To_Chunk : Memory_Size_With_Invalid;
 380       --  The size of the secondary stack up to, but excluding the current
 381       --  chunk.
 382    end record;
 383
 384    Invalid_Chunk : constant Chunk_Info :=
 385                      (Size             => Invalid_Memory_Size,
 386                       Size_Up_To_Chunk => Invalid_Memory_Size);
 387
 388    --  Lightweight version of Stack_Pointer
 389
 390    type Stack_Pointer_Info is record
 391       Byte : Memory_Index;
 392       --  The position of the first free byte within the memory storage of
 393       --  Chunk. Byte - 1 denotes the last occupied byte within Chunk.
 394
 395       Chunk : Chunk_Id_With_Invalid;
 396       --  The Id of the chunk that accommodated the most recent allocation.
 397       --  This could be the static or any dynamic chunk.
 398    end record;
 399
 400    --  Lightweight version of SS_Stack
 401
 402    type Stack_Info is record
 403       Default_Chunk_Size : Memory_Size;
 404       --  The default memory capacity of a chunk
 405
 406       Freeable : Boolean;
 407       --  Indicates whether the secondary stack can be freed
 408
 409       High_Water_Mark : Memory_Size;
 410       --  The maximum amount of memory in use throughout the lifetime of the
 411       --  secondary stack.
 412
 413       Number_Of_Chunks : Chunk_Count;
 414       --  The total number of static and dynamic chunks in the secondary stack
 415
 416       Top : Stack_Pointer_Info;
 417       --  The stack pointer
 418    end record;
 419
 420    function Get_Chunk_Info
 421      (Stack : SS_Stack_Ptr;
 422       C_Id  : Chunk_Id) return Chunk_Info;
 423    --  Obtain the information attributes of a chunk that belongs to secondary
 424    --  stack Stack and is identified by Id C_Id.
 425
 426    function Get_Stack_Info (Stack : SS_Stack_Ptr) return Stack_Info;
 427    --  Obtain the information attributes of secondary stack Stack
 428
 429 end System.Secondary_Stack;