Bug 63698 - [5 Regression] std::set leaks nodes on assignment
Summary: [5 Regression] std::set leaks nodes on assignment
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 5.0
: P3 major
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-10-31 09:14 UTC by Alexandre Duret-Lutz
Modified: 2014-11-05 19:17 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.8.2, 4.9.2
Known to fail: 5.0
Last reconfirmed: 2014-10-31 00:00:00


Attachments
try to fix leak (817 bytes, patch)
2014-10-31 11:45 UTC, Jonathan Wakely
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Alexandre Duret-Lutz 2014-10-31 09:14:00 UTC
Compiling a project of mine with the latest gcc-snapshot distributed by Debian (g++ (Debian 20141016-1) 5.0.0 20141016 (experimental) [trunk revision 216349]), I started to get memory leaks.

I reduced the problem to this small scenario:

% cat foo.cc
#include <set>

int main()
{
  std::set<int> v{2,1};   // The order of 2 and 1 is important.
  std::set<int> w{6,5,4};
  v = w;
  return v.size();
}
% g++ -std=c++11 foo.cc -g -Wall
% valgrind --leak-check=yes -q ./a.out
==30757== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==30757==    at 0x4C29180: operator new(unsigned long) (vg_replace_malloc.c:324)
==30757==    by 0x40277D: __gnu_cxx::new_allocator<std::_Rb_tree_node<int> >::allocate(unsigned long, void const*) (new_allocator.h:104)
==30757==    by 0x4026F8: std::allocator_traits<std::allocator<std::_Rb_tree_node<int> > >::allocate(std::allocator<std::_Rb_tree_node<int> >&, unsigned long) (alloc_traits.h:360)
==30757==    by 0x402668: std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_get_node() (stl_tree.h:485)
==30757==    by 0x40238D: std::_Rb_tree_node<int>* std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_create_node<int const&>(int const&) (stl_tree.h:539)
==30757==    by 0x4021BE: std::_Rb_tree_node<int>* std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Alloc_node::operator()<int const&>(int const&) const (stl_tree.h:453)
==30757==    by 0x401D82: std::_Rb_tree_iterator<int> std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_insert_<int const&, std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Alloc_node>(std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, int const&, std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Alloc_node&) (stl_tree.h:1381)
==30757==    by 0x401324: std::_Rb_tree_iterator<int> std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_insert_unique_<int const&, std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Alloc_node>(std::_Rb_tree_const_iterator<int>, int const&, std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Alloc_node&) (stl_tree.h:1850)
==30757==    by 0x400EF3: void std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_insert_unique<int const*>(int const*, int const*) (stl_tree.h:2096)
==30757==    by 0x400D0B: std::set<int, std::less<int>, std::allocator<int> >::set(std::initializer_list<int>, std::less<int> const&, std::allocator<int> const&) (stl_set.h:225)
==30757==    by 0x400A6A: main (foo.cc:5)


I suspect this is related to what was implemented for
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=29988
Comment 1 Jonathan Wakely 2014-10-31 09:37:06 UTC
(In reply to Alexandre Duret-Lutz from comment #0)
> I suspect this is related to what was implemented for
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=29988

Probably that, thanks for the minimal testcase.
Comment 2 Jonathan Wakely 2014-10-31 11:15:55 UTC
Francois, the bug is in _Reuse_or_alloc_node::_M_extract which returns a node that has a child. When we reuse the node the child is lost.

The LHS of the assignment looks like this:

(gdb) p this->_M_impl._M_header
$1 = {_M_color = std::_S_red, _M_parent = 0x605010, _M_left = 0x605040, _M_right = 0x605010}
(gdb) p *$1._M_left
$2 = {_M_color = std::_S_red, _M_parent = 0x605010, _M_left = 0x0, _M_right = 0x0}
(gdb) p *$1._M_right
$3 = {_M_color = std::_S_black, _M_parent = 0x7fffffffd668, _M_left = 0x605040, _M_right = 0x0}

When that gets handed to the _Reuse_or_alloc_node this->_M_impl._M_header._M_right->_M_parent gets set to null, so when _M_extract returns 0x605010 it thinks it has no more nodes to reuse.
Comment 3 Jonathan Wakely 2014-10-31 11:45:34 UTC
Created attachment 33853 [details]
try to fix leak

The rightmost node is not necessarily a leaf, so set _M_nodes to _M_rightmost()->_M_left if that exists.

Also simplify the constructor as it only needs one argument.
Comment 4 Jonathan Wakely 2014-10-31 12:44:01 UTC
Does the same problem still exist in _M_extract?

This loop moves _M_nodes to the rightmost node again:

		      while (_M_nodes->_M_right)
			_M_nodes = _M_nodes->_M_right;

Can that node have an _M_left child?
Comment 5 Jonathan Wakely 2014-10-31 13:37:19 UTC
Yes, it looks like we also need:

--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -423,6 +423,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
                      while (_M_nodes->_M_right)
                        _M_nodes = _M_nodes->_M_right;
+                     if (_M_nodes->_M_left)
+                       _M_nodes = _M_nodes->_M_left;
                    }
                }
              else // __node is on the left.
Comment 6 Jonathan Wakely 2014-10-31 13:40:52 UTC
This still leaks like a sieve without the second patch:

#include <set>
#include <random>

int main()
{
  std::mt19937 rng;
  std::uniform_int_distribution<int> d;
  std::uniform_int_distribution<int>::param_type p{0, 100};
  std::uniform_int_distribution<int>::param_type x{0, 1000};
  
  for (int i = 0; i < 10; ++i)
  {
    std::set<int> l, r;
    for (int n = d(rng, p); n > 0; --n)
    {
      int i = d(rng, x);
      l.insert(i);
      r.insert(i);
      l = r;
    }
  }
}
Comment 7 François Dumont 2014-11-03 23:04:03 UTC
Yes, looks like I had forgotten node with only a left child, too bad. My initial plan was to use existing tree node algos in tree.cc but erase could not be done without rebalancing which was useless for what we are doing in this case.

So, do you take care of applying this or do you want me to submit a complete patch on libstdc++ with your test ?
Comment 8 François Dumont 2014-11-05 19:16:44 UTC
Author: fdumont
Date: Wed Nov  5 19:16:13 2014
New Revision: 217154

URL: https://gcc.gnu.org/viewcvs?rev=217154&root=gcc&view=rev
Log:
2014-11-04  François Dumont  <fdumont@gcc.gnu.org>
	    Jonathan Wakely  <jwakely@redhat.com>

	PR libstdc++/63698
	* include/bits/stl_tree.h (_Reuse_or_alloc_node): Simplify constructor.
	Always move to the left node if there is one.
	* testsuite/23_containers/set/allocator/move_assign.cc (test04): New.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_tree.h
    trunk/libstdc++-v3/testsuite/23_containers/set/allocator/move_assign.cc
Comment 9 François Dumont 2014-11-05 19:17:54 UTC
Now fixed on trunk