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
9 #include "base/numerics/safe_conversions.h"
10
11 namespace zucchini {
12
13 /******** Abs32GapFinder ********/
14
Abs32GapFinder(ConstBufferView image,ConstBufferView region,const std::vector<offset_t> & abs32_locations,size_t abs32_width)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
27 const offset_t begin_offset =
28 base::checked_cast<offset_t>(region.begin() - image.begin());
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);
32
33 // Find lower boundary, accounting for the possibility that |abs32_cur_[-1]|
34 // may straddle across |region.begin()|.
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_);
38 }
39
40 Abs32GapFinder::~Abs32GapFinder() = default;
41
FindNext()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;
51 }
52 // Emit final segment.
53 if (cur_lo_ < region_end_) {
54 gap_ = ConstBufferView::FromRange(cur_lo_, region_end_);
55 cur_lo_ = region_end_;
56 return true;
57 }
58 return false;
59 }
60
61 /******** Rel32Finder ********/
62
Rel32Finder(ConstBufferView image,const AddressTranslator & translator)63 Rel32Finder::Rel32Finder(ConstBufferView image,
64 const AddressTranslator& translator)
65 : image_(image), offset_to_rva_(translator) {}
66
67 Rel32Finder::~Rel32Finder() = default;
68
SetRegion(ConstBufferView region)69 void Rel32Finder::SetRegion(ConstBufferView region) {
70 region_ = region;
71 accept_it_ = region.begin();
72 }
73
FindNext()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
Accept()87 void Rel32Finder::Accept() {
88 region_.seek(accept_it_);
89 }
90
91 /******** Rel32FinderIntel ********/
92
SetResult(ConstBufferView::const_iterator cursor,uint32_t opcode_size,bool can_point_outside_section)93 Rel32Finder::NextIterators Rel32FinderIntel::SetResult(
94 ConstBufferView::const_iterator cursor,
95 uint32_t opcode_size,
96 bool can_point_outside_section) {
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};
103 return {cursor + 1, cursor + (opcode_size + 4)};
104 }
105
106 /******** Rel32FinderX86 ********/
107
Scan(ConstBufferView region)108 Rel32Finder::NextIterators Rel32FinderX86::Scan(ConstBufferView region) {
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()) {
113 if (cursor[0] == 0xE8 || cursor[0] == 0xE9) // JMP rel32; CALL rel32
114 return SetResult(cursor, 1, false);
115 }
116 if (cursor + 6 <= region.end()) {
117 if (cursor[0] == 0x0F && (cursor[1] & 0xF0) == 0x80) // Jcc long form
118 return SetResult(cursor, 2, false);
119 }
120 ++cursor;
121 }
122 return {nullptr, nullptr};
123 }
124
125 /******** Rel32FinderX64 ********/
126
Scan(ConstBufferView region)127 Rel32Finder::NextIterators Rel32FinderX64::Scan(ConstBufferView region) {
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()) {
132 if (cursor[0] == 0xE8 || cursor[0] == 0xE9) // JMP rel32; CALL rel32
133 return SetResult(cursor, 1, false);
134 }
135 if (cursor + 6 <= region.end()) {
136 if (cursor[0] == 0x0F && (cursor[1] & 0xF0) == 0x80) { // Jcc long form
137 return SetResult(cursor, 2, false);
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]
157 return SetResult(cursor, 2, true);
158 }
159 }
160 ++cursor;
161 }
162 return {nullptr, nullptr};
163 }
164
165 /******** Rel32FinderArm ********/
166
167 template <typename ADDR_TYPE>
Rel32FinderArm(ConstBufferView image,const AddressTranslator & translator)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>
SetResult(Result && result,ConstBufferView::const_iterator cursor,int instr_size)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>
SetEmptyResult()186 Rel32Finder::NextIterators Rel32FinderArm<ADDR_TYPE>::SetEmptyResult() {
187 rel32_ = {kInvalidOffset, kInvalidOffset, ADDR_TYPE::ADDR_NONE};
188 return {nullptr, nullptr};
189 }
190
191 /******** Rel32FinderAArch32 ********/
192
Rel32FinderAArch32(ConstBufferView image,const AddressTranslator & translator,bool is_thumb2)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
ScanA32(ConstBufferView region)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
ScanT32(ConstBufferView region)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
Scan(ConstBufferView region)255 Rel32Finder::NextIterators Rel32FinderAArch32::Scan(ConstBufferView region) {
256 return is_thumb2_ ? ScanT32(region) : ScanA32(region);
257 }
258
259 /******** Rel32FinderAArch64 ********/
260
Rel32FinderAArch64(ConstBufferView image,const AddressTranslator & translator)261 Rel32FinderAArch64::Rel32FinderAArch64(ConstBufferView image,
262 const AddressTranslator& translator)
263 : Rel32FinderArm(image, translator) {}
264
265 Rel32FinderAArch64::~Rel32FinderAArch64() = default;
266
Scan(ConstBufferView region)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
294 } // namespace zucchini
295