Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 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 | |
| 5 | #include "components/zucchini/rel32_finder.h" |
| 6 | |
| 7 | #include <algorithm> |
| 8 | |
Etienne Pierre-doray | 186ef14 | 2018-09-11 13:40:46 +0000 | [diff] [blame] | 9 | #include "base/numerics/safe_conversions.h" |
| 10 | |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 11 | namespace zucchini { |
| 12 | |
| 13 | /******** Abs32GapFinder ********/ |
| 14 | |
| 15 | Abs32GapFinder::Abs32GapFinder(ConstBufferView image, |
| 16 | ConstBufferView region, |
| 17 | const std::vector<offset_t>& abs32_locations, |
| 18 | size_t abs32_width) |
| 19 | : base_(image.begin()), |
| 20 | region_end_(region.end()), |
| 21 | abs32_end_(abs32_locations.end()), |
| 22 | abs32_width_(abs32_width) { |
| 23 | DCHECK_GT(abs32_width, size_t(0)); |
| 24 | DCHECK_GE(region.begin(), image.begin()); |
| 25 | DCHECK_LE(region.end(), image.end()); |
| 26 | |
Etienne Pierre-doray | 186ef14 | 2018-09-11 13:40:46 +0000 | [diff] [blame] | 27 | const offset_t begin_offset = |
| 28 | base::checked_cast<offset_t>(region.begin() - image.begin()); |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 29 | // Find the first |abs32_cur_| with |*abs32_cur_ >= begin_offset|. |
| 30 | abs32_cur_ = std::lower_bound(abs32_locations.begin(), abs32_locations.end(), |
| 31 | begin_offset); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 32 | |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 33 | // Find lower boundary, accounting for the possibility that |abs32_cur_[-1]| |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 34 | // may straddle across |region.begin()|. |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 35 | cur_lo_ = region.begin(); |
| 36 | if (abs32_cur_ > abs32_locations.begin()) |
| 37 | cur_lo_ = std::max(cur_lo_, image.begin() + abs32_cur_[-1] + abs32_width_); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 38 | } |
| 39 | |
| 40 | Abs32GapFinder::~Abs32GapFinder() = default; |
| 41 | |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 42 | bool Abs32GapFinder::FindNext() { |
| 43 | // Iterate over |[abs32_cur_, abs32_end_)| and emit segments. |
| 44 | while (abs32_cur_ != abs32_end_ && base_ + *abs32_cur_ < region_end_) { |
| 45 | ConstBufferView::const_iterator hi = base_ + *abs32_cur_; |
| 46 | gap_ = ConstBufferView::FromRange(cur_lo_, hi); |
| 47 | cur_lo_ = hi + abs32_width_; |
| 48 | ++abs32_cur_; |
| 49 | if (!gap_.empty()) |
| 50 | return true; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 51 | } |
| 52 | // Emit final segment. |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 53 | if (cur_lo_ < region_end_) { |
| 54 | gap_ = ConstBufferView::FromRange(cur_lo_, region_end_); |
| 55 | cur_lo_ = region_end_; |
| 56 | return true; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 57 | } |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 58 | return false; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 59 | } |
| 60 | |
| 61 | /******** Rel32Finder ********/ |
| 62 | |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 63 | Rel32Finder::Rel32Finder(ConstBufferView image, |
| 64 | const AddressTranslator& translator) |
| 65 | : image_(image), offset_to_rva_(translator) {} |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 66 | |
| 67 | Rel32Finder::~Rel32Finder() = default; |
| 68 | |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 69 | void Rel32Finder::SetRegion(ConstBufferView region) { |
| 70 | region_ = region; |
| 71 | accept_it_ = region.begin(); |
| 72 | } |
| 73 | |
| 74 | bool Rel32Finder::FindNext() { |
| 75 | NextIterators next_iters = Scan(region_); |
| 76 | if (next_iters.reject == nullptr) { |
| 77 | region_.seek(region_.end()); |
| 78 | return false; |
| 79 | } |
| 80 | region_.seek(next_iters.reject); |
| 81 | accept_it_ = next_iters.accept; |
| 82 | DCHECK_GE(accept_it_, region_.begin()); |
| 83 | DCHECK_LE(accept_it_, region_.end()); |
| 84 | return true; |
| 85 | } |
| 86 | |
| 87 | void Rel32Finder::Accept() { |
| 88 | region_.seek(accept_it_); |
| 89 | } |
| 90 | |
| 91 | /******** Rel32FinderIntel ********/ |
| 92 | |
| 93 | Rel32Finder::NextIterators Rel32FinderIntel::SetResult( |
| 94 | ConstBufferView::const_iterator cursor, |
| 95 | uint32_t opcode_size, |
| 96 | bool can_point_outside_section) { |
Samuel Huang | 1cec5a7 | 2021-06-01 18:29:53 +0000 | [diff] [blame] | 97 | offset_t location = |
| 98 | base::checked_cast<offset_t>((cursor + opcode_size) - image_.begin()); |
| 99 | rva_t location_rva = offset_to_rva_.Convert(location); |
| 100 | DCHECK_NE(location_rva, kInvalidRva); |
| 101 | rva_t target_rva = location_rva + 4 + image_.read<uint32_t>(location); |
| 102 | rel32_ = {location, target_rva, can_point_outside_section}; |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 103 | return {cursor + 1, cursor + (opcode_size + 4)}; |
| 104 | } |
| 105 | |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 106 | /******** Rel32FinderX86 ********/ |
| 107 | |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 108 | Rel32Finder::NextIterators Rel32FinderX86::Scan(ConstBufferView region) { |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 109 | ConstBufferView::const_iterator cursor = region.begin(); |
| 110 | while (cursor < region.end()) { |
| 111 | // Heuristic rel32 detection by looking for opcodes that use them. |
| 112 | if (cursor + 5 <= region.end()) { |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 113 | if (cursor[0] == 0xE8 || cursor[0] == 0xE9) // JMP rel32; CALL rel32 |
| 114 | return SetResult(cursor, 1, false); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 115 | } |
| 116 | if (cursor + 6 <= region.end()) { |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 117 | if (cursor[0] == 0x0F && (cursor[1] & 0xF0) == 0x80) // Jcc long form |
| 118 | return SetResult(cursor, 2, false); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 119 | } |
| 120 | ++cursor; |
| 121 | } |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 122 | return {nullptr, nullptr}; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 123 | } |
| 124 | |
| 125 | /******** Rel32FinderX64 ********/ |
| 126 | |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 127 | Rel32Finder::NextIterators Rel32FinderX64::Scan(ConstBufferView region) { |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 128 | ConstBufferView::const_iterator cursor = region.begin(); |
| 129 | while (cursor < region.end()) { |
| 130 | // Heuristic rel32 detection by looking for opcodes that use them. |
| 131 | if (cursor + 5 <= region.end()) { |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 132 | if (cursor[0] == 0xE8 || cursor[0] == 0xE9) // JMP rel32; CALL rel32 |
| 133 | return SetResult(cursor, 1, false); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 134 | } |
| 135 | if (cursor + 6 <= region.end()) { |
| 136 | if (cursor[0] == 0x0F && (cursor[1] & 0xF0) == 0x80) { // Jcc long form |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 137 | return SetResult(cursor, 2, false); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 138 | } else if ((cursor[0] == 0xFF && |
| 139 | (cursor[1] == 0x15 || cursor[1] == 0x25)) || |
| 140 | ((cursor[0] == 0x89 || cursor[0] == 0x8B || |
| 141 | cursor[0] == 0x8D) && |
| 142 | (cursor[1] & 0xC7) == 0x05)) { |
| 143 | // 6-byte instructions: |
| 144 | // [2-byte opcode] [disp32]: |
| 145 | // Opcode |
| 146 | // FF 15: CALL QWORD PTR [rip+disp32] |
| 147 | // FF 25: JMP QWORD PTR [rip+disp32] |
| 148 | // |
| 149 | // [1-byte opcode] [ModR/M] [disp32]: |
| 150 | // Opcode |
| 151 | // 89: MOV DWORD PTR [rip+disp32],reg |
| 152 | // 8B: MOV reg,DWORD PTR [rip+disp32] |
| 153 | // 8D: LEA reg,[rip+disp32] |
| 154 | // ModR/M : MMRRRMMM |
| 155 | // MM = 00 & MMM = 101 => rip+disp32 |
| 156 | // RRR: selects reg operand from [eax|ecx|...|edi] |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 157 | return SetResult(cursor, 2, true); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 158 | } |
| 159 | } |
| 160 | ++cursor; |
| 161 | } |
Samuel Huang | 0047fda | 2019-03-21 20:40:55 +0000 | [diff] [blame] | 162 | return {nullptr, nullptr}; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 163 | } |
| 164 | |
Samuel Huang | fa10b05 | 2021-08-05 16:46:38 +0000 | [diff] [blame] | 165 | /******** Rel32FinderArm ********/ |
| 166 | |
| 167 | template <typename ADDR_TYPE> |
| 168 | Rel32FinderArm<ADDR_TYPE>::Rel32FinderArm(ConstBufferView image, |
| 169 | const AddressTranslator& translator) |
| 170 | : Rel32Finder(image, translator) {} |
| 171 | |
| 172 | template <typename ADDR_TYPE> |
| 173 | Rel32FinderArm<ADDR_TYPE>::~Rel32FinderArm() = default; |
| 174 | |
| 175 | template <typename ADDR_TYPE> |
| 176 | Rel32Finder::NextIterators Rel32FinderArm<ADDR_TYPE>::SetResult( |
| 177 | Result&& result, |
| 178 | ConstBufferView::const_iterator cursor, |
| 179 | int instr_size) { |
| 180 | rel32_ = result; |
| 181 | return {cursor + instr_size, cursor + instr_size}; |
| 182 | } |
| 183 | |
| 184 | // SetResult() for end of scan. |
| 185 | template <typename ADDR_TYPE> |
| 186 | Rel32Finder::NextIterators Rel32FinderArm<ADDR_TYPE>::SetEmptyResult() { |
| 187 | rel32_ = {kInvalidOffset, kInvalidOffset, ADDR_TYPE::ADDR_NONE}; |
| 188 | return {nullptr, nullptr}; |
| 189 | } |
| 190 | |
| 191 | /******** Rel32FinderAArch32 ********/ |
| 192 | |
| 193 | Rel32FinderAArch32::Rel32FinderAArch32(ConstBufferView image, |
| 194 | const AddressTranslator& translator, |
| 195 | bool is_thumb2) |
| 196 | : Rel32FinderArm(image, translator), is_thumb2_(is_thumb2) {} |
| 197 | |
| 198 | Rel32FinderAArch32::~Rel32FinderAArch32() = default; |
| 199 | |
| 200 | Rel32Finder::NextIterators Rel32FinderAArch32::ScanA32(ConstBufferView region) { |
| 201 | // Guard against alignment potentially causing |cursor > region.end()|. |
| 202 | if (region.size() < 4) |
| 203 | return SetEmptyResult(); |
| 204 | ConstBufferView::const_iterator cursor = region.begin(); |
| 205 | cursor += IncrementForAlignCeil4(cursor - image_.begin()); |
| 206 | for (; region.end() - cursor >= 4; cursor += 4) { |
| 207 | offset_t offset = base::checked_cast<offset_t>(cursor - image_.begin()); |
| 208 | AArch32Rel32Translator translator; |
| 209 | rva_t instr_rva = offset_to_rva_.Convert(offset); |
| 210 | uint32_t code32 = translator.FetchArmCode32(image_, offset); |
| 211 | rva_t target_rva = kInvalidRva; |
| 212 | if (translator.ReadA24(instr_rva, code32, &target_rva)) { |
| 213 | return SetResult({offset, target_rva, AArch32Rel32Translator::ADDR_A24}, |
| 214 | cursor, 4); |
| 215 | } |
| 216 | } |
| 217 | return SetEmptyResult(); |
| 218 | } |
| 219 | |
| 220 | Rel32Finder::NextIterators Rel32FinderAArch32::ScanT32(ConstBufferView region) { |
| 221 | // Guard against alignment potentially causing |cursor > region.end()|. |
| 222 | if (region.size() < 2) |
| 223 | return SetEmptyResult(); |
| 224 | ConstBufferView::const_iterator cursor = region.begin(); |
| 225 | cursor += IncrementForAlignCeil2(cursor - image_.begin()); |
| 226 | while (region.end() - cursor >= 2) { |
| 227 | offset_t offset = base::checked_cast<offset_t>(cursor - image_.begin()); |
| 228 | AArch32Rel32Translator translator; |
| 229 | AArch32Rel32Translator::AddrType type = AArch32Rel32Translator::ADDR_NONE; |
| 230 | rva_t instr_rva = offset_to_rva_.Convert(offset); |
| 231 | uint16_t code16 = translator.FetchThumb2Code16(image_, offset); |
| 232 | int instr_size = GetThumb2InstructionSize(code16); |
| 233 | rva_t target_rva = kInvalidRva; |
| 234 | if (instr_size == 2) { // 16-bit THUMB2 instruction. |
| 235 | if (translator.ReadT8(instr_rva, code16, &target_rva)) |
| 236 | type = AArch32Rel32Translator::ADDR_T8; |
| 237 | else if (translator.ReadT11(instr_rva, code16, &target_rva)) |
| 238 | type = AArch32Rel32Translator::ADDR_T11; |
| 239 | } else { // |instr_size == 4|: 32-bit THUMB2 instruction. |
| 240 | if (region.end() - cursor >= 4) { |
| 241 | uint32_t code32 = translator.FetchThumb2Code32(image_, offset); |
| 242 | if (translator.ReadT20(instr_rva, code32, &target_rva)) |
| 243 | type = AArch32Rel32Translator::ADDR_T20; |
| 244 | else if (translator.ReadT24(instr_rva, code32, &target_rva)) |
| 245 | type = AArch32Rel32Translator::ADDR_T24; |
| 246 | } |
| 247 | } |
| 248 | if (type != AArch32Rel32Translator::ADDR_NONE) |
| 249 | return SetResult({offset, target_rva, type}, cursor, instr_size); |
| 250 | cursor += instr_size; |
| 251 | } |
| 252 | return SetEmptyResult(); |
| 253 | } |
| 254 | |
| 255 | Rel32Finder::NextIterators Rel32FinderAArch32::Scan(ConstBufferView region) { |
| 256 | return is_thumb2_ ? ScanT32(region) : ScanA32(region); |
| 257 | } |
| 258 | |
| 259 | /******** Rel32FinderAArch64 ********/ |
| 260 | |
| 261 | Rel32FinderAArch64::Rel32FinderAArch64(ConstBufferView image, |
| 262 | const AddressTranslator& translator) |
| 263 | : Rel32FinderArm(image, translator) {} |
| 264 | |
| 265 | Rel32FinderAArch64::~Rel32FinderAArch64() = default; |
| 266 | |
| 267 | Rel32Finder::NextIterators Rel32FinderAArch64::Scan(ConstBufferView region) { |
| 268 | // Guard against alignment potentially causing |cursor > region.end()|. |
| 269 | if (region.size() < 4) |
| 270 | return SetEmptyResult(); |
| 271 | ConstBufferView::const_iterator cursor = region.begin(); |
| 272 | cursor += IncrementForAlignCeil4(cursor - image_.begin()); |
| 273 | for (; region.end() - cursor >= 4; cursor += 4) { |
| 274 | offset_t offset = base::checked_cast<offset_t>(cursor - image_.begin()); |
| 275 | // For simplicity we assume RVA fits within 32-bits. |
| 276 | AArch64Rel32Translator translator; |
| 277 | AArch64Rel32Translator::AddrType type = AArch64Rel32Translator::ADDR_NONE; |
| 278 | rva_t instr_rva = offset_to_rva_.Convert(offset); |
| 279 | uint32_t code32 = translator.FetchCode32(image_, offset); |
| 280 | rva_t target_rva = kInvalidRva; |
| 281 | if (translator.ReadImmd14(instr_rva, code32, &target_rva)) { |
| 282 | type = AArch64Rel32Translator::ADDR_IMMD14; |
| 283 | } else if (translator.ReadImmd19(instr_rva, code32, &target_rva)) { |
| 284 | type = AArch64Rel32Translator::ADDR_IMMD19; |
| 285 | } else if (translator.ReadImmd26(instr_rva, code32, &target_rva)) { |
| 286 | type = AArch64Rel32Translator::ADDR_IMMD26; |
| 287 | } |
| 288 | if (type != AArch64Rel32Translator::ADDR_NONE) |
| 289 | return SetResult({offset, target_rva, type}, cursor, 4); |
| 290 | } |
| 291 | return SetEmptyResult(); |
| 292 | } |
| 293 | |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 294 | } // namespace zucchini |