blob: 79e7ba6c7ee7b36fbf1cb2b4c4a6e404a660521a [file] [log] [blame]
// 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