extent_ranges.cc revision d8b67f49d7f8ae291cd4fa901b2d3767137704e7 
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
30using std::set;
31using std::vector;
32
33namespace chromeos_update_engine {
34
35bool 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
47bool 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
59void ExtentRanges::AddBlock(uint64_t block) {
60  AddExtent(ExtentForRange(block, 1));
61}
62
63void ExtentRanges::SubtractBlock(uint64_t block) {
64  SubtractExtent(ExtentForRange(block, 1));
65}
66
67namespace {
68
69Extent 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
80void 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
105namespace {
106// Returns base - subtractee (set subtraction).
107ExtentRanges::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
123void 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
155void 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
162void 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
169void 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
176void 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
183void 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
190void 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
197bool 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
214void 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
223Extent 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
230vector<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
258vector<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