[DWARF] Fix a bug in line info handling

[loladiro]

Summary

This fixes a bug in the line info handling in the dwarf code, based on a
problem I when implementing RelocVisitor support for MachO.
Since addr+size will give the first address past the end of the function,
we need to back up one line table entry. Fix this by looking up the end_addr-1,
which is the last address in the range. Also factor out the common functionality
into a separate function.
This comes up on MachO much more than on ELF, since MachO
doesn't store the symbol size separately, hence making
said situation always occur.

[dblaikie]

+Alexey

[samsonov]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

608 ↗

(On Diff #26285)

I don't understand this part. Looks like row_pos should be the first row that contains "address". It means that the lookup here should be similar to the one done in lookupAddress function (of course, I'd prefer this code to be shared).

628 ↗

(On Diff #26285)

Can you simply find the number of row that describes the address "end_addr - 1"?

[loladiro]

Yes, I tried, just using address - 1 for the second patch and it passes the testcase, so I'm happy. I don't know enough about this code to decide which is better, so just let me know and I'll update the code accordingly.

[samsonov]

Personally, I would prefer to have a single function that would take an address, and a Sequence, describing this address, and return a row in that sequence, describing this address. Then we can use this function in several places (lookupAddress, lookupAddressRange).

[loladiro]

Updated to factor out common code into a separate function.

[samsonov]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

525 ↗

(On Diff #26339)

consider moving this constant to LineTable struct in the header (and rename to smth. like UnknownRowIndex)

571 ↗

(On Diff #26339)

Looks like this condition should be checked in findRowInSequence function above.

603 ↗

(On Diff #26339)

I'd rather not provide default value for variables, if we're unconditionally initializing them later.

608 ↗

(On Diff #26339)

Just a ternary operator?

uint32_t first_row_index = (seq_pos == start_pos) ? findRowInSeq(cur_seq, address) : cur_seq.FirstRowIndex;

614 ↗

(On Diff #26339)

Fun fact: if you add the call to Sequence::containsPC() at the beginning of findRowInSequence, as suggested above, you won't need this special case:

uint32_t last_row_index = findRowInSequnce(cur_seq, end_addr - 1);
if (last_row_index == UnknownRowIndex)
  last_row_index = cur_seq.LastRowIndex - 1;

621 ↗

(On Diff #26339)

assert that both first_row_index and last_row_index are valid? Or return false in this case.

[loladiro]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

525 ↗

(On Diff #26339)

Will do.

571 ↗

(On Diff #26339)

Sure, it wasn't there before below, so I didn't pull it, but seems reasonable.

603 ↗

(On Diff #26339)

We're not, this also handles the case when seq_pos == start_pos is false.

608 ↗

(On Diff #26339)

But that wouldn't capture the case where findRowInSeq returns an UnknownRowIndex.

614 ↗

(On Diff #26339)

Sounds good.

[loladiro]

Updated again. I also noticed that we were duplicating the last row before (the end_sequence one, which is not in general valid - I believe), so I fixed the test as well - please make sure that seems correct.

[samsonov]

I don't know about the data needed for llvm-rtdyld, so can't comment about the changes to test/DebugInfo/debuglineinfo.test. Otherwise, the patch now looks fine to me (modulo comments below).

include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

208 ↗

(On Diff #26348)

Fix a comment about lookupAddress return value to mention this. Also, lookupAddress should probably be private, the public interface is getFileLineInfoForAddress. Looks like LineTable is now a class, not a struct.

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

538 ↗

(On Diff #26348)

Run patch through clang-format

601 ↗

(On Diff #26348)

Hm, should this be a const reference instead?

[samsonov]

Thank you!

[loladiro]

llvm-rtdyld just uses getLineInfoForAddressRange and dumps that out, so the change in the test case directly corresponds to a change in the return value of that function. However, I do believe that this is correct now, because the extra line was marked with end_sequence, which the DWARF standard says is A boolean indicating that the current address is that of the first byte after the end of a sequence, so I believe it shouldn't be included if you're asking for just the rows that cover the function. Will do the stylistic changes you note.

[loladiro]

Run everything through clang-format, also change cur_seq to a const reference as suggested. I didn't adjust the visibility of LineTable, as that seems to be a separate commit, preferably done by somebody who knows which part of the interface should be public.

[loladiro]

Note that this is currently uncommitable, because llvm-rtdyld can no longer figure out the size of MachO symbols due to rL238028. Maybe @rafael can help fix llvm-rtdyld.

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

struct Sequence {
     bool containsPC(uint64_t pc) const {
       return (LowPC <= pc && pc < HighPC);
     }
   };
 
   struct LineTable {
     LineTable();
 
+    // Represents an invalid row
+    const uint32_t UnknownRowIndex = UINT32_MAX;
+
     void appendRow(const DWARFDebugLine::Row &R) {
       Rows.push_back(R);
     }
     void appendSequence(const DWARFDebugLine::Sequence &S) {
       Sequences.push_back(S);
     }
 
     // Returns the index of the row with file/line info for a given address,
-    // or -1 if there is no such row.
+    // or UnknownRowIndex if there is no such row.
     uint32_t lookupAddress(uint64_t address) const;
 
     bool lookupAddressRange(uint64_t address, uint64_t size,
                             std::vector<uint32_t> &result) const;
 
     // Extracts filename by its index in filename table in prologue.
     // Returns true on success.
     bool getFileNameByIndex(uint64_t FileIndex, const char *CompDir,
struct LineTable {
 
     struct Prologue Prologue;
     typedef std::vector<Row> RowVector;
     typedef RowVector::const_iterator RowIter;
     typedef std::vector<Sequence> SequenceVector;
     typedef SequenceVector::const_iterator SequenceIter;
     RowVector Rows;
     SequenceVector Sequences;
+
+  private:
+    uint32_t findRowInSeq(const DWARFDebugLine::Sequence &seq,
+                          uint64_t address) const;
   };
 
   const LineTable *getLineTable(uint32_t offset) const;
   const LineTable *getOrParseLineTable(DataExtractor debug_line_data,
                                        uint32_t offset);
 
 private:
   struct ParsingState {

llvm/trunk/lib/DebugInfo/DWARF/DWARFDebugLine.cpp

if (!Sequences.empty()) {
     // We don't report warning in this case. For example,
     // sometimes .so compiled from multiple object files contains a few
     // rudimentary sequences for address ranges [0x0, 0xsomething).
   }
 
   return end_offset;
 }
 
+uint32_t
+DWARFDebugLine::LineTable::findRowInSeq(const DWARFDebugLine::Sequence &seq,
+                                        uint64_t address) const {
+  if (!seq.containsPC(address))
+    return UnknownRowIndex;
+  // Search for instruction address in the rows describing the sequence.
+  // Rows are stored in a vector, so we may use arithmetical operations with
+  // iterators.
+  DWARFDebugLine::Row row;
+  row.Address = address;
+  RowIter first_row = Rows.begin() + seq.FirstRowIndex;
+  RowIter last_row = Rows.begin() + seq.LastRowIndex;
+  LineTable::RowIter row_pos = std::lower_bound(
+      first_row, last_row, row, DWARFDebugLine::Row::orderByAddress);
+  if (row_pos == last_row) {
+    return seq.LastRowIndex - 1;
+  }
+  uint32_t index = seq.FirstRowIndex + (row_pos - first_row);
+  if (row_pos->Address > address) {
+    if (row_pos == first_row)
+      return UnknownRowIndex;
+    else
+      index--;
+  }
+  return index;
+}
+
 uint32_t DWARFDebugLine::LineTable::lookupAddress(uint64_t address) const {
-  uint32_t unknown_index = UINT32_MAX;
   if (Sequences.empty())
-    return unknown_index;
+    return UnknownRowIndex;
   // First, find an instruction sequence containing the given address.
   DWARFDebugLine::Sequence sequence;
   sequence.LowPC = address;
   SequenceIter first_seq = Sequences.begin();
   SequenceIter last_seq = Sequences.end();
   SequenceIter seq_pos = std::lower_bound(first_seq, last_seq, sequence,
       DWARFDebugLine::Sequence::orderByLowPC);
   DWARFDebugLine::Sequence found_seq;
   if (seq_pos == last_seq) {
     found_seq = Sequences.back();
   } else if (seq_pos->LowPC == address) {
     found_seq = *seq_pos;
   } else {
     if (seq_pos == first_seq)
-      return unknown_index;
+      return UnknownRowIndex;
     found_seq = *(seq_pos - 1);
   }
-  if (!found_seq.containsPC(address))
-    return unknown_index;
-  // Search for instruction address in the rows describing the sequence.
-  // Rows are stored in a vector, so we may use arithmetical operations with
-  // iterators.
-  DWARFDebugLine::Row row;
-  row.Address = address;
-  RowIter first_row = Rows.begin() + found_seq.FirstRowIndex;
-  RowIter last_row = Rows.begin() + found_seq.LastRowIndex;
-  RowIter row_pos = std::lower_bound(first_row, last_row, row,
-      DWARFDebugLine::Row::orderByAddress);
-  if (row_pos == last_row) {
-    return found_seq.LastRowIndex - 1;
-  }
-  uint32_t index = found_seq.FirstRowIndex + (row_pos - first_row);
-  if (row_pos->Address > address) {
-    if (row_pos == first_row)
-      return unknown_index;
-    else
-      index--;
-  }
-  return index;
+  return findRowInSeq(found_seq, address);
 }
 
 bool DWARFDebugLine::LineTable::lookupAddressRange(
     uint64_t address, uint64_t size, std::vector<uint32_t> &result) const {
   if (Sequences.empty())
     return false;
   uint64_t end_addr = address + size;
   // First, find an instruction sequence containing the given address.
if (!seq_pos->containsPC(address))
     return false;
 
   SequenceIter start_pos = seq_pos;
 
   // Add the rows from the first sequence to the vector, starting with the
   // index we just calculated
 
   while (seq_pos != last_seq && seq_pos->LowPC < end_addr) {
-    DWARFDebugLine::Sequence cur_seq = *seq_pos;
-    uint32_t first_row_index;
-    uint32_t last_row_index;
-    if (seq_pos == start_pos) {
-      // For the first sequence, we need to find which row in the sequence is the
-      // first in our range. Rows are stored in a vector, so we may use
-      // arithmetical operations with iterators.
-      DWARFDebugLine::Row row;
-      row.Address = address;
-      RowIter first_row = Rows.begin() + cur_seq.FirstRowIndex;
-      RowIter last_row = Rows.begin() + cur_seq.LastRowIndex;
-      RowIter row_pos = std::upper_bound(first_row, last_row, row,
-                                         DWARFDebugLine::Row::orderByAddress);
-      // The 'row_pos' iterator references the first row that is greater than
-      // our start address. Unless that's the first row, we want to start at
-      // the row before that.
-      first_row_index = cur_seq.FirstRowIndex + (row_pos - first_row);
-      if (row_pos != first_row)
-        --first_row_index;
-    } else
-      first_row_index = cur_seq.FirstRowIndex;
-
-    // For the last sequence in our range, we need to figure out the last row in
-    // range.  For all other sequences we can go to the end of the sequence.
-    if (cur_seq.HighPC > end_addr) {
-      DWARFDebugLine::Row row;
-      row.Address = end_addr;
-      RowIter first_row = Rows.begin() + cur_seq.FirstRowIndex;
-      RowIter last_row = Rows.begin() + cur_seq.LastRowIndex;
-      RowIter row_pos = std::upper_bound(first_row, last_row, row,
-                                         DWARFDebugLine::Row::orderByAddress);
-      // The 'row_pos' iterator references the first row that is greater than
-      // our end address.  The row before that is the last row we want.
-      last_row_index = cur_seq.FirstRowIndex + (row_pos - first_row) - 1;
-    } else
-      // Contrary to what you might expect, DWARFDebugLine::SequenceLastRowIndex
-      // isn't a valid index within the current sequence.  It's that plus one.
+    const DWARFDebugLine::Sequence &cur_seq = *seq_pos;
+    // first in our range.
+    uint32_t first_row_index = cur_seq.FirstRowIndex;
+    if (seq_pos == start_pos)
+      first_row_index = findRowInSeq(cur_seq, address);
+
+    // Figure out the last row in the range.
+    uint32_t last_row_index = findRowInSeq(cur_seq, end_addr - 1);
+    if (last_row_index == UnknownRowIndex)
       last_row_index = cur_seq.LastRowIndex - 1;
 
+    assert(first_row_index != UnknownRowIndex);
+    assert(last_row_index != UnknownRowIndex);
+
     for (uint32_t i = first_row_index; i <= last_row_index; ++i) {
       result.push_back(i);
     }
 
     ++seq_pos;
   }
 
   return true;

llvm/trunk/test/DebugInfo/debuglineinfo-macho.test

 # Check that relocations get applied
 RUN: llvm-dwarfdump %p/Inputs/test-simple-macho.o | FileCheck %s
 RUN: llvm-dwarfdump %p/Inputs/test-multiple-macho.o | FileCheck %s
-RUN: llvm-rtdyld -printline %p/Inputs/test-multiple-macho.o | \
-RUN:   FileCheck --check-prefix=SIZE %s
+RUN: llvm-rtdyld -printline %p/Inputs/test-multiple-macho.o | FileCheck %s
 RUN: llvm-rtdyld -printobjline %p/Inputs/test-multiple-macho.o | FileCheck %s
 
-SIZE: Function: _bar, Size = 48
-SIZE: Function: _foo, Size = 16
-SIZE: Function: _fubar, Size = 46
-
 CHECK-NOT: error: failed to compute relocation: X86_64_RELOC_UNSIGNED
+
+# Check that relocations get applied correctly
+RUN: llvm-rtdyld -printobjline %p/Inputs/test-simple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_SIMPLE
+RUN: llvm-rtdyld -printline %p/Inputs/test-simple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_SIMPLE
+RUN: llvm-rtdyld -printobjline %p/Inputs/test-multiple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_MULTIPLE
+RUN: llvm-rtdyld -printline %p/Inputs/test-multiple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_MULTIPLE
+
+TEST_SIMPLE:      Function: _foo, Size = 11
+TEST_SIMPLE-NEXT:  Line info @ 0: simple.c, line:1
+TEST_SIMPLE-NEXT:  Line info @ 7: simple.c, line:2
+TEST_SIMPLE-NOT:   Line info @ 11: simple.c, line:2
+
+TEST_MULTIPLE:      Function: _bar, Size = 48
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:5
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:6
+TEST_MULTIPLE-NEXT:   Line info @ 16: multiple.c, line:9
+TEST_MULTIPLE-NEXT:   Line info @ 21: multiple.c, line:9
+TEST_MULTIPLE-NEXT:   Line info @ 26: multiple.c, line:7
+TEST_MULTIPLE-NEXT:   Line info @ 33: multiple.c, line:10
+TEST_MULTIPLE-NOT:    Line info @ 48: multiple.c, line:12
+TEST_MULTIPLE-NEXT: Function: _foo, Size = 16
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:1
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:2
+TEST_MULTIPLE-NOT:    Line info @ 16: multiple.c, line:5
+TEST_MULTIPLE-NEXT: Function: _fubar, Size = 46
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:12
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:13
+TEST_MULTIPLE-NEXT:   Line info @ 12: multiple.c, line:17
+TEST_MULTIPLE-NEXT:   Line info @ 25: multiple.c, line:15
+TEST_MULTIPLE-NEXT:   Line info @ 34: multiple.c, line:19
+TEST_MULTIPLE-NEXT:   Line info @ 41: multiple.c, line:21
+TEST_MULTIPLE-NOT:    Line info @ 46: multiple.c, line:21

llvm/trunk/test/DebugInfo/debuglineinfo.test

 ; both starting at address zero in the; line number table.
 TEST_INLINE:      Function: _Z15test_parametersPfPA2_dR11char_structPPitm, Size = 170
 TEST_INLINE-NEXT: Line info @ 0: test-inline.cpp, line:33
 TEST_INLINE-NEXT: Line info @ 35: test-inline.cpp, line:34
 TEST_INLINE-NEXT: Line info @ 165: test-inline.cpp, line:35
 TEST_INLINE-NEXT: Function: _Z3foov, Size = 3
 TEST_INLINE-NEXT: Line info @ 0: test-inline.cpp, line:28
 TEST_INLINE-NEXT: Line info @ 2: test-inline.cpp, line:29
-TEST_INLINE-NEXT: Line info @ 3: test-inline.cpp, line:29
 TEST_INLINE-NEXT: Function: main, Size = 146
 TEST_INLINE-NEXT: Line info @ 0: test-inline.cpp, line:39
 TEST_INLINE-NEXT: Line info @ 21: test-inline.cpp, line:41
 TEST_INLINE-NEXT: Line info @ 39: test-inline.cpp, line:42
 TEST_INLINE-NEXT: Line info @ 60: test-inline.cpp, line:44
 TEST_INLINE-NEXT: Line info @ 80: test-inline.cpp, line:48
 TEST_INLINE-NEXT: Line info @ 90: test-inline.cpp, line:45
 TEST_INLINE-NEXT: Line info @ 95: test-inline.cpp, line:46
 TEST_INLINE-NEXT: Line info @ 114: test-inline.cpp, line:48 
 TEST_INLINE-NEXT: Line info @ 141: test-inline.cpp, line:49
-TEST_INLINE-NEXT: Line info @ 146: test-inline.cpp, line:49
 
 ; This test checks the case where all code is in a single section.
 TEST_PARAMETERS:      Function: _Z15test_parametersPfPA2_dR11char_structPPitm, Size = 170
 TEST_PARAMETERS-NEXT: Line info @ 0: test-parameters.cpp, line:33
 TEST_PARAMETERS-NEXT: Line info @ 35: test-parameters.cpp, line:34
 TEST_PARAMETERS-NEXT: Line info @ 165: test-parameters.cpp, line:35
 TEST_PARAMETERS-NEXT: Function: _Z3foov, Size = 3
 TEST_PARAMETERS-NEXT: Line info @ 0: test-parameters.cpp, line:28
 TEST_PARAMETERS-NEXT: Line info @ 2: test-parameters.cpp, line:29
 TEST_PARAMETERS-NEXT: Function: main, Size = 146
 TEST_PARAMETERS-NEXT: Line info @ 0: test-parameters.cpp, line:39
 TEST_PARAMETERS-NEXT: Line info @ 21: test-parameters.cpp, line:41
 TEST_PARAMETERS-NEXT: Line info @ 39: test-parameters.cpp, line:42
 TEST_PARAMETERS-NEXT: Line info @ 60: test-parameters.cpp, line:44
 TEST_PARAMETERS-NEXT: Line info @ 80: test-parameters.cpp, line:48
 TEST_PARAMETERS-NEXT: Line info @ 90: test-parameters.cpp, line:45
 TEST_PARAMETERS-NEXT: Line info @ 95: test-parameters.cpp, line:46
 TEST_PARAMETERS-NEXT: Line info @ 114: test-parameters.cpp, line:48 
 TEST_PARAMETERS-NEXT: Line info @ 141: test-parameters.cpp, line:49
-TEST_PARAMETERS-NEXT: Line info @ 146: test-parameters.cpp, line:49