1 // 2 // Copyright (c) 2019 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_BOUNDED_ARRAY_REF_H 30 #define XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H 31 32 #if !TAPI 33 34 #if DRIVERKIT_FRAMEWORK_INCLUDE 35 #include <DriverKit/bounded_array.h> 36 #include <DriverKit/bounded_ptr.h> 37 #else 38 #include <libkern/c++/bounded_array.h> 39 #include <libkern/c++/bounded_ptr.h> 40 #endif /* DRIVERKIT_FRAMEWORK_INCLUDE */ 41 42 #include <stddef.h> 43 #include <os/base.h> 44 45 namespace libkern { 46 namespace bar_detail { 47 using nullptr_t = decltype(nullptr); 48 } 49 50 // Represents a reference to a sequence of 0 or more elements consecutively in 51 // memory, i.e. a start pointer and a length. 52 // 53 // When elements of the sequence are accessed, `bounded_array_ref` ensures 54 // that those elements are in the bounds of the sequence (which are provided 55 // when the `bounded_array_ref` is constructed). 56 // 57 // This class does not own the underlying data. It is expected to be used in 58 // situations where the data resides in some other buffer, whose lifetime 59 // extends past that of the `bounded_array_ref`. For this reason, storing a 60 // `bounded_array_ref` adds the risk of a dangling pointer if the lifetime of 61 // the `bounded_array_ref` extends past that of the underlying data. 62 // 63 // `bounded_array_ref` is trivially copyable and it should be passed by value. 64 template <typename T, typename TrappingPolicy> 65 struct bounded_array_ref { 66 // Creates an empty `bounded_array_ref`. 67 // 68 // An empty `bounded_array_ref` does not reference anything, so its 69 // `data()` is null and its `size()` is 0. bounded_array_refbounded_array_ref70 explicit constexpr bounded_array_ref() noexcept : data_(nullptr), size_(0) 71 { 72 } 73 74 // Creates a `bounded_array_ref` from a bounded pointer and a size. 75 // 76 // The resulting `bounded_array_ref` starts at the location where the 77 // pointer points, and has the given number of elements. All the elements 78 // must be in the bounds of the `bounded_ptr`, otherwise this constructor 79 // will trap. bounded_array_refbounded_array_ref80 explicit constexpr bounded_array_ref(bounded_ptr<T, TrappingPolicy> data, size_t n) 81 : data_(data.unsafe_discard_bounds()), size_(static_cast<uint32_t>(n)) 82 { 83 if (n != 0) { 84 data[n - 1]; // make sure the bounds are valid 85 // TODO: find a better way to do that 86 } 87 if (__improbable(n > UINT32_MAX)) { 88 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 89 } 90 } 91 92 // Creates a `bounded_array_ref` from a raw pointer and a size. 93 // 94 // The resulting `bounded_array_ref` starts at the location where the 95 // pointer points, and has the given number of elements. This constructor 96 // trusts that `n` elements are reachable from the given pointer. bounded_array_refbounded_array_ref97 explicit constexpr bounded_array_ref(T* data, size_t n) : data_(data), size_(static_cast<uint32_t>(n)) 98 { 99 if (__improbable(n > UINT32_MAX)) { 100 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 101 } 102 } 103 104 // Creates a `bounded_array_ref` from a `[first, last)` half-open range. 105 // 106 // The resulting `bounded_array_ref` starts at the location pointed-to by 107 // `first`, and contains `last - first` elements. The `[first, last)` 108 // half-open range must be a valid range, i.e. it must be the case that 109 // `first <= last`, otherwise the constructor traps. bounded_array_refbounded_array_ref110 explicit constexpr bounded_array_ref(T* first, T* last) : data_(first), size_(static_cast<uint32_t>(last - first)) 111 { 112 if (__improbable(first > last)) { 113 TrappingPolicy::trap("bounded_array_ref: The [first, last) constructor requires a valid range."); 114 } 115 if (__improbable(last - first > UINT32_MAX)) { 116 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 117 } 118 } 119 120 // Creates a `bounded_array_ref` from a `bounded_array`. 121 // 122 // The resulting `bounded_array_ref` starts at the first element of the 123 // `bounded_array`, and has the number of elements in the `bounded_array`. 124 template <size_t N> bounded_array_refbounded_array_ref125 constexpr bounded_array_ref(bounded_array<T, N, TrappingPolicy>& data) : data_(data.data()), size_(static_cast<uint32_t>(data.size())) 126 { 127 if (__improbable(data.size() > UINT32_MAX)) { 128 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 129 } 130 } 131 132 // Creates a `bounded_array_ref` from a C-style array. 133 // 134 // The resulting `bounded_array_ref` starts at the first element of the 135 // C-style array, and has the number of elements in that array. 136 template <size_t N> bounded_array_refbounded_array_ref137 constexpr bounded_array_ref(T (&array)[N]) : data_(array), size_(static_cast<uint32_t>(N)) 138 { 139 if (__improbable(N > UINT32_MAX)) { 140 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 141 } 142 } 143 144 constexpr 145 bounded_array_ref(bounded_array_ref const&) = default; 146 constexpr 147 bounded_array_ref(bounded_array_ref&& other) noexcept = default; 148 149 constexpr bounded_array_ref& operator=(bounded_array_ref const&) = default; 150 constexpr bounded_array_ref& operator=(bounded_array_ref&& other) = default; 151 ~bounded_array_ref() = default; 152 153 // Returns whether the `bounded_array_ref` points to a sequence or not. 154 // 155 // Note that pointing to a sequence at all is different from pointing to 156 // a valid sequence, or having a size of 0. If a `bounded_array_ref` 157 // points to a sequence (regardless of whether it is valid or whether 158 // the size of that sequence is 0), this operator will return true. 159 explicit 160 operator bool() const noexcept 161 { 162 return data_ != nullptr; 163 } 164 165 using iterator = bounded_ptr<T, TrappingPolicy>; 166 167 // The following methods allow obtaining iterators (i.e. cursors) to 168 // objects inside a `bounded_array_ref`. 169 // 170 // The iterators of a `bounded_array_ref` are `bounded_ptr`s, which know 171 // the bounds of the sequence and will trap when dereferenced outside 172 // of those bounds. 173 // 174 // `begin()` returns an iterator to the first element in the range, and 175 // `end()` returns an iterator to one-past-the-last element in the range. 176 // The `end()` iterator can't be dereferenced, since it is out of bounds. 177 // 178 // If the `bounded_array_ref` is empty, these methods will return null 179 // `bounded_ptr`s, which can be checked for equality but can't be 180 // dereferenced. 181 OS_ALWAYS_INLINE iterator beginbounded_array_ref182 begin() const noexcept 183 { 184 return iterator(data_, data_, data_ + size_); 185 } 186 iterator endbounded_array_ref187 end() const noexcept 188 { 189 return iterator(data_ + size_, data_, data_ + size_); 190 } 191 192 // Returns the number of elements in the range referenced by the 193 // `bounded_array_ref`. 194 // 195 // This method returns `0` if the `bounded_array_ref` is null, since 196 // such an array ref behaves the same as an empty range. 197 constexpr size_t sizebounded_array_ref198 size() const noexcept 199 { 200 return size_; 201 } 202 203 // This has the same behavior as size(), but is intended to avoid confusion 204 // about whether it is returning an array count or size in bytes. 205 constexpr size_t lengthbounded_array_ref206 length() const noexcept 207 { 208 return size_; 209 } 210 211 // Returns a non-owning pointer to the underlying memory referenced by a 212 // `bounded_array_ref`. 213 // 214 // This method can be called even if the `bounded_array_ref` is null, in 215 // which case the returned pointer will be null. 216 constexpr T* databounded_array_ref217 data() const noexcept 218 { 219 return data_; 220 } 221 222 // Access the n-th element of a `bounded_array_ref`. 223 // 224 // If `n` is out of the bounds of the sequence, this operation will 225 // trap. If the array ref is null, this operation will trap too. 226 // 227 // Design note: 228 // We voluntarily use a signed type to represent the index even though a 229 // negative index will always cause a trap. If we used an unsigned type, 230 // we could get an implicit conversion from signed to unsigned, which 231 // could silently wrap around. We think trapping early is more likely 232 // to be helpful in this situation. 233 OS_ALWAYS_INLINE T& 234 operator[](ptrdiff_t n) const 235 { 236 return begin()[n]; 237 } 238 239 // Chop off the first `n` elements of the array, and keep `m` elements 240 // in the array. 241 // 242 // The resulting range can be described by `[beg + n, beg + n + m)`, where 243 // `beg` is the `begin()` of the range being sliced. This operation traps 244 // if `n + m` is larger than the number of elements in the array. 245 // 246 // Since `bounded_array_ref` checks (or assumes) that the range it is 247 // given on construction is within bounds and `slice()` checks that the 248 // produced slice is within the original range, it is impossible to create 249 // a `bounded_array_ref` that isn't a subset of a valid range using this 250 // function. 251 bounded_array_ref<T, TrappingPolicy> slicebounded_array_ref252 slice(size_t n, size_t m) const 253 { 254 uint32_t total; 255 if (__improbable(os_add_overflow(n, m, &total))) { 256 TrappingPolicy::trap("bounded_array_ref: n + m is larger than the size of any bounded_array_ref"); 257 } 258 if (__improbable(total > size())) { 259 TrappingPolicy::trap("bounded_array_ref: invalid slice provided, the indices are of bounds for the bounded_array_ref"); 260 } 261 return bounded_array_ref(data_ + n, m); 262 } 263 264 private: 265 T* data_; 266 uint32_t size_; 267 }; 268 269 // The comparison functions against `nullptr` all return whether the 270 // `bounded_array_ref` references a sequence or not. 271 template <typename T, typename P> 272 bool 273 operator==(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t) 274 { 275 return !static_cast<bool>(x); 276 } 277 278 template <typename T, typename P> 279 bool 280 operator!=(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t) 281 { 282 return !(x == nullptr); 283 } 284 285 template <typename T, typename P> 286 bool 287 operator==(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x) 288 { 289 return x == nullptr; 290 } 291 292 template <typename T, typename P> 293 bool 294 operator!=(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x) 295 { 296 return x != nullptr; 297 } 298 } // end namespace libkern 299 300 #endif /* !TAPI */ 301 302 #endif // !XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H 303