ab_generator.cc revision 3f39d5cc753905874d8d93bef94f857b8808f19e 
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/bzip.h"
24#include "update_engine/delta_performer.h"
25#include "update_engine/payload_generator/annotated_operation.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