Archive

Archive for November, 2009

Fun Times With Virtual Table Corruption

November 13, 2009 1 comment

Prior to yesterday, I had no idea what a virtual table was. Five hours of debugging with tdot later…. I found out that its corruption was one of the most silent of errors that I’ve yet to encounter.

The story goes like this: Say you create some base class with some private members that you don’t intend on changing after construction and some virtual functions that you intend on extending. Oh… maybe a class like, Base?

#include <iostream>
using namespace std;

class Base {
 int _row;
 int _col;
public:
 Base(int row = 0, int col = 0){
   _row = row;
   _col = col;
 }

 virtual void vf(void){
   cout << "vf called from Base" << endl;
 }
};

Now, let’s extend this here class and create a new class say…. Derived. Now let’s assume that this class can only determine the row and col of it’s base after some calculations. So, how do we set our row and col AFTER we’ve done our calculations? Well simple, we call Base’s constructor at the bottom of Derived’s constructor! We’re also going to derive the vf() function. Something like the following:

class Derived : public Base {
 int _numA;
 int _numB;
public:
 Derived(int someNum, int someOtherNum) : Base(){
   int calc1 = someNum + someOtherNum;
   int calc2 = someOtherNum * 5 / someNum - 2;
   this->Base::Base(calc1, calc2);
 }

 void vf(void){
   cout << "vf called from Derived" << endl;
 }
};

Well there we go! Problem solved, right? Looks harmless enough. Although this code will compile, it will not act nice. Btw, note that we could have easily thrown those calculations right into the constructor in the initializer list but bear with me for the sake of argument πŸ™‚

Infact, here is the output using the following main:

int main(void){
 Derived myDerived(3, 5);
 myDerived.vf();
 Base* myBasePtr = &myDerived;
 myBasePtr->vf();

 return 0;
}

Output:

vf called from Derived
vf called from Base

Notice how the second line shows that the function called was clearly Base’s version. Why didn’t the virtual keyword work?! Well the reason for that is a little interesting… The way C++ handles virtuality is through something called the vtable. The vtable is an array of function pointers that is built by the compiler with one element for every virtual function in the class. The pointer to this table is infact a hidden member variable that the compiler automatically inserts into objects instantiated from classes that contain virtual functions.

Normally, the vtable is updated to point to the most derived versions of a Base class’ functions. This update happens after the constructor for the base class has been called and is infact updated by the derived class’ constructor.

When a virtual function is called, C++ looks up its entry in the vtable and calls the appropriate function! Effective, however this does mean that virtual functions are slightly slower than other functions in execution as they take one more step to be resolved.

So back to the present topic, why did calling vf() on myBasePtr call Base’s version of vf? Well, the reason for that is this line:

   this->Base::Base(calc1, calc2);

What’s happening is that the Base sub-object inside of Derived is being reconstructed which is overwriting the vtable thus losing the reference to the derived vf() function! So make sure that you don’t reconstruct the base part of a derived object at any point, it could cause crazy problems. Consider the fact that virtual destructors are handled in the vtable as well so attempting to delete an object with a corrupted vtable can cause CRAZY assertion failures. At the end of the day, good design will ensure that you don’t have to deal with stuff like this.

As I mentioned earlier, this whole thing took about FIVE hours to debug with tdot‘s help. So, now that I’ve posted this here, hopefully no one will have to go through random virtualization failures πŸ™‚

END TRANSMISSION

Advertisements

DsStack Copy Constructor: Optimized!

November 2, 2009 Leave a comment

Ok so I optimized the DsStack class in multiple ways.

Firstly, I re-wrote the default constructor and the SNode constructor:

/*
 *Made data pass by reference as opposed to by value
 *and made it const
 *Made next const
 */
SNode::SNode(const DString& data, const SNode* next)
                   : data(data), next((SNode*)next){
}

Stack::Stack(void) : top(NULL) {
}

As you may have noticed, most variables are initialized via initialization list. This is to optimize performance; it also happens to save lines πŸ˜‰

I’ve made the copy constructor as well:

Stack::Stack(const Stack& src) : top(NULL) {
  if (&src != this) {
    SNode* prev(NULL);
    SNode* cur(NULL);

    for (SNode* srcCur(src.top);
          srcCur != NULL;
          srcCur = srcCur->next) {
      cur = new SNode(srcCur->data);
      if (prev != NULL)
        prev->next = cur;
      else
        top = cur;
      prev = cur;
    }
  }
}

You’ll notice that this constructor uses initialization lists extensively. As well, I’ve tried to limit the creation of new objects as much as possible. That’s about it.

END TRANSMISSION