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
9use core::{marker::PhantomData, ops::Range, ptr::NonNull};
10
11#[allow(unused_imports)]
12use crate::util::polyfills::NumExt as _;
13use crate::{
14 layout::{CastType, DstLayout, MetadataCastError},
15 util::AsAddress,
16 AlignmentError, CastError, KnownLayout, PointerMetadata, SizeError,
17};
18
19pub(crate) use _def::PtrInner;
20
21mod _def {
22 use super::*;
23 /// The inner pointer stored inside a [`Ptr`][crate::Ptr].
24 ///
25 /// `PtrInner<'a, T>` is [covariant] in `'a` and invariant in `T`.
26 ///
27 /// [covariant]: https://doc.rust-lang.org/reference/subtyping.html
28 pub(crate) struct PtrInner<'a, T>
29 where
30 T: ?Sized,
31 {
32 /// # Invariants
33 ///
34 /// 0. If `ptr`'s referent is not zero sized, then `ptr` has valid
35 /// provenance for its referent, which is entirely contained in some
36 /// Rust allocation, `A`.
37 /// 1. If `ptr`'s referent is not zero sized, `A` is guaranteed to live
38 /// for at least `'a`.
39 ///
40 /// # Postconditions
41 ///
42 /// By virtue of these invariants, code may assume the following, which
43 /// are logical implications of the invariants:
44 /// - `ptr`'s referent is not larger than `isize::MAX` bytes \[1\]
45 /// - `ptr`'s referent does not wrap around the address space \[1\]
46 ///
47 /// \[1\] Per <https://doc.rust-lang.org/1.85.0/std/ptr/index.html#allocated-object>:
48 ///
49 /// For any allocated object with `base` address, `size`, and a set of
50 /// `addresses`, the following are guaranteed:
51 /// ...
52 /// - `size <= isize::MAX`
53 ///
54 /// As a consequence of these guarantees, given any address `a` within
55 /// the set of addresses of an allocated object:
56 /// ...
57 /// - It is guaranteed that, given `o = a - base` (i.e., the offset of
58 /// `a` within the allocated object), `base + o` will not wrap around
59 /// the address space (in other words, will not overflow `usize`)
60 ptr: NonNull<T>,
61 // SAFETY: `&'a UnsafeCell<T>` is covariant in `'a` and invariant in `T`
62 // [1]. We use this construction rather than the equivalent `&mut T`,
63 // because our MSRV of 1.65 prohibits `&mut` types in const contexts.
64 //
65 // [1] https://doc.rust-lang.org/1.81.0/reference/subtyping.html#variance
66 _marker: PhantomData<&'a core::cell::UnsafeCell<T>>,
67 }
68
69 impl<'a, T: 'a + ?Sized> Copy for PtrInner<'a, T> {}
70 impl<'a, T: 'a + ?Sized> Clone for PtrInner<'a, T> {
71 fn clone(&self) -> PtrInner<'a, T> {
72 // SAFETY: None of the invariants on `ptr` are affected by having
73 // multiple copies of a `PtrInner`.
74 *self
75 }
76 }
77
78 impl<'a, T: 'a + ?Sized> PtrInner<'a, T> {
79 /// Constructs a `Ptr` from a [`NonNull`].
80 ///
81 /// # Safety
82 ///
83 /// The caller promises that:
84 ///
85 /// 0. If `ptr`'s referent is not zero sized, then `ptr` has valid
86 /// provenance for its referent, which is entirely contained in some
87 /// Rust allocation, `A`.
88 /// 1. If `ptr`'s referent is not zero sized, `A` is guaranteed to live
89 /// for at least `'a`.
90 pub(crate) const unsafe fn new(ptr: NonNull<T>) -> PtrInner<'a, T> {
91 // SAFETY: The caller has promised to satisfy all safety invariants
92 // of `PtrInner`.
93 Self { ptr, _marker: PhantomData }
94 }
95
96 /// Converts this `PtrInner<T>` to a [`NonNull<T>`].
97 ///
98 /// Note that this method does not consume `self`. The caller should
99 /// watch out for `unsafe` code which uses the returned `NonNull` in a
100 /// way that violates the safety invariants of `self`.
101 pub(crate) const fn as_non_null(&self) -> NonNull<T> {
102 self.ptr
103 }
104 }
105}
106
107impl<'a, T: ?Sized> PtrInner<'a, T> {
108 /// Constructs a `PtrInner` from a reference.
109 #[inline]
110 pub(crate) fn from_ref(ptr: &'a T) -> Self {
111 let ptr = NonNull::from(ptr);
112 // SAFETY:
113 // 0. If `ptr`'s referent is not zero sized, then `ptr`, by invariant on
114 // `&'a T` [1], has valid provenance for its referent, which is
115 // entirely contained in some Rust allocation, `A`.
116 // 1. If `ptr`'s referent is not zero sized, then `A`, by invariant on
117 // `&'a T`, is guaranteed to live for at least `'a`.
118 //
119 // [1] Per https://doc.rust-lang.org/1.85.0/std/primitive.reference.html#safety:
120 //
121 // For all types, `T: ?Sized`, and for all `t: &T` or `t: &mut T`,
122 // when such values cross an API boundary, the following invariants
123 // must generally be upheld:
124 // ...
125 // - if `size_of_val(t) > 0`, then `t` is dereferenceable for
126 // `size_of_val(t)` many bytes
127 //
128 // If `t` points at address `a`, being “dereferenceable” for N bytes
129 // means that the memory range `[a, a + N)` is all contained within a
130 // single allocated object.
131 unsafe { Self::new(ptr) }
132 }
133
134 /// Constructs a `PtrInner` from a mutable reference.
135 #[inline]
136 pub(crate) fn from_mut(ptr: &'a mut T) -> Self {
137 let ptr = NonNull::from(ptr);
138 // SAFETY:
139 // 0. If `ptr`'s referent is not zero sized, then `ptr`, by invariant on
140 // `&'a mut T` [1], has valid provenance for its referent, which is
141 // entirely contained in some Rust allocation, `A`.
142 // 1. If `ptr`'s referent is not zero sized, then `A`, by invariant on
143 // `&'a mut T`, is guaranteed to live for at least `'a`.
144 //
145 // [1] Per https://doc.rust-lang.org/1.85.0/std/primitive.reference.html#safety:
146 //
147 // For all types, `T: ?Sized`, and for all `t: &T` or `t: &mut T`,
148 // when such values cross an API boundary, the following invariants
149 // must generally be upheld:
150 // ...
151 // - if `size_of_val(t) > 0`, then `t` is dereferenceable for
152 // `size_of_val(t)` many bytes
153 //
154 // If `t` points at address `a`, being “dereferenceable” for N bytes
155 // means that the memory range `[a, a + N)` is all contained within a
156 // single allocated object.
157 unsafe { Self::new(ptr) }
158 }
159}
160
161#[allow(clippy::needless_lifetimes)]
162impl<'a, T> PtrInner<'a, [T]> {
163 /// Creates a pointer which addresses the given `range` of self.
164 ///
165 /// # Safety
166 ///
167 /// `range` is a valid range (`start <= end`) and `end <= self.len()`.
168 pub(crate) unsafe fn slice_unchecked(self, range: Range<usize>) -> Self {
169 let base = self.as_non_null().cast::<T>().as_ptr();
170
171 // SAFETY: The caller promises that `start <= end <= self.len()`. By
172 // invariant, if `self`'s referent is not zero-sized, then `self` refers
173 // to a byte range which is contained within a single allocation, which
174 // is no more than `isize::MAX` bytes long, and which does not wrap
175 // around the address space. Thus, this pointer arithmetic remains
176 // in-bounds of the same allocation, and does not wrap around the
177 // address space. The offset (in bytes) does not overflow `isize`.
178 //
179 // If `self`'s referent is zero-sized, then these conditions are
180 // trivially satisfied.
181 let base = unsafe { base.add(range.start) };
182
183 // SAFETY: The caller promises that `start <= end`, and so this will not
184 // underflow.
185 #[allow(unstable_name_collisions, clippy::incompatible_msrv)]
186 let len = unsafe { range.end.unchecked_sub(range.start) };
187
188 let ptr = core::ptr::slice_from_raw_parts_mut(base, len);
189
190 // SAFETY: By invariant, `self`'s referent is either a ZST or lives
191 // entirely in an allocation. `ptr` points inside of or one byte past
192 // the end of that referent. Thus, in either case, `ptr` is non-null.
193 let ptr = unsafe { NonNull::new_unchecked(ptr) };
194
195 // SAFETY:
196 //
197 // Lemma 0: `ptr` addresses a subset of the bytes addressed by `self`,
198 // and has the same provenance. Proof: The caller guarantees
199 // that `start <= end <= self.len()`. Thus, `base` is in-bounds
200 // of `self`, and `base + (end - start)` is also in-bounds of
201 // self. Finally, `ptr` is constructed using
202 // provenance-preserving operations.
203 //
204 // 0. Per Lemma 0 and by invariant on `self`, if `ptr`'s referent is not
205 // zero sized, then `ptr` has valid provenance for its referent,
206 // which is entirely contained in some Rust allocation, `A`.
207 // 1. Per Lemma 0 and by invariant on `self`, if `ptr`'s referent is not
208 // zero sized, then `A` is guaranteed to live for at least `'a`.
209 unsafe { PtrInner::new(ptr) }
210 }
211
212 /// Splits the slice in two.
213 ///
214 /// # Safety
215 ///
216 /// The caller promises that `l_len <= self.len()`.
217 ///
218 /// Given `let (left, right) = ptr.split_at(l_len)`, it is guaranteed
219 /// that `left` and `right` are contiguous and non-overlapping.
220 pub(crate) unsafe fn split_at(self, l_len: usize) -> (Self, Self) {
221 // SAFETY: The caller promises that `l_len <= self.len()`.
222 // Trivially, `0 <= l_len`.
223 let left = unsafe { self.slice_unchecked(0..l_len) };
224
225 // SAFETY: The caller promises that `l_len <= self.len() =
226 // slf.len()`. Trivially, `slf.len() <= slf.len()`.
227 let right = unsafe { self.slice_unchecked(l_len..self.len()) };
228
229 // SAFETY: `left` and `right` are non-overlapping. Proof: `left` is
230 // constructed from `slf` with `l_len` as its (exclusive) upper
231 // bound, while `right` is constructed from `slf` with `l_len` as
232 // its (inclusive) lower bound. Thus, no index is a member of both
233 // ranges.
234 (left, right)
235 }
236
237 /// Iteratively projects the elements `PtrInner<T>` from `PtrInner<[T]>`.
238 pub(crate) fn iter(&self) -> impl Iterator<Item = PtrInner<'a, T>> {
239 // TODO(#429): Once `NonNull::cast` documents that it preserves
240 // provenance, cite those docs.
241 let base = self.as_non_null().cast::<T>().as_ptr();
242 (0..self.len()).map(move |i| {
243 // TODO(https://github.com/rust-lang/rust/issues/74265): Use
244 // `NonNull::get_unchecked_mut`.
245
246 // SAFETY: If the following conditions are not satisfied
247 // `pointer::cast` may induce Undefined Behavior [1]:
248 //
249 // > - The computed offset, `count * size_of::<T>()` bytes, must not
250 // > overflow `isize``.
251 // > - If the computed offset is non-zero, then `self` must be
252 // > derived from a pointer to some allocated object, and the
253 // > entire memory range between `self` and the result must be in
254 // > bounds of that allocated object. In particular, this range
255 // > must not “wrap around” the edge of the address space.
256 //
257 // [1] https://doc.rust-lang.org/std/primitive.pointer.html#method.add
258 //
259 // We satisfy both of these conditions here:
260 // - By invariant on `Ptr`, `self` addresses a byte range whose
261 // length fits in an `isize`. Since `elem` is contained in `self`,
262 // the computed offset of `elem` must fit within `isize.`
263 // - If the computed offset is non-zero, then this means that the
264 // referent is not zero-sized. In this case, `base` points to an
265 // allocated object (by invariant on `self`). Thus:
266 // - By contract, `self.len()` accurately reflects the number of
267 // elements in the slice. `i` is in bounds of `c.len()` by
268 // construction, and so the result of this addition cannot
269 // overflow past the end of the allocation referred to by `c`.
270 // - By invariant on `Ptr`, `self` addresses a byte range which
271 // does not wrap around the address space. Since `elem` is
272 // contained in `self`, the computed offset of `elem` must wrap
273 // around the address space.
274 //
275 // TODO(#429): Once `pointer::add` documents that it preserves
276 // provenance, cite those docs.
277 let elem = unsafe { base.add(i) };
278
279 // SAFETY: `elem` must not be null. `base` is constructed from a
280 // `NonNull` pointer, and the addition that produces `elem` must not
281 // overflow or wrap around, so `elem >= base > 0`.
282 //
283 // TODO(#429): Once `NonNull::new_unchecked` documents that it
284 // preserves provenance, cite those docs.
285 let elem = unsafe { NonNull::new_unchecked(elem) };
286
287 // SAFETY: The safety invariants of `Ptr::new` (see definition) are
288 // satisfied:
289 // 0. If `elem`'s referent is not zero sized, then `elem` has valid
290 // provenance for its referent, because it derived from `self`
291 // using a series of provenance-preserving operations, and
292 // because `self` has valid provenance for its referent. By the
293 // same argument, `elem`'s referent is entirely contained within
294 // the same allocated object as `self`'s referent.
295 // 1. If `elem`'s referent is not zero sized, then the allocation of
296 // `elem` is guaranteed to live for at least `'a`, because `elem`
297 // is entirely contained in `self`, which lives for at least `'a`
298 // by invariant on `Ptr`.
299 unsafe { PtrInner::new(elem) }
300 })
301 }
302
303 /// The number of slice elements in the object referenced by `self`.
304 ///
305 /// # Safety
306 ///
307 /// Unsafe code my rely on `len` satisfying the above contract.
308 pub(crate) fn len(&self) -> usize {
309 self.trailing_slice_len()
310 }
311}
312
313#[allow(clippy::needless_lifetimes)]
314impl<'a, T> PtrInner<'a, T>
315where
316 T: ?Sized + KnownLayout<PointerMetadata = usize>,
317{
318 /// The number of trailing slice elements in the object referenced by
319 /// `self`.
320 ///
321 /// # Safety
322 ///
323 /// Unsafe code my rely on `trailing_slice_len` satisfying the above
324 /// contract.
325 pub(super) fn trailing_slice_len(&self) -> usize {
326 T::pointer_to_metadata(self.as_non_null().as_ptr())
327 }
328}
329
330impl<'a, T, const N: usize> PtrInner<'a, [T; N]> {
331 /// Casts this pointer-to-array into a slice.
332 ///
333 /// # Safety
334 ///
335 /// Callers may assume that the returned `PtrInner` references the same
336 /// address and length as `self`.
337 #[allow(clippy::wrong_self_convention)]
338 pub(crate) fn as_slice(self) -> PtrInner<'a, [T]> {
339 let start = self.as_non_null().cast::<T>().as_ptr();
340 let slice = core::ptr::slice_from_raw_parts_mut(start, N);
341 // SAFETY: `slice` is not null, because it is derived from `start`
342 // which is non-null.
343 let slice = unsafe { NonNull::new_unchecked(slice) };
344 // SAFETY: Lemma: In the following safety arguments, note that `slice`
345 // is derived from `self` in two steps: first, by casting `self: [T; N]`
346 // to `start: T`, then by constructing a pointer to a slice starting at
347 // `start` of length `N`. As a result, `slice` references exactly the
348 // same allocation as `self`, if any.
349 //
350 // 0. By the above lemma, if `slice`'s referent is not zero sized, then
351 // `slice` has the same referent as `self`. By invariant on `self`,
352 // this referent is entirely contained within some allocation, `A`.
353 // Because `slice` was constructed using provenance-preserving
354 // operations, it has provenance for its entire referent.
355 // 1. By the above lemma, if `slice`'s referent is not zero sized, then
356 // `A` is guaranteed to live for at least `'a`, because it is derived
357 // from the same allocation as `self`, which, by invariant on `Ptr`,
358 // lives for at least `'a`.
359 unsafe { PtrInner::new(slice) }
360 }
361}
362
363impl<'a> PtrInner<'a, [u8]> {
364 /// Attempts to cast `self` to a `U` using the given cast type.
365 ///
366 /// If `U` is a slice DST and pointer metadata (`meta`) is provided, then
367 /// the cast will only succeed if it would produce an object with the given
368 /// metadata.
369 ///
370 /// Returns `None` if the resulting `U` would be invalidly-aligned, if no
371 /// `U` can fit in `self`, or if the provided pointer metadata describes an
372 /// invalid instance of `U`. On success, returns a pointer to the
373 /// largest-possible `U` which fits in `self`.
374 ///
375 /// # Safety
376 ///
377 /// The caller may assume that this implementation is correct, and may rely
378 /// on that assumption for the soundness of their code. In particular, the
379 /// caller may assume that, if `try_cast_into` returns `Some((ptr,
380 /// remainder))`, then `ptr` and `remainder` refer to non-overlapping byte
381 /// ranges within `self`, and that `ptr` and `remainder` entirely cover
382 /// `self`. Finally:
383 /// - If this is a prefix cast, `ptr` has the same address as `self`.
384 /// - If this is a suffix cast, `remainder` has the same address as `self`.
385 #[inline]
386 pub(crate) fn try_cast_into<U>(
387 self,
388 cast_type: CastType,
389 meta: Option<U::PointerMetadata>,
390 ) -> Result<(PtrInner<'a, U>, PtrInner<'a, [u8]>), CastError<Self, U>>
391 where
392 U: 'a + ?Sized + KnownLayout,
393 {
394 let layout = match meta {
395 None => U::LAYOUT,
396 // This can return `None` if the metadata describes an object
397 // which can't fit in an `isize`.
398 Some(meta) => {
399 let size = match meta.size_for_metadata(U::LAYOUT) {
400 Some(size) => size,
401 None => return Err(CastError::Size(SizeError::new(self))),
402 };
403 DstLayout { align: U::LAYOUT.align, size_info: crate::SizeInfo::Sized { size } }
404 }
405 };
406 // PANICS: By invariant, the byte range addressed by
407 // `self.as_non_null()` does not wrap around the address space. This
408 // implies that the sum of the address (represented as a `usize`) and
409 // length do not overflow `usize`, as required by
410 // `validate_cast_and_convert_metadata`. Thus, this call to
411 // `validate_cast_and_convert_metadata` will only panic if `U` is a DST
412 // whose trailing slice element is zero-sized.
413 let maybe_metadata = layout.validate_cast_and_convert_metadata(
414 AsAddress::addr(self.as_non_null().as_ptr()),
415 self.len(),
416 cast_type,
417 );
418
419 let (elems, split_at) = match maybe_metadata {
420 Ok((elems, split_at)) => (elems, split_at),
421 Err(MetadataCastError::Alignment) => {
422 // SAFETY: Since `validate_cast_and_convert_metadata` returned
423 // an alignment error, `U` must have an alignment requirement
424 // greater than one.
425 let err = unsafe { AlignmentError::<_, U>::new_unchecked(self) };
426 return Err(CastError::Alignment(err));
427 }
428 Err(MetadataCastError::Size) => return Err(CastError::Size(SizeError::new(self))),
429 };
430
431 // SAFETY: `validate_cast_and_convert_metadata` promises to return
432 // `split_at <= self.len()`.
433 let (l_slice, r_slice) = unsafe { self.split_at(split_at) };
434
435 let (target, remainder) = match cast_type {
436 CastType::Prefix => (l_slice, r_slice),
437 CastType::Suffix => (r_slice, l_slice),
438 };
439
440 let base = target.as_non_null().cast::<u8>();
441
442 let elems = <U as KnownLayout>::PointerMetadata::from_elem_count(elems);
443 // For a slice DST type, if `meta` is `Some(elems)`, then we synthesize
444 // `layout` to describe a sized type whose size is equal to the size of
445 // the instance that we are asked to cast. For sized types,
446 // `validate_cast_and_convert_metadata` returns `elems == 0`. Thus, in
447 // this case, we need to use the `elems` passed by the caller, not the
448 // one returned by `validate_cast_and_convert_metadata`.
449 let elems = meta.unwrap_or(elems);
450
451 let ptr = U::raw_from_ptr_len(base, elems);
452
453 // SAFETY:
454 // 0. By invariant, if `target`'s referent is not zero sized, then
455 // `target` has provenance valid for some Rust allocation, `A`.
456 // Because `ptr` is derived from `target` via provenance-preserving
457 // operations, `ptr` will also have provenance valid for its entire
458 // referent.
459 // 1. `validate_cast_and_convert_metadata` promises that the object
460 // described by `elems` and `split_at` lives at a byte range which is
461 // a subset of the input byte range. Thus, by invariant, if
462 // `target`'s referent is not zero sized, then `target` refers to an
463 // allocation which is guaranteed to live for at least `'a`, and thus
464 // so does `ptr`.
465 Ok((unsafe { PtrInner::new(ptr) }, remainder))
466 }
467}
468
469#[cfg(test)]
470mod tests {
471 use super::*;
472
473 #[test]
474 fn test_split_at() {
475 const N: usize = 16;
476 let arr = [1; N];
477 let ptr = PtrInner::from_ref(&arr).as_slice();
478 for i in 0..=N {
479 assert_eq!(ptr.len(), N);
480 // SAFETY: `i` is in bounds by construction.
481 let (l, r) = unsafe { ptr.split_at(i) };
482 // SAFETY: Points to a valid value by construction.
483 #[allow(clippy::undocumented_unsafe_blocks)] // Clippy false positive
484 let l_sum: usize = l
485 .iter()
486 .map(|ptr| unsafe { core::ptr::read_unaligned(ptr.as_non_null().as_ptr()) })
487 .sum();
488 // SAFETY: Points to a valid value by construction.
489 #[allow(clippy::undocumented_unsafe_blocks)] // Clippy false positive
490 let r_sum: usize = r
491 .iter()
492 .map(|ptr| unsafe { core::ptr::read_unaligned(ptr.as_non_null().as_ptr()) })
493 .sum();
494 assert_eq!(l_sum, i);
495 assert_eq!(r_sum, N - i);
496 assert_eq!(l_sum + r_sum, N);
497 }
498 }
499}
500