[PATCH] libstdc++: Fix debug mode for pb_ds ordered-vector trees [PR127675]
Tomasz Kaminski
tkaminsk@redhat.com
Fri Oct 2 14:39:19 GMT 2026
On Thu, Oct 1, 2026 at 3:31 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> As noted in the bugzilla PR, there are debug mode assertions in the
> ov_tree_map and ov_tree_set code which fail occasionally (but not
> consistently because the tests use the current time as a random seed).
>
> This change first allows the time-based random seed to be overridden
> using the same GLIBCXX_SEED_TEST_RNG environment variable already
> checked elsewhere in the testsuite. This allows failures to be triggered
> reliably.
>
> The bug in erase_if is an exception-safety bug where most state is
> rolled back cleanly if an exception occurs, but some modifications to
> the debug_base::m_keys list are not rolled back. This leaves the
> container in an inconsistent state where the values in m_keys do not
> match the contents of the container. This triggers debug assertions on
> the next operation when the container checks its invariants.
>
> The bug in erase(It) is much simpler and easier to trigger: the function
> calls alloc.allocate(m_size - 1) unconditionally, even if m_size == 1.
> It is unspecified what allocators return for zero-sized allocations, so
> this can return a non-null pointer. That is then inconsistent with the
> debug assertions which require m_a_values == nullptr to be true when
> m_size == 0. The solution here is to simply avoid allocating anything
> when m_size == 1.
>
> Finally, the split and join members of the debug_base are refactored to
> use std::list::splice instead of inserting and erasing elements from the
> two lists. This means they perform no allocations and no copies, so
> cannot throw exceptions (unless the comparison function passed to split
> throws). Although this doesn't fix any known bugs, it makes the callers
> of those functions more robust and makes it easier to ensure those
> callers are exception-safe.
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/127675
> * include/ext/pb_ds/detail/debug_map_base.hpp (split, join): Use
> std::list::splice to move elements without reallocating.
> *
> include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
> (copy_from_ordered_range(It, It, It, It)): Do not allocate new
> storage for an empty container.
> * include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
> (erase_if): Do not modify this->debug_base::m_keys until all
> allocations and other potentially-throwing operations have
> completed successfully.
> (erase_imp): Do not allocate new storage for an empty container.
> * testsuite/ext/pb_ds/regression/127675.cc: New test.
> * testsuite/util/testsuite_rng.h (get_time_determined_seed): Use
> getenv("GLIBCXX_SEED_TEST_RNG") to allow the seed to be fixed.
> ---
>
> Tested x86_64-linux.
>
LGTM, with one suggestion for commit description below:
>
> .../ext/pb_ds/detail/debug_map_base.hpp | 19 +++----
> .../constructors_destructor_fn_imps.hpp | 2 +
> .../detail/ov_tree_map_/erase_fn_imps.hpp | 13 +++--
> .../testsuite/ext/pb_ds/regression/127675.cc | 53 +++++++++++++++++++
> libstdc++-v3/testsuite/util/testsuite_rng.h | 7 ++-
> 5 files changed, 77 insertions(+), 17 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/ext/pb_ds/regression/127675.cc
>
> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp
> b/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp
> index 67bdc3c942f0..8083f1617316 100644
> --- a/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp
> +++ b/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp
> @@ -312,10 +312,7 @@ namespace __gnu_pbds
> iterator it = m_keys.begin();
> while (it != m_keys.end())
> if (cmp_fn(r_key, *it))
> - {
> - other.insert_new(*it);
> - it = m_keys.erase(it);
> - }
> + other.m_keys.splice(other.m_keys.end(), m_keys, it++);
> else
> ++it;
> }
> @@ -325,16 +322,12 @@ namespace __gnu_pbds
> PB_DS_CLASS_C_DEC::
> join(PB_DS_CLASS_C_DEC& other, bool with_cleanup)
> {
> - iterator it = other.m_keys.begin();
> - while (it != other.m_keys.end())
> - {
> + if (with_cleanup)
> + m_keys.splice(m_keys.end(), other.m_keys);
> + else
> + for (iterator it = other.m_keys.begin(), e = other.m_keys.end();
> + it != e; ++it)
> insert_new(*it);
> - if (with_cleanup)
> - it = other.m_keys.erase(it);
> - else
> - ++it;
> - }
> - _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty());
> }
>
> #undef PB_DS_CLASS_T_DEC
> diff --git
> a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
> b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
> index 713d25640487..dffc2f275ee4 100644
> ---
> a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
> +++
> b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
> @@ -162,6 +162,8 @@ copy_from_ordered_range(It first_it, It last_it, It
> other_first_it,
> clear();
> const size_type len = std::distance(first_it, last_it)
> + std::distance(other_first_it, other_last_it);
> + if (len == 0)
> + return;
>
This function is only called in join from split_join_from_impls.h, after
checking that both rangs
are not empty and it's private, so that change does not seem strictly
necessary.
I am not opposed adding this check, but mention that in commit description.
>
> value_vector a_values = s_value_alloc.allocate(len);
>
> diff --git
> a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
> b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
> index 62a1f3de8c2a..930d4a3199e3 100644
> --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
> +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp
> @@ -93,7 +93,11 @@ erase_if(Pred pred)
> value_vector a_new_values = s_value_alloc.allocate(new_size);
> iterator target_it = a_new_values;
> cond_dtor<size_type> cd(a_new_values, target_it, new_size);
> - _GLIBCXX_DEBUG_ONLY(debug_base::clear());
> + _GLIBCXX_DEBUG_ONLY(
> + struct dbase : debug_base {
> + using debug_base::swap;
> + using debug_base::insert_new;
> + } d);
> for (iterator source_it = begin(); source_it != m_end_it; ++source_it)
> {
> if (!pred(*source_it))
> @@ -101,12 +105,13 @@ erase_if(Pred pred)
> new (const_cast<void*>(static_cast<const void*>(target_it)))
> value_type(*source_it);
>
> -
> _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it)));
> + _GLIBCXX_DEBUG_ONLY(d.insert_new(PB_DS_V2F(*source_it)));
> ++target_it;
> }
> }
>
> reallocate_metadata((node_update*)this, new_size);
> + _GLIBCXX_DEBUG_ONLY(d.swap(*this));
> cd.set_no_action();
>
> {
> @@ -138,7 +143,9 @@ erase_imp(It it)
> #endif
>
> _GLIBCXX_DEBUG_ASSERT(m_size > 0);
> - value_vector a_values = s_value_alloc.allocate(m_size - 1);
> + value_vector a_values = 0;
> + if (m_size > 1)
> + a_values = s_value_alloc.allocate(m_size - 1);
> iterator source_it = begin();
> iterator source_end_it = end();
> iterator target_it = a_values;
> diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/127675.cc
> b/libstdc++-v3/testsuite/ext/pb_ds/regression/127675.cc
> new file mode 100644
> index 000000000000..594abf4e937b
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/127675.cc
> @@ -0,0 +1,53 @@
> +// { dg-options "-D_GLIBCXX_DEBUG" }
> +// { dg-do run }
> +
> +#include <ext/pb_ds/assoc_container.hpp>
> +#include <ext/throw_allocator.h>
> +
> +static bool is_odd(int i) { return i & 1; }
> +
> +template<class T, class U, class, class>
> +struct Node_update
> +{
> + typedef int metadata_type;
> + void operator()(U, T) const { }
> +};
> +
> +static void
> +test_erase_if_exception_safety()
> +{
> + using namespace __gnu_pbds;
> + typedef __gnu_cxx::throw_allocator_limit<int> Alloc;
> + typedef tree<int, null_type, std::less<int>, ov_tree_tag, Node_update,
> Alloc> Set;
> +
> + for (int i = 0; i < 100; ++i)
> + {
> + Set s;
> + s.insert(0);
> + s.insert(1);
> + s.insert(2);
> + Alloc::limit_adjustor ladj(i);
> + try
> + {
> + s.erase_if(is_odd); // throwing allocator triggered debug assertion
> + }
> + catch (const __gnu_cxx::forced_error&)
> + {
> + }
> + }
> +}
> +
> +static void
> +test_erase_last_element()
> +{
> + using namespace __gnu_pbds;
> + tree<int, int, std::less<int>, ov_tree_tag> m;
> + m[1] = 1;
> + m.erase(m.begin()); // erasing last element triggered debug assertion
> +}
> +
> +int main()
> +{
> + test_erase_if_exception_safety();
> + test_erase_last_element();
> +}
> diff --git a/libstdc++-v3/testsuite/util/testsuite_rng.h
> b/libstdc++-v3/testsuite/util/testsuite_rng.h
> index 69c0ea8cd5a9..261874be991d 100644
> --- a/libstdc++-v3/testsuite/util/testsuite_rng.h
> +++ b/libstdc++-v3/testsuite/util/testsuite_rng.h
> @@ -38,6 +38,7 @@
>
> #include <ctime>
> #include <climits>
> +#include <cstdlib>
> #include <debug/debug.h>
> #include <tr1/random>
>
> @@ -61,7 +62,11 @@ namespace __gnu_pbds
>
> static unsigned int
> get_time_determined_seed()
> - { return(static_cast<unsigned int>(std::time(0))); }
> + {
> + if (const char* v = std::getenv("GLIBCXX_SEED_TEST_RNG"))
> + return std::strtoul(v, 0, 10);
> + return(static_cast<unsigned int>(std::time(0)));
> + }
>
> unsigned long
> get_unsigned_long(unsigned long min = 0,
> --
> 2.55.0
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20261002/5d3474b4/attachment.htm>
More information about the Libstdc++
mailing list