#102 infinite O(n) recursion in list<>::insert and list<>::splice

closed-rejected
2
2007-01-04
2006-12-28
No

To reproduce:

1) Create a memory allocator that defines operator==() (i.e. for allocating memory from different pools). For test purposes, make memory allocator operator==() return true if and only if the two allocators are actually the same.

2) Create a list<> instance with this allocator.

3) Put some large number of items in the list.

4) Try to copy this list instance into another list object.

5) Observer the "stack overflow" crash (tested on windows and linux).

The following stack trace shows that in the described case the list<>::insert/list<>::splice methods recursively call each other. Thus, for large list the program easily runs out of stack:

list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++
list<>::splice(stlpd_std::priv::_List_iterator<> __pos={...}, stlpd_std::priv::_NonDbg_list<> & __x={...}) Line 596 C++
list<>::_M_splice_insert_dispatch<stlpd_std::priv::_List_iterator< > >() Line 485 C++
list<>::insert<stlpd_std::priv::_List_iterator< > >() Line 462 C++

Discussion

  • Aleksey Sanin

    Aleksey Sanin - 2006-12-28

    Logged In: YES
    user_id=851494
    Originator: YES

    Forgot to add that the problem appears on 5.1.0 release tarball. We were using 5.0.1 before that and everything was OK.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2006-12-28

    Logged In: YES
    user_id=615813
    Originator: NO

    Are you sure this is not problem of you allocator? Short test required to reproduce problem.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2006-12-28
    • priority: 5 --> 3
    • status: open --> open-rejected
     
  • Aleksey Sanin

    Aleksey Sanin - 2006-12-28

    Logged In: YES
    user_id=851494
    Originator: YES

    I am absolutely sure this is not an allocator problem. It went away when I changed allocator's operator==() to always return 'true'.

    Unfortunately, I don't have a small test in hands. However, take a look at the code in _list.h at lines from the stack trace. The recursive loop is pretty obvious.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2006-12-28
    • priority: 3 --> 2
    • assigned_to: nobody --> complement
     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2006-12-28

    Logged In: YES
    user_id=615813
    Originator: NO

    The short clean test in this case strongly required, to proof that

    - usage is correct, conform to standards, free from side effects
    - demonstrate the minimal conditions to reproduce problem

    The presence of list in stack not proof at all: I can write (and do it many times) many wrong code when STLport will be on top of crash, but it still remains my fault.

    The portable code (well, code that can be compiled on *NIXes) is preferable for me.

     
  • Aleksey Sanin

    Aleksey Sanin - 2006-12-28

    Logged In: YES
    user_id=851494
    Originator: YES

    Well, I believe that I gave a reasonable repro and a stack trace with 3 line numbers (462, 596 and 485) to look at. Unfortunately, I don't think I will have time for creating and (more important) testing a standalone repro test.

     
  • Francois Dumont

    Francois Dumont - 2006-12-30

    Logged In: YES
    user_id=1096600
    Originator: NO

    I think the problem is in your allocator implementation.

    We already have a test case for the list container instantiated with an allocator implementation having a state so this allocator implements the == operator like you describe. (see test/unit/list_test.cpp, test case is ListTest::allocator_with_state). We are using list::splice in this method without call stack overflow.

    Lets consider 2 list instances l1 and l2 having l1.get_allocator() != l2.get_allocator(). If you call l1.splice(l1.begin(), l2), list::splice will use list::insert as allocator instances are different. Now list::insert will also use list::splice so you might think that there is a loop. The difference in the call to list::splice in list::insert is that the splice is called with a newly built list instance generated from l1 using l1 allocator. So this new list that we will call l3 should now have l1.get_allocator() == l3.get_allocator() and in this case list::splice won't call insert again.

    So you should check that using your allocator:
    assert(list<...>(l1.get_allocator())).get_allocator() == l1.get_allocator());

     
  • Nobody/Anonymous

    Logged In: NO

    >
    > So you should check that using your allocator:
    >
    > assert(list<...>(l1.get_allocator())).get_allocator() == l1.get_allocator());
    >

    Thanks for explanations! This was not the case for me since the new allocator was picking a semi-random memory pool even in a copy constructor case:

    MyAllocator alloc1;
    MyAllocator alloc2(alloc1);

    =>

    alloc1 is not necessarily equal to alloc2.

    However, is this a *standard* requirement for allocators?

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2007-01-02

    Logged In: YES
    user_id=615813
    Originator: NO

    > However, is this a *standard* requirement for allocators?

    Yes. Standard: 20.1.5, Table 32:

    a1 == a2 ... returns true if storage allocated from each can be deallocated via the other.

    20.1.5 par 5:

    ... any requirements imposed on allocators by containers beyond those requirements that appear in Table 32 and the semantics of containers and algorithms when allocator instances compare non-equal, are implementation-defined.

    Looks like reasonable.

     
  • Aleksey Sanin

    Aleksey Sanin - 2007-01-04

    Logged In: YES
    user_id=851494
    Originator: YES

    OK, sounds fair. After your explanations, I don't feel that this is a real bug. However, it might be a good idea to have

    assert(list<...>(l1.get_allocator())).get_allocator() == l1.get_allocator());

    in the code because the code relies on this behavior and there is a potential crash that depends on the data size (i.e. if you test with 3 items in the list then it works, if you run it with 30000 items in the list then it crashes).

    Thanks again for your explanations!

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2007-01-04
    • status: open-rejected --> closed-rejected
     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2007-01-04

    Logged In: YES
    user_id=615813
    Originator: NO

    > However, it might be a good idea to have ...

    No. Bad idea to check such fault that very specific to you code.

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks