Support for statically allocating tasks (no_alloc usage)

[Dirbaio]

Motivation

It is currently possible to use async_task with no_std, but it requires having alloc available because tasks are dynamically allocated.

In memory-constrained environments, such as embedded microcontroller devices, it's often useful to statically declare everything and not have any dynamic allocator. The main advantage is that you have compile-time guarantees that your program will never run out of RAM (The linker knows how much RAM the target device has, and will error if all the static variables won't fit).

Generally in an embedded device the following kinds of tasks are present:

• tasks that start up at boot and run forever
• tasks that are started and stopped, but never run multiple instances concurrently
• tasks that run a bounded number of concurrent instances (usually small, 4-16 instances)

It is very rare that you want an arbitrary number of tasks of arbitrary types mixed together. You rarely have enough RAM for it, and it tends to cause fragmentation problems and unpredictable out of RAM errors.

It would be a huge boon for embedded if async_task allowed statically pre-allocating tasks.

Aditionally, this would be especially useful combined with #![feature(type_alias_impl_trait)] (rust-lang/rust#63063), which makes it possible to name the future types of async fns. (naming the type is needed so the user can declare the static variable containing the task)

API proposal

The API could be something like this

// maybe R is not needed
pub struct StaticTask<F, R, S, T> { /* storage for a raw task */ } 

impl StaticTask<F, R, S, T>
where
    F: Future<Output = R> + Send + 'static,
    R: Send + 'static,
    S: Fn(Task<T>) + Send + Sync + 'static,
    T: Send + Sync + 'static,
{
    // create a new StaticTask in "free" state
    // The bit pattern of the return value must be only zero bits and uninitialized bits, so
    // StaticTasks can be placed in the .bss section (otherwise they'd go into .data which wastes flash space)
    pub const fn new() -> Self { ... }

    // If self is in "free" state, change it to "used" state and initialize it with the given future, and return the task and joinhandle.
    // if self is in "used" state, return None.
    pub fn spawn<F, R, S, T>(&'static self, future: F, schedule: S, tag: T) -> Option<(Task<T>, JoinHandle<R, T>)> { .. } 
}

This would be used like this

static MY_TASK: StaticTask<MyFuture, MyFuture::Output, ??, ()> = StaticTask::new()

fn main() {
   if let Some(t, j) = MY_TASK.spawn(my_do_something(), |t| { /* schedule t)}, ()) {
      t.schedule()
   } else {
      // spawn failed because the static task is already running, return some error
   }
}

When the task is no longer running (ie when it would be freed if it was dynamically allocated), the StaticTask is returned to "free" state, so it can be used by .spawn() again.

This would make it possible to mix statically-allocated and dynamically-allocated tasks in the same executor.

Having so many generic arguments in StaticTask is somewhat ugly because the user has to manually specify them, but this is something executor libraries could abstract (ie export a newtype so you only have to set F). A higher-level executor API could be like this:

static MY_TASK: my_executor::Task<MyFuture> = my_executor::Task::new()

fn main() {
  // dynamically allocate
  my_executor::spawn(my_do_something());

  // statically allocate
  MY_TASK.spawn(my_do_something());

  my_executor::run()
}

Alternatives

Add an API where the user can specify a custom allocator for spawning, via some trait. Still, th library would still have to export a type so that user code can know what's the size required for a RawTask of a given future, so they can statically allocate buffers of the right size.

Hmm, this looks like a really really difficult problem to solve. async_task::Task would have to be parametrized over the future type and the schedule function type.

I kind of believe that even if we managed to somehow change the API like this, in the end it would be so restrictive that it wouldn't be all that useful for embedded systems. :/

It might be easier to build a new crate that is similar to async-task, but designed for allocation-less systems... I'm saying this because the whole point of async-task is to make building executors easier, but specifically the kind of executors that erase the future type and spawn a lot of different tasks.

[Dirbaio]

async_task::Task would have to be parametrized over the future type and the schedule function type.

Not necessarily, what needs to be parametrized is the StaticTask that you statically allocate for storage, not Task.. You call .spawn() on it and get back an instance of the exact same Task type as now (type-erased), except it points to a buffer inside the StaticTask instead of a heap allocation.

Task could have a new bit in state to store whether its buffer is dynamic or static and do the right thing on deallocation.

I've built a proof of concept of the "statically allocate tasks" idea here: https://github.com/Dirbaio/static-executor . My Task type is equivalent to StaticTask in the API sketch above.

Unfortunately it's not as powerful as async_task since there's no Task equivalent for users to "build their own" executors, it's an executor itself. That simplifies the design hoever (for example, allows using an intrusive list for the task queue instead of having to allocate a deque).

Out of curiosity, what's the reason async_task does the Task layout manually instead of using unions? I was going to implement JoinHandles in async_executor as an union of the future and the result, and I'm curious if there's some scary pitfall I'm not seeing.

I've built a proof of concept of the "statically allocate tasks" idea here: https://github.com/Dirbaio/static-executor . My Task type is equivalent to StaticTask in the API sketch above.

Interesting -- the #[task] attribute looks quite nice! Wow, never thought of that...

Out of curiosity, what's the reason async_task does the Task layout manually instead of using unions? I was going to implement JoinHandles in async_executor as an union of the future and the result, and I'm curious if there's some scary pitfall I'm not seeing.

It's for performance - the idea was to have the best possible performance with as few atomic operations as possible and using as little memory as possible. But, I'm doubting whether it was worth it. I'm considering rewriting async-task in a simpler way with less unsafe code and fewer crazy optimizations.

I don't have much more to add right now... will need to think about this a bit more.

[reevesPAC]

Ok thank you, @Dirbaio I got it.

[notgull]

Probably could be solved via #24