Rust 可以保证我使用正确的对象池释放对象吗？

Question

假设我定义了自己的对象池结构。在内部，它保留了所有对象的 Vec 和一些数据结构，使其知道向量中的哪些项目当前已分发，哪些是免费的。它有一个 allocate 方法，returns 向量中未使用项目的索引，以及一个 free 方法，告诉池中向量中的索引可以再次使用。

我是否可以定义我的对象池的 API 类型系统和借用检查器将保证我将对象释放回正确的池？这是假设我可能有多个相同类型的池实例的情况。在我看来，对于常规的全局分配器，rust 不必担心这个问题，因为只有一个全局分配器。

用法示例：

fn foo() {
    let new_obj1 = global_pool1.allocate();
    let new_obj2 = global_pool2.allocate();

    // do stuff with objects

    global_pool1.free(new_obj2); // oops!, giving back to the wrong pool
    global_pool2.free(new_obj1); // oops!, giving back to the wrong pool
}

Answer 1

首先，需要考虑的一点是，将项目插入 Vec 有时会导致它重新分配和更改地址，这意味着对 Vec 中项目的所有现有引用都将变得无效。我想您曾希望用户可以保留对 Vec 中项目的引用并同时插入新项目，但很遗憾，这是不可能的。

解决此问题的一种方法是 generational_arena 使用的方法。插入一个对象 returns 一个索引。您可以调用 arena.remove(index) 释放对象，调用 arena.get[_mut](index) 获取对象的引用，借用整个区域。

但是，为了便于讨论，我们假设您有办法在插入新项目和执行您可能需要的任何其他操作时保持对竞技场的引用。考虑到引用本质上是一个指针，答案是否定的，没有办法自动记住它来自哪里。但是，您可以创建一个类似于 Box、Rc 等的“智能指针”，它保留对竞技场的引用，以便在对象被丢弃时释放它。

例如（非常粗糙的伪代码）：

struct Arena<T>(Vec<UnsafeCell<T>>);

struct ArenaMutPointer<'a, T> {
    arena: &'a Arena,
    index: usize,
}

impl<T> DerefMut for ArenaPointer<'_, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { self.arena[self.index].get() as &mut T }
    }
}

impl<T> Drop for ArenaPointer<'_, T> {
    fn drop(&mut self) {
        self.arena.free(self.index);
    }
}

Answer 2

品牌化

使用生命周期作为品牌，将特定变量与一个其他变量联系起来的想法已经进行了多次尝试，并且没有别的。

为了获得保证在范围内的索引，已对其进行了显着探索：在创建时检查一次，之后始终可用。

不幸的是，这需要创建不变的生命周期以防止编译器将多个生命周期“合并”在一起，虽然可能我还没有看到任何引人注目的 API。

仿射，非线性。

同样重要的是要注意 Rust 没有线性类型系统，而是仿射类型系统。

线性类型系统是每个值只使用一次的系统，而仿射类型系统是每个值最多使用一次的系统一次。

这里的结果是很容易不小心忘记 return 一个对象到池中。虽然在 Rust 中泄漏对象总是安全的——mem::forget 是一种简单的方法——但这些情况通常很突出，因此相对容易审计。另一方面，仅仅忘记 return 池中的值会导致意外泄漏，这可能会花费相当长的时间。

放下它！

因此，解决方案是让值 return 本身进入它在 Drop 实现中来自的池：

这样就不可能不小心忘记 return。
它要求对象持有对它来自的池的引用，这样就不可能意外 return 它到错误的池。

当然，这是有代价的，即与对象一起存储额外的 8 个字节。

这里有两种可能的解决方案：

瘦指针：struct Thin<'a, T>(&'a Pooled<'a, T>); 其中 struct Pooled<'a, T>(&'a Pool<T>, T);.
胖指针：struct Fat<'a, T>(&'a Pool<T>, &'a T);。

为简单起见，我建议从 Fat 替代方案开始：它更简单。

然后 Thin 或 Fat 的 Drop 实现只是 return 指向池的指针。

Answer 3

您可以使用零大小类型（简称 ZST）来获得您想要的 API，而无需另一个指针的开销。

这是 2 个池的实现，可以扩展它以支持使用宏生成“标记”结构（P1、P2 等）的任意数量的池。一个主要的缺点是忘记 free 使用池会“泄漏”内存。

这个 Ferrous Systems blog post 有许多可能的改进，您可能会感兴趣，特别是如果您静态分配池，并且它们还有一些技巧可以玩弄 P1 的可见性，所以用户将无法滥用 API.


use std::marker::PhantomData;
use std::{cell::RefCell, mem::size_of};

struct Index<D>(usize, PhantomData<D>);
struct Pool<D> {
    data: Vec<[u8; 4]>,
    free_list: RefCell<Vec<bool>>,
    marker: PhantomData<D>,
}

impl<D> Pool<D> {
    fn new() -> Pool<D> {
        Pool {
            data: vec![[0,0,0,0]],
            free_list: vec![true].into(),
            marker: PhantomData::default(),
        }
    }
    
    fn allocate(&self) -> Index<D> {
        self.free_list.borrow_mut()[0] = false;
        
        Index(0, self.marker)
    }
    
    fn free<'a>(&self, item: Index<D>) {
        self.free_list.borrow_mut()[item.0] = true;
    }
}

struct P1;
fn create_pool1() -> Pool<P1> {
    assert_eq!(size_of::<Index<P1>>(), size_of::<usize>());
    Pool::new()
}

struct P2;
fn create_pool2() -> Pool<P2> {
    Pool::new()
}


fn main() {
    
    let global_pool1 = create_pool1();
    let global_pool2 = create_pool2();
    
    let new_obj1 = global_pool1.allocate();
    let new_obj2 = global_pool2.allocate();

    // do stuff with objects

    global_pool1.free(new_obj1);
    global_pool2.free(new_obj2);

    global_pool1.free(new_obj2); // oops!, giving back to the wrong pool
    global_pool2.free(new_obj1); // oops!, giving back to the wrong pool
}

尝试使用错误的池进行释放会导致：

error[E0308]: mismatched types
  --> zpool\src\main.rs:57:23
   |
57 |     global_pool1.free(new_obj2); // oops!, giving back to the wrong pool
   |                       ^^^^^^^^ expected struct `P1`, found struct `P2`
   |
   = note: expected struct `Index<P1>`
              found struct `Index<P2>`

Link to playground

这可以稍微改进，以便借用检查器强制执行 Index 不会 out-live Pool，使用：

fn allocate(&self) -> Index<&'_ D> {
    self.free_list.borrow_mut()[0] = false;
        
    Index(0, Default::default())
}

因此，如果在 Index 处于活动状态时删除池，您会收到此错误：

error[E0505]: cannot move out of `global_pool1` because it is borrowed
  --> zpool\src\main.rs:54:10
   |
49 |     let new_obj1 = global_pool1.allocate();
   |                    ------------ borrow of `global_pool1` occurs here
...
54 |     drop(global_pool1);
   |          ^^^^^^^^^^^^ move out of `global_pool1` occurs here
...
58 |     println!("{}", new_obj1.0);
   |                    ---------- borrow later used here

Link to playground

此外，a link to playground with Item API（返回 Item，与仅返回 Index）

Rust 可以保证我使用正确的对象池释放对象吗？

Can rust guarantee I free an object with the right object pool?

memory

double-free

rust

borrow-checker

品牌化

仿射，非线性。

放下它！