projects/linux·blob master · refs

434 lines · 17.1 KiB

1// SPDX-License-Identifier: (BSD-2-Clause OR Apache-2.0) OR MIT
2//
3// Copyright 2024 The Fuchsia Authors
4//
5// Licensed under a BSD-style license <LICENSE-BSD>, Apache License, Version 2.0
6// <LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0>, or the MIT
7// license <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your option.
8// This file may not be copied, modified, or distributed except according to
9// those terms.
10
11//! Traits for types that encapsulate a `[u8]`.
12//!
13//! These traits are used to bound the `B` parameter of [`Ref`].
14
15use core::{
16 cell,
17 ops::{Deref, DerefMut},
18};
19
20// For each trait polyfill, as soon as the corresponding feature is stable, the
21// polyfill import will be unused because method/function resolution will prefer
22// the inherent method/function over a trait method/function. Thus, we suppress
23// the `unused_imports` warning.
24//
25// See the documentation on `util::polyfills` for more information.
26#[allow(unused_imports)]
27use crate::util::polyfills::{self, NonNullExt as _, NumExt as _};
28#[cfg(doc)]
29use crate::Ref;
30
31/// A mutable or immutable reference to a byte slice.
32///
33/// `ByteSlice` abstracts over the mutability of a byte slice reference, and is
34/// implemented for various special reference types such as
35/// [`Ref<[u8]>`](core::cell::Ref) and [`RefMut<[u8]>`](core::cell::RefMut).
36///
37/// # Safety
38///
39/// Implementations of `ByteSlice` must promise that their implementations of
40/// [`Deref`] and [`DerefMut`] are "stable". In particular, given `B: ByteSlice`
41/// and `b: B`, two calls, each to either `b.deref()` or `b.deref_mut()`, must
42/// return a byte slice with the same address and length. This must hold even if
43/// the two calls are separated by an arbitrary sequence of calls to methods on
44/// `ByteSlice`, [`ByteSliceMut`], [`IntoByteSlice`], or [`IntoByteSliceMut`],
45/// or on their super-traits. This does *not* need to hold if the two calls are
46/// separated by any method calls, field accesses, or field modifications *other
47/// than* those from these traits.
48///
49/// Note that this also implies that, given `b: B`, the address and length
50/// cannot be modified via objects other than `b`, either on the same thread or
51/// on another thread.
52pub unsafe trait ByteSlice: Deref<Target = [u8]> + Sized {}
53
54/// A mutable reference to a byte slice.
55///
56/// `ByteSliceMut` abstracts over various ways of storing a mutable reference to
57/// a byte slice, and is implemented for various special reference types such as
58/// `RefMut<[u8]>`.
59///
60/// `ByteSliceMut` is a shorthand for [`ByteSlice`] and [`DerefMut`].
61pub trait ByteSliceMut: ByteSlice + DerefMut {}
62impl<B: ByteSlice + DerefMut> ByteSliceMut for B {}
63
64/// A [`ByteSlice`] which can be copied without violating dereference stability.
65///
66/// # Safety
67///
68/// If `B: CopyableByteSlice`, then the dereference stability properties
69/// required by [`ByteSlice`] (see that trait's safety documentation) do not
70/// only hold regarding two calls to `b.deref()` or `b.deref_mut()`, but also
71/// hold regarding `c.deref()` or `c.deref_mut()`, where `c` is produced by
72/// copying `b`.
73pub unsafe trait CopyableByteSlice: ByteSlice + Copy + CloneableByteSlice {}
74
75/// A [`ByteSlice`] which can be cloned without violating dereference stability.
76///
77/// # Safety
78///
79/// If `B: CloneableByteSlice`, then the dereference stability properties
80/// required by [`ByteSlice`] (see that trait's safety documentation) do not
81/// only hold regarding two calls to `b.deref()` or `b.deref_mut()`, but also
82/// hold regarding `c.deref()` or `c.deref_mut()`, where `c` is produced by
83/// `b.clone()`, `b.clone().clone()`, etc.
84pub unsafe trait CloneableByteSlice: ByteSlice + Clone {}
85
86/// A [`ByteSlice`] that can be split in two.
87///
88/// # Safety
89///
90/// Unsafe code may depend for its soundness on the assumption that `split_at`
91/// and `split_at_unchecked` are implemented correctly. In particular, given `B:
92/// SplitByteSlice` and `b: B`, if `b.deref()` returns a byte slice with address
93/// `addr` and length `len`, then if `split <= len`, both of these
94/// invocations:
95/// - `b.split_at(split)`
96/// - `b.split_at_unchecked(split)`
97///
98/// ...will return `(first, second)` such that:
99/// - `first`'s address is `addr` and its length is `split`
100/// - `second`'s address is `addr + split` and its length is `len - split`
101pub unsafe trait SplitByteSlice: ByteSlice {
102 /// Attempts to split `self` at the midpoint.
103 ///
104 /// `s.split_at(mid)` returns `Ok((s[..mid], s[mid..]))` if `mid <=
105 /// s.deref().len()` and otherwise returns `Err(s)`.
106 ///
107 /// # Safety
108 ///
109 /// Unsafe code may rely on this function correctly implementing the above
110 /// functionality.
111 #[inline]
112 fn split_at(self, mid: usize) -> Result<(Self, Self), Self> {
113 if mid <= self.deref().len() {
114 // SAFETY: Above, we ensure that `mid <= self.deref().len()`. By
115 // invariant on `ByteSlice`, a supertrait of `SplitByteSlice`,
116 // `.deref()` is guaranteed to be "stable"; i.e., it will always
117 // dereference to a byte slice of the same address and length. Thus,
118 // we can be sure that the above precondition remains satisfied
119 // through the call to `split_at_unchecked`.
120 unsafe { Ok(self.split_at_unchecked(mid)) }
121 } else {
122 Err(self)
123 }
124 }
125
126 /// Splits the slice at the midpoint, possibly omitting bounds checks.
127 ///
128 /// `s.split_at_unchecked(mid)` returns `s[..mid]` and `s[mid..]`.
129 ///
130 /// # Safety
131 ///
132 /// `mid` must not be greater than `self.deref().len()`.
133 ///
134 /// # Panics
135 ///
136 /// Implementations of this method may choose to perform a bounds check and
137 /// panic if `mid > self.deref().len()`. They may also panic for any other
138 /// reason. Since it is optional, callers must not rely on this behavior for
139 /// soundness.
140 #[must_use]
141 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self);
142}
143
144/// A shorthand for [`SplitByteSlice`] and [`ByteSliceMut`].
145pub trait SplitByteSliceMut: SplitByteSlice + ByteSliceMut {}
146impl<B: SplitByteSlice + ByteSliceMut> SplitByteSliceMut for B {}
147
148#[allow(clippy::missing_safety_doc)] // There's a `Safety` section on `into_byte_slice`.
149/// A [`ByteSlice`] that conveys no ownership, and so can be converted into a
150/// byte slice.
151///
152/// Some `ByteSlice` types (notably, the standard library's [`Ref`] type) convey
153/// ownership, and so they cannot soundly be moved by-value into a byte slice
154/// type (`&[u8]`). Some methods in this crate's API (such as [`Ref::into_ref`])
155/// are only compatible with `ByteSlice` types without these ownership
156/// semantics.
157///
158/// [`Ref`]: core::cell::Ref
159pub unsafe trait IntoByteSlice<'a>: ByteSlice {
160 /// Coverts `self` into a `&[u8]`.
161 ///
162 /// # Safety
163 ///
164 /// The returned reference has the same address and length as `self.deref()`
165 /// and `self.deref_mut()`.
166 ///
167 /// Note that, combined with the safety invariant on [`ByteSlice`], this
168 /// safety invariant implies that the returned reference is "stable" in the
169 /// sense described in the `ByteSlice` docs.
170 fn into_byte_slice(self) -> &'a [u8];
171}
172
173#[allow(clippy::missing_safety_doc)] // There's a `Safety` section on `into_byte_slice_mut`.
174/// A [`ByteSliceMut`] that conveys no ownership, and so can be converted into a
175/// mutable byte slice.
176///
177/// Some `ByteSliceMut` types (notably, the standard library's [`RefMut`] type)
178/// convey ownership, and so they cannot soundly be moved by-value into a byte
179/// slice type (`&mut [u8]`). Some methods in this crate's API (such as
180/// [`Ref::into_mut`]) are only compatible with `ByteSliceMut` types without
181/// these ownership semantics.
182///
183/// [`RefMut`]: core::cell::RefMut
184pub unsafe trait IntoByteSliceMut<'a>: IntoByteSlice<'a> + ByteSliceMut {
185 /// Coverts `self` into a `&mut [u8]`.
186 ///
187 /// # Safety
188 ///
189 /// The returned reference has the same address and length as `self.deref()`
190 /// and `self.deref_mut()`.
191 ///
192 /// Note that, combined with the safety invariant on [`ByteSlice`], this
193 /// safety invariant implies that the returned reference is "stable" in the
194 /// sense described in the `ByteSlice` docs.
195 fn into_byte_slice_mut(self) -> &'a mut [u8];
196}
197
198// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
199#[allow(clippy::undocumented_unsafe_blocks)]
200unsafe impl ByteSlice for &[u8] {}
201
202// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
203#[allow(clippy::undocumented_unsafe_blocks)]
204unsafe impl CopyableByteSlice for &[u8] {}
205
206// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
207#[allow(clippy::undocumented_unsafe_blocks)]
208unsafe impl CloneableByteSlice for &[u8] {}
209
210// SAFETY: This delegates to `polyfills:split_at_unchecked`, which is documented
211// to correctly split `self` into two slices at the given `mid` point.
212unsafe impl SplitByteSlice for &[u8] {
213 #[inline]
214 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
215 // SAFETY: By contract on caller, `mid` is not greater than
216 // `self.len()`.
217 #[allow(clippy::multiple_unsafe_ops_per_block)]
218 unsafe {
219 (<[u8]>::get_unchecked(self, ..mid), <[u8]>::get_unchecked(self, mid..))
220 }
221 }
222}
223
224// SAFETY: See inline.
225unsafe impl<'a> IntoByteSlice<'a> for &'a [u8] {
226 #[inline(always)]
227 fn into_byte_slice(self) -> &'a [u8] {
228 // SAFETY: It would be patently insane to implement `<Deref for
229 // &[u8]>::deref` as anything other than `fn deref(&self) -> &[u8] {
230 // *self }`. Assuming this holds, then `self` is stable as required by
231 // `into_byte_slice`.
232 self
233 }
234}
235
236// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
237#[allow(clippy::undocumented_unsafe_blocks)]
238unsafe impl ByteSlice for &mut [u8] {}
239
240// SAFETY: This delegates to `polyfills:split_at_mut_unchecked`, which is
241// documented to correctly split `self` into two slices at the given `mid`
242// point.
243unsafe impl SplitByteSlice for &mut [u8] {
244 #[inline]
245 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
246 use core::slice::from_raw_parts_mut;
247
248 // `l_ptr` is non-null, because `self` is non-null, by invariant on
249 // `&mut [u8]`.
250 let l_ptr = self.as_mut_ptr();
251
252 // SAFETY: By contract on caller, `mid` is not greater than
253 // `self.len()`.
254 let r_ptr = unsafe { l_ptr.add(mid) };
255
256 let l_len = mid;
257
258 // SAFETY: By contract on caller, `mid` is not greater than
259 // `self.len()`.
260 //
261 // FIXME(#67): Remove this allow. See NumExt for more details.
262 #[allow(unstable_name_collisions)]
263 let r_len = unsafe { self.len().unchecked_sub(mid) };
264
265 // SAFETY: These invocations of `from_raw_parts_mut` satisfy its
266 // documented safety preconditions [1]:
267 // - The data `l_ptr` and `r_ptr` are valid for both reads and writes of
268 // `l_len` and `r_len` bytes, respectively, and they are trivially
269 // aligned. In particular:
270 // - The entire memory range of each slice is contained within a
271 // single allocated object, since `l_ptr` and `r_ptr` are both
272 // derived from within the address range of `self`.
273 // - Both `l_ptr` and `r_ptr` are non-null and trivially aligned.
274 // `self` is non-null by invariant on `&mut [u8]`, and the
275 // operations that derive `l_ptr` and `r_ptr` from `self` do not
276 // nullify either pointer.
277 // - The data `l_ptr` and `r_ptr` point to `l_len` and `r_len`,
278 // respectively, consecutive properly initialized values of type `u8`.
279 // This is true for `self` by invariant on `&mut [u8]`, and remains
280 // true for these two sub-slices of `self`.
281 // - The memory referenced by the returned slice cannot be accessed
282 // through any other pointer (not derived from the return value) for
283 // the duration of lifetime `'a``, because:
284 // - `split_at_unchecked` consumes `self` (which is not `Copy`),
285 // - `split_at_unchecked` does not exfiltrate any references to this
286 // memory, besides those references returned below,
287 // - the returned slices are non-overlapping.
288 // - The individual sizes of the sub-slices of `self` are no larger than
289 // `isize::MAX`, because their combined sizes are no larger than
290 // `isize::MAX`, by invariant on `self`.
291 //
292 // [1] https://doc.rust-lang.org/std/slice/fn.from_raw_parts_mut.html#safety
293 #[allow(clippy::multiple_unsafe_ops_per_block)]
294 unsafe {
295 (from_raw_parts_mut(l_ptr, l_len), from_raw_parts_mut(r_ptr, r_len))
296 }
297 }
298}
299
300// SAFETY: See inline.
301unsafe impl<'a> IntoByteSlice<'a> for &'a mut [u8] {
302 #[inline(always)]
303 fn into_byte_slice(self) -> &'a [u8] {
304 // SAFETY: It would be patently insane to implement `<Deref for &mut
305 // [u8]>::deref` as anything other than `fn deref(&self) -> &[u8] {
306 // *self }`. Assuming this holds, then `self` is stable as required by
307 // `into_byte_slice`.
308 self
309 }
310}
311
312// SAFETY: See inline.
313unsafe impl<'a> IntoByteSliceMut<'a> for &'a mut [u8] {
314 #[inline(always)]
315 fn into_byte_slice_mut(self) -> &'a mut [u8] {
316 // SAFETY: It would be patently insane to implement `<DerefMut for &mut
317 // [u8]>::deref` as anything other than `fn deref_mut(&mut self) -> &mut
318 // [u8] { *self }`. Assuming this holds, then `self` is stable as
319 // required by `into_byte_slice_mut`.
320 self
321 }
322}
323
324// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
325#[allow(clippy::undocumented_unsafe_blocks)]
326unsafe impl ByteSlice for cell::Ref<'_, [u8]> {}
327
328// SAFETY: This delegates to stdlib implementation of `Ref::map_split`, which is
329// assumed to be correct, and `SplitByteSlice::split_at_unchecked`, which is
330// documented to correctly split `self` into two slices at the given `mid`
331// point.
332unsafe impl SplitByteSlice for cell::Ref<'_, [u8]> {
333 #[inline]
334 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
335 cell::Ref::map_split(self, |slice|
336 // SAFETY: By precondition on caller, `mid` is not greater than
337 // `slice.len()`.
338 unsafe {
339 SplitByteSlice::split_at_unchecked(slice, mid)
340 })
341 }
342}
343
344// FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
345#[allow(clippy::undocumented_unsafe_blocks)]
346unsafe impl ByteSlice for cell::RefMut<'_, [u8]> {}
347
348// SAFETY: This delegates to stdlib implementation of `RefMut::map_split`, which
349// is assumed to be correct, and `SplitByteSlice::split_at_unchecked`, which is
350// documented to correctly split `self` into two slices at the given `mid`
351// point.
352unsafe impl SplitByteSlice for cell::RefMut<'_, [u8]> {
353 #[inline]
354 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
355 cell::RefMut::map_split(self, |slice|
356 // SAFETY: By precondition on caller, `mid` is not greater than
357 // `slice.len()`
358 unsafe {
359 SplitByteSlice::split_at_unchecked(slice, mid)
360 })
361 }
362}
363
364#[cfg(kani)]
365mod proofs {
366 use super::*;
367
368 fn any_vec() -> Vec<u8> {
369 let len = kani::any();
370 kani::assume(len <= crate::DstLayout::MAX_SIZE);
371 vec![0u8; len]
372 }
373
374 #[kani::proof]
375 fn prove_split_at_unchecked() {
376 let v = any_vec();
377 let slc = v.as_slice();
378 let mid = kani::any();
379 kani::assume(mid <= slc.len());
380 let (l, r) = unsafe { slc.split_at_unchecked(mid) };
381 assert_eq!(l.len() + r.len(), slc.len());
382
383 let slc: *const _ = slc;
384 let l: *const _ = l;
385 let r: *const _ = r;
386
387 assert_eq!(slc.cast::<u8>(), l.cast::<u8>());
388 assert_eq!(unsafe { slc.cast::<u8>().add(mid) }, r.cast::<u8>());
389
390 let mut v = any_vec();
391 let slc = v.as_mut_slice();
392 let len = slc.len();
393 let mid = kani::any();
394 kani::assume(mid <= slc.len());
395 let (l, r) = unsafe { slc.split_at_unchecked(mid) };
396 assert_eq!(l.len() + r.len(), len);
397
398 let l: *mut _ = l;
399 let r: *mut _ = r;
400 let slc: *mut _ = slc;
401
402 assert_eq!(slc.cast::<u8>(), l.cast::<u8>());
403 assert_eq!(unsafe { slc.cast::<u8>().add(mid) }, r.cast::<u8>());
404 }
405}
406
407#[cfg(test)]
408mod tests {
409 use core::cell::RefCell;
410
411 use super::*;
412
413 #[test]
414 fn test_ref_split_at_unchecked() {
415 let cell = RefCell::new([1, 2, 3, 4]);
416 let borrow = cell.borrow();
417 let slice_ref: cell::Ref<'_, [u8]> = cell::Ref::map(borrow, |a| &a[..]);
418 // SAFETY: 2 is within bounds of [1, 2, 3, 4]
419 let (l, r) = unsafe { slice_ref.split_at_unchecked(2) };
420 assert_eq!(*l, [1, 2]);
421 assert_eq!(*r, [3, 4]);
422 }
423
424 #[test]
425 fn test_ref_mut_split_at_unchecked() {
426 let cell = RefCell::new([1, 2, 3, 4]);
427 let borrow_mut = cell.borrow_mut();
428 let slice_ref_mut: cell::RefMut<'_, [u8]> = cell::RefMut::map(borrow_mut, |a| &mut a[..]);
429 // SAFETY: 2 is within bounds of [1, 2, 3, 4]
430 let (l, r) = unsafe { slice_ref_mut.split_at_unchecked(2) };
431 assert_eq!(*l, [1, 2]);
432 assert_eq!(*r, [3, 4]);
433 }
434}