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