extent_utils.cc revision 55c4f9ba7f5c59e3345f2c1869464433ffa8dc2b 
1//
2// Copyright (C) 2009 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_utils.h"
18
19#include <inttypes.h>
20
21#include <string>
22#include <utility>
23#include <vector>
24
25#include <base/logging.h>
26#include <base/macros.h>
27#include <base/strings/stringprintf.h>
28
29#include "update_engine/payload_consumer/payload_constants.h"
30#include "update_engine/payload_generator/annotated_operation.h"
31#include "update_engine/payload_generator/extent_ranges.h"
32
33using std::string;
34using std::vector;
35
36namespace chromeos_update_engine {
37
38void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
39  // First try to extend the last extent in |extents|, if any.
40  if (!extents->empty()) {
41    Extent& extent = extents->back();
42    uint64_t next_block = extent.start_block() == kSparseHole ?
43        kSparseHole : extent.start_block() + extent.num_blocks();
44    if (next_block == block) {
45      extent.set_num_blocks(extent.num_blocks() + 1);
46      return;
47    }
48  }
49  // If unable to extend the last extent, append a new single-block extent.
50  Extent new_extent;
51  new_extent.set_start_block(block);
52  new_extent.set_num_blocks(1);
53  extents->push_back(new_extent);
54}
55
56Extent GetElement(const vector<Extent>& collection, size_t index) {
57  return collection[index];
58}
59
60Extent GetElement(
61    const google::protobuf::RepeatedPtrField<Extent>& collection,
62    size_t index) {
63  return collection.Get(index);
64}
65
66void ExtendExtents(
67    google::protobuf::RepeatedPtrField<Extent>* extents,
68    const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
69  vector<Extent> extents_vector;
70  vector<Extent> extents_to_add_vector;
71  ExtentsToVector(*extents, &extents_vector);
72  ExtentsToVector(extents_to_add, &extents_to_add_vector);
73  extents_vector.insert(extents_vector.end(),
74                        extents_to_add_vector.begin(),
75                        extents_to_add_vector.end());
76  NormalizeExtents(&extents_vector);
77  extents->Clear();
78  StoreExtents(extents_vector, extents);
79}
80
81// Stores all Extents in 'extents' into 'out'.
82void StoreExtents(const vector<Extent>& extents,
83                  google::protobuf::RepeatedPtrField<Extent>* out) {
84  for (const Extent& extent : extents) {
85    Extent* new_extent = out->Add();
86    *new_extent = extent;
87  }
88}
89
90// Stores all extents in |extents| into |out_vector|.
91void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
92                     vector<Extent>* out_vector) {
93  out_vector->clear();
94  for (int i = 0; i < extents.size(); i++) {
95    out_vector->push_back(extents.Get(i));
96  }
97}
98
99string ExtentsToString(const vector<Extent>& extents) {
100  string ext_str;
101  for (const Extent& e : extents)
102    ext_str += base::StringPrintf(
103        "[%" PRIu64 ", %" PRIu64 "] ", e.start_block(), e.num_blocks());
104  return ext_str;
105}
106
107void NormalizeExtents(vector<Extent>* extents) {
108  vector<Extent> new_extents;
109  for (const Extent& curr_ext : *extents) {
110    if (new_extents.empty()) {
111      new_extents.push_back(curr_ext);
112      continue;
113    }
114    Extent& last_ext = new_extents.back();
115    if (last_ext.start_block() + last_ext.num_blocks() ==
116        curr_ext.start_block()) {
117      // If the extents are touching, we want to combine them.
118      last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
119    } else {
120      // Otherwise just include the extent as is.
121      new_extents.push_back(curr_ext);
122    }
123  }
124  *extents = new_extents;
125}
126
127vector<Extent> ExtentsSublist(const vector<Extent>& extents,
128                              uint64_t block_offset, uint64_t block_count) {
129  vector<Extent> result;
130  uint64_t scanned_blocks = 0;
131  if (block_count == 0)
132    return result;
133  uint64_t end_block_offset = block_offset + block_count;
134  for (const Extent& extent : extents) {
135    // The loop invariant is that if |extents| has enough blocks, there's
136    // still some extent to add to |result|. This implies that at the beginning
137    // of the loop scanned_blocks < block_offset + block_count.
138    if (scanned_blocks + extent.num_blocks() > block_offset) {
139      // This case implies that |extent| has some overlapping with the requested
140      // subsequence.
141      uint64_t new_start = extent.start_block();
142      uint64_t new_num_blocks = extent.num_blocks();
143      if (scanned_blocks + new_num_blocks > end_block_offset) {
144        // Cut the end part of the extent.
145        new_num_blocks = end_block_offset - scanned_blocks;
146      }
147      if (block_offset > scanned_blocks) {
148        // Cut the begin part of the extent.
149        new_num_blocks -= block_offset - scanned_blocks;
150        new_start += block_offset - scanned_blocks;
151      }
152      result.push_back(ExtentForRange(new_start, new_num_blocks));
153    }
154    scanned_blocks += extent.num_blocks();
155    if (scanned_blocks >= end_block_offset)
156      break;
157  }
158  return result;
159}
160
161bool operator==(const Extent& a, const Extent& b) {
162  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
163}
164
165}  // namespace chromeos_update_engine
166