[Bug libstdc++/114401] New: libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[Bug libstdc++/114401] New: libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[jblair149 at gmail dot com]

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

            Bug ID: 114401
           Summary: libstdc++ allocator destructor omitted when
                    reinserting node_handle into tree- and hashtable-based
                    containers
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jblair149 at gmail dot com
  Target Milestone: ---

Created attachment 57742
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57742&action=edit
Source code for test program demonstrating the issue with allocator destruction
on node handle insertion.

Summary:
Implementation in the following functions that reinsert nodes into `_Rb_tree`
and `_Hashtable` may set the node handle data pointer to `nullptr`. This
prevents stateful allocators from being properly destructed when extracting and
reinserting nodes.


Functions in stl_tree.h impacted:
`insert_return_type _Rb_tree_impl::_M_reinsert_node_unique(node_type&& __nh)`

`iterator _Rb_tree_impl::_M_reinsert_node_equal(node_type&& __nh)`

`iterator _Rb_tree_impl::_M_reinsert_node_hint_unique(const_iterator __hint,
node_type&& __nh)`

`iterator _Rb_tree_impl::_M_reinsert_node_hint_equal(const_iterator __hint,
node_type&& __nh)`


Functions in hashtable.h impacted:
`insert_return_type _Hashtable::_M_reinsert_node_unique(node_type&& __nh)`

`insert_return_type _Hashtable::_M_reinsert_node_multi(const_iterator __hint,
node_type&& __nh)`


Details:
The allocator of the node is asserted to be equal to the allocator of the
underlying tree or hashtable in each function, but otherwise the allocator is
unused, and on successful insertion `__nh._M_ptr` is set to `nullptr`.
Following that, in the destructor of `_Node_handle_common`, `_M_reset()` is
never called since the node is detected as `empty()`. Further, the union
`_Optional_alloc` defined within `_Node_handle_common` has a no-op destructor,
so only a manual invocation of `_Optional_alloc::release()` can trigger the
destructor of the allocator contained, which may only be invoked if active. As
a result, the allocator instance within the node is never destructed once the
node has been reinserted into the tree or hashtable. This doesn't matter for
stateless allocators, but for stateful ones this can result in a memory leak.

One potential solution is to:
1) Add a new method to `_Node_handle_common` that will be called after a node
is reinserted rather than simply setting `_M_ptr` to `nullptr`. That method
would invoke `_M_alloc.release()` like `_M_reset()` does, and set the pointer
`_M_ptr` to `nullptr`, but omit the actions to destroy the object and
deallocate the memory since the node has been returned to a compatible
container.

2) Within each of the functions mentioned within the files above, replace
`__nh._M_ptr = nullptr;` with an invocation of the function in (1).

I do not know for certain this is the maximal extent of the issue when
reinserting extracted nodes, but I've expanded from my initial issue using
`std::set` to the associative containers I'm aware of which expose
`node_handle`. I also am not familiar with the naming conventions within the
library. To that end, I'm omitting a patch since this may require discussion.


I believe the current master branch of GCC exhibits the issue; I've confirmed
it is present at least as of commit 994d8f922b9d88f45775f57a490409ab1c3baf59.
This issue is likely present in past releases as well, but I don't know how
that should be handled.

Within the repository, the files I know are impacted are:
gcc.git/libstdc++-v3/include/bits/node_handle.h
gcc.git/libstdc++-v3/include/bits/stl_tree.h
gcc.git/libstdc++-v3/include/bits/hashtable.h


I'm attaching a relatively minimal program which demonstrates the issue. The
program uses a logging, stateful allocator within a `std::set`, inserts
elements, extracts a node, modifies the value of the element within the node,
reinserts the node, and triggers the destruction of the set by the end of
scope. Compilation of the program is as follows:

g++ test_node_reinsert.cpp -o test_node_reinsert

The test program may be run without arguments.


The output of this program prior to the fix:

Begin scope for allocator and set.
initial construction
allocate memory pools
allocator copied; active count = 2
allocator copied; active count = 3
allocator copied; active count = 4
allocator destructed; active count = 3
allocator destructed; active count = 2
allocator copied; active count = 3
End scope for allocator and set.
allocator destructed; active count = 2
allocator destructed; active count = 1
Allocator should be completely desctructed.


The output of this program after my (hacky?) fix, following the instructions
above:

Begin scope for allocator and set.
initial construction
allocate memory pools
allocator copied; active count = 2
allocator copied; active count = 3
allocator copied; active count = 4
allocator destructed; active count = 3
allocator destructed; active count = 2
allocator copied; active count = 3
allocator copied; active count = 4
allocator destructed; active count = 3
allocator destructed; active count = 2
End scope for allocator and set.
allocator destructed; active count = 1
allocator destructed; active count = 0
deallocate memory pools
fully destructed
Allocator should be completely desctructed.

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-03-20
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 57748
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57748&action=edit
Untested patch to fix all assoc containers

Thanks for the report and analysis. This should do it.

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5
           Keywords|                            |wrong-code

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
There's another bug in the node move assignment operator, so I'll fix that too.

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

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

commit r14-9636-gc2e28df90a1640cebadef6c6c8ab5ea964071bb1
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Mar 21 13:25:15 2024 +0000

    libstdc++: Destroy allocators in re-inserted container nodes [PR114401]

    The allocator objects in container node handles were not being destroyed
    after the node was re-inserted into a container. They are stored in a
    union and so need to be explicitly destroyed when the node becomes
    empty. The containers were zeroing the node handle's pointer, which
    makes it empty, causing the handle's destructor to think there's nothign
    to clean up.

    Add a new member function to the node handle which destroys the
    allocator and zeros the pointer. Change the containers to call that
    instead of just changing the pointer manually.

    We can also remove the _M_empty member of the union which is not
    necessary.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114401
            * include/bits/hashtable.h (_Hashtable::_M_reinsert_node): Call
            release() on node handle instead of just zeroing its pointer.
            (_Hashtable::_M_reinsert_node_multi): Likewise.
            (_Hashtable::_M_merge_unique): Likewise.
            (_Hashtable::_M_merge_multi): Likewise.
            * include/bits/node_handle.h (_Node_handle_common::release()):
            New member function.
            (_Node_handle_common::_Optional_alloc::_M_empty): Remove
            unnecessary union member.
            (_Node_handle_common): Declare _Hashtable as a friend.
            * include/bits/stl_tree.h (_Rb_tree::_M_reinsert_node_unique):
            Call release() on node handle instead of just zeroing its
            pointer.
            (_Rb_tree::_M_reinsert_node_equal): Likewise.
            (_Rb_tree::_M_reinsert_node_hint_unique): Likewise.
            (_Rb_tree::_M_reinsert_node_hint_equal): Likewise.
            * testsuite/23_containers/multiset/modifiers/114401.cc: New test.
            * testsuite/23_containers/set/modifiers/114401.cc: New test.
            * testsuite/23_containers/unordered_multiset/modifiers/114401.cc:
New test.
            * testsuite/23_containers/unordered_set/modifiers/114401.cc: New
test.

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #2)
> There's another bug in the node move assignment operator, so I'll fix that
> too.

Turns out there wasn't, just the one you reported originally. It's fixed on
trunk, but I'll backport it to the release branches.

[Bug libstdc++/114401] libstdc++ allocator destructor omitted when reinserting node_handle into tree- and hashtable-based containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:47ebdbe5bf71d9eb260359b6aceb5cb071d97acd

commit r13-8570-g47ebdbe5bf71d9eb260359b6aceb5cb071d97acd
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Mar 21 13:25:15 2024 +0000

    libstdc++: Destroy allocators in re-inserted container nodes [PR114401]

    The allocator objects in container node handles were not being destroyed
    after the node was re-inserted into a container. They are stored in a
    union and so need to be explicitly destroyed when the node becomes
    empty. The containers were zeroing the node handle's pointer, which
    makes it empty, causing the handle's destructor to think there's nothing
    to clean up.

    Add a new member function to the node handle which destroys the
    allocator and zeros the pointer. Change the containers to call that
    instead of just changing the pointer manually.

    We can also remove the _M_empty member of the union which is not
    necessary.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114401
            * include/bits/hashtable.h (_Hashtable::_M_reinsert_node): Call
            release() on node handle instead of just zeroing its pointer.
            (_Hashtable::_M_reinsert_node_multi): Likewise.
            (_Hashtable::_M_merge_unique): Likewise.
            (_Hashtable::_M_merge_multi): Likewise.
            * include/bits/node_handle.h (_Node_handle_common::release()):
            New member function.
            (_Node_handle_common::_Optional_alloc::_M_empty): Remove
            unnecessary union member.
            (_Node_handle_common): Declare _Hashtable as a friend.
            * include/bits/stl_tree.h (_Rb_tree::_M_reinsert_node_unique):
            Call release() on node handle instead of just zeroing its
            pointer.
            (_Rb_tree::_M_reinsert_node_equal): Likewise.
            (_Rb_tree::_M_reinsert_node_hint_unique): Likewise.
            (_Rb_tree::_M_reinsert_node_hint_equal): Likewise.
            * testsuite/23_containers/multiset/modifiers/114401.cc: New test.
            * testsuite/23_containers/set/modifiers/114401.cc: New test.
            * testsuite/23_containers/unordered_multiset/modifiers/114401.cc:
New test.
            * testsuite/23_containers/unordered_set/modifiers/114401.cc: New
test.

    (cherry picked from commit c2e28df90a1640cebadef6c6c8ab5ea964071bb1)