1 // SPDX-License-Identifier: GPL-2.0 2 3 //! XArray abstraction. 4 //! 5 //! C header: [`include/linux/xarray.h`](srctree/include/linux/xarray.h) 6 7 use crate::{ 8 alloc, bindings, build_assert, 9 error::{Error, Result}, 10 ffi::c_void, 11 types::{ForeignOwnable, NotThreadSafe, Opaque}, 12 }; 13 use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull}; 14 use pin_init::{pin_data, pin_init, pinned_drop, PinInit}; 15 16 /// An array which efficiently maps sparse integer indices to owned objects. 17 /// 18 /// This is similar to a [`crate::alloc::kvec::Vec<Option<T>>`], but more efficient when there are 19 /// holes in the index space, and can be efficiently grown. 20 /// 21 /// # Invariants 22 /// 23 /// `self.xa` is always an initialized and valid [`bindings::xarray`] whose entries are either 24 /// `XA_ZERO_ENTRY` or came from `T::into_foreign`. 25 /// 26 /// # Examples 27 /// 28 /// ```rust 29 /// use kernel::alloc::KBox; 30 /// use kernel::xarray::{AllocKind, XArray}; 31 /// 32 /// let xa = KBox::pin_init(XArray::new(AllocKind::Alloc1), GFP_KERNEL)?; 33 /// 34 /// let dead = KBox::new(0xdead, GFP_KERNEL)?; 35 /// let beef = KBox::new(0xbeef, GFP_KERNEL)?; 36 /// 37 /// let mut guard = xa.lock(); 38 /// 39 /// assert_eq!(guard.get(0), None); 40 /// 41 /// assert_eq!(guard.store(0, dead, GFP_KERNEL)?.as_deref(), None); 42 /// assert_eq!(guard.get(0).copied(), Some(0xdead)); 43 /// 44 /// *guard.get_mut(0).unwrap() = 0xffff; 45 /// assert_eq!(guard.get(0).copied(), Some(0xffff)); 46 /// 47 /// assert_eq!(guard.store(0, beef, GFP_KERNEL)?.as_deref().copied(), Some(0xffff)); 48 /// assert_eq!(guard.get(0).copied(), Some(0xbeef)); 49 /// 50 /// guard.remove(0); 51 /// assert_eq!(guard.get(0), None); 52 /// 53 /// # Ok::<(), Error>(()) 54 /// ``` 55 #[pin_data(PinnedDrop)] 56 pub struct XArray<T: ForeignOwnable> { 57 #[pin] 58 xa: Opaque<bindings::xarray>, 59 _p: PhantomData<T>, 60 } 61 62 #[pinned_drop] 63 impl<T: ForeignOwnable> PinnedDrop for XArray<T> { drop(self: Pin<&mut Self>)64 fn drop(self: Pin<&mut Self>) { 65 self.iter().for_each(|ptr| { 66 let ptr = ptr.as_ptr(); 67 // SAFETY: `ptr` came from `T::into_foreign`. 68 // 69 // INVARIANT: we own the only reference to the array which is being dropped so the 70 // broken invariant is not observable on function exit. 71 drop(unsafe { T::from_foreign(ptr) }) 72 }); 73 74 // SAFETY: `self.xa` is always valid by the type invariant. 75 unsafe { bindings::xa_destroy(self.xa.get()) }; 76 } 77 } 78 79 /// Flags passed to [`XArray::new`] to configure the array's allocation tracking behavior. 80 pub enum AllocKind { 81 /// Consider the first element to be at index 0. 82 Alloc, 83 /// Consider the first element to be at index 1. 84 Alloc1, 85 } 86 87 impl<T: ForeignOwnable> XArray<T> { 88 /// Creates a new initializer for this type. new(kind: AllocKind) -> impl PinInit<Self>89 pub fn new(kind: AllocKind) -> impl PinInit<Self> { 90 let flags = match kind { 91 AllocKind::Alloc => bindings::XA_FLAGS_ALLOC, 92 AllocKind::Alloc1 => bindings::XA_FLAGS_ALLOC1, 93 }; 94 pin_init!(Self { 95 // SAFETY: `xa` is valid while the closure is called. 96 // 97 // INVARIANT: `xa` is initialized here to an empty, valid [`bindings::xarray`]. 98 xa <- Opaque::ffi_init(|xa| unsafe { 99 bindings::xa_init_flags(xa, flags) 100 }), 101 _p: PhantomData, 102 }) 103 } 104 iter(&self) -> impl Iterator<Item = NonNull<c_void>> + '_105 fn iter(&self) -> impl Iterator<Item = NonNull<c_void>> + '_ { 106 let mut index = 0; 107 108 // SAFETY: `self.xa` is always valid by the type invariant. 109 iter::once(unsafe { 110 bindings::xa_find(self.xa.get(), &mut index, usize::MAX, bindings::XA_PRESENT) 111 }) 112 .chain(iter::from_fn(move || { 113 // SAFETY: `self.xa` is always valid by the type invariant. 114 Some(unsafe { 115 bindings::xa_find_after(self.xa.get(), &mut index, usize::MAX, bindings::XA_PRESENT) 116 }) 117 })) 118 .map_while(|ptr| NonNull::new(ptr.cast())) 119 } 120 121 /// Attempts to lock the [`XArray`] for exclusive access. try_lock(&self) -> Option<Guard<'_, T>>122 pub fn try_lock(&self) -> Option<Guard<'_, T>> { 123 // SAFETY: `self.xa` is always valid by the type invariant. 124 if (unsafe { bindings::xa_trylock(self.xa.get()) } != 0) { 125 Some(Guard { 126 xa: self, 127 _not_send: NotThreadSafe, 128 }) 129 } else { 130 None 131 } 132 } 133 134 /// Locks the [`XArray`] for exclusive access. lock(&self) -> Guard<'_, T>135 pub fn lock(&self) -> Guard<'_, T> { 136 // SAFETY: `self.xa` is always valid by the type invariant. 137 unsafe { bindings::xa_lock(self.xa.get()) }; 138 139 Guard { 140 xa: self, 141 _not_send: NotThreadSafe, 142 } 143 } 144 } 145 146 /// A lock guard. 147 /// 148 /// The lock is unlocked when the guard goes out of scope. 149 #[must_use = "the lock unlocks immediately when the guard is unused"] 150 pub struct Guard<'a, T: ForeignOwnable> { 151 xa: &'a XArray<T>, 152 _not_send: NotThreadSafe, 153 } 154 155 impl<T: ForeignOwnable> Drop for Guard<'_, T> { drop(&mut self)156 fn drop(&mut self) { 157 // SAFETY: 158 // - `self.xa.xa` is always valid by the type invariant. 159 // - The caller holds the lock, so it is safe to unlock it. 160 unsafe { bindings::xa_unlock(self.xa.xa.get()) }; 161 } 162 } 163 164 /// The error returned by [`store`](Guard::store). 165 /// 166 /// Contains the underlying error and the value that was not stored. 167 pub struct StoreError<T> { 168 /// The error that occurred. 169 pub error: Error, 170 /// The value that was not stored. 171 pub value: T, 172 } 173 174 impl<T> From<StoreError<T>> for Error { from(value: StoreError<T>) -> Self175 fn from(value: StoreError<T>) -> Self { 176 value.error 177 } 178 } 179 180 impl<'a, T: ForeignOwnable> Guard<'a, T> { load<F, U>(&self, index: usize, f: F) -> Option<U> where F: FnOnce(NonNull<c_void>) -> U,181 fn load<F, U>(&self, index: usize, f: F) -> Option<U> 182 where 183 F: FnOnce(NonNull<c_void>) -> U, 184 { 185 // SAFETY: `self.xa.xa` is always valid by the type invariant. 186 let ptr = unsafe { bindings::xa_load(self.xa.xa.get(), index) }; 187 let ptr = NonNull::new(ptr.cast())?; 188 Some(f(ptr)) 189 } 190 191 /// Provides a reference to the element at the given index. get(&self, index: usize) -> Option<T::Borrowed<'_>>192 pub fn get(&self, index: usize) -> Option<T::Borrowed<'_>> { 193 self.load(index, |ptr| { 194 // SAFETY: `ptr` came from `T::into_foreign`. 195 unsafe { T::borrow(ptr.as_ptr()) } 196 }) 197 } 198 199 /// Provides a mutable reference to the element at the given index. get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>>200 pub fn get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> { 201 self.load(index, |ptr| { 202 // SAFETY: `ptr` came from `T::into_foreign`. 203 unsafe { T::borrow_mut(ptr.as_ptr()) } 204 }) 205 } 206 207 /// Removes and returns the element at the given index. remove(&mut self, index: usize) -> Option<T>208 pub fn remove(&mut self, index: usize) -> Option<T> { 209 // SAFETY: 210 // - `self.xa.xa` is always valid by the type invariant. 211 // - The caller holds the lock. 212 let ptr = unsafe { bindings::__xa_erase(self.xa.xa.get(), index) }.cast(); 213 // SAFETY: 214 // - `ptr` is either NULL or came from `T::into_foreign`. 215 // - `&mut self` guarantees that the lifetimes of [`T::Borrowed`] and [`T::BorrowedMut`] 216 // borrowed from `self` have ended. 217 unsafe { T::try_from_foreign(ptr) } 218 } 219 220 /// Stores an element at the given index. 221 /// 222 /// May drop the lock if needed to allocate memory, and then reacquire it afterwards. 223 /// 224 /// On success, returns the element which was previously at the given index. 225 /// 226 /// On failure, returns the element which was attempted to be stored. store( &mut self, index: usize, value: T, gfp: alloc::Flags, ) -> Result<Option<T>, StoreError<T>>227 pub fn store( 228 &mut self, 229 index: usize, 230 value: T, 231 gfp: alloc::Flags, 232 ) -> Result<Option<T>, StoreError<T>> { 233 build_assert!( 234 T::FOREIGN_ALIGN >= 4, 235 "pointers stored in XArray must be 4-byte aligned" 236 ); 237 let new = value.into_foreign(); 238 239 let old = { 240 let new = new.cast(); 241 // SAFETY: 242 // - `self.xa.xa` is always valid by the type invariant. 243 // - The caller holds the lock. 244 // 245 // INVARIANT: `new` came from `T::into_foreign`. 246 unsafe { bindings::__xa_store(self.xa.xa.get(), index, new, gfp.as_raw()) } 247 }; 248 249 // SAFETY: `__xa_store` returns the old entry at this index on success or `xa_err` if an 250 // error happened. 251 let errno = unsafe { bindings::xa_err(old) }; 252 if errno != 0 { 253 // SAFETY: `new` came from `T::into_foreign` and `__xa_store` does not take 254 // ownership of the value on error. 255 let value = unsafe { T::from_foreign(new) }; 256 Err(StoreError { 257 value, 258 error: Error::from_errno(errno), 259 }) 260 } else { 261 let old = old.cast(); 262 // SAFETY: `ptr` is either NULL or came from `T::into_foreign`. 263 // 264 // NB: `XA_ZERO_ENTRY` is never returned by functions belonging to the Normal XArray 265 // API; such entries present as `NULL`. 266 Ok(unsafe { T::try_from_foreign(old) }) 267 } 268 } 269 } 270 271 // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`. 272 unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {} 273 274 // SAFETY: `XArray<T>` serialises the interior mutability it provides so it is `Sync` iff `T` is 275 // `Send`. 276 unsafe impl<T: ForeignOwnable + Send> Sync for XArray<T> {} 277