blob: f538c5eb8dab4a3b2b6221f610f4b65ef21e254d [file] [log] [blame]
Alex Deymoaea4c1c2015-08-19 20:24:43 -07001//
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//
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070016
Alex Deymo1beda782015-06-07 23:01:25 +020017#include "update_engine/payload_generator/extent_ranges.h"
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070018
Alex Vakulenkod2779df2014-06-16 13:19:00 -070019#include <algorithm>
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070020#include <set>
21#include <utility>
22#include <vector>
23
24#include <base/logging.h>
25
Alex Deymo161c4a12014-05-16 15:56:21 -070026#include "update_engine/payload_constants.h"
27
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070028using std::set;
29using std::vector;
30
31namespace chromeos_update_engine {
32
33bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) {
34 if (a.start_block() == b.start_block())
35 return true;
Darin Petkov94817cb2013-05-08 14:33:24 +020036 if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
37 return false;
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070038 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
45bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
46 if (a.start_block() == b.start_block())
47 return true;
Darin Petkov94817cb2013-05-08 14:33:24 +020048 if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
49 return false;
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070050 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
57void ExtentRanges::AddBlock(uint64_t block) {
58 AddExtent(ExtentForRange(block, 1));
59}
60
61void ExtentRanges::SubtractBlock(uint64_t block) {
62 SubtractExtent(ExtentForRange(block, 1));
63}
64
65namespace {
66
67Extent UnionOverlappingExtents(const Extent& first, const Extent& second) {
Darin Petkov94817cb2013-05-08 14:33:24 +020068 CHECK_NE(kSparseHole, first.start_block());
69 CHECK_NE(kSparseHole, second.start_block());
Alex Deymof329b932014-10-30 01:37:48 -070070 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());
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070073 return ExtentForRange(start, end - start);
74}
Darin Petkov94817cb2013-05-08 14:33:24 +020075
Alex Vakulenkod2779df2014-06-16 13:19:00 -070076} // namespace
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070077
78void ExtentRanges::AddExtent(Extent extent) {
Darin Petkov94817cb2013-05-08 14:33:24 +020079 if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -070080 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
103namespace {
104// Returns base - subtractee (set subtraction).
105ExtentRanges::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}
Alex Vakulenkod2779df2014-06-16 13:19:00 -0700119} // namespace
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700120
121void ExtentRanges::SubtractExtent(const Extent& extent) {
Darin Petkov94817cb2013-05-08 14:33:24 +0200122 if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700123 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;
Darin Petkov94817cb2013-05-08 14:33:24 +0200133
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700134 if (begin_del == extent_set_.end())
135 begin_del = it;
136 end_del = it;
137 ++end_del;
Darin Petkov94817cb2013-05-08 14:33:24 +0200138
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700139 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
153void 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
160void 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
167void 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
174void 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
181void 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
188void 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
Alex Deymof0061352015-07-01 14:59:15 -0700195bool 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
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700212void 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
221Extent 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
Alex Deymof329b932014-10-30 01:37:48 -0700228vector<Extent> ExtentRanges::GetExtentsForBlockCount(
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700229 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
Alex Deymof0061352015-07-01 14:59:15 -0700255vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
Alex Deymoa376a6e2015-06-05 00:31:34 +0200256 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
Andrew de los Reyes5fdae4a2010-10-05 10:47:42 -0700306} // namespace chromeos_update_engine