句柄是更好的指针(2018年)

2020-08-13 21:01:01

2018年11月28日:我在结尾处添加了一个小更新,介绍如何使用每个插槽生成计数器防止“处理冲突”

…。其中我稍微谈了一下最近我是如何在C和C++中进行动态内存管理的,它基本上是用“索引句柄”取代了原始指针和智能指针。

在我上一篇博客文章中,我提到了免指针和免分配编程,但是跳过了细节。这就是下面这篇博文的主题。

这一切都是基于与相当大的C++代码库(0.5到1MLOC)搏斗了15年以上(有时很痛苦)的经历,在这些代码库中,内存通常是通过智能指针来管理的。最糟糕的情况是数以万计到几十万个小C++对象,每个对象都在自己的堆分配中,通过智能指针相互指向。虽然这类代码在内存损坏方面相当健壮(段错误和损坏很少发生,因为大多数尝试在解除引用智能指针时都被断言捕获),但这种类型的“对象蜘蛛网络代码”也非常慢,没有明显的优化起点,因为整个代码充满了缓存未命中。其他典型的问题是内存碎片和“假内存泄漏”,因为忘记的智能指针会阻止释放底层内存(我称之为“假泄漏”,因为内存调试工具无法捕获这种类型的泄漏)。

这里介绍的并不是什么特别新或特别聪明的东西,它只是收集了一些简单的想法,它们一起在较大的代码库中工作得相当好,可以防止(或至少早期检测)C和C++中与内存有关的一些常见问题,甚至在更高级别的垃圾收集语言中可能会很有用,以减轻垃圾收集器的压力。

然而,底层的设计哲学并不能很好地适应典型的OOP世界,在这个世界中,应用程序是由相互交互的小型自主对象构建的。这就是为什么在现有的大型OOP代码库中实现这些想法也相当棘手的原因,在那里,对象的创建和销毁发生在整个代码中“分散的”。

不过,这里描述的方法在面向数据的体系结构中工作得非常好,在这种体系结构中,中央系统在内存中紧密打包的数据项阵列上工作。

下面的博客文章大部分是从游戏开发人员的角度撰写的,但也应该适用于程序需要在内存中同时处理几百到几百万个对象(或一般的“数据项”),以及经常创建和销毁此类项的其他领域。

将所有内存管理移至集中系统(如渲染、物理、动画、…)。,系统是其内存分配的唯一所有者。

将相同类型的项分组到数组中,并将数组基指针视为系统私有。

创建项目时,只向外部世界返回一个‘index-Handle’,而不是指向该项目的指针。

在索引句柄中,只使用数组索引所需的位数,其余位用于额外的内存安全检查。

只有在绝对需要时才将句柄转换为指针,并且不要将指针存储在任何地方。

下面我将详细解释其中的每一点。但基本的想法是,通用的“用户级”代码不会直接调用内存分配函数(如malloc、new或make_share/make_only),并将指针的使用减少到绝对最少(只有在绝对需要直接访问内存时才作为短暂的引用)。最重要的是,指针永远不是项的底层内存的“所有者”。

相反,直接内存操作尽可能多地发生在少数集中式系统中,在这些系统中,与内存相关的问题更容易调试和优化。

在这篇博客中,“系统”是代码库的一部分(通常相当大),它负责许多相关的任务,比如“渲染”、“物理”、“人工智能”、“角色动画”等等。这样的系统通过清晰定义的函数API与其他系统和“用户代码”分开,对系统数据所做的工作在紧密的中心循环中执行,而不是分散在整个代码库中。

系统通常在用户代码的控制下创建和销毁项目(但请注意,创建和销毁项目不同于分配和释放这些项目使用的内存!)。例如,渲染系统可能处理顶点缓冲区、纹理、着色器和管道状态对象,物理系统处理刚体、关节和碰撞基本体,动画系统处理动画关键点和曲线。

将这些项的内存管理转移到系统本身是有意义的,因为一般的内存分配器不具备关于如何处理数据项以及数据项之间的关系的系统特定的“域知识”。这允许系统优化内存分配,在创建和销毁项目时执行额外的验证检查,并在内存中安排项目以最大限度地利用CPU的数据缓存。

这种“系统域知识”的一个很好的例子是用现代3DAPI呈现资源对象的破坏:资源对象不能简单地在用户代码指示时立即销毁,因为该资源可能仍在等待GPU使用的命令列表中被引用。相反,呈现系统只会在用户代码请求销毁资源对象时将其标记为销毁,但实际销毁会在稍后GPU不再使用该资源时发生。

一旦所有内存管理转移到系统中,系统就可以利用其关于howitems的附加知识来优化内存分配和内存布局。一个明显的优化是通过将相同类型的项分组到数组中,并在系统启动时分配这些数组来减少通用内存分配的数量。

系统不会在每次创建新项时执行内存分配,而是跟踪空闲数组插槽,并挑选下一个空闲插槽。当用户代码不再需要该项时,系统简单地再次将插槽标记为空闲,而不是执行释放分配(与典型的池分配器没有什么不同)。

这种池分配很可能比按项执行内存分配要快一点,但这甚至不是将项保存在数组中的主要原因(现代通用分配器对于小分配也相当快)。

项目保证被紧密地打包在内存中,一般分配器有时需要在实际项目内存旁边保留一些内务数据。

在连续的内存范围内保存“热门项目”更容易,这样CPU就可以更好地利用它的数据缓存

还可以将单个项的数据拆分成不同数组中的几个子项,以实现更紧密的打包和更好的数据缓存使用(AoS与SoA以及两者之间的所有内容),并且所有这些数据布局细节都是系统私有的,更改起来微不足道,不会影响“外部代码”

只要系统不需要重新分配数组,就可以保证不会出现内存碎片(尽管这在64位地址空间中问题不大)。

更容易及早发现内存泄漏,并提供更有用的错误消息:当创建新项目时,系统可以根据预期上限简单地检查当前项目数量(例如,游戏可能知道一次活动的纹理不应该超过1024个,而且由于所有纹理都是通过渲染系统创建的,因此当超过这个数字时,系统可以打印出更有用的警告消息)。

将系统项保存在数组中而不是唯一分配的优点是,可以通过数组索引来标识项,而不需要完整的指针。这对于内存安全非常有用,系统可以将数组基指针视为“私有知识”,而不是将内存指针交给外部世界,而只向公众分发数组索引。如果没有基指针来计算项目的内存位置,外部代码就无法访问项目的内存,即使有很大的犯罪能量也是如此。

在许多情况下,系统外的代码甚至不需要直接访问项的内存,而只需要系统访问。在这种“理想”情况下,用户代码永远不会通过指针访问内存,也不会导致内存损坏。

因为只有系统知道数组基指针,所以可以随意移动或重新分配项数组,而不会使现有的索引句柄无效。

与完整指针相比,数组索引需要的位数更少,并且可以为它们选择更小的数据类型,这反过来又允许更紧密地打包数据结构和更好的数据高速缓存使用(这有一个警告,即可以使用额外的句柄位来提高内存安全性,下面将详细介绍这一点)。

如果用户代码需要直接访问项的内存,则需要通过“查找函数”获取指针,该函数将句柄作为输入并返回指针。一旦存在这样的查找函数,上面概述的相当严密的内存安全场景就不再得到保证,用户代码应该遵守以下几条规则:

指针不应该存储在任何地方,因为下次使用指针时,它可能不再指向同一项,甚至不再指向有效内存。

指针应该只在简单的代码块中使用,而不能“跨越”函数调用。

每次将句柄转换为指针时,系统可以保证返回的指针仍然指向最初为其创建句柄的同一项(下面将详细介绍),但是这种保证会超时,因为指针下的项可能已被销毁,或者底层内存可能已被重新分配到不同的位置(这与C++中迭代器无效的问题相同)。

上面两个简单的规则很容易记住,它们是完全不向用户代码公开指针和每次内存访问都有句柄到指针转换(代价有点高)之间的一个很好的折衷。

首先,每种类型的句柄都应该有自己的C/C++类型,这样就可以在编译时检测到试图将错误的句柄类型传递给函数的行为(请注意,简单的tyecif不足以产生编译器警告,句柄必须包装到它自己的结构或类中-但是,这可以限于调试编译模式)。

所有运行时内存安全检查都发生在将句柄转换为指针的函数中。如果句柄只是一个数组索引,则如下所示:

针对当前项数组大小对索引进行范围检查,这可防止分段错误以及读取或写入已分配但不相关的内存区域。

需要检查索引的数组项槽是否包含活动项(当前不是“空闲槽”),这会阻止“释放后使用”的简单变体

最后,根据私有数组基指针和公共项索引计算项指针。

两者都只能发生在系统的一个函数中,这就是为什么存在两个“指针使用规则”(不要存储指针,不要跨函数调用保留指针)。

不过,上面的释放后使用检查有一个很大的漏洞:如果我们只检查索引句柄后面的数组槽是否包含有效项,就不能保证它与最初为其创建该句柄的项相同。可能会发生这样的情况:原始物品被销毁,而相同的插槽被重新用于新物品。

这就是句柄中的“空闲位”的用武之地:假设我们的句柄是16位的,但我们同时只需要1024个活动项。只需要10个索引位就可以寻址1024个项目,这样就有6个位可以用来处理其他事情。

如果这6位包含某种“唯一模式”,就有可能检测到悬空访问:

创建项时,会选取一个自由数组项,并将其索引放入较低的10个句柄位。将高6位设置为“唯一位模式”

得到的16位句柄(10位索引+6位“唯一模式”)返回给外界,同时与数组槽一起存储。

当项目被销毁时,与数组槽一起存储的项目句柄被设置为“无效句柄”值(可以是零,只要零从未作为有效句柄返回给外界)

当句柄转换为指针时,低10位用作数组索引以查找数组槽,并将整个16位句柄与当前存储在数组槽中的句柄进行比较:如果两个句柄相等,则指针有效,并指向为其创建该句柄的同一项。

否则,这是一次悬空访问,插槽项目要么已被销毁(在这种情况下,存储的句柄将具有“无效句柄”值),要么已被销毁并重新用于新项目(在这种情况下,高6个“唯一模式”位不匹配)。

在将句柄转换为指针时,这种句柄比较检查可以很好地检测悬空访问,但它不是防水的,因为数组索引和“唯一模式”的相同组合迟早会被创建。但它仍然比根本没有悬空保护(如原始指针)或“假内存泄漏”要好,后者在智能指针的类似情况下会发生。

当然,找到好的策略来创建尽可能少发生冲突的独特句柄是最重要的部分,并留给读者作为练习;P<foreign language=“English”>P</foreign>。

显然,将尽可能多的位用于唯一模式是很好的,并且空闲数组槽的重用方式也很重要(例如,后进先出与先进先出)。编写一些创建/销毁压力测试,检查句柄冲突,并可用于调整特定用例的独特模式创建,可能也很好。与很少创建和销毁物品的系统相比,频繁创建和销毁物品的系统需要更多的工作(或者只是更多的句柄位)。

除了整个内存安全方面,句柄对于指针有问题的其他情况也很有用:

句柄可以用作跨进程的共享对象标识符(您所需要的只是某种“create_item_with_handle()”函数,该函数不会创建新的句柄,而是将现有的句柄作为输入参数)。这对于在线游戏特别有用,在游戏会话中,服务器和所有客户端之间可以共享句柄,或者在savegame系统中,用于存储对其他对象的引用。

有时,创建一整组相关项目(用于实例动画关键点和曲线)并使用单个句柄引用整个项目组非常有用。在这种情况下,可以使用某种“范围句柄”,它不仅包含(第一项的)索引,还包含范围中的项数。

在某些情况下,如果编译时静态类型检查不够,为项类型保留几个句柄位也很有用。

总之,我发现用传统的“堆上对象指针”模型很自然、很优雅地解决了我过去遇到的许多问题,现在我很少怀念这个模型(以及围绕它构建的C++部分)。

SOKOL-gfxAPI是C-API的一个示例,它使用句柄而不是呈现资源对象(缓冲区、图像、着色器、…)的指针。:

Oryol动画扩展模块是一个角色动画系统,它将其所有数据保存在数组中:

…。在上面的帖子中,我对为同一个位置创建两次相同的唯一标签的问题不屑一顾,推特上的一位好心人暗示我一个非常简单、优雅、令人尴尬的“显而易见”的解决方案:

每个数组槽都有自己的生成计数器,当释放句柄时会发生碰撞(也可能在创建句柄时发生,但是碰撞释放意味着您不需要“空闲槽”的保留值来检测无效的句柄)。

要检查句柄是否有效,只需将其唯一标记与其槽中的currentGeneration计数器进行比较即可。

一旦生成计数器将“溢出”,则禁用该数组插槽,这样就不会为该插槽返回新的句柄。

这是避免手柄冲突的完美解决方案,但手柄最终会用完,因为所有阵列插槽最终都将被禁用。但是因为每个槽都有自己的计数器,所以这只有在所有句柄位耗尽之后才会发生,而不仅仅是少数几个唯一标记位。

因此,使用32位句柄,您总是可以创建40亿个项目,同时最多有2^(32-num_counter_bits)处于活动状态。这也意味着唯一标签的位数可以减少,而不会损害“处理安全”。

一旦可以保证不再有该插槽的句柄在野外(可能在代码中的特殊位置,如进入或退出关卡),也可以重新激活被禁用的插槽。