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