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-2019, 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 32pragma Compiler_Unit_Warning; 33 34with System.Parameters; 35with System.Storage_Elements; 36 37package System.Secondary_Stack is 38 pragma Preelaborate; 39 40 package SP renames System.Parameters; 41 package SSE renames System.Storage_Elements; 42 43 use type SP.Size_Type; 44 45 type SS_Stack (Default_Chunk_Size : SP.Size_Type) is private; 46 -- An abstraction for a heap structure maintained in a stack-like fashion. 47 -- The structure is comprised of chunks which accommodate allocations of 48 -- varying sizes. See the private part of the package for further details. 49 -- Default_Chunk_Size indicates the size of the static chunk, and provides 50 -- a minimum size for all dynamic chunks. 51 52 type SS_Stack_Ptr is access all SS_Stack; 53 -- A reference to a secondary stack 54 55 type Mark_Id is private; 56 -- An abstraction for tracking the state of the secondary stack 57 58 procedure SS_Init 59 (Stack : in out SS_Stack_Ptr; 60 Size : SP.Size_Type := SP.Unspecified_Size); 61 -- Initialize or reuse a secondary stack denoted by reference Stack. If 62 -- Stack is null, create a new stack of size Size in the following manner: 63 -- 64 -- * If Size denotes Unspecified_Size, allocate the stack from the binder 65 -- generated pool as long as the pool has not been exhausted. 66 -- 67 -- * Otherwise allocate the stack from the heap. 68 -- 69 -- If Stack is not null, reset the state of the stack. No existing chunks 70 -- are freed because they may be reused again. 71 72 procedure SS_Allocate 73 (Addr : out Address; 74 Storage_Size : SSE.Storage_Count); 75 -- Allocate enough space on the secondary stack of the invoking task to 76 -- accommodate an alloction of size Storage_Size. Return the address of the 77 -- first byte of the allocation in Addr. The routine may carry out one or 78 -- more of the following 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 110private 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. It utilizes maximum alignment in 267 -- order to guarantee efficient operations. 268 269 -------------- 270 -- SS_Chunk -- 271 -------------- 272 273 type SS_Chunk (Size : Memory_Size); 274 -- Abstraction for a chunk. Size indicates the memory capacity of the 275 -- chunk. 276 277 type SS_Chunk_Ptr is access all SS_Chunk; 278 -- Reference to the static or any dynamic chunk 279 280 type SS_Chunk (Size : Memory_Size) is record 281 Next : SS_Chunk_Ptr; 282 -- Pointer to the next chunk. The direction of the pointer is from the 283 -- static chunk to the first dynamic chunk, and so on. 284 285 Size_Up_To_Chunk : Memory_Size; 286 -- The size of the secondary stack up to, but excluding the current 287 -- chunk. This value aids in calculating the total amount of memory 288 -- the stack is consuming, for high-water-mark update purposes. 289 290 Memory : Chunk_Memory (1 .. Size); 291 -- The memory storage of the chunk. The 1-indexing facilitates various 292 -- size and indexing calculations. 293 end record; 294 295 ------------------- 296 -- Stack_Pointer -- 297 ------------------- 298 299 -- Abstraction for a secondary stack pointer 300 301 type Stack_Pointer is record 302 Byte : Memory_Index; 303 -- The position of the first free byte within the memory storage of 304 -- Chunk.all. Byte - 1 denotes the last occupied byte within Chunk.all. 305 306 Chunk : SS_Chunk_Ptr; 307 -- Reference to the chunk that accommodated the most recent allocation. 308 -- This could be the static or any dynamic chunk. 309 end record; 310 311 -------------- 312 -- SS_Stack -- 313 -------------- 314 315 type SS_Stack (Default_Chunk_Size : SP.Size_Type) is record 316 Freeable : Boolean; 317 -- Indicates whether the secondary stack can be freed 318 319 High_Water_Mark : Memory_Size; 320 -- The maximum amount of memory in use throughout the lifetime of the 321 -- secondary stack. 322 323 Top : Stack_Pointer; 324 -- The stack pointer 325 326 Static_Chunk : aliased SS_Chunk (Default_Chunk_Size); 327 -- A special chunk with a default size. On targets that do not support 328 -- dynamic allocations, this chunk represents the capacity of the whole 329 -- secondary stack. 330 end record; 331 332 ------------- 333 -- Mark_Id -- 334 ------------- 335 336 type Mark_Id is record 337 Stack : SS_Stack_Ptr; 338 -- The secondary stack whose mark was taken 339 340 Top : Stack_Pointer; 341 -- The value of Stack.Top at the point in time when the mark was taken 342 end record; 343 344 ------------------ 345 -- Testing Aids -- 346 ------------------ 347 348 -- The following section provides lightweight versions of all abstractions 349 -- used to implement a secondary stack. The contents of these versions may 350 -- look identical to the original abstractions, however there are several 351 -- important implications: 352 -- 353 -- * The versions do not expose pointers. 354 -- 355 -- * The types of the versions are all definite. In addition, there are 356 -- no per-object constrained components. As a result, the versions do 357 -- not involve the secondary stack or the heap in any way. 358 -- 359 -- * The types of the versions do not contain potentially big components. 360 361 subtype Chunk_Id_With_Invalid is Natural; 362 -- Numeric Id of a chunk with value zero 363 364 Invalid_Chunk_Id : constant Chunk_Id_With_Invalid := 0; 365 366 subtype Chunk_Id is 367 Chunk_Id_With_Invalid range 1 .. Chunk_Id_With_Invalid'Last; 368 -- Numeric Id of a chunk. A positive Id is considered "valid" because a 369 -- secondary stack will have at least one chunk (the static chunk). 370 371 subtype Chunk_Count is Natural; 372 -- Number of chunks in a secondary stack 373 374 -- Lightweight version of SS_Chunk 375 376 type Chunk_Info is record 377 Size : Memory_Size_With_Invalid; 378 -- The memory capacity of the chunk 379 380 Size_Up_To_Chunk : Memory_Size_With_Invalid; 381 -- The size of the secondary stack up to, but excluding the current 382 -- chunk. 383 end record; 384 385 Invalid_Chunk : constant Chunk_Info := 386 (Size => Invalid_Memory_Size, 387 Size_Up_To_Chunk => Invalid_Memory_Size); 388 389 -- Lightweight version of Stack_Pointer 390 391 type Stack_Pointer_Info is record 392 Byte : Memory_Index; 393 -- The position of the first free byte within the memory storage of 394 -- Chunk. Byte - 1 denotes the last occupied byte within Chunk. 395 396 Chunk : Chunk_Id_With_Invalid; 397 -- The Id of the chunk that accommodated the most recent allocation. 398 -- This could be the static or any dynamic chunk. 399 end record; 400 401 -- Lightweight version of SS_Stack 402 403 type Stack_Info is record 404 Default_Chunk_Size : Memory_Size; 405 -- The default memory capacity of a chunk 406 407 Freeable : Boolean; 408 -- Indicates whether the secondary stack can be freed 409 410 High_Water_Mark : Memory_Size; 411 -- The maximum amount of memory in use throughout the lifetime of the 412 -- secondary stack. 413 414 Number_Of_Chunks : Chunk_Count; 415 -- The total number of static and dynamic chunks in the secondary stack 416 417 Top : Stack_Pointer_Info; 418 -- The stack pointer 419 end record; 420 421 function Get_Chunk_Info 422 (Stack : SS_Stack_Ptr; 423 C_Id : Chunk_Id) return Chunk_Info; 424 -- Obtain the information attributes of a chunk that belongs to secondary 425 -- stack Stack and is identified by Id C_Id. 426 427 function Get_Stack_Info (Stack : SS_Stack_Ptr) return Stack_Info; 428 -- Obtain the information attributes of secondary stack Stack 429 430end System.Secondary_Stack; 431