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