ab_generator.cc revision abdc0115548985d8ca3f3f2aeb1283741ce409a6
1// 2// Copyright (C) 2015 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/ab_generator.h" 18 19#include <algorithm> 20 21#include <base/strings/stringprintf.h> 22 23#include "update_engine/delta_performer.h" 24#include "update_engine/payload_generator/annotated_operation.h" 25#include "update_engine/payload_generator/bzip.h" 26#include "update_engine/payload_generator/delta_diff_generator.h" 27#include "update_engine/payload_generator/delta_diff_utils.h" 28#include "update_engine/utils.h" 29 30using std::string; 31using std::vector; 32 33namespace chromeos_update_engine { 34 35bool ABGenerator::GenerateOperations( 36 const PayloadGenerationConfig& config, 37 const PartitionConfig& old_part, 38 const PartitionConfig& new_part, 39 BlobFileWriter* blob_file, 40 vector<AnnotatedOperation>* aops) { 41 TEST_AND_RETURN_FALSE(old_part.name == new_part.name); 42 43 ssize_t hard_chunk_blocks = (config.hard_chunk_size == -1 ? -1 : 44 config.hard_chunk_size / config.block_size); 45 size_t soft_chunk_blocks = config.soft_chunk_size / config.block_size; 46 47 aops->clear(); 48 TEST_AND_RETURN_FALSE(diff_utils::DeltaReadPartition( 49 aops, 50 old_part, 51 new_part, 52 hard_chunk_blocks, 53 soft_chunk_blocks, 54 blob_file, 55 true)); // src_ops_allowed 56 LOG(INFO) << "done reading " << new_part.name; 57 58 TEST_AND_RETURN_FALSE(FragmentOperations(aops, 59 new_part.path, 60 blob_file)); 61 SortOperationsByDestination(aops); 62 63 // Use the soft_chunk_size when merging operations to prevent merging all 64 // the operations into a huge one if there's no hard limit. 65 size_t merge_chunk_blocks = soft_chunk_blocks; 66 if (hard_chunk_blocks != -1 && 67 static_cast<size_t>(hard_chunk_blocks) < soft_chunk_blocks) { 68 merge_chunk_blocks = hard_chunk_blocks; 69 } 70 71 TEST_AND_RETURN_FALSE(MergeOperations(aops, 72 merge_chunk_blocks, 73 new_part.path, 74 blob_file)); 75 return true; 76} 77 78void ABGenerator::SortOperationsByDestination( 79 vector<AnnotatedOperation>* aops) { 80 sort(aops->begin(), aops->end(), diff_utils::CompareAopsByDestination); 81} 82 83bool ABGenerator::FragmentOperations( 84 vector<AnnotatedOperation>* aops, 85 const string& target_part_path, 86 BlobFileWriter* blob_file) { 87 vector<AnnotatedOperation> fragmented_aops; 88 for (const AnnotatedOperation& aop : *aops) { 89 if (aop.op.type() == InstallOperation::SOURCE_COPY) { 90 TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops)); 91 } else if ((aop.op.type() == InstallOperation::REPLACE) || 92 (aop.op.type() == InstallOperation::REPLACE_BZ)) { 93 TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops, 94 target_part_path, 95 blob_file)); 96 } else { 97 fragmented_aops.push_back(aop); 98 } 99 } 100 *aops = fragmented_aops; 101 return true; 102} 103 104bool ABGenerator::SplitSourceCopy( 105 const AnnotatedOperation& original_aop, 106 vector<AnnotatedOperation>* result_aops) { 107 InstallOperation original_op = original_aop.op; 108 TEST_AND_RETURN_FALSE(original_op.type() == InstallOperation::SOURCE_COPY); 109 // Keeps track of the index of curr_src_ext. 110 int curr_src_ext_index = 0; 111 Extent curr_src_ext = original_op.src_extents(curr_src_ext_index); 112 for (int i = 0; i < original_op.dst_extents_size(); i++) { 113 Extent dst_ext = original_op.dst_extents(i); 114 // The new operation which will have only one dst extent. 115 InstallOperation new_op; 116 uint64_t blocks_left = dst_ext.num_blocks(); 117 while (blocks_left > 0) { 118 if (curr_src_ext.num_blocks() <= blocks_left) { 119 // If the curr_src_ext is smaller than dst_ext, add it. 120 blocks_left -= curr_src_ext.num_blocks(); 121 *(new_op.add_src_extents()) = curr_src_ext; 122 if (curr_src_ext_index + 1 < original_op.src_extents().size()) { 123 curr_src_ext = original_op.src_extents(++curr_src_ext_index); 124 } else { 125 break; 126 } 127 } else { 128 // Split src_exts that are bigger than the dst_ext we're dealing with. 129 Extent first_ext; 130 first_ext.set_num_blocks(blocks_left); 131 first_ext.set_start_block(curr_src_ext.start_block()); 132 *(new_op.add_src_extents()) = first_ext; 133 // Keep the second half of the split op. 134 curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left); 135 curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left); 136 blocks_left -= first_ext.num_blocks(); 137 } 138 } 139 // Fix up our new operation and add it to the results. 140 new_op.set_type(InstallOperation::SOURCE_COPY); 141 *(new_op.add_dst_extents()) = dst_ext; 142 new_op.set_src_length(dst_ext.num_blocks() * kBlockSize); 143 new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize); 144 145 AnnotatedOperation new_aop; 146 new_aop.op = new_op; 147 new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i); 148 result_aops->push_back(new_aop); 149 } 150 if (curr_src_ext_index != original_op.src_extents().size() - 1) { 151 LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all " 152 << "source extents."; 153 } 154 return true; 155} 156 157bool ABGenerator::SplitReplaceOrReplaceBz( 158 const AnnotatedOperation& original_aop, 159 vector<AnnotatedOperation>* result_aops, 160 const string& target_part_path, 161 BlobFileWriter* blob_file) { 162 InstallOperation original_op = original_aop.op; 163 const bool is_replace = original_op.type() == InstallOperation::REPLACE; 164 TEST_AND_RETURN_FALSE(is_replace || 165 original_op.type() == InstallOperation::REPLACE_BZ); 166 167 uint32_t data_offset = original_op.data_offset(); 168 for (int i = 0; i < original_op.dst_extents_size(); i++) { 169 Extent dst_ext = original_op.dst_extents(i); 170 // Make a new operation with only one dst extent. 171 InstallOperation new_op; 172 *(new_op.add_dst_extents()) = dst_ext; 173 uint32_t data_size = dst_ext.num_blocks() * kBlockSize; 174 new_op.set_dst_length(data_size); 175 // If this is a REPLACE, attempt to reuse portions of the existing blob. 176 if (is_replace) { 177 new_op.set_type(InstallOperation::REPLACE); 178 new_op.set_data_length(data_size); 179 new_op.set_data_offset(data_offset); 180 data_offset += data_size; 181 } 182 183 AnnotatedOperation new_aop; 184 new_aop.op = new_op; 185 new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i); 186 TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, 187 blob_file)); 188 189 result_aops->push_back(new_aop); 190 } 191 return true; 192} 193 194bool ABGenerator::MergeOperations(vector<AnnotatedOperation>* aops, 195 size_t chunk_blocks, 196 const string& target_part_path, 197 BlobFileWriter* blob_file) { 198 vector<AnnotatedOperation> new_aops; 199 for (const AnnotatedOperation& curr_aop : *aops) { 200 if (new_aops.empty()) { 201 new_aops.push_back(curr_aop); 202 continue; 203 } 204 AnnotatedOperation& last_aop = new_aops.back(); 205 206 if (last_aop.op.dst_extents_size() <= 0 || 207 curr_aop.op.dst_extents_size() <= 0) { 208 new_aops.push_back(curr_aop); 209 continue; 210 } 211 uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1; 212 uint32_t last_end_block = 213 last_aop.op.dst_extents(last_dst_idx).start_block() + 214 last_aop.op.dst_extents(last_dst_idx).num_blocks(); 215 uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block(); 216 uint32_t combined_block_count = 217 last_aop.op.dst_extents(last_dst_idx).num_blocks() + 218 curr_aop.op.dst_extents(0).num_blocks(); 219 bool good_op_type = curr_aop.op.type() == InstallOperation::SOURCE_COPY || 220 curr_aop.op.type() == InstallOperation::REPLACE || 221 curr_aop.op.type() == InstallOperation::REPLACE_BZ; 222 if (good_op_type && 223 last_aop.op.type() == curr_aop.op.type() && 224 last_end_block == curr_start_block && 225 combined_block_count <= chunk_blocks) { 226 // If the operations have the same type (which is a type that we can 227 // merge), are contiguous, are fragmented to have one destination extent, 228 // and their combined block count would be less than chunk size, merge 229 // them. 230 last_aop.name = base::StringPrintf("%s,%s", 231 last_aop.name.c_str(), 232 curr_aop.name.c_str()); 233 234 ExtendExtents(last_aop.op.mutable_src_extents(), 235 curr_aop.op.src_extents()); 236 if (curr_aop.op.src_length() > 0) 237 last_aop.op.set_src_length(last_aop.op.src_length() + 238 curr_aop.op.src_length()); 239 ExtendExtents(last_aop.op.mutable_dst_extents(), 240 curr_aop.op.dst_extents()); 241 if (curr_aop.op.dst_length() > 0) 242 last_aop.op.set_dst_length(last_aop.op.dst_length() + 243 curr_aop.op.dst_length()); 244 // Set the data length to zero so we know to add the blob later. 245 if (curr_aop.op.type() == InstallOperation::REPLACE || 246 curr_aop.op.type() == InstallOperation::REPLACE_BZ) { 247 last_aop.op.set_data_length(0); 248 } 249 } else { 250 // Otherwise just include the extent as is. 251 new_aops.push_back(curr_aop); 252 } 253 } 254 255 // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged. 256 for (AnnotatedOperation& curr_aop : new_aops) { 257 if (curr_aop.op.data_length() == 0 && 258 (curr_aop.op.type() == InstallOperation::REPLACE || 259 curr_aop.op.type() == InstallOperation::REPLACE_BZ)) { 260 TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path, 261 blob_file)); 262 } 263 } 264 265 *aops = new_aops; 266 return true; 267} 268 269bool ABGenerator::AddDataAndSetType(AnnotatedOperation* aop, 270 const string& target_part_path, 271 BlobFileWriter* blob_file) { 272 TEST_AND_RETURN_FALSE(aop->op.type() == InstallOperation::REPLACE || 273 aop->op.type() == InstallOperation::REPLACE_BZ); 274 275 brillo::Blob data(aop->op.dst_length()); 276 vector<Extent> dst_extents; 277 ExtentsToVector(aop->op.dst_extents(), &dst_extents); 278 TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path, 279 dst_extents, 280 &data, 281 data.size(), 282 kBlockSize)); 283 284 brillo::Blob data_bz; 285 TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz)); 286 CHECK(!data_bz.empty()); 287 288 brillo::Blob* data_p = nullptr; 289 InstallOperation_Type new_op_type; 290 if (data_bz.size() < data.size()) { 291 new_op_type = InstallOperation::REPLACE_BZ; 292 data_p = &data_bz; 293 } else { 294 new_op_type = InstallOperation::REPLACE; 295 data_p = &data; 296 } 297 298 // If the operation doesn't point to a data blob, then we add it. 299 if (aop->op.type() != new_op_type || 300 aop->op.data_length() != data_p->size()) { 301 aop->op.set_type(new_op_type); 302 aop->SetOperationBlob(data_p, blob_file); 303 } 304 305 return true; 306} 307 308} // namespace chromeos_update_engine 309