tock_cells/map_cell.rs
1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Tock specific `MapCell` type for sharing references.
6
7use core::cell::{Cell, UnsafeCell};
8use core::mem::MaybeUninit;
9use core::ptr::drop_in_place;
10
11#[derive(Clone, Copy, PartialEq)]
12enum MapCellState {
13 Uninit,
14 Init,
15 Borrowed,
16}
17
18#[inline(never)]
19#[cold]
20fn access_panic() {
21 panic!("`MapCell` accessed while borrowed");
22}
23
24macro_rules! debug_assert_not_borrowed {
25 ($slf:ident) => {
26 if cfg!(debug_assertions) && $slf.occupied.get() == MapCellState::Borrowed {
27 access_panic();
28 }
29 };
30}
31
32/// A mutable, possibly unset, memory location that provides checked `&mut` access
33/// to its contents via a closure.
34///
35/// A `MapCell` provides checked shared access to its mutable memory. Borrow
36/// rules are enforced by forcing clients to either move the memory out of the
37/// cell or operate on a `&mut` within a closure. You can think of a `MapCell`
38/// as a `Cell<Option<T>>` with an extra "in-use" state to prevent `map` from invoking
39/// undefined behavior when called re-entrantly.
40///
41/// # Examples
42/// ```
43/// # use tock_cells::map_cell::MapCell;
44/// let cell: MapCell<i64> = MapCell::empty();
45///
46/// assert!(cell.is_none());
47/// cell.map(|_| unreachable!("The cell is empty; map does not call the closure"));
48/// assert_eq!(cell.take(), None);
49/// cell.put(10);
50/// assert_eq!(cell.take(), Some(10));
51/// assert_eq!(cell.replace(20), None);
52/// assert_eq!(cell.get(), Some(20));
53///
54/// cell.map(|x| {
55/// assert_eq!(x, &mut 20);
56/// // `map` provides a `&mut` to the contents inside the closure
57/// *x = 30;
58/// });
59/// assert_eq!(cell.replace(60), Some(30));
60/// ```
61pub struct MapCell<T> {
62 // Since val is potentially uninitialized memory, we must be sure to check
63 // `.occupied` before calling `.val.get()` or `.val.assume_init()`. See
64 // [mem::MaybeUninit](https://doc.rust-lang.org/core/mem/union.MaybeUninit.html).
65 val: UnsafeCell<MaybeUninit<T>>,
66
67 // Safety invariants:
68 // - The contents of `val` must be initialized if this is `Init` or `Borrowed`.
69 // - It must be sound to mutate `val` behind a shared reference if this is `Uninit` or `Init`.
70 // No outside mutation can occur while a `&mut` to the contents of `val` exist.
71 occupied: Cell<MapCellState>,
72}
73
74impl<T> Drop for MapCell<T> {
75 fn drop(&mut self) {
76 let state = self.occupied.get();
77 debug_assert_not_borrowed!(self); // This should be impossible
78 if state == MapCellState::Init {
79 unsafe {
80 // SAFETY:
81 // - `occupied` is `Init`; `val` is initialized as an invariant.
82 // - Even though this violates the `occupied` invariant, by causing `val`
83 // to be no longer valid, `self` is immediately dropped.
84 drop_in_place(self.val.get_mut().as_mut_ptr())
85 }
86 }
87 }
88}
89
90impl<T: Copy> MapCell<T> {
91 /// Gets the contents of the cell, if any.
92 ///
93 /// Returns `None` if the cell is empty.
94 ///
95 /// This requires the held type be `Copy` for the same reason [`Cell::get`] does:
96 /// it leaves the contents of `self` intact and so it can't have drop glue.
97 ///
98 /// This returns `None` in release mode if the `MapCell`'s contents are already borrowed.
99 ///
100 /// # Examples
101 /// ```
102 /// # use tock_cells::map_cell::MapCell;
103 /// let cell: MapCell<u32> = MapCell::empty();
104 /// assert_eq!(cell.get(), None);
105 ///
106 /// cell.put(20);
107 /// assert_eq!(cell.get(), Some(20));
108 /// ```
109 ///
110 /// # Panics
111 /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
112 pub fn get(&self) -> Option<T> {
113 debug_assert_not_borrowed!(self);
114 // SAFETY:
115 // - `Init` means that `val` is initialized and can be read
116 // - `T: Copy` so there is no drop glue
117 (self.occupied.get() == MapCellState::Init)
118 .then(|| unsafe { self.val.get().read().assume_init() })
119 }
120}
121
122impl<T> MapCell<T> {
123 /// Creates an empty `MapCell`.
124 pub const fn empty() -> MapCell<T> {
125 MapCell {
126 val: UnsafeCell::new(MaybeUninit::uninit()),
127 occupied: Cell::new(MapCellState::Uninit),
128 }
129 }
130
131 /// Creates a new `MapCell` containing `value`.
132 pub const fn new(value: T) -> MapCell<T> {
133 MapCell {
134 val: UnsafeCell::new(MaybeUninit::new(value)),
135 occupied: Cell::new(MapCellState::Init),
136 }
137 }
138
139 /// Returns `true` if the `MapCell` contains no value.
140 ///
141 /// # Examples
142 /// ```
143 /// # use tock_cells::map_cell::MapCell;
144 /// let x: MapCell<i32> = MapCell::empty();
145 /// assert!(x.is_none());
146 ///
147 /// x.put(10);
148 /// x.map(|_| assert!(!x.is_none()));
149 /// assert!(!x.is_none());
150 /// ```
151 pub fn is_none(&self) -> bool {
152 !self.is_some()
153 }
154
155 /// Returns `true` if the `MapCell` contains a value.
156 ///
157 /// # Examples
158 /// ```
159 /// # use tock_cells::map_cell::MapCell;
160 /// let x: MapCell<i32> = MapCell::new(10);
161 /// assert!(x.is_some());
162 /// x.map(|_| assert!(x.is_some()));
163 ///
164 /// x.take();
165 /// assert!(!x.is_some());
166 /// ```
167 pub fn is_some(&self) -> bool {
168 self.occupied.get() != MapCellState::Uninit
169 }
170
171 /// Takes the value out of the `MapCell`, leaving it empty.
172 ///
173 /// Returns `None` if the cell is empty.
174 ///
175 /// To save size, this has no effect and returns `None` in release mode
176 /// if the `MapCell`'s contents are already borrowed.
177 ///
178 /// # Examples
179 ///
180 /// ```
181 /// # use tock_cells::map_cell::MapCell;
182 /// let cell = MapCell::new(1234);
183 /// let x = &cell;
184 /// let y = &cell;
185 ///
186 /// assert_eq!(x.take(), Some(1234));
187 /// assert_eq!(y.take(), None);
188 /// ```
189 ///
190 /// # Panics
191 /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
192 pub fn take(&self) -> Option<T> {
193 debug_assert_not_borrowed!(self);
194 (self.occupied.get() == MapCellState::Init).then(|| {
195 // SAFETY: Since `occupied` is `Init`, `val` is initialized and can be mutated
196 // behind a shared reference. `result` is therefore initialized.
197 unsafe {
198 let result: MaybeUninit<T> = self.val.get().replace(MaybeUninit::uninit());
199 self.occupied.set(MapCellState::Uninit);
200 result.assume_init()
201 }
202 })
203 }
204
205 /// Puts a value into the `MapCell` without returning the old value.
206 ///
207 /// To save size, this has no effect in release mode if `map` is invoking
208 /// a closure for this cell.
209 ///
210 /// # Panics
211 /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
212 pub fn put(&self, val: T) {
213 debug_assert_not_borrowed!(self);
214 // This will ensure the value as dropped
215 self.replace(val);
216 }
217
218 /// Replaces the contents of the `MapCell`, returning the old value if available.
219 ///
220 /// To save size, this has no effect and returns `None` in release mode
221 /// if the `MapCell`'s contents are already borrowed.
222 ///
223 /// # Panics
224 /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
225 pub fn replace(&self, val: T) -> Option<T> {
226 debug_assert_not_borrowed!(self);
227 let was_occupied = self.occupied.get();
228 match was_occupied {
229 MapCellState::Borrowed => None,
230 MapCellState::Uninit | MapCellState::Init => {
231 self.occupied.set(MapCellState::Init);
232
233 let new_contents = MaybeUninit::new(val);
234 // SAFETY:
235 // - Since `was_occupied` is `Init` or `Uninit`, no `&mut` to the `val`
236 // exists, meaning it is safe to mutate the `get` pointer.
237 let old_contents_maybe_uninit = unsafe { self.val.get().replace(new_contents) };
238
239 (was_occupied == MapCellState::Init).then(|| {
240 // SAFETY:
241 // - If was_occupied is `Init`, `old_contents_maybe_uninit` must be initialized.
242 unsafe { old_contents_maybe_uninit.assume_init() }
243 })
244 }
245 }
246 }
247
248 /// Calls `closure` with a `&mut` of the contents of the `MapCell`, if available.
249 ///
250 /// The closure is only called if the `MapCell` has a value.
251 /// The state of the `MapCell` is unchanged after the closure completes.
252 ///
253 /// # Re-entrancy
254 ///
255 /// This borrows the contents of the cell while the closure is executing.
256 /// Be careful about calling methods on `&self` inside of that closure!
257 /// To save size, this has no effect in release mode, but if debug assertions
258 /// are enabled, this panics to indicate a likely bug.
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// # use tock_cells::map_cell::MapCell;
264 /// let cell = MapCell::new(1234);
265 /// let x = &cell;
266 /// let y = &cell;
267 ///
268 /// x.map(|value| {
269 /// // We have mutable access to the value while in the closure
270 /// *value += 1;
271 /// });
272 ///
273 /// // After the closure completes, the mutable memory is still in the cell,
274 /// // but potentially changed.
275 /// assert_eq!(y.take(), Some(1235));
276 /// ```
277 ///
278 /// # Panics
279 /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
280 #[inline(always)]
281 pub fn map<F, R>(&self, closure: F) -> Option<R>
282 where
283 F: FnOnce(&mut T) -> R,
284 {
285 debug_assert_not_borrowed!(self);
286 (self.occupied.get() == MapCellState::Init).then(move || {
287 self.occupied.set(MapCellState::Borrowed);
288 // `occupied` is reset to initialized at the end of scope,
289 // even if a panic occurs in `closure`.
290 struct ResetToInit<'a>(&'a Cell<MapCellState>);
291 impl Drop for ResetToInit<'_> {
292 #[inline(always)]
293 fn drop(&mut self) {
294 self.0.set(MapCellState::Init);
295 }
296 }
297 let _reset_to_init = ResetToInit(&self.occupied);
298 let val_ptr_mut: *mut T = self.val.get().cast::<T>();
299 // SAFETY: The pointer points to memory for a `T`. Creating the
300 // reference is only sound if the value is initialized, which we
301 // ensured by checking that the state is `MapCell::Init`.
302 let val_ref_mut = unsafe { &mut *val_ptr_mut };
303 closure(val_ref_mut)
304 })
305 }
306
307 /// Behaves like `map`, but returns `default` if there is no value present.
308 #[inline(always)]
309 pub fn map_or<F, R>(&self, default: R, closure: F) -> R
310 where
311 F: FnOnce(&mut T) -> R,
312 {
313 self.map(closure).unwrap_or(default)
314 }
315
316 /// Behaves the same as `map`, except the closure is allowed to return
317 /// an `Option`.
318 #[inline(always)]
319 pub fn and_then<F, R>(&self, closure: F) -> Option<R>
320 where
321 F: FnOnce(&mut T) -> Option<R>,
322 {
323 self.map(closure).flatten()
324 }
325
326 /// If a value is present `modify` is called with a borrow.
327 /// Otherwise, the value is set with `G`.
328 #[inline(always)]
329 pub fn modify_or_replace<F, G>(&self, modify: F, mkval: G)
330 where
331 F: FnOnce(&mut T),
332 G: FnOnce() -> T,
333 {
334 if self.map(modify).is_none() {
335 self.put(mkval());
336 }
337 }
338}
339
340#[cfg(test)]
341mod tests {
342 use super::MapCell;
343
344 struct DropCheck<'a> {
345 flag: &'a mut bool,
346 }
347 impl<'a> Drop for DropCheck<'a> {
348 fn drop(&mut self) {
349 *self.flag = true;
350 }
351 }
352
353 #[test]
354 fn test_drop() {
355 let mut dropped_after_drop = false;
356 let mut dropped_after_put = false;
357 {
358 let cell = MapCell::new(DropCheck {
359 flag: &mut dropped_after_put,
360 });
361 cell.put(DropCheck {
362 flag: &mut dropped_after_drop,
363 });
364 }
365 assert!(dropped_after_drop);
366 assert!(dropped_after_put);
367 }
368
369 #[test]
370 fn test_replace() {
371 let a_cell = MapCell::new(1);
372 let old = a_cell.replace(2);
373 assert_eq!(old, Some(1));
374 assert_eq!(a_cell.take(), Some(2));
375 assert_eq!(a_cell.take(), None);
376 }
377
378 #[test]
379 #[should_panic = "`MapCell` accessed while borrowed"]
380 fn test_map_in_borrow() {
381 let cell = MapCell::new(1);
382 let borrow1 = &cell;
383 let borrow2 = &cell;
384 borrow1.map(|_| borrow2.map(|_| ()));
385 }
386
387 #[test]
388 #[should_panic = "`MapCell` accessed while borrowed"]
389 fn test_replace_in_borrow() {
390 let my_cell = MapCell::new(55);
391 my_cell.map(|_ref1: &mut i32| {
392 // Should fail
393 my_cell.replace(56);
394 });
395 }
396
397 #[test]
398 #[should_panic = "`MapCell` accessed while borrowed"]
399 fn test_put_in_borrow() {
400 let my_cell = MapCell::new(55);
401 my_cell.map(|_ref1: &mut i32| {
402 // Should fail
403 my_cell.put(56);
404 });
405 }
406
407 #[test]
408 #[should_panic = "`MapCell` accessed while borrowed"]
409 fn test_get_in_borrow() {
410 let my_cell = MapCell::new(55);
411 my_cell.map(|_ref1: &mut i32| {
412 // Should fail
413 my_cell.get();
414 });
415 }
416}