1//
2// Copyright (c) 2019-2021 Apple, Inc. All rights reserved.
3//
4// @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5//
6// This file contains Original Code and/or Modifications of Original Code
7// as defined in and that are subject to the Apple Public Source License
8// Version 2.0 (the 'License'). You may not use this file except in
9// compliance with the License. The rights granted to you under the License
10// may not be used to create, or enable the creation or redistribution of,
11// unlawful or unlicensed copies of an Apple operating system, or to
12// circumvent, violate, or enable the circumvention or violation of, any
13// terms of an Apple operating system software license agreement.
14//
15// Please obtain a copy of the License at
16// http://www.opensource.apple.com/apsl/ and read it before using this file.
17//
18// The Original Code and all software distributed under the License are
19// distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20// EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21// INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22// FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23// Please see the License for the specific language governing rights and
24// limitations under the License.
25//
26// @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27//
28
29#ifndef XNU_LIBKERN_LIBKERN_CXX_SAFE_ALLOCATION_H
30#define XNU_LIBKERN_LIBKERN_CXX_SAFE_ALLOCATION_H
31
32#if !TAPI
33
34#include <stddef.h>
35#include <stdint.h>
36#include <os/base.h>
37#if DRIVERKIT_FRAMEWORK_INCLUDE
38#include <DriverKit/bounded_ptr.h>
39#else
40#include <libkern/c++/bounded_ptr.h>
41#endif /* DRIVERKIT_FRAMEWORK_INCLUDE */
42
43#if (defined(__has_include) && __has_include(<__xnu_libcxx_sentinel.h>) && __has_include(<new>))
44#include <new>
45#else
46void* operator new(size_t, void*) noexcept; // forward declaration needed for placement-new
47#endif
48
49namespace libkern {
50namespace sa_detail {
51// TODO: Deduplicate these utilities with other smart pointer utilities
52using nullptr_t = decltype(nullptr);
53template <typename T>
54constexpr bool is_trivially_destructible_v = __is_trivially_destructible(T);
55template <typename T>
56constexpr bool is_empty_v = __is_empty(T);
57template <typename T>
58constexpr bool is_nothrow_default_constructible_v = __is_nothrow_constructible(T);
59
60template <bool Cond, typename T = void> struct enable_if;
61template <typename T> struct enable_if<true, T> { using type = T; };
62template <bool Cond, typename T = void> using enable_if_t = typename enable_if<Cond, T>::type;
63
64template <typename T> struct remove_const { using type = T; };
65template <typename T> struct remove_const<T const> { using type = T; };
66template <typename T> using remove_const_t = typename remove_const<T>::type;
67
68template <typename T>
69void
70generic_swap(T& a, T& b)
71{
72 T tmp = a;
73 a = b;
74 b = tmp;
75}
76
77template <typename T, enable_if_t<!is_trivially_destructible_v<T> >* = nullptr>
78void
79destroy(T* first, T* last)
80{
81 for (; first != last; ++first) {
82 first->~T();
83 }
84}
85
86template <typename T, enable_if_t<is_trivially_destructible_v<T> >* = nullptr>
87void
88destroy(T*, T*)
89{
90 // Nothing to do, the elements are trivially destructible
91}
92
93template <typename T>
94void
95uninitialized_value_construct(T* first, T* last)
96{
97 for (; first != last; ++first) {
98 ::new (static_cast<void*>(first)) T();
99 }
100}
101} // end namespace sa_detail
102
103struct adopt_memory_t {
104 explicit constexpr
105 adopt_memory_t() = default;
106};
107inline constexpr adopt_memory_t adopt_memory{};
108
109struct allocate_memory_t {
110 explicit constexpr
111 allocate_memory_t() = default;
112};
113inline constexpr allocate_memory_t allocate_memory{};
114
115struct allocate_memory_zero_t {
116 explicit constexpr
117 allocate_memory_zero_t() = default;
118};
119inline constexpr allocate_memory_zero_t allocate_memory_zero{};
120
121// Lightweight utility class representing a dynamically allocated slab of
122// memory, with contiguous objects in it.
123//
124// The main purpose `safe_allocation` is to:
125// 1. Manage a uniquely-owned allocation of memory containing multiple objects
126// 2. Check that the allocation is accessed within its bounds on indexing operations
127// 3. Act as a source for obtaining (non-owning) `bounded_ptr`s to the underlying memory
128//
129// In fact, `safe_allocation` should be the primary source of `bounded_ptr`s to
130// heap-allocated memory, via its `.begin()` and `.end()` methods. `safe_allocation`
131// is optimized for use cases where simple scratch space is needed for calculation
132// and deallocated once the calculation is done. As such, it is not a full-blown
133// container class, which drives many design choices behind `safe_allocation`:
134//
135// 1. It can't be copied or compared for equality -- `safe_allocation` is not a proper value type
136// 2. It can't be resized -- this keeps the design extremely simple and free of overhead
137// 3. You can transfer ownership of `safe_allocation` by using std::move
138//
139// Design decision: stateless allocators
140// =====================================
141// Only allow stateless allocators. While we could technically handle stateful
142// allocators (as the C++ Standard Library) does, the benefit of doing so
143// compared to the added complexity is absolutely not worth it. Supporting
144// stateful allocators everywhere in C++ is regarded (at least in the
145// Standardization Committee) as one of the worst design mistakes we've made,
146// and so we won't repeat it here.
147//
148// Design decision: size() is 0 when allocation is null
149// ====================================================
150// When the `safe_allocation` is null (because it's been moved-from, or because
151// allocation failed, or whatever), we could technically leave the `size_`
152// undefined (as long as we make `data_` null). However, this would mean
153// that querying the size of the allocation in that case is undefined behavior
154// (UB), which is seen as something bad in the context of a type that vends
155// itself as safe. So instead, we "overimplement" the type to provide stronger
156// guarantees than would be strictly required if performance were the main goal.
157template <typename T, typename Allocator, typename TrappingPolicy>
158struct safe_allocation {
159 static_assert(sa_detail::is_empty_v<Allocator>,
160 "safe_allocation<T, Alloc, ...> requires the Allocator to be stateless");
161
162 // Create a null allocation, pointing to no memory.
163 //
164 // A null allocation can be destroyed, assigned-to, checked for nullness,
165 // and otherwise queries for length, but trying to access an element of
166 // the allocation will fail.
167 //
168 // A null allocation basically behaves as an empty array, i.e. `begin()`
169 // and `end()` will return iterators that are equal and `size()` will
170 // return `0`.
171 explicit constexpr safe_allocation() noexcept : data_(nullptr), size_(0)
172 {
173 }
174
175 constexpr safe_allocation(sa_detail::nullptr_t) noexcept : safe_allocation()
176 {
177 }
178
179 // Create an allocation pointing to already-allocated and initialized memory.
180 //
181 // This constructor attaches existing memory to a `safe_allocation`, such
182 // that it will be released automatically when the `safe_allocation` goes
183 // out of scope. The objects in that memory must already have been
184 // initialized, or they must be initialized before the `safe_allocation`
185 // goes out of scope.
186 //
187 // The `n` argument is the number of objects of type `T` in the allocation,
188 // i.e. `n * sizeof(T)` bytes should have been allocated.
189 //
190 // Note that the memory MUST have been allocated with an allocator compatible
191 // with the `safe_allocation`'s `Allocator`, since the memory will be
192 // deallocated using that `Allocator`. Bad things will happen if, for
193 // example, `adopt_memory` is used with memory allocated on the stack:
194 // the destructor will try to deallocate that memory and will fail to do so.
195 explicit safe_allocation(T* data, size_t n, adopt_memory_t) : data_(data)
196 {
197 if (__improbable(n > UINT32_MAX)) {
198 TrappingPolicy::trap("safe_allocation size exceeds UINT32_MAX");
199 }
200
201 size_ = static_cast<uint32_t>(n);
202 }
203
204 // Allocate memory for `n` objects of type `T`, and manage it.
205 //
206 // This constructor allocates enough memory for `n` objects of type `T`
207 // using the `Allocator`, and manages that. Each object in the allocation
208 // is value-initialized (either set to 0 or the default-constructor called).
209 //
210 // If either `n * sizeof(T)` overflows or the allocation fails, the
211 // resulting `safe_allocation` will be null. It is therefore necessary
212 // to check whether the allocation is null after using this constructor.
213 explicit safe_allocation(size_t n, allocate_memory_t)
214 {
215 size_t bytes;
216 if (__improbable(os_mul_overflow(n, sizeof(T), &bytes) || (n > UINT32_MAX))) {
217 data_ = nullptr;
218 size_ = 0;
219 } else {
220 data_ = reinterpret_cast<T*>(Allocator::allocate(bytes));
221 size_ = static_cast<uint32_t>(n);
222 using RawT = sa_detail::remove_const_t<T>;
223 RawT* const data = const_cast<RawT*>(data_);
224 sa_detail::uninitialized_value_construct(data, data + size_);
225 }
226 }
227
228 // same as allocate_memory_t variant but allocated data is zero-initialized
229 explicit safe_allocation(size_t n, allocate_memory_zero_t)
230 {
231 static_assert(__is_scalar(T) || __is_aggregate(T),
232 "Creating objects via zero-allocation requires those objects to be scalars or aggregates (more broadly implicit lifetime types)");
233 size_t bytes;
234 if (__improbable(os_mul_overflow(n, sizeof(T), &bytes) || (n > UINT32_MAX))) {
235 data_ = nullptr;
236 size_ = 0;
237 } else {
238 data_ = reinterpret_cast<T*>(Allocator::allocate_zero(bytes));
239 size_ = static_cast<uint32_t>(n);
240 }
241 }
242
243 // A `safe_allocation` can't be copied, because it is not a proper value
244 // type and it doesn't assume that the elements of the allocation can be
245 // copied.
246 safe_allocation(safe_allocation const&) = delete;
247 safe_allocation& operator=(safe_allocation const&) = delete;
248
249 // Moves the ownership of an allocation from one `safe_allocation` to
250 // another one.
251 //
252 // After this operation, the moved-from `safe_allocation` is null, and
253 // any iterator into the moved-from `safe_allocation` are now tied to
254 // the `safe_allocation` that's the target of the assignment, in the
255 // sense that the iterators will be invalidated when the target of the
256 // assignment goes out of scope, not when the moved-from allocation
257 // goes out of scope.
258 safe_allocation(safe_allocation&& other) noexcept : data_(other.data_), size_(other.size_)
259 {
260 other.data_ = nullptr;
261 other.size_ = 0;
262 }
263
264 // Clears a `safe_allocation`, making it a null allocation.
265 //
266 // If the `safe_allocation` was pointing to valid memory, the objects
267 // in that memory are destroyed and that memory is freed.
268 safe_allocation&
269 operator=(sa_detail::nullptr_t)
270 {
271 if (data_ != nullptr) {
272 destroy_dealloc_(ptr: data_, size: size_);
273 }
274 data_ = nullptr;
275 size_ = 0;
276 return *this;
277 }
278
279 // Moves the ownership of an allocation from one `safe_allocation` to
280 // another one.
281 //
282 // After this operation, the moved-from `safe_allocation` is null, and
283 // any iterator to the moved-from `safe_allocation` obtained before the
284 // move operation are invalidated.
285 //
286 // If the destination `safe_allocation` was pointing to memory before the
287 // move-assignment, the objects in that memory are destroyed and the
288 // memory itself is freed.
289 //
290 // In case of self-move-assignment, nothing is done.
291 safe_allocation&
292 operator=(safe_allocation&& other)
293 {
294 if (&other == this) {
295 return *this;
296 }
297
298 T* old_data = data_;
299 size_t old_size = size_;
300
301 data_ = other.data_;
302 size_ = other.size_;
303 other.data_ = nullptr;
304 other.size_ = 0;
305
306 if (old_data != nullptr) {
307 destroy_dealloc_(ptr: old_data, size: old_size);
308 }
309
310 return *this;
311 }
312
313 // Destroys a `safe_allocation`, destroying the objects in it and
314 // deallocating the underlying memory with the `Allocator`.
315 //
316 // If the `safe_allocation` is null, this destructor does nothing.
317 ~safe_allocation()
318 {
319 if (data_ != nullptr) {
320 destroy_dealloc_(ptr: data_, size: size_);
321 }
322 }
323
324 // Returns whether a `safe_allocation` is non-null, i.e. whether it is
325 // pointing to some memory.
326 explicit
327 operator bool() const noexcept
328 {
329 return data_ != nullptr;
330 }
331
332 using iterator = bounded_ptr<T, TrappingPolicy>;
333 using const_iterator = bounded_ptr<T const, TrappingPolicy>;
334
335 // The following methods allow obtaining iterators (i.e. cursors) to
336 // objects inside a `safe_allocation`.
337 //
338 // The iterators of a `safe_allocation` are `bounded_ptr`s, which know
339 // the bounds of the allocation and will trap when dereferenced outside
340 // of those bounds.
341 //
342 // `begin()` returns a (const) iterator to the first element in the
343 // allocation, and `end()` returns a (const) iterator to one-past-the-last
344 // element in the allocation. The `end()` iterator can't be dereferenced,
345 // since it is out of bounds.
346 //
347 // If the allocation is null, these methods will return null `bounded_ptr`s,
348 // which can be checked for equality but can't be dereferenced.
349 OS_ALWAYS_INLINE iterator
350 begin() noexcept
351 {
352 if (data_ == nullptr) {
353 return iterator();
354 } else {
355 return iterator(data_, data_, data_ + size_);
356 }
357 }
358 OS_ALWAYS_INLINE const_iterator
359 begin() const noexcept
360 {
361 if (data_ == nullptr) {
362 return const_iterator();
363 } else {
364 return const_iterator(data_, data_, data_ + size_);
365 }
366 }
367 iterator
368 end() noexcept
369 {
370 if (data_ == nullptr) {
371 return iterator();
372 } else {
373 return iterator(data_ + size_, data_, data_ + size_);
374 }
375 }
376 const_iterator
377 end() const noexcept
378 {
379 if (data_ == nullptr) {
380 return const_iterator();
381 } else {
382 return const_iterator(data_ + size_, data_, data_ + size_);
383 }
384 }
385
386 // Returns the number of objects in the allocation.
387 //
388 // This method returns `0` if the allocation is null, since such an
389 // allocation behaves the same as an empty range.
390 size_t
391 size() const
392 {
393 return size_;
394 }
395
396 // Returns a non-owning pointer to the underlying memory managed by a
397 // `safe_allocation`.
398 //
399 // This method can be called even if the `safe_allocation` is null, in
400 // which case the returned pointer will be null.
401 T*
402 data() noexcept
403 {
404 return data_;
405 }
406 T const*
407 data() const noexcept
408 {
409 return data_;
410 }
411
412 // Access the n-th element of an allocation.
413 //
414 // If `n` is out of the bounds of the allocation, this operation will
415 // trap. If the allocation is null, this operation will trap too.
416 //
417 // Design note:
418 // We voluntarily use a signed type to represent the index even though a
419 // negative index will always cause a trap. If we used an unsigned type,
420 // we could get an implicit conversion from signed to unsigned, which
421 // could silently wrap around. We think trapping early is more likely
422 // to be helpful in this situation.
423 OS_ALWAYS_INLINE T&
424 operator[](ptrdiff_t n)
425 {
426 return begin()[n]; // trap happens in `bounded_ptr` if null or OOB
427 }
428 OS_ALWAYS_INLINE T const&
429 operator[](ptrdiff_t n) const
430 {
431 return begin()[n]; // trap happens in `bounded_ptr` if null or OOB
432 }
433
434private:
435 // Swap support
436 friend void
437 swap(safe_allocation& a, safe_allocation& b) noexcept
438 {
439 sa_detail::generic_swap(a.data_, b.data_);
440 sa_detail::generic_swap(a.size_, b.size_);
441 }
442
443 static void
444 destroy_dealloc_(T* ptr, size_t size)
445 {
446 sa_detail::destroy(ptr, ptr + size);
447 // `size * sizeof(T)` can't overflow, because it would have
448 // overflowed when the allocation was performed otherwise.
449 using RawT = sa_detail::remove_const_t<T>;
450 Allocator::deallocate(const_cast<RawT*>(ptr), size * sizeof(T));
451 }
452
453 T* data_;
454 uint32_t size_;
455};
456
457// The comparison functions against `nullptr` all return whether the allocation
458// is null or not.
459template <typename T, typename A, typename P>
460bool
461operator==(safe_allocation<T, A, P> const& x, sa_detail::nullptr_t)
462{
463 return !static_cast<bool>(x);
464}
465
466template <typename T, typename A, typename P>
467bool
468operator!=(safe_allocation<T, A, P> const& x, sa_detail::nullptr_t)
469{
470 return !(x == nullptr);
471}
472
473template <typename T, typename A, typename P>
474bool
475operator==(sa_detail::nullptr_t, safe_allocation<T, A, P> const& x)
476{
477 return x == nullptr;
478}
479
480template <typename T, typename A, typename P>
481bool
482operator!=(sa_detail::nullptr_t, safe_allocation<T, A, P> const& x)
483{
484 return !(x == nullptr);
485}
486} // end namespace libkern
487
488#endif /* !TAPI */
489
490#endif // !XNU_LIBKERN_LIBKERN_CXX_SAFE_ALLOCATION_H
491