projects/linux·blob master · refs

283 lines · 9.2 KiB

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