1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 **
10 ** This file declares the functions of Gasman, the GAP storage manager.
11 **
12 ** {\Gasman} is a storage manager for applications written in C. That means
13 ** that an application requests blocks of storage from {\Gasman}, which are
14 ** called bags. After using a bag to store data, the application simply
15 ** forgets the bag, and we say that such a block is dead. {\Gasman}
16 ** implements an automatic, cooperating, compacting, generational,
17 ** conservative storage manager. Automatic means that the application only
18 ** allocates bags, but need not explicitly deallocate them. This is
19 ** important for large or complex application, where explicit deallocation
20 ** is difficult. Cooperating means that the allocation must cooperate with
21 ** {\Gasman}, i.e., must follow certain rules. This information provided by
22 ** the application makes {\Gasman} use less storage and run faster.
23 ** Compacting means that {\Gasman} always compacts live bags such that the
24 ** free storage is one large block. Because there is no fragmentation of
25 ** the free storage {\Gasman} uses as little storage as possible.
26 ** Generational means that {\Gasman} usually assumes that bags that have
27 ** been live for some time are still live. This means that it can avoid
28 ** most of the tests whether a bag is still live or already dead. Only when
29 ** not enough storage can be reclaimed under this assumption does it perform
30 ** all the tests. Conservative means that {\Gasman} may keep bags longer
31 ** than necessary because the C compiler does not provide sufficient
32 ** information to distinguish true references to bags from other values that
33 ** happen to look like references.
34 */
35
36 #ifndef GAP_GASMAN_H
37 #define GAP_GASMAN_H
38
39 #include "system.h"
40
41
42 /****************************************************************************
43 **
44 *T Bag . . . . . . . . . . . . . . . . . . . type of the identifier of a bag
45 **
46 ** Each bag is identified by its *bag identifier*. That is each bag has a
47 ** bag identifier and no two live bags have the same identifier. 'Bag' is
48 ** the type of bag identifiers.
49 **
50 ** 0 is a valid value of the type 'Bag', but is guaranteed not to be the
51 ** identifier of any bag.
52 **
53 ** 'NewBag' returns the identifier of the newly allocated bag and the
54 ** application passes this identifier to every {\Gasman} function to tell it
55 ** which bag it should operate on (see "NewBag", "TNUM_BAG", "SIZE_BAG",
56 ** "PTR_BAG", "CHANGED_BAG", "RetypeBag", and "ResizeBag").
57 **
58 ** Note that the identifier of a bag is different from the address of the
59 ** data area of the bag. This address may change during a garbage
60 ** collection while the identifier of a bag never changes.
61 **
62 ** Bags that contain references to other bags must always contain the
63 ** identifiers of these other bags, never the addresses of the data areas of
64 ** the bags.
65 **
66 ** Note that bag identifiers are recycled. That means that after a bag dies
67 ** its identifier may be reused for a new bag.
68 **
69 ** The following is defined in "system.h"
70 **
71 typedef UInt * * Bag;
72 */
73
74
75 /****************************************************************************
76 **
77 **
78 */
79 typedef struct {
80 uint8_t type : 8;
81 uint8_t flags : 8;
82 // the following unnamed field ensures that on 32 bit systems,
83 // the 'size' field is aligned to a 32 bit boundary
84 uint16_t : (sizeof(UInt) == 8) ? 0 : 16;
85 uint64_t size : (sizeof(UInt) == 8) ? 48 : 32;
86 #ifdef USE_GASMAN
87 Bag link;
88 #endif
89 #if defined(GAP_MEMORY_CANARY)
90 // The following variable is marked as not readable or writable
91 // in valgrind, to check for code reading before the start of a Bag.
92 uint64_t memory_canary_padding[8];
93 #endif
94 } BagHeader;
95
96
97 /****************************************************************************
98 **
99 ** 'NUM_TYPES' is the maximal number of different types supported, and
100 ** depends on the number of bits in the type member of struct BagHeader.
101 ** It must be a power of two.
102 */
103 enum {
104 NUM_TYPES = 256,
105 };
106
107
108 /****************************************************************************
109 **
110 *F BAG_HEADER(<bag>) . . . . . . . . . . . . . . . . . . . . header of a bag
111 **
112 ** 'BAG_HEADER' returns the header of the bag with the identifier <bag>.
113 */
BAG_HEADER(Bag bag)114 EXPORT_INLINE BagHeader * BAG_HEADER(Bag bag)
115 {
116 GAP_ASSERT(bag);
117 return (((BagHeader *)*bag) - 1);
118 }
119
120
121 /****************************************************************************
122 **
123 *F TNUM_BAG(<bag>) . . . . . . . . . . . . . . . . . . . . . . type of a bag
124 **
125 ** 'TNUM_BAG' returns the type of the bag with the identifier <bag>.
126 **
127 ** Each bag has a certain type that identifies its structure. The type is a
128 ** integer between 0 and 253. The types 254 and 255 are reserved for
129 ** {\Gasman}. The application specifies the type of a bag when it allocates
130 ** it with 'NewBag' and may later change it with 'RetypeBag' (see "NewBag"
131 ** and "RetypeBag").
132 **
133 ** {\Gasman} needs to know the type of a bag so that it knows which function
134 ** to call to mark all subbags of a given bag (see "InitMarkFuncBags").
135 ** Apart from that {\Gasman} does not care at all about types.
136 */
TNUM_BAG(Bag bag)137 EXPORT_INLINE UInt TNUM_BAG(Bag bag)
138 {
139 return BAG_HEADER(bag)->type;
140 }
141
142
143 /****************************************************************************
144 **
145 *F TEST_BAG_FLAG(<bag>, <flag>) . . . . . . . . . . . . . . . test bag flag
146 *F SET_BAG_FLAG(<bag>, <flag>) . . . . . . . . . . . . . . . . set bag flag
147 *F CLEAR_BAG_FLAG(<bag>, <flag>) . . . . . . . . . . . . . . clear bag flag
148 **
149 ** These three macros test, set, and clear bag flags, respectively.
150 ** Bag flags are stored in the bag header. Multiple flags can be ored
151 ** together using '|' to set or clear multiple flags at once.
152 **
153 ** TEST_BAG_FLAG() will return the ored version of all tested flags. To
154 ** test that one of them is set, check if the result is not equal to zero.
155 ** To test that all of them are set, compare the result to the original
156 ** flags, e.g.
157 **
158 ** if (TEST_BAG_FLAG(obj, FLAG1 | FLAG2 ) == (FLAG1 | FLAG2)) ...
159 **
160 ** Similary, if you wish to test that FLAG1 is set and FLAG2 is not set,
161 ** use:
162 **
163 ** if (TEST_BAG_FLAG(obj, FLAG1 | FLAG2 ) == FLAG1) ...
164 **
165 ** Each flag must be a an integer with exactly one bit set, e.g. a value
166 ** of the form (1 << i). Currently, 'i' must be in the range from 0 to
167 ** 7 (inclusive).
168 */
TEST_BAG_FLAG(Bag bag,uint8_t flag)169 EXPORT_INLINE uint8_t TEST_BAG_FLAG(Bag bag, uint8_t flag)
170 {
171 return BAG_HEADER(bag)->flags & flag;
172 }
173
SET_BAG_FLAG(Bag bag,uint8_t flag)174 EXPORT_INLINE void SET_BAG_FLAG(Bag bag, uint8_t flag)
175 {
176 BAG_HEADER(bag)->flags |= flag;
177 }
178
CLEAR_BAG_FLAG(Bag bag,uint8_t flag)179 EXPORT_INLINE void CLEAR_BAG_FLAG(Bag bag, uint8_t flag)
180 {
181 BAG_HEADER(bag)->flags &= ~flag;
182 }
183
184 /****************************************************************************
185 **
186 *F IS_BAG_REF(<bag>) . . . . . . verify that <bag> is a valid bag identifier
187 **
188 ** 'IS_BAG_REF' checks whether <bag> is a valid bag identifier, i.e. that
189 ** it is neither zero, nor an immediate object.
190 **
191 ** See also 'IS_INTOBJ' and 'IS_FFE'.
192 */
IS_BAG_REF(Obj bag)193 EXPORT_INLINE Int IS_BAG_REF(Obj bag)
194 {
195 return bag && !((Int)bag & 0x03);
196 }
197
198
199 /****************************************************************************
200 **
201 *F SIZE_BAG(<bag>) . . . . . . . . . . . . . . . . . . . . . . size of a bag
202 **
203 ** 'SIZE_BAG' returns the size of the bag with the identifier <bag> in
204 ** bytes.
205 **
206 ** Each bag has a certain size. The size of a bag is measured in bytes.
207 ** The size must be a value between 0 and $2^{32}-1$ (on 32 bit systems)
208 ** respectively $2^{48}-1$ (on 64 bit systems). The application specifies
209 ** the size of a bag when it allocates it with 'NewBag' and may later change
210 ** it with 'ResizeBag' (see "NewBag" and "ResizeBag").
211 */
SIZE_BAG(Bag bag)212 EXPORT_INLINE UInt SIZE_BAG(Bag bag) {
213 return BAG_HEADER(bag)->size;
214 }
215
216
217 /****************************************************************************
218 **
219 *F SIZE_BAG_CONTENTS(<ptr>) . . . . . . . . . . . . . . . . . size of a bag
220 **
221 ** 'SIZE_BAG_CONTENTS' performs the same function as 'SIZE_BAG', but takes
222 ** a pointer to the contents of the bag instead. This is useful for certain
223 ** atomic operations that require a memory barrier in between dereferencing
224 ** the bag pointer and accessing the contents of the bag.
225 */
SIZE_BAG_CONTENTS(const void * ptr)226 EXPORT_INLINE UInt SIZE_BAG_CONTENTS(const void *ptr) {
227 return ((const BagHeader *)ptr)[-1].size;
228 }
229
230
231 /****************************************************************************
232 **
233 *F LINK_BAG(<bag>) . . . . . . . . . . . . . . . . . . link pointer of a bag
234 **
235 ** 'LINK_BAG' returns the link pointer of the bag with the identifier <bag>.
236 **
237 ** Note that 'LINK_BAG' is a macro, so do not call it with arguments that
238 ** have side effects.
239 */
240 #ifdef USE_GASMAN
241 #define LINK_BAG(bag) (BAG_HEADER(bag)->link)
242 #endif
243
244
245 /****************************************************************************
246 **
247 *F PTR_BAG(<bag>) . . . . . . . . . . . . . . . . . . . . pointer to a bag
248 **
249 ** 'PTR_BAG' returns the address of the data area of the bag with identifier
250 ** <bag>. Using this pointer the application can then read data from the
251 ** bag or write data into it. The pointer is of type pointer to bag
252 ** identifier, i.e., 'PTR_BAG(<bag>)[0]' is the identifier of the first
253 ** subbag of the bag, etc. If the bag contains data in a different format,
254 ** the application has to cast the pointer returned by 'PTR_BAG', e.g.,
255 ** '(long\*)PTR_BAG(<bag>)'.
256 **
257 ** Note that the address of the data area of a bag may change during a
258 ** garbage collection. That is the value returned by 'PTR_BAG' may differ
259 ** between two calls, if 'NewBag', 'ResizeBag', 'CollectBags', or any of the
260 ** application\'s functions or macros that may call those functions, is
261 ** called in between (see "NewBag", "ResizeBag", "CollectBags").
262 **
263 ** The first rule for using {\Gasman} is{\:} *The application must not keep
264 ** any pointers to or into the data area of any bag over calls to functions
265 ** that may cause a garbage collection.*
266 **
267 ** That means that the following code is incorrect{\:}
268 **
269 ** ptr = PTR_BAG( old );
270 ** new = NewBag( typeNew, sizeNew );
271 ** *ptr = new;
272 **
273 ** because the creation of the new bag may move the old bag, causing the
274 ** pointer to point no longer to the data area of the bag. It must be
275 ** written as follows{\:}
276 **
277 ** new = NewBag( typeNew, sizeNew );
278 ** ptr = PTR_BAG( old );
279 ** *ptr = new;
280 **
281 ** Note that even the following is incorrect{\:}
282 **
283 ** PTR_BAG(old)[0] = NewBag( typeNew, sizeNew );
284 **
285 ** because a C compiler is free to compile it to a sequence of instructions
286 ** equivalent to first example. Thus whenever the evaluation of a function
287 ** or a macro may cause a garbage collection there must be no call to
288 ** 'PTR_BAG' in the same expression, except as argument to this function or
289 ** macro.
290 **
291 ** Note that after writing a bag identifier, e.g., 'new' in the above
292 ** example, into the data area of another bag, 'old' in the above example,
293 ** the application must inform {\Gasman} that it has changed the bag, by
294 ** calling 'CHANGED_BAG(old)' in the above example (see "CHANGED_BAG").
295 */
PTR_BAG(Bag bag)296 EXPORT_INLINE Bag *PTR_BAG(Bag bag)
297 {
298 GAP_ASSERT(bag != 0);
299 return *(Bag**)bag;
300 }
301
CONST_PTR_BAG(Bag bag)302 EXPORT_INLINE const Bag *CONST_PTR_BAG(Bag bag)
303 {
304 GAP_ASSERT(bag != 0);
305 return *(const Bag * const *)bag;
306 }
307
SET_PTR_BAG(Bag bag,Bag * val)308 EXPORT_INLINE void SET_PTR_BAG(Bag bag, Bag *val)
309 {
310 GAP_ASSERT(bag != 0);
311 *(Bag**)bag = val;
312 }
313
314
315 /****************************************************************************
316 **
317 *F CHANGED_BAG(<bag>) . . . . . . . . notify Gasman that a bag has changed
318 **
319 ** 'CHANGED_BAG' informs {\Gasman} that the bag with identifier <bag> has
320 ** been changed by an assignment of another bag identifier.
321 **
322 ** The second rule for using {\Gasman} is{\:} *After each assignment of a
323 ** bag identifier into a bag the application must inform {\Gasman} that it
324 ** has changed the bag before the next garbage collection can happen.*
325 **
326 ** Note that the application need not inform {\Gasman} if it changes a bag
327 ** by assigning something that is not an identifier of another bag.
328 **
329 ** For example to copy all entries from one list into another the following
330 ** code must be used{\:}
331 **
332 ** for ( i = 0; i < SIZE-BAG(old)/sizeof(Bag); i++ )
333 ** PTR_BAG(new)[i] = PTR_BAG(old)[i];
334 ** CHANGED_BAG( new );
335 **
336 ** On the other hand when the application allocates a matrix, where the
337 ** allocation of each row may cause a garbage collection, the following code
338 ** must be used{\:}
339 **
340 ** mat = NewBag( T_MAT, n * sizeof(Bag) );
341 ** for ( i = 0; i < n; i++ ) {
342 ** row = NewBag( T_ROW, n * sizeof(Bag) );
343 ** PTR_BAG(mat)[i] = row;
344 ** CHANGED_BAG( mat );
345 ** }
346 **
347 ** Note that writing 'PTR_BAG(mat)[i] = NewBag( T_ROW, n\*\ sizeof(Bag) );'
348 ** is incorrect as mentioned in the section for 'PTR_BAG' (see "PTR_BAG").
349 */
350
351 #if defined(USE_BOEHM_GC)
352
CHANGED_BAG(Bag bag)353 EXPORT_INLINE void CHANGED_BAG(Bag bag)
354 {
355 }
356
357 #elif defined(USE_JULIA_GC)
358
359 void CHANGED_BAG(Bag bag);
360
361 int IsGapObj(void *);
362
363 #elif defined(GAP_MEMORY_CANARY)
364
365 /****************************************************************************
366 **
367 ** GAP_MEMORY_CANARY provides (basic) support for catching out-of-bounds
368 ** memory problems in GAP. This is done through the excellent 'valgrind'
369 ** program. Valgrind is of limited use in GAP normally, because it doesn't
370 ** understand GAP's memory manager. Enabling GAP_MEMORY_CANARY will make an
371 ** executable where valgrind will detect memory issues.
372 **
373 */
374
375 void CHANGED_BAG(Bag b);
376
377 #elif defined(USE_GASMAN)
378
379 extern Bag * YoungBags;
380 extern Bag ChangedBags;
CHANGED_BAG(Bag bag)381 EXPORT_INLINE void CHANGED_BAG(Bag bag)
382 {
383 if (CONST_PTR_BAG(bag) <= YoungBags && LINK_BAG(bag) == bag) {
384 LINK_BAG(bag) = ChangedBags;
385 ChangedBags = bag;
386 }
387 }
388
389 #else
390
391 #error unknown garbage collector
392
393 #endif
394
395
396 /****************************************************************************
397 **
398 *F NewBag(<type>,<size>) . . . . . . . . . . . . . . . . allocate a new bag
399 **
400 ** 'NewBag' allocates a new bag of type <type> and <size> bytes. 'NewBag'
401 ** returns the identifier of the new bag, which must be passed as first
402 ** argument to all other {\Gasman} functions.
403 **
404 ** <type> must be a value between 0 and 253. The types 254 and 255 are
405 ** reserved for {\Gasman}. The application can find the type of a bag with
406 ** 'TNUM_BAG' and change it with 'RetypeBag' (see "TNUM_BAG" and
407 ** "RetypeBag").
408 **
409 ** It is probably a good idea to define symbolic constants for all types in
410 ** a system wide header file, e.g., 'types.h', if only to avoid to
411 ** accidently use the same value for two different types.
412 **
413 ** <size> is the size of the new bag in bytes and must be a value between 0
414 ** and $2^{32}-1$ (on 32 bit systems) resp. $2^{48}-1$ (on 64 bit systems).
415 ** The application can find the size of a bag with 'SIZE_BAG' and change it
416 ** with 'ResizeBag' (see "SIZE_BAG" and "ResizeBag").
417 **
418 ** All entries of the new bag will be initialized to 0.
419 **
420 ** What happens if {\Gasman} cannot get enough storage to perform an
421 ** allocation depends on the behavior of the allocation function
422 ** <alloc-func>. If <alloc-func> returns 0 when it cannot do a needed
423 ** extension of the workspace, then 'NewBag' may return 0 to indicate
424 ** failure, and the application has to check the return value of 'NewBag'
425 ** for this. If <alloc-func> aborts when it cannot do a needed extension of
426 ** the workspace, then the application will abort if 'NewBag' would not
427 ** succeed. So in this case whenever 'NewBag' returns, it succeeded, and
428 ** the application need not check the return value of 'NewBag' (see
429 ** "InitBags").
430 **
431 ** Note that 'NewBag' will perform a garbage collection if no free storage
432 ** is available. During the garbage collection the addresses of the data
433 ** areas of all bags may change. So you must not keep any pointers to or
434 ** into the data areas of bags over calls to 'NewBag' (see "PTR_BAG").
435 */
436 Bag NewBag(UInt type, UInt size);
437
438
439 // NewWordSizedBag is the same as NewBag, except it rounds 'size' up to
440 // the next multiple of sizeof(UInt)
NewWordSizedBag(UInt type,UInt size)441 EXPORT_INLINE Bag NewWordSizedBag(UInt type, UInt size)
442 {
443 UInt padding = 0;
444 if(size % sizeof(UInt) != 0) {
445 padding = sizeof(UInt) - (size % sizeof(UInt));
446 }
447 return NewBag(type, size + padding);
448 }
449
450 /****************************************************************************
451 **
452 *F RetypeBag(<bag>,<new>) . . . . . . . . . . . . change the type of a bag
453 **
454 ** 'RetypeBag' changes the type of the bag with identifier <bag> to the new
455 ** type <new>. The identifier, the size, and also the address of the data
456 ** area of the bag do not change.
457 **
458 ** 'Retype' is usually used to set or reset flags that are stored in the
459 ** type of a bag. For example in {\GAP} there are two types of large
460 ** integers, one for positive integers and one for negative integers. To
461 ** compute the difference of a positive integer and a negative, {\GAP} uses
462 ** 'RetypeBag' to temporarily change the second argument into a positive
463 ** integer, and then adds the two operands. For another example when {\GAP}
464 ** detects that a list is sorted and contains no duplicates, it changes the
465 ** type of the bag with 'RetypeBag', and the new type indicates that this
466 ** list has this property, so that this need not be tested again.
467 **
468 ** It is, as usual, the responsibility of the application to ensure that the
469 ** data stored in the bag makes sense when the bag is interpreted as a bag
470 ** of type <type>.
471 */
472 void RetypeBag(Bag bag, UInt new_type);
473
474 #ifdef HPCGAP
475 void RetypeBagIfWritable(Bag bag, UInt new_type);
476 #else
477 #define RetypeBagIfWritable(x,y) RetypeBag(x,y)
478 #endif
479
480
481 /****************************************************************************
482 **
483 ** 'RetypeBagSM' works like 'RetypeBag', but ensures that the given bag
484 ** returns the same mutability (SM).
485 **
486 ** FIXME: for now, this checks the tnums; later, this will be turned
487 ** into a check for an object flag
488 */
489 void RetypeBagSM(Bag bag, UInt new_type);
490 #ifdef HPCGAP
491 void RetypeBagSMIfWritable(Bag bag, UInt new_type);
492 #else
493 #define RetypeBagSMIfWritable(x,y) RetypeBagSM(x,y)
494 #endif
495
496
497 /****************************************************************************
498 **
499 *F ResizeBag(<bag>,<new>) . . . . . . . . . . . . change the size of a bag
500 **
501 ** 'ResizeBag' changes the size of the bag with identifier <bag> to the new
502 ** size <new>. The identifier of the bag does not change, but the address
503 ** of the data area of the bag may change. If the new size <new> is less
504 ** than the old size, {\Gasman} throws away any data in the bag beyond the
505 ** new size. If the new size <new> is larger than the old size, {\Gasman}
506 ** extends the bag.
507 **
508 ** All entries of an extension will be initialized to 0.
509 **
510 ** What happens if {\Gasman} cannot get enough storage to perform an
511 ** extension depends on the behavior of the allocation function
512 ** <alloc-func>. If <alloc-func> returns 0 when it cannot do a needed
513 ** extension of the workspace, then 'ResizeBag' may return 0 to indicate
514 ** failure, and the application has to check the return value of 'ResizeBag'
515 ** for this. If <alloc-func> aborts when it cannot do a needed extension of
516 ** the workspace, then the application will abort if 'ResizeBag' would not
517 ** succeed. So in this case whenever 'ResizeBag' returns, it succeeded, and
518 ** the application need not check the return value of 'ResizeBag' (see
519 ** "InitBags").
520 **
521 ** Note that 'ResizeBag' will perform a garbage collection if no free
522 ** storage is available. During the garbage collection the addresses of the
523 ** data areas of all bags may change. So you must not keep any pointers to
524 ** or into the data areas of bags over calls to 'ResizeBag' (see "PTR_BAG").
525 */
526 UInt ResizeBag(Bag bag, UInt new_size);
527
528 // ResizedWordSizedBag is the same as ResizeBag, except it round 'size'
529 // up to the next multiple of sizeof(UInt)
ResizeWordSizedBag(Bag bag,UInt size)530 EXPORT_INLINE UInt ResizeWordSizedBag(Bag bag, UInt size)
531 {
532 UInt padding = 0;
533 if(size % sizeof(UInt) != 0) {
534 padding = sizeof(UInt) - (size % sizeof(UInt));
535 }
536 return ResizeBag(bag, size + padding);
537 }
538
539
540 /****************************************************************************
541 **
542 *F CollectBags(<size>,<full>) . . . . . . . . . . . . . . collect dead bags
543 **
544 ** 'CollectBags' performs a garbage collection. This means it deallocates
545 ** the dead bags and compacts the live bags at the beginning of the
546 ** workspace. If <full> is 0, then only the dead young bags are
547 ** deallocated, otherwise all dead bags are deallocated.
548 **
549 ** If the application calls 'CollectBags', <size> must be 0, and <full> must
550 ** be 0 or 1 depending on whether it wants to perform a partial or a full
551 ** garbage collection.
552 **
553 ** If 'CollectBags' is called from 'NewBag' or 'ResizeBag', <size> is the
554 ** size of the bag that is currently allocated, and <full> is zero.
555 **
556 ** Note that during the garbage collection the addresses of the data areas
557 ** of all bags may change. So you must not keep any pointers to or into the
558 ** data areas of bags over calls to 'CollectBags' (see "PTR_BAG").
559 */
560 UInt CollectBags(UInt size, UInt full);
561
562
563 /****************************************************************************
564 **
565 *F SwapMasterPoint( <bag1>, <bag2> ) . . . swap pointer of <bag1> and <bag2>
566 */
567 void SwapMasterPoint(Bag bag1, Bag bag2);
568
569
570 /****************************************************************************
571 **
572 *V SizeAllBags . . . . . . . . . . . . . . total size of all bags allocated
573 **
574 ** 'SizeAllBags' is the total size of bags allocated since Gasman was
575 ** initialized. It is incremented for each 'NewBag' call.
576 */
577 extern UInt8 SizeAllBags;
578
579
580 /****************************************************************************
581 **
582 *V InfoBags[<type>] . . . . . . . . . . . . . . . . . information for bags
583 **
584 ** 'InfoBags[<type>]' is a structure containing information for bags of the
585 ** type <type>.
586 **
587 ** 'InfoBags[<type>].nrLive' is the number of bags of type <type> that are
588 ** currently live.
589 **
590 ** 'InfoBags[<type>].nrAll' is the total number of all bags of <type> that
591 ** have been allocated.
592 **
593 ** 'InfoBags[<type>].sizeLive' is the sum of the sizes of the bags of type
594 ** <type> that are currently live.
595 **
596 ** 'InfoBags[<type>].sizeAll' is the sum of the sizes of all bags of type
597 ** <type> that have been allocated.
598 **
599 ** This information is only kept if {\Gasman} is compiled with the option
600 ** 'COUNT_BAGS' defined.
601 */
602 #ifdef COUNT_BAGS
603 typedef struct {
604 UInt nrLive;
605 UInt nrAll;
606 UInt sizeLive;
607 UInt sizeAll;
608 } TNumInfoBags;
609
610 extern TNumInfoBags InfoBags [ 256 ];
611 #endif
612
613
614 #ifdef HPCGAP
615 void MakeBagTypePublic(int type);
616 Bag MakeBagPublic(Bag bag);
617 Bag MakeBagReadOnly(Bag bag);
618 #endif
619
620
621 /****************************************************************************
622 **
623 *F InitMarkFuncBags(<type>,<mark-func>) . . . . . install marking function
624 **
625 ** 'InitMarkFuncBags' installs the function <mark-func> as marking function
626 ** for bags of type <type>. The application *must* install a marking
627 ** function for a type before it allocates any bag of that type. It is
628 ** probably best to install all marking functions before allocating any bag.
629 **
630 ** A marking function is a function that takes a single argument of type
631 ** 'Bag' and returns nothing, i.e., has return type 'void'. Such a function
632 ** must apply the function 'MarkBag' to each bag identifier that appears in
633 ** the bag (see below).
634 **
635 ** Those functions are applied during the garbage collection to each marked
636 ** bag, i.e., bags that are assumed to be still live, to also mark their
637 ** subbags. The ability to use the correct marking function is the only use
638 ** that {\Gasman} has for types.
639 **
640 ** {\Gasman} already provides several marking functions, see below.
641 */
642 typedef void (* TNumMarkFuncBags )( Bag bag );
643 void InitMarkFuncBags(UInt type, TNumMarkFuncBags mark_func);
644
645 #if !defined(USE_THREADSAFE_COPYING) && !defined(USE_BOEHM_GC)
646 extern TNumMarkFuncBags TabMarkFuncBags[NUM_TYPES];
647 #endif
648
649 /****************************************************************************
650 **
651 *F MarkNoSubBags(<bag>) . . . . . . . . marking function that marks nothing
652 **
653 ** 'MarkNoSubBags' is a marking function for types whose bags contain no
654 ** identifier of other bags. It does nothing, as its name implies, and
655 ** simply returns. For example in {\GAP} the bags for large integers
656 ** contain only the digits and no identifiers of bags.
657 */
658 void MarkNoSubBags(Bag bag);
659
660
661 /****************************************************************************
662 **
663 *F MarkOneSubBags(<bag>) . . . . . . marking function that marks one subbag
664 *F MarkTwoSubBags(<bag>) . . . . . . marking function that marks two subbags
665 *F MarkThreeSubBags(<bag>) . . . . marking function that marks three subbags
666 *F MarkFourSubBags(<bag>) . . . . . marking function that marks four subbags
667 **
668 ** These are marking functions for types whose bags contain exactly the
669 ** the indicated number as bag identifiers as their initial entries.
670 ** These functions mark those subbags and return.
671 */
672 void MarkOneSubBags(Bag bag);
673 void MarkTwoSubBags(Bag bag);
674 void MarkThreeSubBags(Bag bag);
675 void MarkFourSubBags(Bag bag);
676
677
678 /****************************************************************************
679 **
680 *F MarkAllSubBags(<bag>) . . . . . . marking function that marks everything
681 **
682 ** 'MarkAllSubBags' is the marking function for types whose bags contain
683 ** only identifier of other bags. It marks every entry of such a bag. Note
684 ** that 'MarkAllSubBags' assumes that all identifiers are at offsets from
685 ** the address of the data area of <bag> that are divisible by
686 ** 'sizeof(Bag)'. Note also that since it does not do any harm to mark
687 ** something which is not actually a bag identifier one could use
688 ** 'MarkAllSubBags' for all types as long as the identifiers in the data
689 ** area are properly aligned as explained above. This would however slow
690 ** down 'CollectBags'. For example in {\GAP} bags for lists contain only
691 ** bag identifiers for the elements of the list or 0 if an entry has no
692 ** assigned value.
693 */
694 void MarkAllSubBags(Bag bag);
695
696 void MarkAllSubBagsDefault(Bag);
697
698 void MarkAllButFirstSubBags(Bag bag);
699
700 /****************************************************************************
701 **
702 *F MarkBag(<bag>) . . . . . . . . . . . . . . . . . . . mark a bag as live
703 **
704 ** 'MarkBag' marks the <bag> as live so that it is not thrown away during
705 ** a garbage collection. 'MarkBag' should only be called from the marking
706 ** functions installed with 'InitMarkFuncBags'.
707 **
708 ** 'MarkBag' tests if <bag> is a valid identifier of a bag in the young
709 ** bags area. If it is not, then 'MarkBag' does nothing, so there is no
710 ** harm in calling 'MarkBag' for something that is not actually a bag
711 ** identifier.
712 */
713 #ifdef USE_BOEHM_GC
MarkBag(Bag bag)714 EXPORT_INLINE void MarkBag( Bag bag )
715 {
716 }
717 #else
718 void MarkBag(Bag bag);
719 #endif
720
721
722 /****************************************************************************
723 **
724 *F MarkArrayOfBags(<array>,<count>) . . . . . . . mark all bags in an array
725 **
726 ** 'MarkArrayOfBags' iterates over <count> all bags in the given array,
727 ** and marks each bag using MarkBag.
728 */
729 extern void MarkArrayOfBags(const Bag array[], UInt count);
730
731
732 /****************************************************************************
733 **
734 *F InitGlobalBag(<addr>,<cookie>) inform Gasman about global bag identifier
735 **
736 ** 'InitGlobalBag' informs {\Gasman} that there is a bag identifier at the
737 ** address <addr>, which must be of type '(Bag\*)'. {\Gasman} will look at
738 ** this address for a bag identifier during a garbage collection.
739 **
740 ** The application *must* call 'InitGlobalBag' for every global variable and
741 ** every entry of a global array that may hold a bag identifier. It is no
742 ** problem if such a variable does not actually hold a bag identifier,
743 ** {\Gasman} will simply ignore it then.
744 **
745 ** There is a limit on the number of calls to 'InitGlobalBag', which is 20000
746 ** by default. If the application has more global variables that may hold
747 ** bag identifier, you have to compile {\Gasman} with a higher value of
748 ** 'NR_GLOBAL_BAGS'.
749 **
750 ** <cookie> is a C string, which should uniquely identify this global
751 ** bag from all others. It is used in reconstructing the Workspace
752 ** after a save and load
753 */
754
755 void InitGlobalBag(Bag * addr, const Char * cookie);
756
757
758 /****************************************************************************
759 **
760 *F InitFreeFuncBag(<type>,<free-func>) . . . . . . install freeing function
761 **
762 ** 'InitFreeFuncBag' installs the function <free-func> as freeing function
763 ** for bags of type <type>.
764 **
765 ** A freeing function is a function that takes a single argument of type
766 ** 'Bag' and returns nothing, i.e., has return type 'void'. If such a
767 ** function is installed for a type <type> then it is called for each bag of
768 ** that type that is about to be deallocated.
769 **
770 ** A freeing function must *not* call 'NewBag', 'ResizeBag', or 'RetypeBag'.
771 **
772 ** When such a function is called for a bag <bag>, its subbags are still
773 ** accessible. Note that it it not specified, whether the freeing functions
774 ** for the subbags of <bag> (if there are freeing functions for bags of
775 ** their types) are called before or after the freeing function for <bag>.
776 */
777 typedef void (* TNumFreeFuncBags ) (
778 Bag bag );
779
780 void InitFreeFuncBag(UInt type, TNumFreeFuncBags free_func);
781
782
783 /****************************************************************************
784 **
785 *F RegisterBeforeCollectFuncBags(<func>) install before-collection function
786 *F RegisterAfterCollectFuncBags(<func>) . install after-collection function
787 **
788 ** Register a callback to be called before respectively after each garbage
789 ** collection.
790 **
791 ** One use of a <before-func> is to call 'CHANGED_BAG' for bags that change
792 ** very often, so you do not have to call 'CHANGED_BAG' for them every time
793 ** they change.
794 **
795 ** One use of after-collection callbacks is to update a pointer for a bag,
796 ** so you do not have to update that pointer after every operation that
797 ** might cause a garbage collection.
798 **
799 ** The number of callbacks which can be registered is limited. If the
800 ** callback was successfully registered, 0 is returned, otherwise 1.
801 */
802 #ifdef USE_GASMAN
803 typedef void (* TNumCollectFuncBags) ( void );
804
805 int RegisterBeforeCollectFuncBags(TNumCollectFuncBags func);
806 int RegisterAfterCollectFuncBags(TNumCollectFuncBags func);
807 #endif
808
809
810 // ExtraMarkFuncBags, if not NULL, is called during garbage collection
811 // This is used for integrating GAP (possibly linked as a shared library) with
812 // other code bases which use their own form of garbage collection. For
813 // example, with Python (for SageMath).
814 typedef void (*TNumExtraMarkFuncBags)(void);
815 void SetExtraMarkFuncBags(TNumExtraMarkFuncBags func);
816
817 /****************************************************************************
818 **
819 *F InitBags(<initialSize>,<stackStart>,<stackAlign>) . . . initialize Gasman
820 **
821 ** 'InitBags' initializes {\Gasman}. It must be called from a application
822 ** using {\Gasman} before any bags can be allocated.
823 **
824 ** <initialSize> must be the size of the initial workspace that 'InitBags'
825 ** should allocate. This value is automatically rounded up to the next
826 ** multiple of 1/2 MByte by 'InitBags'.
827 **
828 ** <stackStart> must be the start of the stack. Note that the start of the
829 ** stack is either the bottom or the top of the stack, depending on whether
830 ** the stack grows upward or downward. A value that usually works is the
831 ** address of the argument 'argc' of the 'main' function of the application,
832 ** i.e., '(Bag\*)\&argc'.
833 **
834 ** <stackAlign> must be the alignment of items of type 'Bag' on the stack.
835 ** It must be a divisor of 'sizeof(Bag)'. The addresses of all identifiers
836 ** on the stack must be a multiple of <stackAlign>. If it is 1, identifiers
837 ** may be anywhere on the stack, and if it is 'sizeof(Bag)', identifiers may
838 ** only be at addresses that are a multiple of 'sizeof(Bag)'. This value
839 ** depends on the machine, the operating system, and the compiler.
840 */
841 void InitBags(UInt initialSize, Bag * stackStart, UInt stackAlign);
842
843
844 /****************************************************************************
845 **
846 *F FinishBags() end GASMAN and free memory
847 */
848 void FinishBags(void);
849
850 #if !defined(USE_GASMAN)
851 void * AllocateMemoryBlock(UInt size);
852 #endif
853
854 #endif // GAP_GASMAN_H
855