« March 2011 | Main | May 2011 »

April 12, 2011

再谈 C 语言的模块化设计

去年谈过 C 语言对模块化支持的欠缺。我引入了一个 USING 方法来表达一个 C 语言编写的模块对其它模块的依赖关系。用它来正确的处理模块初始化。

现代语言为了可以接近玩乐高积木的那样直接组合现有的模块,都对模块化做了语言级别上的支持。我想这一点在软件工程界也是逐步认识到的。C 语言实在是太老了。而它的晚辈 Go 就提供了 import 和 package 两个新的关键字。这也是我最为认可的方式。之前提到的方案只能说是对其拙劣的模拟。确认语言级的支持,恐怕也只能做到这一步了。

在项目实践中,那个 USING 的方案我用了许多年,还算满意。之前有过更为复杂“精巧”的方法,都被淘汰掉了。为什么?因为每每引入新的概念,都增加了新成员的学习成本。因为几乎每个人都有 C 语言经验,但每个人的项目背景却不同。接受新东西是有成本的。任何不是语言层面上的“必须”,都有值得商榷的地方。总有细节遭到质疑。为什么不这样,或许会更好?这是每个程序员说出或埋在心里的问题。

那个 USING 的方案远不完美,它只是足够简洁,可以让程序员勉强接受而已。但其实还不够简洁。因为从逻辑表达上来说,它是多余的。一个模块使用了另一个模块,代码上已经是自明的。从 C 语言的惯例上来说,只要 #include 了一个相关的 .h 文件,就证明它需要使用关联的模块。光用宏的技巧很难只依靠一次 #include 就搞定正确的模块初始化次序。因为 C 语言并没有明显的模块概念。如果将每个子模块都编译为动态库可能能一定的解决问题(我曾经试过这种方案),但却会引出别的问题。细粒度的动态库局限性太大。

这两天我结合这半年学习 Go 语言的体验,又仔细考虑了一下这个问题。想到另一个解决方案。

如果我们能规范系统中子模块 API 的命名规范,或许可以借助编译器和相关工具来做一些 meta programming 的工作。

我们可以使用 objdump 来分析编译好的 .o 文件。比如有一个模块 foo ,实现在 foo.c 中。objdump -t 可以得到 .o 中引用以及导出的符号。

我们要求所有子模块中的 C API 都遵守一致的命名规范,假设用驮峰命名的话,foo 模块中的 Api 就看起来像这样 fooApi 。objdump 的结果可以轻易的识别出规范内的引用的其它子模块有哪些。然后生成一个类似之前提到的 USING 方法可以调用的初始化函数。自定义的模块初始化函数可以统一命名为 fooInit 的形式,当这个初始化函数存在,则由自动生成的代码调用一下即可。

整个过程可能比较繁杂,但很容易用 make 这样的构建工具自动化进行。具体实现我就不列出了。或许不久会新开开源项目实践一下。

April 11, 2011

如果从头开发新的 3d engine

最近闲了下来。断断续续的再想,如果业余时间弄一个开源项目玩儿,什么是比较好的题材,适合自己来做。想来想去,3d engine 是一个比较好的选择。以我来看,对外开源如果要吸引到足够的有经验的同学参加,必须项目有一定价值。要可以迅速的搭建工作环境并直接看到结果,这样才能有兴趣迭代做下去。起步必须自己一个人来做,东西得有个雏形。所以必须是自己比较熟悉的领域。

若论熟悉,其实游戏服务器的架构和实现,我这些年考虑的更多,也做的更多。但这个东西不适合做成开源项目。因为受众太小(不是每个人都有机会和意愿去架设网络游戏服务器的),而且它不能单独运行看到结果。没有玩家的游戏服务器是没有意义的。

3d engine 这些年也有在开发。但是公司不可能允许开源已有项目。如果想玩儿,从头做是唯一选择。而且重新开始有更多的乐趣,再造轮子原本就是程序员们的欢乐源泉之一。如果自娱是唯一目的的话,就不必过多考虑商业引擎必须考虑的问题。比如兼容更多的底层 3D API ,做全平台兼容,支持低端硬件等等。甚至于还要去考虑日后防外挂等无聊的问题。

昨天在 buzz 上提起 game engine 开发的话题,miloyip 同学立刻发了份他的一些想法。有很多的记录,想来也是思考多日。对于 engine 特性方面列的很全了。不过我的出发点不太一样。我更多的考虑的是,如果是做为一个开源项目,怎样可以以最小代价启动起来,让项目自然成长。也就是说,可以在质量和特性上有个高起点,但从一个很小的功能集合开始。而且,如果做这个,没有商业上的目的。所以,不必屈就于进度压力。不必为特别的需求必须去加上什么功能。一切以好玩为目的。只要写代码开心即可。

考虑了一晚上,我觉得如果动手做的话,大概是这样的。

Git 是最近我比较中意的 VCS 工具,如果比较 google code 和 github 的,我比较倾向后者。

开发语言,我希望是 C + Lua 的组合。因为这两个都是我最为熟悉的语言,使用起来最为得心应手。C++ 也很熟悉,某些方面 C++ 写起来要比 C 更方便。尤其是采用 D3D 的底层 API 的话,C 要麻烦的多。而且还有许多第三方组件也是 C++ 接口的。不过我用 C 搭建大的系统已经有多年的经验了,我相信我的经验可以弥补 C 语言的诸多不足。而 Lua 会是对 C 语言很好的一个补充。

Engine 的核心部分,可以以 C 语言写成的库提供,再由独立的 lua 封装层包装起来,二次开发在 Lua 中进行。如果需要在外层使用非 Lua 的接口,比如用 QT/C++ 开发工具,则可以在 Lua 层绕一下,或是再单独开发一个薄的 C++ 的粘合层。

不用太在意粘合层的性能,但需要把粘合层和核心库设计上隔离开。

3d api 可以暂时只支持 DX11 ,openGL 的支持待考虑。不过最好能留下余地。在代码编写上,初期的代码量不宜过大,做好至少一次重构的准备。所以第一期代码不需要面面俱到。这主要是因为我在 3d 领域方面经验不足。

构建工具采用 GNU Make ,这个工具我有比较多的使用经验,也更大众。不必要求所有开发人员都精通 GNU Make 的使用,整体的框架可以一个人先做好即可。

编译工具使用 gcc 。可以考虑兼容 VC 编译。

功能上,Audio/GUI/Input/Network 等都不是先期必要模块,一开始都不必设计和实现的。也不必去抽象窗口管理的部分。但需要搭建一个运行环境,有基本的窗口启动,简单的 GUI (不可定制),方便的 Log 输出。

工具是应该第二步考虑的事情。

至于 3d engine 将支持的特性,那个应该是逐步添加的事情。虽然说,新特性的添加方便于否和 engine 的基础设施的可扩展性很有关系。但,从一个小规模的项目开始,逐步重写和完善,我觉得是更实际的方式。


现在缺少的东西主要有这些:

不知道项目该用什么名字以及项目代号是什么。

对近年的 3d 技术发展没有细致了解,领域知识的缺乏导致很难很好的做基础设计。

还没有下决心开启项目。

April 08, 2011

我在网易的十年

10 年前的今天,我在广州 36 楼办理了入职网易的手续。

这些年陆陆续续写了很多,原本计划在今天总结一下,突然又没有什么感觉了。入职第一天,肖海彤是我的引路人。他私下跟我说,我们没有那种灌输式的入职培训,我知道你也不喜欢那样。很多企业都喜欢那种洗脑式的培训,网易还没有。不过员工手册可以拿去读一下。

多年之后,我在杭州。阿里巴巴是我们的邻居。屡屡听到有入职阿里系的同学说起他们冗长的入职培训,我脑子里总会闪现出“洗脑”的字样。但是念头挥之而去,我知道这是个可笑的想法。如今,我们的新人培训也有至少两天的课程了。如果是毕业生,还会安排拓展。我在广州也做过拓展的领队,那次基本上大家觉得辛苦的运动都会推我上去。当领导的话,必须身先士卒。如果你不愿意做的事情,怎能要求别人去做。写到这里,我想起了莱因哈特。

无论做何项目,我都不希望那个主持大局的人只是指手画脚。如果是程序员,那么就应该保持贡献代码,而且是超出整体质量的代码。这么要求,或许有些固执。但我偏执于坚持对那些付出努力坚辛只为了有朝一日摆脱当下状态的人保留一丝轻蔑的态度。所以,当有不熟悉的同学问起,“你现在还写代码啊?”,我只是一笑,“当然写,三天不写就手痒了”。如果有更多任务要完成,我会分出工作以外的时间去做。而不压减编码第一线的时间。

但我做不了莱因哈特,相比较而言,我更欣赏杨威利。有和他一样的理想,相同的懒散。以及,没有领导者的气质。

wding 有领袖的气质。这足以掩盖他诸多的缺点而坐在 CEO 的办公室。鉴于我还在领他的薪水,不好写太多他负面的东西。但实质上,我这人本也不喜欢捉着人的短处去看。我相信世上的一切皆有其因。可以理解的人和事就是让人放心的。这样,wding 拍桌子想发火时,也从来没针对过我。他老是强调员工的人品,我知道跟某些同学的离开有关。或许他把我划到人品好的一堆人之中吧。也或者对于我这样无欲无求,总能心平气和的和他直说那些他不太愿意听的话的人,他没有太好的办法。当然,我想我说话还是有分寸的。

有时,我对公司挺失望的。在我看来,它封闭,缺乏远见,太着意于眼前的利益。人事关系也不如小规模时简单。懒散的人越来越多,开发效率低下,技术保守。

好吧,一次说了那么多贬义词,却千万别理解为是一种抱怨。那只是我的客观评价而已。如果真是抱怨,我现在就该是肆无忌惮的再写上一个长篇,且是以网易前员工的身份了。以上的一切,都是和心目中的理想状态相比较而得出的结论。但我们知道,理想归理想,和实际是很遥远的。何况我也是能推动其改进的一分子,但是我改变不了,而空想则是不实际的。

从网易离开的人不少。嫉恨的人不能说没有,但也不算太多。反而我不只从一个人那听到,网易还是一个值得怀念的地方。有技术交流,可以研究些好玩的东西,写点没有边际的程序。人和人之间比较简单。做项目虽然有时候有点累,但很有趣。能够在代码仓库里找到一些清爽的代码,技术人员有技术上的追求,等等等等。

MT 是公司前 COO ,现在仍在公司服务。我和他熟悉是在 2004 年去美国参加 GDC ,一行两人。他兴致勃勃的在酒店前停车露一手车技,说教我开车。他带我在美国认识了不少朋友。私下里有人问他,MT 你姓董呢,又是香港人,该不会和那个家族有啥关系吧。他总是笑而不语。

去年,MT 来杭州出差,我拉他到西湖边的小酒吧喝酒。MT 笑谈,wding 绝对想不到我们俩会在杭州喝酒的。从 COO 的位置下来,他空闲了大半年什么都没干,却也没有去做其他的事业。最终,他又留在了网易。MT 说,见过太多当老板的。还是觉得 wding 还算比较靠谱的人了。我们碰杯。其实呢,工作中争执不少,各有其责,追求也不一样。但求求同存异。我们聚在一个大屋檐下,却没有被灌输成有统一的观点,没有被虚妄的所谓公司文化同质化,对于个人,又何尝不是件幸事。合则聚、不合则散。这些自由的人自觉的聚在一起,自然还算是合的来的。

我记得那年和 dingdang 两人骑车从广州到珠海,再从珠海到深圳,最后从深圳回到广州。他那时和我现在同龄。从那时开始,我从来没想过 Dingdang 会离开网易。但当他跟我谈起他辞职的念头时,我脑子猛的转了一下,接着思维就转过来了。但最终他毕竟没有离开。

Dingdang 是正宗的程序员出身,也坦承如今不再是个程序员。我想他也很难再操旧业,以我自身的体验,三个月不写代码,就会手生,慢慢落后于时代了。编程这件事,不进则退,总觉得自己底子好,能保持住状态,只是妄想而已。不过 dingdang 也的确不再需要写程序,他的程序员背景最大的作用是,可以听我们这些程序员反复絮叨着技术上的东西,而真的能够理解。网易若说真有什么文化的话,程序员文化就是其中之一。这是很难刻意营造的,它自然而生。我有时想,我们不应该把之称为好,也绝不是坏。它只是客观存在而已。就像一个人的特质一样,如果你喜欢那就喜欢了,如果你不喜欢,也很难按你的想法改变。网易不再全是一帮工程师加 Geek ,新来的人的加入也在冲淡这些。Dingdang 想过在制度上改造公司,各个流程、职能更为专业化(姑且我这么理解)。wding 也想。我没能也没想深入去了解他们思路上的冲突,姑且理解为,不可能有两个人想法一致吧。管理数千员工是件很复杂的工程。

Dingdang 曾是个事必躬亲的人。这使他在一两年之中,迅速成为网易游戏的不可缺少的灵魂人物。我从未想过在这样一个位置,应该做何考虑。他很辛苦,所以也想摆脱这种辛苦。从我的理解,这倒不是怕累,而是从程序员的直觉上就能感知这是个不正常的状态。我们所有有负责管理工作的人员都在 06 年聚在番禺的小别墅里开会。之前,一切事情都要很自然的问他,这个你来做决定。调动部门间的资源,最简洁的途径便是和他打个招呼。会上,我发明了一种用扑克牌为道具的,不记名投票的方法。大家至少明白了一件事情,其实表面上统一的想法,实质上是有分歧的。之后,事情慢慢就在人为的刻意下有所改变。

我想那段时间是公司的阵痛期。公司里的故交好友和我来谈心的不少。我目睹了不少同学离开。因为听来的各种声音很多,我越发理解了让那么多人一起工作之难。我坚决的反对向一个群体灌输观念,我将其视为对个人自由意志的磨灭。而差异的理念,哪怕只是一点点,人多了,时间久了,都会衍变成大的矛盾。即使你想强调对事不对人,但往往对事上的分歧更为不可调和。想不因此对人产生偏见怕是很难。

我想 dingdang 是个比我更甚的理想主义者。我看到了总总,想不通可以如何改变,就不去想了。于我来说,理解就足够了。他是个坚持想把想法执行下去的人,甚至宁愿去忽略些问题。


前年我谈过在网易的“平等”,甚至觉得被人误解又追加了一篇。我希望这也是网易的特质。在这一点上,有些人认可,有些人不认可。恰巧前两天我看到这么一篇 blog : 无条件自我臭屁 。我想谈谈公司内,或是小到项目内的民主。在生存悠关的时候,我想,一个团队是难以谈的上民主的。这个时候,需要的是领袖的执行力。要么做成,要么失败了大家散伙。如果追求的是成功,尽可以再来。而在事情做成了之后,团队扩大建设时,又应该避免一个人的独断。民主的制度不算很好,但也不至于太差。它可以保护少数人的声音不至于泯灭,可以让大家学会容忍不同的意见,学会妥协。不至于让人过于偏激。我比较赞同把公司看作是一种契约:即人们把自己的财产或是自己提供的劳务交付给一共同的企业,以分享这些的一切带来的利益。即使是网易这样的私有企业。公司也并非仅看作股东们的私有财产。这也是我谈及平等的基础。

从打工者个人的角度来看,我更希望网易提供的是一个让人实现自己梦想的环境。而梦想可有不同,哪怕仅仅是让自己买的起城市里的小套房子也好。而不必苛求他们志向更为远大。对于有不同于物质追求的人来说,公司也能给予包容。大门敞开。我相信物以类聚,人以群分。只要网易保持着它的特质,就会有符合它的人聚在一起。


前言不搭后语的写了这么多。都是些零碎的思绪。原计划是写些来来去去的好些人的,写下我对他们的赞美和偏见。每每提笔又退缩了。毕竟你想是一回事,写出来就是另一回事了。还在这间办公室坐着,未能免俗,还是不议论的好了。再有,见到的一幕幕,难免做狭隘的判断;听来的故事也未必能当真;有幸蒙诸多同学厚爱,能想起与我分享自己的故事,或是让我给出自己的意见,我想也跟我是个合格的听众有关吧。那我觉得,做个聆听者,比做个讲述者更让人放心。

April 02, 2011

把 lua 的 gc 移到独立线程

前几天分析了 lua gc 的实现细节。这里先汇总一下:

btw, 阅读 lua 的代码是段很有趣的经历。但如果是重头读 lua 的源码,建议从简单的部分读起。gc 恰巧是最难的一段。LuaJIT 的作者 Mike 在这方面很有发言权,他在回答 Which OSS codebases out there are so well designed that you would consider them 'must reads'? 这个问题时,列过一张推荐阅读次序表。我的观点一致,Lua 是少有的设计优秀,C 程序员必读的代码。

从小处说,如果想进一步改进,那是必须仔细研读的(但这绝对不是主要原因)。Lua 的 GC 实现的已经相当不错了,想找出实现中的问题,改进算法,可能很难。如果有多核处理器,那么把 GC 放到一个独立线程里去做倒是可以考虑的。

如果没有前面的研读,恐怕只能用一把大锁来安全处理多线程的 GC 了。lua 的代码为多线程安全预留了 lua_locklua_unlock 两个 api 。默认是用宏定义出来关闭的,必要的时候可以改写它们。所有的对外 api 都加入了 lock 的调用。

但是,用它来实现多线程的 gc 是完全没有意义的。GC 部分永远不能并行处理。这个东西只是为了多线程访问同一个 lua state 提供了安全保障而已。

下面我们看看能做点什么。


lua 可以自定义内存管理器。只是一个 lua_Alloc 函数而已。一般,我们会使用标准的 malloc/free/realloc 来模拟。有时,我们信不过 libc/msvcrt 的管理器,会选择一个看起来更好的。

但是,lua_Alloc 的行为和 realloc 等还不完全一样。它提供更多信息。比如它可以准确的指出每个内存块的大小。而标准 api 则做不到这点。通用内存管理器需要使用一个 cookie 来记录数据块的长度,如果你自己实现内存管理器的话,则可以省掉这个 cookie 。

如果你前面有读完 GC 的代码,你会发现,其实 Lua 使用内存是很有规律的。它会在 GC 的 sweep 之前只增不减。然后大批量的释放内存。如果我们想把 GC 放在独立线程中,表面上看需要保证内存管理器的线程安全。但实际上不必要做的那么严格。

释放内存一定只存在 sweep 流程中(除非用户主动调用了 lua_Alloc ,这就意味着,我们可以做一些优化。并不一定要保证严格的线程安全。

内存申请可以是在一整块内存上简单的循序切分,即,每要一块内存,就简单的从整块中切下来(只是调整一下指针),当 sweep 发生时,把备用内存块切换到新的整块上去,让 sweep 流程可以安全在老的内存上工作。因为没有 cookie ,不用链表,sweep 对内存管理器的操作和逻辑主线程是完全独立的,不需要任何锁。

sweep 过程可以是缓慢的(因为已经独立开去),它可以先将所有释放的内存用链表串起来,然后用一个简单的链表冒泡排序,之后就可以把释放的内存块做合并了。少量的用户主动调用的内存释放(一般也是在 userdata 的 gc 元方法里),可以放到请求一个队列中,留到 GC 线程统一处理。除了用户主动调用的内存释放操作,还有一个 realloc 请求,需要释放旧有的空间,申请新的空间。这些更常见,也需要记录。

sweep 完成后,通常可以回收到整块的连续内存,就可以把最大的一块拿来下次使用了。

内存管理器的优化倒不一定必须在独立线程 GC 中用。完全可以单独写一个提供给现在不加修改的 lua 。如果想优化上面的算法,那步对 freelist 的冒泡排序以及整理,倒是可以私下开一个线程。


我们不必把整个 GC 模块都搬到独立线程中去,只考虑那些耗时的工作即可。这样可以最大限量的避免修改 lua 已有的代码。比如只需要考虑 singlestep 里的大运算量部分。

先看 sweep 流程的并行化。关键在于 GCSpropagate 流程中的 propagatemark 函数。atomic 函数完全可以放在主逻辑线程中运行。

propagatemark 的原则是一次只处理一个 GCObject 对象。简单的修改方法是给正在处理的对象加锁。自然不需要为每个 GCObject 都加一个锁,那样太浪费内存。既然一次只有一个,那么在锁里记录正在处理的对象即可。对 TTABLE , TFUNCTION , TTHREAD , TPROTO 的修改都判定这个锁。主逻辑里,被锁 block 住的可能性是非常低的,那只在 GC 刚好运行到同一个对象时才会碰到。

但是对锁的判断可能依然是一个比较大的开销。我们可以先判定 GC 的状态是否处于 GCSpropagate ,这个判断是不需要锁的(因为 gc 的流程状态切换在主线程中)。只要在 GCSpropagate 流程才需要做锁的处理。

TTHREAD 也是一个开销比较大的地方,lua gc 的原始代码中,特地把 thread 放到了 gcagain 里,推迟到 atomic 阶段再扫描一次,而不是对 stack 的修改都做一个特别的 write barrier 也有这方面的顾虑。毕竟大多数的 lua 运算都是基于 local 的。这相当于所有的 local 变量访问都要做 barrier 。

我的解决方案是,当 GC 扫描到 TTHREAD 时,暂时 stop the world ,而不是做锁。这个 stop 当然要经过协调。原本调用 luaC_checkGC 的地方都是一个好的切入点。因为 luaC_checkGC 有可能调用 singlestep ,也就是说,lua 原本的设计就保证了在这些位置插入 GCSpropagate 是安全的。这样,我们的 GC 线程扫描到 TTHREAD 类型时,可以发出信号等待主线程暂停。然后就可以安心的做上一个步骤,再放行主线程继续。

另一个需要特别处理的 write barrier 。write barrier 会比以前稍昂贵,这里也需要仔细考量一下。

write barrier 做的工作其实是当 A 关联到 B 时,检查是否需要把 A mark 一下(当 B 不是 table),或把 B 放入 gray 链(当 B 是一个 table)。如果改成多线程版本的话,直接判断 marked 位状态变得不太合适。我建议这样实现:先判定 GC 是否处于 GCSpropagate 以决定是否需要 barrier 。如果需要,则把需要关联的 A 和 B 放进一个 FIFO 的管道。然后在 GC 线程中,每做一个 singlestep 就检查这个管道,逐个处理 barrier 。极端情况下,这个管道上的 barrier 请求速度快过处理速度(需要实测看是否真的可能发生),则采用上面 TTHREAD 的处理方式暂停主逻辑线程。

GCSsweepstring 流程,在 lstring.c 里加一把锁是很容易并行化的。这个锁只在创建新 string 时才会遇到,所以不会读主逻辑有太大的影响。

GCSsweep 流程几乎是可以直接并行处理的。因为 GCObject 是条单向链表(分为两段,userdata 是后半段),增加新节点都是在链表头加,而 sweep 则都是修改链表中间,相互不影响。需要特殊对待的是 open upvalue ,这个在之前分析代码时已经讨论过。匹配新的 upvalue 时应该加锁处理。这个过程实际运行时触发不会很频繁,写的时候需要小心而已。

GCSfinalize 不太推荐在独立线程处理,毕竟它会调用一段 lua 代码,同一个 lua state 中的代码是不合适并行化的。


以上即总体思路,期望可以顺利完成这项工作。

April 01, 2011

Lua GC 的源码剖析 (6) 完结

GC 中最繁杂的 mark 部分已经谈完了。剩下的东西很简单。今天一次可以写完。

sweep 分两个步骤,一个是清理字符串,另一个是清理其它对象。看代码,lgc.c 573 行:

    case GCSsweepstring: {
      lu_mem old = g->totalbytes;
      sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
      if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
        g->gcstate = GCSsweep;  /* end sweep-string phase */
      lua_assert(old >= g->totalbytes);
      g->estimate -= old - g->totalbytes;
      return GCSWEEPCOST;
    }
    case GCSsweep: {
      lu_mem old = g->totalbytes;
      g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
      if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
        checkSizes(L);
        g->gcstate = GCSfinalize;  /* end sweep phase */
      }
      lua_assert(old >= g->totalbytes);
      g->estimate -= old - g->totalbytes;
      return GCSWEEPMAX*GCSWEEPCOST;
    }

在 GCSsweepstring 中,每步调用 sweepwholelist 清理 strt 这个 hash 表中的一列。理想状态下,所有的 string 都被 hash 散列开没有冲突,这每一列上有一个 string 。我们可以读读 lstring.c 的 68 行:

  if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */

当 hash 表中的 string 数量(nuse) 大于 hash 表的列数(size) 时,lua 将 hash 表的列数扩大一倍。就是按一列一个元素来估计的。

值得一提的是,分布执行的 GC ,在这个阶段,string 对象是有可能清理不干净的。当 GCSsweepstring 步骤中,step 间若发生以上 string table 的 hash 表扩容事件,那么 string table 将被 rehash 。一些来不及清理的 string 很有可能被打乱放到已经通过 GCSsweepstring 的表列里。一旦发生这种情况,部分 string 对象则没有机会在当次 GC 流程中被重置为白色。在某些极端情况下,即使你调用 fullgc 一次也不能彻底的清除垃圾。

关于 string 对象,还有个小地方需要了解。lua 是复用相同值的 TString 的,且同值 string 绝对不能有两份。而 GC 的分步执行,可能会导致一些待清理的 TString 又复活。所以在它在创建新的 TString 对象时做了检查,见 lstring.c 86 行:

    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }

相同的问题也存在于 upvalue 。同样有类似检查。

此处 GCSWEEPCOST 应该是一个经验值。前面我们知道 singlestep 返回的这个步骤大致执行的时间。这样可以让 luaC_step 这个 api 每次执行的时间大致相同。mark 阶段是按扫描的字节数确定这个值的。而每次释放一个 string 的时间大致相等(和 string 的长度无关),GCSWEEPCOST 就是释放一个对象的开销了。

GCSsweep 清理的是整个 GCObject 链表。这个链表很长,所以也是分段完成的。记录遍历位置的指针是 sweepgc ,每次遍历 GCSWEEPMAX 个。无论遍历是否清理,开销都是差不太多的。因为对于存活的对象,需要把颜色位重置;需要清理的对象则需要释放内存。每趟 GCSsweep 的开销势必比 GCSsweepstring 大。大致估算时间为 GCSWEEPMAX*GCSWEEPCOST 。

真正的清理工作通过 lgc.c 408 行的 sweeplist 函数进行。

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  GCObject *curr;
  global_State *g = G(L);
  int deadmask = otherwhite(g);
  while ((curr = *p) != NULL && count-- > 0) {
    if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
      sweepwholelist(L, &gco2th(curr)->openupval);
    if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
      lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
      makewhite(g, curr);  /* make it white (for next cycle) */
      p = &curr->gch.next;
    }
    else {  /* must erase `curr' */
      lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
      *p = curr->gch.next;
      if (curr == g->rootgc)  /* is the first element of the list? */
        g->rootgc = curr->gch.next;  /* adjust first */
      freeobj(L, curr);
    }
  }
  return p;
}

后半段比较好理解,当对象存活的时候,调用 makewhite ;死掉则调用 freeobj 。sweeplist 的起点并不是从 rootgc 而是 sweepgc (它们的值可能相同),所以对于头节点,需要做一点调整。

前面的 sweep open upvalues of each thread 需要做一点解释。为什么 upvalues 需要单独清理?这要从 upvalue 的储存说起。

upvalues 并不是放在整个 GCObject 链表中的。而是存在于每个 thread 自己的 L 中(openupval 域)。为何要这样设计?因为和 string table 类似,upvalues 需要唯一性,即引用相同变量的对象只有一个。所以运行时需要对当前 thread 的已有 upvalues 进行遍历。Lua 为了节省内存,并没有为 upvalues 多申请一个指针放置额外的链表。就借用 GCObject 本身的单向链表。所以每个 thread 拥有的 upvalues 就自成一链了。相关代码可以参考 lfunc.c 53 行处的 luaF_findupval 函数。

但也不是所有 upvalues 都是这样存放的。closed upvalue 就不再需要存在于 thread 的链表中。在 luaF_close 函数中将把它移到其它 GCObject 链中。见 lfunc.c 106 行:

      unlinkupval(uv);
      setobj(L, &uv->u.value, uv->v);
      uv->v = &uv->u.value;  /* now current value lives here */
      luaC_linkupval(L, uv);  /* link upvalue into `gcroot' list */

另,某些 upvalue 天生就是 closed 的。它们可以直接通过 luaF_newupval 构造出来。

按道理来说,对 openvalues 的清理会增加单次 **sweeplist 的负荷,当记入 singlestep 的返回值。但这样会导致 sweeplist 接口变复杂,实现的代价也会增加。鉴于 thread 通常不多,GC 开销也只是一个估算值,也就没有特殊处理了。


GC 的最后一个流程为 GCSfinalize 。

它通过 GCTM 函数,每次调用一个需要回收的 userdata 的 gc 元方法。见 lgc.c 的 446 行:

static void GCTM (lua_State *L) {
  global_State *g = G(L);
  GCObject *o = g->tmudata->gch.next;  /* get first element */
  Udata *udata = rawgco2u(o);
  const TValue *tm;
  /* remove udata from `tmudata' */
  if (o == g->tmudata)  /* last element? */
    g->tmudata = NULL;
  else
    g->tmudata->gch.next = udata->uv.next;
  udata->uv.next = g->mainthread->next;  /* return it to `root' list */
  g->mainthread->next = o;
  makewhite(g, o);
  tm = fasttm(L, udata->uv.metatable, TM_GC);
  if (tm != NULL) {
    lu_byte oldah = L->allowhook;
    lu_mem oldt = g->GCthreshold;
    L->allowhook = 0;  /* stop debug hooks during GC tag method */
    g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
    setobj2s(L, L->top, tm);
    setuvalue(L, L->top+1, udata);
    L->top += 2;
    luaD_call(L, L->top - 2, 0);
    L->allowhook = oldah;  /* restore hooks */
    g->GCthreshold = oldt;  /* restore threshold */
  }
}

代码逻辑很清晰。需要留意的是,gc 元方法里应避免再触发 GC 。所以这里采用修改 GCthreshold 为比较较大值来回避。这其实不能完全避免 GC 的重入。甚至用户错误的编写代码也可能主动触发,但通常问题不大。因为最坏情况也只是把 GCthreshold 设置为一个不太正确的值,并不会引起逻辑上的错误。


后记:

终于把这个系列写完了。接下来的工作,我想做一些分析,看能否以最小代价(尽量少用锁)改造出一个多线程版本的 GC 。