« March 2013 | Main | May 2013 »

April 17, 2013

Lua 5.2.2 中的一处 Bug

前几天, Lua 5.2.2 发布了, 主要是修复了 4 个 Lua 5.2.1 中已知的 bug . 其中包括前段时间一个同学和我在 email 交流中讨论的一个问题.

我把 Lua 5.2.2 更新到公司项目的主干上,同时需要对我的那本 《Lua 源码欣赏》做一些更新,需要把这次的代码更改同步到书里去。这个工作很繁琐,但有它的价值。比如我发现了 Lua 5.2.2 比 5.2.1 的更改远不只官方宣布了 4 处 bugfix ,还有一些小调整,让 Lua 的源码更规整一些。

阿楠同学因为这段时间一直在维护 UniLua 这个 C# 版的 Lua 项目,我就随便和他通告了一下这次的一些代码变更,方便他同步到 UniLua 项目中去。

讨论之中,他提到 luaD_precall 函数的实现有些诡异之处,没有看明白。我顺着他指出的位置又仔细阅读了一下,果然发现这里存在一个隐藏很深的 Bug 。

准确说,这不是 Lua 5.2 引入的新 Bug , 至少在 Lua 5.1 年代就存在了。只不过很难触碰到触发条件。

理解了代码后,我构造了一小段 Lua 代码,可以让 Bug 暴露出来。

function f(p1,p2,p3,p4,p5,p6,p7,p8,p9,...)
  local a1,a2,a3,a4,a5,a6,a7
  local a8,a9,a10,a11,a12,a13,a14
end

f()

运行这段 Lua 代码会让 Lua 虚拟机崩溃。我的修复 patch 如下:

diff --git a/src/ldo.c b/src/ldo.c
index aafa3dc..a901e6c 100644
--- a/src/ldo.c
+++ b/src/ldo.c
@@ -324,7 +324,7 @@ int luaD_precall (lua_State *L, StkId func, int nresults) {
     case LUA_TLCL: {  /* Lua function: prepare its call */
       StkId base;
       Proto *p = clLvalue(func)->p;
-      luaD_checkstack(L, p->maxstacksize);
+      luaD_checkstack(L, p->maxstacksize + p->numparams);
       func = restorestack(L, funcr);
       n = cast_int(L->top - func) - 1;  /* number of real arguments */
       for (; n < p->numparams; n++)

已经提交到 lua mailling list 里去了。Bug 的成因是:在 Lua 函数执行时,先按编译时统计出来的需要的寄存器个数扩展了堆栈。但是,如果函数有不定个数的参数,且调用者没有给完固定参数个数,会触发一个边界条件复制传入参数,结果是让预留的栈空间有可能不够。


4 月 18 日补充:

由于这是因为内存写越界造成的 bug , 所以是否会立即导致程序崩溃和编译环境有关.

我使用的是 mingw32 ,且打开了 -g 选项。

如果想确保看到问题,可以在 luaconf.h 里加上

#include "assert.h"
#define lua_assert assert

这样就会触发定义好的 assert 条件。


4 月 19 日:

这个 bug 终于在 lua mailling list 上被 Roberto 确认了. 英文不好是个问题, 前后写了好几篇才说清楚.

不过这个修复方案还需要斟酌. 因为可以有更好的方法去掉那次加法带来的额外开销.

"we can avoid this little overhead in the common case (non-vararg functions). We can either add p->numparams in the parser (so that the final maxstacksize of vararg functions already reflect this extra need) or check for numparams inside adjust_varargs, only for vararg functions. "

April 16, 2013

树结构的一点想法

数据结构中的树结构在抽象复杂事物时非常常见,在图形引擎中,多用于场景以及 sprite 的层级管理。在 GUI 相关的模块中也是必备的结构。其它领域,比如对程序源码本身的解释翻译,以及对数据文件的组织管理,都离不开树结构。

我觉得,这是因为一个对象,除了它自身的属性(例如大小、形状、颜色等)之外,还需要一些外部属性(例如位置、层次、方向等)需要逐级继承。每个对象都可以分解成更细的对象组合而构成、这些对象在组成新的对象后,它们的聚合体又体现出和个体的相似性(至少具有类似的外部属性)。这使得采用树状数据结构最容易描述它们。

我最近的一些工作代码做了很多这方面的工作,回想这些年里,我不只一次的思考类似的问题(参看 2009 年的一篇 blog),而每次最后解决问题的代码的都有些不同,编程风格也有一些变化。总结一下这段时间的思考,今天再写这么一篇 blog 。

树结构的基本操作无非是遍历整棵树、遍历一层分支、添加节点、移动节点、删除节点这些。但在大部分应用环境下,我们最多用到的只是遍历,而非控制树的结构本身。

所以我认为,遍历应该是对外的 API 、而结构控制则应该是内部的 API 。也就是说,作为一个模块,对外不用显露其实现用到的数据结构,而只关心怎样取得模块内部的状态。这时,合适的遍历接口足以。典型的文件系统的接口就是这样做的:我们可以用 / 连接目录和文件名变成一个完整的路径名,用它打开一个文件;而不必一级级取得目录对象,再从中获得文件对象。

相较于结构控制的 API (增加、删除、移动节点这些),更重要的是树的持久化。因为最终用户关心的是最终的数据,以及怎样使用这些数据,而不大关心数据的构建过程。常见的做法是把树状结构的数据呈现为一个 XML 文件,或是生成一张 Lua 表,然后一次加载它,得以在内存中重建树结构。持久化数据的格式不重要,你可以根据性能需要优化它,也可以因为健壮性而采用易读的文本。在大多数应用需求里,一旦树被重建为编辑产生它时构建的样子,就不会再修改它了。无论多简单的结构,把构建过程直接用代码的形式写在源文件中,是最不值得做的事情。早期的 GUI 程序或许还会一行行调用 API 把窗口以及布局搭建起来,而现代 GUI 框架几乎都为界面布局定义一套 DSL ,鼓励设计人员独立描述它们了。

我认为,即使是动态性要求很高的场合,最好也定义出数据格式,便于和使用了树结构的模块交互。比如在 GUI 程序中,我们不建议把一个按钮被按下的行为注入到那个按钮对象中,而是从外部捕获按钮被按下的消息,忽视掉界面的层次结构而直接处理这些消息。为了做到这一点,我们可以定义出类似 HTML 的语言来定位界面上的按钮。

少量修改已经事先创建好的对象的需求也是普遍存在的。往往对象的结构很复杂,但可以调整的部分却很少。有一些支持对象的语言中,直接提供了蓝图对象的概念。比如早期网络游戏常用的 LPC ,让程序员实现一个对象,再给出方法复制它。

我最近读到 狂刃 的图形引擎也用了类似的方法。它在编辑器中编辑出需要的怪物/粒子等对象,然后持久化到文件中。运行时,加载这些数据构造出编辑得到的对象,再根据需要的数量 clone 它们。

对于那些需要对象中需要少量修改的部分,按蓝图复制出一个复制体,再根据需要修改即可。这是图形引擎常见的需求,比如动画节点当前播放的帧号就是一个随时间变化的节点属性,需要在运行期修改的。


我想再谈一点实现上的细节以及优化。

采用了树结构组织起来的数据体,往往就意味着复杂且零碎的数据片段。因为每个结点下都可能有很多子节点,而子节点上保存的对象类型也可能不同,最终是大量不同尺寸内存片的组合体。但实际上,整棵树的绝大部分是不变的。

如果我们在编辑器里编辑出一个复杂的怪物,以它为蓝图在运行期 clone 出多份的话,会发现,这些克隆体之间的共有数据远多过易变量。所以我觉得,把这些易变量和不变量分开储存可能是个更好的方案。易变量(比如每个节点的当前空间状态等)可以平坦化储存,不变量虽然在逻辑层次上是一棵树,但在编辑完成时就决定了它是怎样的,完全可以持久化为连续的数据,并还原到连续内存中,且作为一个对象来管理。作为公有的蓝图,也不必真的复制为多个克隆体,而只需要指针引用即可。

在我最近的另一个项目中,我用 C + Lua 实现了类似的结构,发现代码没有我一开始想的那么复杂。Lua 和 C 的层次还是能分的很清楚。一些需要靠字符串索引储存的数据,我放到 Lua 表中,而 C 中的数据结构则专注于树结构的表述。这样不会在 Lua 中保存太多零碎的 table ,在 C 结构中保有高效的树结构索引能力,又可以把比较麻烦的字符串管理扔给 Lua GC 。而且在很多情况下,对于字符串常量,Lua 语言比 C 语言要高效的多。

April 15, 2013

WM_CREATE 引起的 bug 一则

今天在维护一个 Windows 程序时,发现一个 bug ,记录一下。

这是一个简单的 Windows 程序,在注册给窗口的 WinProc 回调函数中处理了 WM_CREATEWM_PAINT WM_TIMER 等消息。

bug 的现象是,WM_CREATE 的流程没有走完就开始处理 WM_TIMER 等消息了。表现起来仿佛 WinProc 被重入了。

仔细排查后发现,不知道什么奇怪的原因,我的 Win7 系统在处理 WM_CREATE 消息时,默认捕获了异常。导致消息处理的流程没有走完,但进程却没有崩溃,窗口也被正确创建出来了。然后这个窗口可以继续接收 WM_TIMER 等消息。

我在不同的机器上测试了一下,确认是 Windows 的问题。貌似过去没有碰到过。目前我用的是 Windows 7 的 64 位版本,使用 mingw32 生成的 32bit 程序。

有兴趣的同学可以一试,在

WinProc 里加几行:

case  WM_CREATE: {
    int *p = NULL;
    *p = 0;
    break;
}

这个非法地址写指令不会让进程崩溃。

google 了一下,似乎没有人反应类似问题。

April 02, 2013

动态字体的贴图管理

汉字的显示,是基于 3d api 的图形引擎必须处理的问题。和西方文字不同,汉字的字形很难全部放在一张贴图上,尤其是游戏中有大小不同的字体的需求更是如此。即使放下,也很浪费内存或显存。如果不想申请很大的贴图来存放汉字字形,图形引擎往往需要做动态字形贴图的处理。

即,动态生成一张贴图,把最近常用的汉字画在上面。几乎所有成熟的基于 3d api 的图形引擎都需要有相关的模块才可以对汉字更好的支持。但我到目前为止,还没有看到有把这个模块独立出来的。大多数开源引擎都是在自己的框架内来实现差不多的功能。我觉得,这部分管理功能和如何管理贴图其实没有关系、和取得字形的方法也没有关系、不必和 3d api 打交道,也不用涉及到底用 freetype 还是 os 自带的 api 取得汉字字形,所以值得独立实现。

我们的需求本质上是对一张贴图的区块进行管理。每个汉字都占据其中的一小块。当贴图填满时,最久没有用过的汉字块可以被淘汰掉,让新的汉字覆盖上去。同样的字体的最大高度是相同的,可以排列在一行,但宽度可以不同。横向排列时,少许的空洞的允许的。

我设计了如下接口:

struct dfont_rect {
    int x;
    int y;
    int w;
    int h;
};

struct dfont * dfont_create(int width, int height);
void dfont_release(struct dfont *);
const struct dfont_rect * dfont_lookup(struct dfont *, int c, int height);
const struct dfont_rect * dfont_insert(struct dfont *, int c, int width, int height);
void dfont_flush(struct dfont *);

用 create/release 创建/删除一个管理对象,管理一张指定大小的贴图。贴图本身并不在这个管理对象内,它只负责管理贴图的空间划分。

可以用 insert 来创建一个指定宽高的矩形空间,并为这个空间指定一个 id 。这个 id 一般用汉字的 unicode 即可。insert 会返回一个矩形区域,如果贴图满了,且无法腾出空间,则返回空。禁止创建高度相同的相同 id 。

lookup 可以用于查询一个指定高度的 id ,如果贴图上不存在,则返回空。lookup 会记录这个字最近被使用过,不会被立刻淘汰。

贴图上创建的字型块,在调用 dfont_flush 之前都一定保留。调用 dfont_flush 后,如果贴图满,会淘汰最久没有使用的等高的字形空间。


我把一个开源实现放在 github 上了。不过暂时还没有放在任何项目中用,程序结构略微复杂,所以很可能有 bug 。

具体使用时,每次渲染一个汉字,可以先 lookup 查询过去是否创建过,如果没有,则算出这个字的尺寸,调用 insert 得到一个新的矩形空间,然后取得汉字的位图,上传到贴图的指定区域。每帧渲染完毕,调用一次 dfont_flush 即可。

一般情况下,创建一张 2048 宽的 dfont 对象大约就够用了。但是在字形的淘汰过程中,可能会导致贴图内有空洞(如果能保证尺寸相同,则不会产生这个结果),所以可能会比预想的少排一些字在贴图上。所以实际用的时候,可以考虑创建多创建一个 dfont 对象,交替使用,定期切换。