1 /* -----------------------------------------------------------------------------
3 * (c) The GHC Team, 1998-2004
5 * External Storage Manger Interface
7 * ---------------------------------------------------------------------------*/
13 #include "OSThreads.h"
16 /* -----------------------------------------------------------------------------
19 * We support an arbitrary number of generations, with an arbitrary number
20 * of steps per generation. Notes (in no particular order):
22 * - all generations except the oldest should have two steps. This gives
23 * objects a decent chance to age before being promoted, and in
24 * particular will ensure that we don't end up with too many
25 * thunks being updated in older generations.
27 * - the oldest generation has one step. There's no point in aging
28 * objects in the oldest generation.
30 * - generation 0, step 0 (G0S0) is the allocation area. It is given
31 * a fixed set of blocks during initialisation, and these blocks
34 * - during garbage collection, each step which is an evacuation
35 * destination (i.e. all steps except G0S0) is allocated a to-space.
36 * evacuated objects are allocated into the step's to-space until
37 * GC is finished, when the original step's contents may be freed
38 * and replaced by the to-space.
40 * - the mutable-list is per-generation (not per-step). G0 doesn't
41 * have one (since every garbage collection collects at least G0).
43 * - block descriptors contain pointers to both the step and the
44 * generation that the block belongs to, for convenience.
46 * - static objects are stored in per-generation lists. See GC.c for
47 * details of how we collect CAFs in the generational scheme.
49 * - large objects are per-step, and are promoted in the same way
50 * as small objects, except that we may allocate large objects into
51 * generation 1 initially.
53 * ------------------------------------------------------------------------- */
55 typedef struct step_ {
56 unsigned int no; // step number in this generation
57 unsigned int abs_no; // absolute step number
58 int is_compacted; // compact this step? (old gen only)
60 struct generation_ * gen; // generation this step belongs to
61 unsigned int gen_no; // generation number (cached)
63 bdescr * blocks; // blocks in this step
64 unsigned int n_blocks; // number of blocks
66 struct step_ * to; // destination step for live objects
68 bdescr * large_objects; // large objects (doubly linked)
69 unsigned int n_large_blocks; // no. of blocks used by large objs
72 // ------------------------------------
73 // Fields below are used during GC only
75 // During GC, if we are collecting this step, blocks and n_blocks
76 // are copied into the following two fields. After GC, these blocks
79 #if defined(THREADED_RTS)
80 char pad[128]; // make sure the following is
81 // on a separate cache line.
82 SpinLock sync_todo; // lock for todos
83 SpinLock sync_large_objects; // lock for large_objects
84 // and scavenged_large_objects
87 bdescr * old_blocks; // bdescr of first from-space block
88 unsigned int n_old_blocks; // number of blocks in from-space
90 bdescr * todos; // blocks waiting to be scavenged
91 unsigned int n_todos; // count of above
93 bdescr * scavenged_large_objects; // live large objs after GC (d-link)
94 unsigned int n_scavenged_large_blocks; // size (not count) of above
96 bdescr * bitmap; // bitmap for compacting collection
102 typedef struct generation_ {
103 unsigned int no; // generation number
104 step * steps; // steps
105 unsigned int n_steps; // number of steps
106 unsigned int max_blocks; // max blocks in step 0
107 bdescr *mut_list; // mut objects in this gen (not G0)
110 unsigned int collections;
111 unsigned int failed_promotions;
113 // temporary use during GC:
114 bdescr *saved_mut_list;
117 extern generation * RTS_VAR(generations);
119 extern generation * RTS_VAR(g0);
120 extern step * RTS_VAR(g0s0);
121 extern generation * RTS_VAR(oldest_gen);
122 extern step * RTS_VAR(all_steps);
123 extern nat total_steps;
125 /* -----------------------------------------------------------------------------
126 Initialisation / De-initialisation
127 -------------------------------------------------------------------------- */
129 extern void initStorage(void);
130 extern void exitStorage(void);
131 extern void freeStorage(void);
133 /* -----------------------------------------------------------------------------
136 StgPtr allocateInGen(generation *g, nat n)
137 Allocates a chunk of contiguous store
138 n words long in generation g,
139 returning a pointer to the first word.
142 StgPtr allocate(nat n) Equaivalent to allocateInGen(g0)
144 StgPtr allocateLocal(Capability *cap, nat n)
145 Allocates memory from the nursery in
146 the current Capability. This can be
147 done without taking a global lock,
150 StgPtr allocatePinned(nat n) Allocates a chunk of contiguous store
151 n words long, which is at a fixed
152 address (won't be moved by GC).
153 Returns a pointer to the first word.
156 NOTE: the GC can't in general handle
157 pinned objects, so allocatePinned()
158 can only be used for ByteArrays at the
161 Don't forget to TICK_ALLOC_XXX(...)
162 after calling allocate or
163 allocatePinned, for the
164 benefit of the ticky-ticky profiler.
166 rtsBool doYouWantToGC(void) Returns True if the storage manager is
167 ready to perform a GC, False otherwise.
169 lnat allocatedBytes(void) Returns the number of bytes allocated
170 via allocate() since the last GC.
171 Used in the reporting of statistics.
173 -------------------------------------------------------------------------- */
175 extern StgPtr allocate ( nat n );
176 extern StgPtr allocateInGen ( generation *g, nat n );
177 extern StgPtr allocateLocal ( Capability *cap, nat n );
178 extern StgPtr allocatePinned ( nat n );
179 extern lnat allocatedBytes ( void );
181 extern bdescr * RTS_VAR(small_alloc_list);
182 extern bdescr * RTS_VAR(large_alloc_list);
183 extern bdescr * RTS_VAR(pinned_object_block);
185 extern nat RTS_VAR(alloc_blocks);
186 extern nat RTS_VAR(alloc_blocks_lim);
188 INLINE_HEADER rtsBool
189 doYouWantToGC( void )
191 return (alloc_blocks >= alloc_blocks_lim);
194 /* memory allocator for executable memory */
195 extern void *allocateExec (nat bytes);
196 extern void freeExec (void *p);
198 /* for splitting blocks groups in two */
199 extern bdescr * splitLargeBlock (bdescr *bd, nat blocks);
201 /* -----------------------------------------------------------------------------
202 Performing Garbage Collection
204 GarbageCollect(get_roots) Performs a garbage collection.
205 'get_roots' is called to find all the
206 roots that the system knows about.
209 -------------------------------------------------------------------------- */
211 extern void GarbageCollect(rtsBool force_major_gc);
213 /* -----------------------------------------------------------------------------
214 Generational garbage collection support
216 recordMutable(StgPtr p) Informs the garbage collector that a
217 previously immutable object has
218 become (permanently) mutable. Used
219 by thawArray and similar.
221 updateWithIndirection(p1,p2) Updates the object at p1 with an
222 indirection pointing to p2. This is
223 normally called for objects in an old
224 generation (>0) when they are updated.
226 updateWithPermIndirection(p1,p2) As above but uses a permanent indir.
228 -------------------------------------------------------------------------- */
231 * Storage manager mutex
233 #if defined(THREADED_RTS)
234 extern Mutex sm_mutex;
235 extern Mutex atomic_modify_mutvar_mutex;
236 extern SpinLock recordMutableGen_sync;
239 #if defined(THREADED_RTS)
240 #define ACQUIRE_SM_LOCK ACQUIRE_LOCK(&sm_mutex);
241 #define RELEASE_SM_LOCK RELEASE_LOCK(&sm_mutex);
242 #define ASSERT_SM_LOCK() ASSERT_LOCK_HELD(&sm_mutex);
244 #define ACQUIRE_SM_LOCK
245 #define RELEASE_SM_LOCK
246 #define ASSERT_SM_LOCK()
250 recordMutableGen(StgClosure *p, generation *gen)
255 if (bd->free >= bd->start + BLOCK_SIZE_W) {
257 new_bd = allocBlock();
262 *bd->free++ = (StgWord)p;
267 recordMutableGenLock(StgClosure *p, generation *gen)
270 recordMutableGen(p,gen);
274 extern bdescr *allocBlock_sync(void);
276 // Version of recordMutableGen() for use in parallel GC. The same as
277 // recordMutableGen(), except that we surround it with a spinlock and
278 // call the spinlock version of allocBlock().
280 recordMutableGen_GC(StgClosure *p, generation *gen)
284 ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
287 if (bd->free >= bd->start + BLOCK_SIZE_W) {
289 new_bd = allocBlock_sync();
294 *bd->free++ = (StgWord)p;
296 RELEASE_SPIN_LOCK(&recordMutableGen_sync);
300 recordMutable(StgClosure *p)
303 ASSERT(closure_MUTABLE(p));
305 if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
309 recordMutableLock(StgClosure *p)
316 /* -----------------------------------------------------------------------------
317 The CAF table - used to let us revert CAFs in GHCi
318 -------------------------------------------------------------------------- */
320 /* set to disable CAF garbage collection in GHCi. */
321 /* (needed when dynamic libraries are used). */
322 extern rtsBool keepCAFs;
324 /* -----------------------------------------------------------------------------
325 This is the write barrier for MUT_VARs, a.k.a. IORefs. A
326 MUT_VAR_CLEAN object is not on the mutable list; a MUT_VAR_DIRTY
327 is. When written to, a MUT_VAR_CLEAN turns into a MUT_VAR_DIRTY
328 and is put on the mutable list.
329 -------------------------------------------------------------------------- */
331 void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
333 /* -----------------------------------------------------------------------------
334 DEBUGGING predicates for pointers
336 LOOKS_LIKE_INFO_PTR(p) returns False if p is definitely not an info ptr
337 LOOKS_LIKE_CLOSURE_PTR(p) returns False if p is definitely not a closure ptr
339 These macros are complete but not sound. That is, they might
340 return false positives. Do not rely on them to distinguish info
341 pointers from closure pointers, for example.
343 We don't use address-space predicates these days, for portability
344 reasons, and the fact that code/data can be scattered about the
345 address space in a dynamically-linked environment. Our best option
346 is to look at the alleged info table and see whether it seems to
348 -------------------------------------------------------------------------- */
350 #define LOOKS_LIKE_INFO_PTR(p) \
351 (p && LOOKS_LIKE_INFO_PTR_NOT_NULL(p))
353 #define LOOKS_LIKE_INFO_PTR_NOT_NULL(p) \
354 (((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type != INVALID_OBJECT && \
355 ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type < N_CLOSURE_TYPES)
357 #define LOOKS_LIKE_CLOSURE_PTR(p) \
358 (LOOKS_LIKE_INFO_PTR((UNTAG_CLOSURE((StgClosure *)(p)))->header.info))
360 /* -----------------------------------------------------------------------------
361 Macros for calculating how big a closure will be (used during allocation)
362 -------------------------------------------------------------------------- */
364 INLINE_HEADER StgOffset PAP_sizeW ( nat n_args )
365 { return sizeofW(StgPAP) + n_args; }
367 INLINE_HEADER StgOffset AP_sizeW ( nat n_args )
368 { return sizeofW(StgAP) + n_args; }
370 INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
371 { return sizeofW(StgAP_STACK) + size; }
373 INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
374 { return sizeofW(StgHeader) + p + np; }
376 INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
377 { return sizeofW(StgSelector); }
379 INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
380 { return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
382 /* --------------------------------------------------------------------------
384 ------------------------------------------------------------------------*/
386 INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl )
387 { return sizeofW(StgClosure)
388 + sizeofW(StgPtr) * itbl->layout.payload.ptrs
389 + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
391 INLINE_HEADER StgOffset thunk_sizeW_fromITBL( const StgInfoTable* itbl )
392 { return sizeofW(StgThunk)
393 + sizeofW(StgPtr) * itbl->layout.payload.ptrs
394 + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
396 INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
397 { return AP_STACK_sizeW(x->size); }
399 INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
400 { return AP_sizeW(x->n_args); }
402 INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
403 { return PAP_sizeW(x->n_args); }
405 INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
406 { return sizeofW(StgArrWords) + x->words; }
408 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
409 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
411 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
412 { return TSO_STRUCT_SIZEW + tso->stack_size; }
414 INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
415 { return bco->size; }
418 closure_sizeW_ (StgClosure *p, StgInfoTable *info)
420 switch (info->type) {
423 return sizeofW(StgThunk) + 1;
428 return sizeofW(StgHeader) + 1;
432 return sizeofW(StgThunk) + 2;
439 return sizeofW(StgHeader) + 2;
441 return thunk_sizeW_fromITBL(info);
443 return THUNK_SELECTOR_sizeW();
445 return ap_stack_sizeW((StgAP_STACK *)p);
447 return ap_sizeW((StgAP *)p);
449 return pap_sizeW((StgPAP *)p);
453 case IND_OLDGEN_PERM:
454 return sizeofW(StgInd);
456 return arr_words_sizeW((StgArrWords *)p);
457 case MUT_ARR_PTRS_CLEAN:
458 case MUT_ARR_PTRS_DIRTY:
459 case MUT_ARR_PTRS_FROZEN:
460 case MUT_ARR_PTRS_FROZEN0:
461 return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
463 return tso_sizeW((StgTSO *)p);
465 return bco_sizeW((StgBCO *)p);
466 case TVAR_WATCH_QUEUE:
467 return sizeofW(StgTVarWatchQueue);
469 return sizeofW(StgTVar);
471 return sizeofW(StgTRecChunk);
473 return sizeofW(StgTRecHeader);
474 case ATOMIC_INVARIANT:
475 return sizeofW(StgAtomicInvariant);
476 case INVARIANT_CHECK_QUEUE:
477 return sizeofW(StgInvariantCheckQueue);
479 return sizeW_fromITBL(info);
483 // The definitive way to find the size, in words, of a heap-allocated closure
485 closure_sizeW (StgClosure *p)
487 return closure_sizeW_(p, get_itbl(p));
490 /* -----------------------------------------------------------------------------
491 Sizes of stack frames
492 -------------------------------------------------------------------------- */
494 INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
496 StgRetInfoTable *info;
498 info = get_ret_itbl(frame);
499 switch (info->i.type) {
503 StgRetDyn *dyn = (StgRetDyn *)frame;
504 return sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE +
505 RET_DYN_NONPTR_REGS_SIZE +
506 RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
510 return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;
513 return 1 + GET_LARGE_BITMAP(&info->i)->size;
516 return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);
519 return 1 + BITMAP_SIZE(info->i.layout.bitmap);
523 /* -----------------------------------------------------------------------------
525 -------------------------------------------------------------------------- */
527 extern void allocNurseries ( void );
528 extern void resetNurseries ( void );
529 extern void resizeNurseries ( nat blocks );
530 extern void resizeNurseriesFixed ( nat blocks );
531 extern lnat countNurseryBlocks ( void );
533 /* -----------------------------------------------------------------------------
535 -------------------------------------------------------------------------- */
537 typedef void (*evac_fn)(StgClosure **);
539 extern void threadPaused ( Capability *cap, StgTSO * );
540 extern StgClosure * isAlive ( StgClosure *p );
541 extern void markCAFs ( evac_fn evac );
542 extern void GetRoots ( evac_fn evac );
544 /* -----------------------------------------------------------------------------
545 Stats 'n' DEBUG stuff
546 -------------------------------------------------------------------------- */
548 extern ullong RTS_VAR(total_allocated);
550 extern lnat calcAllocated ( void );
551 extern lnat calcLiveBlocks ( void );
552 extern lnat calcLiveWords ( void );
553 extern lnat countOccupied ( bdescr *bd );
554 extern lnat calcNeeded ( void );
557 extern void memInventory(rtsBool show);
558 extern void checkSanity(void);
559 extern nat countBlocks(bdescr *);
560 extern void checkNurserySanity( step *stp );
564 void printMutOnceList(generation *gen);
565 void printMutableList(generation *gen);
568 /* ----------------------------------------------------------------------------
569 Storage manager internal APIs and globals
570 ------------------------------------------------------------------------- */
572 #define END_OF_STATIC_LIST stgCast(StgClosure*,1)
574 extern void newDynCAF(StgClosure *);
576 extern void move_TSO(StgTSO *src, StgTSO *dest);
577 extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);
579 extern StgClosure * RTS_VAR(scavenged_static_objects);
580 extern StgWeak * RTS_VAR(old_weak_ptr_list);
581 extern StgWeak * RTS_VAR(weak_ptr_list);
582 extern StgClosure * RTS_VAR(caf_list);
583 extern StgClosure * RTS_VAR(revertible_caf_list);
584 extern StgTSO * RTS_VAR(resurrected_threads);
586 #endif /* STORAGE_H */