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@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 49typedef int32_t AddrType; 50typedef int32_t EntryType; 51 52class 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 69TEST_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 80TEST_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 102TEST_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 124class 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 141TEST_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 152TEST_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 174TEST_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 199class 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 216TEST_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 227TEST_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 248TEST_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 272class 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 289TEST_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 305TEST_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 330TEST_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 382int main(int argc, char *argv[]) { 383 ::testing::InitGoogleTest(&argc, argv); 384 385 return RUN_ALL_TESTS(); 386} 387