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/common/test_utils.h"
25 #include "update_engine/payload_consumer/payload_constants.h"
26 #include "update_engine/payload_generator/extent_utils.h"
27 
28 using std::vector;
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   EXPECT_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     EXPECT_FALSE(it == result.end()) << "line: " << line;
49     EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
50     EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
51     ++it;
52   }
53 }
54 
55 #define EXPECT_RANGE_EQ(ranges, var)                       \
56   do {                                                     \
57     ExpectRangeEq(ranges, var, base::size(var), __LINE__); \
58   } while (0)
59 
ExpectRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)60 void ExpectRangesOverlapOrTouch(uint64_t a_start,
61                                 uint64_t a_num,
62                                 uint64_t b_start,
63                                 uint64_t b_num) {
64   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
65       ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
66   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
67       ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
68 }
69 
ExpectFalseRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)70 void ExpectFalseRangesOverlapOrTouch(uint64_t a_start,
71                                      uint64_t a_num,
72                                      uint64_t b_start,
73                                      uint64_t b_num) {
74   EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
75       ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
76   EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(
77       ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
78   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
79                                             ExtentForRange(b_start, b_num)));
80   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
81                                             ExtentForRange(a_start, a_num)));
82 }
83 
ExpectRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)84 void ExpectRangesOverlap(uint64_t a_start,
85                          uint64_t a_num,
86                          uint64_t b_start,
87                          uint64_t b_num) {
88   EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
89                                            ExtentForRange(b_start, b_num)));
90   EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
91                                            ExtentForRange(a_start, a_num)));
92   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
93       ExtentForRange(a_start, a_num), ExtentForRange(b_start, b_num)));
94   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(
95       ExtentForRange(b_start, b_num), ExtentForRange(a_start, a_num)));
96 }
97 
ExpectFalseRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)98 void ExpectFalseRangesOverlap(uint64_t a_start,
99                               uint64_t a_num,
100                               uint64_t b_start,
101                               uint64_t b_num) {
102   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, a_num),
103                                             ExtentForRange(b_start, b_num)));
104   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, b_num),
105                                             ExtentForRange(a_start, a_num)));
106 }
107 
108 }  // namespace
109 
TEST(ExtentRangesTest,ExtentsOverlapTest)110 TEST(ExtentRangesTest, ExtentsOverlapTest) {
111   ExpectRangesOverlapOrTouch(10, 20, 30, 10);
112   ExpectRangesOverlap(10, 20, 25, 10);
113   ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
114   ExpectFalseRangesOverlap(10, 20, 30, 10);
115   ExpectRangesOverlap(12, 4, 12, 3);
116 
117   ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
118   ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
119   ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
120   ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
121   ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
122   ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
123 }
124 
TEST(ExtentRangesTest,SimpleTest)125 TEST(ExtentRangesTest, SimpleTest) {
126   ExtentRanges ranges;
127   {
128     static const uint64_t expected[] = {};
129     // Can't use arraysize() on 0-length arrays:
130     ExpectRangeEq(ranges, expected, 0, __LINE__);
131   }
132   ranges.SubtractBlock(2);
133   {
134     static const uint64_t expected[] = {};
135     // Can't use arraysize() on 0-length arrays:
136     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 const uint64_t expected[] = {0, 2, 3, 1};
146     EXPECT_RANGE_EQ(ranges, expected);
147   }
148   ranges.AddBlock(2);
149   {
150     static const uint64_t expected[] = {0, 4};
151     EXPECT_RANGE_EQ(ranges, expected);
152     ranges.AddBlock(kSparseHole);
153     EXPECT_RANGE_EQ(ranges, expected);
154     ranges.SubtractBlock(kSparseHole);
155     EXPECT_RANGE_EQ(ranges, expected);
156   }
157   ranges.SubtractBlock(2);
158   {
159     static const uint64_t expected[] = {0, 2, 3, 1};
160     EXPECT_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 const 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     EXPECT_RANGE_EQ(ranges, expected);
171   }
172 
173   ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
174   {
175     static const 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     EXPECT_RANGE_EQ(ranges, expected);
179   }
180   ranges.AddExtent(ExtentForRange(100000, 0));
181   {
182     static const 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     EXPECT_RANGE_EQ(ranges, expected);
186   }
187   ranges.SubtractExtent(ExtentForRange(3, 0));
188   {
189     static const 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     EXPECT_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     uint64_t expected[] = {3, 2};
203     EXPECT_RANGE_EQ(ranges_b, expected);
204   }
205   ranges_a.AddRanges(ranges_b);
206   {
207     uint64_t expected[] = {0, 1, 3, 2};
208     EXPECT_RANGE_EQ(ranges_a, expected);
209   }
210   ranges_a.SubtractRanges(ranges_b);
211   {
212     uint64_t expected[] = {0, 1};
213     EXPECT_RANGE_EQ(ranges_a, expected);
214   }
215   {
216     uint64_t expected[] = {3, 2};
217     EXPECT_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     EXPECT_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   EXPECT_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     EXPECT_EQ(expected.size(), actual.size());
243     for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
244       EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
245           << "j = " << j;
246       EXPECT_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   EXPECT_FALSE(ranges.ContainsBlock(123));
255 
256   ranges.AddExtent(ExtentForRange(10, 10));
257   ranges.AddExtent(ExtentForRange(100, 1));
258 
259   EXPECT_FALSE(ranges.ContainsBlock(9));
260   EXPECT_TRUE(ranges.ContainsBlock(10));
261   EXPECT_TRUE(ranges.ContainsBlock(15));
262   EXPECT_TRUE(ranges.ContainsBlock(19));
263   EXPECT_FALSE(ranges.ContainsBlock(20));
264 
265   // Test for an extent with just the block we are requesting.
266   EXPECT_FALSE(ranges.ContainsBlock(99));
267   EXPECT_TRUE(ranges.ContainsBlock(100));
268   EXPECT_FALSE(ranges.ContainsBlock(101));
269 }
270 
TEST(ExtentRangesTest,FilterExtentRangesEmptyRanges)271 TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
272   ExtentRanges ranges;
273   EXPECT_EQ(vector<Extent>(), FilterExtentRanges(vector<Extent>(), ranges));
274   EXPECT_EQ(vector<Extent>{ExtentForRange(50, 10)},
275             FilterExtentRanges(vector<Extent>{ExtentForRange(50, 10)}, ranges));
276   // Check that the empty Extents are ignored.
277   EXPECT_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   EXPECT_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   EXPECT_EQ(vector<Extent>(),
313             FilterExtentRanges(
314                 vector<Extent>{ExtentForRange(10, 1), ExtentForRange(22, 1)},
315                 ranges));
316 }
317 
318 }  // namespace chromeos_update_engine
319