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, it is not 60 // in general safe to store a `bounded_array_ref`. 61 // 62 // `bounded_array_ref` is trivially copyable and it should be passed by value. 63 template <typename T, typename TrappingPolicy> 64 struct bounded_array_ref { 65 // Creates an empty `bounded_array_ref`. 66 // 67 // An empty `bounded_array_ref` does not reference anything, so its 68 // `data()` is null and its `size()` is 0. bounded_array_refbounded_array_ref69 explicit constexpr bounded_array_ref() noexcept : data_(nullptr), size_(0) 70 { 71 } 72 73 // Creates a `bounded_array_ref` from a bounded pointer and a size. 74 // 75 // The resulting `bounded_array_ref` starts at the location where the 76 // pointer points, and has the given number of elements. All the elements 77 // must be in the bounds of the `bounded_ptr`, otherwise this constructor 78 // will trap. bounded_array_refbounded_array_ref79 explicit constexpr bounded_array_ref(bounded_ptr<T, TrappingPolicy> data, size_t n) 80 : data_(data.unsafe_discard_bounds()), size_(static_cast<uint32_t>(n)) 81 { 82 if (n != 0) { 83 data[n - 1]; // make sure the bounds are valid 84 // TODO: find a better way to do that 85 } 86 if (__improbable(n > UINT32_MAX)) { 87 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 88 } 89 } 90 91 // Creates a `bounded_array_ref` from a raw pointer and a size. 92 // 93 // The resulting `bounded_array_ref` starts at the location where the 94 // pointer points, and has the given number of elements. This constructor 95 // trusts that `n` elements are reachable from the given pointer. bounded_array_refbounded_array_ref96 explicit constexpr bounded_array_ref(T* data, size_t n) : data_(data), size_(static_cast<uint32_t>(n)) 97 { 98 if (__improbable(n > UINT32_MAX)) { 99 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 100 } 101 } 102 103 // Creates a `bounded_array_ref` from a `[first, last)` half-open range. 104 // 105 // The resulting `bounded_array_ref` starts at the location pointed-to by 106 // `first`, and contains `last - first` elements. The `[first, last)` 107 // half-open range must be a valid range, i.e. it must be the case that 108 // `first <= last`, otherwise the constructor traps. bounded_array_refbounded_array_ref109 explicit constexpr bounded_array_ref(T* first, T* last) : data_(first), size_(static_cast<uint32_t>(last - first)) 110 { 111 if (__improbable(first > last)) { 112 TrappingPolicy::trap("bounded_array_ref: The [first, last) constructor requires a valid range."); 113 } 114 if (__improbable(last - first > UINT32_MAX)) { 115 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 116 } 117 } 118 119 // Creates a `bounded_array_ref` from a `bounded_array`. 120 // 121 // The resulting `bounded_array_ref` starts at the first element of the 122 // `bounded_array`, and has the number of elements in the `bounded_array`. 123 template <size_t N> bounded_array_refbounded_array_ref124 constexpr bounded_array_ref(bounded_array<T, N, TrappingPolicy>& data) : data_(data.data()), size_(static_cast<uint32_t>(data.size())) 125 { 126 if (__improbable(data.size() > UINT32_MAX)) { 127 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 128 } 129 } 130 131 // Creates a `bounded_array_ref` from a C-style array. 132 // 133 // The resulting `bounded_array_ref` starts at the first element of the 134 // C-style array, and has the number of elements in that array. 135 template <size_t N> bounded_array_refbounded_array_ref136 constexpr bounded_array_ref(T (&array)[N]) : data_(array), size_(static_cast<uint32_t>(N)) 137 { 138 if (__improbable(N > UINT32_MAX)) { 139 TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX"); 140 } 141 } 142 143 constexpr 144 bounded_array_ref(bounded_array_ref const&) = default; 145 constexpr 146 bounded_array_ref(bounded_array_ref&& other) noexcept = default; 147 148 constexpr bounded_array_ref& operator=(bounded_array_ref const&) = default; 149 constexpr bounded_array_ref& operator=(bounded_array_ref&& other) = default; 150 ~bounded_array_ref() = default; 151 152 // Returns whether the `bounded_array_ref` points to a sequence or not. 153 // 154 // Note that pointing to a sequence at all is different from pointing to 155 // a valid sequence, or having a size of 0. If a `bounded_array_ref` 156 // points to a sequence (regardless of whether it is valid or whether 157 // the size of that sequence is 0), this operator will return true. 158 explicit 159 operator bool() const noexcept 160 { 161 return data_ != nullptr; 162 } 163 164 using iterator = bounded_ptr<T, TrappingPolicy>; 165 166 // The following methods allow obtaining iterators (i.e. cursors) to 167 // objects inside a `bounded_array_ref`. 168 // 169 // The iterators of a `bounded_array_ref` are `bounded_ptr`s, which know 170 // the bounds of the sequence and will trap when dereferenced outside 171 // of those bounds. 172 // 173 // `begin()` returns an iterator to the first element in the range, and 174 // `end()` returns an iterator to one-past-the-last element in the range. 175 // The `end()` iterator can't be dereferenced, since it is out of bounds. 176 // 177 // If the `bounded_array_ref` is empty, these methods will return null 178 // `bounded_ptr`s, which can be checked for equality but can't be 179 // dereferenced. 180 iterator beginbounded_array_ref181 begin() const noexcept 182 { 183 return iterator(data_, data_, data_ + size_); 184 } 185 iterator endbounded_array_ref186 end() const noexcept 187 { 188 return iterator(data_ + size_, data_, data_ + size_); 189 } 190 191 // Returns the number of elements in the range referenced by the 192 // `bounded_array_ref`. 193 // 194 // This method returns `0` if the `bounded_array_ref` is null, since 195 // such an array ref behaves the same as an empty range. 196 constexpr size_t sizebounded_array_ref197 size() const 198 { 199 return size_; 200 } 201 202 // Returns a non-owning pointer to the underlying memory referenced by a 203 // `bounded_array_ref`. 204 // 205 // This method can be called even if the `bounded_array_ref` is null, in 206 // which case the returned pointer will be null. 207 constexpr T* databounded_array_ref208 data() const noexcept 209 { 210 return data_; 211 } 212 213 // Access the n-th element of a `bounded_array_ref`. 214 // 215 // If `n` is out of the bounds of the sequence, this operation will 216 // trap. If the array ref is null, this operation will trap too. 217 // 218 // Design note: 219 // We voluntarily use a signed type to represent the index even though a 220 // negative index will always cause a trap. If we used an unsigned type, 221 // we could get an implicit conversion from signed to unsigned, which 222 // could silently wrap around. We think trapping early is more likely 223 // to be helpful in this situation. 224 OS_ALWAYS_INLINE T& 225 operator[](ptrdiff_t n) const 226 { 227 return begin()[n]; 228 } 229 230 // Chop off the first `n` elements of the array, and keep `m` elements 231 // in the array. 232 // 233 // The resulting range can be described by `[beg + n, beg + n + m)`, where 234 // `beg` is the `begin()` of the range being sliced. This operation traps 235 // if `n + m` is larger than the number of elements in the array. 236 // 237 // Since `bounded_array_ref` checks (or assumes) that the range it is 238 // given on construction is within bounds and `slice()` checks that the 239 // produced slice is within the original range, it is impossible to create 240 // a `bounded_array_ref` that isn't a subset of a valid range using this 241 // function. 242 bounded_array_ref<T, TrappingPolicy> slicebounded_array_ref243 slice(size_t n, size_t m) const 244 { 245 uint32_t total; 246 if (__improbable(os_add_overflow(n, m, &total))) { 247 TrappingPolicy::trap("bounded_array_ref: n + m is larger than the size of any bounded_array_ref"); 248 } 249 if (__improbable(total > size())) { 250 TrappingPolicy::trap("bounded_array_ref: invalid slice provided, the indices are of bounds for the bounded_array_ref"); 251 } 252 return bounded_array_ref(data_ + n, m); 253 } 254 255 private: 256 T* data_; 257 uint32_t size_; 258 }; 259 260 // The comparison functions against `nullptr` all return whether the 261 // `bounded_array_ref` references a sequence or not. 262 template <typename T, typename P> 263 bool 264 operator==(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t) 265 { 266 return !static_cast<bool>(x); 267 } 268 269 template <typename T, typename P> 270 bool 271 operator!=(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t) 272 { 273 return !(x == nullptr); 274 } 275 276 template <typename T, typename P> 277 bool 278 operator==(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x) 279 { 280 return x == nullptr; 281 } 282 283 template <typename T, typename P> 284 bool 285 operator!=(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x) 286 { 287 return x != nullptr; 288 } 289 } // end namespace libkern 290 291 #endif /* !TAPI */ 292 293 #endif // !XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H 294