OLD | NEW |
(Empty) | |
| 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 <vector> |
| 6 |
| 7 #include <gtest/gtest.h> |
| 8 |
| 9 #include "update_engine/extent_ranges.h" |
| 10 #include "update_engine/test_utils.h" |
| 11 |
| 12 using std::vector; |
| 13 |
| 14 namespace chromeos_update_engine { |
| 15 |
| 16 class ExtentRangesTest : public ::testing::Test {}; |
| 17 |
| 18 namespace { |
| 19 void ExpectRangeEq(const ExtentRanges& ranges, |
| 20 uint64_t* expected, |
| 21 size_t sz, |
| 22 int line) { |
| 23 uint64_t blocks = 0; |
| 24 for (size_t i = 1; i < sz; i += 2) { |
| 25 blocks += expected[i]; |
| 26 } |
| 27 EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line; |
| 28 |
| 29 const ExtentRanges::ExtentSet& result = ranges.extent_set(); |
| 30 ExtentRanges::ExtentSet::const_iterator it = result.begin(); |
| 31 for (size_t i = 0; i < sz; i += 2) { |
| 32 EXPECT_FALSE(it == result.end()) << "line: " << line; |
| 33 EXPECT_EQ(expected[i], it->start_block()) << "line: " << line; |
| 34 EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line; |
| 35 ++it; |
| 36 } |
| 37 } |
| 38 |
| 39 #define EXPECT_RANGE_EQ(ranges, var) \ |
| 40 do { \ |
| 41 ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \ |
| 42 } while (0) |
| 43 |
| 44 void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num, |
| 45 uint64_t b_start, uint64_t b_num) { |
| 46 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, |
| 47 a_num), |
| 48 ExtentForRange(b_start, |
| 49 b_num))); |
| 50 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, |
| 51 b_num), |
| 52 ExtentForRange(a_start, |
| 53 a_num))); |
| 54 } |
| 55 |
| 56 void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num, |
| 57 uint64_t b_start, uint64_t b_num) { |
| 58 EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, |
| 59 a_num), |
| 60 ExtentForRange(b_start, |
| 61 b_num))); |
| 62 EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, |
| 63 b_num), |
| 64 ExtentForRange(a_start, |
| 65 a_num))); |
| 66 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, |
| 67 a_num), |
| 68 ExtentForRange(b_start, |
| 69 b_num))); |
| 70 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, |
| 71 b_num), |
| 72 ExtentForRange(a_start, |
| 73 a_num))); |
| 74 } |
| 75 |
| 76 void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num, |
| 77 uint64_t b_start, uint64_t b_num) { |
| 78 EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, |
| 79 a_num), |
| 80 ExtentForRange(b_start, |
| 81 b_num))); |
| 82 EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, |
| 83 b_num), |
| 84 ExtentForRange(a_start, |
| 85 a_num))); |
| 86 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, |
| 87 a_num), |
| 88 ExtentForRange(b_start, |
| 89 b_num))); |
| 90 EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, |
| 91 b_num), |
| 92 ExtentForRange(a_start, |
| 93 a_num))); |
| 94 } |
| 95 |
| 96 void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num, |
| 97 uint64_t b_start, uint64_t b_num) { |
| 98 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, |
| 99 a_num), |
| 100 ExtentForRange(b_start, |
| 101 b_num))); |
| 102 EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, |
| 103 b_num), |
| 104 ExtentForRange(a_start, |
| 105 a_num))); |
| 106 } |
| 107 |
| 108 } // namespace {} |
| 109 |
| 110 TEST(ExtentRangesTest, ExtentsOverlapTest) { |
| 111 ExpectRangesOverlapOrTouch(10, 20, 30, 10); |
| 112 ExpectRangesOverlap(10, 20, 25, 10); |
| 113 ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10); |
| 114 ExpectFalseRangesOverlap(10, 20, 30, 10); |
| 115 ExpectRangesOverlap(12, 4, 12, 3); |
| 116 } |
| 117 |
| 118 TEST(ExtentRangesTest, SimpleTest) { |
| 119 ExtentRanges ranges; |
| 120 { |
| 121 uint64_t expected[] = {}; |
| 122 // Can't use arraysize() on 0-length arrays: |
| 123 ExpectRangeEq(ranges, expected, 0, __LINE__); |
| 124 } |
| 125 ranges.SubtractBlock(2); |
| 126 { |
| 127 uint64_t expected[] = {}; |
| 128 // Can't use arraysize() on 0-length arrays: |
| 129 ExpectRangeEq(ranges, expected, 0, __LINE__); |
| 130 } |
| 131 |
| 132 ranges.AddBlock(0); |
| 133 ranges.Dump(); |
| 134 ranges.AddBlock(1); |
| 135 ranges.AddBlock(3); |
| 136 |
| 137 { |
| 138 uint64_t expected[] = {0, 2, 3, 1}; |
| 139 EXPECT_RANGE_EQ(ranges, expected); |
| 140 } |
| 141 ranges.AddBlock(2); |
| 142 { |
| 143 uint64_t expected[] = {0, 4}; |
| 144 EXPECT_RANGE_EQ(ranges, expected); |
| 145 } |
| 146 ranges.SubtractBlock(2); |
| 147 { |
| 148 uint64_t expected[] = {0, 2, 3, 1}; |
| 149 EXPECT_RANGE_EQ(ranges, expected); |
| 150 } |
| 151 |
| 152 for (uint64_t i = 100; i < 1000; i += 100) { |
| 153 ranges.AddExtent(ExtentForRange(i, 50)); |
| 154 } |
| 155 { |
| 156 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50, |
| 157 500, 50, 600, 50, 700, 50, 800, 50, 900, 50}; |
| 158 EXPECT_RANGE_EQ(ranges, expected); |
| 159 } |
| 160 |
| 161 ranges.SubtractExtent(ExtentForRange(210, 410 - 210)); |
| 162 { |
| 163 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, |
| 164 600, 50, 700, 50, 800, 50, 900, 50}; |
| 165 EXPECT_RANGE_EQ(ranges, expected); |
| 166 } |
| 167 ranges.AddExtent(ExtentForRange(100000, 0)); |
| 168 { |
| 169 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, |
| 170 600, 50, 700, 50, 800, 50, 900, 50}; |
| 171 EXPECT_RANGE_EQ(ranges, expected); |
| 172 } |
| 173 ranges.SubtractExtent(ExtentForRange(3, 0)); |
| 174 { |
| 175 uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, |
| 176 600, 50, 700, 50, 800, 50, 900, 50}; |
| 177 EXPECT_RANGE_EQ(ranges, expected); |
| 178 } |
| 179 } |
| 180 |
| 181 TEST(ExtentRangesTest, MultipleRanges) { |
| 182 ExtentRanges ranges_a, ranges_b; |
| 183 ranges_a.AddBlock(0); |
| 184 ranges_b.AddBlock(4); |
| 185 ranges_b.AddBlock(3); |
| 186 { |
| 187 uint64_t expected[] = {3, 2}; |
| 188 EXPECT_RANGE_EQ(ranges_b, expected); |
| 189 } |
| 190 ranges_a.AddRanges(ranges_b); |
| 191 { |
| 192 uint64_t expected[] = {0, 1, 3, 2}; |
| 193 EXPECT_RANGE_EQ(ranges_a, expected); |
| 194 } |
| 195 ranges_a.SubtractRanges(ranges_b); |
| 196 { |
| 197 uint64_t expected[] = {0, 1}; |
| 198 EXPECT_RANGE_EQ(ranges_a, expected); |
| 199 } |
| 200 { |
| 201 uint64_t expected[] = {3, 2}; |
| 202 EXPECT_RANGE_EQ(ranges_b, expected); |
| 203 } |
| 204 } |
| 205 |
| 206 TEST(ExtentRangesTest, GetExtentsForBlockCountTest) { |
| 207 ExtentRanges ranges; |
| 208 ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30))); |
| 209 { |
| 210 vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0); |
| 211 EXPECT_TRUE(zero_extents.empty()); |
| 212 } |
| 213 ::google::protobuf::RepeatedPtrField<Extent> rep_field; |
| 214 *rep_field.Add() = ExtentForRange(30, 40); |
| 215 ranges.AddRepeatedExtents(rep_field); |
| 216 ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10))); |
| 217 *rep_field.Mutable(0) = ExtentForRange(50, 10); |
| 218 ranges.SubtractRepeatedExtents(rep_field); |
| 219 EXPECT_EQ(40, ranges.blocks()); |
| 220 |
| 221 for (int i = 0; i < 2; i++) { |
| 222 vector<Extent> expected(2); |
| 223 expected[0] = ExtentForRange(10, 10); |
| 224 expected[1] = ExtentForRange(30, i == 0 ? 10 : 20); |
| 225 vector<Extent> actual = |
| 226 ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks()); |
| 227 EXPECT_EQ(expected.size(), actual.size()); |
| 228 for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) { |
| 229 EXPECT_EQ(expected[j].start_block(), actual[j].start_block()) |
| 230 << "j = " << j; |
| 231 EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks()) |
| 232 << "j = " << j; |
| 233 } |
| 234 } |
| 235 } |
| 236 |
| 237 } // namespace chromeos_update_engine |
OLD | NEW |