improvements on allocators

[publicqi]

background

as described in #126, svm runtime gives the user heap to use anyways with or without defining a heap allocator.

default BumpAllocator will store two usize on bss section, one indicating the free pointer and the other max len.

default BumpAllocator stores heap free pointer at 0x300000000.

NoAllocator now does not allow alloc generated heap allocation, and #126 adds a manual allocation for NoAllocator.

a few thoughts

1. NoAllocator's name is confusing. it is able to let user to claim heap memory, but it cannot let alloc crate to get memory.
2. NoAllocator is very dev-unfriendly (maybe we can introduce some static check to avoid overlap?)
3. using allocating functions in crate alloc like Box::new will introduces some rust runtime check, like null ptr check. subsequently it emits panic stuff like in use get_unchecked over [] to prevent fmt code emission #85 .
4. allocate_unchecked needs the annoying #![cfg_attr(target_os = "solana", feature(const_mut_refs))]

some easy todo improvements:

• remove len field of BumpAllocator
• remove const for allocate_unchecked (or we wait for toolchain updating to 1.83.0)
• add same interface (allocate_unchecked) for BumpAllocator
• allocate_unchecked should return &'static mut MaybeUninit<T>
• introduce static_assertions for allocate_unchecked to through compile-time error for assertion (e.g. heap oob)

some challenging ones:

• compile time overlap check (not sure if it's possible without touching the compiler)
• bypass alloc runtime check (i.e. lightweight panic if allocation fails). i tried but failed. compiler change needed for this one

[publicqi]

@febo let me know your thoughts on the easy-to-do ones.

[febo]

Great stuff!

I am actually working on something that will hopefully improve the combination of static allocations + bump allocator. It will address some of your points. I should have a draft PR very soon.

My idea is to avoid having to do the compile time overlap check, although it will have trade-offs since it means all allocations have to be known at compile time. E.g., you won't be able to have two different execution paths that allocate all available memory – probably won't be an issue.

Not sure about always returning &'static mut MaybeUninit<T>. Currently you have the option to allocated a MaybeUninit<T>, which will give you a &'static mut MaybeUninit<T> back.

[publicqi]

I am actually working on something that will hopefully improve the combination of static allocations + bump allocator. It will address some of your points. I should have a draft PR very soon.

sounds good i'll leave this to you then. i do think NoAllocator and BumpAllocator can combine. just reserve another 8 bytes for free pointer for NoAllocator

you won't be able to have two different execution paths that allocate all available memory

my initial though it that this is really for NoAllocator alone. if a dev decided to use NoAllocator instead of BumpAllocator, it might indicate they do not want to keep track of free pointer. overlapping could be an issue. but yeah giving the control to the devs is also okay. and if you're refactoring by combining the two allocators this won't be an issue.

Not sure about always returning &'static mut MaybeUninit<T>

for NoAllocator it's not guaranteed the heap returned is unpolluted. but again if you're doing the combining we can guarantee the returned space is zero-filled.

[febo]

for NoAllocator it's not guaranteed the heap returned is unpolluted. but again if you're doing the combining we can guarantee the returned space is zero-filled.

Yeah, we are guaranteed to start with a zeroed heap: https://github.com/anza-xyz/agave/blob/1904feb212505be06087a95ad6f9732b60a20868/program-runtime/src/mem_pool.rs#L67-L74

When you are manually managing the memory, then it is up to you to either don't overlap allocations or use MaybeUninit to allocated previously used memory.

[publicqi]

another one #142