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 void ExtendExtents( 57 google::protobuf::RepeatedPtrField<Extent>* extents, 58 const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) { 59 vector<Extent> extents_vector; 60 vector<Extent> extents_to_add_vector; 61 ExtentsToVector(*extents, &extents_vector); 62 ExtentsToVector(extents_to_add, &extents_to_add_vector); 63 extents_vector.insert(extents_vector.end(), 64 extents_to_add_vector.begin(), 65 extents_to_add_vector.end()); 66 NormalizeExtents(&extents_vector); 67 extents->Clear(); 68 StoreExtents(extents_vector, extents); 69 } 70 71 // Stores all Extents in 'extents' into 'out'. 72 void StoreExtents(const vector<Extent>& extents, 73 google::protobuf::RepeatedPtrField<Extent>* out) { 74 for (const Extent& extent : extents) { 75 Extent* new_extent = out->Add(); 76 *new_extent = extent; 77 } 78 } 79 80 // Stores all extents in |extents| into |out_vector|. 81 void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents, 82 vector<Extent>* out_vector) { 83 out_vector->clear(); 84 for (int i = 0; i < extents.size(); i++) { 85 out_vector->push_back(extents.Get(i)); 86 } 87 } 88 89 string ExtentsToString(const vector<Extent>& extents) { 90 string ext_str; 91 for (const Extent& e : extents) 92 ext_str += base::StringPrintf("[%" PRIu64 ", %" PRIu64 "] ", 93 static_cast<uint64_t>(e.start_block()), 94 static_cast<uint64_t>(e.num_blocks())); 95 return ext_str; 96 } 97 98 void NormalizeExtents(vector<Extent>* extents) { 99 vector<Extent> new_extents; 100 for (const Extent& curr_ext : *extents) { 101 if (new_extents.empty()) { 102 new_extents.push_back(curr_ext); 103 continue; 104 } 105 Extent& last_ext = new_extents.back(); 106 if (last_ext.start_block() + last_ext.num_blocks() == 107 curr_ext.start_block()) { 108 // If the extents are touching, we want to combine them. 109 last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks()); 110 } else { 111 // Otherwise just include the extent as is. 112 new_extents.push_back(curr_ext); 113 } 114 } 115 *extents = new_extents; 116 } 117 118 vector<Extent> ExtentsSublist(const vector<Extent>& extents, 119 uint64_t block_offset, uint64_t block_count) { 120 vector<Extent> result; 121 uint64_t scanned_blocks = 0; 122 if (block_count == 0) 123 return result; 124 uint64_t end_block_offset = block_offset + block_count; 125 for (const Extent& extent : extents) { 126 // The loop invariant is that if |extents| has enough blocks, there's 127 // still some extent to add to |result|. This implies that at the beginning 128 // of the loop scanned_blocks < block_offset + block_count. 129 if (scanned_blocks + extent.num_blocks() > block_offset) { 130 // This case implies that |extent| has some overlapping with the requested 131 // subsequence. 132 uint64_t new_start = extent.start_block(); 133 uint64_t new_num_blocks = extent.num_blocks(); 134 if (scanned_blocks + new_num_blocks > end_block_offset) { 135 // Cut the end part of the extent. 136 new_num_blocks = end_block_offset - scanned_blocks; 137 } 138 if (block_offset > scanned_blocks) { 139 // Cut the begin part of the extent. 140 new_num_blocks -= block_offset - scanned_blocks; 141 new_start += block_offset - scanned_blocks; 142 } 143 result.push_back(ExtentForRange(new_start, new_num_blocks)); 144 } 145 scanned_blocks += extent.num_blocks(); 146 if (scanned_blocks >= end_block_offset) 147 break; 148 } 149 return result; 150 } 151 152 bool operator==(const Extent& a, const Extent& b) { 153 return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks(); 154 } 155 156 } // namespace chromeos_update_engine 157
