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 190 191 192 193 194 195 196 197 198 199 200 201 202 203
//! A dynamically-sized heap-backed data page. Comprises a user-chosen header and //! data array packed into a single allocation. //! //! ## Example //! //! ``` //! use pages::Page; //! // A really crappy replacement for Box<Option<usize>> //! struct Maybe(Page::<bool, usize>); //! impl Maybe { //! fn new() -> Self { Maybe(Page::new(false, 1)) } //! fn put(&mut self, value: usize) { //! *self.0.header_mut() = true; // occupied //! let item: *mut usize = self.0.data_mut()[0].as_mut_ptr(); //! unsafe { item.write(value); } //! } //! fn get(&mut self) -> Option<usize> { //! if !(*self.0.header()) { return None; } //! let item: *mut usize = self.0.data_mut()[0].as_mut_ptr(); //! *self.0.header_mut() = false; // free //! Some(unsafe { *item }) //! } //! } //! //! let mut maybe = Maybe::new(); //! assert_eq!(maybe.get(), None); //! maybe.put(42); //! assert_eq!(maybe.get(), Some(42)); //! ``` #![no_std] extern crate alloc; use alloc::alloc::{Layout, alloc, dealloc}; use core::convert::TryInto; use core::marker::PhantomData; use core::mem::MaybeUninit; use core::ptr::{NonNull, drop_in_place}; use core::slice; /// A dynamically-sized heap-backed data page. Comprises a user-chosen header and /// data array packed into a single allocation. It is an owned object and the /// internal representation is a [`NonNull`]. /// /// ## Example /// /// ``` /// use pages::Page; /// // A really crappy replacement for Box<Option<usize>> /// struct Maybe(Page::<bool, usize>); /// impl Maybe { /// fn new() -> Self { Maybe(Page::new(false, 1)) } /// fn put(&mut self, value: usize) { /// *self.0.header_mut() = true; // occupied /// let item: *mut usize = self.0.data_mut()[0].as_mut_ptr(); /// unsafe { item.write(value); } /// } /// fn get(&mut self) -> Option<usize> { /// if !(*self.0.header()) { return None; } /// let item: *mut usize = self.0.data_mut()[0].as_mut_ptr(); /// *self.0.header_mut() = false; // free /// Some(unsafe { *item }) /// } /// } /// /// let mut maybe = Maybe::new(); /// assert_eq!(maybe.get(), None); /// maybe.put(42); /// assert_eq!(maybe.get(), Some(42)); /// ``` /// /// ## Notes /// /// Data is exposed as a [`MaybeUninit`] slice for maximum flexibility. /// Unfortunately this means we're unable to automatically drop the data /// for you in our destructor. You could cause a memory leak if you don't. #[repr(transparent)] pub struct Page<H, T> { inner: NonNull<u8>, _phantom: PhantomData<(H,T)>, } impl<H, T> Page<H, T> { /// Creates a new [`Page`] with the capacity for the provided number of items on /// the heap and a header. /// /// ## Notes /// /// Will panic if the header plus padding is extremely large (around 2^32 bytes) pub fn new(header: H, items: u32) -> Self { // Get a layout and prepare a book describing it. We do this before // allocation in case it fails. let layout = PageLayout::for_capacity::<H, T>(items); let book = Book { items, data: layout.data.try_into().unwrap() }; // Allocate and prepare pointers to what we need to initialise. All safe if // you trust the layout is correct, which is presumed throughout. let raw_ptr = unsafe { alloc(layout.layout) }; let header_ptr = raw_ptr.cast::<H>(); let book_ptr = unsafe { raw_ptr.add(layout.book) }.cast::<Book>(); // Now we need to do that initialisation. let inner = unsafe { header_ptr.write(header); book_ptr.write(book); NonNull::new_unchecked(header_ptr.cast()) }; Page { inner, _phantom: PhantomData } } /// The capacity of our data array. #[inline(always)] pub fn capacity(&self) -> u32 { self.book().items } /// Access to the header by reference. #[inline(always)] pub fn header(&self) -> &H { unsafe { &*self.inner.as_ptr().cast() } } /// Access to the header by mut reference. #[inline(always)] pub fn header_mut(&mut self) -> &mut H { unsafe { &mut *self.inner.as_ptr().cast() } } /// Access to the raw data as a slice. #[inline(always)] pub fn data(&self) -> &[MaybeUninit<T>] { unsafe { slice::from_raw_parts(self.data_ptr(), self.book().items as usize) } } /// Access to the raw data as a mut slice. #[inline(always)] pub fn data_mut(&mut self) -> &mut [MaybeUninit<T>] { unsafe { slice::from_raw_parts_mut(self.data_ptr(), self.book().items as usize) } } #[inline(always)] /// Returns a copy of our Book. fn book(&self) -> Book { let raw = self.inner.as_ptr(); let book = PageLayout::static_prefix::<H>().1; unsafe { *raw.add(book).cast() } } #[inline(always)] /// Returns a pointer to the start of the data section. fn data_ptr(&self) -> *mut MaybeUninit<T> { let raw = self.inner.as_ptr(); unsafe { raw.add(self.book().data as usize) }.cast() } } unsafe impl<H: Send, T: Send> Send for Page<H, T> {} unsafe impl<H: Sync, T: Sync> Sync for Page<H, T> {} impl<H, T> Drop for Page<H, T> { // Safety: we have exclusive access. fn drop(&mut self) { // Drop the header. let raw = self.inner.as_ptr(); unsafe { drop_in_place(raw.cast::<H>()); } // Deallocate the memory. let layout = PageLayout::for_capacity::<H, T>(self.book().items); unsafe { dealloc(raw, layout.layout); } } } /// Just the numerics from a page layout. Very compact (64 bits). #[derive(Clone,Copy)] struct Book { /// Our item capacity items: u32, /// The offset from the start of a page to the data array. data: u32, } /// Describes the memory layout for a Page. This unassuming struct with no unsafe in /// sight is actually the most important thing for safety. #[derive(Clone,Copy)] struct PageLayout { /// Offset from the start of a page where the book is located. book: usize, /// Offset from the start of a page where the data is located. data: usize, /// A layout suitable for allocation/deallocation of a page. layout: Layout, } impl PageLayout { /// Creates a `PageLayout` with the given item capacity. #[inline(always)] fn for_capacity<H, T>(items: u32) -> Self { let (prefix, book) = Self::static_prefix::<H>(); let array = Layout::array::<T>(items as usize).unwrap(); let (layout, data) = prefix.extend(array).unwrap(); let layout = layout.pad_to_align(); Self { book, data, layout } } /// Info about the statically sized prefix of the page. /// The usize returned is book's offset. #[inline(always)] fn static_prefix<H>() -> (Layout, usize) { let book = Layout::new::<Book>(); let header = Layout::new::<H>(); header.extend(book).unwrap() } }