address_translator.cc 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258
  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/address_translator.h"
  5. #include <algorithm>
  6. #include <utility>
  7. #include "base/containers/cxx20_erase.h"
  8. namespace zucchini {
  9. /******** AddressTranslator::OffsetToRvaCache ********/
  10. AddressTranslator::OffsetToRvaCache::OffsetToRvaCache(
  11. const AddressTranslator& translator)
  12. : translator_(translator) {}
  13. rva_t AddressTranslator::OffsetToRvaCache::Convert(offset_t offset) const {
  14. if (offset >= translator_.fake_offset_begin_) {
  15. // Rely on |translator_| to handle this special case.
  16. return translator_.OffsetToRva(offset);
  17. }
  18. if (cached_unit_ && cached_unit_->CoversOffset(offset))
  19. return cached_unit_->OffsetToRvaUnsafe(offset);
  20. const AddressTranslator::Unit* unit = translator_.OffsetToUnit(offset);
  21. if (!unit)
  22. return kInvalidRva;
  23. cached_unit_ = unit;
  24. return unit->OffsetToRvaUnsafe(offset);
  25. }
  26. /******** AddressTranslator::RvaToOffsetCache ********/
  27. AddressTranslator::RvaToOffsetCache::RvaToOffsetCache(
  28. const AddressTranslator& translator)
  29. : translator_(translator) {}
  30. bool AddressTranslator::RvaToOffsetCache::IsValid(rva_t rva) const {
  31. if (rva == kInvalidRva)
  32. return false;
  33. if (!cached_unit_ || !cached_unit_->CoversRva(rva)) {
  34. const AddressTranslator::Unit* unit = translator_.RvaToUnit(rva);
  35. if (!unit)
  36. return false;
  37. cached_unit_ = unit;
  38. }
  39. return true;
  40. }
  41. offset_t AddressTranslator::RvaToOffsetCache::Convert(rva_t rva) const {
  42. if (!cached_unit_ || !cached_unit_->CoversRva(rva)) {
  43. const AddressTranslator::Unit* unit = translator_.RvaToUnit(rva);
  44. if (!unit)
  45. return kInvalidOffset;
  46. cached_unit_ = unit;
  47. }
  48. return cached_unit_->RvaToOffsetUnsafe(rva, translator_.fake_offset_begin_);
  49. }
  50. /******** AddressTranslator ********/
  51. AddressTranslator::AddressTranslator() = default;
  52. AddressTranslator::AddressTranslator(AddressTranslator&&) = default;
  53. AddressTranslator::~AddressTranslator() = default;
  54. AddressTranslator::Status AddressTranslator::Initialize(
  55. std::vector<Unit>&& units) {
  56. for (Unit& unit : units) {
  57. // Check for overflows and fail if found.
  58. if (!RangeIsBounded<offset_t>(unit.offset_begin, unit.offset_size,
  59. kOffsetBound) ||
  60. !RangeIsBounded<rva_t>(unit.rva_begin, unit.rva_size, kRvaBound)) {
  61. return kErrorOverflow;
  62. }
  63. // If |rva_size < offset_size|: Just shrink |offset_size| to accommodate.
  64. unit.offset_size = std::min(unit.offset_size, unit.rva_size);
  65. // Now |rva_size >= offset_size|. Note that |rva_size > offset_size| is
  66. // allowed; these lead to dangling RVA.
  67. }
  68. // Remove all empty units.
  69. base::EraseIf(units, [](const Unit& unit) { return unit.IsEmpty(); });
  70. // Sort |units| by RVA, then uniquefy.
  71. std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
  72. return std::tie(a.rva_begin, a.rva_size) <
  73. std::tie(b.rva_begin, b.rva_size);
  74. });
  75. units.erase(std::unique(units.begin(), units.end()), units.end());
  76. // Scan for RVA range overlaps, validate, and merge wherever possible.
  77. if (units.size() > 1) {
  78. // Traverse with two iterators: |slow| stays behind and modifies Units that
  79. // absorb all overlapping (or tangent if suitable) Units; |fast| explores
  80. // new Units as candidates for consistency checks and potential merge into
  81. // |slow|.
  82. auto slow = units.begin();
  83. // All |it| with |slow| < |it| < |fast| contain garbage.
  84. for (auto fast = slow + 1; fast != units.end(); ++fast) {
  85. // Comment notation: S = slow offset, F = fast offset, O = overlap offset,
  86. // s = slow RVA, f = fast RVA, o = overlap RVA.
  87. DCHECK_GE(fast->rva_begin, slow->rva_begin);
  88. if (slow->rva_end() < fast->rva_begin) {
  89. // ..ssssss..ffffff..: Disjoint: Can advance |slow|.
  90. *(++slow) = *fast;
  91. continue;
  92. }
  93. // ..ssssffff..: Tangent: Merge is optional.
  94. // ..sssooofff.. / ..sssooosss..: Overlap: Merge is required.
  95. bool merge_is_optional = slow->rva_end() == fast->rva_begin;
  96. // Check whether |fast| and |slow| have identical RVA -> offset shift.
  97. // If not, then merge cannot be resolved. Examples:
  98. // ..ssssffff.. -> ..SSSSFFFF..: Good, can merge.
  99. // ..ssssffff.. -> ..SSSS..FFFF..: Non-fatal: don't merge.
  100. // ..ssssffff.. -> ..FFFF..SSSS..: Non-fatal: don't merge.
  101. // ..ssssffff.. -> ..SSOOFF..: Fatal: Ignore for now (handled later).
  102. // ..sssooofff.. -> ..SSSOOOFFF..: Good, can merge.
  103. // ..sssooofff.. -> ..SSSSSOFFFFF..: Fatal.
  104. // ..sssooofff.. -> ..FFOOOOSS..: Fatal.
  105. // ..sssooofff.. -> ..SSSOOOF..: Good, notice |fast| has dangling RVAs.
  106. // ..oooooo.. -> ..OOOOOO..: Good, can merge.
  107. if (fast->offset_begin < slow->offset_begin ||
  108. fast->offset_begin - slow->offset_begin !=
  109. fast->rva_begin - slow->rva_begin) {
  110. if (merge_is_optional) {
  111. *(++slow) = *fast;
  112. continue;
  113. }
  114. return kErrorBadOverlap;
  115. }
  116. // Check whether dangling RVAs (if they exist) are consistent. Examples:
  117. // ..sssooofff.. -> ..SSSOOOF..: Good, can merge.
  118. // ..sssooosss.. -> ..SSSOOOS..: Good, can merge.
  119. // ..sssooofff.. -> ..SSSOO..: Good, can merge.
  120. // ..sssooofff.. -> ..SSSOFFF..: Fatal.
  121. // ..sssooosss.. -> ..SSSOOFFFF..: Fatal.
  122. // ..oooooo.. -> ..OOO..: Good, can merge.
  123. // Idea of check: Suppose |fast| has dangling RVA, then
  124. // |[fast->rva_start, fast->rva_start + fast->offset_start)| ->
  125. // |[fast->offset_start, **fast->offset_end()**)|, with remaining RVA
  126. // mapping to fake offsets. This means |fast->offset_end()| must be >=
  127. // |slow->offset_end()|, and failure to do so resluts in error. The
  128. // argument for |slow| havng dangling RVA is symmetric.
  129. if ((fast->HasDanglingRva() && fast->offset_end() < slow->offset_end()) ||
  130. (slow->HasDanglingRva() && slow->offset_end() < fast->offset_end())) {
  131. if (merge_is_optional) {
  132. *(++slow) = *fast;
  133. continue;
  134. }
  135. return kErrorBadOverlapDanglingRva;
  136. }
  137. // Merge |fast| into |slow|.
  138. slow->rva_size =
  139. std::max(slow->rva_size, fast->rva_end() - slow->rva_begin);
  140. slow->offset_size =
  141. std::max(slow->offset_size, fast->offset_end() - slow->offset_begin);
  142. }
  143. ++slow;
  144. units.erase(slow, units.end());
  145. }
  146. // After resolving RVA overlaps, any offset overlap would imply error.
  147. std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
  148. return a.offset_begin < b.offset_begin;
  149. });
  150. if (units.size() > 1) {
  151. auto previous = units.begin();
  152. for (auto current = previous + 1; current != units.end(); ++current) {
  153. if (previous->offset_end() > current->offset_begin)
  154. return kErrorBadOverlap;
  155. previous = current;
  156. }
  157. }
  158. // For to fake offset heuristics: Compute exclusive upper bounds for offsets
  159. // and RVAs.
  160. offset_t offset_bound = 0;
  161. rva_t rva_bound = 0;
  162. for (const Unit& unit : units) {
  163. offset_bound = std::max(offset_bound, unit.offset_end());
  164. rva_bound = std::max(rva_bound, unit.rva_end());
  165. }
  166. // Compute pessimistic range and see if it still fits within space of valid
  167. // offsets. This limits image size to one half of |kOffsetBound|, and is a
  168. // main drawback for the current heuristic to convert dangling RVA to fake
  169. // offsets.
  170. if (!RangeIsBounded(offset_bound, rva_bound, kOffsetBound))
  171. return kErrorFakeOffsetBeginTooLarge;
  172. // Success. Store results. |units| is currently sorted by offset, so assign.
  173. units_sorted_by_offset_.assign(units.begin(), units.end());
  174. // Sort |units| by RVA, and just store it directly
  175. std::sort(units.begin(), units.end(), [](const Unit& a, const Unit& b) {
  176. return a.rva_begin < b.rva_begin;
  177. });
  178. units_sorted_by_rva_ = std::move(units);
  179. fake_offset_begin_ = offset_bound;
  180. return kSuccess;
  181. }
  182. rva_t AddressTranslator::OffsetToRva(offset_t offset) const {
  183. if (offset >= fake_offset_begin_) {
  184. // Handle dangling RVA: First shift it to regular RVA space.
  185. rva_t rva = offset - fake_offset_begin_;
  186. // If result is indeed a dangling RVA, return it; else return |kInvalidRva|.
  187. const Unit* unit = RvaToUnit(rva);
  188. return (unit && unit->HasDanglingRva() && unit->CoversDanglingRva(rva))
  189. ? rva
  190. : kInvalidRva;
  191. }
  192. const Unit* unit = OffsetToUnit(offset);
  193. return unit ? unit->OffsetToRvaUnsafe(offset) : kInvalidRva;
  194. }
  195. offset_t AddressTranslator::RvaToOffset(rva_t rva) const {
  196. const Unit* unit = RvaToUnit(rva);
  197. // This also handles dangling RVA.
  198. return unit ? unit->RvaToOffsetUnsafe(rva, fake_offset_begin_)
  199. : kInvalidOffset;
  200. }
  201. const AddressTranslator::Unit* AddressTranslator::OffsetToUnit(
  202. offset_t offset) const {
  203. // Finds first Unit with |offset_begin| > |offset|, rewind by 1 to find the
  204. // last Unit with |offset_begin| >= |offset| (if it exists).
  205. auto it = std::upper_bound(
  206. units_sorted_by_offset_.begin(), units_sorted_by_offset_.end(), offset,
  207. [](offset_t a, const Unit& b) { return a < b.offset_begin; });
  208. if (it == units_sorted_by_offset_.begin())
  209. return nullptr;
  210. --it;
  211. return it->CoversOffset(offset) ? &(*it) : nullptr;
  212. }
  213. const AddressTranslator::Unit* AddressTranslator::RvaToUnit(rva_t rva) const {
  214. auto it = std::upper_bound(
  215. units_sorted_by_rva_.begin(), units_sorted_by_rva_.end(), rva,
  216. [](rva_t a, const Unit& b) { return a < b.rva_begin; });
  217. if (it == units_sorted_by_rva_.begin())
  218. return nullptr;
  219. --it;
  220. return it->CoversRva(rva) ? &(*it) : nullptr;
  221. }
  222. } // namespace zucchini