1  // Copyright 2006 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  // contained_range_map_unittest.cc: Unit tests for ContainedRangeMap
 30  //
 31  // Author: Mark Mentovai
 32  
 33  #ifdef HAVE_CONFIG_H
 34  #include <config.h>  // Must come first
 35  #endif
 36  
 37  #include <stdio.h>
 38  
 39  #include "processor/contained_range_map-inl.h"
 40  
 41  #include "processor/logging.h"
 42  
 43  
 44  #define ASSERT_TRUE(condition) \
 45    if (!(condition)) { \
 46      fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
 47      return false; \
 48    }
 49  
 50  #define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))
 51  
 52  
 53  namespace {
 54  
 55  
 56  using google_breakpad::ContainedRangeMap;
 57  // The first is the querying address, the second is the entries vector result.
 58  using EntriesTestPair = std::pair<unsigned, std::vector<int>>;
 59  using EntriesTestPairVec = std::vector<EntriesTestPair>;
 60  
 61  static bool RunTestsWithRetrieveRange(
 62      const ContainedRangeMap<unsigned int, int>& crm,
 63      const int* test_data,
 64      unsigned int test_length) {
 65    // Now, do the RetrieveRange tests.  This further validates that the
 66    // objects were stored properly and that retrieval returns the correct
 67    // object.
 68    // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
 69    // new test_data array will be printed.  Exercise caution when doing this.
 70    // Be sure to verify the results manually!
 71  #ifdef GENERATE_TEST_DATA
 72    printf("  const int test_data[] = {\n");
 73  #endif  // GENERATE_TEST_DATA
 74  
 75    for (unsigned int address = 0; address < test_length; ++address) {
 76      int value;
 77      if (!crm.RetrieveRange(address, &value))
 78        value = 0;
 79  
 80  #ifndef GENERATE_TEST_DATA
 81      // Don't use ASSERT inside the loop because it won't show the failed
 82      // |address|, and the line number will always be the same.  That makes
 83      // it difficult to figure out which test failed.
 84      if (value != test_data[address]) {
 85        fprintf(stderr, "FAIL: retrieve %d expected %d observed %d @ %s:%d\n",
 86                address, test_data[address], value, __FILE__, __LINE__);
 87        return false;
 88      }
 89  #else   // !GENERATE_TEST_DATA
 90      printf("    %d%c%s  // %d\n", value, address == test_high - 1 ? ' ' : ',',
 91             value < 10 ? " " : "", address);
 92  #endif  // !GENERATE_TEST_DATA
 93    }
 94  
 95  #ifdef GENERATE_TEST_DATA
 96    printf("  };\n");
 97  #endif  // GENERATE_TEST_DATA
 98  
 99    return true;
100  }
101  
102  static bool RunTestsWithRetrieveRangeVector(
103      const ContainedRangeMap<unsigned int, int>& crm,
104      const EntriesTestPairVec& entries_tests) {
105    for (const EntriesTestPair& entries_test : entries_tests) {
106      std::vector<const int*> entries;
107      crm.RetrieveRanges(entries_test.first, entries);
108      if (entries.size() != entries_test.second.size()) {
109        fprintf(stderr,
110                "FAIL: retrieving entries at address %u has size %zu "
111                "expected to have size %zu "
112                "@ %s: %d\n",
113                entries_test.first, entries.size(), entries_test.second.size(),
114                __FILE__, __LINE__);
115        return false;
116      }
117      for (size_t i = 0; i < entries.size(); ++i) {
118        if (*entries[i] != entries_test.second[i]) {
119          fprintf(stderr,
120                  "FAIL: retrieving entries at address %u entries[%zu] is %d "
121                  "expected %d"
122                  "@ %s: %d\n",
123                  entries_test.first, i, *entries[i], entries_test.second[i],
124                  __FILE__, __LINE__);
125          return false;
126        }
127      }
128    }
129    return true;
130  }
131  
132  static bool RunTestsWithNoEqualRange() {
133    ContainedRangeMap<unsigned int, int> crm;
134  
135    // First, do the StoreRange tests.  This validates the containment
136    // rules.
137    ASSERT_TRUE (crm.StoreRange(10, 10,  1));
138    ASSERT_FALSE(crm.StoreRange(10, 10,  2));  // exactly equal to 1
139    ASSERT_FALSE(crm.StoreRange(11, 10,  3));  // begins inside 1 and extends up
140    ASSERT_FALSE(crm.StoreRange( 9, 10,  4));  // begins below 1 and ends inside
141    ASSERT_TRUE (crm.StoreRange(11,  9,  5));  // contained by existing
142    ASSERT_TRUE (crm.StoreRange(12,  7,  6));
143    ASSERT_TRUE (crm.StoreRange( 9, 12,  7));  // contains existing
144    ASSERT_TRUE (crm.StoreRange( 9, 13,  8));
145    ASSERT_TRUE (crm.StoreRange( 8, 14,  9));
146    ASSERT_TRUE (crm.StoreRange(30,  3, 10));
147    ASSERT_TRUE (crm.StoreRange(33,  3, 11));
148    ASSERT_TRUE (crm.StoreRange(30,  6, 12));  // storable but totally masked
149    ASSERT_TRUE (crm.StoreRange(40,  8, 13));  // will be totally masked
150    ASSERT_TRUE (crm.StoreRange(40,  4, 14));
151    ASSERT_TRUE (crm.StoreRange(44,  4, 15));
152    ASSERT_FALSE(crm.StoreRange(32, 10, 16));  // begins in #10, ends in #14
153    ASSERT_FALSE(crm.StoreRange(50,  0, 17));  // zero length
154    ASSERT_TRUE (crm.StoreRange(50, 10, 18));
155    ASSERT_TRUE (crm.StoreRange(50,  1, 19));
156    ASSERT_TRUE (crm.StoreRange(59,  1, 20));
157    ASSERT_TRUE (crm.StoreRange(60,  1, 21));
158    ASSERT_TRUE (crm.StoreRange(69,  1, 22));
159    ASSERT_TRUE (crm.StoreRange(60, 10, 23));
160    ASSERT_TRUE (crm.StoreRange(68,  1, 24));
161    ASSERT_TRUE (crm.StoreRange(61,  1, 25));
162    ASSERT_TRUE (crm.StoreRange(61,  8, 26));
163    ASSERT_FALSE(crm.StoreRange(59,  9, 27));
164    ASSERT_FALSE(crm.StoreRange(59, 10, 28));
165    ASSERT_FALSE(crm.StoreRange(59, 11, 29));
166    ASSERT_TRUE (crm.StoreRange(70, 10, 30));
167    ASSERT_TRUE (crm.StoreRange(74,  2, 31));
168    ASSERT_TRUE (crm.StoreRange(77,  2, 32));
169    ASSERT_FALSE(crm.StoreRange(72,  6, 33));
170    ASSERT_TRUE (crm.StoreRange(80,  3, 34));
171    ASSERT_TRUE (crm.StoreRange(81,  1, 35));
172    ASSERT_TRUE (crm.StoreRange(82,  1, 36));
173    ASSERT_TRUE (crm.StoreRange(83,  3, 37));
174    ASSERT_TRUE (crm.StoreRange(84,  1, 38));
175    ASSERT_TRUE (crm.StoreRange(83,  1, 39));
176    ASSERT_TRUE (crm.StoreRange(86,  5, 40));
177    ASSERT_TRUE (crm.StoreRange(88,  1, 41));
178    ASSERT_TRUE (crm.StoreRange(90,  1, 42));
179    ASSERT_TRUE (crm.StoreRange(86,  1, 43));
180    ASSERT_TRUE (crm.StoreRange(87,  1, 44));
181    ASSERT_TRUE (crm.StoreRange(89,  1, 45));
182    ASSERT_TRUE (crm.StoreRange(87,  4, 46));
183    ASSERT_TRUE (crm.StoreRange(87,  3, 47));
184    ASSERT_FALSE(crm.StoreRange(86,  2, 48));
185  
186    // Each element in test_data contains the expected result when calling
187    // RetrieveRange on an address.
188    const int test_data[] = {
189      0,   // 0
190      0,   // 1
191      0,   // 2
192      0,   // 3
193      0,   // 4
194      0,   // 5
195      0,   // 6
196      0,   // 7
197      9,   // 8
198      7,   // 9
199      1,   // 10
200      5,   // 11
201      6,   // 12
202      6,   // 13
203      6,   // 14
204      6,   // 15
205      6,   // 16
206      6,   // 17
207      6,   // 18
208      5,   // 19
209      7,   // 20
210      8,   // 21
211      0,   // 22
212      0,   // 23
213      0,   // 24
214      0,   // 25
215      0,   // 26
216      0,   // 27
217      0,   // 28
218      0,   // 29
219      10,  // 30
220      10,  // 31
221      10,  // 32
222      11,  // 33
223      11,  // 34
224      11,  // 35
225      0,   // 36
226      0,   // 37
227      0,   // 38
228      0,   // 39
229      14,  // 40
230      14,  // 41
231      14,  // 42
232      14,  // 43
233      15,  // 44
234      15,  // 45
235      15,  // 46
236      15,  // 47
237      0,   // 48
238      0,   // 49
239      19,  // 50
240      18,  // 51
241      18,  // 52
242      18,  // 53
243      18,  // 54
244      18,  // 55
245      18,  // 56
246      18,  // 57
247      18,  // 58
248      20,  // 59
249      21,  // 60
250      25,  // 61
251      26,  // 62
252      26,  // 63
253      26,  // 64
254      26,  // 65
255      26,  // 66
256      26,  // 67
257      24,  // 68
258      22,  // 69
259      30,  // 70
260      30,  // 71
261      30,  // 72
262      30,  // 73
263      31,  // 74
264      31,  // 75
265      30,  // 76
266      32,  // 77
267      32,  // 78
268      30,  // 79
269      34,  // 80
270      35,  // 81
271      36,  // 82
272      39,  // 83
273      38,  // 84
274      37,  // 85
275      43,  // 86
276      44,  // 87
277      41,  // 88
278      45,  // 89
279      42,  // 90
280      0,   // 91
281      0,   // 92
282      0,   // 93
283      0,   // 94
284      0,   // 95
285      0,   // 96
286      0,   // 97
287      0,   // 98
288      0    // 99
289    };
290    unsigned int test_length = sizeof(test_data) / sizeof(int);
291    return RunTestsWithRetrieveRange(crm, test_data, test_length);
292  }
293  
294  static bool RunTestsWithEqualRange() {
295    ContainedRangeMap<unsigned int, int> crm(true);
296  
297    // First, do the StoreRange tests.  This validates the containment
298    // rules.
299    ASSERT_TRUE (crm.StoreRange(1,  3,  1));
300    ASSERT_TRUE (crm.StoreRange(1,  3,  2));  // exactly equal to 1
301    ASSERT_TRUE (crm.StoreRange(1,  3,  3));  // exactly equal to 1, 2
302    ASSERT_TRUE (crm.StoreRange(1,  3,  4));  // exactly equal to 1, 2, 3
303    ASSERT_FALSE(crm.StoreRange(0,  3,  5));  // partial overlap.
304    ASSERT_FALSE(crm.StoreRange(2,  3,  6));  // partial overlap.
305  
306    ASSERT_TRUE (crm.StoreRange(5,  3,  7));
307    ASSERT_TRUE (crm.StoreRange(5,  3,  8));  // exactly equal to 7
308    ASSERT_TRUE (crm.StoreRange(5,  3,  9));  // exactly equal to 7, 8
309    ASSERT_TRUE (crm.StoreRange(5,  4, 10));  // encompasses 7, 8, 9
310    ASSERT_TRUE (crm.StoreRange(5,  5, 11));  // encompasses 7, 8, 9, 10
311  
312    ASSERT_TRUE (crm.StoreRange(10, 3, 12));
313    ASSERT_TRUE (crm.StoreRange(10, 3, 13));  // exactly equal to 12
314    ASSERT_TRUE (crm.StoreRange(11, 2, 14));  // encompasses by 12
315    ASSERT_TRUE (crm.StoreRange(11, 1, 15));  // encompasses by 12, 13
316  
317    ASSERT_TRUE (crm.StoreRange(14, 3, 16));
318    ASSERT_TRUE (crm.StoreRange(14, 3, 17));  // exactly equal to 14
319    ASSERT_TRUE (crm.StoreRange(14, 1, 18));  // encompasses by 14, 15
320    ASSERT_TRUE (crm.StoreRange(14, 2, 19));  // encompasses by 14, 15 and encompasses 16
321    ASSERT_TRUE (crm.StoreRange(14, 1, 20));  // exactly equal to 18
322    ASSERT_TRUE (crm.StoreRange(14, 2, 21));  // exactly equal to 19
323  
324    // Each element in test_data contains the expected result when calling
325    // RetrieveRange on an address.
326    const int test_data[] = {
327        0,   // 0
328        4,   // 1
329        4,   // 2
330        4,   // 3
331        0,   // 4
332        9,   // 5
333        9,   // 6
334        9,   // 7
335        10,  // 8
336        11,   // 9
337        13,  // 10
338        15,  // 11
339        14,  // 12
340        0,   // 13
341        20,  // 14
342        21,  // 15
343        17,  // 16
344        0,   // 17
345    };
346    unsigned int test_length = sizeof(test_data) / sizeof(int);
347    EntriesTestPairVec entries_tests = {
348        {0,  {}},
349        {1,  {4, 3, 2, 1}},
350        {2,  {4, 3, 2, 1}},
351        {3,  {4, 3, 2, 1}},
352        {4,  {}},
353        {5,  {9, 8, 7, 10, 11}},
354        {6,  {9, 8, 7, 10, 11}},
355        {7,  {9, 8, 7, 10, 11}},
356        {8,  {10, 11}},
357        {9,  {11}},
358        {10, {13, 12}},
359        {11, {15, 14, 13, 12}},
360        {12, {14, 13, 12}},
361        {13, {}},
362        {14, {20, 18, 21, 19, 17, 16}},
363        {15, {21, 19, 17, 16}},
364        {16, {17, 16}},
365        {17, {}},
366    };
367    return RunTestsWithRetrieveRange(crm, test_data, test_length) &&
368           RunTestsWithRetrieveRangeVector(crm, entries_tests);
369  }
370  
371  static bool RunTests() {
372    return RunTestsWithNoEqualRange() && RunTestsWithEqualRange();
373  }
374  
375  
376  }  // namespace
377  
378  
379  int main(int argc, char** argv) {
380    BPLOG_INIT(&argc, &argv);
381  
382    return RunTests() ? 0 : 1;
383  }