Your second paragraph doesn't make sense because the whole point of this type of allocation is to guarantee that you will reuse the same address space you just freed.
This sounds like it would make the alloc logic much more complicated and branch-y, defeating the purpose of bumping down anyway, unless your implying some compile-time way to do this.
No, the idea is that you manually make some allocations downward from the top and some allocations upward from the bottom. The bumping code is as simple as in the unidirectional case.
The tricky part is choosing in a way that puts you noticeably ahead of the unidirectional allocator re: what problems you can solve, without putting excessive mental load on yourself. I've found a pattern of "long-lived allocations on one end, short-lived allocations on the other" to work well here (which, yes, doesn't always coincide with the numerous vs. infrequent axis mentioned in my previous comment).
> The mem array is divided into two regions that are allocated separately, but the dividing line between these two regions is not fixed; they grow together until finding their “natural” size in a particular job. Locations less than or equal to lo_mem_max are used for storing variable-length records consisting of two or more words each. […] Locations greater than or equal to hi_mem_min are used for storing one-word records…
(Different allocators are used for the two regions and neither seems to be a bump allocator, so it's probably not very relevant to this thread, but I was reminded of it so just sharing…)
Ok, I get it now. It would add an extra ptr to the struct, but wouldn't be significant overhead.
I do wonder what benefit there is for you over just having two separate allocators, one for long term and one for short term. I imagine there could be benefits in very memory constrained scenarios.
BEAM (Erlang) uses something similar for process memory; a process gets a chunk of memory, heap grows up, stack grows down; when they meet, trigger GC, and if that doesn't reclaim enough, allocate a larger chunk of memory. More details if you're interested [1]. In general, I'd think anywhere that the combined size of two allocators should be a consideration, one going up and one going down would make a lot of sense.
Thats an interesting idea. I'm not sure I'm sold on it v.s. just having two seperate allocators and growing them seperately. The arena allocators I use take advantage of virtual memory to grow which might change my perception of the tradeoffs involved, as I wouldn't typically need to resize one of my allocators (you can just aggressively over-reserve memory and then only commit what is actually used).
In the "bump up" version you could remove both the checked_add branches and replace them with a single check at the end, making the amount of branches the same.
I think this doesn't work because `aligned + size` may wrap all the way around into the valid region again. For example if aligned == ptr + 1, and size is usize::MAX, we will end up with new_ptr == ptr and the allocation will wrongly succeed.
Interesting point. I modified my example to test what you described. I had to play with the compilation flags to get the allocs to not be optimized out and to not panic when the integer overflow happens, but otherwise I didn't change the logic. I'm pretty sure my implementation is correctly handling the case you mention, evidenced by it returning a null pointer.
No, just restrict the domain of the alignment input to like, u8. Maybe u16. Either way, it is easy to ensure your bump allocation space is far enough away from SIZE_MAX.
That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr <= new_ptr < end, seemingly a valid result, but actually with not enough space.
It matters because if the allocator cannot allocate a given amount, it should reliably return NULL to iform the caller that the allocation failed, not return a random invalid pointer that's not usable, which will lead to undefined behavior.
For some uses it might be reasonable to restrict the size input to compile-time constants, which can be verified at compile time. Or you could have a newtype with a checked safe constructor and an unchecked unsafe constructor, which allows bypassing the overhead when you know the sizes are reasonable. On 64-bit systems, it is reasonable in many domains to restrict allocation size to u32. There are lots of possible ways to approach this without falling back to "tolerate any usize input."
Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.
I think it would be pretty reasonable to have an input type for that parameter that isn't a full usize and is instead some more restricted type that can only represent smaller values. The alignment parameter could be, like, u8, or maybe u16.
It's also too limiting: with u8 you can't ask for page-aligned data, and with u16 not for hugepage-aligned data. Granted, those aren't exactly prime use cases for a bump allocator, but it seems like poor design to limit the API unnecessarily.
