1 // Copyright 2018 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/trace_event/cfi_backtrace_android.h"
6
7 #include <sys/mman.h>
8 #include <sys/types.h>
9
10 #include "base/android/apk_assets.h"
11 #include "base/android/library_loader/anchor_functions.h"
12
13 #if !defined(ARCH_CPU_ARMEL)
14 #error This file should not be built for this architecture.
15 #endif
16
17 /*
18 Basics of unwinding:
19 For each instruction in a function we need to know what is the offset of SP
20 (Stack Pointer) to reach the previous function's stack frame. To know which
21 function is being invoked, we need the return address of the next function. The
22 CFI information for an instruction is made up of 2 offsets, CFA (Call Frame
23 Address) offset and RA (Return Address) offset. The CFA offset is the change in
24 SP made by the function till the current instruction. This depends on amount of
25 memory allocated on stack by the function plus some registers that the function
26 stores that needs to be restored at the end of function. So, at each instruction
27 the CFA offset tells the offset from original SP before the function call. The
28 RA offset tells us the offset from the previous SP into the current function
29 where the return address is stored.
30
31 The unwind table file has 2 tables UNW_INDEX and UNW_DATA, inspired from ARM
32 EHABI format. The first table contains function addresses and an index into the
33 UNW_DATA table. The second table contains one or more rows for the function
34 unwind information.
35
36 UNW_INDEX contains two columns of N rows each, where N is the number of
37 functions.
38 1. First column 4 byte rows of all the function start address as offset from
39 start of the binary, in sorted order.
40 2. For each function addr, the second column contains 2 byte indices in order.
41 The indices are offsets (in count of 2 bytes) of the CFI data from start of
42 UNW_DATA.
43 The last entry in the table always contains CANT_UNWIND index to specify the
44 end address of the last function.
45
46 UNW_DATA contains data of all the functions. Each function data contains N rows.
47 The data found at the address pointed from UNW_INDEX will be:
48 2 bytes: N - number of rows that belong to current function.
49 N * 4 bytes: N rows of data. 16 bits : Address offset from function start.
50 14 bits : CFA offset / 4.
51 2 bits : RA offset / 4.
52 If the RA offset of a row is 0, then use the offset of the previous rows in the
53 same function.
54 TODO(ssid): Make sure RA offset is always present.
55
56 See extract_unwind_tables.py for details about how this data is extracted from
57 breakpad symbol files.
58 */
59
60 extern "C" {
61
62 // The address of |__executable_start| gives the start address of the
63 // executable or shared library. This value is used to find the offset address
64 // of the instruction in binary from PC.
65 extern char __executable_start;
66
67 }
68
69 namespace base {
70 namespace trace_event {
71
72 namespace {
73
74 // The value of index when the function does not have unwind information.
75 constexpr uint32_t kCantUnwind = 0xFFFF;
76
77 // The mask on the CFI row data that is used to get the high 14 bits and
78 // multiply it by 4 to get CFA offset. Since the last 2 bits are masked out, a
79 // shift is not necessary.
80 constexpr uint16_t kCFAMask = 0xfffc;
81
82 // The mask on the CFI row data that is used to get the low 2 bits and multiply
83 // it by 4 to get the RA offset.
84 constexpr uint16_t kRAMask = 0x3;
85 constexpr uint16_t kRAShift = 2;
86
87 // The code in this file assumes we are running in 32-bit builds since all the
88 // addresses in the unwind table are specified in 32 bits.
89 static_assert(sizeof(uintptr_t) == 4,
90 "The unwind table format is only valid for 32 bit builds.");
91
92 // The CFI data in UNW_DATA table starts with number of rows (N) and then
93 // followed by N rows of 4 bytes long. The CFIUnwindDataRow represents a single
94 // row of CFI data of a function in the table. Since we cast the memory at the
95 // address after the address of number of rows, into an array of
96 // CFIUnwindDataRow, the size of the struct should be 4 bytes and the order of
97 // the members is fixed according to the given format. The first 2 bytes tell
98 // the address of function and last 2 bytes give the CFI data for the offset.
99 struct CFIUnwindDataRow {
100 // The address of the instruction in terms of offset from the start of the
101 // function.
102 uint16_t addr_offset;
103 // Represents the CFA and RA offsets to get information about next stack
104 // frame. This is the CFI data at the point before executing the instruction
105 // at |addr_offset| from the start of the function.
106 uint16_t cfi_data;
107
108 // Return the RA offset for the current unwind row.
ra_offsetbase::trace_event::__anon59a083ce0111::CFIUnwindDataRow109 size_t ra_offset() const { return (cfi_data & kRAMask) << kRAShift; }
110
111 // Returns the CFA offset for the current unwind row.
cfa_offsetbase::trace_event::__anon59a083ce0111::CFIUnwindDataRow112 size_t cfa_offset() const { return cfi_data & kCFAMask; }
113 };
114
115 static_assert(
116 sizeof(CFIUnwindDataRow) == 4,
117 "The CFIUnwindDataRow struct must be exactly 4 bytes for searching.");
118
119 } // namespace
120
121 // static
GetInitializedInstance()122 CFIBacktraceAndroid* CFIBacktraceAndroid::GetInitializedInstance() {
123 static CFIBacktraceAndroid* instance = new CFIBacktraceAndroid();
124 return instance;
125 }
126
127 // static
is_chrome_address(uintptr_t pc)128 bool CFIBacktraceAndroid::is_chrome_address(uintptr_t pc) {
129 return pc >= base::android::kStartOfText && pc < executable_end_addr();
130 }
131
132 // static
executable_start_addr()133 uintptr_t CFIBacktraceAndroid::executable_start_addr() {
134 return reinterpret_cast<uintptr_t>(&__executable_start);
135 }
136
137 // static
executable_end_addr()138 uintptr_t CFIBacktraceAndroid::executable_end_addr() {
139 return base::android::kEndOfText;
140 }
141
CFIBacktraceAndroid()142 CFIBacktraceAndroid::CFIBacktraceAndroid()
143 : thread_local_cfi_cache_(
144 [](void* ptr) { delete static_cast<CFICache*>(ptr); }) {
145 Initialize();
146 }
147
~CFIBacktraceAndroid()148 CFIBacktraceAndroid::~CFIBacktraceAndroid() {}
149
Initialize()150 void CFIBacktraceAndroid::Initialize() {
151 // This file name is defined by extract_unwind_tables.gni.
152 static constexpr char kCfiFileName[] = "assets/unwind_cfi_32";
153 MemoryMappedFile::Region cfi_region;
154 int fd = base::android::OpenApkAsset(kCfiFileName, &cfi_region);
155 if (fd < 0)
156 return;
157 cfi_mmap_ = std::make_unique<MemoryMappedFile>();
158 // The CFI region starts at |cfi_region.offset|.
159 if (!cfi_mmap_->Initialize(base::File(fd), cfi_region))
160 return;
161
162 ParseCFITables();
163 can_unwind_stack_frames_ = true;
164 }
165
ParseCFITables()166 void CFIBacktraceAndroid::ParseCFITables() {
167 // The first 4 bytes in the file is the number of entries in UNW_INDEX table.
168 size_t unw_index_size = 0;
169 memcpy(&unw_index_size, cfi_mmap_->data(), sizeof(unw_index_size));
170 // UNW_INDEX table starts after 4 bytes.
171 unw_index_function_col_ =
172 reinterpret_cast<const uintptr_t*>(cfi_mmap_->data()) + 1;
173 unw_index_row_count_ = unw_index_size;
174 unw_index_indices_col_ = reinterpret_cast<const uint16_t*>(
175 unw_index_function_col_ + unw_index_row_count_);
176
177 // The UNW_DATA table data is right after the end of UNW_INDEX table.
178 // Interpret the UNW_DATA table as an array of 2 byte numbers since the
179 // indexes we have from the UNW_INDEX table are in terms of 2 bytes.
180 unw_data_start_addr_ = unw_index_indices_col_ + unw_index_row_count_;
181 }
182
Unwind(const void ** out_trace,size_t max_depth)183 size_t CFIBacktraceAndroid::Unwind(const void** out_trace, size_t max_depth) {
184 // This function walks the stack using the call frame information to find the
185 // return addresses of all the functions that belong to current binary in call
186 // stack. For each function the CFI table defines the offset of the previous
187 // call frame and offset where the return address is stored.
188 if (!can_unwind_stack_frames())
189 return 0;
190
191 // Get the current register state. This register state can be taken at any
192 // point in the function and the unwind information would be for this point.
193 // Define local variables before trying to get the current PC and SP to make
194 // sure the register state obtained is consistent with each other.
195 uintptr_t pc = 0, sp = 0;
196 asm volatile("mov %0, pc" : "=r"(pc));
197 asm volatile("mov %0, sp" : "=r"(sp));
198
199 return Unwind(pc, sp, /*lr=*/0, out_trace, max_depth);
200 }
201
Unwind(uintptr_t pc,uintptr_t sp,uintptr_t lr,const void ** out_trace,size_t max_depth)202 size_t CFIBacktraceAndroid::Unwind(uintptr_t pc,
203 uintptr_t sp,
204 uintptr_t lr,
205 const void** out_trace,
206 size_t max_depth) {
207 if (!can_unwind_stack_frames())
208 return 0;
209
210 // We can only unwind as long as the pc is within the chrome.so.
211 size_t depth = 0;
212 while (is_chrome_address(pc) && depth < max_depth) {
213 out_trace[depth++] = reinterpret_cast<void*>(pc);
214 // The offset of function from the start of the chrome.so binary:
215 uintptr_t func_addr = pc - executable_start_addr();
216 CFIRow cfi{};
217 if (!FindCFIRowForPC(func_addr, &cfi)) {
218 if (depth == 1 && lr != 0 && pc != lr) {
219 // If CFI data is not found for the frame, then we stopped in prolog of
220 // a function. The return address is stored in LR when in function
221 // prolog. So, update the PC with address in LR and do not update SP
222 // since SP was not updated by the prolog yet.
223 // TODO(ssid): Write tests / add info to detect if we are actually in
224 // function prolog. https://crbug.com/898276
225 pc = lr;
226 continue;
227 }
228 break;
229 }
230
231 // The rules for unwinding using the CFI information are:
232 // SP_prev = SP_cur + cfa_offset and
233 // PC_prev = * (SP_prev - ra_offset).
234 sp = sp + cfi.cfa_offset;
235 memcpy(&pc, reinterpret_cast<uintptr_t*>(sp - cfi.ra_offset),
236 sizeof(uintptr_t));
237 }
238 return depth;
239 }
240
AllocateCacheForCurrentThread()241 void CFIBacktraceAndroid::AllocateCacheForCurrentThread() {
242 GetThreadLocalCFICache();
243 }
244
FindCFIRowForPC(uintptr_t func_addr,CFIBacktraceAndroid::CFIRow * cfi)245 bool CFIBacktraceAndroid::FindCFIRowForPC(uintptr_t func_addr,
246 CFIBacktraceAndroid::CFIRow* cfi) {
247 if (!can_unwind_stack_frames())
248 return false;
249
250 auto* cache = GetThreadLocalCFICache();
251 *cfi = {0};
252 if (cache->Find(func_addr, cfi))
253 return true;
254
255 // Consider each column of UNW_INDEX table as arrays of uintptr_t (function
256 // addresses) and uint16_t (indices). Define start and end iterator on the
257 // first column array (addresses) and use std::lower_bound() to binary search
258 // on this array to find the required function address.
259 static const uintptr_t* const unw_index_fn_end =
260 unw_index_function_col_ + unw_index_row_count_;
261 const uintptr_t* found =
262 std::lower_bound(unw_index_function_col_, unw_index_fn_end, func_addr);
263
264 // If found is start, then the given function is not in the table. If the
265 // given pc is start of a function then we cannot unwind.
266 if (found == unw_index_function_col_ || *found == func_addr)
267 return false;
268
269 // std::lower_bound() returns the iter that corresponds to the first address
270 // that is greater than the given address. So, the required iter is always one
271 // less than the value returned by std::lower_bound().
272 --found;
273 uintptr_t func_start_addr = *found;
274 size_t row_num = found - unw_index_function_col_;
275 uint16_t index = unw_index_indices_col_[row_num];
276 DCHECK_LE(func_start_addr, func_addr);
277 // If the index is CANT_UNWIND then we do not have unwind infomation for the
278 // function.
279 if (index == kCantUnwind)
280 return false;
281
282 // The unwind data for the current function is at an offsset of the index
283 // found in UNW_INDEX table.
284 const uint16_t* unwind_data = unw_data_start_addr_ + index;
285 // The value of first 2 bytes is the CFI data row count for the function.
286 uint16_t row_count = 0;
287 memcpy(&row_count, unwind_data, sizeof(row_count));
288 // And the actual CFI rows start after 2 bytes from the |unwind_data|. Cast
289 // the data into an array of CFIUnwindDataRow since the struct is designed to
290 // represent each row. We should be careful to read only |row_count| number of
291 // elements in the array.
292 const CFIUnwindDataRow* function_data =
293 reinterpret_cast<const CFIUnwindDataRow*>(unwind_data + 1);
294
295 // Iterate through the CFI rows of the function to find the row that gives
296 // offset for the given instruction address.
297 CFIUnwindDataRow cfi_row = {0, 0};
298 uint16_t ra_offset = 0;
299 for (uint16_t i = 0; i < row_count; ++i) {
300 CFIUnwindDataRow row;
301 memcpy(&row, function_data + i, sizeof(CFIUnwindDataRow));
302 // The return address of the function is the instruction that is not yet
303 // been executed. The cfi row specifies the unwind info before executing the
304 // given instruction. If the given address is equal to the instruction
305 // offset, then use the current row. Or use the row with highest address
306 // less than the given address.
307 if (row.addr_offset + func_start_addr > func_addr)
308 break;
309
310 cfi_row = row;
311 // The ra offset of the last specified row should be used, if unspecified.
312 // So, keep updating the RA offset till we reach the correct CFI row.
313 // TODO(ssid): This should be fixed in the format and we should always
314 // output ra offset.
315 if (cfi_row.ra_offset())
316 ra_offset = cfi_row.ra_offset();
317 }
318 DCHECK_NE(0u, cfi_row.addr_offset);
319 *cfi = {cfi_row.cfa_offset(), ra_offset};
320 DCHECK(cfi->cfa_offset);
321 DCHECK(cfi->ra_offset);
322
323 // safe to update since the cache is thread local.
324 cache->Add(func_addr, *cfi);
325 return true;
326 }
327
GetThreadLocalCFICache()328 CFIBacktraceAndroid::CFICache* CFIBacktraceAndroid::GetThreadLocalCFICache() {
329 auto* cache = static_cast<CFICache*>(thread_local_cfi_cache_.Get());
330 if (!cache) {
331 cache = new CFICache();
332 thread_local_cfi_cache_.Set(cache);
333 }
334 return cache;
335 }
336
Add(uintptr_t address,CFIRow cfi)337 void CFIBacktraceAndroid::CFICache::Add(uintptr_t address, CFIRow cfi) {
338 cache_[address % kLimit] = {address, cfi};
339 }
340
Find(uintptr_t address,CFIRow * cfi)341 bool CFIBacktraceAndroid::CFICache::Find(uintptr_t address, CFIRow* cfi) {
342 if (cache_[address % kLimit].address == address) {
343 *cfi = cache_[address % kLimit].cfi;
344 return true;
345 }
346 return false;
347 }
348
349 } // namespace trace_event
350 } // namespace base
351