Moy Blog

Before starting, I just want to mention that I recently joined http://www.planetalinux.org/ , is a nice group of Linux bloggers, if you read this blog and want to read some interesting posts ( mostly in spanish, but some guys post in english ) go there!

Having said that, let’s finish this post.

Yesterday I was discussing with a friend of mine about how polymorphism is implemented in C++, and that is, using a virtual table ( remember the “virtual” keyword in method definitions? ). A virtual table is, rawly speaking, just like an array of function pointers. Each created object with virtual methods needs a virtual table. So, where does the virtual table is stored?, I really don’t know, but I do know where I can find the address of the virtual table associated to an object ( at least in g++ 4.1.1 ), the first sizeof(void*) bytes of an object are used to store a pointer to the virtual table. With this knowledge, one could think that is possible to override the virtual table pointer of the object and call arbitrary functions, and yes, we can. Let’s see some fun code.

#include <iostream>

using namespace std;

class Parent
{
    public:
        virtual void VirtFunc1() { cout << "Parent::VirtFunc1" << endl; }

        virtual void VirtFunc2() { cout << "Parent::VirtFunc2" << endl; }
};

class Child : public Parent
{
    public:

        void VirtFunc1() { cout << "Child::VirtFunc1" << endl; }
        void VirtFunc2() { cout << "Child::VirtFunc2" << endl; }
};

typedef void (*virtual_function)();

struct FakeVirtualTable {
    virtual_function virtual_one;

    virtual_function virtual_two;
};

void fake_virtual_one()
{
    cout << "Faked virtual call 1" << endl;
}

void fake_virtual_two()
{
    cout << "Faked virtual call 2" << endl;
}

int main()
{
    /* declare a Child class and a base pointer to it. */
    Child child_class_obj;
    Parent* parent_class_ptr = &child_class_obj;

    /* create our fake virtual table with pointers to our fake methods */
    FakeVirtualTable custom_table;
    custom_table.virtual_one = fake_virtual_one;

    custom_table.virtual_two = fake_virtual_two;

    /* take the address of our stack virtual table and override the real object pointer to the virtual table */
    FakeVirtualTable* table_ptr = &custom_table;

    memcpy(parent_class_ptr, &table_ptr, sizeof(void*));

    /* call the methods ( but we're really calling the faked functions ) */

    parent_class_ptr->VirtFunc1();
    parent_class_ptr->VirtFunc2();

    return 0;
}

So, try to run that code and, of course, the expected result is having fake_virtual_one() and fake_virtual_two() functions called. No magic there, we just replace the first sizeof(void*) bytes of the object with our own table pointer. There is not a use I can think of right now, but it is funny ….

In my previous post I was talking about memory alignment, and how the compiler can add padding to structures and classes. Sometimes you don’t want the extra padding, let’s say, because you are going to use the structure or class object as data header to be sent to the network. For simplicity sake let’s take the structure we saw in my previous post:

struct aligned {
    long long_data;
    char byte_data;
    int integer_data;
};

Despite the fact that I would never send such structure by the network, since you never know wich computer architecture is going to receive the data, thus, you have to consider endianess and size of int’s etc, the important thing here is that with padding, that structure is likely to have a size of 12 bytes ( see previous post to know why ). If we want to avoid padding effects, and we are using GCC compiler, we can use packed attribute, like this:

struct aligned {
    long long_data;
    char byte_data;
    int integer_data;
} __attribute__ ((packed));

Using sizeof() to check the size of such structure will show us that has the expected 9 bytes for x86 32 bit. Other compilers, like VisualStudio, might use the #pragma directive, not quite sure about how it is used there, but the effect is the same.

Packing a struct or class is easy, however, there are some considerations we should be aware of, let’s say we have this program:

#include <iostream>

using namespace std;
struct packedstruct {
    int  integer;
    char byte;
} __attribute__ ((packed));

void func(int &val)
{
    cout << "calling func\n";

    val += 10;
}

int main()
{
    packedstruct mypackage;

    mypackage.integer = 10;
    func(mypackage.integer);

    cout << "val is " << mypackage.integer << "\n" << endl;

    return 0;
}

What’s the problem with that? well, trying to compile that code, in recent GCC ( 4.1.0 ), will result in an error like this:

packed.cpp:20: error: cannot bind packed field ‘mypackage.packedstruct::integer’ to ‘int&’

It seems somehow representation of packed/unaligned data is not fully compatible with aligned data? We had this issue with some code, I have not understood yet what exactly means, but doing “const” the reference get rids of the issue, of course, if you really need the reference to be non const, how to proceed? I would like to know what is really going on here, if anyone out there knows, please let me know, I found this link, im still chewing that to understand the implications of what that guy says about the LSB … http://gcc.gnu.org/ml/gcc-patches/2003-07/msg01664.html

I have been busy lately, however, from now on I will try to post at least twice a month. Now I wanted to post about an interesting issue I had at work that is related to endianess and memory alignment. I knew the concept of endianess, but never faced a bug related to it. However, 2 months ago ( yeah, I should have posted this before, but you all know that I am a procrastinator ), we detected a failure in one of our test cases for the ODBC driver to connect to the iSeries. The test case was failing on PowerPC 32 bit architecture only, x86-32bit test was successfull.

So, I logged on via ssh to the test server LPAR and started debugging the problem. I bless gdb and vim, because I did not have to install anything else to debug/develop on site. Finally I found the problem in code similar to this one:

class ConvertHandleToObject {
    /* lots of code here */
    union {
        void* void_ptr;
        TYPE1* type1_ptr;
        TYPE2* type2_ptr;
        TYPE3* type3_ptr;
        struct {
            unsigned free:1;
            unsigned next:31;
        };
    };
};

“free” member was used to denote that the object of class ConvertHandleToObject was available to be used/returned as a handle, but, why share memory space with the actual pointer to the handle object? , and more important why it works in x86 but not at PowerPC?

The reason behind it is memory alignment.

To understand memory alignment we must first introduce “aligned memory access” and “unaligned memory access”. Aligned memory access is when the processor attempts to fetch a data object of size N stored at some memory address that is multiple of N. That is, if we want to access a 32 bit Integer ( 4 bytes ) in aligned fashion, the integer must be stored at memory addresses multiple of 4 (0×04, 0×08 etc), and that’s why access to “char” values are always aligned ( sizeof(char) == 1 ). Unaligned access is the opposite, fetch a dataobject of size N stored at memory address NOT a multiple of N, like fetching a 32bit integer at memory address 0×03. Alignment is important because if the data in your program is aligned, access to data will be faster. Fortunately for us, compilers take care of aligning data. Let’s see an example:

struct aligned {
    long long_data;
    char byte_data;
    int integer_data;
};

This is a classic example of memory alignment. Someone might say that a structure like that has a memory size of sizeof(long) + sizeof(char) + sizeof(int) … that is, 9 bytes for common 32 bit architecture. However if you print sizeof(struct aligned) you will get, most likely, 12 bytes. So where are those 3 bytes of difference? Well, the compiler added 3 bytes of padding to align the “integer_data” member start address. Lets say some structure like this is stored at address 0×00, thus, long_data address is 0×00, byte_data address starts at 0×04 and then, if the compiler ignores alignment requirements, integer_data would start at 0×05, and we would have unaligned memory access when reading integer_data member. Thus, the compiler has added 3 padding bytes, so the aligned struct will be equivalent to:

struct aligned {
    long long_data;
    char byte_data;
    char padding[3];
    int integer_data;
};

If you compare the size of this struct with the size of the previous struct you will find out that both have a 12 bytes length.

Let’s go back to our buggy union. Unions take the alignment of the longest member, in our union the longest element is any of the pointers ( 4 bytes for 32 bit architecture ), thus, the union memory space will be aligned in 4 byte multiples. Those unions were initialized with free = 1; but in the code there were no places where free = 0; The programmer of this code thought that any address aligned in 4 byte multiples will have the last bit set to 0, thus, at any moment a valid pointer was assigned to any of the other union members, the less significant bit at the less significant byte will be zero. Why? well, for the last byte, multiples of 4 in binary are:

00000100 ( 4 )
00001000 ( 8 )
00001100 ( 12 )
00010000 ( 16 )

The code worked well at little endian, confusing code, but it worked. However, at the time of moving this to powerpc ( big endian ) the byte and bit that is assigned to free is no longer the less significant bit and byte, but the most significant, and the code breaks because even when a valid address has been assigned to some pointer in the union, free keeps being 1 ( non free ).

Still with this in mind, I dont quite understand 2 things.

1. The failure was present only in RedHat, not in SuSE. I don’t remember distribution and kernel versions.
2. The failure was present only when launching 2 or more threads.

Somehow allocated memory in SuSE did not hit this issue. When not using threads, RedHat allocations did not hit the issue either. Here are some examples of the memory addresses.

Good:
00010000 00000011 11001000 01100000 ( 0x1003B2D8 )

00010000 00000011 10110010 11011000 ( 0x1003B2D8 )

Bad:

11110110 01100000 00100110 10111000 ( 0xF66026B8 )

Failures started when memory addresses started with F. In little endian, as we see, the memory ended in 8, so, less significant bit was 0 ( setting “free” to zero ), but in big endian the most significant bit was 1, causing the failure.

Conclusion: C/C++ are low level languages, usually you can do funny stuff with hardware. But if it is not necessary don’t do it. The code fix was easy, just move out of the union the free member to not depend on the memory address, and just set free = 0 when the handle was in use.