Lua源码分析 Gc篇（二）数据结构 副本

[TOC]

这是这个gc系列的第二篇，这一篇主要讲GC用到的数据结构，有助于理解gc的，所以放在前面

栈就是我们平时写代码接触最多的lua_State。在实现上是用一个数组实现的。每个成员类型是TValue，看下文详细介绍。这里不打算详细介绍栈的结构和内容，只会介绍和gc相关的一些内容，主要是帮助我们更好的理解lua的gc。

定义

下面是lua_State的定义，会看到栈的身影，top和base指针。

struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;  /* first free slot in the stack */
  StkId base;  /* base of current function */
  global_State *l_G;
  CallInfo *ci;  /* call info for current function */
  const Instruction *savedpc;  /* `savedpc' of current function */
  StkId stack_last;  /* last free slot in the stack */
  StkId stack;  /* stack base */
  CallInfo *end_ci;  /* points after end of ci array*/
  CallInfo *base_ci;  /* array of CallInfo's */
  int stacksize;
  int size_ci;  /* size of array `base_ci' */
  unsigned short nCcalls;  /* number of nested C calls */
  lu_byte hookmask;
  lu_byte allowhook;
  int basehookcount;
  int hookcount;
  lua_Hook hook;
  TValue l_gt;  /* table of globals */
  TValue env;  /* temporary place for environments */
  GCObject *openupval;  /* list of open upvalues in this stack */
  GCObject *gclist;
  struct lua_longjmp *errorJmp;  /* current error recover point */
  ptrdiff_t errfunc;  /* current error handling function (stack index) */
};

简单的图

至于base/top和stack/stack_last、以及base_ci/end_ci之间的关系和区别就不打算详细介绍了。主要是lua的指令操作的实现，以及函数调用的时候也要用到栈，只是他们在这个数组的不同区间。

2.栈元素TValue

这个类型是给栈用的，前面说过栈其实是一个TValue的数组。

定义

typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;
#define TValuefields    Value value; int tt

typedef struct lua_TValue {

TValuefields;

} TValue;

说明

• TValue，是Value加了一个类型

类型定义：

/*
** basic types
*/
#define LUA_TNONE        (-1)
#define LUA_TNIL        0
#define LUA_TBOOLEAN        1
#define LUA_TLIGHTUSERDATA    2
#define LUA_TNUMBER        3
#define LUA_TSTRING        4
#define LUA_TTABLE        5
#define LUA_TFUNCTION        6
#define LUA_TUSERDATA        7
#define LUA_TTHREAD        8

• 可以看到存放真正值的是这是一个union结构
• 用过lua的都知道，lua是一种动态类型语言，所有值都是first-class的。所以代码层就是这个Value
• 简单介绍一下union中成员的含义

成员	含义
GCObject *gc	所有的需要gc的对象都是用的这个成员，所以本系列文章只关注这个成员就好了
void *p	存放lightuserdata
lua_Number n	数值类型，这里也可以看出来lua里面用到的整形浮点型都是用这个存储的，就是double类型
int b	bool类型

看代码：

// bool类型的宏
#define setbvalue(obj,x) 
  { TValue *i_o=(obj); i_o->value.b=(x); i_o->tt=LUA_TBOOLEAN; }
// table类型的宏
#define sethvalue(L,obj,x) 
  { TValue *i_o=(obj); 
    i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TTABLE; 
    checkliveness(G(L),i_o); }

3.GC对象

gc对象就是指lua里面需要被回收的对象，类型是在LUA_TSTRING（4）到LUA_TTHREAD（8）之间（准确来说还有扩展的类型）。开始看的时候，难免会有疑问，lua里面的所有对象不都是放在栈里面的吗？这个gc对象是个什么的存在？

定义

union GCObject {
  GCheader gch;
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};
// head

#define CommonHeader    GCObject *next; lu_byte tt; lu_byte marked

说明

• 这是一个union结构体
• 这里必须提醒注意下这个GCheader，可以看到前面一个GCheader gch的定义，是跟类型无关的。后面在解答上面疑问的时候，一并说明一下。这个CommonHeader实现了一个链表结构(next)，也指明了这个对象的类型(tt)，以及颜色(marked)。
• 会看到除了前面的基本类型之外，多了几个可以回收的类型

/*
** Extra tags for non-values
*/
#define LUA_TPROTO    (LAST_TAG+1)
#define LUA_TUPVAL    (LAST_TAG+2)
#define LUA_TDEADKEY    (LAST_TAG+3)

4.gc链表

这个链表是记录了lua里面所有的可回收对象，另外注意这是一个单向链表。正因为是单向链表，为了效率，才不会去整个遍历一遍，才会再增加扫描的链表等，这些后面篇章详细介绍。

定义

这个链表的指针是放在global_State中rootgc中的。

/*
** `global state', shared by all threads of this state
*/
typedef struct global_State {
  stringtable strt;  /* hash table for strings */
  lua_Alloc frealloc;  /* function to reallocate memory */
  void *ud;         /* auxiliary data to `frealloc' */
  lu_byte currentwhite;
  lu_byte gcstate;  /* state of garbage collector */
  int sweepstrgc;  /* position of sweep in `strt' */
  GCObject *rootgc;  /* list of all collectable objects */
  GCObject **sweepgc;  /* position of sweep in `rootgc' */
  GCObject *gray;  /* list of gray objects */
  GCObject *grayagain;  /* list of objects to be traversed atomically */
  GCObject *weak;  /* list of weak tables (to be cleared) */
  GCObject *tmudata;  /* last element of list of userdata to be GC */
  Mbuffer buff;  /* temporary buffer for string concatentation */
  lu_mem GCthreshold;
  lu_mem totalbytes;  /* number of bytes currently allocated */
  lu_mem estimate;  /* an estimate of number of bytes actually in use */
  lu_mem gcdept;  /* how much GC is `behind schedule' */
  int gcpause;  /* size of pause between successive GCs */
  int gcstepmul;  /* GC `granularity' */
  lua_CFunction panic;  /* to be called in unprotected errors */
  TValue l_registry;
  struct lua_State *mainthread;
  UpVal uvhead;  /* head of double-linked list of all open upvalues */
  struct Table *mt[NUM_TAGS];  /* metatables for basic types */
  TString *tmname[TM_N];  /* array with tag-method names */
} global_State;

这个结构放了所有关于gc的内容(对着后面的注释看一下)：

• currentwhite：这个就是第一篇中提到的gc流程中的当前白色，如果清理阶段某个对象是otherwhite，那么他就会被清理掉
• gcstate：控制gc流程的，后面流程中说的状态就是记录在这里
• rootgc：前面刚提到过，所有可回收的gc对象单向链表
• gray：为了gc的效率增加的一个gc链表
• grayagain：为了实现增量式gc，过程中处理中断问题的一个链表
• GCthreshold，totalbytes，estimate，gcdept，gcpause：这几个单次gc相关的控制或者状态量，直接关系到lua提供的接口collectgarbage
• 另外一些是全局的一些变量的定义，metatable等。这些跟gc扫描不会遍历整个gc链表有关系。

5.栈和gc链表的关系

栈没有细说，但是他和gc链表的关系必须详细说明一下。如下图所示

答疑解惑

就着问题，说一下栈和gc链表之间的关系。

• 1.GCObject的存在

这里就需要了解gc链表和栈中元素的关系。lua的栈是一个数组，里面真正存放了lua里面的所有对象。gc链表存放了lua所有的可回收对象，而事实上gc链表存放的只是所有可回收对象的指针，真正的对象还是以TValue（GCObject* gc成员）的形式放在lua栈中的。当然，对象真正的内容是在堆上（需要自己回收）。而栈和gc链表中存在的只是真实对象的指针，不同类型的结构不一样，所以以这种方式才能存在一起管理

• 2.怎么做到的？

前面提到了CommonHead，它在栈和gc链表关系中起了关键的作用。有相同的头部，所以可以通过强制转换在TValue和GCObject直接为了当时需要进行切换.看源码更清晰了，能够转换为GCObject的结构体都是必须包含这个头部的，需要GC的结构都要添加这个头部，如下所所示：

//
struct lua_State {
  CommonHeader;
//

typedef struct Table {

CommonHeader;
//

typedef struct UpVal {

CommonHeader;
//

typedef struct Proto {

CommonHeader;
//

typedef union Udata {

L_Umaxalign dummy;  /* ensures maximum alignment for `local' udata */

struct {

CommonHeader;
typedef union TString {

L_Umaxalign dummy;  /* ensures maximum alignment for strings */

struct {

CommonHeader;

总结

• 这里并没有把所有的结构体都解释一遍，userdata，upvalue相关的都是比较细节的东西，可以单独看相关的内容，在全局理解的情况下根据自身特性去看也会很容易明白