Vector of recursive structures has memory problems

I am completely stuck with a simple piece of code that misbehaves with memory (as reported by Valgrind). I reduced it to this short test-case:

#include <vector>

struct el
{
    el * next = nullptr;
};

class list
{
public:
    list(): tail(nullptr) {}

    void push_back()
    {
        el nw;
        m_list.push_back(nw);

        if (tail == nullptr)
            tail = &m_list.back();
        else
        {
            tail->next = &m_list.back();
            tail = tail->next;
        }
    }

private:
    std::vector<el> m_list;
    el * tail;
};

int main()
{
    list a;
    a.push_back();
    a.push_back();
    return 0;
}

I expect it to create an array with 2 structures, first of which has a pointer to the second one. The real source crashes with a segfault on destruction, so I consider this report important:

==1630== Invalid write of size 8
==1630==    at 0x400A37: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Address 0x5a86c80 is 0 bytes inside a block of size 8 free'd
==1630==    at 0x4C2A8DC: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4011D5: __gnu_cxx::new_allocator<el>::deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400F79: std::_Vector_base<el, std::allocator<el> >::_M_deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400DA3: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Block was alloc'd at
==1630==    at 0x4C29780: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4012BB: __gnu_cxx::new_allocator<el>::allocate(unsigned long, void const*) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4010D2: std::_Vector_base<el, std::allocator<el> >::_M_allocate(unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400CC1: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x40095D: main (in /home/ilya/Projects/algos/a.out)
==1630==
==1630== Invalid read of size 8
==1630==    at 0x400A42: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Address 0x5a86c80 is 0 bytes inside a block of size 8 free'd
==1630==    at 0x4C2A8DC: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4011D5: __gnu_cxx::new_allocator<el>::deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400F79: std::_Vector_base<el, std::allocator<el> >::_M_deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400DA3: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Block was alloc'd at
==1630==    at 0x4C29780: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4012BB: __gnu_cxx::new_allocator<el>::allocate(unsigned long, void const*) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4010D2: std::_Vector_base<el, std::allocator<el> >::_M_allocate(unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400CC1: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x40095D: main (in /home/ilya/Projects/algos/a.out)

1 answer

  • answered 2017-11-12 20:32 VTT

    Once you push_back into vector or otherwise alter it all references and pointers to stored items are invalidated so all the tail and next fields will contain dangling pointers. And dereferencing them will cause Undefined Behavior. You can actually use std::list or (if you are just writing some list implementation for learning purposes) you can first populate vector and then collect pointers to stored items knowing that they will remain valid.