Re: [PATCH][gdb/symtab] Fix line-table end-of-sequence sorting

[Tom de Vries <tdevries@suse.de>]

[-- Attachment #1: Type: text/plain, Size: 14189 bytes --]

On 06-06-2020 11:25, Andrew Burgess wrote:
> * Tom de Vries <tdevries@suse.de> [2020-06-06 01:44:42 +0200]:
> 
>> [ was: Re: [PATCH 2/3] gdb: Don't reorder line table entries too much
>> when sorting. ]
>>
>> On 05-06-2020 18:00, Tom de Vries wrote:
>>> On 05-06-2020 16:49, Tom de Vries wrote:
>>>> On 23-12-2019 02:51, Andrew Burgess wrote:
>>>>> I had to make a small adjustment in find_pc_sect_line in order to
>>>>> correctly find the previous line in the line table.  In some line
>>>>> tables I was seeing an actual line entry and an end of sequence marker
>>>>> at the same address, before this commit these would reorder to move
>>>>> the end of sequence marker before the line entry (end of sequence has
>>>>> line number 0).  Now the end of sequence marker remains in its correct
>>>>> location, and in order to find a previous line we should step backward
>>>>> over any end of sequence markers.
>>>>>
>>>>> As an example, the binary:
>>>>>   gdb/testsuite/outputs/gdb.dwarf2/dw2-ranges-func/dw2-ranges-func-lo-cold
>>>>>
>>>>> Has this line table before the patch:
>>>>>
>>>>>   INDEX    LINE ADDRESS
>>>>>   0          48 0x0000000000400487
>>>>>   1         END 0x000000000040048e
>>>>>   2          52 0x000000000040048e
>>>>>   3          54 0x0000000000400492
>>>>>   4          56 0x0000000000400497
>>>>>   5         END 0x000000000040049a
>>>>>   6          62 0x000000000040049a
>>>>>   7         END 0x00000000004004a1
>>>>>   8          66 0x00000000004004a1
>>>>>   9          68 0x00000000004004a5
>>>>>   10         70 0x00000000004004aa
>>>>>   11         72 0x00000000004004b9
>>>>>   12        END 0x00000000004004bc
>>>>>   13         76 0x00000000004004bc
>>>>>   14         78 0x00000000004004c0
>>>>>   15         80 0x00000000004004c5
>>>>>   16        END 0x00000000004004cc
>>>>>
>>>>> And after this patch:
>>>>>
>>>>>   INDEX    LINE ADDRESS
>>>>>   0          48 0x0000000000400487
>>>>>   1          52 0x000000000040048e
>>>>>   2         END 0x000000000040048e
>>>>>   3          54 0x0000000000400492
>>>>>   4          56 0x0000000000400497
>>>>>   5         END 0x000000000040049a
>>>>>   6          62 0x000000000040049a
>>>>>   7          66 0x00000000004004a1
>>>>>   8         END 0x00000000004004a1
>>>>>   9          68 0x00000000004004a5
>>>>>   10         70 0x00000000004004aa
>>>>>   11         72 0x00000000004004b9
>>>>>   12        END 0x00000000004004bc
>>>>>   13         76 0x00000000004004bc
>>>>>   14         78 0x00000000004004c0
>>>>>   15         80 0x00000000004004c5
>>>>>   16        END 0x00000000004004cc
>>>>>
>>>>> When calling find_pc_sect_line with the address 0x000000000040048e, in
>>>>> both cases we find entry #3, we then try to find the previous entry,
>>>>> which originally found this entry '2         52 0x000000000040048e',
>>>>> after the patch it finds '2         END 0x000000000040048e', which
>>>>> cases the lookup to fail.
>>>>>
>>>>> By skipping the END marker after this patch we get back to the correct
>>>>> entry, which is now #1: '1          52 0x000000000040048e', and
>>>>> everything works again.
>>>>
>>>> I start to suspect that you have been working around an incorrect line
>>>> table.
>>>>
>>>> Consider this bit:
>>>> ...
>>>>    0          48 0x0000000000400487
>>>>    1          52 0x000000000040048e
>>>>    2         END 0x000000000040048e
>>>> ...
>>>>
>>>> The end marker marks the address one past the end of the sequence.
>>>> Therefore, it makes no sense to have an entry in the sequence with the
>>>> same address as the end marker.
>>>>
>>>> [ dwarf doc:
>>>>
>>>> end_sequence:
>>>>
>>>> A boolean indicating that the current address is that of the first byte
>>>> after the end of a sequence of target machine instructions. end_sequence
>>>> terminates a sequence of lines; therefore other information in the same
>>>> row is not meaningful.
>>>>
>>>> DW_LNE_end_sequence:
>>>>
>>>> The DW_LNE_end_sequence opcode takes no operands. It sets the
>>>> end_sequence register of the state machine to “true” and appends a row
>>>> to the matrix using the current values of the state-machine registers.
>>>> Then it resets the registers to the initial values specified above (see
>>>> Section 6.2.2). Every line number program sequence must end with a
>>>> DW_LNE_end_sequence instruction which creates a row whose address is
>>>> that of the byte after the last target machine instruction of the sequence.
>>>>
>>>> ]
>>>>
>>>> The incorrect entry is generated by this dwarf assembler sequence:
>>>> ...
>>>>                 {DW_LNS_copy}
>>>>                 {DW_LNE_end_sequence}
>>>> ...
>>>>
>>>> I think we should probably fix the dwarf assembly test-cases.
>>>>
>>>> If we want to handle this in gdb, the thing that seems most logical to
>>>> me is to ignore this kind of entries.
>>>
>>> Hmm, that seems to be done already, in buildsym_compunit::record_line.
>>>
>>> Anyway, I was looking at the line table for
>>> gdb.dwarf2/dw2-ranges-base.exp, and got a line table with subsequent end
>>> markers:
>>> ...
>>> INDEX  LINE   ADDRESS            IS-STMT
>>> 0      31     0x00000000004004a7 Y
>>> 1      21     0x00000000004004ae Y
>>> 2      END    0x00000000004004ae Y
>>> 3      11     0x00000000004004ba Y
>>> 4      END    0x00000000004004ba Y
>>> 5      END    0x00000000004004c6 Y
>>> ...
>>>
>>> By using this patch:
>>> ...
>>> diff --git a/gdb/buildsym.c b/gdb/buildsym.c
>>> index 33bf6523e9..76f0b54ff6 100644
>>> --- a/gdb/buildsym.c
>>> +++ b/gdb/buildsym.c
>>> @@ -943,6 +943,10 @@ buildsym_compunit::end_symtab_with_blockvector
>>> (struct block *static_block,
>>>             = [] (const linetable_entry &ln1,
>>>                   const linetable_entry &ln2) -> bool
>>>               {
>>> +               if (ln1.pc == ln2.pc
>>> +                   && ((ln1.line == 0) != (ln2.line == 0)))
>>> +                 return ln1.line == 0 ? true : false;
>>> +
>>>                 return (ln1.pc < ln2.pc);
>>>               };
>>>
>>> ...
>>> I get the expected:
>>> ...
>>> INDEX  LINE   ADDRESS            IS-STMT
>>> 0      31     0x00000000004004a7 Y
>>> 1      END    0x00000000004004ae Y
>>> 2      21     0x00000000004004ae Y
>>> 3      END    0x00000000004004ba Y
>>> 4      11     0x00000000004004ba Y
>>> 5      END    0x00000000004004c6 Y
>>> ...
>>
>> Any comments on patch below?
> 
> Yes! Thank you for working on this.
> 
> This should go in, however, I'd like to tweak the commit message a bit
> please (see below).
> 
> Also, do you plan to include the revert of find_pc_sect_line from
> 3d92a3e313 in this patch - I think you should.
> 

Included in this version of the patch.

> Thanks,
> Andrew
> 
>>
>> Thanks,
>> - Tom
>>
> 
>> [gdb/symtab] Fix line-table end-of-sequence sorting
>>
>> Consider test-case gdb.dwarf2/dw2-ranges-base.exp.  It has a line-table for
>> dw2-ranges-base.c like this:
>> ...
>>  Line Number Statements:
>>   [0x0000014e]  Extended opcode 2: set Address to 0x4004ba
>>   [0x00000159]  Advance Line by 10 to 11
>>   [0x0000015b]  Copy
>>   [0x0000015c]  Advance PC by 12 to 0x4004c6
>>   [0x0000015e]  Advance Line by 19 to 30
>>   [0x00000160]  Copy
>>   [0x00000161]  Extended opcode 1: End of Sequence
>>
>>   [0x00000164]  Extended opcode 2: set Address to 0x4004ae
>>   [0x0000016f]  Advance Line by 20 to 21
>>   [0x00000171]  Copy
>>   [0x00000172]  Advance PC by 12 to 0x4004ba
>>   [0x00000174]  Advance Line by 29 to 50
>>   [0x00000176]  Copy
>>   [0x00000177]  Extended opcode 1: End of Sequence
>>
>>   [0x0000017a]  Extended opcode 2: set Address to 0x4004a7
>>   [0x00000185]  Advance Line by 30 to 31
>>   [0x00000187]  Copy
>>   [0x00000188]  Advance PC by 7 to 0x4004ae
>>   [0x0000018a]  Advance Line by 39 to 70
>>   [0x0000018c]  Copy
>>   [0x0000018d]  Extended opcode 1: End of Sequence
>> ...
>>
>> The Copy followed by End-of-Sequence is as specified in the dwarf assembly,
>> but incorrect.  F.i., consider:
>> ...
>>   [0x0000015c]  Advance PC by 12 to 0x4004c6
>>   [0x0000015e]  Advance Line by 19 to 30
>>   [0x00000160]  Copy
>>   [0x00000161]  Extended opcode 1: End of Sequence
>> ...
>>
>> Both the Copy and the End-of-Sequence append a row to the matrix using the
>> same addres: 0x4004c6.  The Copy declares a target instruction at that
>> address.  The End-of-Sequence declares that the sequence ends before that
>> address.  It's a contradiction that the target instruction is both part of the
>> sequence (according to Copy) and not part of the sequence (according to
>> End-of-Sequence).
> 
> I don't want to argue about this specific test, but about the idea of
> an empty line occurring at the same address as an end of sequence
> marker.  This can happen due to compiler optimisation, though it is
> perfectly reasonable to suggest that in this case the compiler should
> be removing the line marker, this doesn't always happen.
> 
> I guess what I'm saying is that I think the case for this being
> obviously wrong is not quite as clear cut as you seem to imply, but
> also, I don't think this is really relevant to this bug - so maybe we
> could just drop this part?
> 
>> The offending Copy is skipped though by buildsym_compunit::record_line for
>> unrelated reasons.
> 
> Not really unrelated - specifically to catch this case (assuming we're
> thinking about the same code).
>

I read this comment in buildsym_compunit::record_line:
...
  /* Normally, we treat lines as unsorted.  But the end of sequence

     marker is special.  We sort line markers at the same PC by line

     number, so end of sequence markers (which have line == 0) appear

     first.  This is right if the marker ends the previous function,

     and there is no padding before the next function.  But it is

     wrong if the previous line was empty and we are now marking a

     switch to a different subfile.  We must leave the end of sequence

     marker at the end of this group of lines, not sort the empty line

     to after the marker.  The easiest way to accomplish this is to

     delete any empty lines from our table, if they are followed by

     end of sequence markers.  All we lose is the ability to set

     breakpoints at some lines which contain no instructions

     anyway.  */
...

So, my impression is that this was added to deal with problems related
to the sorting based on line numbers, and no to remove invalid dwarf
ops. Hence my "unrelated" classification.

>>                     So, if we disable the sorting in
>> buildsym_compunit::end_symtab_with_blockvector, we have:
>> ...
>> INDEX  LINE   ADDRESS            IS-STMT
>> 0      11     0x00000000004004ba Y
>> 1      END    0x00000000004004c6 Y
>> 2      21     0x00000000004004ae Y
>> 3      END    0x00000000004004ba Y
>> 4      31     0x00000000004004a7 Y
>> 5      END    0x00000000004004ae Y
>> ...
>> but if we re-enable the sorting, we have:
>> ...
>> INDEX  LINE   ADDRESS            IS-STMT
>> 0      31     0x00000000004004a7 Y
>> 1      21     0x00000000004004ae Y
>> 2      END    0x00000000004004ae Y
>> 3      11     0x00000000004004ba Y
>> 4      END    0x00000000004004ba Y
>> 5      END    0x00000000004004c6 Y
>> ...
>> which has both:
>> - the contradictory order for the same-address pairs 1/2 and 3/4, as well as
>> - a non-sensical pair of ENDs,
>> while we'd like:
>> ...
>> INDEX  LINE   ADDRESS            IS-STMT
>> 0      31     0x00000000004004a7 Y
>> 1      END    0x00000000004004ae Y
>> 2      21     0x00000000004004ae Y
>> 3      END    0x00000000004004ba Y
>> 4      11     0x00000000004004ba Y
>> 5      END    0x00000000004004c6 Y
>> ...
> 
> You're description here is absolutely correct, but I don't feel it
> doesn't draw enough attention to what the real mistake inside GDB is.
> 
> Consider this line table, it shows two sequences, each delimited with
> an END marker.  The table is extracted from the DWARF with the entries
> in this exact order:
> 
>   | Address | Line |
>   |---------+------|
>   |   0x100 |   10 |
>   |   0x102 |   11 |
>   |   0x104 |  END |
>   |---------+------|
>   |    0x98 |  100 |
>   |    0x9a |  101 |
>   |    0x9c |  102 |
>   |    0x9e |  103 |
>   |   0x100 |  END |
>   |---------+------|
> 
> What we want is to reorder the two sequences relative to each other.
> The current sorting does this by sorting on 'Address', while leaving
> entries at the same address in their original order, this gives:
> 
>   | Address | Line |
>   |---------+------|
>   |    0x98 |  100 |
>   |    0x9a |  101 |
>   |    0x9c |  102 |
>   |    0x9e |  103 |
>   |   0x100 |   10 |
>   |   0x100 |  END |
>   |---------+------|
>   |   0x102 |   11 |
>   |   0x104 |  END |
>   |---------+------|
> 
> Here we see that line 10 has jumped from being the start of one
> sequence to appear at the end of the other sequence's END marker, this
> is maintained the table order, but is clearly incorrect.
> 
> A better sort would order by 'Address', but always move END markers to
> be the first entry at a given 'Address', this would give us:
> 
>   | Address | Line |
>   |---------+------|
>   |    0x98 |  100 |
>   |    0x9a |  101 |
>   |    0x9c |  102 |
>   |    0x9e |  103 |
>   |   0x100 |  END |
>   |---------+------|
>   |   0x100 |   10 |
>   |   0x102 |   11 |
>   |   0x104 |  END |
>   |---------+------|
> 
>>
>> This is a regression since commit 3d92a3e313 "gdb: Don't reorder line table
>> entries too much when sorting", that introduced sorting on address while
>> keeping entries with the same address in pre-sort order, which leads to
>> incorrect results if one of the entries is an End-Of-Sequence.
> 
> Before commit 3d92a3e313, entries at the same address were sorted by
> line number.  The correctly pushes END markers (line number 0) to be
> the first entry at that address, but also corrupts the ordering of non
> END markers.
> 
> This commit corrects the mistake of 3d92a3e313, by finding a middle
> ground; keep entries at the same address in order _except_ for end
> markers, which are always sorted to be earlier in the table.
> 

Here's the updated patch, I've tried to make the commit message more
detailed based on your feedback above, I hope this addresses your concerns.

Thanks,
- Tom




[-- Attachment #2: 0002-gdb-symtab-Fix-line-table-end-of-sequence-sorting.patch --]
[-- Type: text/x-patch, Size: 5592 bytes --]

[gdb/symtab] Fix line-table end-of-sequence sorting

Consider test-case gdb.dwarf2/dw2-ranges-base.exp.  It has (after
"[gdb/testsuite] Fix bad line table entry sequence") a line-table for
dw2-ranges-base.c like this:
...
 Line Number Statements:
  [0x0000014e]  Extended opcode 2: set Address to 0x4004ba
  [0x00000159]  Advance Line by 10 to 11
  [0x0000015b]  Copy
  [0x0000015c]  Advance PC by 12 to 0x4004c6
  [0x0000015e]  Extended opcode 1: End of Sequence

  [0x00000161]  Extended opcode 2: set Address to 0x4004ae
  [0x0000016c]  Advance Line by 20 to 21
  [0x0000016e]  Copy
  [0x0000016f]  Advance PC by 12 to 0x4004ba
  [0x00000171]  Extended opcode 1: End of Sequence

  [0x00000174]  Extended opcode 2: set Address to 0x4004a7
  [0x0000017f]  Advance Line by 30 to 31
  [0x00000181]  Copy
  [0x00000182]  Advance PC by 7 to 0x4004ae
  [0x00000184]  Extended opcode 1: End of Sequence
...

If we disable the sorting in buildsym_compunit::end_symtab_with_blockvector,
we have the unsorted line table:
...
INDEX  LINE   ADDRESS            IS-STMT
0      11     0x00000000004004ba Y
1      END    0x00000000004004c6 Y
2      21     0x00000000004004ae Y
3      END    0x00000000004004ba Y
4      31     0x00000000004004a7 Y
5      END    0x00000000004004ae Y
...
It contains 3 sequences, 11/END, 21/END and 31/END.

We want to sort the 3 sequences relative to each other, while sorting on
address, to get:
...
INDEX  LINE   ADDRESS            IS-STMT
0      31     0x00000000004004a7 Y
1      END    0x00000000004004ae Y
2      21     0x00000000004004ae Y
3      END    0x00000000004004ba Y
4      11     0x00000000004004ba Y
5      END    0x00000000004004c6 Y
...

However, if we re-enable the sorting, we have instead:
...
INDEX  LINE   ADDRESS            IS-STMT
0      31     0x00000000004004a7 Y
1      21     0x00000000004004ae Y
2      END    0x00000000004004ae Y
3      11     0x00000000004004ba Y
4      END    0x00000000004004ba Y
5      END    0x00000000004004c6 Y
...

This is a regression since commit 3d92a3e313 "gdb: Don't reorder line table
entries too much when sorting", that introduced sorting on address while
keeping entries with the same address in pre-sort order.

Indeed the entries 1 and 2 are in pre-sort order (they map to entries 2 and 5
in the unsorted line table), but entry 1 does not belong in the sequence
terminated by 2.

Fix this by handling End-Of-Sequence entries in the sorting function, such
that they are sorted before other entries with the same address.

Also, revert the find_pc_sect_line workaround introduced in commit 3d92a3e313,
since that's no longer necessary.

Tested on x86_64-linux.

gdb/ChangeLog:

2020-06-06  Tom de Vries  <tdevries@suse.de>

	* buildsym.c (buildsym_compunit::end_symtab_with_blockvector): Handle
	End-Of-Sequence in lte_is_less_than.
	* symtab.c (find_pc_sect_line): Revert change from commit 3d92a3e313
	"gdb: Don't reorder line table entries too much when sorting".

gdb/testsuite/ChangeLog:

2020-06-06  Tom de Vries  <tdevries@suse.de>

	* gdb.dwarf2/dw2-ranges-base.exp: Test line-table order.

---
 gdb/buildsym.c                               |  4 ++++
 gdb/symtab.c                                 |  7 +------
 gdb/testsuite/gdb.dwarf2/dw2-ranges-base.exp | 14 ++++++++++++++
 3 files changed, 19 insertions(+), 6 deletions(-)

diff --git a/gdb/buildsym.c b/gdb/buildsym.c
index 33bf6523e9..aa26b3a97b 100644
--- a/gdb/buildsym.c
+++ b/gdb/buildsym.c
@@ -943,6 +943,10 @@ buildsym_compunit::end_symtab_with_blockvector (struct block *static_block,
 	    = [] (const linetable_entry &ln1,
 		  const linetable_entry &ln2) -> bool
 	      {
+		if (ln1.pc == ln2.pc
+		    && ((ln1.line == 0) != (ln2.line == 0)))
+		  return ln1.line == 0;
+
 		return (ln1.pc < ln2.pc);
 	      };
 
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 791ce11a73..8344904652 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -3237,12 +3237,7 @@ find_pc_sect_line (CORE_ADDR pc, struct obj_section *section, int notcurrent)
       struct linetable_entry *last = item + len;
       item = std::upper_bound (first, last, pc, pc_compare);
       if (item != first)
-	{
-	  /* Found a matching item.  Skip backwards over any end of
-	     sequence markers.  */
-	  for (prev = item - 1; prev->line == 0 && prev != first; prev--)
-	    /* Nothing.  */;
-	}
+	prev = item - 1;		/* Found a matching item.  */
 
       /* At this point, prev points at the line whose start addr is <= pc, and
          item points at the next line.  If we ran off the end of the linetable
diff --git a/gdb/testsuite/gdb.dwarf2/dw2-ranges-base.exp b/gdb/testsuite/gdb.dwarf2/dw2-ranges-base.exp
index 9e4ebf7f3c..430a45c53b 100644
--- a/gdb/testsuite/gdb.dwarf2/dw2-ranges-base.exp
+++ b/gdb/testsuite/gdb.dwarf2/dw2-ranges-base.exp
@@ -138,12 +138,26 @@ gdb_test "info line frame3" \
 
 # Ensure that the line table correctly tracks the end of sequence markers.
 set end_seq_count 0
+set prev -1
+set seq_count 0
 gdb_test_multiple "maint info line-table gdb.dwarf2/dw2-ranges-base.c" \
     "count END markers in line table" {
 	-re "^$decimal\[ \t\]+$decimal\[ \t\]+$hex\(\[ \t\]+Y\)? *\r\n" {
+	    if { $prev != -1 } {
+		gdb_assert "$prev == 1" \
+		    "prev of normal entry at $seq_count is end marker"
+	    }
+	    set prev 0
+	    incr seq_count
 	    exp_continue
 	}
 	-re "^$decimal\[ \t\]+END\[ \t\]+$hex\(\[ \t\]+Y\)? *\r\n" {
+	    if { $prev != -1 } {
+		gdb_assert "$prev == 0" \
+		    "prev of end marker at $seq_count is normal entry"
+	    }
+	    set prev 1
+	    incr seq_count
 	    incr end_seq_count
 	    exp_continue
 	}