# 探索Lua5.2內部實現:Garbage Collection(2) ## GCObject Lua使用union GCObject來表示所有的垃圾回收對象： ~~~ 182?/*? 183?**?Union?of?all?collectable?objects? 184?*/?? 185?union?GCObject?{?? 186???GCheader?gch;??/*?common?header?*/?? 187???union?TString?ts;?? 188???union?Udata?u;?? 189???union?Closure?cl;?? 190???struct?Table?h;?? 191???struct?Proto?p;?? 192???struct?UpVal?uv;?? 193???struct?lua_State?th;??/*?thread?*/?? 194?};?? ~~~ 這就相當于在C++中，將所有的GC對象從GCheader派生，他們都共享GCheader。 ~~~ 74?/*? 75?**?Common?Header?for?all?collectable?objects?(in?macro?form,?to?be? 76?**?included?in?other?objects)? 77?*/?? 78?#define?CommonHeader????GCObject?*next;?lu_byte?tt;?lu_byte?marked?? 79??? 80??? 81?/*? 82?**?Common?header?in?struct?form? 83?*/?? 84?typedef?struct?GCheader?{?? 85???CommonHeader;???? 86?}?GCheader;?? ~~~ marked這個標志用來記錄對象與GC相關的一些標志位。其中0和1位用來表示對象的white狀態和垃圾狀態。當垃圾回收的標識階段結束后，剩下的white對象就是垃圾對象。由于lua并不是立即清除這些垃圾對象，而是一步步逐漸清除，所以這些對象還會在系統中存在一段時間。這就需要我們能夠區分出同樣為white狀態的垃圾對象和非垃圾對象。Lua使用兩個標志位來表示white，就是為了高效的解決這個問題。這個標志位會輪流被當作white狀態標志，另一個表示垃圾狀態。在global_State中保存著一個currentwhite，來表示當前是那個標志位用來標識white。每當GC標識階段完成，系統會切換這個標志位，這樣原來為white的所有對象不需要遍歷就變成了垃圾對象，而真正的white對象則使用新的標志位標識。 第2個標志位用來表示black狀態，而既非white也非black就是gray狀態。 除了short string和open upvalue之外，所有的GCObject都通過next被串接到全局狀態global_State中的allgc鏈表上。我們可以通過遍歷allgc鏈表來訪問系統中的所有GCObject。short string被字符串標單獨管理。open upvalue會在被close時也連接到allgc上。 ## 引用關系 垃圾回收過程通過對象之間的引用關系來標識對象。以下是lua對象之間在垃圾回收標識過程中需要遍歷的引用關系：  所有字符串對象，無論是長串還是短串，都沒有對其他對象的引用。 usedata對象會引用到一個metatable和一個env table。 Upval對象通過v引用一個TValue，再通過這個TValue間接引用一個對象。在open狀態下，這個v指向stack上的一個TValue。在close狀態下，v指向Upval自己的TValue。 Table對象會通過key，value引用到其他對象，并且如果數組部分有效，也會通過數組部分引用。并且，table會引用一個metatable對象。 Lua closure會引用到Proto對象，并且會通過upvalues數組引用到Upval對象。 C closure會通過upvalues數組引用到其他對象。這里的upvalue與lua closure的upvalue完全不是一個意思。 Proto對象會引用到一些編譯期產生的名稱，常量，以及內嵌于本Proto中的Proto對象。 Thread對象通過stack引用其他對象。 ## barrier 在《[原理](http://blog.csdn.net/yuanlin2008/article/details/8558103)》中我們說過，incremental gc在mark階段，為了保證“所有的black對象都不會引用white對象”這個不變性，需要使用barrier。 barrier被分為“向前”和“向后”兩種。 luaC_barrier_函數用來實現“向前”的barrier。“向前”的意思就是當一個black對象需要引用一個white對象時，立即mark這個white對象。這樣white對象就變為gray對象，等待下一步的掃描。這也就是幫助gc向前標識一步。luaC_barrier_函數被用在以下引用變化處： * 虛擬機執行過程中或者通過api修改close upvalue對其他對象的引用 * 通過api設置userdata或table的metatable引用 * 通過api設置userdata的env table引用 * 編譯構建proto對象過程中proto對象對其他編譯產生對象的引用 luaC_barrierback_函數用來實現“向后”的barrier。“向后”的意思就是當一個black對象需要引用一個white對象時，將已經掃描過的black對象再次變為gray對象，等待重新掃描。這也就是將gc的mark后退一步。luaC_barrierback_目前只用于監控table的key和value對象引用的變化。Table是lua中最主要的數據結構，連全局變量都是被保存在一個table中，所以table的變化是比較頻繁的，并且同一個引用可能被反復設置成不同的對象。對table的引用使用“向前”的barrier，逐個掃描每次引用變化的對象，會造成很多不必要的消耗。而使用“向后”的barrier就等于將table分成了“未變”和“已變”兩種狀態。只要一個table改變了一次，就將其變成gray，等待重新掃描。被變成gray的table在被重新掃描之前，無論引用再發生多少次變化也都無關緊要了。 引用關系變化最頻繁的要數thread對象了。thread通過stack引用其他對象，而stack作為運行期棧，在一直不停地被修改。如果要監控這些引用變化，肯定會造成執行效率嚴重下降。所以lua并沒有在所有的stack引用變化處加入barrier，而是直接假設stack就是變化的。所以thread對象就算被掃描完成，也不會被設置成black，而是再次設置成gray，等待再次掃描。 ## Upvalue Upvalue對象在垃圾回收中的處理是比較特殊的。 對于open狀態的upvalue，其v指向的是一個stack上的TValue，所以open upvalue與thread的關系非常緊密。引用到open upvalue的只可能是其從屬的thread，以及lua closure。如果沒有lua closure引用這個open upvalue，就算他一定被thread引用著，也已經沒有實際的意義了，應該被回收掉。也就是說thread對open upvalue的引用完全是一個弱引用。所以Lua沒有將open upvalue當作一個獨立的可回收對象，而是將其清理工作交給從屬的thread對象來完成。在mark過程中，open upvalue對象只使用white和gray兩個狀態，來代表是否被引用到。通過上面的引用關系可以看到，有可能引用open upvalue的對象只可能被lua closure引用到。所以一個gray的open upvalue就代表當前有lua closure正在引用他，而這個lua closure不一定在這個thread的stack上面。在清掃階段，thread對象會遍歷所有從屬于自己的open upvalue。如果不是gray，就說明當前沒有lua closure引用這個open upvalue了，可以被銷毀。 當退出upvalue的語法域或者thread被銷毀，open upvalue會被close。所有close upvalue與thread已經沒有弱引用關系，會被轉化為一個普通的可回收對象，和其他對象一樣進行獨立的垃圾回收。