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