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