Tripped on C

Almost right after I got into programming, I fell in love with C++.

Its immensely powerful nature keeps fascinating me day after day, and I’m always hungry to pick up a new piece of C++ wizardry to appreciate.

Now, along the way of appreciating various C++ magic, I’ve also come to learn various things about C, such that static linkage limits function’s scope to its translation unit, a function can be implicitly called without being declared first, and how various pseudo-templates can be produced by employing layers after layers of macro hacks…

It’s great stuff and I love it. But I got carried away. At one point, I thought to myself that though I probably would never fully understand even two-thirds about C++, grasping most of C shouldn’t be that hard. After all, knowing function pointers, bit manipulations, and tricks here and there should be sufficient. Right?

And so, I dared to think I knew C.

But I didn’t (and still don’t). In fact, I didn’t even fully grasp some of the fundamentals. I’ve since then learned a few precious lessons dealing with C and this is here to remind me not to get ahead of myself again.

So I was working on sending some debugging data over the usb from an embedded device to its pc side client. Basically, the routine goes: pc connects to the device’s firmware, sends it a more feature-rich version of the same firmware, and that firmware would then assume control of the device and communicate with the pc client, etc. I was facing some problems; namely, the device itself could have a different version of the firmware than the one we send during usb connection.

For example, in the beginning we could have a data structure that looks like this.

typedef struct SomeDataStruct_t {
    uint32_t version;
    uint32_t length;
    uint32_t someConfigFlag;
    /* more stuff */
} SomeDataStruct;

Now both the pc client and the device firmware understand this structure as they include the same header. Problems, however, could potentially arise if we had a different version of firmware on the device than the one on the pc client, since we would regularly modify this data structure to store information about changes and new features of the firmware. Also, in our build environment, the pc client requires two separate components, one is the core part of the client and the other the slightly more feature-rich version of the firmware. We tend not to update the pc client’s version of the firmware as frequently as we update the device’s firmware.

So later on down the road, while the pc client’s firmware remains unchanged, the device may have a much newer version of the firmware and the structure may now look something like this.

typedef struct SomeDataStruct_t {
    uint32_t version;
    uint32_t length;
    uint32_t someConfigFlag;
    /* more stuff */
    uint32_t newDeviceStatusFlag;
    /* even more stuff */
} SomeDataStruct;

Now, granted that we always add more things into the structure and never take away any, we can assume that the layout from the beginning to the end of the old version remains unchanged. This means the pc client can always at least print out everything correctly until the end of the old version of the structure. Also, we pass the data through a buffer and the size of how much data we pass is determined at run time (like this).

/* length is assigned when we first populate the structure */
SendData(DataType, Destination, dataStruct.length, (uint8_t *)&dataStruct);

This is passed into a buffer whose definition looks like this.

/* buffer size is guaranteed to be greater than dataStruct
 * otherwise, we report an error before transmitting data
 */
typedef struct SomeDataStructBuffer_t {
    uint8_t _[1024];    /* buffer size is 1024 bytes */
} SomeDataStructBuffer;

We would like to simply print out the raw data in hexadecimal onto the screen after we have printed out everything until the end of the old version of the data structure. This way, rather than relinking the pc client with the updated firmware, we can simply examine the raw data (they are mostly all just 32bit unsigned integers, so not that hard to comprehend). To print them out, I figured I could just go through the rest of the data structure by four byte segments.

Ah, Pointer Arithmetic. How hard can it be?

SomeDataStruct *dataStruct;
SomeDataStructBuffer buffer;
GetSomeDataStruct(&buffer);
dataStruct = (SomeDataStruct *)&buffer;

/* print out known contents of the buffer
 * version, length, config, etc.
 */
if (dataStruct->length <= sizeof(SomeDataStruct)
    return;    /* no more data than we already know */

/* print out rest of the data in buffer. */
for (uint32_t *rawData = (uint32_t *)(&buffer + sizeof(SomeDataStruct));
     rawData < (uint32_t *)(&buffer + dataStruct->length);
     ++rawData;)
    printf("%08X\n", *rawData);

Simple, isn’t it?

This code should print out everything the pc client knows about the data structure and if there is more data that the client does not know, it simply prints out the raw data. However, to my surprise, it does not work at all. Instead, when I tested the code with one uint32_t difference in the old and new versions of the structure, it spits out a chunk of data four times bigger than the buffer itself!

To put it precisely, this piece of code does work properly for the known content of the structure. But as soon as it goes past that, it starts to scan through seemingly arbitrary memory space and print out ridiculous large amount of garbage.

I was confused. What could be wrong? I would add the size known by the pc client to the starting address of buffer to get the end of the old version of the structure. Then, I would start from that location, printing out data by four byte chunks until the end of the new version of the structure, which could be obtained by adding the length field to the starting address of the buffer.

So I printed out the sizes of the old and new data structures, the address of the buffer, and the addresses of where the old and new data structures end. I got the following results.

printf("0x%08X", sizeof(SomeDataStructure));
printf("0x%08X", dataStruct->length);
printf("0x%08X", &buffer);
printf("0x%08X", &buffer + sizeof(SomeDataStructure));
printf("0x%08X", &buffer + dataStruct->length);

/* And the results */
Old Struct Size: 0x00000020
New Struct Size: 0x00000024
Buffer Location: 0x01B8000C
Old Struct End : 0x01B8800C
New Struct End : 0x01B8900C

I was utterly shocked. I was confident in my skill of manipulating memory. I thought I knew pointers inside out. So, why this?

First of all, why incrementing 0x20 bytes of an address would result in a 0x8000 byte difference? Or, why incrementing 1 byte would result in an increase of 0x100 bytes?

For three hours I sat on my chair, scratching my head. I couldn’t figure out what went wrong. I even thought of the possibilities of a memory alignment problem as the pc client is built using msvc, whereas the device firmware is built using a proprietary arm compiler. But that can’t be. All the data up to the end of the old data structure was printed out correctly. It’s got to be something else. My confidence was getting shattered. I thought I knew C!

Another hour then passed without much progress. Out of frustration, I decided to convert the difference between the locations of the old and new end of the structure into decimals; just to see what it’s like.  So, 0x1000 became 4096. Wait a minute. 4096, isn’t that 4 kilobytes? There should only be 4 bytes difference between old and new versions of the data structure.

Then it struck me. What happens if you add 1 to a pointer to type int32_t?

int32_t *ptr = 0x00000000;
++ptr;
printf("0x%08X", ptr);    /* prints 0x00000004 */

Yes, the compiler is doing pointer arithmetic here. Incrementing a pointer to type int32_t by 1 means incrementing the pointer to point to the second int32_t type, moving ptr past its old position by sizeof(int32_t) bytes instead of 1 byte.

So, my earlier attempt really worked like this.

for (uint32_t *rawData = (uint32_t *)(&buffer + sizeof(SomeDataStruct));
     rawData < (uint32_t *)(&buffer + dataStruct->length);
     ++rawData;)
    printf("%08X\n", *rawData);
/* This does not work as expected at all!
 * It is equivalent to the following lines.
 */
SomeDataStructBuffer *start = &buffer + sizeof(SomeDataStruct);
SomeDataStructBuffer *end   = &buffer + dataStruct->length;
uint32_t *rawData = (uint32_t *)start;
while (rawData < end) {
    printf("%08X\n", *rawData);
    ++rawData;
}

This code first tells the compiler to point to a SomeDataStructBuffer type in the memory that is sizeof(SomeDataStruct) bytes past the beginning of the buffer. Thus, instead of moving 32 bytes past the beginning of the buffer, it went 32 * sizeof(SomeDataStructBuffer) bytes. Then the compiler reinterpreted this address as an address pointing to a uint32_t type. After that, it would increment the pointer by sizeof(uint32_t) each time it loops, until it reaches the end. The end address is calculated in similar manner as the start address is. Intead of getting an address that is 4 byte away from the start address, it was 4 * sizeof(SomeDataStructBuffer) bytes away; hence the 4 kilobyte difference.

So, how to increment the address properly? It turned out that in order to increment the address by exactly the number of bytes specified, the compiler needed to be informed that a pointer arithmetic was not desired.

for (uint32_t *rawData = (uint32_t *)
                         ((unsigned int)&buffer +
                          (unsigned int)sizeof(SomeDataStruct));
     rawData < (uint32_t *)(&(unsigned int)buffer +
                             (unsigned int)dataStruct->length);
     ++rawData;)
    printf("%08X\n", *rawData);

A few casts were enough. By casting the addresses and sizes to int type, the compiler was informed that simple arithmetic addition here would be sufficient. And so, the compiler obediently did what I commanded, and this piece of code finally worked, printing out exactly that one extra field in hexadecimal.

It really was not a complicated problem. If this were on a school assignment or an exam, I could probably spot it sooner. However, I was not ready, I didn’t foresee the possibility of such problems arising nor could I identify the root cause in a timely manner when it did happen. I vaguely knew the theory, yet I had not the slightest clue what it would look like outside of school and a few fancy articles flowing around on the internet.

Do I now know C slightly better? Indeed. Do I know C? No.

Advertisements

One thought on “Tripped on C”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s