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;
}
1
2
3
4
5
6

用@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[]);
}
1
2
3
4
5
6
7

借用时用空切片交换有效负载,对块的底层内存,可保持只有一个引用的不变性.

活动

确定唯一性后,保证活动性所必需的,就是确保在成功释放后不再使用引用分配的单个唯一块.

最简单方法是让deallocate按引用取其Block参数,并在成功释放时,用nullBlock覆盖它:

void deallocate(ref Block block);
1

为了检查是否成功释放,现在让块与Block.init比较,而不是检查布尔返回值:

Block block = someAllocator.allocate(123);
//用块干活...
someAllocator.deallocate(block);
if (block == Block.init)
{
    //成功释放
}
else
{
    //释放失败
}
1
2
3
4
5
6
7
8
9
10
11

因为检查null很常见,因此添加个助手方法:

struct Block
{
    //...
    bool isNull() => this == typeof(this).init;
}
1
2
3
4
5

匹配

要考虑两点:
1,实现拥有(owns)的分配器.
2,未实现拥有的分配器.

(1)时,保证匹配很容易:可在释放内部调用拥有(owns).如:

void deallocate(ref Block block) @safe
{
    if (block.isNull) return;
    if (!this.owns(block)) assert(0, "Invalid block");
    //执行实际释放...
}
1
2
3
4
5
6

注意,这要求拥有(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;
    }
    //...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果只能从Mallocator.allocate取MallocatorBlock,则只能把Mallocator分配的块传递给Mallocator.deallocate.即,分配和释放保证匹配.

因为这是在编译时通过类型系统确保的,拥有(owns)的实现很简单:

struct Mallocator
{
    //...
    bool owns(ref MallocatorBlock block) @safe
    { 
        return !block.isNull;
    }
    //...
}
1
2
3
4
5
6
7
8
9

自定义块数据

如果想支持的每个分配器都是全局的,或可自己单独实现拥有,则仅自定义块类型就可保证匹配.大多数现实世界的分配器确实属于这两类之一,包括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;
    }
    //...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

根据Win32API文档,创建时HeapCreate返回的句柄唯一标识每个私有堆.因此,如果扩展自定义块类型来存储分配它的堆的句柄,可简单检查句柄是否匹配来实现拥有.

优点是执行成本极低.缺点是会增加块50%的大小,且会把该存储成本强加给使用PrivateHeap分配内存的任意代码.

或使用辅助数据结构来跟踪块和堆间的关联:

struct PrivateHeap
{
    @system bool[Block] ownedBlocks; //AA用作集
    bool owns(ref Block block) @trusted
    {
        return !block.isNull && block in ownedBlocks;
    }
    //...
}
1
2
3
4
5
6
7
8
9

优点是不需要自定义块类型,且不会对外部代码施加存储成本.缺点是给PrivateHeap自身增加了大量的存储成本,且拥有更昂贵.

有趣的是,除了为支持Mallocator工作外,这两个方法都不需要更改提议的分配器接口.特别是,一旦决定允许自定义块类型,就可"免费"在其中存储额外数据.

结论

1,如果不完全重新设计,就无法使D的分配器接口既@safe又@nogc.
2,新设计必须替换void[]为块类型,来保持安全释放期望的不变量.
3,允许分配器自定义块类型,可不超过必要的运行时成本的,允许分配器支持@safe释放.