unsafe_list/
lib.rs

1//! Unsafe list head 实现
2//!
3//! Unsafe list head 的实现是 linux 的 `list_head` 实现.
4//! 这个模块是一个非常底层的接口, 没有并发支持, 没有所有权,
5//! 操作的对象都是裸指针, 所有操作均是 unsafe 的.
6//! 这个模块的实现只是为了方便实现 page alloc 接口.
7#![no_std]
8#![allow(unsafe_code, clippy::ptr_eq)]
9
10/// 链表标识1
11pub const LIST_POISON1: usize = 0xdead0100;
12/// 链表标识2
13pub const LIST_POISON2: usize = 0xdead0200;
14
15/// 链表头
16#[derive(Clone, Copy)]
17pub struct UnsafeListHead<T> {
18    next: *mut UnsafeListNode<T>,
19    prev: *mut UnsafeListNode<T>,
20    offset: usize,
21}
22
23impl<T> Default for UnsafeListHead<T> {
24    fn default() -> Self {
25        Self::new()
26    }
27}
28
29impl<T> UnsafeListHead<T> {
30    /// 构造一个链表(未初始化)
31    ///
32    /// 需要调用`init_list_head`初始化才能使用
33    pub const fn new() -> Self {
34        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
35        Self { next: init, prev: init, offset: 0 }
36    }
37
38    /// 初始化链表头
39    pub fn init_list_head(&mut self, offset: usize) {
40        let ptr = (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>();
41        unsafe {
42            core::ptr::write_volatile(&raw mut self.next, ptr);
43        }
44        self.prev = ptr;
45        self.offset = offset;
46    }
47
48    #[inline(always)]
49    unsafe fn __list_add(
50        new: &mut UnsafeListNode<T>,
51        prev: &mut UnsafeListNode<T>,
52        next: &mut UnsafeListNode<T>,
53    ) {
54        unsafe {
55            next.prev = new;
56            new.next = next;
57            new.prev = prev;
58            core::ptr::write_volatile(&raw mut prev.next, new);
59        }
60    }
61
62    /// # Safety
63    ///
64    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
65    #[inline(always)]
66    pub unsafe fn list_add(&mut self, new: &mut UnsafeListNode<T>) {
67        unsafe {
68            UnsafeListHead::__list_add(
69                new,
70                &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
71                &mut *self.next,
72            );
73        }
74    }
75
76    /// # Safety
77    ///
78    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
79    #[inline(always)]
80    pub unsafe fn list_add_tail(&mut self, new: &mut UnsafeListNode<T>) {
81        unsafe {
82            UnsafeListHead::__list_add(
83                new,
84                &mut *self.prev,
85                &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
86            );
87        }
88    }
89
90    /// # Safety
91    ///
92    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
93    #[inline(always)]
94    pub unsafe fn list_is_last(&self, list: &mut UnsafeListNode<T>) -> bool {
95        core::ptr::eq(
96            list.next as *const UnsafeListNode<T>,
97            (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
98        )
99    }
100
101    /// # Safety
102    ///
103    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
104    #[inline(always)]
105    pub unsafe fn list_empty(&self) -> bool {
106        unsafe {
107            core::ptr::eq(
108                core::ptr::read_volatile(&raw const self.next) as *const UnsafeListNode<T>,
109                (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
110            )
111        }
112    }
113
114    /// # Safety
115    ///
116    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
117    #[inline(always)]
118    pub unsafe fn list_empty_careful(&self) -> bool {
119        let next = self.next as *const UnsafeListNode<T>;
120        next == (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>() && next == self.prev
121    }
122
123    /// # Safety
124    ///
125    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
126    #[inline(always)]
127    pub unsafe fn list_first_entry_or_null(&self) -> Option<&T> {
128        unsafe {
129            let next = self.next;
130            if core::ptr::eq(
131                next as *const UnsafeListNode<T>,
132                (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
133            ) {
134                None
135            } else {
136                Some(&*((next as usize - self.offset) as *const T))
137            }
138        }
139    }
140
141    /// # Safety
142    ///
143    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
144    #[inline(always)]
145    pub unsafe fn list_first_entry_or_null_mut(&mut self) -> Option<&mut T> {
146        unsafe {
147            let next = self.next;
148            if next == (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>() {
149                None
150            } else {
151                Some(&mut *((next as usize - self.offset) as *mut T))
152            }
153        }
154    }
155
156    /// # Safety
157    ///
158    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
159    #[inline(always)]
160    pub unsafe fn list_first_entry_mut(&mut self) -> &mut T {
161        unsafe { &mut *((self.next as usize - self.offset) as *mut T) }
162    }
163
164    /// # Safety
165    ///
166    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
167    #[inline(always)]
168    pub unsafe fn list_first_entry(&self) -> &T {
169        unsafe { &*((self.next as usize - self.offset) as *const T) }
170    }
171
172    /// # Safety
173    ///
174    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
175    #[inline(always)]
176    pub unsafe fn list_last_entry_mut(&mut self) -> &mut T {
177        unsafe { &mut *((self.prev as usize - self.offset) as *mut T) }
178    }
179
180    /// # Safety
181    ///
182    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
183    #[inline(always)]
184    pub unsafe fn list_last_entry(&self) -> &T {
185        unsafe { &*((self.prev as usize - self.offset) as *const T) }
186    }
187}
188
189/// 初始化链表头
190#[macro_export]
191macro_rules! init_unsafe_list_head {
192    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
193        $var.init_list_head(core::mem::offset_of!($type, $($member).+));
194    };
195}
196
197/// 定义并初始化链表头
198#[macro_export]
199macro_rules! define_unsafe_list_head {
200    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
201        let mut $var = $crate::UnsafeListHead::<$type>::new();
202        $crate::init_unsafe_list_head!($var, $type, $($member).+);
203    };
204}
205
206/// 链表节点
207#[derive(Clone, Copy)]
208pub struct UnsafeListNode<T> {
209    next: *mut UnsafeListNode<T>,
210    prev: *mut UnsafeListNode<T>,
211}
212
213impl<T> Default for UnsafeListNode<T> {
214    fn default() -> Self {
215        Self::new()
216    }
217}
218
219impl<T> UnsafeListNode<T> {
220    /// 构造一个链表节点
221    pub const fn new() -> Self {
222        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
223        Self { next: init, prev: init }
224    }
225
226    #[inline(always)]
227    unsafe fn init_list_node(&mut self) {
228        unsafe {
229            let value = self as *mut UnsafeListNode<T>;
230            core::ptr::write_volatile(&raw mut self.next, value);
231            self.prev = value;
232        }
233    }
234
235    #[inline(always)]
236    unsafe fn __list_del(prev: &mut UnsafeListNode<T>, next: &mut UnsafeListNode<T>) {
237        unsafe {
238            next.prev = prev;
239            core::ptr::write_volatile(&raw mut prev.next, next);
240        }
241    }
242
243    #[inline(always)]
244    unsafe fn __list_del_entry(&mut self) {
245        unsafe {
246            UnsafeListNode::__list_del(&mut *self.prev, &mut *self.next);
247        }
248    }
249
250    /// # Safety
251    ///
252    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
253    #[inline(always)]
254    pub unsafe fn list_del(&mut self) {
255        unsafe {
256            self.__list_del_entry();
257            self.next = LIST_POISON1 as *mut UnsafeListNode<T>;
258            self.prev = LIST_POISON2 as *mut UnsafeListNode<T>;
259        }
260    }
261
262    /// # Safety
263    ///
264    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
265    #[inline(always)]
266    pub unsafe fn list_replace(&mut self, new: &mut UnsafeListNode<T>) {
267        unsafe {
268            new.next = self.next;
269            (*new.next).prev = new;
270            new.prev = self.prev;
271            (*new.prev).next = new;
272        }
273    }
274
275    /// # Safety
276    ///
277    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
278    #[inline(always)]
279    pub unsafe fn list_replace_init(&mut self, new: &mut UnsafeListNode<T>) {
280        unsafe {
281            self.list_replace(new);
282            self.init_list_node();
283        }
284    }
285
286    /// # Safety
287    ///
288    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
289    #[inline(always)]
290    pub unsafe fn list_del_init(&mut self) {
291        unsafe {
292            self.__list_del_entry();
293            self.init_list_node();
294        }
295    }
296
297    /// # Safety
298    ///
299    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
300    #[inline(always)]
301    pub unsafe fn list_move(&mut self, head: &mut UnsafeListHead<T>) {
302        unsafe {
303            self.__list_del_entry();
304            head.list_add(self);
305        }
306    }
307
308    /// # Safety
309    ///
310    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
311    #[inline(always)]
312    pub unsafe fn list_move_tail(&mut self, head: &mut UnsafeListHead<T>) {
313        unsafe {
314            self.__list_del_entry();
315            head.list_add_tail(self);
316        }
317    }
318
319    #[inline(always)]
320    unsafe fn list_next_entry_mut(&mut self, offset: usize) -> &mut T {
321        unsafe { &mut *((self.next as usize - offset) as *mut T) }
322    }
323
324    #[inline(always)]
325    unsafe fn list_next_entry(&self, offset: usize) -> &T {
326        unsafe { &*((self.next as usize - offset) as *const T) }
327    }
328
329    #[inline(always)]
330    unsafe fn list_prev_entry_mut(&mut self, offset: usize) -> &mut T {
331        unsafe { &mut *((self.prev as usize - offset) as *mut T) }
332    }
333
334    #[inline(always)]
335    unsafe fn list_prev_entry(&self, offset: usize) -> &T {
336        unsafe { &*((self.prev as usize - offset) as *const T) }
337    }
338}
339
340/// 链表迭代器
341pub struct UnsafeListHeadIter<'a, T> {
342    prev_pos: *const UnsafeListNode<T>,
343    next_pos: *const UnsafeListNode<T>,
344    head: &'a UnsafeListHead<T>,
345}
346
347impl<'a, T> UnsafeListHeadIter<'a, T> {
348    fn new(head: &'a UnsafeListHead<T>) -> Self {
349        let init = core::ptr::null::<UnsafeListNode<T>>();
350        Self { prev_pos: init, next_pos: init, head }
351    }
352}
353
354impl<T> UnsafeListHead<T> {
355    /// 创建迭代器
356    pub fn iter(&self) -> UnsafeListHeadIter<T> {
357        UnsafeListHeadIter::new(self)
358    }
359}
360
361impl<'a, T> Iterator for UnsafeListHeadIter<'a, T> {
362    type Item = &'a T;
363    fn next(&mut self) -> Option<Self::Item> {
364        unsafe {
365            if self.next_pos.is_null() {
366                self.next_pos = self.head.next;
367                return Some(self.head.list_first_entry());
368            }
369
370            let this = (*self.next_pos).next as *const UnsafeListNode<T>;
371            let end = if self.prev_pos.is_null() {
372                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
373            } else {
374                self.prev_pos
375            };
376            if this == end {
377                return None;
378            }
379
380            let val = (*self.next_pos).list_next_entry(self.head.offset);
381            self.next_pos = (*self.next_pos).next;
382            Some(val)
383        }
384    }
385}
386
387impl<'a, T> DoubleEndedIterator for UnsafeListHeadIter<'a, T> {
388    fn next_back(&mut self) -> Option<&'a T> {
389        unsafe {
390            if self.prev_pos.is_null() {
391                self.prev_pos = self.head.prev;
392                return Some(self.head.list_last_entry());
393            }
394
395            let this = (*self.prev_pos).prev as *const UnsafeListNode<T>;
396            let end = if self.next_pos.is_null() {
397                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
398            } else {
399                self.next_pos
400            };
401            if this == end {
402                return None;
403            }
404
405            let val = (*self.prev_pos).list_prev_entry(self.head.offset);
406            self.prev_pos = (*self.prev_pos).prev;
407            Some(val)
408        }
409    }
410}
411
412/// 链表可变迭代器
413pub struct UnsafeListHeadIterMut<'a, T> {
414    prev_pos: *mut UnsafeListNode<T>,
415    next_pos: *mut UnsafeListNode<T>,
416    head: &'a mut UnsafeListHead<T>,
417}
418
419impl<'a, T> UnsafeListHeadIterMut<'a, T> {
420    fn new(head: &'a mut UnsafeListHead<T>) -> Self {
421        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
422        Self { prev_pos: init, next_pos: init, head }
423    }
424}
425
426impl<T> UnsafeListHead<T> {
427    /// 创建可变迭代器
428    pub fn iter_mut(&mut self) -> UnsafeListHeadIterMut<T> {
429        UnsafeListHeadIterMut::new(self)
430    }
431}
432
433impl<'a, T> Iterator for UnsafeListHeadIterMut<'a, T> {
434    type Item = &'a mut T;
435    fn next(&mut self) -> Option<Self::Item> {
436        unsafe {
437            if self.next_pos.is_null() {
438                self.next_pos = self.head.next;
439                let this = self.head as *mut UnsafeListHead<T>;
440                return Some((*this).list_first_entry_mut());
441            }
442
443            let this = (*self.next_pos).next as *const UnsafeListNode<T>;
444            let end = if self.prev_pos.is_null() {
445                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
446            } else {
447                self.prev_pos
448            };
449            if this == end {
450                return None;
451            }
452
453            let val = (*self.next_pos).list_next_entry_mut(self.head.offset);
454            self.next_pos = (*self.next_pos).next;
455            Some(val)
456        }
457    }
458}
459
460impl<'a, T> DoubleEndedIterator for UnsafeListHeadIterMut<'a, T> {
461    fn next_back(&mut self) -> Option<&'a mut T> {
462        unsafe {
463            if self.prev_pos.is_null() {
464                self.prev_pos = self.head.prev;
465                let this = self.head as *mut UnsafeListHead<T>;
466                return Some((*this).list_last_entry_mut());
467            }
468
469            let this = (*self.prev_pos).prev as *const UnsafeListNode<T>;
470            let end = if self.next_pos.is_null() {
471                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
472            } else {
473                self.next_pos
474            };
475            if this == end {
476                return None;
477            }
478
479            let val = (*self.prev_pos).list_prev_entry_mut(self.head.offset);
480            self.prev_pos = (*self.prev_pos).prev;
481            Some(val)
482        }
483    }
484}
unsafe_list/lib.rs

unsafe_list/
lib.rs
