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