chrome_unwinder_android_v2.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414
  1. // Copyright 2021 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/profiler/chrome_unwinder_android_v2.h"
  5. #include <algorithm>
  6. #include "base/check_op.h"
  7. #include "base/memory/aligned_memory.h"
  8. #include "base/notreached.h"
  9. #include "base/numerics/checked_math.h"
  10. #include "base/profiler/chrome_unwind_info_android.h"
  11. namespace base {
  12. namespace {
  13. uintptr_t* GetRegisterPointer(RegisterContext* context,
  14. uint8_t register_index) {
  15. DCHECK_LE(register_index, 15);
  16. static unsigned long RegisterContext::*const registers[16] = {
  17. &RegisterContext::arm_r0, &RegisterContext::arm_r1,
  18. &RegisterContext::arm_r2, &RegisterContext::arm_r3,
  19. &RegisterContext::arm_r4, &RegisterContext::arm_r5,
  20. &RegisterContext::arm_r6, &RegisterContext::arm_r7,
  21. &RegisterContext::arm_r8, &RegisterContext::arm_r9,
  22. &RegisterContext::arm_r10, &RegisterContext::arm_fp,
  23. &RegisterContext::arm_ip, &RegisterContext::arm_sp,
  24. &RegisterContext::arm_lr, &RegisterContext::arm_pc,
  25. };
  26. return reinterpret_cast<uintptr_t*>(&(context->*registers[register_index]));
  27. }
  28. // Pops the value on the top of stack out and assign it to target register.
  29. // This is equivalent to arm instruction `Pop r[n]` where n = `register_index`.
  30. // Returns whether the pop is successful.
  31. bool PopRegister(RegisterContext* context, uint8_t register_index) {
  32. const uintptr_t sp = RegisterContextStackPointer(context);
  33. const uintptr_t stacktop_value = *reinterpret_cast<uintptr_t*>(sp);
  34. const auto new_sp = CheckedNumeric<uintptr_t>(sp) + sizeof(uintptr_t);
  35. const bool success =
  36. new_sp.AssignIfValid(&RegisterContextStackPointer(context));
  37. if (success)
  38. *GetRegisterPointer(context, register_index) = stacktop_value;
  39. return success;
  40. }
  41. // Decodes the given bytes as an ULEB128 format number and advances the bytes
  42. // pointer by the size of ULEB128.
  43. //
  44. // This function assumes the given bytes are in valid ULEB128
  45. // format and the decoded number should not overflow `uintptr_t` type.
  46. uintptr_t DecodeULEB128(const uint8_t*& bytes) {
  47. uintptr_t value = 0;
  48. unsigned shift = 0;
  49. do {
  50. DCHECK_LE(shift, sizeof(uintptr_t) * 8); // ULEB128 must not overflow.
  51. value += (*bytes & 0x7fu) << shift;
  52. shift += 7;
  53. } while (*bytes++ & 0x80);
  54. return value;
  55. }
  56. uint8_t GetTopBits(uint8_t byte, unsigned bits) {
  57. DCHECK_LE(bits, 8u);
  58. return byte >> (8 - bits);
  59. }
  60. } // namespace
  61. ChromeUnwinderAndroidV2::ChromeUnwinderAndroidV2(
  62. const ChromeUnwindInfoAndroid& unwind_info,
  63. uintptr_t chrome_module_base_address,
  64. uintptr_t text_section_start_address)
  65. : unwind_info_(unwind_info),
  66. chrome_module_base_address_(chrome_module_base_address),
  67. text_section_start_address_(text_section_start_address) {
  68. DCHECK_GT(text_section_start_address_, chrome_module_base_address_);
  69. }
  70. bool ChromeUnwinderAndroidV2::CanUnwindFrom(const Frame& current_frame) const {
  71. return current_frame.module &&
  72. current_frame.module->GetBaseAddress() == chrome_module_base_address_;
  73. }
  74. UnwindResult ChromeUnwinderAndroidV2::TryUnwind(
  75. RegisterContext* thread_context,
  76. uintptr_t stack_top,
  77. std::vector<Frame>* stack) const {
  78. DCHECK(CanUnwindFrom(stack->back()));
  79. uintptr_t frame_initial_sp = RegisterContextStackPointer(thread_context);
  80. const uintptr_t unwind_initial_pc =
  81. RegisterContextInstructionPointer(thread_context);
  82. do {
  83. const uintptr_t pc = RegisterContextInstructionPointer(thread_context);
  84. const uintptr_t instruction_byte_offset_from_text_section_start =
  85. pc - text_section_start_address_;
  86. const absl::optional<FunctionOffsetTableIndex> function_offset_table_index =
  87. GetFunctionTableIndexFromInstructionOffset(
  88. unwind_info_.page_table, unwind_info_.function_table,
  89. instruction_byte_offset_from_text_section_start);
  90. if (!function_offset_table_index) {
  91. return UnwindResult::kAborted;
  92. }
  93. const uint32_t current_unwind_instruction_index =
  94. GetFirstUnwindInstructionIndexFromFunctionOffsetTableEntry(
  95. &unwind_info_
  96. .function_offset_table[function_offset_table_index
  97. ->function_offset_table_byte_index],
  98. function_offset_table_index
  99. ->instruction_offset_from_function_start);
  100. const uint8_t* current_unwind_instruction =
  101. &unwind_info_
  102. .unwind_instruction_table[current_unwind_instruction_index];
  103. UnwindInstructionResult instruction_result;
  104. bool pc_was_updated = false;
  105. do {
  106. instruction_result = ExecuteUnwindInstruction(
  107. current_unwind_instruction, pc_was_updated, thread_context);
  108. const uintptr_t sp = RegisterContextStackPointer(thread_context);
  109. if (sp > stack_top || sp < frame_initial_sp ||
  110. !IsAligned(sp, sizeof(uintptr_t))) {
  111. return UnwindResult::kAborted;
  112. }
  113. } while (instruction_result ==
  114. UnwindInstructionResult::kInstructionPending);
  115. if (instruction_result == UnwindInstructionResult::kAborted) {
  116. return UnwindResult::kAborted;
  117. }
  118. DCHECK_EQ(instruction_result, UnwindInstructionResult::kCompleted);
  119. const uintptr_t new_sp = RegisterContextStackPointer(thread_context);
  120. // Validate SP is properly aligned across frames.
  121. // See
  122. // https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/using-the-stack-in-aarch32-and-aarch64
  123. // for SP alignment rules.
  124. if (!IsAligned(new_sp, 2 * sizeof(uintptr_t))) {
  125. return UnwindResult::kAborted;
  126. }
  127. // Validate that SP does not decrease across frames.
  128. const bool is_leaf_frame = stack->size() == 1;
  129. // Each frame unwind is expected to only pop from stack memory, which will
  130. // cause sp to increase.
  131. // Non-Leaf frames are expected to at least pop lr off stack, so sp is
  132. // expected to strictly increase for non-leaf frames.
  133. if (new_sp <= (is_leaf_frame ? frame_initial_sp - 1 : frame_initial_sp)) {
  134. return UnwindResult::kAborted;
  135. }
  136. // For leaf functions, if SP does not change, PC must change, otherwise,
  137. // the overall execution state will be the same before/after the frame
  138. // unwind.
  139. if (is_leaf_frame && new_sp == frame_initial_sp &&
  140. RegisterContextInstructionPointer(thread_context) ==
  141. unwind_initial_pc) {
  142. return UnwindResult::kAborted;
  143. }
  144. frame_initial_sp = new_sp;
  145. stack->emplace_back(RegisterContextInstructionPointer(thread_context),
  146. module_cache()->GetModuleForAddress(
  147. RegisterContextInstructionPointer(thread_context)));
  148. } while (CanUnwindFrom(stack->back()));
  149. return UnwindResult::kUnrecognizedFrame;
  150. }
  151. UnwindInstructionResult ExecuteUnwindInstruction(
  152. const uint8_t*& instruction,
  153. bool& pc_was_updated,
  154. RegisterContext* thread_context) {
  155. if (GetTopBits(*instruction, 2) == 0b00) {
  156. // 00xxxxxx
  157. // vsp = vsp + (xxxxxx << 2) + 4. Covers range 0x04-0x100 inclusive.
  158. const uintptr_t offset = ((*instruction++ & 0b00111111u) << 2) + 4;
  159. const auto new_sp =
  160. CheckedNumeric<uintptr_t>(RegisterContextStackPointer(thread_context)) +
  161. offset;
  162. if (!new_sp.AssignIfValid(&RegisterContextStackPointer(thread_context))) {
  163. return UnwindInstructionResult::kAborted;
  164. }
  165. } else if (GetTopBits(*instruction, 2) == 0b01) {
  166. // 01xxxxxx
  167. // vsp = vsp - (xxxxxx << 2) - 4. Covers range 0x04-0x100 inclusive.
  168. const uintptr_t offset = ((*instruction++ & 0b00111111u) << 2) + 4;
  169. const auto new_sp =
  170. CheckedNumeric<uintptr_t>(RegisterContextStackPointer(thread_context)) -
  171. offset;
  172. if (!new_sp.AssignIfValid(&RegisterContextStackPointer(thread_context))) {
  173. return UnwindInstructionResult::kAborted;
  174. }
  175. } else if (GetTopBits(*instruction, 4) == 0b1001) {
  176. // 1001nnnn (nnnn != 13,15)
  177. // Set vsp = r[nnnn].
  178. const uint8_t register_index = *instruction++ & 0b00001111;
  179. DCHECK_NE(register_index, 13); // Must not set sp to sp.
  180. DCHECK_NE(register_index, 15); // Must not set sp to pc.
  181. // Note: We shouldn't have cases that are setting caller-saved registers
  182. // using this instruction.
  183. DCHECK_GE(register_index, 4);
  184. RegisterContextStackPointer(thread_context) =
  185. *GetRegisterPointer(thread_context, register_index);
  186. } else if (GetTopBits(*instruction, 5) == 0b10101) {
  187. // 10101nnn
  188. // Pop r4-r[4+nnn], r14
  189. const uint8_t max_register_index = (*instruction++ & 0b00000111u) + 4;
  190. for (uint8_t n = 4; n <= max_register_index; n++) {
  191. if (!PopRegister(thread_context, n)) {
  192. return UnwindInstructionResult::kAborted;
  193. }
  194. }
  195. if (!PopRegister(thread_context, 14)) {
  196. return UnwindInstructionResult::kAborted;
  197. }
  198. } else if (*instruction == 0b10000000 && *(instruction + 1) == 0) {
  199. // 10000000 00000000
  200. // Refuse to unwind.
  201. instruction += 2;
  202. return UnwindInstructionResult::kAborted;
  203. } else if (GetTopBits(*instruction, 4) == 0b1000) {
  204. const uint32_t register_bitmask =
  205. ((*instruction & 0xfu) << 8) + *(instruction + 1);
  206. instruction += 2;
  207. // 1000iiii iiiiiiii
  208. // Pop up to 12 integer registers under masks {r15-r12}, {r11-r4}
  209. for (uint8_t register_index = 4; register_index < 16; register_index++) {
  210. if (register_bitmask & (1 << (register_index - 4))) {
  211. if (!PopRegister(thread_context, register_index)) {
  212. return UnwindInstructionResult::kAborted;
  213. }
  214. }
  215. }
  216. // If we set pc (r15) with value on stack, we should no longer copy lr to
  217. // pc on COMPLETE.
  218. pc_was_updated |= register_bitmask & (1 << (15 - 4));
  219. } else if (*instruction == 0b10110000) {
  220. // Finish
  221. // Code 0xb0, Finish, copies VRS[r14] to VRS[r15] and also
  222. // indicates that no further instructions are to be processed for this
  223. // frame.
  224. instruction++;
  225. // Only copy lr to pc when pc is not updated by other instructions before.
  226. if (!pc_was_updated)
  227. thread_context->arm_pc = thread_context->arm_lr;
  228. return UnwindInstructionResult::kCompleted;
  229. } else if (*instruction == 0b10110010) {
  230. // 10110010 uleb128
  231. // vsp = vsp + 0x204 + (uleb128 << 2)
  232. // (for vsp increments of 0x104-0x200, use 00xxxxxx twice)
  233. instruction++;
  234. const auto new_sp =
  235. CheckedNumeric<uintptr_t>(RegisterContextStackPointer(thread_context)) +
  236. (CheckedNumeric<uintptr_t>(DecodeULEB128(instruction)) << 2) + 0x204;
  237. if (!new_sp.AssignIfValid(&RegisterContextStackPointer(thread_context))) {
  238. return UnwindInstructionResult::kAborted;
  239. }
  240. } else {
  241. NOTREACHED();
  242. }
  243. return UnwindInstructionResult::kInstructionPending;
  244. }
  245. uintptr_t GetFirstUnwindInstructionIndexFromFunctionOffsetTableEntry(
  246. const uint8_t* function_offset_table_entry,
  247. int instruction_offset_from_function_start) {
  248. DCHECK_GE(instruction_offset_from_function_start, 0);
  249. const uint8_t* current_function_offset_table_position =
  250. function_offset_table_entry;
  251. do {
  252. const uintptr_t function_offset =
  253. DecodeULEB128(current_function_offset_table_position);
  254. const uintptr_t unwind_table_index =
  255. DecodeULEB128(current_function_offset_table_position);
  256. // Each function always ends at 0 offset. It is guaranteed to find an entry
  257. // as long as the function offset table is well-structured.
  258. if (function_offset <=
  259. static_cast<uint32_t>(instruction_offset_from_function_start))
  260. return unwind_table_index;
  261. } while (true);
  262. NOTREACHED();
  263. return 0;
  264. }
  265. const absl::optional<FunctionOffsetTableIndex>
  266. GetFunctionTableIndexFromInstructionOffset(
  267. span<const uint32_t> page_start_instructions,
  268. span<const FunctionTableEntry> function_offset_table_indices,
  269. uint32_t instruction_byte_offset_from_text_section_start) {
  270. DCHECK(!page_start_instructions.empty());
  271. DCHECK(!function_offset_table_indices.empty());
  272. // First function on first page should always start from 0 offset.
  273. DCHECK_EQ(function_offset_table_indices.front()
  274. .function_start_address_page_instruction_offset,
  275. 0ul);
  276. const uint16_t page_number =
  277. instruction_byte_offset_from_text_section_start >> 17;
  278. const uint16_t page_instruction_offset =
  279. (instruction_byte_offset_from_text_section_start >> 1) &
  280. 0xffff; // 16 bits.
  281. // Invalid instruction_byte_offset_from_text_section_start:
  282. // instruction_byte_offset_from_text_section_start falls after the last page.
  283. if (page_number >= page_start_instructions.size()) {
  284. return absl::nullopt;
  285. }
  286. const span<const FunctionTableEntry>::const_iterator
  287. function_table_entry_start =
  288. function_offset_table_indices.begin() +
  289. checked_cast<ptrdiff_t>(page_start_instructions[page_number]);
  290. const span<const FunctionTableEntry>::const_iterator
  291. function_table_entry_end =
  292. page_number == page_start_instructions.size() - 1
  293. ? function_offset_table_indices.end()
  294. : function_offset_table_indices.begin() +
  295. checked_cast<ptrdiff_t>(
  296. page_start_instructions[page_number + 1]);
  297. // `std::upper_bound` finds first element that > target in range
  298. // [function_table_entry_start, function_table_entry_end).
  299. const auto first_larger_entry_location = std::upper_bound(
  300. function_table_entry_start, function_table_entry_end,
  301. page_instruction_offset,
  302. [](uint16_t page_instruction_offset, const FunctionTableEntry& entry) {
  303. return page_instruction_offset <
  304. entry.function_start_address_page_instruction_offset;
  305. });
  306. // Offsets the element found by 1 to get the biggest element that <= target.
  307. const auto entry_location = first_larger_entry_location - 1;
  308. // When all offsets in current range > page_instruction_offset (including when
  309. // there is no entry in current range), the `FunctionTableEntry` we are
  310. // looking for is not within the function_offset_table_indices range we are
  311. // inspecting, because the function is too long that it spans multiple pages.
  312. //
  313. // We need to locate the previous entry on function_offset_table_indices and
  314. // find its corresponding page_table index.
  315. //
  316. // Example:
  317. // +--------------------+--------------------+
  318. // | <-----2 byte-----> | <-----2 byte-----> |
  319. // +--------------------+--------------------+
  320. // | Page Offset | Offset Table Index |
  321. // +--------------------+--------------------+-----
  322. // | 10 | XXX | |
  323. // +--------------------+--------------------+ |
  324. // | ... | ... |Page 0x100
  325. // +--------------------+--------------------+ |
  326. // | 65500 | ZZZ | |
  327. // +--------------------+--------------------+----- Page 0x101 is empty
  328. // | 200 | AAA | |
  329. // +--------------------+--------------------+ |
  330. // | ... | ... |Page 0x102
  331. // +--------------------+--------------------+ |
  332. // | 65535 | BBB | |
  333. // +--------------------+--------------------+-----
  334. //
  335. // Example:
  336. // For
  337. // - page_number = 0x100, page_instruction_offset >= 65535
  338. // - page_number = 0x101, all page_instruction_offset
  339. // - page_number = 0x102, page_instruction_offset < 200
  340. // We should be able to map them all to entry [65500, ZZZ] in page 0x100.
  341. // Finds the page_number that corresponds to `entry_location`. The page
  342. // might not be the page we are inspecting, when the function spans over
  343. // multiple pages.
  344. uint16_t function_start_page_number = page_number;
  345. while (function_offset_table_indices.begin() +
  346. checked_cast<ptrdiff_t>(
  347. page_start_instructions[function_start_page_number]) >
  348. entry_location) {
  349. // First page in page table must not be empty.
  350. DCHECK_NE(function_start_page_number, 0);
  351. function_start_page_number--;
  352. };
  353. const uint32_t function_start_address_instruction_offset =
  354. (uint32_t{function_start_page_number} << 16) +
  355. entry_location->function_start_address_page_instruction_offset;
  356. const int instruction_offset_from_function_start =
  357. static_cast<int>((instruction_byte_offset_from_text_section_start >> 1) -
  358. function_start_address_instruction_offset);
  359. DCHECK_GE(instruction_offset_from_function_start, 0);
  360. return FunctionOffsetTableIndex{
  361. instruction_offset_from_function_start,
  362. entry_location->function_offset_table_byte_index,
  363. };
  364. }
  365. } // namespace base