1 // Copyright (c) 2010, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 // static_contained_range_map_unittest.cc: Unit tests for
31 // StaticContainedRangeMap.
32 //
33 // Author: Siyang Xie (lambxsy@google.com)
34
35 #include "breakpad_googletest_includes.h"
36 #include "common/scoped_ptr.h"
37 #include "processor/contained_range_map-inl.h"
38 #include "processor/static_contained_range_map-inl.h"
39 #include "processor/simple_serializer-inl.h"
40 #include "processor/map_serializers-inl.h"
41 #include "processor/logging.h"
42
43 namespace {
44
45 typedef google_breakpad::ContainedRangeMap<unsigned int, int> CRMMap;
46 typedef google_breakpad::StaticContainedRangeMap<unsigned int, int> TestMap;
47
48 // Each element in test_data contains the expected result when calling
49 // RetrieveRange on an address.
50 const int test_data[] = {
51 0, // 0
52 0, // 1
53 0, // 2
54 0, // 3
55 0, // 4
56 0, // 5
57 0, // 6
58 0, // 7
59 9, // 8
60 7, // 9
61 1, // 10
62 5, // 11
63 6, // 12
64 6, // 13
65 6, // 14
66 6, // 15
67 6, // 16
68 6, // 17
69 6, // 18
70 5, // 19
71 7, // 20
72 8, // 21
73 0, // 22
74 0, // 23
75 0, // 24
76 0, // 25
77 0, // 26
78 0, // 27
79 0, // 28
80 0, // 29
81 10, // 30
82 10, // 31
83 10, // 32
84 11, // 33
85 11, // 34
86 11, // 35
87 0, // 36
88 0, // 37
89 0, // 38
90 0, // 39
91 14, // 40
92 14, // 41
93 14, // 42
94 14, // 43
95 15, // 44
96 15, // 45
97 15, // 46
98 15, // 47
99 0, // 48
100 0, // 49
101 19, // 50
102 18, // 51
103 18, // 52
104 18, // 53
105 18, // 54
106 18, // 55
107 18, // 56
108 18, // 57
109 18, // 58
110 20, // 59
111 21, // 60
112 25, // 61
113 26, // 62
114 26, // 63
115 26, // 64
116 26, // 65
117 26, // 66
118 26, // 67
119 24, // 68
120 22, // 69
121 30, // 70
122 30, // 71
123 30, // 72
124 30, // 73
125 31, // 74
126 31, // 75
127 30, // 76
128 32, // 77
129 32, // 78
130 30, // 79
131 34, // 80
132 35, // 81
133 36, // 82
134 39, // 83
135 38, // 84
136 37, // 85
137 43, // 86
138 44, // 87
139 41, // 88
140 45, // 89
141 42, // 90
142 0, // 91
143 0, // 92
144 0, // 93
145 0, // 94
146 0, // 95
147 0, // 96
148 0, // 97
149 0, // 98
150 0 // 99
151 };
152
153 } // namespace
154
155 namespace google_breakpad {
156
157 class TestStaticCRMMap : public ::testing::Test {
158 protected:
159 void SetUp();
160
161 // A referrence map for testing StaticCRMMap.
162 google_breakpad::ContainedRangeMap<unsigned int, int> crm_map_;
163
164 // Static version of crm_map using serialized data of crm_map.
165 // The goal of testing is to make sure TestMap provides same results for
166 // lookup operation(s) as CRMMap does.
167 google_breakpad::StaticContainedRangeMap<unsigned int, int> test_map_;
168
169 google_breakpad::ContainedRangeMapSerializer<unsigned int, int> serializer_;
170
171 scoped_array<char> serialized_data_;
172 };
173
SetUp()174 void TestStaticCRMMap::SetUp() {
175 // First, do the StoreRange tests. This validates the containment
176 // rules.
177 // We confirm the referrence map correctly stores data during setup.
178 ASSERT_TRUE (crm_map_.StoreRange(10, 10, 1));
179 ASSERT_FALSE(crm_map_.StoreRange(10, 10, 2)); // exactly equal to 1
180 ASSERT_FALSE(crm_map_.StoreRange(11, 10, 3)); // begins inside 1 and extends up
181 ASSERT_FALSE(crm_map_.StoreRange( 9, 10, 4)); // begins below 1 and ends inside
182 ASSERT_TRUE (crm_map_.StoreRange(11, 9, 5)); // contained by existing
183 ASSERT_TRUE (crm_map_.StoreRange(12, 7, 6));
184 ASSERT_TRUE (crm_map_.StoreRange( 9, 12, 7)); // contains existing
185 ASSERT_TRUE (crm_map_.StoreRange( 9, 13, 8));
186 ASSERT_TRUE (crm_map_.StoreRange( 8, 14, 9));
187 ASSERT_TRUE (crm_map_.StoreRange(30, 3, 10));
188 ASSERT_TRUE (crm_map_.StoreRange(33, 3, 11));
189 ASSERT_TRUE (crm_map_.StoreRange(30, 6, 12)); // storable but totally masked
190 ASSERT_TRUE (crm_map_.StoreRange(40, 8, 13)); // will be totally masked
191 ASSERT_TRUE (crm_map_.StoreRange(40, 4, 14));
192 ASSERT_TRUE (crm_map_.StoreRange(44, 4, 15));
193 ASSERT_FALSE(crm_map_.StoreRange(32, 10, 16)); // begins in #10, ends in #14
194 ASSERT_FALSE(crm_map_.StoreRange(50, 0, 17)); // zero length
195 ASSERT_TRUE (crm_map_.StoreRange(50, 10, 18));
196 ASSERT_TRUE (crm_map_.StoreRange(50, 1, 19));
197 ASSERT_TRUE (crm_map_.StoreRange(59, 1, 20));
198 ASSERT_TRUE (crm_map_.StoreRange(60, 1, 21));
199 ASSERT_TRUE (crm_map_.StoreRange(69, 1, 22));
200 ASSERT_TRUE (crm_map_.StoreRange(60, 10, 23));
201 ASSERT_TRUE (crm_map_.StoreRange(68, 1, 24));
202 ASSERT_TRUE (crm_map_.StoreRange(61, 1, 25));
203 ASSERT_TRUE (crm_map_.StoreRange(61, 8, 26));
204 ASSERT_FALSE(crm_map_.StoreRange(59, 9, 27));
205 ASSERT_FALSE(crm_map_.StoreRange(59, 10, 28));
206 ASSERT_FALSE(crm_map_.StoreRange(59, 11, 29));
207 ASSERT_TRUE (crm_map_.StoreRange(70, 10, 30));
208 ASSERT_TRUE (crm_map_.StoreRange(74, 2, 31));
209 ASSERT_TRUE (crm_map_.StoreRange(77, 2, 32));
210 ASSERT_FALSE(crm_map_.StoreRange(72, 6, 33));
211 ASSERT_TRUE (crm_map_.StoreRange(80, 3, 34));
212 ASSERT_TRUE (crm_map_.StoreRange(81, 1, 35));
213 ASSERT_TRUE (crm_map_.StoreRange(82, 1, 36));
214 ASSERT_TRUE (crm_map_.StoreRange(83, 3, 37));
215 ASSERT_TRUE (crm_map_.StoreRange(84, 1, 38));
216 ASSERT_TRUE (crm_map_.StoreRange(83, 1, 39));
217 ASSERT_TRUE (crm_map_.StoreRange(86, 5, 40));
218 ASSERT_TRUE (crm_map_.StoreRange(88, 1, 41));
219 ASSERT_TRUE (crm_map_.StoreRange(90, 1, 42));
220 ASSERT_TRUE (crm_map_.StoreRange(86, 1, 43));
221 ASSERT_TRUE (crm_map_.StoreRange(87, 1, 44));
222 ASSERT_TRUE (crm_map_.StoreRange(89, 1, 45));
223 ASSERT_TRUE (crm_map_.StoreRange(87, 4, 46));
224 ASSERT_TRUE (crm_map_.StoreRange(87, 3, 47));
225 ASSERT_FALSE(crm_map_.StoreRange(86, 2, 48));
226
227 // Serialize crm_map to generate serialized data.
228 unsigned int size;
229 serialized_data_.reset(serializer_.Serialize(&crm_map_, &size));
230 BPLOG(INFO) << "Serialized data size: " << size << " Bytes.";
231
232 // Construct test_map_ from serialized data.
233 test_map_ = TestMap(serialized_data_.get());
234 }
235
TEST_F(TestStaticCRMMap,TestEmptyMap)236 TEST_F(TestStaticCRMMap, TestEmptyMap) {
237 CRMMap empty_crm_map;
238
239 unsigned int size;
240 scoped_array<char> serialized_data;
241 serialized_data.reset(serializer_.Serialize(&empty_crm_map, &size));
242 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
243
244 const unsigned int kCorrectSizeForEmptyMap = 16;
245 ASSERT_EQ(kCorrectSizeForEmptyMap, size);
246
247 const int *entry_test;
248 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
249 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
250 ASSERT_FALSE(test_map->RetrieveRange(10, entry_test));
251 }
252
TEST_F(TestStaticCRMMap,TestSingleElementMap)253 TEST_F(TestStaticCRMMap, TestSingleElementMap) {
254 CRMMap crm_map;
255 // Test on one element:
256 int entry = 1;
257 crm_map.StoreRange(10, 10, entry);
258
259 unsigned int size;
260 scoped_array<char> serialized_data;
261 serialized_data.reset(serializer_.Serialize(&crm_map, &size));
262 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
263
264 const unsigned int kCorrectSizeForSingleElementMap = 40;
265 ASSERT_EQ(kCorrectSizeForSingleElementMap, size);
266
267 const int *entry_test;
268 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
269 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
270 ASSERT_TRUE(test_map->RetrieveRange(10, entry_test));
271 ASSERT_EQ(*entry_test, entry);
272 ASSERT_TRUE(test_map->RetrieveRange(13, entry_test));
273 ASSERT_EQ(*entry_test, entry);
274 }
275
TEST_F(TestStaticCRMMap,RunTestData)276 TEST_F(TestStaticCRMMap, RunTestData) {
277 unsigned int test_high = sizeof(test_data) / sizeof(test_data[0]);
278
279 // Now, do the RetrieveRange tests. This further validates that the
280 // objects were stored properly and that retrieval returns the correct
281 // object.
282 // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
283 // new test_data array will be printed. Exercise caution when doing this.
284 // Be sure to verify the results manually!
285 #ifdef GENERATE_TEST_DATA
286 printf(" const int test_data[] = {\n");
287 #endif // GENERATE_TEST_DATA
288
289 for (unsigned int address = 0; address < test_high; ++address) {
290 const int *entryptr;
291 int value = 0;
292 if (test_map_.RetrieveRange(address, entryptr))
293 value = *entryptr;
294
295 #ifndef GENERATE_TEST_DATA
296 // Don't use ASSERT inside the loop because it won't show the failed
297 // |address|, and the line number will always be the same. That makes
298 // it difficult to figure out which test failed.
299 EXPECT_EQ(value, test_data[address]) << "FAIL: retrieve address "
300 << address;
301 #else // !GENERATE_TEST_DATA
302 printf(" %d%c%s // %d\n", value,
303 address == test_high - 1 ? ' ' : ',',
304 value < 10 ? " " : "",
305 address);
306 #endif // !GENERATE_TEST_DATA
307 }
308
309 #ifdef GENERATE_TEST_DATA
310 printf(" };\n");
311 #endif // GENERATE_TEST_DATA
312 }
313
314 } // namespace google_breakpad
315
main(int argc,char * argv[])316 int main(int argc, char *argv[]) {
317 ::testing::InitGoogleTest(&argc, argv);
318
319 return RUN_ALL_TESTS();
320 }
321