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