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