Vector is deleted after resize()

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[i].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[i].left = x;
b[i].right = y;

there is no segmentation fault anymore. It seems to me the original
code has the b[i] value cached, hence, during the assignment to
b[i].right, it uses old b[i] 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[i].left = build_recursive(n-1);
b[i].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<Ab;
};

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

re: Vector is deleted after resize()

"xman" <cshinyee@gmail.comwrote in message
news:1180005499.973548.130670@p47g2000hsd.googlegr oups.com...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...

--
Marco

re: Vector is deleted after resize()

xman a scris: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.

re: Vector is deleted after resize()

On May 24, 7:55 pm, asterisc <Rares....@ni.comwrote: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(K DTreeNode*, unsigned
long) (new_allocator.h:94)
==24373== by 0x4039E4: std::_Vector_base<KDTreeNode,
std::allocator<KDTreeNode::_M_deallocate(KDTreeNod e*, unsigned
long) (stl_vector.h:133)
==24373== by 0x406039: std::vector<KDTreeNode,
std::allocator<KDTreeNode>std::vector<KDTreeNode, std::allocator<KDTreeNode >, unsigned long,
KDTreeNode const&) (vector.tcc:381)
==24373== by 0x406100: std::vector<KDTreeNode,
std::allocator<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)

re: Vector is deleted after resize()

On May 24, 7:43 pm, "*PaN!*" <s...@pinningids.orgwrote:By default gcc doesnt turn on optimizations. Even I do "gcc -O0 ", it
still writes to the wrong memory address.

re: Vector is deleted after resize()

On May 24, 7:55 pm, asterisc <Rares....@ni.comwrote: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)
==24421== by 0x401130: std::_Vector_base<A, std::allocator<A>==24421== by 0x40155A: std::vector<A, std::allocator<A>std::allocator<A >, A const&)
==24421== by 0x401655: std::vector<A, std::allocator<A>==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

re: Vector is deleted after resize()

xman wrote: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] =
i++; is invalid (comp.lang.c FAQ 3.1).
This looks like a suitable fix.

Subtle issue, though.

Charles.

re: Vector is deleted after resize()

xman wrote:[SNIP]
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[i].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

re: Vector is deleted after resize()

xman <cshinyee@gmail.comwrote in message ...If you also want to 'reset' capacity (.clear() doesn't):
vector<A>.swap( b ); // b.clear() not needed
Do you do something with 'root'?
Else just:
build_recursive( n ); // ignore return.
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::out_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).
// recursion is a bitch! <G>
// I'm not sure how try{} reacts in a recursive call, so, 'grain-of-salt'...
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<Ab;
};

Just some ideas for you to think about.
--
Bob R
POVrookie

re: Vector is deleted after resize()

On May 24, 1:43 pm, "*PaN!*" <s...@pinningids.orgwrote:[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.]
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[i] 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.
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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34