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 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 19 20 #include <map> 21 #include <set> 22 #include <vector> 23 24 #include <base/macros.h> 25 26 #include "update_engine/common/utils.h" 27 #include "update_engine/update_metadata.pb.h" 28 29 // An ExtentRanges object represents an unordered collection of extents (and 30 // therefore blocks). Such an object may be modified by adding or subtracting 31 // blocks (think: set addition or set subtraction). Note that ExtentRanges 32 // ignores sparse hole extents mostly to avoid confusion between extending a 33 // sparse hole range vs. set addition but also to ensure that the delta 34 // generator doesn't use sparse holes as scratch space. 35 36 namespace chromeos_update_engine { 37 38 struct ExtentLess { operatorExtentLess39 bool operator()(const Extent& x, const Extent& y) const { 40 if (x.start_block() == y.start_block()) { 41 return x.num_blocks() < y.num_blocks(); 42 } 43 return x.start_block() < y.start_block(); 44 } 45 }; 46 47 Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks); 48 Extent ExtentForBytes(uint64_t block_size, 49 uint64_t start_bytes, 50 uint64_t size_bytes); 51 52 class ExtentRanges { 53 public: 54 typedef std::set<Extent, ExtentLess> ExtentSet; 55 56 ExtentRanges() = default; 57 // When |merge_touching_extents| is set to false, extents that are only 58 // touching but not overlapping won't be merged. This slightly decreases 59 // space/time efficiency, but should not impact correctness. 60 // Only intended usecase is for VABC XOR. 61 // E.g. [5-9] and [10-14] will be merged iff |merge_touching_extents| is true ExtentRanges(bool merge_touching_extents)62 explicit ExtentRanges(bool merge_touching_extents) 63 : merge_touching_extents_(merge_touching_extents) {} 64 void AddBlock(uint64_t block); 65 void SubtractBlock(uint64_t block); 66 void AddExtent(Extent extent); 67 void SubtractExtent(const Extent& extent); 68 void AddExtents(const std::vector<Extent>& extents); 69 void SubtractExtents(const std::vector<Extent>& extents); 70 void AddRepeatedExtents( 71 const ::google::protobuf::RepeatedPtrField<Extent>& exts); 72 void SubtractRepeatedExtents( 73 const ::google::protobuf::RepeatedPtrField<Extent>& exts); 74 void AddRanges(const ExtentRanges& ranges); 75 void SubtractRanges(const ExtentRanges& ranges); 76 77 // Returns true if the input extent overlaps with the current ExtentRanges. 78 bool OverlapsWithExtent(const Extent& extent) const; 79 80 // Returns whether the block |block| is in this ExtentRange. 81 bool ContainsBlock(uint64_t block) const; 82 83 static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b); 84 static bool ExtentsOverlap(const Extent& a, const Extent& b); 85 86 // Dumps contents to the log file. Useful for debugging. 87 void Dump() const; 88 blocks()89 uint64_t blocks() const { return blocks_; } extent_set()90 const ExtentSet& extent_set() const { return extent_set_; } 91 92 // Returns an ordered vector of extents for |count| blocks, 93 // using extents in extent_set_. The returned extents are not 94 // removed from extent_set_. |count| must be less than or equal to 95 // the number of blocks in this extent set. 96 std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const; 97 98 // Compute the intersection between this ExtentRange and the |extent| 99 // parameter. Return results in a vector. If there's no intersection, an empty 100 // vector is returned. 101 std::vector<Extent> GetIntersectingExtents(const Extent& extent) const; 102 103 // Get a range of extents that possibly intersect with |extent|. (Returned 104 // extents do not necessarily intersect!). It is perfectly acceptable to just 105 // return all extents in this set, though more efficient solution using binary 106 // search is preferred. 107 Range<ExtentSet::const_iterator> GetCandidateRange( 108 const Extent& extent) const; 109 110 private: 111 ExtentSet extent_set_; 112 uint64_t blocks_ = 0; 113 bool merge_touching_extents_ = true; 114 }; 115 116 // Filters out from the passed list of extents |extents| all the blocks in the 117 // ExtentRanges set. Note that the order of the blocks in |extents| is preserved 118 // omitting blocks present in the ExtentRanges |ranges|. 119 std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents, 120 const ExtentRanges& ranges); 121 122 Extent GetOverlapExtent(const Extent& extent1, const Extent& extent2); 123 124 } // namespace chromeos_update_engine 125 126 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 127