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("[%" PRIu64 ", %" PRIu64 "] ", 103 static_cast<uint64_t>(e.start_block()), 104 static_cast<uint64_t>(e.num_blocks())); 105 return ext_str; 106 } 107 108 void NormalizeExtents(vector<Extent>* extents) { 109 vector<Extent> new_extents; 110 for (const Extent& curr_ext : *extents) { 111 if (new_extents.empty()) { 112 new_extents.push_back(curr_ext); 113 continue; 114 } 115 Extent& last_ext = new_extents.back(); 116 if (last_ext.start_block() + last_ext.num_blocks() == 117 curr_ext.start_block()) { 118 // If the extents are touching, we want to combine them. 119 last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks()); 120 } else { 121 // Otherwise just include the extent as is. 122 new_extents.push_back(curr_ext); 123 } 124 } 125 *extents = new_extents; 126 } 127 128 vector<Extent> ExtentsSublist(const vector<Extent>& extents, 129 uint64_t block_offset, uint64_t block_count) { 130 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 162 bool operator==(const Extent& a, const Extent& b) { 163 return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks(); 164 } 165 166 } // namespace chromeos_update_engine 167
