gc_shadowstack/lib.rs
1//! Shadow stack implementation for rooting in GCs
2//!
3//!
4//! # Description
5//! Unlike other algorithms to take care of rooted objects like use reference counting to take count of instances
6//! on stack, this algorithm maintains a singly linked list of stack roots. This so-called "shadow stack" mirrors the
7//! machine stack. Maintaining this data is much faster and memory-efficent than using reference-counted stack roots,
8//! it does not require heap allocation, and does not rely on compiler optimizations.
9#![no_std]
10
11pub use mopa;
12pub use paste;
13
14/// Instatiate shadow stack type that can work with your GC API.
15///
16/// # Paramters
17/// - `$name`: Shadow stack type name itself.
18/// - `$traceable`: Your GC traceable trait that is implemented for all types that can be traced.
19/// - `$rootable`: New trait name that should be implemented for rooted values.
20/// - `$rooted`: Type of rooted value.
21/// - `$handle`: Type of reference to rooted value. This creates `$handle` and `$handle Mut` types.
22/// - `$letroot`: Name that is given to macro that will instantiate rooted values.
23///
24#[macro_export]
25macro_rules! gc_shadowstack {
26 ($name: ident,$traceable: path,$rootable: ident,$rooted: ident,$handle: ident,$letroot: ident) => {
27
28 $crate::paste::paste!(
29
30 /// Shadow stack implementation. Internally this is singly-linked list of on stack rooted values.
31 pub struct $name {
32 #[doc(hidden)]
33 pub head: core::cell::Cell<*mut [<Raw $name Entry>]>,
34 }
35
36
37 impl $name {
38 /// Create new shadow stack instance.
39 pub fn new() -> Self {
40 Self {
41 head: core::cell::Cell::new(core::ptr::null_mut())
42 }
43 }
44 /// Walk all rooted values in this shadow stack.
45 ///
46 /// # Safety
47 /// TODO: I don't really know if this method should be safe or unsafe.
48 ///
49 pub unsafe fn walk(&self,mut visitor: impl FnMut(&mut dyn $rootable)) {
50 let mut head = *self.head.as_ptr();
51 while !head.is_null() {
52 let next = (*head).prev;
53 visitor((*head).get_dyn());
54 head = next;
55 }
56 }
57 }
58
59
60 );
61
62 $crate::paste::paste!{
63 /// Raw entry in GC shadow stack. Internal fields is not exposed in public API in any ways.
64 ///
65 ///
66 /// This type internally stores shadow stack pointeter,previous pointer from the list and vtable
67 /// that is used to construct `dyn` trait.
68 ///
69 #[repr(C)]
70 pub struct [<Raw $name Entry>] {
71 /// Shadowstack itself
72 stack: *mut $name,
73 /// Previous rooted entry
74 prev: *mut [<Raw $name Entry>],
75 /// Pointer to vtable that is a `Trace` of rooted variable
76 vtable: usize,
77 /// Value is located right after vtable pointer, to access it we can construct trait object.
78 data_start: [u8; 0],
79 }
80 }
81 /// Trait that should be implemented for all types that could be rooted.
82 /// In simple cases `impl<T: Traceable> Rootable for T {}` is enough.
83 pub trait $rootable: $traceable {}
84 $crate::paste::paste!(
85 impl [<Raw $name Entry>] {
86 /// Obtain mutable reference to rooted value.
87 ///
88 /// # Safety
89 /// This method is `&self` but returns `&mut dyn` which is *very* unsafey. If moving GC uses shadow stack
90 /// it should be ***very*** accurate when moving objects around.
91 pub unsafe fn get_dyn(&self) -> &mut dyn $rootable {
92 core::mem::transmute($crate::mopa::TraitObject {
93 vtable: self.vtable as _,
94 data: self.data_start.as_ptr() as *mut (),
95 })
96 }
97 }
98
99 /// Almost the same as raw entry of shadow stack except this one gives access to value.
100 /// This type is not exposed in public API and used only internally.
101 #[repr(C)]
102 pub struct [<$name Internal>]<'a,T: $rootable> {
103 pub stack :&'a $name,
104 pub prev: *mut [<Raw $name Entry>],
105 pub vtable: usize,
106 pub value: T
107 }
108
109 impl<'a, T:$rootable> [<$name Internal>]<'a, T> {
110 /// Constructs internal shadow stack value. Must not be used outside of `$letroot!` macro.
111 #[inline]
112 pub unsafe fn construct(
113 stack: &'a ShadowStack,
114 prev: *mut [<Raw $name Entry>],
115 vtable: usize,
116 value: T,
117 ) -> Self {
118 Self {
119 stack,
120 prev,
121 vtable,
122 value,
123 }
124 }
125 }
126
127 impl<T: $rootable> Drop for [<$name Internal>]<'_,T> {
128 /// Drop current shadow stack entry and update shadow stack state.
129 fn drop(&mut self) {
130 (*self.stack).head.set(self.prev);
131 }
132 }
133
134 /// Rooted value on stack. This is non-copyable type that is used to hold GC thing on stack.
135 pub struct $rooted<'a, 'b, T: $rootable> {
136 #[doc(hidden)]
137 pinned: core::pin::Pin<&'a mut [<$name Internal>]<'b, T>>,
138 }
139
140 impl<'a, 'b, T: $rootable> $rooted<'a, 'b, T> {
141 /// Create rooted value from pinned reference. Note that this function must be used only
142 /// inside `$letroot` macro.
143 pub unsafe fn construct(pin: core::pin::Pin<&'a mut [< $name Internal>]<'b, T>>) -> Self {
144 Self { pinned: pin }
145 }
146 pub unsafe fn get_internal(&self) -> &[<$name Internal>]<T> {
147 core::mem::transmute_copy::<_, _>(&self.pinned)
148 }
149 pub unsafe fn get_internal_mut(&mut self) -> &mut &[<$name Internal>]<T> {
150 core::mem::transmute_copy::<_, _>(&self.pinned)
151 }
152
153 pub fn mut_handle(&mut self) -> [<$handle Mut>]<'_, T> {
154 HandleMut { value: &mut **self }
155 }
156
157 pub fn handle(&self) -> $handle<'_, T> {
158 Handle { value: &**self }
159 }
160 }
161
162 impl<'a, T: $rootable> core::ops::Deref for $rooted<'a, '_, T> {
163 type Target = T;
164 fn deref(&self) -> &Self::Target {
165 &self.pinned.value
166 }
167 }
168
169 impl<'a, T: $rootable> core::ops::DerefMut for $rooted<'a, '_, T> {
170 fn deref_mut(&mut self) -> &mut Self::Target {
171 unsafe {
172 &mut core::mem::transmute_copy::<_, &mut [<$name Internal>]<T>>(&mut self.pinned).value
173 }
174 }
175 }
176
177 /// Reference to rooted value.
178 pub struct $handle<'a, T: $rootable> {
179 value: &'a T,
180 }
181 /// Mutable reference to rooted value.
182 pub struct [<$handle Mut>]<'a, T: $rootable> {
183 value: &'a mut T,
184 }
185
186 impl<'a, T: $rootable> [<$handle Mut>]<'a, T> {
187 pub fn set(&mut self, value: T) -> T {
188 core::mem::replace(self.value, value)
189 }
190 }
191 impl<T: $rootable> core::ops::Deref for $handle<'_, T> {
192 type Target = T;
193 fn deref(&self) -> &Self::Target {
194 self.value
195 }
196 }
197
198 impl<T: $rootable> core::ops::Deref for [<$handle Mut>]<'_, T> {
199 type Target = T;
200 fn deref(&self) -> &Self::Target {
201 self.value
202 }
203 }
204 impl<T: $rootable> core::ops::DerefMut for [<$handle Mut>]<'_, T> {
205 fn deref_mut(&mut self) -> &mut Self::Target {
206 self.value
207 }
208 }
209
210
211 /// Create rooted value and push it to provided shadowstack instance.
212 ///
213 ///
214 /// ***NOTE***: This macro does not heap allocate internally. It uses some unsafe tricks to
215 /// allocate value on stack and push stack reference to shadowstack. Returned rooted value internally
216 /// is `Pin<&mut T>`.
217 ///
218 #[macro_export]
219 macro_rules! $letroot {
220 ($var_name: ident: $t: ty = $stack: expr,$value: expr) => {
221 let stack: &$name = &$stack;
222 let value = $value;
223 let mut $var_name = unsafe {
224 [<$name Internal>]::<$t>::construct(
225 stack,
226 stack.head.get(),
227 core::mem::transmute::<_, $crate::mopa::TraitObject>(&value as &dyn $rootable)
228 .vtable as usize,
229 value,
230 )
231 };
232
233 stack.head.set(unsafe { core::mem::transmute(&mut $var_name) });
234 #[allow(unused_mut)]
235 let mut $var_name =
236 unsafe { $rooted::construct(std::pin::Pin::new(&mut $var_name)) };
237 };
238
239 ($var_name : ident = $stack: expr,$value: expr) => {
240 let stack: &$name = &$stack;
241 let value = $value;
242 let mut $var_name = unsafe {
243 [<$name Internal>]::<_>::construct(
244 stack,
245 stack.head.get(),
246 core::mem::transmute::<_, $crate::mopa::TraitObject>(&value as &dyn $rootable)
247 .vtable as usize,
248 value,
249 )
250 };
251
252 stack.head.set(unsafe { core::mem::transmute(&mut $var_name) });
253 #[allow(unused_mut)]
254 let mut $var_name =
255 unsafe { $rooted::construct(core::pin::Pin::new(&mut $var_name)) };
256 };
257 }
258 );
259 };
260}
261
262#[cfg(doc)]
263pub mod dummy {
264 //! Dummy module that generates shadow stack type to see documentation of all APIs provided.
265 pub trait Traceable {}
266 gc_shadowstack!(
267 ShadowStack,
268 Traceable,
269 Rootable,
270 Rooted,
271 Handle,
272 dummy_letroot
273 );
274}