Alex Deymo | 5c6c655 | 2015-06-03 19:06:50 +0200 | [diff] [blame] | 1 | // Copyright (c) 2009 The Chromium OS Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #include "update_engine/payload_generator/extent_utils.h" |
| 6 | |
| 7 | #include <string> |
| 8 | #include <utility> |
| 9 | #include <vector> |
| 10 | |
| 11 | #include <base/logging.h> |
| 12 | #include <base/macros.h> |
| 13 | |
| 14 | #include "update_engine/payload_constants.h" |
| 15 | #include "update_engine/payload_generator/annotated_operation.h" |
Alex Deymo | 1beda78 | 2015-06-07 23:01:25 +0200 | [diff] [blame] | 16 | #include "update_engine/payload_generator/extent_ranges.h" |
Alex Deymo | 5c6c655 | 2015-06-03 19:06:50 +0200 | [diff] [blame] | 17 | |
| 18 | using std::string; |
| 19 | using std::vector; |
| 20 | |
| 21 | namespace chromeos_update_engine { |
| 22 | |
| 23 | void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) { |
| 24 | // First try to extend the last extent in |extents|, if any. |
| 25 | if (!extents->empty()) { |
| 26 | Extent& extent = extents->back(); |
| 27 | uint64_t next_block = extent.start_block() == kSparseHole ? |
| 28 | kSparseHole : extent.start_block() + extent.num_blocks(); |
| 29 | if (next_block == block) { |
| 30 | extent.set_num_blocks(extent.num_blocks() + 1); |
| 31 | return; |
| 32 | } |
| 33 | } |
| 34 | // If unable to extend the last extent, append a new single-block extent. |
| 35 | Extent new_extent; |
| 36 | new_extent.set_start_block(block); |
| 37 | new_extent.set_num_blocks(1); |
| 38 | extents->push_back(new_extent); |
| 39 | } |
| 40 | |
| 41 | Extent GetElement(const vector<Extent>& collection, size_t index) { |
| 42 | return collection[index]; |
| 43 | } |
Alex Deymo | 1415857 | 2015-06-13 03:37:08 -0700 | [diff] [blame^] | 44 | |
Alex Deymo | 5c6c655 | 2015-06-03 19:06:50 +0200 | [diff] [blame] | 45 | Extent GetElement( |
| 46 | const google::protobuf::RepeatedPtrField<Extent>& collection, |
| 47 | size_t index) { |
| 48 | return collection.Get(index); |
| 49 | } |
| 50 | |
Alex Deymo | 1415857 | 2015-06-13 03:37:08 -0700 | [diff] [blame^] | 51 | void ExtendExtents( |
| 52 | google::protobuf::RepeatedPtrField<Extent>* extents, |
| 53 | const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) { |
| 54 | vector<Extent> extents_vector; |
| 55 | vector<Extent> extents_to_add_vector; |
| 56 | ExtentsToVector(*extents, &extents_vector); |
| 57 | ExtentsToVector(extents_to_add, &extents_to_add_vector); |
| 58 | extents_vector.insert(extents_vector.end(), |
| 59 | extents_to_add_vector.begin(), |
| 60 | extents_to_add_vector.end()); |
| 61 | NormalizeExtents(&extents_vector); |
| 62 | extents->Clear(); |
| 63 | StoreExtents(extents_vector, extents); |
| 64 | } |
| 65 | |
| 66 | // Stores all Extents in 'extents' into 'out'. |
| 67 | void StoreExtents(const vector<Extent>& extents, |
| 68 | google::protobuf::RepeatedPtrField<Extent>* out) { |
| 69 | for (const Extent& extent : extents) { |
| 70 | Extent* new_extent = out->Add(); |
| 71 | *new_extent = extent; |
| 72 | } |
| 73 | } |
| 74 | |
| 75 | // Stores all extents in |extents| into |out_vector|. |
| 76 | void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents, |
| 77 | vector<Extent>* out_vector) { |
| 78 | out_vector->clear(); |
| 79 | for (int i = 0; i < extents.size(); i++) { |
| 80 | out_vector->push_back(extents.Get(i)); |
| 81 | } |
| 82 | } |
| 83 | |
Alex Deymo | 52490e7 | 2015-06-04 14:53:44 +0200 | [diff] [blame] | 84 | void NormalizeExtents(vector<Extent>* extents) { |
| 85 | vector<Extent> new_extents; |
| 86 | for (const Extent& curr_ext : *extents) { |
| 87 | if (new_extents.empty()) { |
| 88 | new_extents.push_back(curr_ext); |
| 89 | continue; |
| 90 | } |
| 91 | Extent& last_ext = new_extents.back(); |
| 92 | if (last_ext.start_block() + last_ext.num_blocks() == |
| 93 | curr_ext.start_block()) { |
| 94 | // If the extents are touching, we want to combine them. |
| 95 | last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks()); |
| 96 | } else { |
| 97 | // Otherwise just include the extent as is. |
| 98 | new_extents.push_back(curr_ext); |
| 99 | } |
| 100 | } |
| 101 | *extents = new_extents; |
| 102 | } |
| 103 | |
| 104 | vector<Extent> ExtentsSublist(const vector<Extent>& extents, |
| 105 | uint64_t block_offset, uint64_t block_count) { |
| 106 | vector<Extent> result; |
| 107 | uint64_t scanned_blocks = 0; |
| 108 | if (block_count == 0) |
| 109 | return result; |
| 110 | uint64_t end_block_offset = block_offset + block_count; |
| 111 | for (const Extent& extent : extents) { |
| 112 | // The loop invariant is that if |extents| has enough blocks, there's |
| 113 | // still some extent to add to |result|. This implies that at the beginning |
| 114 | // of the loop scanned_blocks < block_offset + block_count. |
| 115 | if (scanned_blocks + extent.num_blocks() > block_offset) { |
| 116 | // This case implies that |extent| has some overlapping with the requested |
| 117 | // subsequence. |
| 118 | uint64_t new_start = extent.start_block(); |
| 119 | uint64_t new_num_blocks = extent.num_blocks(); |
| 120 | if (scanned_blocks + new_num_blocks > end_block_offset) { |
| 121 | // Cut the end part of the extent. |
| 122 | new_num_blocks = end_block_offset - scanned_blocks; |
| 123 | } |
| 124 | if (block_offset > scanned_blocks) { |
| 125 | // Cut the begin part of the extent. |
| 126 | new_num_blocks -= block_offset - scanned_blocks; |
| 127 | new_start += block_offset - scanned_blocks; |
| 128 | } |
| 129 | result.push_back(ExtentForRange(new_start, new_num_blocks)); |
| 130 | } |
| 131 | scanned_blocks += extent.num_blocks(); |
| 132 | if (scanned_blocks >= end_block_offset) |
| 133 | break; |
| 134 | } |
| 135 | return result; |
| 136 | } |
| 137 | |
Alex Deymo | 5c6c655 | 2015-06-03 19:06:50 +0200 | [diff] [blame] | 138 | bool operator==(const Extent& a, const Extent& b) { |
| 139 | return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks(); |
| 140 | } |
| 141 | |
| 142 | } // namespace chromeos_update_engine |