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,
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
ExpectFalseRangesOverlapOrTouch(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)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
ExpectRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)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
ExpectFalseRangesOverlap(uint64_t a_start,uint64_t a_num,uint64_t b_start,uint64_t b_num)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
TEST(ExtentRangesTest,ExtentsOverlapTest)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
TEST(ExtentRangesTest,SimpleTest)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
TEST(ExtentRangesTest,MultipleRanges)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
TEST(ExtentRangesTest,GetExtentsForBlockCountTest)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
TEST(ExtentRangesTest,ContainsBlockTest)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
TEST(ExtentRangesTest,FilterExtentRangesEmptyRanges)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
TEST(ExtentRangesTest,FilterExtentRangesMultipleRanges)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
TEST(ExtentRangesTest,FilterExtentRangesOvelapping)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