2402d,d的内存库设计
原文
为D设计新的分配器接口
设计目标
对std.experimental.allocator
的Allocator
接口
必备品
1,允许适合分配器的通用容器
2,用户定义的分配器
3,结合@safe
和@nogc
,没有
锦上添花
1,可组合分配器
2,运行时多态性(IAllocator)
3,无异常
4,BetterC
兼容性
非目标
1,替换现有代码
中对new/malloc/etc.
的直接调用.
2,可配置的全局分配器
.
原理
允许适合分配器的通用容器
D是一个旨在支持从低级系统编程
到高级脚本
的各种用例
的通用语言
.
Phobos
当前的容器库std.container
无法支持其中的许多用例
,主要是因为它硬编码依赖druntime
的GC
来分配
内存.
因此,会看到code.dlang.org
上的大量不完整的或很少维护
的容器库.
启用与任意分配器
一起工作的通用容器
可弥补
此缺点.
用户定义的分配器
不同分配内存
方法适合
不同应用.为了支持尽量多的用例
,用户
必须可自定义分配器.
结合@safe
和@nogc
std.experimental.allocator
的allocator
接口(及依赖
它的emsi_containers
等库)的用户
目前被迫在@safe
和@nogc
间选择
.不应这样.
可组合分配器
通过组合可重用
组件,来定义新的分配器
可大大减少创建
复杂分配器或试验不同分配内存
方法的期望代码量
.
虽然很有用,但很少有用户
可能利用它,且可用其他方式
满足,因此它只是"很高兴拥有
",而不是"必须拥有
".
运行时多态
分配器的运行时多态
允许通用容器
用户使用单个具体类型
(如Array!(int,IAllocator)
),而不是仅因分配器
选择而异的各种各样的类型
(如,Array!(int,Mallocator)
,数组!(int,GCAllocator)
等).
虽然很方便,但标准库
已有解决该问题的功能:区间
.即,允许接受具体类型InputRange
(或ForwardRange,RandomAccessRange
等)的代码实现std.range.interfaces
中的接口类型
的相应接口
的容器
.
区间
并未涵盖分配器多态性
的所有可能用例
,但足以使目标
从"必须
"降级为"最好拥有
".
无异常
虽然最终根据分配器作者
决定是否使用异常
,但分配器
接口设计
应适应这两个选择
.
最好,除非无法保证内存安全
,分配器接口
不应要求使用异常
.因为内存安全是"必须
的",因此目标是"很好
".
BetterC
兼容性
同样,最终根据分配器的作者
决定,是否依赖druntime
,但接口
自身应该可在BetterC
中使用.
现有代码中替换直接调用new/malloc/etc.
使分配器接口@safe
期望的特征
,使用起来很麻烦.已用(如new
或malloc
)特定分配器的代码
无法轻松采用新接口
,且可能不会从中受益
.
可配置的全局分配器
全局状态
一般是代码气味
,因此需要令人信服的用例
来证明包含可配置全局分配器
的合理性.
没有证据表明存在此用例.std.experimental.allocator
同时提供了theAllocator
和processAllocator
,但没人用它们.
挑战
结合@safe
和@nogc
分配
本质是内存安全
的;只有释放
(及扩展的重新分配
)才可能导致内存破坏
或UB
.
因为想支持通用容器
和用户定义的分配器
,因此在调用释放
分配时,释放
方法自身必须@safe
(或@trusted
),不能要求容器
使用@trusted
.有关更详细的讨论,见此论坛主题.
在没有GC
时,要使分配器
安全释放内存块
,必须满足以下条件:
1,唯一性
:不得有对块
的其他引用
.
2,活跃:块
必须尚未释放
.
3,匹配
:块必须是来自分配器
的分配
方法.
要让deallocate(释放)
变得@safe
,必须按禁止编译违反这些条件的@safe
代码,来设计分配器API
.
在std.experimental.allocator
的allocator
接口中,块使用void[]
,让编译器无法确保上述所有3个条件
.
1,可自由复制void[]
块.
2,可传递同一void[]
块的多个副本
给释放
.
3,无论从哪来的void[]
块,都可把它传递给释放
方法.
不能简单
更改实现来使std.experimental.allocator
变得@safe
.必须重新设计
分配器接口自身.
BetterC
兼容性
std.experimental.allocator
的Allocator
接口并不依赖D运行时
,且实现原则
上已与BetterC
兼容.
确保新版本
分配器接口
保持BetterC
兼容应该不难.
但是,因为std.experimental.allocator
是Phobos
的一部分,并且被编译到Phobos
共享库(libphobos.so
或等效库)中,因此在链接
阶段,它的许多重要部分排除了BetterC
程序.
因此,尽管原则上与BetterC
兼容,但它无法在BetterC
中使用.
本文档的主题是设计新的分配器接口
.因为这里的挑战是实现挑战
,而不是接口设计挑战
,因此不再讨论.
可能方法
结合@safe
和@nogc
唯一性
为了保证唯一性
,可用不可复制
的包装器
类型替换void[]
块:
struct Block
{
@system void[] payload;
@system this(void[] payload) { this.payload = payload; }
@disable this(ref inout Block) inout;
}
用@system
变量作负载,以避免@safe
代码创建块内存
的未跟踪引用
,用@system
构造器来避免@safe
代码创建
别名现有void[]
的块
.
为了允许在@safe
代码中临时受控
访问内存
,可用"借用模式
":
auto borrow(alias callback)(ref Block block)
{
scope void[] tmp = null;
() @trusted { swap(block.payload, tmp); }();
scope(exit) () @trusted { swap(block.payload, tmp); }();
return callback(tmp[]);
}
借用
时用空切片
交换有效负载
,对块的底层内存
,可保持
只有一个引用
的不变性
.
活动
确定唯一性
后,保证活动性
所必需的,就是确保
在成功释放
后不再使用引用
分配的单个唯一块
.
最简单方法是让deallocate
按引用
取其Block
参数,并在成功释放
时,用nullBlock
覆盖它:
void deallocate(ref Block block);
为了检查是否成功释放
,现在让块
与Block.init
比较,而不是检查布尔返回值
:
Block block = someAllocator.allocate(123);
//用块干活...
someAllocator.deallocate(block);
if (block == Block.init)
{
//成功释放
}
else
{
//释放失败
}
因为检查null
很常见,因此添加个助手方法
:
struct Block
{
//...
bool isNull() => this == typeof(this).init;
}
匹配
要考虑两点
:
1,实现拥有(owns)
的分配器.
2,未实现拥有
的分配器.
(1)
时,保证匹配
很容易:可在释放内部
调用拥有(owns)
.如:
void deallocate(ref Block block) @safe
{
if (block.isNull) return;
if (!this.owns(block)) assert(0, "Invalid block");
//执行实际释放...
}
注意,这要求拥有(owns)
总是返回true
或false
,而不是Ternary.unknown
.std.experimental.allocator
中实现拥有(owns)
的每个分配器
都满足此要求.
(2)
需要更多工作.
根本上来说,为了保证分配和释放
的匹配,必须要回答,“该块
是否来自该分配器
”,因为这是拥有(owns)
要回答的相同问题
,很明显,可回答它
的方法,也可用来实现拥有(owns)
.
因此,方法是,对任意分配器
,即使是"天生"
不支持它的分配器
,找到实现拥有
的方式.
如果可能,还想用最小的运行时成本
来完成它,并避免惩罚已实现(拥有)own
的分配器
.
自定义块类型
从简单示例
开始:Mallocator
.因为Mallocator
只有一个全局实例
,所以实现拥有(owns)
只需要把每个块
与一位
信息关联
:该块是由Mallocator
分配的,还是由其他
分配的.
在不产生运行时成本
时,可给Mallocator
提供自己的块类型
:
struct MallocatorBlock { /*...*/ }
struct Mallocator
{
MallocatorBlock allocate(size_t n) @trusted
{
if (n == 0) return MallocatorBlock.init;
void* p = malloc(n);
if (p) return MallocatorBlock(p[0 .. n]);
else return MallocatorBlock.init;
}
void deallocate(ref MallocatorBlock block) @trusted
{
if (block.isNull) return;
if (!this.owns(block)) assert(0, "Invalid block");
free(block.payload.ptr);
block = MallocatorBlock.init;
}
//...
}
如果只能从Mallocator.allocate
取MallocatorBlock
,则只能把Mallocator
分配的块
传递给Mallocator.deallocate
.即,分配和释放
保证匹配
.
因为这是在编译时
通过类型系统
确保的,拥有(owns)
的实现
很简单:
struct Mallocator
{
//...
bool owns(ref MallocatorBlock block) @safe
{
return !block.isNull;
}
//...
}
自定义块数据
如果想支持的每个分配器
都是全局
的,或可自己单独实现拥有
,则仅自定义块类型
就可保证
匹配.大多数现实世界
的分配器确实属于这两类
之一,包括std.experimental.allocator
目前提供的每个分配器
.
尽管如此,还要考虑,对缺乏开箱即用
的非全局分配器
来说,实现拥有
还需要
什么.如果很容易
做到,则可以;如果很难
,就算了.
碰巧,至少有个此类分配器的真实示例
:Win32
私有堆API
这里.
要实现此分配器
的拥有
,需要足够信息
来唯一标识
它的特定实例
,且需要关联信息
与它分配的每个块
.
广义上讲,有两个
方法可完成.一是直接
添加必要信息到自定义块类型
中:
struct PrivateHeapBlock
{
//...
@system HANDLE handle;
}
struct PrivateHeap
{
@system HANDLE handle;
bool owns(ref PrivateHeapBlock block) @trusted
{
return !block.isNull && block.handle == this.handle;
}
//...
}
根据Win32API
文档,创建
时HeapCreate
返回的句柄
唯一标识每个私有堆
.因此,如果扩展自定义块类型
来存储分配它的堆的句柄
,可简单检查句柄
是否匹配
来实现拥有
.
优点
是执行
成本极低.缺点
是会增加块50%
的大小,且会把该存储成本
强加给使用PrivateHeap
分配内存的任意代码
.
或使用辅助数据结构
来跟踪块和堆
间的关联
:
struct PrivateHeap
{
@system bool[Block] ownedBlocks; //AA用作集
bool owns(ref Block block) @trusted
{
return !block.isNull && block in ownedBlocks;
}
//...
}
优点
是不需要自定义块类型
,且不会对外部代码
施加存储成本
.缺点是给PrivateHeap
自身增加了大量的存储成本
,且拥有
更昂贵.
有趣的是,除了为支持Mallocator
工作外,这两个方法都不需要更改
提议的分配器接口
.特别是,一旦决定允许自定义块类型
,就可"免费"
在其中存储
额外数据.
结论
1,如果不完全
重新设计,就无法使D的分配器接口既@safe
又@nogc
.
2,新设计
必须替换void[]
为块类型
,来保持安全释放期望
的不变量
.
3,允许分配器自定义块类型
,可不超过必要的运行时成本
的,允许分配器支持@safe
释放.