Crate futures_intrusive

Synchronization primitives and utilities based on intrusive collections.

This crate provides a variety of Futures-based and async/await compatible types that are based on the idea of intrusive collections:

• Channels in a variety of flavors:
  • Oneshot
  • Multi-Producer Multi-Consumer (MPMC)
  • State Broadcast
• Synchronization Primitives:
  • Manual Reset Event
  • Mutex
  • Semaphore
• A timer

Intrusive collections?

In an intrusive collection, the elements that want to get stored inside the collection provide the means to store themselves inside the collection. E.g. in an intrusive linked list, each element that gets stored inside the list contains a pointer field that points to the next list element. E.g.

// The element which is intended to be stored inside an intrusive container
struct ListElement {
   data: u32,
   next: *mut ListElement,
}

// The intrusive container
struct List {
    head: *mut ListElement,
}

The advantage here is that the intrusive collection (here: the list) requires only a fixed amount of memory. In this case it only needs a pointer to the first element.

The list container itself has a fixed size of a single pointer independent of the number of stored elements.

Intrusive lists are often used in low-level code like in operating system kernels. E.g. they can be used for storing elements that represent threads that are blocked and waiting on queue. In that case the stored elements can be on the call stack of the caller of each blocked thread, since the call stack won’t change as long as the thread is blocked.

Application in Futures

This library brings this idea into the world of Rusts Futures. Due to the addition of Pinning, the address of a certain Future is not allowed to change between the first call to poll() and when the Future is dropped. This means the data inside the Future itself can be inserted into an intrusive container. If the the call to Future::poll() is not immedately ready, some parts of the Future itself are registered in the type which yielded the Future. Each Future can store a Waker. When the original type becomes ready, it can iterate through the list of registered Futures, wakeup associated tasks, and potentially remove them from its queue.

The result is that the future-yielding type is not required to copy an arbitrary number of Waker objects into itself, and thereby does not require dynamic memory for this task.

When a Future gets destructed/dropped, it must make sure to remove itself from any collections that refer to it to avoid invalid memory accesses.

This library implements common synchronization primitives for the usage in asychronous code based on this concept.

The implementation requires the usage of a fair chunk of unsafe annotations. However the provided user-level API is intended to be fully safe.

Features of this library

The following types are currently implemented:

• Channels (oneshot and multi-producer-multi-consumer)
• Synchronization primitives (async mutexes and events)
• Timers

Design goals for the library

• Provide implementations of common synchronization primitives in a platform independent fashion.
• Support no-std environments. As many types as possible are also provided for no-std environments. The library should boost the ability to use async Rust code in environments like:
  • Microcontrollers (RTOS and bare-metal)
  • Kernels
  • Drivers
• Avoid dynamic memory allocations at runtime. After objects from this library have been created, they should not require allocation of any further memory at runtime. E.g. they should not need to allocate memory for each call to an asynchronous function or each time a new task accesses the same object in parallel.
• Offer familiar APIs. The library tries to mimic the APIs of existing Rust libraries like the standard library and futures-rs as closely as possible.

Non goals

• Provide IO primitives (like sockets), or platform specific implementations.
• Reach the highest possible performance in terms of throughput and latency. While code in this library is optimized for performance, portability and deterministic memory usage are more important goals.
• Provide future wrappers for platform-specific APIs.

Local, Non-local and shared flavors

The library provides types in a variety of flavors:

• A local flavor (e.g. channel::LocalChannel)
• A non-local flavor (e.g. channel::Channel)
• A shared flavor (e.g. channel::shared::Sender)
• A generic flavor (e.g. channel::GenericChannel and channel::shared::GenericSender)

The difference between these types lie in their thread-safety. The non-local flavors of types can be accessed from multiple threads (and thereby also futures tasks) concurrently. This means they implement the Sync trait in addition to the Send trait. The local flavors only implement the Send trait.

Local flavor

The local flavors will require no internal synchronization (e.g. internal Mutexes) and can therefore be provided for all platforms (including no-std). Due the lack of required synchronization, they are also very fast.

It might seem counter-intuitive to provide synchronization primitives that only work within a single task. However there are a variety of applications where these can be used to coordinate sub-tasks (futures that are polled on a single task concurrently).

The following example demonstrates this use-case:

async fn async_fn() {
    let event = LocalManualResetEvent::new(false);
    let task_a = async {
        // Wait for the event
        event.wait().await;
        // Do something with the knowledge that task_b reached a certain state
    };
    let task_b = async {
        // Some complex asynchronous workflow here
        // ...
        // Signal task_a
        event.set();
    };
    join!(task_a, task_b);
}

Non-local flavor

The non-local flavors can be used between arbitrary tasks and threads. They use internal synchronization for this in form of an embedded Mutex of parking_lot::Mutex type.

The non-local flavors are only available in alloc environments.

Shared flavor

For some types a shared flavor is provided. Non-local flavors of types are Sync, but they still can only be shared by reference between various tasks. Shared flavors are also Sync, but the types additionally implement the Clone trait, which allows duplicating the object, and passing ownership of it to a different task. These types allow avoiding references (and thereby lifetimes) in some scenarios, which makes them more convenient to use. The types also return Futures which do not have an associated lifetime. This allows using those types as implementations of traits without the need for generic associated types (GATs).

Due to the requirement of atomic reference counting, these types are currently only available for alloc environments.

Generic flavor

The generic flavors of provided types are parameterized around a lock_api::RawMutex type. These form the base for the non-local and shared flavors which simply parameterize the generic flavor in either a non-thread-safe or thread-safe fashion.

Users can directly use the generic flavors to adapt the provided thread-safe types for use in no-std environments.

E.g. by providing a custom lock_api::RawMutex implementation, the following platforms can be supported:

• For RTOS platforms, RTOS-specific mutexes can be wrapped.
• For kernel development, spinlock based mutexes can be created.
• For embedded development, mutexes which just disable interrupts can be utilized.

Relation to types in other libraries

Other libraries (e.g. futures-rs and tokio) provide many primitives that are comparable feature-wise to the types in this library.

The most important differences are:

• This library has a bigger focus on no-std environments, and does not only try to provide an implementation for alloc or std.
• The types in this library do not require dynamic memory allocation for waking up an arbitrary number of tasks waiting on a particular Future. Other libraries typically require heap-allocated nodes of growing vectors for handling a varying number of tasks.
• The Futures produced by this library are all !Unpin, which might make them less ergonomic to use.

Modules

buffer

Buffer types

channel

Asynchronous channels.

sync

Asynchronous synchronization primitives based on intrusive collections.

timer

Asynchronous timers.