1 //
2 // Copyright (C) 2015 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 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
19
20 #include <limits>
21 #include <string>
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/update_metadata.pb.h"
29
30 // Utility functions for manipulating Extents and lists of blocks.
31
32 namespace chromeos_update_engine {
33 struct ExtentLess {
operatorExtentLess34 constexpr bool operator()(const Extent& x, const Extent& y) const {
35 if (x.start_block() == y.start_block()) {
36 return x.num_blocks() < y.num_blocks();
37 }
38 return x.start_block() < y.start_block();
39 }
40 };
41
42 // |block| must either be the next block in the last extent or a block
43 // in the next extent. This function will not handle inserting block
44 // into an arbitrary place in the extents.
45 void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
46
47 // Takes a collection (vector or RepeatedPtrField) of Extent and
48 // returns a vector of the blocks referenced, in order.
49 template <typename T>
ExpandExtents(const T & extents)50 std::vector<uint64_t> ExpandExtents(const T& extents) {
51 std::vector<uint64_t> ret;
52 for (const auto& extent : extents) {
53 if (extent.start_block() == kSparseHole) {
54 ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
55 } else {
56 for (uint64_t block = extent.start_block();
57 block < (extent.start_block() + extent.num_blocks());
58 block++) {
59 ret.push_back(block);
60 }
61 }
62 }
63 return ret;
64 }
65
66 // Stores all Extents in 'extents' into 'out'.
67 void StoreExtents(const std::vector<Extent>& extents,
68 google::protobuf::RepeatedPtrField<Extent>* out);
69
70 // Stores all extents in |extents| into |out_vector|.
71 void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
72 std::vector<Extent>* out_vector);
73
74 // Returns a string representing all extents in |extents|.
75 std::string ExtentsToString(const std::vector<Extent>& extents);
76 std::string ExtentsToString(
77 const google::protobuf::RepeatedPtrField<Extent>& extents);
78
79 // Takes a pointer to extents |extents| and extents |extents_to_add|, and
80 // merges them by adding |extents_to_add| to |extents| and normalizing.
81 void ExtendExtents(
82 google::protobuf::RepeatedPtrField<Extent>* extents,
83 const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
84
85 // Takes a vector of extents and normalizes those extents. Expects the extents
86 // to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
87 // then |extents| will be changed to [(1, 7), (10, 2)].
88 void NormalizeExtents(std::vector<Extent>* extents);
89
90 // Return a subsequence of the list of blocks passed. Both the passed list of
91 // blocks |extents| and the return value are expressed as a list of Extent, not
92 // blocks. The returned list skips the first |block_offset| blocks from the
93 // |extents| and cotains |block_count| blocks (or less if |extents| is shorter).
94 std::vector<Extent> ExtentsSublist(const std::vector<Extent>& extents,
95 uint64_t block_offset,
96 uint64_t block_count);
97
98 bool operator==(const Extent& a, const Extent& b) noexcept;
99
100 bool operator!=(const Extent& a, const Extent& b) noexcept;
101
102 // TODO(zhangkelvin) This is ugly. Rewrite using C++20's coroutine once
103 // that's available. Unfortunately with C++17 this is the best I could do.
104
105 // An iterator that takes a sequence of extents, and iterate over blocks
106 // inside this sequence of extents.
107 // Example usage:
108
109 // BlockIterator it1{src_extents};
110 // while(!it1.is_end()) {
111 // auto block = *it1;
112 // Do stuff with |block|
113 // }
114 struct BlockIterator {
BlockIteratorBlockIterator115 explicit BlockIterator(
116 const google::protobuf::RepeatedPtrField<Extent>& extents)
117 : extents_(extents) {}
118
119 BlockIterator& operator++() {
120 CHECK_LT(cur_extent_, extents_.size());
121 block_offset_++;
122 if (block_offset_ >= extents_[cur_extent_].num_blocks()) {
123 cur_extent_++;
124 block_offset_ = 0;
125 }
126 return *this;
127 }
128
is_endBlockIterator129 [[nodiscard]] bool is_end() { return cur_extent_ >= extents_.size(); }
130 [[nodiscard]] uint64_t operator*() {
131 return extents_[cur_extent_].start_block() + block_offset_;
132 }
133
134 const google::protobuf::RepeatedPtrField<Extent>& extents_;
135 int cur_extent_ = 0;
136 size_t block_offset_ = 0;
137 };
138
139 std::ostream& operator<<(std::ostream& out, const Extent& extent);
140 std::ostream& operator<<(std::ostream& out, const std::vector<Extent>& extent);
141 std::ostream& operator<<(std::ostream& out, const std::set<Extent>& extents);
142
143 std::ostream& operator<<(std::ostream& out,
144 const std::set<Extent, ExtentLess>& extents);
145 std::ostream& operator<<(
146 std::ostream& out,
147 Range<std::set<Extent, ExtentLess>::const_iterator> range);
148
149 std::ostream& operator<<(
150 std::ostream& out,
151 const google::protobuf::RepeatedPtrField<Extent>& extent);
152
153 template <typename Container>
GetNthBlock(const Container & extents,const size_t n)154 size_t GetNthBlock(const Container& extents, const size_t n) {
155 size_t cur_block_count = 0;
156 for (const auto& extent : extents) {
157 if (n - cur_block_count < extent.num_blocks()) {
158 return extent.start_block() + (n - cur_block_count);
159 }
160 cur_block_count += extent.num_blocks();
161 }
162 return std::numeric_limits<size_t>::max();
163 }
164
ExtentContains(const Extent & extent,size_t block)165 constexpr bool ExtentContains(const Extent& extent, size_t block) {
166 return extent.start_block() <= block &&
167 block < extent.start_block() + extent.num_blocks();
168 }
169
170 // return true iff |big| extent contains |small| extent
ExtentContains(const Extent & big,const Extent & small)171 constexpr bool ExtentContains(const Extent& big, const Extent& small) {
172 return big.start_block() <= small.start_block() &&
173 small.start_block() + small.num_blocks() <=
174 big.start_block() + big.num_blocks();
175 }
176
177 template <typename T>
Dedup(T * container)178 constexpr void Dedup(T* container) {
179 std::sort(container->begin(), container->end());
180 container->erase(std::unique(container->begin(), container->end()),
181 container->end());
182 }
183
184 } // namespace chromeos_update_engine
185
186 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
187