lldb/source/Symbol/LineTable.cpp

   1 //===-- LineTable.cpp -----------------------------------------------------===//
   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/LineTable.h"
  10 #include "lldb/Core/Address.h"
  11 #include "lldb/Core/Module.h"
  12 #include "lldb/Core/Section.h"
  13 #include "lldb/Symbol/CompileUnit.h"
  14 #include "lldb/Utility/Stream.h"
  15 #include <algorithm>
  16
  17 using namespace lldb;
  18 using namespace lldb_private;
  19
  20 // LineTable constructor
  21 LineTable::LineTable(CompileUnit *comp_unit)
  22     : m_comp_unit(comp_unit), m_entries() {}
  23
  24 LineTable::LineTable(CompileUnit *comp_unit,
  25                      std::vector<std::unique_ptr<LineSequence>> &&sequences)
  26     : m_comp_unit(comp_unit), m_entries() {
  27   LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  28   llvm::stable_sort(sequences, less_than_bp);
  29   for (const auto &sequence : sequences) {
  30     LineSequenceImpl *seq = static_cast<LineSequenceImpl *>(sequence.get());
  31     m_entries.insert(m_entries.end(), seq->m_entries.begin(),
  32                      seq->m_entries.end());
  33   }
  34 }
  35
  36 // Destructor
  37 LineTable::~LineTable() = default;
  38
  39 void LineTable::InsertLineEntry(lldb::addr_t file_addr, uint32_t line,
  40                                 uint16_t column, uint16_t file_idx,
  41                                 bool is_start_of_statement,
  42                                 bool is_start_of_basic_block,
  43                                 bool is_prologue_end, bool is_epilogue_begin,
  44                                 bool is_terminal_entry) {
  45   Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
  46               is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
  47               is_terminal_entry);
  48
  49   LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
  50   entry_collection::iterator pos =
  51       llvm::upper_bound(m_entries, entry, less_than_bp);
  52
  53   //  Stream s(stdout);
  54   //  s << "\n\nBefore:\n";
  55   //  Dump (&s, Address::DumpStyleFileAddress);
  56   m_entries.insert(pos, entry);
  57   //  s << "After:\n";
  58   //  Dump (&s, Address::DumpStyleFileAddress);
  59 }
  60
  61 LineSequence::LineSequence() = default;
  62
  63 void LineTable::LineSequenceImpl::Clear() { m_entries.clear(); }
  64
  65 std::unique_ptr<LineSequence> LineTable::CreateLineSequenceContainer() {
  66   return std::make_unique<LineTable::LineSequenceImpl>();
  67 }
  68
  69 void LineTable::AppendLineEntryToSequence(
  70     LineSequence *sequence, lldb::addr_t file_addr, uint32_t line,
  71     uint16_t column, uint16_t file_idx, bool is_start_of_statement,
  72     bool is_start_of_basic_block, bool is_prologue_end, bool is_epilogue_begin,
  73     bool is_terminal_entry) {
  74   assert(sequence != nullptr);
  75   LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
  76   Entry entry(file_addr, line, column, file_idx, is_start_of_statement,
  77               is_start_of_basic_block, is_prologue_end, is_epilogue_begin,
  78               is_terminal_entry);
  79   entry_collection &entries = seq->m_entries;
  80   // Replace the last entry if the address is the same, otherwise append it. If
  81   // we have multiple line entries at the same address, this indicates illegal
  82   // DWARF so this "fixes" the line table to be correct. If not fixed this can
  83   // cause a line entry's address that when resolved back to a symbol context,
  84   // could resolve to a different line entry. We really want a
  85   // 1 to 1 mapping
  86   // here to avoid these kinds of inconsistencies. We will need tor revisit
  87   // this if the DWARF line tables are updated to allow multiple entries at the
  88   // same address legally.
  89   if (!entries.empty() && entries.back().file_addr == file_addr) {
  90     // GCC don't use the is_prologue_end flag to mark the first instruction
  91     // after the prologue.
  92     // Instead of it is issuing a line table entry for the first instruction
  93     // of the prologue and one for the first instruction after the prologue. If
  94     // the size of the prologue is 0 instruction then the 2 line entry will
  95     // have the same file address. Removing it will remove our ability to
  96     // properly detect the location of the end of prologe so we set the
  97     // prologue_end flag to preserve this information (setting the prologue_end
  98     // flag for an entry what is after the prologue end don't have any effect)
  99     entry.is_prologue_end = entry.file_idx == entries.back().file_idx;
 100     entries.back() = entry;
 101   } else
 102     entries.push_back(entry);
 103 }
 104
 105 void LineTable::InsertSequence(LineSequence *sequence) {
 106   assert(sequence != nullptr);
 107   LineSequenceImpl *seq = reinterpret_cast<LineSequenceImpl *>(sequence);
 108   if (seq->m_entries.empty())
 109     return;
 110   Entry &entry = seq->m_entries.front();
 111
 112   // If the first entry address in this sequence is greater than or equal to
 113   // the address of the last item in our entry collection, just append.
 114   if (m_entries.empty() ||
 115       !Entry::EntryAddressLessThan(entry, m_entries.back())) {
 116     m_entries.insert(m_entries.end(), seq->m_entries.begin(),
 117                      seq->m_entries.end());
 118     return;
 119   }
 120
 121   // Otherwise, find where this belongs in the collection
 122   entry_collection::iterator begin_pos = m_entries.begin();
 123   entry_collection::iterator end_pos = m_entries.end();
 124   LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
 125   entry_collection::iterator pos =
 126       upper_bound(begin_pos, end_pos, entry, less_than_bp);
 127
 128   // We should never insert a sequence in the middle of another sequence
 129   if (pos != begin_pos) {
 130     while (pos < end_pos && !((pos - 1)->is_terminal_entry))
 131       pos++;
 132   }
 133
 134 #ifndef NDEBUG
 135   // If we aren't inserting at the beginning, the previous entry should
 136   // terminate a sequence.
 137   if (pos != begin_pos) {
 138     entry_collection::iterator prev_pos = pos - 1;
 139     assert(prev_pos->is_terminal_entry);
 140   }
 141 #endif
 142   m_entries.insert(pos, seq->m_entries.begin(), seq->m_entries.end());
 143 }
 144
 145 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(
 146     LineTable *line_table)
 147     : m_line_table(line_table) {}
 148
 149 bool LineTable::Entry::LessThanBinaryPredicate::
 150 operator()(const LineTable::Entry &a, const LineTable::Entry &b) const {
 151 #define LT_COMPARE(a, b)                                                       \
 152   if (a != b)                                                                  \
 153   return a < b
 154   LT_COMPARE(a.file_addr, b.file_addr);
 155   // b and a reversed on purpose below.
 156   LT_COMPARE(b.is_terminal_entry, a.is_terminal_entry);
 157   LT_COMPARE(a.line, b.line);
 158   LT_COMPARE(a.column, b.column);
 159   LT_COMPARE(a.is_start_of_statement, b.is_start_of_statement);
 160   LT_COMPARE(a.is_start_of_basic_block, b.is_start_of_basic_block);
 161   // b and a reversed on purpose below.
 162   LT_COMPARE(b.is_prologue_end, a.is_prologue_end);
 163   LT_COMPARE(a.is_epilogue_begin, b.is_epilogue_begin);
 164   LT_COMPARE(a.file_idx, b.file_idx);
 165   return false;
 166 #undef LT_COMPARE
 167 }
 168
 169 bool LineTable::Entry::LessThanBinaryPredicate::
 170 operator()(const std::unique_ptr<LineSequence> &sequence_a,
 171            const std::unique_ptr<LineSequence> &sequence_b) const {
 172   auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a.get());
 173   auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b.get());
 174   return (*this)(seq_a->m_entries.front(), seq_b->m_entries.front());
 175 }
 176
 177 uint32_t LineTable::GetSize() const { return m_entries.size(); }
 178
 179 bool LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry) {
 180   if (idx < m_entries.size()) {
 181     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 182     return true;
 183   }
 184   line_entry.Clear();
 185   return false;
 186 }
 187
 188 bool LineTable::FindLineEntryByAddress(const Address &so_addr,
 189                                        LineEntry &line_entry,
 190                                        uint32_t *index_ptr) {
 191   if (index_ptr != nullptr)
 192     *index_ptr = UINT32_MAX;
 193
 194   bool success = false;
 195
 196   if (so_addr.GetModule().get() == m_comp_unit->GetModule().get()) {
 197     Entry search_entry;
 198     search_entry.file_addr = so_addr.GetFileAddress();
 199     if (search_entry.file_addr != LLDB_INVALID_ADDRESS) {
 200       entry_collection::const_iterator begin_pos = m_entries.begin();
 201       entry_collection::const_iterator end_pos = m_entries.end();
 202       entry_collection::const_iterator pos = lower_bound(
 203           begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan);
 204       if (pos != end_pos) {
 205         if (pos != begin_pos) {
 206           if (pos->file_addr != search_entry.file_addr)
 207             --pos;
 208           else if (pos->file_addr == search_entry.file_addr) {
 209             // If this is a termination entry, it shouldn't match since entries
 210             // with the "is_terminal_entry" member set to true are termination
 211             // entries that define the range for the previous entry.
 212             if (pos->is_terminal_entry) {
 213               // The matching entry is a terminal entry, so we skip ahead to
 214               // the next entry to see if there is another entry following this
 215               // one whose section/offset matches.
 216               ++pos;
 217               if (pos != end_pos) {
 218                 if (pos->file_addr != search_entry.file_addr)
 219                   pos = end_pos;
 220               }
 221             }
 222
 223             if (pos != end_pos) {
 224               // While in the same section/offset backup to find the first line
 225               // entry that matches the address in case there are multiple
 226               while (pos != begin_pos) {
 227                 entry_collection::const_iterator prev_pos = pos - 1;
 228                 if (prev_pos->file_addr == search_entry.file_addr &&
 229                     prev_pos->is_terminal_entry == false)
 230                   --pos;
 231                 else
 232                   break;
 233               }
 234             }
 235           }
 236         }
 237         else
 238         {
 239           // There might be code in the containing objfile before the first
 240           // line table entry.  Make sure that does not get considered part of
 241           // the first line table entry.
 242           if (pos->file_addr > so_addr.GetFileAddress())
 243             return false;
 244         }
 245
 246         // Make sure we have a valid match and that the match isn't a
 247         // terminating entry for a previous line...
 248         if (pos != end_pos && pos->is_terminal_entry == false) {
 249           uint32_t match_idx = std::distance(begin_pos, pos);
 250           success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry);
 251           if (index_ptr != nullptr && success)
 252             *index_ptr = match_idx;
 253         }
 254       }
 255     }
 256   }
 257   return success;
 258 }
 259
 260 bool LineTable::ConvertEntryAtIndexToLineEntry(uint32_t idx,
 261                                                LineEntry &line_entry) {
 262   if (idx >= m_entries.size())
 263     return false;
 264
 265   const Entry &entry = m_entries[idx];
 266   ModuleSP module_sp(m_comp_unit->GetModule());
 267   if (!module_sp)
 268     return false;
 269
 270   addr_t file_addr = entry.file_addr;
 271
 272   // A terminal entry can point outside of a module or a section. Decrement the
 273   // address to ensure it resolves correctly.
 274   if (entry.is_terminal_entry)
 275     --file_addr;
 276
 277   if (!module_sp->ResolveFileAddress(file_addr,
 278                                      line_entry.range.GetBaseAddress()))
 279     return false;
 280
 281   // Now undo the decrement above.
 282   if (entry.is_terminal_entry)
 283     line_entry.range.GetBaseAddress().Slide(1);
 284
 285   if (!entry.is_terminal_entry && idx + 1 < m_entries.size())
 286     line_entry.range.SetByteSize(m_entries[idx + 1].file_addr -
 287                                  entry.file_addr);
 288   else
 289     line_entry.range.SetByteSize(0);
 290
 291   line_entry.file_sp =
 292       m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx);
 293   line_entry.original_file_sp =
 294       m_comp_unit->GetSupportFiles().GetSupportFileAtIndex(entry.file_idx);
 295   line_entry.line = entry.line;
 296   line_entry.column = entry.column;
 297   line_entry.is_start_of_statement = entry.is_start_of_statement;
 298   line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
 299   line_entry.is_prologue_end = entry.is_prologue_end;
 300   line_entry.is_epilogue_begin = entry.is_epilogue_begin;
 301   line_entry.is_terminal_entry = entry.is_terminal_entry;
 302   return true;
 303 }
 304
 305 uint32_t LineTable::FindLineEntryIndexByFileIndex(
 306     uint32_t start_idx, uint32_t file_idx,
 307     const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
 308   auto file_idx_matcher = [](uint32_t file_index, uint16_t entry_file_idx) {
 309     return file_index == entry_file_idx;
 310   };
 311   return FindLineEntryIndexByFileIndexImpl<uint32_t>(
 312
 313       start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
 314 }
 315
 316 uint32_t LineTable::FindLineEntryIndexByFileIndex(
 317     uint32_t start_idx, const std::vector<uint32_t> &file_idx,
 318     const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr) {
 319   auto file_idx_matcher = [](const std::vector<uint32_t> &file_indexes,
 320                              uint16_t entry_file_idx) {
 321     return llvm::is_contained(file_indexes, entry_file_idx);
 322   };
 323
 324   return FindLineEntryIndexByFileIndexImpl<std::vector<uint32_t>>(
 325       start_idx, file_idx, src_location_spec, line_entry_ptr, file_idx_matcher);
 326 }
 327
 328 size_t LineTable::FindLineEntriesForFileIndex(uint32_t file_idx, bool append,
 329                                               SymbolContextList &sc_list) {
 330
 331   if (!append)
 332     sc_list.Clear();
 333
 334   size_t num_added = 0;
 335   const size_t count = m_entries.size();
 336   if (count > 0) {
 337     SymbolContext sc(m_comp_unit);
 338
 339     for (size_t idx = 0; idx < count; ++idx) {
 340       // Skip line table rows that terminate the previous row
 341       // (is_terminal_entry is non-zero)
 342       if (m_entries[idx].is_terminal_entry)
 343         continue;
 344
 345       if (m_entries[idx].file_idx == file_idx) {
 346         if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) {
 347           ++num_added;
 348           sc_list.Append(sc);
 349         }
 350       }
 351     }
 352   }
 353   return num_added;
 354 }
 355
 356 void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style,
 357                      Address::DumpStyle fallback_style, bool show_line_ranges) {
 358   const size_t count = m_entries.size();
 359   LineEntry line_entry;
 360   SupportFileSP prev_file;
 361   for (size_t idx = 0; idx < count; ++idx) {
 362     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 363     line_entry.Dump(s, target, !prev_file->Equal(*line_entry.original_file_sp),
 364                     style, fallback_style, show_line_ranges);
 365     s->EOL();
 366     prev_file = line_entry.original_file_sp;
 367   }
 368 }
 369
 370 void LineTable::GetDescription(Stream *s, Target *target,
 371                                DescriptionLevel level) {
 372   const size_t count = m_entries.size();
 373   LineEntry line_entry;
 374   for (size_t idx = 0; idx < count; ++idx) {
 375     ConvertEntryAtIndexToLineEntry(idx, line_entry);
 376     line_entry.GetDescription(s, level, m_comp_unit, target, true);
 377     s->EOL();
 378   }
 379 }
 380
 381 size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
 382                                                  bool append) {
 383   if (!append)
 384     file_ranges.Clear();
 385   const size_t initial_count = file_ranges.GetSize();
 386
 387   const size_t count = m_entries.size();
 388   LineEntry line_entry;
 389   FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0);
 390   for (size_t idx = 0; idx < count; ++idx) {
 391     const Entry &entry = m_entries[idx];
 392
 393     if (entry.is_terminal_entry) {
 394       if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) {
 395         range.SetRangeEnd(entry.file_addr);
 396         file_ranges.Append(range);
 397         range.Clear(LLDB_INVALID_ADDRESS);
 398       }
 399     } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) {
 400       range.SetRangeBase(entry.file_addr);
 401     }
 402   }
 403   return file_ranges.GetSize() - initial_count;
 404 }
 405
 406 LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) {
 407   std::unique_ptr<LineTable> line_table_up(new LineTable(m_comp_unit));
 408   LineSequenceImpl sequence;
 409   const size_t count = m_entries.size();
 410   LineEntry line_entry;
 411   const FileRangeMap::Entry *file_range_entry = nullptr;
 412   const FileRangeMap::Entry *prev_file_range_entry = nullptr;
 413   lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS;
 414   bool prev_entry_was_linked = false;
 415   bool range_changed = false;
 416   for (size_t idx = 0; idx < count; ++idx) {
 417     const Entry &entry = m_entries[idx];
 418
 419     const bool end_sequence = entry.is_terminal_entry;
 420     const lldb::addr_t lookup_file_addr =
 421         entry.file_addr - (end_sequence ? 1 : 0);
 422     if (file_range_entry == nullptr ||
 423         !file_range_entry->Contains(lookup_file_addr)) {
 424       prev_file_range_entry = file_range_entry;
 425       file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr);
 426       range_changed = true;
 427     }
 428
 429     lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS;
 430     lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS;
 431
 432     bool terminate_previous_entry = false;
 433     if (file_range_entry) {
 434       entry_linked_file_addr = entry.file_addr -
 435                                file_range_entry->GetRangeBase() +
 436                                file_range_entry->data;
 437       // Determine if we need to terminate the previous entry when the previous
 438       // entry was not contiguous with this one after being linked.
 439       if (range_changed && prev_file_range_entry) {
 440         prev_end_entry_linked_file_addr =
 441             std::min<lldb::addr_t>(entry.file_addr,
 442                                    prev_file_range_entry->GetRangeEnd()) -
 443             prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
 444         if (prev_end_entry_linked_file_addr != entry_linked_file_addr)
 445           terminate_previous_entry = prev_entry_was_linked;
 446       }
 447     } else if (prev_entry_was_linked) {
 448       // This entry doesn't have a remapping and it needs to be removed. Watch
 449       // out in case we need to terminate a previous entry needs to be
 450       // terminated now that one line entry in a sequence is not longer valid.
 451       if (!sequence.m_entries.empty() &&
 452           !sequence.m_entries.back().is_terminal_entry) {
 453         terminate_previous_entry = true;
 454       }
 455     }
 456
 457     if (terminate_previous_entry && !sequence.m_entries.empty()) {
 458       assert(prev_file_addr != LLDB_INVALID_ADDRESS);
 459       UNUSED_IF_ASSERT_DISABLED(prev_file_addr);
 460       sequence.m_entries.push_back(sequence.m_entries.back());
 461       if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS)
 462         prev_end_entry_linked_file_addr =
 463             std::min<lldb::addr_t>(entry.file_addr,
 464                                    prev_file_range_entry->GetRangeEnd()) -
 465             prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data;
 466       sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr;
 467       sequence.m_entries.back().is_terminal_entry = true;
 468
 469       // Append the sequence since we just terminated the previous one
 470       line_table_up->InsertSequence(&sequence);
 471       sequence.Clear();
 472     }
 473
 474     // Now link the current entry
 475     if (file_range_entry) {
 476       // This entry has an address remapping and it needs to have its address
 477       // relinked
 478       sequence.m_entries.push_back(entry);
 479       sequence.m_entries.back().file_addr = entry_linked_file_addr;
 480     }
 481
 482     // If we have items in the sequence and the last entry is a terminal entry,
 483     // insert this sequence into our new line table.
 484     if (!sequence.m_entries.empty() &&
 485         sequence.m_entries.back().is_terminal_entry) {
 486       line_table_up->InsertSequence(&sequence);
 487       sequence.Clear();
 488       prev_entry_was_linked = false;
 489     } else {
 490       prev_entry_was_linked = file_range_entry != nullptr;
 491     }
 492     prev_file_addr = entry.file_addr;
 493     range_changed = false;
 494   }
 495   if (line_table_up->m_entries.empty())
 496     return nullptr;
 497   return line_table_up.release();
 498 }