1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2010 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 171beda780333ce51d7872603b70712772eb2383fbAlex Deymo#include "update_engine/payload_generator/extent_ranges.h" 18aab50e31f0b80ed53a9b8d5dbabcf943974bd32cAlex Deymo 195fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <vector> 205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <gtest/gtest.h> 225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2339910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/common/test_utils.h" 2439910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/payload_consumer/payload_constants.h" 25a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo#include "update_engine/payload_generator/extent_utils.h" 265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesusing std::vector; 285fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace chromeos_update_engine { 305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 315fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesclass ExtentRangesTest : public ::testing::Test {}; 325fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 335fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace { 345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExpectRangeEq(const ExtentRanges& ranges, 3594817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov const uint64_t* expected, 365fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes size_t sz, 375fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes int line) { 385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t blocks = 0; 395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (size_t i = 1; i < sz; i += 2) { 405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes blocks += expected[i]; 415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line; 435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ExtentRanges::ExtentSet& result = ranges.extent_set(); 455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges::ExtentSet::const_iterator it = result.begin(); 465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (size_t i = 0; i < sz; i += 2) { 475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(it == result.end()) << "line: " << line; 485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(expected[i], it->start_block()) << "line: " << line; 495fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line; 505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ++it; 515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 535fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#define EXPECT_RANGE_EQ(ranges, var) \ 555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes do { \ 565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \ 575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } while (0) 585fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num, 605fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t b_start, uint64_t b_num) { 615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, 625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 635fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 645fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 655fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, 665fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 675fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 685fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 695fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 705fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 715fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num, 725fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t b_start, uint64_t b_num) { 735fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, 745fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 755fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 765fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 775fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, 785fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 795fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 805fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 815fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, 825fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 835fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 845fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 855fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, 865fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 875fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 885fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 895fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 905fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 915fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExpectRangesOverlap(uint64_t a_start, uint64_t a_num, 925fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t b_start, uint64_t b_num) { 935fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, 945fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 955fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 965fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 975fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, 985fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 995fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 1005fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 1015fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start, 1025fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 1035fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 1045fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 1055fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start, 1065fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 1075fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 1085fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 1095fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1105fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1115fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num, 1125fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t b_start, uint64_t b_num) { 1135fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start, 1145fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num), 1155fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(b_start, 1165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num))); 1175fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start, 1185fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes b_num), 1195fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentForRange(a_start, 1205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes a_num))); 1215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 123d2779df63aaad8b65fc5d4badee7dbc9bed7f2b6Alex Vakulenko} // namespace 1245fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesTEST(ExtentRangesTest, ExtentsOverlapTest) { 1265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangesOverlapOrTouch(10, 20, 30, 10); 1275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangesOverlap(10, 20, 25, 10); 1285fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10); 1295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectFalseRangesOverlap(10, 20, 30, 10); 1305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangesOverlap(12, 4, 12, 3); 13194817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 13294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3); 13394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3); 13494817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3); 13594817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3); 13694817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3); 13794817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ExpectFalseRangesOverlap(10, 2, kSparseHole, 3); 1385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesTEST(ExtentRangesTest, SimpleTest) { 1415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges ranges; 1425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 14394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = {}; 1445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // Can't use arraysize() on 0-length arrays: 1455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangeEq(ranges, expected, 0, __LINE__); 1465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractBlock(2); 1485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 14994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = {}; 1505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // Can't use arraysize() on 0-length arrays: 1515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExpectRangeEq(ranges, expected, 0, __LINE__); 1525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 15394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 1545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddBlock(0); 1555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.Dump(); 1565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddBlock(1); 1575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddBlock(3); 15894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 1595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 16094817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = {0, 2, 3, 1}; 1615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 1625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1635fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddBlock(2); 1645fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 16594817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = {0, 4}; 16694817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov EXPECT_RANGE_EQ(ranges, expected); 16794817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ranges.AddBlock(kSparseHole); 16894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov EXPECT_RANGE_EQ(ranges, expected); 16994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov ranges.SubtractBlock(kSparseHole); 1705fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 1715fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1725fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractBlock(2); 1735fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 17494817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = {0, 2, 3, 1}; 1755fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 1765fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1775fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1785fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (uint64_t i = 100; i < 1000; i += 100) { 1795fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddExtent(ExtentForRange(i, 50)); 1805fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1815fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 18294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = { 18394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50, 18494817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 500, 50, 600, 50, 700, 50, 800, 50, 900, 50 18594817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov }; 1865fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 1875fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1885fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1895fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractExtent(ExtentForRange(210, 410 - 210)); 1905fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 19194817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = { 19294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, 19394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 600, 50, 700, 50, 800, 50, 900, 50 19494817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov }; 1955fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 1965fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1975fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddExtent(ExtentForRange(100000, 0)); 1985fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 19994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = { 20094817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, 20194817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 600, 50, 700, 50, 800, 50, 900, 50 20294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov }; 2035fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 2045fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2055fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractExtent(ExtentForRange(3, 0)); 2065fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 20794817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov static const uint64_t expected[] = { 20894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50, 20994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 600, 50, 700, 50, 800, 50, 900, 50 21094817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov }; 2115fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges, expected); 2125fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2135fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 2145fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2155fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesTEST(ExtentRangesTest, MultipleRanges) { 2165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges ranges_a, ranges_b; 2175fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges_a.AddBlock(0); 2185fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges_b.AddBlock(4); 2195fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges_b.AddBlock(3); 2205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 2215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t expected[] = {3, 2}; 2225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges_b, expected); 2235fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2245fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges_a.AddRanges(ranges_b); 2255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 2265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t expected[] = {0, 1, 3, 2}; 2275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges_a, expected); 2285fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges_a.SubtractRanges(ranges_b); 2305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 2315fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t expected[] = {0, 1}; 2325fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges_a, expected); 2335fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 2355fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t expected[] = {3, 2}; 2365fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_RANGE_EQ(ranges_b, expected); 2375fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 2395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesTEST(ExtentRangesTest, GetExtentsForBlockCountTest) { 2415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges ranges; 2425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30))); 2435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes { 2445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0); 2455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_TRUE(zero_extents.empty()); 2465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ::google::protobuf::RepeatedPtrField<Extent> rep_field; 2485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes *rep_field.Add() = ExtentForRange(30, 40); 2495fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.AddRepeatedExtents(rep_field); 2505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10))); 2515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes *rep_field.Mutable(0) = ExtentForRange(50, 10); 2525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.SubtractRepeatedExtents(rep_field); 25380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(40U, ranges.blocks()); 2545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (int i = 0; i < 2; i++) { 2565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes vector<Extent> expected(2); 2575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes expected[0] = ExtentForRange(10, 10); 2585fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes expected[1] = ExtentForRange(30, i == 0 ? 10 : 20); 2595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes vector<Extent> actual = 2605fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks()); 2615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(expected.size(), actual.size()); 2625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) { 2635fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(expected[j].start_block(), actual[j].start_block()) 2645fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes << "j = " << j; 2655fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks()) 2665fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes << "j = " << j; 2675fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2685fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2695fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 270f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 271f0061358b5f741baeeb9177b838b289d2ce318f3Alex DeymoTEST(ExtentRangesTest, ContainsBlockTest) { 272f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo ExtentRanges ranges; 273f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_FALSE(ranges.ContainsBlock(123)); 274f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 275f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo ranges.AddExtent(ExtentForRange(10, 10)); 276f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo ranges.AddExtent(ExtentForRange(100, 1)); 277f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 278f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_FALSE(ranges.ContainsBlock(9)); 279f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_TRUE(ranges.ContainsBlock(10)); 280f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_TRUE(ranges.ContainsBlock(15)); 281f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_TRUE(ranges.ContainsBlock(19)); 282f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_FALSE(ranges.ContainsBlock(20)); 283f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 284f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo // Test for an extent with just the block we are requesting. 285f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_FALSE(ranges.ContainsBlock(99)); 286f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_TRUE(ranges.ContainsBlock(100)); 287f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo EXPECT_FALSE(ranges.ContainsBlock(101)); 288f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo} 2895fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 290a376a6e9007539531e99d3e879bc72ad1273f72fAlex DeymoTEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) { 291a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentRanges ranges; 292a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo EXPECT_EQ(vector<Extent>(), 293a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo FilterExtentRanges(vector<Extent>(), ranges)); 294a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo EXPECT_EQ( 295a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo vector<Extent>{ ExtentForRange(50, 10) }, 296a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo FilterExtentRanges(vector<Extent>{ ExtentForRange(50, 10) }, ranges)); 297a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // Check that the empty Extents are ignored. 298a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo EXPECT_EQ( 299a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo (vector<Extent>{ ExtentForRange(10, 10), ExtentForRange(20, 10) }), 300a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo FilterExtentRanges(vector<Extent>{ 301a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(10, 10), 302a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(3, 0), 303a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(20, 10) }, ranges)); 304a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo} 305a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo 306a376a6e9007539531e99d3e879bc72ad1273f72fAlex DeymoTEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) { 307a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // Two overlaping extents, with three ranges to remove. 308a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo vector<Extent> extents { 309a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(10, 100), 310a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(30, 100) }; 311a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentRanges ranges; 312a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // This overlaps the beginning of the second extent. 313a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(28, 3)); 314a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(50, 10)); 315a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(70, 10)); 316a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // This overlaps the end of the second extent. 317a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(108, 6)); 318a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo EXPECT_EQ( 319a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo (vector<Extent>{ 320a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // For the first extent: 321a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(10, 18), 322a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(31, 19), 323a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(60, 10), 324a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(80, 28), 325a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // For the second extent: 326a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(31, 19), 327a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(60, 10), 328a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(80, 28), 329a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(114, 16)}), 330a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo FilterExtentRanges(extents, ranges)); 331a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo} 332a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo 333a376a6e9007539531e99d3e879bc72ad1273f72fAlex DeymoTEST(ExtentRangesTest, FilterExtentRangesOvelapping) { 334a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentRanges ranges; 335a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(10, 3)); 336a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges.AddExtent(ExtentForRange(20, 5)); 337a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // Requested extent overlaps with one of the ranges. 338a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo EXPECT_EQ(vector<Extent>(), 339a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo FilterExtentRanges(vector<Extent>{ 340a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(10, 1), 341a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(22, 1) }, 342a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ranges)); 343a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo} 344a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo 3455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} // namespace chromeos_update_engine 346