Rust 内存分配

使用Unique会给Vec(以及所有的标准库集合)带来一个问题:空的Vec不会分配内存。如果既不能分配内存,又不能给ptr传递一个空指针,那我们在Vec::new中能做什么呢?好吧,我们就胡乱往Vec里塞点东西。

这么做没什么问题,因为我们用cap == 0来表示没有分配空间。我们也不用做什么特殊的处理,因为我们通常都会去检查cap > len或者len > 0。Rust推荐的放进去的值是mem::<T>()。Unique则提供了一个更方便的方式Unique::empty()。我们会在很多的地方用到empty,因为有时候我们没有实际分配的内存,而null会降低编译器的效率。

所以:

#![feature(alloc, heap_api)]

use std::mem;

impl<T> Vec<T> {
    fn new() -> Self {
        assert!(mem::size_of::<T>() != 0, "还没准备好处理零尺寸类型");
        Vec { ptr: Unique::empty(), len: 0, cap: 0 }
    }
}

我们插入了一个assert语句,因为零尺寸类型需要做很多特殊的处理,我们希望以后再讨论这个问题。如果没有assert的话,我们之前的代码会出现很多严重的问题。

接下来我们要讨论在需要内存空间的时候,我们要做些什么。这里我们需要使用其他的heap API。这些API允许我们直接和Rust的分配器(默认是jemalloc)打交道。

我们还需要能够处理内存不足(OOM)的方法。标准库会调用std::oom(),而这个函数会调用oomlangitem。默认情况下,它就是执行一个非法的CPU指令来中止程序。之所以要终止程序而不是panic,是因为栈展开的过程也可能需要分配内存,而你的分配器早就告诉过你“嘿,我这没有更多的内存了”。

当然,这么做显得有一点傻乎乎,因为大多数平台正常情况下都不会真的没有内存。如果你的程序正常地耗尽了内存,操作系统可能会用其他的方式kill掉它。真的遇到OOM,最有可能的原因是我们一次性的请求严重过量的内存(比如,理论地址空间的一半)。这种情况下其实可以panic而不用担心有什么问题。不过,我们希望尽量模仿标准库的行为,所以我们还是中止整个程序。

好了,现在我们可以编写扩容的代码了。简单粗暴一点,我们需要这样的逻辑:

if cap == 0:
    allocate()
    cap = 1
else:
    reallocate()
    cap *= 2

但是Rust支持的分配器API过于底层了,我们不得不做一些其他的工作。我们还需要应对过大的或者空的内存分配等特殊的场景。

特别是ptr::offset会给我们造成很多麻烦。因为它的语义是LLVM的GEP inbounds指令。如果你很幸运,以前没有处理过这个语义,这里就简单介绍一下GEP的作用:别名分析,别名分析,别名分析。推导数据依赖和别名对于一个成熟的编译器来说至关重要。

一个简单的例子,看一下下面这段代码:

*x *= 7;
*y *= 3;

如果编译器可以证明xy指向内存的不同区域,那么这两个操作理论上可以并行执行(比如,把它们加载到不同的寄存器并各自独立地处理)。但一般编译器不能这么做,因为如果x和y指向相同的区域,两个操作是在同一个值上做的,最后的结果不能合并到一起。

如果你使用了GEP inbounds,你其实是在告诉LLVM你的offset操作是在一个分配实体里面做的。LLVM可以认为,当已知两个指针指向不同的对象时,他们所有的offset也都不是重名的(因为它们只能指向某个确定范围内的位置)。LLVM针对GEP offset做了很多的优化,而inbounds offset是效果最好的,所以我们也要尽可能地利用它。

这就是GEP做的事情,那么它怎么会给我们制造麻烦呢?

第一个问题,我们索引数组时使用的是无符号整数,但GEP(其实也就是ptr::offset)接受的是有符号整数。这表明有一半合法的索引值是超出了GEP的范围的,会指向错误的方向。所以我们必须限制所有的分配空间最多有isize::Max个元素。这实际意味着我们只需要关心一个字节大小的对象,因为数量> isize::MAXu16会耗尽系统的内存。不过,为了避免一些奇怪的边界场景,比如有人将少于isize::MAX个对象的数组重解析为字节数组,标准库还限制了分配空间最大为isize::MAX个字节。

Rust目前支持的各种64位目标平台,都被人为限制了内存地址空间明显小于64位(现代x86平台只暴露了48位的寻址空间),所以我们可以依赖于OOM实现上面的要求。但是对于32位目标平台,特别是那些借助扩展可以使用多于寻址空间的内存的平台(PAE x86或x32),理论上可能成功分配到多于isize::MAX字节的内存。

不过因为本书只是一个教程,我们也不必做得绝对完美。这里就使用无条件检查,而不用更智能的平台相关的cfg

另一个需要关注的边界场景是空分配。而空分配又分为两种:cap = 0,以及cap > 0但是类型大小为0。

这些场景的特殊性在于,它们都做了特殊的处理以适配LLVM的“已分配”的概念。LLVM的分配的概念比我们通常的理解要更加抽象。因为LLVM要适配多种语言的语义以及分配器,它其实并不知道什么叫做分配。它所谓的分配的实际含义是“不要和其他的东西重叠”。也就是说,堆分配、栈分配以及全局变量都不能有重合的区域。是的,这就是别名分析。如果Rust和这一概念保持一致的话,理论上可以做到更快更灵活。

回到空分配的场景,代码中许多的地方都可能需要offset 0。现在的问题是:这么做会导致冲突吗?对于零尺寸类型,我们知道它可以做到任意数量的GEP inbounds offset而不会引起任何问题。这实际上是一个运行期的no-op,因为所有的元素都不占用空间,可以假设有无数个零尺寸类型位于0x01。当然,没有哪个分配器真的会分配那个地址,因为它们不会分配0x00,而最小的对齐(alignment)通常要大于一个字节。同时,内存的第一页通常处于受保护状态,不会在上面分配空间(对于大多数平台,一页是4k的空间)。

如果是尺寸大于0的类型呢?这种情况就更复杂一些。原则上,你可以认为offset 0不会给LLVM提供任何的信息:地址的前面或后面可能存在一些元素,可不需要知道它们确切是什么。但是,我们还是谨慎一些,假设这么做有可能导致不好的情况。所以我们会显式地避免这种场景。

终于要结束了。

不要再说这些废话了,我们实际写一段内存分配的代码:

use std::alloc::oom;

fn grow(&mut self) {
    // 整段代码都很脆弱,所以我们把它整体设为unsafe
    unsafe {
        // 现在的API允许我们手工指定对齐和尺寸
        let align = mem::align_of::<T>();
        let elem_size = mem::size_of::<T>();

        let (new_cap, ptr) = if self.cap == 0 {
            let ptr = heap::allocate(elem_size, align);
            (1, ptr)
        } else {
            // 简单起见,我们假设self.cap < isize::MAX,所以这里不需要做检查
            let new_cap = self.cap * 2;
            // 因为之前已经成功分配过了,所以这块不会溢出
            let old_num_bytes = self.cap * elem_size;

            // 检查新分配的空间不超过isize::MAX,而不管实际的系统容量大小。
            // 这里包含了对new_vap<=isize::MAX和new_num_bytes<=usize::MAX的检查
            // 我们不能充分利用所有的地址空间。比如,一个i16的Vec在32位平台上,
            // 有2/3的地址空间分配不到。这些空间永远地离开了我们。
            // Alas, poor Yorick -- I knew him, Horatio.(译注:《哈姆雷特》中悼念逝去生命的经典台词)
            assert!(old_num_bytes <= (::std::isize::MAX as usize) / 2,
                    "capacity overflow");

            let new_num_bytes = old_num_bytes * 2;
            let ptr = heap::reallocate(self.ptr.as_ptr() as *mut _,
                                        old_num_bytes,
                                        new_num_bytes,
                                        align);
            (new_cap, ptr)
        };

        // 如果分配或者再分配失败,我们会得到null
        if ptr.is_null() { oom(); }

        self.ptr = Unique::new(ptr as *mut _);
        self.cap = new_cap;
    }
}

没有什么特别奇怪的操作。只是计算类型大小和对其,然后小心地做一些乘法检查。

我们从push开始,实现一些真正的功能。它要做的事情就是检查空间是否已满,满了就扩容,然后写数据到下一个索引位置,最后增加长度。写数据时,我们一定要小心,不要计算我们要写入的内存位置的值。最坏的情况,那块内存是一 ...