1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2010 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 171beda780333ce51d7872603b70712772eb2383fbAlex Deymo#include "update_engine/payload_generator/extent_ranges.h" 185fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 19d2779df63aaad8b65fc5d4badee7dbc9bed7f2b6Alex Vakulenko#include <algorithm> 205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <set> 215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <utility> 225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <vector> 235fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 245fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes#include <base/logging.h> 255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2639910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/payload_consumer/payload_constants.h" 27161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 285fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesusing std::set; 295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesusing std::vector; 305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 315fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace chromeos_update_engine { 325fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 335fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesbool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) { 345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (a.start_block() == b.start_block()) 355fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return true; 3694817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov if (a.start_block() == kSparseHole || b.start_block() == kSparseHole) 3794817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov return false; 385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (a.start_block() < b.start_block()) { 395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return a.start_block() + a.num_blocks() >= b.start_block(); 405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } else { 415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return b.start_block() + b.num_blocks() >= a.start_block(); 425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesbool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) { 465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (a.start_block() == b.start_block()) 475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return true; 4894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov if (a.start_block() == kSparseHole || b.start_block() == kSparseHole) 4994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov return false; 505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (a.start_block() < b.start_block()) { 515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return a.start_block() + a.num_blocks() > b.start_block(); 525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } else { 535fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return b.start_block() + b.num_blocks() > a.start_block(); 545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::AddBlock(uint64_t block) { 585fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes AddExtent(ExtentForRange(block, 1)); 595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 605fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::SubtractBlock(uint64_t block) { 625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes SubtractExtent(ExtentForRange(block, 1)); 635fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 645fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 655fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace { 665fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 675fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesExtent UnionOverlappingExtents(const Extent& first, const Extent& second) { 6894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov CHECK_NE(kSparseHole, first.start_block()); 6994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov CHECK_NE(kSparseHole, second.start_block()); 70f329b933db41d26644a97afef928eb1b319d6d99Alex Deymo uint64_t start = std::min(first.start_block(), second.start_block()); 71f329b933db41d26644a97afef928eb1b319d6d99Alex Deymo uint64_t end = std::max(first.start_block() + first.num_blocks(), 72f329b933db41d26644a97afef928eb1b319d6d99Alex Deymo second.start_block() + second.num_blocks()); 735fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return ExtentForRange(start, end - start); 745fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 7594817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 76d2779df63aaad8b65fc5d4badee7dbc9bed7f2b6Alex Vakulenko} // namespace 775fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 785fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::AddExtent(Extent extent) { 7994817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov if (extent.start_block() == kSparseHole || extent.num_blocks() == 0) 805fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return; 815fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 825fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet::iterator begin_del = extent_set_.end(); 835fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet::iterator end_del = extent_set_.end(); 845fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t del_blocks = 0; 855fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end(); 865fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 875fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (ExtentsOverlapOrTouch(*it, extent)) { 885fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes end_del = it; 895fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ++end_del; 905fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes del_blocks += it->num_blocks(); 915fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (begin_del == extent_set_.end()) 925fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes begin_del = it; 935fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 945fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes extent = UnionOverlappingExtents(extent, *it); 955fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 965fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 975fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes extent_set_.erase(begin_del, end_del); 985fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes extent_set_.insert(extent); 995fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes blocks_ -= del_blocks; 1005fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes blocks_ += extent.num_blocks(); 1015fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1025fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1035fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesnamespace { 1045fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes// Returns base - subtractee (set subtraction). 1055fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesExtentRanges::ExtentSet SubtractOverlappingExtents(const Extent& base, 1065fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const Extent& subtractee) { 1075fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentRanges::ExtentSet ret; 1085fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (subtractee.start_block() > base.start_block()) { 1095fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ret.insert(ExtentForRange(base.start_block(), 1105fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes subtractee.start_block() - base.start_block())); 1115fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1125fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t base_end = base.start_block() + base.num_blocks(); 1135fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t subtractee_end = subtractee.start_block() + subtractee.num_blocks(); 1145fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (base_end > subtractee_end) { 1155fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ret.insert(ExtentForRange(subtractee_end, base_end - subtractee_end)); 1165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1175fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return ret; 1185fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 119d2779df63aaad8b65fc5d4badee7dbc9bed7f2b6Alex Vakulenko} // namespace 1205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::SubtractExtent(const Extent& extent) { 12294817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov if (extent.start_block() == kSparseHole || extent.num_blocks() == 0) 1235fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return; 1245fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet::iterator begin_del = extent_set_.end(); 1265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet::iterator end_del = extent_set_.end(); 1275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t del_blocks = 0; 1285fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet new_extents; 1295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end(); 1305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 1315fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (!ExtentsOverlap(*it, extent)) 1325fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes continue; 13394817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 1345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (begin_del == extent_set_.end()) 1355fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes begin_del = it; 1365fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes end_del = it; 1375fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ++end_del; 13894817cb77d41d4be746a9f4f59ce0e9a0574218aDarin Petkov 1395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes del_blocks += it->num_blocks(); 1405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ExtentSet subtraction = SubtractOverlappingExtents(*it, extent); 1425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::iterator jt = subtraction.begin(), je = subtraction.end(); 1435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes jt != je; ++jt) { 1445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes new_extents.insert(*jt); 1455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes del_blocks -= jt->num_blocks(); 1465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes extent_set_.erase(begin_del, end_del); 1495fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes extent_set_.insert(new_extents.begin(), new_extents.end()); 1505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes blocks_ -= del_blocks; 1515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1535fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::AddRanges(const ExtentRanges& ranges) { 1545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::const_iterator it = ranges.extent_set_.begin(), 1555fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes e = ranges.extent_set_.end(); it != e; ++it) { 1565fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes AddExtent(*it); 1575fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1585fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1595fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1605fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::SubtractRanges(const ExtentRanges& ranges) { 1615fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::const_iterator it = ranges.extent_set_.begin(), 1625fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes e = ranges.extent_set_.end(); it != e; ++it) { 1635fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes SubtractExtent(*it); 1645fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1655fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1665fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1675fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::AddExtents(const vector<Extent>& extents) { 1685fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); 1695fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 1705fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes AddExtent(*it); 1715fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1725fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1735fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1745fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::SubtractExtents(const vector<Extent>& extents) { 1755fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); 1765fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 1775fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes SubtractExtent(*it); 1785fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1795fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1805fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1815fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::AddRepeatedExtents( 1825fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ::google::protobuf::RepeatedPtrField<Extent> &exts) { 1835fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (int i = 0, e = exts.size(); i != e; ++i) { 1845fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes AddExtent(exts.Get(i)); 1855fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1865fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1875fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 1885fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::SubtractRepeatedExtents( 1895fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const ::google::protobuf::RepeatedPtrField<Extent> &exts) { 1905fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (int i = 0, e = exts.size(); i != e; ++i) { 1915fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes SubtractExtent(exts.Get(i)); 1925fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 1935fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 1945fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 195f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymobool ExtentRanges::ContainsBlock(uint64_t block) const { 196f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo auto lower = extent_set_.lower_bound(ExtentForRange(block, 1)); 197f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo // The block could be on the extent before the one in |lower|. 198f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo if (lower != extent_set_.begin()) 199f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo lower--; 200f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo // Any extent starting at block+1 or later is not interesting, so this is the 201f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo // upper limit. 202f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo auto upper = extent_set_.lower_bound(ExtentForRange(block + 1, 0)); 203f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo for (auto iter = lower; iter != upper; ++iter) { 204f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo if (iter->start_block() <= block && 205f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo block < iter->start_block() + iter->num_blocks()) { 206f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo return true; 207f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo } 208f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo } 209f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo return false; 210f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo} 211f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 2125fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyesvoid ExtentRanges::Dump() const { 2135fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_; 2145fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::const_iterator it = extent_set_.begin(), 2155fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes e = extent_set_.end(); 2165fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 2175fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes LOG(INFO) << "{" << it->start_block() << ", " << it->num_blocks() << "}"; 2185fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2195fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 2205fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 2215fdae4a66db266219449d43ffc565888ee08dcadAndrew de los ReyesExtent ExtentForRange(uint64_t start_block, uint64_t num_blocks) { 2225fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes Extent ret; 2235fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ret.set_start_block(start_block); 2245fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes ret.set_num_blocks(num_blocks); 2255fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return ret; 2265fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 2275fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 228f329b933db41d26644a97afef928eb1b319d6d99Alex Deymovector<Extent> ExtentRanges::GetExtentsForBlockCount( 2295fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t count) const { 2305fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes vector<Extent> out; 2315fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (count == 0) 2325fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return out; 2335fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes uint64_t out_blocks = 0; 2345fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes CHECK(count <= blocks_); 2355fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes for (ExtentSet::const_iterator it = extent_set_.begin(), 2365fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes e = extent_set_.end(); 2375fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes it != e; ++it) { 2385fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const uint64_t blocks_needed = count - out_blocks; 2395fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes const Extent& extent = *it; 2405fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes out.push_back(extent); 2415fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes out_blocks += extent.num_blocks(); 2425fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (extent.num_blocks() < blocks_needed) 2435fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes continue; 2445fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes if (extent.num_blocks() == blocks_needed) 2455fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes break; 2465fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes // If we get here, we just added the last extent needed, but it's too big 2475fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes out_blocks -= extent.num_blocks(); 2485fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes out_blocks += blocks_needed; 2495fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes out.back().set_num_blocks(blocks_needed); 2505fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes break; 2515fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes } 2525fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes return out; 2535fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} 2545fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes 255f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymovector<Extent> FilterExtentRanges(const vector<Extent>& extents, 256a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo const ExtentRanges& ranges) { 257a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo vector<Extent> result; 258a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo const ExtentRanges::ExtentSet& extent_set = ranges.extent_set(); 259a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo for (Extent extent : extents) { 260a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // The extents are sorted by the start_block. We want to iterate all the 261a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // Extents in the ExtentSet possibly overlapping the current |extent|. This 262a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // is achieved by looking from the extent whose start_block is *lower* than 263a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // the extent.start_block() up to the greatest extent whose start_block is 264a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // lower than extent.start_block() + extent.num_blocks(). 265a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo auto lower = extent_set.lower_bound(extent); 266a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // We need to decrement the lower_bound to look at the extent that could 267a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // overlap the beginning of the current |extent|. 268a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (lower != extent_set.begin()) 269a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo lower--; 270a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo auto upper = extent_set.lower_bound( 271a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(extent.start_block() + extent.num_blocks(), 0)); 272a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo for (auto iter = lower; iter != upper; ++iter) { 273a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (!ExtentRanges::ExtentsOverlap(extent, *iter)) 274a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo continue; 275a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (iter->start_block() <= extent.start_block()) { 276a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // We need to cut blocks from the beginning of the |extent|. 277a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo uint64_t cut_blocks = iter->start_block() + iter->num_blocks() - 278a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent.start_block(); 279a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (cut_blocks >= extent.num_blocks()) { 280a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent.set_num_blocks(0); 281a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo break; 282a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } 283a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent = ExtentForRange(extent.start_block() + cut_blocks, 284a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent.num_blocks() - cut_blocks); 285a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } else { 286a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // We need to cut blocks on the middle of the extent, possible up to the 287a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo // end of it. 288a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo result.push_back( 289a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo ExtentForRange(extent.start_block(), 290a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo iter->start_block() - extent.start_block())); 291a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo uint64_t new_start = iter->start_block() + iter->num_blocks(); 292a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo uint64_t old_end = extent.start_block() + extent.num_blocks(); 293a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (new_start >= old_end) { 294a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent.set_num_blocks(0); 295a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo break; 296a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } 297a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo extent = ExtentForRange(new_start, old_end - new_start); 298a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } 299a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } 300a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo if (extent.num_blocks() > 0) 301a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo result.push_back(extent); 302a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo } 303a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo return result; 304a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo} 305a376a6e9007539531e99d3e879bc72ad1273f72fAlex Deymo 3065fdae4a66db266219449d43ffc565888ee08dcadAndrew de los Reyes} // namespace chromeos_update_engine 307