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