[PATCH][gdb/symtab] Fix line-table end-of-sequence sorting
Andrew Burgess
andrew.burgess@embecosm.com
Mon Jun 15 10:42:45 GMT 2020
* Tom de Vries <tdevries@suse.de> [2020-06-08 17:50:33 +0200]:
> 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.
Well, sorting _and_ empty lines, so I think it is extremely relevant.
For reference, the thread where this was added, which specifically
talks about encountering empty lines in the wild, and how this
interacts with sorting:
https://sourceware.org/pipermail/gdb-patches/2007-October/052736.html
And the commit where this code landed:
commit 607ae575a784d7d02956031883ae407faf06fd89
Date: Thu Oct 11 17:38:59 2007 +0000
* buildsym.c (record_line): Remove empty lines followed by
end-of-sequence markers.
>
> >> 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
>
>
>
> [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".
LGTM.
Thanks for doing this.
Andrew
>
> 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
> }
More information about the Gdb-patches
mailing list