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的低三位,标记的具体值为:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
#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

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

—|—

新增分代使用的全局变量

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
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之间的转换

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
// 进入到分步模式  
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类型进行不同的操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

    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);  
  }  
}  

—|—

  1. 分代step

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25

    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 */  
  }  
}  

—|—

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

    1
    2
    3
    4

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

—|—

  1. young gc

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37

    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);  
}  

—|—

  1. markold

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

    // 从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);  
      }  
    }  
  }  
}  

—|—

  1. sweepgen

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29

    // 从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;  
}  

—|—

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

  2. finishgencycle

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

    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);  
}  

—|—

  1. correctgraylist

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40

    // 对列表进行操作,前面说了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)) {  
<span class="l

糖果

糖果
LUA教程

如果不小心安装错 SQL Server 为 Evaluation 的版本,要小心当超过 180 天之后,系统就会无法正常使用了 这几天遇到一个蛮特别的案例,原本收到的问题是 “维护计划” 忽然无法使用,即便是里面没有任何的Task,都无法顺利地执行。但从对方所提供的错误消...… Continue reading

PLUM NIZ静电容键盘怎么样?

Published on September 25, 2020

程序员如何选择合适的机械键盘

Published on September 18, 2020