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 StgPtr RTS_VAR(alloc_Hp);
 177 extern StgPtr RTS_VAR(alloc_HpLim);
 178
 179 extern nat RTS_VAR(alloc_blocks);
 180 extern nat RTS_VAR(alloc_blocks_lim);
 181
 182 INLINE_HEADER rtsBool
 183 doYouWantToGC( void )
 184 {
 185   return (alloc_blocks >= alloc_blocks_lim);
 186 }
 187
 188 /* memory allocator for executable memory */
 189 extern void *allocateExec (nat bytes);
 190 extern void freeExec (void *p);
 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 INLINE_HEADER void
 266 recordMutableGen_GC(StgClosure *p, generation *gen)
 267 {
 268     ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
 269     recordMutableGen(p,gen);
 270     RELEASE_SPIN_LOCK(&recordMutableGen_sync);
 271 }
 272
 273 INLINE_HEADER void
 274 recordMutable(StgClosure *p)
 275 {
 276     bdescr *bd;
 277     ASSERT(closure_MUTABLE(p));
 278     bd = Bdescr((P_)p);
 279     if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
 280 }
 281
 282 INLINE_HEADER void
 283 recordMutableLock(StgClosure *p)
 284 {
 285     ACQUIRE_SM_LOCK;
 286     recordMutable(p);
 287     RELEASE_SM_LOCK;
 288 }
 289
 290 /* -----------------------------------------------------------------------------
 291    The CAF table - used to let us revert CAFs in GHCi
 292    -------------------------------------------------------------------------- */
 293
 294 /* set to disable CAF garbage collection in GHCi. */
 295 /* (needed when dynamic libraries are used). */
 296 extern rtsBool keepCAFs;
 297
 298 /* -----------------------------------------------------------------------------
 299    This is the write barrier for MUT_VARs, a.k.a. IORefs.  A
 300    MUT_VAR_CLEAN object is not on the mutable list; a MUT_VAR_DIRTY
 301    is.  When written to, a MUT_VAR_CLEAN turns into a MUT_VAR_DIRTY
 302    and is put on the mutable list.
 303    -------------------------------------------------------------------------- */
 304
 305 void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
 306
 307 /* -----------------------------------------------------------------------------
 308    DEBUGGING predicates for pointers
 309
 310    LOOKS_LIKE_INFO_PTR(p)    returns False if p is definitely not an info ptr
 311    LOOKS_LIKE_CLOSURE_PTR(p) returns False if p is definitely not a closure ptr
 312
 313    These macros are complete but not sound.  That is, they might
 314    return false positives.  Do not rely on them to distinguish info
 315    pointers from closure pointers, for example.
 316
 317    We don't use address-space predicates these days, for portability
 318    reasons, and the fact that code/data can be scattered about the
 319    address space in a dynamically-linked environment.  Our best option
 320    is to look at the alleged info table and see whether it seems to
 321    make sense...
 322    -------------------------------------------------------------------------- */
 323
 324 #define LOOKS_LIKE_INFO_PTR(p) \
 325    (p && LOOKS_LIKE_INFO_PTR_NOT_NULL(p))
 326
 327 #define LOOKS_LIKE_INFO_PTR_NOT_NULL(p) \
 328    (((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type != INVALID_OBJECT && \
 329     ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type < N_CLOSURE_TYPES)
 330
 331 #define LOOKS_LIKE_CLOSURE_PTR(p) \
 332   (LOOKS_LIKE_INFO_PTR((UNTAG_CLOSURE((StgClosure *)(p)))->header.info))
 333
 334 /* -----------------------------------------------------------------------------
 335    Macros for calculating how big a closure will be (used during allocation)
 336    -------------------------------------------------------------------------- */
 337
 338 INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
 339 { return sizeofW(StgPAP) + n_args; }
 340
 341 INLINE_HEADER StgOffset AP_sizeW   ( nat n_args )
 342 { return sizeofW(StgAP) + n_args; }
 343
 344 INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
 345 { return sizeofW(StgAP_STACK) + size; }
 346
 347 INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
 348 { return sizeofW(StgHeader) + p + np; }
 349
 350 INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
 351 { return sizeofW(StgSelector); }
 352
 353 INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
 354 { return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
 355
 356 /* --------------------------------------------------------------------------
 357    Sizes of closures
 358    ------------------------------------------------------------------------*/
 359
 360 INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl )
 361 { return sizeofW(StgClosure)
 362        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 363        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 364
 365 INLINE_HEADER StgOffset thunk_sizeW_fromITBL( const StgInfoTable* itbl )
 366 { return sizeofW(StgThunk)
 367        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 368        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 369
 370 INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
 371 { return AP_STACK_sizeW(x->size); }
 372
 373 INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
 374 { return AP_sizeW(x->n_args); }
 375
 376 INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
 377 { return PAP_sizeW(x->n_args); }
 378
 379 INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
 380 { return sizeofW(StgArrWords) + x->words; }
 381
 382 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
 383 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
 384
 385 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
 386 { return TSO_STRUCT_SIZEW + tso->stack_size; }
 387
 388 INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
 389 { return bco->size; }
 390
 391 INLINE_HEADER nat
 392 closure_sizeW_ (StgClosure *p, StgInfoTable *info)
 393 {
 394     switch (info->type) {
 395     case THUNK_0_1:
 396     case THUNK_1_0:
 397         return sizeofW(StgThunk) + 1;
 398     case FUN_0_1:
 399     case CONSTR_0_1:
 400     case FUN_1_0:
 401     case CONSTR_1_0:
 402         return sizeofW(StgHeader) + 1;
 403     case THUNK_0_2:
 404     case THUNK_1_1:
 405     case THUNK_2_0:
 406         return sizeofW(StgThunk) + 2;
 407     case FUN_0_2:
 408     case CONSTR_0_2:
 409     case FUN_1_1:
 410     case CONSTR_1_1:
 411     case FUN_2_0:
 412     case CONSTR_2_0:
 413         return sizeofW(StgHeader) + 2;
 414     case THUNK:
 415         return thunk_sizeW_fromITBL(info);
 416     case THUNK_SELECTOR:
 417         return THUNK_SELECTOR_sizeW();
 418     case AP_STACK:
 419         return ap_stack_sizeW((StgAP_STACK *)p);
 420     case AP:
 421         return ap_sizeW((StgAP *)p);
 422     case PAP:
 423         return pap_sizeW((StgPAP *)p);
 424     case IND:
 425     case IND_PERM:
 426     case IND_OLDGEN:
 427     case IND_OLDGEN_PERM:
 428         return sizeofW(StgInd);
 429     case ARR_WORDS:
 430         return arr_words_sizeW((StgArrWords *)p);
 431     case MUT_ARR_PTRS_CLEAN:
 432     case MUT_ARR_PTRS_DIRTY:
 433     case MUT_ARR_PTRS_FROZEN:
 434     case MUT_ARR_PTRS_FROZEN0:
 435         return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
 436     case TSO:
 437         return tso_sizeW((StgTSO *)p);
 438     case BCO:
 439         return bco_sizeW((StgBCO *)p);
 440     case TVAR_WATCH_QUEUE:
 441         return sizeofW(StgTVarWatchQueue);
 442     case TVAR:
 443         return sizeofW(StgTVar);
 444     case TREC_CHUNK:
 445         return sizeofW(StgTRecChunk);
 446     case TREC_HEADER:
 447         return sizeofW(StgTRecHeader);
 448     case ATOMIC_INVARIANT:
 449         return sizeofW(StgAtomicInvariant);
 450     case INVARIANT_CHECK_QUEUE:
 451         return sizeofW(StgInvariantCheckQueue);
 452     default:
 453         return sizeW_fromITBL(info);
 454     }
 455 }
 456
 457 // The definitive way to find the size, in words, of a heap-allocated closure
 458 INLINE_HEADER nat
 459 closure_sizeW (StgClosure *p)
 460 {
 461     return closure_sizeW_(p, get_itbl(p));
 462 }
 463
 464 /* -----------------------------------------------------------------------------
 465    Sizes of stack frames
 466    -------------------------------------------------------------------------- */
 467
 468 INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
 469 {
 470     StgRetInfoTable *info;
 471
 472     info = get_ret_itbl(frame);
 473     switch (info->i.type) {
 474
 475     case RET_DYN:
 476     {
 477         StgRetDyn *dyn = (StgRetDyn *)frame;
 478         return  sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE +
 479             RET_DYN_NONPTR_REGS_SIZE +
 480             RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
 481     }
 482
 483     case RET_FUN:
 484         return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;
 485
 486     case RET_BIG:
 487         return 1 + GET_LARGE_BITMAP(&info->i)->size;
 488
 489     case RET_BCO:
 490         return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);
 491
 492     default:
 493         return 1 + BITMAP_SIZE(info->i.layout.bitmap);
 494     }
 495 }
 496
 497 /* -----------------------------------------------------------------------------
 498    Nursery manipulation
 499    -------------------------------------------------------------------------- */
 500
 501 extern void     allocNurseries       ( void );
 502 extern void     resetNurseries       ( void );
 503 extern void     resizeNurseries      ( nat blocks );
 504 extern void     resizeNurseriesFixed ( nat blocks );
 505 extern lnat     countNurseryBlocks   ( void );
 506
 507 /* -----------------------------------------------------------------------------
 508    Functions from GC.c
 509    -------------------------------------------------------------------------- */
 510
 511 typedef void (*evac_fn)(StgClosure **);
 512
 513 extern void         threadPaused ( Capability *cap, StgTSO * );
 514 extern StgClosure * isAlive      ( StgClosure *p );
 515 extern void         markCAFs     ( evac_fn evac );
 516 extern void         GetRoots     ( evac_fn evac );
 517
 518 /* -----------------------------------------------------------------------------
 519    Stats 'n' DEBUG stuff
 520    -------------------------------------------------------------------------- */
 521
 522 extern ullong RTS_VAR(total_allocated);
 523
 524 extern lnat calcAllocated  ( void );
 525 extern lnat calcLive       ( void );
 526 extern lnat calcNeeded     ( void );
 527
 528 #if defined(DEBUG)
 529 extern void memInventory(void);
 530 extern void checkSanity(void);
 531 extern nat  countBlocks(bdescr *);
 532 extern void checkNurserySanity( step *stp );
 533 #endif
 534
 535 #if defined(DEBUG)
 536 void printMutOnceList(generation *gen);
 537 void printMutableList(generation *gen);
 538 #endif
 539
 540 /* ----------------------------------------------------------------------------
 541    Storage manager internal APIs and globals
 542    ------------------------------------------------------------------------- */
 543
 544 #define END_OF_STATIC_LIST stgCast(StgClosure*,1)
 545
 546 extern void newDynCAF(StgClosure *);
 547
 548 extern void move_TSO(StgTSO *src, StgTSO *dest);
 549 extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);
 550
 551 extern StgClosure * RTS_VAR(scavenged_static_objects);
 552 extern StgWeak    * RTS_VAR(old_weak_ptr_list);
 553 extern StgWeak    * RTS_VAR(weak_ptr_list);
 554 extern StgClosure * RTS_VAR(caf_list);
 555 extern StgClosure * RTS_VAR(revertible_caf_list);
 556 extern StgTSO     * RTS_VAR(resurrected_threads);
 557
 558 #endif /* STORAGE_H */