diff options
Diffstat (limited to 'apps/plugins/lua/lgc.c')
-rw-r--r-- | apps/plugins/lua/lgc.c | 1417 |
1 files changed, 963 insertions, 454 deletions
diff --git a/apps/plugins/lua/lgc.c b/apps/plugins/lua/lgc.c index d9e0b78294..52460dcdd5 100644 --- a/apps/plugins/lua/lgc.c +++ b/apps/plugins/lua/lgc.c | |||
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lgc.c,v 2.38.1.1 2007/12/27 13:02:25 roberto Exp $ | 2 | ** $Id: lgc.c,v 2.140.1.2 2013/04/26 18:22:05 roberto Exp $ |
3 | ** Garbage Collector | 3 | ** Garbage Collector |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -23,376 +23,663 @@ | |||
23 | #include "ltm.h" | 23 | #include "ltm.h" |
24 | 24 | ||
25 | 25 | ||
26 | #define GCSTEPSIZE 1024u | ||
27 | #define GCSWEEPMAX 40 | ||
28 | #define GCSWEEPCOST 10 | ||
29 | #define GCFINALIZECOST 100 | ||
30 | 26 | ||
27 | /* | ||
28 | ** cost of sweeping one element (the size of a small object divided | ||
29 | ** by some adjust for the sweep speed) | ||
30 | */ | ||
31 | #define GCSWEEPCOST ((sizeof(TString) + 4) / 4) | ||
31 | 32 | ||
32 | #define maskmarks cast_byte(~(bitmask(BLACKBIT)|WHITEBITS)) | 33 | /* maximum number of elements to sweep in each single step */ |
34 | #define GCSWEEPMAX (cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4)) | ||
33 | 35 | ||
34 | #define makewhite(g,x) \ | 36 | /* maximum number of finalizers to call in each GC step */ |
35 | ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g))) | 37 | #define GCFINALIZENUM 4 |
38 | |||
39 | |||
40 | /* | ||
41 | ** macro to adjust 'stepmul': 'stepmul' is actually used like | ||
42 | ** 'stepmul / STEPMULADJ' (value chosen by tests) | ||
43 | */ | ||
44 | #define STEPMULADJ 200 | ||
45 | |||
46 | |||
47 | /* | ||
48 | ** macro to adjust 'pause': 'pause' is actually used like | ||
49 | ** 'pause / PAUSEADJ' (value chosen by tests) | ||
50 | */ | ||
51 | #define PAUSEADJ 100 | ||
36 | 52 | ||
37 | #define white2gray(x) reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT) | ||
38 | #define black2gray(x) resetbit((x)->gch.marked, BLACKBIT) | ||
39 | 53 | ||
40 | #define stringmark(s) reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT) | 54 | /* |
55 | ** 'makewhite' erases all color bits plus the old bit and then | ||
56 | ** sets only the current white bit | ||
57 | */ | ||
58 | #define maskcolors (~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS)) | ||
59 | #define makewhite(g,x) \ | ||
60 | (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g))) | ||
41 | 61 | ||
62 | #define white2gray(x) resetbits(gch(x)->marked, WHITEBITS) | ||
63 | #define black2gray(x) resetbit(gch(x)->marked, BLACKBIT) | ||
42 | 64 | ||
43 | #define isfinalized(u) testbit((u)->marked, FINALIZEDBIT) | ||
44 | #define markfinalized(u) l_setbit((u)->marked, FINALIZEDBIT) | ||
45 | 65 | ||
66 | #define isfinalized(x) testbit(gch(x)->marked, FINALIZEDBIT) | ||
46 | 67 | ||
47 | #define KEYWEAK bitmask(KEYWEAKBIT) | 68 | #define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n))) |
48 | #define VALUEWEAK bitmask(VALUEWEAKBIT) | ||
49 | 69 | ||
50 | 70 | ||
71 | #define checkconsistency(obj) \ | ||
72 | lua_longassert(!iscollectable(obj) || righttt(obj)) | ||
73 | |||
51 | 74 | ||
52 | #define markvalue(g,o) { checkconsistency(o); \ | 75 | #define markvalue(g,o) { checkconsistency(o); \ |
53 | if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); } | 76 | if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); } |
54 | 77 | ||
55 | #define markobject(g,t) { if (iswhite(obj2gco(t))) \ | 78 | #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \ |
56 | reallymarkobject(g, obj2gco(t)); } | 79 | reallymarkobject(g, obj2gco(t)); } |
57 | 80 | ||
81 | static void reallymarkobject (global_State *g, GCObject *o); | ||
82 | |||
83 | |||
84 | /* | ||
85 | ** {====================================================== | ||
86 | ** Generic functions | ||
87 | ** ======================================================= | ||
88 | */ | ||
89 | |||
90 | |||
91 | /* | ||
92 | ** one after last element in a hash array | ||
93 | */ | ||
94 | #define gnodelast(h) gnode(h, cast(size_t, sizenode(h))) | ||
95 | |||
58 | 96 | ||
59 | #define setthreshold(g) (g->GCthreshold = (g->estimate/100) * g->gcpause) | 97 | /* |
98 | ** link table 'h' into list pointed by 'p' | ||
99 | */ | ||
100 | #define linktable(h,p) ((h)->gclist = *(p), *(p) = obj2gco(h)) | ||
60 | 101 | ||
61 | 102 | ||
103 | /* | ||
104 | ** if key is not marked, mark its entry as dead (therefore removing it | ||
105 | ** from the table) | ||
106 | */ | ||
62 | static void removeentry (Node *n) { | 107 | static void removeentry (Node *n) { |
63 | lua_assert(ttisnil(gval(n))); | 108 | lua_assert(ttisnil(gval(n))); |
64 | if (iscollectable(gkey(n))) | 109 | if (valiswhite(gkey(n))) |
65 | setttype(gkey(n), LUA_TDEADKEY); /* dead key; remove it */ | 110 | setdeadvalue(gkey(n)); /* unused and unmarked key; remove it */ |
111 | } | ||
112 | |||
113 | |||
114 | /* | ||
115 | ** tells whether a key or value can be cleared from a weak | ||
116 | ** table. Non-collectable objects are never removed from weak | ||
117 | ** tables. Strings behave as `values', so are never removed too. for | ||
118 | ** other objects: if really collected, cannot keep them; for objects | ||
119 | ** being finalized, keep them in keys, but not in values | ||
120 | */ | ||
121 | static int iscleared (global_State *g, const TValue *o) { | ||
122 | if (!iscollectable(o)) return 0; | ||
123 | else if (ttisstring(o)) { | ||
124 | markobject(g, rawtsvalue(o)); /* strings are `values', so are never weak */ | ||
125 | return 0; | ||
126 | } | ||
127 | else return iswhite(gcvalue(o)); | ||
66 | } | 128 | } |
67 | 129 | ||
68 | 130 | ||
131 | /* | ||
132 | ** barrier that moves collector forward, that is, mark the white object | ||
133 | ** being pointed by a black object. | ||
134 | */ | ||
135 | void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) { | ||
136 | global_State *g = G(L); | ||
137 | lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o)); | ||
138 | lua_assert(g->gcstate != GCSpause); | ||
139 | lua_assert(gch(o)->tt != LUA_TTABLE); | ||
140 | if (keepinvariantout(g)) /* must keep invariant? */ | ||
141 | reallymarkobject(g, v); /* restore invariant */ | ||
142 | else { /* sweep phase */ | ||
143 | lua_assert(issweepphase(g)); | ||
144 | makewhite(g, o); /* mark main obj. as white to avoid other barriers */ | ||
145 | } | ||
146 | } | ||
147 | |||
148 | |||
149 | /* | ||
150 | ** barrier that moves collector backward, that is, mark the black object | ||
151 | ** pointing to a white object as gray again. (Current implementation | ||
152 | ** only works for tables; access to 'gclist' is not uniform across | ||
153 | ** different types.) | ||
154 | */ | ||
155 | void luaC_barrierback_ (lua_State *L, GCObject *o) { | ||
156 | global_State *g = G(L); | ||
157 | lua_assert(isblack(o) && !isdead(g, o) && gch(o)->tt == LUA_TTABLE); | ||
158 | black2gray(o); /* make object gray (again) */ | ||
159 | gco2t(o)->gclist = g->grayagain; | ||
160 | g->grayagain = o; | ||
161 | } | ||
162 | |||
163 | |||
164 | /* | ||
165 | ** barrier for prototypes. When creating first closure (cache is | ||
166 | ** NULL), use a forward barrier; this may be the only closure of the | ||
167 | ** prototype (if it is a "regular" function, with a single instance) | ||
168 | ** and the prototype may be big, so it is better to avoid traversing | ||
169 | ** it again. Otherwise, use a backward barrier, to avoid marking all | ||
170 | ** possible instances. | ||
171 | */ | ||
172 | LUAI_FUNC void luaC_barrierproto_ (lua_State *L, Proto *p, Closure *c) { | ||
173 | global_State *g = G(L); | ||
174 | lua_assert(isblack(obj2gco(p))); | ||
175 | if (p->cache == NULL) { /* first time? */ | ||
176 | luaC_objbarrier(L, p, c); | ||
177 | } | ||
178 | else { /* use a backward barrier */ | ||
179 | black2gray(obj2gco(p)); /* make prototype gray (again) */ | ||
180 | p->gclist = g->grayagain; | ||
181 | g->grayagain = obj2gco(p); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | |||
186 | /* | ||
187 | ** check color (and invariants) for an upvalue that was closed, | ||
188 | ** i.e., moved into the 'allgc' list | ||
189 | */ | ||
190 | void luaC_checkupvalcolor (global_State *g, UpVal *uv) { | ||
191 | GCObject *o = obj2gco(uv); | ||
192 | lua_assert(!isblack(o)); /* open upvalues are never black */ | ||
193 | if (isgray(o)) { | ||
194 | if (keepinvariant(g)) { | ||
195 | resetoldbit(o); /* see MOVE OLD rule */ | ||
196 | gray2black(o); /* it is being visited now */ | ||
197 | markvalue(g, uv->v); | ||
198 | } | ||
199 | else { | ||
200 | lua_assert(issweepphase(g)); | ||
201 | makewhite(g, o); | ||
202 | } | ||
203 | } | ||
204 | } | ||
205 | |||
206 | |||
207 | /* | ||
208 | ** create a new collectable object (with given type and size) and link | ||
209 | ** it to '*list'. 'offset' tells how many bytes to allocate before the | ||
210 | ** object itself (used only by states). | ||
211 | */ | ||
212 | GCObject *luaC_newobj (lua_State *L, int tt, size_t sz, GCObject **list, | ||
213 | int offset) { | ||
214 | global_State *g = G(L); | ||
215 | char *raw = cast(char *, luaM_newobject(L, novariant(tt), sz)); | ||
216 | GCObject *o = obj2gco(raw + offset); | ||
217 | if (list == NULL) | ||
218 | list = &g->allgc; /* standard list for collectable objects */ | ||
219 | gch(o)->marked = luaC_white(g); | ||
220 | gch(o)->tt = tt; | ||
221 | gch(o)->next = *list; | ||
222 | *list = o; | ||
223 | return o; | ||
224 | } | ||
225 | |||
226 | /* }====================================================== */ | ||
227 | |||
228 | |||
229 | |||
230 | /* | ||
231 | ** {====================================================== | ||
232 | ** Mark functions | ||
233 | ** ======================================================= | ||
234 | */ | ||
235 | |||
236 | |||
237 | /* | ||
238 | ** mark an object. Userdata, strings, and closed upvalues are visited | ||
239 | ** and turned black here. Other objects are marked gray and added | ||
240 | ** to appropriate list to be visited (and turned black) later. (Open | ||
241 | ** upvalues are already linked in 'headuv' list.) | ||
242 | */ | ||
69 | static void reallymarkobject (global_State *g, GCObject *o) { | 243 | static void reallymarkobject (global_State *g, GCObject *o) { |
70 | lua_assert(iswhite(o) && !isdead(g, o)); | 244 | lu_mem size; |
71 | white2gray(o); | 245 | white2gray(o); |
72 | switch (o->gch.tt) { | 246 | switch (gch(o)->tt) { |
73 | case LUA_TSTRING: { | 247 | case LUA_TSHRSTR: |
74 | return; | 248 | case LUA_TLNGSTR: { |
249 | size = sizestring(gco2ts(o)); | ||
250 | break; /* nothing else to mark; make it black */ | ||
75 | } | 251 | } |
76 | case LUA_TUSERDATA: { | 252 | case LUA_TUSERDATA: { |
77 | Table *mt = gco2u(o)->metatable; | 253 | Table *mt = gco2u(o)->metatable; |
78 | gray2black(o); /* udata are never gray */ | 254 | markobject(g, mt); |
79 | if (mt) markobject(g, mt); | ||
80 | markobject(g, gco2u(o)->env); | 255 | markobject(g, gco2u(o)->env); |
81 | return; | 256 | size = sizeudata(gco2u(o)); |
257 | break; | ||
82 | } | 258 | } |
83 | case LUA_TUPVAL: { | 259 | case LUA_TUPVAL: { |
84 | UpVal *uv = gco2uv(o); | 260 | UpVal *uv = gco2uv(o); |
85 | markvalue(g, uv->v); | 261 | markvalue(g, uv->v); |
86 | if (uv->v == &uv->u.value) /* closed? */ | 262 | if (uv->v != &uv->u.value) /* open? */ |
87 | gray2black(o); /* open upvalues are never black */ | 263 | return; /* open upvalues remain gray */ |
264 | size = sizeof(UpVal); | ||
265 | break; | ||
266 | } | ||
267 | case LUA_TLCL: { | ||
268 | gco2lcl(o)->gclist = g->gray; | ||
269 | g->gray = o; | ||
88 | return; | 270 | return; |
89 | } | 271 | } |
90 | case LUA_TFUNCTION: { | 272 | case LUA_TCCL: { |
91 | gco2cl(o)->c.gclist = g->gray; | 273 | gco2ccl(o)->gclist = g->gray; |
92 | g->gray = o; | 274 | g->gray = o; |
93 | break; | 275 | return; |
94 | } | 276 | } |
95 | case LUA_TTABLE: { | 277 | case LUA_TTABLE: { |
96 | gco2h(o)->gclist = g->gray; | 278 | linktable(gco2t(o), &g->gray); |
97 | g->gray = o; | 279 | return; |
98 | break; | ||
99 | } | 280 | } |
100 | case LUA_TTHREAD: { | 281 | case LUA_TTHREAD: { |
101 | gco2th(o)->gclist = g->gray; | 282 | gco2th(o)->gclist = g->gray; |
102 | g->gray = o; | 283 | g->gray = o; |
103 | break; | 284 | return; |
104 | } | 285 | } |
105 | case LUA_TPROTO: { | 286 | case LUA_TPROTO: { |
106 | gco2p(o)->gclist = g->gray; | 287 | gco2p(o)->gclist = g->gray; |
107 | g->gray = o; | 288 | g->gray = o; |
108 | break; | 289 | return; |
109 | } | 290 | } |
110 | default: lua_assert(0); | 291 | default: lua_assert(0); return; |
111 | } | 292 | } |
293 | gray2black(o); | ||
294 | g->GCmemtrav += size; | ||
295 | } | ||
296 | |||
297 | |||
298 | /* | ||
299 | ** mark metamethods for basic types | ||
300 | */ | ||
301 | static void markmt (global_State *g) { | ||
302 | int i; | ||
303 | for (i=0; i < LUA_NUMTAGS; i++) | ||
304 | markobject(g, g->mt[i]); | ||
112 | } | 305 | } |
113 | 306 | ||
114 | 307 | ||
115 | static void marktmu (global_State *g) { | 308 | /* |
116 | GCObject *u = g->tmudata; | 309 | ** mark all objects in list of being-finalized |
117 | if (u) { | 310 | */ |
118 | do { | 311 | static void markbeingfnz (global_State *g) { |
119 | u = u->gch.next; | 312 | GCObject *o; |
120 | makewhite(g, u); /* may be marked, if left from previous GC */ | 313 | for (o = g->tobefnz; o != NULL; o = gch(o)->next) { |
121 | reallymarkobject(g, u); | 314 | makewhite(g, o); |
122 | } while (u != g->tmudata); | 315 | reallymarkobject(g, o); |
123 | } | 316 | } |
124 | } | 317 | } |
125 | 318 | ||
126 | 319 | ||
127 | /* move `dead' udata that need finalization to list `tmudata' */ | 320 | /* |
128 | size_t luaC_separateudata (lua_State *L, int all) { | 321 | ** mark all values stored in marked open upvalues. (See comment in |
129 | global_State *g = G(L); | 322 | ** 'lstate.h'.) |
130 | size_t deadmem = 0; | 323 | */ |
131 | GCObject **p = &g->mainthread->next; | 324 | static void remarkupvals (global_State *g) { |
132 | GCObject *curr; | 325 | UpVal *uv; |
133 | while ((curr = *p) != NULL) { | 326 | for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) { |
134 | if (!(iswhite(curr) || all) || isfinalized(gco2u(curr))) | 327 | if (isgray(obj2gco(uv))) |
135 | p = &curr->gch.next; /* don't bother with them */ | 328 | markvalue(g, uv->v); |
136 | else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) { | ||
137 | markfinalized(gco2u(curr)); /* don't need finalization */ | ||
138 | p = &curr->gch.next; | ||
139 | } | ||
140 | else { /* must call its gc method */ | ||
141 | deadmem += sizeudata(gco2u(curr)); | ||
142 | markfinalized(gco2u(curr)); | ||
143 | *p = curr->gch.next; | ||
144 | /* link `curr' at the end of `tmudata' list */ | ||
145 | if (g->tmudata == NULL) /* list is empty? */ | ||
146 | g->tmudata = curr->gch.next = curr; /* creates a circular list */ | ||
147 | else { | ||
148 | curr->gch.next = g->tmudata->gch.next; | ||
149 | g->tmudata->gch.next = curr; | ||
150 | g->tmudata = curr; | ||
151 | } | ||
152 | } | ||
153 | } | 329 | } |
154 | return deadmem; | ||
155 | } | 330 | } |
156 | 331 | ||
157 | 332 | ||
158 | static int traversetable (global_State *g, Table *h) { | 333 | /* |
159 | int i; | 334 | ** mark root set and reset all gray lists, to start a new |
160 | int weakkey = 0; | 335 | ** incremental (or full) collection |
161 | int weakvalue = 0; | 336 | */ |
162 | const TValue *mode; | 337 | static void restartcollection (global_State *g) { |
163 | if (h->metatable) | 338 | g->gray = g->grayagain = NULL; |
164 | markobject(g, h->metatable); | 339 | g->weak = g->allweak = g->ephemeron = NULL; |
165 | mode = gfasttm(g, h->metatable, TM_MODE); | 340 | markobject(g, g->mainthread); |
166 | if (mode && ttisstring(mode)) { /* is there a weak mode? */ | 341 | markvalue(g, &g->l_registry); |
167 | weakkey = (strchr(svalue(mode), 'k') != NULL); | 342 | markmt(g); |
168 | weakvalue = (strchr(svalue(mode), 'v') != NULL); | 343 | markbeingfnz(g); /* mark any finalizing object left from previous cycle */ |
169 | if (weakkey || weakvalue) { /* is really weak? */ | 344 | } |
170 | h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */ | 345 | |
171 | h->marked |= cast_byte((weakkey << KEYWEAKBIT) | | 346 | /* }====================================================== */ |
172 | (weakvalue << VALUEWEAKBIT)); | 347 | |
173 | h->gclist = g->weak; /* must be cleared after GC, ... */ | 348 | |
174 | g->weak = obj2gco(h); /* ... so put in the appropriate list */ | 349 | /* |
175 | } | 350 | ** {====================================================== |
176 | } | 351 | ** Traverse functions |
177 | if (weakkey && weakvalue) return 1; | 352 | ** ======================================================= |
178 | if (!weakvalue) { | 353 | */ |
179 | i = h->sizearray; | 354 | |
180 | while (i--) | 355 | static void traverseweakvalue (global_State *g, Table *h) { |
181 | markvalue(g, &h->array[i]); | 356 | Node *n, *limit = gnodelast(h); |
182 | } | 357 | /* if there is array part, assume it may have white values (do not |
183 | i = sizenode(h); | 358 | traverse it just to check) */ |
184 | while (i--) { | 359 | int hasclears = (h->sizearray > 0); |
185 | Node *n = gnode(h, i); | 360 | for (n = gnode(h, 0); n < limit; n++) { |
186 | lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n))); | 361 | checkdeadkey(n); |
187 | if (ttisnil(gval(n))) | 362 | if (ttisnil(gval(n))) /* entry is empty? */ |
188 | removeentry(n); /* remove empty entries */ | 363 | removeentry(n); /* remove it */ |
189 | else { | 364 | else { |
190 | lua_assert(!ttisnil(gkey(n))); | 365 | lua_assert(!ttisnil(gkey(n))); |
191 | if (!weakkey) markvalue(g, gkey(n)); | 366 | markvalue(g, gkey(n)); /* mark key */ |
192 | if (!weakvalue) markvalue(g, gval(n)); | 367 | if (!hasclears && iscleared(g, gval(n))) /* is there a white value? */ |
368 | hasclears = 1; /* table will have to be cleared */ | ||
193 | } | 369 | } |
194 | } | 370 | } |
195 | return weakkey || weakvalue; | 371 | if (hasclears) |
372 | linktable(h, &g->weak); /* has to be cleared later */ | ||
373 | else /* no white values */ | ||
374 | linktable(h, &g->grayagain); /* no need to clean */ | ||
196 | } | 375 | } |
197 | 376 | ||
198 | 377 | ||
199 | /* | 378 | static int traverseephemeron (global_State *g, Table *h) { |
200 | ** All marks are conditional because a GC may happen while the | 379 | int marked = 0; /* true if an object is marked in this traversal */ |
201 | ** prototype is still being created | 380 | int hasclears = 0; /* true if table has white keys */ |
202 | */ | 381 | int prop = 0; /* true if table has entry "white-key -> white-value" */ |
203 | static void traverseproto (global_State *g, Proto *f) { | 382 | Node *n, *limit = gnodelast(h); |
204 | int i; | 383 | int i; |
205 | if (f->source) stringmark(f->source); | 384 | /* traverse array part (numeric keys are 'strong') */ |
206 | for (i=0; i<f->sizek; i++) /* mark literals */ | 385 | for (i = 0; i < h->sizearray; i++) { |
207 | markvalue(g, &f->k[i]); | 386 | if (valiswhite(&h->array[i])) { |
208 | for (i=0; i<f->sizeupvalues; i++) { /* mark upvalue names */ | 387 | marked = 1; |
209 | if (f->upvalues[i]) | 388 | reallymarkobject(g, gcvalue(&h->array[i])); |
210 | stringmark(f->upvalues[i]); | 389 | } |
211 | } | ||
212 | for (i=0; i<f->sizep; i++) { /* mark nested protos */ | ||
213 | if (f->p[i]) | ||
214 | markobject(g, f->p[i]); | ||
215 | } | 390 | } |
216 | for (i=0; i<f->sizelocvars; i++) { /* mark local-variable names */ | 391 | /* traverse hash part */ |
217 | if (f->locvars[i].varname) | 392 | for (n = gnode(h, 0); n < limit; n++) { |
218 | stringmark(f->locvars[i].varname); | 393 | checkdeadkey(n); |
394 | if (ttisnil(gval(n))) /* entry is empty? */ | ||
395 | removeentry(n); /* remove it */ | ||
396 | else if (iscleared(g, gkey(n))) { /* key is not marked (yet)? */ | ||
397 | hasclears = 1; /* table must be cleared */ | ||
398 | if (valiswhite(gval(n))) /* value not marked yet? */ | ||
399 | prop = 1; /* must propagate again */ | ||
400 | } | ||
401 | else if (valiswhite(gval(n))) { /* value not marked yet? */ | ||
402 | marked = 1; | ||
403 | reallymarkobject(g, gcvalue(gval(n))); /* mark it now */ | ||
404 | } | ||
219 | } | 405 | } |
406 | if (prop) | ||
407 | linktable(h, &g->ephemeron); /* have to propagate again */ | ||
408 | else if (hasclears) /* does table have white keys? */ | ||
409 | linktable(h, &g->allweak); /* may have to clean white keys */ | ||
410 | else /* no white keys */ | ||
411 | linktable(h, &g->grayagain); /* no need to clean */ | ||
412 | return marked; | ||
220 | } | 413 | } |
221 | 414 | ||
222 | 415 | ||
223 | 416 | static void traversestrongtable (global_State *g, Table *h) { | |
224 | static void traverseclosure (global_State *g, Closure *cl) { | 417 | Node *n, *limit = gnodelast(h); |
225 | markobject(g, cl->c.env); | 418 | int i; |
226 | if (cl->c.isC) { | 419 | for (i = 0; i < h->sizearray; i++) /* traverse array part */ |
227 | int i; | 420 | markvalue(g, &h->array[i]); |
228 | for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */ | 421 | for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ |
229 | markvalue(g, &cl->c.upvalue[i]); | 422 | checkdeadkey(n); |
423 | if (ttisnil(gval(n))) /* entry is empty? */ | ||
424 | removeentry(n); /* remove it */ | ||
425 | else { | ||
426 | lua_assert(!ttisnil(gkey(n))); | ||
427 | markvalue(g, gkey(n)); /* mark key */ | ||
428 | markvalue(g, gval(n)); /* mark value */ | ||
429 | } | ||
230 | } | 430 | } |
231 | else { | 431 | } |
232 | int i; | 432 | |
233 | lua_assert(cl->l.nupvalues == cl->l.p->nups); | 433 | |
234 | markobject(g, cl->l.p); | 434 | static lu_mem traversetable (global_State *g, Table *h) { |
235 | for (i=0; i<cl->l.nupvalues; i++) /* mark its upvalues */ | 435 | const char *weakkey, *weakvalue; |
236 | markobject(g, cl->l.upvals[i]); | 436 | const TValue *mode = gfasttm(g, h->metatable, TM_MODE); |
437 | markobject(g, h->metatable); | ||
438 | if (mode && ttisstring(mode) && /* is there a weak mode? */ | ||
439 | ((weakkey = strchr(svalue(mode), 'k')), | ||
440 | (weakvalue = strchr(svalue(mode), 'v')), | ||
441 | (weakkey || weakvalue))) { /* is really weak? */ | ||
442 | black2gray(obj2gco(h)); /* keep table gray */ | ||
443 | if (!weakkey) /* strong keys? */ | ||
444 | traverseweakvalue(g, h); | ||
445 | else if (!weakvalue) /* strong values? */ | ||
446 | traverseephemeron(g, h); | ||
447 | else /* all weak */ | ||
448 | linktable(h, &g->allweak); /* nothing to traverse now */ | ||
237 | } | 449 | } |
450 | else /* not weak */ | ||
451 | traversestrongtable(g, h); | ||
452 | return sizeof(Table) + sizeof(TValue) * h->sizearray + | ||
453 | sizeof(Node) * cast(size_t, sizenode(h)); | ||
238 | } | 454 | } |
239 | 455 | ||
240 | 456 | ||
241 | static void checkstacksizes (lua_State *L, StkId max) { | 457 | static int traverseproto (global_State *g, Proto *f) { |
242 | int ci_used = cast_int(L->ci - L->base_ci); /* number of `ci' in use */ | 458 | int i; |
243 | int s_used = cast_int(max - L->stack); /* part of stack in use */ | 459 | if (f->cache && iswhite(obj2gco(f->cache))) |
244 | if (L->size_ci > LUAI_MAXCALLS) /* handling overflow? */ | 460 | f->cache = NULL; /* allow cache to be collected */ |
245 | return; /* do not touch the stacks */ | 461 | markobject(g, f->source); |
246 | if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci) | 462 | for (i = 0; i < f->sizek; i++) /* mark literals */ |
247 | luaD_reallocCI(L, L->size_ci/2); /* still big enough... */ | 463 | markvalue(g, &f->k[i]); |
248 | condhardstacktests(luaD_reallocCI(L, ci_used + 1)); | 464 | for (i = 0; i < f->sizeupvalues; i++) /* mark upvalue names */ |
249 | if (4*s_used < L->stacksize && | 465 | markobject(g, f->upvalues[i].name); |
250 | 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize) | 466 | for (i = 0; i < f->sizep; i++) /* mark nested protos */ |
251 | luaD_reallocstack(L, L->stacksize/2); /* still big enough... */ | 467 | markobject(g, f->p[i]); |
252 | condhardstacktests(luaD_reallocstack(L, s_used)); | 468 | for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */ |
469 | markobject(g, f->locvars[i].varname); | ||
470 | return sizeof(Proto) + sizeof(Instruction) * f->sizecode + | ||
471 | sizeof(Proto *) * f->sizep + | ||
472 | sizeof(TValue) * f->sizek + | ||
473 | sizeof(int) * f->sizelineinfo + | ||
474 | sizeof(LocVar) * f->sizelocvars + | ||
475 | sizeof(Upvaldesc) * f->sizeupvalues; | ||
253 | } | 476 | } |
254 | 477 | ||
255 | 478 | ||
256 | static void traversestack (global_State *g, lua_State *l) { | 479 | static lu_mem traverseCclosure (global_State *g, CClosure *cl) { |
257 | StkId o, lim; | 480 | int i; |
258 | CallInfo *ci; | 481 | for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ |
259 | markvalue(g, gt(l)); | 482 | markvalue(g, &cl->upvalue[i]); |
260 | lim = l->top; | 483 | return sizeCclosure(cl->nupvalues); |
261 | for (ci = l->base_ci; ci <= l->ci; ci++) { | 484 | } |
262 | lua_assert(ci->top <= l->stack_last); | 485 | |
263 | if (lim < ci->top) lim = ci->top; | 486 | static lu_mem traverseLclosure (global_State *g, LClosure *cl) { |
264 | } | 487 | int i; |
265 | for (o = l->stack; o < l->top; o++) | 488 | markobject(g, cl->p); /* mark its prototype */ |
489 | for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ | ||
490 | markobject(g, cl->upvals[i]); | ||
491 | return sizeLclosure(cl->nupvalues); | ||
492 | } | ||
493 | |||
494 | |||
495 | static lu_mem traversestack (global_State *g, lua_State *th) { | ||
496 | int n = 0; | ||
497 | StkId o = th->stack; | ||
498 | if (o == NULL) | ||
499 | return 1; /* stack not completely built yet */ | ||
500 | for (; o < th->top; o++) /* mark live elements in the stack */ | ||
266 | markvalue(g, o); | 501 | markvalue(g, o); |
267 | for (; o <= lim; o++) | 502 | if (g->gcstate == GCSatomic) { /* final traversal? */ |
268 | setnilvalue(o); | 503 | StkId lim = th->stack + th->stacksize; /* real end of stack */ |
269 | checkstacksizes(l, lim); | 504 | for (; o < lim; o++) /* clear not-marked stack slice */ |
505 | setnilvalue(o); | ||
506 | } | ||
507 | else { /* count call infos to compute size */ | ||
508 | CallInfo *ci; | ||
509 | for (ci = &th->base_ci; ci != th->ci; ci = ci->next) | ||
510 | n++; | ||
511 | } | ||
512 | return sizeof(lua_State) + sizeof(TValue) * th->stacksize + | ||
513 | sizeof(CallInfo) * n; | ||
270 | } | 514 | } |
271 | 515 | ||
272 | 516 | ||
273 | /* | 517 | /* |
274 | ** traverse one gray object, turning it to black. | 518 | ** traverse one gray object, turning it to black (except for threads, |
275 | ** Returns `quantity' traversed. | 519 | ** which are always gray). |
276 | */ | 520 | */ |
277 | static l_mem propagatemark (global_State *g) { | 521 | static void propagatemark (global_State *g) { |
522 | lu_mem size; | ||
278 | GCObject *o = g->gray; | 523 | GCObject *o = g->gray; |
279 | lua_assert(isgray(o)); | 524 | lua_assert(isgray(o)); |
280 | gray2black(o); | 525 | gray2black(o); |
281 | switch (o->gch.tt) { | 526 | switch (gch(o)->tt) { |
282 | case LUA_TTABLE: { | 527 | case LUA_TTABLE: { |
283 | Table *h = gco2h(o); | 528 | Table *h = gco2t(o); |
284 | g->gray = h->gclist; | 529 | g->gray = h->gclist; /* remove from 'gray' list */ |
285 | if (traversetable(g, h)) /* table is weak? */ | 530 | size = traversetable(g, h); |
286 | black2gray(o); /* keep it gray */ | 531 | break; |
287 | return sizeof(Table) + sizeof(TValue) * h->sizearray + | 532 | } |
288 | sizeof(Node) * sizenode(h); | 533 | case LUA_TLCL: { |
289 | } | 534 | LClosure *cl = gco2lcl(o); |
290 | case LUA_TFUNCTION: { | 535 | g->gray = cl->gclist; /* remove from 'gray' list */ |
291 | Closure *cl = gco2cl(o); | 536 | size = traverseLclosure(g, cl); |
292 | g->gray = cl->c.gclist; | 537 | break; |
293 | traverseclosure(g, cl); | 538 | } |
294 | return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) : | 539 | case LUA_TCCL: { |
295 | sizeLclosure(cl->l.nupvalues); | 540 | CClosure *cl = gco2ccl(o); |
541 | g->gray = cl->gclist; /* remove from 'gray' list */ | ||
542 | size = traverseCclosure(g, cl); | ||
543 | break; | ||
296 | } | 544 | } |
297 | case LUA_TTHREAD: { | 545 | case LUA_TTHREAD: { |
298 | lua_State *th = gco2th(o); | 546 | lua_State *th = gco2th(o); |
299 | g->gray = th->gclist; | 547 | g->gray = th->gclist; /* remove from 'gray' list */ |
300 | th->gclist = g->grayagain; | 548 | th->gclist = g->grayagain; |
301 | g->grayagain = o; | 549 | g->grayagain = o; /* insert into 'grayagain' list */ |
302 | black2gray(o); | 550 | black2gray(o); |
303 | traversestack(g, th); | 551 | size = traversestack(g, th); |
304 | return sizeof(lua_State) + sizeof(TValue) * th->stacksize + | 552 | break; |
305 | sizeof(CallInfo) * th->size_ci; | ||
306 | } | 553 | } |
307 | case LUA_TPROTO: { | 554 | case LUA_TPROTO: { |
308 | Proto *p = gco2p(o); | 555 | Proto *p = gco2p(o); |
309 | g->gray = p->gclist; | 556 | g->gray = p->gclist; /* remove from 'gray' list */ |
310 | traverseproto(g, p); | 557 | size = traverseproto(g, p); |
311 | return sizeof(Proto) + sizeof(Instruction) * p->sizecode + | 558 | break; |
312 | sizeof(Proto *) * p->sizep + | ||
313 | sizeof(TValue) * p->sizek + | ||
314 | sizeof(int) * p->sizelineinfo + | ||
315 | sizeof(LocVar) * p->sizelocvars + | ||
316 | sizeof(TString *) * p->sizeupvalues; | ||
317 | } | 559 | } |
318 | default: lua_assert(0); return 0; | 560 | default: lua_assert(0); return; |
319 | } | 561 | } |
562 | g->GCmemtrav += size; | ||
320 | } | 563 | } |
321 | 564 | ||
322 | 565 | ||
323 | static size_t propagateall (global_State *g) { | 566 | static void propagateall (global_State *g) { |
324 | size_t m = 0; | 567 | while (g->gray) propagatemark(g); |
325 | while (g->gray) m += propagatemark(g); | ||
326 | return m; | ||
327 | } | 568 | } |
328 | 569 | ||
329 | 570 | ||
571 | static void propagatelist (global_State *g, GCObject *l) { | ||
572 | lua_assert(g->gray == NULL); /* no grays left */ | ||
573 | g->gray = l; | ||
574 | propagateall(g); /* traverse all elements from 'l' */ | ||
575 | } | ||
576 | |||
330 | /* | 577 | /* |
331 | ** The next function tells whether a key or value can be cleared from | 578 | ** retraverse all gray lists. Because tables may be reinserted in other |
332 | ** a weak table. Non-collectable objects are never removed from weak | 579 | ** lists when traversed, traverse the original lists to avoid traversing |
333 | ** tables. Strings behave as `values', so are never removed too. for | 580 | ** twice the same table (which is not wrong, but inefficient) |
334 | ** other objects: if really collected, cannot keep them; for userdata | ||
335 | ** being finalized, keep them in keys, but not in values | ||
336 | */ | 581 | */ |
337 | static int iscleared (const TValue *o, int iskey) { | 582 | static void retraversegrays (global_State *g) { |
338 | if (!iscollectable(o)) return 0; | 583 | GCObject *weak = g->weak; /* save original lists */ |
339 | if (ttisstring(o)) { | 584 | GCObject *grayagain = g->grayagain; |
340 | stringmark(rawtsvalue(o)); /* strings are `values', so are never weak */ | 585 | GCObject *ephemeron = g->ephemeron; |
341 | return 0; | 586 | g->weak = g->grayagain = g->ephemeron = NULL; |
342 | } | 587 | propagateall(g); /* traverse main gray list */ |
343 | return iswhite(gcvalue(o)) || | 588 | propagatelist(g, grayagain); |
344 | (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o)))); | 589 | propagatelist(g, weak); |
590 | propagatelist(g, ephemeron); | ||
591 | } | ||
592 | |||
593 | |||
594 | static void convergeephemerons (global_State *g) { | ||
595 | int changed; | ||
596 | do { | ||
597 | GCObject *w; | ||
598 | GCObject *next = g->ephemeron; /* get ephemeron list */ | ||
599 | g->ephemeron = NULL; /* tables will return to this list when traversed */ | ||
600 | changed = 0; | ||
601 | while ((w = next) != NULL) { | ||
602 | next = gco2t(w)->gclist; | ||
603 | if (traverseephemeron(g, gco2t(w))) { /* traverse marked some value? */ | ||
604 | propagateall(g); /* propagate changes */ | ||
605 | changed = 1; /* will have to revisit all ephemeron tables */ | ||
606 | } | ||
607 | } | ||
608 | } while (changed); | ||
345 | } | 609 | } |
346 | 610 | ||
611 | /* }====================================================== */ | ||
612 | |||
347 | 613 | ||
348 | /* | 614 | /* |
349 | ** clear collected entries from weaktables | 615 | ** {====================================================== |
616 | ** Sweep Functions | ||
617 | ** ======================================================= | ||
350 | */ | 618 | */ |
351 | static void cleartable (GCObject *l) { | 619 | |
352 | while (l) { | 620 | |
353 | Table *h = gco2h(l); | 621 | /* |
354 | int i = h->sizearray; | 622 | ** clear entries with unmarked keys from all weaktables in list 'l' up |
355 | lua_assert(testbit(h->marked, VALUEWEAKBIT) || | 623 | ** to element 'f' |
356 | testbit(h->marked, KEYWEAKBIT)); | 624 | */ |
357 | if (testbit(h->marked, VALUEWEAKBIT)) { | 625 | static void clearkeys (global_State *g, GCObject *l, GCObject *f) { |
358 | while (i--) { | 626 | for (; l != f; l = gco2t(l)->gclist) { |
359 | TValue *o = &h->array[i]; | 627 | Table *h = gco2t(l); |
360 | if (iscleared(o, 0)) /* value was collected? */ | 628 | Node *n, *limit = gnodelast(h); |
361 | setnilvalue(o); /* remove value */ | 629 | for (n = gnode(h, 0); n < limit; n++) { |
630 | if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) { | ||
631 | setnilvalue(gval(n)); /* remove value ... */ | ||
632 | removeentry(n); /* and remove entry from table */ | ||
362 | } | 633 | } |
363 | } | 634 | } |
364 | i = sizenode(h); | 635 | } |
365 | while (i--) { | 636 | } |
366 | Node *n = gnode(h, i); | 637 | |
367 | if (!ttisnil(gval(n)) && /* non-empty entry? */ | 638 | |
368 | (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) { | 639 | /* |
640 | ** clear entries with unmarked values from all weaktables in list 'l' up | ||
641 | ** to element 'f' | ||
642 | */ | ||
643 | static void clearvalues (global_State *g, GCObject *l, GCObject *f) { | ||
644 | for (; l != f; l = gco2t(l)->gclist) { | ||
645 | Table *h = gco2t(l); | ||
646 | Node *n, *limit = gnodelast(h); | ||
647 | int i; | ||
648 | for (i = 0; i < h->sizearray; i++) { | ||
649 | TValue *o = &h->array[i]; | ||
650 | if (iscleared(g, o)) /* value was collected? */ | ||
651 | setnilvalue(o); /* remove value */ | ||
652 | } | ||
653 | for (n = gnode(h, 0); n < limit; n++) { | ||
654 | if (!ttisnil(gval(n)) && iscleared(g, gval(n))) { | ||
369 | setnilvalue(gval(n)); /* remove value ... */ | 655 | setnilvalue(gval(n)); /* remove value ... */ |
370 | removeentry(n); /* remove entry from table */ | 656 | removeentry(n); /* and remove entry from table */ |
371 | } | 657 | } |
372 | } | 658 | } |
373 | l = h->gclist; | ||
374 | } | 659 | } |
375 | } | 660 | } |
376 | 661 | ||
377 | 662 | ||
378 | static void freeobj (lua_State *L, GCObject *o) { | 663 | static void freeobj (lua_State *L, GCObject *o) { |
379 | switch (o->gch.tt) { | 664 | switch (gch(o)->tt) { |
380 | case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break; | 665 | case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break; |
381 | case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break; | 666 | case LUA_TLCL: { |
382 | case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break; | 667 | luaM_freemem(L, o, sizeLclosure(gco2lcl(o)->nupvalues)); |
383 | case LUA_TTABLE: luaH_free(L, gco2h(o)); break; | ||
384 | case LUA_TTHREAD: { | ||
385 | lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread); | ||
386 | luaE_freethread(L, gco2th(o)); | ||
387 | break; | 668 | break; |
388 | } | 669 | } |
389 | case LUA_TSTRING: { | 670 | case LUA_TCCL: { |
390 | G(L)->strt.nuse--; | 671 | luaM_freemem(L, o, sizeCclosure(gco2ccl(o)->nupvalues)); |
391 | luaM_freemem(L, o, sizestring(gco2ts(o))); | ||
392 | break; | 672 | break; |
393 | } | 673 | } |
394 | case LUA_TUSERDATA: { | 674 | case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break; |
395 | luaM_freemem(L, o, sizeudata(gco2u(o))); | 675 | case LUA_TTABLE: luaH_free(L, gco2t(o)); break; |
676 | case LUA_TTHREAD: luaE_freethread(L, gco2th(o)); break; | ||
677 | case LUA_TUSERDATA: luaM_freemem(L, o, sizeudata(gco2u(o))); break; | ||
678 | case LUA_TSHRSTR: | ||
679 | G(L)->strt.nuse--; | ||
680 | /* go through */ | ||
681 | case LUA_TLNGSTR: { | ||
682 | luaM_freemem(L, o, sizestring(gco2ts(o))); | ||
396 | break; | 683 | break; |
397 | } | 684 | } |
398 | default: lua_assert(0); | 685 | default: lua_assert(0); |
@@ -400,312 +687,534 @@ static void freeobj (lua_State *L, GCObject *o) { | |||
400 | } | 687 | } |
401 | 688 | ||
402 | 689 | ||
403 | |||
404 | #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM) | 690 | #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM) |
691 | static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count); | ||
405 | 692 | ||
406 | 693 | ||
694 | /* | ||
695 | ** sweep the (open) upvalues of a thread and resize its stack and | ||
696 | ** list of call-info structures. | ||
697 | */ | ||
698 | static void sweepthread (lua_State *L, lua_State *L1) { | ||
699 | if (L1->stack == NULL) return; /* stack not completely built yet */ | ||
700 | sweepwholelist(L, &L1->openupval); /* sweep open upvalues */ | ||
701 | luaE_freeCI(L1); /* free extra CallInfo slots */ | ||
702 | /* should not change the stack during an emergency gc cycle */ | ||
703 | if (G(L)->gckind != KGC_EMERGENCY) | ||
704 | luaD_shrinkstack(L1); | ||
705 | } | ||
706 | |||
707 | |||
708 | /* | ||
709 | ** sweep at most 'count' elements from a list of GCObjects erasing dead | ||
710 | ** objects, where a dead (not alive) object is one marked with the "old" | ||
711 | ** (non current) white and not fixed. | ||
712 | ** In non-generational mode, change all non-dead objects back to white, | ||
713 | ** preparing for next collection cycle. | ||
714 | ** In generational mode, keep black objects black, and also mark them as | ||
715 | ** old; stop when hitting an old object, as all objects after that | ||
716 | ** one will be old too. | ||
717 | ** When object is a thread, sweep its list of open upvalues too. | ||
718 | */ | ||
407 | static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) { | 719 | static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) { |
408 | GCObject *curr; | ||
409 | global_State *g = G(L); | 720 | global_State *g = G(L); |
410 | int deadmask = otherwhite(g); | 721 | int ow = otherwhite(g); |
411 | while ((curr = *p) != NULL && count-- > 0) { | 722 | int toclear, toset; /* bits to clear and to set in all live objects */ |
412 | if (curr->gch.tt == LUA_TTHREAD) /* sweep open upvalues of each thread */ | 723 | int tostop; /* stop sweep when this is true */ |
413 | sweepwholelist(L, &gco2th(curr)->openupval); | 724 | if (isgenerational(g)) { /* generational mode? */ |
414 | if ((curr->gch.marked ^ WHITEBITS) & deadmask) { /* not dead? */ | 725 | toclear = ~0; /* clear nothing */ |
415 | lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT)); | 726 | toset = bitmask(OLDBIT); /* set the old bit of all surviving objects */ |
416 | makewhite(g, curr); /* make it white (for next cycle) */ | 727 | tostop = bitmask(OLDBIT); /* do not sweep old generation */ |
417 | p = &curr->gch.next; | 728 | } |
418 | } | 729 | else { /* normal mode */ |
419 | else { /* must erase `curr' */ | 730 | toclear = maskcolors; /* clear all color bits + old bit */ |
420 | lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT)); | 731 | toset = luaC_white(g); /* make object white */ |
421 | *p = curr->gch.next; | 732 | tostop = 0; /* do not stop */ |
422 | if (curr == g->rootgc) /* is the first element of the list? */ | 733 | } |
423 | g->rootgc = curr->gch.next; /* adjust first */ | 734 | while (*p != NULL && count-- > 0) { |
424 | freeobj(L, curr); | 735 | GCObject *curr = *p; |
736 | int marked = gch(curr)->marked; | ||
737 | if (isdeadm(ow, marked)) { /* is 'curr' dead? */ | ||
738 | *p = gch(curr)->next; /* remove 'curr' from list */ | ||
739 | freeobj(L, curr); /* erase 'curr' */ | ||
740 | } | ||
741 | else { | ||
742 | if (testbits(marked, tostop)) | ||
743 | return NULL; /* stop sweeping this list */ | ||
744 | if (gch(curr)->tt == LUA_TTHREAD) | ||
745 | sweepthread(L, gco2th(curr)); /* sweep thread's upvalues */ | ||
746 | /* update marks */ | ||
747 | gch(curr)->marked = cast_byte((marked & toclear) | toset); | ||
748 | p = &gch(curr)->next; /* go to next element */ | ||
425 | } | 749 | } |
426 | } | 750 | } |
751 | return (*p == NULL) ? NULL : p; | ||
752 | } | ||
753 | |||
754 | |||
755 | /* | ||
756 | ** sweep a list until a live object (or end of list) | ||
757 | */ | ||
758 | static GCObject **sweeptolive (lua_State *L, GCObject **p, int *n) { | ||
759 | GCObject ** old = p; | ||
760 | int i = 0; | ||
761 | do { | ||
762 | i++; | ||
763 | p = sweeplist(L, p, 1); | ||
764 | } while (p == old); | ||
765 | if (n) *n += i; | ||
427 | return p; | 766 | return p; |
428 | } | 767 | } |
429 | 768 | ||
769 | /* }====================================================== */ | ||
770 | |||
771 | |||
772 | /* | ||
773 | ** {====================================================== | ||
774 | ** Finalization | ||
775 | ** ======================================================= | ||
776 | */ | ||
430 | 777 | ||
431 | static void checkSizes (lua_State *L) { | 778 | static void checkSizes (lua_State *L) { |
432 | global_State *g = G(L); | 779 | global_State *g = G(L); |
433 | /* check size of string hash */ | 780 | if (g->gckind != KGC_EMERGENCY) { /* do not change sizes in emergency */ |
434 | if (g->strt.nuse < cast(lu_int32, g->strt.size/4) && | 781 | int hs = g->strt.size / 2; /* half the size of the string table */ |
435 | g->strt.size > MINSTRTABSIZE*2) | 782 | if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */ |
436 | luaS_resize(L, g->strt.size/2); /* table is too big */ | 783 | luaS_resize(L, hs); /* halve its size */ |
437 | /* check size of buffer */ | 784 | luaZ_freebuffer(L, &g->buff); /* free concatenation buffer */ |
438 | if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) { /* buffer too big? */ | ||
439 | size_t newsize = luaZ_sizebuffer(&g->buff) / 2; | ||
440 | luaZ_resizebuffer(L, &g->buff, newsize); | ||
441 | } | 785 | } |
442 | } | 786 | } |
443 | 787 | ||
444 | 788 | ||
445 | static void GCTM (lua_State *L) { | 789 | static GCObject *udata2finalize (global_State *g) { |
790 | GCObject *o = g->tobefnz; /* get first element */ | ||
791 | lua_assert(isfinalized(o)); | ||
792 | g->tobefnz = gch(o)->next; /* remove it from 'tobefnz' list */ | ||
793 | gch(o)->next = g->allgc; /* return it to 'allgc' list */ | ||
794 | g->allgc = o; | ||
795 | resetbit(gch(o)->marked, SEPARATED); /* mark that it is not in 'tobefnz' */ | ||
796 | lua_assert(!isold(o)); /* see MOVE OLD rule */ | ||
797 | if (!keepinvariantout(g)) /* not keeping invariant? */ | ||
798 | makewhite(g, o); /* "sweep" object */ | ||
799 | return o; | ||
800 | } | ||
801 | |||
802 | |||
803 | static void dothecall (lua_State *L, void *ud) { | ||
804 | UNUSED(ud); | ||
805 | luaD_call(L, L->top - 2, 0, 0); | ||
806 | } | ||
807 | |||
808 | |||
809 | static void GCTM (lua_State *L, int propagateerrors) { | ||
446 | global_State *g = G(L); | 810 | global_State *g = G(L); |
447 | GCObject *o = g->tmudata->gch.next; /* get first element */ | ||
448 | Udata *udata = rawgco2u(o); | ||
449 | const TValue *tm; | 811 | const TValue *tm; |
450 | /* remove udata from `tmudata' */ | 812 | TValue v; |
451 | if (o == g->tmudata) /* last element? */ | 813 | setgcovalue(L, &v, udata2finalize(g)); |
452 | g->tmudata = NULL; | 814 | tm = luaT_gettmbyobj(L, &v, TM_GC); |
453 | else | 815 | if (tm != NULL && ttisfunction(tm)) { /* is there a finalizer? */ |
454 | g->tmudata->gch.next = udata->uv.next; | 816 | int status; |
455 | udata->uv.next = g->mainthread->next; /* return it to `root' list */ | ||
456 | g->mainthread->next = o; | ||
457 | makewhite(g, o); | ||
458 | tm = fasttm(L, udata->uv.metatable, TM_GC); | ||
459 | if (tm != NULL) { | ||
460 | lu_byte oldah = L->allowhook; | 817 | lu_byte oldah = L->allowhook; |
461 | lu_mem oldt = g->GCthreshold; | 818 | int running = g->gcrunning; |
462 | L->allowhook = 0; /* stop debug hooks during GC tag method */ | 819 | L->allowhook = 0; /* stop debug hooks during GC metamethod */ |
463 | g->GCthreshold = 2*g->totalbytes; /* avoid GC steps */ | 820 | g->gcrunning = 0; /* avoid GC steps */ |
464 | setobj2s(L, L->top, tm); | 821 | setobj2s(L, L->top, tm); /* push finalizer... */ |
465 | setuvalue(L, L->top+1, udata); | 822 | setobj2s(L, L->top + 1, &v); /* ... and its argument */ |
466 | L->top += 2; | 823 | L->top += 2; /* and (next line) call the finalizer */ |
467 | luaD_call(L, L->top - 2, 0); | 824 | status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top - 2), 0); |
468 | L->allowhook = oldah; /* restore hooks */ | 825 | L->allowhook = oldah; /* restore hooks */ |
469 | g->GCthreshold = oldt; /* restore threshold */ | 826 | g->gcrunning = running; /* restore state */ |
827 | if (status != LUA_OK && propagateerrors) { /* error while running __gc? */ | ||
828 | if (status == LUA_ERRRUN) { /* is there an error object? */ | ||
829 | const char *msg = (ttisstring(L->top - 1)) | ||
830 | ? svalue(L->top - 1) | ||
831 | : "no message"; | ||
832 | luaO_pushfstring(L, "error in __gc metamethod (%s)", msg); | ||
833 | status = LUA_ERRGCMM; /* error in __gc metamethod */ | ||
834 | } | ||
835 | luaD_throw(L, status); /* re-throw error */ | ||
836 | } | ||
470 | } | 837 | } |
471 | } | 838 | } |
472 | 839 | ||
473 | 840 | ||
474 | /* | 841 | /* |
475 | ** Call all GC tag methods | 842 | ** move all unreachable objects (or 'all' objects) that need |
843 | ** finalization from list 'finobj' to list 'tobefnz' (to be finalized) | ||
476 | */ | 844 | */ |
477 | void luaC_callGCTM (lua_State *L) { | 845 | static void separatetobefnz (lua_State *L, int all) { |
478 | while (G(L)->tmudata) | 846 | global_State *g = G(L); |
479 | GCTM(L); | 847 | GCObject **p = &g->finobj; |
848 | GCObject *curr; | ||
849 | GCObject **lastnext = &g->tobefnz; | ||
850 | /* find last 'next' field in 'tobefnz' list (to add elements in its end) */ | ||
851 | while (*lastnext != NULL) | ||
852 | lastnext = &gch(*lastnext)->next; | ||
853 | while ((curr = *p) != NULL) { /* traverse all finalizable objects */ | ||
854 | lua_assert(!isfinalized(curr)); | ||
855 | lua_assert(testbit(gch(curr)->marked, SEPARATED)); | ||
856 | if (!(iswhite(curr) || all)) /* not being collected? */ | ||
857 | p = &gch(curr)->next; /* don't bother with it */ | ||
858 | else { | ||
859 | l_setbit(gch(curr)->marked, FINALIZEDBIT); /* won't be finalized again */ | ||
860 | *p = gch(curr)->next; /* remove 'curr' from 'finobj' list */ | ||
861 | gch(curr)->next = *lastnext; /* link at the end of 'tobefnz' list */ | ||
862 | *lastnext = curr; | ||
863 | lastnext = &gch(curr)->next; | ||
864 | } | ||
865 | } | ||
480 | } | 866 | } |
481 | 867 | ||
482 | 868 | ||
483 | void luaC_freeall (lua_State *L) { | 869 | /* |
870 | ** if object 'o' has a finalizer, remove it from 'allgc' list (must | ||
871 | ** search the list to find it) and link it in 'finobj' list. | ||
872 | */ | ||
873 | void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) { | ||
484 | global_State *g = G(L); | 874 | global_State *g = G(L); |
485 | int i; | 875 | if (testbit(gch(o)->marked, SEPARATED) || /* obj. is already separated... */ |
486 | g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT); /* mask to collect all elements */ | 876 | isfinalized(o) || /* ... or is finalized... */ |
487 | sweepwholelist(L, &g->rootgc); | 877 | gfasttm(g, mt, TM_GC) == NULL) /* or has no finalizer? */ |
488 | for (i = 0; i < g->strt.size; i++) /* free all string lists */ | 878 | return; /* nothing to be done */ |
489 | sweepwholelist(L, &g->strt.hash[i]); | 879 | else { /* move 'o' to 'finobj' list */ |
880 | GCObject **p; | ||
881 | GCheader *ho = gch(o); | ||
882 | if (g->sweepgc == &ho->next) { /* avoid removing current sweep object */ | ||
883 | lua_assert(issweepphase(g)); | ||
884 | g->sweepgc = sweeptolive(L, g->sweepgc, NULL); | ||
885 | } | ||
886 | /* search for pointer pointing to 'o' */ | ||
887 | for (p = &g->allgc; *p != o; p = &gch(*p)->next) { /* empty */ } | ||
888 | *p = ho->next; /* remove 'o' from root list */ | ||
889 | ho->next = g->finobj; /* link it in list 'finobj' */ | ||
890 | g->finobj = o; | ||
891 | l_setbit(ho->marked, SEPARATED); /* mark it as such */ | ||
892 | if (!keepinvariantout(g)) /* not keeping invariant? */ | ||
893 | makewhite(g, o); /* "sweep" object */ | ||
894 | else | ||
895 | resetoldbit(o); /* see MOVE OLD rule */ | ||
896 | } | ||
490 | } | 897 | } |
491 | 898 | ||
899 | /* }====================================================== */ | ||
492 | 900 | ||
493 | static void markmt (global_State *g) { | 901 | |
494 | int i; | 902 | /* |
495 | for (i=0; i<NUM_TAGS; i++) | 903 | ** {====================================================== |
496 | if (g->mt[i]) markobject(g, g->mt[i]); | 904 | ** GC control |
905 | ** ======================================================= | ||
906 | */ | ||
907 | |||
908 | |||
909 | /* | ||
910 | ** set a reasonable "time" to wait before starting a new GC cycle; | ||
911 | ** cycle will start when memory use hits threshold | ||
912 | */ | ||
913 | static void setpause (global_State *g, l_mem estimate) { | ||
914 | l_mem debt, threshold; | ||
915 | estimate = estimate / PAUSEADJ; /* adjust 'estimate' */ | ||
916 | threshold = (g->gcpause < MAX_LMEM / estimate) /* overflow? */ | ||
917 | ? estimate * g->gcpause /* no overflow */ | ||
918 | : MAX_LMEM; /* overflow; truncate to maximum */ | ||
919 | debt = -cast(l_mem, threshold - gettotalbytes(g)); | ||
920 | luaE_setdebt(g, debt); | ||
497 | } | 921 | } |
498 | 922 | ||
499 | 923 | ||
500 | /* mark root set */ | 924 | #define sweepphases \ |
501 | static void markroot (lua_State *L) { | 925 | (bitmask(GCSsweepstring) | bitmask(GCSsweepudata) | bitmask(GCSsweep)) |
926 | |||
927 | |||
928 | /* | ||
929 | ** enter first sweep phase (strings) and prepare pointers for other | ||
930 | ** sweep phases. The calls to 'sweeptolive' make pointers point to an | ||
931 | ** object inside the list (instead of to the header), so that the real | ||
932 | ** sweep do not need to skip objects created between "now" and the start | ||
933 | ** of the real sweep. | ||
934 | ** Returns how many objects it swept. | ||
935 | */ | ||
936 | static int entersweep (lua_State *L) { | ||
502 | global_State *g = G(L); | 937 | global_State *g = G(L); |
503 | g->gray = NULL; | 938 | int n = 0; |
504 | g->grayagain = NULL; | 939 | g->gcstate = GCSsweepstring; |
505 | g->weak = NULL; | 940 | lua_assert(g->sweepgc == NULL && g->sweepfin == NULL); |
506 | markobject(g, g->mainthread); | 941 | /* prepare to sweep strings, finalizable objects, and regular objects */ |
507 | /* make global table be traversed before main stack */ | 942 | g->sweepstrgc = 0; |
508 | markvalue(g, gt(g->mainthread)); | 943 | g->sweepfin = sweeptolive(L, &g->finobj, &n); |
509 | markvalue(g, registry(L)); | 944 | g->sweepgc = sweeptolive(L, &g->allgc, &n); |
510 | markmt(g); | 945 | return n; |
511 | g->gcstate = GCSpropagate; | ||
512 | } | 946 | } |
513 | 947 | ||
514 | 948 | ||
515 | static void remarkupvals (global_State *g) { | 949 | /* |
516 | UpVal *uv; | 950 | ** change GC mode |
517 | for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) { | 951 | */ |
518 | lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv); | 952 | void luaC_changemode (lua_State *L, int mode) { |
519 | if (isgray(obj2gco(uv))) | 953 | global_State *g = G(L); |
520 | markvalue(g, uv->v); | 954 | if (mode == g->gckind) return; /* nothing to change */ |
955 | if (mode == KGC_GEN) { /* change to generational mode */ | ||
956 | /* make sure gray lists are consistent */ | ||
957 | luaC_runtilstate(L, bitmask(GCSpropagate)); | ||
958 | g->GCestimate = gettotalbytes(g); | ||
959 | g->gckind = KGC_GEN; | ||
960 | } | ||
961 | else { /* change to incremental mode */ | ||
962 | /* sweep all objects to turn them back to white | ||
963 | (as white has not changed, nothing extra will be collected) */ | ||
964 | g->gckind = KGC_NORMAL; | ||
965 | entersweep(L); | ||
966 | luaC_runtilstate(L, ~sweepphases); | ||
521 | } | 967 | } |
522 | } | 968 | } |
523 | 969 | ||
524 | 970 | ||
525 | static void atomic (lua_State *L) { | 971 | /* |
972 | ** call all pending finalizers | ||
973 | */ | ||
974 | static void callallpendingfinalizers (lua_State *L, int propagateerrors) { | ||
526 | global_State *g = G(L); | 975 | global_State *g = G(L); |
527 | size_t udsize; /* total size of userdata to be finalized */ | 976 | while (g->tobefnz) { |
528 | /* remark occasional upvalues of (maybe) dead threads */ | 977 | resetoldbit(g->tobefnz); |
529 | remarkupvals(g); | 978 | GCTM(L, propagateerrors); |
530 | /* traverse objects cautch by write barrier and by 'remarkupvals' */ | 979 | } |
531 | propagateall(g); | 980 | } |
532 | /* remark weak tables */ | 981 | |
533 | g->gray = g->weak; | 982 | |
534 | g->weak = NULL; | 983 | void luaC_freeallobjects (lua_State *L) { |
984 | global_State *g = G(L); | ||
985 | int i; | ||
986 | separatetobefnz(L, 1); /* separate all objects with finalizers */ | ||
987 | lua_assert(g->finobj == NULL); | ||
988 | callallpendingfinalizers(L, 0); | ||
989 | g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */ | ||
990 | g->gckind = KGC_NORMAL; | ||
991 | sweepwholelist(L, &g->finobj); /* finalizers can create objs. in 'finobj' */ | ||
992 | sweepwholelist(L, &g->allgc); | ||
993 | for (i = 0; i < g->strt.size; i++) /* free all string lists */ | ||
994 | sweepwholelist(L, &g->strt.hash[i]); | ||
995 | lua_assert(g->strt.nuse == 0); | ||
996 | } | ||
997 | |||
998 | |||
999 | static l_mem atomic (lua_State *L) { | ||
1000 | global_State *g = G(L); | ||
1001 | l_mem work = -cast(l_mem, g->GCmemtrav); /* start counting work */ | ||
1002 | GCObject *origweak, *origall; | ||
535 | lua_assert(!iswhite(obj2gco(g->mainthread))); | 1003 | lua_assert(!iswhite(obj2gco(g->mainthread))); |
536 | markobject(g, L); /* mark running thread */ | 1004 | markobject(g, L); /* mark running thread */ |
537 | markmt(g); /* mark basic metatables (again) */ | 1005 | /* registry and global metatables may be changed by API */ |
538 | propagateall(g); | 1006 | markvalue(g, &g->l_registry); |
539 | /* remark gray again */ | 1007 | markmt(g); /* mark basic metatables */ |
540 | g->gray = g->grayagain; | 1008 | /* remark occasional upvalues of (maybe) dead threads */ |
541 | g->grayagain = NULL; | 1009 | remarkupvals(g); |
542 | propagateall(g); | 1010 | propagateall(g); /* propagate changes */ |
543 | udsize = luaC_separateudata(L, 0); /* separate userdata to be finalized */ | 1011 | work += g->GCmemtrav; /* stop counting (do not (re)count grays) */ |
544 | marktmu(g); /* mark `preserved' userdata */ | 1012 | /* traverse objects caught by write barrier and by 'remarkupvals' */ |
545 | udsize += propagateall(g); /* remark, to propagate `preserveness' */ | 1013 | retraversegrays(g); |
546 | cleartable(g->weak); /* remove collected objects from weak tables */ | 1014 | work -= g->GCmemtrav; /* restart counting */ |
547 | /* flip current white */ | 1015 | convergeephemerons(g); |
548 | g->currentwhite = cast_byte(otherwhite(g)); | 1016 | /* at this point, all strongly accessible objects are marked. */ |
549 | g->sweepstrgc = 0; | 1017 | /* clear values from weak tables, before checking finalizers */ |
550 | g->sweepgc = &g->rootgc; | 1018 | clearvalues(g, g->weak, NULL); |
551 | g->gcstate = GCSsweepstring; | 1019 | clearvalues(g, g->allweak, NULL); |
552 | g->estimate = g->totalbytes - udsize; /* first estimate */ | 1020 | origweak = g->weak; origall = g->allweak; |
1021 | work += g->GCmemtrav; /* stop counting (objects being finalized) */ | ||
1022 | separatetobefnz(L, 0); /* separate objects to be finalized */ | ||
1023 | markbeingfnz(g); /* mark objects that will be finalized */ | ||
1024 | propagateall(g); /* remark, to propagate `preserveness' */ | ||
1025 | work -= g->GCmemtrav; /* restart counting */ | ||
1026 | convergeephemerons(g); | ||
1027 | /* at this point, all resurrected objects are marked. */ | ||
1028 | /* remove dead objects from weak tables */ | ||
1029 | clearkeys(g, g->ephemeron, NULL); /* clear keys from all ephemeron tables */ | ||
1030 | clearkeys(g, g->allweak, NULL); /* clear keys from all allweak tables */ | ||
1031 | /* clear values from resurrected weak tables */ | ||
1032 | clearvalues(g, g->weak, origweak); | ||
1033 | clearvalues(g, g->allweak, origall); | ||
1034 | g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ | ||
1035 | work += g->GCmemtrav; /* complete counting */ | ||
1036 | return work; /* estimate of memory marked by 'atomic' */ | ||
553 | } | 1037 | } |
554 | 1038 | ||
555 | 1039 | ||
556 | static l_mem singlestep (lua_State *L) { | 1040 | static lu_mem singlestep (lua_State *L) { |
557 | global_State *g = G(L); | 1041 | global_State *g = G(L); |
558 | /*lua_checkmemory(L);*/ | ||
559 | switch (g->gcstate) { | 1042 | switch (g->gcstate) { |
560 | case GCSpause: { | 1043 | case GCSpause: { |
561 | markroot(L); /* start a new collection */ | 1044 | /* start to count memory traversed */ |
562 | return 0; | 1045 | g->GCmemtrav = g->strt.size * sizeof(GCObject*); |
1046 | lua_assert(!isgenerational(g)); | ||
1047 | restartcollection(g); | ||
1048 | g->gcstate = GCSpropagate; | ||
1049 | return g->GCmemtrav; | ||
563 | } | 1050 | } |
564 | case GCSpropagate: { | 1051 | case GCSpropagate: { |
565 | if (g->gray) | 1052 | if (g->gray) { |
566 | return propagatemark(g); | 1053 | lu_mem oldtrav = g->GCmemtrav; |
1054 | propagatemark(g); | ||
1055 | return g->GCmemtrav - oldtrav; /* memory traversed in this step */ | ||
1056 | } | ||
567 | else { /* no more `gray' objects */ | 1057 | else { /* no more `gray' objects */ |
568 | atomic(L); /* finish mark phase */ | 1058 | lu_mem work; |
569 | return 0; | 1059 | int sw; |
1060 | g->gcstate = GCSatomic; /* finish mark phase */ | ||
1061 | g->GCestimate = g->GCmemtrav; /* save what was counted */; | ||
1062 | work = atomic(L); /* add what was traversed by 'atomic' */ | ||
1063 | g->GCestimate += work; /* estimate of total memory traversed */ | ||
1064 | sw = entersweep(L); | ||
1065 | return work + sw * GCSWEEPCOST; | ||
570 | } | 1066 | } |
571 | } | 1067 | } |
572 | case GCSsweepstring: { | 1068 | case GCSsweepstring: { |
573 | lu_mem old = g->totalbytes; | 1069 | int i; |
574 | sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]); | 1070 | for (i = 0; i < GCSWEEPMAX && g->sweepstrgc + i < g->strt.size; i++) |
575 | if (g->sweepstrgc >= g->strt.size) /* nothing more to sweep? */ | 1071 | sweepwholelist(L, &g->strt.hash[g->sweepstrgc + i]); |
576 | g->gcstate = GCSsweep; /* end sweep-string phase */ | 1072 | g->sweepstrgc += i; |
577 | lua_assert(old >= g->totalbytes); | 1073 | if (g->sweepstrgc >= g->strt.size) /* no more strings to sweep? */ |
578 | g->estimate -= old - g->totalbytes; | 1074 | g->gcstate = GCSsweepudata; |
579 | return GCSWEEPCOST; | 1075 | return i * GCSWEEPCOST; |
580 | } | 1076 | } |
581 | case GCSsweep: { | 1077 | case GCSsweepudata: { |
582 | lu_mem old = g->totalbytes; | 1078 | if (g->sweepfin) { |
583 | g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX); | 1079 | g->sweepfin = sweeplist(L, g->sweepfin, GCSWEEPMAX); |
584 | if (*g->sweepgc == NULL) { /* nothing more to sweep? */ | 1080 | return GCSWEEPMAX*GCSWEEPCOST; |
585 | checkSizes(L); | ||
586 | g->gcstate = GCSfinalize; /* end sweep phase */ | ||
587 | } | ||
588 | lua_assert(old >= g->totalbytes); | ||
589 | g->estimate -= old - g->totalbytes; | ||
590 | return GCSWEEPMAX*GCSWEEPCOST; | ||
591 | } | ||
592 | case GCSfinalize: { | ||
593 | if (g->tmudata) { | ||
594 | GCTM(L); | ||
595 | if (g->estimate > GCFINALIZECOST) | ||
596 | g->estimate -= GCFINALIZECOST; | ||
597 | return GCFINALIZECOST; | ||
598 | } | 1081 | } |
599 | else { | 1082 | else { |
600 | g->gcstate = GCSpause; /* end collection */ | 1083 | g->gcstate = GCSsweep; |
601 | g->gcdept = 0; | ||
602 | return 0; | 1084 | return 0; |
603 | } | 1085 | } |
604 | } | 1086 | } |
1087 | case GCSsweep: { | ||
1088 | if (g->sweepgc) { | ||
1089 | g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX); | ||
1090 | return GCSWEEPMAX*GCSWEEPCOST; | ||
1091 | } | ||
1092 | else { | ||
1093 | /* sweep main thread */ | ||
1094 | GCObject *mt = obj2gco(g->mainthread); | ||
1095 | sweeplist(L, &mt, 1); | ||
1096 | checkSizes(L); | ||
1097 | g->gcstate = GCSpause; /* finish collection */ | ||
1098 | return GCSWEEPCOST; | ||
1099 | } | ||
1100 | } | ||
605 | default: lua_assert(0); return 0; | 1101 | default: lua_assert(0); return 0; |
606 | } | 1102 | } |
607 | } | 1103 | } |
608 | 1104 | ||
609 | 1105 | ||
610 | void luaC_step (lua_State *L) { | 1106 | /* |
1107 | ** advances the garbage collector until it reaches a state allowed | ||
1108 | ** by 'statemask' | ||
1109 | */ | ||
1110 | void luaC_runtilstate (lua_State *L, int statesmask) { | ||
611 | global_State *g = G(L); | 1111 | global_State *g = G(L); |
612 | l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul; | 1112 | while (!testbit(statesmask, g->gcstate)) |
613 | if (lim == 0) | 1113 | singlestep(L); |
614 | lim = (MAX_LUMEM-1)/2; /* no limit */ | ||
615 | g->gcdept += g->totalbytes - g->GCthreshold; | ||
616 | do { | ||
617 | lim -= singlestep(L); | ||
618 | if (g->gcstate == GCSpause) | ||
619 | break; | ||
620 | } while (lim > 0); | ||
621 | if (g->gcstate != GCSpause) { | ||
622 | if (g->gcdept < GCSTEPSIZE) | ||
623 | g->GCthreshold = g->totalbytes + GCSTEPSIZE; /* - lim/g->gcstepmul;*/ | ||
624 | else { | ||
625 | g->gcdept -= GCSTEPSIZE; | ||
626 | g->GCthreshold = g->totalbytes; | ||
627 | } | ||
628 | } | ||
629 | else { | ||
630 | lua_assert(g->totalbytes >= g->estimate); | ||
631 | setthreshold(g); | ||
632 | } | ||
633 | } | 1114 | } |
634 | 1115 | ||
635 | 1116 | ||
636 | void luaC_fullgc (lua_State *L) { | 1117 | static void generationalcollection (lua_State *L) { |
637 | global_State *g = G(L); | 1118 | global_State *g = G(L); |
638 | if (g->gcstate <= GCSpropagate) { | 1119 | lua_assert(g->gcstate == GCSpropagate); |
639 | /* reset sweep marks to sweep all elements (returning them to white) */ | 1120 | if (g->GCestimate == 0) { /* signal for another major collection? */ |
640 | g->sweepstrgc = 0; | 1121 | luaC_fullgc(L, 0); /* perform a full regular collection */ |
641 | g->sweepgc = &g->rootgc; | 1122 | g->GCestimate = gettotalbytes(g); /* update control */ |
642 | /* reset other collector lists */ | ||
643 | g->gray = NULL; | ||
644 | g->grayagain = NULL; | ||
645 | g->weak = NULL; | ||
646 | g->gcstate = GCSsweepstring; | ||
647 | } | ||
648 | lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate); | ||
649 | /* finish any pending sweep phase */ | ||
650 | while (g->gcstate != GCSfinalize) { | ||
651 | lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep); | ||
652 | singlestep(L); | ||
653 | } | 1123 | } |
654 | markroot(L); | 1124 | else { |
655 | while (g->gcstate != GCSpause) { | 1125 | lu_mem estimate = g->GCestimate; |
656 | singlestep(L); | 1126 | luaC_runtilstate(L, bitmask(GCSpause)); /* run complete (minor) cycle */ |
1127 | g->gcstate = GCSpropagate; /* skip restart */ | ||
1128 | if (gettotalbytes(g) > (estimate / 100) * g->gcmajorinc) | ||
1129 | g->GCestimate = 0; /* signal for a major collection */ | ||
1130 | else | ||
1131 | g->GCestimate = estimate; /* keep estimate from last major coll. */ | ||
1132 | |||
657 | } | 1133 | } |
658 | setthreshold(g); | 1134 | setpause(g, gettotalbytes(g)); |
1135 | lua_assert(g->gcstate == GCSpropagate); | ||
659 | } | 1136 | } |
660 | 1137 | ||
661 | 1138 | ||
662 | void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) { | 1139 | static void incstep (lua_State *L) { |
663 | global_State *g = G(L); | 1140 | global_State *g = G(L); |
664 | lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o)); | 1141 | l_mem debt = g->GCdebt; |
665 | lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause); | 1142 | int stepmul = g->gcstepmul; |
666 | lua_assert(ttype(&o->gch) != LUA_TTABLE); | 1143 | if (stepmul < 40) stepmul = 40; /* avoid ridiculous low values (and 0) */ |
667 | /* must keep invariant? */ | 1144 | /* convert debt from Kb to 'work units' (avoid zero debt and overflows) */ |
668 | if (g->gcstate == GCSpropagate) | 1145 | debt = (debt / STEPMULADJ) + 1; |
669 | reallymarkobject(g, v); /* restore invariant */ | 1146 | debt = (debt < MAX_LMEM / stepmul) ? debt * stepmul : MAX_LMEM; |
670 | else /* don't mind */ | 1147 | do { /* always perform at least one single step */ |
671 | makewhite(g, o); /* mark as white just to avoid other barriers */ | 1148 | lu_mem work = singlestep(L); /* do some work */ |
1149 | debt -= work; | ||
1150 | } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause); | ||
1151 | if (g->gcstate == GCSpause) | ||
1152 | setpause(g, g->GCestimate); /* pause until next cycle */ | ||
1153 | else { | ||
1154 | debt = (debt / stepmul) * STEPMULADJ; /* convert 'work units' to Kb */ | ||
1155 | luaE_setdebt(g, debt); | ||
1156 | } | ||
672 | } | 1157 | } |
673 | 1158 | ||
674 | 1159 | ||
675 | void luaC_barrierback (lua_State *L, Table *t) { | 1160 | /* |
1161 | ** performs a basic GC step | ||
1162 | */ | ||
1163 | void luaC_forcestep (lua_State *L) { | ||
676 | global_State *g = G(L); | 1164 | global_State *g = G(L); |
677 | GCObject *o = obj2gco(t); | 1165 | int i; |
678 | lua_assert(isblack(o) && !isdead(g, o)); | 1166 | if (isgenerational(g)) generationalcollection(L); |
679 | lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause); | 1167 | else incstep(L); |
680 | black2gray(o); /* make table gray (again) */ | 1168 | /* run a few finalizers (or all of them at the end of a collect cycle) */ |
681 | t->gclist = g->grayagain; | 1169 | for (i = 0; g->tobefnz && (i < GCFINALIZENUM || g->gcstate == GCSpause); i++) |
682 | g->grayagain = o; | 1170 | GCTM(L, 1); /* call one finalizer */ |
683 | } | 1171 | } |
684 | 1172 | ||
685 | 1173 | ||
686 | void luaC_link (lua_State *L, GCObject *o, lu_byte tt) { | 1174 | /* |
1175 | ** performs a basic GC step only if collector is running | ||
1176 | */ | ||
1177 | void luaC_step (lua_State *L) { | ||
687 | global_State *g = G(L); | 1178 | global_State *g = G(L); |
688 | o->gch.next = g->rootgc; | 1179 | if (g->gcrunning) luaC_forcestep(L); |
689 | g->rootgc = o; | 1180 | else luaE_setdebt(g, -GCSTEPSIZE); /* avoid being called too often */ |
690 | o->gch.marked = luaC_white(g); | ||
691 | o->gch.tt = tt; | ||
692 | } | 1181 | } |
693 | 1182 | ||
694 | 1183 | ||
695 | void luaC_linkupval (lua_State *L, UpVal *uv) { | 1184 | |
1185 | /* | ||
1186 | ** performs a full GC cycle; if "isemergency", does not call | ||
1187 | ** finalizers (which could change stack positions) | ||
1188 | */ | ||
1189 | void luaC_fullgc (lua_State *L, int isemergency) { | ||
696 | global_State *g = G(L); | 1190 | global_State *g = G(L); |
697 | GCObject *o = obj2gco(uv); | 1191 | int origkind = g->gckind; |
698 | o->gch.next = g->rootgc; /* link upvalue into `rootgc' list */ | 1192 | lua_assert(origkind != KGC_EMERGENCY); |
699 | g->rootgc = o; | 1193 | if (isemergency) /* do not run finalizers during emergency GC */ |
700 | if (isgray(o)) { | 1194 | g->gckind = KGC_EMERGENCY; |
701 | if (g->gcstate == GCSpropagate) { | 1195 | else { |
702 | gray2black(o); /* closed upvalues need barrier */ | 1196 | g->gckind = KGC_NORMAL; |
703 | luaC_barrier(L, uv, uv->v); | 1197 | callallpendingfinalizers(L, 1); |
704 | } | 1198 | } |
705 | else { /* sweep phase: sweep it (turning it into white) */ | 1199 | if (keepinvariant(g)) { /* may there be some black objects? */ |
706 | makewhite(g, o); | 1200 | /* must sweep all objects to turn them back to white |
707 | lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause); | 1201 | (as white has not changed, nothing will be collected) */ |
708 | } | 1202 | entersweep(L); |
1203 | } | ||
1204 | /* finish any pending sweep phase to start a new cycle */ | ||
1205 | luaC_runtilstate(L, bitmask(GCSpause)); | ||
1206 | luaC_runtilstate(L, ~bitmask(GCSpause)); /* start new collection */ | ||
1207 | luaC_runtilstate(L, bitmask(GCSpause)); /* run entire collection */ | ||
1208 | if (origkind == KGC_GEN) { /* generational mode? */ | ||
1209 | /* generational mode must be kept in propagate phase */ | ||
1210 | luaC_runtilstate(L, bitmask(GCSpropagate)); | ||
709 | } | 1211 | } |
1212 | g->gckind = origkind; | ||
1213 | setpause(g, gettotalbytes(g)); | ||
1214 | if (!isemergency) /* do not run finalizers during emergency GC */ | ||
1215 | callallpendingfinalizers(L, 1); | ||
710 | } | 1216 | } |
711 | 1217 | ||
1218 | /* }====================================================== */ | ||
1219 | |||
1220 | |||