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
185
186
187
188
189
|
//! A circular doubly-linked list of power-of-two-sized subregions.
use core::{
fmt,
marker::PhantomPinned,
pin::Pin,
ptr::{self, NonNull},
};
use contracts::requires;
/// 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");
/// The magic number set into the spot for a node's magic number when it gets unlinked.
const USED_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"ALLOC'ED");
/// A circular 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 circular
/// doubly-linked list of subregions of the correct size, which it owns.
pub struct FreeList {
sentinel: FreeListNode,
}
impl FreeList {
/// Pops a subregion from the free-list, returning ownership to the caller.
pub fn pop(mut self: Pin<&mut FreeList>) -> Option<NonNull<u8>> {
assert_ne!(self.sentinel.next, ptr::null_mut());
assert_ne!(self.sentinel.prev, ptr::null_mut());
// Check if the sentinel's next pointer points to the sentinel itself.
let sentinel = &self.sentinel as *const FreeListNode as *mut FreeListNode;
let next = *self.as_mut().sentinel().next_mut();
if sentinel == next {
// If so, the list is empty.
None
} else {
// Otherwise, unlink that node.
//
// UNWRAP: The pointer was non-null, by the invariants of FreeList.
let mut node = NonNull::new(next).unwrap();
// SAFETY: The list was valid, by the invariants of FreeList.
unsafe { node.as_mut().unlink() };
Some(node.cast())
}
}
/// 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.
//
// SAFETY: This &mut is not used to move out of the node.
let sentinel = unsafe { self.as_mut().sentinel().get_unchecked_mut() };
let mut node = subregion_ptr.cast();
node.write(FreeListNode {
next: sentinel.next,
prev: sentinel,
magic: FREE_NODE_MAGIC,
_phantom: PhantomPinned,
});
// Link the node into the list.
//
// SAFETY: There are no other references to the node live.
let node = unsafe { node.as_mut() };
(*node.prev).next = node;
(*node.next).prev = node;
}
/// 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 }
}
/// Links the node into a circular doubly-linked list.
///
/// # Safety
///
/// This must be a node that's not part of any linked list.
unsafe fn link(&mut self) {
todo!()
}
/// Unlinks a node from a circular doubly-linked list.
///
/// # Safety
///
/// This must be a non-sentinel node in a valid circular doubly-linked list.
#[requires(self.magic == FREE_NODE_MAGIC)]
#[ensures(self.magic == USED_NODE_MAGIC)]
unsafe fn unlink(&mut self) {
let prev = self.prev;
let next = self.next;
use core::ptr::addr_of_mut;
*addr_of_mut!((*prev).next) = next;
*addr_of_mut!((*next).prev) = prev;
self.next = ptr::null_mut();
self.prev = ptr::null_mut();
self.magic = USED_NODE_MAGIC;
}
}
|
