1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
use core::marker::PhantomPinned;
use core::pin::Pin;
use core::sync::atomic::{AtomicPtr, Ordering};
use critical_section as cs;
/// An atomic sorted linked list for the timer queue.
///
/// Atomicity is guaranteed using very short [`critical_section`]s, so this list is _not_
/// lock free, but it will not deadlock.
pub(crate) struct LinkedList<T> {
head: AtomicPtr<Link<T>>,
}
impl<T> LinkedList<T> {
/// Create a new linked list.
pub const fn new() -> Self {
Self {
head: AtomicPtr::new(core::ptr::null_mut()),
}
}
}
impl<T: PartialOrd + Clone> LinkedList<T> {
/// Pop the first element in the queue if the closure returns true.
pub fn pop_if<F: FnOnce(&T) -> bool>(&self, f: F) -> Option<T> {
cs::with(|_| {
// Make sure all previous writes are visible
core::sync::atomic::fence(Ordering::SeqCst);
let head = self.head.load(Ordering::Relaxed);
// SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
if let Some(head) = unsafe { head.as_ref() } {
if f(&head.val) {
// Move head to the next element
self.head
.store(head.next.load(Ordering::Relaxed), Ordering::Relaxed);
// We read the value at head
let head_val = head.val.clone();
return Some(head_val);
}
}
None
})
}
/// Delete a link at an address.
pub fn delete(&self, addr: usize) {
cs::with(|_| {
// Make sure all previous writes are visible
core::sync::atomic::fence(Ordering::SeqCst);
let head = self.head.load(Ordering::Relaxed);
// SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
let head_ref = if let Some(head_ref) = unsafe { head.as_ref() } {
head_ref
} else {
// 1. List is empty, do nothing
return;
};
if head as *const _ as usize == addr {
// 2. Replace head with head.next
self.head
.store(head_ref.next.load(Ordering::Relaxed), Ordering::Relaxed);
return;
}
// 3. search list for correct node
let mut curr = head_ref;
let mut next = head_ref.next.load(Ordering::Relaxed);
// SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
while let Some(next_link) = unsafe { next.as_ref() } {
// Next is not null
if next as *const _ as usize == addr {
curr.next
.store(next_link.next.load(Ordering::Relaxed), Ordering::Relaxed);
return;
}
// Continue searching
curr = next_link;
next = next_link.next.load(Ordering::Relaxed);
}
})
}
/// Insert a new link into the linked list.
/// The return is (updated head, address), where the address of the link is for use
/// with `delete`.
///
/// SAFETY: The pinned link must live until it is removed from this list.
pub unsafe fn insert(&self, val: Pin<&Link<T>>) -> (bool, usize) {
cs::with(|_| {
// SAFETY: This datastructure does not move the underlying value.
let val = val.get_ref();
let addr = val as *const _ as usize;
// Make sure all previous writes are visible
core::sync::atomic::fence(Ordering::SeqCst);
let head = self.head.load(Ordering::Relaxed);
// 3 cases to handle
// 1. List is empty, write to head
// SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
let head_ref = if let Some(head_ref) = unsafe { head.as_ref() } {
head_ref
} else {
self.head
.store(val as *const _ as *mut _, Ordering::Relaxed);
return (true, addr);
};
// 2. val needs to go in first
if val.val < head_ref.val {
// Set current head as next of `val`
val.next.store(head, Ordering::Relaxed);
// `val` is now first in the queue
self.head
.store(val as *const _ as *mut _, Ordering::Relaxed);
return (true, addr);
}
// 3. search list for correct place
let mut curr = head_ref;
let mut next = head_ref.next.load(Ordering::Relaxed);
// SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
while let Some(next_link) = unsafe { next.as_ref() } {
// Next is not null
if val.val < next_link.val {
// Replace next with `val`
val.next.store(next, Ordering::Relaxed);
// Insert `val`
curr.next
.store(val as *const _ as *mut _, Ordering::Relaxed);
return (false, addr);
}
// Continue searching
curr = next_link;
next = next_link.next.load(Ordering::Relaxed);
}
// No next, write link to last position in list
curr.next
.store(val as *const _ as *mut _, Ordering::Relaxed);
(false, addr)
})
}
}
/// A link in the linked list.
pub struct Link<T> {
pub(crate) val: T,
next: AtomicPtr<Link<T>>,
_up: PhantomPinned,
}
impl<T> Link<T> {
/// Create a new link.
pub const fn new(val: T) -> Self {
Self {
val,
next: AtomicPtr::new(core::ptr::null_mut()),
_up: PhantomPinned,
}
}
}
|
