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 // map_serializers_unittest.cc: Unit tests for std::map serializer and
30 // std::map wrapper serializers.
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 <climits>
39 #include <map>
40 #include <string>
41 #include <utility>
42 #include <iostream>
43 #include <sstream>
44
45 #include "breakpad_googletest_includes.h"
46 #include "map_serializers-inl.h"
47
48 #include "processor/address_map-inl.h"
49 #include "processor/range_map-inl.h"
50 #include "processor/contained_range_map-inl.h"
51
52 typedef int32_t AddrType;
53 typedef int32_t EntryType;
54
55 class TestStdMapSerializer : public ::testing::Test {
56 protected:
SetUp()57 void SetUp() {
58 serialized_size_ = 0;
59 serialized_data_ = NULL;
60 }
61
TearDown()62 void TearDown() {
63 delete [] serialized_data_;
64 }
65
66 std::map<AddrType, EntryType> std_map_;
67 google_breakpad::StdMapSerializer<AddrType, EntryType> serializer_;
68 uint32_t serialized_size_;
69 char* serialized_data_;
70 };
71
TEST_F(TestStdMapSerializer,EmptyMapTestCase)72 TEST_F(TestStdMapSerializer, EmptyMapTestCase) {
73 const int32_t correct_data[] = { 0 };
74 uint32_t correct_size = sizeof(correct_data);
75
76 // std_map_ is empty.
77 serialized_data_ = serializer_.Serialize(std_map_, &serialized_size_);
78
79 EXPECT_EQ(correct_size, serialized_size_);
80 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
81 }
82
TEST_F(TestStdMapSerializer,MapWithTwoElementsTestCase)83 TEST_F(TestStdMapSerializer, MapWithTwoElementsTestCase) {
84 const int32_t correct_data[] = {
85 // # of nodes
86 2,
87 // Offsets
88 20, 24,
89 // Keys
90 1, 3,
91 // Values
92 2, 6
93 };
94 uint32_t correct_size = sizeof(correct_data);
95
96 std_map_.insert(std::make_pair(1, 2));
97 std_map_.insert(std::make_pair(3, 6));
98
99 serialized_data_ = serializer_.Serialize(std_map_, &serialized_size_);
100
101 EXPECT_EQ(correct_size, serialized_size_);
102 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
103 }
104
TEST_F(TestStdMapSerializer,MapWithFiveElementsTestCase)105 TEST_F(TestStdMapSerializer, MapWithFiveElementsTestCase) {
106 const int32_t correct_data[] = {
107 // # of nodes
108 5,
109 // Offsets
110 44, 48, 52, 56, 60,
111 // Keys
112 1, 2, 3, 4, 5,
113 // Values
114 11, 12, 13, 14, 15
115 };
116 uint32_t correct_size = sizeof(correct_data);
117
118 for (int i = 1; i < 6; ++i)
119 std_map_.insert(std::make_pair(i, 10 + i));
120
121 serialized_data_ = serializer_.Serialize(std_map_, &serialized_size_);
122
123 EXPECT_EQ(correct_size, serialized_size_);
124 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
125 }
126
127 class TestAddressMapSerializer : public ::testing::Test {
128 protected:
SetUp()129 void SetUp() {
130 serialized_size_ = 0;
131 serialized_data_ = 0;
132 }
133
TearDown()134 void TearDown() {
135 delete [] serialized_data_;
136 }
137
138 google_breakpad::AddressMap<AddrType, EntryType> address_map_;
139 google_breakpad::AddressMapSerializer<AddrType, EntryType> serializer_;
140 uint32_t serialized_size_;
141 char* serialized_data_;
142 };
143
TEST_F(TestAddressMapSerializer,EmptyMapTestCase)144 TEST_F(TestAddressMapSerializer, EmptyMapTestCase) {
145 const int32_t correct_data[] = { 0 };
146 uint32_t correct_size = sizeof(correct_data);
147
148 // std_map_ is empty.
149 serialized_data_ = serializer_.Serialize(address_map_, &serialized_size_);
150
151 EXPECT_EQ(correct_size, serialized_size_);
152 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
153 }
154
TEST_F(TestAddressMapSerializer,MapWithTwoElementsTestCase)155 TEST_F(TestAddressMapSerializer, MapWithTwoElementsTestCase) {
156 const int32_t correct_data[] = {
157 // # of nodes
158 2,
159 // Offsets
160 20, 24,
161 // Keys
162 1, 3,
163 // Values
164 2, 6
165 };
166 uint32_t correct_size = sizeof(correct_data);
167
168 address_map_.Store(1, 2);
169 address_map_.Store(3, 6);
170
171 serialized_data_ = serializer_.Serialize(address_map_, &serialized_size_);
172
173 EXPECT_EQ(correct_size, serialized_size_);
174 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
175 }
176
TEST_F(TestAddressMapSerializer,MapWithFourElementsTestCase)177 TEST_F(TestAddressMapSerializer, MapWithFourElementsTestCase) {
178 const int32_t correct_data[] = {
179 // # of nodes
180 4,
181 // Offsets
182 36, 40, 44, 48,
183 // Keys
184 -6, -4, 8, 123,
185 // Values
186 2, 3, 5, 8
187 };
188 uint32_t correct_size = sizeof(correct_data);
189
190 address_map_.Store(-6, 2);
191 address_map_.Store(-4, 3);
192 address_map_.Store(8, 5);
193 address_map_.Store(123, 8);
194
195 serialized_data_ = serializer_.Serialize(address_map_, &serialized_size_);
196
197 EXPECT_EQ(correct_size, serialized_size_);
198 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
199 }
200
201
202 class TestRangeMapSerializer : public ::testing::Test {
203 protected:
SetUp()204 void SetUp() {
205 serialized_size_ = 0;
206 serialized_data_ = 0;
207 }
208
TearDown()209 void TearDown() {
210 delete [] serialized_data_;
211 }
212
213 google_breakpad::RangeMap<AddrType, EntryType> range_map_;
214 google_breakpad::RangeMapSerializer<AddrType, EntryType> serializer_;
215 uint32_t serialized_size_;
216 char* serialized_data_;
217 };
218
TEST_F(TestRangeMapSerializer,EmptyMapTestCase)219 TEST_F(TestRangeMapSerializer, EmptyMapTestCase) {
220 const int32_t correct_data[] = { 0 };
221 uint32_t correct_size = sizeof(correct_data);
222
223 // range_map_ is empty.
224 serialized_data_ = serializer_.Serialize(range_map_, &serialized_size_);
225
226 EXPECT_EQ(correct_size, serialized_size_);
227 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
228 }
229
TEST_F(TestRangeMapSerializer,MapWithOneRangeTestCase)230 TEST_F(TestRangeMapSerializer, MapWithOneRangeTestCase) {
231 const int32_t correct_data[] = {
232 // # of nodes
233 1,
234 // Offsets
235 12,
236 // Keys: high address
237 10,
238 // Values: (low address, entry) pairs
239 1, 6
240 };
241 uint32_t correct_size = sizeof(correct_data);
242
243 range_map_.StoreRange(1, 10, 6);
244
245 serialized_data_ = serializer_.Serialize(range_map_, &serialized_size_);
246
247 EXPECT_EQ(correct_size, serialized_size_);
248 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
249 }
250
TEST_F(TestRangeMapSerializer,MapWithThreeRangesTestCase)251 TEST_F(TestRangeMapSerializer, MapWithThreeRangesTestCase) {
252 const int32_t correct_data[] = {
253 // # of nodes
254 3,
255 // Offsets
256 28, 36, 44,
257 // Keys: high address
258 5, 9, 20,
259 // Values: (low address, entry) pairs
260 2, 1, 6, 2, 10, 3
261 };
262 uint32_t correct_size = sizeof(correct_data);
263
264 ASSERT_TRUE(range_map_.StoreRange(2, 4, 1));
265 ASSERT_TRUE(range_map_.StoreRange(6, 4, 2));
266 ASSERT_TRUE(range_map_.StoreRange(10, 11, 3));
267
268 serialized_data_ = serializer_.Serialize(range_map_, &serialized_size_);
269
270 EXPECT_EQ(correct_size, serialized_size_);
271 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
272 }
273
274
275 class TestContainedRangeMapSerializer : public ::testing::Test {
276 protected:
SetUp()277 void SetUp() {
278 serialized_size_ = 0;
279 serialized_data_ = 0;
280 }
281
TearDown()282 void TearDown() {
283 delete [] serialized_data_;
284 }
285
286 google_breakpad::ContainedRangeMap<AddrType, EntryType> crm_map_;
287 google_breakpad::ContainedRangeMapSerializer<AddrType, EntryType> serializer_;
288 uint32_t serialized_size_;
289 char* serialized_data_;
290 };
291
TEST_F(TestContainedRangeMapSerializer,EmptyMapTestCase)292 TEST_F(TestContainedRangeMapSerializer, EmptyMapTestCase) {
293 const int32_t correct_data[] = {
294 0, // base address of root
295 4, // size of entry
296 0, // entry stored at root
297 0 // empty map stored at root
298 };
299 uint32_t correct_size = sizeof(correct_data);
300
301 // crm_map_ is empty.
302 serialized_data_ = serializer_.Serialize(&crm_map_, &serialized_size_);
303
304 EXPECT_EQ(correct_size, serialized_size_);
305 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
306 }
307
TEST_F(TestContainedRangeMapSerializer,MapWithOneRangeTestCase)308 TEST_F(TestContainedRangeMapSerializer, MapWithOneRangeTestCase) {
309 const int32_t correct_data[] = {
310 0, // base address of root
311 4, // size of entry
312 0, // entry stored at root
313 // Map stored at root node:
314 1, // # of nodes
315 12, // offset
316 9, // key
317 // value: a child ContainedRangeMap
318 3, // base address of child CRM
319 4, // size of entry
320 -1, // entry stored in child CRM
321 0 // empty sub-map stored in child CRM
322 };
323 uint32_t correct_size = sizeof(correct_data);
324
325 crm_map_.StoreRange(3, 7, -1);
326
327 serialized_data_ = serializer_.Serialize(&crm_map_, &serialized_size_);
328
329 EXPECT_EQ(correct_size, serialized_size_);
330 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
331 }
332
TEST_F(TestContainedRangeMapSerializer,MapWithTwoLevelsTestCase)333 TEST_F(TestContainedRangeMapSerializer, MapWithTwoLevelsTestCase) {
334 // Tree structure of ranges:
335 // root level 0
336 // |
337 // map
338 // / \ level 1: child1, child2
339 // 2~8 10~20
340 // | |
341 // map map
342 // / \ |
343 // 3~4 6~7 16-20 level 2: grandchild1, grandchild2, grandchild3
344
345 const int32_t correct_data[] = {
346 // root: base, entry_size, entry
347 0, 4, 0,
348 // root's map: # of nodes, offset1, offset2, key1, key2
349 2, 20, 84, 8, 20,
350 // child1: base, entry_size, entry:
351 2, 4, -1,
352 // child1's map: # of nodes, offset1, offset2, key1, key2
353 2, 20, 36, 4, 7,
354 // grandchild1: base, entry_size, entry, empty_map
355 3, 4, -1, 0,
356 // grandchild2: base, entry_size, entry, empty_map
357 6, 4, -1, 0,
358 // child2: base, entry_size, entry:
359 10, 4, -1,
360 // child2's map: # of nodes, offset1, key1
361 1, 12, 20,
362 // grandchild3: base, entry_size, entry, empty_map
363 16, 4, -1, 0
364 };
365 uint32_t correct_size = sizeof(correct_data);
366
367 // Store child1.
368 ASSERT_TRUE(crm_map_.StoreRange(2, 7, -1));
369 // Store child2.
370 ASSERT_TRUE(crm_map_.StoreRange(10, 11, -1));
371 // Store grandchild1.
372 ASSERT_TRUE(crm_map_.StoreRange(3, 2, -1));
373 // Store grandchild2.
374 ASSERT_TRUE(crm_map_.StoreRange(6, 2, -1));
375 // Store grandchild3.
376 ASSERT_TRUE(crm_map_.StoreRange(16, 5, -1));
377
378 serialized_data_ = serializer_.Serialize(&crm_map_, &serialized_size_);
379
380 EXPECT_EQ(correct_size, serialized_size_);
381 EXPECT_EQ(memcmp(correct_data, serialized_data_, correct_size), 0);
382 }
383
384
main(int argc,char * argv[])385 int main(int argc, char* argv[]) {
386 ::testing::InitGoogleTest(&argc, argv);
387
388 return RUN_ALL_TESTS();
389 }
390