« Posts under C/C++/Embedded

Pointers in C: Part VII, Being Relaxed About The Strict Aliasing Rule

“I am free, no matter what rules surround me. If I find them tolerable, I tolerate them; if I find them too obnoxious, I break them. I am free because I know that I alone am morally responsible for everything I do.”
― Robert A. Heinlein

The largely unknown “Strict Aliasing Rule” (SAR) has the potential to send tears to the eyes of even the most seasoned C/C++ developers. Why? Because of it, a lot of the code they have written over the years belongs to the realm of “undefined behavior”.

Despite its name, the term “undefined behavior” itself is well-defined by the C language standard: it’s “behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements. Which means anything can happen: your program could randomly crash or even send suggestive emails to your boss.

THE PROBLEM

Let’s start with the code snippet that I used in my original post on SAR:

Here, data that has been received into a buffer (‘data’) is converted into a high-level data structure (‘measurements’). From the compiler’s point of view, what ‘data’ refers to is just a single ‘uint8_t’ but we access it through a pointer to type ‘struct measurements_t’. What we’ve got here is a clear violation of SAR, which entails undefined behavior.

SAFE ALTERNATIVES

“But, Ralf”, you might respond, “this can’t be true. I write code like this every day and it works flawlessly, even in safety-critical systems like medical devices!”

This doesn’t surprise me in the least. “Undefined behavior” can — get this — also mean “works flawlessly”. But there are no guarantees, whatsoever. It might work on one platform, with a particular compiler or compiler version, but might fail on another platform, or with a different compiler version. Hence, to err on the truly safe side (which you should, especially if you work on safety-critical systems), you should use truly safe alternatives.

One obvious and time-proven approach is to do such so-called type punning through unions. It works by storing data via a member of one type and reading it via another member of a different type:

The receiving function would store byte-wise into the ‘receive_buffer.data’ array, while high-level functions would use the ‘receive_buffer.measurements’ member. This will work reliably in any version of C, but it might fail in C++.

Bulletproof type-punning, one that works in both, C and C++, uses ‘memcpy’. ‘memcpy’!? ‘memcpy’, that’s right:

Believe it or not, there’s a high probability that your compiler will optimize-out the call to ‘memcpy’. I’ve observed this, among others, with ‘gcc’ and ‘clang’, but I’ve also seen compilers always call ‘memcpy’, even for the smallest amounts of data copied, regardless of the optimization level used (Texas Instruments ARM C/C++ compiler 19.6, for instance). Nevertheless, this is my go-to type-punning technique these days, unless performance is paramount. (You first have to prove that your code really impacts overall performance by profiling. Otherwise, your optimizations are like buying Dwayne Johnson an expensive hair brush — it doesn’t really harm, but it’s not of much use, either.)

BUT I REEELLY, REEELLY MUST USE CASTS

Sometimes, you have to use SAR-breaking casts, if only to maintain social peace in your team. So how likely is it that your compiler will do something obscene?

VERY unlikely, at least in this example. Let me explain.

First of all, compiler vendors know that most developers either haven’t heard about SAR or at least don’t give a foo about it. Therefore, they usually don’t aggressively optimize such instances. This is particularly true for compilers that are part of toolchains used in deeply (bare-metal) embedded systems. However, ‘gcc’ as well as ‘clang’, which are used in all kinds of systems, take advantage of SAR from optimization level 2 on. (You can explicitly disable SAR-related optimizations regardless of the optimization level by passing the ‘-fno-strict-aliasing’ option.)

Second, what ‘convert’ is doing is pretty much well-behaved. Sure, it aliases the ‘data’ and ‘measurements’ pointers, but it never accesses them concurrently. Once the ‘measurements’ pointer has been created, the ‘data’ pointer is not used anymore. If the caller (or the whole call-chain) are equally well-behaved, I don’t see a problem (don’t trust me!).

Third, there’s no aliased read/write access. Even if ‘data’ and ‘measurements’ were used concurrently, it wouldn’t be a problem, as long as both are only used for reading data (don’t trust me on this one, either!). By contrast, this I consider harmful:

To the compiler ‘data’ and ‘measurements’ are two totally unrelated pointers to unrelated memory areas. The original value of ‘data[0]’ might be cached in a register and not refetched from memory, hence the ‘assert’ might fail. In general, this is what will most likely happen when SAR is violated in contexts where it does matter: instead of suggestive emails being sent to your boss, you are much more likely got get stale values (which of course could lead to crashes later on).

NO PUN INTENDED

Let’s get real about SAR. Here are some relaxed, pragmatic rules on how to deal with the Strict Aliasing Rule:

0. Fully understand SAR
1. Try hard to adhere to SAR
2. Type-pun using ‘memcpy’
3. If you can’t, disable SAR-related compiler optimizations
4. If you can’t, avoid concurrent, aliased read/write access

But don’t assume that just because you didn’t get a ticket for speeding in the past, you will never ever get a ticket for speeding. What you’re doing is against the law. If you get busted someday, don’t whine and don’t complain I didn’t warn you. Rather own your failures and move on.

Breakin’ rocks in the hot sun
I fought the law and the law won
I fought the law and the law won
I USED SOME CASTS FOR TYPE PUN
I fought the law and the law won
I fought the law and the law won

(with apologies to Sonny Curtis)

Bug Hunting Adventures #14: Bitmap [BM]adness (Solution)

It’s a given fact of life that something that’s deemed totally safe in one environment may be totally unsafe in another. Every German who has ever used an American sauna knows what I’m talking about.

Similar (but far less embarrassing!) traps lurk in situations where you reuse perfectly working C++ code in a C environment. Some time ago, I integrated a little home-grown C++ library into a plain C project. However, instead of the expected, proven functionality I got plenty of core dumps. After some assembly-level debugging, I came to the conclusion that I had found a compiler bug. Code along these lines

was compiled to this:

Why the heck did the compiler insert an offset of 4 instead of 1?

The answer to this question, which is also the answer to our bug hunting adventure, can be found here.

Bug Hunting Adventures #14: Bitmap [BM]adness

“What’s the meaning of goodness if there isn’t a little badness to overcome?”
― Anne Revere

The code below is part of a C graphics processing library, which parses data in the venerable bitmap (BMP) file format. A bitmap file consists of a two parts: a header and the pixel data block. More specifically, a bitmap file is laid-out like this:

Offset Size Content
0 1 Character ‘B’
1 1 Character ‘M’
2 4 Size of the bitmap file
6 4 Reserved
10 4 Offset to the first byte of the pixel data (ofs)
14 n Info block
ofs m Pixel data

All multi-byte integer values (like the bitmap file size and the offset to the pixel data) are stored in little-endian format.

The function ‘bmp_pixel_data’ takes a pointer to a bitmap file data and returns a pointer to the bitmap’s pixel data area within the bitmap. The size of the pixel data area is returned via the ‘size’ out parameter. In case the provided bitmap file data is malformed, a NULL pointer is returned and the ‘size’ out parameter is set to zero.

As always, the code compiles cleanly without warnings (at ‘-W -Wall’), but when the function ‘bmp_pixel_data’ was put to use, it failed miserably. Where did the programmer goof?

Solution

Bug Hunting Adventures #13: Prime Sums (Solution)

The challenge suffers from what I call a “chain of blunders”, where one blunder leads to another. Here are the exact details, in the traditional format.

The first who got close to the true nature of this bug was reader Shlomo who commented directly on the post, but I held back his comment in order not to spoil the fun for others. (Unfortunately, I couldn’t tell him, because he used a bogus email address—boo!). Christian Hujer, hacker extraordinaire, gave the most precise and extensive account on LinkedIn. While many found the blunder in the Makefile (Joe Nelson was the first), it was apparently such a good smokescreen that many people didn’t look any further. To me, the root blunder that started the chain of blunders is in the C language itself, which should have never allowed implicit zero-initialization of constants in the first place (which was corrected in C++).

Some believed that the preincrement of the loop-counter was the culprit as it would skip the first prime, but that’s not the case. The expression after the second semicolon gets evaluated always at the end of the loop body:

is equivalent to

Substitute ++i or i++ for <e> — there’s no difference!

On a general note, guys, please register by entering your email address in the top right corner to ensure that you will get automatic notifications for new posts as soon as they’re published. I also (usually) announce new posts on LinkedIn, but mostly hours if not days later. Nevertheless, connecting with me on LinkedIn is always a good idea and highly encouraged. Your subscriptions, likes, praise, and criticism keep me motivated to carry on, so don’t hold back!

Bug Hunting Adventures #13: Prime Sums

“Why, yes; and not exactly that either. The fact is, we have all been a good deal puzzled because the affair is so simple, and yet baffles us altogether.”
― Edgar Allan Poe, The Purloined Letter

Below, you find a little C project that doesn’t do what it’s supposed to do, namely print the sum of the first 10 prime numbers. The program builds cleanly with gcc and clang; that is, without any warnings even when using -Wextra -Wall -pedantic -ansi as compiler options. It’s well-formed and doesn’t crash.

What’s the root cause of this bug? What’s the output of the program? Here are the files, you can also find them on GitHub:

prime_table.h:

prime_table.c:

prime_sum.c:

Makefile:

Solution

const_map, anyone?

Today, I want to share a little C++ container class with you that has proved useful over the years: const_map. I finally got around to turning it into something reusable, or so I hope. Special thanks go to John Hinke, who provided awesome feedback.

In simple words, const_map is an associated array, just like good ol’ std::map: a mapping from keys to values which allows you to lookup values by keys:

Contrary to std::map, however, const_map is a read-only container. To set it up, you provide a key/value mapping table to the constructor:

Once a const_map is instantiated, it’s not possible to add or remove key/value pairs anymore:

Just like std::map, const_map’s runtime is O(log(n)). Contrary to std::map, the implementation isn’t based on binary trees but on binary search. Hence, the mapping table must be sorted by key in ascending order.

const_map doesn’t do any heap allocations. All it does is maintain two pointers: one to the beginning and another one to the end of the mapping table. Apart form these two pointers, const_map doesn’t need any other state or housekeeping data. Thus, on a 32-bit platform, const_map instances will cost you eight measly bytes of RAM.

Now, I know there are some embedded cheapskates out there to whom even eight bytes is sometimes too big a sacrifice. If you’re so tight on RAM and are willing to forgo the fancy STL-like interface and rather expend a little bit more typing, you can use the static class member function ‘lookup’ which is completely stateless and doesn’t require an instance:

I’ve mostly used const_map as a replacement for long, unwieldy switch-case abominations. Either to translate values from one data type to another or to determine which action to take based on a given value. In the latter case, my value type was a function pointer or functor.

Share and enjoy!