jonaskruckenberg.de
Next Generation WASM Microkernel Operating System
1// Copyright 2025 Jonas Kruckenberg
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8use crate::arch;
9use crate::mem::address::{PhysicalAddress, VirtualAddress};
10use crate::mem::frame_alloc::FRAME_ALLOC;
11use alloc::slice;
12use cordyceps::Linked;
13use cordyceps::list;
14use core::marker::PhantomData;
15use core::mem::offset_of;
16use core::ops::Deref;
17use core::ptr::NonNull;
18use core::sync::atomic;
19use core::sync::atomic::{AtomicUsize, Ordering};
20use core::{fmt, ptr};
21use static_assertions::assert_impl_all;
22
23/// Soft limit on the amount of references that may be made to a `Frame`.
24const MAX_REFCOUNT: usize = isize::MAX as usize;
25
26/// A thread-safe reference-counted pointer to a frame of physical memory.
27///
28/// This type is similar to [`alloc::sync::Arc`][1] and provides shared ownership of a [`FrameInfo`] instance
29/// and by extension its associated physical memory. Just like [`Arc`][1] invoking [`clone`][Frame::clone] will
30/// produce a new `Frame` instance, which points to the same [`FrameInfo`] instance as the source `Frame`, while
31/// increasing its reference count. When the last `Frame` is dropped instance is dropped, the underlying
32/// [`FrameInfo`] is marked as *free* and returned to the frame allocator freelists.
33///
34/// [1]: [alloc::sync::Arc]
35pub struct Frame {
36 ptr: NonNull<FrameInfo>,
37 phantom: PhantomData<FrameInfo>,
38}
39
40pub struct FrameInfo {
41 /// Links to other frames in a freelist either a global `Arena` or cpu-local page cache.
42 links: list::Links<FrameInfo>,
43 /// Number of references to this frame, zero indicates a free frame.
44 refcount: AtomicUsize,
45 /// The physical address of the frame.
46 addr: PhysicalAddress,
47}
48assert_impl_all!(FrameInfo: Send, Sync);
49
50// === Frame ===
51
52// Safety: assert_impl_all! above ensures that `FrameInfo` is `Send`
53unsafe impl Send for Frame {}
54
55// Safety: assert_impl_all! above ensures that `FrameInfo` is `Sync`
56unsafe impl Sync for Frame {}
57
58impl Clone for Frame {
59 /// Makes a clone of the `Frame`.
60 ///
61 /// This creates reference to the same `FrameInfo`, increasing the reference count by one.
62 fn clone(&self) -> Self {
63 // Increase the reference count by one. Using relaxed ordering, as knowledge of the
64 // original reference prevents other threads from erroneously deleting
65 // the object.
66 //
67 // Again, restating what the `Arc` implementation quotes from the
68 // [Boost documentation][1]:
69 //
70 // > Increasing the reference counter can always be done with memory_order_relaxed: New
71 // > references to an object can only be formed from an existing
72 // > reference, and passing an existing reference from one thread to
73 // > another must already provide any required synchronization.
74 //
75 // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
76 let old_size = self.info().refcount.fetch_add(1, Ordering::Relaxed);
77 debug_assert_ne!(old_size, 0);
78
79 // Just like with `Arc` we want to prevent excessive refcounts in the case that we are leaking
80 // `Frame`s somewhere (which we really shouldn't but just in case). Overflowing the refcount
81 // would *really* bad as it would treat the frame as free and potentially cause a use-after-free
82 // scenario. Realistically this branch should never be taken.
83 //
84 // Also worth noting: Just like `Arc`, the refcount could still overflow when in between
85 // the load above and this check some other cpu increased the refcount from `isize::MAX` to
86 // `usize::MAX` but that seems unlikely. The other option, doing the comparison and update in
87 // one conditional atomic operation produces much worse code, so if its good enough for the
88 // standard library, it is good enough for us.
89 assert!(old_size <= MAX_REFCOUNT, "Frame refcount overflow");
90
91 // Safety: self was valid so it's info ptr is as well
92 unsafe { Self::from_info(self.ptr) }
93 }
94}
95impl Drop for Frame {
96 /// Drops the `Frame`.
97 ///
98 /// This will decrement the reference count. If the reference count reaches zero
99 /// then this frame will be marked as free and returned to the frame allocator.
100 fn drop(&mut self) {
101 if self.info().refcount.fetch_sub(1, Ordering::Release) != 1 {
102 return;
103 }
104
105 // Ensure uses of `FrameInfo` happen before freeing it.
106 // Because it is marked `Release`, the decreasing of the reference count synchronizes
107 // with this `Acquire` fence. This means that use of `FrameInfo` happens before decreasing
108 // the reference count, which happens before this fence, which happens before freeing `FrameInfo`.
109 //
110 // This section of the [Boost documentation][1] as quoted in Rusts `Arc` implementation and
111 // may explain further:
112 //
113 // > It is important to enforce any possible access to the object in one
114 // > thread (through an existing reference) to *happen before* deleting
115 // > the object in a different thread. This is achieved by a "release"
116 // > operation after dropping a reference (any access to the object
117 // > through this reference must obviously happened before), and an
118 // > "acquire" operation before deleting the object.
119 //
120 // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
121 atomic::fence(Ordering::Acquire);
122
123 self.drop_slow();
124 }
125}
126
127impl Frame {
128 #[inline]
129 #[must_use]
130 pub fn ptr_eq(this: &Self, other: &Self) -> bool {
131 ptr::addr_eq(this.ptr.as_ptr(), other.ptr.as_ptr())
132 }
133
134 /// Asserts the `Frame` is in a valid state.
135 pub fn assert_valid(&self) {
136 let refcount = self.info().refcount.load(Ordering::Acquire);
137 assert!(refcount > 0);
138 assert!(refcount < MAX_REFCOUNT);
139 self.info().assert_valid();
140 }
141
142 #[inline]
143 fn info(&self) -> &FrameInfo {
144 // Safety: Through `Clone` and `Drop` we're guaranteed that the FrameInfo remains valid as long as
145 // this Frame is alive, we also know that `FrameInfo` is `Sync` and therefore - analogous to `Arc` -
146 // handing out an immutable reference is fine.
147 // Because it is an immutable reference, safe code can also not move out of `FrameInner`.
148 unsafe { self.ptr.as_ref() }
149 }
150
151 pub(crate) unsafe fn from_free_info(info: NonNull<FrameInfo>) -> Frame {
152 // Safety: caller has to ensure ptr is valid
153 unsafe {
154 let prev_refcount = info.as_ref().refcount.swap(1, Ordering::Acquire);
155 debug_assert_eq!(
156 prev_refcount, 0,
157 "attempted to create Frame from non-free FrameInfo"
158 );
159
160 Self::from_info(info)
161 }
162 }
163
164 #[inline]
165 unsafe fn from_info(info: NonNull<FrameInfo>) -> Self {
166 Self {
167 ptr: info,
168 phantom: PhantomData,
169 }
170 }
171
172 pub fn get_mut(this: &mut Frame) -> Option<&mut FrameInfo> {
173 if this.is_unique() {
174 // Safety: This unsafety is ok because we're guaranteed that the pointer
175 // returned is the *only* pointer that will ever be returned to T. Our
176 // reference count is guaranteed to be 1 at this point, and we required
177 // the Arc itself to be `mut`, so we're returning the only possible
178 // reference to the inner data.
179 unsafe { Some(Frame::get_mut_unchecked(this)) }
180 } else {
181 None
182 }
183 }
184
185 pub unsafe fn get_mut_unchecked(this: &mut Self) -> &mut FrameInfo {
186 // Safety: construction ensures the base ptr is valid
187 unsafe { this.ptr.as_mut() }
188 }
189
190 pub fn is_unique(&self) -> bool {
191 self.refcount() == 1
192 }
193
194 #[inline(never)]
195 fn drop_slow(&mut self) {
196 // TODO if we ever add more fields to FrameInfo we should reset them here
197
198 let alloc = FRAME_ALLOC
199 .get()
200 .expect("cannot access FRAME_ALLOC before it is initialized");
201 let mut cpu_local_cache = alloc.cpu_local_cache.get().unwrap().borrow_mut();
202 cpu_local_cache.free_list.push_back(self.ptr);
203 }
204}
205
206impl Deref for Frame {
207 type Target = FrameInfo;
208
209 #[inline]
210 fn deref(&self) -> &FrameInfo {
211 self.info()
212 }
213}
214
215impl fmt::Debug for Frame {
216 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217 // Safety: construction ensures the base ptr is valid
218 fmt::Debug::fmt(unsafe { self.ptr.as_ref() }, f)
219 }
220}
221
222impl fmt::Pointer for Frame {
223 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
224 fmt::Pointer::fmt(&self.ptr, f)
225 }
226}
227
228// === FrameInfo ===
229
230impl FrameInfo {
231 /// Private constructor for use in `frame_alloc/arena.rs`
232 pub(crate) fn new(addr: PhysicalAddress) -> Self {
233 Self {
234 links: list::Links::default(),
235 addr,
236 refcount: AtomicUsize::new(0),
237 }
238 }
239
240 /// The physical address of this frame.
241 pub fn addr(&self) -> PhysicalAddress {
242 self.addr
243 }
244
245 /// Gets the number of references to this frame.
246 #[inline]
247 #[must_use]
248 pub fn refcount(&self) -> usize {
249 self.refcount.load(Ordering::Relaxed)
250 }
251
252 /// Returns a slice of the corresponding physical memory
253 #[inline]
254 pub fn as_slice(&self) -> &[u8] {
255 let base = VirtualAddress::from_phys(self.addr).unwrap().as_ptr();
256 // Safety: construction ensures the base ptr is valid
257 unsafe { slice::from_raw_parts(base, arch::PAGE_SIZE) }
258 }
259
260 /// Returns a mutable slice of the corresponding physical memory
261 #[inline]
262 pub fn as_mut_slice(&mut self) -> &mut [u8] {
263 let base = VirtualAddress::from_phys(self.addr).unwrap().as_mut_ptr();
264 // Safety: construction ensures the base ptr is valid
265 unsafe { slice::from_raw_parts_mut(base, arch::PAGE_SIZE) }
266 }
267
268 #[inline]
269 pub fn assert_valid(&self) {
270 // TODO add asserts here as we add more fields
271 }
272}
273
274/// Implement the cordyceps [Linked] trait so that [FrameInfo] can be used
275/// with coryceps linked [List].
276// Safety: unsafe trait
277unsafe impl Linked<list::Links<FrameInfo>> for FrameInfo {
278 type Handle = NonNull<FrameInfo>;
279
280 fn into_ptr(r: Self::Handle) -> NonNull<Self> {
281 r
282 }
283
284 unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle {
285 ptr
286 }
287
288 unsafe fn links(ptr: NonNull<Self>) -> NonNull<list::Links<Self>> {
289 ptr.map_addr(|addr| {
290 let offset = offset_of!(Self, links);
291 addr.checked_add(offset).unwrap()
292 })
293 .cast()
294 }
295}
296
297impl fmt::Debug for FrameInfo {
298 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
299 f.debug_struct("FrameInfo")
300 .field("refcount", &self.refcount)
301 .field("addr", &self.addr)
302 .finish_non_exhaustive()
303 }
304}