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
45namespace libkern {
46namespace bar_detail {
47using 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.
64template <typename T, typename TrappingPolicy>
65struct 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.
70 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.
80 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.
97 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.
110 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>
125 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>
137 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
182 begin() const noexcept
183 {
184 return iterator(data_, data_, data_ + size_);
185 }
186 iterator
187 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
198 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
206 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*
217 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>
252 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
264private:
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.
271template <typename T, typename P>
272bool
273operator==(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t)
274{
275 return !static_cast<bool>(x);
276}
277
278template <typename T, typename P>
279bool
280operator!=(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t)
281{
282 return !(x == nullptr);
283}
284
285template <typename T, typename P>
286bool
287operator==(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x)
288{
289 return x == nullptr;
290}
291
292template <typename T, typename P>
293bool
294operator!=(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