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#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 181beda780333ce51d7872603b70712772eb2383fbAlex Deymo#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 195fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <map> 215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <set> 225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <vector> 235fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2405735a1879a553153458aae0a25fa5d42e3e408fBen Chan#include <base/macros.h> 255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include "update_engine/update_metadata.pb.h" 275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// An ExtentRanges object represents an unordered collection of extents (and 2994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// therefore blocks). Such an object may be modified by adding or subtracting 3094817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// blocks (think: set addition or set subtraction). Note that ExtentRanges 3194817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// ignores sparse hole extents mostly to avoid confusion between extending a 3294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// sparse hole range vs. set addition but also to ensure that the delta 3394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov// generator doesn't use sparse holes as scratch space. 345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 355fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace chromeos_update_engine { 365fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 375fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesstruct ExtentLess { 385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes bool operator()(const Extent& x, const Extent& y) const { 395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return x.start_block() < y.start_block(); 405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes}; 425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesExtent ExtentForRange(uint64_t start_block, uint64_t num_blocks); 445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesclass ExtentRanges { 465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes public: 475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes typedef std::set<Extent, ExtentLess> ExtentSet; 485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 495fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges() : blocks_(0) {} 505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void AddBlock(uint64_t block); 515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void SubtractBlock(uint64_t block); 525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void AddExtent(Extent extent); 535fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void SubtractExtent(const Extent& extent); 545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void AddExtents(const std::vector<Extent>& extents); 555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void SubtractExtents(const std::vector<Extent>& extents); 565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void AddRepeatedExtents( 575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ::google::protobuf::RepeatedPtrField<Extent> &exts); 585fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void SubtractRepeatedExtents( 595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ::google::protobuf::RepeatedPtrField<Extent> &exts); 605fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void AddRanges(const ExtentRanges& ranges); 615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void SubtractRanges(const ExtentRanges& ranges); 625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 63f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo // Returns whether the block |block| is in this ExtentRange. 64f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo bool ContainsBlock(uint64_t block) const; 65f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 665fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b); 675fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes static bool ExtentsOverlap(const Extent& a, const Extent& b); 685fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 695fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // Dumps contents to the log file. Useful for debugging. 705fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes void Dump() const; 7194817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 725fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t blocks() const { return blocks_; } 735fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ExtentSet& extent_set() const { return extent_set_; } 745fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 755fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // Returns an ordered vector of extents for |count| blocks, 765fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // using extents in extent_set_. The returned extents are not 775fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // removed from extent_set_. |count| must be less than or equal to 785fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // the number of blocks in this extent set. 795fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const; 805fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 815fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes private: 825fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet extent_set_; 835fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t blocks_; 845fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes}; 855fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 86a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo// Filters out from the passed list of extents |extents| all the blocks in the 87a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo// ExtentRanges set. Note that the order of the blocks in |extents| is preserved 88a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo// omitting blocks present in the ExtentRanges |ranges|. 89a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymostd::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents, 90a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo const ExtentRanges& ranges); 91a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo 925fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} // namespace chromeos_update_engine 935fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 941beda780333ce51d7872603b70712772eb2383fbAlex Deymo#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 95