extent_ranges_unittest.cc revision 39910dcd1d68987ccee7c3031dc269233a8490bb 
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
27using std::vector;
28
29namespace chromeos_update_engine {
30
31class ExtentRangesTest : public ::testing::Test {};
32
33namespace {
34void 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
59void 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
71void 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
91void 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
111void 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
125TEST(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
140TEST(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
215TEST(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
240TEST(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(40, 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
271TEST(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
290TEST(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
306TEST(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
333TEST(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