1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <stdint.h>
18
19 #include <unwindstack/DwarfError.h>
20 #include <unwindstack/DwarfLocation.h>
21 #include <unwindstack/DwarfMemory.h>
22 #include <unwindstack/DwarfSection.h>
23 #include <unwindstack/DwarfStructs.h>
24 #include <unwindstack/Elf.h>
25 #include <unwindstack/Log.h>
26 #include <unwindstack/Memory.h>
27 #include <unwindstack/Regs.h>
28
29 #include "DwarfCfa.h"
30 #include "DwarfDebugFrame.h"
31 #include "DwarfEhFrame.h"
32 #include "DwarfEncoding.h"
33 #include "DwarfOp.h"
34 #include "RegsInfo.h"
35
36 namespace unwindstack {
37
DwarfSection(Memory * memory)38 DwarfSection::DwarfSection(Memory* memory) : memory_(memory) {}
39
Step(uint64_t pc,Regs * regs,Memory * process_memory,bool * finished,bool * is_signal_frame)40 bool DwarfSection::Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished,
41 bool* is_signal_frame) {
42 // Lookup the pc in the cache.
43 auto it = loc_regs_.upper_bound(pc);
44 if (it == loc_regs_.end() || pc < it->second.pc_start) {
45 last_error_.code = DWARF_ERROR_NONE;
46 const DwarfFde* fde = GetFdeFromPc(pc);
47 if (fde == nullptr || fde->cie == nullptr) {
48 last_error_.code = DWARF_ERROR_ILLEGAL_STATE;
49 return false;
50 }
51
52 // Now get the location information for this pc.
53 DwarfLocations loc_regs;
54 if (!GetCfaLocationInfo(pc, fde, &loc_regs, regs->Arch())) {
55 return false;
56 }
57 loc_regs.cie = fde->cie;
58
59 // Store it in the cache.
60 it = loc_regs_.emplace(loc_regs.pc_end, std::move(loc_regs)).first;
61 }
62
63 *is_signal_frame = it->second.cie->is_signal_frame;
64
65 // Now eval the actual registers.
66 return Eval(it->second.cie, process_memory, it->second, regs, finished);
67 }
68
69 template <typename AddressType>
GetCieFromOffset(uint64_t offset)70 const DwarfCie* DwarfSectionImpl<AddressType>::GetCieFromOffset(uint64_t offset) {
71 auto cie_entry = cie_entries_.find(offset);
72 if (cie_entry != cie_entries_.end()) {
73 return &cie_entry->second;
74 }
75 DwarfCie* cie = &cie_entries_[offset];
76 memory_.set_data_offset(entries_offset_);
77 memory_.set_cur_offset(offset);
78 if (!FillInCieHeader(cie) || !FillInCie(cie)) {
79 // Erase the cached entry.
80 cie_entries_.erase(offset);
81 return nullptr;
82 }
83 return cie;
84 }
85
86 template <typename AddressType>
FillInCieHeader(DwarfCie * cie)87 bool DwarfSectionImpl<AddressType>::FillInCieHeader(DwarfCie* cie) {
88 cie->lsda_encoding = DW_EH_PE_omit;
89 uint32_t length32;
90 if (!memory_.ReadBytes(&length32, sizeof(length32))) {
91 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
92 last_error_.address = memory_.cur_offset();
93 return false;
94 }
95 if (length32 == static_cast<uint32_t>(-1)) {
96 // 64 bit Cie
97 uint64_t length64;
98 if (!memory_.ReadBytes(&length64, sizeof(length64))) {
99 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
100 last_error_.address = memory_.cur_offset();
101 return false;
102 }
103
104 cie->cfa_instructions_end = memory_.cur_offset() + length64;
105 // TODO(b/192012848): This is wrong. We need to propagate pointer size here.
106 cie->fde_address_encoding = DW_EH_PE_udata8;
107
108 uint64_t cie_id;
109 if (!memory_.ReadBytes(&cie_id, sizeof(cie_id))) {
110 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
111 last_error_.address = memory_.cur_offset();
112 return false;
113 }
114 if (cie_id != cie64_value_) {
115 // This is not a Cie, something has gone horribly wrong.
116 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
117 return false;
118 }
119 } else {
120 // 32 bit Cie
121 cie->cfa_instructions_end = memory_.cur_offset() + length32;
122 // TODO(b/192012848): This is wrong. We need to propagate pointer size here.
123 cie->fde_address_encoding = DW_EH_PE_udata4;
124
125 uint32_t cie_id;
126 if (!memory_.ReadBytes(&cie_id, sizeof(cie_id))) {
127 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
128 last_error_.address = memory_.cur_offset();
129 return false;
130 }
131 if (cie_id != cie32_value_) {
132 // This is not a Cie, something has gone horribly wrong.
133 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
134 return false;
135 }
136 }
137 return true;
138 }
139
140 template <typename AddressType>
FillInCie(DwarfCie * cie)141 bool DwarfSectionImpl<AddressType>::FillInCie(DwarfCie* cie) {
142 if (!memory_.ReadBytes(&cie->version, sizeof(cie->version))) {
143 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
144 last_error_.address = memory_.cur_offset();
145 return false;
146 }
147
148 if (cie->version != 1 && cie->version != 3 && cie->version != 4 && cie->version != 5) {
149 // Unrecognized version.
150 last_error_.code = DWARF_ERROR_UNSUPPORTED_VERSION;
151 return false;
152 }
153
154 // Read the augmentation string.
155 char aug_value;
156 do {
157 if (!memory_.ReadBytes(&aug_value, 1)) {
158 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
159 last_error_.address = memory_.cur_offset();
160 return false;
161 }
162 cie->augmentation_string.push_back(aug_value);
163 } while (aug_value != '\0');
164
165 if (cie->version == 4 || cie->version == 5) {
166 char address_size;
167 if (!memory_.ReadBytes(&address_size, 1)) {
168 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
169 last_error_.address = memory_.cur_offset();
170 return false;
171 }
172 cie->fde_address_encoding = address_size == 8 ? DW_EH_PE_udata8 : DW_EH_PE_udata4;
173
174 // Segment Size
175 if (!memory_.ReadBytes(&cie->segment_size, 1)) {
176 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
177 last_error_.address = memory_.cur_offset();
178 return false;
179 }
180 }
181
182 // Code Alignment Factor
183 if (!memory_.ReadULEB128(&cie->code_alignment_factor)) {
184 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
185 last_error_.address = memory_.cur_offset();
186 return false;
187 }
188
189 // Data Alignment Factor
190 if (!memory_.ReadSLEB128(&cie->data_alignment_factor)) {
191 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
192 last_error_.address = memory_.cur_offset();
193 return false;
194 }
195
196 if (cie->version == 1) {
197 // Return Address is a single byte.
198 uint8_t return_address_register;
199 if (!memory_.ReadBytes(&return_address_register, 1)) {
200 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
201 last_error_.address = memory_.cur_offset();
202 return false;
203 }
204 cie->return_address_register = return_address_register;
205 } else if (!memory_.ReadULEB128(&cie->return_address_register)) {
206 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
207 last_error_.address = memory_.cur_offset();
208 return false;
209 }
210
211 if (cie->augmentation_string[0] != 'z') {
212 cie->cfa_instructions_offset = memory_.cur_offset();
213 return true;
214 }
215
216 uint64_t aug_length;
217 if (!memory_.ReadULEB128(&aug_length)) {
218 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
219 last_error_.address = memory_.cur_offset();
220 return false;
221 }
222 cie->cfa_instructions_offset = memory_.cur_offset() + aug_length;
223
224 for (size_t i = 1; i < cie->augmentation_string.size(); i++) {
225 switch (cie->augmentation_string[i]) {
226 case 'L':
227 if (!memory_.ReadBytes(&cie->lsda_encoding, 1)) {
228 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
229 last_error_.address = memory_.cur_offset();
230 return false;
231 }
232 break;
233 case 'P': {
234 uint8_t encoding;
235 if (!memory_.ReadBytes(&encoding, 1)) {
236 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
237 last_error_.address = memory_.cur_offset();
238 return false;
239 }
240 memory_.set_pc_offset(pc_offset_);
241 if (!memory_.ReadEncodedValue<AddressType>(encoding, &cie->personality_handler)) {
242 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
243 last_error_.address = memory_.cur_offset();
244 return false;
245 }
246 } break;
247 case 'R':
248 if (!memory_.ReadBytes(&cie->fde_address_encoding, 1)) {
249 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
250 last_error_.address = memory_.cur_offset();
251 return false;
252 }
253 break;
254 case 'S':
255 cie->is_signal_frame = true;
256 break;
257 }
258 }
259 return true;
260 }
261
262 template <typename AddressType>
GetFdeFromOffset(uint64_t offset)263 const DwarfFde* DwarfSectionImpl<AddressType>::GetFdeFromOffset(uint64_t offset) {
264 auto fde_entry = fde_entries_.find(offset);
265 if (fde_entry != fde_entries_.end()) {
266 return &fde_entry->second;
267 }
268 DwarfFde* fde = &fde_entries_[offset];
269 memory_.set_data_offset(entries_offset_);
270 memory_.set_cur_offset(offset);
271 if (!FillInFdeHeader(fde) || !FillInFde(fde)) {
272 fde_entries_.erase(offset);
273 return nullptr;
274 }
275 return fde;
276 }
277
278 template <typename AddressType>
FillInFdeHeader(DwarfFde * fde)279 bool DwarfSectionImpl<AddressType>::FillInFdeHeader(DwarfFde* fde) {
280 uint32_t length32;
281 if (!memory_.ReadBytes(&length32, sizeof(length32))) {
282 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
283 last_error_.address = memory_.cur_offset();
284 return false;
285 }
286
287 if (length32 == static_cast<uint32_t>(-1)) {
288 // 64 bit Fde.
289 uint64_t length64;
290 if (!memory_.ReadBytes(&length64, sizeof(length64))) {
291 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
292 last_error_.address = memory_.cur_offset();
293 return false;
294 }
295 fde->cfa_instructions_end = memory_.cur_offset() + length64;
296
297 uint64_t value64;
298 if (!memory_.ReadBytes(&value64, sizeof(value64))) {
299 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
300 last_error_.address = memory_.cur_offset();
301 return false;
302 }
303 if (value64 == cie64_value_) {
304 // This is a Cie, this means something has gone wrong.
305 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
306 return false;
307 }
308
309 // Get the Cie pointer, which is necessary to properly read the rest of
310 // of the Fde information.
311 fde->cie_offset = GetCieOffsetFromFde64(value64);
312 } else {
313 // 32 bit Fde.
314 fde->cfa_instructions_end = memory_.cur_offset() + length32;
315
316 uint32_t value32;
317 if (!memory_.ReadBytes(&value32, sizeof(value32))) {
318 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
319 last_error_.address = memory_.cur_offset();
320 return false;
321 }
322 if (value32 == cie32_value_) {
323 // This is a Cie, this means something has gone wrong.
324 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
325 return false;
326 }
327
328 // Get the Cie pointer, which is necessary to properly read the rest of
329 // of the Fde information.
330 fde->cie_offset = GetCieOffsetFromFde32(value32);
331 }
332 return true;
333 }
334
335 template <typename AddressType>
FillInFde(DwarfFde * fde)336 bool DwarfSectionImpl<AddressType>::FillInFde(DwarfFde* fde) {
337 uint64_t cur_offset = memory_.cur_offset();
338
339 const DwarfCie* cie = GetCieFromOffset(fde->cie_offset);
340 if (cie == nullptr) {
341 return false;
342 }
343 fde->cie = cie;
344
345 if (cie->segment_size != 0) {
346 // Skip over the segment selector for now.
347 cur_offset += cie->segment_size;
348 }
349 memory_.set_cur_offset(cur_offset);
350
351 // The load bias only applies to the start.
352 memory_.set_pc_offset(section_bias_);
353 bool valid = memory_.ReadEncodedValue<AddressType>(cie->fde_address_encoding, &fde->pc_start);
354 fde->pc_start = AdjustPcFromFde(fde->pc_start);
355
356 memory_.set_pc_offset(0);
357 if (!valid || !memory_.ReadEncodedValue<AddressType>(cie->fde_address_encoding, &fde->pc_end)) {
358 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
359 last_error_.address = memory_.cur_offset();
360 return false;
361 }
362 fde->pc_end += fde->pc_start;
363
364 if (cie->augmentation_string.size() > 0 && cie->augmentation_string[0] == 'z') {
365 // Augmentation Size
366 uint64_t aug_length;
367 if (!memory_.ReadULEB128(&aug_length)) {
368 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
369 last_error_.address = memory_.cur_offset();
370 return false;
371 }
372 uint64_t cur_offset = memory_.cur_offset();
373
374 memory_.set_pc_offset(pc_offset_);
375 if (!memory_.ReadEncodedValue<AddressType>(cie->lsda_encoding, &fde->lsda_address)) {
376 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
377 last_error_.address = memory_.cur_offset();
378 return false;
379 }
380
381 // Set our position to after all of the augmentation data.
382 memory_.set_cur_offset(cur_offset + aug_length);
383 }
384 fde->cfa_instructions_offset = memory_.cur_offset();
385
386 return true;
387 }
388
389 template <typename AddressType>
EvalExpression(const DwarfLocation & loc,Memory * regular_memory,AddressType * value,RegsInfo<AddressType> * regs_info,bool * is_dex_pc)390 bool DwarfSectionImpl<AddressType>::EvalExpression(const DwarfLocation& loc, Memory* regular_memory,
391 AddressType* value,
392 RegsInfo<AddressType>* regs_info,
393 bool* is_dex_pc) {
394 DwarfOp<AddressType> op(&memory_, regular_memory);
395 op.set_regs_info(regs_info);
396
397 // Need to evaluate the op data.
398 uint64_t end = loc.values[1];
399 uint64_t start = end - loc.values[0];
400 if (!op.Eval(start, end)) {
401 last_error_ = op.last_error();
402 return false;
403 }
404 if (op.StackSize() == 0) {
405 last_error_.code = DWARF_ERROR_ILLEGAL_STATE;
406 return false;
407 }
408 // We don't support an expression that evaluates to a register number.
409 if (op.is_register()) {
410 last_error_.code = DWARF_ERROR_NOT_IMPLEMENTED;
411 return false;
412 }
413 *value = op.StackAt(0);
414 if (is_dex_pc != nullptr && op.dex_pc_set()) {
415 *is_dex_pc = true;
416 }
417 return true;
418 }
419
420 template <typename AddressType>
421 struct EvalInfo {
422 const DwarfLocations* loc_regs;
423 const DwarfCie* cie;
424 Memory* regular_memory;
425 AddressType cfa;
426 bool return_address_undefined = false;
427 RegsInfo<AddressType> regs_info;
428 };
429
430 template <typename AddressType>
EvalRegister(const DwarfLocation * loc,uint32_t reg,AddressType * reg_ptr,void * info)431 bool DwarfSectionImpl<AddressType>::EvalRegister(const DwarfLocation* loc, uint32_t reg,
432 AddressType* reg_ptr, void* info) {
433 EvalInfo<AddressType>* eval_info = reinterpret_cast<EvalInfo<AddressType>*>(info);
434 Memory* regular_memory = eval_info->regular_memory;
435 switch (loc->type) {
436 case DWARF_LOCATION_OFFSET:
437 if (!regular_memory->ReadFully(eval_info->cfa + loc->values[0], reg_ptr, sizeof(AddressType))) {
438 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
439 last_error_.address = eval_info->cfa + loc->values[0];
440 return false;
441 }
442 break;
443 case DWARF_LOCATION_VAL_OFFSET:
444 *reg_ptr = eval_info->cfa + loc->values[0];
445 break;
446 case DWARF_LOCATION_REGISTER: {
447 uint32_t cur_reg = loc->values[0];
448 if (cur_reg >= eval_info->regs_info.Total()) {
449 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
450 return false;
451 }
452 *reg_ptr = eval_info->regs_info.Get(cur_reg) + loc->values[1];
453 break;
454 }
455 case DWARF_LOCATION_EXPRESSION:
456 case DWARF_LOCATION_VAL_EXPRESSION: {
457 AddressType value;
458 bool is_dex_pc = false;
459 if (!EvalExpression(*loc, regular_memory, &value, &eval_info->regs_info, &is_dex_pc)) {
460 return false;
461 }
462 if (loc->type == DWARF_LOCATION_EXPRESSION) {
463 if (!regular_memory->ReadFully(value, reg_ptr, sizeof(AddressType))) {
464 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
465 last_error_.address = value;
466 return false;
467 }
468 } else {
469 *reg_ptr = value;
470 if (is_dex_pc) {
471 eval_info->regs_info.regs->set_dex_pc(value);
472 }
473 }
474 break;
475 }
476 case DWARF_LOCATION_UNDEFINED:
477 if (reg == eval_info->cie->return_address_register) {
478 eval_info->return_address_undefined = true;
479 }
480 break;
481 case DWARF_LOCATION_PSEUDO_REGISTER:
482 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
483 return false;
484 default:
485 break;
486 }
487
488 return true;
489 }
490
491 template <typename AddressType>
Eval(const DwarfCie * cie,Memory * regular_memory,const DwarfLocations & loc_regs,Regs * regs,bool * finished)492 bool DwarfSectionImpl<AddressType>::Eval(const DwarfCie* cie, Memory* regular_memory,
493 const DwarfLocations& loc_regs, Regs* regs,
494 bool* finished) {
495 RegsImpl<AddressType>* cur_regs = reinterpret_cast<RegsImpl<AddressType>*>(regs);
496 if (cie->return_address_register >= cur_regs->total_regs()) {
497 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
498 return false;
499 }
500
501 // Get the cfa value;
502 auto cfa_entry = loc_regs.find(CFA_REG);
503 if (cfa_entry == loc_regs.end()) {
504 last_error_.code = DWARF_ERROR_CFA_NOT_DEFINED;
505 return false;
506 }
507
508 // Always set the dex pc to zero when evaluating.
509 cur_regs->set_dex_pc(0);
510
511 // Reset necessary pseudo registers before evaluation.
512 // This is needed for ARM64, for example.
513 regs->ResetPseudoRegisters();
514
515 EvalInfo<AddressType> eval_info{.loc_regs = &loc_regs,
516 .cie = cie,
517 .regular_memory = regular_memory,
518 .regs_info = RegsInfo<AddressType>(cur_regs)};
519 const DwarfLocation* loc = &cfa_entry->second;
520 // Only a few location types are valid for the cfa.
521 switch (loc->type) {
522 case DWARF_LOCATION_REGISTER:
523 if (loc->values[0] >= cur_regs->total_regs()) {
524 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
525 return false;
526 }
527 eval_info.cfa = (*cur_regs)[loc->values[0]];
528 eval_info.cfa += loc->values[1];
529 break;
530 case DWARF_LOCATION_VAL_EXPRESSION: {
531 AddressType value;
532 if (!EvalExpression(*loc, regular_memory, &value, &eval_info.regs_info, nullptr)) {
533 return false;
534 }
535 // There is only one type of valid expression for CFA evaluation.
536 eval_info.cfa = value;
537 break;
538 }
539 default:
540 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
541 return false;
542 }
543
544 for (const auto& entry : loc_regs) {
545 uint32_t reg = entry.first;
546 // Already handled the CFA register.
547 if (reg == CFA_REG) continue;
548
549 AddressType* reg_ptr;
550 if (reg >= cur_regs->total_regs()) {
551 if (entry.second.type != DWARF_LOCATION_PSEUDO_REGISTER) {
552 // Skip this unknown register.
553 continue;
554 }
555 if (!eval_info.regs_info.regs->SetPseudoRegister(reg, entry.second.values[0])) {
556 last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
557 return false;
558 }
559 } else {
560 reg_ptr = eval_info.regs_info.Save(reg);
561 if (!EvalRegister(&entry.second, reg, reg_ptr, &eval_info)) {
562 return false;
563 }
564 }
565 }
566
567 // Find the return address location.
568 if (eval_info.return_address_undefined) {
569 cur_regs->set_pc(0);
570 } else {
571 cur_regs->set_pc((*cur_regs)[cie->return_address_register]);
572 }
573
574 // If the pc was set to zero, consider this the final frame. Exception: if
575 // this is the sigreturn frame, then we want to try to recover the real PC
576 // using the return address (from LR or the stack), so keep going.
577 *finished = (cur_regs->pc() == 0 && !cie->is_signal_frame) ? true : false;
578
579 cur_regs->set_sp(eval_info.cfa);
580
581 return true;
582 }
583
584 template <typename AddressType>
GetCfaLocationInfo(uint64_t pc,const DwarfFde * fde,DwarfLocations * loc_regs,ArchEnum arch)585 bool DwarfSectionImpl<AddressType>::GetCfaLocationInfo(uint64_t pc, const DwarfFde* fde,
586 DwarfLocations* loc_regs, ArchEnum arch) {
587 DwarfCfa<AddressType> cfa(&memory_, fde, arch);
588
589 // Look for the cached copy of the cie data.
590 auto reg_entry = cie_loc_regs_.find(fde->cie_offset);
591 if (reg_entry == cie_loc_regs_.end()) {
592 if (!cfa.GetLocationInfo(pc, fde->cie->cfa_instructions_offset, fde->cie->cfa_instructions_end,
593 loc_regs)) {
594 last_error_ = cfa.last_error();
595 return false;
596 }
597 cie_loc_regs_[fde->cie_offset] = *loc_regs;
598 }
599 cfa.set_cie_loc_regs(&cie_loc_regs_[fde->cie_offset]);
600 if (!cfa.GetLocationInfo(pc, fde->cfa_instructions_offset, fde->cfa_instructions_end, loc_regs)) {
601 last_error_ = cfa.last_error();
602 return false;
603 }
604 return true;
605 }
606
607 template <typename AddressType>
Log(uint8_t indent,uint64_t pc,const DwarfFde * fde,ArchEnum arch)608 bool DwarfSectionImpl<AddressType>::Log(uint8_t indent, uint64_t pc, const DwarfFde* fde,
609 ArchEnum arch) {
610 DwarfCfa<AddressType> cfa(&memory_, fde, arch);
611
612 // Always print the cie information.
613 const DwarfCie* cie = fde->cie;
614 if (!cfa.Log(indent, pc, cie->cfa_instructions_offset, cie->cfa_instructions_end)) {
615 last_error_ = cfa.last_error();
616 return false;
617 }
618 if (!cfa.Log(indent, pc, fde->cfa_instructions_offset, fde->cfa_instructions_end)) {
619 last_error_ = cfa.last_error();
620 return false;
621 }
622 return true;
623 }
624
625 template <typename AddressType>
Init(uint64_t offset,uint64_t size,int64_t section_bias)626 bool DwarfSectionImpl<AddressType>::Init(uint64_t offset, uint64_t size, int64_t section_bias) {
627 section_bias_ = section_bias;
628 entries_offset_ = offset;
629 entries_end_ = offset + size;
630
631 memory_.clear_func_offset();
632 memory_.clear_text_offset();
633 memory_.set_cur_offset(offset);
634 pc_offset_ = offset;
635
636 return true;
637 }
638
639 // Read CIE or FDE entry at the given offset, and set the offset to the following entry.
640 // The 'fde' argument is set only if we have seen an FDE entry.
641 template <typename AddressType>
GetNextCieOrFde(uint64_t & next_entries_offset,std::optional<DwarfFde> & fde_entry)642 bool DwarfSectionImpl<AddressType>::GetNextCieOrFde(uint64_t& next_entries_offset,
643 std::optional<DwarfFde>& fde_entry) {
644 const uint64_t start_offset = next_entries_offset;
645
646 memory_.set_data_offset(entries_offset_);
647 memory_.set_cur_offset(next_entries_offset);
648 uint32_t value32;
649 if (!memory_.ReadBytes(&value32, sizeof(value32))) {
650 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
651 last_error_.address = memory_.cur_offset();
652 return false;
653 }
654
655 uint64_t cie_offset;
656 uint8_t cie_fde_encoding;
657 bool entry_is_cie = false;
658 if (value32 == static_cast<uint32_t>(-1)) {
659 // 64 bit entry.
660 uint64_t value64;
661 if (!memory_.ReadBytes(&value64, sizeof(value64))) {
662 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
663 last_error_.address = memory_.cur_offset();
664 return false;
665 }
666
667 next_entries_offset = memory_.cur_offset() + value64;
668 // Read the Cie Id of a Cie or the pointer of the Fde.
669 if (!memory_.ReadBytes(&value64, sizeof(value64))) {
670 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
671 last_error_.address = memory_.cur_offset();
672 return false;
673 }
674
675 if (value64 == cie64_value_) {
676 entry_is_cie = true;
677 cie_fde_encoding = DW_EH_PE_udata8;
678 } else {
679 cie_offset = GetCieOffsetFromFde64(value64);
680 }
681 } else {
682 next_entries_offset = memory_.cur_offset() + value32;
683
684 // 32 bit Cie
685 if (!memory_.ReadBytes(&value32, sizeof(value32))) {
686 last_error_.code = DWARF_ERROR_MEMORY_INVALID;
687 last_error_.address = memory_.cur_offset();
688 return false;
689 }
690
691 if (value32 == cie32_value_) {
692 entry_is_cie = true;
693 cie_fde_encoding = DW_EH_PE_udata4;
694 } else {
695 cie_offset = GetCieOffsetFromFde32(value32);
696 }
697 }
698
699 if (entry_is_cie) {
700 auto entry = cie_entries_.find(start_offset);
701 if (entry == cie_entries_.end()) {
702 DwarfCie* cie = &cie_entries_[start_offset];
703 cie->lsda_encoding = DW_EH_PE_omit;
704 cie->cfa_instructions_end = next_entries_offset;
705 cie->fde_address_encoding = cie_fde_encoding;
706
707 if (!FillInCie(cie)) {
708 cie_entries_.erase(start_offset);
709 return false;
710 }
711 }
712 fde_entry.reset();
713 } else {
714 fde_entry = DwarfFde{};
715 fde_entry->cfa_instructions_end = next_entries_offset;
716 fde_entry->cie_offset = cie_offset;
717 if (!FillInFde(&*fde_entry)) {
718 return false;
719 }
720 }
721 return true;
722 }
723
724 template <typename AddressType>
GetFdes(std::vector<const DwarfFde * > * fdes)725 void DwarfSectionImpl<AddressType>::GetFdes(std::vector<const DwarfFde*>* fdes) {
726 if (fde_index_.empty()) {
727 BuildFdeIndex();
728 }
729 for (auto& it : fde_index_) {
730 fdes->push_back(GetFdeFromOffset(it.second));
731 }
732 }
733
734 template <typename AddressType>
GetFdeFromPc(uint64_t pc)735 const DwarfFde* DwarfSectionImpl<AddressType>::GetFdeFromPc(uint64_t pc) {
736 // Ensure that the binary search table is initialized.
737 if (fde_index_.empty()) {
738 BuildFdeIndex();
739 }
740
741 // Find the FDE offset in the binary search table.
742 auto comp = [](uint64_t pc, auto& entry) { return pc < entry.first; };
743 auto it = std::upper_bound(fde_index_.begin(), fde_index_.end(), pc, comp);
744 if (it == fde_index_.end()) {
745 return nullptr;
746 }
747
748 // Load the full FDE entry based on the offset.
749 const DwarfFde* fde = GetFdeFromOffset(/*fde_offset=*/it->second);
750 return fde != nullptr && fde->pc_start <= pc ? fde : nullptr;
751 }
752
753 // Create binary search table to make FDE lookups fast (sorted by pc_end).
754 // We store only the FDE offset rather than the full entry to save memory.
755 //
756 // If there are overlapping entries, it inserts additional entries to ensure
757 // that one of the overlapping entries is found (it is undefined which one).
758 template <typename AddressType>
BuildFdeIndex()759 void DwarfSectionImpl<AddressType>::BuildFdeIndex() {
760 struct FdeInfo {
761 uint64_t pc_start, pc_end, fde_offset;
762 };
763 std::vector<FdeInfo> fdes;
764 for (uint64_t offset = entries_offset_; offset < entries_end_;) {
765 const uint64_t initial_offset = offset;
766 std::optional<DwarfFde> fde;
767 if (!GetNextCieOrFde(offset, fde)) {
768 break;
769 }
770 if (fde.has_value() && /* defensive check */ (fde->pc_start < fde->pc_end)) {
771 fdes.push_back({fde->pc_start, fde->pc_end, initial_offset});
772 }
773 if (offset <= initial_offset) {
774 break; // Jump back. Simply consider the processing done in this case.
775 }
776 }
777 std::sort(fdes.begin(), fdes.end(), [](const FdeInfo& a, const FdeInfo& b) {
778 return std::tie(a.pc_end, a.fde_offset) < std::tie(b.pc_end, b.fde_offset);
779 });
780
781 // If there are overlapping entries, ensure that we can always find one of them.
782 // For example, for entries: [300, 350) [400, 450) [100, 550) [600, 650)
783 // We add the following: [100, 300) [100, 400)
784 // Which ensures that the [100, 550) entry can be found in its whole range.
785 if (!fdes.empty()) {
786 FdeInfo filling = fdes.back(); // Entry with the minimal pc_start seen so far.
787 for (ssize_t i = fdes.size() - 1; i >= 0; i--) { // Iterate backwards.
788 uint64_t prev_pc_end = (i > 0) ? fdes[i - 1].pc_end : 0;
789 // If there is a gap between entries and the filling reaches the gap, fill it.
790 if (prev_pc_end < fdes[i].pc_start && filling.pc_start < fdes[i].pc_start) {
791 fdes.push_back({filling.pc_start, fdes[i].pc_start, filling.fde_offset});
792 }
793 if (fdes[i].pc_start < filling.pc_start) {
794 filling = fdes[i];
795 }
796 }
797 }
798
799 // Copy data to the final binary search table (pc_end, fde_offset) and sort it.
800 fde_index_.reserve(fdes.size());
801 for (const FdeInfo& it : fdes) {
802 fde_index_.emplace_back(it.pc_end, it.fde_offset);
803 }
804 if (!std::is_sorted(fde_index_.begin(), fde_index_.end())) {
805 std::sort(fde_index_.begin(), fde_index_.end());
806 }
807 }
808
809 // Explicitly instantiate DwarfSectionImpl
810 template class DwarfSectionImpl<uint32_t>;
811 template class DwarfSectionImpl<uint64_t>;
812
813 // Explicitly instantiate DwarfDebugFrame
814 template class DwarfDebugFrame<uint32_t>;
815 template class DwarfDebugFrame<uint64_t>;
816
817 // Explicitly instantiate DwarfEhFrame
818 template class DwarfEhFrame<uint32_t>;
819 template class DwarfEhFrame<uint64_t>;
820
821 } // namespace unwindstack
822