1 %************************************************************************
3 \section[closure-layout]{Closure Layout}
5 %************************************************************************
7 We first describes the data structures that are shared by
8 both the reducer and storage manager and then go on to describe
9 the interface and its implementation.
11 The heap consists of a contiguous sequence of closures. Each standard
12 closure occupies a contiguous sequence of machine words, which is laid
17 \mbox{\epsffile{closure.ps}}
23 < fixed-hdr-size> < var-hdr-size >
24 -----------------+-----------------+---------+-------------+
25 |info| | | | | | ptrs... | nonptrs ... |
26 -----------------+-----------------+---------+-------------+
27 <------------- header ------------>
31 The closure starts with a header. Typically, the first word in the
32 header is the {\em info pointer}, and points to its {\em info-table}.
33 The rest of the header is used for bookkeeping and depends on the
34 compiler options used. The fixed header is the same for all closures
35 while the variable header may depend on the closure type.
37 Following the header is a block of words each of which contains a
38 pointer to another closure, followed by a block of words containing
39 non-pointers. The non-pointers may include an unused portion of
40 ``slop'' needed to pad the closure. This is to satisfy any minimum
41 closure size requirements, primarily for updates in place. The
42 distinction between the pointers and non-pointers is that the garbage
43 collector must follow the former but not the latter. The pointers are
44 placed first to mimimize the number of distinct closure shapes that
45 have to be managed by the garbage collector.
47 There are a few non-standard closures which do not follow the convention
48 of placing all pointers first, but they are all administrative closures
49 which require their own unique garbage collection code anyway (such as
50 @TSO@'s and @STKO@'s in the threaded world).
52 The heap grows upwards (towards higher addresses), and closures are
53 laid out with the info pointer at the lowest address.
55 During reduction, the heap pointer (@Hp@) points to the last word of
56 allocated space (and not to the first word of free space) and the heap
57 limit (@HpLim@) points to the last word of available space.
59 %************************************************************************
61 \subsection[closure-size]{The ``Size'' of Closures}
63 %************************************************************************
65 When we speak of the ``size'' of a closure, we mean {\em the number of
66 words in the closure, excluding the fixed header, but including the
67 variable header, the pointers, non-pointers and slop, if any}.
69 All closures which may be updated must have a size of at least
70 @MIN_UPD_SIZE@---currently, this is two, so that they may be directly
71 overwritten with a small constructor closure, such as a @(:)@ cell or
72 an indirection on the ``mutables'' list.
74 %************************************************************************
76 \subsection[closure-kinds]{Types of Closure}
78 %************************************************************************
80 {\em This section is now hopelessly out-of-date}. This stuff is {\em
81 important} if you want newcomers to understand GHC. Am I the only
82 person who bothers with documentation?! KH
84 Yes, Kevin, you are. I've taken a stab at this section. I think {\em
85 hopelessly out-of-date} is a bit overboard, especially compared to
86 some of the other documentation in this system. If you still don't
87 like it, you're welcome to update it.
89 (Umm... Before we update it, would anyone like to go for a pizza?
92 We identify several kinds of heap closures. Each type of closure
93 is treated differently by the storage manager. Different
94 info-table macros are used to declare the appropriate info-tables used
95 by the storage manager (see section \ref{info-table-macros}).
97 Note: it is vitally important that every closure has an appropriate
98 info-table attached---otherwise chaos results!
102 \item[@SPEC@ closures:] These are standard closures which contain
103 specialized garbage collection code that ``knows'' the @size@/@ptrs@
104 of the closure. It is only possible to use a specialized info-table if
105 appropriately specialized garbage collection code is present in the
106 runtime system. This implies that the compiler needs to know which
107 @size@/@ptr@ combinations have specialized info-tables. A link-time
108 error results if the compiler attempts to build a @SPEC@ closure for
109 an inappropriate @size@/@ptr@ combination.
111 \item[@GEN@ closures:] These are normal closures which use generic
112 code for garbage collection. This interprets the @size@/@ptrs@
113 information stored in the info table. @GEN@ closures can be built for
114 any @size@/@ptrs@ combination.
116 \item[@DYN@ closures:] Dynamic closures have the layout information
117 (@size@/@ptrs@) stored within the variable header of the closure
118 itself. They are currently only used for partial applications (@PAP@s)
119 and the ``stable pointer table.''
120 %partain:\begin{center}
121 \begin{tabular}{|c|c|c|c|c|c|}
123 {\em Fixed Hdr} & {\em Size} & {\em No of ptrs} & {\em Pointers\ldots} & {\em Non-pointers\ldots} \\ \hline
125 %partain:\end{center}
127 \item[@TUPLE@ closure:] These are similar to @DYN@ closures but for
128 closures which contain only pointers. They are currently used for
129 primitive arrays of pointers when mutuples and immutuples do not have
130 to be distinguished during garbage collection.
131 %partain:\begin{center}
132 \begin{tabular}{|c|c|c|c|}
134 {\em Fixed Hdr} & {\em Size (= No of ptrs + TUPLE\_VHS)} & {\em Pointers\ldots} \\ \hline
136 %partain:\end{center}
138 \item[@DATA@ closures:] These are also similar to @DYN@ closures but
139 for closures containing only non-pointers. They are currently used for
140 primitive arrays of bytes (arbitrary precision integers and arrays of
141 unboxed values, for example).
142 %partain:\begin{center}
143 \begin{tabular}{|c|c|c|}
145 {\em Fixed Hdr} & {\em Size (= No of non-ptr words + DATA\_VHS)} & {\em Non-pointers\ldots} \\ \hline
147 %partain:\end{center}
149 \item[@MUTUPLE@ closures:] These are a variant of the @TUPLE@
150 closure. They are used when the garbage collection strategy requires a
151 distinction between mutable and immutable tuples (i.e. when there is a
152 ``mutables'' list.) Such an array may be frozen, becoming an @IMMUTUPLE@,
153 with a different info-table.
154 %partain:\begin{center}
155 \begin{tabular}{|c|c|c|c|}
157 {\em Fixed Hdr} & {\em Size (= No of ptrs + MUTUPLE\_VHS)} & {\em Pointers\ldots} \\ \hline
159 %partain:\end{center}
161 \item[@IMMUTUPLE@ closures:] These are frozen @MUTUPLE@ closures.
162 %mattson:\begin{center}
163 \begin{tabular}{|c|c|c|c|}
165 {\em Fixed Hdr} & {\em Size (= No of ptrs + MUTUPLE\_VHS)} & {\em Pointers\ldots} \\ \hline
167 %mattson:\end{center}
171 %************************************************************************
173 \subsection[special-closure-types]{Special types}
175 %************************************************************************
177 Special kinds of closures are required for static closures, ``black
178 holes'', indirections, and in-place updates.
180 When a ``black hole'' is updated it must be updated with a closure of
181 size @MIN_UPD_SIZE@ or less. Updates to some specific closure types
182 are handled specially, as follows:
186 if the new closure is of zero arity, then the black hole is replaced by
187 the corresponding static closure (@CONST@);
189 if the data type of the new closure is isomorphic to Char (one
190 constructor, with argument type @Char#@), then the black hole is
191 replaced by the corresponding member of the static character table
194 if the data type of the new closure is isomorphic to Int (one
195 constructor, with argument type @Int#@), and the argument is in the
196 range of the static small-int table then the black hole is replaced by
197 the corresponding member of the integer table (@INTLIKE@).
200 The special kinds of closure are:
204 \item[@STATIC@ closures:] These are closures which are declared
205 statically and hence do not reside in the heap. Such closures must not
206 contain any heap pointers and must not be updated. @CAF@ closures are
207 an exception; see below.
209 \item[@CONST@ closures:] There need be only one (static) closure for a
210 nullary constructor. These are declared static at compile time and all
211 references use the static closure (avoiding heap allocation). However,
212 dynamic heap-allocated ones will nevertheless arise through updates.
214 \item[@CHARLIKE@ and @INTLIKE@ closures] There is a similar story for
215 constructors which have a single primitive data field such as @Int#@
216 or @Char#@. During garbage collection, pointers to these closures can
217 be replaced with a known @STATIC@ closure if an appropriate one exists.
219 \item[@BH@ closures:] Black hole closures are used to overwrite
220 closures currently being evaluated. They inform the garbage collector
221 that there are no live roots in the closure, thus removing a potential
222 space leak. They also become synchronization points in the threaded
225 \item[@BQ@ closures:] Blocking queue closures are black holes with a
226 list of blocked threads to be awakened when the black hole is updated.
228 \item[@IND@ closures:] Indirection closures just point to other
229 closures. They are introduced when a closure is updated with a closure
230 that has to be allocated in the heap. The closure to be updated is
231 {\em indirected} to the new closure. Indirections are normally
232 removed during garbage collection. However, when profiling, it may be
233 necessary to maintain cost center information in an indirection, so
234 there are also ``permanent indirections'' which are retained forever.
236 \item[@CAF@ indirections:] These are statically defined closures which have
237 been updated with a heap-allocated result.
238 Initially these are exactly the same as a @STATIC@ closure but with
239 special entry code. On entering the closure the entry code must:
241 \item Allocate a black hole in the heap which will be updated with
243 \item Overwrite the static closure with a special @CAF@ indirection.
245 \item Link the static indirection onto the list of updated @CAF@s.
247 The indirection and the link field require the initial @STATIC@
248 closure to be of at least size @MIN_UPD_SIZE@ (excluding the fixed
251 @CAF@s are treated as special garbage collection roots. These roots
252 are explicitly collected by the garbage collector, since they may
253 appear in code even if they are not linked with the main heap. They
254 consequently represent potentially enormous space-leaks. A @CAF@
255 closure retains a fixed location in statically allocated data space.
256 When updated, the contents of the @CAF@ indirection are changed to
257 reflect the new closure. @CAF@ indirections require special garbage
260 \item[@FETCHME@ closures:] These are simply references to remote
261 objects in the parallel system.
263 \item[@TSO@ closures:] These are ``thread state objects,'' which are
264 used in the threaded world to maintain the context (STG registers,
265 PC location when asleep, etc.) for individual threads of computation.
267 \item[@STKO@ closures:] These are ``stack objects,'' which are
268 used in the threaded world as the stack for each thread is allocated
269 from the heap in smallish chunks. (The stack in the sequential world
270 is allocated outside of the heap.)
272 \item[@SPEC_RBH@ and @GEN_RBH@ closures:] These are ``revertible black
273 holes'' for updatable @SPEC@ (respectively @GEN@) closures. They are
274 currently used in the parallel system, but they could also be used for
275 speculation. They act like a black hole for thread synchronization,
276 but they can also be reverted back to the original @SPEC@
277 (respectively @GEN@) form (so they do introduce a space leak).
281 %************************************************************************
283 \subsection[closure-layout-macros]{Closure layout macros}
285 %************************************************************************
289 This is the number of fixed-header words present in every closures.
290 This includes the info pointer---always the first word---and any
291 other fixed info. Because this name occurs so often, @_FHS@ is used as
294 \item[@SET_FIXED_HDR(closure, infolbl, costcentre)@:] Initialize the
295 fixed-header part of @closure@, putting @infolbl@ into the first word
296 (where the info-table pointer normally lives). Note that @infolbl@
297 should be the name of the appropriate info-table. If we are profiling
298 on a sequential machine, then the cost centre will be placed in the
299 second word of the fixed header.
301 \item[@<closure-kind>_VHS@:]
302 This is the number of words in the variable part of the header. This
303 includes the @size@ and/or @ptr@ fields if required for this closure
304 type, and any words which are reserved for garbage collection.
306 @SPEC@, @CONST@, @CHARLIKE@, @INTLIKE@, @BH@ and @IND@ do
307 not have variable header parts, hence no @<closure-kind>_VHS@ macro is
308 defined for any of these closure types.
310 \item[@SET_<closure-kind>_HDR(closure,infolbl,costcentre,size,no-of-ptrs)@:]
311 This is used to initialize the header of a \tr{<closure-kind>} closure.
312 The fixed header is set by using @SET_FIXED_HDR(closure,infolbl,costcentre)@
315 The variable part of the header, if present, uses the
316 @size@/@ptrs@ fields. The @size@ should {\em include} any slop
317 words in the closure. Any field that is not used may be junk.
319 The fields actually used depend on the type of the closure (other
322 %partain:\begin{center}
323 \begin{tabular}{|l|l|} \hline
324 Closure & Fields Used \\ \hline
326 \tr{SPEC} & size/nonptrs fields ignored \\
327 \tr{GEN} & both fields also ignored \\
328 \tr{DYN} & both fields used \\
329 \tr{TUPLE} & size used (ptrs = size - \tr{TUPLE_VHS}) \\
330 \tr{DATA} & size used (ptrs = 0) \\\hline
332 %partain:\end{center}
334 \item[@<closure-kind>_HS@:]
335 Total number of words in the header:
337 \pl{TOT_HDR = FIXED_HDR + VAR_HDR}.
339 \item[@<closure-kind>_CLOSURE_SIZE(closure)@:]
340 Returns the size of a closure of this kind. This includes any @VAR_HDR@
341 words and slop---but excludes the @FIXED_HDR@ words.
343 \item[@<closure-kind>_CLOSURE_NoPTRS(closure)@:]
344 Returns the number of closure pointer words in a closure of this kind.
346 \item[@<closure-kind>_CLOSURE_NoNONPTRS(closure)@:]
347 Returns the number of useful non-pointer words (including slop) in a
348 closure of this kind. These follow the pointer words in the closure;
349 \pl{NoNONPTRS = SIZE - NoPTRS - VAR_HDR}.
351 \item[@<closure-kind>_CLOSURE_PTR(closure,nth)@:]
352 Returns the $n$th closure pointer in the closure (starting at 1).
354 If a loop needs to process all the pointers and non-pointers in a closure then
355 this macro should be avoided. Instead, have a pointer run over the closure;
356 for example (from @StgUpdate.lhc@):
358 { P_ p = PapClosure + FIXED_HS + DYN_VHS;
359 I_ NPtrWords = DYN_CLOSURE_NoPTRS(Node);
360 I_ NNonPtrWords = DYN_CLOSURE_NoNONPTRS(Node);
361 for (i=0; i<NPtrWords; i++) SpA[AREL(i)] = *(p++);
362 for (i=0; i<NNonPtrWords; i++) SpB[BREL(i)] = *(p++);
369 %************************************************************************
371 \subsection[SMinterface.h-implementation]{Interface implementation}
373 %************************************************************************
375 This section details the implementation of the storage manager
378 NB: Heap objects specific to parallel implementations are not defined
379 here, but in \tr{Parallel.lh} instead.
381 %************************************************************************
383 \subsubsection[common-to-all-closures]{Bits common to all closures (esp. @FIXED_HS@)}
385 %************************************************************************
387 The maximum number of pointers in a generic closure (@GEN@, @DYN@,
388 @TUPLE@, @DATA@) is defined here.
390 Multi-slurp protection:
396 Macros to make rep-table names:
397 If you change either of these, change .../nativeGen/StixInfo.lhs
401 #define MK_REP_LBL(n,s,p) CAT6(n,_,s,_,p,_rtbl)
402 #define MK_REP_REF(n,s,p) CAT6(n,_,s,_,p,_rtbl)
406 At the start of a closure is a fixed header. The info-pointer is
407 normally the first word of a closure, in the fixed header. Following
408 this we may have any of (but occuring in this order): parallel words
409 (currently a global address); profiling words (currently a cost
410 centre). It is possible to change the ordering of fixed header
411 components by changing the @_HDR_POSN@ macros in the appropriate
412 files, and the @SET_FIXED_HDR@/@SET_STATIC_FIXED_HDR@ macros below.
414 The @FIXED_HS@, @SET_FIXED_HDR@ macros and the components
415 which are used to define them must all be defined consistently.
419 #define FIXED_HS (INFO_FIXED_HDR + PAR_FIXED_HDR + PROF_FIXED_HDR + AGE_FIXED_HDR)
421 /* NB: this *defines* the intended order for the pieces of
422 the fixed header. Care should be taken to ensure that this
423 is followed below and in the component headers.
426 #define _FHS FIXED_HS /* shorthand */
428 #define SET_FIXED_HDR(closure,infolbl,costcentre) \
429 SET_INFO_PTR(closure,infolbl); \
430 SET_GRAN_HDR(closure,ThisPE); \
431 SET_PAR_HDR(closure,LOCAL_GA); \
432 SET_PROF_HDR(closure,costcentre); \
435 #define UPD_FIXED_HDR(closure,infolbl,costcentre) \
436 SET_INFO_PTR(closure,infolbl); \
437 SET_PROF_HDR(closure,costcentre)
438 /* fiddling SET_PAR_HDR would be a bug (says Patrick) */
439 /* no SET_AGE_HDR for inplace updates */
441 /* These items are comma-separated */
443 #define SET_STATIC_FIXED_HDR(closure,infolbl,cc_ident) \
444 SET_STATIC_INFO_PTR(infolbl) \
445 SET_STATIC_PROCS(closure) \
446 SET_STATIC_PAR_HDR(closure) \
447 SET_STATIC_PROF_HDR(cc_ident) \
452 We define @MIN_UPD_SIZE@ to be the minimum size for updatable
453 closures. This must be at least 2, to allow for @(:)@ cells and
454 indirections on the ``mutables'' list. This is defined in
455 \tr{GhcConstants.lh}.
457 All updates are performed on closures of this size so @BH@ and @IND@
458 closures all have this size.
460 Finally we define the number of words that the storage-manager needs
461 to reserve in the variable header for mutable closures:
464 #if defined(GCap) || defined(GCgn)
465 # define GC_MUT_REQUIRED
466 # define GC_MUT_RESERVED_WORDS 1
467 # define MUT_NOT_LINKED 1 /* Assuming 1 is not a valid pointer */
468 # define MUT_LINK(closure) (((P_)(closure))[FIXED_HS])
469 # define SET_MUT_RESERVED_WORDS(closure) MUT_LINK(closure) = MUT_NOT_LINKED
470 # define SET_STATIC_MUT_RESERVED_WORDS , (W_) MUT_NOT_LINKED
472 # define GC_MUT_RESERVED_WORDS 0
473 # define SET_STATIC_MUT_RESERVED_WORDS
478 %************************************************************************
480 \subsubsection[SPEC-closures]{@SPEC@ (specialized) closure macros}
482 %************************************************************************
484 @SPEC@ closures have no variable header size---it is always 0.
485 @SPEC_VHS@ is left undefined, so that if anyone tries to use it,
486 they will hear about it soon enough (WDP 95/05).
489 #define SPEC_HS (FIXED_HS)
491 #define SPEC_CLOSURE_PTR(closure, no) (((P_)(closure))[SPEC_HS + (no) - 1])
492 #define SPEC_CLOSURE_SIZE(closure) ((W_)INFO_SIZE(INFO_PTR(closure)))
493 #define SPEC_CLOSURE_NoPTRS(closure) ((W_)INFO_NoPTRS(INFO_PTR(closure)))
494 #define SPEC_CLOSURE_NoNONPTRS(closure) (SPEC_CLOSURE_SIZE(closure)-SPEC_CLOSURE_NoPTRS(closure)/*-SPEC_VHS*/)
496 #define SET_SPEC_HDR(closure,infolbl,cc,size,ptrs) \
497 SET_FIXED_HDR(closure,infolbl,cc)
500 %************************************************************************
502 \subsubsection[MallocPtr-closures]{@MallocPtr@ closure macros}
504 %************************************************************************
506 Here's what a MallocPtr looks like:
510 +----------+----------+------+------+
511 | Info Ptr | Forward | Data | List |
512 +----------+----------+------+------+
515 The list is a pointer to the next MallocPtr in the list of all
516 MallocPtrs. Note that it is essential that the garbage collector {\em
517 not\/} follow this link but that the link must get updated with the
520 The optional @Forward@ field is used by copying collectors to insert
521 the forwarding pointer into. (If we overwrite the @Data@ part, we
522 don't know which MallocPtr has just died; if we overwrite the @List@ part,
523 we can't traverse the list of all MallocPtrs.)
528 # if defined(_INFO_COPYING)
529 # define MallocPtr_VHS 1
531 # define MallocPtr_VHS 0
534 # define MallocPtr_HS (FIXED_HS + MallocPtr_VHS)
535 # define MallocPtr_SIZE (MallocPtr_VHS + 2)
537 # define MallocPtr_CLOSURE_NoPTRS(closure) 0
538 # define MallocPtr_CLOSURE_DATA(closure) (((StgMallocPtr *)(closure))[MallocPtr_HS + 0])
539 # define MallocPtr_CLOSURE_LINK(closure) (((StgPtrPtr) (closure))[MallocPtr_HS + 1])
541 # define SET_MallocPtr_HDR(closure,infolbl,cc,size,ptrs) \
542 SET_FIXED_HDR(closure,infolbl,cc)
545 And to check that a Malloc ptr closure is valid
548 EXTDATA_RO(MallocPtr_info);
552 # define CHECK_MallocPtr_CLOSURE( closure ) \
554 CHECK_MallocPtr_InfoTable( closure ); \
557 # define CHECK_MallocPtr_InfoTable( closure ) \
558 ASSERT( (*((PP_)(closure))) == MallocPtr_info )
560 extern void Validate_MallocPtrList( P_ MPlist );
561 # define VALIDATE_MallocPtrList( mplist ) Validate_MallocPtrList( mplist )
565 # define CHECK_MallocPtr_CLOSURE( closure ) /* nothing */
566 # define VALIDATE_MallocPtrList( mplist ) /* nothing */
572 %************************************************************************
574 \subsubsection[SP-table-closures]{@SPTable@ Stable Pointer Table closure macros}
576 %************************************************************************
579 A stable pointer is a name for a Haskell object which can be passed to
580 the external world. It is ``stable'' in the sense that the name does
581 not change when the Haskell garbage collector runs---in contrast to
582 the address of the object which may well change.
584 The stable pointer type is parameterized by the type of the thing
591 A stable pointer is represented by an index into the (unique,
592 heap-allocated) @StablePointerTable@. The Haskell garbage collector
593 treats the @StablePointerTable@ as a source of roots for GC.
595 In order to provide efficient access to stable pointers and to be able
596 to cope with any number of stable pointers ($0 \ldots 100000$), the
597 table of stable pointers is an array stored on the heap and can grow
598 when it overflows. (Since we cannot compact the table by moving
599 stable pointers about, it seems unlikely that a half-empty table can
600 be reduced in size---this could be fixed if neccessary by using a
601 hash table of some sort.)
603 In general a stable pointer table closure looks like this:
606 <------------header--------------->
607 +------+------------+------+-------+---+---+---+-----+-----+--+--+--+----+
608 | Info | GCReserved | Size | NPtrs |SP0|SP1|...|SPn-1| Top |s0|s1|..|sn-1|
609 +------+------------+------+-------+---+---+---+-----+-----+--+--+--+----+
615 \item[@Size@:] number of words excluding fixed header ($= @DYN_VHS@ + @NPtrs@ + 1 + @NPtrs@$)
617 \item[@NPtrs@:] number of (stable) pointers.
619 \item[@SPi@:] ``unstable'' pointer to a closure. This is the pointer
620 that gets updated when the garbage collector moves an object we have a
621 stable pointer to. If the pointer is not in use, it points to a
624 \item[@si@:] entry in a stack of unused pointers. Entries in
625 use will contain a number in the range $0\ldots n-1$.
627 \item[@Top@] is the index of the first element above the top of the stack.
631 For example, with $n = 4$ and pointers @0@ and @3@ in use (pointing to
632 @p1@ and @p2@ respectively), the table might look like this:
635 +------+----+---+----+---+---+----+---+---+---+---+---+
636 | Info | 11 | 4 | p1 | x | x | p2 | 2 | 2 | 1 | ? | ? |
637 +------+----+---+----+---+---+----+---+---+---+---+---+
641 From the above description, it should be clear that this is just a
642 special case of a @DYN@ closure. However, a few macros to access the
643 various fields would be jolly useful.
645 Nota Bene: one might think that since the table is mutable, we'd need
646 to treat it a bit more like a @MUTUPLE@. This isn't necessary because
647 we treat the stable pointer table as a root.
654 # define SPT_SIZE(closure) DYN_CLOSURE_SIZE(closure)
655 # define SPT_NoPTRS(closure) DYN_CLOSURE_NoPTRS(closure)
656 # define SPT_TOP(closure) (((I_ *) closure)[DYN_HS + SPT_NoPTRS(closure)])
657 # define SPT_SPTR(closure,index) (((PP_) closure)[DYN_HS + index])
658 # define SPT_FREE(closure,index) (((I_ *) closure)[DYN_HS + SPT_NoPTRS(closure) + 1 + index])
661 And to implement the stack:
664 # define SPT_FULL(closure) (SPT_TOP(closure) == SPT_NoPTRS(closure))
665 # define SPT_EMPTY(closure) (SPT_TOP(closure) == 0)
667 # define SPT_PUSH(closure,free) SPT_FREE(closure,SPT_TOP(closure)++) = free
668 # define SPT_POP(closure) SPT_FREE(closure,--SPT_TOP(closure))
671 And to check that an SPT_Closure is what it's supposed to be, we check
672 that the size and number of pointers match up and we check that the
673 free list and sptr areas are consistent.
675 Note that we cannot always check the info table since we might be
676 halfway through garbage collection when we call these (eg in
682 # define CHECK_SPT_CLOSURE( closure ) \
684 CHECK_SPT_InfoTable( closure ); \
685 CHECK_SPT_Size( closure ); \
686 CHECK_SPT_Contents( closure ); \
689 EXTDATA_RO(StablePointerTable_info);
690 EXTDATA_RO(EmptyStablePointerTable_static_info);
691 EXTDATA(EmptySPTable_closure);
692 extern int ValidateSPTable PROTO(( P_ SPTable ));
694 # define CHECK_SPT_InfoTable( closure ) \
695 ASSERT( (*((PP_) (closure)) == EmptyStablePointerTable_static_info && (closure == EmptySPTable_closure) ) || \
696 (*((PP_) (closure)) == StablePointerTable_info) )
698 # define CHECK_SPT_Size( closure ) \
699 ASSERT( SPT_SIZE( closure ) == DYN_VHS + 2 * SPT_NoPTRS( closure ) + 1 )
701 # define CHECK_SPT_Contents( closure ) \
702 ASSERT( ValidateSPTable( closure ) == 0 )
706 # define CHECK_SPT_InfoTable( closure ) /* nothing */
707 # define CHECK_SPT_Contents( closure ) /* nothing */
708 # define CHECK_SPT_Size( closure ) /* nothing */
709 # define CHECK_SPT_CLOSURE( closure ) /* nothing */
715 %************************************************************************
717 \subsubsection[GEN-closures]{@GEN@ (generic) closure macros}
719 %************************************************************************
723 #define GEN_HS (FIXED_HS + GEN_VHS)
725 #define GEN_N_VHS GEN_VHS
726 #define GEN_N_HS GEN_HS
728 #define GEN_S_VHS GEN_VHS
729 #define GEN_S_HS GEN_HS
731 #define GEN_U_VHS GEN_VHS
732 #define GEN_U_HS GEN_HS
734 #define GEN_CLOSURE_SIZE(closure) GEN_INFO_SIZE(INFO_PTR(closure))
735 #define GEN_CLOSURE_NoPTRS(closure) GEN_INFO_NoPTRS(INFO_PTR(closure))
737 #define GEN_CLOSURE_NoNONPTRS(closure) (GEN_CLOSURE_SIZE(closure) - GEN_CLOSURE_NoPTRS(closure) - GEN_VHS)
738 #define GEN_CLOSURE_PTR(closure, no) (((P_)(closure))[GEN_HS + (no) - 1])
740 #define SET_GEN_HDR(closure,infolbl,cc,size,ptrs) SET_FIXED_HDR(closure,infolbl,cc)
743 %************************************************************************
745 \subsubsection[DYN-closures]{@DYN@ (dynamic) closure macros}
747 %************************************************************************
749 For dynamic closures (with both pointers and data stored within the closure).
753 #define DYN_HS (FIXED_HS + DYN_VHS)
755 #define DYN_CLOSURE_SIZE(closure) (((P_)(closure))[FIXED_HS])
756 #define DYN_CLOSURE_NoPTRS(closure) (((P_)(closure))[FIXED_HS + 1])
758 #define DYN_CLOSURE_NoNONPTRS(closure) (DYN_CLOSURE_SIZE(closure) - DYN_CLOSURE_NoPTRS(closure) - DYN_VHS)
759 #define DYN_CLOSURE_PTR(closure, no) (((P_)(closure))[DYN_HS + (no) - 1])
761 #define SET_DYN_HDR(closure,infolbl,cc,size,ptrs) \
762 { SET_FIXED_HDR(closure,infolbl,cc); \
763 DYN_CLOSURE_NoPTRS(closure) = (W_)(ptrs); \
764 DYN_CLOSURE_SIZE(closure) = (W_)(size); }
767 %************************************************************************
769 \subsubsection[TUPLE-closures]{@TUPLE@ (big purely-pointer) closure macros}
771 %************************************************************************
773 For tuple closures (which contain only pointers after the variable header).
777 #define TUPLE_HS (FIXED_HS + TUPLE_VHS)
779 #define TUPLE_CLOSURE_SIZE(closure) (((P_)(closure))[FIXED_HS])
781 #define TUPLE_CLOSURE_NoPTRS(closure) (TUPLE_CLOSURE_SIZE(closure) - TUPLE_VHS)
782 #define TUPLE_CLOSURE_NoNONPTRS(closure) 0L
783 #define TUPLE_CLOSURE_PTR(closure, no) (((P_)(closure))[TUPLE_HS + (no) - 1])
785 #define SET_TUPLE_HDR(closure,infolbl,cc,size,ptrs) \
786 { SET_FIXED_HDR(closure,infolbl,cc); \
787 TUPLE_CLOSURE_SIZE(closure) = (W_)(size); }
790 %************************************************************************
792 \subsubsection[DATA-closures]{@DATA@ (big purely non-pointer) closure macros}
794 %************************************************************************
796 For data closures (which contain only raw data (no pointers) after the
801 #define DATA_HS (FIXED_HS + DATA_VHS)
803 #define DATA_CLOSURE_SIZE(closure) (((P_)(closure))[FIXED_HS])
805 #define DATA_CLOSURE_NoPTRS(closure) ((I_)0)
806 #define DATA_CLOSURE_NoNONPTRS(closure) (DATA_CLOSURE_SIZE(closure) - DATA_VHS)
808 #define SET_DATA_HDR(closure,infolbl,cc,size,ptrs/*==0*/) \
809 { SET_FIXED_HDR(closure,infolbl,cc); \
810 DATA_CLOSURE_SIZE(closure) = (W_)(size); }
814 %************************************************************************
816 \subsubsection[MUTUPLE-closures]{@MUTUPLE@ (mutable pointer) closure macros}
818 %************************************************************************
820 Mutable closures of pointers have to be treated specially for the
821 benefit of generational garbage collection schemes. If the garbage
822 collection scheme does not need to treat them specially
823 @GC_MUT_REQUIRED@ is undefined and the closures are defined
824 identical to @TUPLE@ closures.
828 #if defined(GC_MUT_REQUIRED)
830 # define MUTUPLE_VHS (1 + GC_MUT_RESERVED_WORDS)
831 # define MUTUPLE_HS (FIXED_HS + MUTUPLE_VHS)
833 # define MUTUPLE_CLOSURE_SIZE(closure) (((P_)(closure))[FIXED_HS + GC_MUT_RESERVED_WORDS])
835 # define MUTUPLE_CLOSURE_NoPTRS(closure) (MUTUPLE_CLOSURE_SIZE(closure) - MUTUPLE_VHS)
836 # define MUTUPLE_CLOSURE_NoNONPTRS(closure) 0L
837 # define MUTUPLE_CLOSURE_PTR(closure, no) (((P_)(closure))[MUTUPLE_HS + (no) - 1])
839 # define SET_MUTUPLE_HDR(closure,infolbl,cc,size,ptrs) \
840 { SET_FIXED_HDR(closure,infolbl,cc); \
841 SET_MUT_RESERVED_WORDS(closure); \
842 MUTUPLE_CLOSURE_SIZE(closure) = (W_)(size); }
844 #else /* ! GC_MUT_REQUIRED---define as TUPLE closure */
846 # define MUTUPLE_VHS TUPLE_VHS
847 # define MUTUPLE_HS TUPLE_HS
848 # define MUTUPLE_CLOSURE_SIZE(closure) TUPLE_CLOSURE_SIZE(closure)
849 # define MUTUPLE_CLOSURE_NoPTRS(closure) TUPLE_CLOSURE_NoPTRS(closure)
850 # define MUTUPLE_CLOSURE_NoNONPTRS(closure) TUPLE_CLOSURE_NoNONPTRS(closure)
851 # define MUTUPLE_CLOSURE_PTR(closure, no) TUPLE_CLOSURE_PTR(closure, no)
852 # define SET_MUTUPLE_HDR(closure,infolbl,cc,size,ptrs) \
853 SET_TUPLE_HDR(closure,infolbl,cc,size,ptrs)
858 %************************************************************************
860 \subsubsection[STATIC-closures]{@STATIC@ closure macros}
862 %************************************************************************
864 Static closures are those that are allocated in text/data space at
865 compile time (i.e., not in dynamic heap). The odd-looking macro
866 @SET_STATIC_HDR@ depends on the compiler to cooperate---it must drop
867 in the closure free-variable words and the concluding @};@! Also note
868 that the info-table label is a ``base'' label.
870 @SET_STATIC_HDR@ is for SPEC-layout closures.
874 #define STATIC_HS (FIXED_HS)
876 #define STATIC_CLOSURE_SIZE(closure) (STATIC_INFO_SIZE(INFO_PTR(closure)))
877 #define STATIC_CLOSURE_NoPTRS(closure) (STATIC_INFO_NoPTRS(INFO_PTR(closure)))
878 #define STATIC_CLOSURE_NoNONPTRS(closure) (STATIC_CLOSURE_SIZE(closure)-STATIC_CLOSURE_NoPTRS(closure)-STATIC_VHS)
880 #define SET_STATIC_HDR(closure,infolbl,cc,closure_localness,info_localness_macro) \
881 info_localness_macro(infolbl); \
883 W_ closure[] = {SET_STATIC_FIXED_HDR(&closure[0],infolbl,cc)
886 %************************************************************************
888 \subsubsection[IND-closures]{@IND@ (indirection) closure macros}
890 %************************************************************************
892 Indirections are introduced when closures are updated. They are only
893 built by the update macros and the special @CAF@ entry macro in
896 Indirections also have a fixed size of @IND_CLOSURE_SIZE(closure)@.
898 Both for @CAF@s and for normal nodes in Appel's collector we have to
899 be able to identify and link together lists of indirections which are
900 treated specially by the garbage collector. For this purpose we use
901 the @MUT_LINK@ field.
903 @CAF@s (which look like indirections) need to be linked regardless of
904 whether or not we're doing generational collection, so we don't rely
905 on @MUT_LINK@ being defined.
909 #define IND_HS (FIXED_HS + IND_VHS)
911 #define IND_CLOSURE_SIZE(closure) (MIN_UPD_SIZE)
912 #define IND_CLOSURE_NoPTRS(closure) 1
913 #define IND_CLOSURE_NoNONPTRS(closure) (IND_CLOSURE_SIZE(closure)-IND_CLOSURE_NoPTRS(closure)-IND_VHS)
916 Indirections must store a pointer to the closure which is the target
919 #define IND_CLOSURE_PTR(closure) (((P_)(closure))[IND_HS])
923 #define IND_CLOSURE_LINK(closure) (((P_)(closure))[FIXED_HS])
926 When we are profiling, we occasionally use ``permanent indirections'' to
927 store cost centres associated in some way with PAPs. Don't ask me why.
928 For now, a permanent indirection must have the same shape as a regular
929 indirection. The only difference is that it is, well, permanent. That is
930 to say, it is never short-circuited. (What is the point, anyway?)
932 Presumably, such objects could shrink as they moved into the old generation,
933 but then their header size would change as well (the word that they get to
934 lose is the VHS word of a standard indirection), and I just don't feel up
938 #ifdef USE_COST_CENTRES
940 #define PERM_IND_CLOSURE_PTR(closure,dummy) IND_CLOSURE_PTR(closure)
945 %************************************************************************
947 \subsubsection[BH-closures]{@BH@ (black hole) closure macros}
949 %************************************************************************
951 There are two flavours of black holes; one for updatable closures
952 (size @MIN_UPD_SIZE@) and one for single entry closures (size
953 @MIN_NONUPD_SIZE@). Note that single-entry black holes can never
954 become blocking queues, because that would imply multiple entries
957 Black holes are introduced either on entering a closure or when
958 performing garbage collection (see section
959 \ref{black-hole-overwrite}). They indicate that the pointers within
960 the closure are no longer needed.
962 The compiler will also allocate an updatable black hole on entering a
966 #define BH_HS (FIXED_HS)
969 #define BH_CLOSURE_SIZE(closure) ((W_)INFO_SIZE(INFO_PTR(closure)))
970 #define BH_CLOSURE_NoPTRS(closure) 0L
971 #define BH_CLOSURE_NoNONPTRS(closure) (BH_CLOSURE_SIZE(closure)-BH_CLOSURE_NoPTRS(closure)-BH_VHS)
973 #define SET_BH_HDR(closure,infolbl,cc,size,ptrs) \
974 SET_FIXED_HDR(closure,infolbl,cc)
975 /* most args aren't used, but are required for SET_*_HDR uniformity */
978 %************************************************************************
980 \subsubsection[RBH-closures]{@RBH@ (revertable black hole) closure macros}
982 %************************************************************************
984 There are two kinds of revertable black holes, produced from GEN or
985 SPEC closures, respectively. There's no @SET_RBH_HDR@ macro -- use
986 @TurnIntoRBH@ instead!!
988 Note that the NoPTRS and NoNONPTRS macros refer to the *original* closure.
991 #define SPEC_RBH_VHS (1L)
992 #define SPEC_RBH_HS (FIXED_HS + SPEC_RBH_VHS)
994 #define SPEC_RBH_CLOSURE_PTR(closure, no) (((P_)(closure))[SPEC_RBH_HS + (no) - 1])
995 #define SPEC_RBH_CLOSURE_SIZE(closure) ((W_)INFO_SIZE(REVERT_INFOPTR(INFO_PTR(closure))))
996 #define SPEC_RBH_CLOSURE_NoPTRS(closure) ((W_)INFO_NoPTRS(REVERT_INFOPTR(INFO_PTR(closure))))
997 #define SPEC_RBH_CLOSURE_NoNONPTRS(closure) (SPEC_RBH_CLOSURE_SIZE(closure)-SPEC_RBH_CLOSURE_NoPTRS(closure)/*-SPEC_VHS*/)
999 #define SPEC_RBH_BQ_LOCN (SPEC_RBH_HS)
1000 #define SPEC_RBH_BQ(closure) (((P_)(closure))[SPEC_RBH_BQ_LOCN])
1002 #define GEN_RBH_VHS (1L)
1003 #define GEN_RBH_HS (FIXED_HS + GEN_RBH_VHS)
1005 #define GEN_RBH_CLOSURE_PTR(closure, no) (((P_)(closure))[GEN_RBH_HS + (no) - 1])
1006 #define GEN_RBH_CLOSURE_SIZE(closure) (GEN_INFO_SIZE(REVERT_INFOPTR(INFO_PTR(closure))))
1007 #define GEN_RBH_CLOSURE_NoPTRS(closure) (GEN_INFO_NoPTRS(REVERT_INFOPTR(INFO_PTR(closure))))
1008 #define GEN_RBH_CLOSURE_NoNONPTRS(closure) (GEN_RBH_CLOSURE_SIZE(closure)-GEN_RBH_CLOSURE_NoPTRS(closure)-GEN_VHS)
1010 #define GEN_RBH_BQ_LOCN (GEN_RBH_HS)
1011 #define GEN_RBH_BQ(closure) (((P_)(closure))[GEN_RBH_BQ_LOCN])
1016 %************************************************************************
1018 \subsubsection[CONST-closures]{@CONST@ (nullary data-constructor) closure macros}
1020 %************************************************************************
1022 These are never allocated normally---static closures are used
1023 instead. They arise only as a result of in-place updates which use
1027 #define CONST_HS (FIXED_HS)
1028 #define CONST_VHS (0L)
1030 #define CONST_CLOSURE_SIZE(closure) (0L)
1031 #define CONST_CLOSURE_NoPTRS(closure) (0L)
1032 #define CONST_CLOSURE_NoNONPTRS(closure) (0L)
1035 %************************************************************************
1037 \subsubsection[CHARLIKE-closures]{@CHARLIKE@ closure macros}
1039 %************************************************************************
1041 These are never allocated normally. They are a static array of
1042 closures indexed by literal characters. As with @CONST@ closures,
1043 @CHARLIKE@ closures only arise from in-place updates using
1046 #define CHARLIKE_HS (FIXED_HS)
1047 #define CHARLIKE_VHS (0L)
1049 #define CHARLIKE_CLOSURE_SIZE(closure) (1L)
1050 #define CHARLIKE_CLOSURE_NoPTRS(closure) (0L)
1051 #define CHARLIKE_CLOSURE_NoNONPTRS(closure) (1L)
1053 /* Array of static charlike closures */
1054 extern const W_ CHARLIKE_closures[];
1056 /* Macro to retrieve static charlike closure */
1057 #define CHARLIKE_CLOSURE(the_char) \
1058 (& CHARLIKE_closures[(CHARLIKE_HS+1) * ((W_)(the_char))])
1060 #define CHARLIKE_VALUE(closure) \
1061 (((P_)(closure))[CHARLIKE_HS])
1063 /* INPLACE_UPD_HDR used for inplace updates */
1067 %************************************************************************
1069 \subsubsection[INTLIKE-closures]{@INTLIKE@ closure macros}
1071 %************************************************************************
1073 These may be allocated normally (@SET_INTLIKE_HDR@) or result from
1074 inplace updates (@INPLACE_UPD_HDR@). They may be converted to a static
1075 closure during garbage collection.
1077 Note: the garbage collector (@EVAC_FN(IntLike)@) assumes that this has
1078 the same structure as a @SPEC_1_0@ closure.
1081 #define INTLIKE_HS (FIXED_HS)
1082 #define INTLIKE_VHS (0L)
1084 #define INTLIKE_CLOSURE_SIZE(closure) (1L)
1085 #define INTLIKE_CLOSURE_NoPTRS(closure) (0L)
1086 #define INTLIKE_CLOSURE_NoNONPTRS(closure) (1L)
1088 /* Array of static intlike closures */
1089 extern P_ INTLIKE_closures;
1091 /* Range of static intlike closures MAX_INTLIKE, MIN_INTLIKE is in GhcConstants.lh */
1093 /* Macro to retrieve static intlike closure */
1094 #define INTLIKE_CLOSURE(the_int) \
1095 (INTLIKE_closures + ((INTLIKE_HS+1) * ((I_)(the_int))))
1097 #define INTLIKE_VALUE(closure) \
1098 ((I_) ((P_)(closure))[INTLIKE_HS])
1100 #define SET_INTLIKE_HDR(closure,infolbl,cc,size,ptrs) \
1101 SET_FIXED_HDR(closure,infolbl,cc)
1103 /* INPLACE_UPD_HDR used for inplace updates */
1107 End multi-slurp protection:
1109 #endif /* SMClosures_H */