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 33 using std::string; 34 using std::vector; 35 36 namespace chromeos_update_engine { 37 38 void 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 56 Extent GetElement(const vector<Extent>& collection, size_t index) { 57 return collection[index]; 58 } 59 60 Extent GetElement( 61 const google::protobuf::RepeatedPtrField<Extent>& collection, 62 size_t index) { 63 return collection.Get(index); 64 } 65 66 void 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'. 82 void 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|. 91 void 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 99 string 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 107 void 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 127 vector<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 161 bool 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
