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/DwarfStructs.h>
20 #include <unwindstack/Memory.h>
21
22 #include "Check.h"
23 #include "DwarfEhFrame.h"
24 #include "DwarfError.h"
25
26 namespace unwindstack {
27
28 template <typename AddressType>
Init(uint64_t offset,uint64_t size)29 bool DwarfEhFrame<AddressType>::Init(uint64_t offset, uint64_t size) {
30 uint8_t data[4];
31
32 memory_.clear_func_offset();
33 memory_.clear_text_offset();
34 memory_.set_data_offset(offset);
35 memory_.set_cur_offset(offset);
36
37 // Read the first four bytes all at once.
38 if (!memory_.ReadBytes(data, 4)) {
39 last_error_ = DWARF_ERROR_MEMORY_INVALID;
40 return false;
41 }
42
43 version_ = data[0];
44 if (version_ != 1) {
45 // Unknown version.
46 last_error_ = DWARF_ERROR_UNSUPPORTED_VERSION;
47 return false;
48 }
49
50 ptr_encoding_ = data[1];
51 uint8_t fde_count_encoding = data[2];
52 table_encoding_ = data[3];
53 table_entry_size_ = memory_.template GetEncodedSize<AddressType>(table_encoding_);
54
55 memory_.set_pc_offset(memory_.cur_offset());
56 if (!memory_.template ReadEncodedValue<AddressType>(ptr_encoding_, &ptr_offset_)) {
57 last_error_ = DWARF_ERROR_MEMORY_INVALID;
58 return false;
59 }
60
61 memory_.set_pc_offset(memory_.cur_offset());
62 if (!memory_.template ReadEncodedValue<AddressType>(fde_count_encoding, &fde_count_)) {
63 last_error_ = DWARF_ERROR_MEMORY_INVALID;
64 return false;
65 }
66
67 entries_offset_ = memory_.cur_offset();
68 entries_end_ = offset + size;
69 entries_data_offset_ = offset;
70 cur_entries_offset_ = entries_offset_;
71
72 return true;
73 }
74
75 template <typename AddressType>
GetFdeFromIndex(size_t index)76 const DwarfFde* DwarfEhFrame<AddressType>::GetFdeFromIndex(size_t index) {
77 const FdeInfo* info = GetFdeInfoFromIndex(index);
78 if (info == nullptr) {
79 return nullptr;
80 }
81 return this->GetFdeFromOffset(info->offset);
82 }
83
84 template <typename AddressType>
GetFdeInfoFromIndex(size_t index)85 const typename DwarfEhFrame<AddressType>::FdeInfo* DwarfEhFrame<AddressType>::GetFdeInfoFromIndex(
86 size_t index) {
87 auto entry = fde_info_.find(index);
88 if (entry != fde_info_.end()) {
89 return &fde_info_[index];
90 }
91 FdeInfo* info = &fde_info_[index];
92
93 memory_.set_data_offset(entries_data_offset_);
94 memory_.set_cur_offset(entries_offset_ + 2 * index * table_entry_size_);
95 memory_.set_pc_offset(memory_.cur_offset());
96 uint64_t value;
97 if (!memory_.template ReadEncodedValue<AddressType>(table_encoding_, &value) ||
98 !memory_.template ReadEncodedValue<AddressType>(table_encoding_, &info->offset)) {
99 last_error_ = DWARF_ERROR_MEMORY_INVALID;
100 fde_info_.erase(index);
101 return nullptr;
102 }
103 info->pc = value;
104 return info;
105 }
106
107 template <typename AddressType>
GetFdeOffsetBinary(uint64_t pc,uint64_t * fde_offset,uint64_t total_entries)108 bool DwarfEhFrame<AddressType>::GetFdeOffsetBinary(uint64_t pc, uint64_t* fde_offset,
109 uint64_t total_entries) {
110 CHECK(fde_count_ > 0);
111 CHECK(total_entries <= fde_count_);
112
113 size_t first = 0;
114 size_t last = total_entries;
115 while (first < last) {
116 size_t current = (first + last) / 2;
117 const FdeInfo* info = GetFdeInfoFromIndex(current);
118 if (pc == info->pc) {
119 *fde_offset = info->offset;
120 return true;
121 }
122 if (pc < info->pc) {
123 last = current;
124 } else {
125 first = current + 1;
126 }
127 }
128 if (last != 0) {
129 const FdeInfo* info = GetFdeInfoFromIndex(last - 1);
130 *fde_offset = info->offset;
131 return true;
132 }
133 return false;
134 }
135
136 template <typename AddressType>
GetFdeOffsetSequential(uint64_t pc,uint64_t * fde_offset)137 bool DwarfEhFrame<AddressType>::GetFdeOffsetSequential(uint64_t pc, uint64_t* fde_offset) {
138 CHECK(fde_count_ != 0);
139 last_error_ = DWARF_ERROR_NONE;
140 // We can do a binary search if the pc is in the range of the elements
141 // that have already been cached.
142 if (!fde_info_.empty()) {
143 const FdeInfo* info = &fde_info_[fde_info_.size() - 1];
144 if (pc >= info->pc) {
145 *fde_offset = info->offset;
146 return true;
147 }
148 if (pc < info->pc) {
149 return GetFdeOffsetBinary(pc, fde_offset, fde_info_.size());
150 }
151 }
152
153 if (cur_entries_offset_ == 0) {
154 // All entries read, or error encountered.
155 return false;
156 }
157
158 memory_.set_data_offset(entries_data_offset_);
159 memory_.set_cur_offset(cur_entries_offset_);
160 cur_entries_offset_ = 0;
161
162 FdeInfo* prev_info = nullptr;
163 for (size_t current = fde_info_.size();
164 current < fde_count_ && memory_.cur_offset() < entries_end_; current++) {
165 memory_.set_pc_offset(memory_.cur_offset());
166 uint64_t value;
167 if (!memory_.template ReadEncodedValue<AddressType>(table_encoding_, &value)) {
168 last_error_ = DWARF_ERROR_MEMORY_INVALID;
169 return false;
170 }
171
172 FdeInfo* info = &fde_info_[current];
173 if (!memory_.template ReadEncodedValue<AddressType>(table_encoding_, &info->offset)) {
174 fde_info_.erase(current);
175 last_error_ = DWARF_ERROR_MEMORY_INVALID;
176 return false;
177 }
178 info->pc = value;
179
180 if (pc < info->pc) {
181 if (prev_info == nullptr) {
182 return false;
183 }
184 cur_entries_offset_ = memory_.cur_offset();
185 *fde_offset = prev_info->offset;
186 return true;
187 }
188 prev_info = info;
189 }
190
191 if (fde_count_ == fde_info_.size() && pc >= prev_info->pc) {
192 *fde_offset = prev_info->offset;
193 return true;
194 }
195 return false;
196 }
197
198 template <typename AddressType>
GetFdeOffsetFromPc(uint64_t pc,uint64_t * fde_offset)199 bool DwarfEhFrame<AddressType>::GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) {
200 if (fde_count_ == 0) {
201 return false;
202 }
203
204 if (table_entry_size_ > 0) {
205 // Do a binary search since the size of each table entry is fixed.
206 return GetFdeOffsetBinary(pc, fde_offset, fde_count_);
207 } else {
208 // Do a sequential search since each table entry size is variable.
209 return GetFdeOffsetSequential(pc, fde_offset);
210 }
211 }
212
213 // Explicitly instantiate DwarfEhFrame.
214 template class DwarfEhFrame<uint32_t>;
215 template class DwarfEhFrame<uint64_t>;
216
217 } // namespace unwindstack
218