Storage.h 17.4 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
#include <stddef.h>
13
#include "OSThreads.h"
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

/* -----------------------------------------------------------------------------
 * 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.
 *
 * ------------------------------------------------------------------------- */

54
typedef struct step_ {
55
56
57
  unsigned int         no;		/* step number */
  bdescr *             blocks;		/* blocks in this step */
  unsigned int         n_blocks;	/* number of blocks */
58
59
  struct step_ *       to;		/* destination step for live objects */
  struct generation_ * gen;		/* generation this step belongs to */
60
61
62
63
64
  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) */

65
66
67
68
69
70
  /* During GC, if we are collecting this step, blocks and n_blocks
   * are copied into the following two fields.  After GC, these blocks
   * are freed. */
  bdescr *     old_blocks;	        /* bdescr of first from-space block */
  unsigned int n_old_blocks;		/* number of blocks in from-space */

71
72
73
74
  /* 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 */
75
76
  StgPtr       scavd_hp;		/* ... same as above, but already */
  StgPtr       scavd_hpLim;		/*     scavenged.  */
77
78
79
80
81
82
83
84
  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;

85
typedef struct generation_ {
86
87
88
89
  unsigned int   no;			/* generation number */
  step *         steps;			/* steps */
  unsigned int   n_steps;		/* number of steps */
  unsigned int   max_blocks;		/* max blocks in step 0 */
90
  bdescr        *mut_list;      	/* mut objects in this gen (not G0)*/
91
92

  /* temporary use during GC: */
93
  bdescr        *saved_mut_list;
94
95
96
97
98
99
100
101
102
103
104

  /* 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);
105
106
107
108
109
110
111

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

extern void initStorage(void);
extern void exitStorage(void);
Simon Marlow's avatar
Simon Marlow committed
112
extern void freeStorage(void);
113
114
115
116

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

117
   StgPtr allocate(nat n)       Allocates a chunk of contiguous store
118
119
   				n words long, returning a pointer to
				the first word.  Always succeeds.
120
				
121
122
123
124
125
126
127
128
129
130
131
   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.

132
				Don't forget to TICK_ALLOC_XXX(...)
133
134
				after calling allocate or
				allocatePinned, for the
135
				benefit of the ticky-ticky profiler.
136
137
138
139

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

140
   lnat  allocatedBytes(void)  Returns the number of bytes allocated
141
                                via allocate() since the last GC.
sof's avatar
sof committed
142
				Used in the reporting of statistics.
143

144
   THREADED_RTS: allocate and doYouWantToGC can be used from STG code, they are
145
   surrounded by a mutex.
146
147
   -------------------------------------------------------------------------- */

148
extern StgPtr  allocate        ( nat n );
149
extern StgPtr  allocateLocal   ( Capability *cap, nat n );
150
extern StgPtr  allocatePinned  ( nat n );
151
extern lnat    allocatedBytes  ( void );
152

153
154
155
156
157
158
159
160
161
162
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
163
INLINE_HEADER rtsBool
164
doYouWantToGC( void )
165
166
167
168
{
  return (alloc_blocks >= alloc_blocks_lim);
}

169
170
171
172
/* memory allocator for executable memory */
extern void *allocateExec (nat bytes);
extern void freeExec (void *p);

173
174
175
176
177
178
179
180
181
182
183
/* -----------------------------------------------------------------------------
   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.
   -------------------------------------------------------------------------- */

184
extern void GarbageCollect(void (*get_roots)(evac_fn),rtsBool force_major_gc);
185
186
187
188

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

189
   recordMutable(StgPtr p)       Informs the garbage collector that a
190
191
192
193
				 previously immutable object has
				 become (permanently) mutable.  Used
				 by thawArray and similar.

194
   updateWithIndirection(p1,p2)  Updates the object at p1 with an
195
196
197
198
				 indirection pointing to p2.  This is
				 normally called for objects in an old
				 generation (>0) when they are updated.

199
200
   updateWithPermIndirection(p1,p2)  As above but uses a permanent indir.

201
202
   -------------------------------------------------------------------------- */

203
204
/*
 * Storage manager mutex
205
 */
206
#if defined(THREADED_RTS)
207
extern Mutex sm_mutex;
208
extern Mutex atomic_modify_mutvar_mutex;
209
210
#endif

211
#if defined(THREADED_RTS)
212
213
#define ACQUIRE_SM_LOCK   ACQUIRE_LOCK(&sm_mutex);
#define RELEASE_SM_LOCK   RELEASE_LOCK(&sm_mutex);
214
#define ASSERT_SM_LOCK()  ASSERT_LOCK_HELD(&sm_mutex);
215
216
217
#else
#define ACQUIRE_SM_LOCK
#define RELEASE_SM_LOCK
218
#define ASSERT_SM_LOCK()
219
220
#endif

sof's avatar
sof committed
221
INLINE_HEADER void
222
recordMutableGen(StgClosure *p, generation *gen)
223
{
224
225
226
227
228
229
230
231
232
233
234
    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;
235
236
237
238
239
240
241
242
243

}

INLINE_HEADER void
recordMutableGenLock(StgClosure *p, generation *gen)
{
    ACQUIRE_SM_LOCK;
    recordMutableGen(p,gen);
    RELEASE_SM_LOCK;
244
245
}

sof's avatar
sof committed
246
INLINE_HEADER void
247
recordMutable(StgClosure *p)
248
{
249
250
251
252
    bdescr *bd;
    ASSERT(closure_MUTABLE(p));
    bd = Bdescr((P_)p);
    if (bd->gen_no > 0) recordMutableGen(p, &RTS_DEREF(generations)[bd->gen_no]);
253
254
}

255
256
257
258
259
260
261
262
INLINE_HEADER void
recordMutableLock(StgClosure *p)
{
    ACQUIRE_SM_LOCK;
    recordMutable(p);
    RELEASE_SM_LOCK;
}

263
/* -----------------------------------------------------------------------------
264
   The CAF table - used to let us revert CAFs in GHCi
265
266
   -------------------------------------------------------------------------- */

267
268
/* set to disable CAF garbage collection in GHCi. */
/* (needed when dynamic libraries are used). */
269
270
extern rtsBool keepCAFs;

271
272
273
274
275
276
277
/* -----------------------------------------------------------------------------
   This is the write barrier for MUT_VARs, a.k.a. IORefs.  A
   MUT_VAR_CLEAN object is not on the mutable list; a MUT_VAR_DIRTY
   is.  When written to, a MUT_VAR_CLEAN turns into a MUT_VAR_DIRTY
   and is put on the mutable list.
   -------------------------------------------------------------------------- */

278
void dirty_MUT_VAR(StgRegTable *reg, StgClosure *p);
279

280
281
/* -----------------------------------------------------------------------------
   DEBUGGING predicates for pointers
282

283
284
   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
285

286
287
288
   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.
289

290
291
292
293
294
   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...
295
296
   -------------------------------------------------------------------------- */

297
298
299
#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)
300

301
302
#define LOOKS_LIKE_CLOSURE_PTR(p) \
   (LOOKS_LIKE_INFO_PTR(((StgClosure *)(p))->header.info))
303

304
305
306
307
/* -----------------------------------------------------------------------------
   Macros for calculating how big a closure will be (used during allocation)
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
308
INLINE_HEADER StgOffset PAP_sizeW   ( nat n_args )
309
{ return sizeofW(StgPAP) + n_args; }
310

311
312
313
INLINE_HEADER StgOffset AP_sizeW   ( nat n_args )
{ return sizeofW(StgAP) + n_args; }

sof's avatar
sof committed
314
INLINE_HEADER StgOffset AP_STACK_sizeW ( nat size )
315
{ return sizeofW(StgAP_STACK) + size; }
316

sof's avatar
sof committed
317
INLINE_HEADER StgOffset CONSTR_sizeW( nat p, nat np )
318
319
{ return sizeofW(StgHeader) + p + np; }

sof's avatar
sof committed
320
INLINE_HEADER StgOffset THUNK_SELECTOR_sizeW ( void )
321
{ return sizeofW(StgSelector); }
322

sof's avatar
sof committed
323
INLINE_HEADER StgOffset BLACKHOLE_sizeW ( void )
324
{ return sizeofW(StgHeader)+MIN_PAYLOAD_SIZE; }
325
326

/* --------------------------------------------------------------------------
327
328
   Sizes of closures
   ------------------------------------------------------------------------*/
329

sof's avatar
sof committed
330
INLINE_HEADER StgOffset sizeW_fromITBL( const StgInfoTable* itbl ) 
331
332
333
334
{ return sizeofW(StgClosure) 
       + sizeofW(StgPtr)  * itbl->layout.payload.ptrs 
       + sizeofW(StgWord) * itbl->layout.payload.nptrs; }

335
336
337
338
339
INLINE_HEADER StgOffset thunk_sizeW_fromITBL( const StgInfoTable* itbl ) 
{ return sizeofW(StgThunk) 
       + sizeofW(StgPtr)  * itbl->layout.payload.ptrs 
       + sizeofW(StgWord) * itbl->layout.payload.nptrs; }

sof's avatar
sof committed
340
INLINE_HEADER StgOffset ap_stack_sizeW( StgAP_STACK* x )
341
342
{ return AP_STACK_sizeW(x->size); }

343
344
345
INLINE_HEADER StgOffset ap_sizeW( StgAP* x )
{ return AP_sizeW(x->n_args); }

sof's avatar
sof committed
346
INLINE_HEADER StgOffset pap_sizeW( StgPAP* x )
347
348
{ return PAP_sizeW(x->n_args); }

sof's avatar
sof committed
349
INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
350
351
{ return sizeofW(StgArrWords) + x->words; }

sof's avatar
sof committed
352
INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
353
354
{ return sizeofW(StgMutArrPtrs) + x->ptrs; }

sof's avatar
sof committed
355
INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
356
357
{ return TSO_STRUCT_SIZEW + tso->stack_size; }

sof's avatar
sof committed
358
INLINE_HEADER StgWord bco_sizeW ( StgBCO *bco )
359
360
{ return bco->size; }

361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
STATIC_INLINE nat
closure_sizeW_ (StgClosure *p, StgInfoTable *info)
{
    switch (info->type) {
    case THUNK_0_1:
    case THUNK_1_0:
	return sizeofW(StgThunk) + 1;
    case FUN_0_1:
    case CONSTR_0_1:
    case FUN_1_0:
    case CONSTR_1_0:
	return sizeofW(StgHeader) + 1;
    case THUNK_0_2:
    case THUNK_1_1:
    case THUNK_2_0:
	return sizeofW(StgThunk) + 2;
    case FUN_0_2:
    case CONSTR_0_2:
    case FUN_1_1:
    case CONSTR_1_1:
    case FUN_2_0:
    case CONSTR_2_0:
	return sizeofW(StgHeader) + 2;
Simon Marlow's avatar
Simon Marlow committed
384
385
    case THUNK:
	return thunk_sizeW_fromITBL(info);
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
    case THUNK_SELECTOR:
	return THUNK_SELECTOR_sizeW();
    case AP_STACK:
	return ap_stack_sizeW((StgAP_STACK *)p);
    case AP:
    case PAP:
	return pap_sizeW((StgPAP *)p);
    case IND:
    case IND_PERM:
    case IND_OLDGEN:
    case IND_OLDGEN_PERM:
	return sizeofW(StgInd);
    case ARR_WORDS:
	return arr_words_sizeW((StgArrWords *)p);
    case MUT_ARR_PTRS_CLEAN:
    case MUT_ARR_PTRS_DIRTY:
    case MUT_ARR_PTRS_FROZEN:
    case MUT_ARR_PTRS_FROZEN0:
	return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
    case TSO:
	return tso_sizeW((StgTSO *)p);
    case BCO:
	return bco_sizeW((StgBCO *)p);
tharris@microsoft.com's avatar
tharris@microsoft.com committed
409
410
    case TVAR_WATCH_QUEUE:
        return sizeofW(StgTVarWatchQueue);
411
412
413
414
415
416
    case TVAR:
        return sizeofW(StgTVar);
    case TREC_CHUNK:
        return sizeofW(StgTRecChunk);
    case TREC_HEADER:
        return sizeofW(StgTRecHeader);
tharris@microsoft.com's avatar
tharris@microsoft.com committed
417
418
419
420
    case ATOMIC_INVARIANT:
        return sizeofW(StgAtomicInvariant);
    case INVARIANT_CHECK_QUEUE:
        return sizeofW(StgInvariantCheckQueue);
421
422
423
424
425
    default:
	return sizeW_fromITBL(info);
    }
}

Simon Marlow's avatar
Simon Marlow committed
426
// The definitive way to find the size, in words, of a heap-allocated closure
427
428
429
430
431
432
STATIC_INLINE nat
closure_sizeW (StgClosure *p)
{
    return closure_sizeW_(p, get_itbl(p));
}

433
434
435
436
/* -----------------------------------------------------------------------------
   Sizes of stack frames
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
437
INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
438
439
440
441
442
443
444
445
446
{
    StgRetInfoTable *info;

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

    case RET_DYN:
    {
	StgRetDyn *dyn = (StgRetDyn *)frame;
447
448
	return  sizeofW(StgRetDyn) + RET_DYN_BITMAP_SIZE + 
	    RET_DYN_NONPTR_REGS_SIZE +
449
	    RET_DYN_PTRS(dyn->liveness) + RET_DYN_NONPTRS(dyn->liveness);
450
451
452
453
454
455
    }
	    
    case RET_FUN:
	return sizeofW(StgRetFun) + ((StgRetFun *)frame)->size;

    case RET_BIG:
456
    case RET_VEC_BIG:
457
	return 1 + GET_LARGE_BITMAP(&info->i)->size;
458
459
460
461
462
463
464
465
466
467

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

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

/* -----------------------------------------------------------------------------
468
469
470
   Nursery manipulation
   -------------------------------------------------------------------------- */

471
472
473
474
475
476
extern void     allocNurseries       ( void );
extern void     resetNurseries       ( void );
extern void     resizeNurseries      ( nat blocks );
extern void     resizeNurseriesFixed ( nat blocks );
extern void     tidyAllocateLists    ( void );
extern lnat     countNurseryBlocks   ( void );
477
478
479
480
481

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

482
extern void         threadPaused ( Capability *cap, StgTSO * );
483
484
485
486
487
extern StgClosure * isAlive      ( StgClosure *p );
extern void         markCAFs     ( evac_fn evac );

/* -----------------------------------------------------------------------------
   Stats 'n' DEBUG stuff
488
489
   -------------------------------------------------------------------------- */

490
extern ullong RTS_VAR(total_allocated);
491
492
493
494
495
496
497
498
499

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 *);
500
extern void checkNurserySanity( step *stp );
501
502
#endif

503
504
505
506
#if defined(DEBUG)
void printMutOnceList(generation *gen);
void printMutableList(generation *gen);
#endif
507

508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
/* ----------------------------------------------------------------------------
   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(scavenged_static_objects);
extern StgWeak    * RTS_VAR(old_weak_ptr_list);
extern StgWeak    * RTS_VAR(weak_ptr_list);
extern StgClosure * RTS_VAR(caf_list);
523
extern StgClosure * RTS_VAR(revertible_caf_list);
524
525
extern StgTSO     * RTS_VAR(resurrected_threads);

526
#endif /* STORAGE_H */