1 /*
2 * Copyright 2018 Google LLC
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "fcp/base/bounds.h"
18
19 #include "gmock/gmock.h"
20 #include "gtest/gtest.h"
21
22 namespace fcp {
23
24 using ::testing::Eq;
25
26 //
27 // Now follows a bunch of support for the TryCastInteger test. That
28 // implementation is very easy to get wrong, due to the sneaky conversion rules
29 // imposed on us by C++ (nice example: (int32_t)-1 > (uint32_t)1).
30 //
31 // In fact, it's fairly easy for the same class of issues to manifest in the
32 // test itself (or, even just mistaking the type of an integer literal).
33 //
34 // So, we approach this test like so:
35 //
36 // - Prevent unintended conversions in the test itself, and be explicit about
37 // integer types. Recall that this tends to compile:
38 // uint8_t u = -1; // Oh dear.
39 //
40 // But meanwhile, the rules for integer template arguments (maybe constant
41 // expressions generally?) are much stricter.
42 //
43 // We introduce a macro to raise an integer literal into a template
44 // argument. Subsequent attempts to cast it are checked at compile time with
45 // the stricter rules (Clang, by default, complains under
46 // -Wc++11-narrowing).
47 //
48 // LITERAL(-1)::As<uint8_t> // Error!
49 // LITERAL(-1)::As<int8_t> // Good.
50 //
51 // - Be thorough: just test all the interesting combinations!
52 //
53 // We start by defining a set (AllIntTypes) of the common integer types to
54 // test with: the signed and unsigned variants with sizes of 1, 2, 4, and 8
55 // bytes.
56 //
57 // Then, we choose some interesting LITERALs to test: for example, -1, and
58 // the min / max values for each type in AllIntTypes. For each LITERAL, we
59 // write down the _expected_ set of types that can fully represent it. As a
60 // shorthand, we work in terms of the _minimum_ sizes that work (a larger
61 // type of the same signed-ness always works). Some examples:
62 //
63 // // Any signed type (i.e. >= 8 bits) can represent -1
64 // VerifyIntCasts<LITERAL(-1), Signed<k8>>();
65 // // The max value of int64_t also fits in uint64_t
66 // VerifyIntCasts<MAX_LITERAL(int64_t), SignedOrUnsigned<k64>>();
67 // // Nothing else can hold a uint64_t's max value
68 // VerifyIntCasts<MAX_LITERAL(uint64_t), Unsigned<k64>>();
69 //
70 // (a LITERAL is safely cast to each type in its expected set at compile
71 // time)
72 //
73 // For each literal, we test runtime casts like follows:
74 //
75 // for (Type From : Expected) {
76 // From e = As<From>(); // Checked at compile time
77 // for (Type To : AllIntTypes) {
78 // bool succeeded = TryCastInteger<To, From>(...);
79 // if (To in Expected) {
80 // EXPECT_TRUE(succeeded);
81 // ...
82 // } else {
83 // EXPECT_FALSE(succeeded);
84 // }
85 // }
86 // }
87 //
88
89 enum IntSize { kNone, k8 = 1, k16 = 2, k32 = 4, k64 = 8 };
90
91 /**
92 * The set of the integer types we care about, with a filter applied.
93 * Apply() instantiates a given template, for each integer type passing the
94 * filter. We use the filter to model the set of types that can represent a
95 * literal (each instantiation tries to compile ::As).
96 */
97 template <typename FilterType>
98 class IntTypeSet {
99 public:
100 template <typename F>
Apply(F f)101 static void Apply(F f) {
102 ApplySingle<uint8_t>(f);
103 ApplySingle<uint16_t>(f);
104 ApplySingle<uint32_t>(f);
105 ApplySingle<uint64_t>(f);
106
107 ApplySingle<int8_t>(f);
108 ApplySingle<int16_t>(f);
109 ApplySingle<int32_t>(f);
110 ApplySingle<int64_t>(f);
111 }
112
113 template <typename T>
Matches()114 static constexpr bool Matches() {
115 return FilterType::template Matches<T>();
116 }
117
118 private:
119 template <bool B>
120 using BoolTag = std::integral_constant<bool, B>;
121
122 template <typename T, typename F>
ApplySingle(F f)123 static void ApplySingle(F f) {
124 ApplySingleImpl<T>(f, BoolTag<Matches<T>()>{});
125 }
126
127 template <typename T, typename F>
ApplySingleImpl(F f,BoolTag<true>)128 static void ApplySingleImpl(F f, BoolTag<true>) {
129 f.template Apply<T>();
130 }
131
132 template <typename T, typename F>
ApplySingleImpl(F f,BoolTag<false>)133 static void ApplySingleImpl(F f, BoolTag<false>) {}
134 };
135
136 struct NoFilter {
137 template <typename T>
Matchesfcp::NoFilter138 static constexpr bool Matches() {
139 return true;
140 }
141 };
142
143 /**
144 * The filter type we use per literal. It's sufficient to give a minimum size,
145 * separately per signed / unsigned.
146 */
147 template <IntSize MinSignedSize, IntSize MinUnsignedSize>
148 struct IntSizeFilter {
149 template <typename T>
Matchesfcp::IntSizeFilter150 static constexpr bool Matches() {
151 return SizeRequiredForType<T>() != IntSize::kNone &&
152 sizeof(T) >= SizeRequiredForType<T>();
153 }
154
155 template <typename T>
SizeRequiredForTypefcp::IntSizeFilter156 static constexpr IntSize SizeRequiredForType() {
157 return std::is_signed<T>() ? MinSignedSize : MinUnsignedSize;
158 }
159 };
160
161 using AllIntTypes = IntTypeSet<NoFilter>;
162
163 template <IntSize MinSignedSize>
164 using Signed = IntTypeSet<IntSizeFilter<MinSignedSize, kNone>>;
165 template <IntSize MinUnsignedSize>
166 using Unsigned = IntTypeSet<IntSizeFilter<kNone, MinUnsignedSize>>;
167 template <IntSize MinSignedSize, IntSize MinUnsignedSize = MinSignedSize>
168 using SignedOrUnsigned =
169 IntTypeSet<IntSizeFilter<MinSignedSize, MinUnsignedSize>>;
170
171 template <typename T, T Value_>
172 struct Literal {
173 template <typename R>
174 using As = Literal<R, Value_>;
175
Valuefcp::Literal176 static constexpr T Value() { return Value_; }
177 };
178
179 /**
180 * This is the per-literal test as described at the top of the file -
181 * but uglier.
182 */
183 template <typename LiteralType, typename SetType>
184 struct VerifyCastFromEachInSetToAll {
185 // Outer loop body: called for each type in the literal's 'expected' set.
186 template <typename FromType>
Applyfcp::VerifyCastFromEachInSetToAll187 void Apply() {
188 AllIntTypes::Apply(ForAll<FromType>{});
189 }
190
191 template <typename FromType>
192 struct ForAll {
Fromfcp::VerifyCastFromEachInSetToAll::ForAll193 static constexpr FromType From() {
194 return LiteralType::template As<FromType>::Value();
195 }
196
197 // Inner loop body: called for all integer types.
198 template <typename ToType>
Applyfcp::VerifyCastFromEachInSetToAll::ForAll199 void Apply() {
200 ToType actual;
201 bool succeeded = TryCastInteger(From(), &actual);
202 if (SetType::template Matches<ToType>()) {
203 EXPECT_TRUE(succeeded);
204 if (succeeded) {
205 EXPECT_THAT(actual, Eq(static_cast<ToType>(From())));
206 EXPECT_THAT(static_cast<FromType>(actual), Eq(From()));
207 }
208 } else {
209 EXPECT_FALSE(succeeded);
210 }
211 }
212 };
213 };
214
215 template <typename LiteralType, typename SetType>
VerifyIntCasts()216 void VerifyIntCasts() {
217 SetType::Apply(VerifyCastFromEachInSetToAll<LiteralType, SetType>{});
218 }
219
220 #define LITERAL(i) Literal<decltype(i), i>
221 #define MAX_LITERAL(t) Literal<t, std::numeric_limits<t>::max()>
222 #define MIN_LITERAL(t) Literal<t, std::numeric_limits<t>::min()>
223
TEST(BoundsTest,TryCastInteger)224 TEST(BoundsTest, TryCastInteger) {
225 VerifyIntCasts<LITERAL(-1), Signed<k8>>();
226 VerifyIntCasts<LITERAL(0), SignedOrUnsigned<k8>>();
227
228 VerifyIntCasts<MAX_LITERAL(int8_t), SignedOrUnsigned<k8>>();
229 VerifyIntCasts<MAX_LITERAL(int16_t), SignedOrUnsigned<k16>>();
230 VerifyIntCasts<MAX_LITERAL(int32_t), SignedOrUnsigned<k32>>();
231 VerifyIntCasts<MAX_LITERAL(int64_t), SignedOrUnsigned<k64>>();
232
233 VerifyIntCasts<MAX_LITERAL(uint8_t), SignedOrUnsigned<k16, k8>>();
234 VerifyIntCasts<MAX_LITERAL(uint16_t), SignedOrUnsigned<k32, k16>>();
235 VerifyIntCasts<MAX_LITERAL(uint32_t), SignedOrUnsigned<k64, k32>>();
236 VerifyIntCasts<MAX_LITERAL(uint64_t), Unsigned<k64>>();
237
238 VerifyIntCasts<MIN_LITERAL(int8_t), Signed<k8>>();
239 VerifyIntCasts<MIN_LITERAL(int16_t), Signed<k16>>();
240 VerifyIntCasts<MIN_LITERAL(int32_t), Signed<k32>>();
241 VerifyIntCasts<MIN_LITERAL(int64_t), Signed<k64>>();
242
243 VerifyIntCasts<MIN_LITERAL(uint8_t), SignedOrUnsigned<k8>>();
244 VerifyIntCasts<MIN_LITERAL(uint16_t), SignedOrUnsigned<k8>>();
245 VerifyIntCasts<MIN_LITERAL(uint32_t), SignedOrUnsigned<k8>>();
246 VerifyIntCasts<MIN_LITERAL(uint64_t), SignedOrUnsigned<k8>>();
247 }
248
249 //
250 // End of the TryCastInteger test
251 //
252
MakeFakeAddressSpace(uint64_t start,uint64_t size)253 AddressSpace MakeFakeAddressSpace(uint64_t start, uint64_t size) {
254 return AddressSpace::Embedded(reinterpret_cast<void*>(start), size);
255 }
256
257 MATCHER_P(IsAddress, addr, "") {
258 return reinterpret_cast<uint64_t>(arg) == addr;
259 }
260
TEST(BoundsTest,MapOutOfAddressSpace_Success)261 TEST(BoundsTest, MapOutOfAddressSpace_Success) {
262 AddressSpace space = MakeFakeAddressSpace(128, 128);
263 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{0}, 8, 1),
264 IsAddress(128));
265 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{0}, 8, 128 / 8),
266 IsAddress(128));
267 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{127}, 1, 1),
268 IsAddress(128 + 127));
269 }
270
TEST(BoundsTest,MapOutOfAddressSpace_OutOfBounds)271 TEST(BoundsTest, MapOutOfAddressSpace_OutOfBounds) {
272 AddressSpace space = MakeFakeAddressSpace(128, 128);
273 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{128}, 8, 1),
274 Eq(nullptr));
275 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{8}, 8, 128 / 8),
276 Eq(nullptr));
277 }
278
TEST(BoundsTest,MapOutOfAddressSpace_ZeroSizeEdge)279 TEST(BoundsTest, MapOutOfAddressSpace_ZeroSizeEdge) {
280 AddressSpace space = MakeFakeAddressSpace(128, 128);
281 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{128}, 1, 0),
282 IsAddress(128 + 128));
283 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{128}, 1, 1),
284 Eq(nullptr));
285 }
286
TEST(BoundsTest,MapOutOfAddressSpace_HighAddress)287 TEST(BoundsTest, MapOutOfAddressSpace_HighAddress) {
288 constexpr uint64_t kMax = std::numeric_limits<uint64_t>::max();
289 // Note that kMax is *not* a valid address; AddressSpace requires that 'one
290 // past the end' is <= kMax.
291 AddressSpace space = MakeFakeAddressSpace(kMax - 128, 128);
292
293 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{0}, 8, 128 / 8),
294 IsAddress(kMax - 128));
295 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{127}, 1, 1),
296 IsAddress(kMax - 1));
297 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{128}, 1, 0),
298 IsAddress(kMax));
299
300 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{128}, 1, 1),
301 Eq(nullptr));
302 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{0}, 1, 129),
303 Eq(nullptr));
304 }
305
TEST(BoundsTest,MapOutOfAddressSpace_Overflow)306 TEST(BoundsTest, MapOutOfAddressSpace_Overflow) {
307 constexpr uint64_t kMax = std::numeric_limits<uint64_t>::max();
308 AddressSpace space = MakeFakeAddressSpace(0, kMax);
309
310 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{kMax - 1}, 1, 1),
311 IsAddress(kMax - 1));
312 EXPECT_THAT(MapOutOfAddressSpace(space, ForeignPointer{kMax - 1}, 1, 2),
313 Eq(nullptr));
314 }
315
316 } // namespace fcp
317