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