[PATCH][gdb/symtab] Fix line-table end-of-sequence sorting
Tom de Vries
tdevries@suse.de
Mon Jun 8 15:50:33 GMT 2020
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-gdb-symtab-Fix-line-table-end-of-sequence-sorting.patch
Type: text/x-patch
Size: 5592 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/gdb-patches/attachments/20200608/e659431a/attachment-0001.bin>
More information about the Gdb-patches
mailing list