[Zucchini] Move Zucchini from /chrome/installer/ to /components/.

(Use "git log --follow" to see older revisions of files).

/components/ is the most logical place to put Zucchini, which only
depends on /base and /testing/gtest. This move also enables Zucchini to
be used by the Component Updater. Details:
- Move all files; run the following to change deps and guards:
  sed 's/chrome\/installer/components/' *.cc *.h -i
  sed 's/CHROME_INSTALLER/COMPONENTS/' *.cc *.h -i
  - Sorting works out pretty well!
- Change all 'chrome/installer/zucchini' to 'components/zucchini'
  throughout other parts of the repo; sort if necessary.
- Fix 6 'git cl lint' errors.
- Change 1 Bind() usage to BindRepeated().
- Update OWNER.

Bug: 729154
Change-Id: I50c5a7d411ea85f707b5994ab319dfb2a1acccf7
Reviewed-on: https://chromium-review.googlesource.com/954923
Reviewed-by: Greg Thompson <grt@chromium.org>
Reviewed-by: Jochen Eisinger <jochen@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Commit-Queue: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542857}
NOKEYCHECK=True
GitOrigin-RevId: 577ef6c435e8d43be6e3e60ccbcbd1881780f4ec

1 files changed, 254 insertions, 0 deletions

diff --git a/address_translator.cc b/address_translator.cc
new file mode 100644
index 0000000..79e7ba6
--- /dev/null
+++ b/address_translator.cc
@@ -0,0 +1,254 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/zucchini/address_translator.h"
+
+#include <algorithm>
+#include <utility>
+
+namespace zucchini {
+
+/******** AddressTranslator::OffsetToRvaCache ********/
+
+AddressTranslator::OffsetToRvaCache::OffsetToRvaCache(
+    const AddressTranslator& translator)
+    : translator_(translator) {}
+
+rva_t AddressTranslator::OffsetToRvaCache::Convert(offset_t offset) const {
+  if (offset >= translator_.fake_offset_begin_) {
+    // Rely on |translator_| to handle this special case.
+    return translator_.OffsetToRva(offset);
+  }
+  if (cached_unit_ && cached_unit_->CoversOffset(offset))
+    return cached_unit_->OffsetToRvaUnsafe(offset);
+  const AddressTranslator::Unit* unit = translator_.OffsetToUnit(offset);
+  if (!unit)
+    return kInvalidRva;
+  cached_unit_ = unit;
+  return unit->OffsetToRvaUnsafe(offset);
+}
+
+/******** AddressTranslator::RvaToOffsetCache ********/
+
+AddressTranslator::RvaToOffsetCache::RvaToOffsetCache(
+    const AddressTranslator& translator)
+    : translator_(translator) {}
+
+bool AddressTranslator::RvaToOffsetCache::IsValid(rva_t rva) const {
+  if (!cached_unit_ || !cached_unit_->CoversRva(rva)) {
+    const AddressTranslator::Unit* unit = translator_.RvaToUnit(rva);
+    if (!unit)
+      return false;
+    cached_unit_ = unit;
+  }
+  return true;
+}
+
+offset_t AddressTranslator::RvaToOffsetCache::Convert(rva_t rva) const {
+  if (!cached_unit_ || !cached_unit_->CoversRva(rva)) {
+    const AddressTranslator::Unit* unit = translator_.RvaToUnit(rva);
+    if (!unit)
+      return kInvalidOffset;
+    cached_unit_ = unit;
+  }
+  return cached_unit_->RvaToOffsetUnsafe(rva, translator_.fake_offset_begin_);
+}
+
+/******** AddressTranslator ********/
+
+AddressTranslator::AddressTranslator() = default;
+
+AddressTranslator::~AddressTranslator() = default;
+
+AddressTranslator::Status AddressTranslator::Initialize(
+    std::vector<Unit>&& units) {
+  for (Unit& unit : units) {
+    // Check for overflows and fail if found.
+    if (!RangeIsBounded<offset_t>(unit.offset_begin, unit.offset_size,
+                                  kOffsetBound) ||
+        !RangeIsBounded<rva_t>(unit.rva_begin, unit.rva_size, kRvaBound)) {
+      return kErrorOverflow;
+    }
+    // If |rva_size < offset_size|: Just shrink |offset_size| to accommodate.
+    unit.offset_size = std::min(unit.offset_size, unit.rva_size);
+    // Now |rva_size >= offset_size|. Note that |rva_size > offset_size| is
+    // allowed; these lead to dangling RVA.
+  }
+
+  // Remove all empty units.
+  units.erase(std::remove_if(units.begin(), units.end(),
+                             [](const Unit& unit) { return unit.IsEmpty(); }),
+              units.end());
+
+  // Sort |units| by RVA, then uniquefy.
+  std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
+    return std::tie(a.rva_begin, a.rva_size) <
+           std::tie(b.rva_begin, b.rva_size);
+  });
+  units.erase(std::unique(units.begin(), units.end()), units.end());
+
+  // Scan for RVA range overlaps, validate, and merge wherever possible.
+  if (units.size() > 1) {
+    // Traverse with two iterators: |slow| stays behind and modifies Units that
+    // absorb all overlapping (or tangent if suitable) Units; |fast| explores
+    // new Units as candidates for consistency checks and potential merge into
+    // |slow|.
+    auto slow = units.begin();
+
+    // All |it| with |slow| < |it| < |fast| contain garbage.
+    for (auto fast = slow + 1; fast != units.end(); ++fast) {
+      // Comment notation: S = slow offset, F = fast offset, O = overlap offset,
+      // s = slow RVA, f = fast RVA, o = overlap RVA.
+      DCHECK_GE(fast->rva_begin, slow->rva_begin);
+      if (slow->rva_end() < fast->rva_begin) {
+        // ..ssssss..ffffff..: Disjoint: Can advance |slow|.
+        *(++slow) = *fast;
+        continue;
+      }
+
+      // ..ssssffff..: Tangent: Merge is optional.
+      // ..sssooofff.. / ..sssooosss..: Overlap: Merge is required.
+      bool merge_is_optional = slow->rva_end() == fast->rva_begin;
+
+      // Check whether |fast| and |slow| have identical RVA -> offset shift.
+      // If not, then merge cannot be resolved. Examples:
+      // ..ssssffff.. -> ..SSSSFFFF..: Good, can merge.
+      // ..ssssffff.. -> ..SSSS..FFFF..: Non-fatal: don't merge.
+      // ..ssssffff.. -> ..FFFF..SSSS..: Non-fatal: don't merge.
+      // ..ssssffff.. -> ..SSOOFF..: Fatal: Ignore for now (handled later).
+      // ..sssooofff.. -> ..SSSOOOFFF..: Good, can merge.
+      // ..sssooofff.. -> ..SSSSSOFFFFF..: Fatal.
+      // ..sssooofff.. -> ..FFOOOOSS..: Fatal.
+      // ..sssooofff.. -> ..SSSOOOF..: Good, notice |fast| has dangling RVAs.
+      // ..oooooo.. -> ..OOOOOO..: Good, can merge.
+      if (fast->offset_begin < slow->offset_begin ||
+          fast->offset_begin - slow->offset_begin !=
+              fast->rva_begin - slow->rva_begin) {
+        if (merge_is_optional) {
+          *(++slow) = *fast;
+          continue;
+        }
+        return kErrorBadOverlap;
+      }
+
+      // Check whether dangling RVAs (if they exist) are consistent. Examples:
+      // ..sssooofff.. -> ..SSSOOOF..: Good, can merge.
+      // ..sssooosss.. -> ..SSSOOOS..: Good, can merge.
+      // ..sssooofff.. -> ..SSSOO..: Good, can merge.
+      // ..sssooofff.. -> ..SSSOFFF..: Fatal.
+      // ..sssooosss.. -> ..SSSOOFFFF..: Fatal.
+      // ..oooooo.. -> ..OOO..: Good, can merge.
+      // Idea of check: Suppose |fast| has dangling RVA, then
+      // |[fast->rva_start, fast->rva_start + fast->offset_start)| ->
+      // |[fast->offset_start, **fast->offset_end()**)|, with remaining RVA
+      // mapping to fake offsets. This means |fast->offset_end()| must be >=
+      // |slow->offset_end()|, and failure to do so resluts in error. The
+      // argument for |slow| havng dangling RVA is symmetric.
+      if ((fast->HasDanglingRva() && fast->offset_end() < slow->offset_end()) ||
+          (slow->HasDanglingRva() && slow->offset_end() < fast->offset_end())) {
+        if (merge_is_optional) {
+          *(++slow) = *fast;
+          continue;
+        }
+        return kErrorBadOverlapDanglingRva;
+      }
+
+      // Merge |fast| into |slow|.
+      slow->rva_size =
+          std::max(slow->rva_size, fast->rva_end() - slow->rva_begin);
+      slow->offset_size =
+          std::max(slow->offset_size, fast->offset_end() - slow->offset_begin);
+    }
+    ++slow;
+    units.erase(slow, units.end());
+  }
+
+  // After resolving RVA overlaps, any offset overlap would imply error.
+  std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
+    return a.offset_begin < b.offset_begin;
+  });
+
+  if (units.size() > 1) {
+    auto previous = units.begin();
+    for (auto current = previous + 1; current != units.end(); ++current) {
+      if (previous->offset_end() > current->offset_begin)
+        return kErrorBadOverlap;
+      previous = current;
+    }
+  }
+
+  // For to fake offset heuristics: Compute exclusive upper bounds for offsets
+  // and RVAs.
+  offset_t offset_bound = 0;
+  rva_t rva_bound = 0;
+  for (const Unit& unit : units) {
+    offset_bound = std::max(offset_bound, unit.offset_end());
+    rva_bound = std::max(rva_bound, unit.rva_end());
+  }
+
+  // Compute pessimistic range and see if it still fits within space of valid
+  // offsets. This limits image size to one half of |kOffsetBound|, and is a
+  // main drawback for the current heuristic to convert dangling RVA to fake
+  // offsets.
+  if (!RangeIsBounded(offset_bound, rva_bound, kOffsetBound))
+    return kErrorFakeOffsetBeginTooLarge;
+
+  // Success. Store results. |units| is currently sorted by offset, so assign.
+  units_sorted_by_offset_.assign(units.begin(), units.end());
+
+  // Sort |units| by RVA, and just store it directly
+  std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
+    return a.rva_begin < b.rva_begin;
+  });
+  units_sorted_by_rva_ = std::move(units);
+
+  fake_offset_begin_ = offset_bound;
+  return kSuccess;
+}
+
+rva_t AddressTranslator::OffsetToRva(offset_t offset) const {
+  if (offset >= fake_offset_begin_) {
+    // Handle dangling RVA: First shift it to regular RVA space.
+    rva_t rva = offset - fake_offset_begin_;
+    // If result is indeed a dangling RVA, return it; else return |kInvalidRva|.
+    const Unit* unit = RvaToUnit(rva);
+    return (unit && unit->HasDanglingRva() && unit->CoversDanglingRva(rva))
+               ? rva
+               : kInvalidRva;
+  }
+  const Unit* unit = OffsetToUnit(offset);
+  return unit ? unit->OffsetToRvaUnsafe(offset) : kInvalidRva;
+}
+
+offset_t AddressTranslator::RvaToOffset(rva_t rva) const {
+  const Unit* unit = RvaToUnit(rva);
+  // This also handles dangling RVA.
+  return unit ? unit->RvaToOffsetUnsafe(rva, fake_offset_begin_)
+              : kInvalidOffset;
+}
+
+const AddressTranslator::Unit* AddressTranslator::OffsetToUnit(
+    offset_t offset) const {
+  // Finds first Unit with |offset_begin| > |offset|, rewind by 1 to find the
+  // last Unit with |offset_begin| >= |offset| (if it exists).
+  auto it = std::upper_bound(
+      units_sorted_by_offset_.begin(), units_sorted_by_offset_.end(), offset,
+      [](offset_t a, const Unit& b) { return a < b.offset_begin; });
+  if (it == units_sorted_by_offset_.begin())
+    return nullptr;
+  --it;
+  return it->CoversOffset(offset) ? &(*it) : nullptr;
+}
+
+const AddressTranslator::Unit* AddressTranslator::RvaToUnit(rva_t rva) const {
+  auto it = std::upper_bound(
+      units_sorted_by_rva_.begin(), units_sorted_by_rva_.end(), rva,
+      [](rva_t a, const Unit& b) { return a < b.rva_begin; });
+  if (it == units_sorted_by_rva_.begin())
+    return nullptr;
+  --it;
+  return it->CoversRva(rva) ? &(*it) : nullptr;
+}
+
+}  // namespace zucchini