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