projects/linux·blob v6.16-rc5 · refs

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