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