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() {} 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() {} 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 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 = 292 m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(entry.file_idx); 293 line_entry.original_file = 294 m_comp_unit->GetSupportFiles().GetFileSpecAtIndex(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, const std::vector<uint32_t> &file_indexes, 307 uint32_t line, bool exact, LineEntry *line_entry_ptr) { 308 309 const size_t count = m_entries.size(); 310 size_t best_match = UINT32_MAX; 311 312 for (size_t idx = start_idx; idx < count; ++idx) { 313 // Skip line table rows that terminate the previous row (is_terminal_entry 314 // is non-zero) 315 if (m_entries[idx].is_terminal_entry) 316 continue; 317 318 if (!llvm::is_contained(file_indexes, m_entries[idx].file_idx)) 319 continue; 320 321 // Exact match always wins. Otherwise try to find the closest line > the 322 // desired line. 323 // FIXME: Maybe want to find the line closest before and the line closest 324 // after and 325 // if they're not in the same function, don't return a match. 326 327 if (m_entries[idx].line < line) { 328 continue; 329 } else if (m_entries[idx].line == line) { 330 if (line_entry_ptr) 331 ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr); 332 return idx; 333 } else if (!exact) { 334 if (best_match == UINT32_MAX) 335 best_match = idx; 336 else if (m_entries[idx].line < m_entries[best_match].line) 337 best_match = idx; 338 } 339 } 340 341 if (best_match != UINT32_MAX) { 342 if (line_entry_ptr) 343 ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr); 344 return best_match; 345 } 346 return UINT32_MAX; 347 } 348 349 uint32_t LineTable::FindLineEntryIndexByFileIndex(uint32_t start_idx, 350 uint32_t file_idx, 351 uint32_t line, bool exact, 352 LineEntry *line_entry_ptr) { 353 const size_t count = m_entries.size(); 354 size_t best_match = UINT32_MAX; 355 356 for (size_t idx = start_idx; idx < count; ++idx) { 357 // Skip line table rows that terminate the previous row (is_terminal_entry 358 // is non-zero) 359 if (m_entries[idx].is_terminal_entry) 360 continue; 361 362 if (m_entries[idx].file_idx != file_idx) 363 continue; 364 365 // Exact match always wins. Otherwise try to find the closest line > the 366 // desired line. 367 // FIXME: Maybe want to find the line closest before and the line closest 368 // after and 369 // if they're not in the same function, don't return a match. 370 371 if (m_entries[idx].line < line) { 372 continue; 373 } else if (m_entries[idx].line == line) { 374 if (line_entry_ptr) 375 ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr); 376 return idx; 377 } else if (!exact) { 378 if (best_match == UINT32_MAX) 379 best_match = idx; 380 else if (m_entries[idx].line < m_entries[best_match].line) 381 best_match = idx; 382 } 383 } 384 385 if (best_match != UINT32_MAX) { 386 if (line_entry_ptr) 387 ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr); 388 return best_match; 389 } 390 return UINT32_MAX; 391 } 392 393 size_t LineTable::FineLineEntriesForFileIndex(uint32_t file_idx, bool append, 394 SymbolContextList &sc_list) { 395 396 if (!append) 397 sc_list.Clear(); 398 399 size_t num_added = 0; 400 const size_t count = m_entries.size(); 401 if (count > 0) { 402 SymbolContext sc(m_comp_unit); 403 404 for (size_t idx = 0; idx < count; ++idx) { 405 // Skip line table rows that terminate the previous row 406 // (is_terminal_entry is non-zero) 407 if (m_entries[idx].is_terminal_entry) 408 continue; 409 410 if (m_entries[idx].file_idx == file_idx) { 411 if (ConvertEntryAtIndexToLineEntry(idx, sc.line_entry)) { 412 ++num_added; 413 sc_list.Append(sc); 414 } 415 } 416 } 417 } 418 return num_added; 419 } 420 421 void LineTable::Dump(Stream *s, Target *target, Address::DumpStyle style, 422 Address::DumpStyle fallback_style, bool show_line_ranges) { 423 const size_t count = m_entries.size(); 424 LineEntry line_entry; 425 FileSpec prev_file; 426 for (size_t idx = 0; idx < count; ++idx) { 427 ConvertEntryAtIndexToLineEntry(idx, line_entry); 428 line_entry.Dump(s, target, prev_file != line_entry.original_file, style, 429 fallback_style, show_line_ranges); 430 s->EOL(); 431 prev_file = line_entry.original_file; 432 } 433 } 434 435 void LineTable::GetDescription(Stream *s, Target *target, 436 DescriptionLevel level) { 437 const size_t count = m_entries.size(); 438 LineEntry line_entry; 439 for (size_t idx = 0; idx < count; ++idx) { 440 ConvertEntryAtIndexToLineEntry(idx, line_entry); 441 line_entry.GetDescription(s, level, m_comp_unit, target, true); 442 s->EOL(); 443 } 444 } 445 446 size_t LineTable::GetContiguousFileAddressRanges(FileAddressRanges &file_ranges, 447 bool append) { 448 if (!append) 449 file_ranges.Clear(); 450 const size_t initial_count = file_ranges.GetSize(); 451 452 const size_t count = m_entries.size(); 453 LineEntry line_entry; 454 FileAddressRanges::Entry range(LLDB_INVALID_ADDRESS, 0); 455 for (size_t idx = 0; idx < count; ++idx) { 456 const Entry &entry = m_entries[idx]; 457 458 if (entry.is_terminal_entry) { 459 if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) { 460 range.SetRangeEnd(entry.file_addr); 461 file_ranges.Append(range); 462 range.Clear(LLDB_INVALID_ADDRESS); 463 } 464 } else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) { 465 range.SetRangeBase(entry.file_addr); 466 } 467 } 468 return file_ranges.GetSize() - initial_count; 469 } 470 471 LineTable *LineTable::LinkLineTable(const FileRangeMap &file_range_map) { 472 std::unique_ptr<LineTable> line_table_up(new LineTable(m_comp_unit)); 473 LineSequenceImpl sequence; 474 const size_t count = m_entries.size(); 475 LineEntry line_entry; 476 const FileRangeMap::Entry *file_range_entry = nullptr; 477 const FileRangeMap::Entry *prev_file_range_entry = nullptr; 478 lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS; 479 bool prev_entry_was_linked = false; 480 bool range_changed = false; 481 for (size_t idx = 0; idx < count; ++idx) { 482 const Entry &entry = m_entries[idx]; 483 484 const bool end_sequence = entry.is_terminal_entry; 485 const lldb::addr_t lookup_file_addr = 486 entry.file_addr - (end_sequence ? 1 : 0); 487 if (file_range_entry == nullptr || 488 !file_range_entry->Contains(lookup_file_addr)) { 489 prev_file_range_entry = file_range_entry; 490 file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr); 491 range_changed = true; 492 } 493 494 lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS; 495 lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS; 496 497 bool terminate_previous_entry = false; 498 if (file_range_entry) { 499 entry_linked_file_addr = entry.file_addr - 500 file_range_entry->GetRangeBase() + 501 file_range_entry->data; 502 // Determine if we need to terminate the previous entry when the previous 503 // entry was not contiguous with this one after being linked. 504 if (range_changed && prev_file_range_entry) { 505 prev_end_entry_linked_file_addr = 506 std::min<lldb::addr_t>(entry.file_addr, 507 prev_file_range_entry->GetRangeEnd()) - 508 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; 509 if (prev_end_entry_linked_file_addr != entry_linked_file_addr) 510 terminate_previous_entry = prev_entry_was_linked; 511 } 512 } else if (prev_entry_was_linked) { 513 // This entry doesn't have a remapping and it needs to be removed. Watch 514 // out in case we need to terminate a previous entry needs to be 515 // terminated now that one line entry in a sequence is not longer valid. 516 if (!sequence.m_entries.empty() && 517 !sequence.m_entries.back().is_terminal_entry) { 518 terminate_previous_entry = true; 519 } 520 } 521 522 if (terminate_previous_entry && !sequence.m_entries.empty()) { 523 assert(prev_file_addr != LLDB_INVALID_ADDRESS); 524 UNUSED_IF_ASSERT_DISABLED(prev_file_addr); 525 sequence.m_entries.push_back(sequence.m_entries.back()); 526 if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS) 527 prev_end_entry_linked_file_addr = 528 std::min<lldb::addr_t>(entry.file_addr, 529 prev_file_range_entry->GetRangeEnd()) - 530 prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; 531 sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr; 532 sequence.m_entries.back().is_terminal_entry = true; 533 534 // Append the sequence since we just terminated the previous one 535 line_table_up->InsertSequence(&sequence); 536 sequence.Clear(); 537 } 538 539 // Now link the current entry 540 if (file_range_entry) { 541 // This entry has an address remapping and it needs to have its address 542 // relinked 543 sequence.m_entries.push_back(entry); 544 sequence.m_entries.back().file_addr = entry_linked_file_addr; 545 } 546 547 // If we have items in the sequence and the last entry is a terminal entry, 548 // insert this sequence into our new line table. 549 if (!sequence.m_entries.empty() && 550 sequence.m_entries.back().is_terminal_entry) { 551 line_table_up->InsertSequence(&sequence); 552 sequence.Clear(); 553 prev_entry_was_linked = false; 554 } else { 555 prev_entry_was_linked = file_range_entry != nullptr; 556 } 557 prev_file_addr = entry.file_addr; 558 range_changed = false; 559 } 560 if (line_table_up->m_entries.empty()) 561 return nullptr; 562 return line_table_up.release(); 563 } 564