cfi_backtrace_android.cc 14 KB

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