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