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