云风的 BLOG

前几天, 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. "

Posted by 云风 at 04:59 PM | Permalink | Comments (8)

数据结构中的树结构在抽象复杂事物时非常常见，在图形引擎中，多用于场景以及 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 语言要高效的多。

Posted by 云风 at 05:15 PM | Permalink | Comments (8)

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

这是一个简单的 Windows 程序，在注册给窗口的 WinProc 回调函数中处理了 WM_CREATE 和 WM_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 了一下，似乎没有人反应类似问题。

Posted by 云风 at 05:03 PM | Permalink | Comments (14)

汉字的显示，是基于 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 对象，交替使用，定期切换。

Posted by 云风 at 04:28 PM | Permalink | Comments (20)