lua

A copy of the Lua development repository
Log | Files | Refs | README

lgc.h (9007B)


      1 /*
      2 ** $Id: lgc.h $
      3 ** Garbage Collector
      4 ** See Copyright Notice in lua.h
      5 */
      6 
      7 #ifndef lgc_h
      8 #define lgc_h
      9 
     10 
     11 #include <stddef.h>
     12 
     13 
     14 #include "lobject.h"
     15 #include "lstate.h"
     16 
     17 /*
     18 ** Collectable objects may have one of three colors: white, which means
     19 ** the object is not marked; gray, which means the object is marked, but
     20 ** its references may be not marked; and black, which means that the
     21 ** object and all its references are marked.  The main invariant of the
     22 ** garbage collector, while marking objects, is that a black object can
     23 ** never point to a white one. Moreover, any gray object must be in a
     24 ** "gray list" (gray, grayagain, weak, allweak, ephemeron) so that it
     25 ** can be visited again before finishing the collection cycle. (Open
     26 ** upvalues are an exception to this rule, as they are attached to
     27 ** a corresponding thread.)  These lists have no meaning when the
     28 ** invariant is not being enforced (e.g., sweep phase).
     29 */
     30 
     31 
     32 /*
     33 ** Possible states of the Garbage Collector
     34 */
     35 #define GCSpropagate	0
     36 #define GCSenteratomic	1
     37 #define GCSatomic	2
     38 #define GCSswpallgc	3
     39 #define GCSswpfinobj	4
     40 #define GCSswptobefnz	5
     41 #define GCSswpend	6
     42 #define GCScallfin	7
     43 #define GCSpause	8
     44 
     45 
     46 #define issweepphase(g)  \
     47 	(GCSswpallgc <= (g)->gcstate && (g)->gcstate <= GCSswpend)
     48 
     49 
     50 /*
     51 ** macro to tell when main invariant (white objects cannot point to black
     52 ** ones) must be kept. During a collection, the sweep phase may break
     53 ** the invariant, as objects turned white may point to still-black
     54 ** objects. The invariant is restored when sweep ends and all objects
     55 ** are white again.
     56 */
     57 
     58 #define keepinvariant(g)	((g)->gcstate <= GCSatomic)
     59 
     60 
     61 /*
     62 ** some useful bit tricks
     63 */
     64 #define resetbits(x,m)		((x) &= cast_byte(~(m)))
     65 #define setbits(x,m)		((x) |= (m))
     66 #define testbits(x,m)		((x) & (m))
     67 #define bitmask(b)		(1<<(b))
     68 #define bit2mask(b1,b2)		(bitmask(b1) | bitmask(b2))
     69 #define l_setbit(x,b)		setbits(x, bitmask(b))
     70 #define resetbit(x,b)		resetbits(x, bitmask(b))
     71 #define testbit(x,b)		testbits(x, bitmask(b))
     72 
     73 
     74 /*
     75 ** Layout for bit use in 'marked' field. First three bits are
     76 ** used for object "age" in generational mode. Last bit is used
     77 ** by tests.
     78 */
     79 #define WHITE0BIT	3  /* object is white (type 0) */
     80 #define WHITE1BIT	4  /* object is white (type 1) */
     81 #define BLACKBIT	5  /* object is black */
     82 #define FINALIZEDBIT	6  /* object has been marked for finalization */
     83 
     84 #define TESTBIT		7
     85 
     86 
     87 
     88 #define WHITEBITS	bit2mask(WHITE0BIT, WHITE1BIT)
     89 
     90 
     91 #define iswhite(x)      testbits((x)->marked, WHITEBITS)
     92 #define isblack(x)      testbit((x)->marked, BLACKBIT)
     93 #define isgray(x)  /* neither white nor black */  \
     94 	(!testbits((x)->marked, WHITEBITS | bitmask(BLACKBIT)))
     95 
     96 #define tofinalize(x)	testbit((x)->marked, FINALIZEDBIT)
     97 
     98 #define otherwhite(g)	((g)->currentwhite ^ WHITEBITS)
     99 #define isdeadm(ow,m)	((m) & (ow))
    100 #define isdead(g,v)	isdeadm(otherwhite(g), (v)->marked)
    101 
    102 #define changewhite(x)	((x)->marked ^= WHITEBITS)
    103 #define nw2black(x)  \
    104 	check_exp(!iswhite(x), l_setbit((x)->marked, BLACKBIT))
    105 
    106 #define luaC_white(g)	cast_byte((g)->currentwhite & WHITEBITS)
    107 
    108 
    109 /* object age in generational mode */
    110 #define G_NEW		0	/* created in current cycle */
    111 #define G_SURVIVAL	1	/* created in previous cycle */
    112 #define G_OLD0		2	/* marked old by frw. barrier in this cycle */
    113 #define G_OLD1		3	/* first full cycle as old */
    114 #define G_OLD		4	/* really old object (not to be visited) */
    115 #define G_TOUCHED1	5	/* old object touched this cycle */
    116 #define G_TOUCHED2	6	/* old object touched in previous cycle */
    117 
    118 #define AGEBITS		7  /* all age bits (111) */
    119 
    120 #define getage(o)	((o)->marked & AGEBITS)
    121 #define setage(o,a)  ((o)->marked = cast_byte(((o)->marked & (~AGEBITS)) | a))
    122 #define isold(o)	(getage(o) > G_SURVIVAL)
    123 
    124 
    125 /*
    126 ** In generational mode, objects are created 'new'. After surviving one
    127 ** cycle, they become 'survival'. Both 'new' and 'survival' can point
    128 ** to any other object, as they are traversed at the end of the cycle.
    129 ** We call them both 'young' objects.
    130 ** If a survival object survives another cycle, it becomes 'old1'.
    131 ** 'old1' objects can still point to survival objects (but not to
    132 ** new objects), so they still must be traversed. After another cycle
    133 ** (that, being old, 'old1' objects will "survive" no matter what)
    134 ** finally the 'old1' object becomes really 'old', and then they
    135 ** are no more traversed.
    136 **
    137 ** To keep its invariants, the generational mode uses the same barriers
    138 ** also used by the incremental mode. If a young object is caught in a
    139 ** forward barrier, it cannot become old immediately, because it can
    140 ** still point to other young objects. Instead, it becomes 'old0',
    141 ** which in the next cycle becomes 'old1'. So, 'old0' objects is
    142 ** old but can point to new and survival objects; 'old1' is old
    143 ** but cannot point to new objects; and 'old' cannot point to any
    144 ** young object.
    145 **
    146 ** If any old object ('old0', 'old1', 'old') is caught in a back
    147 ** barrier, it becomes 'touched1' and goes into a gray list, to be
    148 ** visited at the end of the cycle.  There it evolves to 'touched2',
    149 ** which can point to survivals but not to new objects. In yet another
    150 ** cycle then it becomes 'old' again.
    151 **
    152 ** The generational mode must also control the colors of objects,
    153 ** because of the barriers.  While the mutator is running, young objects
    154 ** are kept white. 'old', 'old1', and 'touched2' objects are kept black,
    155 ** as they cannot point to new objects; exceptions are threads and open
    156 ** upvalues, which age to 'old1' and 'old' but are kept gray. 'old0'
    157 ** objects may be gray or black, as in the incremental mode. 'touched1'
    158 ** objects are kept gray, as they must be visited again at the end of
    159 ** the cycle.
    160 */
    161 
    162 
    163 /*
    164 ** {======================================================
    165 ** Default Values for GC parameters
    166 ** =======================================================
    167 */
    168 
    169 /*
    170 ** Minor collections will shift to major ones after LUAI_MINORMAJOR%
    171 ** bytes become old.
    172 */
    173 #define LUAI_MINORMAJOR         70
    174 
    175 /*
    176 ** Major collections will shift to minor ones after a collection
    177 ** collects at least LUAI_MAJORMINOR% of the new bytes.
    178 */
    179 #define LUAI_MAJORMINOR         50
    180 
    181 /*
    182 ** A young (minor) collection will run after creating LUAI_GENMINORMUL%
    183 ** new bytes.
    184 */
    185 #define LUAI_GENMINORMUL         20
    186 
    187 
    188 /* incremental */
    189 
    190 /* Number of bytes must be LUAI_GCPAUSE% before starting new cycle */
    191 #define LUAI_GCPAUSE    250
    192 
    193 /*
    194 ** Step multiplier: The collector handles LUAI_GCMUL% work units for
    195 ** each new allocated word. (Each "work unit" corresponds roughly to
    196 ** sweeping one object or traversing one slot.)
    197 */
    198 #define LUAI_GCMUL      200
    199 
    200 /* How many bytes to allocate before next GC step */
    201 #define LUAI_GCSTEPSIZE	(200 * sizeof(Table))
    202 
    203 
    204 #define setgcparam(g,p,v)  (g->gcparams[LUA_GCP##p] = luaO_codeparam(v))
    205 #define applygcparam(g,p,x)  luaO_applyparam(g->gcparams[LUA_GCP##p], x)
    206 
    207 /* }====================================================== */
    208 
    209 
    210 /*
    211 ** Control when GC is running:
    212 */
    213 #define GCSTPUSR	1  /* bit true when GC stopped by user */
    214 #define GCSTPGC		2  /* bit true when GC stopped by itself */
    215 #define GCSTPCLS	4  /* bit true when closing Lua state */
    216 #define gcrunning(g)	((g)->gcstp == 0)
    217 
    218 
    219 /*
    220 ** Does one step of collection when debt becomes zero. 'pre'/'pos'
    221 ** allows some adjustments to be done only when needed. macro
    222 ** 'condchangemem' is used only for heavy tests (forcing a full
    223 ** GC cycle on every opportunity)
    224 */
    225 
    226 #if !defined(HARDMEMTESTS)
    227 #define condchangemem(L,pre,pos,emg)	((void)0)
    228 #else
    229 #define condchangemem(L,pre,pos,emg)  \
    230 	{ if (gcrunning(G(L))) { pre; luaC_fullgc(L, emg); pos; } }
    231 #endif
    232 
    233 #define luaC_condGC(L,pre,pos) \
    234 	{ if (G(L)->GCdebt <= 0) { pre; luaC_step(L); pos;}; \
    235 	  condchangemem(L,pre,pos,0); }
    236 
    237 /* more often than not, 'pre'/'pos' are empty */
    238 #define luaC_checkGC(L)		luaC_condGC(L,(void)0,(void)0)
    239 
    240 
    241 #define luaC_objbarrier(L,p,o) (  \
    242 	(isblack(p) && iswhite(o)) ? \
    243 	luaC_barrier_(L,obj2gco(p),obj2gco(o)) : cast_void(0))
    244 
    245 #define luaC_barrier(L,p,v) (  \
    246 	iscollectable(v) ? luaC_objbarrier(L,p,gcvalue(v)) : cast_void(0))
    247 
    248 #define luaC_objbarrierback(L,p,o) (  \
    249 	(isblack(p) && iswhite(o)) ? luaC_barrierback_(L,p) : cast_void(0))
    250 
    251 #define luaC_barrierback(L,p,v) (  \
    252 	iscollectable(v) ? luaC_objbarrierback(L, p, gcvalue(v)) : cast_void(0))
    253 
    254 LUAI_FUNC void luaC_fix (lua_State *L, GCObject *o);
    255 LUAI_FUNC void luaC_freeallobjects (lua_State *L);
    256 LUAI_FUNC void luaC_step (lua_State *L);
    257 LUAI_FUNC void luaC_runtilstate (lua_State *L, int state, int fast);
    258 LUAI_FUNC void luaC_fullgc (lua_State *L, int isemergency);
    259 LUAI_FUNC GCObject *luaC_newobj (lua_State *L, lu_byte tt, size_t sz);
    260 LUAI_FUNC GCObject *luaC_newobjdt (lua_State *L, lu_byte tt, size_t sz,
    261                                                  size_t offset);
    262 LUAI_FUNC void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v);
    263 LUAI_FUNC void luaC_barrierback_ (lua_State *L, GCObject *o);
    264 LUAI_FUNC void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt);
    265 LUAI_FUNC void luaC_changemode (lua_State *L, int newmode);
    266 
    267 
    268 #endif