柚子快報(bào)邀請碼778899分享：lua的GC

http://yzkb.51969.com/

關(guān)于lua的gc云風(fēng)大佬在 Lua GC 的源碼剖析 系列文章中講得很清楚，這里做一下簡單的記錄。

分步gc

lua使用的是一種三色標(biāo)記清除算法（tri-color incremental mark & sweep），大體步驟如下： 初始階段，所有對象標(biāo)為白色； 標(biāo)記階段的開始，將所有從root可達(dá)的對象標(biāo)記為灰色； 標(biāo)記階段，逐個(gè)取出灰色對象，將其本身標(biāo)記為黑色，將其所有引用的白色對象標(biāo)記為灰色； 當(dāng)不存在灰色對象時(shí)，進(jìn)入清除階段，清除所有白色對象，將所有黑色對象標(biāo)記回白色。

具體而言，lua的gc分為markroot、mark、atomic、sweepstring、sweep、finalize幾個(gè)階段（見singlestep()）。 markroot函數(shù)將若干lua對象鏈表的根節(jié)點(diǎn)置為灰色，放入gray鏈表/隊(duì)列；mark階段類似樹的廣度優(yōu)先遍歷，從gray隊(duì)列中取出灰色對象，標(biāo)為黑色，再將其所引用的對象置為灰色，加入gray隊(duì)列；mark是分步執(zhí)行的，中間對象關(guān)系可能又發(fā)生變化，在開始清理工作前，還需要做最后一次掃描，這個(gè)過程不可以再被打斷，就是atomic函數(shù)；sweepstring階段分步清理字符串；sweep階段分步清理其他對象；userdata對象可能會(huì)有自定義gc方法，finalize階段就用來調(diào)用這些gc方法，userdata對象本身則放在下輪gc清理。

標(biāo)記階段和清除階段都是可以分步的，所以稱為分步gc。但中間可能出現(xiàn)這樣的情況：A引用B，B引用C；A已經(jīng)標(biāo)記為黑色，B標(biāo)記為灰色，C為白色；在gc間歇期間，程序修改了對象間的引用關(guān)系， B不再引用C，而A開始引用C。C本來是活躍對象，但卻會(huì)被清除，這會(huì)造成嚴(yán)重錯(cuò)誤。算法引入寫屏障技術(shù)，來解決這種問題：將此 白色 對象標(biāo)記成 灰色，稱為barrier forward，因?yàn)檎Ｊ前咨?>灰色->黑色的轉(zhuǎn)換方向；將此 黑色 對象標(biāo)記回 灰色，稱為barrier back。

如何確定gc的步伐大小是一系列的微操，見singlestep()、luaC_setp()。

數(shù)據(jù)類型

在Lua中共有9種數(shù)據(jù)類型，分別為nil、boolean、lightuserdata、number、string、table、function、userdata和thread。其中只有string table function thread四種在vm中以引用方式共享，是需要被GC管理回收的對象。其它類型都以值形式存在。 另外還有兩種類型的對象需要被GC管理，分別是proto和upvalue。

string創(chuàng)建后掛載于g->strt->hash upvalue創(chuàng)建后被鏈在g->uvhead table、thread、function、proto則都是掛在g->rootgc上，在mark階段簡單加到gray隊(duì)列即可

markroot

有3個(gè)鏈表用于標(biāo)記和清理過程，gray是灰色對象的鏈表，grayagain是在atomic階段需要再次標(biāo)記的對象的鏈表，weak是弱表的鏈表。 markroot()先將這三個(gè)鏈表清空，再將mainthread、mainthread的全局表、注冊表、各類型元表標(biāo)記，放到gray隊(duì)列中，開始mark階段。

string

mark的時(shí)候只是置灰，不掛載到gray上，所以它沒有黑色。 在sweepstring階段集中處理g->strt->hash。

userdata

rootgc初始化為mainthread，創(chuàng)建其他對象時(shí)使用的是頭部插入，所以mainthread是鏈表的最后一個(gè)元素。 但是luaS_newudata()中將userdata掛到mainthread后，所以rootgc鏈表被mainthread分為兩部分，后邊是userdata，前邊是其他對象。 userdata沒有灰色，mark時(shí)直接標(biāo)為黑色。 atomic中遍歷mainthread之后的userdata鏈表（luaC_separateudata()），空閑且有g(shù)c方法的從rootgc移到g->tmudata中。 finalize階段專門用來處理tmudata鏈表，對每個(gè)元素標(biāo)記為白色，返還給rootgc，然后調(diào)用它的gc方法。 沒有g(shù)c方法的空閑數(shù)據(jù)，就在sweep階段被清理掉；有g(shù)c方法的，第一輪gc時(shí)先調(diào)用gc方法，第二輪gc時(shí)在sweep階段清理掉userdata本身，通過finalized標(biāo)志來識別userdata的狀態(tài)。

string和userdata不引用其他對象，都是葉子節(jié)點(diǎn)。

upval

mark的時(shí)候： 如果是opend的，其指向棧上變量，將其指向的變量變灰； 如果是closed，其已是葉子節(jié)點(diǎn)，直接變黑。

以下引用自 Lua GC 的源碼剖析 (4)：

為何 open 狀態(tài)的 TUPVAL 需要留為灰色待處理呢？這是因?yàn)?open TUPVAL 是易變的。GC 分步執(zhí)行，我們無法預(yù)料在 mark 流程走完前，堆棧上被引用的數(shù)據(jù)會(huì)不會(huì)發(fā)生變化。事實(shí)上，在 mark 的最后一個(gè)步驟，我們會(huì)看到所有的 open TUPVAL 被再次 mark 一次，做這件事情的函數(shù)是 remarkupvals。

thread

mark的時(shí)候，從gray移到grayagain，且不變黑。 堆棧是隨著運(yùn)行過程不斷變化的，為了效率其上數(shù)據(jù)的修改是不經(jīng)過barrier的，所以把它推遲到atomic階段重掃描。

table

traversetable()的時(shí)候，弱表不會(huì)從灰變黑，而是轉(zhuǎn)移到weak鏈表上。 若弱表引用的元素被移除，也需要將元素從弱表中移除，atomic()中會(huì)調(diào)用cleartable()來做這件事。 移除table中hash部分value為nil的entry是通過removeentry()：

static void removeentry (Node *n) {

lua_assert(ttisnil(gval(n)));

if (iscollectable(gkey(n)))

ttype(gkey(n)) = LUA_TDEADKEY; /* dead key; remove it */

}

可以看到只是將key設(shè)為LUA_TDEADKEY類型，并沒有從表中真刪掉，那何時(shí)真正刪除呢？是rehash的時(shí)候。 所以 高性能 Lua 技巧（譯） 中這樣說“你不該期望通過從一個(gè)大表里刪除一些數(shù)據(jù)來回收內(nèi)存，更好的做法是刪除這個(gè)表本身。”。

參考

講解 Lua 內(nèi)部實(shí)現(xiàn)的 gc 機(jī)制 Lua GC 的工作原理 Lua GC 的源碼剖析

柚子快報(bào)邀請碼778899分享：lua的GC

http://yzkb.51969.com/

好文閱讀