« January 2024 | Main

February 22, 2024

关于虚拟文件系统的一些新想法

虚拟文件系统 (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 模块变成了管理一个纯内存数据结构,而不涉及网络同步,和外部数据如何存放于本地文件系统中无关。

February 05, 2024

为 log 实现的无锁 Ringbuffer

这两天在改 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 也应该很快能发现。

February 04, 2024

一个格式化文本信息版面的小玩意

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

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