views:

605

answers:

3

I defined a class named nth_best_parse this way:

class nth_best_parse {
      public:
        int traversal;
        int nth_best_active;
        int nth_best_passive;
        double viterbi_prob;

        nth_best_parse();
        nth_best_parse(int t, int nbl, int nbr, double v) {traversal = t; nth_best_active = nbl; nth_best_passive = nbr; viterbi_prob = v;}
    };

Then I declared vectors of this nth_best_parse as members of two different classes:

class Edge {        // an edge associates an Earley style dotted-item with a span
      public:

        <some irrelevant stuff>

        Span span;      // Span of the edge
        bool isActive;
        vector<Traversal *> leading_traversals; // The list of traversals which lead to parsing of this edge

        vector<nth_best_parse> n_best_parses;


        union {
                DottedRule rule_state;  // Accessed if isActive is true
                int symbol;     // Accessed if isActive is false
                                // A symbol corresponding to the category of a passive edge
                                // Put inside this union to save space
        };

        inline int span_length() {return span.end - span.start;}

    };

<some other stuff>

class BPCFGParser {

  public:

    // Some data structures used in intermediary computations for calculating the n-best parses

//    vector<vector<int> > nth_best_pairs;
    vector<vector<nth_best_parse> > n_best_pairs_for_traversals;

    <some other stuff>

    void compute_n_best_parses(Edge *e, int n);

    <some other stuff>
}

Then I run this program with gdb (by the way, I'm using Linux Ubuntu 9.04, g++ 4.3.3,GNU gdb 6.8-debian) and set a breakpoint at the end of the definition of compute_n_best_parses() with some conditions (to locate the exact call of this function I wanted, I was tracing back from a segmentation fault). When gdb hit the breakpoint, I issued a set of commands and the gdb output was like this:

(gdb) print e->n_best_parses.size()
$27 = 1
(gdb) print e->n_best_parses[0]
$28 = (nth_best_parse &) @0x1e96240: {traversal = 0, nth_best_active = 0, nth_best_passive = 0, viterbi_prob = 0.16666666666666666}
(gdb) print e->n_best_parses[0].traversal
$29 = 0
(gdb) print &(e->n_best_parses[0].traversal)
$30 = (int *) 0x1e96240
(gdb) awatch *$30
Hardware access (read/write) watchpoint 6: *$30
(gdb) print e->n_best_parses
$31 = {<std::_Vector_base<nth_best_parse, std::allocator<nth_best_parse> >> = {
    _M_impl = {<std::allocator<nth_best_parse>> = {<__gnu_cxx::new_allocator<nth_best_parse>> = {<No data fields>}, <No data fields>}, 
      _M_start = 0x1e96240, _M_finish = 0x1e96258, _M_end_of_storage = 0x1e96288}}, <No data fields>}
(gdb) continue
Continuing.
Hardware access (read/write) watchpoint 6: *$30

Old value = 0
New value = 1
0x0000000000408a4c in __gnu_cxx::new_allocator<nth_best_parse>::construct<nth_best_parse> (this=0x1e96208, __p=0x1e96240, __args#0=@0x7fff8ad82260)
    at /usr/include/c++/4.3/ext/new_allocator.h:114
114     { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
(gdb) backtrace
#0  0x0000000000408a4c in __gnu_cxx::new_allocator<nth_best_parse>::construct<nth_best_parse> (this=0x1e96208, __p=0x1e96240, __args#0=@0x7fff8ad82260)
    at /usr/include/c++/4.3/ext/new_allocator.h:114
#1  0x000000000042169c in std::vector<nth_best_parse, std::allocator<nth_best_parse> >::push_back<nth_best_parse> (this=0x1e96208, __args#0=@0x7fff8ad82260)
    at /usr/include/c++/4.3/bits/stl_vector.h:703
#2  0x0000000000402bef in BPCFGParser::compute_n_best_parses (this=0x7fff8ad82770, e=0x7f5492858b78, n=3) at BPCFGParser.cpp:639
#3  0x00000000004027fd in BPCFGParser::compute_n_best_parses (this=0x7fff8ad82770, e=0x7f5492859d58, n=3) at BPCFGParser.cpp:606
#4  0x00000000004027fd in BPCFGParser::compute_n_best_parses (this=0x7fff8ad82770, e=0x7f549285a1d0, n=3) at BPCFGParser.cpp:606
#5  0x00000000004064d8 in main () at experiments.cpp:75

Line 639 of BPCFGParser.cpp was like this:

PUSH_BEST_PAIR_FOR_TRAVERSAL(i,row,column,grammar->probs[temp_rule.symbol][temp_rule.expansion]);

This was a macro defined at the beginning of the file as:

#define PUSH_BEST_PAIR_FOR_TRAVERSAL(x,y,z,t) n_best_pairs_for_traversals[x].push_back(nth_best_parse(x, y, z, e->leading_traversals[x]->active_edge->n_best_parses[y].viterbi_prob * e->leading_traversals[x]->passive_edge->n_best_parses[z].viterbi_prob * t))

By the way, class Traversal is defined as:

class Traversal {   // Class for a traversal
      public:
        Edge *active_edge;
        Edge *passive_edge;
        Traversal();
        Traversal(Edge *a, Edge *p) {active_edge = a; passive_edge = p;}
    };

So actually I'm pushing something to the vector n_best_pairs_for_traversals, which is a member of an instance of the class BPCFGParser and the push_back() code somehow overwrites on the vector n_best_parses, which is a member of an instance of the class Edge. How can this ever be possible?

A: 

Are you sure you're passing a valid first argument to your macro? Maybe you're accessing out of bounds when doing n_best_pairs_for_traversals[x] because x is larger than the vector size.

Nicolás
Yes! Acutally I had checked it, but I think I was not careful enough. Somehow it did not give segmentation fault and the memory corruption occured. Thanks for the help.
Onur Cobanoglu
You could use the at() method instead of operator[] to detect such problems more easily. It will check if you're out of bounds and throw an exception, instead of invoking undefined behavior. Obviously at a performance cost.
Nicolás
+5  A: 

You obviously have memory corruption problems somewhere.
BUT there is not enough here inofrmation to help you.

But you are writting C+ code and your class contain pointers.
This is not a good sign (there should hardly ever be a RAW pointer in a C++ class).
This is also often the cause of memory corruption for inexperienced C++ developers!

Have you obeyed the rule of 4?

Make sure every class that contains RAW owned pointers:

  • constructor
  • copy constructor
  • assignment operator
  • destructror.
Martin York
A: 

I'd guess that you are using a vector to store objects (perhaps Traversal?), not realizing that pushing new elements onto that vector can invalidate pointers to elements already in the vector. Use a deque instead if this is the case.

ergosys
Vectors are storing objects of type nth_best_parse, not Traversal. The vector at the back of which I push a new object and the vector overwritten are different vectors.
Onur Cobanoglu
OK, but you can't really watch a vector element if you are adding elements to the vector. The underlying array may be reallocated, making your watched address no longer point to the element you want. A deque does guarantee that there is no reallocation when elements are only added to the end.
ergosys
Of course, this may have nothing to do with the vectors getting corrupted. Did you see this problem using some other debugging method?
ergosys