[RFC] spring clean (revamp) the Pool API

[japaric]

All memory Pools are backed by a Treiber stack, which is effectively a linked list (an intrusive collection). as of v0.7.x, The "node" of this linked list (struct shown below) stores the data next to the "next" pointer, which points to the next item in the linked list. This results in each node having a size of sizeof(T) + max(sizeof(usize), alignof(T)) bytes

// treiber stack (linked list) node
struct Node<T> {
    // in the CAS variant, this is AtomicPtr (still pointer sized)
    next: Option<NonNull<T>>,
    data: MaybeUninit<T>,
}

This RFC proposes to change the layout of Node to be an union (shown below) to reduce the footprint of Node to max(sizeof(T), sizeof(usize))

union Node<T> {
   next: Option<NonNull<T>>,
   data: MaybeUninit<T>,
}

(also see #167)

This document also proposes changing the existing Pool API to make it closer to the API of Box the standard library; and adding an ObjectPool API that manages initialized objects that are never destroyed

Finally, this document proposes removing the x86-sync-pool Cargo feature and providing the family of Pool APIs only on targets where it can be implemented in a sound lock-free manner, i.e. x86 and targets that have LL/SC operations, like ARM and RISC-V

API changes

Summary:

• Box loses its Uninit type state.
  • rationale: the type state can be layered on top of Box<T>, e.g. Box<Initialized<T, Yes>> / Box<Initialized<T, No>>
• remove the deprecated Box::freeze API
• rename Pool to BoxPool
• rename arc::Pool to ArcPool
• grow is removed and grow_exact gets renamed to manage
• Node gets renamed to MemoryBlock
• add ObjectPool API

Changes in existing API

the following snippets highlight the changes. the snippets are using the non-singleton API for simplicity; v0.8.x will also include a singleton version of the API

common code

struct Thing {
    data: [u8; 128],
}

impl Thing {
    fn new() -> Self {
        Self { data: [0; 128] }
    }
}

impl Drop for Thing {
    fn drop(&mut self) {
        todo!() // side effect
    }
}

current / v0.7.x

static P: Pool<Thing> = Pool::new();

static mut BLOCKS: MaybeUninit<[Node<Thing>; 8]> = MaybeUninit::uninit();
// emulate cortex-m-rt::entry transform
let blocks: &'static mut _ = unsafe { &mut BLOCKS };

P.grow_exact(blocks);

let uninit: Box<T, Uninit> = P.alloc().unwrap();
let mut x: Box<T, Init> = uninit.init(Thing::new());
// .. do stuff ..
P.free(x); // Thing's destructor runs

proposed / v0.8.x

static P: BoxPool<Thing> = BoxPool::new();

const BLOCK: MemoryBlock<Thing> = MemoryBlock::new();
static mut BLOCKS: [MemoryBlock<Thing>; 8] = [BLOCKS; 8];
// emulate cortex-m-rt::entry transform
let blocks: &'static mut _ = unsafe { &mut BLOCKS };

for block in blocks {
    P.manage(block);
}

let mut x: Box<Thing> = P.alloc(Thing::new()).ok().unwrap();
// .. do stuff ..
P.free(x); // Thing's destructor runs

new ObjectPool API

ObjectPool manages already initialized objects. Objects managed by this pool will never be drop-ped. The main use case is reusing POD (Plain Old Data) types, like arrays of bytes, without re-initializing the object every time is requested. Example:

static P: ObjectPool<[u8; 128]> = ObjectPool::new();

const BLOCK: ObjectBlock<[u8; 128]> = ObjectBlock::new([0; 128]);
static mut BLOCKS: [ObjectBlock<[u8; 128]>; 8] = [BLOCK; 8];
// emulate cortex-m-rt::entry transform
let blocks: &'static mut _ = unsafe { &mut BLOCKS };

for block in blocks {
    P.manage(block);
}

// NOTE no initialization required
let mut x: Object<[u8; 128]> = P.request().unwrap();
// .. do stuff ..
P.return_(x); // no destructor runs here

Sketch implementation

the singleton API has been omitted for simplicity. See https://gist.github.com/japaric/cb0d6e460b6253f17f954557c4ab0baa

thoughts @korken89 ?