| // |
| // Copyright (C) 2009 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| #include "update_engine/payload_generator/extent_utils.h" |
| |
| #include <string> |
| #include <utility> |
| #include <vector> |
| |
| #include <base/logging.h> |
| #include <base/macros.h> |
| |
| #include "update_engine/payload_consumer/payload_constants.h" |
| #include "update_engine/payload_generator/annotated_operation.h" |
| #include "update_engine/payload_generator/extent_ranges.h" |
| |
| using std::string; |
| using std::vector; |
| |
| namespace chromeos_update_engine { |
| |
| void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) { |
| // First try to extend the last extent in |extents|, if any. |
| if (!extents->empty()) { |
| Extent& extent = extents->back(); |
| uint64_t next_block = extent.start_block() == kSparseHole ? |
| kSparseHole : extent.start_block() + extent.num_blocks(); |
| if (next_block == block) { |
| extent.set_num_blocks(extent.num_blocks() + 1); |
| return; |
| } |
| } |
| // If unable to extend the last extent, append a new single-block extent. |
| Extent new_extent; |
| new_extent.set_start_block(block); |
| new_extent.set_num_blocks(1); |
| extents->push_back(new_extent); |
| } |
| |
| Extent GetElement(const vector<Extent>& collection, size_t index) { |
| return collection[index]; |
| } |
| |
| Extent GetElement( |
| const google::protobuf::RepeatedPtrField<Extent>& collection, |
| size_t index) { |
| return collection.Get(index); |
| } |
| |
| void ExtendExtents( |
| google::protobuf::RepeatedPtrField<Extent>* extents, |
| const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) { |
| vector<Extent> extents_vector; |
| vector<Extent> extents_to_add_vector; |
| ExtentsToVector(*extents, &extents_vector); |
| ExtentsToVector(extents_to_add, &extents_to_add_vector); |
| extents_vector.insert(extents_vector.end(), |
| extents_to_add_vector.begin(), |
| extents_to_add_vector.end()); |
| NormalizeExtents(&extents_vector); |
| extents->Clear(); |
| StoreExtents(extents_vector, extents); |
| } |
| |
| // Stores all Extents in 'extents' into 'out'. |
| void StoreExtents(const vector<Extent>& extents, |
| google::protobuf::RepeatedPtrField<Extent>* out) { |
| for (const Extent& extent : extents) { |
| Extent* new_extent = out->Add(); |
| *new_extent = extent; |
| } |
| } |
| |
| // Stores all extents in |extents| into |out_vector|. |
| void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents, |
| vector<Extent>* out_vector) { |
| out_vector->clear(); |
| for (int i = 0; i < extents.size(); i++) { |
| out_vector->push_back(extents.Get(i)); |
| } |
| } |
| |
| void NormalizeExtents(vector<Extent>* extents) { |
| vector<Extent> new_extents; |
| for (const Extent& curr_ext : *extents) { |
| if (new_extents.empty()) { |
| new_extents.push_back(curr_ext); |
| continue; |
| } |
| Extent& last_ext = new_extents.back(); |
| if (last_ext.start_block() + last_ext.num_blocks() == |
| curr_ext.start_block()) { |
| // If the extents are touching, we want to combine them. |
| last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks()); |
| } else { |
| // Otherwise just include the extent as is. |
| new_extents.push_back(curr_ext); |
| } |
| } |
| *extents = new_extents; |
| } |
| |
| vector<Extent> ExtentsSublist(const vector<Extent>& extents, |
| uint64_t block_offset, uint64_t block_count) { |
| vector<Extent> result; |
| uint64_t scanned_blocks = 0; |
| if (block_count == 0) |
| return result; |
| uint64_t end_block_offset = block_offset + block_count; |
| for (const Extent& extent : extents) { |
| // The loop invariant is that if |extents| has enough blocks, there's |
| // still some extent to add to |result|. This implies that at the beginning |
| // of the loop scanned_blocks < block_offset + block_count. |
| if (scanned_blocks + extent.num_blocks() > block_offset) { |
| // This case implies that |extent| has some overlapping with the requested |
| // subsequence. |
| uint64_t new_start = extent.start_block(); |
| uint64_t new_num_blocks = extent.num_blocks(); |
| if (scanned_blocks + new_num_blocks > end_block_offset) { |
| // Cut the end part of the extent. |
| new_num_blocks = end_block_offset - scanned_blocks; |
| } |
| if (block_offset > scanned_blocks) { |
| // Cut the begin part of the extent. |
| new_num_blocks -= block_offset - scanned_blocks; |
| new_start += block_offset - scanned_blocks; |
| } |
| result.push_back(ExtentForRange(new_start, new_num_blocks)); |
| } |
| scanned_blocks += extent.num_blocks(); |
| if (scanned_blocks >= end_block_offset) |
| break; |
| } |
| return result; |
| } |
| |
| bool operator==(const Extent& a, const Extent& b) { |
| return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks(); |
| } |
| |
| } // namespace chromeos_update_engine |