[Bug libgcc/111731] New: [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[Bug libgcc/111731] New: [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[crazylht at gmail dot com]

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

            Bug ID: 111731
           Summary: [13/14 regression] gcc_assert is hit at
                    libgcc/unwind-dw2-fde.c#L291
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libgcc
          Assignee: unassigned at gcc dot gnu.org
          Reporter: crazylht at gmail dot com
  Target Milestone: ---

The issue is not solved by PR110956'fix.

I did some debugging with gdb, and here are the logs:

The first time gdb stop at
https://github.com/gcc-mirror/gcc/blob/master/libgcc/unwind-dw2-fde.c#L143

│   138           ob->next = unseen_objects;                                    
│   139           unseen_objects = ob;                                          
│   140                                                                         
│   141           __gthread_mutex_unlock (&object_mutex);                       
│   142         #endif                                                          
│  >143         }            

(gdb) frame
#0  __register_frame_info_bases (begin=0x7fffd551e000, ob=0x1e386d0, tbase=0x0,
dbase=0x0) at ../../../libgcc/unwind-dw2-fde.c:143
(gdb) p registered_frames->root->entry_count
$31 = 2
(gdb) p registered_frames->root->content.entries[0]
$32 = {base = 140736772300800, size = 1, ob = 0x1e386d0}
(gdb) p registered_frames->root->content.entries[1]
$33 = {base = 140736772317184, size = 178483158, ob = 0x1e386d0}

The second time gdb stop at
https://github.com/gcc-mirror/gcc/blob/master/libgcc/unwind-dw2-fde.c#L143

│   138           ob->next = unseen_objects;                                    
│   139           unseen_objects = ob;                                          
│   140                                                                         
│   141           __gthread_mutex_unlock (&object_mutex);                       
│   142         #endif                                                          
│  >143         }    

(gdb) frame
#0  __register_frame_info_bases (begin=0x7fffd409c000, ob=0x26b2e00, tbase=0x0,
dbase=0x0) at ../../../libgcc/unwind-dw2-fde.c:143
(gdb) p registered_frames->root->entry_count
$34 = 4
(gdb) p registered_frames->root->content.entries[0]
$35 = {base = 140736750796800, size = 1, ob = 0x26b2e00}
(gdb) p registered_frames->root->content.entries[1]
$36 = {base = 140736750817280, size = 199987168, ob = 0x26b2e00}
(gdb) p registered_frames->root->content.entries[2]
$37 = {base = 140736772300800, size = 1, ob = 0x1e386d0}
(gdb) p registered_frames->root->content.entries[3]
$38 = {base = 140736772317184, size = 178483158, ob = 0x1e386d0}

The first time gdb stop at unexpected line
https://github.com/gcc-mirror/gcc/blob/master/libgcc/unwind-dw2-btree.h#L829:

│   825           unsigned slot = btree_node_find_leaf_slot (iter, base);       
│   826           if ((slot >= iter->entry_count) ||
(iter->content.entries[slot].base != base))                                     
│   827             {                                                           
│   828               // Not found, this should never happen.                   
│  >829               btree_node_unlock_exclusive (iter);                       
│   830               return NULL;                                              
│   831             } 

(gdb) p slot
$26 = 1
(gdb) p iter->content.entries[slot]
$27 = {base = 140736750817280, size = 199987168, ob = 0x26e7900}
(gdb) p iter->content.entries[2]
$28 = {base = 140736772300800, size = 1, ob = 0x1e386d0}
We can see that when we try to remove btree node of
0x7fffd551e000(140736772300800).

 The return value of btree_node_find_leaf_slot is 1, but I think it should
return 2. 


Both btree_insert and btree_remove will call

// Find the position for a slot in a leaf node.
static unsigned
btree_node_find_leaf_slot (const struct btree_node *n, uintptr_type value)
{
  for (unsigned index = 0, ec = n->entry_count; index != ec; ++index)
   if (n->content.entries[index].base + n->content.entries[index].size > value) 
     return index;
  return n->entry_count;
} 


But

registered_frames->root->content.entries[1].base +
registered_frames->root->content.entries[1].size >
registered_frames->root->content.entries[2].base

registered_frames->root->content.entries[2].base +
registered_frames->root->content.entries[2].size >
registered_frames->root->content.entries[1].base 

and it makes btree_node_find_leaf_slot return wrong slot(at btree_insert, it
will return slot 1 for base1, and move base2 to slot2, but at btree_remove, it
still return slot 1 bacause of upper logic), I'm not sure if this is the
rootcause.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[crazylht at gmail dot com]

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

--- Comment #1 from Hongtao.liu <crazylht at gmail dot com> ---
GCC11.3 is ok, GCC13.2 and later have the issue, I didn't verify GCC12.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[crazylht at gmail dot com]

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

--- Comment #2 from Hongtao.liu <crazylht at gmail dot com> ---
The original project is too complex for me to come up with a reproduction case,
I can help with gdb if additional information is needed.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.3
                 CC|                            |tneumann at users dot sourceforge.
                   |                            |net
           Keywords|                            |wrong-code

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

Dimitar Yordanov <dimitar.yordanov at sap dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dimitar.yordanov at sap dot com

--- Comment #3 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
Hi,

what I can further add as a detail to the code below is that in the error case
"begin" is after "range[0]" as calculated by get_pc_range

-----------------
void
__register_frame_info_bases (const void *begin, struct object *ob,
                             void *tbase, void *dbase)
{
 .....

  // Register the object itself to know the base pointer on deregistration.
  btree_insert (&registered_frames, (uintptr_type) begin, 1, ob);

  // Register the frame in the b-tree
  uintptr_type range[2];
  get_pc_range (ob, range);
  btree_insert (&registered_frames, range[0], range[1] - range[0], ob);
-----------------

and pc_begin comes from the following with "((encoding & 0x70) ==
DW_EH_PE_pcrel" being true

-----------------
static const unsigned char *
read_encoded_value_with_base (unsigned char encoding, _Unwind_Ptr base,
                              const unsigned char *p, _Unwind_Ptr *val)
{
....
        case DW_EH_PE_sdata8:
          result = u->s8;
          p += 8;
....
        result += ((encoding & 0x70) == DW_EH_PE_pcrel
                     ? (_Unwind_Internal_Ptr) u : base);

-----------------
E.g. u->s8 has a value of 0xffffffffffffe6f8 u 0x7fa7fc22f908 and with that
result 0x7fa7fc22e000 which is lower as the begin 0x7fa7fc22f160

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

--- Comment #4 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
It looks like the code does not find an unwind frame when de-registering an
exception handler. Are you sure that you do not de-register a dynamic frame
twice?

Otherwise I would need a way to reproduce the problem, ideally with a binary. I
am also fine with remote access if that is easier for you. Or if that is not
possible you might want to add printf calls to btree_insert and btree_remove,
tracing their call arguments. Having such a tracer should allow us to reproduce
the problem even without the host program.

(And it would allow for detecting duplicate de-registrations, i.e., errors in
the host program. I had that problem in the past myself with JITed code).

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #5 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
> It looks like the code does not find an unwind frame when de-registering an exception handler

From what I understand so far the issue is already there when doing the
registration. There is twice a call to btree_insert:

btree_insert (&registered_frames, (uintptr_type) begin, 1, ob);
btree_insert (&registered_frames, range[0], range[1] - range[0], ob);

for those, calls when "range[0]" is before "begin" with the same "ob" the next
search for removing will return the slot where range[0] is not the one of
begin. Because of the way "btree_node_find_leaf_slot" works, doing a 

if (n->content.entries[index].base + n->content.entries[index].size > value)

which is true for the second insert call even if we want to find the slot for
the first insert.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #6 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
Before the fix for PR 110956 there was just one btree_insert call for the same
"ob"

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

--- Comment #7 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
Is it correct that in your case range[0]<begin<range[1]? That is, the unwind
table is within the code? That might cause problems.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #8 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
yes

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

--- Comment #9 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
I will check how we can handle such a situation. But how did this happen to
begin with? Is this regular code or did you do anything special? I am puzzled
how the unwinding table can be placed like that.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #10 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
Valid question. Seeing others hitting the same issue and looking at the
backtrace I would think it is not directly in our code but comes with the usage
LLVMs LLJIT

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

--- Comment #11 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
Created attachment 57669
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57669&action=edit
patch to handle overlapping ranges

Does this patch fix the problem for you? I think it should, but I would really
like to have a reproducer to make sure.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #12 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
> Does this patch fix the problem for you?
yes. The failing testcase is successful after the change. I'll schedule more
tests.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Thomas Neumann from comment #11)
> Created attachment 57669 [details]
> patch to handle overlapping ranges
> 
> Does this patch fix the problem for you? I think it should, but I would
> really like to have a reproducer to make sure.

Note, the formatting is wrong, single statements shouldn't be wrapped in
between { and } in if/else/while/do/for etc. subblocks.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

Thomas Neumann <tneumann at users dot sourceforge.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #57669|0                           |1
        is obsolete|                            |

--- Comment #14 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
Created attachment 57675
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57675&action=edit
updated patch

updated patch without single line blocks

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

Thomas Neumann <tneumann at users dot sourceforge.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #57675|0                           |1
        is obsolete|                            |

--- Comment #15 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
Created attachment 57679
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57679&action=edit
fixed patch

Can you please try the updated patch? I had accidentally dropped an if nesting
level when trying to adhere to the gcc style, sorry for that.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[liuhongt at gcc dot gnu.org]

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

Hongtao Liu <liuhongt at gcc dot gnu.org> changed:

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

--- Comment #16 from Hongtao Liu <liuhongt at gcc dot gnu.org> ---
(In reply to Thomas Neumann from comment #15)
> Created attachment 57679 [details]
> fixed patch
> 
> Can you please try the updated patch? I had accidentally dropped an if
> nesting level when trying to adhere to the gcc style, sorry for that.

I'm trying to validating your patch, but it could take sometime to setup
enviroments.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #17 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
I've executed more tests and see another one failing. This time "begin" is
inside of another range, not the one that gets calculated with this "begin". So
there is again an overlapping in the btree. Could we maybe use two trees, one
for "begin" and one for the ranges?

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[tneumann at users dot sourceforge.net]

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

Thomas Neumann <tneumann at users dot sourceforge.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #57679|0                           |1
        is obsolete|                            |

--- Comment #18 from Thomas Neumann <tneumann at users dot sourceforge.net> ---
Created attachment 57692
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57692&action=edit
patch with separate btrees

We will have to do that, I have updated the patch to use a separate lookup
structure for the tables.

Which prevents the original problem and hopefully fixes the issue. The only
thing that makes me nervous is that if some JITer comes up with the idea of
placing an unwind tuple inside some code range, what prevents them from placing
code from one table within code from another table? Which would break the
assumption that code ranges do not overlap.

Note that the non-fast-path code also makes the assumption that code ranges do
not overlap, see the comment in _Unwind_Find_FDE. Thus perhaps no JIT code
emitter will do that. But if somebody does we should probably store the fde
instead of the object inside the lookup structure. The fde ranges really must
not overlap, otherwise everything breaks. But I would like to not do that
because we have more fdes than objects and storing each fde individually would
make frame registration more expensive (even though lookup became faster,
because we would no longer have to traverse the object).

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[dimitar.yordanov at sap dot com]

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

--- Comment #19 from Dimitar Yordanov <dimitar.yordanov at sap dot com> ---
I've rerun related tests and they look OK with the latest patch.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[cvs-commit at gcc dot gnu.org]

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

--- Comment #20 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Thomas Neumann <tneumann@gcc.gnu.org>:

https://gcc.gnu.org/g:a364148530c28645ce87adbc58a66c9f32a325ab

commit r14-9620-ga364148530c28645ce87adbc58a66c9f32a325ab
Author: Thomas Neumann <tneumann@users.sourceforge.net>
Date:   Mon Mar 11 14:35:20 2024 +0100

    handle unwind tables that are embedded within unwinding code [PR111731]

    Original bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111731

    The unwinding mechanism registers both the code range and the unwind
    table itself within a b-tree lookup structure. That data structure
    assumes that is consists of non-overlappping intervals. This
    becomes a problem if the unwinding table is embedded within the
    code itself, as now the intervals do overlap.

    To fix this problem we now keep the unwind tables in a separate
    b-tree, which prevents the overlap.

    libgcc/ChangeLog:
            PR libgcc/111731
            * unwind-dw2-fde.c: Split unwind ranges if they contain the
            unwind table.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[cvs-commit at gcc dot gnu.org]

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

--- Comment #21 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Thomas Neumann
<tneumann@gcc.gnu.org>:

https://gcc.gnu.org/g:11f37868bb5812c4f0ac023909f5421595f68a43

commit r13-8555-g11f37868bb5812c4f0ac023909f5421595f68a43
Author: Thomas Neumann <tneumann@users.sourceforge.net>
Date:   Mon Mar 11 14:35:20 2024 +0100

    handle unwind tables that are embedded within unwinding code [PR111731]

    Original bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111731

    The unwinding mechanism registers both the code range and the unwind
    table itself within a b-tree lookup structure. That data structure
    assumes that is consists of non-overlappping intervals. This
    becomes a problem if the unwinding table is embedded within the
    code itself, as now the intervals do overlap.

    To fix this problem we now keep the unwind tables in a separate
    b-tree, which prevents the overlap.

    libgcc/ChangeLog:
            PR libgcc/111731
            * unwind-dw2-fde.c: Split unwind ranges if they contain the
            unwind table.

[Bug libgcc/111731] [13/14 regression] gcc_assert is hit at libgcc/unwind-dw2-fde.c#L291

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |13.2.1
      Known to fail|                            |13.2.0
         Resolution|---                         |FIXED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #22 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.