Lua的垃圾回收(下)

ronald3个月前职场1800

Lua 5.3版本的垃圾回收

Lua垃圾回收源码实现

    结合前面描述的垃圾回收的流程,我们参照源码进行逐个的拆解和介绍。

    lua的垃圾回收主要都是在接口luaC_step里面完成的,这里面本质上是控制了一个状态机,根据global_State->gcstate进行渐进式的垃圾回收处理。

GCSpause

    GCSpause是Lua垃圾回收的起始状态,这一步的核心逻辑在接口restartcollection中,主要任务是将根节点集合标记为灰色,建立灰色初始链表,具体实现如下:

/*
** mark root set and reset all gray lists, to start a new collection
*/
static void restartcollection (global_State *g) {
  g->gray = g->grayagain = NULL;
  g->weak = g->allweak = g->ephemeron = NULL;
  markobject(g, g->mainthread);
  markvalue(g, &g->l_registry);
  markmt(g);
  markbeingfnz(g);  /* mark any finalizing object left from previous cycle */
}

/*
** mark an object. Userdata, strings, and closed upvalues are visited
** and turned black here. Other objects are marked gray and added
** to appropriate list to be visited (and turned black) later. (Open
** upvalues are already linked in 'headuv' list.)
*/
static void reallymarkobject (global_State *g, GCObject *o) {
 reentry:
  white2gray(o);
  switch (o->tt) {
    case LUA_TSHRSTR: {
      gray2black(o);
      g->GCmemtrav += sizelstring(gco2ts(o)->shrlen);
      break;
    }
    case LUA_TLNGSTR: {
      gray2black(o);
      g->GCmemtrav += sizelstring(gco2ts(o)->u.lnglen);
      break;
    }
    case LUA_TUSERDATA: {
      TValue uvalue;
      markobjectN(g, gco2u(o)->metatable);  /* mark its metatable */
      gray2black(o);
      g->GCmemtrav += sizeudata(gco2u(o));
      getuservalue(g->mainthread, gco2u(o), &uvalue);
      if (valiswhite(&uvalue)) {  /* markvalue(g, &uvalue); */
        o = gcvalue(&uvalue);
        goto reentry;
      }
      break;
    }
    case LUA_TLCL: {
      linkgclist(gco2lcl(o), g->gray);
      break;
    }
    case LUA_TCCL: {
      linkgclist(gco2ccl(o), g->gray);
      break;
    }
    case LUA_TTABLE: {
      linkgclist(gco2t(o), g->gray);
      break;
    }
    case LUA_TTHREAD: {
      linkgclist(gco2th(o), g->gray);
      break;
    }
    case LUA_TPROTO: {
      linkgclist(gco2p(o), g->gray);
      break;
    }
    default: lua_assert(0); break;
  }
}

restartcollection用于重新开启一轮GC,在接口中有:

1)先将灰色链表g->gray、弱引用链表g->weak等重置,其中

    ·g->gray普通的灰色对象表

    ·g->grayagain是在分布标记阶段被重新置灰的对象组成的表

2)对主线程的对象进行标记markobject(g, g->mainthread)

3)对注册表的对象进行标记markvalue(g, &g->l_registry)

4)对基础类型的元表进行标记markmt,其中markmt处理的是基本类型的metatable是全局元表

5)对tobefnz链表进行标记

    ·上述流程底层都是reallymarkobject接口

    ·接口reallymarkobject中,对于值类型对象直接设置为black,对于闭包、tablethreadproto等引用类型添加到灰色链表,作为灰色链表的初始集合

    ·reallymarkobject建立gray表,是通过接口linkgclist采取头插法进行插入,通过字段gclist进行节点间的串联

    ·无论是white2gray还是gray2black,都是对CommonHeader->marked字段进行对应比特位的设置

    总结下来,这一步就是将根集合的值类型设置为black,其他非值类型设置为灰,添加到global_state->gray表中,建立灰色表的初始集合之后进入GCSpropagate状态。

GCSpropagate

    分步标记阶段,轮询灰色链表,若链表非空,则pop一个对象遍历其子对象进行处理,直到灰色链表为空(为空则进入到GCSatomic状态),主要逻辑在接口propagatemark

static void propagatemark (global_State *g) {
  lu_mem size;
  GCObject *o = g->gray;
  lua_assert(isgray(o));
  gray2black(o);
  switch (o->tt) {
    case LUA_TTABLE: {
      Table *h = gco2t(o);
      g->gray = h->gclist;  /* remove from 'gray' list */
      size = traversetable(g, h);
      break;
    }
    case LUA_TLCL: {
      LClosure *cl = gco2lcl(o);
      g->gray = cl->gclist;  /* remove from 'gray' list */
      size = traverseLclosure(g, cl);
      break;
    }
    case LUA_TCCL: {
      CClosure *cl = gco2ccl(o);
      g->gray = cl->gclist;  /* remove from 'gray' list */
      size = traverseCclosure(g, cl);
      break;
    }
    case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      g->gray = th->gclist;  /* remove from 'gray' list */
      linkgclist(th, g->grayagain);  
      black2gray(o);
      size = traversethread(g, th);
      break;
    }
    case LUA_TPROTO: {
      Proto *p = gco2p(o);
      g->gray = p->gclist;  /* remove from 'gray' list */
      size = traverseproto(g, p);
      break;
    }
    default: lua_assert(0); return;
  }
  g->GCmemtrav += size;
}

propagatemark接口中:

(1)gray2black(o):取灰色队列的队头并设置为黑,设置marked字段的BLACKBIT

(2)针对队头元素类型不同调用不同接口进行处理:

·table类型,取接口traversetable进行处理

    非弱引用表,调用接口traversestrongtable进行处理,本质上遍历table的顺序数组和哈希表部分,调用接口markvalue进行处理。

    弱引用表,则:

    1)弱引用val表,调用接口traverseweakvalue处理,key部分markvalue常规处理,并将表放入grayagain

    2)弱引用key表,调用接口traverseephemeron处理,val部分通过reallymarkobject进行标记,然后把表放到grayagain

    3)kv都是弱引用,直接插入到allweak链表中

    总结起来,在渐进标记阶段对于强引用表的key、val通过接口markvalue进行标记(就是进行灰色和黑色标记);对于弱引用表强引用部分正常使用markvalue进行标记,弱引用部分丢到grayagain链表等到统一后面阶段统一处理。

·closure类型,取traverseLclosuretraverseCclosure处理

    1)closure分为两个部分,proto部分和upvalue部分

    2)proto部分,通过markobjectN进行处理,将proto添加到灰色表中

    3)upvalue部分,非open状态的upvalue通过markvalue进行标记;open状态的upvalue在栈上,后续处理thread的时候会处理到,这里先标记

·thread类型,取traversethread进行处理

    1)lua的线程中global_state->stackglobal_stack->top分别存放线程栈的栈顶和栈底

    2)traversethread在此阶段遍历栈,取里面每个object进行处理,调用接口markvalue进行标记

·proto类型,取traverseproto进行处理

    1)proto包含upvaluelocvarconstantproto几个部分

    2)各个部分通过markobjectN进行处理


GCSatomic

    当灰色节点已经被处理处理完毕之后if (g->gray == NULL){}垃圾回收进入GCSatomic阶段,分为几个部分:

propagateall

static void propagateall (global_State *g) {
  while (g->gray) propagatemark(g);
}

    propagateall因为从propagate到atomic阶段非连续执行,期间节点状态可能会发生变化,因此在后续处理之前遍历gray链表,把残余的灰色节点处理完,以统一的状态进入下一状态。

atomic

static l_mem atomic (lua_State *L) {
  GCObject *grayagain = g->grayagain;  /* save original list */
  g->gcstate = GCSinsideatomic;
  markobject(g, L);  /* mark running thread */
  /* registry and global metatables may be changed by API */
  markvalue(g, &g->l_registry);
  markmt(g);  /* mark global metatables */
  remarkupvals(g);
  propagateall(g);  /* propagate changes */
  work = g->GCmemtrav;  
  g->gray = grayagain;
  propagateall(g);  /* traverse 'grayagain' list */
  g->GCmemtrav = 0;  /* restart counting */
  convergeephemerons(g);
  clearvalues(g, g->weak, NULL);
  clearvalues(g, g->allweak, NULL);
  origweak = g->weak; origall = g->allweak;
  work += g->GCmemtrav;  /*stop count (objects being finalized) */
  separatetobefnz(g, 0);  /* separate objects to be finalized */
  g->gcfinnum = 1;  /* there may be objects to be finalized */
  markbeingfnz(g);  /* mark objects that will be finalized */
  propagateall(g);  /* remark, to propagate 'resurrection' */
  g->GCmemtrav = 0;  /* restart counting */
  convergeephemerons(g);
  /* at this point, all resurrected objects are marked. */
  /* remove dead objects from weak tables */
  clearkeys(g, g->ephemeron, NULL); 
  clearkeys(g, g->allweak, NULL); 
  /* clear values from resurrected weak tables */
  clearvalues(g, g->weak, origweak);
  clearvalues(g, g->allweak, origall);
  luaS_clearcache(g);
  g->currentwhite = cast_byte(otherwhite(g));  /
  return work;  /* estimate of memory marked by 'atomic' */
}

(1)切换内存回收的状态GCSinsideatomic

(2)GCSpropagateGCSinsideatomic中间内存状态会发生变化,需要对:

    ·主线程:markobject(g,L)

    ·注册表:markvalue(g,&g->l_registry)

    ·原始元表:markmt(g)

    ·僵死线程:remarkupvals(g)进行重新标记,加入gray

    ·并通过propagateallgraygrayagain进行统一处理

    ·通过一系列clearvaluesclearkeys释放一些内存

    ·convergeephemerons?

    1)global_state->ephemeron存放的是key为弱引用的table组成的链表

    2)convergeephemerons中遍历链表,调用traverseephemeron接口处理

  ·切换currentwhite的白色状态

    结合前面来看,因为在此执行序列中,期间创建的对象通过atomic接口在前面已经标记了一份,所以不存在临时创建但未标记的object,但是后续过程也是分步进行的,为避免出现冲突,在这里切换currentwhite状态,这样后续创建的对象的white为新类型且和之前的white类型不同,就不会被错误回收掉。

entersweep

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  global_State *g = G(L);
  int ow = otherwhite(g);
  int white = luaC_white(g);  /* current white */
  while (*p != NULL && count-- > 0) {
    GCObject *curr = *p;
    int marked = curr->marked;
    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* change mark to 'white' */
      curr->marked = cast_byte((marked & maskcolors) | white);
      p = &curr->next;  /* go to next element */
    }
  }
  return (*p == NULL) ? NULL : p;
}

static void entersweep (lua_State *L) {
  global_State *g = G(L);
  g->gcstate = GCSswpallgc;
  lua_assert(g->sweepgc == NULL);
  g->sweepgc = sweeplist(L, &g->allgc, 1);
}

entersweep做了两件事:

    1)切换GC状态GCSswpallgc

    2)sweepgc指向后续垃圾回收的起始扫描位置,在当前位置指向allgc链表

    为什么是指向g->allgc->next呢?因为entersweep之后,GC流程又进入了增量分步执行的状态,此期间有新对象创建又会挂在allgc链表头,被g->allgc指向,此时头部的元素一定为白且不能回收,为了避免这种情况,直接从第二个开始遍历回收即可。


GCSswpallgc

static lu_mem sweepstep (lua_State *L, global_State *g,
                         int nextstate, GCObject **nextlist) {
  if (g->sweepgc) {
    l_mem olddebt = g->GCdebt;
    g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
    g->GCestimate += g->GCdebt - olddebt;  
    if (g->sweepgc)  /* is there still something to sweep? */
      return (GCSWEEPMAX * GCSWEEPCOST);
  }
  /* else enter next state */
  g->gcstate = nextstate;
  g->sweepgc = nextlist;
  return 0;
}

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  global_State *g = G(L);
  int ow = otherwhite(g);
  int white = luaC_white(g);  /* current white */
  while (*p != NULL && count-- > 0) {
    GCObject *curr = *p;
    int marked = curr->marked;
    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* change mark to 'white' */
      curr->marked = cast_byte((marked & maskcolors) | white);
      p = &curr->next;  /* go to next element */
    }
  }
  return (*p == NULL) ? NULL : p;
}

(1)GCSswpallgc步做的工作包括:

回收global_state->allgc链表上的元素

并设置垃圾回收状态为GCSswpfinobj

设置下次链表回收的起始位置为global_state->finobj

(2)global_state->finobj这个链表存有具有回收接口的可回收对象;在lua中,当调用接口luaC_newobj创建一个可回收对象的时候,会将其添加到allgc列表中,但是在后续处理这个对象的时候,在lua_setmetatable里面,即设置元表的时候会检查,是不是设置了__gc元方法,若设置了,则通过接口luaC_checkfinalizer将这个对象移到finobj列表中

(3)前面提到Lua的三色标记法,分别是黑白灰三色,但实际上Lua的白色分为0型白色和1型白色,这是因为Lua的GC是渐进式分步骤进行的,在标记完成之后清理尚未完成之前,可能会有对象创建,因为对象在标记之后,默认是白色的,此时若是按照白色进行处理会被回收掉,又不能设置为黑(设置黑之后若是此对象不再被引用则就一直黑了,没办法翻白被回收)所以引申出0型白和1型白,叠加lua_state->currentwhite进行判断是否是当前白,当对象刚创建出来的时候,默认为白色,且白的类型和lua_state->currentwhite保持一致,此时清理的时候先判断是不是当前白luaC_white,是的话表示是垃圾回收阶段创建的对象,暂不清理,等下个阶段lua_state->currentwhite翻成另外一个类型白(假设上个阶段是0型白,下个阶段就变成1型阶段)这个在atomic接口进行,若此对象在下个阶段仍为白,则变成非当前白otherwhite表示非垃圾清理阶段创建的对象且未被引用,可以清理了

(4)而sweeplist,主要就是遍历垃圾回收链表p,对于里面的元素

    ·此节点为white节点&且非当前标白的节点(!0)

    ·GCObject->marked:用于记录当前对象的颜色:白色-0、白色-1、还是黑色;分别对应marked的bit-1(1<<0)、bit-2(1<<1)、bit-3(1<<2)

    ·在创建时设置上,表示当前对象是白色,且白的类型和lua_state->currentwhite一致

    ·isdeadm为true表示此对象为:

    ·否则标记此对象为当前白(同时也 把black标记bit给清除了)

(5)需要注意的是:

    ·lua_state->currentwhite的初始值为1,在atomic接口中会通过otherwhite进行切换,值的切换是1->2和2->1

    ·这里看代码有#define otherwhite(g) ((g)->currentwhite ^ WHITEBITS),这是C的代码,所以这里的^代表的含义是异或,而初始值g->currentwhite = bitmask(WHITE0BIT)为1,在atomic中通过otherwhite进行切换,即1^3切换为2,和2^3切换为1

GCSswpfinobj

GCSswptobefnz

    ·依次处理链表g->finobjg->tobefnz上的对象,并进行状态的切换

GCSswpend

    ·makewhite(g,g->mainthread)mainthread重置为curr-white(luaC_white)

GCScallfin

static GCObject *udata2finalize (global_State *g) {
  GCObject *o = g->tobefnz;  /* get first element */
  g->tobefnz = o->next;  /* remove it from 'tobefnz' list */
  o->next = g->allgc;  /* return it to 'allgc' list */
  g->allgc = o;
  resetbit(o->marked, FINALIZEDBIT);  /* object is "normal" again */
  if (issweepphase(g))
    makewhite(g, o);  /* "sweep" object */
  return o;
}

static void GCTM (lua_State *L, int propagateerrors) {
  setgcovalue(L, &v, udata2finalize(g));
  tm = luaT_gettmbyobj(L, &v, TM_GC);
  if (tm != NULL && ttisfunction(tm)) {  /* is there a finalizer? */
    lu_byte oldah = L->allowhook;
    setobj2s(L, L->top, tm);  /* push finalizer... */
    setobj2s(L, L->top + 1, &v);  /* ... and its argument */
    L->top += 2;  /* and (next line) call the finalizer */
    L->ci->callstatus |= CIST_FIN;  /* will run a finalizer */
    status = luaD_pcall(L,dothecall,NULL,savestack(L,L->top - 2), 0);
    L->ci->callstatus &= ~CIST_FIN;  
    L->allowhook = oldah;  /* restore hooks */
    g->gcrunning = running;  /* restore state */
    if (status != LUA_OK && propagateerrors) {  /* error while running __gc? */
      if (status == LUA_ERRRUN) {  /* is there an error object? */
        luaO_pushfstring(L, "error in __gc metamethod (%s)", msg);
        status = LUA_ERRGCMM;  /* error in __gc metamethod */
      }
      luaD_throw(L, status);  /* re-throw error */
    }
  }
}

(1)Lua的对象创建之后,若是对象设置有元表,则这个对象会放到global_state->finobj链表里面管理,在垃圾回收过程中,在atomic阶段的separatetobefnz接口中,若finobj里面的对象不可达(即iswhite),则会被移入到global_state->tobefnz链表中。

(2)对于具有gc元方法的object,在当前轮次的垃圾回收并不直接回收,而是先执行其元方法,执行完毕之后放回到allgc链表中,等下次gc做回收,主要通过如下接口完成:

    ·udata2finalizetobefnz链表中的对象放到allgc链表中;

    ·luaT_gettmbyobjgc元方法,通过luaD_pcall执行;

    因为对于Lua来说GC元方法可能是开协程执行的,所以很难说在一个回收周期里面做完,所以这里对具备回收条件的带元方法的对象,将gc方法和实际对象的回收放到两个回收周期里面做,避免执行流等待或者一些指令执行的时序问题。


参考文献

    Lua GC机制分析与理解-上 - 知乎 (zhihu.com)

    Lua垃圾回收机制和弱引用table - 简书 (jianshu.com)

    Lua 5.3 设计实现(六) GC 垃圾回收 | Yuerer's Blog

    云风的 BLOG: Lua GC 的工作原理 (codingnow.com)

    深入 Lua Garbage Collector(四) | 趣果有间 (kelele67.github.io)

    lua垃圾回收机制格物致知-CSDN博客lua垃圾回收

    [Lua]弱表Weak table超越-CSDN博客lua 弱表





相关文章

K8S实战技巧(一)

一. 概述        K8S是谷歌开源的一个容器编排管理工具,可以帮助业务实现自动化部署、故障发现、容灾、扩缩容、流量管理等,大大提升业务的服务能力;k8s通过yaml描述文件实现容器的部署,本文介绍一些实际应用过程中可能用到一些k8s的特性及配置方法,适用于对k8s有一定了解的读者。二. 共享进程命名空间&nbs...

K8S背景

    在深入了解K8S之前,我们先了解一下K8S产生的背景,看下是为了解决怎样的问题一步步衍生出K8S这样一套系统。一. 微服务化    随着需求的发展,单体应用的复杂度越来越高,大大增加了系统现网的运维成本,主要包括以下几个方面。    1. 模块耦合度提升,维护成本高&nb...

关于LUA(下)

关于LUA(下)

Lua与OOP    Lua是面向过程的语言,不提供面向对象的特性,但是我们可以利用Lua的元表和元方法模拟面向对象的效果。OOP的特性封装    所谓封装,是隐藏对象的属性和细节,仅对外暴露公共的访问方式。本质上分为两层:    1)成员变量和成员方法,提升代码的内聚性,降低模...

K8S入门-概念篇(上)

K8S入门-概念篇(上)

    认识到K8S的产生背景之后,我们开始进一步了解K8S,基于对K8S里面一些概念的了解之后,我们再去探讨K8S的一些原理:一. node    如前所述,K8S是一个容器编排平台,即容器的自动部署、扩展和管理;其最终的落点是把容器调度到一个运行他的节点上,在K8S中这个运行容器的节点就是node,但是需要注意的是...

第四次引擎编程尝试

第四次引擎编程尝试

本节我们将尝试在游戏中创建AI,并针根据游戏内的事件做出对应的反应。创建自己的AI类· 按照介绍的,先创建一个我们的AI类,因为AI可以移动、碰撞等,所以我们选择其继承自Character· 创建好AI类之后,我们创建其蓝图类· 创建好蓝图我们进入AI的编辑界面从界面中,我们可以看到:    我们的FPSTpl2AIGuard继承自Character,拥有A...

协程-无栈协程(下)

无栈协程库——protothread    ProtoThread源码如下所示:#define LC_INIT(s) s = 0; #define LC_RESUME(s) switch(s) { case 0: #define LC_SET(s)...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。