Rollback Stack Allocator

The Rollback Stack allocator is a variant of the Stack allocator concept able to handle out-of-order free operations. I had devised it for the Odin test runner, as I needed the simplest possible custom memory allocator that could arbitrarily free data, in order to comply with the requirements of Odin’s memory Tracking_Allocator which this was to sit on top of.

The allocator keeps track of what entries have been set as free and only allows that memory to be used again when a contiguous block from the end has been freed, at which point it resets the pointer.

Its design works well with test suites, where most allocations and deallocations follow a triangular shape, but it has the added bonus of allowing out-of-order frees while still being able to recover the memory, so long as there exists a contiguous block of freed memory from the end, hence the name “rollback” stack allocator.

Imagine we have been running a program for a while with this allocator, and at one point, the memory usage looks like this:

The orange indicates allocated memory and the blue indicates memory marked as free. Any new allocations will happen at the tail end of our memory block.

Now let’s say we free the intervening allocations.

Having freed a contiguous block of memory from the tail end, the allocator is able to reclaim all of that memory, resulting in this layout:

The simplicity in this design is because we only reclaim the memory when we have this kind of pattern. We do not have to worry about re-distributing memory that has been freed, finding appropriately-sized blocks, or dealing with fragmentation. The rollback stack allocator implementation in Odin is less than 400 lines long and only slightly more complicated than a regular stack allocator.

Normally, an arena allocator would be sufficient for the task, but I had wanted to track the memory usage of tests in order to evaluate leaks in all the APIs under coverage, and Odin’s memory tracker requires the allocator that it watches to actually free the underlying memory – or at least report that it did.

Odin’s arena allocators return a Mode_Not_Implemented error any time a free call is made, which makes sense. In retrospect, I could have made an arena allocator instead that just lied to the memory tracker. That could’ve been fine in most cases, but there’s still the possibility of a test allocating memory, freeing it, and allocating again in a loop to the extent that it unduly taxed the machine.

A couple months out from the overhaul of the test runner, and I still think it was the best fit for the job, considering the circumstances.