[Bug c++/17012] New: std::list's function, remove, looks like it is reading memory that has been freed.

[Bug c++/17012] New: std::list's function, remove, looks like it is reading memory that has been freed.

[debrak at sgi dot com]

---------------------------------------------------------
I use purify to look for errors in my code.
But I think it may have found a "Free Memory Read" error 
in the std::list template's function, remove.

My program is:
----------------------------
#include <iostream>
#include <list>
using namespace std;

int main()
{ 
  list<int> var;
  var.push_back(0);
  var.push_back(1);
  var.push_back(2);
  var.push_back(3);
  var.push_back(4);

  cout<<"BEFORE remove():"<<endl;
  for (list<int>::iterator i = var.begin(); i!=var.end(); i++) {
    cout<<"*i="<<*i<<endl;
  }

  list<int>::iterator i0 = var.begin();
  i0++;
  i0++;
  var.remove(*i0);

  cout<<"\nAFTER remove():"<<endl;
  for (list<int>::iterator i = var.begin(); i!=var.end(); i++) {
    cout<<"*i="<<*i<<endl;
  }
}
----------------------------

When I run purify on it, I see 
a Free Memory Error which occurs when "var.remove(*i0) is executed.


---------------------------------------------------------
* the exact version of GCC; 3.4.1
* the system type; i686-pc-linux-gnu
* the options given when GCC was configured/built; --prefix=/usr/local/gcc-3.4.1

The above information was obtained by doing:

% gcc -v
Reading specs from /usr/local/gcc-3.4.1/lib/gcc/i686-pc-linux-gnu/3.4.1/specs
Configured with: /home/duff1/debrak/gcc-3.4.1/gcc-3.4.1/configure
--prefix=/usr/local/gcc-3.4.1
Thread model: posix
gcc version 3.4.1

---------------------------------------------------------
* the complete command line that triggers the bug;

%  bug1.pure
BEFORE remove():
*i=0
*i=1
*i=2
*i=3
*i=4

AFTER remove():
*i=0
*i=1
*i=3
*i=4

Look in purify.log for the FMR (Free Memory Read) error.

---------------------------------------------------------
* the compiler output (error messages, warnings, etc.); and

There are no errors or Warnings when I compile:

% gcc -v -save-temps -g -Wall -o bug1.o -c bug1.cpp

% gcc -g -Wall -o bug1.o -c bug1.cpp

% g++ -g -Wall -o bug1      bug1.o

% purify -log-file=purify.log g++ -g -Wall -o bug1.pure bug1.o
Purify 2003a.06.00 Linux (32-bit) Copyright (C) 1992-2003 Rational Software
Corp.  All rights reserved.  
Instrumenting: bug1.o  Linking

---------------------------------------------------------
* the preprocessed file (*.i*) that triggers the bug, generated by adding
-save-temps to the complete compilation command, or, in the case of a bug report
for the GNAT front end, a complete set of source files (see below).


#################################################################
The purigy log is as follows:

****  Purify instrumented bug1.pure (pid 3776 at Thu Aug 12 15:47:38 2004)
  * Purify 2003a.06.00 Linux (32-bit) Copyright (C) 1992-2003 Rational Software
Corp.  All rights reserved.  
  * For contact information type: "purify -help"
  * Options settings: -chain-length=20 -threads=yes \
    -follow-child-processes=yes -g++=yes -purify -log-file=purify.log \
    -purify-home=/usr/local/Rational/releases/purify.i386_linux2.2003a.06.00 \
    -cache-dir=/usr/local/Rational/releases/purify.i386_linux2.2003a.06.00/cache 
  * License successfully checked out.
  * Command-line: bug1.pure 

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_internal_ascii [libc.so.6]
	wctob          [libc.so.6]
	std::ctype< wchar_t>::_M_initialize_ctype( void) [ctype_members.cc:265]
	std::ctype< wchar_t>::ctype( unsigned) [ctype.cc:91]
	std::locale::_Impl::_Impl( unsigned) [new:92]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffedd8 on the stack.
  * Address 0xbfffedd8 is       96 bytes below frame pointer in function wctob.

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_ascii_internal [libc.so.6]
	btowc          [libc.so.6]
	std::ctype< wchar_t>::_M_initialize_ctype( void) [ctype_members.cc:277]
	std::ctype< wchar_t>::ctype( unsigned) [ctype.cc:91]
	std::locale::_Impl::_Impl( unsigned) [new:92]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffede4 on the stack.
  * Address 0xbfffede4 is       84 bytes below frame pointer in function btowc.

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_ascii_internal [libc.so.6]
	btowc          [libc.so.6]
	std::numpunct< wchar_t>::_M_initialize_numpunct(__locale_struct *)
[numeric_members.cc:119]
	std::locale::_Impl::_Impl( unsigned) [locale_facets.h:1700]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffee04 on the stack.
  * Address 0xbfffee04 is       84 bytes below frame pointer in function btowc.

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_ascii_internal [libc.so.6]
	btowc          [libc.so.6]
	std::numpunct< wchar_t>::_M_initialize_numpunct(__locale_struct *)
[numeric_members.cc:125]
	std::locale::_Impl::_Impl( unsigned) [locale_facets.h:1700]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffee04 on the stack.
  * Address 0xbfffee04 is       84 bytes below frame pointer in function btowc.

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_ascii_internal [libc.so.6]
	btowc          [libc.so.6]
	std::moneypunct< wchar_t,false>::_M_initialize_moneypunct(__locale_struct *,
char const *) [monetary_members.cc:524]
	std::locale::_Impl::_Impl( unsigned) [locale_facets.h:3581]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffedc4 on the stack.
  * Address 0xbfffedc4 is       84 bytes below frame pointer in function btowc.

****  Purify instrumented bug1.pure (pid 3776)  ****
UMR: Uninitialized memory read:
  * This is occurring while in:
	__gconv_transform_ascii_internal [libc.so.6]
	btowc          [libc.so.6]
	std::moneypunct< wchar_t,true>::_M_initialize_moneypunct(__locale_struct *,
char const *) [monetary_members.cc:379]
	std::locale::_Impl::_Impl( unsigned) [locale_facets.h:3581]
	std::locale::_S_initialize_once( void) [new:92]
	std::locale::_S_initialize( void) [locale_init.cc:155]
	std::locale::locale( void) [locale_init.cc:103]
	std::ios_base::Init::Init( void) [streambuf:437]
	__static_initialization_and_destruction_0( int, int) [iostream:77]
	_GLOBAL__I_main [bug1.cpp:8]
	__do_global_ctors_aux [crtend.o]
	_init          [crti.o]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0xbfffedc4 on the stack.
  * Address 0xbfffedc4 is       84 bytes below frame pointer in function btowc.

****  Purify instrumented bug1.pure (pid 3776)  ****
FMR: Free memory read:
  * This is occurring while in:
	std::list< int,std::allocator< int>>::remove( int const &) [list.tcc:181]
	main           [bug1.cpp:22]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * Reading 4 bytes from 0x80a62e8 in the heap.
  * Address 0x80a62e8 is 8 bytes into a freed  block at 0x80a62e0 of 12 bytes.
  * This block was allocated from:
	malloc         [rtlib.o]
	operator new( unsigned) [new_op.cc:48]
	__gnu_cxx::new_allocator<std::_List_node< int>>::allocate( unsigned, void const
*) [new_allocator.h:81]
	std::_List_base< int,std::allocator< int>>::_M_get_node( void) [stl_list.h:309]
	std::list< int,std::allocator< int>>::_M_create_node( int const &) [stl_list.h:433]
	std::list< int,std::allocator< int>>::_M_insert(std::_List_iterator< int>, int
const &) [stl_list.h:1161]
	std::list< int,std::allocator< int>>::push_back( int const &) [stl_list.h:783]
	main           [bug1.cpp:10]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]
  * There have been 0 frees since this block was freed from:
	free           [rtlib.o]
	_ZdLpV         [del_op.cc:40]
	__gnu_cxx::new_allocator<std::_List_node< int>>::deallocate(std::_List_node<
int> *, unsigned) [new_allocator.h:86]
	std::_List_base< int,std::allocator< int>>::_M_put_node(std::_List_node< int>
*) [stl_list.h:313]
	std::list< int,std::allocator< int>>::_M_erase(std::_List_iterator< int>)
[stl_list.h:1172]
	std::list< int,std::allocator< int>>::remove( int const &) [list.tcc:182]
	main           [bug1.cpp:22]
	__libc_start_main [libc.so.6]
	_start         [crt1.o]

****  Purify instrumented bug1.pure (pid 3776)  ****
Current file descriptors in use: 5
FIU: file descriptor 0: <stdin>
FIU: file descriptor 1: <stdout>
FIU: file descriptor 2: <stderr>
FIU: file descriptor 26: <reserved for Purify internal use>
FIU: file descriptor 27: <reserved for Purify internal use>

****  Purify instrumented bug1.pure (pid 3776)  ****
Purify: Searching for all memory leaks...

Memory leaked: 0 bytes (0%); potentially leaked: 0 bytes (0%)

Purify Heap Analysis (combining suppressed and unsuppressed blocks)
                         Blocks        Bytes
              Leaked          1           16
  Potentially Leaked          0            0
              In-Use          1           64
  ----------------------------------------
     Total Allocated          2           80

****  Purify instrumented bug1.pure (pid 3776)  ****
  * Program exited with status code 0.
  * 7 access errors, 470 total occurrences.
  * 0 bytes leaked.
  * 0 bytes potentially leaked.
  * Basic memory usage (including Purify overhead):
    236244 code
    144532 data/bss
    4236 heap (peak use)
    4184 stack
  * Shared library memory usage (including Purify overhead):
    1782596 libstdc++.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (shared code)
    125556 libstdc++.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (private data)
    300483 libm.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (shared code)
    724 libm.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (private data)
    73956 libgcc_s.so.1_pure_p3_c0_108272013_2418-187xsmp_32 (shared code)
    2280 libgcc_s.so.1_pure_p3_c0_108272013_2418-187xsmp_32 (private data)
    18023 libdl.so.2_pure_p3_c0_108272013_2418-187xsmp_32 (shared code)
    648 libdl.so.2_pure_p3_c0_108272013_2418-187xsmp_32 (private data)
    8097 libinternal_stubs.so.1.0 (shared code)
    372 libinternal_stubs.so.1.0 (private data)
    2951235 libc.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (shared code)
    36448 libc.so.6_pure_p3_c0_108272013_2418-187xsmp_32 (private data)
    77321 ld-linux.so.2 (shared code)
    1744 ld-linux.so.2 (private data)

-- 
           Summary: std::list's function, remove, looks like it is reading
                    memory that has been freed.
           Product: gcc
           Version: 3.4.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: debrak at sgi dot com
                CC: debrak at sgi dot com,gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug c++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[giovannibajo at libero dot it]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |giovannibajo at libero dot
                   |                            |it


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug c++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-08-12 20:11 -------
Hummm, I can "confirm" this on x86 with Valgrind:

==28990== Invalid read of size 4
==28990==    at 0x8048F73: std::list<int, std::allocator<int> >::remove(int
const&) (list.tcc:181)
==28990==    by 0x8048BFA: main (17012.cc:22)
==28990==    by 0x40365E45: __libc_start_main (libc-start.c:225)
==28990==    by 0x8048850: ??? (start.S:102)
==28990==    Address 0x4187C0A4 is 8 bytes inside a block of size 12 free'd
==28990==    at 0x4002BDED: __builtin_delete (vg_replace_malloc.c:244)
==28990==    by 0x4002BE18: operator delete(void*) (vg_replace_malloc.c:253)
==28990==    by 0x804923C: __gnu_cxx::new_allocator<std::_List_node<int>
>::deallocate(std::_List_node<int>*, unsigned) (new_allocator.h:86)
==28990==    by 0x8049195: std::_List_base<int, std::allocator<int>
>::_M_put_node(std::_List_node<int>*) (stl_list.h:313)


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-08-12 20:11:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-08-12 20:51 -------
Another bit of information: the error disappear if I replace var.remove(*i0)
with var.erase(i0)... 

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[debrak at sgi dot com]

------- Additional Comments From debrak at sgi dot com  2004-08-12 21:07 -------
My compile does not work if I replace var.remove(*i0) with var.erase(i0):

%  gcc -g -Wall -o bug1.o -c bug1.cpp
bug1.cpp: In function `int main()':
bug1.cpp:22: error: no matching function for call to `std::list<int,
std::allocator<int> >::remove(std::_List_iterator<int>&)'
/usr/local/gcc-3.4.1/lib/gcc/i686-pc-linux-gnu/3.4.1/../../../../include/c++/3.4.1/bits/list.tcc:174:
note: candidates are: void std::list<_Tp, _Alloc>::remove(const _Tp&) [with _Tp
= int, _Alloc = std::allocator<int>]




-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-08-12 21:20 -------
Hey, in your compile you didn't change remove(*i0) to erase(i0), but instead,
wrongly, remove(i0)! Anyway, this info is trivially true: the problem appear
at line 181 of list.tcc, which is 'if (*__first == __value)'...

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[bkoz at gcc dot gnu dot org]

------- Additional Comments From bkoz at gcc dot gnu dot org  2004-09-02 21:56 -------

What is the status on this? Is there a patch?

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-09-04 12:50 -------
Hi Benjamin: no we don't have a patch, but frankly I'm not sure we have a real 
bug either, despite valgrind agreeing with purify... I mean to look into it 
much more during the next days... 

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[caj at cs dot york dot ac dot uk]

------- Additional Comments From caj at cs dot york dot ac dot uk  2004-09-05 09:42 -------
The cause of this problem is because list::remove takes the object to be 
searched for by reference. We then search along the list and (of course) remove 
it. This then means that any comparisions later on in the list are checking 
against a deleted variable, but tend to work because it was only just deleted. 
Strictly very bad things are happening here.

This could be fixed by not taking the input by reference but instead taking a 
copy of it. This would however obviously be more inefficent.

I think this problem in fact occurs in various places (basically whenever an 
function takes a series of iterators and an object, is it defined if that 
object obtained by dereferencing one of the inputer iterators?). I'm not sure 
that this is decided one way or the other generally, and probably should be.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |caj at cs dot york dot ac
                   |                            |dot uk


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[caj at cs dot york dot ac dot uk]

------- Additional Comments From caj at cs dot york dot ac dot uk  2004-09-05 11:40 -------
This problem seems to go deeper than just list::remove.

As an example, given

A[]={0,1,0,1,0,1,0,1};

then
std::remove(A,A+8,1) and std::remove(A,A+8,*(A+1)) produce different output, as 
the second one will start removing different elements once the value of A[1] is 
changed while the algorithm is running.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012

[Bug libstdc++/17012] std::list's function, remove, looks like it is reading memory that has been freed.

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-07-05 12:11 -------
It seems to me that this is just a simple NAB. There seems to be 3 options
1) Just leave it as is
2) Alter list::remove so in debug mode it aborts if you give it an element from the list
3) Alter list::remove so this code works (which in some very quick checking seems to produce about a 
~15% slowdown on things like list<int>s)

The similar problem on things in <algorithm> I think is more cut (if you pass something by reference to 
an algorithm, that algorithm shouldn't change it, clearly). This could still perhaps be made clearer in the 
standard...

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17012