lua 5.4分代研究及luajit分代移植

lua垃圾回收发展历程

• 为什么不用引用计数？

  1. 引用计数有循环引用问题，会导致内存泄漏
  2. 应用计数嗯外开销大，赋值的时候会带来额外引用计数计算的开销。尤其是在内存比较稳定，没有新内存申请和释放的时候，你也需要承担这部分开销。

• 5.0及以前使用的是stop the world的标记清除法，会卡住所有操作，直到gc完成

• 5.1引入了分步gc，整个gc过程可以分为好几步，穿插在运行过程中
• 5.2引入了分代gc，属于实验性质，实际效果不好，在5.3的时候又移除了
• 5.4重新分代了分代gc，具体实现方式会在后面介绍

分代gc原理

经验表明，大部分对象在被分配之后很快就被回收掉了，长时间存活的对象很大可能会一直存活下去。所以，垃圾回收可以集中精力去回收刚刚造出来的对象。
将所有gc对象分成两种，young和old。当young节点活过了两次gc过程，就会变成old。old节点将不再被清除和遍历。
活过两次gc过程也是与5.2 gc过程的最大不同点。5.2 gc只需要活过一次，就算做old。但是往往可能当前在某个函数执行过程中申请了临时变量触发了gc，这时候如果gc完成的话，当前函数堆栈上面申请的所有临时变量都会被误标记为old，导致内存一直在上涨。
如何确保往old节点加入新的节点也能正确的遍历？新增touched状态，如果old节点加入新的节点，则该old节点变成touched状态，经过两次gc之后，touched节点又重新变为old节点。

5.4分代具体实现

需要对分步gc有一定了解

新增一个old标记的概念，存放在marked的低三位，标记的具体值为：

#define G_SURVIVAL	1	// 当前gc存活下来的对象;
#define G_OLD0		2	// 当前gc循环被barrier forward的节点，如果被插入的节点为isold()为true的节点;
#define G_OLD1		3	// 活过了一次完整的gc;
#define G_OLD		4	// 活过了两次完整的gc，标记为G_OLD，不再被访问;
#define G_TOUCHED1	5	// old节点被插入新节点;
#define G_TOUCHED2	6	// G_TOUCHED1节点经过一次完整的gc还没有新的节点插入;

#define AGEBITS		7   // age使用的位mask，age只使用了marked的0,1,2字段;

#define getage(o)	((o)->marked & AGEBITS)
#define setage(o,a)  ((o)->marked = cast_byte(((o)->marked & (~AGEBITS)) | a))
#define isold(o)	(getage(o) > G_SURVIVAL)		// 大于G_SURVIVAL都为old;

// 开启lua_assert模式下会先判断age是否为f状态，之后在赋值;
#define changeage(o,f,t)  
    check_exp(getage(o) == (f), (o)->marked ^= ((f)^(t)))

整个age标记变化过程:

• G_NEW -> G_SURVIVAL -> G_OLD1 -> G_OLD
  从G_NEW到G_OLD实际上经过了三次gc，但是被打上G_OLD1标记的节点在gc开始前会被重新mark，所以肯定是会进入到G_OLD状态。为什么会有这个过程？因为节点在G_SURVIVAL的状态时候可能会被插入子节点，这时候无论是barrier forward或者barrier back都不会触发isold判断，所以经过这次gc如果G_SURVIVAL直接进入到G_OLD的话，子节点则处在G_SURVIVAL，那下次gc触发的时候子节点可能会被误删。那为什么要增加一个G_SURVIVAL状态？我讲讲自己的理解，可能不太正确。因为lua 5.2证明了一次gc直接进入到old是不理想的，所以如果G_NEW经过一次gc直接进入到G_OLD1，那如果在这时候触发barrier back的时候，该节点无论如何最终会随着没有新的子节点加入，会直接进入到G_OLD标记。这就相当于一次gc之后就判断为old了。所以最佳方案就是引入了G_OLD1节点.
• G_OLD0 -> G_OLD1 -> G_OLD
  G_OLD0只会在barrier_forward过程中，如果父节点被isold判断成立，则进行mark并且标记为G_OLD0，但是这里会有问题，被mark之后肯定能活过当前gc，那状态肯定能变为G_OLD1，而G_OLD1会在gc开始之前进行一次标记，所以G_OLD1的节点肯定能活过gc过程，这样G_OLD1就一定会变成G_OLD。也就是说打上G_OLD0的节点肯定会变为G_OLD（疑惑？）
• G_OLD0/G_OLD1/G_OLD2/G_TOUCHED2 -> G_TOUCHED1 -> G_TOUCHED2 -> G_OLD
  因为isold判断函数使用了age > G_SURVIVAL，所以G_OLD0/G_OLD1/G_OLD2/G_TOUCHED2节点如果插入子节点的话，在barrier back过程中都会变为G_TOUCHED1

  新增gc类型，表示当前处于分步gc还是分代gc，存放在g->gckind

  /* kinds of Garbage Collection */
  #define KGC_INC		0	/* incremental gc */
  #define KGC_GEN		1	/* generational gc */

新增分代使用的全局变量

typedef struct  {
  // ...
  
  lu_byte genminormul;  // 控制执行一次分代小gc的时机
  lu_byte genmajormul;  // 控制执行一次分代大gc(full gc)的时机
  
  GCObject *survival;  // 指向活过一次gc的节点
  GCObject *old;       // 指向活过两次的gc节点
  GCObject *reallyold; // 指向被标记为G_OLD的开始节点
  GCObject *finobjsur; // 意义同上面三个变量，指向的是带有"__gc"元方法的userdata或者table
  GCObject *finobjold; 
  GCObject *finobjrold;
  
  //...
} global_State;

两种gc之间的转换

// 进入到分步模式
static void enterinc (global_State *g) {
  // 1. 把所有节点标记为白色
  whitelist(g, g->allgc);
  
  // 2. 清空分代的变量
  g->reallyold = g->old = g->survival = NULL;
  whitelist(g, g->finobj);
  whitelist(g, g->tobefnz);
  g->finobjrold = g->finobjold = g->finobjsur = NULL;
  
  // 3. 初始化gc状态
  g->gcstate = GCSpause;、
  
  // 4. 初始化gc类型
  g->gckind = KGC_INC;
}

// 进入到分代模式
static void entergen (lua_State *L, global_State *g) {
  // 1. 执行一次完整的遍历过程
  luaC_runtilstate(L, bitmask(GCSpause));  /* prepare to start a new cycle */
  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
  atomic(L);
  
  // 2. 清除过期的对象，同时把所有对象存活的对象标记为G_OLD
  sweep2old(L, &g->allgc);
  
  // 3. 初始化分代变量
  g->reallyold = g->old = g->survival = g->allgc;

  sweep2old(L, &g->finobj);
  g->finobjrold = g->finobjold = g->finobjsur = g->finobj;

  sweep2old(L, &g->tobefnz);

  // 3. 初始化gc类型
  g->gckind = KGC_GEN;
  
  // 4. 设置基础内存值
  g->GCestimate = gettotalbytes(g);  /* base for memory control */
  
  // 5. finishgencycle里做了很多事情，这里用到了它去回调所有设置了"__gc"元方法的table或者userdata
  finishgencycle(L, g);
}

分代gc过程

1. 触发gc step，根据gc类型进行不同的操作

   void luaC_step (lua_State *L) {
     global_State *g = G(L);
     if (g->gcrunning) {  /* running? */
   
   	// 根据当前gc处于什么类型进入到不同的step中;
       if (g->gckind == KGC_INC)
         incstep(L, g);
   	else
   	  genstep(L, g);
     }
   }

2. 分代step

   static void genstep (lua_State *L, global_State *g) {
   
     // 保存基础值，该基础值会在entergen初始化;
     lu_mem majorbase = g->GCestimate;
     int majormul = getgcparam(g->genmajormul);
   
     // 判断是否该进行full gen gc;
     // 判断条件为当前总内存值是否为上次full gc完成内存的(100+genmajormul)%;
     if (g->GCdebt > 0 &&
         gettotalbytes(g) > (majorbase / 100) * (100 + majormul)) {
       fullgen(L, g);
     }
     else {
   	// 执行一次young gc;
       lu_mem mem;
       youngcollection(L, g);
       mem = gettotalbytes(g);
       
       // 重新设置下次进行小gc的时机
       luaE_setdebt(g, -(cast(l_mem, (mem / 100)) * g->genminormul));
   
   	// 重新赋值为基础值;
       g->GCestimate = majorbase;  /* preserve base value */
     }
   }

3. full gen gc，很简单的利用enterinc和entergen两个函数

   static void fullgen (lua_State *L, global_State *g) {
     enterinc(g);
     entergen(L, g);
   }

4. young gc

   static void youngcollection (lua_State *L, global_State *g) {
     GCObject **psurvival;  /* to point to first non-dead survival object */
     lua_assert(g->gcstate == GCSpropagate);
     
     // 将G_OLD1的所有的黑色节点，重新mark一次，原因在age变化过程中有写
     markold(g, g->survival, g->reallyold);
     markold(g, g->finobj, g->finobjrold);
     
     // 标记节点
     atomic(L);
   
     // 遍历此次创建的节点，free掉没被引用的节点，设置被引用的节点到新的age状态;
     // 返回的psurvival指向的是g->survival的上一个节点的next指针;
     // 这样可以确保g->survival能进行正确的删除操作
     psurvival = sweepgen(L, g, &g->allgc, g->survival);
     
     // 对psurvival到g->reallyold的节点进行相同操作;
     sweepgen(L, g, psurvival, g->reallyold);
     
     // 重新设置三个指针
     g->reallyold = g->old;
     g->old = *psurvival;  /* 'survival' survivals are old now */
     g->survival = g->allgc;  /* all news are survivals */
   
     /* repeat for 'finobj' lists */
     psurvival = sweepgen(L, g, &g->finobj, g->finobjsur);
     /* sweep 'survival' and 'old' */
     sweepgen(L, g, psurvival, g->finobjrold);
     g->finobjrold = g->finobjold;
     g->finobjold = *psurvival;  /* 'survival' survivals are old now */
     g->finobjsur = g->finobj;  /* all news are survivals */
   
     sweepgen(L, g, &g->tobefnz, NULL);
   
     // 进行分代gc的后续操作
     finishgencycle(L, g);
   }

5. markold

   // 从from到to，如果节点为G_OLD1并且为黑色，则进行mark，不是黑色表明，该节点已经被mark，所以不用在mark
   static void markold (global_State *g, GCObject *from, GCObject *to) {
     GCObject *p;
     for (p = from; p != to; p = p->next) {
       if (getage(p) == G_OLD1) {
         lua_assert(!iswhite(p));
         if (isblack(p)) {
           black2gray(p);  /* should be '2white', but gray works too */
           reallymarkobject(g, p);
         }
       }
     }
   }

6. sweepgen

   // 从p开始到limit，如果该节点没有被mark过则清除，否则将age设置到下一状态
   static GCObject **sweepgen (lua_State *L, global_State *g, GCObject **p,
                               GCObject *limit) {
     static lu_byte nextage[] = {
       G_SURVIVAL,  /* from G_NEW */
       G_OLD1,      /* from G_SURVIVAL */
       G_OLD1,      /* from G_OLD0 */
       G_OLD,       /* from G_OLD1 */
       G_OLD,       /* from G_OLD (do not change) */
       G_TOUCHED1,  /* from G_TOUCHED1 (do not change) */
       G_TOUCHED2   /* from G_TOUCHED2 (do not change) */
     };
     int white = luaC_white(g);
     GCObject *curr;
     while ((curr = *p) != limit) {
       if (iswhite(curr)) {  /* is 'curr' dead? */
         lua_assert(!isold(curr) && isdead(g, curr));
         *p = curr->next;  /* remove 'curr' from list */
         freeobj(L, curr);  /* erase 'curr' */
       }
       else {  /* correct mark and age */
         if (getage(curr) == G_NEW)
           curr->marked = cast_byte((curr->marked & maskgencolors) | white);
         setage(curr, nextage[getage(curr)]);
         p = &curr->next;  /* go to next element */
       }
     }
     return p;
   }

7. 一些细节
   分代模式充分利用了grayagain这个链表，在atomic开始之处会把该链表先保存起来，然后置空。因为在atomic的遍历过程中会有新的节点加入到grayagain，例如线程，table或者弱key的table。在gen结束的时候会再次遍历grayagain链表，进行touched状态的相关操作
   分代只有才gc过程中会处于atomic节点，其他清空下都是一直处于GCSpropagate状态

8. finishgencycle

   static void finishgencycle (lua_State *L, global_State *g) {
   
     // 遍历所有grayagain以及weak系table链表进行操作
     correctgraylists(g);
     
     // 查看是否需要进行string表resize操作
     checkSizes(L, g);
     g->gcstate = GCSpropagate;  /* skip restart */
     
     // 调用所有的table或者userdata的"__gc"元方法
     if (!g->gcemergency)
       callallpendingfinalizers(L, 1);
   }

9. correctgraylist

   // 对列表进行操作，前面说了graygain链表会在最后进行touched相关的操作
   static GCObject **correctgraylist (GCObject **p) {
     GCObject *curr;
     while ((curr = *p) != NULL) {
       switch (curr->tt) {
         case LUA_TTABLE: case LUA_TUSERDATA: {
           GCObject **next = getgclist(curr);
           if (getage(curr) == G_TOUCHED1) {  /* touched in this cycle? */
             // 处于G_TOUCHED1状态，则变为G_TOUCHED2，并且保留在grayagain链表
             lua_assert(isgray(curr));
             gray2black(curr);  /* make it black, for next barrier */
             changeage(curr, G_TOUCHED1, G_TOUCHED2);
             p = next;  /* go to next element */
           }
           else {
             if (!iswhite(curr)) {