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 <algorithm> 20 #include <set> 21 #include <utility> 22 #include <vector> 23 24 #include <base/logging.h> 25 26 #include "update_engine/common/utils.h" 27 #include "update_engine/payload_consumer/payload_constants.h" 28 #include "update_engine/payload_generator/extent_utils.h" 29 30 using std::set; 31 using std::vector; 32 33 namespace chromeos_update_engine { 34 35 bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) { 36 if (a.start_block() == b.start_block()) 37 return true; 38 if (a.start_block() == kSparseHole || b.start_block() == kSparseHole) 39 return false; 40 if (a.start_block() < b.start_block()) { 41 return a.start_block() + a.num_blocks() >= b.start_block(); 42 } else { 43 return b.start_block() + b.num_blocks() >= a.start_block(); 44 } 45 } 46 47 bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) { 48 if (a.start_block() == b.start_block()) 49 return true; 50 if (a.start_block() == kSparseHole || b.start_block() == kSparseHole) 51 return false; 52 if (a.start_block() < b.start_block()) { 53 return a.start_block() + a.num_blocks() > b.start_block(); 54 } else { 55 return b.start_block() + b.num_blocks() > a.start_block(); 56 } 57 } 58 59 void ExtentRanges::AddBlock(uint64_t block) { 60 AddExtent(ExtentForRange(block, 1)); 61 } 62 63 void ExtentRanges::SubtractBlock(uint64_t block) { 64 SubtractExtent(ExtentForRange(block, 1)); 65 } 66 67 namespace { 68 69 Extent UnionOverlappingExtents(const Extent& first, const Extent& second) { 70 CHECK_NE(kSparseHole, first.start_block()); 71 CHECK_NE(kSparseHole, second.start_block()); 72 uint64_t start = std::min(first.start_block(), second.start_block()); 73 uint64_t end = std::max(first.start_block() + first.num_blocks(), 74 second.start_block() + second.num_blocks()); 75 return ExtentForRange(start, end - start); 76 } 77 78 } // namespace 79 80 void ExtentRanges::AddExtent(Extent extent) { 81 if (extent.start_block() == kSparseHole || extent.num_blocks() == 0) 82 return; 83 84 ExtentSet::iterator begin_del = extent_set_.end(); 85 ExtentSet::iterator end_del = extent_set_.end(); 86 uint64_t del_blocks = 0; 87 for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end(); 88 it != e; ++it) { 89 if (ExtentsOverlapOrTouch(*it, extent)) { 90 end_del = it; 91 ++end_del; 92 del_blocks += it->num_blocks(); 93 if (begin_del == extent_set_.end()) 94 begin_del = it; 95 96 extent = UnionOverlappingExtents(extent, *it); 97 } 98 } 99 extent_set_.erase(begin_del, end_del); 100 extent_set_.insert(extent); 101 blocks_ -= del_blocks; 102 blocks_ += extent.num_blocks(); 103 } 104 105 namespace { 106 // Returns base - subtractee (set subtraction). 107 ExtentRanges::ExtentSet SubtractOverlappingExtents(const Extent& base, 108 const Extent& subtractee) { 109 ExtentRanges::ExtentSet ret; 110 if (subtractee.start_block() > base.start_block()) { 111 ret.insert(ExtentForRange(base.start_block(), 112 subtractee.start_block() - base.start_block())); 113 } 114 uint64_t base_end = base.start_block() + base.num_blocks(); 115 uint64_t subtractee_end = subtractee.start_block() + subtractee.num_blocks(); 116 if (base_end > subtractee_end) { 117 ret.insert(ExtentForRange(subtractee_end, base_end - subtractee_end)); 118 } 119 return ret; 120 } 121 } // namespace 122 123 void ExtentRanges::SubtractExtent(const Extent& extent) { 124 if (extent.start_block() == kSparseHole || extent.num_blocks() == 0) 125 return; 126 127 ExtentSet::iterator begin_del = extent_set_.end(); 128 ExtentSet::iterator end_del = extent_set_.end(); 129 uint64_t del_blocks = 0; 130 ExtentSet new_extents; 131 for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end(); 132 it != e; ++it) { 133 if (!ExtentsOverlap(*it, extent)) 134 continue; 135 136 if (begin_del == extent_set_.end()) 137 begin_del = it; 138 end_del = it; 139 ++end_del; 140 141 del_blocks += it->num_blocks(); 142 143 ExtentSet subtraction = SubtractOverlappingExtents(*it, extent); 144 for (ExtentSet::iterator jt = subtraction.begin(), je = subtraction.end(); 145 jt != je; ++jt) { 146 new_extents.insert(*jt); 147 del_blocks -= jt->num_blocks(); 148 } 149 } 150 extent_set_.erase(begin_del, end_del); 151 extent_set_.insert(new_extents.begin(), new_extents.end()); 152 blocks_ -= del_blocks; 153 } 154 155 void ExtentRanges::AddRanges(const ExtentRanges& ranges) { 156 for (ExtentSet::const_iterator it = ranges.extent_set_.begin(), 157 e = ranges.extent_set_.end(); it != e; ++it) { 158 AddExtent(*it); 159 } 160 } 161 162 void ExtentRanges::SubtractRanges(const ExtentRanges& ranges) { 163 for (ExtentSet::const_iterator it = ranges.extent_set_.begin(), 164 e = ranges.extent_set_.end(); it != e; ++it) { 165 SubtractExtent(*it); 166 } 167 } 168 169 void ExtentRanges::AddExtents(const vector<Extent>& extents) { 170 for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); 171 it != e; ++it) { 172 AddExtent(*it); 173 } 174 } 175 176 void ExtentRanges::SubtractExtents(const vector<Extent>& extents) { 177 for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); 178 it != e; ++it) { 179 SubtractExtent(*it); 180 } 181 } 182 183 void ExtentRanges::AddRepeatedExtents( 184 const ::google::protobuf::RepeatedPtrField<Extent> &exts) { 185 for (int i = 0, e = exts.size(); i != e; ++i) { 186 AddExtent(exts.Get(i)); 187 } 188 } 189 190 void ExtentRanges::SubtractRepeatedExtents( 191 const ::google::protobuf::RepeatedPtrField<Extent> &exts) { 192 for (int i = 0, e = exts.size(); i != e; ++i) { 193 SubtractExtent(exts.Get(i)); 194 } 195 } 196 197 bool ExtentRanges::ContainsBlock(uint64_t block) const { 198 auto lower = extent_set_.lower_bound(ExtentForRange(block, 1)); 199 // The block could be on the extent before the one in |lower|. 200 if (lower != extent_set_.begin()) 201 lower--; 202 // Any extent starting at block+1 or later is not interesting, so this is the 203 // upper limit. 204 auto upper = extent_set_.lower_bound(ExtentForRange(block + 1, 0)); 205 for (auto iter = lower; iter != upper; ++iter) { 206 if (iter->start_block() <= block && 207 block < iter->start_block() + iter->num_blocks()) { 208 return true; 209 } 210 } 211 return false; 212 } 213 214 void ExtentRanges::Dump() const { 215 LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_; 216 for (ExtentSet::const_iterator it = extent_set_.begin(), 217 e = extent_set_.end(); 218 it != e; ++it) { 219 LOG(INFO) << "{" << it->start_block() << ", " << it->num_blocks() << "}"; 220 } 221 } 222 223 Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks) { 224 Extent ret; 225 ret.set_start_block(start_block); 226 ret.set_num_blocks(num_blocks); 227 return ret; 228 } 229 230 vector<Extent> ExtentRanges::GetExtentsForBlockCount( 231 uint64_t count) const { 232 vector<Extent> out; 233 if (count == 0) 234 return out; 235 uint64_t out_blocks = 0; 236 CHECK(count <= blocks_); 237 for (ExtentSet::const_iterator it = extent_set_.begin(), 238 e = extent_set_.end(); 239 it != e; ++it) { 240 const uint64_t blocks_needed = count - out_blocks; 241 const Extent& extent = *it; 242 out.push_back(extent); 243 out_blocks += extent.num_blocks(); 244 if (extent.num_blocks() < blocks_needed) 245 continue; 246 if (extent.num_blocks() == blocks_needed) 247 break; 248 // If we get here, we just added the last extent needed, but it's too big 249 out_blocks -= extent.num_blocks(); 250 out_blocks += blocks_needed; 251 out.back().set_num_blocks(blocks_needed); 252 break; 253 } 254 CHECK(out_blocks == utils::BlocksInExtents(out)); 255 return out; 256 } 257 258 vector<Extent> FilterExtentRanges(const vector<Extent>& extents, 259 const ExtentRanges& ranges) { 260 vector<Extent> result; 261 const ExtentRanges::ExtentSet& extent_set = ranges.extent_set(); 262 for (Extent extent : extents) { 263 // The extents are sorted by the start_block. We want to iterate all the 264 // Extents in the ExtentSet possibly overlapping the current |extent|. This 265 // is achieved by looking from the extent whose start_block is *lower* than 266 // the extent.start_block() up to the greatest extent whose start_block is 267 // lower than extent.start_block() + extent.num_blocks(). 268 auto lower = extent_set.lower_bound(extent); 269 // We need to decrement the lower_bound to look at the extent that could 270 // overlap the beginning of the current |extent|. 271 if (lower != extent_set.begin()) 272 lower--; 273 auto upper = extent_set.lower_bound( 274 ExtentForRange(extent.start_block() + extent.num_blocks(), 0)); 275 for (auto iter = lower; iter != upper; ++iter) { 276 if (!ExtentRanges::ExtentsOverlap(extent, *iter)) 277 continue; 278 if (iter->start_block() <= extent.start_block()) { 279 // We need to cut blocks from the beginning of the |extent|. 280 uint64_t cut_blocks = iter->start_block() + iter->num_blocks() - 281 extent.start_block(); 282 if (cut_blocks >= extent.num_blocks()) { 283 extent.set_num_blocks(0); 284 break; 285 } 286 extent = ExtentForRange(extent.start_block() + cut_blocks, 287 extent.num_blocks() - cut_blocks); 288 } else { 289 // We need to cut blocks on the middle of the extent, possible up to the 290 // end of it. 291 result.push_back( 292 ExtentForRange(extent.start_block(), 293 iter->start_block() - extent.start_block())); 294 uint64_t new_start = iter->start_block() + iter->num_blocks(); 295 uint64_t old_end = extent.start_block() + extent.num_blocks(); 296 if (new_start >= old_end) { 297 extent.set_num_blocks(0); 298 break; 299 } 300 extent = ExtentForRange(new_start, old_end - new_start); 301 } 302 } 303 if (extent.num_blocks() > 0) 304 result.push_back(extent); 305 } 306 return result; 307 } 308 309 } // namespace chromeos_update_engine 310