blob: 851db8a223269e453a12f83d44340aa42ffbbf77 [file] [log] [blame]
Alex Deymoaea4c1c2015-08-19 20:24:43 -07001//
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//
Alex Deymo5c6c6552015-06-03 19:06:50 +020016
17#include "update_engine/payload_generator/extent_utils.h"
18
Sen Jiang55c4f9b2016-02-10 11:26:20 -080019#include <inttypes.h>
20
Alex Deymo5c6c6552015-06-03 19:06:50 +020021#include <string>
Alex Deymo5c6c6552015-06-03 19:06:50 +020022#include <vector>
23
24#include <base/logging.h>
25#include <base/macros.h>
Sen Jiang55c4f9b2016-02-10 11:26:20 -080026#include <base/strings/stringprintf.h>
Alex Deymo5c6c6552015-06-03 19:06:50 +020027
Alex Deymo39910dc2015-11-09 17:04:30 -080028#include "update_engine/payload_consumer/payload_constants.h"
Alex Deymo1beda782015-06-07 23:01:25 +020029#include "update_engine/payload_generator/extent_ranges.h"
Alex Deymo5c6c6552015-06-03 19:06:50 +020030
31using std::string;
32using std::vector;
33
34namespace chromeos_update_engine {
35
36void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
37 // First try to extend the last extent in |extents|, if any.
38 if (!extents->empty()) {
39 Extent& extent = extents->back();
Amin Hassani232f8f92019-01-14 16:15:31 -080040 uint64_t next_block = extent.start_block() == kSparseHole
41 ? kSparseHole
42 : extent.start_block() + extent.num_blocks();
Alex Deymo5c6c6552015-06-03 19:06:50 +020043 if (next_block == block) {
44 extent.set_num_blocks(extent.num_blocks() + 1);
45 return;
46 }
47 }
48 // If unable to extend the last extent, append a new single-block extent.
49 Extent new_extent;
50 new_extent.set_start_block(block);
51 new_extent.set_num_blocks(1);
52 extents->push_back(new_extent);
53}
54
Alex Deymo14158572015-06-13 03:37:08 -070055void ExtendExtents(
56 google::protobuf::RepeatedPtrField<Extent>* extents,
57 const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
58 vector<Extent> extents_vector;
59 vector<Extent> extents_to_add_vector;
60 ExtentsToVector(*extents, &extents_vector);
61 ExtentsToVector(extents_to_add, &extents_to_add_vector);
62 extents_vector.insert(extents_vector.end(),
63 extents_to_add_vector.begin(),
64 extents_to_add_vector.end());
65 NormalizeExtents(&extents_vector);
66 extents->Clear();
67 StoreExtents(extents_vector, extents);
68}
69
70// Stores all Extents in 'extents' into 'out'.
71void StoreExtents(const vector<Extent>& extents,
72 google::protobuf::RepeatedPtrField<Extent>* out) {
73 for (const Extent& extent : extents) {
74 Extent* new_extent = out->Add();
75 *new_extent = extent;
76 }
77}
78
79// Stores all extents in |extents| into |out_vector|.
80void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
81 vector<Extent>* out_vector) {
82 out_vector->clear();
83 for (int i = 0; i < extents.size(); i++) {
84 out_vector->push_back(extents.Get(i));
85 }
86}
87
Kelvin Zhang40d96662021-02-24 14:21:29 -050088template <typename Container>
89string ExtentsToStringTemplate(const Container& extents) {
Sen Jiang55c4f9b2016-02-10 11:26:20 -080090 string ext_str;
91 for (const Extent& e : extents)
Tamas Berghammer9d66d762016-07-15 14:19:04 +010092 ext_str += base::StringPrintf("[%" PRIu64 ", %" PRIu64 "] ",
93 static_cast<uint64_t>(e.start_block()),
94 static_cast<uint64_t>(e.num_blocks()));
Sen Jiang55c4f9b2016-02-10 11:26:20 -080095 return ext_str;
96}
97
Kelvin Zhang40d96662021-02-24 14:21:29 -050098std::string ExtentsToString(const std::vector<Extent>& extents) {
99 return ExtentsToStringTemplate(extents);
100}
101
102std::string ExtentsToString(
103 const google::protobuf::RepeatedPtrField<Extent>& extents) {
104 return ExtentsToStringTemplate(extents);
105}
106
Alex Deymo52490e72015-06-04 14:53:44 +0200107void 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,
Amin Hassani232f8f92019-01-14 16:15:31 -0800128 uint64_t block_offset,
129 uint64_t block_count) {
Alex Deymo52490e72015-06-04 14:53:44 +0200130 vector<Extent> result;
131 uint64_t scanned_blocks = 0;
132 if (block_count == 0)
133 return result;
134 uint64_t end_block_offset = block_offset + block_count;
135 for (const Extent& extent : extents) {
136 // The loop invariant is that if |extents| has enough blocks, there's
137 // still some extent to add to |result|. This implies that at the beginning
138 // of the loop scanned_blocks < block_offset + block_count.
139 if (scanned_blocks + extent.num_blocks() > block_offset) {
140 // This case implies that |extent| has some overlapping with the requested
141 // subsequence.
142 uint64_t new_start = extent.start_block();
143 uint64_t new_num_blocks = extent.num_blocks();
144 if (scanned_blocks + new_num_blocks > end_block_offset) {
145 // Cut the end part of the extent.
146 new_num_blocks = end_block_offset - scanned_blocks;
147 }
148 if (block_offset > scanned_blocks) {
149 // Cut the begin part of the extent.
150 new_num_blocks -= block_offset - scanned_blocks;
151 new_start += block_offset - scanned_blocks;
152 }
153 result.push_back(ExtentForRange(new_start, new_num_blocks));
154 }
155 scanned_blocks += extent.num_blocks();
156 if (scanned_blocks >= end_block_offset)
157 break;
158 }
159 return result;
160}
161
Kelvin Zhang4bb49202021-07-08 21:39:05 -0400162bool operator==(const Extent& a, const Extent& b) noexcept {
Alex Deymo5c6c6552015-06-03 19:06:50 +0200163 return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
164}
165
Kelvin Zhang4bb49202021-07-08 21:39:05 -0400166bool operator!=(const Extent& a, const Extent& b) noexcept {
167 return !(a == b);
168}
169
Kelvin Zhangeb8703b2020-12-10 14:17:21 -0500170std::ostream& operator<<(std::ostream& out, const Extent& extent) {
Kelvin Zhange532af32024-01-10 15:29:02 -0800171 out << "(" << extent.start_block() << " - " << extent.num_blocks() << ")";
Kelvin Zhangeb8703b2020-12-10 14:17:21 -0500172 return out;
173}
174
Kelvin Zhang4bb49202021-07-08 21:39:05 -0400175template <typename T>
176std::ostream& PrintExtents(std::ostream& out, const T& extents) {
177 if (extents.begin() == extents.end()) {
178 out << "{}";
179 return out;
180 }
181 out << "{";
182 auto begin = extents.begin();
183 out << *begin;
184 for (const auto& ext : Range{++begin, extents.end()}) {
185 out << ", " << ext;
186 }
187 out << "}";
188 return out;
189}
190
191std::ostream& operator<<(std::ostream& out,
192 const std::vector<Extent>& extents) {
193 return PrintExtents(out, extents);
194}
195std::ostream& operator<<(
196 std::ostream& out,
197 const google::protobuf::RepeatedPtrField<Extent>& extents) {
198 return PrintExtents(out, extents);
199}
200
Kelvin Zhange532af32024-01-10 15:29:02 -0800201std::ostream& operator<<(std::ostream& out, const std::set<Extent>& extents) {
202 return PrintExtents(out, extents);
203}
204
205std::ostream& operator<<(std::ostream& out,
206 const std::set<Extent, ExtentLess>& extents) {
207 return PrintExtents(out, extents);
208}
209
210std::ostream& operator<<(
211 std::ostream& out,
212 Range<std::set<Extent, ExtentLess>::const_iterator> range) {
213 return PrintExtents(out, range);
214}
215
Alex Deymo5c6c6552015-06-03 19:06:50 +0200216} // namespace chromeos_update_engine