courgette/ensemble_create.cc

   1 // Copyright (c) 2011 The Chromium 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 // The main idea in Courgette is to do patching *under a tranformation*.  The
   6 // input is transformed into a new representation, patching occurs in the new
   7 // repesentation, and then the tranform is reversed to get the patched data.
   8 //
   9 // The idea is applied to pieces (or 'elements') of the whole (or 'ensemble').
  10 // Each of the elements has to go through the same set of steps in lock-step.
  11
  12 // This file contains the code to create the patch.
  13
  14
  15 #include "courgette/ensemble.h"
  16
  17 #include <stddef.h>
  18
  19 #include <limits>
  20 #include <vector>
  21
  22 #include "base/logging.h"
  23 #include "base/time/time.h"
  24
  25 #include "courgette/crc.h"
  26 #include "courgette/difference_estimator.h"
  27 #include "courgette/patch_generator_x86_32.h"
  28 #include "courgette/patcher_x86_32.h"
  29 #include "courgette/region.h"
  30 #include "courgette/simple_delta.h"
  31 #include "courgette/streams.h"
  32 #include "courgette/third_party/bsdiff/bsdiff.h"
  33
  34 namespace courgette {
  35
  36 TransformationPatchGenerator::TransformationPatchGenerator(
  37     Element* old_element,
  38     Element* new_element,
  39     TransformationPatcher* patcher)
  40     : old_element_(old_element),
  41       new_element_(new_element),
  42       patcher_(patcher) {
  43 }
  44
  45 TransformationPatchGenerator::~TransformationPatchGenerator() {
  46   delete patcher_;
  47 }
  48
  49 // The default implementation of PredictTransformParameters delegates to the
  50 // patcher.
  51 Status TransformationPatchGenerator::PredictTransformParameters(
  52     SinkStreamSet* prediction) {
  53   return patcher_->PredictTransformParameters(prediction);
  54 }
  55
  56 // The default implementation of Reform delegates to the patcher.
  57 Status TransformationPatchGenerator::Reform(
  58     SourceStreamSet* transformed_element,
  59     SinkStream* reformed_element) {
  60   return patcher_->Reform(transformed_element, reformed_element);
  61 }
  62
  63 // Makes a TransformationPatchGenerator of the appropriate variety for the
  64 // Element kind.
  65 TransformationPatchGenerator* MakeGenerator(Element* old_element,
  66                                             Element* new_element) {
  67   switch (new_element->kind()) {
  68     case EXE_UNKNOWN:
  69       break;
  70     case EXE_WIN_32_X86: {
  71       TransformationPatchGenerator* generator =
  72           new PatchGeneratorX86_32(
  73               old_element,
  74               new_element,
  75               new PatcherX86_32(old_element->region()),
  76               EXE_WIN_32_X86);
  77       return generator;
  78     }
  79     case EXE_ELF_32_X86: {
  80       TransformationPatchGenerator* generator =
  81           new PatchGeneratorX86_32(
  82               old_element,
  83               new_element,
  84               new PatcherX86_32(old_element->region()),
  85               EXE_ELF_32_X86);
  86       return generator;
  87     }
  88     case EXE_ELF_32_ARM: {
  89       TransformationPatchGenerator* generator =
  90           new PatchGeneratorX86_32(
  91               old_element,
  92               new_element,
  93               new PatcherX86_32(old_element->region()),
  94               EXE_ELF_32_ARM);
  95       return generator;
  96     }
  97     case EXE_WIN_32_X64: {
  98       TransformationPatchGenerator* generator =
  99           new PatchGeneratorX86_32(
 100               old_element,
 101               new_element,
 102               new PatcherX86_32(old_element->region()),
 103               EXE_WIN_32_X64);
 104       return generator;
 105     }
 106   }
 107
 108   LOG(WARNING) << "Unexpected Element::Kind " << old_element->kind();
 109   return nullptr;
 110 }
 111
 112 // Checks to see if the proposed comparison is 'unsafe'.  Sometimes one element
 113 // from 'old' is matched as the closest element to multiple elements from 'new'.
 114 // Each time this happens, the old element is transformed and serialized.  This
 115 // is a problem when the old element is huge compared with the new element
 116 // because the mutliple serialized copies can be much bigger than the size of
 117 // either ensemble.
 118 //
 119 // The right way to avoid this is to ensure any one element from 'old' is
 120 // serialized once, which requires matching code in the patch application.
 121 //
 122 // This is a quick hack to avoid the problem by prohibiting a big difference in
 123 // size between matching elements.
 124 bool UnsafeDifference(Element* old_element, Element* new_element) {
 125   double kMaxBloat = 2.0;
 126   size_t kMinWorrysomeDifference = 2 << 20;  // 2MB
 127   size_t old_size = old_element->region().length();
 128   size_t new_size = new_element->region().length();
 129   size_t low_size = std::min(old_size, new_size);
 130   size_t high_size = std::max(old_size, new_size);
 131   if (high_size - low_size < kMinWorrysomeDifference) return false;
 132   if (high_size < low_size * kMaxBloat) return false;
 133   return true;
 134 }
 135
 136 // FindGenerators finds TransformationPatchGenerators for the elements of
 137 // |new_ensemble|.  For each element of |new_ensemble| we find the closest
 138 // matching element from |old_ensemble| and use that as the basis for
 139 // differential compression.  The elements have to be the same kind so as to
 140 // support transformation into the same kind of 'new representation'.
 141 //
 142 Status FindGenerators(Ensemble* old_ensemble, Ensemble* new_ensemble,
 143                       std::vector<TransformationPatchGenerator*>* generators) {
 144   base::Time start_find_time = base::Time::Now();
 145   old_ensemble->FindEmbeddedElements();
 146   new_ensemble->FindEmbeddedElements();
 147   VLOG(1) << "done FindEmbeddedElements "
 148           << (base::Time::Now() - start_find_time).InSecondsF();
 149
 150   std::vector<Element*> old_elements(old_ensemble->elements());
 151   std::vector<Element*> new_elements(new_ensemble->elements());
 152
 153   VLOG(1) << "old has " << old_elements.size() << " elements";
 154   VLOG(1) << "new has " << new_elements.size() << " elements";
 155
 156   DifferenceEstimator difference_estimator;
 157   std::vector<DifferenceEstimator::Base*> bases;
 158
 159   base::Time start_bases_time = base::Time::Now();
 160   for (size_t i = 0;  i < old_elements.size();  ++i) {
 161     bases.push_back(
 162         difference_estimator.MakeBase(old_elements[i]->region()));
 163   }
 164   VLOG(1) << "done make bases "
 165           << (base::Time::Now() - start_bases_time).InSecondsF() << "s";
 166
 167   for (size_t new_index = 0;  new_index < new_elements.size();  ++new_index) {
 168     Element* new_element = new_elements[new_index];
 169     DifferenceEstimator::Subject* new_subject =
 170         difference_estimator.MakeSubject(new_element->region());
 171
 172     // Search through old elements to find the best match.
 173     //
 174     // TODO(sra): This is O(N x M), i.e. O(N^2) since old_ensemble and
 175     // new_ensemble probably have a very similar structure.  We can make the
 176     // search faster by making the comparison provided by DifferenceEstimator
 177     // more nuanced, returning early if the measured difference is greater than
 178     // the current best.  This will be most effective if we can arrange that the
 179     // first elements we try to match are likely the 'right' ones.  We could
 180     // prioritize elements that are of a similar size or similar position in the
 181     // sequence of elements.
 182     //
 183     Element* best_old_element = nullptr;
 184     size_t best_difference = std::numeric_limits<size_t>::max();
 185     for (size_t old_index = 0;  old_index < old_elements.size();  ++old_index) {
 186       Element* old_element = old_elements[old_index];
 187       // Elements of different kinds are incompatible.
 188       if (old_element->kind() != new_element->kind())
 189         continue;
 190
 191       if (UnsafeDifference(old_element, new_element))
 192         continue;
 193
 194       base::Time start_compare = base::Time::Now();
 195       DifferenceEstimator::Base* old_base = bases[old_index];
 196       size_t difference = difference_estimator.Measure(old_base, new_subject);
 197
 198       VLOG(1) << "Compare " << old_element->Name()
 199               << " to " << new_element->Name()
 200               << " --> " << difference
 201               << " in " << (base::Time::Now() - start_compare).InSecondsF()
 202               << "s";
 203       if (difference == 0) {
 204         VLOG(1) << "Skip " << new_element->Name()
 205                 << " - identical to " << old_element->Name();
 206         best_difference = 0;
 207         best_old_element = nullptr;
 208         break;
 209       }
 210       if (difference < best_difference) {
 211         best_difference = difference;
 212         best_old_element = old_element;
 213       }
 214     }
 215
 216     if (best_old_element) {
 217       VLOG(1) << "Matched " << best_old_element->Name()
 218               << " to " << new_element->Name()
 219               << " --> " << best_difference;
 220       TransformationPatchGenerator* generator =
 221           MakeGenerator(best_old_element, new_element);
 222       if (generator)
 223         generators->push_back(generator);
 224     }
 225   }
 226
 227   VLOG(1) << "done FindGenerators found " << generators->size()
 228           << " in " << (base::Time::Now() - start_find_time).InSecondsF()
 229           << "s";
 230
 231   return C_OK;
 232 }
 233
 234 void FreeGenerators(std::vector<TransformationPatchGenerator*>* generators) {
 235   for (size_t i = 0;  i < generators->size();  ++i) {
 236     delete (*generators)[i];
 237   }
 238   generators->clear();
 239 }
 240
 241 ////////////////////////////////////////////////////////////////////////////////
 242
 243 Status GenerateEnsemblePatch(SourceStream* base,
 244                              SourceStream* update,
 245                              SinkStream* final_patch) {
 246   VLOG(1) << "start GenerateEnsemblePatch";
 247   base::Time start_time = base::Time::Now();
 248
 249   Region old_region(base->Buffer(), base->Remaining());
 250   Region new_region(update->Buffer(), update->Remaining());
 251   Ensemble old_ensemble(old_region, "old");
 252   Ensemble new_ensemble(new_region, "new");
 253   std::vector<TransformationPatchGenerator*> generators;
 254   Status generators_status = FindGenerators(&old_ensemble, &new_ensemble,
 255                                             &generators);
 256   if (generators_status != C_OK)
 257     return generators_status;
 258
 259   SinkStreamSet patch_streams;
 260
 261   SinkStream* tranformation_descriptions      = patch_streams.stream(0);
 262   SinkStream* parameter_correction            = patch_streams.stream(1);
 263   SinkStream* transformed_elements_correction = patch_streams.stream(2);
 264   SinkStream* ensemble_correction             = patch_streams.stream(3);
 265
 266   size_t number_of_transformations = generators.size();
 267   if (!tranformation_descriptions->WriteSizeVarint32(number_of_transformations))
 268     return C_STREAM_ERROR;
 269
 270   for (size_t i = 0;  i < number_of_transformations;  ++i) {
 271     ExecutableType kind = generators[i]->Kind();
 272     if (!tranformation_descriptions->WriteVarint32(kind))
 273       return C_STREAM_ERROR;
 274   }
 275
 276   for (size_t i = 0;  i < number_of_transformations;  ++i) {
 277     Status status =
 278         generators[i]->WriteInitialParameters(tranformation_descriptions);
 279     if (status != C_OK)
 280       return status;
 281   }
 282
 283   //
 284   // Generate sub-patch for parameters.
 285   //
 286   SinkStreamSet predicted_parameters_sink;
 287   SinkStreamSet corrected_parameters_sink;
 288
 289   for (size_t i = 0;  i < number_of_transformations;  ++i) {
 290     SinkStreamSet single_predicted_parameters;
 291     Status status;
 292     status = generators[i]->PredictTransformParameters(
 293         &single_predicted_parameters);
 294     if (status != C_OK)
 295       return status;
 296     if (!predicted_parameters_sink.WriteSet(&single_predicted_parameters))
 297       return C_STREAM_ERROR;
 298
 299     SinkStreamSet single_corrected_parameters;
 300     status = generators[i]->CorrectedTransformParameters(
 301         &single_corrected_parameters);
 302     if (status != C_OK)
 303       return status;
 304     if (!corrected_parameters_sink.WriteSet(&single_corrected_parameters))
 305       return C_STREAM_ERROR;
 306   }
 307
 308   SinkStream linearized_predicted_parameters;
 309   SinkStream linearized_corrected_parameters;
 310
 311   if (!predicted_parameters_sink.CopyTo(&linearized_predicted_parameters))
 312     return C_STREAM_ERROR;
 313   if (!corrected_parameters_sink.CopyTo(&linearized_corrected_parameters))
 314     return C_STREAM_ERROR;
 315
 316   SourceStream predicted_parameters_source;
 317   SourceStream corrected_parameters_source;
 318   predicted_parameters_source.Init(linearized_predicted_parameters);
 319   corrected_parameters_source.Init(linearized_corrected_parameters);
 320
 321   Status delta1_status = GenerateSimpleDelta(&predicted_parameters_source,
 322                                              &corrected_parameters_source,
 323                                              parameter_correction);
 324   if (delta1_status != C_OK)
 325     return delta1_status;
 326
 327   //
 328   // Generate sub-patch for elements.
 329   //
 330   corrected_parameters_source.Init(linearized_corrected_parameters);
 331   SourceStreamSet corrected_parameters_source_set;
 332   if (!corrected_parameters_source_set.Init(&corrected_parameters_source))
 333     return C_STREAM_ERROR;
 334
 335   SinkStreamSet predicted_transformed_elements;
 336   SinkStreamSet corrected_transformed_elements;
 337
 338   for (size_t i = 0;  i < number_of_transformations;  ++i) {
 339     SourceStreamSet single_parameters;
 340     if (!corrected_parameters_source_set.ReadSet(&single_parameters))
 341       return C_STREAM_ERROR;
 342     SinkStreamSet single_predicted_transformed_element;
 343     SinkStreamSet single_corrected_transformed_element;
 344     Status status = generators[i]->Transform(
 345         &single_parameters,
 346         &single_predicted_transformed_element,
 347         &single_corrected_transformed_element);
 348     if (status != C_OK)
 349       return status;
 350     if (!single_parameters.Empty())
 351       return C_STREAM_NOT_CONSUMED;
 352     if (!predicted_transformed_elements.WriteSet(
 353             &single_predicted_transformed_element))
 354       return C_STREAM_ERROR;
 355     if (!corrected_transformed_elements.WriteSet(
 356             &single_corrected_transformed_element))
 357       return C_STREAM_ERROR;
 358   }
 359
 360   if (!corrected_parameters_source_set.Empty())
 361     return C_STREAM_NOT_CONSUMED;
 362
 363   SinkStream linearized_predicted_transformed_elements;
 364   SinkStream linearized_corrected_transformed_elements;
 365
 366   if (!predicted_transformed_elements.CopyTo(
 367           &linearized_predicted_transformed_elements))
 368     return C_STREAM_ERROR;
 369   if (!corrected_transformed_elements.CopyTo(
 370           &linearized_corrected_transformed_elements))
 371     return C_STREAM_ERROR;
 372
 373   SourceStream predicted_transformed_elements_source;
 374   SourceStream corrected_transformed_elements_source;
 375   predicted_transformed_elements_source
 376       .Init(linearized_predicted_transformed_elements);
 377   corrected_transformed_elements_source
 378       .Init(linearized_corrected_transformed_elements);
 379
 380   Status delta2_status =
 381       GenerateSimpleDelta(&predicted_transformed_elements_source,
 382                           &corrected_transformed_elements_source,
 383                           transformed_elements_correction);
 384   if (delta2_status != C_OK)
 385     return delta2_status;
 386
 387   // Last use, free storage.
 388   linearized_predicted_transformed_elements.Retire();
 389
 390   //
 391   // Generate sub-patch for whole enchilada.
 392   //
 393   SinkStream predicted_ensemble;
 394
 395   if (!predicted_ensemble.Write(base->Buffer(), base->Remaining()))
 396     return C_STREAM_ERROR;
 397
 398   SourceStreamSet corrected_transformed_elements_source_set;
 399   corrected_transformed_elements_source
 400       .Init(linearized_corrected_transformed_elements);
 401   if (!corrected_transformed_elements_source_set
 402       .Init(&corrected_transformed_elements_source))
 403     return C_STREAM_ERROR;
 404
 405   for (size_t i = 0;  i < number_of_transformations;  ++i) {
 406     SourceStreamSet single_corrected_transformed_element;
 407     if (!corrected_transformed_elements_source_set.ReadSet(
 408             &single_corrected_transformed_element))
 409       return C_STREAM_ERROR;
 410     Status status = generators[i]->Reform(&single_corrected_transformed_element,
 411                                           &predicted_ensemble);
 412     if (status != C_OK)
 413       return status;
 414     if (!single_corrected_transformed_element.Empty())
 415       return C_STREAM_NOT_CONSUMED;
 416   }
 417
 418   if (!corrected_transformed_elements_source_set.Empty())
 419     return C_STREAM_NOT_CONSUMED;
 420
 421   // No more references to this stream's buffer.
 422   linearized_corrected_transformed_elements.Retire();
 423
 424   FreeGenerators(&generators);
 425
 426   size_t final_patch_input_size = predicted_ensemble.Length();
 427   SourceStream predicted_ensemble_source;
 428   predicted_ensemble_source.Init(predicted_ensemble);
 429   Status delta3_status = GenerateSimpleDelta(&predicted_ensemble_source,
 430                                              update,
 431                                              ensemble_correction);
 432   if (delta3_status != C_OK)
 433     return delta3_status;
 434
 435   //
 436   // Final output stream has a header followed by a StreamSet.
 437   //
 438   if (!final_patch->WriteVarint32(CourgettePatchFile::kMagic) ||
 439       !final_patch->WriteVarint32(CourgettePatchFile::kVersion) ||
 440       !final_patch->WriteVarint32(CalculateCrc(old_region.start(),
 441                                                old_region.length())) ||
 442       !final_patch->WriteVarint32(CalculateCrc(new_region.start(),
 443                                                new_region.length())) ||
 444       !final_patch->WriteSizeVarint32(final_patch_input_size) ||
 445       !patch_streams.CopyTo(final_patch)) {
 446     return C_STREAM_ERROR;
 447   }
 448
 449   VLOG(1) << "done GenerateEnsemblePatch "
 450           << (base::Time::Now() - start_time).InSecondsF() << "s";
 451
 452   return C_OK;
 453 }
 454
 455 }  // namespace