Patchwork [v3] Fix memory leak in forward_list

login
register
mail settings
Submitter Jonathan Wakely
Date Oct. 31, 2012, 1:11 a.m.
Message ID <CAH6eHdRN1N3gwDcwnKZAUODMg3ngxHBxwKFEc7Z98uN8K4aazA@mail.gmail.com>
Download mbox | patch
Permalink /patch/195680/
State New
Headers show

Comments

Jonathan Wakely - Oct. 31, 2012, 1:11 a.m.
This fixes a memory leak in the allocator-extended move constructor I
added to _Fwd_list_base two weeks ago. When the supplied allocator is
not equal to the one in the rvalue parameter the rvalue's head pointer
was zeroed out, without freeing the nodes it pointed to.  This new
version leaves the rvalue list intact, which is faster than clearing
it and would allow its nodes to be reused by forward_list::assign ...
if we didn't always call clear() before assigning anything (that's
something to fix another day.)

        * include/bits/forward_list.h (forward_list): Adjust comments.
        (forward_list(const forward_list&, const _Alloc&)): Use
        _M_range_initialize to copy elements.
        (forward_list(forward_list&&, const _Alloc&)): Add exception
        specification.
        (_Fwd_list_base(const _Fwd_list_base&, const _Node_alloc_type&)):
        Remove.
        * include/bits/forward_list.tcc (_Fwd_list_base(const _Fwd_list_base&,
        const _Node_alloc_type&)): Remove.
        (_Fwd_list_base(_Fwd_list_base&&, const _Node_alloc_type&)): Fix
        memory leak when allocators are not equal.

Tested x86_64-linux, committed to trunk.
commit e4e5b11cf5f7ed7c8afe0fa4a5aedcb4102acb37
Author: Jonathan Wakely <jwakely.gcc@gmail.com>
Date:   Tue Oct 30 23:29:33 2012 +0000

    	* include/bits/forward_list.h (forward_list): Adjust comments.
    	(forward_list(const forward_list&, const _Alloc&)): Use
    	_M_range_initialize to copy elements.
    	(forward_list(forward_list&&, const _Alloc&)): Add exception
    	specification.
    	(_Fwd_list_base(const _Fwd_list_base&, const _Node_alloc_type&)):
    	Remove.
    	* include/bits/forward_list.tcc (_Fwd_list_base(const _Fwd_list_base&,
    	const _Node_alloc_type&)): Remove.
    	(_Fwd_list_base(_Fwd_list_base&&, const _Node_alloc_type&)): Fix
    	memory leak when allocators are not equal.

Patch

diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h
index a5c9f43..8d4915d 100644
--- a/libstdc++-v3/include/bits/forward_list.h
+++ b/libstdc++-v3/include/bits/forward_list.h
@@ -314,8 +314,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _Fwd_list_base(const _Node_alloc_type& __a)
       : _M_impl(__a) { }
 
-      _Fwd_list_base(const _Fwd_list_base& __lst, const _Node_alloc_type& __a);
-
       _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a);
 
       _Fwd_list_base(_Fwd_list_base&& __lst)
@@ -394,14 +392,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    *  Also unlike the other standard containers, std::forward_list provides
    *  specialized algorithms %unique to linked lists, such as
    *  splicing, sorting, and in-place reversal.
-   *
-   *  A couple points on memory allocation for forward_list<Tp>:
-   *
-   *  First, we never actually allocate a Tp, we allocate
-   *  Fwd_list_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
-   *  that after elements from %forward_list<X,Alloc1> are spliced into
-   *  %forward_list<X,Alloc2>, destroying the memory of the second %list is a
-   *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
    */
   template<typename _Tp, typename _Alloc = allocator<_Tp> >
     class forward_list : private _Fwd_list_base<_Tp, _Alloc>
@@ -429,7 +419,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       typedef std::ptrdiff_t                               difference_type;
       typedef _Alloc                                       allocator_type;
 
-      // 23.2.3.1 construct/copy/destroy:
+      // 23.3.4.2 construct/copy/destroy:
 
       /**
        *  @brief  Creates a %forward_list with no elements.
@@ -446,8 +436,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @param  __al    An allocator object.
        */
       forward_list(const forward_list& __list, const _Alloc& __al)
-      : _Base(__list, _Node_alloc_type(__al))
-      { }
+      : _Base(_Node_alloc_type(__al))
+      { _M_range_initialize(__list.begin(), __list.end()); }
 
       /**
        *  @brief  Move constructor with allocator argument.
@@ -455,6 +445,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @param  __al    An allocator object.
        */
       forward_list(forward_list&& __list, const _Alloc& __al)
+      noexcept(_Node_alloc_traits::_S_always_equal())
       : _Base(std::move(__list), _Node_alloc_type(__al))
       { }
 
@@ -504,7 +495,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  The %forward_list copy constructor.
        *  @param  __list  A %forward_list of identical element and allocator
-       *                types.
+       *                  types.
        */
       forward_list(const forward_list& __list)
       : _Base(_Node_alloc_traits::_S_select_on_copy(
@@ -514,10 +505,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  The %forward_list move constructor.
        *  @param  __list  A %forward_list of identical element and allocator
-       *                types.
+       *                  types.
        *
        *  The newly-created %forward_list contains the exact contents of @a
-       *  forward_list. The contents of @a __list are a valid, but unspecified
+       *  __list. The contents of @a __list are a valid, but unspecified
        *  %forward_list.
        */
       forward_list(forward_list&& __list) noexcept
@@ -647,7 +638,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       get_allocator() const noexcept
       { return allocator_type(this->_M_get_Node_allocator()); }
 
-      // 23.2.3.2 iterators:
+      // 23.3.4.3 iterators:
 
       /**
        *  Returns a read/write iterator that points before the first element
@@ -743,7 +734,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       max_size() const noexcept
       { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); }
 
-      // 23.2.3.3 element access:
+      // 23.3.4.4 element access:
 
       /**
        *  Returns a read/write reference to the data at the first
@@ -767,7 +758,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         return __front->_M_value;
       }
 
-      // 23.2.3.4 modifiers:
+      // 23.3.4.5 modifiers:
 
       /**
        *  @brief  Constructs object in %forward_list at the front of the
@@ -1031,7 +1022,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       clear() noexcept
       { this->_M_erase_after(&this->_M_impl._M_head, 0); }
 
-      // 23.2.3.5 forward_list operations:
+      // 23.3.4.6 forward_list operations:
 
       /**
        *  @brief  Insert contents of another %forward_list.
@@ -1223,7 +1214,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { this->_M_impl._M_head._M_reverse_after(); }
 
     private:
-      // Called by the range constructor to implement [23.1.1]/9
+      // Called by the range constructor to implement [23.3.4.2]/9
       template<typename _InputIterator>
         void
         _M_range_initialize(_InputIterator __first, _InputIterator __last);
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 5d18a6e..4f9a7fa 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -36,28 +36,14 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
   template<typename _Tp, typename _Alloc>
     _Fwd_list_base<_Tp, _Alloc>::
-    _Fwd_list_base(const _Fwd_list_base& __lst, const _Node_alloc_type& __a)
-    : _M_impl(__a)
-    {
-      this->_M_impl._M_head._M_next = 0;
-      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
-      _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
-
-      while (__curr)
-        {
-          __to->_M_next = _M_create_node(__curr->_M_value);
-          __to = __to->_M_next;
-          __curr = static_cast<_Node*>(__curr->_M_next);
-        }
-    }
-
-  template<typename _Tp, typename _Alloc>
-    _Fwd_list_base<_Tp, _Alloc>::
     _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a)
     : _M_impl(__a)
     {
       if (__lst._M_get_Node_allocator() == __a)
-        this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
+	{
+	  this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
+	  __lst._M_impl._M_head._M_next = 0;
+	}
       else
         {
           this->_M_impl._M_head._M_next = 0;
@@ -72,7 +58,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
               __curr = static_cast<_Node*>(__curr->_M_next);
             }
         }
-      __lst._M_impl._M_head._M_next = 0;
     }
 
   template<typename _Tp, typename _Alloc>
@@ -119,7 +104,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       return __last;
     }
 
-  // Called by the range constructor to implement [23.1.1]/9
+  // Called by the range constructor to implement [23.3.4.2]/9
   template<typename _Tp, typename _Alloc>
     template<typename _InputIterator>
       void