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