ertrace/
ertrace.rs

1//! Singly linked list of `ErtraceLocation`s, with O(1) Drop to a global,
2//! lock-free free list.
3
4extern crate alloc;
5
6use crate::ertrace_location::ErtraceLocation;
7use alloc::boxed::Box;
8use core::ptr::NonNull;
9use core::sync::atomic::{AtomicPtr, Ordering};
10
11static FREE_LIST: AtomicPtr<ErtraceNode> = AtomicPtr::new(core::ptr::null_mut());
12
13fn try_take_from_free_list() -> Result<NonNull<ErtraceNode>, ()> {
14    loop {
15        let current_ptr = FREE_LIST.load(Ordering::Acquire);
16        // NOTE: this is safe because this pointer is either null or valid.
17        let node = if let Some(p) = unsafe { current_ptr.as_ref() } {
18            p
19        } else {
20            return Err(());
21        };
22        let new_ptr = node.next.load(Ordering::Relaxed);
23        if FREE_LIST.compare_and_swap(current_ptr, new_ptr, Ordering::Release) == current_ptr {
24            node.next.store(core::ptr::null_mut(), Ordering::Relaxed);
25            // NOTE: this is safe because the pointer is non-null if we reached here.
26            return Ok(unsafe { NonNull::new_unchecked(current_ptr) });
27        }
28    }
29}
30
31fn new_tail_node(data: &'static ErtraceLocation) -> NonNull<ErtraceNode> {
32    match try_take_from_free_list() {
33        Ok(mut node_ptr) => {
34            // NOTE: this is safe because the pointer is valid and globally unique.
35            unsafe { node_ptr.as_mut() }.data = data;
36            node_ptr
37        }
38        Err(()) => {
39            //TODO: alloc from arena
40            let node_ptr = Box::into_raw(Box::new(ErtraceNode {
41                next: AtomicPtr::new(core::ptr::null_mut()),
42                data,
43            }));
44            // NOTE: this is safe because the pointer is non-null.
45            unsafe { NonNull::new_unchecked(node_ptr) }
46        }
47    }
48}
49
50#[derive(Debug)]
51pub struct Ertrace {
52    head: NonNull<ErtraceNode>,
53    tail: NonNull<ErtraceNode>,
54}
55
56impl core::fmt::Display for Ertrace {
57    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
58        writeln!(f, "error return trace:")?;
59        for (i, location) in self.iter().enumerate() {
60            write!(f, "{:>5}: {}", i, location)?;
61        }
62        writeln!(f, "")
63    }
64}
65
66impl Ertrace {
67    pub fn new(data: &'static ErtraceLocation) -> Self {
68        let new_tail = new_tail_node(data);
69        Self {
70            head: new_tail,
71            tail: new_tail,
72        }
73    }
74
75    pub fn from_cause<T: Into<Ertrace>>(cause: T, data: &'static ErtraceLocation) -> Self {
76        let mut ertrace: crate::Ertrace = cause.into();
77        ertrace.push_back(data);
78        ertrace
79    }
80
81    pub fn push_back(&mut self, data: &'static ErtraceLocation) {
82        let new_tail = new_tail_node(data);
83        // NOTE: this is safe because
84        //   1) the pointer to this ErtraceNode is valid, and
85        //   2) we control access to the only other pointer to this ErtraceNode,
86        //   and can guarantee that it is not converted into a mutable reference while
87        //   this mutable reference exists.
88        unsafe { self.tail.as_mut() }
89            .next
90            .store(new_tail.as_ptr(), Ordering::Relaxed);
91        self.tail = new_tail;
92    }
93
94    pub fn iter(&self) -> ErtraceIter {
95        ErtraceIter {
96            ertrace: &self,
97            maybe_next_ptr: Some(self.head),
98        }
99    }
100}
101
102#[derive(Debug)]
103pub struct ErtraceIter<'a> {
104    #[allow(dead_code)]
105    ertrace: &'a Ertrace,
106    maybe_next_ptr: Option<NonNull<ErtraceNode>>,
107}
108
109impl<'a> Iterator for ErtraceIter<'a> {
110    type Item = &'static ErtraceLocation;
111    fn next(&mut self) -> Option<Self::Item> {
112        match self.maybe_next_ptr {
113            Some(next_ptr) => {
114                // NOTE: this is safe because the pointer is valid.
115                let node = unsafe { next_ptr.as_ref() };
116                self.maybe_next_ptr = NonNull::new(node.next.load(Ordering::Relaxed));
117                Some(node.data)
118            }
119            None => None,
120        }
121    }
122}
123
124#[derive(Debug)]
125struct ErtraceNode {
126    next: AtomicPtr<ErtraceNode>,
127    data: &'static ErtraceLocation,
128}
129
130impl Drop for Ertrace {
131    fn drop(&mut self) {
132        // NOTE: this is safe because
133        //   1) the pointer to this ErtraceNode is valid, and
134        //   2) we control access to the only other pointer to this ErtraceNode,
135        //   and can guarantee that it is not converted into a mutable reference while
136        //   this mutable reference exists.
137        let tail = unsafe { self.tail.as_mut() };
138        loop {
139            let old_next = FREE_LIST.load(Ordering::Acquire);
140            tail.next.store(old_next, Ordering::Relaxed);
141            if FREE_LIST.compare_and_swap(old_next, self.head.as_ptr(), Ordering::Release)
142                == old_next
143            {
144                return;
145            }
146        }
147    }
148}
ertrace/ertrace.rs

ertrace/
ertrace.rs
