Module lilos::list

👎Deprecated since 1.2.0: please move to the lilos-list crate

Doubly-linked intrusive lists for scheduling and waking (old version).

Please use the lilos_list crate instead. It’s better in literally every way.

A List<T> keeps track of nodes (of type Node<T>) that each contain some value T. The list is kept in sorted order by comparing the Ts:

• List::insert_and_wait traverses the list to insert the Node in its proper place, and then waits for the node to be kicked back out.
• List::wake_thru starts at one end and removes every Node with a value less than or equal to a threshold.

The sort order is used to order things by timestamps, but you may find other uses for it.

If you just want to keep things in a list, and don’t care about order or need to associate a timestamp, simply use List<()>. This disables the sorting and removes the order-related fields from both the list and node. Such a list will track its nodes in the order in which they were inserted.

Using as a timer list, or other type of ordered list

• Create a List<YourTimestamp>.

• To track a waiter in the list, create a Node<YourTimestamp> and pass it to List::insert_and_wait. The node will be inserted in timestamp order, after any existing nodes with the same timestamp. Note that you must await (or poll) the future produced by insert_and_wait for the node to actually join the list in its proper place.

• At some future point, wake all nodes in a timestamp range by using either List::wake_while or, as a convenience for writing timers, List::wake_thru.

Using as a wait queue

• Create a List<()>.

• To track a waiter in the list, create a Node<()> and pass it to List::insert_and_wait. The node will be inserted at the tail of the list. Note that you must await (or poll) the future produced by insert_and_wait for the node to actually join the list in its proper place.

• To wake one waiter, use List::wake_one.

• To wake a series of waiters, us List::wake_while.

Pinning

Because List and Node create circular, self-referential data structures, all operations require that they be pinned. Because we don’t use the heap, we provide ways to create and use pinned data structures on the stack. This is, unfortunately, kind of involved – but the create_node! and create_list! convenience macros help.

Here is an example of creating a Node, since that’s what user code creates most often; see the sources for mutex for a real-world example.

// This creates a local variable called "my_node"
os::create_node!(my_node, ());

// Join a wait list
wait_list.insert_and_wait(my_node.as_mut()).await;

// All done, my_node can be dropped

Creating a list or node is a three-step process. We’ll use Node as a running example here, but the same applies to List.

1. Create a partially-initialized version using Node::new and extract it from the ManuallyDrop container. This is unsafe, because the object you’re now holding will dereference bogus pointers if dropped. This makes it very important to proceed to the next two steps without doing anything else, particularly anything that could panic.

2. Put the Node in its final resting place (which may be a local, or might be a field of a struct, etc.) and pin it. The pin! macro makes doing this on the stack easier.

3. Finish setting it up by calling Node::finish_init.

While each of these steps is unsafe, if you do them in sequence without panicking, the result can be used safely – and so the create_node! and create_list! macros themselves are safe.

(These operations must be macros, not functions, because we can’t return an object by-value once it’s pinned.)

So, with that in mind, the fully-manual version of the example above reads as follows:

// Create a partially initialized node, pinned on the stack.
//
// Safety: this is safe as long as we fulfill the rest of the conditions
// required by Node::new before doing anything that could result in dropping
// the node, including `panic!` or `await`.
let mut my_node = core::pin::pin!(unsafe {
    core::mem::ManuallyDrop::into_inner(
        os::list::Node::new((), os::exec::noop_waker())
    )
});
// Finish initialization.
//
// Safety: this discharges the rest of the obligations laid out by
// Node::new.
unsafe {
    os::list::Node::finish_init(my_node.as_mut());
}

// Join a wait list
wait_list.insert_and_wait(my_node.as_mut()).await;

// All done, my_node can be dropped

The metadata (M) parameter

List<T> is actually List<T, M>, but the M parameter defaults to () and is ignored by most users.

M is for metadata, and allows you to associate an arbitrary, application-specific piece of data with each node in the list. For instance, if a wait queue distinguishes between different kinds of waiters, you could declare an enum listing the kinds, and use that as the metadata parameter.

Metadata is available for inspection in the List::wake_one_if and List::wake_while operations, through the Node::meta function.

How is this safe?

The List API relies on blocking for safety. Because insert_and_wait takes control away from the caller until the node is kicked back out of the list, it is borrowing the &mut Node for the duration of its membership in the list. If the API were instead insert, we’d return to the caller, who is still holding a &mut Node – a supposedly exclusive reference to a structure that is now also reachable through the List!

This is why there is no insert operation, or a take operation that returns a node – both operations would compromise memory safety.

Structs

• ListDeprecated
  A list of Nodes.
• NodeDeprecated
  A member of a list.