zucchini_gen.cc 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468
  1. // Copyright 2017 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. #include "components/zucchini/zucchini_gen.h"
  5. #include <stddef.h>
  6. #include <stdint.h>
  7. #include <algorithm>
  8. #include <map>
  9. #include <memory>
  10. #include <string>
  11. #include <utility>
  12. #include "base/logging.h"
  13. #include "base/numerics/safe_conversions.h"
  14. #include "components/zucchini/disassembler.h"
  15. #include "components/zucchini/element_detection.h"
  16. #include "components/zucchini/encoded_view.h"
  17. #include "components/zucchini/ensemble_matcher.h"
  18. #include "components/zucchini/equivalence_map.h"
  19. #include "components/zucchini/heuristic_ensemble_matcher.h"
  20. #include "components/zucchini/image_index.h"
  21. #include "components/zucchini/imposed_ensemble_matcher.h"
  22. #include "components/zucchini/patch_writer.h"
  23. #include "components/zucchini/suffix_array.h"
  24. #include "components/zucchini/targets_affinity.h"
  25. namespace zucchini {
  26. namespace {
  27. // Parameters for patch generation.
  28. constexpr double kMinEquivalenceSimilarity = 12.0;
  29. constexpr double kMinLabelAffinity = 64.0;
  30. } // namespace
  31. std::vector<offset_t> FindExtraTargets(const TargetPool& projected_old_targets,
  32. const TargetPool& new_targets) {
  33. std::vector<offset_t> extra_targets;
  34. std::set_difference(
  35. new_targets.begin(), new_targets.end(), projected_old_targets.begin(),
  36. projected_old_targets.end(), std::back_inserter(extra_targets));
  37. return extra_targets;
  38. }
  39. // Label matching (between "old" and "new") can guide EquivalenceMap
  40. // construction; but EquivalenceMap induces Label matching. This apparent "chick
  41. // and egg" problem is solved by alternating 2 steps |num_iterations| times:
  42. // - Associate targets based on previous EquivalenceMap. Note on the first
  43. // iteration, EquivalenceMap is empty, resulting in a no-op.
  44. // - Construct refined EquivalenceMap based on new targets associations.
  45. EquivalenceMap CreateEquivalenceMap(const ImageIndex& old_image_index,
  46. const ImageIndex& new_image_index,
  47. int num_iterations) {
  48. size_t pool_count = old_image_index.PoolCount();
  49. // |target_affinities| is outside the loop to reduce allocation.
  50. std::vector<TargetsAffinity> target_affinities(pool_count);
  51. EquivalenceMap equivalence_map;
  52. for (int i = 0; i < num_iterations; ++i) {
  53. EncodedView old_view(old_image_index);
  54. EncodedView new_view(new_image_index);
  55. // Associate targets from "old" to "new" image based on |equivalence_map|
  56. // for each reference pool.
  57. for (const auto& old_pool_tag_and_targets :
  58. old_image_index.target_pools()) {
  59. PoolTag pool_tag = old_pool_tag_and_targets.first;
  60. target_affinities[pool_tag.value()].InferFromSimilarities(
  61. equivalence_map, old_pool_tag_and_targets.second.targets(),
  62. new_image_index.pool(pool_tag).targets());
  63. // Creates labels for strongly associated targets.
  64. std::vector<uint32_t> old_labels;
  65. std::vector<uint32_t> new_labels;
  66. size_t label_bound = target_affinities[pool_tag.value()].AssignLabels(
  67. kMinLabelAffinity, &old_labels, &new_labels);
  68. old_view.SetLabels(pool_tag, std::move(old_labels), label_bound);
  69. new_view.SetLabels(pool_tag, std::move(new_labels), label_bound);
  70. }
  71. // Build equivalence map, where references in "old" and "new" that share
  72. // common semantics (i.e., their respective targets were associated earlier
  73. // on) are considered equivalent.
  74. equivalence_map.Build(
  75. MakeSuffixArray<InducedSuffixSort>(old_view, old_view.Cardinality()),
  76. old_view, new_view, target_affinities, kMinEquivalenceSimilarity);
  77. }
  78. return equivalence_map;
  79. }
  80. bool GenerateEquivalencesAndExtraData(ConstBufferView new_image,
  81. const EquivalenceMap& equivalence_map,
  82. PatchElementWriter* patch_writer) {
  83. // Make 2 passes through |equivalence_map| to reduce write churn.
  84. // Pass 1: Write all equivalences.
  85. EquivalenceSink equivalences_sink;
  86. for (const EquivalenceCandidate& candidate : equivalence_map)
  87. equivalences_sink.PutNext(candidate.eq);
  88. patch_writer->SetEquivalenceSink(std::move(equivalences_sink));
  89. // Pass 2: Write data in gaps in |new_image| before / between after
  90. // |equivalence_map| as "extra data".
  91. ExtraDataSink extra_data_sink;
  92. offset_t dst_offset = 0;
  93. for (const EquivalenceCandidate& candidate : equivalence_map) {
  94. extra_data_sink.PutNext(
  95. new_image[{dst_offset, candidate.eq.dst_offset - dst_offset}]);
  96. dst_offset = candidate.eq.dst_end();
  97. DCHECK_LE(dst_offset, new_image.size());
  98. }
  99. extra_data_sink.PutNext(
  100. new_image[{dst_offset, new_image.size() - dst_offset}]);
  101. patch_writer->SetExtraDataSink(std::move(extra_data_sink));
  102. return true;
  103. }
  104. bool GenerateRawDelta(
  105. ConstBufferView old_image,
  106. ConstBufferView new_image,
  107. const EquivalenceMap& equivalence_map,
  108. const ImageIndex& new_image_index,
  109. const std::map<TypeTag, std::unique_ptr<ReferenceMixer>>& reference_mixers,
  110. PatchElementWriter* patch_writer) {
  111. RawDeltaSink raw_delta_sink;
  112. // Visit |equivalence_map| blocks in |new_image| order. Find and emit all
  113. // bytewise differences.
  114. offset_t base_copy_offset = 0;
  115. for (const EquivalenceCandidate& candidate : equivalence_map) {
  116. Equivalence equivalence = candidate.eq;
  117. // For each bytewise delta from |old_image| to |new_image|, compute "copy
  118. // offset" and pass it along with delta to the sink.
  119. for (offset_t i = 0; i < equivalence.length;) {
  120. if (new_image_index.IsReference(equivalence.dst_offset + i)) {
  121. DCHECK(new_image_index.IsToken(equivalence.dst_offset + i));
  122. TypeTag type_tag =
  123. new_image_index.LookupType(equivalence.dst_offset + i);
  124. ReferenceMixer* mixer = reference_mixers.at(type_tag).get();
  125. offset_t width = new_image_index.refs(type_tag).width();
  126. // Reference delta has its own flow. On some architectures (e.g., x86)
  127. // this does not involve raw delta, so we skip. On other architectures
  128. // (e.g., ARM) references are mixed with other bits that may change, so
  129. // we need to "mix" data and store some changed bits into raw delta.
  130. if (mixer) {
  131. ConstBufferView mixed_reference = mixer->Mix(
  132. equivalence.src_offset + i, equivalence.dst_offset + i);
  133. for (offset_t j = 0; j < width; ++j) {
  134. int8_t diff =
  135. mixed_reference[j] - old_image[equivalence.src_offset + i + j];
  136. if (diff != 0)
  137. raw_delta_sink.PutNext({base_copy_offset + i + j, diff});
  138. }
  139. }
  140. i += width;
  141. DCHECK_LE(i, equivalence.length);
  142. } else {
  143. int8_t diff = new_image[equivalence.dst_offset + i] -
  144. old_image[equivalence.src_offset + i];
  145. if (diff)
  146. raw_delta_sink.PutNext({base_copy_offset + i, diff});
  147. ++i;
  148. }
  149. }
  150. base_copy_offset += equivalence.length;
  151. }
  152. patch_writer->SetRawDeltaSink(std::move(raw_delta_sink));
  153. return true;
  154. }
  155. bool GenerateReferencesDelta(const ReferenceSet& src_refs,
  156. const ReferenceSet& dst_refs,
  157. const TargetPool& projected_target_pool,
  158. const OffsetMapper& offset_mapper,
  159. const EquivalenceMap& equivalence_map,
  160. ReferenceDeltaSink* reference_delta_sink) {
  161. size_t ref_width = src_refs.width();
  162. auto dst_ref = dst_refs.begin();
  163. // For each equivalence, for each covered |dst_ref| and the matching
  164. // |src_ref|, emit the delta between the respective target labels. Note: By
  165. // construction, each reference location (with |ref_width|) lies either
  166. // completely inside an equivalence or completely outside. We perform
  167. // "straddle checks" throughout to verify this assertion.
  168. for (const auto& candidate : equivalence_map) {
  169. const Equivalence equiv = candidate.eq;
  170. // Increment |dst_ref| until it catches up to |equiv|.
  171. while (dst_ref != dst_refs.end() && dst_ref->location < equiv.dst_offset)
  172. ++dst_ref;
  173. if (dst_ref == dst_refs.end())
  174. break;
  175. if (dst_ref->location >= equiv.dst_end())
  176. continue;
  177. // Straddle check.
  178. DCHECK_LE(dst_ref->location + ref_width, equiv.dst_end());
  179. offset_t src_loc =
  180. equiv.src_offset + (dst_ref->location - equiv.dst_offset);
  181. auto src_ref = std::lower_bound(
  182. src_refs.begin(), src_refs.end(), src_loc,
  183. [](const Reference& a, offset_t b) { return a.location < b; });
  184. for (; dst_ref != dst_refs.end() &&
  185. dst_ref->location + ref_width <= equiv.dst_end();
  186. ++dst_ref, ++src_ref) {
  187. // Local offset of |src_ref| should match that of |dst_ref|.
  188. DCHECK_EQ(src_ref->location - equiv.src_offset,
  189. dst_ref->location - equiv.dst_offset);
  190. offset_t old_offset = src_ref->target;
  191. offset_t new_estimated_offset =
  192. offset_mapper.ExtendedForwardProject(old_offset);
  193. offset_t new_estimated_key =
  194. projected_target_pool.KeyForNearestOffset(new_estimated_offset);
  195. offset_t new_offset = dst_ref->target;
  196. offset_t new_key = projected_target_pool.KeyForOffset(new_offset);
  197. reference_delta_sink->PutNext(
  198. static_cast<int32_t>(new_key - new_estimated_key));
  199. }
  200. if (dst_ref == dst_refs.end())
  201. break; // Done.
  202. // Straddle check.
  203. DCHECK_GE(dst_ref->location, equiv.dst_end());
  204. }
  205. return true;
  206. }
  207. bool GenerateExtraTargets(const std::vector<offset_t>& extra_targets,
  208. PoolTag pool_tag,
  209. PatchElementWriter* patch_writer) {
  210. TargetSink target_sink;
  211. for (offset_t target : extra_targets)
  212. target_sink.PutNext(target);
  213. patch_writer->SetTargetSink(pool_tag, std::move(target_sink));
  214. return true;
  215. }
  216. bool GenerateRawElement(const std::vector<offset_t>& old_sa,
  217. ConstBufferView old_image,
  218. ConstBufferView new_image,
  219. PatchElementWriter* patch_writer) {
  220. ImageIndex old_image_index(old_image);
  221. ImageIndex new_image_index(new_image);
  222. EquivalenceMap equivalences;
  223. equivalences.Build(old_sa, EncodedView(old_image_index),
  224. EncodedView(new_image_index), {},
  225. kMinEquivalenceSimilarity);
  226. patch_writer->SetReferenceDeltaSink({});
  227. std::map<TypeTag, std::unique_ptr<ReferenceMixer>> reference_mixers;
  228. return GenerateEquivalencesAndExtraData(new_image, equivalences,
  229. patch_writer) &&
  230. GenerateRawDelta(old_image, new_image, equivalences, new_image_index,
  231. reference_mixers, patch_writer);
  232. }
  233. bool GenerateExecutableElement(ExecutableType exe_type,
  234. ConstBufferView old_image,
  235. ConstBufferView new_image,
  236. PatchElementWriter* patch_writer) {
  237. // Initialize Disassemblers.
  238. std::unique_ptr<Disassembler> old_disasm =
  239. MakeDisassemblerOfType(old_image, exe_type);
  240. std::unique_ptr<Disassembler> new_disasm =
  241. MakeDisassemblerOfType(new_image, exe_type);
  242. if (!old_disasm || !new_disasm) {
  243. LOG(ERROR) << "Failed to create Disassembler.";
  244. return false;
  245. }
  246. DCHECK_EQ(old_disasm->GetExeType(), new_disasm->GetExeType());
  247. // Initialize ImageIndexes.
  248. ImageIndex old_image_index(old_image);
  249. ImageIndex new_image_index(new_image);
  250. if (!old_image_index.Initialize(old_disasm.get()) ||
  251. !new_image_index.Initialize(new_disasm.get())) {
  252. LOG(ERROR) << "Failed to create ImageIndex: Overlapping references found?";
  253. return false;
  254. }
  255. DCHECK_EQ(old_image_index.PoolCount(), new_image_index.PoolCount());
  256. EquivalenceMap equivalences =
  257. CreateEquivalenceMap(old_image_index, new_image_index,
  258. new_disasm->num_equivalence_iterations());
  259. OffsetMapper offset_mapper(equivalences,
  260. base::checked_cast<offset_t>(old_image.size()),
  261. base::checked_cast<offset_t>(new_image.size()));
  262. ReferenceDeltaSink reference_delta_sink;
  263. for (const auto& old_targets : old_image_index.target_pools()) {
  264. PoolTag pool_tag = old_targets.first;
  265. TargetPool projected_old_targets = old_targets.second;
  266. projected_old_targets.FilterAndProject(offset_mapper);
  267. std::vector<offset_t> extra_target =
  268. FindExtraTargets(projected_old_targets, new_image_index.pool(pool_tag));
  269. projected_old_targets.InsertTargets(extra_target);
  270. if (!GenerateExtraTargets(extra_target, pool_tag, patch_writer))
  271. return false;
  272. for (TypeTag type_tag : old_targets.second.types()) {
  273. if (!GenerateReferencesDelta(old_image_index.refs(type_tag),
  274. new_image_index.refs(type_tag),
  275. projected_old_targets, offset_mapper,
  276. equivalences, &reference_delta_sink)) {
  277. return false;
  278. }
  279. }
  280. }
  281. std::map<TypeTag, std::unique_ptr<ReferenceMixer>> reference_mixers;
  282. std::vector<ReferenceGroup> ref_groups = old_disasm->MakeReferenceGroups();
  283. for (const auto& group : ref_groups) {
  284. auto result = reference_mixers.emplace(
  285. group.type_tag(),
  286. group.GetMixer(old_image, new_image, old_disasm.get()));
  287. DCHECK(result.second);
  288. }
  289. patch_writer->SetReferenceDeltaSink(std::move(reference_delta_sink));
  290. return GenerateEquivalencesAndExtraData(new_image, equivalences,
  291. patch_writer) &&
  292. GenerateRawDelta(old_image, new_image, equivalences, new_image_index,
  293. reference_mixers, patch_writer);
  294. }
  295. status::Code GenerateBufferCommon(ConstBufferView old_image,
  296. ConstBufferView new_image,
  297. std::unique_ptr<EnsembleMatcher> matcher,
  298. EnsemblePatchWriter* patch_writer) {
  299. if (!matcher->RunMatch(old_image, new_image)) {
  300. LOG(INFO) << "RunMatch() failed, generating raw patch.";
  301. return GenerateBufferRaw(old_image, new_image, patch_writer);
  302. }
  303. const std::vector<ElementMatch>& matches = matcher->matches();
  304. LOG(INFO) << "Matching: Found " << matches.size()
  305. << " nontrivial matches and " << matcher->num_identical()
  306. << " identical matches.";
  307. size_t num_elements = matches.size();
  308. if (num_elements == 0) {
  309. LOG(INFO) << "No nontrival matches, generating raw patch.";
  310. return GenerateBufferRaw(old_image, new_image, patch_writer);
  311. }
  312. // "Gaps" are |new_image| bytes not covered by new_elements in |matches|.
  313. // These are treated as raw data, and patched against the entire |old_image|.
  314. // |patch_element_map| (keyed by "new" offsets) stores PatchElementWriter
  315. // results so elements and "gap" results can be computed separately (to reduce
  316. // peak memory usage), and later, properly serialized to |patch_writer|
  317. // ordered by "new" offset.
  318. std::map<offset_t, PatchElementWriter> patch_element_map;
  319. // Variables to track element patching successes.
  320. std::vector<BufferRegion> covered_new_regions;
  321. size_t covered_new_bytes = 0;
  322. // Process elements first, since non-fatal failures may turn some into gaps.
  323. for (const ElementMatch& match : matches) {
  324. BufferRegion new_region = match.new_element.region();
  325. LOG(INFO) << "--- Match [" << new_region.lo() << "," << new_region.hi()
  326. << ")";
  327. auto it_and_success = patch_element_map.emplace(
  328. base::checked_cast<offset_t>(new_region.lo()), match);
  329. DCHECK(it_and_success.second);
  330. PatchElementWriter& patch_element = it_and_success.first->second;
  331. ConstBufferView old_sub_image = old_image[match.old_element.region()];
  332. ConstBufferView new_sub_image = new_image[new_region];
  333. if (GenerateExecutableElement(match.exe_type(), old_sub_image,
  334. new_sub_image, &patch_element)) {
  335. covered_new_regions.push_back(new_region);
  336. covered_new_bytes += new_region.size;
  337. } else {
  338. LOG(INFO) << "Fall back to raw patching.";
  339. patch_element_map.erase(it_and_success.first);
  340. }
  341. }
  342. if (covered_new_bytes < new_image.size()) {
  343. // Process all "gaps", which are patched against the entire "old" image. To
  344. // compute equivalence maps, "gaps" share a common suffix array
  345. // |old_sa_raw|, whose lifetime is kept separated from elements' suffix
  346. // arrays to reduce peak memory.
  347. Element entire_old_element(old_image.local_region(), kExeTypeNoOp);
  348. ImageIndex old_image_index(old_image);
  349. EncodedView old_view_raw(old_image_index);
  350. std::vector<offset_t> old_sa_raw =
  351. MakeSuffixArray<InducedSuffixSort>(old_view_raw, size_t(256));
  352. offset_t gap_lo = 0;
  353. // Add sentinel that points to end of "new" file, to simplify gap iteration.
  354. covered_new_regions.emplace_back(BufferRegion{new_image.size(), 0});
  355. for (const BufferRegion& covered : covered_new_regions) {
  356. offset_t gap_hi = base::checked_cast<offset_t>(covered.lo());
  357. DCHECK_GE(gap_hi, gap_lo);
  358. offset_t gap_size = gap_hi - gap_lo;
  359. if (gap_size > 0) {
  360. LOG(INFO) << "--- Gap [" << gap_lo << "," << gap_hi << ")";
  361. ElementMatch gap_match{{entire_old_element, kExeTypeNoOp},
  362. {{gap_lo, gap_size}, kExeTypeNoOp}};
  363. auto it_and_success = patch_element_map.emplace(gap_lo, gap_match);
  364. DCHECK(it_and_success.second);
  365. PatchElementWriter& patch_element = it_and_success.first->second;
  366. ConstBufferView new_sub_image = new_image[{gap_lo, gap_size}];
  367. if (!GenerateRawElement(old_sa_raw, old_image, new_sub_image,
  368. &patch_element)) {
  369. return status::kStatusFatal;
  370. }
  371. }
  372. gap_lo = base::checked_cast<offset_t>(covered.hi());
  373. }
  374. }
  375. // Write all PatchElementWriter sorted by "new" offset.
  376. for (auto& new_lo_and_patch_element : patch_element_map)
  377. patch_writer->AddElement(std::move(new_lo_and_patch_element.second));
  378. return status::kStatusSuccess;
  379. }
  380. /******** Exported Functions ********/
  381. status::Code GenerateBuffer(ConstBufferView old_image,
  382. ConstBufferView new_image,
  383. EnsemblePatchWriter* patch_writer) {
  384. return GenerateBufferCommon(
  385. old_image, new_image, std::make_unique<HeuristicEnsembleMatcher>(nullptr),
  386. patch_writer);
  387. }
  388. status::Code GenerateBufferImposed(ConstBufferView old_image,
  389. ConstBufferView new_image,
  390. std::string imposed_matches,
  391. EnsemblePatchWriter* patch_writer) {
  392. if (imposed_matches.empty())
  393. return GenerateBuffer(old_image, new_image, patch_writer);
  394. return GenerateBufferCommon(
  395. old_image, new_image,
  396. std::make_unique<ImposedEnsembleMatcher>(imposed_matches), patch_writer);
  397. }
  398. status::Code GenerateBufferRaw(ConstBufferView old_image,
  399. ConstBufferView new_image,
  400. EnsemblePatchWriter* patch_writer) {
  401. ImageIndex old_image_index(old_image);
  402. EncodedView old_view(old_image_index);
  403. std::vector<offset_t> old_sa =
  404. MakeSuffixArray<InducedSuffixSort>(old_view, old_view.Cardinality());
  405. PatchElementWriter patch_element(
  406. {Element(old_image.local_region()), Element(new_image.local_region())});
  407. if (!GenerateRawElement(old_sa, old_image, new_image, &patch_element))
  408. return status::kStatusFatal;
  409. patch_writer->AddElement(std::move(patch_element));
  410. return status::kStatusSuccess;
  411. }
  412. } // namespace zucchini