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
|
//! A doubly-linked list of power-of-two-sized subregions.
use core::{
fmt,
marker::PhantomPinned,
pin::Pin,
ptr::{self, NonNull},
};
/// The magic number a non-sentinel node should have.
const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");
/// The magic number a sentinel node should have.
const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL");
/// A doubly-linked list of power-of-two-sized subregions.
///
/// This type is valid when zero-initialized.
///
/// # Safety
///
/// - This type is valid only if it is zero-initialized or if it contains a valid doubly-linked
/// list of subregions of the correct size, which it owns.
pub struct FreeList {
sentinel: FreeListNode,
}
impl FreeList {
/// Pushes a subregion into the free-list.
///
/// # Safety
///
/// - `subregion_ptr` must convey ownership over untyped memory of the correct size.
pub unsafe fn push(mut self: Pin<&mut FreeList>, subregion_ptr: NonNull<u8>) {
assert_ne!(self.sentinel.next, ptr::null_mut());
assert_ne!(self.sentinel.prev, ptr::null_mut());
// Write the header the node should have to the node.
let sentinel = &self.sentinel as *const FreeListNode as *mut FreeListNode;
let next = *self.as_mut().sentinel().next_mut();
let node = subregion_ptr.cast();
node.write(FreeListNode {
next,
prev: sentinel,
magic: FREE_NODE_MAGIC,
_phantom: PhantomPinned,
});
// Link the node into the list.
*self.sentinel().next_mut() = node.as_ptr();
(*next).prev = node.as_ptr();
}
/// Performs self-linking. This must be done before the free list is used in any other way.
pub fn self_link(self: Pin<&mut FreeList>) {
assert_eq!(self.sentinel.next, ptr::null_mut());
assert_eq!(self.sentinel.prev, ptr::null_mut());
let mut sentinel = self.sentinel_unchecked();
// SAFETY: We do not use this pointer to move out of the sentinel.
let sentinel_ptr = unsafe { sentinel.as_mut().get_unchecked_mut() as *mut FreeListNode };
*sentinel.as_mut().next_mut() = sentinel_ptr;
*sentinel.as_mut().prev_mut() = sentinel_ptr;
*sentinel.as_mut().magic_mut() = SENTINEL_MAGIC;
}
/// Projects the sentinel node out of the list.
fn sentinel(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
let mut sentinel = self.sentinel_unchecked();
assert_eq!(*sentinel.as_mut().magic_mut(), SENTINEL_MAGIC);
sentinel
}
/// Projects the sentinel node out of the list, without checking the magic number.
fn sentinel_unchecked(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
// SAFETY: sentinel is structurally pinned.
unsafe { self.map_unchecked_mut(|list| &mut list.sentinel) }
}
}
/// This impl will panic until the sentinel has been self-linked.
impl fmt::Debug for FreeList {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
assert_ne!(self.sentinel.next, ptr::null_mut());
assert_ne!(self.sentinel.prev, ptr::null_mut());
let sentinel = &self.sentinel as *const FreeListNode;
// SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid list,
// the next pointer is always valid and non-null.
let mut ptr = unsafe { sentinel.as_ref().unwrap().next as *const FreeListNode };
let mut fmt = fmt.debug_list();
while ptr != sentinel {
fmt.entry(&ptr);
// SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid
// list, the next pointer is always valid and non-null.
ptr = unsafe { ptr.as_ref().unwrap().next as *const FreeListNode };
}
fmt.finish()
}
}
#[derive(Debug)]
struct FreeListNode {
next: *mut FreeListNode,
prev: *mut FreeListNode,
magic: u64,
_phantom: PhantomPinned,
}
impl FreeListNode {
/// Projects the `next` pointer out of the node.
fn next_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
// SAFETY: next is not structurally pinned.
unsafe { &mut self.get_unchecked_mut().next }
}
/// Projects the `prev` pointer out of the node.
fn prev_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
// SAFETY: prev is structurally pinned.
unsafe { &mut self.get_unchecked_mut().prev }
}
/// Projects the `magic` number out of the node.
fn magic_mut(self: Pin<&mut FreeListNode>) -> &mut u64 {
// SAFETY: magic is structurally pinned.
unsafe { &mut self.get_unchecked_mut().magic }
}
}
|
