Vector is deleted after resize()

[xman]

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Any ideas? Compiler problems? or non-trivial bugs? Thanks.

#include <vector>
using std::vector;

class A {
public:
int left;
int right;
};

class B {
public:
void build(int n) {
b.clear();
next_index = 0;
int root = build_recursive(n);
}

int build_recursive(int n) {
int i = get_next_index();
if (n > 0) {
b.left = build_recursive(n-1);
b.right = build_recursive(n-1);
}
return i;
}

int get_next_index(void) {
A a;
b.push_back(a);
int index = next_index++;
return index;
}

int next_index;
vector<A> b;
};

int main(int argc, char* argv[])
{
B tree;
tree.build(14);
return 0 ;
}

 

[*PaN!*]

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Funny. Looks like your compiler is taking the address of the left part
before evaluating the right part... some kind of RVO failing badly. Try to
disable some (or all) optimizations and try again...

 

[asterisc]

xman a scris:

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Any ideas? Compiler problems? or non-trivial bugs? Thanks.

#include <vector>
using std::vector;

class A {
public:
int left;
int right;
};

class B {
public:
void build(int n) {
b.clear();
next_index = 0;
int root = build_recursive(n);
}

int build_recursive(int n) {
int i = get_next_index();
if (n > 0) {
b.left = build_recursive(n-1);
b.right = build_recursive(n-1);
}
return i;
}

int get_next_index(void) {
A a;
b.push_back(a);
int index = next_index++;
return index;
}

int next_index;
vector<A> b;
};

int main(int argc, char* argv[])
{
B tree;
tree.build(14);
return 0 ;
}

I'm using windows and there is no segmentation fault.
You can choose to reserve() the size instead of clean().. in build()
function. That way, there will be no resizes.

 

[xman]

I'm using windows and there is no segmentation fault.
You can choose to reserve() the size instead of clean().. in build()
function. That way, there will be no resizes.

Whether a program segfault is tricky. I traced the execution using
Valgrind and confirmed that it writes to a freed memory address. See
trace below. reserve() doesnt serve the purpose because I dont know
how many to reserve.

==24373== Invalid write of size 4
==24373== at 0x407A41:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A39:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A39:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A08:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:239)
==24373== by 0x407A08:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:239)
==24373== by 0x407A08:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:239)
==24373== by 0x407CA7: KDTree::build_tree() (kdtree.h:188)
==24373== by 0x401463: main (main.cpp:26)
==24373== Address 0x54565CC is 1,436 bytes inside a block of size
900,960 free'd
==24373== at 0x4A051A0: operator delete(void*) (vg_replace_malloc.c:
244)
==24373== by 0x4039B2:
__gnu_cxx::new_allocator<KDTreeNode>::deallocate(KDTreeNode*, unsigned
long) (new_allocator.h:94)
==24373== by 0x4039E4: std::_Vector_base<KDTreeNode,
std::allocator<KDTreeNode> >::_M_deallocate(KDTreeNode*, unsigned
long) (stl_vector.h:133)
==24373== by 0x406039: std::vector<KDTreeNode,

::_M_fill_insert(__gnu_cxx::__normal_iterator<KDTreeNode*,

std::vector<KDTreeNode, std::allocator<KDTreeNode> > >, unsigned long,
KDTreeNode const&) (vector.tcc:381)
==24373== by 0x406100: std::vector<KDTreeNode,

::insert(__gnu_cxx::__normal_iterator<KDTreeNode*,

std::vector<KDTreeNode, std::allocator<KDTreeNode> > >, unsigned long,
KDTreeNode const&) (stl_vector.h:658)
==24373== by 0x40619D: std::vector<KDTreeNode,
std::allocator<KDTreeNode> >::resize(unsigned long, KDTreeNode)
(stl_vector.h:426)
==24373== by 0x4061E0: KDTree::get_next_free_node_index() (kdtree.h:
309)
==24373== by 0x40777E:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:202)
==24373== by 0x407A39:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A39:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A39:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:240)
==24373== by 0x407A08:
KDTree::build_tree_recursive(std::vector<int, std::allocator<int> >
const&) (kdtree.h:239)

 

[xman]

Funny. Looks like your compiler is taking the address of the left part
before evaluating the right part... some kind of RVO failing badly. Try to
disable some (or all) optimizations and try again...

By default gcc doesnt turn on optimizations. Even I do "gcc -O0 ", it
still writes to the wrong memory address.

 

[xman]

I'm using windows and there is no segmentation fault.
You can choose to reserve() the size instead of clean().. in build()
function. That way, there will be no resizes.

Whether a program segfault is tricky. I traced the execution using
Valgrind and confirmed that it writes to a freed memory address. See
sample
trace below. reserve() doesnt serve the purpose because I dont know
how many to reserve.

==24421== Invalid write of size 4
==24421== at 0x4016FA: B::build_recursive(int)
==24421== by 0x401739: B::build(int)
==24421== by 0x40080E: main
==24421== Address 0x51762CC is 4 bytes inside a block of size 131,072
free'd
==24421== at 0x4A051A0: operator delete(void*) (vg_replace_malloc.c:
244)
==24421== by 0x4010FE: __gnu_cxx::new_allocator<A>::deallocate(A*,
unsigned long)

::_M_deallocate(A*, unsigned long)

::_M_insert_aux(__gnu_cxx::__normal_iterator<A*, std::vector<A,

:ush_back(A const&)

==24421== by 0x401674: B::get_next_index()
==24421== by 0x4016A4: B::build_recursive(int)
==24421== by 0x4016F9: B::build_recursive(int)
==24421== by 0x401739: B::build(int)
==24421== by 0x40080E: main

 

[Charles Bailey]

int build_recursive(int n) {
int i = get_next_index();
if (n > 0) {
b.left = build_recursive(n-1);
b.right = build_recursive(n-1);
}
return i;
}

In gcc it looks like the left hand side of the assignment operator is
evaluated (as an lvalue of type int), so in reality as an address to
write to, before the right hand side is evaluated. This is allowed
behaviour. The 'bug' is that the evaluation of the right hand side has
a side effect that makes the address determined in the first step not
where you actually want to store the value of the r.h.s., but worse than
this, it makes it invalid.

The assignment expression is invalid in much the same way that a =
i++; is invalid (comp.lang.c FAQ 3.1).

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

This looks like a suitable fix.

Subtle issue, though.

Charles.

 

[Zeppe]

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Any ideas? Compiler problems? or non-trivial bugs? Thanks.

[SNIP]

b.left = build_recursive(n-1);
b.right = build_recursive(n-1);

I'm afraid it's your fault. The order of evaluation of the left and
right side of the operator = is undefined, so you can't assume that
b.right will be evaluated after the function call (and actually it
isn't). Your workaround is correct, because there is a sequence point at
the end of each instruction.

The bug is actually a little bit difficult to find without experiencing
the segmentation fault. It's a matter of experience (messing up with the
evaluation order is quite common in c/c++). In this case it's also
difficult to see due to the fact that you don't notice instantly that
the function build_recursive will modify b...

Regards,

Zeppe

 

[BobR]

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().

If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Any ideas? Compiler problems? or non-trivial bugs? Thanks.

#include <vector>
using std::vector;

class A {
public:
int left;
int right;
};

class B{ public:
void build(int n){
b.clear();

If you also want to 'reset' capacity (.clear() doesn't):

next_index = 0;
int root = build_recursive(n);

Do you do something with 'root'?
Else just:
build_recursive( n ); // ignore return.

}

int build_recursive(int n) {
int i = get_next_index();
if (n > 0) {
b.left = build_recursive(n-1);
b.right = build_recursive(n-1);
}
return i;
}

This won't fix the problem, but might help you find it faster (next time):

int build_recursive(int n) {
int i = get_next_index();
if (n > 0) {
try{
b.at( i ).left = build_recursive( n-1);
b.at( i ).right = build_recursive( n-1);
}
catch( std:ut_of_range const &Oor){
std::cerr << "caught Oor=" << Oor.what() << std::endl;
std::cerr<<"i="<<i<<" n="<<n<<std::endl;
} // catch(oor)
} // if(n)
return i;
}
// note: this is for 'testing'. You would remove the try-catch for final.
// You could put the try-catch in main() (still use the '.at()' though).

int get_next_index(void) {
A a;
b.push_back(a);
int index = next_index++;
return index;
}
int next_index;
vector<A> b;
};

int main(int argc, char* argv[]){
B tree;
tree.build(14);
return 0 ;
}

You do know you can set the vector size in constructor, don't you?

class B{ public:
B( std::size_t size ): b( size ){}
// .....
vector<A> b;
};

Just some ideas for you to think about.

 

[James Kanze]

The codes below basically builds a binary tree. It runs well on Intel
compiler. However, when I use gcc 4.2.0, the assignment to b.right
causes segmentation fault. Tracing with valgrind reveals that the
particular memory address was deleted during push_back().
If I change the assignments to

int x = build_recursive(n-1);
int y = build_recursive(n-1);
b.left = x;
b.right = y;

[The original code was:

b[ i ].left = build_recursive( n - 1 ) ;
b[ i ].right = build_recursive( n - 1 ) ;

b is an std::vector, on which build_recursive does a
push_back.]

there is no segmentation fault anymore. It seems to me the original
code has the b value cached, hence, during the assignment to
b.right, it uses old b which may be invalidated after
push_back() due to resize.

Funny. Looks like your compiler is taking the address of the left part
before evaluating the right part...

And why shouldn't it? The most "natural" way to evaluate an
expression is left to right. (Java requires evaluation from
left to right. In this case, you wouldn't get undefined
behavior in Java, because garbage collection would keep the
memory live. But the reference in the b would be the last
reference to the memory, so the memory you wrote to would be
freed immediately after you wrote to it---you wouldn't be
writing to the underlying memory of the vector.)

Historically, of course, compilers would evaluation first which
ever side of the operator required the most registers.

The problem is that he is calling a function with side effects,
in a non-trivial expression. That's almost always a recepe for
problems.

some kind of RVO failing badly. Try to
disable some (or all) optimizations and try again...

It has nothing to do with optimization, although optimization
may change whether the problem appears or not. And the compiler
is correct here; it is the code which is wrong.