OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2010, Google Inc. | |
mmandlis
2016/06/02 23:50:59
2016?
ivanpe
2016/06/03 03:56:56
Doh!
| |
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 // range_map_shrink_down_unittest.cc: Unit tests for RangeMap that specifically | |
31 // test shrink down when ranges overlap. | |
32 // | |
33 // Author: Ivan Penkov | |
34 | |
35 #include <limits.h> | |
36 #include <stdio.h> | |
37 | |
38 #include "processor/range_map-inl.h" | |
39 | |
40 #include "breakpad_googletest_includes.h" | |
41 #include "common/scoped_ptr.h" | |
42 #include "processor/linked_ptr.h" | |
43 #include "processor/logging.h" | |
44 | |
45 namespace { | |
46 | |
47 using google_breakpad::linked_ptr; | |
48 using google_breakpad::scoped_ptr; | |
49 using google_breakpad::RangeMap; | |
50 | |
51 // A CountedObject holds an int. A global (not thread safe!) count of | |
52 // allocated CountedObjects is maintained to help test memory management. | |
53 class CountedObject { | |
54 public: | |
55 explicit CountedObject(int id) : id_(id) { ++count_; } | |
56 ~CountedObject() { --count_; } | |
57 | |
58 static int count() { return count_; } | |
59 int id() const { return id_; } | |
60 | |
61 private: | |
62 static int count_; | |
63 int id_; | |
64 }; | |
65 | |
66 int CountedObject::count_; | |
67 | |
68 typedef int AddressType; | |
69 typedef RangeMap<AddressType, linked_ptr<CountedObject>> TestMap; | |
70 | |
71 // Same range cannot be stored wice. | |
72 TEST(RangeMap, TestShinkDown_SameRange) { | |
73 TestMap range_map; | |
74 range_map.SetEnableShrinkDown(true); | |
75 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
76 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
77 object_1)); | |
78 | |
79 // Same range cannot be stored wice. | |
80 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
81 EXPECT_FALSE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
82 object_2)); | |
83 } | |
84 | |
85 // If a range is completely contained by another range, then the larger range | |
86 // should be shrinked down. | |
87 TEST(RangeMap, TestShinkDown_CompletelyContained_1) { | |
88 TestMap range_map; | |
89 range_map.SetEnableShrinkDown(true); | |
90 // Larger range is added first. | |
91 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
92 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
93 object_1)); | |
94 // Smaller (contained) range is added second. | |
95 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
96 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */, | |
97 object_2)); | |
98 linked_ptr<CountedObject> object; | |
99 AddressType retrieved_base = AddressType(); | |
100 AddressType retrieved_delta = AddressType(); | |
101 AddressType retrieved_size = AddressType(); | |
102 // The first range contains the second, so the first range should have been | |
103 // shrunk to [90, 99]. Range [0, 9] should be free. | |
104 EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base, | |
105 &retrieved_delta, &retrieved_size)); | |
106 EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base, | |
107 &retrieved_delta, &retrieved_size)); | |
108 EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base, | |
109 &retrieved_delta, &retrieved_size)); | |
110 EXPECT_EQ(1, object->id()); | |
111 EXPECT_EQ(90, retrieved_base); | |
112 EXPECT_EQ(90, retrieved_delta); | |
113 EXPECT_EQ(10, retrieved_size); | |
114 // Validate the properties of the smaller range (should be untouched). | |
115 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base, | |
116 &retrieved_delta, &retrieved_size)); | |
117 EXPECT_EQ(2, object->id()); | |
118 EXPECT_EQ(10, retrieved_base); | |
119 EXPECT_EQ(0, retrieved_delta); | |
120 EXPECT_EQ(80, retrieved_size); | |
121 } | |
122 | |
123 // Same as the previous test, however the larger range is added second. | |
124 TEST(RangeMap, TestShinkDown_CompletelyContained_2) { | |
mmandlis
2016/06/02 23:50:59
nit - maybe use more descriptive test case names,
ivanpe
2016/06/03 03:56:56
Done.
| |
125 TestMap range_map; | |
126 range_map.SetEnableShrinkDown(true); | |
127 // Smaller (contained) range is added first. | |
128 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
129 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */, | |
130 object_1)); | |
131 // Larger range is added second. | |
132 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
133 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
134 object_2)); | |
135 linked_ptr<CountedObject> object; | |
136 AddressType retrieved_base = AddressType(); | |
137 AddressType retrieved_delta = AddressType(); | |
138 AddressType retrieved_size = AddressType(); | |
139 // The second range contains the first, so the second range should have been | |
140 // shrunk to [90, 99]. Range [0, 9] should be free. | |
141 EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base, | |
142 &retrieved_delta, &retrieved_size)); | |
143 EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base, | |
144 &retrieved_delta, &retrieved_size)); | |
145 EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base, | |
146 &retrieved_delta, &retrieved_size)); | |
147 EXPECT_EQ(2, object->id()); | |
148 EXPECT_EQ(90, retrieved_base); | |
149 EXPECT_EQ(90, retrieved_delta); | |
150 EXPECT_EQ(10, retrieved_size); | |
151 // Validate the properties of the smaller range (should be untouched). | |
152 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base, | |
153 &retrieved_delta, &retrieved_size)); | |
154 EXPECT_EQ(1, object->id()); | |
155 EXPECT_EQ(10, retrieved_base); | |
156 EXPECT_EQ(0, retrieved_delta); | |
157 EXPECT_EQ(80, retrieved_size); | |
158 } | |
159 | |
160 TEST(RangeMap, TestShinkDown_PartialOverlap_AtBeginning) { | |
161 TestMap range_map; | |
162 range_map.SetEnableShrinkDown(true); | |
163 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
164 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
165 object_1)); | |
166 | |
167 // Partial overlap at the beginning of the new range. | |
168 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
169 EXPECT_TRUE(range_map.StoreRange(90 /* base address */, 110 /* size */, | |
170 object_2)); | |
171 | |
172 linked_ptr<CountedObject> object; | |
173 AddressType retrieved_base = AddressType(); | |
174 AddressType retrieved_delta = AddressType(); | |
175 AddressType retrieved_size = AddressType(); | |
176 // The second range is supposed to be shrunk down so the following address | |
177 // should resize in the first range. | |
178 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base, | |
179 &retrieved_delta, &retrieved_size)); | |
180 EXPECT_EQ(1, object->id()); | |
181 EXPECT_EQ(0, retrieved_base); | |
182 EXPECT_EQ(0, retrieved_delta); | |
183 EXPECT_EQ(100, retrieved_size); | |
184 // Validate the properties of the shrunk down range. | |
185 EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base, | |
186 &retrieved_delta, &retrieved_size)); | |
187 EXPECT_EQ(2, object->id()); | |
188 EXPECT_EQ(100, retrieved_base); | |
189 EXPECT_EQ(10, retrieved_delta); | |
190 EXPECT_EQ(100, retrieved_size); | |
191 } | |
192 | |
193 TEST(RangeMap, TestShinkDown_PartialOverlap_AtEnd) { | |
194 TestMap range_map; | |
195 range_map.SetEnableShrinkDown(true); | |
196 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
197 EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 50 /* size */, | |
198 object_1)); | |
199 | |
200 // Partial overlap at the end of the new range. | |
201 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
202 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 70 /* size */, | |
203 object_2)); | |
204 | |
205 linked_ptr<CountedObject> object; | |
206 AddressType retrieved_base = AddressType(); | |
207 AddressType retrieved_delta = AddressType(); | |
208 AddressType retrieved_size = AddressType(); | |
209 // The first range is supposed to be shrunk down so the following address | |
210 // should resize in the first range. | |
211 EXPECT_TRUE(range_map.RetrieveRange(69, &object, &retrieved_base, | |
212 &retrieved_delta, &retrieved_size)); | |
213 EXPECT_EQ(2, object->id()); | |
214 EXPECT_EQ(0, retrieved_base); | |
215 EXPECT_EQ(0, retrieved_delta); | |
216 EXPECT_EQ(70, retrieved_size); | |
217 // Validate the properties of the shrunk down range. | |
218 EXPECT_TRUE(range_map.RetrieveRange(70, &object, &retrieved_base, | |
219 &retrieved_delta, &retrieved_size)); | |
220 EXPECT_EQ(1, object->id()); | |
221 EXPECT_EQ(70, retrieved_base); | |
222 EXPECT_EQ(20, retrieved_delta); | |
223 EXPECT_EQ(30, retrieved_size); | |
224 } | |
225 | |
226 // A new range is overlapped at both ends. The new range and the range | |
227 // that overlaps at the end should be shrink. The range that overlaps at the | |
228 // beginning should be left untouched. | |
229 TEST(RangeMap, TestShinkDown_OverlapAtBothEnds) { | |
230 TestMap range_map; | |
231 range_map.SetEnableShrinkDown(true); | |
232 // This should overlap object_3 at the beginning. | |
233 linked_ptr<CountedObject> object_1(new CountedObject(1)); | |
234 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */, | |
235 object_1)); | |
236 | |
237 // This should overlap object_3 at the end. | |
238 linked_ptr<CountedObject> object_2(new CountedObject(2)); | |
239 EXPECT_TRUE(range_map.StoreRange(100 /* base address */, 100 /* size */, | |
240 object_2)); | |
241 | |
242 // This should be overlapped on both ends by object_1 and object_2. | |
243 linked_ptr<CountedObject> object_3(new CountedObject(3)); | |
244 EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 100 /* size */, | |
245 object_3)); | |
246 | |
247 linked_ptr<CountedObject> object; | |
248 AddressType retrieved_base = AddressType(); | |
249 AddressType retrieved_delta = AddressType(); | |
250 AddressType retrieved_size = AddressType(); | |
251 // The first range should be intact. | |
252 EXPECT_TRUE(range_map.RetrieveRange(0, &object, &retrieved_base, | |
253 &retrieved_delta, &retrieved_size)); | |
254 EXPECT_EQ(1, object->id()); | |
255 EXPECT_EQ(0, retrieved_base); | |
256 EXPECT_EQ(0, retrieved_delta); | |
257 EXPECT_EQ(100, retrieved_size); | |
258 // The second range should be shrunk down by 50. | |
259 EXPECT_TRUE(range_map.RetrieveRange(150, &object, &retrieved_base, | |
260 &retrieved_delta, &retrieved_size)); | |
261 EXPECT_EQ(2, object->id()); | |
262 EXPECT_EQ(150, retrieved_base); | |
263 EXPECT_EQ(50, retrieved_delta); | |
264 EXPECT_EQ(50, retrieved_size); | |
265 // The third range (in the middle) should be shrunk down by 50. | |
266 EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base, | |
267 &retrieved_delta, &retrieved_size)); | |
268 EXPECT_EQ(3, object->id()); | |
269 EXPECT_EQ(100, retrieved_base); | |
270 EXPECT_EQ(50, retrieved_delta); | |
271 EXPECT_EQ(50, retrieved_size); | |
272 } | |
273 | |
274 } // namespace | |
OLD | NEW |