学校网站建设 分工,wordpress备份插件中文,app登录wordpress,做外汇模拟的网站关于lua的gc云风大佬在 Lua GC 的源码剖析 系列文章中讲得很清楚#xff0c;这里做一下简单的记录。
分步gc
lua使用的是一种三色标记清除算法#xff08;tri-color incremental mark sweep#xff09;#xff0c;大体步骤如下#xff1a; 初始阶段#xff0c;所…关于lua的gc云风大佬在 Lua GC 的源码剖析 系列文章中讲得很清楚这里做一下简单的记录。
分步gc
lua使用的是一种三色标记清除算法tri-color incremental mark sweep大体步骤如下 初始阶段所有对象标为白色 标记阶段的开始将所有从root可达的对象标记为灰色 标记阶段逐个取出灰色对象将其本身标记为黑色将其所有引用的白色对象标记为灰色 当不存在灰色对象时进入清除阶段清除所有白色对象将所有黑色对象标记回白色。
具体而言lua的gc分为markroot、mark、atomic、sweepstring、sweep、finalize几个阶段见singlestep()。 markroot函数将若干lua对象链表的根节点置为灰色放入gray链表/队列mark阶段类似树的广度优先遍历从gray队列中取出灰色对象标为黑色再将其所引用的对象置为灰色加入gray队列mark是分步执行的中间对象关系可能又发生变化在开始清理工作前还需要做最后一次扫描这个过程不可以再被打断就是atomic函数sweepstring阶段分步清理字符串sweep阶段分步清理其他对象userdata对象可能会有自定义gc方法finalize阶段就用来调用这些gc方法userdata对象本身则放在下轮gc清理。
标记阶段和清除阶段都是可以分步的所以称为分步gc。但中间可能出现这样的情况A引用BB引用CA已经标记为黑色B标记为灰色C为白色在gc间歇期间程序修改了对象间的引用关系 B不再引用C而A开始引用C。C本来是活跃对象但却会被清除这会造成严重错误。算法引入写屏障技术来解决这种问题将此 白色 对象标记成 灰色称为barrier forward因为正常是白色-灰色-黑色的转换方向将此 黑色 对象标记回 灰色称为barrier back。
如何确定gc的步伐大小是一系列的微操见singlestep()、luaC_setp()。
数据类型
在Lua中共有9种数据类型分别为nil、boolean、lightuserdata、number、string、table、function、userdata和thread。其中只有string table function thread四种在vm中以引用方式共享是需要被GC管理回收的对象。其它类型都以值形式存在。 另外还有两种类型的对象需要被GC管理分别是proto和upvalue。
string创建后挂载于g-strt-hash upvalue创建后被链在g-uvhead table、thread、function、proto则都是挂在g-rootgc上在mark阶段简单加到gray队列即可
markroot
有3个链表用于标记和清理过程gray是灰色对象的链表grayagain是在atomic阶段需要再次标记的对象的链表weak是弱表的链表。 markroot()先将这三个链表清空再将mainthread、mainthread的全局表、注册表、各类型元表标记放到gray队列中开始mark阶段。
string
mark的时候只是置灰不挂载到gray上所以它没有黑色。 在sweepstring阶段集中处理g-strt-hash。
userdata
rootgc初始化为mainthread创建其他对象时使用的是头部插入所以mainthread是链表的最后一个元素。 但是luaS_newudata()中将userdata挂到mainthread后所以rootgc链表被mainthread分为两部分后边是userdata前边是其他对象。 userdata没有灰色mark时直接标为黑色。 atomic中遍历mainthread之后的userdata链表luaC_separateudata()空闲且有gc方法的从rootgc移到g-tmudata中。 finalize阶段专门用来处理tmudata链表对每个元素标记为白色返还给rootgc然后调用它的gc方法。 没有gc方法的空闲数据就在sweep阶段被清理掉有gc方法的第一轮gc时先调用gc方法第二轮gc时在sweep阶段清理掉userdata本身通过finalized标志来识别userdata的状态。
string和userdata不引用其他对象都是叶子节点。
upval
mark的时候 如果是opend的其指向栈上变量将其指向的变量变灰 如果是closed其已是叶子节点直接变黑。
以下引用自 Lua GC 的源码剖析 (4) 为何 open 状态的 TUPVAL 需要留为灰色待处理呢这是因为 open TUPVAL 是易变的。GC 分步执行我们无法预料在 mark 流程走完前堆栈上被引用的数据会不会发生变化。事实上在 mark 的最后一个步骤我们会看到所有的 open TUPVAL 被再次 mark 一次做这件事情的函数是 remarkupvals。 thread
mark的时候从gray移到grayagain且不变黑。 堆栈是随着运行过程不断变化的为了效率其上数据的修改是不经过barrier的所以把它推迟到atomic阶段重扫描。
table
traversetable()的时候弱表不会从灰变黑而是转移到weak链表上。 若弱表引用的元素被移除也需要将元素从弱表中移除atomic()中会调用cleartable()来做这件事。 移除table中hash部分value为nil的entry是通过removeentry()
static void removeentry (Node *n) {lua_assert(ttisnil(gval(n)));if (iscollectable(gkey(n)))ttype(gkey(n)) LUA_TDEADKEY; /* dead key; remove it */
}可以看到只是将key设为LUA_TDEADKEY类型并没有从表中真删掉那何时真正删除呢是rehash的时候。 所以 高性能 Lua 技巧译 中这样说“你不该期望通过从一个大表里删除一些数据来回收内存更好的做法是删除这个表本身。”。
参考
讲解 Lua 内部实现的 gc 机制 Lua GC 的工作原理 Lua GC 的源码剖析
