« July 2017 | Main

August 16, 2017

Lua 5.3.4 的一个 bug

昨天我们一个项目发现了一处死循环的 bug ,经过一整晚的排查,终于确认是 lua 5.3.4 的问题。

起因是最近项目中接入了我前段时间写的一个库,用来给客户端加载大量配置表格数据 。它的原理是将数据表先转换为 C 结构,放在一块连续内存里。在运行时,可以根据需要提取出其中用到的部分加载都虚拟机中。这样做可以极大的提高加载速度。项目在用的时候还做了一点点小修改,把数据表都设置成 weaktable ,可以让暂时不用的数据项可以回收掉。

正式后面这个小修改触发了 bug 。

排除掉是我这个库引起的 bug 后,我们把注意力集中在 lua 的实现上。

bug 的现象是:运行一段时间后,某次 table copy 的过程中,对一个 table 的 set 操作陷入了死循环。我们知道 lua 的 table 中有一个闭散列 hash 表,如果在插入新项目时,发现 hash 冲突,则需要重新找到一个空的 slot 并将其串在 hash 查询时所在的 slot 上的链表中。

而 bug 发生时,这个链表损坏了,指向了一个空 slot ,空 slot 的 next 指针指向自己,导致死循环遍历。

从 coredump 上分析,我认为是 hash 查询出来的冲突对象(一个 long string )的数据结构受损。原本在 long string 结构中有一个 extra 变量指示这个对象是否有计算过 hash ,它的值只能是 0 或 1 ,但这里却是 67 。而 hash 值则为 0 (通常 hash 值是 0 的概率非常小),导致重新索引 hash slot 时指向了 slot 0 ,那里是空的。

我们自定义了 lua 的分配器,在分配器中输出 log 显示,在访问这个 slot 前,那个受损的 long string key 对象其实已经被 lua vm 释放过了。


一开始我们怀疑是自定义的内存分配器有 bug ,但很快放弃了这个想法,转而去追查 lua 的 gc 过程。这个 table 是 key value 都是弱的弱表,若只设置 value 为弱则不会触发 bug 。

确认问题出在清除弱表项的环节,也就是 lgc.c 中的 GCSatomic 阶段的 atomic 函数中。它有一个步骤是调用 clearkeys(g, g->allweak, NULL); 清除在扫描过程标记出来的弱表,并检查 key 是否需要清除。

该函数是这样的:


/*
** clear entries with unmarked keys from all weaktables in list 'l' up
** to element 'f'
*/
static void clearkeys (global_State *g, GCObject *l, GCObject *f) {
  for (; l != f; l = gco2t(l)->gclist) {
    Table *h = gco2t(l);
    Node *n, *limit = gnodelast(h);
    for (n = gnode(h, 0); n < limit; n++) {
      if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) {
        setnilvalue(gval(n));  /* remove value ... */
        removeentry(n);  /* and remove entry from table */
      }
    }
  }
}

遍历 hash 表,当 value 不为空,且 key 可以被清除的时候,将 slot 清空。

string 对于 gc 是一个特殊的对象,因为它即是一个 GCObject ,但又被视为值而不是引用。string 并不会因为在 vm 中没有 weak table 之外的地方引用而被清除。对 string 的特殊处理是在 iscleared 函数中完成的。

/*
** tells whether a key or value can be cleared from a weak
** table. Non-collectable objects are never removed from weak
** tables. Strings behave as 'values', so are never removed too. for
** other objects: if really collected, cannot keep them; for objects
** being finalized, keep them in keys, but not in values
*/
static int iscleared (global_State *g, const TValue *o) {
  if (!iscollectable(o)) return 0;
  else if (ttisstring(o)) {
    markobject(g, tsvalue(o));  /* strings are 'values', so are never weak */
    return 0;
  }
  else return iswhite(gcvalue(o));
}

如果发现 key 是一个 string 则会将其标黑。

但是在 clearkeys 里漏掉了一点,如果 value 为 nil 是不会执行 iscleared 函数的。而什么时候 key 为 string , value 为 nil 呢?最简单的途径是主动给 table 的表项设置为 nil 。这样,在 gc 一轮后,hash 表中就可能残留一个已经被释放的 GCObject 指针。

如果这个 string 是一个短 string 其实不会引起问题,因为再次设置 hash 表的时候,short string 是按指针比较的,不会访问其内容;但是 long string 不一样,hash set 时真的会比较对象的内容:两个 long string 是否相等取决于 string 的值相同,而不必是对象内存地址相同。


制作一个纯 lua 的 MWE 很困难,所以我写了一段 C 代码来演示这个问题:

#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
#include <stdlib.h>
#include <lstring.h>

static void *
l_alloc (void *ud, void *ptr, size_t osize, size_t nsize) {
    if (nsize == 0) {
        printf("free %p\n", ptr);
        free(ptr);
        return NULL;
    } else {
        return realloc(ptr, nsize);
    }
}

static int
lpointer(lua_State *L) {
    const char * str = luaL_checkstring(L, 1);
    const TString *ts = (const TString *)str - 1;
    lua_pushlightuserdata(L, (void *)ts);
    return 1;
}

const char *source = "\n\
local a = setmetatable({} , { __mode = 'kv' })\n\
a['ABCDEFGHIJKLMNOPQRSTUVWXYZ' .. 'abcdefghijklmnopqrstuvwxyz' ] = {}\n\
print(pointer((next(a))))\n\
a[next(a)] = nil\n\
collectgarbage 'collect'\n\
local key = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' .. 'abcdefghijklmnopqrstuvwxyz'\n\
print(pointer(key))\n\
a[key] = {}\n\
print(pointer((next(a))))\n\
";

int main() {
    lua_State *L = lua_newstate (l_alloc, NULL);
    luaL_openlibs(L);
    lua_pushcfunction(L, lpointer);
    lua_setglobal(L, "pointer");
    luaL_dostring(L, source);

    return 0;
}

运行输出:

...
userdata: 00000000006fedd0     这里是ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
free 00000000006FAB50     这里进入 GC 开始释放不用的对象
free 00000000006FA890
free 00000000006FE940
free 00000000006FE910
free 0000000000000000
free 00000000006FA650
free 00000000006FEDD0      这里显示前面那个长字符串 6FEDD0 已经释放了。
free 00000000006FEBC0
free 0000000000000000
free 00000000006FAA50
free 00000000006F9770
userdata: 00000000006f1eb0   这里构造了一个新的字符串
 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
userdata: 00000000006fedd0   这里显示前面那个已经被释放的 6FEDD0  字符串又回来了。

这个 bug 最简单的修改方法是把 clearkeys 中的 !ttisnil(gval(n)) 条件判断去掉。不过或许还有更完善的解决方案。

我已经将 bug report 到 lua 的邮件列表,暂时尚未被官方确认修正。

August 11, 2017

基于办公的 IM 的基础设计

现在的 IM 在设计上是基于会话的,多个人可以组成一个会话,相当于一个聊天室,当一个人加入到一个会话后,就可以看到从加入开始之后这个聊天室里所有参与人的发言。有的 IM 会把两人对话也抽象成同一个东西,也可能出于优化的考虑把双人对话特殊处理。

所以,这些 IM 在操作界面上会有一个会话列表:表现出来会是联系人名单、聊天群列表等等。选中会话列表中的项目,进入会话查看聊天记录、发言,就是这类 IM 的使用逻辑。

我认为,这种对即时通讯的抽象方式,其实是不适合办公环境的。和日常个人社交环境不同,办公群体其实是一个相对关系密切的团体,我们通常不会拉黑一个同事不让他给你发消息,也不会拒收公司发的通告,也不会因为一个同事平常不和你打交道就拒绝建立联系。项目组里的讨论,也未见得是多么保密的事情,需要防止隔壁组的同事旁听。你也很少会在办公 IM 上和妹子私聊谈人生理想。

我们这几年使用腾讯的 RTX 作为公司办公使用,我就感受到了太多这类设计缺陷。比如,有同事找我有事,我忽略了他的私聊信息;找人一般在对方活跃的项目群组里吼;程序群沦为了日常扯淡的位置,常常同时讨论着不同的问题,线索及其混乱。“群”这个设计,我在很多年前就思考过 ,我一直觉得需要在根本上换个角度看待社交聊天的需求。

我现在的想法是这样的:

作为办公 IM ,我们不应该基于固定会话(群)来设计,而应该是“通知”和“话题”。

所谓通知,就是有人发起了一条消息,他需要把这条消息传达给某些对象,对象可以是人,也可以是某个组织:比如程序、游戏项目组、等等。

组织并非是群那样的聊天室,而仅仅是一个标签,由人来关注标签,而不是去组织这个聊天室里有多少听众。

而话题,则是由消息或旧话题衍生而来。任何通知消息、话题内部消息,都可以变成一个新话题。话题也可以包含在一则消息里转发给某个对象。

用户的客户端应该把所有的通知按时间线排列在一起,呈现在同一个地方。也就是说,无论是谁给我发消息(默认就是通知)都应该投递在一起,而不是像现在 RTX 那样只是在系统托盘里闪烁提醒、也不是微信 qq 那样,联系人名单上多出一个小红点。

而一旦我回复一个通知消息,其实就把这则通知转化成了一个话题,在时间线上,话题内的消息是归属在一起的。同一时刻,无论你的思维切换多么快,其实在短时间内你只能聚焦在一个话题上,所以客户端界面是很容易表达的,把当前话题展开在主界面(通知的时间线)即可,切换话题后自然可以折叠起来。

话题并不是聊天室、它更像是论坛的帖子。一个话题可以有很多人参与(至少发言一次),更应该支持更多的人浏览。我们不应该按聊天室的思路:用户只有在加入聊天室的那一刻开始,才能收到后续的消息,而应该像论坛那样,他只是打开了这个话题帖,可以随时聊天过去到现在发生的事情。话题内的任何一个消息,都可以由用户展开为新话题,老话题对新话题只是一个引用链接而已,并不需要有层级关系,我们也可以把任意一个话题或尚未转化为话题的消息转发出去,如果有人对他评论,就生成了新话题。

话题是一个有时效性的东西,对于办公来说,如果一个话题超过 8 小时没有新的消息,就可以认为这个话题已经结束了。但是事后我们依然可以对老话题浏览,或是继续讨论,而继续讨论就是生成的一个新话题了。

只要生成话题足够方便,每个用户的主时间线上就只会有不多的通知消息,信息传达更为有效。而管理每天的消息、检索旧消息也有很强的时间线。不像现有的 IM 群聊天,每天的聊天内容会被自然的组织成话题,这些话题上标识了参与人数、归属的组织的 tag 、继承于哪个父话题或通知、经历的时间段、衍生出哪些后续话题,等等。

即使是两个人之间的对话,也同样应该是话题的形式,而不应该把消息直接组织成一长串的聊天历史。话题未必有明确的主题,只是一种更自然的信息聚合形式而已。

对于办公场合来说,有意个最重要的优势:用户群有足够的自律。基于这种自律,我认为上面的思路若实现出来很容易推广使用。

在自律之外,或许还需要一些权限管理。这些权限管理应该是相对松散简单的,主要是限制用户订阅特定组织的 tag (比如一般员工不能订阅管理层的 tag ),限制围观特定话题(比如两人之间的私聊话题默认就是不对第三人开放权限的),话题可以锁定不准转发。权限设置的细节还需要进一步推敲。