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 /* for splitting blocks groups in two */
 190 extern bdescr * splitLargeBlock (bdescr *bd, nat blocks);
 191
 192 /* -----------------------------------------------------------------------------
 193    Performing Garbage Collection
 194
 195    GarbageCollect(get_roots)    Performs a garbage collection.
 196                                 'get_roots' is called to find all the
 197                                 roots that the system knows about.
 198
 199
 200    -------------------------------------------------------------------------- */
 201
 202 extern void GarbageCollect(rtsBool force_major_gc);
 203
 204 /* -----------------------------------------------------------------------------
 205    Generational garbage collection support
 206
 207    recordMutable(StgPtr p)       Informs the garbage collector that a
 208                                  previously immutable object has
 209                                  become (permanently) mutable.  Used
 210                                  by thawArray and similar.
 211
 212    updateWithIndirection(p1,p2)  Updates the object at p1 with an
 213                                  indirection pointing to p2.  This is
 214                                  normally called for objects in an old
 215                                  generation (>0) when they are updated.
 216
 217    updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.
 218
 219    -------------------------------------------------------------------------- */
 220
 221 /*
 222  * Storage manager mutex
 223  */
 224 #if defined(THREADED_RTS)
 225 extern Mutex sm_mutex;
 226 extern Mutex atomic_modify_mutvar_mutex;
 227 extern SpinLock recordMutableGen_sync;
 228 #endif
 229
 230 #if defined(THREADED_RTS)
 231 #define ACQUIRE_SM_LOCK   ACQUIRE_LOCK(&sm_mutex);
 232 #define RELEASE_SM_LOCK   RELEASE_LOCK(&sm_mutex);
 233 #define ASSERT_SM_LOCK()  ASSERT_LOCK_HELD(&sm_mutex);
 234 #else
 235 #define ACQUIRE_SM_LOCK
 236 #define RELEASE_SM_LOCK
 237 #define ASSERT_SM_LOCK()
 238 #endif
 239
 240 INLINE_HEADER void
 241 recordMutableGen(StgClosure *p, generation *gen)
 242 {
 243     bdescr *bd;
 244
 245     bd = gen->mut_list;
 246     if (bd->free >= bd->start + BLOCK_SIZE_W) {
 247         bdescr *new_bd;
 248         new_bd = allocBlock();
 249         new_bd->link = bd;
 250         bd = new_bd;
 251         gen->mut_list = bd;
 252     }
 253     *bd->free++ = (StgWord)p;
 254
 255 }
 256
 257 INLINE_HEADER void
 258 recordMutableGenLock(StgClosure *p, generation *gen)
 259 {
 260     ACQUIRE_SM_LOCK;
 261     recordMutableGen(p,gen);
 262     RELEASE_SM_LOCK;
 263 }
 264
 265 extern bdescr *allocBlock_sync(void);
 266
 267 // Version of recordMutableGen() for use in parallel GC.  The same as
 268 // recordMutableGen(), except that we surround it with a spinlock and
 269 // call the spinlock version of allocBlock().
 270 INLINE_HEADER void
 271 recordMutableGen_GC(StgClosure *p, generation *gen)
 272 {
 273     bdescr *bd;
 274
 275     ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
 276
 277     bd = gen->mut_list;
 278     if (bd->free >= bd->start + BLOCK_SIZE_W) {
 279         bdescr *new_bd;
 280         new_bd = allocBlock_sync();
 281         new_bd->link = bd;
 282         bd = new_bd;
 283         gen->mut_list = bd;
 284     }
 285     *bd->free++ = (StgWord)p;
 286
 287     RELEASE_SPIN_LOCK(&recordMutableGen_sync);
 288 }
 289
 290 INLINE_HEADER void
 291 recordMutable(StgClosure *p)
 292 {
 293     bdescr *bd;
 294     ASSERT(closure_MUTABLE(p));
 295     bd = Bdescr((P_)p);
 296     if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
 297 }
 298
 299 INLINE_HEADER void
 300 recordMutableLock(StgClosure *p)
 301 {
 302     ACQUIRE_SM_LOCK;
 303     recordMutable(p);
 304     RELEASE_SM_LOCK;
 305 }
 306
 307 /* -----------------------------------------------------------------------------
 308    The CAF table - used to let us revert CAFs in GHCi
 309    -------------------------------------------------------------------------- */
 310
 311 /* set to disable CAF garbage collection in GHCi. */
 312 /* (needed when dynamic libraries are used). */
 313 extern rtsBool keepCAFs;
 314
 315 /* -----------------------------------------------------------------------------
 316    This is the write barrier for MUT_VARs, a.k.a. IORefs.  A
 317    MUT_VAR_CLEAN object is not on the mutable list; a MUT_VAR_DIRTY
 318    is.  When written to, a MUT_VAR_CLEAN turns into a MUT_VAR_DIRTY
 319    and is put on the mutable list.
 320    -------------------------------------------------------------------------- */
 321
 322 void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
 323
 324 /* -----------------------------------------------------------------------------
 325    DEBUGGING predicates for pointers
 326
 327    LOOKS_LIKE_INFO_PTR(p)    returns False if p is definitely not an info ptr
 328    LOOKS_LIKE_CLOSURE_PTR(p) returns False if p is definitely not a closure ptr
 329
 330    These macros are complete but not sound.  That is, they might
 331    return false positives.  Do not rely on them to distinguish info
 332    pointers from closure pointers, for example.
 333
 334    We don't use address-space predicates these days, for portability
 335    reasons, and the fact that code/data can be scattered about the
 336    address space in a dynamically-linked environment.  Our best option
 337    is to look at the alleged info table and see whether it seems to
 338    make sense...
 339    -------------------------------------------------------------------------- */
 340
 341 #define LOOKS_LIKE_INFO_PTR(p) \
 342    (p && LOOKS_LIKE_INFO_PTR_NOT_NULL(p))
 343
 344 #define LOOKS_LIKE_INFO_PTR_NOT_NULL(p) \
 345    (((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type != INVALID_OBJECT && \
 346     ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type < N_CLOSURE_TYPES)
 347
 348 #define LOOKS_LIKE_CLOSURE_PTR(p) \
 349   (LOOKS_LIKE_INFO_PTR((UNTAG_CLOSURE((StgClosure *)(p)))->header.info))
 350
 351 /* -----------------------------------------------------------------------------
 352    Macros for calculating how big a closure will be (used during allocation)
 353    -------------------------------------------------------------------------- */
 354
 355 INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
 356 { return sizeofW(StgPAP) + n_args; }
 357
 358 INLINE_HEADER StgOffset AP_sizeW   ( nat n_args )
 359 { return sizeofW(StgAP) + n_args; }
 360
 361 INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
 362 { return sizeofW(StgAP_STACK) + size; }
 363
 364 INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
 365 { return sizeofW(StgHeader) + p + np; }
 366
 367 INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
 368 { return sizeofW(StgSelector); }
 369
 370 INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
 371 { return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
 372
 373 /* --------------------------------------------------------------------------
 374    Sizes of closures
 375    ------------------------------------------------------------------------*/
 376
 377 INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl )
 378 { return sizeofW(StgClosure)
 379        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 380        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 381
 382 INLINE_HEADER StgOffset thunk_sizeW_fromITBL( const StgInfoTable* itbl )
 383 { return sizeofW(StgThunk)
 384        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 385        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 386
 387 INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
 388 { return AP_STACK_sizeW(x->size); }
 389
 390 INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
 391 { return AP_sizeW(x->n_args); }
 392
 393 INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
 394 { return PAP_sizeW(x->n_args); }
 395
 396 INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
 397 { return sizeofW(StgArrWords) + x->words; }
 398
 399 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
 400 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
 401
 402 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
 403 { return TSO_STRUCT_SIZEW + tso->stack_size; }
 404
 405 INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
 406 { return bco->size; }
 407
 408 INLINE_HEADER nat
 409 closure_sizeW_ (StgClosure *p, StgInfoTable *info)
 410 {
 411     switch (info->type) {
 412     case THUNK_0_1:
 413     case THUNK_1_0:
 414         return sizeofW(StgThunk) + 1;
 415     case FUN_0_1:
 416     case CONSTR_0_1:
 417     case FUN_1_0:
 418     case CONSTR_1_0:
 419         return sizeofW(StgHeader) + 1;
 420     case THUNK_0_2:
 421     case THUNK_1_1:
 422     case THUNK_2_0:
 423         return sizeofW(StgThunk) + 2;
 424     case FUN_0_2:
 425     case CONSTR_0_2:
 426     case FUN_1_1:
 427     case CONSTR_1_1:
 428     case FUN_2_0:
 429     case CONSTR_2_0:
 430         return sizeofW(StgHeader) + 2;
 431     case THUNK:
 432         return thunk_sizeW_fromITBL(info);
 433     case THUNK_SELECTOR:
 434         return THUNK_SELECTOR_sizeW();
 435     case AP_STACK:
 436         return ap_stack_sizeW((StgAP_STACK *)p);
 437     case AP:
 438         return ap_sizeW((StgAP *)p);
 439     case PAP:
 440         return pap_sizeW((StgPAP *)p);
 441     case IND:
 442     case IND_PERM:
 443     case IND_OLDGEN:
 444     case IND_OLDGEN_PERM:
 445         return sizeofW(StgInd);
 446     case ARR_WORDS:
 447         return arr_words_sizeW((StgArrWords *)p);
 448     case MUT_ARR_PTRS_CLEAN:
 449     case MUT_ARR_PTRS_DIRTY:
 450     case MUT_ARR_PTRS_FROZEN:
 451     case MUT_ARR_PTRS_FROZEN0:
 452         return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
 453     case TSO:
 454         return tso_sizeW((StgTSO *)p);
 455     case BCO:
 456         return bco_sizeW((StgBCO *)p);
 457     case TVAR_WATCH_QUEUE:
 458         return sizeofW(StgTVarWatchQueue);
 459     case TVAR:
 460         return sizeofW(StgTVar);
 461     case TREC_CHUNK:
 462         return sizeofW(StgTRecChunk);
 463     case TREC_HEADER:
 464         return sizeofW(StgTRecHeader);
 465     case ATOMIC_INVARIANT:
 466         return sizeofW(StgAtomicInvariant);
 467     case INVARIANT_CHECK_QUEUE:
 468         return sizeofW(StgInvariantCheckQueue);
 469     default:
 470         return sizeW_fromITBL(info);
 471     }
 472 }
 473
 474 // The definitive way to find the size, in words, of a heap-allocated closure
 475 INLINE_HEADER nat
 476 closure_sizeW (StgClosure *p)
 477 {
 478     return closure_sizeW_(p, get_itbl(p));
 479 }
 480
 481 /* -----------------------------------------------------------------------------
 482    Sizes of stack frames
 483    -------------------------------------------------------------------------- */
 484
 485 INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
 486 {
 487     StgRetInfoTable *info;
 488
 489     info = get_ret_itbl(frame);
 490     switch (info->i.type) {
 491
 492     case RET_DYN:
 493     {
 494         StgRetDyn *dyn = (StgRetDyn *)frame;
 495         return  sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE +
 496             RET_DYN_NONPTR_REGS_SIZE +
 497             RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
 498     }
 499
 500     case RET_FUN:
 501         return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;
 502
 503     case RET_BIG:
 504         return 1 + GET_LARGE_BITMAP(&info->i)->size;
 505
 506     case RET_BCO:
 507         return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);
 508
 509     default:
 510         return 1 + BITMAP_SIZE(info->i.layout.bitmap);
 511     }
 512 }
 513
 514 /* -----------------------------------------------------------------------------
 515    Nursery manipulation
 516    -------------------------------------------------------------------------- */
 517
 518 extern void     allocNurseries       ( void );
 519 extern void     resetNurseries       ( void );
 520 extern void     resizeNurseries      ( nat blocks );
 521 extern void     resizeNurseriesFixed ( nat blocks );
 522 extern lnat     countNurseryBlocks   ( void );
 523
 524 /* -----------------------------------------------------------------------------
 525    Functions from GC.c
 526    -------------------------------------------------------------------------- */
 527
 528 typedef void (*evac_fn)(StgClosure **);
 529
 530 extern void         threadPaused ( Capability *cap, StgTSO * );
 531 extern StgClosure * isAlive      ( StgClosure *p );
 532 extern void         markCAFs     ( evac_fn evac );
 533 extern void         GetRoots     ( evac_fn evac );
 534
 535 /* -----------------------------------------------------------------------------
 536    Stats 'n' DEBUG stuff
 537    -------------------------------------------------------------------------- */
 538
 539 extern ullong RTS_VAR(total_allocated);
 540
 541 extern lnat calcAllocated  ( void );
 542 extern lnat calcLiveBlocks ( void );
 543 extern lnat calcLiveWords  ( void );
 544 extern lnat countOccupied  ( bdescr *bd );
 545 extern lnat calcNeeded     ( void );
 546
 547 #if defined(DEBUG)
 548 extern void memInventory(rtsBool show);
 549 extern void checkSanity(void);
 550 extern nat  countBlocks(bdescr *);
 551 extern void checkNurserySanity( step *stp );
 552 #endif
 553
 554 #if defined(DEBUG)
 555 void printMutOnceList(generation *gen);
 556 void printMutableList(generation *gen);
 557 #endif
 558
 559 /* ----------------------------------------------------------------------------
 560    Storage manager internal APIs and globals
 561    ------------------------------------------------------------------------- */
 562
 563 #define END_OF_STATIC_LIST stgCast(StgClosure*,1)
 564
 565 extern void newDynCAF(StgClosure *);
 566
 567 extern void move_TSO(StgTSO *src, StgTSO *dest);
 568 extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);
 569
 570 extern StgClosure * RTS_VAR(scavenged_static_objects);
 571 extern StgWeak    * RTS_VAR(old_weak_ptr_list);
 572 extern StgWeak    * RTS_VAR(weak_ptr_list);
 573 extern StgClosure * RTS_VAR(caf_list);
 574 extern StgClosure * RTS_VAR(revertible_caf_list);
 575 extern StgTSO     * RTS_VAR(resurrected_threads);
 576
 577 #endif /* STORAGE_H */