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/common/test_utils.h"
24 #include "update_engine/payload_consumer/payload_constants.h"
25 #include "update_engine/payload_generator/extent_utils.h"
26 
27 using std::vector;
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   EXPECT_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     EXPECT_FALSE(it == result.end()) << "line: " << line;
48     EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
49     EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
50     ++it;
51   }
52 }
53 
54 #define EXPECT_RANGE_EQ(ranges, var)                            \
55   do {                                                          \
56     ExpectRangeEq(ranges, var, arraysize(var), __LINE__);       \
57   } while (0)
58 
ExpectRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)59 void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
60                                 uint64_t b_start, uint64_t b_num) {
61   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
62                                                                  a_num),
63                                                   ExtentForRange(b_start,
64                                                                  b_num)));
65   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
66                                                                  b_num),
67                                                   ExtentForRange(a_start,
68                                                                  a_num)));
69 }
70 
ExpectFalseRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)71 void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
72                                      uint64_t b_start, uint64_t b_num) {
73   EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
74                                                                   a_num),
75                                                    ExtentForRange(b_start,
76                                                                   b_num)));
77   EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
78                                                                   b_num),
79                                                    ExtentForRange(a_start,
80                                                                   a_num)));
81   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
82                                                            a_num),
83                                             ExtentForRange(b_start,
84                                                            b_num)));
85   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
86                                                            b_num),
87                                             ExtentForRange(a_start,
88                                                            a_num)));
89 }
90 
ExpectRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)91 void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num,
92                          uint64_t b_start, uint64_t b_num) {
93   EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
94                                                           a_num),
95                                            ExtentForRange(b_start,
96                                                           b_num)));
97   EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
98                                                           b_num),
99                                            ExtentForRange(a_start,
100                                                           a_num)));
101   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
102                                                                  a_num),
103                                                   ExtentForRange(b_start,
104                                                                  b_num)));
105   EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
106                                                                  b_num),
107                                                   ExtentForRange(a_start,
108                                                                  a_num)));
109 }
110 
ExpectFalseRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)111 void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num,
112                               uint64_t b_start, uint64_t b_num) {
113   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
114                                                            a_num),
115                                             ExtentForRange(b_start,
116                                                            b_num)));
117   EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
118                                                            b_num),
119                                             ExtentForRange(a_start,
120                                                            a_num)));
121 }
122 
123 }  // namespace
124 
TEST(ExtentRangesTest,ExtentsOverlapTest)125 TEST(ExtentRangesTest, ExtentsOverlapTest) {
126   ExpectRangesOverlapOrTouch(10, 20, 30, 10);
127   ExpectRangesOverlap(10, 20, 25, 10);
128   ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
129   ExpectFalseRangesOverlap(10, 20, 30, 10);
130   ExpectRangesOverlap(12, 4, 12, 3);
131 
132   ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
133   ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
134   ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
135   ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
136   ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
137   ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
138 }
139 
TEST(ExtentRangesTest,SimpleTest)140 TEST(ExtentRangesTest, SimpleTest) {
141   ExtentRanges ranges;
142   {
143     static const uint64_t expected[] = {};
144     // Can't use arraysize() on 0-length arrays:
145     ExpectRangeEq(ranges, expected, 0, __LINE__);
146   }
147   ranges.SubtractBlock(2);
148   {
149     static const uint64_t expected[] = {};
150     // Can't use arraysize() on 0-length arrays:
151     ExpectRangeEq(ranges, expected, 0, __LINE__);
152   }
153 
154   ranges.AddBlock(0);
155   ranges.Dump();
156   ranges.AddBlock(1);
157   ranges.AddBlock(3);
158 
159   {
160     static const uint64_t expected[] = {0, 2, 3, 1};
161     EXPECT_RANGE_EQ(ranges, expected);
162   }
163   ranges.AddBlock(2);
164   {
165     static const uint64_t expected[] = {0, 4};
166     EXPECT_RANGE_EQ(ranges, expected);
167     ranges.AddBlock(kSparseHole);
168     EXPECT_RANGE_EQ(ranges, expected);
169     ranges.SubtractBlock(kSparseHole);
170     EXPECT_RANGE_EQ(ranges, expected);
171   }
172   ranges.SubtractBlock(2);
173   {
174     static const uint64_t expected[] = {0, 2, 3, 1};
175     EXPECT_RANGE_EQ(ranges, expected);
176   }
177 
178   for (uint64_t i = 100; i < 1000; i += 100) {
179     ranges.AddExtent(ExtentForRange(i, 50));
180   }
181   {
182     static const uint64_t expected[] = {
183       0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
184       500, 50, 600, 50, 700, 50, 800, 50, 900, 50
185     };
186     EXPECT_RANGE_EQ(ranges, expected);
187   }
188 
189   ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
190   {
191     static const uint64_t expected[] = {
192       0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
193       600, 50, 700, 50, 800, 50, 900, 50
194     };
195     EXPECT_RANGE_EQ(ranges, expected);
196   }
197   ranges.AddExtent(ExtentForRange(100000, 0));
198   {
199     static const uint64_t expected[] = {
200       0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
201       600, 50, 700, 50, 800, 50, 900, 50
202     };
203     EXPECT_RANGE_EQ(ranges, expected);
204   }
205   ranges.SubtractExtent(ExtentForRange(3, 0));
206   {
207     static const uint64_t expected[] = {
208       0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
209       600, 50, 700, 50, 800, 50, 900, 50
210     };
211     EXPECT_RANGE_EQ(ranges, expected);
212   }
213 }
214 
TEST(ExtentRangesTest,MultipleRanges)215 TEST(ExtentRangesTest, MultipleRanges) {
216   ExtentRanges ranges_a, ranges_b;
217   ranges_a.AddBlock(0);
218   ranges_b.AddBlock(4);
219   ranges_b.AddBlock(3);
220   {
221     uint64_t expected[] = {3, 2};
222     EXPECT_RANGE_EQ(ranges_b, expected);
223   }
224   ranges_a.AddRanges(ranges_b);
225   {
226     uint64_t expected[] = {0, 1, 3, 2};
227     EXPECT_RANGE_EQ(ranges_a, expected);
228   }
229   ranges_a.SubtractRanges(ranges_b);
230   {
231     uint64_t expected[] = {0, 1};
232     EXPECT_RANGE_EQ(ranges_a, expected);
233   }
234   {
235     uint64_t expected[] = {3, 2};
236     EXPECT_RANGE_EQ(ranges_b, expected);
237   }
238 }
239 
TEST(ExtentRangesTest,GetExtentsForBlockCountTest)240 TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
241   ExtentRanges ranges;
242   ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
243   {
244     vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
245     EXPECT_TRUE(zero_extents.empty());
246   }
247   ::google::protobuf::RepeatedPtrField<Extent> rep_field;
248   *rep_field.Add() = ExtentForRange(30, 40);
249   ranges.AddRepeatedExtents(rep_field);
250   ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
251   *rep_field.Mutable(0) = ExtentForRange(50, 10);
252   ranges.SubtractRepeatedExtents(rep_field);
253   EXPECT_EQ(40U, ranges.blocks());
254 
255   for (int i = 0; i < 2; i++) {
256     vector<Extent> expected(2);
257     expected[0] = ExtentForRange(10, 10);
258     expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
259     vector<Extent> actual =
260         ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
261     EXPECT_EQ(expected.size(), actual.size());
262     for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
263       EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
264           << "j = " << j;
265       EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
266           << "j = " << j;
267     }
268   }
269 }
270 
TEST(ExtentRangesTest,ContainsBlockTest)271 TEST(ExtentRangesTest, ContainsBlockTest) {
272   ExtentRanges ranges;
273   EXPECT_FALSE(ranges.ContainsBlock(123));
274 
275   ranges.AddExtent(ExtentForRange(10, 10));
276   ranges.AddExtent(ExtentForRange(100, 1));
277 
278   EXPECT_FALSE(ranges.ContainsBlock(9));
279   EXPECT_TRUE(ranges.ContainsBlock(10));
280   EXPECT_TRUE(ranges.ContainsBlock(15));
281   EXPECT_TRUE(ranges.ContainsBlock(19));
282   EXPECT_FALSE(ranges.ContainsBlock(20));
283 
284   // Test for an extent with just the block we are requesting.
285   EXPECT_FALSE(ranges.ContainsBlock(99));
286   EXPECT_TRUE(ranges.ContainsBlock(100));
287   EXPECT_FALSE(ranges.ContainsBlock(101));
288 }
289 
TEST(ExtentRangesTest,FilterExtentRangesEmptyRanges)290 TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
291   ExtentRanges ranges;
292   EXPECT_EQ(vector<Extent>(),
293             FilterExtentRanges(vector<Extent>(), ranges));
294   EXPECT_EQ(
295       vector<Extent>{ ExtentForRange(50, 10) },
296       FilterExtentRanges(vector<Extent>{ ExtentForRange(50, 10) }, ranges));
297   // Check that the empty Extents are ignored.
298   EXPECT_EQ(
299       (vector<Extent>{ ExtentForRange(10, 10), ExtentForRange(20, 10) }),
300       FilterExtentRanges(vector<Extent>{
301            ExtentForRange(10, 10),
302            ExtentForRange(3, 0),
303            ExtentForRange(20, 10) }, ranges));
304 }
305 
TEST(ExtentRangesTest,FilterExtentRangesMultipleRanges)306 TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
307   // Two overlaping extents, with three ranges to remove.
308   vector<Extent> extents {
309       ExtentForRange(10, 100),
310       ExtentForRange(30, 100) };
311   ExtentRanges ranges;
312   // This overlaps the beginning of the second extent.
313   ranges.AddExtent(ExtentForRange(28, 3));
314   ranges.AddExtent(ExtentForRange(50, 10));
315   ranges.AddExtent(ExtentForRange(70, 10));
316   // This overlaps the end of the second extent.
317   ranges.AddExtent(ExtentForRange(108, 6));
318   EXPECT_EQ(
319       (vector<Extent>{
320            // For the first extent:
321            ExtentForRange(10, 18),
322            ExtentForRange(31, 19),
323            ExtentForRange(60, 10),
324            ExtentForRange(80, 28),
325            // For the second extent:
326            ExtentForRange(31, 19),
327            ExtentForRange(60, 10),
328            ExtentForRange(80, 28),
329            ExtentForRange(114, 16)}),
330       FilterExtentRanges(extents, ranges));
331 }
332 
TEST(ExtentRangesTest,FilterExtentRangesOvelapping)333 TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
334   ExtentRanges ranges;
335   ranges.AddExtent(ExtentForRange(10, 3));
336   ranges.AddExtent(ExtentForRange(20, 5));
337   // Requested extent overlaps with one of the ranges.
338   EXPECT_EQ(vector<Extent>(),
339             FilterExtentRanges(vector<Extent>{
340                                    ExtentForRange(10, 1),
341                                    ExtentForRange(22, 1) },
342                                ranges));
343 }
344 
345 }  // namespace chromeos_update_engine
346