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 15 use 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)] 27 use crate::util::polyfills::{self, NonNullExt as _, NumExt as _}; 28 #[cfg(doc)] 29 use 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. 52 pub 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`]. 61 pub trait ByteSliceMut: ByteSlice + DerefMut {} 62 impl<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`. 73 pub 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. 84 pub 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` 101 pub 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`]. 145 pub trait SplitByteSliceMut: SplitByteSlice + ByteSliceMut {} 146 impl<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 159 pub 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 184 pub 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)] 200 unsafe impl ByteSlice for &[u8] {} 201 202 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`. 203 #[allow(clippy::undocumented_unsafe_blocks)] 204 unsafe impl CopyableByteSlice for &[u8] {} 205 206 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`. 207 #[allow(clippy::undocumented_unsafe_blocks)] 208 unsafe 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. 212 unsafe 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. 225 unsafe 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)] 238 unsafe 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. 243 unsafe 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. 301 unsafe 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. 313 unsafe 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)] 326 unsafe 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. 332 unsafe 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)] 346 unsafe 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. 352 unsafe 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)] 365 mod 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)] 408 mod 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 } 435