I want to implement a node-based data structure (suppose, for example, that it is a linked list), where the presence of each node in the list is restricted by the lifetime of some pinned object; when the object is dropped, it removes its node from the data structure. (The motivation here is an internal detail of an embedded async/await task wakeup system, which will be relevant later.) This naturally requires a good amount of internal unsafe code but should result in a safe API.
A naive approach using dynamically allocated nodes is as follows.
Code
#![no_std]
extern crate alloc;
extern crate critical_section;
use alloc::boxed::Box;
use core::{
marker::PhantomPinned,
ptr::NonNull,
};
use critical_section::CriticalSection;
struct List<T: Send + Sync> {
head: *mut Node<T>,
}
struct Node<T: Send + Sync> {
/// Pointer to pointer to this node; either points to [`List::head`] or
/// [`Self::next`].
prev_ptr: NonNull<*mut Node<T>>,
/// Pointer to next node; null if empty.
next: *mut Node<T>,
value: T,
}
struct Entry<T: Send + Sync> {
my_node: NonNull<Node<T>>,
_pin: PhantomPinned,
}
impl<T: Send + Sync> Entry<T> {
pub fn new(value: T, list: &mut List<T>, _cs: CriticalSection) -> Self {
// Insert a node at the head of the list.
let node = Box::new(Node {
prev_ptr: NonNull::from(&mut list.head),
next: list.head,
value,
});
let node = Box::leak(node);
if let Some(head) = unsafe { list.head.as_mut() } {
head.prev_ptr = NonNull::from(&mut node.next);
}
list.head = node as _;
Entry {
my_node: NonNull::from(node),
_pin: PhantomPinned,
}
}
pub fn access(&mut self, _cs: CriticalSection) -> &mut T {
&mut unsafe { self.my_node.as_mut() }.value
}
}
impl<T: Send + Sync> Drop for Entry<T> {
fn drop(&mut self) {
critical_section::with(|_cs| unsafe {
let node = self.my_node.as_mut();
// Remove the node from the list.
node.prev_ptr.write(node.next);
if let Some(next) = node.next.as_mut() {
next.prev_ptr = node.prev_ptr;
}
// End the scope of `node` to ensure no aliasing.
#[allow(dropping_references)]
drop(node);
// Destruct and deallocate the node.
drop(Box::from_raw(self.my_node.as_ptr()));
});
}
}
The issue is, though, that we shouldn't need dynamic memory allocation here; if we correctly design an API around Entry being pinned, we should be able to put Node inside Entry directly (i.e., have my_node not be a pointer). Avoiding any dynamic memory allocation, especially within a critical path, would be very helpful for embedded systems.
However, what type can we actually make my_node in that case? Initially, I went with just Node<T>, but then I realized this violated aliasing rules, since plausibly an exclusive reference to the Entry<T> (or to a data structure in which it is contained) may exist when the list is being traversed (not shown in the above code). I then thought of making it UnsafeCell<Node<T>>, but I realized that this does nothing in the case where we have an exclusive reference; UnsafeCell::get_mut is safe, after all.
As I noted earlier, the motivation here is part of a wakeup primitive in an embedded async/await executor; thus, I am partially constrained by needing to fit into the Future API. This means that things will interact with Entry via a pinned exclusive reference; thus, I cannot force the API to restrict everything to shared references. Essentially, it feels like what I need is some sort of interior immutability or interior aliasability, so I can avoid breaking aliasing rules without unnecessary indirection, but I don't see how to do this within the constraints imposed by the Future API.
For reference, here is a C++ implementation of this idea with a usage example; obviously, much more care is needed in this case by a library consumer to enusre it is being used correctly, which is a big part of why I prefer using Rust, but I can't figure out how to replicate this in Rust without dynamic memory allocaiton.
Code
#include <cassert>
#include <iostream>
#include <optional>
#include <utility>
template<class T>
struct Node {
Node<T> **prev_ptr;
Node<T> *next;
T value;
};
template<class T>
struct List {
Node<T> *head = nullptr;
void print() {
std::cout << "List:";
auto cur = head;
while (cur) {
std::cout << " " << cur->value;
cur = cur->next;
}
std::cout << std::endl;
}
};
template<class T>
class Entry {
std::optional<Node<T>> my_node;
public:
void insert_into(T &&value, List<T> &list) {
assert(!my_node);
my_node.emplace(Node<T>{&list.head, list.head, std::move(value)});
if (list.head) {
list.head->prev_ptr = &my_node->next;
}
list.head = &*my_node;
}
T *operator*() {
return &my_node->value;
}
~Entry() {
// Assume this uses some sort of critical section to ensure atomicity of
// interaction with the overall list.
if (my_node) {
*my_node->prev_ptr = my_node->next;
if (my_node->next) {
my_node->next->prev_ptr = my_node->prev_ptr;
}
}
}
};
/*
Output:
List:
List: 5
List: 10 5
List: 5
List:
*/
int main() {
List<int> l;
l.print();
{
Entry<int> e1;
e1.insert_into(5, l);
l.print();
{
Entry<int> e2;
e2.insert_into(10, l);
l.print();
}
l.print();
}
l.print();
return 0;
}
Questions:
- Is this currently possible to do this soundly in Rust (even with
unsafecode)? If so, how? - If not, would it be reasonable to propose a new special (i.e.,
lang_item) cell type, sayAliasCell, such that&mut AliasCell<T>is approximately&UnsafeCell<T>(or alternatively,*mut T)? I know this is would be a fairly intrusive addition, but I don't see how else to enable this sort of data structure without dynamic memory allocation.