The critical question is how you define a heap, and how object lifetimes can be bounded.
I understand a heap as a store of objects with dynamic lifetimes – once the lifetime of an object ends, its storage can be reused for other objects. For example, in the C standard library the malloc() function creates an object and the free() function ends the lifetime of an object. With garbage collection, the GC algorithm detects unreferenced objects on its own and then ends their lifetime. While heaps are very flexible, managing free and in-use chunks of memory requires extra metadata and extra effort.
Other stores such as stacks constrain the lifetime of objects. With a stack, the lifetimes are strictly LIFO – all younger objects must end their lifetime before the lifetime of older objects can end. This is a perfect fit for call stacks that store temporary variables until a function returns. It is also possible to have an append-only stack that only adds new objects but never frees any memory for reuse – which is extremely time-efficient but means that eventually all available memory will be used up.
You have provided the following C++ snippet of a code with complicated object lifetimes:
Task SetupIsrAsync()
{
TaskCompletionSource tcs;
c_style_callback_to_isr_registration([tcs]{ tcs.SetResult(); });
return tcs.Task;
}
In C++, the object tcs has automatic storage duration, i.e. the lifetimes continues until the end of the scope. The lambda creates its own copy, which lives for the duration of the lambda. A part of tcs is copied and returned. Due to the use of copies, all lifetime bounds are satisfied.
A way to handle this in C++ without copies is to “leak memory”, i.e. to create an object that lives until the end of the program. For example:
Task& SetupIsrAsync()
{
auto tcs = new TaskCompletionSource(); // new but no delete
c_style_callback_to_isr_registration([tcs]{ tcs->SetResult(); });
return tcs->Task;
}
But, use of such immortal objects wouldn't involve a heap as per the above definition.
If only one such task completion source can exist globally, then a variable with static lifetime can be used equivalently:
Task& SetupIsrAsync()
{
static TaskCompletionSource tcs; // lives until end of program
c_style_callback_to_isr_registration([&tcs]{ tcs.SetResult(); });
return tcs.Task;
}
A heap- or GC-based approach that frees the TCS when it's no longer needed might look like:
shared_ptr<Task> SetupIsrAsync()
{
auto tcs = make_shared<TaskCompletionSource>();
c_style_callback_to_isr_registration([tcs]{ tcs->SetResult(); });
return shared_ptr<Task>(tcs, &tcs->Task); // aliasing shared poiner
}
After this function returns, there are two shared owners of the tcs object. When the last owner ends its lifetime, the lifetime of the tcs object is ended. However, this shared pointer contains additional metadata to count active owners.
Until now, I'm assuming that c_style_callback_to_isr_registration() takes ownership of a callback and keeps it potentially until the end of the program, in particular if the lifetime of the callback is dynamic so that it might live that long.
If this registration function guarantees that it only needs the object for some statically checkable duration, then other solutions become possible as well. For this example, let's switch to Rust notation. Let's assume the registration function only needs to hold the callback for at most the lifetime 'a. Then we might have:
// the callback is a function that is valid for at least 'a
fn c_style_callback_to_isr_registration(callback: impl Fn() + 'a) { ... }
fn setup_isr_async(alloc: SomeAllocator<'a>) -> &'a Task {
// this lifetime-bounded allocator creates an object that is valid for at least 'a
let tcs: &'a TaskCompletionSource = alloc.allocate(TaskCompletionSource::new());
c_style_callback_to_isr_registration(|| tcs.set_result());
return &tcs.task;
}
Then, the caller can provide some allocator that guarantees a suitable minimum lifetime of objects. If the lifetime 'a happens to be the lifetime of the caller's local variables, then the allocator might be able to use storage on the call stack.
(But in reality, Rust's concept of lifetimes is probably not sufficiently expressive to do this.)
How could such storage semantics be implemented in practice?
Given a non-recursive function context() that bounds the lifetime of the registered callback and therefore the lifetime of the task completion source, we might have a call stack
...
#2 context()
#1 some_other_function()
#0 setup_isr_async()
Then, a downwards-growing stack might contain the following data:
...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V
We could now store the task completion source at the end of this stack:
...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
| TaskCompletionSource tcs
V
When the setup function returns, there will be a hole in the stack:
...
| context frame
| context frame
| context frame
| (empty)
| (empty)
| (empty)
| (empty)
| TaskCompletionSource tcs
V
The easiest way to handle this would be to note the maximum stack offset in the allocator (a tiny bit of dynamic data), and then in the context frame skip back to that maximum extent (so basically using the C alloca() function). For example, if context() calls another_function(), then we might get the following stack layout that just wastes the empty space:
...
| context frame
| context frame
| context frame
| (empty)
| (empty)
| (empty)
| (empty)
| TaskCompletionSource tcs
| another_function frame
| another_function frame
V
But this is extremely restrictive. To do that, we need the following constraints:
- the maximum stack usage of all functions that perform this kind of allocation must be statically known
- this prohibits recursion
- this prohibits dynamic linking, function pointers, OOP, or other indirect calls
This scheme allows a dynamic amount of objects to be created. If the number of allocations is statically known, then space could be reserved by the caller and we might get a stack layout (just before the tcs is allocated) like this:
...
| context frame
| context frame
| context frame
| (reserved space for allocation)
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V
But that is an extremely tight requirement.
Back to the case that the lifetime of allocated objects is bounded but the number of objects to be allocated is not statically known. We don't have to leave holes in the stack, and don't need to prohibit recursion. For essentially the same amount of metadata + overhead but with less stringent requirements, it would be possible to support those allocations via a second stack just for data. Here would be an example of a data stack in the same memory space that grows towards the call stack:
...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V
...
^
| TaskCompletionSource tcs
...
Since we defined that the TCS cannot outlive the lifetime of the context() invocation, the code for context() could contain code to clean up all allocations performed by its child functions:
static char* data_stack = ...;
void context() {
char* old_data_stack = data_stack;
// call that eventually allocates on the data stack
some_other_function();
// call that executes while the allocated objects remain alive
another_function();
// end lifetime of all those allocations
data_stack = old_data_stack
}
So yes, your idea kind of works for very specific constellations, if you can somehow bound the lifetime of objects, and if we define this kind data storage to not be a true heap.
In practice, you'll find that few interesting problems have such clear bounds.
Good examples where allocations are clearly bounded include graph problems where the entire graph can be deallocated once a query has been answered, and request handlers in a web server where no object outlives the response (all data that outlives the request/response must be externalized, e.g. into a database). But for exactly those problems, generational GC will also perform very well (if enough memory overhead can be allowed).
Examples were it's extremely difficult to find lifetime bounds include any software with a long-term mutable in-memory data model, for example GUI applications.
