includes/rts/storage/GC.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 1998-2004
   4  *
   5  * External Storage Manger Interface
   6  *
   7  * ---------------------------------------------------------------------------*/
   8
   9 #ifndef RTS_STORAGE_GC_H
  10 #define RTS_STORAGE_GC_H
  11
  12 #include <stddef.h>
  13 #include "rts/OSThreads.h"
  14
  15 /* -----------------------------------------------------------------------------
  16  * Generational GC
  17  *
  18  * We support an arbitrary number of generations, with an arbitrary number
  19  * of steps per generation.  Notes (in no particular order):
  20  *
  21  *       - all generations except the oldest should have the same
  22  *         number of steps.  Multiple steps gives objects a decent
  23  *         chance to age before being promoted, and helps ensure that
  24  *         we don't end up with too many thunks being updated in older
  25  *         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  *         normally stay in G0S0.  In parallel execution, each
  33  *         Capability has its own nursery.
  34  *
  35  *       - during garbage collection, each step which is an evacuation
  36  *         destination (i.e. all steps except G0S0) is allocated a to-space.
  37  *         evacuated objects are allocated into the step's to-space until
  38  *         GC is finished, when the original step's contents may be freed
  39  *         and replaced by the to-space.
  40  *
  41  *       - the mutable-list is per-generation (not per-step).  G0 doesn't
  42  *         have one (since every garbage collection collects at least G0).
  43  *
  44  *       - block descriptors contain pointers to both the step and the
  45  *         generation that the block belongs to, for convenience.
  46  *
  47  *       - static objects are stored in per-generation lists.  See GC.c for
  48  *         details of how we collect CAFs in the generational scheme.
  49  *
  50  *       - large objects are per-step, and are promoted in the same way
  51  *         as small objects, except that we may allocate large objects into
  52  *         generation 1 initially.
  53  *
  54  * ------------------------------------------------------------------------- */
  55
  56 typedef struct step_ {
  57     unsigned int         no;            // step number in this generation
  58     unsigned int         abs_no;        // absolute step number
  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_large_objects;    // lock for large_objects
  86                                         //    and scavenged_large_objects
  87 #endif
  88
  89     int          mark;                  // mark (not copy)? (old gen only)
  90     int          compact;               // compact (not sweep)? (old gen only)
  91
  92     bdescr *     old_blocks;            // bdescr of first from-space block
  93     unsigned int n_old_blocks;          // number of blocks in from-space
  94     unsigned int live_estimate;         // for sweeping: estimate of live data
  95
  96     bdescr *     part_blocks;           // partially-full scanned blocks
  97     unsigned int n_part_blocks;         // count of above
  98
  99     bdescr *     scavenged_large_objects;  // live large objs after GC (d-link)
 100     unsigned int n_scavenged_large_blocks; // size (not count) of above
 101
 102     bdescr *     bitmap;                // bitmap for compacting collection
 103
 104     StgTSO *     old_threads;
 105
 106 } step;
 107
 108
 109 typedef struct generation_ {
 110     unsigned int   no;                  // generation number
 111     step *         steps;               // steps
 112     unsigned int   n_steps;             // number of steps
 113     unsigned int   max_blocks;          // max blocks in step 0
 114     bdescr        *mut_list;            // mut objects in this gen (not G0)
 115
 116     // stats information
 117     unsigned int collections;
 118     unsigned int par_collections;
 119     unsigned int failed_promotions;
 120
 121     // temporary use during GC:
 122     bdescr        *saved_mut_list;
 123 } generation;
 124
 125 extern generation * generations;
 126
 127 extern generation * g0;
 128 extern step * g0s0;
 129 extern generation * oldest_gen;
 130 extern step * all_steps;
 131 extern nat total_steps;
 132
 133 /* -----------------------------------------------------------------------------
 134    Generic allocation
 135
 136    StgPtr allocateInGen(generation *g, nat n)
 137                                 Allocates a chunk of contiguous store
 138                                 n words long in generation g,
 139                                 returning a pointer to the first word.
 140                                 Always succeeds.
 141
 142    StgPtr allocate(nat n)       Equaivalent to allocateInGen(g0)
 143
 144    StgPtr allocateLocal(Capability *cap, nat n)
 145                                 Allocates memory from the nursery in
 146                                 the current Capability.  This can be
 147                                 done without taking a global lock,
 148                                 unlike allocate().
 149
 150    StgPtr allocatePinned(nat n) Allocates a chunk of contiguous store
 151                                 n words long, which is at a fixed
 152                                 address (won't be moved by GC).
 153                                 Returns a pointer to the first word.
 154                                 Always succeeds.
 155
 156                                 NOTE: the GC can't in general handle
 157                                 pinned objects, so allocatePinned()
 158                                 can only be used for ByteArrays at the
 159                                 moment.
 160
 161                                 Don't forget to TICK_ALLOC_XXX(...)
 162                                 after calling allocate or
 163                                 allocatePinned, for the
 164                                 benefit of the ticky-ticky profiler.
 165
 166    rtsBool doYouWantToGC(void)  Returns True if the storage manager is
 167                                 ready to perform a GC, False otherwise.
 168
 169    lnat  allocatedBytes(void)  Returns the number of bytes allocated
 170                                 via allocate() since the last GC.
 171                                 Used in the reporting of statistics.
 172
 173    -------------------------------------------------------------------------- */
 174
 175 StgPtr  allocate        ( lnat n );
 176 StgPtr  allocateInGen   ( generation *g, lnat n );
 177 StgPtr  allocateLocal   ( Capability *cap, lnat n );
 178 StgPtr  allocatePinned  ( lnat n );
 179 lnat    allocatedBytes  ( void );
 180
 181 /* memory allocator for executable memory */
 182 void * allocateExec(unsigned int len, void **exec_addr);
 183 void   freeExec (void *p);
 184
 185 /* -----------------------------------------------------------------------------
 186    Performing Garbage Collection
 187    -------------------------------------------------------------------------- */
 188
 189 void performGC(void);
 190 void performMajorGC(void);
 191
 192 /* -----------------------------------------------------------------------------
 193    The CAF table - used to let us revert CAFs in GHCi
 194    -------------------------------------------------------------------------- */
 195
 196 void newCAF     (StgClosure*);
 197 void newDynCAF  (StgClosure *);
 198 void revertCAFs (void);
 199
 200 /* set to disable CAF garbage collection in GHCi. */
 201 /* (needed when dynamic libraries are used). */
 202 extern rtsBool keepCAFs;
 203
 204 #endif /* RTS_STORAGE_GC_H */