重归混沌 | | 重归混沌的BLOG

历史之2018

2018年已经成为历史，当我想总结一下过去一年的所得时，却发现什么都想不起来。借着过去一年的blog和github，总算可以粗略回溯一下历史。

去年的今天，我定下三个目标：

1. 阅读lua源码，并实现虚拟机
2. 阅读《计算机程序设计艺术》
3. 实现一个软件光栅器

到今天为止，lua源码只完整阅读了GC部分，计算机程序设计艺术几乎等于没看，只有软件光栅器做了个七七八八（但其实连光照都没做完)。

下面来说一说流水帐。

过完农历年后，我先挑了“软件光栅器”来做。

一方面是因为《计算机程序艺术》和阅读lua源码都需要比较大的时间片，而软件光栅器相对来讲可能更像是快程课。同时在三个目标中，我的渲染知识最弱，对于一直致力于全栈的我来讲，肯定也要先补齐短板。

从另一方面来讲，前两个更属于内功，软件光栅器更偏向招式，容易被人看出来，早点学可以防身。

在此过程中，主要的叁考书籍就是《3D游戏编程大师技巧》，这本书介绍了如何利用《3D数学基础》中的知识，将图形渲染出来。

但是这本书实在太老了，老到作者为了程序可以流畅跑起来，做了很多优化，比如这个坑其实最后的修正版，就是一个lerp而已。但是作者没有提示出这一关键，导致我最开始渲染出的图形一直有问题。甚至都搞了半个多月。

之后断断续续踩了几个坑，不带光照版的光栅器总算将就能看了。

然而，我这个人有个大毛病，一直想克服，但是至今没有成功。当我认为我会了，我就懒得进行下一步了。

刚好这时lua5.4 work1发布了。增加了分代GC支持，我一看这是个高级特性了，得跟上潮流，下载代码一看，其实lua5.4的分代GC是在5.3的增量三色GC算法上改进而来的，加上年初定的目标，就咬咬牙花了大概一周的时间，把lua5.3的GC源码大致看了一遍。

但是由于每次我看lua源码时，闭包上值的实现，总是让我有意无意的略过去了，因此其实算不上真正把lua GC看懂，应该说是基本看了个七七八八。

刚看完luaGC没两天，差不多五月份左右，我们项目中一个战斗系统刚好也算正式定下怎么做了。

这个系统有一个极特殊的地方，就是同屏人数可能上百，这就意味在数据同步量会非常大，那么如何尽可能的降低数据同步量，成了整个系统设计的重中之重。

这时我开始困难的回忆我所知道的所有知识，比如帧同步，状态同步。每一种都有自己的适应场景，但是都不太适合我们现在这种游戏模式。当然这里所说的帧同步，其实已经退化成行为同步了。

最终，我终于打破了自己的思维局限。

谁说一定只能用一种模式，以我们游戏的模式，其实是可以两者之间进行折中，每走到一片土地后，我们可以先用状态模式拉一下所有状态，然后只要视野不变，就采用行为同步方式进行同步。这样需要广播的数据量大大减少。

其实现在想一想，我以前做过的FPS游戏，中途加入游戏，其实跟我们切视野的思路差不多，这再次印证了太阳底下没有新鲜事。

解决完这个问题，我的周末终于又是我的了。

这时我自认能写软件光栅器了，就想去解决一个我心中的痛投影贴花，这个效果我在做FPS时，别人给我说过之后，我就开始研究了。然而一都没有办法去实现，即使找到文章都看不懂为何能达到这样的效果。幸运的是这次竟然真的看懂了。

解决了，又不知道要干啥了，刚好看到想到最近微服务这么火，那就研究微服务吧。即然都说docker好用，那就把我VPS上的进程全部Docker化吧。

在docker化时，发现了rssreader的一些bug。

在修改bug过程中，发现了一个奇怪的现象，在某些情况下杀死silly会进入死锁状态。其实之前也出现过几次，只是当时没有在意。这次打算认真查一下到底是什么原因。

最后发现，其实是因为lua中的__gc函数使用不当，造成了GC竞争, 这种情况只会以程序退出进行清理资源时才会出现。

具体情况是，由于GC竞争，导致在不同的GC函数中double free了同一个指针，而在进程退出时，jemalloc由于这个double free死锁了。

在做上面这些事的同时，我还有一条支线任务，就是阅读《计算机程序设计艺术》，由于这本书很多地方都会计算指令级开销，让我有种过早优化的倾向。

所以周末翻了翻软件工程神作《Unix编程艺术》，没想到这次解决了一个我当时工作中碰到了一个很棘手的问题。

这时，已经八月份了，时间已经溜走了将近三分之二了。也就是从八月份起，我需要处理很多生活中的问题。

因此后三分之一的时间，我其实并没有太多的精力去探索了。在这期间只是把以前的想法落实到代码上去。

比如我做了一个客户端差量更新工具，这个工具其实我早在三年前，就有打算做了，只是当时一来没需求，二来兴趣也不是很大。这次之所以动手做，还是因为我对他们引入的第三方框架的更新工具，很不满意。

再比如，我封装了一个lua框架forUnity,同样是因为我对现有的框架很不满意。

总结到现在，我发现一个规律，不管有没有生活上的其他事，我每年在10月分之后，基本代码和灵感都呈现断崖式下跌。

是时候定一下，2019年的目标了：

1. 断续阅读lua源码
2. 继续阅读《计算机程序设计艺术》
3. 为软件光栅器加上实时光照和阴影
4. 转向Unreal阵营，这次一定要先下手为强
5. 如果有精力的化，尽量涉及一下深度学习，以打码工具做为项目驱动

再见！ 2018。

DC3算法

最近做了一个差量更新工具，实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后，根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是，为了尽可能的减少网络传输，patch文件需要尽可能的小，并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑，我重新设计了一个二进制patch格式，整个patch文件中有两种Action（分别是COPY， INSERT)，大致数据结构如下：

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据（这代表这段数据在文件a中找不到)。

之所以不需要新文件新文件的位置，是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时，我遇到了一个问题.

即，如何快速找到，同时存在于文件a和文件b中的最长子串。算法导论上的LCS（公共子序列）算法并不是很适合我，因为COPY只是去借数据，并不在乎这块数据在哪个位置。

最终发现，有序后缀数组更符合我的需求，空间复杂度极底，并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3，我搞了将近2周才总算搞明白。

整个算法一共就分4步，原始数据在buf中，长度为N，（这里仅粗略描述)：

1. 将(i % 3 != 0， i >= 0 and i < N)的值取出来放到一个数组SA12中.

2. 对S12进行排序, S12中的每个值n都代表一个三元组（buf[n],buf[n+1],buf[n+2]），排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

3. 如果任意两个三元组都不相等，说明仅凭前三个字母就可以对后缀确定顺序，则直接执行步骤4。否则，对s12中的数据递归执行DC3。

4. 根据s12来生成数组SA12，然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序，与SA12进行有序合并，成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的，如快排，二分查找，甚至红黑树那么直观。他神奇到，我完全不知道这是在做什么，后缀数组已经排完序了。

在看这个算法时，在第2步我有几个很大的疑惑。

一是有个很神奇的操作，在生成s12的时，如果n % 3 ==1, 要把rank值放左边，n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的（没有空洞x, buf[x]会比buf数组中所有值都要小)，就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字，2行不行。

搞明白之后发现，整个算法的核心思想就是”收敛”, 运用递归的思想不断的收敛，直到比如结果为止。举个例子：

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】]，

将n%3==1的放左边，n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x，而buf[x]一定比buf[0~n]中的值都要小，所以就不用插入分隔符了，后面会看到分隔符的作用。

从上面列表可以看出’1,2,3’ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序（不满足步骤3)，因为要接着递归执行，先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到，之所以要把i%3==1的放左边，i%3==2放右边，其实是为再次递归DC3做准备。第二次递归DC3，实质上是取所有后缀的前9个前缀来进行排序，如果还有相同的，则再次递归采用前27个前缀进行排序，直到排出顺序为止。

为了利用上次递归的结果，上面数组会被转化成转换之后（【3】【3】【2】【1】【5】【5】，【4】）再递归传入DC3。

而之所以要插分隔符，其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2，3，4’参与排序，毕间7，8，9，10已经是从位置7开始后缀子串的全部内容了，如果2，3，4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字，其实跟步骤4是有关系的。

在步骤4进行有序合并时，i%3==1时，会将3元组扩展成4元组，i%3==2时，将3元组扩展成5元组，之后再比较。

当i%3==1时，如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了，所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较，由于s12[1]中的值各不相同，因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3’, ‘2,3,4,5’，可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组，‘0,1,2,3,4′,’2,3,4,5,6’，这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里，为什么不用2就很明显了，因为在最后一步合并时2不满足重用上一步结果的要求。

总的来说这是一个很神奇的算法，有动态规划的影子，各个步骤又配合的天衣无缝。

移动平台native代码遭遇的坑

最近客户端终于开始运行在移动平台上了（当然，快开发完才开始在移动平台尝试运行，本身就是一件很错误的顺序，然而这并不是我所能控制的），之前在PC平台上完全没问题的代码，开始出现一些诡异的问题。

为了保证客户端和服务器使用绝对相同的逻辑执行流程，我们采用C++来开发一部分native代码同时供客户端和服务端来使用。在迁移到移动平台时，这些native库在IOS和Android平台上出现了不同程度的水土不服。

首次在移动平台就发生了crash,并且只有Android平台会crash, 而IOS可以正常进入游戏。

最后定位到，当执行类似下面的代码时安卓平台就会发生crash。

int a = 3;
char buf[64];
char *p = buf;
*p = 0;
*(int *)(p + 1) = a;

在编译安卓平台native动态库时，为了尽可能的保证兼容性，我们采用了armeabi-v7a来编译native动态库，据ARMv7开发文档显示，在ARMv7架构下，uint32_t *需要4字节对齐，而uint16_t *则需要2字节对齐，只有uint8_t *才不需要对齐约定。

而苹果自iphone5s发行时，就采用了基于ARMv8-A架构的的Apple-A7。根据ARMv8-A开发文档显示，在ARMv8-A架构下，所有地址访问都不再需要指针对齐要求。换句话说在IOS的64位平台上，上面代码是完全正确的。

当然，木桶原理，为了保证代码在所有平台上都能正常运行，需要做出如下修改：

//此段代码同时可以无视机器大小端，而强制a在内存中的布局为大端还是小端，此种写法为小端
- *(int *)(p + 1) = a;
+ p[1] = a & 0xff; 
+ p[2] = (a >> 8) & 0xff; 
+ p[3] = (a >> 16) & 0xff; 
+ p[4] = (a >> 24) & 0xff;

如果要保持与机器大小端相同可采用如下写法:

- *(int *)(p + 1) = a;
//由于a只有四个字节，此处可以手动展开memcpy以优化函数调用和for循环
+ memcpy(p, &a, sizeof(a));

看到Android这么热闹，IOS也有点不平衡，在调用某个native函数时，报出了`To marshal a managed method, please add an attribute named ‘MonoPInvokeCallback’ to the method definition.`错误。

但是并不是所有native函数都会有这个问题。经过比较发现，这个函数在设计时，为了方便方便Unity可以接管native内部的log, 多增加了一个参数，用来将C#中log函数传入。直接将参数改为NULL时，果然问题解决了。但是很奇怪的是，在Windows下并不会有此问题。

最终在MonoTouch的官方文档中找到了答案。

在微软向ECMA提出的CLI（通用语言基础架构）中，并没有定义标签`MonoPInvokeCallback`。这也正印证了，我们在PC平台上从来没有出现过此问题。

如果在编译成移动平台时’Scripting backend’选项选用了`IL2CPP`，就需要使用AOT编译器来进行编译。

而进行AOT编译时，MONO需要知道哪些静态函数可能会被native代码调用，以便对C#函数进行额外处理（ps. 理论上，一个函数是否需要会被传入native函数中，是可以在编译时推导出来的，不知道MONO为什么没有做这件事)。

从CPU层面谈谈优化

大多数时间，大家都在从设计和算法上优化效率（这类优化往往效果比较明显，比如一个二分查找可以轻易将时间复杂度降低为lg(n))。但是在实现上，却很少有人注重实现效率，而理由是反正每年都会有更高频率的CPU出现，我何必花那个心思呢（Java程序员尤其擅长使用这个理由@_@)。

我个人不是完全同意上面的说辞，在不影响代码的可读性和花费不高的代价下，我习惯性的会写最我当前所知道的性能最高的写法。

在很早以前，我一度只有在编写汇编时才可以计算出汇编条数。随着代码量的增加，我慢慢意识到，这种想法是错误的。即使在写C语言时，其实生成的汇编也时有迹可寻的。

程序中所有代码一般都分为三个步骤（有些汇编指令会合并其中的某几步)。

1. 从内存读到寄存器（有可能直接从cache读）
2. 操作寄存器进行运算,并将结果保存在寄存器
3. 将结果写入内存（有可能会同时写入cache)

一般步骤1和3是对称的，只要步骤1的效率高，步骤3会同样高效。因此下面只分析步骤1和步骤2。

先来定义几个数据结构：

struct foo {
    int b;
    int a;
};
struct bar {
    struct foo f;
    struct foo *fp; //assume fp = &f
};

影响访问内存效率的第一个因素，汇编条数：

int access1(struct bar *b)
{
    return b->f.a;
}
int access2(struct bar *b)
{
    return b->fp->a;
}

在上面代码中access1比access2快一倍，这是因为结构体嵌套，不论嵌套多少层，其子成员偏移量都是常量。因此`b->f.a` 等价于`int a = *(int*)((unsigned char *)b + 4)`，所以这句代码翻译成汇编就是`movl 4(%rdi),%eax`(这里%rdi就是b的值)。

而access2就必须要经过两次内存访问, `struct foo *p = ((unsigned char *)b + 8); int a = *(int)((unsigned char *)p + 4)`。翻译成汇编就成了`movq 8(%rdi),%rax, movl 4(%rax), %eax`(这里%rdi同样是参数b）。

因此当你写出类似下面代码时请慎重。

b->fp->a = xx;
b->fp->b = xx;
b->fp->c = xx;
b->fp->d = xx;
b->fp->e = xx;

反观下面的代码，除了代码前缀长一点，却并不会产生什么问题。

b->fp.a = xx;
b->fp.b = xx;
b->fp.c = xx;
b->fp.d = xx;
b->fp.e = xx;

影响访问内存效率的第二个因素, 访问内存的频率。也许很多人都写过类似下面的代码:

void test(struct bar *b)
{
    int i;
    for (i = 0; i < b->foo.a; i++)
        do_something()
}

编译器在执行优化时，一般不会使用寄存器缓存指针指向的内容和函数调用的返回结果（这个不同的编译器实现可能不太一样，至少我使用的GCC在O2的情况下并不会做此优化），我称之为指针不可优化原则。因为从理论上来讲内存是整个进程共享的，而进程中到底会有多少个线程编译器并不知晓，它并不知道在执行for期间，b->foo.a是否会被其他线程修改。函数调用也是同理。

这也意味着每执行一次do_somthing之后都会先去访问b->foo.a的值，再来比较。这会增加访存次数, 即使有cache的存在，也没有直接访问寄存器来的快。因此这时我们可以向编译器做个暗示(增加一个局部变量，告诉编译器，我们需要的这个值，在for循环期间不会变化)，比如像下面这样。

void test(struct bar *b)
{
    int i, n = b->foo.a;
    for (i = 0; i < n; i++)
        do_something()
}

影响访问内存效率的第三个因素, CPU CACHE。

数据结构的设计与CPU CACHE的命中率其实是息息相关。

由于Cache要远小于内存，因此一般会采用某种映射算法进行映射（是的，上学时“计算机组成原理”上讲的都是真的）。

然而不论CPU采用何种算法，Cache line的概念是不变的。即在Cache miss时，是按Cache line的模式来加载的.

比如在X86架构上Cache line一般为64字节，我们在访问内存地址0x100时，CPU会自动将0x100 ~ 0x140的内存全部载入Cache。

假如我们需要频繁在一个链表中，查出某几个结点进行数据修改，下面的数据结构就是低效的。

struct node {
    struct node *next;
    int select;
    char buffer[128];
};
void test(struct node *head, int select)
{
    struct node *h;
    for (h = head; h != NULL; h = h->next) {
        if (h->select == select) {
            cook(h->buffer, sizeof(h->buffer));
            break;
        }
    }
}

很显然，从上面的算法来看，在for循环时我们现关心node.next 和 node.select字段，node.buffer只有在最后一步时才会访问，而上面的代码每访问一次h->select的值，都会使Cache line充满了node.buffer的值，而这个值我们是不需要的。

因此我们需要优化struct node的内存布局，以使链表中所有的node.next, node.select 尽可能的排布在一起，以便可以充分使用Cache line的预加载功能。

最后，再简单看一下运算过程中的两个优化（并不是只有两个，而是我只会这几个:D)

一个是比较功能，在所有比较中，与0比较是最快的，因为大部分CPU的指令都会影响ZF标准位。比如下面代码:

void test1(struct foo *f)
{
	if ((f->a & 0xf) == 0)
		do_something();
}
int test2(struct foo *f)
{
	if ((f->a & 0xf) == 1)
		do_something();
}

test1函数比test2函数快3倍，因为test1函数可以直接用test指令然后判断ZF标准位，而test2需要先将f->a取出来，然后做and, 最后做compare操作。也许直接上汇编会更能说明问题。

//test1
testb	$15, 4(%rdi)
je	LBB3_2
//test2
movl	4(%rdi), %eax
andl	$15, %eax
cmpl	$1, %eax
jne	LBB4_1

再一个就是switch功能。

在写switch语句时，如果case的值是连续的, 则编译器会采用跳转表的形式来直接jmp, 时间复杂度为O(1)。

如果值是不连续的，编译器默认会采用二分查找法来进行，时间复杂度为O(lgn)。因此如果有可能，应该尽可能将case的值定义为连续。

GC竞争问题

在阅读Lua GC源码中，我们就提到过一个细节，所有带有__gc函数的对象，在第一轮GC循环中只会执行__gc函数，直到第二轮GC才真正清除。

一直没有找到必须这样做的场景，直到最近我发生了一例GC竞争的bug之后，才恍然大悟。回过头想想，其实在我之前翻译Barry Hayes大神的一篇论文里也早都提到过，只不过当时例子是释放OS资源，而场景也太过抽象，才没有引起我的注意。下面来看一个MWE。

我已经尽可能的精简代码，然而还是需要170+LOC。

在这个例子里，实现了一个链表管理，所有的link和node结构均交由Lua GC来自动管理内存。

由于Lua GC不能分析C结构之间的引用关系，因此所有的node(userdata)必须通过一个Table来保持引用，以防GC误回收。这也是为什么在luaopen_link函数中，我们为所有函数绑定了一个相同的UpVal(Table)。

下面来分析为什么会有竞争的发生。

首先这个UpVal是全局的，也就是会与luaVM同生共死。所以`UpVal中node对象的生命周期` >= `link的生命周期`。

因此竞争问题只会出现在UpVal的生命周期与link的生命周期一同结束时。假设UpVal和link的生命周期都在GC 循环C1中结束。没有机制能保证UpVal先于或后于link死亡，因此node对象的__gc和link.free在这一周期是竞争执行的。这就是RACE1和RACE2都需要将buff置为NULL的原因，只要有一方不置为NULL另一方就有可能出现double free。

之所以置NULL不会有memory corruption问题. 是因为在Lua GC实现中，所有带__gc函数的对象，在当前GC循环死亡后并不会立即释放内存，而是会等到下一轮GC循环才会真正释放。换句话说只要在本轮GC循环中，不管什么时间访问操作node指针都是有效的。

反过来讲，由于在释放过程中可能存在竞争或释放过程中循环依赖的情况。GC模块要保证在执行__gc函数过程中，所有需要的数据都是有效的，就必须要延迟一个GC循环来回收内存。

ps.其实上面的竞争问题可以通过其他手段解决，比如为link设置一个__gc函数来释放buff, 移除掉node对象中__gc函数的释放buff行为，但是不管怎么样竞争场景确实存在，比如两个user data相互引用，并被同一个Table持有等。

通过Mesh投影来实现贴花系统

在做FPS之类的游戏中，如果枪打到了墙角，并不能简单放置一来弹孔面片了事。而是要像一张贴纸一样，完全与墙角贴合。这时就需要去实现一个贴花系统来达到这种效果。

贴花系统有几种不同的实现方式，但这里仅考虑通过Mesh投影来实现贴花系统的实现原理。

这种方式的本质是，找到视野中贴花资源会影响的Mesh, 并创建一个同样大小以贴花资源为纹理的Mesh覆盖上去，从而达到贴花的目的。主要分下面两步来实现。

1. 先找到会受影响的物体，比如将弹孔贴在两面墙的夹角，那么受影响的物体就是两面墙。

怎么找到这两面墙不同的需求可能实现方式也不一样，在场景编辑器中通过贴花来实现静态点缀效果，可以通过创建贴花资源的AABB盒来实现。如果是运行时动态创建弹孔也可以通过四次射线检测来达到，总之方式有很多。

2. 先创建一个半径为0.5单位的裁切立方体，在裁切坐标系中，贴花资源就被放在y=0平面中，贴花资源的中心就是裁切坐标系的(0, 0, 0)点。

需要说明的时这一步实际上并没有代码操作，只是一个数学抽象。我们的目的是要将所有受影响的三角形投影到y=0平面上，以便可以正确的采样贴花纹理。

3. 将受影响物体Mesh的所有三角形均转换到裁切立方体的坐标系之下对立方体的8个平面进行裁切。

在进行裁切之前，有一种情况需要处理，因为三角形是有朝向的，这个朝向是通过面法线来确定的（Unity中三角形的法线为Cross(v2-v1, v3-v1))，在正常的渲染流程中法线不能射入眼睛时，是不会被渲染的。在Unity中视锥体坐标系中，Vector3(0, 0, -1)是前向，因此眼睛的位置在Vector3(0, 0, 1)处。

在这个裁切立方体同样如此，不可能将纹理投影到一个三角形平面的背面，所以需要先先判断三角形的法线与Vector3(0, 0, 1)的夹角是否小于90度，只有小于90度才可能会被投影，才需要被裁切。

裁切时会出现，三角形完全在立方体外，三角形完全在立方体内，三角形一部分在立方体外一部分在立方体内。前两种情况很好处理，但是第三种情况有可能会将一个三解形切成2个，因此需要格外注意。具体的裁切算法视锥体裁切算法一致，这里就不赘述。

4. 纹理采样，在创建三角形时，我们需要为每个一顶点指定一个uv坐标。前面已经说过了，我们的实现方式是将裁切后合法的三角形投影到裁切坐标系的y=0平面上, 投影之后的坐标为(x, 0, z). 因此uv可直接执行u = Lerp(0.0f, 1.0f, x + 0.5f), v = Lerp(0.0f, 1.0f, z + 0.5f).这里之所以加0.5f修正是因为立方体中心坐标为(0, 0, 0),这也意味着x,y,z的最小值均为-0.5f.

说了这么多附上源码一篇。需要说明的是，这个源码并不是我实现的，是我从网上找来之后修改的，毕竟我对Unity3d没有那么熟悉。

ps.单位相同的裁切立方体如何适应不同尺寸的贴花资源？在Unity中可以通过设置Scale拉伸坐标轴来实现，所以说3D数学真奇妙。

pps.在实现过程中发现，新创建的Mesh不能紧贴被覆盖的Mesh, 因为在相同的深度情况下，新创建的Mesh并不能保证一定在被覆盖的Mesh之后渲染，这会概率性出现新创建的Mesh与被覆盖的Mesh相互覆盖的情况。因为在创建完Mesh之后，需要根据平面法线上浮一点，以保证Z-Buffer正常工作。

谈谈我对数据同步的理解

We性质b和网游最大的不同也许就在于数据同步。

Web的工作流程（这里不包括页游）虽然也有很多变化，但是一般都大致分为三步。

1. 在浏览器输入网址，浏览器通过HTTP协议请求服务器加载数据，服务器在收到HTTP请求之后，从数据库加载相应的数据（有可能是HTML,JS等一些用于浏览器渲染的数据）并返回给客户端。这一步我称之为查询。

2. 浏览器收到服务器返回的数据之后，将数据渲染并呈现给用户。这一步我称之为渲染。

3. 用户在看到浏览器呈现的内容之后，根据需要去执行不同的操作，这些操作为导致浏览器将一些数据发往服务器进行处理，这一步我称为提交。

大部分Web逻辑除了在这三步之间循环之外，还有一个很重要的特点，那就是几乎很少与旁人进行实时交互。比如你在某论坛改了名字，也需要对方手动刷新才能看到。当然也有可以实现显示的，但那是极少功能才有的待遇（并且一般都是通过Hang住HTTP请求来实现的），这里不考虑这种情况。

因此，市面上对Web的高可伸缩性的研究，大都维绕着数据库来做。因为HTTP的数据同步量真的没有什么好研究的，这种模式几乎已经把数据同步量压缩到最低了。只有用户操作才会加载数据，这是多么节省的一种数据同步方式啊。

网游本身就是一个强交互的模式，玩家A做了一个操作，所有应该能看到玩家A的其他玩家都必须能看到玩家A做了什么操作（只是理论上，也许由于某种技能别人看不到）。

这样数据的同步量就会非常大，而且这种数据量，会随着同时在线的玩家的数量成指数性增加。

于是人们研究了各种减少数据同步量的算法，比如AOI、帧同步等。

这里我先私自把游戏分为开房间和大地图两种模式。

开房间模式的游戏,一般同一个房间的人数不会过多。所以最简单的做法就是，直接同步位置和状态。

每个人客户端移动过程中定时（比如10ms)广播坐标给房间内所有玩家，然后客户端根据收到的新坐标，做插值补偿。这又被称作影子跟随算法，即客户端实际表现的位置永远落后于其真正的位置。

如果客户端放了一个技能，就把这个技能效果广播给房间内的所有玩家。

但是这里会存在一个问题，如果这是一个延时类技能，比如几秒后生效，那么服务器在收到释放技能时就需要广播一次，当技能真正生效时，还需要再次广播一次。如果是一个每隔几秒就生效一次的buff就会更麻烦，每次buff生效，都要进行消息广播。数据量会远超于玩家的操作频次。

即然大部分数据量都是状态同步引起的，那么就把所有状态全部交给客户端自己运算，这就是帧同步的本质。客户端拥有整个游戏的全部运算逻辑，将整个游戏进程人为划分为逻辑帧，每个逻辑帧玩家上报自己的操作，由服务器进行房间内广播。客户端收到操作为自己还原各种状态。如果房间内有N个人，每个人操作M次，数据同步量只有M*N条消息，远低于之前的状态同步的数据量。这对于流量并不富裕的手机来说尤其是个好消息。

如何保证所有客户端逻辑和表现都一致，除了要做正确一逻辑帧操作还原外，还有一点很重要，就是复原随机逻辑（战斗中经常会有各种概率判断)。这一点可以通过伪随机序列来保证。

下面来看看大地图模式（这里的大地图模式，是指所有玩家在一张地图上，并且战斗过程中不切换场景）。

在大地图模式，所有玩家都在一张地图上行动，因此玩家数量与房间内的数量根本不是一个数据级（虽然有可能为了增加同时在线人数，会将地图进行分块处理。但即使如此，单块地图上的玩家也远大于房间内玩家数量)。

这也就意味着将数据（操作数据或状态数据）广播给地图上的所有玩家，是不现实的。所以必须要采用AOI算法，来选取需要收到这些数据的玩家。然后将这些数据组播给选取到的玩家。

在使用了AOI算法之后，一般来讲人数的量级与上面开房间模式需要同步的人数量级就差不多了。

那么是否使用了AOI之后，同样可以采用帧同步算法优化掉状态同步呢。

答案显然是否定的，上面也提到，所有的战斗系统一般都会有概率的存在，而一张大地图上必须也只可能有一个伪随机序列（因为玩家之间的视野是交错的）。这也就意味着所有的客户端不可能事先知道这个伪随机序列走到哪一步了（每场战斗都会使伪随机序列前进一步，如果要所有客户端都实时知道当前伪随机序列的进度，就必须在每一场战斗之后，将当前随机数广播给地图内所有玩家，这显然是不是现实的)。

从上面的分析可以得出一个结论，制约大地图模式使用帧同步算法的惟一因素，就是无法复原随机逻辑。那么如果我们游戏地图内没有随机因素（暂且不论是不是有可能），是否可以在AOI的基础上再使用帧同步算法的变种呢。

我们来分析几种情况来看看是否可行，这里需要强调一点，我们假设整个通信采用TCP（TCP具有FIFO性质）传输，服务器采用的是单线程模式。

1. 玩家B先看到了玩家A，然后玩家A被打了掉了5滴血，最终玩家A还有75滴血。

玩家B首先在视野内看到了玩家A，这时会同步到玩家A的血量为80.

然后B收到了玩家A被打的操作（这个操作固定伤5滴血）,玩家B将80减去5得出玩家A还有75滴血的结果。显然这是正确的。

虽然可能buff之类带时间的逻辑不好控制，但是相信经过合理的设计，逻辑上应该不会有太大问题。

2. 玩家B还没收看到玩家A，然后玩家A被打掉了5滴血。

玩家B收到玩家A被打的操作消息后，发现自己视野内还没有加载出玩家A的数据（注意是从服务器加载到的数据，不是客户端还没有把模型之类的数据加载完), 于是将消息抛弃。

之后，玩家B收到的从服务器请求来的数据，A的血量为75。显然这也没有错。

所以在没有伪随机存在的情况下，完全可以使用帧同步算法的理论，进一步优化状态同步。

很巧我们最近开发的游戏，大地图上的表现确实不需要伪随机序列。

这次分析再次告诉我，一定要认清算法的局限在哪里，这样才能根据实际情况灵活组合运用。别人不能用，并不是你就一定不能用。

又一个类型提升引起的Bug

在好几年前我已经中招过一次了，没想到最近一不留神又中招一次。不过这次的花样和上次又不太一样。

Bug的起因是，我需要一个函数，根据指定速度（可能不是整数)和距离来获取到达目的点的时间，于是就有了下面这样一段代码。

//#define TIME time(NULL)
#define TIME 1526796356
time_t foo(int distance, float speed)
{
        return TIME + distance / speed;
}
int main()
{
        printf("%ld\n", foo(30, 3.0f));
}

咋一看这代码几乎没毛病，严格遵循牛顿大神给出来的公式来算。

然而他的输出却是`1526796416`这样一个值。在思考了将近20分钟之后，我才恍然大悟。

根据《The C Programming Language》第二版中的A6.5节算术转换一节的内容

`
First, if either operand is long double, the other is converted to long double. Otherwise, if either operand is double, the other is converted to double.

Otherwise, if either operand is float, the other is converted to float.

Otherwise, the integral promotions are performed on’ both operands; then, if either operand is unsigned long int, the other is converted to unsigned long int

Otherwise, if one operand is long int and the other is unsigned int, the effect depends on whether a long int can represent all values of an unsigned int; if so, the unsigned int operand is converted to long int; if not, both are converted to unsigned long int

Otherwise, if one operand is long int, the other is converted to long int

Otherwise, if either operand is unsigned int, the other is converted to unsigned int

Otherwise, both operands have type int

There are two changes here. First, arithmetic on float operands may be done in single precision, rather than double; the first edition specified that all floating arithmetic was double precision. Second, shorter unsigned types, when combined with a larger signed type, do not propagate the unsigned property to the result type; in the first edition, the unsigned always dominated. The new rules are slightly more complicated, but reduce somewhat the surprises that may occur when an unsigned quantity meets signed. Unexpected results may still occur when an unsigned expression is compared to a signed expression of the same size.
`

代码`return TIME + distance / speed`在实际执行时会被转换成`return (float)TIME + (float)distance / speed`来执行。

之所以思考了那么久才发现问题，是因为在写代码时就知道编译器会进行类型提升。而从理论上来讲，编译器在进行数学运算时，总是会向最大值更大的类型进行转换，以保证隐式转换的正确性。所以首先就把这种错误是类型提升造成的可能给排除了。

这种理论本身也是正确的，因为float的最大值为`340282346638528859811704183484516925440`，可是我忽略了一个很重要的事实，就是float即然叫单精度，就说明它本身是有精度的。

来看一下float的构成.

float由1个符号位，8个指数位和23位尾数位构成，而精度完全是由23位尾数控制的，因此虽然float可以表示很大，但那是通过指数位进行跳跃（乘以2的N次方)来得到了，换句话说，float能表示的数其实是不连续的，而我们现在的time(NULL)值`1526796356（0101 1011 0000 0001 0000 0100 0100b)`已经使用了31位二进制了，它的二进制有效数字位为29位，已经超出了float中的尾数位。因此在int转向float时必然会丢失精度。

弄清楚了问题之后，只需要加个类型强制转换就可以解决问题了:

//#define TIME time(NULL)
#define TIME 1526796356
time_t foo(int distance, float speed)
{
        return TIME + (time_t)(distance / speed);
}

BTW. 在查阅文档时，发现了一个有意思的事，《The C Program Language》第二版在算术类型转换一节中特意标注，在第一版中，所有的float类型算术运算都是先转换成double再进行，而第二版的描述是float类型算术运算‘有可能’直接进行，而不是转换成double之后再进行。

Lua5.3 GC源码阅读(4)

接上篇, Lua中的GC采用的是三色垃圾增量回收算法.

因此真正进入singlestep函数之前, 先来简单介绍一下三色垃圾回收算法.

在三色垃圾回收算法有,每个可回收对象都会有”黑”,”白”,”灰”三种颜色. 所有对象刚创建都是白色(这里暂不考虑barrier的效果), 一个完整的GC循环大概如下:

1. GC从根对象开始遍历并为对象标记颜色.(这里需要明确的时,根对象并不是指前面的global_State.allgc, 而是指Lua中的一些全局对象,比如lua_State, 注册表)

2. GC每当发现一个发现一个可回收对象A,就将其标记为”灰”色. 然后去遍历对象A引用了哪些可回收对象.

3. 当对象A引用的所有可回收对象都被标记以后, 对象A被标记为”黑色”.

4. GC递归执行2,3步骤直到遍历完所有可达的对象

5. GC清除掉所有的白色对象(这时global_State.allgc就派上用场了)

列举一下Lua中所有可回收对象,及每个对象都可能有哪些引用别的对象的方式(从函数reallymarkobject, propagatemark可以得出这些信息)

* “字符串(LUA_TSTRING)”: 不会引用其他对象,只要被标记就一定是黑色

* “用户数据(LUA_TUSERDATA)”: 元表(metatable), 用户数据(user value)

* “表(LUA_TTABLE)”: 元表(metatable), 表中的key和value字段,需要说明的是,如果__mode=”k”则,key的可达不会阻此key所引用的对象被回收,__mode=”v”同样如此, 更详细的弱表GC在这里

* “Lua闭包(LUA_TLCL)”: Lua函数原型(LUA_TPROTO), 上值(upvalue)

* “Lua C闭包(LUA_TCCL)”: 上值(upvalue)

* “协程(LUA_TTRHEAD)”: 栈上的所有Value

* “Lua函数原型(LUA_TPROTO)”: 常量字符串(literals), 上值的名字(upvalue names), 嵌套的LUA_TPROTO, 局部变量的名字

终于可以进行singlestep函数了.

singlestep函数本质上是个状态机, 会根据global_State.gcstate的值执行不同的逻辑, global_State.gcstate 共有8个可选值, LuaVM刚创建时global_State.gcstate默认值是GCSpause, 换句话说GC循环是从GCSpause状态开始的.

//lgc.h
#define GCSpropagate    0
#define GCSatomic       1
#define GCSswpallgc     2
#define GCSswpfinobj    3
#define GCSswptobefnz   4
#define GCSswpend       5
#define GCScallfin      6
#define GCSpause        7
//lstate.h
/*
** Some notes about garbage-collected objects: All objects in Lua must
** be kept somehow accessible until being freed, so all objects always
** belong to one (and only one) of these lists, using field 'next' of
** the 'CommonHeader' for the link:
**
** 'allgc': all objects not marked for finalization;
** 'finobj': all objects marked for finalization;
** 'tobefnz': all objects ready to be finalized;
** 'fixedgc': all objects that are not to be collected (currently
** only small strings, such as reserved words).
*/
typedef struct global_State {
  ...
  GCObject *allgc;  /* list of all collectable objects */
  GCObject **sweepgc;  /* current position of sweep in list */
  GCObject *finobj;  /* list of collectable objects with finalizers */
  GCObject *gray;  /* list of gray objects */
  GCObject *grayagain;  /* list of objects to be traversed atomically */
  GCObject *weak;  /* list of tables with weak values */
  GCObject *ephemeron;  /* list of ephemeron tables (weak keys) */
  GCObject *allweak;  /* list of all-weak tables */
  GCObject *tobefnz;  /* list of userdata to be GC */
  GCObject *fixedgc;  /* list of objects not to be collected */
  ...
};

//lstate.c
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  ...
  g->gcstate = GCSpause;
  ...
}

下面从GCSpause状态开始分析singlestep中每个状态都干了什么.

//lgc.c
static void restartcollection (global_State *g) {
  g->gray = g->grayagain = NULL;
  g->weak = g->allweak = g->ephemeron = NULL;
  markobject(g, g->mainthread);
  markvalue(g, &g->l_registry);
  markmt(g);
  markbeingfnz(g);  /* mark any finalizing object left from previous cycle */
}
case GCSpause: {
  g->GCmemtrav = g->strt.size * sizeof(GCObject*);
  restartcollection(g);
  g->gcstate = GCSpropagate;
  return g->GCmemtrav;
}

GCSpause是一个GC循环的开始, 不存在灰色对象, 因此清空灰色对象列表

然后标记根(全局)对象:mainthread(主线程(协程), 注册表(registry), 全局元表(metatable), 上次GC循环中剩余的finalize中的对象

在GSpause状态下标记的对象即是上面提到的根对象, 下面进入GCSpropagate阶段

case GCSpropagate: {
  g->GCmemtrav = 0;
  lua_assert(g->gray);
  propagatemark(g);
   if (g->gray == NULL)  /* no more gray objects? */
    g->gcstate = GCSatomic;  /* finish propagate phase */
  return g->GCmemtrav;  /* memory traversed in this step */
}

在GSpause状态下,每次都会取出一个灰色对象(引用的值还没有被标记的对象), 对他引用的所有对象进行标记.

直到所有灰色对象都变成黑色对象,就会进入GCSatomic状态.

在分析GSatomic之前, 先保存一下上下文, 来看看GC屏障(barrier)是怎么回事.

增量GC的标记过程可能会被打断(这一点可以从`case GCSpropagate`看出), 当一个对象被标记为黑色后, Lua应用程序可能会重新对这个黑色对象进行操作,这时就需要屏障(barrier)来感知这一行为.

Lua的GC有两种GC屏障,向前屏障(luaC_barrier)和向后屏障(luaC_barrierback).

#define luaC_barrier(L,p,v) (  \
  (iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ?  \
  luaC_barrier_(L,obj2gco(p),gcvalue(v)) : cast_void(0))

#define luaC_barrierback(L,p,v) (  \
  (iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ? \
  luaC_barrierback_(L,p) : cast_void(0))

void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  if (keepinvariant(g))  /* must keep invariant? */
    reallymarkobject(g, v);  /* restore invariant */
  else {  /* sweep phase */
    lua_assert(issweepphase(g));
    makewhite(g, o);  /* mark main obj. as white to avoid other barriers */
  }
}

void luaC_barrierback_ (lua_State *L, Table *t) {
  global_State *g = G(L);
  lua_assert(isblack(t) && !isdead(g, t));
  black2gray(t);  /* make table gray (again) */
  linkgclist(t, g->grayagain);
}

这两种屏障效果是相同的,之所以有两种不同的形式是因为出于效率考虑, 这一点Roberto大神也有明确说过, 不过具体出于什么原因确没有说.

我grep了所有代码, 发现发现只有三种情况下会调用luaC_barrier, 分别是: 为C闭包设置上值, 为full userdata设置用户数据, 设置元表(metatable)

这些操作都有一个明显的特别, 做这些操作时, 只会改变少量的引用关系, 可能Roberto大神觉得这种情况下直接将父节点变灰是不值得的(因为变灰后,会重新遍历所有引用的值).

虽然像tbl[k] = v这种操作也仅仅改变了一个引用关系,但是在两次singlestep之间有可能对一个表进行多次tbl[k] = v这种操作, 这样看来将tbl节点直接变灰是值得的, 因为中间可能会有多种变化(忽略这些变化可能会让GC负担更轻).

除了GCSatomic阶段是必须一次执行的外,标记和清除阶段都是增量进行的, 如果在执行完GCSatomic阶段后, 必须要保证新建的对象(新建对象默认全是白色的)不会被误清除.

Lua在这一点有一个精巧的实现, 在GC中有两种白色值(暂时称为W1,和W2), 在执行完GCSatomic之后白色值就会从W1切换到W2(假设GCSatomic之前白色值为W1), 在清除阶段只会清除白色值为W1的对像,并将所有非白色的对像置为W2的白色,而新建的对象白色值也都为W2, 在下一轮GC循环中,同样只会清除白色值为W2的对象, 而在GCSatomic之后对建的对象默认颜色值都为W1,依次交替进行.

在luaC_barrier_函数中, keepinvariant返回非0代表当前标记阶段还没有完成,因此直接将对象v挂在灰色列表(global_State.gray)上去, 让singlestep自行消化, 如果标记阶段已完成, 则直接将对象o置为白色, 留待下一个GC循环再重新进行标记跟踪(因为在GCSatomic阶段之后的白色对象必然时新一轮的白色值).

luaC_barrierback_函数比较粗爆,直接将对象t变为灰色. 这里会出现两种情况:

1. 在GCSatomic之前被调用, 直接将其挂到global_State.gray列表中,GCSpropagate, GCSatomic中会自行标记处理
2. 在GCSatomic之后被调用, 产生barrier的对象A必为新一轮的白色, 而在sweeplist阶段也会将对象t置为新一轮的白色,同样不会影响对象A的生命周期

现在恢复一下上下文, 进入GCSatomic状态.

static void propagateall (global_State *g) {
  while (g->gray) propagatemark(g);
}
case GCSatomic: {
  lu_mem work;
  propagateall(g);  /* make sure gray list is empty */
  work = atomic(L);  /* work is what was traversed by 'atomic' */
  entersweep(L);
  g->GCestimate = gettotalbytes(g);  /* first estimate */;
  return work;
}

之所以会上来先检测g->gray,是因为luaC_barrier函数的存在,它个函数在调用reallymarkobject时有可能会操作变量global_State.gray.

下面来看GCSatomic中最重要的步骤, atomic函数.

static l_mem atomic (lua_State *L) {
  global_State *g = G(L);
  l_mem work;
  GCObject *origweak, *origall;
  GCObject *grayagain = g->grayagain;  /* save original list */
  lua_assert(g->ephemeron == NULL && g->weak == NULL);
  lua_assert(!iswhite(g->mainthread));
  g->gcstate = GCSinsideatomic;
  g->GCmemtrav = 0;  /* start counting work */
  markobject(g, L);  /* mark running thread */
  /* registry and global metatables may be changed by API */
  markvalue(g, &g->l_registry);
  markmt(g);  /* mark global metatables */
  /* remark occasional upvalues of (maybe) dead threads */
  remarkupvals(g);
  propagateall(g);  /* propagate changes */
  work = g->GCmemtrav;  /* stop counting (do not recount 'grayagain') */
  g->gray = grayagain;
  propagateall(g);  /* traverse 'grayagain' list */
  g->GCmemtrav = 0;  /* restart counting */
  convergeephemerons(g);
  /* at this point, all strongly accessible objects are marked. */
  /* Clear values from weak tables, before checking finalizers */
  clearvalues(g, g->weak, NULL);
  clearvalues(g, g->allweak, NULL);
  origweak = g->weak; origall = g->allweak;
  work += g->GCmemtrav;  /* stop counting (objects being finalized) */
  separatetobefnz(g, 0);  /* separate objects to be finalized */
  g->gcfinnum = 1;  /* there may be objects to be finalized */
  markbeingfnz(g);  /* mark objects that will be finalized */
  propagateall(g);  /* remark, to propagate 'resurrection' */
  g->GCmemtrav = 0;  /* restart counting */
  convergeephemerons(g);
  /* at this point, all resurrected objects are marked. */
  /* remove dead objects from weak tables */
  clearkeys(g, g->ephemeron, NULL);  /* clear keys from all ephemeron tables */
  clearkeys(g, g->allweak, NULL);  /* clear keys from all 'allweak' tables */
  /* clear values from resurrected weak tables */
  clearvalues(g, g->weak, origweak);
  clearvalues(g, g->allweak, origall);
  luaS_clearcache(g);
  g->currentwhite = cast_byte(otherwhite(g));  /* flip current white */
  work += g->GCmemtrav;  /* complete counting */
  return work;  /* estimate of memory marked by 'atomic' */
}

说一下这个global_State.grayagain变量, 在进行GCSpropagate, 为了防止每次进入singlestep时global_State.gray上都有对象产生活锁, 对于可能反复变灰,或者二次变灰的对象都会挂在global_State.grayagain变量上留待GCSatomic阶段一次性标记.

* atomic函数刚开始就先保存g->grayagain, 因此为atomic函数中间不会让出, 为原子操作, 不会受barrier函数的影响, 而除此之外在GCSatomic阶段惟一能进入g->grayagain的就只有LUA_TTHREAD和weak table(这个类型永远不会为黑色), 重复去遍历g->grayagain没有意义

* atomic开始重新遍历(跟踪)根对象（当前thread, 注册表l_registry, 全局metatable, 线程相关的上值), 原因如下：

1. 在lstate.c中函数init_registry会改变global_State.l_registry的值，并且不会有barrier的调用
2. 根据lapi.c中的lua_setmetatable函数可知，在修改全局metatable表时，同样不会有barrier
3. 线程相关的上值经常变化，因为必须在atomic阶段重新遍历标记。

* atomic接着去遍历之前的grayagain(grayagain上会有弱表的存在), 并清理弱表的空间)

* atomic接着去调用separatetobefnz函数将带__gc函数的需要回收的(白色)对象放到global_State.tobefnz表中,留待以后清理

这里需要修改一下前面说过所有对象都在allgc链表的说法.

当对一个对像设置__gc函数时, 例如`setmetatable(tbl, {__gc == function() end})`, LuaVM会调用luaC_checkfinalizer函数将对像tbl从global_State.allgc链表上移除,并将其添加到global_State.finobj上(ps.从这里可以得出一个结论,__gc元表设置越早效率越高,因为这一操作需要遍历才实现).

* atomic重新使global_State.tobefnz上的所有对象全部可达, 不然global_State.tobefnz上的对象就有可能被singlestep的后续步骤清除, 这样当调用__gc(tbl)时, 就无法传入正确的tbl.

* atomic最后重新清理了一下弱表(global_State.tobefnz上的对象是有可能引用弱表的,如果这些弱表在此时还是白色的,同样需要阻止其被回收,但是其中的一些key需要重新考虑清除一下), 将当前白色值切换到新一轮的白色值(在此之后,所有新建的对象虽然也为白色,但是在GC循环走完之前并不会被回收), 准备进入GCSswpallgc状态.

* atomic在进入GCSswpallgc前会将global_State.sweepgc指向global_State.allgc上几乎所有对象,之所以用’几乎’这个词, 是因为它是通过函数`sweeplist`来做转换的, 这里不直接使用g->sweepgc = &g->allgc, 是希望g->sweepgc尽可能为&(g->allgc->next)的值. 这样做是原因是, 在进入GCSswpallgc状态后,整个GC又进入了增量模式, 此时可能会有很多新创建的对象(而这些对象是下一轮GC的白色值,因为必然不会被回收)挂在global_State.allgc上, g->sweepgc指向&(g->allgc->next)可以尽可能的避免这些额外干扰.

static void entersweep (lua_State *L) {
  global_State *g = G(L);
  g->gcstate = GCSswpallgc;
  lua_assert(g->sweepgc == NULL);
  g->sweepgc = sweeplist(L, &g->allgc, 1);
}

GCSatomic状态之后又进入增量模式，接着就是GCSswpallgc状态。

GCSswpallgc的作用就是将global_State.sweepgc上的所有死对象释放（上GCSatomic状态以前的白色值的对象)并将活对象重新标记为当前白色值。

接下来的GCSswpfinobj和GCSswptobefnz两个状态也调用了sweepstep函数。但是从上下文分析global_State.finobj和global_State.tobefnz链表上是不可能有死对象的，因此它们的作用仅仅是将这些对象重新设置为新一轮的白色。

GCSswpend用来释放mainthread上的一些空间，如：字符串表，连接缓冲区等。

整个GC大循环的最后一步就是GCScallfin状态，在这个状态会逐个取出global_State.tobefnz链表上的对象，然后调用其__gc函数，并将其放入global_State.allgc链表中，准备在下个GC循环回正式回收此对象（这也意味着对象可以在GC函数中被复活，同时这个被被复活的对象会失去其原有的__gc函数)

整个GC流程到此结束，有时间再详细分析关于弱表的实现。

作者：重归混沌