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