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