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