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, 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 71 void 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 91 void 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 111 void 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 125 TEST(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 140 TEST(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 215 TEST(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 240 TEST(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(40U, 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 271 TEST(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 290 TEST(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 306 TEST(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 333 TEST(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
