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 (lambxsy@google.com)
 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:
 57    void SetUp() {
 58      serialized_size_ = 0;
 59      serialized_data_ = NULL;
 60    }
 61  
 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  
 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  
 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  
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:
129    void SetUp() {
130      serialized_size_ = 0;
131      serialized_data_ = 0;
132    }
133  
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  
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  
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  
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:
204    void SetUp() {
205      serialized_size_ = 0;
206      serialized_data_ = 0;
207    }
208  
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  
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  
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  
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:
277    void SetUp() {
278      serialized_size_ = 0;
279      serialized_data_ = 0;
280    }
281  
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  
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  
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  
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  
385  int main(int argc, char* argv[]) {
386    ::testing::InitGoogleTest(&argc, argv);
387  
388    return RUN_ALL_TESTS();
389  }