1 //
2 // Copyright (C) 2010 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16
17 #include "update_engine/payload_generator/extent_ranges.h"
18
19 #include <vector>
20
21 #include <gtest/gtest.h>
22
23 #include "update_engine/payload_consumer/payload_constants.h"
24 #include "update_engine/payload_generator/extent_utils.h"
25
26 using std::vector;
27 using chromeos_update_engine::operator==;
28
29 namespace chromeos_update_engine {
30
31 class ExtentRangesTest : public ::testing::Test {};
32
33 namespace {
ExpectRangeEq(const ExtentRanges & ranges,const uint64_t * expected,size_t sz,int line)34 void ExpectRangeEq(const ExtentRanges& ranges,
35 const uint64_t* expected,
36 size_t sz,
37 int line) {
38 uint64_t blocks = 0;
39 for (size_t i = 1; i < sz; i += 2) {
40 blocks += expected[i];
41 }
42 ASSERT_EQ(blocks, ranges.blocks()) << "line: " << line;
43
44 const ExtentRanges::ExtentSet& result = ranges.extent_set();
45 ExtentRanges::ExtentSet::const_iterator it = result.begin();
46 for (size_t i = 0; i < sz; i += 2) {
47 ASSERT_FALSE(it == result.end()) << "line: " << line;
48 ASSERT_EQ(expected[i], it->start_block()) << "line: " << line;
49 ASSERT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
50 ++it;
51 }
52 }
53
54 #define ASSERT_RANGE_EQ(ranges, var) \
55 ASSERT_NO_FATAL_FAILURE(ExpectRangeEq(ranges, var, std::size(var), __LINE__))
56
ExpectRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)57 void ExpectRangesOverlapOrTouch(uint64_t a_start,
58 uint64_t a_num,
59 uint64_t b_start,
60 uint64_t b_num) {
61 ASSERT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
62 ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
63 ASSERT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
64 ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
65 }
66
ExpectFalseRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)67 void ExpectFalseRangesOverlapOrTouch(uint64_t a_start,
68 uint64_t a_num,
69 uint64_t b_start,
70 uint64_t b_num) {
71 ASSERT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
72 ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
73 ASSERT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
74 ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
75 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
76 ExtentForRange(b_start, b_num)));
77 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
78 ExtentForRange(a_start, a_num)));
79 }
80
ExpectRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)81 void ExpectRangesOverlap(uint64_t a_start,
82 uint64_t a_num,
83 uint64_t b_start,
84 uint64_t b_num) {
85 ASSERT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
86 ExtentForRange(b_start, b_num)));
87 ASSERT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
88 ExtentForRange(a_start, a_num)));
89 ASSERT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
90 ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
91 ASSERT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
92 ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
93 }
94
ExpectFalseRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)95 void ExpectFalseRangesOverlap(uint64_t a_start,
96 uint64_t a_num,
97 uint64_t b_start,
98 uint64_t b_num) {
99 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
100 ExtentForRange(b_start, b_num)));
101 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
102 ExtentForRange(a_start, a_num)));
103 }
104
105 } // namespace
106
TEST(ExtentRangesTest,ExtentsOverlapTest)107 TEST(ExtentRangesTest, ExtentsOverlapTest) {
108 ASSERT_NO_FATAL_FAILURE(ExpectRangesOverlapOrTouch(10, 20, 30, 10));
109 ASSERT_NO_FATAL_FAILURE(ExpectRangesOverlap(10, 20, 25, 10));
110 ASSERT_NO_FATAL_FAILURE(ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10));
111 ASSERT_NO_FATAL_FAILURE(ExpectFalseRangesOverlap(10, 20, 30, 10));
112 ASSERT_NO_FATAL_FAILURE(ExpectRangesOverlap(12, 4, 12, 3));
113
114 ASSERT_NO_FATAL_FAILURE(
115 ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3));
116 ASSERT_NO_FATAL_FAILURE(ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3));
117 ASSERT_NO_FATAL_FAILURE(
118 ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3));
119 ASSERT_NO_FATAL_FAILURE(
120 ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3));
121 ASSERT_NO_FATAL_FAILURE(ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3));
122 ASSERT_NO_FATAL_FAILURE(ExpectFalseRangesOverlap(10, 2, kSparseHole, 3));
123 }
124
TEST(ExtentRangesTest,SimpleTest)125 TEST(ExtentRangesTest, SimpleTest) {
126 ExtentRanges ranges;
127 {
128 static constexpr uint64_t expected[] = {};
129 // Can't use arraysize() on 0-length arrays:
130 ASSERT_NO_FATAL_FAILURE(ExpectRangeEq(ranges, expected, 0, __LINE__));
131 }
132 ranges.SubtractBlock(2);
133 {
134 static constexpr uint64_t expected[] = {};
135 // Can't use arraysize() on 0-length arrays:
136 ASSERT_NO_FATAL_FAILURE(ExpectRangeEq(ranges, expected, 0, __LINE__));
137 }
138
139 ranges.AddBlock(0);
140 ranges.Dump();
141 ranges.AddBlock(1);
142 ranges.AddBlock(3);
143
144 {
145 static constexpr uint64_t expected[] = {0, 2, 3, 1};
146 ASSERT_RANGE_EQ(ranges, expected);
147 }
148 ranges.AddBlock(2);
149 {
150 static constexpr uint64_t expected[] = {0, 4};
151 ASSERT_RANGE_EQ(ranges, expected);
152 ranges.AddBlock(kSparseHole);
153 ASSERT_RANGE_EQ(ranges, expected);
154 ranges.SubtractBlock(kSparseHole);
155 ASSERT_RANGE_EQ(ranges, expected);
156 }
157 ranges.SubtractBlock(2);
158 {
159 static constexpr uint64_t expected[] = {0, 2, 3, 1};
160 ASSERT_RANGE_EQ(ranges, expected);
161 }
162
163 for (uint64_t i = 100; i < 1000; i += 100) {
164 ranges.AddExtent(ExtentForRange(i, 50));
165 }
166 {
167 static constexpr uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50,
168 300, 50, 400, 50, 500, 50, 600, 50,
169 700, 50, 800, 50, 900, 50};
170 ASSERT_RANGE_EQ(ranges, expected);
171 }
172
173 ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
174 {
175 static constexpr uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
176 10, 410, 40, 500, 50, 600, 50,
177 700, 50, 800, 50, 900, 50};
178 ASSERT_RANGE_EQ(ranges, expected);
179 }
180 ranges.AddExtent(ExtentForRange(100000, 0));
181 {
182 static constexpr uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
183 10, 410, 40, 500, 50, 600, 50,
184 700, 50, 800, 50, 900, 50};
185 ASSERT_RANGE_EQ(ranges, expected);
186 }
187 ranges.SubtractExtent(ExtentForRange(3, 0));
188 {
189 static constexpr uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200,
190 10, 410, 40, 500, 50, 600, 50,
191 700, 50, 800, 50, 900, 50};
192 ASSERT_RANGE_EQ(ranges, expected);
193 }
194 }
195
TEST(ExtentRangesTest,MultipleRanges)196 TEST(ExtentRangesTest, MultipleRanges) {
197 ExtentRanges ranges_a, ranges_b;
198 ranges_a.AddBlock(0);
199 ranges_b.AddBlock(4);
200 ranges_b.AddBlock(3);
201 {
202 constexpr uint64_t expected[] = {3, 2};
203 ASSERT_RANGE_EQ(ranges_b, expected);
204 }
205 ranges_a.AddRanges(ranges_b);
206 {
207 constexpr uint64_t expected[] = {0, 1, 3, 2};
208 ASSERT_RANGE_EQ(ranges_a, expected);
209 }
210 ranges_a.SubtractRanges(ranges_b);
211 {
212 constexpr uint64_t expected[] = {0, 1};
213 ASSERT_RANGE_EQ(ranges_a, expected);
214 }
215 {
216 constexpr uint64_t expected[] = {3, 2};
217 ASSERT_RANGE_EQ(ranges_b, expected);
218 }
219 }
220
TEST(ExtentRangesTest,GetExtentsForBlockCountTest)221 TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
222 ExtentRanges ranges;
223 ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
224 {
225 vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
226 ASSERT_TRUE(zero_extents.empty());
227 }
228 ::google::protobuf::RepeatedPtrField<Extent> rep_field;
229 *rep_field.Add() = ExtentForRange(30, 40);
230 ranges.AddRepeatedExtents(rep_field);
231 ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
232 *rep_field.Mutable(0) = ExtentForRange(50, 10);
233 ranges.SubtractRepeatedExtents(rep_field);
234 ASSERT_EQ(40U, ranges.blocks());
235
236 for (int i = 0; i < 2; i++) {
237 vector<Extent> expected(2);
238 expected[0] = ExtentForRange(10, 10);
239 expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
240 vector<Extent> actual =
241 ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
242 ASSERT_EQ(expected.size(), actual.size());
243 for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
244 ASSERT_EQ(expected[j].start_block(), actual[j].start_block())
245 << "j = " << j;
246 ASSERT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
247 << "j = " << j;
248 }
249 }
250 }
251
TEST(ExtentRangesTest,ContainsBlockTest)252 TEST(ExtentRangesTest, ContainsBlockTest) {
253 ExtentRanges ranges;
254 ASSERT_FALSE(ranges.ContainsBlock(123));
255
256 ranges.AddExtent(ExtentForRange(10, 10));
257 ranges.AddExtent(ExtentForRange(100, 1));
258
259 ASSERT_FALSE(ranges.ContainsBlock(9));
260 ASSERT_TRUE(ranges.ContainsBlock(10));
261 ASSERT_TRUE(ranges.ContainsBlock(15));
262 ASSERT_TRUE(ranges.ContainsBlock(19));
263 ASSERT_FALSE(ranges.ContainsBlock(20));
264
265 // Test for an extent with just the block we are requesting.
266 ASSERT_FALSE(ranges.ContainsBlock(99));
267 ASSERT_TRUE(ranges.ContainsBlock(100));
268 ASSERT_FALSE(ranges.ContainsBlock(101));
269 }
270
TEST(ExtentRangesTest,FilterExtentRangesEmptyRanges)271 TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
272 ExtentRanges ranges;
273 ASSERT_EQ(vector<Extent>(), FilterExtentRanges(vector<Extent>(), ranges));
274 ASSERT_EQ(vector<Extent>{ExtentForRange(50, 10)},
275 FilterExtentRanges(vector<Extent>{ExtentForRange(50, 10)}, ranges));
276 // Check that the empty Extents are ignored.
277 ASSERT_EQ((vector<Extent>{ExtentForRange(10, 10), ExtentForRange(20, 10)}),
278 FilterExtentRanges(vector<Extent>{ExtentForRange(10, 10),
279 ExtentForRange(3, 0),
280 ExtentForRange(20, 10)},
281 ranges));
282 }
283
TEST(ExtentRangesTest,FilterExtentRangesMultipleRanges)284 TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
285 // Two overlapping extents, with three ranges to remove.
286 vector<Extent> extents{ExtentForRange(10, 100), ExtentForRange(30, 100)};
287 ExtentRanges ranges;
288 // This overlaps the beginning of the second extent.
289 ranges.AddExtent(ExtentForRange(28, 3));
290 ranges.AddExtent(ExtentForRange(50, 10));
291 ranges.AddExtent(ExtentForRange(70, 10));
292 // This overlaps the end of the second extent.
293 ranges.AddExtent(ExtentForRange(108, 6));
294 ASSERT_EQ((vector<Extent>{// For the first extent:
295 ExtentForRange(10, 18),
296 ExtentForRange(31, 19),
297 ExtentForRange(60, 10),
298 ExtentForRange(80, 28),
299 // For the second extent:
300 ExtentForRange(31, 19),
301 ExtentForRange(60, 10),
302 ExtentForRange(80, 28),
303 ExtentForRange(114, 16)}),
304 FilterExtentRanges(extents, ranges));
305 }
306
TEST(ExtentRangesTest,FilterExtentRangesOvelapping)307 TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
308 ExtentRanges ranges;
309 ranges.AddExtent(ExtentForRange(10, 3));
310 ranges.AddExtent(ExtentForRange(20, 5));
311 // Requested extent overlaps with one of the ranges.
312 ASSERT_EQ(vector<Extent>(),
313 FilterExtentRanges(
314 vector<Extent>{ExtentForRange(10, 1), ExtentForRange(22, 1)},
315 ranges));
316 }
317
TEST(ExtentRangesTest,GetOverlapExtent)318 TEST(ExtentRangesTest, GetOverlapExtent) {
319 const auto ret1 =
320 GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(10, 10));
321 ASSERT_EQ(ret1.num_blocks(), 0UL) << ret1;
322 const auto ret2 =
323 GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(9, 10));
324 ASSERT_EQ(ret2, ExtentForRange(9, 1));
325
326 const auto ret3 =
327 GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 10));
328 ASSERT_EQ(ret3, ExtentForRange(7, 5));
329 const auto ret4 =
330 GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 3));
331 ASSERT_EQ(ret4.num_blocks(), 0UL);
332 }
333
TEST(ExtentRangesTest,ContainsBlockSameStart)334 TEST(ExtentRangesTest, ContainsBlockSameStart) {
335 ExtentRanges ranges{false};
336 ranges.AddExtent(ExtentForRange(5, 4));
337 ranges.AddExtent(ExtentForRange(10, 5));
338 ranges.AddExtent(ExtentForRange(15, 5));
339 ranges.AddExtent(ExtentForRange(20, 5));
340 ranges.AddExtent(ExtentForRange(25, 5));
341
342 ASSERT_TRUE(ranges.ContainsBlock(10));
343 ASSERT_TRUE(ranges.ContainsBlock(15));
344 ASSERT_TRUE(ranges.ContainsBlock(20));
345 ASSERT_TRUE(ranges.ContainsBlock(25));
346 ASSERT_TRUE(ranges.ContainsBlock(29));
347 ASSERT_FALSE(ranges.ContainsBlock(30));
348 ASSERT_FALSE(ranges.ContainsBlock(9));
349 }
350
TEST(ExtentRangesTest,OverlapsWithExtentSameStart)351 TEST(ExtentRangesTest, OverlapsWithExtentSameStart) {
352 ExtentRanges ranges{false};
353 ranges.AddExtent(ExtentForRange(5, 4));
354 ranges.AddExtent(ExtentForRange(10, 5));
355 ranges.AddExtent(ExtentForRange(15, 5));
356 ranges.AddExtent(ExtentForRange(20, 5));
357 ranges.AddExtent(ExtentForRange(25, 5));
358
359 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(9, 2)));
360 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(12, 5)));
361 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(14, 5)));
362 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(10, 9)));
363 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(11, 20)));
364 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(0, 5)));
365 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(30, 20)));
366 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(9, 1)));
367
368 ranges.SubtractExtent(ExtentForRange(12, 5));
369 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(12, 5)));
370 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(13, 3)));
371 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(15, 2)));
372 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(14, 5)));
373 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(17, 1)));
374 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(8, 5)));
375 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(8, 4)));
376 }
377
TEST(ExtentRangesTest,OverlapsWithExtent)378 TEST(ExtentRangesTest, OverlapsWithExtent) {
379 ExtentRanges ranges;
380 ranges.AddExtent(ExtentForRange(5, 5));
381 ranges.AddExtent(ExtentForRange(15, 5));
382 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(3, 10)));
383 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(17, 10)));
384 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(0, 10)));
385 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(10, 5)));
386 ASSERT_FALSE(ranges.OverlapsWithExtent(ExtentForRange(20, 5)));
387 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(7, 1)));
388 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(0, 100)));
389 ASSERT_TRUE(ranges.OverlapsWithExtent(ExtentForRange(19, 1)));
390 }
391
TEST(ExtentRangesTest,AddExtentMergeStressTest)392 TEST(ExtentRangesTest, AddExtentMergeStressTest) {
393 ExtentRanges ranges(true);
394 for (size_t i = 0; i < 1000000; i++) {
395 ranges.AddExtent(ExtentForRange(i, 1));
396 }
397 ASSERT_EQ(ranges.extent_set().size(), 1UL) << ranges.extent_set();
398 }
399
TEST(ExtentRangesTest,AddExtentNoMergeStressTest)400 TEST(ExtentRangesTest, AddExtentNoMergeStressTest) {
401 ExtentRanges ranges(true);
402 for (size_t i = 0; i < 200000; i++) {
403 ranges.AddExtent(ExtentForRange(i * 2, 1));
404 }
405 ASSERT_EQ(ranges.extent_set().size(), 200000UL) << ranges.extent_set();
406 }
407
TEST(ExtentRangesTest,AddExtentTouching)408 TEST(ExtentRangesTest, AddExtentTouching) {
409 ExtentRanges ranges(true);
410 ranges.AddExtent(ExtentForRange(5, 5));
411 ranges.AddExtent(ExtentForRange(25, 7));
412 ASSERT_EQ(ranges.extent_set().size(), 2UL) << ranges.extent_set();
413 ranges.AddExtent(ExtentForRange(0, 5));
414 ASSERT_EQ(ranges.extent_set().size(), 2UL) << ranges.extent_set();
415 ranges.AddExtent(ExtentForRange(10, 15));
416 ASSERT_EQ(ranges.extent_set().size(), 1UL) << ranges.extent_set();
417 ranges.AddExtent(ExtentForRange(32, 8));
418 ASSERT_EQ(ranges.extent_set().size(), 1UL) << ranges.extent_set();
419 ranges.AddExtent(ExtentForRange(45, 5));
420 ASSERT_EQ(ranges.extent_set().size(), 2UL) << ranges.extent_set();
421 }
422
423 } // namespace chromeos_update_engine
424