1 // Copyright 2010 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 // static_contained_range_map_unittest.cc: Unit tests for
30 // StaticContainedRangeMap.
31 //
32 // Author: Siyang Xie ([email protected])
33
34 #ifdef HAVE_CONFIG_H
35 #include <config.h> // Must come first
36 #endif
37
38 #include "breakpad_googletest_includes.h"
39 #include "common/scoped_ptr.h"
40 #include "processor/contained_range_map-inl.h"
41 #include "processor/static_contained_range_map-inl.h"
42 #include "processor/simple_serializer-inl.h"
43 #include "processor/map_serializers-inl.h"
44 #include "processor/logging.h"
45
46 namespace {
47
48 typedef google_breakpad::ContainedRangeMap<unsigned int, int> CRMMap;
49 typedef google_breakpad::StaticContainedRangeMap<unsigned int, int> TestMap;
50
51 // Each element in test_data contains the expected result when calling
52 // RetrieveRange on an address.
53 const int test_data[] = {
54 0, // 0
55 0, // 1
56 0, // 2
57 0, // 3
58 0, // 4
59 0, // 5
60 0, // 6
61 0, // 7
62 9, // 8
63 7, // 9
64 1, // 10
65 5, // 11
66 6, // 12
67 6, // 13
68 6, // 14
69 6, // 15
70 6, // 16
71 6, // 17
72 6, // 18
73 5, // 19
74 7, // 20
75 8, // 21
76 0, // 22
77 0, // 23
78 0, // 24
79 0, // 25
80 0, // 26
81 0, // 27
82 0, // 28
83 0, // 29
84 10, // 30
85 10, // 31
86 10, // 32
87 11, // 33
88 11, // 34
89 11, // 35
90 0, // 36
91 0, // 37
92 0, // 38
93 0, // 39
94 14, // 40
95 14, // 41
96 14, // 42
97 14, // 43
98 15, // 44
99 15, // 45
100 15, // 46
101 15, // 47
102 0, // 48
103 0, // 49
104 19, // 50
105 18, // 51
106 18, // 52
107 18, // 53
108 18, // 54
109 18, // 55
110 18, // 56
111 18, // 57
112 18, // 58
113 20, // 59
114 21, // 60
115 25, // 61
116 26, // 62
117 26, // 63
118 26, // 64
119 26, // 65
120 26, // 66
121 26, // 67
122 24, // 68
123 22, // 69
124 30, // 70
125 30, // 71
126 30, // 72
127 30, // 73
128 31, // 74
129 31, // 75
130 30, // 76
131 32, // 77
132 32, // 78
133 30, // 79
134 34, // 80
135 35, // 81
136 36, // 82
137 39, // 83
138 38, // 84
139 37, // 85
140 43, // 86
141 44, // 87
142 41, // 88
143 45, // 89
144 42, // 90
145 0, // 91
146 0, // 92
147 0, // 93
148 0, // 94
149 0, // 95
150 0, // 96
151 0, // 97
152 0, // 98
153 0 // 99
154 };
155
156 } // namespace
157
158 namespace google_breakpad {
159
160 class TestStaticCRMMap : public ::testing::Test {
161 protected:
162 void SetUp();
163
164 // A referrence map for testing StaticCRMMap.
165 google_breakpad::ContainedRangeMap<unsigned int, int> crm_map_;
166
167 // Static version of crm_map using serialized data of crm_map.
168 // The goal of testing is to make sure TestMap provides same results for
169 // lookup operation(s) as CRMMap does.
170 google_breakpad::StaticContainedRangeMap<unsigned int, int> test_map_;
171
172 google_breakpad::ContainedRangeMapSerializer<unsigned int, int> serializer_;
173
174 scoped_array<char> serialized_data_;
175 };
176
SetUp()177 void TestStaticCRMMap::SetUp() {
178 // First, do the StoreRange tests. This validates the containment
179 // rules.
180 // We confirm the referrence map correctly stores data during setup.
181 ASSERT_TRUE (crm_map_.StoreRange(10, 10, 1));
182 ASSERT_FALSE(crm_map_.StoreRange(10, 10, 2)); // exactly equal to 1
183 ASSERT_FALSE(crm_map_.StoreRange(11, 10, 3)); // begins inside 1 and extends up
184 ASSERT_FALSE(crm_map_.StoreRange( 9, 10, 4)); // begins below 1 and ends inside
185 ASSERT_TRUE (crm_map_.StoreRange(11, 9, 5)); // contained by existing
186 ASSERT_TRUE (crm_map_.StoreRange(12, 7, 6));
187 ASSERT_TRUE (crm_map_.StoreRange( 9, 12, 7)); // contains existing
188 ASSERT_TRUE (crm_map_.StoreRange( 9, 13, 8));
189 ASSERT_TRUE (crm_map_.StoreRange( 8, 14, 9));
190 ASSERT_TRUE (crm_map_.StoreRange(30, 3, 10));
191 ASSERT_TRUE (crm_map_.StoreRange(33, 3, 11));
192 ASSERT_TRUE (crm_map_.StoreRange(30, 6, 12)); // storable but totally masked
193 ASSERT_TRUE (crm_map_.StoreRange(40, 8, 13)); // will be totally masked
194 ASSERT_TRUE (crm_map_.StoreRange(40, 4, 14));
195 ASSERT_TRUE (crm_map_.StoreRange(44, 4, 15));
196 ASSERT_FALSE(crm_map_.StoreRange(32, 10, 16)); // begins in #10, ends in #14
197 ASSERT_FALSE(crm_map_.StoreRange(50, 0, 17)); // zero length
198 ASSERT_TRUE (crm_map_.StoreRange(50, 10, 18));
199 ASSERT_TRUE (crm_map_.StoreRange(50, 1, 19));
200 ASSERT_TRUE (crm_map_.StoreRange(59, 1, 20));
201 ASSERT_TRUE (crm_map_.StoreRange(60, 1, 21));
202 ASSERT_TRUE (crm_map_.StoreRange(69, 1, 22));
203 ASSERT_TRUE (crm_map_.StoreRange(60, 10, 23));
204 ASSERT_TRUE (crm_map_.StoreRange(68, 1, 24));
205 ASSERT_TRUE (crm_map_.StoreRange(61, 1, 25));
206 ASSERT_TRUE (crm_map_.StoreRange(61, 8, 26));
207 ASSERT_FALSE(crm_map_.StoreRange(59, 9, 27));
208 ASSERT_FALSE(crm_map_.StoreRange(59, 10, 28));
209 ASSERT_FALSE(crm_map_.StoreRange(59, 11, 29));
210 ASSERT_TRUE (crm_map_.StoreRange(70, 10, 30));
211 ASSERT_TRUE (crm_map_.StoreRange(74, 2, 31));
212 ASSERT_TRUE (crm_map_.StoreRange(77, 2, 32));
213 ASSERT_FALSE(crm_map_.StoreRange(72, 6, 33));
214 ASSERT_TRUE (crm_map_.StoreRange(80, 3, 34));
215 ASSERT_TRUE (crm_map_.StoreRange(81, 1, 35));
216 ASSERT_TRUE (crm_map_.StoreRange(82, 1, 36));
217 ASSERT_TRUE (crm_map_.StoreRange(83, 3, 37));
218 ASSERT_TRUE (crm_map_.StoreRange(84, 1, 38));
219 ASSERT_TRUE (crm_map_.StoreRange(83, 1, 39));
220 ASSERT_TRUE (crm_map_.StoreRange(86, 5, 40));
221 ASSERT_TRUE (crm_map_.StoreRange(88, 1, 41));
222 ASSERT_TRUE (crm_map_.StoreRange(90, 1, 42));
223 ASSERT_TRUE (crm_map_.StoreRange(86, 1, 43));
224 ASSERT_TRUE (crm_map_.StoreRange(87, 1, 44));
225 ASSERT_TRUE (crm_map_.StoreRange(89, 1, 45));
226 ASSERT_TRUE (crm_map_.StoreRange(87, 4, 46));
227 ASSERT_TRUE (crm_map_.StoreRange(87, 3, 47));
228 ASSERT_FALSE(crm_map_.StoreRange(86, 2, 48));
229
230 // Serialize crm_map to generate serialized data.
231 unsigned int size;
232 serialized_data_.reset(serializer_.Serialize(&crm_map_, &size));
233 BPLOG(INFO) << "Serialized data size: " << size << " Bytes.";
234
235 // Construct test_map_ from serialized data.
236 test_map_ = TestMap(serialized_data_.get());
237 }
238
TEST_F(TestStaticCRMMap,TestEmptyMap)239 TEST_F(TestStaticCRMMap, TestEmptyMap) {
240 CRMMap empty_crm_map;
241
242 unsigned int size;
243 scoped_array<char> serialized_data;
244 serialized_data.reset(serializer_.Serialize(&empty_crm_map, &size));
245 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
246
247 const unsigned int kCorrectSizeForEmptyMap = 16;
248 ASSERT_EQ(kCorrectSizeForEmptyMap, size);
249
250 const int *entry_test;
251 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
252 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
253 ASSERT_FALSE(test_map->RetrieveRange(10, entry_test));
254 }
255
TEST_F(TestStaticCRMMap,TestSingleElementMap)256 TEST_F(TestStaticCRMMap, TestSingleElementMap) {
257 CRMMap crm_map;
258 // Test on one element:
259 int entry = 1;
260 crm_map.StoreRange(10, 10, entry);
261
262 unsigned int size;
263 scoped_array<char> serialized_data;
264 serialized_data.reset(serializer_.Serialize(&crm_map, &size));
265 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
266
267 const unsigned int kCorrectSizeForSingleElementMap = 40;
268 ASSERT_EQ(kCorrectSizeForSingleElementMap, size);
269
270 const int *entry_test;
271 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
272 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
273 ASSERT_TRUE(test_map->RetrieveRange(10, entry_test));
274 ASSERT_EQ(*entry_test, entry);
275 ASSERT_TRUE(test_map->RetrieveRange(13, entry_test));
276 ASSERT_EQ(*entry_test, entry);
277 }
278
TEST_F(TestStaticCRMMap,TestRetrieveRangeEntries)279 TEST_F(TestStaticCRMMap, TestRetrieveRangeEntries) {
280 CRMMap crm_map;
281
282 crm_map.StoreRange(2, 5, 0);
283 crm_map.StoreRange(2, 6, 1);
284 crm_map.StoreRange(2, 7, 2);
285
286 unsigned int size;
287 scoped_array<char> serialized_data;
288 serialized_data.reset(serializer_.Serialize(&crm_map, &size));
289 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
290
291 std::vector<const int*> entry_tests;
292 ASSERT_TRUE(test_map->RetrieveRanges(3, entry_tests));
293 ASSERT_EQ(*entry_tests[0], 0);
294 ASSERT_EQ(*entry_tests[1], 1);
295 ASSERT_EQ(*entry_tests[2], 2);
296 }
297
TEST_F(TestStaticCRMMap,RunTestData)298 TEST_F(TestStaticCRMMap, RunTestData) {
299 unsigned int test_high = sizeof(test_data) / sizeof(test_data[0]);
300
301 // Now, do the RetrieveRange tests. This further validates that the
302 // objects were stored properly and that retrieval returns the correct
303 // object.
304 // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
305 // new test_data array will be printed. Exercise caution when doing this.
306 // Be sure to verify the results manually!
307 #ifdef GENERATE_TEST_DATA
308 printf(" const int test_data[] = {\n");
309 #endif // GENERATE_TEST_DATA
310
311 for (unsigned int address = 0; address < test_high; ++address) {
312 const int *entryptr;
313 int value = 0;
314 if (test_map_.RetrieveRange(address, entryptr))
315 value = *entryptr;
316
317 #ifndef GENERATE_TEST_DATA
318 // Don't use ASSERT inside the loop because it won't show the failed
319 // |address|, and the line number will always be the same. That makes
320 // it difficult to figure out which test failed.
321 EXPECT_EQ(value, test_data[address]) << "FAIL: retrieve address "
322 << address;
323 #else // !GENERATE_TEST_DATA
324 printf(" %d%c%s // %d\n", value,
325 address == test_high - 1 ? ' ' : ',',
326 value < 10 ? " " : "",
327 address);
328 #endif // !GENERATE_TEST_DATA
329 }
330
331 #ifdef GENERATE_TEST_DATA
332 printf(" };\n");
333 #endif // GENERATE_TEST_DATA
334 }
335
336 } // namespace google_breakpad
337
main(int argc,char * argv[])338 int main(int argc, char *argv[]) {
339 ::testing::InitGoogleTest(&argc, argv);
340
341 return RUN_ALL_TESTS();
342 }
343