includes/Storage.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 1998-2004
   4  *
   5  * External Storage Manger Interface
   6  *
   7  * ---------------------------------------------------------------------------*/
   8
   9 #ifndef STORAGE_H
  10 #define STORAGE_H
  11
  12 #include <stddef.h>
  13 #include "OSThreads.h"
  14 #include "SMP.h"
  15
  16 /* -----------------------------------------------------------------------------
  17  * Generational GC
  18  *
  19  * We support an arbitrary number of generations, with an arbitrary number
  20  * of steps per generation.  Notes (in no particular order):
  21  *
  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.
  26  *
  27  *       - the oldest generation has one step.  There's no point in aging
  28  *         objects in the oldest generation.
  29  *
  30  *       - generation 0, step 0 (G0S0) is the allocation area.  It is given
  31  *         a fixed set of blocks during initialisation, and these blocks
  32  *         are never freed.
  33  *
  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.
  39  *
  40  *       - the mutable-list is per-generation (not per-step).  G0 doesn't
  41  *         have one (since every garbage collection collects at least G0).
  42  *
  43  *       - block descriptors contain pointers to both the step and the
  44  *         generation that the block belongs to, for convenience.
  45  *
  46  *       - static objects are stored in per-generation lists.  See GC.c for
  47  *         details of how we collect CAFs in the generational scheme.
  48  *
  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.
  52  *
  53  * ------------------------------------------------------------------------- */
  54
  55 typedef struct step_ {
  56     unsigned int         no;            // step number
  57     int                  is_compacted;  // compact this step? (old gen only)
  58
  59     struct generation_ * gen;           // generation this step belongs to
  60     unsigned int         gen_no;        // generation number (cached)
  61
  62     bdescr *             blocks;        // blocks in this step
  63     unsigned int         n_blocks;      // number of blocks
  64
  65     struct step_ *       to;            // destination step for live objects
  66
  67     bdescr *             large_objects;  // large objects (doubly linked)
  68     unsigned int         n_large_blocks; // no. of blocks used by large objs
  69
  70     // ------------------------------------
  71     // Fields below are used during GC only
  72
  73     // During GC, if we are collecting this step, blocks and n_blocks
  74     // are copied into the following two fields.  After GC, these blocks
  75     // are freed.
  76     bdescr *     old_blocks;            // bdescr of first from-space block
  77     unsigned int n_old_blocks;          // number of blocks in from-space
  78
  79     bdescr *     todos;                 // blocks waiting to be scavenged
  80     unsigned int n_todos;               // count of above
  81
  82 #if defined(THREADED_RTS)
  83     SpinLock     sync_todo;             // lock for todos
  84     SpinLock     sync_large_objects;    // lock for large_objects
  85                                         //    and scavenged_large_objects
  86 #endif
  87
  88     bdescr *     scavenged_large_objects;  // live large objs after GC (d-link)
  89     unsigned int n_scavenged_large_blocks; // size (not count) of above
  90
  91     bdescr *     bitmap;                // bitmap for compacting collection
  92 } step;
  93
  94
  95 typedef struct generation_ {
  96     unsigned int   no;                  // generation number
  97     step *         steps;               // steps
  98     unsigned int   n_steps;             // number of steps
  99     unsigned int   max_blocks;          // max blocks in step 0
 100     bdescr        *mut_list;            // mut objects in this gen (not G0)
 101
 102     // stats information
 103     unsigned int collections;
 104     unsigned int failed_promotions;
 105
 106     // temporary use during GC:
 107     bdescr        *saved_mut_list;
 108 } generation;
 109
 110 extern generation * RTS_VAR(generations);
 111
 112 extern generation * RTS_VAR(g0);
 113 extern step * RTS_VAR(g0s0);
 114 extern generation * RTS_VAR(oldest_gen);
 115
 116 /* -----------------------------------------------------------------------------
 117    Initialisation / De-initialisation
 118    -------------------------------------------------------------------------- */
 119
 120 extern void initStorage(void);
 121 extern void exitStorage(void);
 122 extern void freeStorage(void);
 123
 124 /* -----------------------------------------------------------------------------
 125    Generic allocation
 126
 127    StgPtr allocateInGen(generation *g, nat n)
 128                                 Allocates a chunk of contiguous store
 129                                 n words long in generation g,
 130                                 returning a pointer to the first word.
 131                                 Always succeeds.
 132
 133    StgPtr allocate(nat n)       Equaivalent to allocateInGen(g0)
 134
 135    StgPtr allocateLocal(Capability *cap, nat n)
 136                                 Allocates memory from the nursery in
 137                                 the current Capability.  This can be
 138                                 done without taking a global lock,
 139                                 unlike allocate().
 140
 141    StgPtr allocatePinned(nat n) Allocates a chunk of contiguous store
 142                                 n words long, which is at a fixed
 143                                 address (won't be moved by GC).
 144                                 Returns a pointer to the first word.
 145                                 Always succeeds.
 146
 147                                 NOTE: the GC can't in general handle
 148                                 pinned objects, so allocatePinned()
 149                                 can only be used for ByteArrays at the
 150                                 moment.
 151
 152                                 Don't forget to TICK_ALLOC_XXX(...)
 153                                 after calling allocate or
 154                                 allocatePinned, for the
 155                                 benefit of the ticky-ticky profiler.
 156
 157    rtsBool doYouWantToGC(void)  Returns True if the storage manager is
 158                                 ready to perform a GC, False otherwise.
 159
 160    lnat  allocatedBytes(void)  Returns the number of bytes allocated
 161                                 via allocate() since the last GC.
 162                                 Used in the reporting of statistics.
 163
 164    -------------------------------------------------------------------------- */
 165
 166 extern StgPtr  allocate        ( nat n );
 167 extern StgPtr  allocateInGen   ( generation *g, nat n );
 168 extern StgPtr  allocateLocal   ( Capability *cap, nat n );
 169 extern StgPtr  allocatePinned  ( nat n );
 170 extern lnat    allocatedBytes  ( void );
 171
 172 extern bdescr * RTS_VAR(small_alloc_list);
 173 extern bdescr * RTS_VAR(large_alloc_list);
 174 extern bdescr * RTS_VAR(pinned_object_block);
 175
 176 extern nat RTS_VAR(alloc_blocks);
 177 extern nat RTS_VAR(alloc_blocks_lim);
 178
 179 INLINE_HEADER rtsBool
 180 doYouWantToGC( void )
 181 {
 182   return (alloc_blocks >= alloc_blocks_lim);
 183 }
 184
 185 /* memory allocator for executable memory */
 186 extern void *allocateExec (nat bytes);
 187 extern void freeExec (void *p);
 188
 189 /* -----------------------------------------------------------------------------
 190    Performing Garbage Collection
 191
 192    GarbageCollect(get_roots)    Performs a garbage collection.
 193                                 'get_roots' is called to find all the
 194                                 roots that the system knows about.
 195
 196
 197    -------------------------------------------------------------------------- */
 198
 199 extern void GarbageCollect(rtsBool force_major_gc);
 200
 201 /* -----------------------------------------------------------------------------
 202    Generational garbage collection support
 203
 204    recordMutable(StgPtr p)       Informs the garbage collector that a
 205                                  previously immutable object has
 206                                  become (permanently) mutable.  Used
 207                                  by thawArray and similar.
 208
 209    updateWithIndirection(p1,p2)  Updates the object at p1 with an
 210                                  indirection pointing to p2.  This is
 211                                  normally called for objects in an old
 212                                  generation (>0) when they are updated.
 213
 214    updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.
 215
 216    -------------------------------------------------------------------------- */
 217
 218 /*
 219  * Storage manager mutex
 220  */
 221 #if defined(THREADED_RTS)
 222 extern Mutex sm_mutex;
 223 extern Mutex atomic_modify_mutvar_mutex;
 224 extern SpinLock recordMutableGen_sync;
 225 #endif
 226
 227 #if defined(THREADED_RTS)
 228 #define ACQUIRE_SM_LOCK   ACQUIRE_LOCK(&sm_mutex);
 229 #define RELEASE_SM_LOCK   RELEASE_LOCK(&sm_mutex);
 230 #define ASSERT_SM_LOCK()  ASSERT_LOCK_HELD(&sm_mutex);
 231 #else
 232 #define ACQUIRE_SM_LOCK
 233 #define RELEASE_SM_LOCK
 234 #define ASSERT_SM_LOCK()
 235 #endif
 236
 237 INLINE_HEADER void
 238 recordMutableGen(StgClosure *p, generation *gen)
 239 {
 240     bdescr *bd;
 241
 242     bd = gen->mut_list;
 243     if (bd->free >= bd->start + BLOCK_SIZE_W) {
 244         bdescr *new_bd;
 245         new_bd = allocBlock();
 246         new_bd->link = bd;
 247         bd = new_bd;
 248         gen->mut_list = bd;
 249     }
 250     *bd->free++ = (StgWord)p;
 251
 252 }
 253
 254 INLINE_HEADER void
 255 recordMutableGenLock(StgClosure *p, generation *gen)
 256 {
 257     ACQUIRE_SM_LOCK;
 258     recordMutableGen(p,gen);
 259     RELEASE_SM_LOCK;
 260 }
 261
 262 INLINE_HEADER void
 263 recordMutableGen_GC(StgClosure *p, generation *gen)
 264 {
 265     ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
 266     recordMutableGen(p,gen);
 267     RELEASE_SPIN_LOCK(&recordMutableGen_sync);
 268 }
 269
 270 INLINE_HEADER void
 271 recordMutable(StgClosure *p)
 272 {
 273     bdescr *bd;
 274     ASSERT(closure_MUTABLE(p));
 275     bd = Bdescr((P_)p);
 276     if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
 277 }
 278
 279 INLINE_HEADER void
 280 recordMutableLock(StgClosure *p)
 281 {
 282     ACQUIRE_SM_LOCK;
 283     recordMutable(p);
 284     RELEASE_SM_LOCK;
 285 }
 286
 287 /* -----------------------------------------------------------------------------
 288    The CAF table - used to let us revert CAFs in GHCi
 289    -------------------------------------------------------------------------- */
 290
 291 /* set to disable CAF garbage collection in GHCi. */
 292 /* (needed when dynamic libraries are used). */
 293 extern rtsBool keepCAFs;
 294
 295 /* -----------------------------------------------------------------------------
 296    This is the write barrier for MUT_VARs, a.k.a. IORefs.  A
 297    MUT_VAR_CLEAN object is not on the mutable list; a MUT_VAR_DIRTY
 298    is.  When written to, a MUT_VAR_CLEAN turns into a MUT_VAR_DIRTY
 299    and is put on the mutable list.
 300    -------------------------------------------------------------------------- */
 301
 302 void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
 303
 304 /* -----------------------------------------------------------------------------
 305    DEBUGGING predicates for pointers
 306
 307    LOOKS_LIKE_INFO_PTR(p)    returns False if p is definitely not an info ptr
 308    LOOKS_LIKE_CLOSURE_PTR(p) returns False if p is definitely not a closure ptr
 309
 310    These macros are complete but not sound.  That is, they might
 311    return false positives.  Do not rely on them to distinguish info
 312    pointers from closure pointers, for example.
 313
 314    We don't use address-space predicates these days, for portability
 315    reasons, and the fact that code/data can be scattered about the
 316    address space in a dynamically-linked environment.  Our best option
 317    is to look at the alleged info table and see whether it seems to
 318    make sense...
 319    -------------------------------------------------------------------------- */
 320
 321 #define LOOKS_LIKE_INFO_PTR(p) \
 322    (p && LOOKS_LIKE_INFO_PTR_NOT_NULL(p))
 323
 324 #define LOOKS_LIKE_INFO_PTR_NOT_NULL(p) \
 325    (((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type != INVALID_OBJECT && \
 326     ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type < N_CLOSURE_TYPES)
 327
 328 #define LOOKS_LIKE_CLOSURE_PTR(p) \
 329   (LOOKS_LIKE_INFO_PTR((UNTAG_CLOSURE((StgClosure *)(p)))->header.info))
 330
 331 /* -----------------------------------------------------------------------------
 332    Macros for calculating how big a closure will be (used during allocation)
 333    -------------------------------------------------------------------------- */
 334
 335 INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
 336 { return sizeofW(StgPAP) + n_args; }
 337
 338 INLINE_HEADER StgOffset AP_sizeW   ( nat n_args )
 339 { return sizeofW(StgAP) + n_args; }
 340
 341 INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
 342 { return sizeofW(StgAP_STACK) + size; }
 343
 344 INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
 345 { return sizeofW(StgHeader) + p + np; }
 346
 347 INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
 348 { return sizeofW(StgSelector); }
 349
 350 INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
 351 { return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
 352
 353 /* --------------------------------------------------------------------------
 354    Sizes of closures
 355    ------------------------------------------------------------------------*/
 356
 357 INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl )
 358 { return sizeofW(StgClosure)
 359        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 360        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 361
 362 INLINE_HEADER StgOffset thunk_sizeW_fromITBL( const StgInfoTable* itbl )
 363 { return sizeofW(StgThunk)
 364        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 365        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 366
 367 INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
 368 { return AP_STACK_sizeW(x->size); }
 369
 370 INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
 371 { return AP_sizeW(x->n_args); }
 372
 373 INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
 374 { return PAP_sizeW(x->n_args); }
 375
 376 INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
 377 { return sizeofW(StgArrWords) + x->words; }
 378
 379 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
 380 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
 381
 382 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
 383 { return TSO_STRUCT_SIZEW + tso->stack_size; }
 384
 385 INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
 386 { return bco->size; }
 387
 388 INLINE_HEADER nat
 389 closure_sizeW_ (StgClosure *p, StgInfoTable *info)
 390 {
 391     switch (info->type) {
 392     case THUNK_0_1:
 393     case THUNK_1_0:
 394         return sizeofW(StgThunk) + 1;
 395     case FUN_0_1:
 396     case CONSTR_0_1:
 397     case FUN_1_0:
 398     case CONSTR_1_0:
 399         return sizeofW(StgHeader) + 1;
 400     case THUNK_0_2:
 401     case THUNK_1_1:
 402     case THUNK_2_0:
 403         return sizeofW(StgThunk) + 2;
 404     case FUN_0_2:
 405     case CONSTR_0_2:
 406     case FUN_1_1:
 407     case CONSTR_1_1:
 408     case FUN_2_0:
 409     case CONSTR_2_0:
 410         return sizeofW(StgHeader) + 2;
 411     case THUNK:
 412         return thunk_sizeW_fromITBL(info);
 413     case THUNK_SELECTOR:
 414         return THUNK_SELECTOR_sizeW();
 415     case AP_STACK:
 416         return ap_stack_sizeW((StgAP_STACK *)p);
 417     case AP:
 418         return ap_sizeW((StgAP *)p);
 419     case PAP:
 420         return pap_sizeW((StgPAP *)p);
 421     case IND:
 422     case IND_PERM:
 423     case IND_OLDGEN:
 424     case IND_OLDGEN_PERM:
 425         return sizeofW(StgInd);
 426     case ARR_WORDS:
 427         return arr_words_sizeW((StgArrWords *)p);
 428     case MUT_ARR_PTRS_CLEAN:
 429     case MUT_ARR_PTRS_DIRTY:
 430     case MUT_ARR_PTRS_FROZEN:
 431     case MUT_ARR_PTRS_FROZEN0:
 432         return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
 433     case TSO:
 434         return tso_sizeW((StgTSO *)p);
 435     case BCO:
 436         return bco_sizeW((StgBCO *)p);
 437     case TVAR_WATCH_QUEUE:
 438         return sizeofW(StgTVarWatchQueue);
 439     case TVAR:
 440         return sizeofW(StgTVar);
 441     case TREC_CHUNK:
 442         return sizeofW(StgTRecChunk);
 443     case TREC_HEADER:
 444         return sizeofW(StgTRecHeader);
 445     case ATOMIC_INVARIANT:
 446         return sizeofW(StgAtomicInvariant);
 447     case INVARIANT_CHECK_QUEUE:
 448         return sizeofW(StgInvariantCheckQueue);
 449     default:
 450         return sizeW_fromITBL(info);
 451     }
 452 }
 453
 454 // The definitive way to find the size, in words, of a heap-allocated closure
 455 INLINE_HEADER nat
 456 closure_sizeW (StgClosure *p)
 457 {
 458     return closure_sizeW_(p, get_itbl(p));
 459 }
 460
 461 /* -----------------------------------------------------------------------------
 462    Sizes of stack frames
 463    -------------------------------------------------------------------------- */
 464
 465 INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
 466 {
 467     StgRetInfoTable *info;
 468
 469     info = get_ret_itbl(frame);
 470     switch (info->i.type) {
 471
 472     case RET_DYN:
 473     {
 474         StgRetDyn *dyn = (StgRetDyn *)frame;
 475         return  sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE +
 476             RET_DYN_NONPTR_REGS_SIZE +
 477             RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
 478     }
 479
 480     case RET_FUN:
 481         return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;
 482
 483     case RET_BIG:
 484         return 1 + GET_LARGE_BITMAP(&info->i)->size;
 485
 486     case RET_BCO:
 487         return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);
 488
 489     default:
 490         return 1 + BITMAP_SIZE(info->i.layout.bitmap);
 491     }
 492 }
 493
 494 /* -----------------------------------------------------------------------------
 495    Nursery manipulation
 496    -------------------------------------------------------------------------- */
 497
 498 extern void     allocNurseries       ( void );
 499 extern void     resetNurseries       ( void );
 500 extern void     resizeNurseries      ( nat blocks );
 501 extern void     resizeNurseriesFixed ( nat blocks );
 502 extern lnat     countNurseryBlocks   ( void );
 503
 504 /* -----------------------------------------------------------------------------
 505    Functions from GC.c
 506    -------------------------------------------------------------------------- */
 507
 508 typedef void (*evac_fn)(StgClosure **);
 509
 510 extern void         threadPaused ( Capability *cap, StgTSO * );
 511 extern StgClosure * isAlive      ( StgClosure *p );
 512 extern void         markCAFs     ( evac_fn evac );
 513 extern void         GetRoots     ( evac_fn evac );
 514
 515 /* -----------------------------------------------------------------------------
 516    Stats 'n' DEBUG stuff
 517    -------------------------------------------------------------------------- */
 518
 519 extern ullong RTS_VAR(total_allocated);
 520
 521 extern lnat calcAllocated  ( void );
 522 extern lnat calcLiveBlocks ( void );
 523 extern lnat calcLiveWords  ( void );
 524 extern lnat countOccupied  ( bdescr *bd );
 525 extern lnat calcNeeded     ( void );
 526
 527 #if defined(DEBUG)
 528 extern void memInventory(void);
 529 extern void checkSanity(void);
 530 extern nat  countBlocks(bdescr *);
 531 extern void checkNurserySanity( step *stp );
 532 #endif
 533
 534 #if defined(DEBUG)
 535 void printMutOnceList(generation *gen);
 536 void printMutableList(generation *gen);
 537 #endif
 538
 539 /* ----------------------------------------------------------------------------
 540    Storage manager internal APIs and globals
 541    ------------------------------------------------------------------------- */
 542
 543 #define END_OF_STATIC_LIST stgCast(StgClosure*,1)
 544
 545 extern void newDynCAF(StgClosure *);
 546
 547 extern void move_TSO(StgTSO *src, StgTSO *dest);
 548 extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);
 549
 550 extern StgClosure * RTS_VAR(scavenged_static_objects);
 551 extern StgWeak    * RTS_VAR(old_weak_ptr_list);
 552 extern StgWeak    * RTS_VAR(weak_ptr_list);
 553 extern StgClosure * RTS_VAR(caf_list);
 554 extern StgClosure * RTS_VAR(revertible_caf_list);
 555 extern StgTSO     * RTS_VAR(resurrected_threads);
 556
 557 #endif /* STORAGE_H */