1 // Copyright 2006 Google LLC
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above
10 // copyright notice, this list of conditions and the following disclaimer
11 // in the documentation and/or other materials provided with the
12 // distribution.
13 // * Neither the name of Google LLC nor the names of its
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 // contained_range_map_unittest.cc: Unit tests for ContainedRangeMap
30 //
31 // Author: Mark Mentovai
32
33 #ifdef HAVE_CONFIG_H
34 #include <config.h> // Must come first
35 #endif
36
37 #include <stdio.h>
38
39 #include "processor/contained_range_map-inl.h"
40
41 #include "processor/logging.h"
42
43
44 #define ASSERT_TRUE(condition) \
45 if (!(condition)) { \
46 fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
47 return false; \
48 }
49
50 #define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))
51
52
53 namespace {
54
55
56 using google_breakpad::ContainedRangeMap;
57 // The first is the querying address, the second is the entries vector result.
58 using EntriesTestPair = std::pair<unsigned, std::vector<int>>;
59 using EntriesTestPairVec = std::vector<EntriesTestPair>;
60
RunTestsWithRetrieveRange(const ContainedRangeMap<unsigned int,int> & crm,const int * test_data,unsigned int test_length)61 static bool RunTestsWithRetrieveRange(
62 const ContainedRangeMap<unsigned int, int>& crm,
63 const int* test_data,
64 unsigned int test_length) {
65 // Now, do the RetrieveRange tests. This further validates that the
66 // objects were stored properly and that retrieval returns the correct
67 // object.
68 // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
69 // new test_data array will be printed. Exercise caution when doing this.
70 // Be sure to verify the results manually!
71 #ifdef GENERATE_TEST_DATA
72 printf(" const int test_data[] = {\n");
73 #endif // GENERATE_TEST_DATA
74
75 for (unsigned int address = 0; address < test_length; ++address) {
76 int value;
77 if (!crm.RetrieveRange(address, &value))
78 value = 0;
79
80 #ifndef GENERATE_TEST_DATA
81 // Don't use ASSERT inside the loop because it won't show the failed
82 // |address|, and the line number will always be the same. That makes
83 // it difficult to figure out which test failed.
84 if (value != test_data[address]) {
85 fprintf(stderr, "FAIL: retrieve %d expected %d observed %d @ %s:%d\n",
86 address, test_data[address], value, __FILE__, __LINE__);
87 return false;
88 }
89 #else // !GENERATE_TEST_DATA
90 printf(" %d%c%s // %d\n", value, address == test_high - 1 ? ' ' : ',',
91 value < 10 ? " " : "", address);
92 #endif // !GENERATE_TEST_DATA
93 }
94
95 #ifdef GENERATE_TEST_DATA
96 printf(" };\n");
97 #endif // GENERATE_TEST_DATA
98
99 return true;
100 }
101
RunTestsWithRetrieveRangeVector(const ContainedRangeMap<unsigned int,int> & crm,const EntriesTestPairVec & entries_tests)102 static bool RunTestsWithRetrieveRangeVector(
103 const ContainedRangeMap<unsigned int, int>& crm,
104 const EntriesTestPairVec& entries_tests) {
105 for (const EntriesTestPair& entries_test : entries_tests) {
106 std::vector<const int*> entries;
107 crm.RetrieveRanges(entries_test.first, entries);
108 if (entries.size() != entries_test.second.size()) {
109 fprintf(stderr,
110 "FAIL: retrieving entries at address %u has size %zu "
111 "expected to have size %zu "
112 "@ %s: %d\n",
113 entries_test.first, entries.size(), entries_test.second.size(),
114 __FILE__, __LINE__);
115 return false;
116 }
117 for (size_t i = 0; i < entries.size(); ++i) {
118 if (*entries[i] != entries_test.second[i]) {
119 fprintf(stderr,
120 "FAIL: retrieving entries at address %u entries[%zu] is %d "
121 "expected %d"
122 "@ %s: %d\n",
123 entries_test.first, i, *entries[i], entries_test.second[i],
124 __FILE__, __LINE__);
125 return false;
126 }
127 }
128 }
129 return true;
130 }
131
RunTestsWithNoEqualRange()132 static bool RunTestsWithNoEqualRange() {
133 ContainedRangeMap<unsigned int, int> crm;
134
135 // First, do the StoreRange tests. This validates the containment
136 // rules.
137 ASSERT_TRUE (crm.StoreRange(10, 10, 1));
138 ASSERT_FALSE(crm.StoreRange(10, 10, 2)); // exactly equal to 1
139 ASSERT_FALSE(crm.StoreRange(11, 10, 3)); // begins inside 1 and extends up
140 ASSERT_FALSE(crm.StoreRange( 9, 10, 4)); // begins below 1 and ends inside
141 ASSERT_TRUE (crm.StoreRange(11, 9, 5)); // contained by existing
142 ASSERT_TRUE (crm.StoreRange(12, 7, 6));
143 ASSERT_TRUE (crm.StoreRange( 9, 12, 7)); // contains existing
144 ASSERT_TRUE (crm.StoreRange( 9, 13, 8));
145 ASSERT_TRUE (crm.StoreRange( 8, 14, 9));
146 ASSERT_TRUE (crm.StoreRange(30, 3, 10));
147 ASSERT_TRUE (crm.StoreRange(33, 3, 11));
148 ASSERT_TRUE (crm.StoreRange(30, 6, 12)); // storable but totally masked
149 ASSERT_TRUE (crm.StoreRange(40, 8, 13)); // will be totally masked
150 ASSERT_TRUE (crm.StoreRange(40, 4, 14));
151 ASSERT_TRUE (crm.StoreRange(44, 4, 15));
152 ASSERT_FALSE(crm.StoreRange(32, 10, 16)); // begins in #10, ends in #14
153 ASSERT_FALSE(crm.StoreRange(50, 0, 17)); // zero length
154 ASSERT_TRUE (crm.StoreRange(50, 10, 18));
155 ASSERT_TRUE (crm.StoreRange(50, 1, 19));
156 ASSERT_TRUE (crm.StoreRange(59, 1, 20));
157 ASSERT_TRUE (crm.StoreRange(60, 1, 21));
158 ASSERT_TRUE (crm.StoreRange(69, 1, 22));
159 ASSERT_TRUE (crm.StoreRange(60, 10, 23));
160 ASSERT_TRUE (crm.StoreRange(68, 1, 24));
161 ASSERT_TRUE (crm.StoreRange(61, 1, 25));
162 ASSERT_TRUE (crm.StoreRange(61, 8, 26));
163 ASSERT_FALSE(crm.StoreRange(59, 9, 27));
164 ASSERT_FALSE(crm.StoreRange(59, 10, 28));
165 ASSERT_FALSE(crm.StoreRange(59, 11, 29));
166 ASSERT_TRUE (crm.StoreRange(70, 10, 30));
167 ASSERT_TRUE (crm.StoreRange(74, 2, 31));
168 ASSERT_TRUE (crm.StoreRange(77, 2, 32));
169 ASSERT_FALSE(crm.StoreRange(72, 6, 33));
170 ASSERT_TRUE (crm.StoreRange(80, 3, 34));
171 ASSERT_TRUE (crm.StoreRange(81, 1, 35));
172 ASSERT_TRUE (crm.StoreRange(82, 1, 36));
173 ASSERT_TRUE (crm.StoreRange(83, 3, 37));
174 ASSERT_TRUE (crm.StoreRange(84, 1, 38));
175 ASSERT_TRUE (crm.StoreRange(83, 1, 39));
176 ASSERT_TRUE (crm.StoreRange(86, 5, 40));
177 ASSERT_TRUE (crm.StoreRange(88, 1, 41));
178 ASSERT_TRUE (crm.StoreRange(90, 1, 42));
179 ASSERT_TRUE (crm.StoreRange(86, 1, 43));
180 ASSERT_TRUE (crm.StoreRange(87, 1, 44));
181 ASSERT_TRUE (crm.StoreRange(89, 1, 45));
182 ASSERT_TRUE (crm.StoreRange(87, 4, 46));
183 ASSERT_TRUE (crm.StoreRange(87, 3, 47));
184 ASSERT_FALSE(crm.StoreRange(86, 2, 48));
185
186 // Each element in test_data contains the expected result when calling
187 // RetrieveRange on an address.
188 const int test_data[] = {
189 0, // 0
190 0, // 1
191 0, // 2
192 0, // 3
193 0, // 4
194 0, // 5
195 0, // 6
196 0, // 7
197 9, // 8
198 7, // 9
199 1, // 10
200 5, // 11
201 6, // 12
202 6, // 13
203 6, // 14
204 6, // 15
205 6, // 16
206 6, // 17
207 6, // 18
208 5, // 19
209 7, // 20
210 8, // 21
211 0, // 22
212 0, // 23
213 0, // 24
214 0, // 25
215 0, // 26
216 0, // 27
217 0, // 28
218 0, // 29
219 10, // 30
220 10, // 31
221 10, // 32
222 11, // 33
223 11, // 34
224 11, // 35
225 0, // 36
226 0, // 37
227 0, // 38
228 0, // 39
229 14, // 40
230 14, // 41
231 14, // 42
232 14, // 43
233 15, // 44
234 15, // 45
235 15, // 46
236 15, // 47
237 0, // 48
238 0, // 49
239 19, // 50
240 18, // 51
241 18, // 52
242 18, // 53
243 18, // 54
244 18, // 55
245 18, // 56
246 18, // 57
247 18, // 58
248 20, // 59
249 21, // 60
250 25, // 61
251 26, // 62
252 26, // 63
253 26, // 64
254 26, // 65
255 26, // 66
256 26, // 67
257 24, // 68
258 22, // 69
259 30, // 70
260 30, // 71
261 30, // 72
262 30, // 73
263 31, // 74
264 31, // 75
265 30, // 76
266 32, // 77
267 32, // 78
268 30, // 79
269 34, // 80
270 35, // 81
271 36, // 82
272 39, // 83
273 38, // 84
274 37, // 85
275 43, // 86
276 44, // 87
277 41, // 88
278 45, // 89
279 42, // 90
280 0, // 91
281 0, // 92
282 0, // 93
283 0, // 94
284 0, // 95
285 0, // 96
286 0, // 97
287 0, // 98
288 0 // 99
289 };
290 unsigned int test_length = sizeof(test_data) / sizeof(int);
291 return RunTestsWithRetrieveRange(crm, test_data, test_length);
292 }
293
RunTestsWithEqualRange()294 static bool RunTestsWithEqualRange() {
295 ContainedRangeMap<unsigned int, int> crm(true);
296
297 // First, do the StoreRange tests. This validates the containment
298 // rules.
299 ASSERT_TRUE (crm.StoreRange(1, 3, 1));
300 ASSERT_TRUE (crm.StoreRange(1, 3, 2)); // exactly equal to 1
301 ASSERT_TRUE (crm.StoreRange(1, 3, 3)); // exactly equal to 1, 2
302 ASSERT_TRUE (crm.StoreRange(1, 3, 4)); // exactly equal to 1, 2, 3
303 ASSERT_FALSE(crm.StoreRange(0, 3, 5)); // partial overlap.
304 ASSERT_FALSE(crm.StoreRange(2, 3, 6)); // partial overlap.
305
306 ASSERT_TRUE (crm.StoreRange(5, 3, 7));
307 ASSERT_TRUE (crm.StoreRange(5, 3, 8)); // exactly equal to 7
308 ASSERT_TRUE (crm.StoreRange(5, 3, 9)); // exactly equal to 7, 8
309 ASSERT_TRUE (crm.StoreRange(5, 4, 10)); // encompasses 7, 8, 9
310 ASSERT_TRUE (crm.StoreRange(5, 5, 11)); // encompasses 7, 8, 9, 10
311
312 ASSERT_TRUE (crm.StoreRange(10, 3, 12));
313 ASSERT_TRUE (crm.StoreRange(10, 3, 13)); // exactly equal to 12
314 ASSERT_TRUE (crm.StoreRange(11, 2, 14)); // encompasses by 12
315 ASSERT_TRUE (crm.StoreRange(11, 1, 15)); // encompasses by 12, 13
316
317 ASSERT_TRUE (crm.StoreRange(14, 3, 16));
318 ASSERT_TRUE (crm.StoreRange(14, 3, 17)); // exactly equal to 14
319 ASSERT_TRUE (crm.StoreRange(14, 1, 18)); // encompasses by 14, 15
320 ASSERT_TRUE (crm.StoreRange(14, 2, 19)); // encompasses by 14, 15 and encompasses 16
321 ASSERT_TRUE (crm.StoreRange(14, 1, 20)); // exactly equal to 18
322 ASSERT_TRUE (crm.StoreRange(14, 2, 21)); // exactly equal to 19
323
324 // Each element in test_data contains the expected result when calling
325 // RetrieveRange on an address.
326 const int test_data[] = {
327 0, // 0
328 4, // 1
329 4, // 2
330 4, // 3
331 0, // 4
332 9, // 5
333 9, // 6
334 9, // 7
335 10, // 8
336 11, // 9
337 13, // 10
338 15, // 11
339 14, // 12
340 0, // 13
341 20, // 14
342 21, // 15
343 17, // 16
344 0, // 17
345 };
346 unsigned int test_length = sizeof(test_data) / sizeof(int);
347 EntriesTestPairVec entries_tests = {
348 {0, {}},
349 {1, {4, 3, 2, 1}},
350 {2, {4, 3, 2, 1}},
351 {3, {4, 3, 2, 1}},
352 {4, {}},
353 {5, {9, 8, 7, 10, 11}},
354 {6, {9, 8, 7, 10, 11}},
355 {7, {9, 8, 7, 10, 11}},
356 {8, {10, 11}},
357 {9, {11}},
358 {10, {13, 12}},
359 {11, {15, 14, 13, 12}},
360 {12, {14, 13, 12}},
361 {13, {}},
362 {14, {20, 18, 21, 19, 17, 16}},
363 {15, {21, 19, 17, 16}},
364 {16, {17, 16}},
365 {17, {}},
366 };
367 return RunTestsWithRetrieveRange(crm, test_data, test_length) &&
368 RunTestsWithRetrieveRangeVector(crm, entries_tests);
369 }
370
RunTests()371 static bool RunTests() {
372 return RunTestsWithNoEqualRange() && RunTestsWithEqualRange();
373 }
374
375
376 } // namespace
377
378
main(int argc,char ** argv)379 int main(int argc, char** argv) {
380 BPLOG_INIT(&argc, &argv);
381
382 return RunTests() ? 0 : 1;
383 }
384