Intrusive Data Structures

Intrusive data structures are specialized data structures where elements themselves contain the metadata required for their organization. This contrasts with non-intrusive data structures, where the metadata is stored in an external wrapper (e.g., a linked list node).

The presence of embedded metadata (i.e. pointer or references) means there is no wrapping, reducing memory overhead and allowing efficient manipulation as well as signaling to other elements. Given there are fewer layer of indirection, cache locality is also better

Tip

In contrast, an element in a non-intrusive Linked List cannot signal the other elements after a certain operations, because it doesn’t know it’s in the list

Attention

The data structure and its elements are tightly coupled, reducing generality compared to non-intrusive designs.

The Tokio runtime scheduler uses an intrusive linked list to manage its run queue. Tasks are enqueued and dequeued as part of managing task execution across multiple threads.

Since pushing (enqueue) operations only involve updating the next pointer of the last task and the queue’s tail, they are completely lock free. Popping tasks from the head requires a mutex to coordinate access between multiple consumers, ensuring safe removal and ownership transfer of tasks.

use std::ptr::null_mut;
 
struct Task {
    id: usize,
    next: *mut Task, // Pointer for queue linkage
}
 
impl Task {
    fn new(id: usize) -> Box<Self> {
        Box::new(Task { id, next: null_mut() })
    }
}
 
struct TaskQueue {
    head: *mut Task,
    tail: *mut Task,
}
 
impl TaskQueue {
    fn new() -> Self {
        TaskQueue {
            head: null_mut(),
            tail: null_mut(),
        }
    }
 
    // Enqueue a task at the tail
    fn enqueue(&mut self, task: &mut Task) {
        unsafe {
            task.next = null_mut();
            let task_ptr = task as *mut Task;
 
            if self.tail.is_null() {
                self.head = task_ptr;
                self.tail = task_ptr;
            } else {
                (*self.tail).next = task_ptr;
                self.tail = task_ptr;
            }
        }
    }
 
    // Dequeue a task from the head
    fn dequeue(&mut self) -> Option<*mut Task> {
        if self.head.is_null() {
            None
        } else {
            unsafe {
                let head = self.head;
                self.head = (*self.head).next;
 
                if self.head.is_null() {
                    self.tail = null_mut(); // Queue is now empty
                }
 
                (*head).next = null_mut(); // Clear linkage
                Some(head)
            }
        }
    }
}

Example Usage

fn main() {
    let mut queue = TaskQueue::new();
 
    // Create tasks
    let mut task1 = Task::new(1);
    let mut task2 = Task::new(2);
    let mut task3 = Task::new(3);
 
    // Enqueue tasks
    queue.enqueue(&mut *task1);
    queue.enqueue(&mut *task2);
    queue.enqueue(&mut *task3);
 
    // Dequeue tasks and print their IDs
    while let Some(task_ptr) = queue.dequeue() {
        unsafe {
            println!("Dequeued task with ID: {}", (*task_ptr).id);
        }
    }
}

Output:

Dequeued task with ID: 1
Dequeued task with ID: 2
Dequeued task with ID: 3