将Verse事务内存语义引入C++

Phil Pizlo

从《Fortnite》版本28.10开始,我们的一些服务器(基于虚幻引擎的大型C++可执行文件)将使用新的编译器进行编译,该编译器将为C++提供与Verse兼容的事务内存语义。这是在保留Verse语义的同时,向Verse公开更多虚幻引擎功能的第一步。

Verse编程语言事务内存特性作为头等功能。以下是一个示例:

var X = 0
if:
  set X = 42      # 这会发生回滚,原因在于
                  # 下一行
  X > 100         # 这会失败,导致回滚
X = 0               # 由于回滚,X重新变为0

这种行为适用于任何效应,而不仅仅是Verse中的set操作。例如,这次,我们可以调用一个C++函数,使用C++修改某个可变变量(即存储到指针上),然后,我们可以使用其他C++函数来读取这个可变变量:

SetSomething(0)            # 在c++中实现,设置一个c++
                          # 变量
if:
   SetSomething(42)       # 这会回滚,原因在于
                          # 下一行
   GetSomething() > 100   # 这会失败,导致回滚
GetSomething() = 0         # 由于回滚,重新变为0

因此,为了支持正确的Verse语义,我们需要C++遵守Verse的事务规则,记录所有效应,以便回滚。

Verse代码始终在事务中运行,而事务要么成功完成,要么中止。中止的事务是“不可见”的,它们会消除所有效应,就像什么都没发生过。除了对并发性的影响外,Verse的事务模型还表明:
  • Verse中的运行时错误应该中止整个事务,因为Verse不允许提交没有成功的事务。
  • Verse的失败上下文(如if语句的条件)是嵌套的事务,如果条件成功则提交,不成功则中止。允许条件表达式产生效应。如果条件失败,效应将消失,如同从未存在。
  • 所有效应都是事务化的,即使存在于本地代码中的效应也是如此。如果Verse程序要求C++执行某些操作,然后在同一事务中遇到运行时错误,那么C++所做的一切操作都必须撤销。如果Verse程序要求C++在失败上下文中执行某些操作,然后条件失败,那么C++所做的一切操作也必须撤销。
  • Verse事务是粗粒度的。默认情况下,Verse代码始终在一个事务中,该事务的范围由进入Verse的最外层调用者决定。由于大多数Verse API都是用C++实现的,这意味着每当中止一个Verse事务时,几乎总是必须撤销一些C++状态的更改。

在Verse的最初实现中,解决这个问题的方式是:
  • 搁置Verse运行时错误语义。目前,Verse运行时错误无法正确回滚中止的事务。这是我们需要修复的问题。
  • 与Verse的语义相反,在失败上下文中,许多API都是不允许调用的。这在语言中表现为<no_rollback>效应,一旦这个问题被修复,我们就会弃用它。
  • 让支持事务的C++代码为其执行的任何效应手动注册撤销处理程序。这太过复杂,以至于无法扩展(因此出现了<no_rollback>效应),并且容易出错,导致难以调试的崩溃(比如为已删除的内容注册了一个撤销处理程序)。

《Fortnite》28.10版开始,我们的部分服务器将使用基于clang的新C++编译器进行编译,我们称之为AutoRTFM(故障内存自动回滚事务)。该编译器会自动转换C++代码,精确地为每个效应(包括每个存储指令)注册撤销处理程序,以便在发生Verse回滚时可以撤销这些效应。AutoRTFM实现了这一目标,对于任何不在事务中运行的C++代码,其性能开销为零。即使在事务中和事务外使用同一个C++函数,情况也是如此;只有当运行线程位于事务范围内时,才会产生开销。此外,虽然某些C++代码必须经过修改才能在AutoRTFM中运行,但我们只需对《Fortnite》的代码库做出总计94处代码修改,即可使其适应AutoRTFM。而且正如我们将在本文中展示的,即使是那些更改,也异常简单。

在这篇文章中,我们将详细介绍该编译器及其运行时的工作原理,并预测这将如何影响Verse生态系统。

AutoRTFM 编译器和运行时

AutoRTFM的设计初衷是提供一种简单的方式,让现有的C++代码(在设计时并未考虑任何事务语义)只需使用另一种编译器就能实现事务处理。例如,AutoRTFM允许你编写以下代码:

void Foo()
{
   TArray
<int> Array = {1, 2, 3};
   AutoRTFM::Transact([&] ()
    {
       
Array.Push(42);
       // 这里的数组是{1、2、3、42}。
       AutoRTFM::Abort();
   });
   // 由于中止,这里的数组是{1,2,3}。
}

这无需对TArray做出任何更改即可生效。即使TArray需要在Push内部重新分配其后备存储,它也能正常工作。TArray在这方面甚至并不特殊;AutoRTFM也可以为std::vector/std::map,以及虚幻引擎和C++标准库中的大量其他数据结构和函数做到这一点。为了实现这一点,唯一需要进行的更改就是AutoRTFM与底层内存分配器和垃圾回收器(GC)的集成,而且正如我们将在本节中展示的那样,即使是这些更改,幅度也非常小(它们纯粹是累加进来的,而且只有寥寥几行;我们已经将它们添加到了虚幻引擎的许多malloc、GC以及系统malloc/new中)。除此之外,AutoRTFM在实现这一点时,对于那些在事务之外运行的代码路径(即在Transact调用的动态范围之外),性能不会出现任何下降。最重要的是,即使代码路径(如TArray和许多其他代码路径)在事务内部使用,那些在事务外部使用的情况也不会产生任何成本。当代码在事务内部执行时,开销会很高(我们在一些内部基准测试中看到了4倍的开销),但还不足以影响《Fortnite》服务器的Tick率。

本节将说明这一成果的实现方式。首先,我们将介绍整体架构。然后,我们将介绍新的LLVM编译器通道,它不直接对代码进行插桩,而是为所有可能参与事务的代码创建事务克隆,然后只对克隆进行插桩。接下来,我们将介绍运行时及其API,它们将简化AutoRTFM与现有C++代码的集成(这里涉及更有趣的部分,例如分配器)。下面的两节将分别介绍这两个组成部分。
 

AutoRTFM架构

从长远看,我们希望使用事务内存实现并行性。实现并行性的事务内存实现通常会维护一个读写集,该集跟踪事务运行时的堆状态快照。因此,我们必须对写入读取进行插桩;否则,我们将无法知道只读取某个位置的事务是否由于并行提交而遇到竞态条件。

但从短期来看,我们需要实现两个目标:
  • 即使Verse代码调用了C++,也要为Verse代码提供事务语义。这并不需要并行性,但确实需要事务内存。
  • 使用添加了事务内存语义的新编译器规范化编译《Fortnite》服务器(非常庞大且成熟的C++代码)。

因此,我们的第一步不是实现AutoSTM(软件事务内存),而是实现AutoRTFM(故障内存回滚事务),它只实现了单线程事务。AutoRTFM处理的问题严格来说更简单。由于不存在并发性(Verse可能调用的游戏代码预期仅在主线程中运行),我们只需记录写入。忽略读取意味着在初始引导时开销较低,而且错误更少,因为任何只读取堆的代码都能在AutoRTFM中正常工作。

AutoRTFM的架构在概念上非常简单。AutoRTFM运行时会维护内存位置及其旧值的日志。每当写入内存时,编译器都会对代码进行插桩,以调用AutoRTFM运行时中的函数。接下来的两节将详细介绍编译器和运行时。
 

LLVM编译器通道

AutoRTFMPass的任务是对所有代码进行插桩,使其能够遵守Verse的事务语义。但是,在《Fortnite》中,同样的代码可能用于堆栈上没有Verse代码,并且Verse语义没有必要的地方,也可能用于堆栈上有Verse代码,并且可能发生回滚的地方。

AutoRTFTM编译器是围绕克隆而构建的,而不是生成“如果当前线程在事务中记录写入”这样的代码。处于事务中的状态完全由在事务克隆中执行来表示。实际上,bCurrentThreadIsInTransaction位被编码在了程序计数器中。从编译器的角度看,这很简单:它只是克隆你的所有代码,向克隆的函数赋予重整后的名称以免混淆,然后只对克隆进行插桩。原始代码保持未插桩状态,不进行任何日志记录或其他特殊操作,因此运行该代码不会产生任何成本。克隆的代码得到插桩,并且肯定知道自己处于事务中,这甚至使我们能够玩出类似虚拟机的技巧,比如尝试备用的调用约定。

由于代码是克隆的,我们还需要在克隆中对间接函数代码进行插桩。如果函数执行一个间接调用,那么它试图调用的指针将是指向被调用者原始版本的指针。因此,在克隆代码中,所有的间接调用首先向AutoRTFM运行时请求该函数的克隆版本。就像AutoRTFM的所有插桩一样,这会使克隆代码成本更高,但对原始代码没有影响。

AutoRTFMPass在LLVM管线中的运行时机与Sanitizer相同,即在所有IR优化完成之后,将代码发送到后端之前。这具有重要影响,例如,即使在被插桩的克隆中,也只有在优化后幸存下来的加载和存储才会被插桩。所以,虽然在C++中给非逃逸本地变量赋值在抽象意义上是一种“存储”(并且当clang为该程序创建未优化的LLVM IR时,它会以这种方式表示),但在AutoRTFMPass开始工作时,这个存储会完全消失。最有可能的是,它将被SSA数据流替换,AutoRTFM无需干预。我们还基于现有的LLVM静态分析实现了一些小的优化,以避免在可证明不必要的情况下对存储进行插桩。

使用函数克隆意味着,如果你使用我们的编译器编译了一些C++代码,但从未调用过任何AutoRTFM运行时API,那么克隆将永远不会被调用,因此除了拥有一个包含大量死代码的较大二进制文件所需的成本外,你完全不需要承担任何开销(因此并非完全为零,但也接近于零)。

下一节将介绍AutoRTFM运行时如何让被插桩的克隆充分发挥作用。
 

AutoRTFM运行时

AutoRTFM的运行时集成到了虚幻引擎核心中,因此从虚幻引擎程序(如《Fortnite》)的角度来看,它始终可用。AutoRTFM中实现神奇效果的关键函数是AutoRTFM::Transact。使用lambda调用该函数会使运行时建立一个事务对象,其中包含日志数据结构和其他事务状态。然后,Transact会调用lambda的克隆。这与 lambda 完全相同,但具有事务插桩,并遵守AutoRTFM ABI。

目前,我们会在Verse进入失败上下文(如if条件)时调用Transact。在将来,我们将在进入任何Verse执行之前调用Transact

运行时必须处理(并提供API处理)以下情况:
  • 如果传递给Transact的lambda,或者它传递调用的某个函数没有克隆,会怎么样呢?这种情况会发生在系统库函数或未使用AutoRTFM编译的模块中的任何函数上。
  • 如果事务化的代码需要执行一些非事务安全的操作,比如使用原子操作对物理命令缓冲区无锁添加命令,该怎么办呢?AutoRTFM提供了多个API,用于手动控制事务。这个问题最常见的执行实例是malloc/free和相关函数(如自定义分配器)。

每当要求AutoRTFM查找克隆函数时,如果没有找到克隆函数,AutoRTFM就会中止事务,并报错。这样做可以确保安全,因为不可能意外调用到非事务安全的代码。要么被调用者已被事务化,克隆存在并被调用;要么被调用者不存在,事务因为缺少函数而中止。所以,默认情况下,在事务中调用WriteFile之类的函数会出错。这是理想的默认行为,因为WriteFile无法被可靠地撤销——即使我们稍后尝试撤销写入,其他线程(无论是在我们的进程中还是在另一个进程中)可能已经看到了写入,并据此执行了不可恢复的操作。因此,使用AutoRTFM编译现有的C++程序,然后尝试执行Transact,是一种实用的做法。它要么会正常工作,要么会出现错误,提示你调用了非事务安全函数,并附上关于如何找到该函数及其调用位置的消息。

最难处理的部分是malloc和相关函数。AutoRTFM采取的方法是不对malloc的实现进行事务化,但强制调用者用AutoRTFM API封装对malloc的调用。在像虚幻引擎这样的程序中,这尤其简单明了,因为已经有一个外观API封装了实际的malloc实现。最好通过查看代码来了解我们的工作。在使用AutoRTFM之前,FMemory::Malloc大致是这样的:
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
   
return GMalloc->Malloc(Count, Alignment);
}


注意,我们去掉了很多细节,只展示重要的部分。

有了AutoRTFM,我们改为这样做:
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
   
void* Ptr;
 
  UE_AUTORTFM_OPEN(
   {
       Ptr =
GMalloc->Malloc(Count, Alignment);
   });
   AutoRTFM::
OnAbort([Ptr]
   {
       
Free(Ptr);
   });
   
return AutoRTFM::DidAllocate(Ptr, Count);
}


让我们一步步地了解发生了什么。
  1. 我们使用UE_AUTORTFM_OPEN指出,括号内的代码块(会被转换成lambda)应该在没有事务插桩的情况下运行。这对于运行时和编译器来说,很容易实现:它只意味着我们发出对lambda的原始(未克隆)版本的调用。这意味着GMalloc->Malloc在事务中运行,但没有任何事务插桩。我们将此称为“开放式运行”(与意味着运行事务化克隆的封闭式运行相对)。因此,在UE_AUTORTFM_OPEN返回后,malloc调用将立即运行完成,而没有注册任何回滚。这保持了事务语义,因为malloc已经是线程安全的,因此在malloc对象的指针从事务中泄漏出来之前,其他线程无法观察到这个线程进行了malloc操作。在提交之前,指针不会从事务中泄漏出去,因为Ptr可以存放的地方要么是其他新分配的内存,要么是AutoRTFM将通过记录写入将要事务化的内存。
  2. 接下来,我们使用AutoRTFM::OnAbort注册一个在中止时释放对象的处理程序。如果事务提交,该处理程序不会运行,因此malloc的对象会被保留下来。但是,如果事务中止,我们将释放该对象。这确保了在中止时没有内存泄漏。
  3. 最后,我们通知AutoRTFM,这块内存是新分配的,这意味着运行时无需记录对该内存的写入。不记录对内存的写入使运行OnAbort变得更容易,因为我们不必担心AutoRTFM会在我们释放对象后,尝试将对象内容覆盖回之前的状态。而且,不记录对新分配内存的写入是一种有用的优化。

如果此代码在事务之外运行(即,所有这些代码都是从开放状态调用的),那么:
  • UE_AUTORTFM_OPEN只运行代码块。
  • AutoRTFM::OnAbort是一个空操作;传入的lambda会被忽略。
  • AutoRTFM::DidAllocate是一个空操作。

接下来,我们看看在释放时会发生什么。再次强调,我们已经删除了一些对于本讨论不重要的细节。

void FMemory::Free(void* Original)
{
 
  UE_AUTORTFM_ONCOMMIT(
   {
       
GMalloc->Free(Original);
   });
}

 
UE_AUTORTFM_ONCOMMIT函数具有以下行为:
  • 在事务化代码中:这将注册一个在事务提交时执行的处理程序,以在开放状态下调用给定的 lambda。所以,当发生事务提交时,对象被释放。它不会立即被释放。如果事务中止,对象不会被释放。
  • 在开放代码中:立即运行lambda,因此对象会立即被释放。

这种插桩风格(malloc立即分配内存,但在中止时释放,而free在提交时释放)被应用到了我们所有分配器中。AutoRTFM运行时甚至通过函数查找和编译器技巧,为malloc/free/new/delete安装了自己的处理程序,所以即使你使用系统分配器,也能得到正确的行为。虚幻引擎的GC也做了类似的事情,只是没有free函数,我们在关卡Tick结束时运行GC增量——所以在任何事务之外。

结合编译器、运行时以及使用Open/OnCommit/OnAbortAPI的malloc/GC插桩,只要代码不使用原子操作、锁、系统调用,或者调用我们选择完全不进行事务化的虚幻引擎代码库部分(比如当前的渲染引擎和物理引擎),我们就有了运行 C++ 代码的事务所需的一切。这使得Open API在整个《Fortnite》中的总使用次数达到了94次。这些使用涉及以适当的粒度用Open和相关API封装现有代码,而无需更改算法或数据结构。

Verse生态系统影响

AutoRTFM是为UEFN提供更多Verse语义的第一步。有了AutoRTFM,我们将能够:
  • 实现更简洁的运行时错误行为,使游戏在出现错误后仍能继续运行。即使运行时错误是在C++代码深处检测到的,AutoRTFM也能让我们恢复到已知状态。
  • 移除<no_rollback>效应,以便可以从iffor调用更多代码。这种效应污染了大量函数签名,它之所以存在,是因为大多数C++代码无法进行事务处理。AutoRTFM解决了这个问题。
  • 公开全局事务语义,可以只使用Verse代码和全局变量编写数据库访问。AutoRTFM使Verse代码可以被推测性地运行。这将带来激动人心的可能性,例如让Verse参与跨越网络的事务,因为我们将能够进行推测,以摊销远程数据访问的成本。

立即获取虚幻引擎!

获取全球最开放、最先进的创作工具。
虚幻引擎包罗万象,并提供完整的源代码访问权限,开箱即用,诚意十足。