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