« February 2011 | Main | April 2011 »

March 31, 2011

废稿留档:Effective C++ 3rd 的评注版(序)

Effective C++ 3rd 的评注版要出版了。我在这本书上花了不少心血。编辑约我最后写一篇序。我新码了点文字,用了点以前 blog 上写的旧文

今天侠少同学说“现在全文看下来还是有些纠结,反对、支持、再反对,再支持,百转千回的小情绪,读者恐怕会犯晕”。嗯,的确很羞愧的。不应该在这本大牛的书前面发牢骚。打算晚上改稿子。旧稿就贴这里存档吧。


2010 年秋电子社编辑侠少寄给我一本Effective C++(第三版)英文原版书,并托我为这本书写一些评注,希望做成评注版在国内出版。老实说,之前我并无阅读这本书的计划。 通过更深入地理解 C++ 而获得一种喜悦感,是十多年前的事情了。那时我刚刚从 C 语言迁移到 C++ 来做实际的项目。当时,我接触学习 C++已有六七个年头,一直未把它作为主要工作语言来用。

2000 年前后国内突然出版了大批 C++语言相关的著作,我读了一本后便一发不可收拾。之前已有的语言经验,让我的阅读没有太大障碍。而几乎是空白的 C++大型软件项目经验,让我没有各种先入为主的偏见。从纯粹学习语言的角度来讲,Effective C++ 是相当重要的一本书。阅读到这一本时,我已经用 C++ 编写过一个开源的游戏引擎,有数万行代码,书中总结的条款读来总觉得心有戚戚焉。我几乎是在书店驻足读完大半本书,才去收银台买下来的。

之后的几年里,我用 C++ 编写了数十万行代码。写得越多,对之前的作品越不满意,代码风格也随着阅读而变化,而且慢慢产生怀疑,到底是否存在一种普遍合理高效的C++ 使用方法:它可以让其他程序员,或是将来的自己审阅代码后,表示一致赞赏,而不需要用无休止的重构来满足自己的完美主义倾向。

后来,我的日常工作逐步转移回 C 语言开发,并开始大量使用多语言混合编程(使用的最多的是一种动态类型语言 Lua )。网络上对 C++的批评和质疑的声音越来越多。我自己也在 Blog (http://blog.codingnow.com)上写过数篇响应这种声音的文章。我想我对 C++ 已经足够了解,有较为丰富的实践经验,有能力表达自己的看法。

我觉得,作为一个热爱编程的程序员,在职业生涯中,对特性丰富的 C++ 语言没产生过兴趣并为之吸引,是几乎不可能的事情;而始终停留在对 C++ 的热恋中,把它作为解决一切问题的万能钥匙,亦非优秀的程序员。无论是 C++ 的狂热份子,还是希望了解C++不足的一般程序员,这本书都非常值得一读。当我全部读完这本书,深深地感觉到,较之前些年读的第二版,这简直是一本新书。

这本书,我读得很慢,不仅仅是因为这是一本英文书,还因为编辑之托。对于要印成白纸黑字的文章,不得不谨慎一些。所以,我又重温了《C++语言的设计和演化》的几个章节。可能还是因为我对 C++偏见过多,其程度有如前几年对其的推崇备至。总觉得书里讲得太细,有自己的观点本是好的,只是局限在了 C++ 语言中。明明是 C++ 的缺陷,却让人绞尽心力地回避那些问题,或以 C++ 独特的方式回避。在别的语言中不该存在的问题,却成了 C++程序员必备的知识。人生苦短,何苦制造问题来解决之。

可这也正映射了本书的主题:有效使用 C++ 。读下去,感觉能懂 Scott Meyers了。我不相信大牛如厮,这个主题写了十多年,就没有什么可抱怨的。当我读到 Item 25 ,关于对 std::swap 的扩展问题(原书第109页) 引申到特例化 std 名字空间里的方法时,一句“Alas, the form of the prohibition may dismayyou” 尽显无奈,不由会心一笑。

我是在去广州开会的旅途上开始读这本书的。当时飞机晚点,在机场耽搁了四个小时,随身带的就这本书和一支铅笔,连同空中的时间,一共六小时,在书上做了几千字的记录。后来在新西兰,晚上边读边记,磨磨蹭蹭地读了几十页,当是把书越读越厚了。

如果不是为了完成先前百般推脱的这个任务,想来是不会这么有耐心逐字读那些英文句子的。读得越细越发现没啥好评注的。要以我近年对 C++的态度,每篇只读个标题,估计就草草翻过了。都是 C++ 程序员必备的知识,还翻来覆去讲个没完。剩下那些语法细节,属于语言工具相关的知识,不做 C++ 程序员本不必学习了,没太大启发。

结果,评注下来大部分都是对 C++的争议。稿子发给侠少看了,说是缺少一些对“初学者解惑和提速”的部分,而“批判固然是好的”,但比例也太大了。而且大部分页面空空,没落任何文字。

我也认为,无论怎样写下文章,都带有现实的局限性。或许过两年想法就变了。但文字印刷出来,就无法更改。希望不要因我言论误导,而放弃学习 C++。更不希望因为我的评注,影响了书的销量。如果说,我的评注只是对 C++ 的批评,那是一种误解。评注这个工作比翻译难做。作者细节上讲地非常清楚,大部分地方都不觉得有必要再加注解。原文的英文非常流畅,前后反复呼应,让我这个平时英文阅读量并不大的人,也可以舒适阅读。我想跟这本书反复写了十年有关。所以很多页我都没留评注,真的不知道可以写什么。

除了少部分评注,是针对个别代码段,或关键词,大部分都是独立成段的。跟具体原文句子关系不大,只跟篇章段落主题有些许联系。限于水平,有很多地方,我想表达,但依然没讲透彻,感觉是一种遗憾。相对于Scott Meyers 积累了十数年的精彩文字,我这个后学晚辈仓促成文并列其间,实在是诚惶诚恐的。希望其中错误之处,方家看到能一笑了之。

祝各位读者拥有和我一样的愉快阅读体验。

云风 2011 年春 于 杭州

Lua GC 的源码剖析 (5)

今天来说说 write barrier 。

在 GC 的扫描过程中,由于分步执行,难免会出现少描了一半时,那些已经被置黑的对象又被修改,需要重新标记的情况。这就需要在改写对象时,建立 write barrier 。在扫描过程中触发 write barrier 的操作影响的对象被正确染色,或是把需要再染色的对象记录下来,留到 mark 的最后阶段 atomic 完成。

和 barrier 相关的 API 有四个,定义在 lgc.h 86 行:

#define luaC_barrier(L,p,v) { if (valiswhite(v) && isblack(obj2gco(p)))  \
    luaC_barrierf(L,obj2gco(p),gcvalue(v)); }

#define luaC_barriert(L,t,v) { if (valiswhite(v) && isblack(obj2gco(t)))  \
    luaC_barrierback(L,t); }

#define luaC_objbarrier(L,p,o)  \
    { if (iswhite(obj2gco(o)) && isblack(obj2gco(p))) \
        luaC_barrierf(L,obj2gco(p),obj2gco(o)); }

#define luaC_objbarriert(L,t,o)  \
   { if (iswhite(obj2gco(o)) && isblack(obj2gco(t))) luaC_barrierback(L,t); }

luaC_barrierluaC_objbarrier 功能上相同,只不过前者是针对 TValue 的,后者则针对 GCObject 。它用于把 v 向 p 关联时,当 v 为白色且 p 为黑色时,调用 luaC_barrierf

luaC_barriertluaC_objbarriert 则是用于将 v 关联到 t 时,调用 luaC_barrierback 。当然前提条件也是 v 为白色,且 t 为黑色。

为何 table 要被特殊对待?

因为 table 的引用关系是 1 对 N ,往往修改同一个 table 是很频繁的。而其它对象之间则是有限的联系。分开处理可以减少 barrier 本身的开销。

luaC_barrierf 用于把新建立联系的对象立刻标记。它的实现在 lgc.c 的 663 行:

void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  lua_assert(ttype(&o->gch) != LUA_TTABLE);
  /* must keep invariant? */
  if (g->gcstate == GCSpropagate)
    reallymarkobject(g, v);  /* restore invariant */
  else  /* don't mind */
    makewhite(g, o);  /* mark as white just to avoid other barriers */
}

简而言之,当 GC 处于 GCSpropagate 状态(mark 流程中),就标记 v 。否则,把与之联系的节点 o 从黑色置为白色。前面我们已经说过,lua 的 GC 采用了两种白色标记,乒乓切换。在 mark 流程结束后,白色状态被切换。这个时候调用 makewhite 并不会导致 sweep 过程清除这个节点。同时,由于 o 变为白色,就可以减少 barrier 的开销。即,再有对 o 的修改,不会产生 luaC_barrierf 的函数调用了。

luaC_barrierback 会把要修改的 table 退回 gary 集合,留待将来继续标记。见代码 lgc.c 的 676 行:

void luaC_barrierback (lua_State *L, Table *t) {
  global_State *g = G(L);
  GCObject *o = obj2gco(t);
  lua_assert(isblack(o) && !isdead(g, o));
  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  black2gray(o);  /* make table gray (again) */
  t->gclist = g->grayagain;
  g->grayagain = o;
}

这里提到了 grayagain 链,昨天已经看到,这个链表会推迟到 atomic 阶段处理。把 table 设会灰色可使后续对其的修改不再触发 luaC_barrierback

注意,对弱表的修改是不会触发 luaC_barrierback 的。因为弱表不会是黑色。弱表也不能触发它。因为每个 GCObject 都只能存在于一个链表上。弱表自己挂接到 weak 链,就不能向 grayagain 挂接。这就解释了 lgc.c 285 行:

      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */

为何要把弱表从黑色设回灰色。

因为弱表又分 key weak 和 value weak ,它倒不一定完全都包含了弱引用。在扫描过程中,对弱表的修改又不会触发 barrier 。这会导致最终扫描完成后,某些弱表里可能还藏有一些新建立的强应用关系。到这里,我们便可以解释昨天遗留的另一个问题,弱表为何到了 atomic 节点需要再次 mark 。见 lgc.c 的 533 行:

  /* remark weak tables */
  g->gray = g->weak;
  g->weak = NULL;
  lua_assert(!iswhite(obj2gco(g->mainthread)));
  markobject(g, L);  /* mark running thread */
  markmt(g);  /* mark basic metatables (again) */
  propagateall(g);

再次 mark basic metatables 的原因是,设置基本类型的全局 metatable 并没有设置 write barrier (这组 metatable 比较特殊,不适合用以上的 barrier 函数)。见 lapi.c 的 710 行:

  switch (ttype(obj)) {
    case LUA_TTABLE: {
      hvalue(obj)->metatable = mt;
      if (mt)
        luaC_objbarriert(L, hvalue(obj), mt);
      break;
    }
    case LUA_TUSERDATA: {
      uvalue(obj)->metatable = mt;
      if (mt)
        luaC_objbarrier(L, rawuvalue(obj), mt);
      break;
    }
    default: {
      G(L)->mt[ttype(obj)] = mt;
      break;
    }
  }

这里,修改 table 的 metatable 调用了 luaC_objbarriert ,修改 userdata 的 metatable 调用了 luaC_objbarrier ,修改全局 metatable 是直接进行的。

如果审查所有的代码,会发现 barrier 的调用分布在很多地方。大多数情况下,barrier 的开销并不大,就是一次条件判断。但 barrier 也会被执行很频繁,性能必须有保障,这也是为什么 barrier 相关 api 都用宏来实现的缘故。


理解了 write barrier 的实现,我们就可以回头来看 propagatemark 过程了。

propagatemark 每次会标记一个灰色对象所有的关联节点,并把自己置为黑色。见 lgc.c 的 273 行。

/*
** traverse one gray object, turning it to black.
** Returns `quantity' traversed.
*/
static l_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  lua_assert(isgray(o));
  gray2black(o);
  switch (o->gch.tt) {

之后就是对需要迭代标记的具体类型的处理了。

对 table 的处理是这样的,见 lgc.c 的 282 行:

    case LUA_TTABLE: {
      Table *h = gco2h(o);
      g->gray = h->gclist;
      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */
      return sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h);
    }

从 gray 链上取掉当前 table 节点,然后迭代这个 table ,如果是一个弱表,则把其还原为灰色。

traversetable 枚举了 table 中的所有引用项。并对弱表做了处理。见 lgc.c 的 166 行:

  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
    weakkey = (strchr(svalue(mode), 'k') != NULL);
    weakvalue = (strchr(svalue(mode), 'v') != NULL);
    if (weakkey || weakvalue) {  /* is really weak? */
      h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
      h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
                             (weakvalue << VALUEWEAKBIT));
      h->gclist = g->weak;  /* must be cleared after GC, ... */
      g->weak = obj2gco(h);  /* ... so put in the appropriate list */
    }
  }

被扫描到的弱表把自己挂到了 weak 链上。单独保存一个链表是因为弱表在扫描的最后阶段还需要把里面不存在的弱引用项清理掉。关于清理工作,是由 atomic 函数中对 cleartable 调用完成的。昨天已经讲过,无庸赘述。

对 function 的 mark 工作在 traverseclosure 函数中进行,lgc.c 224 行:

static void traverseclosure (global_State *g, Closure *cl) {
  markobject(g, cl->c.env);
  if (cl->c.isC) {
    int i;
    for (i=0; ic.nupvalues; i++)  /* mark its upvalues */
      markvalue(g, &cl->c.upvalue[i]);
  }
  else {
    int i;
    lua_assert(cl->l.nupvalues == cl->l.p->nups);
    markobject(g, cl->l.p);
    for (i=0; il.nupvalues; i++)  /* mark its upvalues */
      markobject(g, cl->l.upvals[i]);
  }
}

lua 中 C Function 和 Lua Function 的内部结构是不同的。所以是分别独立的代码。主要就是对 upvalue 以及环境表的标记了。

对 thread 的处理相对复杂一点。见 lgc.c 297 行:

    case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      g->gray = th->gclist;
      th->gclist = g->grayagain;
      g->grayagain = o;
      black2gray(o);
      traversestack(g, th);
      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci;
    }

这里的链表操作可以简述为,把自己从 gray 链上摘下,放到 grayagain 链表中。并把自己保持为灰色状态。

这是因为 thread 关联的对象其实是运行堆栈,堆栈是随着运行过程不断变化的。如果目前尚处于 mark 流程没有结束的话,后面发生变化是很有可能的。而 stack 上数据的修改是不经过 write barrier 的。也没有必要为最频繁的 stack 修改做 barrier ,那样对性能影响就很大了。最简单的办法就是把 thread 推迟到 atomic 阶段重扫描一次。

atomic 函数,lgc.c 537 行的

  markobject(g, L);  /* mark running thread */

也是这个用意。

ps. lua 的 GC 在实现时,即使要推迟扫描,也要先做一次。都是为了 atomic 阶段尽量短,把有可能遍历的部分先遍历完。

TPROTO 对象的遍历函数在 lgc.c 的 199 行:

/*
** All marks are conditional because a GC may happen while the
** prototype is still being created
*/
static void traverseproto (global_State *g, Proto *f) {
  int i;
  if (f->source) stringmark(f->source);
  for (i=0; isizek; i++)  /* mark literals */
    markvalue(g, &f->k[i]);
  for (i=0; isizeupvalues; i++) {  /* mark upvalue names */
    if (f->upvalues[i])
      stringmark(f->upvalues[i]);
  }
  for (i=0; isizep; i++) {  /* mark nested protos */
    if (f->p[i])
      markobject(g, f->p[i]);
  }
  for (i=0; isizelocvars; i++) {  /* mark local-variable names */
    if (f->locvars[i].varname)
      stringmark(f->locvars[i].varname);
  }
}

如注释所言,这里有很多的判断。这缘于 prototype 的创建过程是可能分步的,中间有可能被 GC 打断。prototype 的创建伴随着诸多 GCObject 的创建。新对象的创建(大多数是 string)带来的是新的内存申请,很容易触发自动 GC 的进行。如果对 prototype 的创建过程有兴趣,可以去阅读 lparser.c 的 luaY_parser 函数,以及 lundump.c 中的 luaU_undump 函数。

以上就是所有需要迭代遍历的数据类型了。

一切准备妥当后,GC 将切换到 GCSsweepstring 。见 lgc.c 548 行:

  /* flip current white */
  g->currentwhite = cast_byte(otherwhite(g));
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gcstate = GCSsweepstring;
  g->estimate = g->totalbytes - udsize;  /* first estimate */

这时,userdata 的 gc 元方法虽未调用,所有不再有引用的 userdata 不会在这趟 GC 环节中清理出去,但它们占据的空间已经被 estimate 忽略。

Lua GC 的源码剖析 (4)

今天来看一下 mark 过程是怎样实现的。

所有的 GC 流程,都从 singlestep 函数开始。singlestep 就是一个最简单的状态机。GC 状态简单的从一个状态切换到下一个状态,循环不止。状态标识放在 global state 的 gcstate 域中。这一点前面谈过。

开始的两个状态和 mark 过程有关。

初始的 GCSpause 状态下,执行 markroot 函数。我们来看一下 markroot 的代码。见 lgc.c 的 501 行。

/* mark root set */
static void markroot (lua_State *L) {
  global_State *g = G(L);
  g->gray = NULL;
  g->grayagain = NULL;
  g->weak = NULL;
  markobject(g, g->mainthread);
  /* make global table be traversed before main stack */
  markvalue(g, gt(g->mainthread));
  markvalue(g, registry(L));
  markmt(g);
  g->gcstate = GCSpropagate;
}

主要是把状态复位的操作以及标记根节点。

lua 采用是 Tri-colour marking GC 算法 。需要维护一个灰色节点集。这里用 gary 存放。grayagain 保存着需要原子操作标记的灰色节点。

weak 保存着需要清理的 weak 表。

这里的 markobject 和 markvalue 都是用宏实现的。区别仅在于操作的是 GCObject 还是 TValue 。最终都是通过调用 reallymarkobject 实现的。markmt 也是直接 mark 的 global state 中的若干元表。这些元表作用于基本的几个数据类型。这些加起来成为整个数据的根。对 lua 语言有所了解的话,不难理解这几行实现。

核心的实现见 lgc.c 的 69 行

static void reallymarkobject (global_State *g, GCObject *o) {
  lua_assert(iswhite(o) && !isdead(g, o));
  white2gray(o);
  switch (o->gch.tt) {
    case LUA_TSTRING: {
      return;
    }
    case LUA_TUSERDATA: {
      Table *mt = gco2u(o)->metatable;
      gray2black(o);  /* udata are never gray */
      if (mt) markobject(g, mt);
      markobject(g, gco2u(o)->env);
      return;
    }
    case LUA_TUPVAL: {
      UpVal *uv = gco2uv(o);
      markvalue(g, uv->v);
      if (uv->v == &uv->u.value)  /* closed? */
        gray2black(o);  /* open upvalues are never black */
      return;
    }
    case LUA_TFUNCTION: {
      gco2cl(o)->c.gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TTABLE: {
      gco2h(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TTHREAD: {
      gco2th(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TPROTO: {
      gco2p(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    default: lua_assert(0);
  }
}

它按 GCObject 的实际类型来 mark 它。reallymarkobject 的时间复杂度是 O(1) 的,它不会递归标记相关对象,虽然大多数 GCObject 都关联有其它对象。

保证 O(1) 时间使得标记过程可以均匀分摊在逐个短小的时间片内,不至于停止世界太久。这里就需要用到三色标记法。

reallymarkobject 进入时,先把对象设置为灰色(通过 white2gray 这个宏)。然后再根据具体类型,当一个对象的所有关联对象都被标记后,再从灰色转为黑色。

因为 TSTRING 一定没有关联对象,而且所有的字符串都是统一独立处理的。这里可以做一个小优化,不需要设置为黑色,只要不是白色就可以清理。所以此处不必染黑。

但 TUSERDATA 则不同,它是跟其它对象一起处理的。标记 userdata 就需要调用 gray2black 了。另外,还需要标记 userdata 的元表和环境表。

TUPVAL 是一个特殊的东西。在 lua 编程,以及写 C 代码和 lua 交互时,都看不到这种类型。它用来解决多个 closure 共享同一个 upvalue 的情况。实际上是对一个 upvalue 的引用。问什么 TUPVAL 会有 open 和 closed 两种状态?应该这样理解。

当一个 lua 函数本执行的时候,和 C 语言不一样,它不仅可以看到当前层次上的 local 变量,还可以看到上面所有层次的 local 变量。这个可见性是由 lua 解析器解析你的 lua 代码时定位的(换句话说,就是在“编译”期决定的)。那些不属于你的函数当前层次上的 local 变量,就称之为 upvalue 。upvalue 这个概念是由 parser 引入的。在 Lua 中,任何一个 function 其实都是由 proto 和运行时绑定的 upvalue 构成的。proto 将如何绑定 upvalue 是在 parser 生成的 bytecode 里描述清楚了的。如果对这一块的实现代码有兴趣,可以参考 lvm.c 的 719 行:

      case OP_CLOSURE: {
        Proto *p;
        Closure *ncl;
        int nup, j;
        p = cl->p->p[GETARG_Bx(i)];
        nup = p->nups;
        ncl = luaF_newLclosure(L, nup, cl->env);
        ncl->l.p = p;
        for (j=0; jl.upvals[j] = cl->upvals[GETARG_B(*pc)];
          else {
            lua_assert(GET_OPCODE(*pc) == OP_MOVE);
            ncl->l.upvals[j] = luaF_findupval(L, base + GETARG_B(*pc));
          }
        }
        setclvalue(L, ra, ncl);
        Protect(luaC_checkGC(L));
        continue;
      }

我们会看到,调用 luaF_newLclosure 生成完一个 Lua Closure 后,会去填那张 upvalue 表。当 upvalue 尚在堆栈上时,其实是调用 luaF_findupval 去生成一个对堆栈上的特定值之引用的 TUPVAL 对象的。luaF_findupval 的实现不再列在这里,它的主要作用就是保证对堆栈相同位置的引用之生成一次。生成的这个对象就是 open 状态的。所有 open 的 TUPVAL 用一个双向链表串起来,挂在 global state 的 uvhead 中。

一旦函数返回,某些堆栈上的变量就会消失,这时,还被某些 upvalue 引用的变量就必须找个地方妥善安置。这个安全的地方就是 TUPVAL 结构之中。修改引用指针的结果,就被认为是 close 了这个 TUPVAL 。相关代码可以去看 lfunc.c 中 luaF_close 的实现。

走题太多。现在回来看 TUPVAL 的 mark 过程。mark upvalue 引用的对象之后,closed TUPVAL 就可以置黑了。为何 open 状态的 TUPVAL 需要留为灰色待处理呢?这是因为 open TUPVAL 是易变的。GC 分步执行,我们无法预料在 mark 流程走完前,堆栈上被引用的数据会不会发生变化。

事实上,在 mark 的最后一个步骤,我们会看到所有的 open TUPVAL 被再次 mark 一次。做这件事情的函数是 lgc.c 516 行的:

static void remarkupvals (global_State *g) {
  UpVal *uv;
  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
    lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
    if (isgray(obj2gco(uv)))
      markvalue(g, uv->v);
  }
}

其它的数据类型处理都很简单。把自己挂在 gray 链表上即可。这条链表将在后面的 GCSpropagate 步骤被处理到。


GC 状态为 GCSpropagate 时,singlestep 就是调用 propagatemark 处理 global state 中的 gray 链。

今天白天因为有些其他工作做,所以没有留太多时间写这篇 Blog ,propagatemark 内部的细节分析得等到下一篇了。从总体看来,propagatemark 标记了各种 GCObject 的直接相关级的对象。

到这里,我们可以回答昨天遗留下来的一个问题:GC 的分步过程是如何控制进度的。

从前面分析过的代码上来,singlestep 的返回值决定了 GC 的进度。在 GC 进行过程中,如何知道做完整个 GC 流程的时间,以及目前做的进度呢?

我们可以依靠的数据只有内存管理器辖下的内存数量。大致上,整个 GC 需要的总时间和 GCObject 的数量成正比。但每种类型的 GCObject 的处理时间复杂度却各不相同。仔细衡量每种类型的处理时间差别不太现实,它可能和具体机器也有关系。但我们却可以大体上认为,占用内存较多的对象,处理时间也更长一点。这里不包括 string 和 userdata 。它们即使占用内存较多,但却没有增加 mark 的时间。虽然不太精确,但对 table ,function ,thread 这些类型来说,这种估算方式却比较接近。

所以在 propagatemark 过程中,每 mark 一个灰色节点,就返回了它实际占用的内存字节数作为 quantity 值。

如果回顾昨天看过的代码。

  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */
  g->gcdept += g->totalbytes - g->GCthreshold;
  do {
    lim -= singlestep(L);
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);

我们就能理解,当 gcstepmul 为 100 时,每次由 luaC_checkGC 满足条件后调用一次 luaC_step ,大致就会标记 1K 的数据(当处于 mark 环节中时)。而每次 luaC_step 会递增 GCthreshold 1K 。

  if (g->gcstate != GCSpause) {
    if (g->gcdept < GCSTEPSIZE)
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {
      g->gcdept -= GCSTEPSIZE;
      g->GCthreshold = g->totalbytes;
    }
  }

依赖自动 GC ,只有 totalbytes 持续增长才会驱动 luaC_step 不断工作下去的。但增长速度如果快于 mark 速度,那么就会产生问题。这正是 lua 手册中所警告的:“step multiplier 控制了收集器相对内存分配的速度。 更大的数字将导致收集器工作的更主动的同时,也使每步收集的尺寸增加。 小于 1 的值会使收集器工作的非常慢,可能导致收集器永远都结束不了当前周期。”

我们也可以看到,自动 GC 过程处于 sweep 流程时,收集器也并不那么急于释放内存了。因为释放内存会导致 totalbytes 减少,如果没有新的对象分配出来,totalbytes 是不会增加到触发新的 luaC_step 的。

手动分步 GC 则是另一番光景。lua_gc GCSTEP 使用的 data 值,在处于 mark 流程时,便可以认为扫描的内存字节数乘上 step multiplier 这个系数。当然这只是大致上个估计。毕竟内存不是理想中的逐字节扫描的。

等待所有灰色节点都处理完,我们就可以开始清理那些剩下的白色节点了吗?不,因为 mark 是分步执行的,中间 lua 虚拟机中的对象关系可能又发生的变化。所以在开始清理工作前,我们还需要做最后一次扫描。这个过程不可以再被打断。

让我们看看相关的处理函数。见 lgc.c 526 行:

static void atomic (lua_State *L) {
  global_State *g = G(L);
  size_t udsize;  /* total size of userdata to be finalized */
  /* remark occasional upvalues of (maybe) dead threads */
  remarkupvals(g);
  /* traverse objects cautch by write barrier and by 'remarkupvals' */
  propagateall(g);
  /* remark weak tables */
  g->gray = g->weak;
  g->weak = NULL;
  lua_assert(!iswhite(obj2gco(g->mainthread)));
  markobject(g, L);  /* mark running thread */
  markmt(g);  /* mark basic metatables (again) */
  propagateall(g);
  /* remark gray again */
  g->gray = g->grayagain;
  g->grayagain = NULL;
  propagateall(g);
  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
  marktmu(g);  /* mark `preserved' userdata */
  udsize += propagateall(g);  /* remark, to propagate `preserveness' */
  cleartable(g->weak);  /* remove collected objects from weak tables */
  /* flip current white */
  g->currentwhite = cast_byte(otherwhite(g));
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gcstate = GCSsweepstring;
  g->estimate = g->totalbytes - udsize;  /* first estimate */
}

代码中注释的很详细。propagateall 是用来迭代所有的灰色节点的。所以每个关键步骤结束后,都需要调用一下保证处理完所有可能需要标记的对象。第一个步骤是那些 open 的 TUPVAL ,在前面已经提及。然后是处理弱表。

弱表是个比较特殊的东西,这里,弱表需要反复 mark ,跟 write barrier 的行为有关,超出了今天的话题。write barrier 还会引起另一些对象再 mark ,即对 grayagain 链的处理。都留到明天再谈。

接下来处理 userdata 的部分,luaC_separateudata 之前已经解释过了。

所以的一切都标记完后,那些不被引用的对象就都被分离出来了。可以安全的清理所有尚被引用的弱表。cleartable 就是干的这件事情。实现没有什么好谈的,一目了然。这里也不列代码了。不过值得一提的是对可以清理的项的判定函数:iscleared 。见 lgc.c 的 329 行。

/*
** The next function 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 userdata
** being finalized, keep them in keys, but not in values
*/
static int iscleared (const TValue *o, int iskey) {
    printf("is cleared %p,%d\n", o,iskey);
  if (!iscollectable(o)) return 0;
  if (ttisstring(o)) {
    stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
    return 0;
  }
  return iswhite(gcvalue(o)) ||
    (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
}

如果你对 for userdata being finalized, keep them in keys, but not in values 这一句表示困惑的话。可以读读 Roberto 对此的解释

和那些被清理掉的 userdata 一样。当 userdata 被标为白色,在下一个 GC 周期中,它便不再认为是 isfinalized 状态。对应弱表中的 k/v 就被真的被清除掉了。

March 29, 2011

Lua GC 的源码剖析 (3)

有了前几天的基础,我们可以从顶向下来读 lua gc 部分的代码了。

我们知道,lua 对外的 API 中,一切个 gc 打交道的都通过 lua_gc 。C 语言构建系统时,一般不讲设计模式。但模式还是存在的。若要按《设计模式》中的分类,这应该归于 Facade 模式。代码在 lapi.c 的 895 行:

/*
** Garbage-collection function
*/

LUA_API int lua_gc (lua_State *L, int what, int data) {
  int res = 0;
  global_State *g;
  lua_lock(L);
  g = G(L);
  switch (what) {
    case LUA_GCSTOP: {
      g->GCthreshold = MAX_LUMEM;
      break;
    }
    case LUA_GCRESTART: {
      g->GCthreshold = g->totalbytes;
      break;
    }
    case LUA_GCCOLLECT: {
      luaC_fullgc(L);
      break;
    }
    case LUA_GCCOUNT: {
      /* GC values are expressed in Kbytes: #bytes/2^10 */
      res = cast_int(g->totalbytes >> 10);
      break;
    }
    case LUA_GCCOUNTB: {
      res = cast_int(g->totalbytes & 0x3ff);
      break;
    }
    case LUA_GCSTEP: {
      lu_mem a = (cast(lu_mem, data) << 10);
      if (a <= g->totalbytes)
        g->GCthreshold = g->totalbytes - a;
      else
        g->GCthreshold = 0;
      while (g->GCthreshold <= g->totalbytes) {
        luaC_step(L);
        if (g->gcstate == GCSpause) {  /* end of cycle? */
          res = 1;  /* signal it */
          break;
        }
      }
      break;
    }
    case LUA_GCSETPAUSE: {
      res = g->gcpause;
      g->gcpause = data;
      break;
    }
    case LUA_GCSETSTEPMUL: {
      res = g->gcstepmul;
      g->gcstepmul = data;
      break;
    }
    default: res = -1;  /* invalid option */
  }
  lua_unlock(L);
  return res;
}

从代码可见,对内部状态的访问,都是直接访问 global state 表的。GC 控制则是调用内部 api 。lua 中对外的 api 和内部模块交互的 api 都是分开的。这样层次分明。内部子模块一般名为 luaX_xxx X 为子模块代号。对于收集器相关的 api 一律以 luaC_xxx 命名。这些 api 定义在 lgc.h 中。

此间提到的 api 有两个:

LUAI_FUNC void luaC_step (lua_State *L);
LUAI_FUNC void luaC_fullgc (lua_State *L);

用于分步 GC 已经完整 GC 。

另一个重要的 api 是:

#define luaC_checkGC(L) { \
  condhardstacktests(luaD_reallocstack(L, L->stacksize - EXTRA_STACK - 1)); \
  if (G(L)->totalbytes >= G(L)->GCthreshold) \
    luaC_step(L); }

它以宏形式定义出来,用于自动的 GC 。如果我们审查 lapi.c ldo.c lvm.c ,会发现大部分会导致内存增长的 api 中,都调用了它。保证 gc 可以随内存使用增加而自动进行。

这里插几句。

使用自动 gc 会有一个问题。它很可能使系统的峰值内存占用远超过实际需求量。原因就在于,收集行为往往发生在调用栈很深的地方。当你的应用程序呈现出某种周期性(大多数包驱动的服务都是这样)。在一个服务周期内,往往会引用众多临时对象,这个时候做 mark 工作,会导致许多临时对象也被 mark 住。

一个经验方法是,调用 LUA_GCSTOP 停止自动 GC。在周期间定期调用 gcstep 且使用较大的 data 值,在有限个周期做完一整趟 gc 。

另,condhardstacktests 是一个宏,通常是不开启的。


先来看 luaC_fullgc 。它用来执行完整的一次 gc 动作。fullgc 并不是仅仅把当前的流程走完。因为之前的 gc 行为可能执行了一半,可能有一些半路加进来的需要回收的对象。所以在走完一趟流程后,fullgc 将阻塞着再完整跑一遍 gc 。整个流程有一些优化的余地。即,前半程的 gc 流程其实不必严格执行,它并不需要真的去清除什么。只需要把状态恢复。这个工作是如何做到的呢?见 lgc.c 的 637 行:

void luaC_fullgc (lua_State *L) {
  global_State *g = G(L);
  if (g->gcstate <= GCSpropagate) {
    /* reset sweep marks to sweep all elements (returning them to white) */
    g->sweepstrgc = 0;
    g->sweepgc = &g->rootgc;
    /* reset other collector lists */
    g->gray = NULL;
    g->grayagain = NULL;
    g->weak = NULL;
    g->gcstate = GCSsweepstring;
  }
  lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
  /* finish any pending sweep phase */
  while (g->gcstate != GCSfinalize) {
    lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
    singlestep(L);
  }

比较耗时的 mark 步骤被简单跳过了(如果它还没进行完的话)。和正常的 mark 流程不同,正常的 mark 流程最后,会将白色标记反转。见 lgc.c 548 行,atomic 函数:

  /* flip current white */
  g->currentwhite = cast_byte(otherwhite(g));

在 fullgc 的前半程中,直接跳过了 GCSpropagate ,重置了内部状态,但没有翻转白色标记。这会导致后面的 sweep 流程不会真的释放那些白色对象。sweep 工作实际做的只是把所有对象又重新设置回白色而已。

接下来就是一个完整不被打断的 gc 过程了。

  markroot(L);
  while (g->gcstate != GCSpause) {
    singlestep(L);
  }
  setthreshold(g);

从根开始 mark ,直到整个 gc 流程执行完毕。最后,重新设置了 GCthreshold 。注:调用 fullgc 会重置 GCthreshold ,所以如果你曾经调用 LUA_GCSTOP 暂停自动 GC 的话(也是通过修改 GCthreshold 实现) ,记得再调用一次。

stepgc 要相对复杂一些。在 lua 手册的 2.10 解释了 garbage-collector pause 和 step multiplier 的意义,却没有给出精确定义。lua_gc 的说明里,也只说“LUA_GCSTEP: 发起一步增量垃圾收集。 步数由 data 控制(越大的值意味着越多步), 而其具体含义(具体数字表示了多少)并未标准化。 如果你想控制这个步数,必须实验性的测试 data 的值。 如果这一步结束了一个垃圾收集周期,返回返回 1 。 并没有给出准确的含义。实践中,我们也都是以经验取值。

回到源代码,我们就能搞清楚它们到底是什么了。

    case LUA_GCSETPAUSE: {
      res = g->gcpause;
      g->gcpause = data;
      break;
    }
    case LUA_GCSETSTEPMUL: {
      res = g->gcstepmul;
      g->gcstepmul = data;
      break;
    }

这里只是设置 gcpause gcstepmul 。gcpause 实际只在 lgc.c 59 行的 setthreshold 宏中用到

#define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)

看见,GCSETPAUSE 其实是通过调整 GCthreshold 来实现的。当 GCthreshold 足够大时,luaC_step 不会被 luaC_checkGC 自动触发。事实上,GCSTOP 正是通过设置一个很大的 GCthreshold 值来实现的。

    case LUA_GCSTOP: {
      g->GCthreshold = MAX_LUMEM;
      break;
    }

gcpause 值的含义很文档一致,用来表示和实际内存使用量 estimate 的比值(放大 100 倍)。一旦内存使用量超过这个阀值,就会出发 GC 的工作。

要理解 gcstepmul ,就要从 lua_gcLUA_GCSTEP 的实现看起。

    case LUA_GCSTEP: {
      lu_mem a = (cast(lu_mem, data) << 10);
      if (a <= g->totalbytes)
        g->GCthreshold = g->totalbytes - a;
      else
        g->GCthreshold = 0;
      while (g->GCthreshold <= g->totalbytes) {
        luaC_step(L);
        if (g->gcstate == GCSpause) {  /* end of cycle? */
          res = 1;  /* signal it */
          break;
        }
      }
      break;
    }

step 的长度 data 被放大了 1024 倍。在 lgc.c 的 26 行,也可以看到

#define GCSTEPSIZE  1024u

我们姑且可以认为 data 的单位是 KBytes ,和 lua 总共占用的内存 totalbytes 有些关系。

ps. 这里 totalbytes 是严格通过 Alloc 管理的内存量。而前面提到的 estimate 则不同,它是一个估算量,比 totalbytes 要小。这是因为,前面也提到过,userdata 的回收比较特殊。被检测出已经访问不到的 userdata 占用的内存并不会马上释放(保证 gc 元方法的安全调用),但 estimate 会抛去这部分,不算在实际内存使用量内。

见 lgc.c 544 行

  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */

以及 lgc.c 553 行

  g->estimate = g->totalbytes - udsize;  /* first estimate */

从代码逻辑,我们暂时可以把 data 理解为,需要处理的字节数量(以 K bytes 为单位)。如果需要处理的数据量超过了 totalbytes ,自然就可以把 GCthreshold 设置为 0 了。

实际上不能完全这么理解。因为 GC 过程并不是一点点回收内存,同时可用内存越来越多。GC 分标记(mark) 清除(sweep) 调用 userdata 元方法等几个阶段。只有中间的清除阶段是真正释放内存的。所以可用内存的增加( totalbytes 减少)过程,时间上并不是线性的。通常标记的开销更大。为了让 gcstep 的每个步骤消耗的时间更平滑,就得有手段动态调整 GCthreshold 值。它和 totalbytes 最终影响了每个 step 的时间。

下面的关注焦点转向 luaC_step ,见 lgc.c 的 611 行:

void luaC_step (lua_State *L) {
  global_State *g = G(L);
  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */
  g->gcdept += g->totalbytes - g->GCthreshold;
  do {
    lim -= singlestep(L);
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);
  if (g->gcstate != GCSpause) {
    if (g->gcdept < GCSTEPSIZE)
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {
      g->gcdept -= GCSTEPSIZE;
      g->GCthreshold = g->totalbytes;
    }
  }
  else {
    lua_assert(g->totalbytes >= g->estimate);
    setthreshold(g);
  }
}

从代码我们可以看到,GC 的核心其实在于 singlestep 函数。luaC_step 每次调用多少次 singlestep 跟 gcstepmul 的值有关。

如果是自动进行的 GC ,当 totalbytes 大于等于 GCthreshold 时,就会触发 luaC_step 。每次 luaC_step ,GCthreshold 都会被调高 1K (GCSTEPSIZE) 直到 GCthreshold 追上 totalbytes 。这个追赶过程通常发生在 mark 流程。因为这个流程中,totalbytes 是只增不减的。

如果是手控 GC ,每次 gcstep 调用执行多少次 luaC_step 则跟 data 值有关。大体上是 1 就表示一次(在 mark 过程中就是这样)到了 sweep 流程就不一定了。这和 singlestep 调用次数,即 gcstepmul 的值有关。它影响了 totalbytes 的减小速度。

所以,一两句话很难严格定义出这些控制 GC 步进量的参数的含义,只能慢慢阅读代码,看看实现了。

在 lua 手册的 2.10 这样描述“step multiplier 控制了收集器相对内存分配的速度。 更大的数字将导致收集器工作的更主动的同时,也使每步收集的尺寸增加。 小于 1 的值会使收集器工作的非常慢,可能导致收集器永远都结束不了当前周期。 缺省值为 2 ,这意味着收集器将以内存分配器的两倍速运行。”

从代码看,这绝非严格定义。至少从今天已经分析的代码中还看不出这一点。

gcstepmul 的值和内存增涨速度如何产生联系?明天再写 :)

March 28, 2011

Lua GC 的源码剖析 (2)

早期的 Lua GC 采用的是 stop the world 的实现。一旦发生 gc 就需要等待整个 gc 流程走完。如果你用 lua 处理较少量数据,或是数据增删不频繁,这样做不是问题。但当处理的数据量变大时,对于实时性要求较高的应用,比如网络游戏服务器,这个代价则是不可忽略的。lua 本身是个很精简的系统,但不代表处理的数据量也一定很小。

从 Lua 5.1 开始,GC 的实现改为分步的。虽然依旧是 stop the world ,但是,每个步骤都可以分阶段执行。这样,每次停顿的时间较小。随之,这部分的代码也相对复杂了。分步执行最关键的问题是需要解决在 GC 的步骤之间,如果数据关联的状态发生了变化,如果保证 GC 的正确性。GC 的分步执行相对于一次执行完,总的时间开销的差别并不是零代价的。只是在实现上,要尽量让额外增加的代价较小。

先来看 GC 流程的划分。

lua 的 GC 分为五个大的阶段。GC 处于哪个阶段(代码中被称为状态),依据的是 global_State 中的 gcstate 域。状态以宏形式定义在 lgc.h 的 14 行。

/*
** Possible states of the Garbage Collector
*/
#define GCSpause    0
#define GCSpropagate    1
#define GCSsweepstring  2
#define GCSsweep    3
#define GCSfinalize 4

状态的值的大小也暗示着它们的执行次序。需要注意的是,GC 的执行过程并非每步骤都拥塞在一个状态上。

GCSpause 阶段是每个 GC 流程的启始步骤。只是标记系统的根节点。见 lgc.c 的 561 行。

  switch (g->gcstate) {
    case GCSpause: {
      markroot(L);  /* start a new collection */
      return 0;
    }

markroot 这个函数所做之事,就是标记主线程对象,标记主线程的全局表、注册表,以及为全局类型注册的元表。标记的具体过程我们后面再讲。

GCSpause 阶段执行完,立刻就将状态切换到了 GCSpropagate 。这是一个标记流程。这个流程会分步完成。当检测到尚有对象待标记时,迭代标记(反复调用 propagatemark);最终,会有一个标记过程不可被打断,这些操作放在一个叫作 atomic 的函数中执行。见 lgc.c 的 565 行:

    case GCSpropagate: {
      if (g->gray)
        return propagatemark(g);
      else {  /* no more `gray' objects */
        atomic(L);  /* finish mark phase */
        return 0;
      }
    }

这里可能需要顺带提一下的是 gray 域。顾名思义,它指 GCObject 中的灰色节点链。何为灰色,即处于白色和黑色之间的状态。关于节点的颜色,马上就会展开分析。

接下来就是清除流程了。

前面我们提到过,string 在 Lua 中是单独管理的,所以也需要单独清除。GCSsweepstring 阶段干的就是这个事情。string table 以 hash 表形式管理所有的 string 。GCSsweepstring 中,每个步骤(step) 清理 hash 表的一列。代码见 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;
    }

这里可以看到 estimate 和 totalbytes 两个域,从名字上可以知道,它们分别表示了 lua vm 占用的内存字节数以及实际分配的字节数。

ps. 如果你自己实现过内存管理器,当知道内存管理本身是有额外的内存开销的。如果有必要精确控制内存数量,我个人倾向于结合内存管理器统计准确的内存使用情况。比如你向内存管理器索要 8 字节内存,实际的内存开销很可能是 12 字节,甚至更多。如果想做这方面的修改,让 lua 的 gc 能更真实的反应内存实际使用情况,推荐修改 lmem.c 的 76 行,luaM_realloc_ 函数。所有的 lua 中的内存使用变化都会通过这个函数。

从上面这段代码中,我们还见到了 GCSWEEPCOST 这个神秘数字。这个数字用于控制 GC 的进度。这超出了今天的话题。留待以后分析。

接下来就是对所有未标记的其它 GCObject 做清理工作了。即 GCSsweep 阶段。它和上面的 GCSsweepstring 类似。

最后是 GCSfinalize 阶段。如果在前面的阶段发现了需要调用 gc 元方法的 userdata 对象,将在这个阶段逐个调用。做这件事情的函数是 GCTM 。

前面已经谈到过,所有拥有 gc 元方法的 userdata 对象以及其关联的数据,实际上都不会在之前的清除阶段被清除。(由于单独做过标记)所有的元方法调用都是安全的。而它们的实际清除,则需等到下一次 GC 流程了。或是在 lua_close 被调用时清除。

ps. lua_close 并不做完整的 gc 工作,只是简单的处理所有 userdata 的 gc 元方法,以及释放所有用到的内存。它是相对廉价的。


接下来我们看看 GC 标记流程涉及的一些概念。

简单的说,lua 认为每个 GCObject (需要被 GC 收集器管理的对象)都有一个颜色。一开始,所有节点都是白色的。新创建出来的节点也被默认设置为白色。

在标记阶段,可见的节点,逐个被设置为黑色。有些节点比较复杂,它会关联别的节点。在没有处理完所有关联节点前,lua 认为它是灰色的。

节点的颜色被储存在 GCObject 的 CommonHeader 里,放在 marked 域中。为了节约内存,是以位形式存放。marked 是一个单字节量。总共可以储存 8 个标记。而 lua 5.1.4 用到了 7 个标记位。在 lgc.h 的 41 行,有其解释:

/*
** Layout for bit use in `marked' field:
** bit 0 - object is white (type 0)
** bit 1 - object is white (type 1)
** bit 2 - object is black
** bit 3 - for userdata: has been finalized
** bit 3 - for tables: has weak keys
** bit 4 - for tables: has weak values
** bit 5 - object is fixed (should not be collected)
** bit 6 - object is "super" fixed (only the main thread)
*/


#define WHITE0BIT   0
#define WHITE1BIT   1
#define BLACKBIT    2
#define FINALIZEDBIT    3
#define KEYWEAKBIT  3
#define VALUEWEAKBIT    4
#define FIXEDBIT    5
#define SFIXEDBIT   6
#define WHITEBITS   bit2mask(WHITE0BIT, WHITE1BIT)

lua 定义了一组宏来操作这些标记位,代码就不再列出。只需要打开 lgc.h 就能很轻松的理解这些宏的函数。

白色和黑色是分别标记的。当一个对象非白非黑时,就认为它是灰色的。

为什么有两个白色标记位?这是 lua 采用的一个小技巧。在 GC 的标记流程结束,但清理流程尚未作完前。一旦对象间的关系发生变化,比如新增加了一个对象。这些对象的生命期是不可预料的。最安全的方法是把它们标记为不可清除。但我们又不能直接把对象设置为黑色。因为清理过程结束,需要把所有对象设置回白色,方便下次清理。lua 实际上是单遍扫描,处理完一个节点就重置一个节点的颜色的。简单的把新创建出来的对象设置为黑,有可能导致它在 GC 流程结束后,再也没机会变回白色了。

简单的方法就是设置从第三种状态。也就是第 2 种白色。

在 Lua 中,两个白色状态是一个乒乓开关,当前需要删除 0 型白色节点时, 1 型白色节点就是被保护起来的;反之也一样。

当前的白色是 0 型还是 1 型,见 global_State 的 currentwhite 域。otherwhite() 用于乒乓切换。获得当前白色状态,使用定义在 lgcc.h 77 行的宏:

#define luaC_white(g)   cast(lu_byte, (g)->currentwhite & WHITEBITS)

FINALIZEDBIT 用于标记 userdata 。当 userdata 确认不被引用,则设置上这个标记。它不同于颜色标记。因为 userdata 由于 gc 元方法的存在,释放所占内存是需要延迟到 gc 元方法调用之后的。这个标记可以保证元方法不会被反复调用。

KEYWEAKBIT 和 VALUEWEAKBIT 用于标记 table 的 weak 属性,无需多言。

FIXEDBIT 可以保证一个 GCObject 不会在 GC 流程中被清除。为什么要有这种状态?关键在于 lua 本身会用到一个字符串,它们有可能不被任何地方引用,但在每次接触到这个字符串时,又不希望反复生成。那么,这些字符串就会被保护起来,设置上 FIXEDBIT 。

在 lstring.h 的 24 行定义有:

#define luaS_fix(s) l_setbit((s)->tsv.marked, FIXEDBIT)

可以把一个字符串设置为被保护的。

典型的应用场合见 llex.c 的 64 行:

void luaX_init (lua_State *L) {
  int i;
  for (i=0; itsv.reserved = cast_byte(i+1);  /* reserved word */
  }
}

以及 ltm.c 的 30 行:

void luaT_init (lua_State *L) {
  static const char *const luaT_eventname[] = {  /* ORDER TM */
    "__index", "__newindex",
    "__gc", "__mode", "__eq",
    "__add", "__sub", "__mul", "__div", "__mod",
    "__pow", "__unm", "__len", "__lt", "__le",
    "__concat", "__call"
  };
  int i;
  for (i=0; itmname[i] = luaS_new(L, luaT_eventname[i]);
    luaS_fix(G(L)->tmname[i]);  /* never collect these names */
  }
}

以元方法为例,如果我们利用 lua 标准 api 来模拟 metatable 的行为,就不可能写的和原生的 meta 机制高效。因为,当我们取到一个 table 的 key ,想知道它是不是 __index 时,要么我们需要调用 strcmp 做比较;要么使用 lua_pushlstring 先将需要比较的 string 压入 lua_State ,然后再比较。

我们知道 lua 中值一致的 string 共享了一个 string 对象,即 TString 地址是一致的。比较两个 lua string 的代价非常小(只需要比较一个指针),比 C 函数 strcmp 高效。但 lua_pushlstring 却有额外开销。它需要去计算 hash 值,查询 hash 表 (string table) 。

lua 的 GC 算法并不做内存整理,它不会在内存中迁移数据。实际上,如果你能肯定一个 string 不会被清除,那么它的内存地址也是不变的,这样就带来的优化空间。ltm.c 中就是这样做的。

见 lstate.c 的 93 行:

  TString *tmname[TM_N];  /* array with tag-method names */

global_State 中 tmname 域就直接以 TString 指针的方式记录了所有元方法的名字。换作标准的 lua api 来做的话,通常我们需要把这些 string 放到注册表,或环境表中,才能保证其不被 gc 清除,且可以在比较时拿到。lua 自己的实现则利用 FIXEDBIT 做了一步优化。

最后,我们来看看 SFIXEDBIT 。其实它的用途只有一个,就是标记主 mainthread 。也就是一切的起点。我们调用 lua_newstate 返回的那个结构。

为什么需要把这个结构特殊对待?因为即使到 lua_close 的那一刻,这个结构也是不能随意清除的。我们来看看世界末日时,程序都执行了什么?见 lstate.c 的 105 行。

static void close_state (lua_State *L) {
  global_State *g = G(L);
  luaF_close(L, L->stack);  /* close all upvalues for this thread */
  luaC_freeall(L);  /* collect all objects */
  lua_assert(g->rootgc == obj2gco(L));
  lua_assert(g->strt.nuse == 0);
  luaM_freearray(L, G(L)->strt.hash, G(L)->strt.size, TString *);
  luaZ_freebuffer(L, &g->buff);
  freestack(L, L);
  lua_assert(g->totalbytes == sizeof(LG));
  (*g->frealloc)(g->ud, fromstate(L), state_size(LG), 0);
}

这是 lua_close 的最后一个步骤。 luaC_freeall 将释放所有的 GCObject ,但不包括有 SFIXEDBIT 的 mainthread 对象 。见 lgc.c 484 行

void luaC_freeall (lua_State *L) {
  global_State *g = G(L);
  int i;
  g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
  sweepwholelist(L, &g->rootgc);
  for (i = 0; i < g->strt.size; i++)  /* free all string lists */
    sweepwholelist(L, &g->strt.hash[i]);
}

这里 FIXEDBIT 是被无视的,而在此之前,FIXEDBIT 被保护着。见 lstate.c 的 153 行(lua_newstate 函数):

  g->currentwhite = bit2mask(WHITE0BIT, FIXEDBIT);

这么做很容易理解,lua 世界的起源,一切根数据都放在这个对象中,如果被提前清理,后面的代码就会出问题。真正释放这个对象不是在 GC 中,而是最后那句:

  lua_assert(g->totalbytes == sizeof(LG));
  (*g->frealloc)(g->ud, fromstate(L), state_size(LG), 0);

顺带还 assert 了一下,最终,世界上是不是只剩下这个结构。


写累了,待续。

March 27, 2011

Lua GC 的源码剖析 (1)

最近发现在大数据量的 lua 环境中,GC 占据了很多的 CPU 。差不多是整个 CPU 时间的 20% 左右。希望着手改进。这样,必须先对 lua 的 gc 算法极其实现有一个详尽的理解。我之前读过 lua 的源代码,由于 lua 源码版本变迁,这个工作还需要再做一次。这次我重新阅读了 lua 5.1.4 的源代码。从今天起,做一个笔记,详细分析一下 lua 的 gc 是如何实现的。阅读代码整整花掉了我一天时间。但写出来恐怕比阅读时间更长。我会分几天写在 blog 上。


Lua 采用一个简单的标记清除算法的 GC 系统。

在 Lua 中,一共只有 9 种数据类型,分别为 nil 、boolean 、lightuserdata 、number 、string 、 table 、 function 、 userdata 和 thread 。其中,只有 string table function thread 四种在 vm 中以引用方式共享,是需要被 GC 管理回收的对象。其它类型都以值形式存在。

但在 Lua 的实现中,还有两种类型的对象需要被 GC 管理。分别是 proto (可以看作未绑定 upvalue 的函数), upvalue (多个 upvalue 会引用同一个值)。

Lua 是以 union + type 的形式保存值。具体定义可见 lobject.h 的 56 - 75 行:

/*
** Union of all Lua values
*/
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;


/*
** Tagged Values
*/

#define TValuefields    Value value; int tt

typedef struct lua_TValue {
  TValuefields;
} TValue;

我们可以看到,Value 以 union 方式定义。如果是需要被 GC 管理的对象,就以 GCObject 指针形式保存,否则直接存值。在代码的其它部分,并不直接使用 Value 类型,而是 TValue 类型。它比 Value 多了一个类型标识。用 int tt 记录。通常的系统中,每个 TValue 长为 12 字节。btw, 在 The implementation of Lua 5.0 中作者讨论了,在 32 位系统下,为何不用某种 trick 把 type 压缩到前 8 字节内。

所有的 GCObject 都有一个相同的数据头,叫作 CommonHeader ,在 lobject.h 里 43 行 以宏形式定义出来的。使用宏是源于使用上的某种便利。C 语言不支持结构的继承。

#define CommonHeader    GCObject *next; lu_byte tt; lu_byte marked

从这里我们可以看到:所有的 GCObject 都用一个单向链表串了起来。每个对象都以 tt 来识别其类型。marked 域用于标记清除的工作。

标记清除算法是一种简单的 GC 算法。每次 GC 过程,先以若干根节点开始,逐个把直接以及间接和它们相关的节点都做上标记。对于 Lua ,这个过程很容易实现。因为所有 GObject 都在同一个链表上,当标记完成后,遍历这个链表,把未被标记的节点一一删除即可。

Lua 在实际实现时,其实不只用一条链表维系所有 GCObject 。这是因为 string 类型有其特殊性。所有的 string 放在一张大的 hash 表中。它需要保证系统中不会有值相同的 string 被创建两份。顾 string 是被单独管理的,而不串在 GCObject 的链表中。

回头来看看 lua_State 这个类型。这是写 C 和 Lua 交互时用的最多的数据类型。顾名思义,它表示了 lua vm 的某种状态。从实现上来说,更接近 lua 的一个 thread 以及其间包含的相关数据(堆栈、环境等等)。事实上,一个 lua_State 也是一个类型为 thread 的 GCObject 。见其定义于 lstate.h 97 行。

/*
** `per thread' state
*/
struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;  /* first free slot in the stack */
  StkId base;  /* base of current function */
  global_State *l_G;
  CallInfo *ci;  /* call info for current function */
  const Instruction *savedpc;  /* `savedpc' of current function */
  StkId stack_last;  /* last free slot in the stack */
  StkId stack;  /* stack base */
  CallInfo *end_ci;  /* points after end of ci array*/
  CallInfo *base_ci;  /* array of CallInfo's */
  int stacksize;
  int size_ci;  /* size of array `base_ci' */
  unsigned short nCcalls;  /* number of nested C calls */
  unsigned short baseCcalls;  /* nested C calls when resuming coroutine */
  lu_byte hookmask;
  lu_byte allowhook;
  int basehookcount;
  int hookcount;
  lua_Hook hook;
  TValue l_gt;  /* table of globals */
  TValue env;  /* temporary place for environments */
  GCObject *openupval;  /* list of open upvalues in this stack */
  GCObject *gclist;
  struct lua_longjmp *errorJmp;  /* current error recover point */
  ptrdiff_t errfunc;  /* current error handling function (stack index) */
};

一个完整的 lua 虚拟机在运行时,可有多个 lua_State ,即多个 thread 。它们会共享一些数据。这些数据放在 global_State *l_G 域中。其中自然也包括所有 GCobject 的链表。

所有的 string 则以 stringtable 结构保存在 stringtable strt 域。string 的值类型为 TString ,它和其它 GCObject 一样,拥有 CommonHeader 。但需要注意,CommonHeader 中的 next 域却和其它类型的单向链表意义不同。它被挂接在 stringtable 这个 hash 表中。

除 string 外的 GCObject 链表头在 rootgc ( lstate.h 75 行)域中。初始化时,这个域被初始化为主线程。见 lstate.c 170 行,lua_newstate 函数中:

  g->rootgc = obj2gco(L);

每当一个新的 GCobject 被创建出来,都会被挂接到这个链表上,挂接函数有两个,在 lgc.c 687 行的

void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  global_State *g = G(L);
  o->gch.next = g->rootgc;
  g->rootgc = o;
  o->gch.marked = luaC_white(g);
  o->gch.tt = tt;
}

void luaC_linkupval (lua_State *L, UpVal *uv) {
  global_State *g = G(L);
  GCObject *o = obj2gco(uv);
  o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
  g->rootgc = o;
  if (isgray(o)) { 
    if (g->gcstate == GCSpropagate) {
      gray2black(o);  /* closed upvalues need barrier */
      luaC_barrier(L, uv, uv->v);
    }
    else {  /* sweep phase: sweep it (turning it into white) */
      makewhite(g, o);
      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
    }
  }
}

upvalue 在 C 中类型为 UpVal ,也是一个 GCObject 。但这里被特殊处理。为什么会这样?因为 Lua 的 GC 可以分步扫描。别的类型被新创建时,都可以直接作为一个白色节点(新节点)挂接在整个系统中。但 upvalue 却是对已有的对象的间接引用,不是新数据。一旦 GC 在 mark 的过程中( gc 状态为 GCSpropagate ),则需增加屏障 luaC_barrier 。对于这个问题,会在以后详细展开。

lua 还有另一种数据类型创建时的挂接过程也被特殊处理。那就是 userdata 。见 lstring.c 的 95 行:

Udata *luaS_newudata (lua_State *L, size_t s, Table *e) {
  Udata *u;
  if (s > MAX_SIZET - sizeof(Udata))
    luaM_toobig(L);
  u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata)));
  u->uv.marked = luaC_white(G(L));  /* is not finalized */
  u->uv.tt = LUA_TUSERDATA;
  u->uv.len = s;
  u->uv.metatable = NULL;
  u->uv.env = e;
  /* chain it on udata list (after main thread) */
  u->uv.next = G(L)->mainthread->next;
  G(L)->mainthread->next = obj2gco(u);
  return u;
}

这里并没有调用 luaC_link 来挂接新的 Udata 对象,而是直接使用的

  /* chain it on udata list (after main thread) */
  u->uv.next = G(L)->mainthread->next;
  G(L)->mainthread->next = obj2gco(u);

把 u 挂接在 mainthread 之后。

从前面的 mainstate 创建过程可知。mainthread 一定是 GCObject 链表上的最后一个节点(除 Udata 外)。这是因为挂接过程都是向链表头添加的。

这里,就可以把所有 userdata 全部挂接在其它类型之后。这么做的理由是,所有 userdata 都可能有 gc 方法(其它类型则没有)。需要统一去调用这些 gc 方面,则应该有一个途径来单独遍历所有的 userdata 。除此之外,userdata 和其它 GCObject 的处理方式则没有区别,顾依旧挂接在整个 GCObject 链表上而不需要单独再分出一个链表。

处理 userdata 的流程见 lgc.c 的 127 行

/* move `dead' udata that need finalization to list `tmudata' */
size_t luaC_separateudata (lua_State *L, int all) {

这个函数会把所有带有 gc 方法的 userdata 挑出来,放到一个循环链表中。这个循环链表在 global_State 的 tmudata 域。需要调用 gc 方法的这些 userdata 在当个 gc 循环是不能被直接清除的。所以在 mark 环节的最后,会被重新 mark 为不可清除节点。见 lgc.c 的 545 行:

  marktmu(g);  /* mark `preserved' userdata */

这样,可以保证在调用 gc 方法环节,这些对象的内存都没有被释放。但因为这些对象被设置了 finalized 标记。(通过 markfinalized ),下一次 gc 过程不会进入 tmudata 链表,将会被正确清理。

具体 userdata 的清理流程,会在后面展开解释。


今天暂时先到这里。

March 16, 2011

服务器排队系统的一点想法

今天突然想到的,先记下来。

以前考虑过这个问题,写过一篇 blog 。我今天想到,其实可以把排队完全独立出来。和原有系统分离。这样,所有不支持排队的游戏系统,只要简单加上就可以用了,不用对系统结构做大的调整。

想法是这样的:

游戏系统需要估计自己的环境大约可以支持一定时间段多少人可以进入。这个用来估算每个新用户的大致等待时间。

游戏系统采用一个以时间为演算因子的序列 key ,用来做进入的验证。只有持有这个 key 的用户才认为是经过排队的。允许进入。

排队服务器独立安置,当用户直接连接游戏服务器遇到拥堵时,服务器简单记录他的用户名,和等待鉴权的口令,然后让其去排队服务器排队。如果用户再次连接上来而没有经过排队。因为有用户名记录,所以可以在帐户信息里做记录。之后的处理就比较简单了。

用户的这个流程(先尝试游戏服务器,再被转到排队服务器,并不可以二次尝试),这个过程由用户 Client 保证。用户不修改 Client 是不会违规的。游戏服务器只是记录那些用异常手法插队的用户。

在排队服务器,首先向第一次进来的用户发放序号,以及通知大约等待时间。并记录用户的用户名,以及一个等待鉴权的口令。用户则可以离线,由 Client 等待指定时间再上来排队。为何要提交鉴权口令?因为要防止有人恶意冒充插队。当排队服务器检测到用户不守规定不在规定等待时间内重复尝试,则回头鉴定用户是否的确是本人,而后再决定在其帐号里做违规记录。

等待用户快排到了,则可以向排队服务器保持长连接,直到排队服务器发放进入游戏服务器的口令。他就可以离开队伍,前去游戏了。


这样做这个系统,可以让排队系统和游戏足够分离。便于开发。不受游戏服务器的构架变换影响,也更容易部署。

March 14, 2011

方便的分享照片

只是随便想想,还没找到类似软件,希望有人读了后能够受启发做一个 :)

网上做像册的倒是很多,但目前的网络带宽很难满足我的一个需求。即,我这人不喜欢带相机出去旅游。有时候出去玩了,朋友拍了好几 G 的照片,就懒的要了。网上传起来太麻烦。如果真给我寄光盘,估计我也不会有多大兴趣倒腾到计算机里。若是让对方往网上像册上传,估计也难。

其实我的需求很简单,我需要在几百上千张照片里自己挑出需要保留的几张来,然后打包给我。大部分相片不需要冲印出来,所以我也不需要动则几兆的大分辨率照片。缩小到屏幕适合观看的尺寸即可。

挑选照片时,用比较小的缩略图即可。下载时,应该可以定制尺寸。然后全部照片应该被打包下载。

这个服务多用于个人对个人,其实没有太大需求放在公众网上。应该力求网上带宽消耗最小。我想到的理想的方案是由分享方建立一个专门的图片 web 服务器(至于穿防火墙问题,可以增加一个服务器中转)

浏览分拣的时候,应实时提供所有图片的缩略图。选择好需要的图片后,可以按需求缩小尺寸。而后打包。

鉴于我本人程序员出生,对软件的实现也有所要求。我希望 server 端不要因为需要提供各种不同尺寸的图片,以及打包,占用额外的临时磁盘空间。因为这个服务是点对点服务的,服务对象也是一个个人,生成好图片以做 cache 是不必要的。在对方索取的时候在内存生成就够了。

打包的过程应该是自己写,或是用比较底层的打包库的 api 来做,而不是直接调用打包工具,那样会生成过多的中间文件。jpg 或 png 格式本身已经有压缩,所以仅仅是打包而不需要压缩打包了。通用包格式都支持把文件直接连接的,这样其实可以直接流式发送一个包的。这也省略了打包几十上百兆内容的等待时间。(即可以支持一边向包追加数据,一边传输)

好吧,我总说,万事求人不如求己。有空自己做一个罢了。

March 09, 2011

梦幻西游服务器 IO 问题

当多核解决了 CPU 运算能力问题,当 64 bit 系统解决了内存不足问题,IO 问题依然让人困扰。

梦幻西游的服务器从更早的产品延续,已经跑了 10 年了。当初只求快速把项目做出来,用最简单的方法做出来,保证稳定可以用,自然遗留了无数问题。逻辑脚本中充斥随手可见的磁盘操作。

最终,当磁盘操作堆积起来,尤其是阻塞方式请求,并行的过程全部都在磁盘访问处串行起来了。固然整个系统的处理能力并没有下降。但用户的反应时间却会变长。

仔细分析了问题后,我发现,系统利用磁盘其实是有两种不同的用途。

一是备份需求,定期需要把数据持久化下来。因为服务器数量很多,硬件故障率几乎是每周一到两次。所以必须保证定期(不长于半小时)的数据备份。避免硬件故障的意外导致长期回档。

二是数据交换的需求。由于游戏逻辑写的很随意,以快速实现的新功能为主。许多脚本中随便读写文件,提供给逻辑需要来使用。这部分甚至许多是阻塞的。整个游戏逻辑进程串行执行逻辑,任何点的阻塞都会导致服务阻塞。这有很大的历史原因在里面,是不可能彻底修改其结构的。

根据系统调用的监测,我们发现,在定期写盘的高峰期段,逻辑进程中偶尔的读文件操作 API 可能用长达 1 到 2 秒读一个较小的文件。据我理解,导致这个现象的产生多是因为硬盘设备上的操作队列被阻塞。有大量未完成的磁盘 IO 工作在进行,导致系统延迟。

理论上,所以真正写到磁盘上的操作都应该被安排到优先级很低,保证所有的读操作可以以最快的速度完成。这样才能让反映速度变快。即,写盘操作,应该先刷新内存 cache ,然后把真正的写操作推迟到 IO 队列尾上。中间有任何的读操作都应该允许插队完成。由于我们的逻辑进程只有一个线程在跑逻辑,而所有的读文件操作都只发生在这个线程里。(其它工作进程都无读操作)整个系统对磁盘的读操作本身是不会竞争。而写操作则几乎是允许无限推迟的。

可惜,我们很难在 os 的底层控制 IO 操作队列的细节。

今天,想了一个变通的方案来解决这个问题:


为服务器配备两块硬盘,或是配置一个硬盘和一个独立网卡做网盘分区。此目的可以让两种需求的磁盘应用分摊到两个独立设备上去。

另外,在系统启动时,配置一个 ram disk 分区。

至此,我们有三个独立的盘,分别看成 R(ram) ,D(data) ,B(backup)

系统启动前,我们首先用脚本保证 D 和 B 的数据一致,以 B 的数据为主。然后把 B 上面较新文件,复制入 R ,但不将 R 填满,留一定空间。

系统启动后,当遇到 load file 的请求时,首先检查 R 中,看是否有需要的文件,如果有则加载返回。若没有,则从 D 中加载,并同时复制文件到 R

当遇到 save file 的请求时,把文件写入 R ,然后在另一线程中,把写入 R 的文件复制一份到 B 。

系统正常停机后,将所有 R 中的文件写到 D 。 如果系统异常停机,则同步 B 到 D 。(即前面所述的启动前工作)


这个方案之所以可以解决问题,在于,系统工作时 D 是 Read Only 的,而 B 是 write only 的。R 则相当于人为的磁盘 cache ,并保证了数据一致性。

write only 的 B 盘,可以在独立线程和独立设备上慢慢工作,尽可能的不影响 Read Only 的 D 盘上的工作。


这里,假设的是 R 在系统工作中空间无限大。但实际上是比较难做到的。必须考虑 R 这个 cache 满的情况。

这种情况应该如下处理:

在写盘时,如果写入 R 的操作失败(通常为空间满),则需要把数据也写入 D 盘。不过这样,D 就不是 read only 了。不过,在我们的实际运行中,每次的写文件操作都是小文件。可以后台跑一个脚本定期检查 R 的空间状态,一旦空间紧缺,则按时间先后淘汰一部分文件,在此空闲时把文件写到 R 中。这个后台脚本可以缓慢进行,清理 cache 。

我们的服务每天凌晨最为空闲。这个时段做一次清理工作,剩下的时间 R 盘留出支撑 24 小时的容量即可。

Go 语言初学实践(3)

这几天一直在写个小东西,基本也做完了。抽点时间贴段代码继续这个系列。

我写的 http server 在支持断点续传时碰到个小的算法问题。就是我希望用户在完整下载完一次指定文件后,就让这个文件 URL 失效。而如果用户不断的从中间开始分段下载的话,很难从统计下载字节数来判定整个文件是否下载完一次。

我希望把下载完一次的标准定为,文件的每个字节都至少被请求一次。这个问题用线段树来实现最为贴切。当然还会有各种其它方案,就不展开讨论了。

这里的代码有很大的优化余地,但是就具体应用来说,性能方面也足够了。严谨点来说,我在服务器上额外增加了一些判断,防止被恶意攻击。比如如果分段太多(恶意的每间隔一个字节请求一个字节)对于大文件会导致这个数据结构占据过多内存。这时直接掐断服务即可,这里不展开讨论。

今天贴的代码和 C 很接近。没什么特别有特色的地方。不过,Go 的 Slice 的确很好用,还有 Built-in 的函数 copy ,这些都使得 Go 比 C 在处理数据块上更方便和安全。

代码在这里。暂时 Blog 系统没支持 Go ,所以换个位置贴了。


btw, 受周爱民同学邀请,明天我将去支付宝给那里的同学介绍一下 Go 语言。我自己也是初学乍练 。最近多用 Go 写点小程序,也是为了稍微熟悉一点。希望明天不要让人太失望了。

March 02, 2011

Go 语言初学实践(2)

继续昨天的。

现在要实现一个特殊的 map ,支持 push 和 pop 两个操作。看起来是这样的:

type myMap interface {
    push(key string, e interface {}) interface{} 
    pop(key string) interface{}
}

当 push 的时候,如果 map 中 key 已存在,返回原来对应的 value ;若 key 不存在,则创建一个新的 key 把 value 放进去。

而 pop 操作,返回 key 对应的 value ,并把 key/value 对从 map 中删除。

鉴于 Go 程序中通常会使用大量 goroutine ,所以,这个 map 应该是线程安全的。那么用 Go 怎么实现它呢?最简单也就是最传统的方式是使用锁,即 sync.Mutex ,代码如下:


package main

import (
    "fmt"
    "sync"
)

type myMap struct {
    m map[string] interface {}
    sync.Mutex
}

func (m *myMap) push(key string, e interface {}) interface {} {
    m.Lock()
    defer m.Unlock()
    if v,exist := m.m[key] ; exist {
        return v;
    }
    m.m[key] = e
    return nil
}

func (m *myMap) pop(key string) interface {} {
    m.Lock()
    defer m.Unlock()
    if v,exist := m.m[key] ; exist {
        m.m[key] = nil, false
        return v
    }
    return nil
}

func newMap() *myMap {
    return &myMap { m: make(map[string] interface {}) }
}

func main() {
    m := newMap()
    fmt.Println(m.push("hello","world"))
    fmt.Println(m.push("hello","world"))
    fmt.Println(m.pop("hello"))
    fmt.Println(m.pop("hello"))
}

这里,newMap() 方法会返回一个 myMap 指针。其实按之前的定义,返回 muMap interface 也可以,它们在功能上是等价的。 但这里不可以返回 myMap 结构。因为,其中包含有一个其它包里的结构 sync.Mutex ,它是不可以被复制的。Go 里面没有 C++ 中重载赋值运算那些污七八糟的语法糖,所以用指针就好了。反正有 gc 不用担心。


其实,这个东东也可以把所有对 map 的操作放到同一个 goroutine 里完成,就不需要显式的锁了。不过具体到这个需求上,这么实现的意义实在有限。下面列出代码来,只是说可以这么做而已。

package main

import "fmt"

type myMap interface {
    push(key string, e interface {}) interface{} 
    pop(key string) interface{}
}

type myMapPair struct {
    key string
    value interface {}
}

type mapChan struct {
    push_req chan * myMapPair
    push_rep chan interface{}
    pop_req chan string
    pop_rep chan interface{}
}

func (c *mapChan) push(key string, e interface{}) interface{} {
    c.push_req <- & myMapPair {key,e}
    return <- c.push_rep
}

func (c *mapChan) pop(key string) interface {} {
    c.pop_req <- key
    return <- c.pop_rep
}

func newMap() myMap {
    c := mapChan { 
        push_req : make (chan * myMapPair),
        push_rep : make (chan interface{}),
        pop_req : make (chan string),
        pop_rep : make (chan interface{}),
    }
    m := make(map[string] interface {})
    go func() {
        for {
            select {
            case r := <- c.push_req :
                if v , exist := m[r.key] ; exist {
                    c.push_rep <- v
                } else {
                    m[r.key] = r.value
                    c.push_rep <- nil
                }
            case r := <- c.pop_req:
                if v,exist := m[r] ; exist {
                    m[r] = nil, false
                    c.pop_rep <- v
                } else {
                    c.pop_rep <- nil
                }
            }
        }
    } ()
    return &c   
}

func main() {
    m := newMap()
    fmt.Println(m.push("hello","world"))
    fmt.Println(m.push("hello","world"))
    fmt.Println(m.pop("hello"))
    fmt.Println(m.pop("hello"))
}

这里建立了四个 chan ,也就是两对请求/回应通道,让单一的 goroutine 来处理两种对 map 操作的请求。这个处理的 goroutine 可以看成是对其它 goroutine 提供的服务。能这么方便的使用这种模式,在大多数编程语言里并不多见。Erlang 可以算一个。但 Go 的优势在于,允许你使用可能对你更为习惯的命令式编程方式,而不需要转换思维到函数式编程。

March 01, 2011

Go 语言初学实践(1)

今天想到个点子,做一个文件传输的服务。我觉得是个很简单的东西,可以满足自己的需要。写了篇 blog 理了一下思路。不过,如果光这口头说说其实是很偷懒的一件事情。我觉得,大部分网络产品弄个专职的所谓产品经理,光说想要啥自己不动手实现一下(或是不会写程序),是件极其不靠谱的事情。

说些啥都不如自己动手做出来。最近半年我好象老干这种事情,光说不练。最近一个月也没写什么大篇幅的代码,再老是这样,肯定会手生的。管它好不好,动手实现才是王道。正好最近想折腾一下 Go 语言,那么就拿 Go 来写写看吧。

新语言还是不熟的,老要翻资料。不过这也是学习的必经之路。晚上写了几百行程序,还经常出现语法错误,速度很慢,不过慢慢就有状态了。

在这里,就随便贴一小段代码,算是一点点初学实践吧。

这里有一个小需求,希望有一个 Go 函数,每次调用一次,就返回一个由英文大写字母构成的随机字符串。(用来生成一个短网址)那么用 Go 怎么实现好呢?

package main

import "fmt"
import "rand"

var keyGen func() string

func init() {
    keys := make(chan string)
    go func() {
        for {
            var buf [8]byte
            for i:=0 ; i<8 ; i++ {
                buf[i] = byte(rand.Intn(26)) + byte('A')
            }
            keys <- string(buf[:])
        }
    } ()
    keyGen = func() string {
        return <-keys
    }
}

func main() {
    fmt.Println(keyGen())
    fmt.Println(keyGen())
    fmt.Println(keyGen())
}

这是我的一个范例程序,不知道是否符合 Go 语言的惯用法。

这里使用了一个 goroutine ,不断的产生随机串,送去一个 chan 。然后 keyGen 是由 init 函数初始化的 closure ,它每次从 chan 里读到一个生成好的串。

这种实现手法,应该算是 go 程序和 C/C++ 程序最大的不同吧。如果用 C 实现,几乎不会有人采用多线程方案来生成它们,但是 go 里使用 goroutine 却是一件很自然的事情。嗯,我是这么理解的。

分享文件服务

今天一个朋友用 qq 邮箱给我发了个 200+ M 的大文件,我无法提取。这让我意识到,在网络上分享大文件也是个比较大的需求。此类服务很多,历史也很悠久(很多网盘也被用户用来解决此问题)。但好用的并不多。

记得 opera 的新版也提供了分享本机文件的功能,可能是墙的原因,在国内也很难用。

我觉得如果为公众提供一个方便的渠道(又尽量压缩成本)来分享自己机器上的文件,或许会有许多用户的。关键在于便捷,功能纯粹。

最简单的方法是让发送文件方在本机架一个 web server ,然后把文件放到 web server 可以管理的文件服务目录中去。这个方案最好实施,对于懂行的同学来说,windows linux 等都提供有 httpd 服务,设置一下即可。对于不懂的同学,提供一个小型软件安装一下也很容易。而文件接收方仅需要用浏览器下载文件即可。

但是这个方案有很大的缺陷。大多数人机器都在防火墙背后,也没有权限可以在网关上设置 NAT 。很大可能是无法使用的。另外,架设 server 隐藏有一定安全上的风险。

而我的想法是这样的:

制作一款简单的小软件鼓励用户安装。(类似 DropBox 那样,只有安装了 client 才能享受服务)

这个软件负责分享本机上的文件,软件设置可以简化到只关联一个文件夹即可。它本身只提供一个 localhost 的 web 服务,方便用户监测自己分享出去的文件列表,以及分享进度等。

在公众网上提供一个 web 服务,其实是一个 proxy 服务,把文件请求转发到每个用户本机的 client 上。注:这里公众网和每个用户机的沟通并不通过 http 协议。而走一个 tcp 长连接。

用户想分享文件的时候,通过本机的服务,获得分享文件夹内指定文件的一个 URI 。这个 URI 其实是由公众服务生成的,类似短网址服务那样的。

文件分享方可以把这个 URI 通过其它手段(比如 IM)发送给接收者。接收者可以用浏览器直接下载。

这个下载过程,公众网上的 web server 只是起到 proxy 作用,一般不 cache 整个文件。仅仅把文件的一段段从用户 client 那里拉过来转发。架设这个公众网上的服务只有带宽成本,无储存成本。

由于用户 client 是定制的软件,可以知道对方下载的进度等等,用起来就和 IM 上传送文件无差别。

这个方案对文件接收者是无额外代价的。

如果服务想收费,可以用用户付费获得更大的带宽或是允许广播文件(允许多个接收方同时下载,或开放多线程下载,甚至是 cache 文件服务即提供储存)

用户 client 这边,如果设计良好,可以非常方便的实现多平台(甚至智能手机平台,方便分享照片等)。甚至 client 也可以开源,让用户用的放心,并鼓励第三方应用。


在构思的时候,我也想过在 client 中提供 p2p 功能,实现起来也很容易。但后来觉得这个功能虽有一定价值,但会破坏整个产品的纯粹性。