lgc.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863
  1. /*
  2. ** $Id: lgc.c,v 2.60 2009/11/06 17:06:19 roberto Exp roberto $
  3. ** Garbage Collector
  4. ** See Copyright Notice in lua.h
  5. */
  6. #include <string.h>
  7. #define lgc_c
  8. #define LUA_CORE
  9. #include "lua.h"
  10. #include "ldebug.h"
  11. #include "ldo.h"
  12. #include "lfunc.h"
  13. #include "lgc.h"
  14. #include "lmem.h"
  15. #include "lobject.h"
  16. #include "lstate.h"
  17. #include "lstring.h"
  18. #include "ltable.h"
  19. #include "ltm.h"
  20. #define GCSTEPSIZE 1024u
  21. #define GCSWEEPMAX 40
  22. #define GCSWEEPCOST 10
  23. #define GCFINALIZECOST 100
  24. #define maskcolors cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
  25. #define makewhite(g,x) \
  26. (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g)))
  27. #define white2gray(x) resetbits(gch(x)->marked, WHITEBITS)
  28. #define black2gray(x) resetbit(gch(x)->marked, BLACKBIT)
  29. #define stringmark(s) resetbits((s)->tsv.marked, WHITEBITS)
  30. #define isfinalized(u) testbit((u)->marked, FINALIZEDBIT)
  31. #define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n)))
  32. #define markvalue(g,o) { checkconsistency(o); \
  33. if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
  34. #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \
  35. reallymarkobject(g, obj2gco(t)); }
  36. #define setthreshold(g) (g->GCthreshold = (g->estimate/100) * g->gcpause)
  37. static void reallymarkobject (global_State *g, GCObject *o);
  38. /*
  39. ** {======================================================
  40. ** Generic functions
  41. ** =======================================================
  42. */
  43. static void linktable (Table *h, GCObject **p) {
  44. h->gclist = *p;
  45. *p = obj2gco(h);
  46. }
  47. static void removeentry (Node *n) {
  48. lua_assert(ttisnil(gval(n)));
  49. if (iscollectable(gkey(n)))
  50. setdeadvalue(gkey(n)); /* dead key; remove it */
  51. }
  52. /*
  53. ** The next function tells whether a key or value can be cleared from
  54. ** a weak table. Non-collectable objects are never removed from weak
  55. ** tables. Strings behave as `values', so are never removed too. for
  56. ** other objects: if really collected, cannot keep them; for objects
  57. ** being finalized, keep them in keys, but not in values
  58. */
  59. static int iscleared (const TValue *o, int iskey) {
  60. if (!iscollectable(o)) return 0;
  61. if (ttisstring(o)) {
  62. stringmark(rawtsvalue(o)); /* strings are `values', so are never weak */
  63. return 0;
  64. }
  65. return iswhite(gcvalue(o)) ||
  66. (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
  67. }
  68. void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
  69. global_State *g = G(L);
  70. lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  71. lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  72. lua_assert(gch(o)->tt != LUA_TTABLE);
  73. /* must keep invariant? */
  74. if (g->gcstate == GCSpropagate)
  75. reallymarkobject(g, v); /* restore invariant */
  76. else /* don't mind */
  77. makewhite(g, o); /* mark as white just to avoid other barriers */
  78. }
  79. void luaC_barrierback (lua_State *L, Table *t) {
  80. global_State *g = G(L);
  81. GCObject *o = obj2gco(t);
  82. lua_assert(isblack(o) && !isdead(g, o));
  83. lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  84. black2gray(o); /* make table gray (again) */
  85. t->gclist = g->grayagain;
  86. g->grayagain = o;
  87. }
  88. void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  89. global_State *g = G(L);
  90. gch(o)->marked = luaC_white(g);
  91. gch(o)->tt = tt;
  92. gch(o)->next = g->rootgc;
  93. g->rootgc = o;
  94. }
  95. void luaC_linkupval (lua_State *L, UpVal *uv) {
  96. global_State *g = G(L);
  97. GCObject *o = obj2gco(uv);
  98. gch(o)->next = g->rootgc; /* link upvalue into `rootgc' list */
  99. g->rootgc = o;
  100. if (isgray(o)) {
  101. if (g->gcstate == GCSpropagate) {
  102. gray2black(o); /* closed upvalues need barrier */
  103. luaC_barrier(L, uv, uv->v);
  104. }
  105. else { /* sweep phase: sweep it (turning it into white) */
  106. makewhite(g, o);
  107. lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  108. }
  109. }
  110. }
  111. /* }====================================================== */
  112. /*
  113. ** {======================================================
  114. ** Mark functions
  115. ** =======================================================
  116. */
  117. static void reallymarkobject (global_State *g, GCObject *o) {
  118. lua_assert(iswhite(o) && !isdead(g, o));
  119. white2gray(o);
  120. switch (gch(o)->tt) {
  121. case LUA_TSTRING: {
  122. return;
  123. }
  124. case LUA_TUSERDATA: {
  125. Table *mt = gco2u(o)->metatable;
  126. gray2black(o); /* udata are never gray */
  127. markobject(g, mt);
  128. markobject(g, gco2u(o)->env);
  129. return;
  130. }
  131. case LUA_TUPVAL: {
  132. UpVal *uv = gco2uv(o);
  133. markvalue(g, uv->v);
  134. if (uv->v == &uv->u.value) /* closed? */
  135. gray2black(o); /* open upvalues are never black */
  136. return;
  137. }
  138. case LUA_TFUNCTION: {
  139. gco2cl(o)->c.gclist = g->gray;
  140. g->gray = o;
  141. break;
  142. }
  143. case LUA_TTABLE: {
  144. linktable(gco2t(o), &g->gray);
  145. break;
  146. }
  147. case LUA_TTHREAD: {
  148. gco2th(o)->gclist = g->gray;
  149. g->gray = o;
  150. break;
  151. }
  152. case LUA_TPROTO: {
  153. gco2p(o)->gclist = g->gray;
  154. g->gray = o;
  155. break;
  156. }
  157. default: lua_assert(0);
  158. }
  159. }
  160. static void markmt (global_State *g) {
  161. int i;
  162. for (i=0; i<NUM_TAGS; i++)
  163. markobject(g, g->mt[i]);
  164. }
  165. static void markbeingfnz (global_State *g) {
  166. GCObject *o;
  167. for (o = g->tobefnz; o != NULL; o = gch(o)->next) {
  168. lua_assert(testbit(gch(o)->marked, SEPARATED));
  169. makewhite(g, o);
  170. reallymarkobject(g, o);
  171. }
  172. }
  173. /* mark root set */
  174. static void markroot (lua_State *L) {
  175. global_State *g = G(L);
  176. g->gray = NULL;
  177. g->grayagain = NULL;
  178. g->weak = g->ephemeron = g->allweak = NULL;
  179. markobject(g, g->mainthread);
  180. /* make global table and registry to be traversed before main stack */
  181. markvalue(g, &g->l_gt);
  182. markvalue(g, &g->l_registry);
  183. markmt(g);
  184. markbeingfnz(g); /* mark any finalizing object left from previous cycle */
  185. g->gcstate = GCSpropagate;
  186. }
  187. static void remarkupvals (global_State *g) {
  188. UpVal *uv;
  189. for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
  190. lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
  191. if (isgray(obj2gco(uv)))
  192. markvalue(g, uv->v);
  193. }
  194. }
  195. /* }====================================================== */
  196. /*
  197. ** {======================================================
  198. ** Traverse functions
  199. ** =======================================================
  200. */
  201. static void traverseweakvalue (global_State *g, Table *h) {
  202. int i = sizenode(h);
  203. while (i--) {
  204. Node *n = gnode(h, i);
  205. checkdeadkey(n);
  206. if (ttisnil(gval(n)))
  207. removeentry(n); /* remove empty entries */
  208. else {
  209. lua_assert(!ttisnil(gkey(n)));
  210. markvalue(g, gkey(n));
  211. }
  212. }
  213. linktable(h, &g->weak);
  214. }
  215. static int traverseephemeron (global_State *g, Table *h) {
  216. int marked = 0;
  217. int hasclears = 0;
  218. int i = h->sizearray;
  219. while (i--) { /* mark array part (numeric keys are 'strong') */
  220. if (valiswhite(&h->array[i])) {
  221. marked = 1;
  222. reallymarkobject(g, gcvalue(&h->array[i]));
  223. }
  224. }
  225. i = sizenode(h);
  226. while (i--) {
  227. Node *n = gnode(h, i);
  228. checkdeadkey(n);
  229. if (ttisnil(gval(n))) /* entry is empty? */
  230. removeentry(n); /* remove it */
  231. else if (valiswhite(gval(n))) {
  232. /* value is not marked yet */
  233. if (iscleared(key2tval(n), 1)) /* key is not marked (yet)? */
  234. hasclears = 1; /* may have to propagate mark from key to value */
  235. else { /* mark value only if key is marked */
  236. marked = 1; /* some mark changed status */
  237. reallymarkobject(g, gcvalue(gval(n)));
  238. }
  239. }
  240. }
  241. if (hasclears)
  242. linktable(h, &g->ephemeron);
  243. else /* nothing to propagate */
  244. linktable(h, &g->weak); /* avoid convergence phase */
  245. return marked;
  246. }
  247. static void traversestrongtable (global_State *g, Table *h) {
  248. int i;
  249. i = h->sizearray;
  250. while (i--)
  251. markvalue(g, &h->array[i]);
  252. i = sizenode(h);
  253. while (i--) {
  254. Node *n = gnode(h, i);
  255. checkdeadkey(n);
  256. if (ttisnil(gval(n)))
  257. removeentry(n); /* remove empty entries */
  258. else {
  259. lua_assert(!ttisnil(gkey(n)));
  260. markvalue(g, gkey(n));
  261. markvalue(g, gval(n));
  262. }
  263. }
  264. }
  265. static void traversetable (global_State *g, Table *h) {
  266. const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
  267. markobject(g, h->metatable);
  268. if (mode && ttisstring(mode)) { /* is there a weak mode? */
  269. int weakkey = (strchr(svalue(mode), 'k') != NULL);
  270. int weakvalue = (strchr(svalue(mode), 'v') != NULL);
  271. if (weakkey || weakvalue) { /* is really weak? */
  272. black2gray(obj2gco(h)); /* keep table gray */
  273. if (!weakkey) /* strong keys? */
  274. traverseweakvalue(g, h);
  275. else if (!weakvalue) /* strong values? */
  276. traverseephemeron(g, h);
  277. else
  278. linktable(h, &g->allweak); /* nothing to traverse now */
  279. return;
  280. } /* else go through */
  281. }
  282. traversestrongtable(g, h);
  283. }
  284. /*
  285. ** All marks are conditional because a GC may happen while the
  286. ** prototype is still being created
  287. */
  288. static void traverseproto (global_State *g, Proto *f) {
  289. int i;
  290. if (f->source) stringmark(f->source);
  291. for (i=0; i<f->sizek; i++) /* mark literals */
  292. markvalue(g, &f->k[i]);
  293. for (i=0; i<f->sizeupvalues; i++) { /* mark upvalue names */
  294. if (f->upvalues[i].name)
  295. stringmark(f->upvalues[i].name);
  296. }
  297. for (i=0; i<f->sizep; i++) /* mark nested protos */
  298. markobject(g, f->p[i]);
  299. for (i=0; i<f->sizelocvars; i++) { /* mark local-variable names */
  300. if (f->locvars[i].varname)
  301. stringmark(f->locvars[i].varname);
  302. }
  303. }
  304. static void traverseclosure (global_State *g, Closure *cl) {
  305. markobject(g, cl->c.env);
  306. if (cl->c.isC) {
  307. int i;
  308. for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */
  309. markvalue(g, &cl->c.upvalue[i]);
  310. }
  311. else {
  312. int i;
  313. lua_assert(cl->l.nupvalues == cl->l.p->sizeupvalues);
  314. markobject(g, cl->l.p);
  315. for (i=0; i<cl->l.nupvalues; i++) /* mark its upvalues */
  316. markobject(g, cl->l.upvals[i]);
  317. }
  318. }
  319. static void traversestack (global_State *g, lua_State *L) {
  320. StkId o;
  321. if (L->stack == NULL)
  322. return; /* stack not completely built yet */
  323. for (o = L->stack; o < L->top; o++)
  324. markvalue(g, o);
  325. if (g->gcstate == GCSatomic) { /* final traversal? */
  326. StkId lim = L->stack + L->stacksize; /* real end of stack */
  327. for (; o < lim; o++) /* clear not-marked stack slice */
  328. setnilvalue(o);
  329. }
  330. }
  331. /*
  332. ** traverse one gray object, turning it to black.
  333. ** Returns `quantity' traversed.
  334. */
  335. static l_mem propagatemark (global_State *g) {
  336. GCObject *o = g->gray;
  337. lua_assert(isgray(o));
  338. gray2black(o);
  339. switch (gch(o)->tt) {
  340. case LUA_TTABLE: {
  341. Table *h = gco2t(o);
  342. g->gray = h->gclist;
  343. traversetable(g, h);
  344. return sizeof(Table) + sizeof(TValue) * h->sizearray +
  345. sizeof(Node) * sizenode(h);
  346. }
  347. case LUA_TFUNCTION: {
  348. Closure *cl = gco2cl(o);
  349. g->gray = cl->c.gclist;
  350. traverseclosure(g, cl);
  351. return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
  352. sizeLclosure(cl->l.nupvalues);
  353. }
  354. case LUA_TTHREAD: {
  355. lua_State *th = gco2th(o);
  356. g->gray = th->gclist;
  357. th->gclist = g->grayagain;
  358. g->grayagain = o;
  359. black2gray(o);
  360. traversestack(g, th);
  361. return sizeof(lua_State) + sizeof(TValue) * th->stacksize;
  362. }
  363. case LUA_TPROTO: {
  364. Proto *p = gco2p(o);
  365. g->gray = p->gclist;
  366. traverseproto(g, p);
  367. return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
  368. sizeof(Proto *) * p->sizep +
  369. sizeof(TValue) * p->sizek +
  370. sizeof(int) * p->sizelineinfo +
  371. sizeof(LocVar) * p->sizelocvars +
  372. sizeof(TString *) * p->sizeupvalues;
  373. }
  374. default: lua_assert(0); return 0;
  375. }
  376. }
  377. static size_t propagateall (global_State *g) {
  378. size_t m = 0;
  379. while (g->gray) m += propagatemark(g);
  380. return m;
  381. }
  382. static void traverselistofgrays (global_State *g, GCObject **l) {
  383. lua_assert(g->gray == NULL); /* no grays left */
  384. g->gray = *l; /* now 'l' is new gray list */
  385. *l = NULL;
  386. propagateall(g);
  387. }
  388. static void convergeephemerons (global_State *g) {
  389. int changed;
  390. do {
  391. GCObject *w;
  392. GCObject *next = g->ephemeron;
  393. g->ephemeron = NULL;
  394. changed = 0;
  395. while ((w = next) != NULL) {
  396. next = gco2t(w)->gclist;
  397. if (traverseephemeron(g, gco2t(w))) {
  398. changed = 1;
  399. propagateall(g);
  400. }
  401. }
  402. } while (changed);
  403. }
  404. /* }====================================================== */
  405. /*
  406. ** {======================================================
  407. ** Sweep Functions
  408. ** =======================================================
  409. */
  410. /* clear collected entries from weaktables */
  411. static void cleartable (GCObject *l) {
  412. while (l) {
  413. Table *h = gco2t(l);
  414. int i = h->sizearray;
  415. while (i--) {
  416. TValue *o = &h->array[i];
  417. if (iscleared(o, 0)) /* value was collected? */
  418. setnilvalue(o); /* remove value */
  419. }
  420. i = sizenode(h);
  421. while (i--) {
  422. Node *n = gnode(h, i);
  423. if (!ttisnil(gval(n)) && /* non-empty entry? */
  424. (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
  425. setnilvalue(gval(n)); /* remove value ... */
  426. removeentry(n); /* remove entry from table */
  427. }
  428. }
  429. l = h->gclist;
  430. }
  431. }
  432. static void freeobj (lua_State *L, GCObject *o) {
  433. switch (gch(o)->tt) {
  434. case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
  435. case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
  436. case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
  437. case LUA_TTABLE: luaH_free(L, gco2t(o)); break;
  438. case LUA_TTHREAD: luaE_freethread(L, gco2th(o)); break;
  439. case LUA_TUSERDATA: luaM_freemem(L, o, sizeudata(gco2u(o))); break;
  440. case LUA_TSTRING: {
  441. G(L)->strt.nuse--;
  442. luaM_freemem(L, o, sizestring(gco2ts(o)));
  443. break;
  444. }
  445. default: lua_assert(0);
  446. }
  447. }
  448. #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM)
  449. static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count);
  450. static void sweepthread (lua_State *L, lua_State *L1, int alive) {
  451. if (L1->stack == NULL) return; /* stack not completely built yet */
  452. sweepwholelist(L, &L1->openupval); /* sweep open upvalues */
  453. luaE_freeCI(L1); /* free extra CallInfo slots */
  454. /* should not change the stack during an emergency gc cycle */
  455. if (alive && G(L)->gckind != KGC_EMERGENCY)
  456. luaD_shrinkstack(L1);
  457. }
  458. static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  459. GCObject *curr;
  460. global_State *g = G(L);
  461. int deadmask = otherwhite(g);
  462. while ((curr = *p) != NULL && count-- > 0) {
  463. int alive = (gch(curr)->marked ^ WHITEBITS) & deadmask;
  464. if (gch(curr)->tt == LUA_TTHREAD)
  465. sweepthread(L, gco2th(curr), alive);
  466. if (alive) {
  467. lua_assert(!isdead(g, curr) || testbit(gch(curr)->marked, FIXEDBIT));
  468. makewhite(g, curr); /* make it white (for next cycle) */
  469. p = &gch(curr)->next;
  470. }
  471. else { /* must erase `curr' */
  472. lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
  473. *p = gch(curr)->next; /* remove 'curr' from list */
  474. freeobj(L, curr);
  475. }
  476. }
  477. return p;
  478. }
  479. /* }====================================================== */
  480. /*
  481. ** {======================================================
  482. ** Finalization
  483. ** =======================================================
  484. */
  485. static void checkSizes (lua_State *L) {
  486. global_State *g = G(L);
  487. if (g->strt.nuse < cast(lu_int32, g->strt.size)) {
  488. /* string-table size could be the smaller power of 2 larger than 'nuse' */
  489. int size = 1 << luaO_ceillog2(g->strt.nuse);
  490. if (size < g->strt.size) /* current table too large? */
  491. luaS_resize(L, size); /* shrink it */
  492. }
  493. luaZ_freebuffer(L, &g->buff);
  494. }
  495. static Udata *udata2finalize (global_State *g) {
  496. GCObject *o = g->tobefnz; /* get first element */
  497. g->tobefnz = gch(o)->next; /* remove it from 'tobefnz' list */
  498. gch(o)->next = g->rootgc; /* return it to `root' list */
  499. g->rootgc = o;
  500. lua_assert(isfinalized(gch(o)));
  501. resetbit(gch(o)->marked, SEPARATED); /* mark it as such */
  502. makewhite(g, o);
  503. return rawgco2u(o);
  504. }
  505. static void dothecall (lua_State *L, void *ud) {
  506. UNUSED(ud);
  507. luaD_call(L, L->top - 2, 0, 0);
  508. }
  509. static void GCTM (lua_State *L, int propagateerrors) {
  510. global_State *g = G(L);
  511. Udata *udata = udata2finalize(g);
  512. const TValue *tm = gfasttm(g, udata->uv.metatable, TM_GC);
  513. if (tm != NULL && ttisfunction(tm)) {
  514. int status;
  515. lu_byte oldah = L->allowhook;
  516. lu_mem oldt = g->GCthreshold;
  517. L->allowhook = 0; /* stop debug hooks during GC tag method */
  518. g->GCthreshold = 2*g->totalbytes; /* avoid GC steps */
  519. setobj2s(L, L->top, tm);
  520. setuvalue(L, L->top+1, udata);
  521. L->top += 2;
  522. status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top - 2), 0);
  523. if (status != LUA_OK && propagateerrors) { /* error while running __gc? */
  524. if (status == LUA_ERRRUN) { /* is there an error msg.? */
  525. luaO_pushfstring(L, "error in __gc tag method (%s)",
  526. lua_tostring(L, -1));
  527. status = LUA_ERRGCMM; /* error in __gc metamethod */
  528. }
  529. luaD_throw(L, status); /* re-send error */
  530. }
  531. L->allowhook = oldah; /* restore hooks */
  532. g->GCthreshold = oldt; /* restore threshold */
  533. }
  534. }
  535. /*
  536. ** Call all GC tag methods (without raising errors)
  537. */
  538. void luaC_callAllGCTM (lua_State *L) {
  539. while (G(L)->tobefnz) GCTM(L, 0);
  540. }
  541. /* move 'dead' udata that need finalization to list 'tobefnz' */
  542. size_t luaC_separateudata (lua_State *L, int all) {
  543. global_State *g = G(L);
  544. size_t deadmem = 0; /* total size of all objects to be finalized */
  545. GCObject **p = &g->mainthread->next;
  546. GCObject *curr;
  547. GCObject **lastnext = &g->tobefnz;
  548. /* find last 'next' field in 'tobefnz' list (to insert elements in its end) */
  549. while (*lastnext != NULL) lastnext = &gch(*lastnext)->next;
  550. while ((curr = *p) != NULL) { /* traverse all finalizable objects */
  551. lua_assert(gch(curr)->tt == LUA_TUSERDATA && !isfinalized(gco2u(curr)));
  552. lua_assert(testbit(gch(curr)->marked, SEPARATED));
  553. if (!(all || iswhite(curr))) /* not being collected? */
  554. p = &gch(curr)->next; /* don't bother with it */
  555. else {
  556. l_setbit(gch(curr)->marked, FINALIZEDBIT); /* won't be finalized again */
  557. deadmem += sizeudata(gco2u(curr));
  558. *p = gch(curr)->next; /* remove 'curr' from 'rootgc' list */
  559. /* link 'curr' at the end of 'tobefnz' list */
  560. gch(curr)->next = *lastnext;
  561. *lastnext = curr;
  562. lastnext = &gch(curr)->next;
  563. }
  564. }
  565. return deadmem;
  566. }
  567. void luaC_checkfinalizer (lua_State *L, Udata *u) {
  568. global_State *g = G(L);
  569. if (testbit(u->uv.marked, SEPARATED) || /* userdata is already separated... */
  570. isfinalized(&u->uv) || /* ... or is finalized... */
  571. gfasttm(g, u->uv.metatable, TM_GC) == NULL) /* or has no finalization? */
  572. return; /* nothing to be done */
  573. else { /* move 'u' to 2nd part of root list */
  574. GCObject **p;
  575. for (p = &g->rootgc; *p != obj2gco(u); p = &gch(*p)->next)
  576. lua_assert(*p != obj2gco(g->mainthread)); /* 'u' must be in this list */
  577. *p = u->uv.next; /* remove 'u' from root list */
  578. u->uv.next = g->mainthread->next; /* re-link it in list */
  579. g->mainthread->next = obj2gco(u);
  580. l_setbit(u->uv.marked, SEPARATED); /* mark it as such */
  581. }
  582. }
  583. /* }====================================================== */
  584. /*
  585. ** {======================================================
  586. ** GC control
  587. ** =======================================================
  588. */
  589. void luaC_freeall (lua_State *L) {
  590. global_State *g = G(L);
  591. int i;
  592. lua_assert(g->tobefnz == NULL);
  593. /* mask to collect all elements */
  594. g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);
  595. sweepwholelist(L, &g->rootgc);
  596. lua_assert(g->rootgc == obj2gco(g->mainthread));
  597. lua_assert(g->mainthread->next == NULL);
  598. for (i = 0; i < g->strt.size; i++) /* free all string lists */
  599. sweepwholelist(L, &g->strt.hash[i]);
  600. lua_assert(g->strt.nuse == 0);
  601. }
  602. static void atomic (lua_State *L) {
  603. global_State *g = G(L);
  604. size_t udsize; /* total size of userdata to be finalized */
  605. /* global table and registry may be changed by API */
  606. markvalue(g, &g->l_gt);
  607. markvalue(g, &g->l_registry);
  608. /* remark occasional upvalues of (maybe) dead threads */
  609. g->gcstate = GCSatomic;
  610. remarkupvals(g);
  611. /* traverse objects caught by write barrier and by 'remarkupvals' */
  612. propagateall(g);
  613. /* remark weak tables */
  614. g->gray = g->weak;
  615. g->weak = NULL;
  616. lua_assert(!iswhite(obj2gco(g->mainthread)));
  617. markobject(g, L); /* mark running thread */
  618. markmt(g); /* mark basic metatables (again) */
  619. propagateall(g);
  620. traverselistofgrays(g, &g->ephemeron); /* remark ephemeron tables */
  621. traverselistofgrays(g, &g->grayagain); /* remark gray again */
  622. convergeephemerons(g);
  623. udsize = luaC_separateudata(L, 0); /* separate userdata to be finalized */
  624. markbeingfnz(g); /* mark userdata that will be finalized */
  625. udsize += propagateall(g); /* remark, to propagate `preserveness' */
  626. convergeephemerons(g);
  627. /* remove collected objects from weak tables */
  628. cleartable(g->weak);
  629. cleartable(g->ephemeron);
  630. cleartable(g->allweak);
  631. /* flip current white */
  632. g->currentwhite = cast_byte(otherwhite(g));
  633. g->sweepstrgc = 0;
  634. g->gcstate = GCSsweepstring;
  635. lua_assert(g->totalbytes > udsize);
  636. g->estimate = g->totalbytes - udsize; /* first estimate */
  637. }
  638. #define correctestimate(g,s) { \
  639. lu_mem old = g->totalbytes; s; \
  640. lua_assert(old >= g->totalbytes); \
  641. if (g->estimate >= old - g->totalbytes) \
  642. g->estimate -= (old - g->totalbytes);}
  643. static l_mem singlestep (lua_State *L) {
  644. global_State *g = G(L);
  645. /*lua_checkmemory(L);*/
  646. switch (g->gcstate) {
  647. case GCSpause: {
  648. markroot(L); /* start a new collection */
  649. return 0;
  650. }
  651. case GCSpropagate: {
  652. if (g->gray)
  653. return propagatemark(g);
  654. else { /* no more `gray' objects */
  655. atomic(L); /* finish mark phase */
  656. return 0;
  657. }
  658. }
  659. case GCSsweepstring: {
  660. correctestimate(g, sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]));
  661. if (g->sweepstrgc >= g->strt.size) { /* nothing more to sweep? */
  662. g->sweepgc = &g->rootgc;
  663. g->gcstate = GCSsweep; /* sweep all other objects */
  664. }
  665. return GCSWEEPCOST;
  666. }
  667. case GCSsweep: {
  668. correctestimate(g, g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX));
  669. if (*g->sweepgc == NULL) /* nothing more to sweep? */
  670. g->gcstate = GCSfinalize; /* end sweep phase */
  671. return GCSWEEPMAX*GCSWEEPCOST;
  672. }
  673. case GCSfinalize: {
  674. if (g->tobefnz) {
  675. GCTM(L, 1);
  676. if (g->estimate > GCFINALIZECOST)
  677. g->estimate -= GCFINALIZECOST;
  678. return GCFINALIZECOST;
  679. }
  680. else {
  681. correctestimate(g, checkSizes(L));
  682. g->gcstate = GCSpause; /* end collection */
  683. g->gcdept = 0;
  684. return 0;
  685. }
  686. }
  687. default: lua_assert(0); return 0;
  688. }
  689. }
  690. void luaC_step (lua_State *L) {
  691. global_State *g = G(L);
  692. l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  693. lua_assert(g->gckind == KGC_NORMAL);
  694. if (lim == 0)
  695. lim = (MAX_LUMEM-1)/2; /* no limit */
  696. g->gcdept += g->totalbytes - g->GCthreshold;
  697. do {
  698. lim -= singlestep(L);
  699. if (g->gcstate == GCSpause)
  700. break;
  701. } while (lim > 0);
  702. if (g->gcstate != GCSpause) {
  703. if (g->gcdept < GCSTEPSIZE)
  704. g->GCthreshold = g->totalbytes + GCSTEPSIZE; /* - lim/g->gcstepmul;*/
  705. else {
  706. g->gcdept -= GCSTEPSIZE;
  707. g->GCthreshold = g->totalbytes;
  708. }
  709. }
  710. else {
  711. if (g->estimate > g->totalbytes)
  712. g->estimate = g->totalbytes;
  713. setthreshold(g);
  714. }
  715. }
  716. void luaC_fullgc (lua_State *L, int isemergency) {
  717. global_State *g = G(L);
  718. lua_assert(g->gckind == KGC_NORMAL);
  719. g->gckind = isemergency ? KGC_EMERGENCY : KGC_FORCED;
  720. if (g->gcstate <= GCSpropagate) {
  721. /* reset other collector lists */
  722. g->gray = NULL;
  723. g->grayagain = NULL;
  724. g->weak = g->ephemeron = g->allweak = NULL;
  725. g->sweepstrgc = 0;
  726. g->gcstate = GCSsweepstring;
  727. }
  728. lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
  729. /* finish any pending sweep phase */
  730. while (g->gcstate != GCSfinalize) {
  731. lua_assert(issweep(g));
  732. singlestep(L);
  733. }
  734. markroot(L);
  735. /* run collector up to finalizers */
  736. while (g->gcstate != GCSfinalize)
  737. singlestep(L);
  738. g->gckind = KGC_NORMAL;
  739. if (!isemergency) { /* do not run finalizers during emergency GC */
  740. while (g->gcstate != GCSpause)
  741. singlestep(L);
  742. }
  743. setthreshold(g);
  744. }
  745. /* }====================================================== */