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
  66     struct step_ *       to;            // destination step for live objects
  67
  68     bdescr *             large_objects;  // large objects (doubly linked)
  69     unsigned int         n_large_blocks; // no. of blocks used by large objs
  70
  71
  72     // ------------------------------------
  73     // Fields below are used during GC only
  74
  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
  77     // are freed.
  78
  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
  85 #endif
  86
  87     bdescr *     old_blocks;            // bdescr of first from-space block
  88     unsigned int n_old_blocks;          // number of blocks in from-space
  89
  90     bdescr *     todos;                 // blocks waiting to be scavenged
  91     unsigned int n_todos;               // count of above
  92
  93     bdescr *     scavenged_large_objects;  // live large objs after GC (d-link)
  94     unsigned int n_scavenged_large_blocks; // size (not count) of above
  95
  96     bdescr *     bitmap;                // bitmap for compacting collection
  97
  98
  99 } step;
 100
 101
 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)
 108
 109     // stats information
 110     unsigned int collections;
 111     unsigned int failed_promotions;
 112
 113     // temporary use during GC:
 114     bdescr        *saved_mut_list;
 115 } generation;
 116
 117 extern generation * RTS_VAR(generations);
 118
 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;
 124
 125 /* -----------------------------------------------------------------------------
 126    Initialisation / De-initialisation
 127    -------------------------------------------------------------------------- */
 128
 129 extern void initStorage(void);
 130 extern void exitStorage(void);
 131 extern void freeStorage(void);
 132
 133 /* -----------------------------------------------------------------------------
 134    Generic allocation
 135
 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.
 140                                 Always succeeds.
 141
 142    StgPtr allocate(nat n)       Equaivalent to allocateInGen(g0)
 143
 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,
 148                                 unlike allocate().
 149
 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.
 154                                 Always succeeds.
 155
 156                                 NOTE: the GC can't in general handle
 157                                 pinned objects, so allocatePinned()
 158                                 can only be used for ByteArrays at the
 159                                 moment.
 160
 161                                 Don't forget to TICK_ALLOC_XXX(...)
 162                                 after calling allocate or
 163                                 allocatePinned, for the
 164                                 benefit of the ticky-ticky profiler.
 165
 166    rtsBool doYouWantToGC(void)  Returns True if the storage manager is
 167                                 ready to perform a GC, False otherwise.
 168
 169    lnat  allocatedBytes(void)  Returns the number of bytes allocated
 170                                 via allocate() since the last GC.
 171                                 Used in the reporting of statistics.
 172
 173    -------------------------------------------------------------------------- */
 174
 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 );
 180
 181 extern bdescr * RTS_VAR(small_alloc_list);
 182 extern bdescr * RTS_VAR(large_alloc_list);
 183 extern bdescr * RTS_VAR(pinned_object_block);
 184
 185 extern nat RTS_VAR(alloc_blocks);
 186 extern nat RTS_VAR(alloc_blocks_lim);
 187
 188 INLINE_HEADER rtsBool
 189 doYouWantToGC( void )
 190 {
 191   return (alloc_blocks >= alloc_blocks_lim);
 192 }
 193
 194 /* memory allocator for executable memory */
 195 extern void *allocateExec (nat bytes);
 196 extern void freeExec (void *p);
 197
 198 /* for splitting blocks groups in two */
 199 extern bdescr * splitLargeBlock (bdescr *bd, nat blocks);
 200
 201 /* -----------------------------------------------------------------------------
 202    Performing Garbage Collection
 203
 204    GarbageCollect(get_roots)    Performs a garbage collection.
 205                                 'get_roots' is called to find all the
 206                                 roots that the system knows about.
 207
 208
 209    -------------------------------------------------------------------------- */
 210
 211 extern void GarbageCollect(rtsBool force_major_gc);
 212
 213 /* -----------------------------------------------------------------------------
 214    Generational garbage collection support
 215
 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.
 220
 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.
 225
 226    updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.
 227
 228    -------------------------------------------------------------------------- */
 229
 230 /*
 231  * Storage manager mutex
 232  */
 233 #if defined(THREADED_RTS)
 234 extern Mutex sm_mutex;
 235 extern Mutex atomic_modify_mutvar_mutex;
 236 extern SpinLock recordMutableGen_sync;
 237 #endif
 238
 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);
 243 #else
 244 #define ACQUIRE_SM_LOCK
 245 #define RELEASE_SM_LOCK
 246 #define ASSERT_SM_LOCK()
 247 #endif
 248
 249 INLINE_HEADER void
 250 recordMutableGen(StgClosure *p, generation *gen)
 251 {
 252     bdescr *bd;
 253
 254     bd = gen->mut_list;
 255     if (bd->free >= bd->start + BLOCK_SIZE_W) {
 256         bdescr *new_bd;
 257         new_bd = allocBlock();
 258         new_bd->link = bd;
 259         bd = new_bd;
 260         gen->mut_list = bd;
 261     }
 262     *bd->free++ = (StgWord)p;
 263
 264 }
 265
 266 INLINE_HEADER void
 267 recordMutableGenLock(StgClosure *p, generation *gen)
 268 {
 269     ACQUIRE_SM_LOCK;
 270     recordMutableGen(p,gen);
 271     RELEASE_SM_LOCK;
 272 }
 273
 274 extern bdescr *allocBlock_sync(void);
 275
 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().
 279 INLINE_HEADER void
 280 recordMutableGen_GC(StgClosure *p, generation *gen)
 281 {
 282     bdescr *bd;
 283
 284     ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
 285
 286     bd = gen->mut_list;
 287     if (bd->free >= bd->start + BLOCK_SIZE_W) {
 288         bdescr *new_bd;
 289         new_bd = allocBlock_sync();
 290         new_bd->link = bd;
 291         bd = new_bd;
 292         gen->mut_list = bd;
 293     }
 294     *bd->free++ = (StgWord)p;
 295
 296     RELEASE_SPIN_LOCK(&recordMutableGen_sync);
 297 }
 298
 299 INLINE_HEADER void
 300 recordMutable(StgClosure *p)
 301 {
 302     bdescr *bd;
 303     ASSERT(closure_MUTABLE(p));
 304     bd = Bdescr((P_)p);
 305     if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
 306 }
 307
 308 INLINE_HEADER void
 309 recordMutableLock(StgClosure *p)
 310 {
 311     ACQUIRE_SM_LOCK;
 312     recordMutable(p);
 313     RELEASE_SM_LOCK;
 314 }
 315
 316 /* -----------------------------------------------------------------------------
 317    The CAF table - used to let us revert CAFs in GHCi
 318    -------------------------------------------------------------------------- */
 319
 320 /* set to disable CAF garbage collection in GHCi. */
 321 /* (needed when dynamic libraries are used). */
 322 extern rtsBool keepCAFs;
 323
 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    -------------------------------------------------------------------------- */
 330
 331 void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
 332
 333 /* -----------------------------------------------------------------------------
 334    DEBUGGING predicates for pointers
 335
 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
 338
 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.
 342
 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
 347    make sense...
 348    -------------------------------------------------------------------------- */
 349
 350 #define LOOKS_LIKE_INFO_PTR(p) \
 351    (p && LOOKS_LIKE_INFO_PTR_NOT_NULL(p))
 352
 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)
 356
 357 #define LOOKS_LIKE_CLOSURE_PTR(p) \
 358   (LOOKS_LIKE_INFO_PTR((UNTAG_CLOSURE((StgClosure *)(p)))->header.info))
 359
 360 /* -----------------------------------------------------------------------------
 361    Macros for calculating how big a closure will be (used during allocation)
 362    -------------------------------------------------------------------------- */
 363
 364 INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
 365 { return sizeofW(StgPAP) + n_args; }
 366
 367 INLINE_HEADER StgOffset AP_sizeW   ( nat n_args )
 368 { return sizeofW(StgAP) + n_args; }
 369
 370 INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
 371 { return sizeofW(StgAP_STACK) + size; }
 372
 373 INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
 374 { return sizeofW(StgHeader) + p + np; }
 375
 376 INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
 377 { return sizeofW(StgSelector); }
 378
 379 INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
 380 { return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
 381
 382 /* --------------------------------------------------------------------------
 383    Sizes of closures
 384    ------------------------------------------------------------------------*/
 385
 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; }
 390
 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; }
 395
 396 INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
 397 { return AP_STACK_sizeW(x->size); }
 398
 399 INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
 400 { return AP_sizeW(x->n_args); }
 401
 402 INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
 403 { return PAP_sizeW(x->n_args); }
 404
 405 INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
 406 { return sizeofW(StgArrWords) + x->words; }
 407
 408 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
 409 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
 410
 411 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
 412 { return TSO_STRUCT_SIZEW + tso->stack_size; }
 413
 414 INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
 415 { return bco->size; }
 416
 417 INLINE_HEADER nat
 418 closure_sizeW_ (StgClosure *p, StgInfoTable *info)
 419 {
 420     switch (info->type) {
 421     case THUNK_0_1:
 422     case THUNK_1_0:
 423         return sizeofW(StgThunk) + 1;
 424     case FUN_0_1:
 425     case CONSTR_0_1:
 426     case FUN_1_0:
 427     case CONSTR_1_0:
 428         return sizeofW(StgHeader) + 1;
 429     case THUNK_0_2:
 430     case THUNK_1_1:
 431     case THUNK_2_0:
 432         return sizeofW(StgThunk) + 2;
 433     case FUN_0_2:
 434     case CONSTR_0_2:
 435     case FUN_1_1:
 436     case CONSTR_1_1:
 437     case FUN_2_0:
 438     case CONSTR_2_0:
 439         return sizeofW(StgHeader) + 2;
 440     case THUNK:
 441         return thunk_sizeW_fromITBL(info);
 442     case THUNK_SELECTOR:
 443         return THUNK_SELECTOR_sizeW();
 444     case AP_STACK:
 445         return ap_stack_sizeW((StgAP_STACK *)p);
 446     case AP:
 447         return ap_sizeW((StgAP *)p);
 448     case PAP:
 449         return pap_sizeW((StgPAP *)p);
 450     case IND:
 451     case IND_PERM:
 452     case IND_OLDGEN:
 453     case IND_OLDGEN_PERM:
 454         return sizeofW(StgInd);
 455     case ARR_WORDS:
 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);
 462     case TSO:
 463         return tso_sizeW((StgTSO *)p);
 464     case BCO:
 465         return bco_sizeW((StgBCO *)p);
 466     case TVAR_WATCH_QUEUE:
 467         return sizeofW(StgTVarWatchQueue);
 468     case TVAR:
 469         return sizeofW(StgTVar);
 470     case TREC_CHUNK:
 471         return sizeofW(StgTRecChunk);
 472     case TREC_HEADER:
 473         return sizeofW(StgTRecHeader);
 474     case ATOMIC_INVARIANT:
 475         return sizeofW(StgAtomicInvariant);
 476     case INVARIANT_CHECK_QUEUE:
 477         return sizeofW(StgInvariantCheckQueue);
 478     default:
 479         return sizeW_fromITBL(info);
 480     }
 481 }
 482
 483 // The definitive way to find the size, in words, of a heap-allocated closure
 484 INLINE_HEADER nat
 485 closure_sizeW (StgClosure *p)
 486 {
 487     return closure_sizeW_(p, get_itbl(p));
 488 }
 489
 490 /* -----------------------------------------------------------------------------
 491    Sizes of stack frames
 492    -------------------------------------------------------------------------- */
 493
 494 INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
 495 {
 496     StgRetInfoTable *info;
 497
 498     info = get_ret_itbl(frame);
 499     switch (info->i.type) {
 500
 501     case RET_DYN:
 502     {
 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);
 507     }
 508
 509     case RET_FUN:
 510         return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;
 511
 512     case RET_BIG:
 513         return 1 + GET_LARGE_BITMAP(&info->i)->size;
 514
 515     case RET_BCO:
 516         return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);
 517
 518     default:
 519         return 1 + BITMAP_SIZE(info->i.layout.bitmap);
 520     }
 521 }
 522
 523 /* -----------------------------------------------------------------------------
 524    Nursery manipulation
 525    -------------------------------------------------------------------------- */
 526
 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 );
 532
 533 /* -----------------------------------------------------------------------------
 534    Functions from GC.c
 535    -------------------------------------------------------------------------- */
 536
 537 typedef void (*evac_fn)(StgClosure **);
 538
 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 );
 543
 544 /* -----------------------------------------------------------------------------
 545    Stats 'n' DEBUG stuff
 546    -------------------------------------------------------------------------- */
 547
 548 extern ullong RTS_VAR(total_allocated);
 549
 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 );
 555
 556 #if defined(DEBUG)
 557 extern void memInventory(rtsBool show);
 558 extern void checkSanity(void);
 559 extern nat  countBlocks(bdescr *);
 560 extern void checkNurserySanity( step *stp );
 561 #endif
 562
 563 #if defined(DEBUG)
 564 void printMutOnceList(generation *gen);
 565 void printMutableList(generation *gen);
 566 #endif
 567
 568 /* ----------------------------------------------------------------------------
 569    Storage manager internal APIs and globals
 570    ------------------------------------------------------------------------- */
 571
 572 #define END_OF_STATIC_LIST stgCast(StgClosure*,1)
 573
 574 extern void newDynCAF(StgClosure *);
 575
 576 extern void move_TSO(StgTSO *src, StgTSO *dest);
 577 extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);
 578
 579 extern StgWeak    * RTS_VAR(old_weak_ptr_list);
 580 extern StgWeak    * RTS_VAR(weak_ptr_list);
 581 extern StgClosure * RTS_VAR(caf_list);
 582 extern StgClosure * RTS_VAR(revertible_caf_list);
 583 extern StgTSO     * RTS_VAR(resurrected_threads);
 584
 585 #endif /* STORAGE_H */