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