云风的 BLOG

虚拟文件系统 (vfs) 是 Ant 引擎的核心模块。在 wiki 上有介绍 ，blog 上也有总结。

最近在按前段时间拟定的思路重构编辑器。在这个过程中对 vfs 有了一些新想法。短期内不打算把工作重心放到重构 vfs 上面，先记录一下。

最早设计 vfs 的时候，是从网络文件系统的角度看待它的。我把它设想为一个类似 git 的组织方式，带版本控制的网络文件系统。所以，很多设计思路都是延续这个而来。但是，经过了这些年的数次重构，我对最初的思路产生了一些怀疑。

其中，最重要的一条：在游戏运行时，游戏程序看到的 vfs 是一个树结构的不变快照。这样，它像 git 一样，就可以用一个 Merkle tree 的 hash 值就可以代表这个快照，也可以方便的通过网络同步它。

为了实现编辑器，我们在这个设计上打了一些补丁，让编辑器可以在运行时动态的修改它。而我今天反思，“不变快照” 这一点是否是多余的？或者并不需要这个约束，也可以用简单的方案实现现在所有的功能。

经过一些思考后，我认为可以用这样一个新方案：

1. vfs 是一个在运行时可以动态增删的树结构，而这个树结构只存在于内存中，不需要持久化。一开始，vfs 只有一个空的根目录。

2. 在运行时，需要不断的对 vfs 进行增改。把空的根目录扩展出更多的文件。我们可以设置一个路径 path 为一个特定的 hash 值。如果这个 path 中的任意一个子目录不存在，都应该被立刻创建出来。如果 path 对应的文件已经存在，则覆盖掉原有的值。即：vfs 是一颗树，每个叶节点都是一个 hash 值。

3. 可以把 vfs 树中任意一个 hash 值绑定内容。这个内容可以是内存数据块，也可以是一个本地文件（加上时间戳）。hash 值是数据内容的 sha1 ，所以同一个 hash 值只可以（也只需要）绑定一次。

4. 另有一个模块，可以递归计算本地文件目录：这包括所有文件及子目录的 hash 。生成一张表。如果程序在本地启动，不连接文件服务器，那么在启动时，计算本地目录的 hash ，用 3 中提到的 api 把相关 hash 全部绑定，再将 vfs 的根替换为计算好的 root hash 即可。

5. 如果连接文件服务器，那么可以向文件服务器请求当前任意 path 的 hash ，以及任意 hash 对应的内容。并在本地 cache hash 的内容。这个环节和现在已有的实现完全相同。

遵循以上的方案，vfs 就不必遵循不变快照的假设。而是在运行时可以任意增删查改。和现有的方案相比：vfs 模块变成了管理一个纯内存数据结构，而不涉及网络同步，和外部数据如何存放于本地文件系统中无关。

Posted by 云风 at 03:21 PM | Permalink | Comments (3)

这两天在改 log 模块。我们需要一个并发写 log 的模块，它有多个 log 生产者一个消费者，这个唯一的消费者在 log 线程中把 log 数据持久化。

大多数 log 生产者是在第三方库的 callback 函数中调用的，比如 bgfx ，如果写 log 不够快的话，就会阻塞渲染。这个 callback 需要自己保证线程安全。因为 bgfx 支持多线程渲染，所以写 log 的 callback 可能在不同的线程触发。

过去在实现 bgfx 的 luabinding 时，我实现了一个简单的 mpsc 队列，get_log 这个函数就是那个单一消费者，它取出队列中所有的 log 信息，返回到 lua 虚拟机中。

它是用 spin_lock 实现的。这两天，我想应该可以实现一个更通用的无锁版本。

在我的需求中，log 信息是允许丢掉的。所以我开了一个固定大小的 ringbuffer 收集各个不同线程生产出来的 log ，然后在一个单一线程定期（通常是一个渲染帧一次）取出它们。只要取的频率够高，而生产的 log 数量不那么快的话，一个合适大小的 ringbuffer 就能以最简单的数据结构解决问题。

我觉得一个无锁结构的 log 系统需要两个 ringbuffer 。

我们缓存的 log 条目数目上限估计不用太大，4096 或许是个合适的数字：即，每帧不会产生超过 4000 条 log 。那么就用一个 4096 的固定数组即可。

实现这么一个 ringbuffer 需要有两个 64bit 变量，head 和 tail 。其中 tail 被多个生产者共享，所以它必须是原子变量，让多个生产者依次尾进头出这个队列 ring buffer。head 只由唯一消费者控制，不需要原子变量。写入数据保持这样的流程：

1. index = fetch and add tail, 1
2. buffer[index % 4096] = meta

这里只需要记录 meta 信息，而不是 log 的文本。这里的 meta 信息只这一条 log 的实际内容在另一个 ringbuffer 中的 offset 和 size 。写入 meta 信息时，需要先写 offset 再写 size。为什么是这个次序，下面会展开说。

第二个 ringbuffer 记录 log 的文本内容，可以用一个更大的队列，比如 64K 。这个 ringbuffer 只需要一个 64bit 的原子变量 ptr 。而将 log 文本写入 buffer 只需要下列的流程：

1. offset = fetch and add ptr, size
2. copy string to buffer + offset % 64K （回绕时，需要分两段复制）

也就是说，我们把 log 文本写入一个固定长度的 ringbuffer 时，只要不断的推进 ptr 指针，然后写入数据即可，不用考虑是否覆盖了旧数据。

而 log 的消费者负责检查数据是否还在 ringbuffer 中，或是已经被覆盖丢失。这个检查条件非常简单： offset + 64K 小于 ptr 表示该 offset 处的内容已经不在内存中。因为持有引用方记住的 offset 和 ringbuffer 自己的 ptr 都是 64bit 单调递增的，而内存中只保存有 ptr 之前 64k 的内容，比较它们两个值就能知道数据是否有效。

在第一个 ringbuffer 每个条目的 meta 信息中，我们保存有数据在第二个 buffer 中的 offset 和 size 。读取后便可以校验读到的数据是否有效。

唯一一个读取 log 的消费者可遵循这样的流程：

1. 如果在第一个 ringbuffer 中， head == tail 表示队列为空。
2. 如果 head 对应的 meta.size 为负数， 表示数据还没有准备好（也可以视为空）。
3. 队列有效时，index = head++ 。递增 head 。
4. 根据 buffer[index] 的 offset 和 size 从第二个 ringbuffer 中取出内容。
5. buffer[index].size = -1 。赋值 size 为 -1 。这样可以标识这个 slot 是无效的。这可以保证在生产者填入数据时（最后写 size 字段），如果没填完，以上 step 2 就能检查出来。

我简单实现了一下：

https://gist.github.com/cloudwu/e8cc734a31dd01b439d8d131acc361c3

尚未测试。而且就我写并发代码，尤其是无锁结构，是很容易出错的。所以以上代码仅供参考。它的确很简单，如果有 bug 也应该很快能发现。

Posted by 云风 at 02:17 PM | Permalink | Comments (7)

bgfx 提供了一组调试文本输出的 api ，可以把一些文本信息显示在屏幕上。这些 API 非常简陋，只是提供了一个文本模式缓冲区。离控制台还很远。

具体见 文档中 的 dbgText* 系列函数。

随着我们的游戏引擎中越来越多的信息需要展示，直接使用这些 api 就越发简陋了。最近萌发的想法是干脆使用 imgui 来绘制调试信息界面。但我又觉得保留 bgfx 自带的这个文本模式也有一些好处。

这个周末，孩子被爷爷奶奶带回老家去了。难得有不需要陪娃的一天。我周六一大早起来就在想写点什么。

最开始的想法是，使用基于 ncursors 的 UI 库。翻了一下没看见什么特别喜欢的。而且 bgfx 的文本模式并不是一个终端，可能还需要先把它改造成一个 VT100 终端先。

在 github 上搜索了一番，我用 VT100 Emulator 找到一些简单的库，没见到开箱即用的。感觉自己实现一个 VT100 终端也不算太复杂。大约 400 行代码就够了。主要是实现 ansi escape code ，有了这个，就能对接 ncursors 或 pdcursors 之类的库，然后文本界面 TUI 的选择也有很多。

然后，我发现了 imtui 这样一个有趣的玩具。它给 imgui 加了一个文本模式的 backend 。看起来还是挺炫酷的。但仔细一看，项目不太活跃很久没更新了。翻了下实现，也就几百行代码，花了半个小时就懂了。

imgui 输出的是 draw list ，即绘图指令列表。backend 把这些绘图指令传给真正的图形 api 画出来就好了。但是，这些绘图指令包含的是顶点数据流，而丢失了最初想画什么这个信息。

比如，UI 上的文字，在 draw list 里看到的就是两个三角形；菜单上的箭头，变成了一个三角形；圆形则变成了很多很多三角形……

如果你想在文本模式下重现这些图案，在不修改 imgui 的代码的前提下，只能靠猜。猜 draw list 里那些三角形到底在干什么。然后把 draw list 的顶点流切分开，还原成更高阶的绘图指令。imtui 这个库在这方面做的并不算太好，我一下就想到了许多猜测的方案，要廉价很多，更好实现。

花了一个上午，我模仿 imtui 自己写了一个新的 imgui 的 backend ，我是这样猜测的：

我为字体定义了一个特有的 texture id ，如果 draw list 里用到这个 id ，就一定是在绘制文字。然后，我使用自定义字形，把 ascii 码都从 imgui 的默认字体中替换掉，换成一个个 1x1 一个像素的字模，并把 ascii 写到贴图上。这样，在 drawlist 里发现文字绘制的时候，我直接根据 uv 取字体贴图，就能取到文本的 ascii 码。

然后，drawlist 里相邻两个三角形如果能构成一个矩形的话，就认为是背景框。在文本缓冲区上画带颜色的背景框还是很简单的。btw, imtui 里还真的写了一个三角形光栅化的代码，我觉得完全没有必要。

有些非矩形的三角形，也很容易判断出是什么方向的箭头，转换为文本字符。其它复杂的集合图形就直接扔掉。

等我把这一切做完，单独测试了一下新的 imgui backend 输出一屏幕的文本图案后。我对整个方案又产生了怀疑。如果做下去，去对接 bgfx api 倒是不难，但是，让 imgui 输出一大堆三角形，再想办法反向解析回来，又有多少意义呢？

其实，我并不需要一个完整的可交互的 UI 界面啊。只是为了调试时在屏幕展示一些信息而已。之前不好用，是因为没有做一个方便的版面编排接口。imgui 我倒是用过一段时间，它的 api 非常好用，尤其是 table api ，可以在屏幕上任意切分区块，在里面安放控件。

如果我只需要这么一个版面控制模块，并只支持文本输出的话，好像就解决了问题。

仔细想了一下，实现似乎也不难。我迅速扔掉了上午写的代码，下午重新实现了一套新的文本信息排版的库。最难的 API 设计部分 ImGui 已经做好了，抄就可以。具体实现几百行代码就能搞定。

https://github.com/cloudwu/textcell

到晚饭时间，基本就写完了。这种一天就能搞定的小玩具，真的是周末最好的消遣。

Posted by 云风 at 02:41 PM | Permalink | Comments (1)