Storage.h 13.9 KB
Newer Older
1
/* -----------------------------------------------------------------------------
2
 *
3
 * (c) The GHC Team, 1998-2004
4 5 6 7 8 9 10 11
 *
 * External Storage Manger Interface
 *
 * ---------------------------------------------------------------------------*/

#ifndef STORAGE_H
#define STORAGE_H

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
#include <stddef.h>

/* -----------------------------------------------------------------------------
 * Generational GC
 *
 * We support an arbitrary number of generations, with an arbitrary number
 * of steps per generation.  Notes (in no particular order):
 *
 *       - all generations except the oldest should have two steps.  This gives
 *         objects a decent chance to age before being promoted, and in
 *         particular will ensure that we don't end up with too many
 *         thunks being updated in older generations.
 *
 *       - the oldest generation has one step.  There's no point in aging
 *         objects in the oldest generation.
 *
 *       - generation 0, step 0 (G0S0) is the allocation area.  It is given
 *         a fixed set of blocks during initialisation, and these blocks
 *         are never freed.
 *
 *       - during garbage collection, each step which is an evacuation
 *         destination (i.e. all steps except G0S0) is allocated a to-space.
 *         evacuated objects are allocated into the step's to-space until
 *         GC is finished, when the original step's contents may be freed
 *         and replaced by the to-space.
 *
 *       - the mutable-list is per-generation (not per-step).  G0 doesn't 
 *         have one (since every garbage collection collects at least G0).
 * 
 *       - block descriptors contain pointers to both the step and the
 *         generation that the block belongs to, for convenience.
 *
 *       - static objects are stored in per-generation lists.  See GC.c for
 *         details of how we collect CAFs in the generational scheme.
 *
 *       - large objects are per-step, and are promoted in the same way
 *         as small objects, except that we may allocate large objects into
 *         generation 1 initially.
 *
 * ------------------------------------------------------------------------- */

typedef struct _step {
  unsigned int         no;		/* step number */
  bdescr *             blocks;		/* blocks in this step */
  unsigned int         n_blocks;	/* number of blocks */
  struct _step *       to;		/* destination step for live objects */
  struct _generation * gen;		/* generation this step belongs to */
  unsigned int         gen_no;          /* generation number (cached) */
  bdescr *             large_objects;	/* large objects (doubly linked) */
  unsigned int         n_large_blocks;  /* no. of blocks used by large objs */
  int                  is_compacted;	/* compact this step? (old gen only) */

  /* temporary use during GC: */
  StgPtr       hp;			/* next free locn in to-space */
  StgPtr       hpLim;			/* end of current to-space block */
  bdescr *     hp_bd;			/* bdescr of current to-space block */
  bdescr *     to_blocks;		/* bdescr of first to-space block */
  unsigned int n_to_blocks;		/* number of blocks in to-space */
  bdescr *     scan_bd;			/* block currently being scanned */
  StgPtr       scan;			/* scan pointer in current block */
  bdescr *     new_large_objects;    	/* large objects collected so far */
  bdescr *     scavenged_large_objects; /* live large objs after GC (d-link) */
  unsigned int n_scavenged_large_blocks;/* size of above */
  bdescr *     bitmap;  		/* bitmap for compacting collection */
} step;

typedef struct _generation {
  unsigned int   no;			/* generation number */
  step *         steps;			/* steps */
  unsigned int   n_steps;		/* number of steps */
  unsigned int   max_blocks;		/* max blocks in step 0 */
83
  bdescr        *mut_list;      	/* mut objects in this gen (not G0)*/
84 85

  /* temporary use during GC: */
86
  bdescr        *saved_mut_list;
87 88 89 90 91 92 93 94 95 96 97

  /* stats information */
  unsigned int collections;
  unsigned int failed_promotions;
} generation;

extern generation * RTS_VAR(generations);

extern generation * RTS_VAR(g0);
extern step * RTS_VAR(g0s0);
extern generation * RTS_VAR(oldest_gen);
98 99 100 101 102 103 104 105 106 107 108

/* -----------------------------------------------------------------------------
   Initialisation / De-initialisation
   -------------------------------------------------------------------------- */

extern void initStorage(void);
extern void exitStorage(void);

/* -----------------------------------------------------------------------------
   Generic allocation

109
   StgPtr allocate(nat n)       Allocates a chunk of contiguous store
110 111
   				n words long, returning a pointer to
				the first word.  Always succeeds.
112
				
113 114 115 116 117 118 119 120 121 122 123
   StgPtr allocatePinned(nat n) Allocates a chunk of contiguous store
   				n words long, which is at a fixed
				address (won't be moved by GC).  
				Returns a pointer to the first word.
				Always succeeds.
				
				NOTE: the GC can't in general handle
				pinned objects, so allocatePinned()
				can only be used for ByteArrays at the
				moment.

124
				Don't forget to TICK_ALLOC_XXX(...)
125 126
				after calling allocate or
				allocatePinned, for the
127
				benefit of the ticky-ticky profiler.
128 129 130 131 132 133

   rtsBool doYouWantToGC(void)  Returns True if the storage manager is
   				ready to perform a GC, False otherwise.

   lnat  allocated_bytes(void)  Returns the number of bytes allocated
                                via allocate() since the last GC.
sof's avatar
sof committed
134
				Used in the reporting of statistics.
135 136 137

   SMP: allocate and doYouWantToGC can be used from STG code, they are
   surrounded by a mutex.
138 139
   -------------------------------------------------------------------------- */

140 141 142 143
extern StgPtr  allocate        ( nat n );
extern StgPtr  allocatePinned  ( nat n );
extern lnat    allocated_bytes ( void );

144 145 146 147 148 149 150 151 152 153
extern bdescr * RTS_VAR(small_alloc_list);
extern bdescr * RTS_VAR(large_alloc_list);
extern bdescr * RTS_VAR(pinned_object_block);

extern StgPtr RTS_VAR(alloc_Hp);
extern StgPtr RTS_VAR(alloc_HpLim);

extern nat RTS_VAR(alloc_blocks);
extern nat RTS_VAR(alloc_blocks_lim);

sof's avatar
sof committed
154
INLINE_HEADER rtsBool
155
doYouWantToGC( void )
156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
{
  return (alloc_blocks >= alloc_blocks_lim);
}

/* -----------------------------------------------------------------------------
   Performing Garbage Collection

   GarbageCollect(get_roots)    Performs a garbage collection.  
				'get_roots' is called to find all the 
				roots that the system knows about.

   StgClosure 			Called by get_roots on each root.	
   MarkRoot(StgClosure *p)	Returns the new location of the root.
   -------------------------------------------------------------------------- */

171
extern void GarbageCollect(void (*get_roots)(evac_fn),rtsBool force_major_gc);
172 173 174 175

/* -----------------------------------------------------------------------------
   Generational garbage collection support

176
   recordMutable(StgPtr p)       Informs the garbage collector that a
177 178 179 180
				 previously immutable object has
				 become (permanently) mutable.  Used
				 by thawArray and similar.

181
   updateWithIndirection(p1,p2)  Updates the object at p1 with an
182 183 184 185
				 indirection pointing to p2.  This is
				 normally called for objects in an old
				 generation (>0) when they are updated.

186 187
   updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.

188 189
   -------------------------------------------------------------------------- */

190 191 192
/*
 * Storage manager mutex
 */
sof's avatar
sof committed
193 194 195 196 197 198 199
#if defined(SMP)
extern Mutex sm_mutex;
#define ACQUIRE_SM_LOCK   ACQUIRE_LOCK(&sm_mutex)
#define RELEASE_SM_LOCK   RELEASE_LOCK(&sm_mutex)
#else
#define ACQUIRE_SM_LOCK
#define RELEASE_SM_LOCK
200 201
#endif

202 203 204
/* ToDo: shouldn't recordMutable acquire some
 * kind of lock in the SMP case?  Or do we need per-processor
 * mutable lists?
205
 */
sof's avatar
sof committed
206
INLINE_HEADER void
207
recordMutableGen(StgClosure *p, generation *gen)
208
{
209 210 211 212 213 214 215 216 217 218 219
    bdescr *bd;

    bd = gen->mut_list;
    if (bd->free >= bd->start + BLOCK_SIZE_W) {
	bdescr *new_bd;
	new_bd = allocBlock();
	new_bd->link = bd;
	bd = new_bd;
	gen->mut_list = bd;
    }
    *bd->free++ = (StgWord)p;
220 221
}

sof's avatar
sof committed
222
INLINE_HEADER void
223
recordMutable(StgClosure *p)
224
{
225 226 227 228
    bdescr *bd;
    ASSERT(closure_MUTABLE(p));
    bd = Bdescr((P_)p);
    if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
229 230
}

231
/* -----------------------------------------------------------------------------
232
   The CAF table - used to let us revert CAFs in GHCi
233 234
   -------------------------------------------------------------------------- */

235 236
void revertCAFs( void );

237 238
/* -----------------------------------------------------------------------------
   DEBUGGING predicates for pointers
239

240 241
   LOOKS_LIKE_INFO_PTR(p)    returns False if p is definitely not an info ptr
   LOOKS_LIKE_CLOSURE_PTR(p) returns False if p is definitely not a closure ptr
242

243 244 245
   These macros are complete but not sound.  That is, they might
   return false positives.  Do not rely on them to distinguish info
   pointers from closure pointers, for example.
246

247 248 249 250 251
   We don't use address-space predicates these days, for portability
   reasons, and the fact that code/data can be scattered about the
   address space in a dynamically-linked environment.  Our best option
   is to look at the alleged info table and see whether it seems to
   make sense...
252 253
   -------------------------------------------------------------------------- */

254 255 256
#define LOOKS_LIKE_INFO_PTR(p) \
   (p && ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type != INVALID_OBJECT && \
    ((StgInfoTable *)(INFO_PTR_TO_STRUCT(p)))->type < N_CLOSURE_TYPES)
257

258 259
#define LOOKS_LIKE_CLOSURE_PTR(p) \
   (LOOKS_LIKE_INFO_PTR(((StgClosure *)(p))->header.info))
260

261 262 263 264
/* -----------------------------------------------------------------------------
   Macros for calculating how big a closure will be (used during allocation)
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
265
INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
266
{ return sizeofW(StgPAP) + n_args; }
267

sof's avatar
sof committed
268
INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
269
{ return sizeofW(StgAP_STACK) + size; }
270

sof's avatar
sof committed
271
INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
272 273
{ return sizeofW(StgHeader) + p + np; }

sof's avatar
sof committed
274
INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
275
{ return stg_max(sizeofW(StgHeader)+MIN_UPD_SIZE, sizeofW(StgSelector)); }
276

sof's avatar
sof committed
277
INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
278
{ return stg_max(sizeofW(StgHeader)+MIN_UPD_SIZE, sizeofW(StgBlockingQueue)); }
279 280

/* --------------------------------------------------------------------------
281 282
   Sizes of closures
   ------------------------------------------------------------------------*/
283

sof's avatar
sof committed
284
INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl ) 
285 286 287 288
{ return sizeofW(StgClosure) 
       + sizeofW(StgPtr)  * itbl->layout.payload.ptrs 
       + sizeofW(StgWord) * itbl->layout.payload.nptrs; }

sof's avatar
sof committed
289
INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
290 291
{ return AP_STACK_sizeW(x->size); }

sof's avatar
sof committed
292
INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
293 294
{ return PAP_sizeW(x->n_args); }

sof's avatar
sof committed
295
INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
296 297
{ return sizeofW(StgArrWords) + x->words; }

sof's avatar
sof committed
298
INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
299 300
{ return sizeofW(StgMutArrPtrs) + x->ptrs; }

sof's avatar
sof committed
301
INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
302 303
{ return TSO_STRUCT_SIZEW + tso->stack_size; }

sof's avatar
sof committed
304
INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
305 306
{ return bco->size; }

307 308 309 310
/* -----------------------------------------------------------------------------
   Sizes of stack frames
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
311
INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
312 313 314 315 316 317 318 319 320
{
    StgRetInfoTable *info;

    info = get_ret_itbl(frame);
    switch (info->i.type) {

    case RET_DYN:
    {
	StgRetDyn *dyn = (StgRetDyn *)frame;
321 322
	return  sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE + 
	    RET_DYN_NONPTR_REGS_SIZE +
323
	    RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
324 325 326 327 328 329
    }
	    
    case RET_FUN:
	return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;

    case RET_BIG:
330
    case RET_VEC_BIG:
331
	return 1 + GET_LARGE_BITMAP(&info->i)->size;
332 333 334 335 336 337 338 339 340 341

    case RET_BCO:
	return 2 + BCO_BITMAP_SIZE((StgBCO *)((P_)frame)[1]);

    default:
	return 1 + BITMAP_SIZE(info->i.layout.bitmap);
    }
}

/* -----------------------------------------------------------------------------
342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
   Nursery manipulation
   -------------------------------------------------------------------------- */

extern void     allocNurseries ( void );
extern void     resetNurseries ( void );
extern bdescr * allocNursery   ( bdescr *last_bd, nat blocks );
extern void     resizeNursery  ( nat blocks );
extern void     tidyAllocateLists ( void );

/* -----------------------------------------------------------------------------
   Functions from GC.c 
   -------------------------------------------------------------------------- */

extern void         threadPaused ( StgTSO * );
extern StgClosure * isAlive      ( StgClosure *p );
extern void         markCAFs     ( evac_fn evac );

/* -----------------------------------------------------------------------------
   Stats 'n' DEBUG stuff
361 362
   -------------------------------------------------------------------------- */

363
extern ullong RTS_VAR(total_allocated);
364 365 366 367 368 369 370 371 372 373 374

extern lnat calcAllocated  ( void );
extern lnat calcLive       ( void );
extern lnat calcNeeded     ( void );

#if defined(DEBUG)
extern void memInventory(void);
extern void checkSanity(void);
extern nat  countBlocks(bdescr *);
#endif

375 376 377 378
#if defined(DEBUG)
void printMutOnceList(generation *gen);
void printMutableList(generation *gen);
#endif
379

380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397
/* ----------------------------------------------------------------------------
   Storage manager internal APIs and globals
   ------------------------------------------------------------------------- */

#define END_OF_STATIC_LIST stgCast(StgClosure*,1)

extern void newDynCAF(StgClosure *);

extern void move_TSO(StgTSO *src, StgTSO *dest);
extern StgTSO *relocate_stack(StgTSO *dest, ptrdiff_t diff);

extern StgClosure * RTS_VAR(static_objects);
extern StgClosure * RTS_VAR(scavenged_static_objects);
extern StgWeak    * RTS_VAR(old_weak_ptr_list);
extern StgWeak    * RTS_VAR(weak_ptr_list);
extern StgClosure * RTS_VAR(caf_list);
extern StgTSO     * RTS_VAR(resurrected_threads);

398
#endif // STORAGE_H