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