[Bug sanitizer/65479] New: sanitizer stack trace missing frames past #0 on powerpc64

[Bug sanitizer/65479] New: sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

            Bug ID: 65479
           Summary: sanitizer stack trace missing frames past #0 on
                    powerpc64
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: sanitizer
          Assignee: unassigned at gcc dot gnu.org
          Reporter: msebor at gcc dot gnu.org
                CC: dodji at gcc dot gnu.org, dvyukov at gcc dot gnu.org,
                    jakub at gcc dot gnu.org, kcc at gcc dot gnu.org

On both powerpc64 and powerpc64le, the c-c++-common/asan/misalign-1.c shows 6
failures, all in the output pattern test.  The failures are due to to the stack
trace missing stack frame #1 (it only includes frame #0).  It looks like the
backtrace on powerpc doesn't work correctly.

=================================================================
==87868==ERROR: AddressSanitizer: unknown-crash on address 0x3fffc231eb2f at pc
0x000010000ce8 bp 0x3fffc231e9f0 sp 0x3fffc231ea10
READ of size 4 at 0x3fffc231eb2f thread T0
    #0 0x10000ce4 in foo
/src/gcc-5.0-git/gcc/testsuite/c-c++-common/asan/misalign-1.c:11

Address 0x3fffc231eb2f is located in stack of thread T0 at offset 175 in frame
    #0 0x1000086c in main
/src/gcc-5.0-git/gcc/testsuite/c-c++-common/asan/misalign-1.c:28

  This frame has 3 object(s):
    [32, 36) 'v'
    [96, 100) 'w'
    [160, 176) 't' <== Memory access at offset 175 partially overflows this
variable
HINT: this may be a false positive if your program uses some custom stack
unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: unknown-crash
/src/gcc-5.0-git/gcc/testsuite/c-c++-common/asan/misalign-1.c:11 foo
Shadow bytes around the buggy address:
  0x09fff8463d10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d30: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d50: f1 f1 f1 f1 04 f4 f4 f4 f2 f2 f2 f2 04 f4 f4 f4
=>0x09fff8463d60: f2 f2 f2 f2 00[00]f4 f4 f3 f3 f3 f3 00 00 00 00
  0x09fff8463d70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463d90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463da0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x09fff8463db0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==87868==ABORTING

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #1 from Martin Sebor <msebor at gcc dot gnu.org> ---
The same problem is causing failures in the following tests on these targets:
c-c++-common/asan/misalign-2.c
c-c++-common/asan/null-deref-1.c

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #2 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 35196
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35196&action=edit
Proof-of-concept patch.

Two problems are contributing to the failures in these tests:

1) a missing -fasynchronous-unwind-tables option; the option is necessary on
powerpc*-*-*-* to generate a full stack trace
2) a bug in the backtrace_qsort function introduced in r208403 that makes the
algorithm unstable (see also
http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00342.html)

The attached proof-of-concept patch adds the missing option mentioned in (1)
and backs out the commit referenced in (2) as a proof of concept of fixing the
problem.  I'll try to come up with an approach that doesn't undo the
performance improvement in a subsequent patch.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|powerpc64*-linux-*          |

--- Comment #3 from Martin Sebor <msebor at gcc dot gnu.org> ---
The bug in backtrace_qsort is actually worse than the regression introduced in
r208403.  There is a fundamental problem with relying on the addresses of the
array elements to maintain stability.  Either the algorithm needs to be
replaced with a stable one like Merge Sort, or a new data member needs to be
introduced into struct line to reflect their initial order.  I suspect the
latter alternative will be cheaper in terms of resources (i.e., less memory and
faster sort time).

This also means that the aspect of the bug isn't powerpc specific.  It only
happens to manifest in the testsuite runs on that target.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ian at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
As for the -fasynchronous-unwind-tables option, this really should be handled
by teaching libsanitizer to handle powerpc* fast unwinding.
For the backtrace_qsort, can you cook up some short testcase that calls
backtrace_qsort and sorts things incorrectly?

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #5 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 35289
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35289&action=edit
Test case demonstrating stability problem with backtrace_qsort.

Attached is a demo program showing the stability bug in the backtrace_qsort
function.  The output shows the result of the current implementation (Unstable)
and the expected result (Stable).  A better test case wouldn't rely on the
knowledge of the line_compare function and instead arrange to construct a DWARF
line program with similar properties that would then cause the backtrace line
problem.  I suspect that would take quite a bit of effort to put together,
especially if we wanted it to be reproducible across targets.

I plan to work on the fast unwinding but I don't expect it to be ready in time
for the 5.0 release.  In the meantime, I'll post a patch to fix the test
failures and maintain stability to be considered for 5.0.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Martin Sebor from comment #5)
> Created attachment 35289 [details]
> Test case demonstrating stability problem with backtrace_qsort.
> 
> Attached is a demo program showing the stability bug in the backtrace_qsort
> function.  The output shows the result of the current implementation
> (Unstable) and the expected result (Stable).  A better test case wouldn't
> rely on the knowledge of the line_compare function and instead arrange to
> construct a DWARF line program with similar properties that would then cause
> the backtrace line problem.  I suspect that would take quite a bit of effort
> to put together, especially if we wanted it to be reproducible across
> targets.
> 
> I plan to work on the fast unwinding but I don't expect it to be ready in
> time for the 5.0 release.  In the meantime, I'll post a patch to fix the
> test failures and maintain stability to be considered for 5.0.

That hints at a bug in the line_compare function, what it does is just bogus.
Adding the idx field to struct line sounds IMHO like the right thing, and on
64-bit arches won't even eat any extra memory because there have been 32 bits
of padding.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |65749

--- Comment #7 from Martin Sebor <msebor at gcc dot gnu.org> ---
I forgot to mention that there is yet another bug here that's complicating
things.  I was initially going to describe it here but since it's independent
of this problem I decided to open a separate bug: pr65749.

The complication is that a patch for this bug that produces the expected
results on POWER (i.e., passes all sanitizer tests) breaks at least one test on
x86_64 because of the incorrect computation of the PC value in
libsanitizer/sanitizer_common/sanitizer_stacktrace_libcdep.cc.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #8 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 35308
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35308&action=edit
Patch tested on powerp64*-*-*

This patch lets the affected tests pass on powerp64*-*-* but due to bug 65749,
causes regressions in the stack-overflow-1.c test where asan reports different
line numbers in the stack trace than expected.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #35196|0                           |1
        is obsolete|                            |
  Attachment #35308|0                           |1
        is obsolete|                            |

--- Comment #9 from Martin Sebor <msebor at gcc dot gnu.org> ---
Created attachment 35360
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35360&action=edit
Proposed patch.

The attached patch resolves all the Address Sanitizer test suite failures on
powerpc64 except for those that are subject to pr65643.  Tested on
powerpc64*-*-*-* and x86_64.

[Bug sanitizer/65479] sanitizer stack trace missing frames past #0 on powerpc64

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65479

--- Comment #10 from Martin Sebor <msebor at gcc dot gnu.org> ---
Author: msebor
Date: Fri Jun 12 00:01:50 2015
New Revision: 224402

URL: https://gcc.gnu.org/viewcvs?rev=224402&root=gcc&view=rev
Log:
2015-06-11  Martin Sebor  <msebor@redhat.com>

        PR sanitizer/65479
        * dwarf.c (struct line): Add new field idx.
        (line_compare): Use it.
        (add_line): Set it.
        (read_line_info): Reset it.

Modified:
    trunk/libbacktrace/ChangeLog
    trunk/libbacktrace/dwarf.c