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