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