contrib/llvm-project/lldb/source/Symbol/CompactUnwindInfo.cpp

   1 //===-- CompactUnwindInfo.cpp -----------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "lldb/Symbol/CompactUnwindInfo.h"
  10 #include "lldb/Core/Module.h"
  11 #include "lldb/Core/Section.h"
  12 #include "lldb/Symbol/ObjectFile.h"
  13 #include "lldb/Symbol/UnwindPlan.h"
  14 #include "lldb/Target/Process.h"
  15 #include "lldb/Target/Target.h"
  16 #include "lldb/Utility/ArchSpec.h"
  17 #include "lldb/Utility/DataBufferHeap.h"
  18 #include "lldb/Utility/Log.h"
  19 #include "lldb/Utility/StreamString.h"
  20
  21 #include "llvm/Support/MathExtras.h"
  22
  23 #include <algorithm>
  24 #include <memory>
  25
  26 using namespace lldb;
  27 using namespace lldb_private;
  28
  29 namespace lldb_private {
  30
  31 // Constants from <mach-o/compact_unwind_encoding.h>
  32
  33 FLAGS_ANONYMOUS_ENUM(){
  34     UNWIND_IS_NOT_FUNCTION_START = 0x80000000, UNWIND_HAS_LSDA = 0x40000000,
  35     UNWIND_PERSONALITY_MASK = 0x30000000,
  36 };
  37
  38 FLAGS_ANONYMOUS_ENUM(){
  39     UNWIND_X86_MODE_MASK = 0x0F000000,
  40     UNWIND_X86_MODE_EBP_FRAME = 0x01000000,
  41     UNWIND_X86_MODE_STACK_IMMD = 0x02000000,
  42     UNWIND_X86_MODE_STACK_IND = 0x03000000,
  43     UNWIND_X86_MODE_DWARF = 0x04000000,
  44
  45     UNWIND_X86_EBP_FRAME_REGISTERS = 0x00007FFF,
  46     UNWIND_X86_EBP_FRAME_OFFSET = 0x00FF0000,
  47
  48     UNWIND_X86_FRAMELESS_STACK_SIZE = 0x00FF0000,
  49     UNWIND_X86_FRAMELESS_STACK_ADJUST = 0x0000E000,
  50     UNWIND_X86_FRAMELESS_STACK_REG_COUNT = 0x00001C00,
  51     UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION = 0x000003FF,
  52
  53     UNWIND_X86_DWARF_SECTION_OFFSET = 0x00FFFFFF,
  54 };
  55
  56 enum {
  57   UNWIND_X86_REG_NONE = 0,
  58   UNWIND_X86_REG_EBX = 1,
  59   UNWIND_X86_REG_ECX = 2,
  60   UNWIND_X86_REG_EDX = 3,
  61   UNWIND_X86_REG_EDI = 4,
  62   UNWIND_X86_REG_ESI = 5,
  63   UNWIND_X86_REG_EBP = 6,
  64 };
  65
  66 FLAGS_ANONYMOUS_ENUM(){
  67     UNWIND_X86_64_MODE_MASK = 0x0F000000,
  68     UNWIND_X86_64_MODE_RBP_FRAME = 0x01000000,
  69     UNWIND_X86_64_MODE_STACK_IMMD = 0x02000000,
  70     UNWIND_X86_64_MODE_STACK_IND = 0x03000000,
  71     UNWIND_X86_64_MODE_DWARF = 0x04000000,
  72
  73     UNWIND_X86_64_RBP_FRAME_REGISTERS = 0x00007FFF,
  74     UNWIND_X86_64_RBP_FRAME_OFFSET = 0x00FF0000,
  75
  76     UNWIND_X86_64_FRAMELESS_STACK_SIZE = 0x00FF0000,
  77     UNWIND_X86_64_FRAMELESS_STACK_ADJUST = 0x0000E000,
  78     UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT = 0x00001C00,
  79     UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION = 0x000003FF,
  80
  81     UNWIND_X86_64_DWARF_SECTION_OFFSET = 0x00FFFFFF,
  82 };
  83
  84 enum {
  85   UNWIND_X86_64_REG_NONE = 0,
  86   UNWIND_X86_64_REG_RBX = 1,
  87   UNWIND_X86_64_REG_R12 = 2,
  88   UNWIND_X86_64_REG_R13 = 3,
  89   UNWIND_X86_64_REG_R14 = 4,
  90   UNWIND_X86_64_REG_R15 = 5,
  91   UNWIND_X86_64_REG_RBP = 6,
  92 };
  93
  94 FLAGS_ANONYMOUS_ENUM(){
  95     UNWIND_ARM64_MODE_MASK = 0x0F000000,
  96     UNWIND_ARM64_MODE_FRAMELESS = 0x02000000,
  97     UNWIND_ARM64_MODE_DWARF = 0x03000000,
  98     UNWIND_ARM64_MODE_FRAME = 0x04000000,
  99
 100     UNWIND_ARM64_FRAME_X19_X20_PAIR = 0x00000001,
 101     UNWIND_ARM64_FRAME_X21_X22_PAIR = 0x00000002,
 102     UNWIND_ARM64_FRAME_X23_X24_PAIR = 0x00000004,
 103     UNWIND_ARM64_FRAME_X25_X26_PAIR = 0x00000008,
 104     UNWIND_ARM64_FRAME_X27_X28_PAIR = 0x00000010,
 105     UNWIND_ARM64_FRAME_D8_D9_PAIR = 0x00000100,
 106     UNWIND_ARM64_FRAME_D10_D11_PAIR = 0x00000200,
 107     UNWIND_ARM64_FRAME_D12_D13_PAIR = 0x00000400,
 108     UNWIND_ARM64_FRAME_D14_D15_PAIR = 0x00000800,
 109
 110     UNWIND_ARM64_FRAMELESS_STACK_SIZE_MASK = 0x00FFF000,
 111     UNWIND_ARM64_DWARF_SECTION_OFFSET = 0x00FFFFFF,
 112 };
 113
 114 FLAGS_ANONYMOUS_ENUM(){
 115     UNWIND_ARM_MODE_MASK = 0x0F000000,
 116     UNWIND_ARM_MODE_FRAME = 0x01000000,
 117     UNWIND_ARM_MODE_FRAME_D = 0x02000000,
 118     UNWIND_ARM_MODE_DWARF = 0x04000000,
 119
 120     UNWIND_ARM_FRAME_STACK_ADJUST_MASK = 0x00C00000,
 121
 122     UNWIND_ARM_FRAME_FIRST_PUSH_R4 = 0x00000001,
 123     UNWIND_ARM_FRAME_FIRST_PUSH_R5 = 0x00000002,
 124     UNWIND_ARM_FRAME_FIRST_PUSH_R6 = 0x00000004,
 125
 126     UNWIND_ARM_FRAME_SECOND_PUSH_R8 = 0x00000008,
 127     UNWIND_ARM_FRAME_SECOND_PUSH_R9 = 0x00000010,
 128     UNWIND_ARM_FRAME_SECOND_PUSH_R10 = 0x00000020,
 129     UNWIND_ARM_FRAME_SECOND_PUSH_R11 = 0x00000040,
 130     UNWIND_ARM_FRAME_SECOND_PUSH_R12 = 0x00000080,
 131
 132     UNWIND_ARM_FRAME_D_REG_COUNT_MASK = 0x00000700,
 133
 134     UNWIND_ARM_DWARF_SECTION_OFFSET = 0x00FFFFFF,
 135 };
 136 }
 137
 138 #ifndef UNWIND_SECOND_LEVEL_REGULAR
 139 #define UNWIND_SECOND_LEVEL_REGULAR 2
 140 #endif
 141
 142 #ifndef UNWIND_SECOND_LEVEL_COMPRESSED
 143 #define UNWIND_SECOND_LEVEL_COMPRESSED 3
 144 #endif
 145
 146 #ifndef UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET
 147 #define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry) (entry & 0x00FFFFFF)
 148 #endif
 149
 150 #ifndef UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX
 151 #define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry)                     \
 152   ((entry >> 24) & 0xFF)
 153 #endif
 154
 155 #define EXTRACT_BITS(value, mask)                                              \
 156   ((value >>                                                                   \
 157     llvm::countTrailingZeros(static_cast<uint32_t>(mask), llvm::ZB_Width)) &   \
 158    (((1 << llvm::countPopulation(static_cast<uint32_t>(mask)))) - 1))
 159
 160 // constructor
 161
 162 CompactUnwindInfo::CompactUnwindInfo(ObjectFile &objfile, SectionSP &section_sp)
 163     : m_objfile(objfile), m_section_sp(section_sp),
 164       m_section_contents_if_encrypted(), m_mutex(), m_indexes(),
 165       m_indexes_computed(eLazyBoolCalculate), m_unwindinfo_data(),
 166       m_unwindinfo_data_computed(false), m_unwind_header() {}
 167
 168 // destructor
 169
 170 CompactUnwindInfo::~CompactUnwindInfo() {}
 171
 172 bool CompactUnwindInfo::GetUnwindPlan(Target &target, Address addr,
 173                                       UnwindPlan &unwind_plan) {
 174   if (!IsValid(target.GetProcessSP())) {
 175     return false;
 176   }
 177   FunctionInfo function_info;
 178   if (GetCompactUnwindInfoForFunction(target, addr, function_info)) {
 179     // shortcut return for functions that have no compact unwind
 180     if (function_info.encoding == 0)
 181       return false;
 182
 183     if (ArchSpec arch = m_objfile.GetArchitecture()) {
 184
 185       Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_UNWIND));
 186       if (log && log->GetVerbose()) {
 187         StreamString strm;
 188         addr.Dump(
 189             &strm, nullptr,
 190             Address::DumpStyle::DumpStyleResolvedDescriptionNoFunctionArguments,
 191             Address::DumpStyle::DumpStyleFileAddress,
 192             arch.GetAddressByteSize());
 193         LLDB_LOGF(log, "Got compact unwind encoding 0x%x for function %s",
 194                   function_info.encoding, strm.GetData());
 195       }
 196
 197       if (function_info.valid_range_offset_start != 0 &&
 198           function_info.valid_range_offset_end != 0) {
 199         SectionList *sl = m_objfile.GetSectionList();
 200         if (sl) {
 201           addr_t func_range_start_file_addr =
 202               function_info.valid_range_offset_start +
 203               m_objfile.GetBaseAddress().GetFileAddress();
 204           AddressRange func_range(func_range_start_file_addr,
 205                                   function_info.valid_range_offset_end -
 206                                       function_info.valid_range_offset_start,
 207                                   sl);
 208           unwind_plan.SetPlanValidAddressRange(func_range);
 209         }
 210       }
 211
 212       if (arch.GetTriple().getArch() == llvm::Triple::x86_64) {
 213         return CreateUnwindPlan_x86_64(target, function_info, unwind_plan,
 214                                        addr);
 215       }
 216       if (arch.GetTriple().getArch() == llvm::Triple::aarch64 ||
 217           arch.GetTriple().getArch() == llvm::Triple::aarch64_32) {
 218         return CreateUnwindPlan_arm64(target, function_info, unwind_plan, addr);
 219       }
 220       if (arch.GetTriple().getArch() == llvm::Triple::x86) {
 221         return CreateUnwindPlan_i386(target, function_info, unwind_plan, addr);
 222       }
 223       if (arch.GetTriple().getArch() == llvm::Triple::arm ||
 224           arch.GetTriple().getArch() == llvm::Triple::thumb) {
 225         return CreateUnwindPlan_armv7(target, function_info, unwind_plan, addr);
 226       }
 227     }
 228   }
 229   return false;
 230 }
 231
 232 bool CompactUnwindInfo::IsValid(const ProcessSP &process_sp) {
 233   if (m_section_sp.get() == nullptr)
 234     return false;
 235
 236   if (m_indexes_computed == eLazyBoolYes && m_unwindinfo_data_computed)
 237     return true;
 238
 239   ScanIndex(process_sp);
 240
 241   return m_indexes_computed == eLazyBoolYes && m_unwindinfo_data_computed;
 242 }
 243
 244 void CompactUnwindInfo::ScanIndex(const ProcessSP &process_sp) {
 245   std::lock_guard<std::mutex> guard(m_mutex);
 246   if (m_indexes_computed == eLazyBoolYes && m_unwindinfo_data_computed)
 247     return;
 248
 249   // We can't read the index for some reason.
 250   if (m_indexes_computed == eLazyBoolNo) {
 251     return;
 252   }
 253
 254   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_UNWIND));
 255   if (log)
 256     m_objfile.GetModule()->LogMessage(
 257         log, "Reading compact unwind first-level indexes");
 258
 259   if (!m_unwindinfo_data_computed) {
 260     if (m_section_sp->IsEncrypted()) {
 261       // Can't get section contents of a protected/encrypted section until we
 262       // have a live process and can read them out of memory.
 263       if (process_sp.get() == nullptr)
 264         return;
 265       m_section_contents_if_encrypted =
 266           std::make_shared<DataBufferHeap>(m_section_sp->GetByteSize(), 0);
 267       Status error;
 268       if (process_sp->ReadMemory(
 269               m_section_sp->GetLoadBaseAddress(&process_sp->GetTarget()),
 270               m_section_contents_if_encrypted->GetBytes(),
 271               m_section_sp->GetByteSize(),
 272               error) == m_section_sp->GetByteSize() &&
 273           error.Success()) {
 274         m_unwindinfo_data.SetAddressByteSize(
 275             process_sp->GetTarget().GetArchitecture().GetAddressByteSize());
 276         m_unwindinfo_data.SetByteOrder(
 277             process_sp->GetTarget().GetArchitecture().GetByteOrder());
 278         m_unwindinfo_data.SetData(m_section_contents_if_encrypted, 0);
 279       }
 280     } else {
 281       m_objfile.ReadSectionData(m_section_sp.get(), m_unwindinfo_data);
 282     }
 283     if (m_unwindinfo_data.GetByteSize() != m_section_sp->GetByteSize())
 284       return;
 285     m_unwindinfo_data_computed = true;
 286   }
 287
 288   if (m_unwindinfo_data.GetByteSize() > 0) {
 289     offset_t offset = 0;
 290
 291     // struct unwind_info_section_header
 292     // {
 293     // uint32_t    version;            // UNWIND_SECTION_VERSION
 294     // uint32_t    commonEncodingsArraySectionOffset;
 295     // uint32_t    commonEncodingsArrayCount;
 296     // uint32_t    personalityArraySectionOffset;
 297     // uint32_t    personalityArrayCount;
 298     // uint32_t    indexSectionOffset;
 299     // uint32_t    indexCount;
 300
 301     m_unwind_header.version = m_unwindinfo_data.GetU32(&offset);
 302     m_unwind_header.common_encodings_array_offset =
 303         m_unwindinfo_data.GetU32(&offset);
 304     m_unwind_header.common_encodings_array_count =
 305         m_unwindinfo_data.GetU32(&offset);
 306     m_unwind_header.personality_array_offset =
 307         m_unwindinfo_data.GetU32(&offset);
 308     m_unwind_header.personality_array_count = m_unwindinfo_data.GetU32(&offset);
 309     uint32_t indexSectionOffset = m_unwindinfo_data.GetU32(&offset);
 310
 311     uint32_t indexCount = m_unwindinfo_data.GetU32(&offset);
 312
 313     if (m_unwind_header.common_encodings_array_offset >
 314             m_unwindinfo_data.GetByteSize() ||
 315         m_unwind_header.personality_array_offset >
 316             m_unwindinfo_data.GetByteSize() ||
 317         indexSectionOffset > m_unwindinfo_data.GetByteSize() ||
 318         offset > m_unwindinfo_data.GetByteSize()) {
 319       Host::SystemLog(Host::eSystemLogError, "error: Invalid offset "
 320                                              "encountered in compact unwind "
 321                                              "info, skipping\n");
 322       // don't trust anything from this compact_unwind section if it looks
 323       // blatantly invalid data in the header.
 324       m_indexes_computed = eLazyBoolNo;
 325       return;
 326     }
 327
 328     // Parse the basic information from the indexes We wait to scan the second
 329     // level page info until it's needed
 330
 331     // struct unwind_info_section_header_index_entry {
 332     //     uint32_t        functionOffset;
 333     //     uint32_t        secondLevelPagesSectionOffset;
 334     //     uint32_t        lsdaIndexArraySectionOffset;
 335     // };
 336
 337     bool clear_address_zeroth_bit = false;
 338     if (ArchSpec arch = m_objfile.GetArchitecture()) {
 339       if (arch.GetTriple().getArch() == llvm::Triple::arm ||
 340           arch.GetTriple().getArch() == llvm::Triple::thumb)
 341         clear_address_zeroth_bit = true;
 342     }
 343
 344     offset = indexSectionOffset;
 345     for (uint32_t idx = 0; idx < indexCount; idx++) {
 346       uint32_t function_offset =
 347           m_unwindinfo_data.GetU32(&offset); // functionOffset
 348       uint32_t second_level_offset =
 349           m_unwindinfo_data.GetU32(&offset); // secondLevelPagesSectionOffset
 350       uint32_t lsda_offset =
 351           m_unwindinfo_data.GetU32(&offset); // lsdaIndexArraySectionOffset
 352
 353       if (second_level_offset > m_section_sp->GetByteSize() ||
 354           lsda_offset > m_section_sp->GetByteSize()) {
 355         m_indexes_computed = eLazyBoolNo;
 356       }
 357
 358       if (clear_address_zeroth_bit)
 359         function_offset &= ~1ull;
 360
 361       UnwindIndex this_index;
 362       this_index.function_offset = function_offset;
 363       this_index.second_level = second_level_offset;
 364       this_index.lsda_array_start = lsda_offset;
 365
 366       if (m_indexes.size() > 0) {
 367         m_indexes[m_indexes.size() - 1].lsda_array_end = lsda_offset;
 368       }
 369
 370       if (second_level_offset == 0) {
 371         this_index.sentinal_entry = true;
 372       }
 373
 374       m_indexes.push_back(this_index);
 375     }
 376     m_indexes_computed = eLazyBoolYes;
 377   } else {
 378     m_indexes_computed = eLazyBoolNo;
 379   }
 380 }
 381
 382 uint32_t CompactUnwindInfo::GetLSDAForFunctionOffset(uint32_t lsda_offset,
 383                                                      uint32_t lsda_count,
 384                                                      uint32_t function_offset) {
 385   // struct unwind_info_section_header_lsda_index_entry {
 386   //         uint32_t        functionOffset;
 387   //         uint32_t        lsdaOffset;
 388   // };
 389
 390   offset_t first_entry = lsda_offset;
 391   uint32_t low = 0;
 392   uint32_t high = lsda_count;
 393   while (low < high) {
 394     uint32_t mid = (low + high) / 2;
 395     offset_t offset = first_entry + (mid * 8);
 396     uint32_t mid_func_offset =
 397         m_unwindinfo_data.GetU32(&offset); // functionOffset
 398     uint32_t mid_lsda_offset = m_unwindinfo_data.GetU32(&offset); // lsdaOffset
 399     if (mid_func_offset == function_offset) {
 400       return mid_lsda_offset;
 401     }
 402     if (mid_func_offset < function_offset) {
 403       low = mid + 1;
 404     } else {
 405       high = mid;
 406     }
 407   }
 408   return 0;
 409 }
 410
 411 lldb::offset_t CompactUnwindInfo::BinarySearchRegularSecondPage(
 412     uint32_t entry_page_offset, uint32_t entry_count, uint32_t function_offset,
 413     uint32_t *entry_func_start_offset, uint32_t *entry_func_end_offset) {
 414   // typedef uint32_t compact_unwind_encoding_t;
 415   // struct unwind_info_regular_second_level_entry {
 416   //     uint32_t                    functionOffset;
 417   //     compact_unwind_encoding_t    encoding;
 418
 419   offset_t first_entry = entry_page_offset;
 420
 421   uint32_t low = 0;
 422   uint32_t high = entry_count;
 423   uint32_t last = high - 1;
 424   while (low < high) {
 425     uint32_t mid = (low + high) / 2;
 426     offset_t offset = first_entry + (mid * 8);
 427     uint32_t mid_func_offset =
 428         m_unwindinfo_data.GetU32(&offset); // functionOffset
 429     uint32_t next_func_offset = 0;
 430     if (mid < last) {
 431       offset = first_entry + ((mid + 1) * 8);
 432       next_func_offset = m_unwindinfo_data.GetU32(&offset); // functionOffset
 433     }
 434     if (mid_func_offset <= function_offset) {
 435       if (mid == last || (next_func_offset > function_offset)) {
 436         if (entry_func_start_offset)
 437           *entry_func_start_offset = mid_func_offset;
 438         if (mid != last && entry_func_end_offset)
 439           *entry_func_end_offset = next_func_offset;
 440         return first_entry + (mid * 8);
 441       } else {
 442         low = mid + 1;
 443       }
 444     } else {
 445       high = mid;
 446     }
 447   }
 448   return LLDB_INVALID_OFFSET;
 449 }
 450
 451 uint32_t CompactUnwindInfo::BinarySearchCompressedSecondPage(
 452     uint32_t entry_page_offset, uint32_t entry_count,
 453     uint32_t function_offset_to_find, uint32_t function_offset_base,
 454     uint32_t *entry_func_start_offset, uint32_t *entry_func_end_offset) {
 455   offset_t first_entry = entry_page_offset;
 456
 457   uint32_t low = 0;
 458   uint32_t high = entry_count;
 459   uint32_t last = high - 1;
 460   while (low < high) {
 461     uint32_t mid = (low + high) / 2;
 462     offset_t offset = first_entry + (mid * 4);
 463     uint32_t entry = m_unwindinfo_data.GetU32(&offset); // entry
 464     uint32_t mid_func_offset = UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry);
 465     mid_func_offset += function_offset_base;
 466     uint32_t next_func_offset = 0;
 467     if (mid < last) {
 468       offset = first_entry + ((mid + 1) * 4);
 469       uint32_t next_entry = m_unwindinfo_data.GetU32(&offset); // entry
 470       next_func_offset = UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(next_entry);
 471       next_func_offset += function_offset_base;
 472     }
 473     if (mid_func_offset <= function_offset_to_find) {
 474       if (mid == last || (next_func_offset > function_offset_to_find)) {
 475         if (entry_func_start_offset)
 476           *entry_func_start_offset = mid_func_offset;
 477         if (mid != last && entry_func_end_offset)
 478           *entry_func_end_offset = next_func_offset;
 479         return UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry);
 480       } else {
 481         low = mid + 1;
 482       }
 483     } else {
 484       high = mid;
 485     }
 486   }
 487
 488   return UINT32_MAX;
 489 }
 490
 491 bool CompactUnwindInfo::GetCompactUnwindInfoForFunction(
 492     Target &target, Address address, FunctionInfo &unwind_info) {
 493   unwind_info.encoding = 0;
 494   unwind_info.lsda_address.Clear();
 495   unwind_info.personality_ptr_address.Clear();
 496
 497   if (!IsValid(target.GetProcessSP()))
 498     return false;
 499
 500   addr_t text_section_file_address = LLDB_INVALID_ADDRESS;
 501   SectionList *sl = m_objfile.GetSectionList();
 502   if (sl) {
 503     SectionSP text_sect = sl->FindSectionByType(eSectionTypeCode, true);
 504     if (text_sect.get()) {
 505       text_section_file_address = text_sect->GetFileAddress();
 506     }
 507   }
 508   if (text_section_file_address == LLDB_INVALID_ADDRESS)
 509     return false;
 510
 511   addr_t function_offset =
 512       address.GetFileAddress() - m_objfile.GetBaseAddress().GetFileAddress();
 513
 514   UnwindIndex key;
 515   key.function_offset = function_offset;
 516
 517   std::vector<UnwindIndex>::const_iterator it;
 518   it = std::lower_bound(m_indexes.begin(), m_indexes.end(), key);
 519   if (it == m_indexes.end()) {
 520     return false;
 521   }
 522
 523   if (it->function_offset != key.function_offset) {
 524     if (it != m_indexes.begin())
 525       --it;
 526   }
 527
 528   if (it->sentinal_entry) {
 529     return false;
 530   }
 531
 532   auto next_it = it + 1;
 533   if (next_it != m_indexes.end()) {
 534     // initialize the function offset end range to be the start of the next
 535     // index offset.  If we find an entry which is at the end of the index
 536     // table, this will establish the range end.
 537     unwind_info.valid_range_offset_end = next_it->function_offset;
 538   }
 539
 540   offset_t second_page_offset = it->second_level;
 541   offset_t lsda_array_start = it->lsda_array_start;
 542   offset_t lsda_array_count = (it->lsda_array_end - it->lsda_array_start) / 8;
 543
 544   offset_t offset = second_page_offset;
 545   uint32_t kind = m_unwindinfo_data.GetU32(
 546       &offset); // UNWIND_SECOND_LEVEL_REGULAR or UNWIND_SECOND_LEVEL_COMPRESSED
 547
 548   if (kind == UNWIND_SECOND_LEVEL_REGULAR) {
 549     // struct unwind_info_regular_second_level_page_header {
 550     //     uint32_t    kind;    // UNWIND_SECOND_LEVEL_REGULAR
 551     //     uint16_t    entryPageOffset;
 552     //     uint16_t    entryCount;
 553
 554     // typedef uint32_t compact_unwind_encoding_t;
 555     // struct unwind_info_regular_second_level_entry {
 556     //     uint32_t                    functionOffset;
 557     //     compact_unwind_encoding_t    encoding;
 558
 559     uint16_t entry_page_offset =
 560         m_unwindinfo_data.GetU16(&offset);                    // entryPageOffset
 561     uint16_t entry_count = m_unwindinfo_data.GetU16(&offset); // entryCount
 562
 563     offset_t entry_offset = BinarySearchRegularSecondPage(
 564         second_page_offset + entry_page_offset, entry_count, function_offset,
 565         &unwind_info.valid_range_offset_start,
 566         &unwind_info.valid_range_offset_end);
 567     if (entry_offset == LLDB_INVALID_OFFSET) {
 568       return false;
 569     }
 570     entry_offset += 4; // skip over functionOffset
 571     unwind_info.encoding = m_unwindinfo_data.GetU32(&entry_offset); // encoding
 572     if (unwind_info.encoding & UNWIND_HAS_LSDA) {
 573       SectionList *sl = m_objfile.GetSectionList();
 574       if (sl) {
 575         uint32_t lsda_offset = GetLSDAForFunctionOffset(
 576             lsda_array_start, lsda_array_count, function_offset);
 577         addr_t objfile_base_address =
 578             m_objfile.GetBaseAddress().GetFileAddress();
 579         unwind_info.lsda_address.ResolveAddressUsingFileSections(
 580             objfile_base_address + lsda_offset, sl);
 581       }
 582     }
 583     if (unwind_info.encoding & UNWIND_PERSONALITY_MASK) {
 584       uint32_t personality_index =
 585           EXTRACT_BITS(unwind_info.encoding, UNWIND_PERSONALITY_MASK);
 586
 587       if (personality_index > 0) {
 588         personality_index--;
 589         if (personality_index < m_unwind_header.personality_array_count) {
 590           offset_t offset = m_unwind_header.personality_array_offset;
 591           offset += 4 * personality_index;
 592           SectionList *sl = m_objfile.GetSectionList();
 593           if (sl) {
 594             uint32_t personality_offset = m_unwindinfo_data.GetU32(&offset);
 595             addr_t objfile_base_address =
 596                 m_objfile.GetBaseAddress().GetFileAddress();
 597             unwind_info.personality_ptr_address.ResolveAddressUsingFileSections(
 598                 objfile_base_address + personality_offset, sl);
 599           }
 600         }
 601       }
 602     }
 603     return true;
 604   } else if (kind == UNWIND_SECOND_LEVEL_COMPRESSED) {
 605     // struct unwind_info_compressed_second_level_page_header {
 606     //     uint32_t    kind;    // UNWIND_SECOND_LEVEL_COMPRESSED
 607     //     uint16_t    entryPageOffset;         // offset from this 2nd lvl page
 608     //     idx to array of entries
 609     //                                          // (an entry has a function
 610     //                                          offset and index into the
 611     //                                          encodings)
 612     //                                          // NB function offset from the
 613     //                                          entry in the compressed page
 614     //                                          // must be added to the index's
 615     //                                          functionOffset value.
 616     //     uint16_t    entryCount;
 617     //     uint16_t    encodingsPageOffset;     // offset from this 2nd lvl page
 618     //     idx to array of encodings
 619     //     uint16_t    encodingsCount;
 620
 621     uint16_t entry_page_offset =
 622         m_unwindinfo_data.GetU16(&offset);                    // entryPageOffset
 623     uint16_t entry_count = m_unwindinfo_data.GetU16(&offset); // entryCount
 624     uint16_t encodings_page_offset =
 625         m_unwindinfo_data.GetU16(&offset); // encodingsPageOffset
 626     uint16_t encodings_count =
 627         m_unwindinfo_data.GetU16(&offset); // encodingsCount
 628
 629     uint32_t encoding_index = BinarySearchCompressedSecondPage(
 630         second_page_offset + entry_page_offset, entry_count, function_offset,
 631         it->function_offset, &unwind_info.valid_range_offset_start,
 632         &unwind_info.valid_range_offset_end);
 633     if (encoding_index == UINT32_MAX ||
 634         encoding_index >=
 635             encodings_count + m_unwind_header.common_encodings_array_count) {
 636       return false;
 637     }
 638     uint32_t encoding = 0;
 639     if (encoding_index < m_unwind_header.common_encodings_array_count) {
 640       offset = m_unwind_header.common_encodings_array_offset +
 641                (encoding_index * sizeof(uint32_t));
 642       encoding = m_unwindinfo_data.GetU32(
 643           &offset); // encoding entry from the commonEncodingsArray
 644     } else {
 645       uint32_t page_specific_entry_index =
 646           encoding_index - m_unwind_header.common_encodings_array_count;
 647       offset = second_page_offset + encodings_page_offset +
 648                (page_specific_entry_index * sizeof(uint32_t));
 649       encoding = m_unwindinfo_data.GetU32(
 650           &offset); // encoding entry from the page-specific encoding array
 651     }
 652     if (encoding == 0)
 653       return false;
 654
 655     unwind_info.encoding = encoding;
 656     if (unwind_info.encoding & UNWIND_HAS_LSDA) {
 657       SectionList *sl = m_objfile.GetSectionList();
 658       if (sl) {
 659         uint32_t lsda_offset = GetLSDAForFunctionOffset(
 660             lsda_array_start, lsda_array_count, function_offset);
 661         addr_t objfile_base_address =
 662             m_objfile.GetBaseAddress().GetFileAddress();
 663         unwind_info.lsda_address.ResolveAddressUsingFileSections(
 664             objfile_base_address + lsda_offset, sl);
 665       }
 666     }
 667     if (unwind_info.encoding & UNWIND_PERSONALITY_MASK) {
 668       uint32_t personality_index =
 669           EXTRACT_BITS(unwind_info.encoding, UNWIND_PERSONALITY_MASK);
 670
 671       if (personality_index > 0) {
 672         personality_index--;
 673         if (personality_index < m_unwind_header.personality_array_count) {
 674           offset_t offset = m_unwind_header.personality_array_offset;
 675           offset += 4 * personality_index;
 676           SectionList *sl = m_objfile.GetSectionList();
 677           if (sl) {
 678             uint32_t personality_offset = m_unwindinfo_data.GetU32(&offset);
 679             addr_t objfile_base_address =
 680                 m_objfile.GetBaseAddress().GetFileAddress();
 681             unwind_info.personality_ptr_address.ResolveAddressUsingFileSections(
 682                 objfile_base_address + personality_offset, sl);
 683           }
 684         }
 685       }
 686     }
 687     return true;
 688   }
 689   return false;
 690 }
 691
 692 enum x86_64_eh_regnum {
 693   rax = 0,
 694   rdx = 1,
 695   rcx = 2,
 696   rbx = 3,
 697   rsi = 4,
 698   rdi = 5,
 699   rbp = 6,
 700   rsp = 7,
 701   r8 = 8,
 702   r9 = 9,
 703   r10 = 10,
 704   r11 = 11,
 705   r12 = 12,
 706   r13 = 13,
 707   r14 = 14,
 708   r15 = 15,
 709   rip = 16 // this is officially the Return Address register number, but close
 710            // enough
 711 };
 712
 713 // Convert the compact_unwind_info.h register numbering scheme to
 714 // eRegisterKindEHFrame (eh_frame) register numbering scheme.
 715 uint32_t translate_to_eh_frame_regnum_x86_64(uint32_t unwind_regno) {
 716   switch (unwind_regno) {
 717   case UNWIND_X86_64_REG_RBX:
 718     return x86_64_eh_regnum::rbx;
 719   case UNWIND_X86_64_REG_R12:
 720     return x86_64_eh_regnum::r12;
 721   case UNWIND_X86_64_REG_R13:
 722     return x86_64_eh_regnum::r13;
 723   case UNWIND_X86_64_REG_R14:
 724     return x86_64_eh_regnum::r14;
 725   case UNWIND_X86_64_REG_R15:
 726     return x86_64_eh_regnum::r15;
 727   case UNWIND_X86_64_REG_RBP:
 728     return x86_64_eh_regnum::rbp;
 729   default:
 730     return LLDB_INVALID_REGNUM;
 731   }
 732 }
 733
 734 bool CompactUnwindInfo::CreateUnwindPlan_x86_64(Target &target,
 735                                                 FunctionInfo &function_info,
 736                                                 UnwindPlan &unwind_plan,
 737                                                 Address pc_or_function_start) {
 738   unwind_plan.SetSourceName("compact unwind info");
 739   unwind_plan.SetSourcedFromCompiler(eLazyBoolYes);
 740   unwind_plan.SetUnwindPlanValidAtAllInstructions(eLazyBoolNo);
 741   unwind_plan.SetUnwindPlanForSignalTrap(eLazyBoolNo);
 742   unwind_plan.SetRegisterKind(eRegisterKindEHFrame);
 743
 744   unwind_plan.SetLSDAAddress(function_info.lsda_address);
 745   unwind_plan.SetPersonalityFunctionPtr(function_info.personality_ptr_address);
 746
 747   UnwindPlan::RowSP row(new UnwindPlan::Row);
 748
 749   const int wordsize = 8;
 750   int mode = function_info.encoding & UNWIND_X86_64_MODE_MASK;
 751   switch (mode) {
 752   case UNWIND_X86_64_MODE_RBP_FRAME: {
 753     row->GetCFAValue().SetIsRegisterPlusOffset(
 754         translate_to_eh_frame_regnum_x86_64(UNWIND_X86_64_REG_RBP),
 755         2 * wordsize);
 756     row->SetOffset(0);
 757     row->SetRegisterLocationToAtCFAPlusOffset(x86_64_eh_regnum::rbp,
 758                                               wordsize * -2, true);
 759     row->SetRegisterLocationToAtCFAPlusOffset(x86_64_eh_regnum::rip,
 760                                               wordsize * -1, true);
 761     row->SetRegisterLocationToIsCFAPlusOffset(x86_64_eh_regnum::rsp, 0, true);
 762
 763     uint32_t saved_registers_offset =
 764         EXTRACT_BITS(function_info.encoding, UNWIND_X86_64_RBP_FRAME_OFFSET);
 765
 766     uint32_t saved_registers_locations =
 767         EXTRACT_BITS(function_info.encoding, UNWIND_X86_64_RBP_FRAME_REGISTERS);
 768
 769     saved_registers_offset += 2;
 770
 771     for (int i = 0; i < 5; i++) {
 772       uint32_t regnum = saved_registers_locations & 0x7;
 773       switch (regnum) {
 774       case UNWIND_X86_64_REG_NONE:
 775         break;
 776       case UNWIND_X86_64_REG_RBX:
 777       case UNWIND_X86_64_REG_R12:
 778       case UNWIND_X86_64_REG_R13:
 779       case UNWIND_X86_64_REG_R14:
 780       case UNWIND_X86_64_REG_R15:
 781         row->SetRegisterLocationToAtCFAPlusOffset(
 782             translate_to_eh_frame_regnum_x86_64(regnum),
 783             wordsize * -saved_registers_offset, true);
 784         break;
 785       }
 786       saved_registers_offset--;
 787       saved_registers_locations >>= 3;
 788     }
 789     unwind_plan.AppendRow(row);
 790     return true;
 791   } break;
 792
 793   case UNWIND_X86_64_MODE_STACK_IND: {
 794     // The clang in Xcode 6 is emitting incorrect compact unwind encodings for
 795     // this style of unwind.  It was fixed in llvm r217020. The clang in Xcode
 796     // 7 has this fixed.
 797     return false;
 798   } break;
 799
 800   case UNWIND_X86_64_MODE_STACK_IMMD: {
 801     uint32_t stack_size = EXTRACT_BITS(function_info.encoding,
 802                                        UNWIND_X86_64_FRAMELESS_STACK_SIZE);
 803     uint32_t register_count = EXTRACT_BITS(
 804         function_info.encoding, UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT);
 805     uint32_t permutation = EXTRACT_BITS(
 806         function_info.encoding, UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION);
 807
 808     if (mode == UNWIND_X86_64_MODE_STACK_IND &&
 809         function_info.valid_range_offset_start != 0) {
 810       uint32_t stack_adjust = EXTRACT_BITS(
 811           function_info.encoding, UNWIND_X86_64_FRAMELESS_STACK_ADJUST);
 812
 813       // offset into the function instructions; 0 == beginning of first
 814       // instruction
 815       uint32_t offset_to_subl_insn = EXTRACT_BITS(
 816           function_info.encoding, UNWIND_X86_64_FRAMELESS_STACK_SIZE);
 817
 818       SectionList *sl = m_objfile.GetSectionList();
 819       if (sl) {
 820         ProcessSP process_sp = target.GetProcessSP();
 821         if (process_sp) {
 822           Address subl_payload_addr(function_info.valid_range_offset_start, sl);
 823           subl_payload_addr.Slide(offset_to_subl_insn);
 824           Status error;
 825           uint64_t large_stack_size = process_sp->ReadUnsignedIntegerFromMemory(
 826               subl_payload_addr.GetLoadAddress(&target), 4, 0, error);
 827           if (large_stack_size != 0 && error.Success()) {
 828             // Got the large stack frame size correctly - use it
 829             stack_size = large_stack_size + (stack_adjust * wordsize);
 830           } else {
 831             return false;
 832           }
 833         } else {
 834           return false;
 835         }
 836       } else {
 837         return false;
 838       }
 839     }
 840
 841     int32_t offset = mode == UNWIND_X86_64_MODE_STACK_IND
 842                          ? stack_size
 843                          : stack_size * wordsize;
 844     row->GetCFAValue().SetIsRegisterPlusOffset(x86_64_eh_regnum::rsp, offset);
 845
 846     row->SetOffset(0);
 847     row->SetRegisterLocationToAtCFAPlusOffset(x86_64_eh_regnum::rip,
 848                                               wordsize * -1, true);
 849     row->SetRegisterLocationToIsCFAPlusOffset(x86_64_eh_regnum::rsp, 0, true);
 850
 851     if (register_count > 0) {
 852
 853       // We need to include (up to) 6 registers in 10 bits. That would be 18
 854       // bits if we just used 3 bits per reg to indicate the order they're
 855       // saved on the stack.
 856       //
 857       // This is done with Lehmer code permutation, e.g. see
 858       // http://stackoverflow.com/questions/1506078/fast-permutation-number-
 859       // permutation-mapping-algorithms
 860       int permunreg[6] = {0, 0, 0, 0, 0, 0};
 861
 862       // This decodes the variable-base number in the 10 bits and gives us the
 863       // Lehmer code sequence which can then be decoded.
 864
 865       switch (register_count) {
 866       case 6:
 867         permunreg[0] = permutation / 120; // 120 == 5!
 868         permutation -= (permunreg[0] * 120);
 869         permunreg[1] = permutation / 24; // 24 == 4!
 870         permutation -= (permunreg[1] * 24);
 871         permunreg[2] = permutation / 6; // 6 == 3!
 872         permutation -= (permunreg[2] * 6);
 873         permunreg[3] = permutation / 2; // 2 == 2!
 874         permutation -= (permunreg[3] * 2);
 875         permunreg[4] = permutation; // 1 == 1!
 876         permunreg[5] = 0;
 877         break;
 878       case 5:
 879         permunreg[0] = permutation / 120;
 880         permutation -= (permunreg[0] * 120);
 881         permunreg[1] = permutation / 24;
 882         permutation -= (permunreg[1] * 24);
 883         permunreg[2] = permutation / 6;
 884         permutation -= (permunreg[2] * 6);
 885         permunreg[3] = permutation / 2;
 886         permutation -= (permunreg[3] * 2);
 887         permunreg[4] = permutation;
 888         break;
 889       case 4:
 890         permunreg[0] = permutation / 60;
 891         permutation -= (permunreg[0] * 60);
 892         permunreg[1] = permutation / 12;
 893         permutation -= (permunreg[1] * 12);
 894         permunreg[2] = permutation / 3;
 895         permutation -= (permunreg[2] * 3);
 896         permunreg[3] = permutation;
 897         break;
 898       case 3:
 899         permunreg[0] = permutation / 20;
 900         permutation -= (permunreg[0] * 20);
 901         permunreg[1] = permutation / 4;
 902         permutation -= (permunreg[1] * 4);
 903         permunreg[2] = permutation;
 904         break;
 905       case 2:
 906         permunreg[0] = permutation / 5;
 907         permutation -= (permunreg[0] * 5);
 908         permunreg[1] = permutation;
 909         break;
 910       case 1:
 911         permunreg[0] = permutation;
 912         break;
 913       }
 914
 915       // Decode the Lehmer code for this permutation of the registers v.
 916       // http://en.wikipedia.org/wiki/Lehmer_code
 917
 918       int registers[6] = {UNWIND_X86_64_REG_NONE, UNWIND_X86_64_REG_NONE,
 919                           UNWIND_X86_64_REG_NONE, UNWIND_X86_64_REG_NONE,
 920                           UNWIND_X86_64_REG_NONE, UNWIND_X86_64_REG_NONE};
 921       bool used[7] = {false, false, false, false, false, false, false};
 922       for (uint32_t i = 0; i < register_count; i++) {
 923         int renum = 0;
 924         for (int j = 1; j < 7; j++) {
 925           if (!used[j]) {
 926             if (renum == permunreg[i]) {
 927               registers[i] = j;
 928               used[j] = true;
 929               break;
 930             }
 931             renum++;
 932           }
 933         }
 934       }
 935
 936       uint32_t saved_registers_offset = 1;
 937       saved_registers_offset++;
 938
 939       for (int i = (sizeof(registers) / sizeof(int)) - 1; i >= 0; i--) {
 940         switch (registers[i]) {
 941         case UNWIND_X86_64_REG_NONE:
 942           break;
 943         case UNWIND_X86_64_REG_RBX:
 944         case UNWIND_X86_64_REG_R12:
 945         case UNWIND_X86_64_REG_R13:
 946         case UNWIND_X86_64_REG_R14:
 947         case UNWIND_X86_64_REG_R15:
 948         case UNWIND_X86_64_REG_RBP:
 949           row->SetRegisterLocationToAtCFAPlusOffset(
 950               translate_to_eh_frame_regnum_x86_64(registers[i]),
 951               wordsize * -saved_registers_offset, true);
 952           saved_registers_offset++;
 953           break;
 954         }
 955       }
 956     }
 957     unwind_plan.AppendRow(row);
 958     return true;
 959   } break;
 960
 961   case UNWIND_X86_64_MODE_DWARF: {
 962     return false;
 963   } break;
 964
 965   case 0: {
 966     return false;
 967   } break;
 968   }
 969   return false;
 970 }
 971
 972 enum i386_eh_regnum {
 973   eax = 0,
 974   ecx = 1,
 975   edx = 2,
 976   ebx = 3,
 977   ebp = 4,
 978   esp = 5,
 979   esi = 6,
 980   edi = 7,
 981   eip = 8 // this is officially the Return Address register number, but close
 982           // enough
 983 };
 984
 985 // Convert the compact_unwind_info.h register numbering scheme to
 986 // eRegisterKindEHFrame (eh_frame) register numbering scheme.
 987 uint32_t translate_to_eh_frame_regnum_i386(uint32_t unwind_regno) {
 988   switch (unwind_regno) {
 989   case UNWIND_X86_REG_EBX:
 990     return i386_eh_regnum::ebx;
 991   case UNWIND_X86_REG_ECX:
 992     return i386_eh_regnum::ecx;
 993   case UNWIND_X86_REG_EDX:
 994     return i386_eh_regnum::edx;
 995   case UNWIND_X86_REG_EDI:
 996     return i386_eh_regnum::edi;
 997   case UNWIND_X86_REG_ESI:
 998     return i386_eh_regnum::esi;
 999   case UNWIND_X86_REG_EBP:
1000     return i386_eh_regnum::ebp;
1001   default:
1002     return LLDB_INVALID_REGNUM;
1003   }
1004 }
1005
1006 bool CompactUnwindInfo::CreateUnwindPlan_i386(Target &target,
1007                                               FunctionInfo &function_info,
1008                                               UnwindPlan &unwind_plan,
1009                                               Address pc_or_function_start) {
1010   unwind_plan.SetSourceName("compact unwind info");
1011   unwind_plan.SetSourcedFromCompiler(eLazyBoolYes);
1012   unwind_plan.SetUnwindPlanValidAtAllInstructions(eLazyBoolNo);
1013   unwind_plan.SetUnwindPlanForSignalTrap(eLazyBoolNo);
1014   unwind_plan.SetRegisterKind(eRegisterKindEHFrame);
1015
1016   unwind_plan.SetLSDAAddress(function_info.lsda_address);
1017   unwind_plan.SetPersonalityFunctionPtr(function_info.personality_ptr_address);
1018
1019   UnwindPlan::RowSP row(new UnwindPlan::Row);
1020
1021   const int wordsize = 4;
1022   int mode = function_info.encoding & UNWIND_X86_MODE_MASK;
1023   switch (mode) {
1024   case UNWIND_X86_MODE_EBP_FRAME: {
1025     row->GetCFAValue().SetIsRegisterPlusOffset(
1026         translate_to_eh_frame_regnum_i386(UNWIND_X86_REG_EBP), 2 * wordsize);
1027     row->SetOffset(0);
1028     row->SetRegisterLocationToAtCFAPlusOffset(i386_eh_regnum::ebp,
1029                                               wordsize * -2, true);
1030     row->SetRegisterLocationToAtCFAPlusOffset(i386_eh_regnum::eip,
1031                                               wordsize * -1, true);
1032     row->SetRegisterLocationToIsCFAPlusOffset(i386_eh_regnum::esp, 0, true);
1033
1034     uint32_t saved_registers_offset =
1035         EXTRACT_BITS(function_info.encoding, UNWIND_X86_EBP_FRAME_OFFSET);
1036
1037     uint32_t saved_registers_locations =
1038         EXTRACT_BITS(function_info.encoding, UNWIND_X86_EBP_FRAME_REGISTERS);
1039
1040     saved_registers_offset += 2;
1041
1042     for (int i = 0; i < 5; i++) {
1043       uint32_t regnum = saved_registers_locations & 0x7;
1044       switch (regnum) {
1045       case UNWIND_X86_REG_NONE:
1046         break;
1047       case UNWIND_X86_REG_EBX:
1048       case UNWIND_X86_REG_ECX:
1049       case UNWIND_X86_REG_EDX:
1050       case UNWIND_X86_REG_EDI:
1051       case UNWIND_X86_REG_ESI:
1052         row->SetRegisterLocationToAtCFAPlusOffset(
1053             translate_to_eh_frame_regnum_i386(regnum),
1054             wordsize * -saved_registers_offset, true);
1055         break;
1056       }
1057       saved_registers_offset--;
1058       saved_registers_locations >>= 3;
1059     }
1060     unwind_plan.AppendRow(row);
1061     return true;
1062   } break;
1063
1064   case UNWIND_X86_MODE_STACK_IND:
1065   case UNWIND_X86_MODE_STACK_IMMD: {
1066     uint32_t stack_size =
1067         EXTRACT_BITS(function_info.encoding, UNWIND_X86_FRAMELESS_STACK_SIZE);
1068     uint32_t register_count = EXTRACT_BITS(
1069         function_info.encoding, UNWIND_X86_FRAMELESS_STACK_REG_COUNT);
1070     uint32_t permutation = EXTRACT_BITS(
1071         function_info.encoding, UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION);
1072
1073     if (mode == UNWIND_X86_MODE_STACK_IND &&
1074         function_info.valid_range_offset_start != 0) {
1075       uint32_t stack_adjust = EXTRACT_BITS(function_info.encoding,
1076                                            UNWIND_X86_FRAMELESS_STACK_ADJUST);
1077
1078       // offset into the function instructions; 0 == beginning of first
1079       // instruction
1080       uint32_t offset_to_subl_insn =
1081           EXTRACT_BITS(function_info.encoding, UNWIND_X86_FRAMELESS_STACK_SIZE);
1082
1083       SectionList *sl = m_objfile.GetSectionList();
1084       if (sl) {
1085         ProcessSP process_sp = target.GetProcessSP();
1086         if (process_sp) {
1087           Address subl_payload_addr(function_info.valid_range_offset_start, sl);
1088           subl_payload_addr.Slide(offset_to_subl_insn);
1089           Status error;
1090           uint64_t large_stack_size = process_sp->ReadUnsignedIntegerFromMemory(
1091               subl_payload_addr.GetLoadAddress(&target), 4, 0, error);
1092           if (large_stack_size != 0 && error.Success()) {
1093             // Got the large stack frame size correctly - use it
1094             stack_size = large_stack_size + (stack_adjust * wordsize);
1095           } else {
1096             return false;
1097           }
1098         } else {
1099           return false;
1100         }
1101       } else {
1102         return false;
1103       }
1104     }
1105
1106     int32_t offset =
1107         mode == UNWIND_X86_MODE_STACK_IND ? stack_size : stack_size * wordsize;
1108     row->GetCFAValue().SetIsRegisterPlusOffset(i386_eh_regnum::esp, offset);
1109     row->SetOffset(0);
1110     row->SetRegisterLocationToAtCFAPlusOffset(i386_eh_regnum::eip,
1111                                               wordsize * -1, true);
1112     row->SetRegisterLocationToIsCFAPlusOffset(i386_eh_regnum::esp, 0, true);
1113
1114     if (register_count > 0) {
1115
1116       // We need to include (up to) 6 registers in 10 bits. That would be 18
1117       // bits if we just used 3 bits per reg to indicate the order they're
1118       // saved on the stack.
1119       //
1120       // This is done with Lehmer code permutation, e.g. see
1121       // http://stackoverflow.com/questions/1506078/fast-permutation-number-
1122       // permutation-mapping-algorithms
1123       int permunreg[6] = {0, 0, 0, 0, 0, 0};
1124
1125       // This decodes the variable-base number in the 10 bits and gives us the
1126       // Lehmer code sequence which can then be decoded.
1127
1128       switch (register_count) {
1129       case 6:
1130         permunreg[0] = permutation / 120; // 120 == 5!
1131         permutation -= (permunreg[0] * 120);
1132         permunreg[1] = permutation / 24; // 24 == 4!
1133         permutation -= (permunreg[1] * 24);
1134         permunreg[2] = permutation / 6; // 6 == 3!
1135         permutation -= (permunreg[2] * 6);
1136         permunreg[3] = permutation / 2; // 2 == 2!
1137         permutation -= (permunreg[3] * 2);
1138         permunreg[4] = permutation; // 1 == 1!
1139         permunreg[5] = 0;
1140         break;
1141       case 5:
1142         permunreg[0] = permutation / 120;
1143         permutation -= (permunreg[0] * 120);
1144         permunreg[1] = permutation / 24;
1145         permutation -= (permunreg[1] * 24);
1146         permunreg[2] = permutation / 6;
1147         permutation -= (permunreg[2] * 6);
1148         permunreg[3] = permutation / 2;
1149         permutation -= (permunreg[3] * 2);
1150         permunreg[4] = permutation;
1151         break;
1152       case 4:
1153         permunreg[0] = permutation / 60;
1154         permutation -= (permunreg[0] * 60);
1155         permunreg[1] = permutation / 12;
1156         permutation -= (permunreg[1] * 12);
1157         permunreg[2] = permutation / 3;
1158         permutation -= (permunreg[2] * 3);
1159         permunreg[3] = permutation;
1160         break;
1161       case 3:
1162         permunreg[0] = permutation / 20;
1163         permutation -= (permunreg[0] * 20);
1164         permunreg[1] = permutation / 4;
1165         permutation -= (permunreg[1] * 4);
1166         permunreg[2] = permutation;
1167         break;
1168       case 2:
1169         permunreg[0] = permutation / 5;
1170         permutation -= (permunreg[0] * 5);
1171         permunreg[1] = permutation;
1172         break;
1173       case 1:
1174         permunreg[0] = permutation;
1175         break;
1176       }
1177
1178       // Decode the Lehmer code for this permutation of the registers v.
1179       // http://en.wikipedia.org/wiki/Lehmer_code
1180
1181       int registers[6] = {UNWIND_X86_REG_NONE, UNWIND_X86_REG_NONE,
1182                           UNWIND_X86_REG_NONE, UNWIND_X86_REG_NONE,
1183                           UNWIND_X86_REG_NONE, UNWIND_X86_REG_NONE};
1184       bool used[7] = {false, false, false, false, false, false, false};
1185       for (uint32_t i = 0; i < register_count; i++) {
1186         int renum = 0;
1187         for (int j = 1; j < 7; j++) {
1188           if (!used[j]) {
1189             if (renum == permunreg[i]) {
1190               registers[i] = j;
1191               used[j] = true;
1192               break;
1193             }
1194             renum++;
1195           }
1196         }
1197       }
1198
1199       uint32_t saved_registers_offset = 1;
1200       saved_registers_offset++;
1201
1202       for (int i = (sizeof(registers) / sizeof(int)) - 1; i >= 0; i--) {
1203         switch (registers[i]) {
1204         case UNWIND_X86_REG_NONE:
1205           break;
1206         case UNWIND_X86_REG_EBX:
1207         case UNWIND_X86_REG_ECX:
1208         case UNWIND_X86_REG_EDX:
1209         case UNWIND_X86_REG_EDI:
1210         case UNWIND_X86_REG_ESI:
1211         case UNWIND_X86_REG_EBP:
1212           row->SetRegisterLocationToAtCFAPlusOffset(
1213               translate_to_eh_frame_regnum_i386(registers[i]),
1214               wordsize * -saved_registers_offset, true);
1215           saved_registers_offset++;
1216           break;
1217         }
1218       }
1219     }
1220
1221     unwind_plan.AppendRow(row);
1222     return true;
1223   } break;
1224
1225   case UNWIND_X86_MODE_DWARF: {
1226     return false;
1227   } break;
1228   }
1229   return false;
1230 }
1231
1232 // DWARF register numbers from "DWARF for the ARM 64-bit Architecture (AArch64)"
1233 // doc by ARM
1234
1235 enum arm64_eh_regnum {
1236   x19 = 19,
1237   x20 = 20,
1238   x21 = 21,
1239   x22 = 22,
1240   x23 = 23,
1241   x24 = 24,
1242   x25 = 25,
1243   x26 = 26,
1244   x27 = 27,
1245   x28 = 28,
1246
1247   fp = 29,
1248   ra = 30,
1249   sp = 31,
1250   pc = 32,
1251
1252   // Compact unwind encodes d8-d15 but we don't have eh_frame / dwarf reg #'s
1253   // for the 64-bit fp regs.  Normally in DWARF it's context sensitive - so it
1254   // knows it is fetching a 32- or 64-bit quantity from reg v8 to indicate s0
1255   // or d0 - but the unwinder is operating at a lower level and we'd try to
1256   // fetch 128 bits if we were told that v8 were stored on the stack...
1257   v8 = 72,
1258   v9 = 73,
1259   v10 = 74,
1260   v11 = 75,
1261   v12 = 76,
1262   v13 = 77,
1263   v14 = 78,
1264   v15 = 79,
1265 };
1266
1267 enum arm_eh_regnum {
1268   arm_r0 = 0,
1269   arm_r1 = 1,
1270   arm_r2 = 2,
1271   arm_r3 = 3,
1272   arm_r4 = 4,
1273   arm_r5 = 5,
1274   arm_r6 = 6,
1275   arm_r7 = 7,
1276   arm_r8 = 8,
1277   arm_r9 = 9,
1278   arm_r10 = 10,
1279   arm_r11 = 11,
1280   arm_r12 = 12,
1281
1282   arm_sp = 13,
1283   arm_lr = 14,
1284   arm_pc = 15,
1285
1286   arm_d0 = 256,
1287   arm_d1 = 257,
1288   arm_d2 = 258,
1289   arm_d3 = 259,
1290   arm_d4 = 260,
1291   arm_d5 = 261,
1292   arm_d6 = 262,
1293   arm_d7 = 263,
1294   arm_d8 = 264,
1295   arm_d9 = 265,
1296   arm_d10 = 266,
1297   arm_d11 = 267,
1298   arm_d12 = 268,
1299   arm_d13 = 269,
1300   arm_d14 = 270,
1301 };
1302
1303 bool CompactUnwindInfo::CreateUnwindPlan_arm64(Target &target,
1304                                                FunctionInfo &function_info,
1305                                                UnwindPlan &unwind_plan,
1306                                                Address pc_or_function_start) {
1307   unwind_plan.SetSourceName("compact unwind info");
1308   unwind_plan.SetSourcedFromCompiler(eLazyBoolYes);
1309   unwind_plan.SetUnwindPlanValidAtAllInstructions(eLazyBoolNo);
1310   unwind_plan.SetUnwindPlanForSignalTrap(eLazyBoolNo);
1311   unwind_plan.SetRegisterKind(eRegisterKindEHFrame);
1312
1313   unwind_plan.SetLSDAAddress(function_info.lsda_address);
1314   unwind_plan.SetPersonalityFunctionPtr(function_info.personality_ptr_address);
1315
1316   UnwindPlan::RowSP row(new UnwindPlan::Row);
1317
1318   const int wordsize = 8;
1319   int mode = function_info.encoding & UNWIND_ARM64_MODE_MASK;
1320
1321   if (mode == UNWIND_ARM64_MODE_DWARF)
1322     return false;
1323
1324   if (mode == UNWIND_ARM64_MODE_FRAMELESS) {
1325     row->SetOffset(0);
1326
1327     uint32_t stack_size =
1328         (EXTRACT_BITS(function_info.encoding,
1329                       UNWIND_ARM64_FRAMELESS_STACK_SIZE_MASK)) *
1330         16;
1331
1332     // Our previous Call Frame Address is the stack pointer plus the stack size
1333     row->GetCFAValue().SetIsRegisterPlusOffset(arm64_eh_regnum::sp, stack_size);
1334
1335     // Our previous PC is in the LR
1336     row->SetRegisterLocationToRegister(arm64_eh_regnum::pc, arm64_eh_regnum::ra,
1337                                        true);
1338
1339     unwind_plan.AppendRow(row);
1340     return true;
1341   }
1342
1343   // Should not be possible
1344   if (mode != UNWIND_ARM64_MODE_FRAME)
1345     return false;
1346
1347   // mode == UNWIND_ARM64_MODE_FRAME
1348
1349   row->GetCFAValue().SetIsRegisterPlusOffset(arm64_eh_regnum::fp, 2 * wordsize);
1350   row->SetOffset(0);
1351   row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::fp, wordsize * -2,
1352                                             true);
1353   row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::pc, wordsize * -1,
1354                                             true);
1355   row->SetRegisterLocationToIsCFAPlusOffset(arm64_eh_regnum::sp, 0, true);
1356
1357   int reg_pairs_saved_count = 1;
1358
1359   uint32_t saved_register_bits = function_info.encoding & 0xfff;
1360
1361   if (saved_register_bits & UNWIND_ARM64_FRAME_X19_X20_PAIR) {
1362     int cfa_offset = reg_pairs_saved_count * -2 * wordsize;
1363     cfa_offset -= wordsize;
1364     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x19, cfa_offset,
1365                                               true);
1366     cfa_offset -= wordsize;
1367     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x20, cfa_offset,
1368                                               true);
1369     reg_pairs_saved_count++;
1370   }
1371
1372   if (saved_register_bits & UNWIND_ARM64_FRAME_X21_X22_PAIR) {
1373     int cfa_offset = reg_pairs_saved_count * -2 * wordsize;
1374     cfa_offset -= wordsize;
1375     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x21, cfa_offset,
1376                                               true);
1377     cfa_offset -= wordsize;
1378     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x22, cfa_offset,
1379                                               true);
1380     reg_pairs_saved_count++;
1381   }
1382
1383   if (saved_register_bits & UNWIND_ARM64_FRAME_X23_X24_PAIR) {
1384     int cfa_offset = reg_pairs_saved_count * -2 * wordsize;
1385     cfa_offset -= wordsize;
1386     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x23, cfa_offset,
1387                                               true);
1388     cfa_offset -= wordsize;
1389     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x24, cfa_offset,
1390                                               true);
1391     reg_pairs_saved_count++;
1392   }
1393
1394   if (saved_register_bits & UNWIND_ARM64_FRAME_X25_X26_PAIR) {
1395     int cfa_offset = reg_pairs_saved_count * -2 * wordsize;
1396     cfa_offset -= wordsize;
1397     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x25, cfa_offset,
1398                                               true);
1399     cfa_offset -= wordsize;
1400     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x26, cfa_offset,
1401                                               true);
1402     reg_pairs_saved_count++;
1403   }
1404
1405   if (saved_register_bits & UNWIND_ARM64_FRAME_X27_X28_PAIR) {
1406     int cfa_offset = reg_pairs_saved_count * -2 * wordsize;
1407     cfa_offset -= wordsize;
1408     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x27, cfa_offset,
1409                                               true);
1410     cfa_offset -= wordsize;
1411     row->SetRegisterLocationToAtCFAPlusOffset(arm64_eh_regnum::x28, cfa_offset,
1412                                               true);
1413     reg_pairs_saved_count++;
1414   }
1415
1416   // If we use the v8-v15 regnums here, the unwinder will try to grab 128 bits
1417   // off the stack;
1418   // not sure if we have a good way to represent the 64-bitness of these saves.
1419
1420   if (saved_register_bits & UNWIND_ARM64_FRAME_D8_D9_PAIR) {
1421     reg_pairs_saved_count++;
1422   }
1423   if (saved_register_bits & UNWIND_ARM64_FRAME_D10_D11_PAIR) {
1424     reg_pairs_saved_count++;
1425   }
1426   if (saved_register_bits & UNWIND_ARM64_FRAME_D12_D13_PAIR) {
1427     reg_pairs_saved_count++;
1428   }
1429   if (saved_register_bits & UNWIND_ARM64_FRAME_D14_D15_PAIR) {
1430     reg_pairs_saved_count++;
1431   }
1432
1433   unwind_plan.AppendRow(row);
1434   return true;
1435 }
1436
1437 bool CompactUnwindInfo::CreateUnwindPlan_armv7(Target &target,
1438                                                FunctionInfo &function_info,
1439                                                UnwindPlan &unwind_plan,
1440                                                Address pc_or_function_start) {
1441   unwind_plan.SetSourceName("compact unwind info");
1442   unwind_plan.SetSourcedFromCompiler(eLazyBoolYes);
1443   unwind_plan.SetUnwindPlanValidAtAllInstructions(eLazyBoolNo);
1444   unwind_plan.SetUnwindPlanForSignalTrap(eLazyBoolNo);
1445   unwind_plan.SetRegisterKind(eRegisterKindEHFrame);
1446
1447   unwind_plan.SetLSDAAddress(function_info.lsda_address);
1448   unwind_plan.SetPersonalityFunctionPtr(function_info.personality_ptr_address);
1449
1450   UnwindPlan::RowSP row(new UnwindPlan::Row);
1451
1452   const int wordsize = 4;
1453   int mode = function_info.encoding & UNWIND_ARM_MODE_MASK;
1454
1455   if (mode == UNWIND_ARM_MODE_DWARF)
1456     return false;
1457
1458   uint32_t stack_adjust = (EXTRACT_BITS(function_info.encoding,
1459                                         UNWIND_ARM_FRAME_STACK_ADJUST_MASK)) *
1460                           wordsize;
1461
1462   row->GetCFAValue().SetIsRegisterPlusOffset(arm_r7,
1463                                              (2 * wordsize) + stack_adjust);
1464   row->SetOffset(0);
1465   row->SetRegisterLocationToAtCFAPlusOffset(
1466       arm_r7, (wordsize * -2) - stack_adjust, true);
1467   row->SetRegisterLocationToAtCFAPlusOffset(
1468       arm_pc, (wordsize * -1) - stack_adjust, true);
1469   row->SetRegisterLocationToIsCFAPlusOffset(arm_sp, 0, true);
1470
1471   int cfa_offset = -stack_adjust - (2 * wordsize);
1472
1473   uint32_t saved_register_bits = function_info.encoding & 0xff;
1474
1475   if (saved_register_bits & UNWIND_ARM_FRAME_FIRST_PUSH_R6) {
1476     cfa_offset -= wordsize;
1477     row->SetRegisterLocationToAtCFAPlusOffset(arm_r6, cfa_offset, true);
1478   }
1479
1480   if (saved_register_bits & UNWIND_ARM_FRAME_FIRST_PUSH_R5) {
1481     cfa_offset -= wordsize;
1482     row->SetRegisterLocationToAtCFAPlusOffset(arm_r5, cfa_offset, true);
1483   }
1484
1485   if (saved_register_bits & UNWIND_ARM_FRAME_FIRST_PUSH_R4) {
1486     cfa_offset -= wordsize;
1487     row->SetRegisterLocationToAtCFAPlusOffset(arm_r4, cfa_offset, true);
1488   }
1489
1490   if (saved_register_bits & UNWIND_ARM_FRAME_SECOND_PUSH_R12) {
1491     cfa_offset -= wordsize;
1492     row->SetRegisterLocationToAtCFAPlusOffset(arm_r12, cfa_offset, true);
1493   }
1494
1495   if (saved_register_bits & UNWIND_ARM_FRAME_SECOND_PUSH_R11) {
1496     cfa_offset -= wordsize;
1497     row->SetRegisterLocationToAtCFAPlusOffset(arm_r11, cfa_offset, true);
1498   }
1499
1500   if (saved_register_bits & UNWIND_ARM_FRAME_SECOND_PUSH_R10) {
1501     cfa_offset -= wordsize;
1502     row->SetRegisterLocationToAtCFAPlusOffset(arm_r10, cfa_offset, true);
1503   }
1504
1505   if (saved_register_bits & UNWIND_ARM_FRAME_SECOND_PUSH_R9) {
1506     cfa_offset -= wordsize;
1507     row->SetRegisterLocationToAtCFAPlusOffset(arm_r9, cfa_offset, true);
1508   }
1509
1510   if (saved_register_bits & UNWIND_ARM_FRAME_SECOND_PUSH_R8) {
1511     cfa_offset -= wordsize;
1512     row->SetRegisterLocationToAtCFAPlusOffset(arm_r8, cfa_offset, true);
1513   }
1514
1515   if (mode == UNWIND_ARM_MODE_FRAME_D) {
1516     uint32_t d_reg_bits =
1517         EXTRACT_BITS(function_info.encoding, UNWIND_ARM_FRAME_D_REG_COUNT_MASK);
1518     switch (d_reg_bits) {
1519     case 0:
1520       // vpush {d8}
1521       cfa_offset -= 8;
1522       row->SetRegisterLocationToAtCFAPlusOffset(arm_d8, cfa_offset, true);
1523       break;
1524     case 1:
1525       // vpush {d10}
1526       // vpush {d8}
1527       cfa_offset -= 8;
1528       row->SetRegisterLocationToAtCFAPlusOffset(arm_d10, cfa_offset, true);
1529       cfa_offset -= 8;
1530       row->SetRegisterLocationToAtCFAPlusOffset(arm_d8, cfa_offset, true);
1531       break;
1532     case 2:
1533       // vpush {d12}
1534       // vpush {d10}
1535       // vpush {d8}
1536       cfa_offset -= 8;
1537       row->SetRegisterLocationToAtCFAPlusOffset(arm_d12, cfa_offset, true);
1538       cfa_offset -= 8;
1539       row->SetRegisterLocationToAtCFAPlusOffset(arm_d10, cfa_offset, true);
1540       cfa_offset -= 8;
1541       row->SetRegisterLocationToAtCFAPlusOffset(arm_d8, cfa_offset, true);
1542       break;
1543     case 3:
1544       // vpush {d14}
1545       // vpush {d12}
1546       // vpush {d10}
1547       // vpush {d8}
1548       cfa_offset -= 8;
1549       row->SetRegisterLocationToAtCFAPlusOffset(arm_d14, cfa_offset, true);
1550       cfa_offset -= 8;
1551       row->SetRegisterLocationToAtCFAPlusOffset(arm_d12, cfa_offset, true);
1552       cfa_offset -= 8;
1553       row->SetRegisterLocationToAtCFAPlusOffset(arm_d10, cfa_offset, true);
1554       cfa_offset -= 8;
1555       row->SetRegisterLocationToAtCFAPlusOffset(arm_d8, cfa_offset, true);
1556       break;
1557     case 4:
1558       // vpush {d14}
1559       // vpush {d12}
1560       // sp = (sp - 24) & (-16);
1561       // vst   {d8, d9, d10}
1562       cfa_offset -= 8;
1563       row->SetRegisterLocationToAtCFAPlusOffset(arm_d14, cfa_offset, true);
1564       cfa_offset -= 8;
1565       row->SetRegisterLocationToAtCFAPlusOffset(arm_d12, cfa_offset, true);
1566
1567       // FIXME we don't have a way to represent reg saves at an specific
1568       // alignment short of
1569       // coming up with some DWARF location description.
1570
1571       break;
1572     case 5:
1573       // vpush {d14}
1574       // sp = (sp - 40) & (-16);
1575       // vst   {d8, d9, d10, d11}
1576       // vst   {d12}
1577
1578       cfa_offset -= 8;
1579       row->SetRegisterLocationToAtCFAPlusOffset(arm_d14, cfa_offset, true);
1580
1581       // FIXME we don't have a way to represent reg saves at an specific
1582       // alignment short of
1583       // coming up with some DWARF location description.
1584
1585       break;
1586     case 6:
1587       // sp = (sp - 56) & (-16);
1588       // vst   {d8, d9, d10, d11}
1589       // vst   {d12, d13, d14}
1590
1591       // FIXME we don't have a way to represent reg saves at an specific
1592       // alignment short of
1593       // coming up with some DWARF location description.
1594
1595       break;
1596     case 7:
1597       // sp = (sp - 64) & (-16);
1598       // vst   {d8, d9, d10, d11}
1599       // vst   {d12, d13, d14, d15}
1600
1601       // FIXME we don't have a way to represent reg saves at an specific
1602       // alignment short of
1603       // coming up with some DWARF location description.
1604
1605       break;
1606     }
1607   }
1608
1609   unwind_plan.AppendRow(row);
1610   return true;
1611 }