Allocating a chunk of stack space to carve up for general use

I've been working on a crate called bump-into for a while and using it in a project that's currently private. bump-into is a no-std, no-alloc crate providing a bump allocator over a chunk of memory that may be situated anywhere you can move a Rust value to, most importantly the stack. It can be used with no unsafe; here's the usage example from the README:

use bump_into::{self, BumpInto};

// allocate 64 bytes of uninitialized space on the stack
let mut bump_into_space = bump_into::space!(64);
let bump_into = BumpInto::from_slice(&mut bump_into_space[..]);

// allocating an object produces a mutable reference with
// the same lifetime as the `BumpInto` instance, or gives
// back its argument in `Err` if there isn't enough space
let number: &mut u64 = bump_into
    .alloc_with(|| 123)
    .expect("not enough space");
assert_eq!(*number, 123);
*number = 50000;
assert_eq!(*number, 50000);

// slices can be allocated as well
let slice: &mut [u16] = bump_into
    .alloc_n_with(5, core::iter::repeat(10))
    .expect("not enough space");
assert_eq!(slice, &[10; 5]);
slice[2] = 100;
assert_eq!(slice, &[10, 10, 100, 10, 10]);

This isn't something the language really provides for, and I'd like to see what people think about how sound my solution is.

Unlike a chunk of memory allocated using the alloc APIs, a chunk of memory on the stack needs to have a type in Rust. This is a problem if it's going to be written over with values of other arbitrary types, because reinterpreting the bytes of non-repr(C) values is undefined behavior.

I avoid reinterpreting bytes by giving the chunk of memory a type of either MaybeUninit or [MaybeUninit; N] (depending on which API is being used to allocate the space). When a BumpInto is constructed, it takes a pointer to the chunk of memory and turns it into a &mut [MaybeUninit<u8>], which is then carved up. The allocation methods are meant to respect alignment, and to avoid letting live mutable references point to overlapping regions of memory.

Hopefully that introduces the design and doesn't read too badly. For more insight, you can read the docs and the source. The tests currently fail under miri because of issue #1074. Values stored in the allocated spaces are never dropped (which I should put in the docs, now that I think about it).

So what do you think? Is the basic idea sound? There are a lot of moving parts here that could lead to unsoundness, and if anyone is interested in poking around in the source for fatal mistakes, I would appreciate that, too.

In addition to adding it to the docs, you might consider using mem::needs_drop() to guard the primary entrypoints, and only allow Drop types via an _unchecked variant. Since it’s a const fn, the optimizer should get rid of the check in the final binary.

It could be helpful to have a check, but that function's documentation says it may be implemented conservatively, so it seems unwise to fail on it.

You’re right; I hadn’t read the details of that one in a while. I guess that you could use it to conditionally add allocations to a free list that you process in your own Drop implementation, but that could get complicated fast.

Yeah, I considered doing something like that early on but decided it didn't need to be a part of this crate.

What you are doing sounds a lot like a bump allocator. Have you perchance checked out bumpalo?

It is a bump allocator, but it's distinct from bumpalo in that it doesn't depend on alloc and can't allocate space beyond what it's initially given.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.