ghc/rts/Storage.h

   1 /* -----------------------------------------------------------------------------
   2  * $Id: Storage.h,v 1.36 2001/08/08 10:50:37 simonmar Exp $
   3  *
   4  * (c) The GHC Team, 1998-1999
   5  *
   6  * External Storage Manger Interface
   7  *
   8  * ---------------------------------------------------------------------------*/
   9
  10 #ifndef STORAGE_H
  11 #define STORAGE_H
  12
  13 #include "Block.h"
  14 #include "BlockAlloc.h"
  15 #include "StoragePriv.h"
  16
  17 /* -----------------------------------------------------------------------------
  18    Initialisation / De-initialisation
  19    -------------------------------------------------------------------------- */
  20
  21 extern void initStorage(void);
  22 extern void exitStorage(void);
  23
  24 /* -----------------------------------------------------------------------------
  25    Generic allocation
  26
  27    StgPtr allocate(nat n)       Allocates a chunk of contiguous store
  28                                 n words long, returning a pointer to
  29                                 the first word.  Always succeeds.
  30
  31    StgPtr allocatePinned(nat n) Allocates a chunk of contiguous store
  32                                 n words long, which is at a fixed
  33                                 address (won't be moved by GC).
  34                                 Returns a pointer to the first word.
  35                                 Always succeeds.
  36
  37                                 NOTE: the GC can't in general handle
  38                                 pinned objects, so allocatePinned()
  39                                 can only be used for ByteArrays at the
  40                                 moment.
  41
  42                                 Don't forget to TICK_ALLOC_XXX(...)
  43                                 after calling allocate or
  44                                 allocatePinned, for the
  45                                 benefit of the ticky-ticky profiler.
  46
  47    rtsBool doYouWantToGC(void)  Returns True if the storage manager is
  48                                 ready to perform a GC, False otherwise.
  49
  50    lnat  allocated_bytes(void)  Returns the number of bytes allocated
  51                                 via allocate() since the last GC.
  52                                 Used in the reoprting of statistics.
  53
  54    SMP: allocate and doYouWantToGC can be used from STG code, they are
  55    surrounded by a mutex.
  56    -------------------------------------------------------------------------- */
  57
  58 extern StgPtr  allocate        ( nat n );
  59 extern StgPtr  allocatePinned  ( nat n );
  60 extern lnat    allocated_bytes ( void );
  61
  62 static inline rtsBool
  63 doYouWantToGC( void )
  64 {
  65   return (alloc_blocks >= alloc_blocks_lim);
  66 }
  67
  68 /* -----------------------------------------------------------------------------
  69    ExtendNursery(hp,hplim)      When hplim is reached, try to grab
  70                                 some more allocation space.  Returns
  71                                 False if the allocation space is
  72                                 exhausted, and the application should
  73                                 call GarbageCollect().
  74   -------------------------------------------------------------------------- */
  75
  76 #define ExtendNursery(hp,hplim)                 \
  77   (CurrentNursery->free = (P_)(hp)+1,           \
  78    CurrentNursery->link == NULL ? rtsFalse :    \
  79    (CurrentNursery = CurrentNursery->link,      \
  80     OpenNursery(hp,hplim),                      \
  81     rtsTrue))
  82
  83 extern void PleaseStopAllocating(void);
  84
  85 /* -----------------------------------------------------------------------------
  86    Performing Garbage Collection
  87
  88    GarbageCollect(get_roots)    Performs a garbage collection.
  89                                 'get_roots' is called to find all the
  90                                 roots that the system knows about.
  91
  92    StgClosure                   Called by get_roots on each root.
  93    MarkRoot(StgClosure *p)      Returns the new location of the root.
  94    -------------------------------------------------------------------------- */
  95
  96 extern void GarbageCollect(void (*get_roots)(evac_fn),rtsBool force_major_gc);
  97
  98 /* -----------------------------------------------------------------------------
  99    Generational garbage collection support
 100
 101    recordMutable(StgPtr p)       Informs the garbage collector that a
 102                                  previously immutable object has
 103                                  become (permanently) mutable.  Used
 104                                  by thawArray and similar.
 105
 106    updateWithIndirection(p1,p2)  Updates the object at p1 with an
 107                                  indirection pointing to p2.  This is
 108                                  normally called for objects in an old
 109                                  generation (>0) when they are updated.
 110
 111    updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.
 112
 113    -------------------------------------------------------------------------- */
 114
 115 /*
 116  * Storage manager mutex
 117  */
 118 #ifdef SMP
 119 extern pthread_mutex_t sm_mutex;
 120 #endif
 121
 122 /* ToDo: shouldn't recordMutable and recordOldToNewPtrs acquire some
 123  * kind of lock in the SMP case?
 124  */
 125 static inline void
 126 recordMutable(StgMutClosure *p)
 127 {
 128   bdescr *bd;
 129
 130 #ifdef SMP
 131   ASSERT(p->header.info == &stg_WHITEHOLE_info || closure_MUTABLE(p));
 132 #else
 133   ASSERT(closure_MUTABLE(p));
 134 #endif
 135
 136   bd = Bdescr((P_)p);
 137   if (bd->gen_no > 0) {
 138     p->mut_link = generations[bd->gen_no].mut_list;
 139     generations[bd->gen_no].mut_list = p;
 140   }
 141 }
 142
 143 static inline void
 144 recordOldToNewPtrs(StgMutClosure *p)
 145 {
 146   bdescr *bd;
 147
 148   bd = Bdescr((P_)p);
 149   if (bd->gen_no > 0) {
 150     p->mut_link = generations[bd->gen_no].mut_once_list;
 151     generations[bd->gen_no].mut_once_list = p;
 152   }
 153 }
 154
 155 #ifndef DEBUG
 156 #define updateWithIndirection(info, p1, p2)                             \
 157   {                                                                     \
 158     bdescr *bd;                                                         \
 159                                                                         \
 160     bd = Bdescr((P_)p1);                                                \
 161     if (bd->gen_no == 0) {                                              \
 162       ((StgInd *)p1)->indirectee = p2;                                  \
 163       SET_INFO(p1,&stg_IND_info);                                       \
 164       TICK_UPD_NEW_IND();                                               \
 165     } else {                                                            \
 166       ((StgIndOldGen *)p1)->indirectee = p2;                            \
 167       if (info != &stg_BLACKHOLE_BQ_info) {                             \
 168         ACQUIRE_LOCK(&sm_mutex);                                        \
 169         ((StgIndOldGen *)p1)->mut_link = generations[bd->gen_no].mut_once_list; \
 170         generations[bd->gen_no].mut_once_list = (StgMutClosure *)p1;                    \
 171         RELEASE_LOCK(&sm_mutex);                                        \
 172       }                                                                 \
 173       SET_INFO(p1,&stg_IND_OLDGEN_info);                                \
 174       TICK_UPD_OLD_IND();                                               \
 175     }                                                                   \
 176   }
 177 #else
 178
 179 /* In the DEBUG case, we also zero out the slop of the old closure,
 180  * so that the sanity checker can tell where the next closure is.
 181  *
 182  * Two important invariants: we should never try to update a closure
 183  * to point to itself, and the closure being updated should not
 184  * already have been updated (the mutable list will get messed up
 185  * otherwise).
 186  */
 187 #define updateWithIndirection(info, p1, p2)                             \
 188   {                                                                     \
 189     bdescr *bd;                                                         \
 190                                                                         \
 191     ASSERT( p1 != p2 && !closure_IND(p1) );                             \
 192     bd = Bdescr((P_)p1);                                                \
 193     if (bd->gen_no == 0) {                                              \
 194       ((StgInd *)p1)->indirectee = p2;                                  \
 195       SET_INFO(p1,&stg_IND_info);                                       \
 196       TICK_UPD_NEW_IND();                                               \
 197     } else {                                                            \
 198       if (info != &stg_BLACKHOLE_BQ_info) {                             \
 199         {                                                               \
 200           StgInfoTable *inf = get_itbl(p1);                             \
 201           nat np = inf->layout.payload.ptrs,                            \
 202               nw = inf->layout.payload.nptrs, i;                        \
 203           if (inf->type != THUNK_SELECTOR) {                            \
 204              for (i = np; i < np + nw; i++) {                           \
 205                 ((StgClosure *)p1)->payload[i] = 0;                     \
 206              }                                                          \
 207           }                                                             \
 208         }                                                               \
 209         ACQUIRE_LOCK(&sm_mutex);                                        \
 210         ((StgIndOldGen *)p1)->mut_link = generations[bd->gen_no].mut_once_list; \
 211         generations[bd->gen_no].mut_once_list = (StgMutClosure *)p1;                    \
 212         RELEASE_LOCK(&sm_mutex);                                        \
 213       }                                                                 \
 214       ((StgIndOldGen *)p1)->indirectee = p2;                            \
 215       SET_INFO(p1,&stg_IND_OLDGEN_info);                                \
 216       TICK_UPD_OLD_IND();                                               \
 217     }                                                                   \
 218   }
 219 #endif
 220
 221 /* Static objects all live in the oldest generation
 222  */
 223 #define updateWithStaticIndirection(info, p1, p2)                       \
 224   {                                                                     \
 225     ASSERT( p1 != p2 && !closure_IND(p1) );                             \
 226     ASSERT( ((StgMutClosure*)p1)->mut_link == NULL );                   \
 227                                                                         \
 228     ACQUIRE_LOCK(&sm_mutex);                                            \
 229     ((StgMutClosure *)p1)->mut_link = oldest_gen->mut_once_list;        \
 230     oldest_gen->mut_once_list = (StgMutClosure *)p1;                    \
 231     RELEASE_LOCK(&sm_mutex);                                            \
 232                                                                         \
 233     ((StgInd *)p1)->indirectee = p2;                                    \
 234     SET_INFO((StgInd *)p1, &stg_IND_STATIC_info);                       \
 235     TICK_UPD_STATIC_IND();                                              \
 236   }
 237
 238 #if defined(TICKY_TICKY) || defined(PROFILING)
 239 static inline void
 240 updateWithPermIndirection(const StgInfoTable *info, StgClosure *p1, StgClosure *p2)
 241 {
 242   bdescr *bd;
 243
 244   ASSERT( p1 != p2 && !closure_IND(p1) );
 245   bd = Bdescr((P_)p1);
 246   if (bd->gen_no == 0) {
 247     ((StgInd *)p1)->indirectee = p2;
 248     SET_INFO(p1,&stg_IND_PERM_info);
 249     TICK_UPD_NEW_PERM_IND(p1);
 250   } else {
 251     ((StgIndOldGen *)p1)->indirectee = p2;
 252     if (info != &stg_BLACKHOLE_BQ_info) {
 253       ACQUIRE_LOCK(&sm_mutex);
 254       ((StgIndOldGen *)p1)->mut_link = generations[bd->gen_no].mut_once_list;
 255       generations[bd->gen_no].mut_once_list = (StgMutClosure *)p1;
 256       RELEASE_LOCK(&sm_mutex);
 257     }
 258     SET_INFO(p1,&stg_IND_OLDGEN_PERM_info);
 259     TICK_UPD_OLD_PERM_IND();
 260   }
 261 }
 262 #endif
 263
 264 /* -----------------------------------------------------------------------------
 265    The CAF table - used to let us revert CAFs
 266    -------------------------------------------------------------------------- */
 267
 268 void revertCAFs( void );
 269
 270 #if defined(DEBUG)
 271 void printMutOnceList(generation *gen);
 272 void printMutableList(generation *gen);
 273 #endif /* DEBUG */
 274
 275 /* --------------------------------------------------------------------------
 276                       Address space layout macros
 277    --------------------------------------------------------------------------
 278
 279    Here are the assumptions GHC makes about address space layout.
 280    Broadly, it thinks there are three sections:
 281
 282      CODE    Read-only.  Contains code and read-only data (such as
 283                 info tables)
 284              Also called "text"
 285
 286      DATA    Read-write data.  Contains static closures (and on some
 287                 architectures, info tables too)
 288
 289      HEAP    Dynamically-allocated closures
 290
 291      USER    None of the above.  The only way USER things arise right
 292              now is when GHCi allocates a constructor info table, which
 293              it does by mallocing them.
 294
 295    Three macros identify these three areas:
 296      IS_CODE(p), IS_DATA(p), HEAP_ALLOCED(p)
 297
 298    HEAP_ALLOCED is called FOR EVERY SINGLE CLOSURE during GC.
 299    It needs to be FAST.
 300
 301    Implementation of HEAP_ALLOCED
 302    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 303    Concerning HEAP, most of the time (certainly under [Static] and [GHCi],
 304    we ensure that the heap is allocated above some fixed address HEAP_BASE
 305    (defined in MBlock.h).  In this case we set TEXT_BEFORE_HEAP, and we
 306    get a nice fast test.
 307
 308    Sometimes we can't be quite sure.  For example in Windows, we can't
 309    fix where our heap address space comes from.  In this case we un-set
 310    TEXT_BEFORE_HEAP. That makes it more expensive to test whether a pointer
 311    comes from the HEAP section, because we need to look at the allocator's
 312    address maps (see HEAP_ALLOCED macro)
 313
 314    Implementation of CODE and DATA
 315    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 316    Concerning CODE and DATA, there are three main regimes:
 317
 318      [Static] Totally      The segments are contiguous, and laid out
 319      statically linked     exactly as above
 320
 321      [GHCi] Static,        GHCi may load new modules, but it knows the
 322      except for GHCi       address map, so for any given address it can
 323                            still tell which section it belongs to
 324
 325      [DLL] OS-supported    Chunks of CODE and DATA may be mixed in
 326      dynamic loading       the address space, and we can't tell how
 327
 328
 329    For the [Static] case, we assume memory is laid out like this
 330    (in order of increasing addresses)
 331
 332        Start of memory
 333            CODE section
 334        TEXT_SECTION_END_MARKER   (usually _etext)
 335            DATA section
 336        DATA_SECTION_END_MARKER   (usually _end)
 337            USER section
 338        HEAP_BASE
 339            HEAP section
 340
 341    For the [GHCi] case, we have to consult GHCi's dynamic linker's
 342    address maps, which is done by macros
 343          is_dynamically_loaded_code_or_rodata_ptr
 344          is_dynamically_loaded_code_or_rwdata_ptr
 345
 346    For the [DLL] case, IS_CODE and IS_DATA are really not usable at all.
 347  */
 348
 349
 350 #undef TEXT_BEFORE_HEAP
 351 #ifndef mingw32_TARGET_OS
 352 #define TEXT_BEFORE_HEAP 1
 353 #endif
 354
 355 extern void* TEXT_SECTION_END_MARKER_DECL;
 356 extern void* DATA_SECTION_END_MARKER_DECL;
 357
 358 /* Take into account code sections in dynamically loaded object files. */
 359 #define IS_CODE_PTR(p) (  ((P_)(p) < (P_)&TEXT_SECTION_END_MARKER) \
 360                        || is_dynamically_loaded_code_or_rodata_ptr((char *)p) )
 361 #define IS_DATA_PTR(p) ( ((P_)(p) >= (P_)&TEXT_SECTION_END_MARKER && \
 362                           (P_)(p) < (P_)&DATA_SECTION_END_MARKER) \
 363                        || is_dynamically_loaded_rwdata_ptr((char *)p) )
 364 #define IS_USER_PTR(p) ( ((P_)(p) >= (P_)&DATA_SECTION_END_MARKER) \
 365                        && is_not_dynamically_loaded_ptr((char *)p) )
 366
 367 /* The HEAP_ALLOCED test below is called FOR EVERY SINGLE CLOSURE
 368  * during GC.  It needs to be FAST.
 369  *
 370  * BEWARE: when we're dynamically loading code (for GHCi), make sure
 371  * that we don't load any code above HEAP_BASE, or this test won't work.
 372  */
 373 #ifdef TEXT_BEFORE_HEAP
 374 # define HEAP_ALLOCED(x)  ((StgPtr)(x) >= (StgPtr)(HEAP_BASE))
 375 #else
 376 extern int is_heap_alloced(const void* x);
 377 # define HEAP_ALLOCED(x)  (is_heap_alloced(x))
 378 #endif
 379
 380
 381 /* --------------------------------------------------------------------------
 382    Macros for distinguishing data pointers from code pointers
 383    --------------------------------------------------------------------------
 384
 385   Specification
 386   ~~~~~~~~~~~~~
 387   The garbage collector needs to make some critical distinctions between pointers.
 388   In particular we need
 389
 390      LOOKS_LIKE_GHC_INFO(p)          p points to an info table
 391
 392   For both of these macros, p is
 393       *either* a pointer to a closure (static or heap allocated)
 394       *or* a return address on the (Haskell) stack
 395
 396   (Return addresses are in fact info-pointers, so that the Haskell stack
 397   looks very like a chunk of heap.)
 398
 399   The garbage collector uses LOOKS_LIKE_GHC_INFO when walking the stack, as it
 400   walks over the "pending arguments" on its way to the next return address.
 401   It is called moderately often, but not as often as HEAP_ALLOCED
 402
 403   ToDo: LOOKS_LIKE_GHC_INFO(p) does not return True when p points to a
 404   constructor info table allocated by GHCi.  We should really rename
 405   LOOKS_LIKE_GHC_INFO to LOOKS_LIKE_GHC_RETURN_INFO.
 406
 407   Implementation
 408   ~~~~~~~~~~~~~~
 409   LOOKS_LIKE_GHC_INFO is more complicated because of the need to distinguish
 410   between static closures and info tables.  It's a known portability problem.
 411   We have three approaches:
 412
 413   Plan A: Address-space partitioning.
 414     Keep info tables in the (single, contiguous) text segment:    IS_CODE_PTR(p)
 415     and static closures in the (single, contiguous) data segment: IS_DATA_PTR(p)
 416
 417   Plan A can fail for two reasons:
 418     * In many environments (eg. dynamic loading),
 419       text and data aren't in a single contiguous range.
 420     * When we compile through vanilla C (no mangling) we sometimes
 421       can't guaranteee to put info tables in the text section.  This
 422       happens eg. on MacOS where the C compiler refuses to put const
 423       data in the text section if it has any code pointers in it
 424       (which info tables do *only* when we're compiling without
 425       TABLES_NEXT_TO_CODE).
 426
 427   Hence, Plan B: (compile-via-C-with-mangling, or native code generation)
 428     Put a zero word before each static closure.
 429     When compiling to native code, or via C-with-mangling, info tables
 430     are laid out "backwards" from the address specified in the info pointer
 431     (the entry code goes forward from the info pointer).  Hence, the word
 432     before the one referenced the info pointer is part of the info table,
 433     and is guaranteed non-zero.
 434
 435     For reasons nobody seems to fully understand, the statically-allocated tables
 436     of INTLIKE and CHARLIKE closures can't have this zero word, so we
 437     have to test separately for them.
 438
 439     Plan B fails altogether for the compile-through-vanilla-C route, because
 440     info tables aren't laid out backwards.
 441
 442
 443   Hence, Plan C: (unregisterised, compile-through-vanilla-C route only)
 444     If we didn't manage to get info tables into the text section, then
 445     we can distinguish between a static closure pointer and an info
 446     pointer as follows:  the first word of an info table is a code pointer,
 447     and therefore in text space, whereas the first word of a closure pointer
 448     is an info pointer, and therefore not.  Shazam!
 449 */
 450
 451
 452 /* When working with Win32 DLLs, static closures are identified by
 453    being prefixed with a zero word. This is needed so that we can
 454    distinguish between pointers to static closures and (reversed!)
 455    info tables.
 456
 457    This 'scheme' breaks down for closure tables such as CHARLIKE,
 458    so we catch these separately.
 459
 460    LOOKS_LIKE_STATIC_CLOSURE()
 461        - discriminates between static closures and info tbls
 462          (needed by LOOKS_LIKE_GHC_INFO() below - [Win32 DLLs only.])
 463    LOOKS_LIKE_STATIC()
 464        - distinguishes between static and heap allocated data.
 465  */
 466 #if defined(ENABLE_WIN32_DLL_SUPPORT)
 467             /* definitely do not enable for mingw DietHEP */
 468 #define LOOKS_LIKE_STATIC(r) (!(HEAP_ALLOCED(r)))
 469
 470 /* Tiresome predicates needed to check for pointers into the closure tables */
 471 #define IS_CHARLIKE_CLOSURE(p) \
 472     ( (P_)(p) >= (P_)stg_CHARLIKE_closure && \
 473       (char*)(p) <= ((char*)stg_CHARLIKE_closure + \
 474                      (MAX_CHARLIKE-MIN_CHARLIKE) * sizeof(StgIntCharlikeClosure)) )
 475 #define IS_INTLIKE_CLOSURE(p) \
 476     ( (P_)(p) >= (P_)stg_INTLIKE_closure && \
 477       (char*)(p) <= ((char*)stg_INTLIKE_closure + \
 478                      (MAX_INTLIKE-MIN_INTLIKE) * sizeof(StgIntCharlikeClosure)) )
 479
 480 #define LOOKS_LIKE_STATIC_CLOSURE(r) (((*(((unsigned long *)(r))-1)) == 0) || IS_CHARLIKE_CLOSURE(r) || IS_INTLIKE_CLOSURE(r))
 481 #else
 482 #define LOOKS_LIKE_STATIC(r) IS_DATA_PTR(r)
 483 #define LOOKS_LIKE_STATIC_CLOSURE(r) IS_DATA_PTR(r)
 484 #endif
 485
 486
 487 /* -----------------------------------------------------------------------------
 488    Macros for distinguishing infotables from closures.
 489
 490    You'd think it'd be easy to tell an info pointer from a closure pointer:
 491    closures live on the heap and infotables are in read only memory.  Right?
 492    Wrong!  Static closures live in read only memory and Hugs allocates
 493    infotables for constructors on the (writable) C heap.
 494    -------------------------------------------------------------------------- */
 495
 496 /* not accurate by any means, but stops the assertions failing... */
 497 /* TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO */
 498 #define IS_HUGS_CONSTR_INFO(info)  IS_USER_PTR(info)
 499
 500 /* LOOKS_LIKE_GHC_INFO is called moderately often during GC, but
 501  * Certainly not as often as HEAP_ALLOCED.
 502  */
 503 #ifdef TEXT_BEFORE_HEAP /* needed for mingw DietHEP */
 504 # define LOOKS_LIKE_GHC_INFO(info) IS_CODE_PTR(info)
 505 #else
 506 # define LOOKS_LIKE_GHC_INFO(info) (!HEAP_ALLOCED(info) \
 507                                     && !LOOKS_LIKE_STATIC_CLOSURE(info))
 508 #endif
 509
 510
 511 /* -----------------------------------------------------------------------------
 512    Macros for calculating how big a closure will be (used during allocation)
 513    -------------------------------------------------------------------------- */
 514
 515 static __inline__ StgOffset AP_sizeW    ( nat n_args )
 516 { return sizeofW(StgAP_UPD) + n_args; }
 517
 518 static __inline__ StgOffset PAP_sizeW   ( nat n_args )
 519 { return sizeofW(StgPAP)    + n_args; }
 520
 521 static __inline__ StgOffset CONSTR_sizeW( nat p, nat np )
 522 { return sizeofW(StgHeader) + p + np; }
 523
 524 static __inline__ StgOffset THUNK_SELECTOR_sizeW ( void )
 525 { return sizeofW(StgHeader) + MIN_UPD_SIZE; }
 526
 527 static __inline__ StgOffset BLACKHOLE_sizeW ( void )
 528 { return sizeofW(StgHeader) + MIN_UPD_SIZE; }
 529
 530 /* --------------------------------------------------------------------------
 531  * Sizes of closures
 532  * ------------------------------------------------------------------------*/
 533
 534 static __inline__ StgOffset sizeW_fromITBL( const StgInfoTable* itbl )
 535 { return sizeofW(StgClosure)
 536        + sizeofW(StgPtr)  * itbl->layout.payload.ptrs
 537        + sizeofW(StgWord) * itbl->layout.payload.nptrs; }
 538
 539 static __inline__ StgOffset pap_sizeW( StgPAP* x )
 540 { return PAP_sizeW(x->n_args); }
 541
 542 static __inline__ StgOffset arr_words_sizeW( StgArrWords* x )
 543 { return sizeofW(StgArrWords) + x->words; }
 544
 545 static __inline__ StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
 546 { return sizeofW(StgMutArrPtrs) + x->ptrs; }
 547
 548 static __inline__ StgWord tso_sizeW ( StgTSO *tso )
 549 { return TSO_STRUCT_SIZEW + tso->stack_size; }
 550
 551 #endif /* STORAGE_H */
 552