ensemble_create.cc 16 KB

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