fuchsia_rcu_collections/
rcu_intrusive_list.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#![warn(unsafe_op_in_unsafe_fn)]
6
7use fuchsia_rcu::subtle::{RcuPtr, RcuPtrRef};
8use fuchsia_rcu::{RcuDroppable, RcuReadScope};
9
10/// `Link` is an intrusive structure in a doubly-linked list.
11///
12/// Links are address-sensitive and cannot be moved once inserted into a list.
13#[derive(Debug, RcuDroppable)]
14pub struct Link {
15    /// The next node in the list.
16    ///
17    /// This field can be used to traverse the list within an RcuReadScope.
18    next: RcuPtr<Link>,
19
20    /// The previous node in the list.
21    ///
22    /// This pointer cannot be used without external synchronization.
23    prev: RcuPtr<Link>,
24}
25
26impl Default for Link {
27    fn default() -> Self {
28        Self { next: RcuPtr::null(), prev: RcuPtr::null() }
29    }
30}
31
32/// Returns the container of a given field.
33///
34/// # Safety
35///
36/// The pointer must point to the given field in a valid instance of the container.
37#[macro_export]
38macro_rules! container_of {
39    ($ptr:expr, $container:path, $field:ident) => {{ $ptr.sub_byte_offset::<$container>(memoffset::offset_of!($container, $field)) }};
40}
41
42/// Returns the field of a given container.
43///
44/// # Safety
45///
46/// The pointer must point to a valid instance of the container.
47#[macro_export]
48macro_rules! field_of {
49    ($ptr:expr, $container:path, $field:ident, $field_type:ty) => {{ $ptr.add_byte_offset::<$field_type>(memoffset::offset_of!($container, $field)) }};
50}
51
52#[macro_export]
53macro_rules! rcu_list_adapter {
54    ($node:ty, $link:ident) => {
55        fn to_link(
56            node: fuchsia_rcu::subtle::RcuPtrRef<'_, $node>,
57        ) -> fuchsia_rcu::subtle::RcuPtrRef<'_, Link> {
58            if node.is_null() {
59                return fuchsia_rcu::subtle::RcuPtrRef::null();
60            }
61            // SAFETY: The pointer is valid and points to the given field.
62            unsafe { $crate::field_of!(node, $node, $link, Link) }
63        }
64
65        fn from_link(
66            link: fuchsia_rcu::subtle::RcuPtrRef<'_, Link>,
67        ) -> fuchsia_rcu::subtle::RcuPtrRef<'_, $node> {
68            if link.is_null() {
69                return fuchsia_rcu::subtle::RcuPtrRef::null();
70            }
71            // SAFETY: The pointer is valid and points to the given field.
72            unsafe { $crate::container_of!(link, $node, $link) }
73        }
74    };
75}
76
77pub use container_of;
78pub use field_of;
79pub use rcu_list_adapter;
80
81pub trait RcuListAdapter<T> {
82    /// Returns a pointer to the Link embedded in a Node.
83    fn to_link(node: RcuPtrRef<'_, T>) -> RcuPtrRef<'_, Link>;
84
85    /// Returns a pointer to the Node containing the given Link.
86    fn from_link(link: RcuPtrRef<'_, Link>) -> RcuPtrRef<'_, T>;
87}
88
89#[derive(Debug, RcuDroppable)]
90pub struct RcuIntrusiveList<T, A: RcuListAdapter<T>> {
91    /// The first element of the list, if any.
92    ///
93    /// This field can be used to traverse the list within an RcuReadScope.
94    head: RcuPtr<Link>,
95
96    /// The last element of the list, if any.
97    ///
98    /// This pointer cannot be used without external synchronization.
99    tail: RcuPtr<Link>,
100
101    _marker: std::marker::PhantomData<(T, A)>,
102}
103
104impl<T, A: RcuListAdapter<T>> Default for RcuIntrusiveList<T, A> {
105    fn default() -> Self {
106        Self::new(RcuPtr::null(), RcuPtr::null())
107    }
108}
109
110impl<T, A: RcuListAdapter<T>> RcuIntrusiveList<T, A> {
111    /// Creates a new list with the given head and tail.
112    pub(crate) fn new(head: RcuPtr<Link>, tail: RcuPtr<Link>) -> Self {
113        Self { head, tail, _marker: std::marker::PhantomData }
114    }
115
116    /// Pushes a new element to the front of the list.
117    ///
118    /// # Safety
119    ///
120    /// Requires external synchronization to exclude concurrent writers.
121    pub unsafe fn push_front<'a>(&self, scope: &'a RcuReadScope, data: RcuPtrRef<'a, T>) {
122        let link_ptr = A::to_link(data);
123        let link = link_ptr.as_ref().unwrap();
124        let head_ptr = self.head.read(&scope);
125        if let Some(head) = head_ptr.as_ref() {
126            head.prev.assign_ptr(link_ptr);
127            link.next.assign_ptr(head_ptr);
128        } else {
129            self.tail.assign_ptr(link_ptr);
130        }
131        self.head.assign_ptr(link_ptr);
132    }
133
134    /// Pushes a new element to the back of the list.
135    ///
136    /// # Safety
137    ///
138    /// Requires external synchronization to exclude concurrent writers.
139    pub unsafe fn push_back<'a>(&self, scope: &RcuReadScope, data: RcuPtrRef<'a, T>) {
140        let link_ptr = A::to_link(data);
141        let link = link_ptr.as_ref().unwrap();
142        let tail_ptr = self.tail.read(&scope);
143        if let Some(tail) = tail_ptr.as_ref() {
144            link.prev.assign_ptr(tail_ptr);
145            tail.next.assign_ptr(link_ptr);
146        } else {
147            self.head.assign_ptr(link_ptr);
148        }
149        self.tail.assign_ptr(link_ptr);
150    }
151
152    /// Appends another list to the end of this list.
153    ///
154    /// # Safety
155    ///
156    /// Requires external synchronization to exclude concurrent writers.
157    pub unsafe fn append(&self, scope: &RcuReadScope, other: Self) {
158        let other_head_ptr = other.head.read(&scope);
159        if let Some(other_head) = other_head_ptr.as_ref() {
160            let tail_ptr = self.tail.read(&scope);
161            if let Some(tail) = tail_ptr.as_ref() {
162                tail.next.assign_ptr(other_head_ptr);
163                other_head.prev.assign_ptr(tail_ptr);
164            } else {
165                self.head.assign_ptr(other_head_ptr);
166            }
167            let other_tail_ptr = other.tail.read(&scope);
168            assert!(!other_tail_ptr.is_null());
169            self.tail.assign_ptr(other_tail_ptr);
170        }
171        other.head.assign(std::ptr::null_mut());
172        other.tail.assign(std::ptr::null_mut());
173    }
174
175    /// Removes the given node from the list.
176    ///
177    /// Returns the link of the next node in the list, if any.
178    ///
179    /// # Safety
180    ///
181    /// Requires external synchronization to exclude concurrent writers.
182    pub unsafe fn remove<'a>(
183        &self,
184        scope: &'a RcuReadScope,
185        node: RcuPtrRef<'a, T>,
186    ) -> RcuPtrRef<'a, Link> {
187        let link_ptr = A::to_link(node);
188        let link = link_ptr.as_ref().unwrap();
189
190        let prev = link.prev.read(scope);
191        let next = link.next.read(scope);
192
193        if let Some(next) = next.as_ref() {
194            next.prev.assign_ptr(prev);
195        } else {
196            self.tail.assign_ptr(prev);
197        }
198        if let Some(prev) = prev.as_ref() {
199            prev.next.assign_ptr(next);
200        } else {
201            self.head.assign_ptr(next);
202        }
203
204        // Other readers may continue to see this entry in the list and use the `next` pointer,
205        // but they should not read the `prev` pointer anymore.
206        link.prev.poison();
207
208        next
209    }
210
211    /// Splits the list into two lists at the given position.
212    ///
213    /// If the given position is past the end of the list, returns an empty list.
214    ///
215    /// # Safety
216    ///
217    /// Requires external synchronization to exclude concurrent writers.
218    pub unsafe fn split_off(&self, scope: &RcuReadScope, pos: usize) -> Self {
219        // If we're splitting at the front, just return the entire list and
220        // clear the list.
221        if pos == 0 {
222            let head = RcuPtr::new(self.head.replace(std::ptr::null_mut()));
223            let tail = RcuPtr::new(self.tail.replace(std::ptr::null_mut()));
224            return Self::new(head, tail);
225        }
226        let mut i = 1;
227        let mut prev_ptr = self.head.read(&scope);
228        while let Some(prev) = prev_ptr.as_ref() {
229            if i == pos {
230                let head = prev.next.replace(std::ptr::null_mut());
231                if head.is_null() {
232                    // There are no elements after the split point, so return an empty list.
233                    break;
234                }
235                let tail = self.tail.read(&scope);
236                self.tail.assign_ptr(prev_ptr);
237                return Self::new(RcuPtr::new(head), RcuPtr::new(tail.as_mut_ptr()));
238            }
239            prev_ptr = prev.next.read(&scope);
240            i += 1;
241        }
242        // We reached the end of the list, so return an empty list.
243        Self::default()
244    }
245
246    /// Updates the list with the contents of another list.
247    ///
248    /// # Safety
249    ///
250    /// Requires external synchronization to exclude concurrent writers.
251    pub unsafe fn update(&self, scope: &RcuReadScope, other: Self) {
252        self.head.assign_ptr(other.head.read(scope));
253        self.tail.assign_ptr(other.tail.read(scope));
254    }
255
256    /// Removes all elements from the list.
257    ///
258    /// The callback is called for each element in the list. The caller is responsible for cleaning
259    /// up the removed elements.
260    ///
261    /// Concurrent readers may continue to see the old value of the list until the RCU state machine
262    /// has made sufficient progress to ensure that no concurrent readers are holding read guards.
263    ///
264    /// # Safety
265    ///
266    /// Requires external synchronization to exclude concurrent writers.
267    pub unsafe fn clear<'a>(&self, scope: &'a RcuReadScope, callback: impl Fn(RcuPtrRef<'a, T>))
268    where
269        T: 'static,
270    {
271        let mut current = self.head.read(scope);
272
273        self.head.assign(std::ptr::null_mut());
274        self.tail.assign(std::ptr::null_mut());
275
276        while let Some(link) = current.as_ref() {
277            let next = link.next.read(scope);
278
279            // Other readers may continue to see this entry in the list and use the `next` pointer,
280            // but they should not read the `prev` pointer anymore.
281            link.prev.poison();
282            callback(A::from_link(current));
283            current = next;
284        }
285    }
286
287    #[cfg(test)]
288    pub(crate) fn is_empty(&self, scope: &RcuReadScope) -> bool {
289        self.head.read(scope).is_null()
290    }
291
292    /// Returns a cursor that can be used to traverse and modify the list.
293    ///
294    /// Concurrent readers may continue to see the old value of the list until the RCU state machine
295    /// has made sufficient progress to ensure that no concurrent readers are holding read guards.
296    pub fn cursor<'a>(&'a self, scope: &'a RcuReadScope) -> RcuIntrusiveListCursor<'a, T, A> {
297        let current = self.head.read(scope);
298        RcuIntrusiveListCursor { scope, list: self, current }
299    }
300
301    /// Returns an iterator over the elements in the list.
302    pub fn iter<'a>(&self, scope: &'a RcuReadScope) -> impl Iterator<Item = &'a T>
303    where
304        T: 'static,
305    {
306        let next = self.head.read(&scope);
307        RcuIntrusiveListIter::<T, A> { scope, next, _marker: std::marker::PhantomData }
308    }
309}
310
311/// A cursor for traversing and modifying an `RcuList`.
312///
313/// See `RcuList::cursor` for more information.
314pub struct RcuIntrusiveListCursor<'a, T, A: RcuListAdapter<T>> {
315    scope: &'a RcuReadScope,
316    list: &'a RcuIntrusiveList<T, A>,
317    current: RcuPtrRef<'a, Link>,
318}
319
320impl<'a, T, A: RcuListAdapter<T>> RcuIntrusiveListCursor<'a, T, A> {
321    /// Returns the element at the current cursor position.
322    pub fn current(&self) -> Option<&'a T> {
323        let node = A::from_link(self.current);
324        node.as_ref()
325    }
326
327    /// Advances the cursor to the next element in the list.
328    pub fn advance(&mut self) {
329        if let Some(link) = self.current.as_ref() {
330            self.current = link.next.read(&self.scope);
331        }
332    }
333
334    /// Removes the element at the current cursor position.
335    ///
336    /// After calling `remove`, the cursor will be positioned at the next element in the list.
337    ///
338    /// Returns a pointer to the removed element. The caller is responsible for cleaning up the
339    /// removed element.
340    ///
341    /// Concurrent readers may continue to see this entry in the list until the RCU state machine
342    /// has made sufficient progress to ensure that no concurrent readers are holding read guards.
343    ///
344    /// # Safety
345    ///
346    /// Requires external synchronization to exclude concurrent writers.
347    pub unsafe fn remove(&mut self) -> RcuPtrRef<'a, T> {
348        if self.current.is_null() {
349            return RcuPtrRef::null();
350        }
351        let removed_node = A::from_link(self.current);
352        // SAFETY: The caller promises to exclude concurrent writers.
353        unsafe {
354            self.current = self.list.remove(&self.scope, removed_node);
355        }
356        removed_node
357    }
358}
359
360struct RcuIntrusiveListIter<'a, T, A: RcuListAdapter<T>> {
361    scope: &'a RcuReadScope,
362    next: RcuPtrRef<'a, Link>,
363    _marker: std::marker::PhantomData<(T, A)>,
364}
365
366impl<'a, T: 'static, A: RcuListAdapter<T>> Iterator for RcuIntrusiveListIter<'a, T, A> {
367    type Item = &'a T;
368
369    fn next(&mut self) -> Option<Self::Item> {
370        if let Some(link) = self.next.as_ref() {
371            let current = self.next;
372            self.next = link.next.read(&self.scope);
373            Some(A::from_link(current).as_ref().unwrap())
374        } else {
375            None
376        }
377    }
378}
fuchsia_rcu_collections/rcu_intrusive_list.rs

fuchsia_rcu_collections/
rcu_intrusive_list.rs
