A GCC Compiler Mistake

“Most of the evil in this world is done by people with good intentions.”
— T.S. Eliot

Errors, defects, bugs, blunders — when we talk about software-related errors, we often use terms loosely and synonymously — but there are differences. For instance, in his book “The Design of Everyday Things“, Donald A. Norman makes a clear distinction between “mistakes” and “slips”:

“Errors come in several forms. Two fundamental categories are slips and mistakes. Slips result from automatic behavior, when subconscious actions that are intended to satisfy our goals get waylaid en route. Mistakes result from conscious deliberations.”

In short: mistakes are the result of faulty ideas whereas slips are errors made when implementing an idea. Usually, slips are not just easy to make, but also easy to fix. Fixing mistakes is typically much harder.

One of the easiest slips to make in C/C++ is to inadvertently do a boolean test on an assignment expression:

which is equivalent to:

While in some rare cases this is exactly what the developer had in mind, in 99% of all cases it’s not. Hence, boolean-testing assignments is explicitly banned by many C/C++ coding standards and frowned-upon by most developers.

But what’s all the fuzz about, you might ask. If an unlucky developer forgets to type the second ‘=’, any decent 21st century compiler surely generates a warning, doesn’t it? Well, the answer is, as we shall see, both, yes and no.

If you compile the example above with GCC (I’ve tried version 5.4.0) using options ‘-W -Wall’, you do get a warning:

warning: suggest parentheses around assignment used as truth value

GCC’s reasoning is this: if developers really wanted to truth test the assignment (there are still people out there who do, as strange as this may sound), they need to put an extra pair of parentheses around the assignment, to show their intend:

Requiring an extra set of parentheses seems to be a neat idea, but it’s the devil in disguise. For one thing, it reminds me of Sledge Hammer saying “Trust me, I know what I’m doing” (which was usually entailed by disaster), for another, it doesn’t work reliably. In order to explain, I first need to put the same slip in a slightly more complicated expression:

In this case, you not just get a warning, your compiler will refuse to compile this code. Why? According to C’s precedence rules, the assignment operator has lower priority than the ‘&&’ operator, which means that the code is equivalent to

The C language standard says that the result of an ‘&&’ expression is a so-called “rvalue” and an rvalue is more or less read-only. Thus, assigning ‘d’ to it is just not possible and GCC is right when it barks:

error: lvalue required as left operand of assignment

A slip that doesn’t compile is a kind slip, you might think, but read on. We only got lucky by accident, so to speak.

Many coding standards, like MISRA, for instance, require that you put parentheses around subexpressions to clearly show what precedence you have in mind, instead of relying on obscure operator precedence rules. Hence, instead of

you have to write

MISRA exists to make coding errors unlikely, but if a MISRA-abiding developer forgets the second ‘=’, he’s out of luck, at least if he’s using GCC:

Now the devil reveals himself: since the parentheses are properly placed, there is no attempt to assign to an rvalue, so there won’t be a compile-time error and because of GCC’s “parentheses feature” mentioned above, GCC doesn’t issue a warning, either.

Early in my career as a software developer, I read the aforementioned book “The Design of Everyday Things” and I believe it left a mark on me. One of the book’s unforgettable key lesson is this:

“When you have trouble with things — whether it’s figuring out whether to push or pull a door or the arbitrary vagaries of the modern computer and electronics industry — it’s not your fault. Don’t blame yourself: blame the designer.”

GCC’s “extra parentheses” feature is far from neat design — it’s rather bad design that doesn’t work in all contexts and gives developers a false sense of security. It was deliberately put in and correctly implemented but the idea was wrong from the outset. Thus, it’s not a slip, but obviously a mistake.

Dangerously Confusing Interfaces IV: The Perils of C’s “safe” String Functions

“It ain’t what you don’t know that gets you into trouble. It’s what you know for sure that just ain’t so.”
–Mark Twain

Buffer overflows are among the most frequent causes of security flaws in software. They typically arise in situations such as when a programmer is 100% certain that the buffer to hold a user’s name is big enough — until a guy from India logs in. Thus, well-behaved developers always use the bounded-length versions of string functions. Alas, they come with differing, dangerously confusing interfaces.

THE GOOD

Let’s start with ‘fgets‘:

No matter what users type into their terminals, ‘fgets’ will ensure that ‘user_name’ is a well-formed, zero-terminated string of at most 29 characters (one character is needed for the ‘\0’ terminator). The same goes for the ‘snprintf‘ function. After executing the following code

‘buffer’ will contain the string “The”, again, properly zero-terminated.

Both functions follow the same, easy-to-grasp pattern: you pass a pointer to a target buffer as well as the buffer’s total size and get back a terminated string that doesn’t overflow the buffer. Awesome!

THE BAD

In order to copy strings safely, developers often reach for ‘strncpy‘ to guard themselves against dreaded buffer overruns:

Unfortunately, this is not how ‘strncpy’ works! We assumed that it followed the pattern established by ‘fgets’ and ‘snprintf’ but that’s not the case. Even if ‘strncpy’ promises that it never overflows the target buffer, it doesn’t necessarily zero-terminate it. What it does is copy up to ‘sizeof(buffer)’ bytes from ‘user_name’ to ‘buffer’ but if the last byte that is copied is not ‘\0’ (i. e. ‘user_name’ comprises more than ‘sizeof(buffer)’ characters), ‘strncpy’ leaves you with an untermiated string! A traditional approach to solve this shortcoming is to enforce zero-termination by putting a ‘\0’ character as the last element of the target buffer after the call to ‘strncpy’:

Using ‘strncpy’ without such explicit string termination is almost always an error — a rather insidious one, as your code will work most of the time but not when the buffer is completely filled (i. e. your Indian colleague “Villupuram Chinnaih Pillai Ganesan” logs on).

Boy, oh boy is this inconsistent! ‘fgets’ and ‘snprintf’ give you guaranteed zero-termination but ‘strncpy’ doesn’t. A clear violation of the principle of least surprise. Apparently, ‘strncpy’ fixes one safety problem and at the same time lays the foundation for another one.

THE UGLY

Can it get worse? You bet! How do you think ‘strncat‘, the bounded-length string concatenation function, behaves? Ponder this code:

But this is wrong, of course: the third argument to ‘strncat’ (let’s call this argument ‘n’) is not the size of the target buffer. It is the maximum number of characters to copy from the source string (‘string2’) to the destination buffer (‘buffer’). If the length of the source string is greater or equal to ‘n’, ‘strncat’ copies ‘n’ characters plus a ‘\0’ to terminate the target string. Confused? Don’t worry, here’s how you would use it to avoid concatenation buffer overruns:

Yuck! What’s the likelihood that people remember this correctly?

THE REMEDY

Even if the different interfaces and behaviors of the bounded-length string functions in the C API make sense for certain use cases (or made sense at some point in time), the upshot is that they confuse programmers and potentially lead to new security holes when in fact they were supposed to plug them. What’s a poor C coder supposed to do?

As always, you can roll your own versions of bounded/safe string functions or use my safe version of ‘strcpy’. If you rather prefer something from the standard library, I’d suggest that you use ‘snprintf’ as a replacement for both, ‘strncpy’ and ‘strncat’:

Looks like ‘snprintf’ is the swiss army knife of safe string processing, doesn’t it? The moral is this: use whatever you’re comfortable with, but refrain from using ‘strncat’ or ‘strncat’ directly.

More dangerously confusing interfaces…

Playgrounds Revamped

“Play is the highest form of research.”
— Albert Einstein

Many years ago, I wrote about the importance of having playgrounds, that is, easy-to-access try-out areas for carrying out programming-related experiments with the overall goal of exploring and learning.

Recently, I’ve reworked my C++ playground and uploaded it to GitHub. Compared to my previous C++ playground, the new one comes with the following major advantages:

  1. Shared access to playgrounds from multiple computers — since it is based on a Git repository.
  2. Every experiment has its own subdirectory — the top-level playground directory stays clean and clearly arranged.
  3. Unit test support through Google Test — running ‘make’ not just builds the experiment but also executes contained unit tests.

Once cloned and installed, you can start a new experiment is this:

‘pg-setup’ will create a directory called ‘init_within_loop_body’ along with a ‘Makefile’ and a ‘init_within_loop_body.cpp’ source file. Plus, if you have defined your ‘EDITOR’ environment variable properly, it will open ‘init_within_loop_body.cpp’ in your favorite editor for you. All that’s left to do is add your experiment’s code to the testcase template:

Now, just type/execute ‘make’ (either from within your editor or from the command-line) and your code will be compiled and run:

Pointers in C, Part II: CV-Qualifiers

“A teacher is never a giver of truth; he is a guide, a pointer to the truth that each student must find for himself.”
— Bruce Lee

In part I of this series, I explained what pointers are in general, how they are similar to arrays, and — more importantly — where, when, and why they are different to arrays. Today, I’ll shed some light on the so-called ‘cv qualifiers’ which are frequently encountered in pointer contexts.

CV-QUALIFIER BASICS

CV-qualifiers allow you to supplement a type declaration with the keywords ‘const’ or ‘volatile’ in order to give a type (or rather an object of a certain type) special treatment. Take ‘const’, for instance:

‘const’ is a guarantee that a value isn’t (inadvertently) changed by a developer. On top of that, it gives the compiler some leeway to perform certain optimizations, like placing ‘const’ objects in ROM/non-volatile memory instead of (expensive) RAM, or even not storing the object at all and instead ‘inline’ the literal value whenever it’s needed.

‘volatile’, on the other hand, prevents optimizations. It’s a hint to the compiler that the value of an object can change in ways not known by the compiler and thus the value must never be cached in a processor register (or inlined) but instead always loaded from memory. Apart from this ‘don’t optimize’ behavior, there’s little that ‘volatile’ guarantees. In particular — and contrary to common belief — it’s no cure for typical race condition problems — It’s mostly used in signal handlers and to access memory-mapped hardware devices.

Even if it sounds silly at first, it’s possible to combine ‘const’ and ‘volatile’. The following code declares a constant that shall not be inlined/optimized:

Using both ‘const’ and ‘volatile’ together makes sense when you want to ensure that developers can’t change the value of a constant and at the same time retain the possibility to update the value through some other means, later. In such a setting, you would place ‘MAX_SENSORS’ in a dedicated non-volatile memory section (ie. flash or EEPROM) that is independent of the code, eg. a section that only hosts configuration values*. By combining ‘const’ and ‘volatile’ you ensure that the latest configuration values are used and that these configuration values cannot be altered by the programmer (ie. from within the software).

To sum it up, ‘const’ means “not modifiable by the programmer” whereas ‘volatile’ denotes “modifiable in unforeseeable ways”.

CV-QUALIFIERS COMBINED WITH POINTERS

Like I stated in the intro, cv-qualifiers often appear in pointer declarations. However, this poses a problem because we have to differentiate between cv-qualifying the pointer and cv-qualifying the pointed-to object. There are “pointers to ‘const'” and “‘const’ pointers”, two terms that are often confused. Here’s code involving a pointer to a constant value:

Since the pointer is declared as pointing to ‘const’, no changes through this pointer are possible, even if it points to a mutable object in reality.

Constant pointers, on the other hand, behave differently. Have a look at this example:

The takeaway is this: if the ‘const’ keyword appears to the left of the ‘*’, the pointed-to value is ‘const’ and hence we are dealing with a pointer to ‘const’; if the ‘const’ keyword is to the right of the ‘*’, the pointer itself is ‘const’. Of course, it’s possible to have the ‘const’ qualifier on both sides at the same time:

The same goes for multi-level pointers:

Here, ‘v’ is a regular (non-‘const’) pointer to ‘const’ pointer to a pointer to a ‘const’ integer.

Yuck! Sometimes, I really wish the inventors of C had used ‘<-‘ instead of ‘*’ for pointer declarations — the resulting code would have been easier on the eyes! Consider:

versus

So

would read from right to left as “v is a POINTER TO const POINTER TO const int”. Life would be some much simpler… but let’s face reality and stop day-dreaming!

Everything I said about ‘const’ equally applies to pointers to ‘volatile’ and ‘volatile’ pointers: pointers to ‘volatile’ ensure that the pointed-to value is always loaded from memory whenever a pointer is dereferenced; with ‘volatile’ pointers, the pointer itself is always loaded from memory (and never kept in registers).

Things really get complicated when there is a free mix of ‘volatile’ and ‘const’ keywords with pointers involving more than two levels of indirection:

Let’s better not go there! If you are in multi-level pointer trouble, remember that there’s a little tool called ‘cdecl‘ which I showcased in the previous episode. But now let’s move on to the topic of how and when cv-qualified pointers can be assigned to each other.

ASSIGNMENT COMPATIBILITY I

Pointers are assignable if the pointer on the left hand side of the ‘=’ sign is not more capable than the pointer on the right hand side. In other words: you can assign a less constrained pointer to a more constrained pointer, but not vice versa. If you could, the promise made by the constrained pointer would be broken:

If the previous statement was legal, a programmer could suddenly get write access to a read-only variable:

Again, the same restrictions hold for pointers to ‘volatile’. In general, pointers to cv-qualified objects are more constrained than their non-qualified counterparts and hence may not appear on the right hand side of an assignment expression. By the same token, this is not legal:

ASSIGNMENT COMPATIBILITY II

The rule which requires that the right hand side must not be more constrained than the left hand side might lead you to the conclusion that the following code is perfectly kosher:

However, it’s not, and for good reason, as I will explain shortly. But it’s far from obvious and it’s a conundrum to most — even seasoned — C developers. Why is it possible to assign a pointer to non-const to a pointer to ‘const’:

but not a pointer to a pointer to non-const to a pointer to a pointer to ‘const’?

Here is why. Imagine this example:

Graphically, our situation is this. ‘ppc’ points to ‘p’ which in turn points to some random memory location, as it hasn’t been initialized yet:

Now, when we dereference ‘ppc’ one time, we get to our pointer ‘p’. Let’s point it to ‘VALUE’:

It shouldn’t surprise you that this assignment is valid: the right hand side (pointer to const int) is not less constrained than the left hand side (also pointer to const int). The resulting picture is this:

Everything looks safe. If we attempt to update ‘VALUE’, we won’t succeed:

But we are far from safe. Remember that we also (indirectly) updated ‘p’ which was declared as pointing to a non-const int and ‘p’ was declared as pointing to non-const? The compiler would happily accept the following assignment:

which leads to undefined behavior, as the C language standard calls it.

This example should have convinced you that it’s a good thing that the compiler rejects the assignment from ‘int**’ to ‘const int**’: it would open-up a backdoor for granting write access to more constrained objects. Finding the corresponding words in the C language standard is not so easy, however and requires some digging. If you feel “qualified” enough (sorry for the pun), look at chapter “6.5.16.1 Simple assignment”, which states the rules of objects assignability. You probably also need to have a look at “6.7.5.1 Pointer declarators” which details pointer type compatibility as well as “6.7.3 Type qualifiers” which specifies compatibility of qualified types. Putting this all into a cohesive picture is left as an exercise to the diligent reader.

________________________________
*) Separating code from configuration values is generally a good idea in embedded context as it allows you to replace either of them independently.

The Right to Choose

Shame on me! For the first time in a decade, I forgot to celebrate Towel Day. The fact that my towel proved so incredibly useful a couple of days earlier makes me feel even guiltier.

Douglas Adams is admired by most of his fans because he was not just tremendously funny, but also a shrewd freethinker who loved to show people how limited and simple-minded their views and beliefs are (anyone remember the Total Perspective Vortex?). But actually, he himself had his eyes opened one day by another person: in an interview with BBC, Douglas Adams disclosed that one of the most influential, eye-opening books he had read was “The Blind Watchmaker” by Richard Dawkins.

In his book, Richard Dawkins demonstrates that by Darwin’s Theory of Evolution and natural selection enormous complexity can arise out of even the simplest building blocks and that there really is no need for a Creator. Douglas Adams and Richard Dawkins were so like-minded that it’s no wonder they later became close friends.

At the end of one of his talks, Richard Dawkins presents a slide titled “The Illogic of Default”, which demonstrates the ill-reasoning of many Creationists:

1. We have theory A and theory B
2. Theory A is supported by loads of evidence
3. Theory B is supported by no evidence at all
4. I can’t understand how theory A explains X
5. Therefore theory B must be right

This exactly describes what happend to me one day when a muslim taxi driver tried to “prove” to me that there indeed must be a god. “See”, he said, “the theory of evolution just can’t be right. If we humans are really decedents of animals like apes and dogs, why are there still apes and dogs around?”.

I refrained from arguing with my taxi driver, even though it was obvious that he didn’t understand the Theory of Evolution at all. How could I resist the temptation?

I absolutely admire Richard Dawkins for his wit and I recommend that you watch all of his Youtube talks and videos, but there is a problem with atheists like him: sometimes, they are just as annoying as followers of any other conviction when they try to foist their views on others. Even if we know that Creationist’s arguments are utterly wrong from a logical and scientific point of view, it doesn’t help: it’s a documented fact that a significant part of humankind has a strong desire for spirituality. And, as we all know, whenever strong desires are involved, appealing to logic doesn’t work: drug addicts do know that drugs ultimately kill them but they nevertheless don’t quit.

Likewise, deep in their hearts, many believers in god assume that there is no god, at least not one like the one that is depicted in the holy scriptures, but they need a god for their mental well-being, anyway. Trying to prove to them that there is no Creator is a) futile and b) hurts them — not physically but emotionally. This is why I didn’t argue with the taxi driver. I strive to follow the Golden Rule, which — incidentally — also appears in many holy scriptures: always treat others the way you want to be treated.

So why I and many other people prefer to have their eyes opened, others don’t. Everybody should be free to choose the color of the pill they take.

Pointers in C, Part I: Pointers vs. Arrays

“Remember, When You Point a Finger at Someone, There Are Three More Pointing Back at You”
— Unknown

It’s easy to meet even long-time C programmers who don’t fully grok pointers, let alone beginners. Because of this and the fact that pointers play such a crucial role in the C programming language, I’ve decided to launch a new series of blog posts on pointers. I want to start off with an episode that sheds some light on similarities and — more importantly — differences between pointers and arrays.

POINTERS AND ARRAYS: THE BASICS

An array is a sequence of same-sized objects, integers, for instance:

On a big-endian machine, ‘array’ could be stored like this (that it starts at memory address 0xB00010 is just an example):

The compiler (or rather the linker) places the array at a fixed memory location. Thus, When you think array, think memory.

By contrast, a pointer is an object that holds a memory address. Pointers are used to refer to memory where an object of a specific type (like ‘int’) resides.

Pointers are used for flexibility: you can refer to another object at run-time by changing the memory address stored inside the pointer variable:

A pointer introduces a level of indirection: in order to access the actual object it refers to (and not the pointer variable itself), you dereference it:

DIRECT ACCESS VS. INDIRECT ACCESS

The crucial difference between pointers and arrays is how memory is accessed. For instance, when you retrieve the first array element:

the compiler generates code along these lines:

1. Load address of beginning of array into register A
2. Load data at address stored in A into register B

Whereas when you fetch the first array element via a pointer pointing to it:

The generated code will access memory indirectly very much like this:

1. Load address of pointer into register X
2. Load data at address in register X into register Y
3. Load data at address in register Y into register B

So as you can see, pointers and arrays use different ways to access memory and hence are fundamentally different beasts.

WHEN POINTERS LOOK LIKE ARRAYS AND VICE VERSA

Nevertheless, there are cases where pointers and arrays appear to be same thing.

The C language comes with a little bit of syntactic sugar. In certain situations you can use an array like you would use a pointer:

This looks like you are dereferencing a pointer named ‘array’, but looks can be deceiving. What this really compiles to is this:

Why? According to the C language standard, in expressions, the name of an array acts as a pointer to the first array element. Hence, the compiler really sees this:

which is equivalent to

Similarly, you can dereference pointers not just by using the ‘*’ operator but also by using the subscript operator [], which is another form of syntactic sugar — one that makes you believe you are accessing an array instead of a pointer:

All this syntactic sugar makes C code involving pointers and arrays easier on the eyes — the compiler will do some access magic behind the scenes. The downside is, that it deludes people into believing that pointers and arrays are the same, which is not the case: arrays employ direct access, pointers indirect access.

Contrary to expressions, such syntactic sugar is not available in declarations. If you define an array in one translation unit (file):

and foolishly attempt to import it into another translation unit via this forward declaration:

you risk a crash because dereferencing ‘VALUES’ will indirectly access memory when a direct access was required. Let’s assume that the array is stored like this, as defined in the first translation unit:

Now, dereferencing ‘VALUES’ declared as a pointer will lead to these steps:

1. Load address of pointer ‘VALUES into register X (X = 0x00B00210)
2. Load data at address in register X into register Y (Y = 0x00001111)
3. Load data at address in register Y into register B (B = ???)

What this means in practice depends on whether the address 0x00001111 is a valid address or not. If it is, arbitrary data will be read; otherwise, the memory management unit (MMU) will raise an exception. Therefore, make sure that your array declarations exactly match your definitions:

PASSING ARRAYS TO FUNCTIONS

So far so good (or bad). Another source of confusion is the fact that arrays are the only objects in C that are implicitly passed by reference:* You always provide a pointer to the first array element to get an array into a function:

At the caller’s site, the code looks like this:

TYPE-SAFETY THAT ISN’T

Sometimes, you want to ensure at compile-time, that only arrays of certain sizes can enter your function. Imagine you have a function that builds a 128-bit random value in an array of eight bytes:

‘get_random’ assumes that it is passed the address of eight bytes of memory, but nobody prevents the caller from passing an array that is not big enough:

Which will — of course — lead to a dreaded buffer overrun.

Is it possible to make ‘get_random’ type-safe, such that arrays with a length different to eight lead to compile-time errors?

One (ill-fated) approach is to employ a C feature that allows you to declare arguments using array-like notation:

However, this doesn’t give you any extra type safety. To the compiler, ‘random’ is still a pointer to a ‘uint8_t’ and if you ask for the size of ‘random’ (via sizeof(random)) in the body of the function, you will still get the value returned by sizeof(uint8_t*). Few developers are aware of this fact. To me, it’s a source of nasty bugs.

Since this array-ish syntax fools people into believing that a real array was passed to a function (by value) I don’t recommend using it.

TYPE-SAFETY DONE RIGHT

You can get real type-safety for your “array” arguments through so-called “pointers to arrays”. Alas, this C feature tends to confuse the heck out of programmers.

In the previous examples, we passed an array (conceptually) by passing a pointer to the first element:

The real type of the array and the size of the array is lost in this process; the called function only sees a pointer to a ‘uint8_t’. By contrast, the following syntax allows you to obtain a pointer to an array that preserves the full type information:

This ‘pointer’ is completely type-safe:

To add type-safety to our ‘get_random’ function, we could define it like this:

With this change, ‘get_random_type_safe’ only accepts pointers to 8 element arrays of uint8_t’s. Passing any other kind of pointer will result in a compile-time error.

We know that in expressions, using an array’s name like ‘array’ is short for “pointer to first element in array” but that doesn’t mean that ‘&array’ is a pointer to a pointer to the first element — the ‘&’ operator doesn’t create another level of indirection, even though it looks like it did. In the previous example, the value stored in ‘pointer’ is still the address of the first element of the array. Hence, this assertion holds:

Since the actual pointer values are the same, you can still use legacy APIs that only accept pointers to ‘uint8_t’s (like the original ‘get_random’ function), if you apply type casts:

You don’t need typedefs like ‘RANDVAL’ if you want to employ pointers to arrays. I mainly used it to avoid overwhelming you with the hideous pointer-to-array syntax. Without typedefs, you would need to type in things like this:

The syntax to declare pointers to arrays is similar to the syntax to declare pointers to functions and takes a little getting used to. If in doubt, ask the Linux tool ‘cdecl’ which is also available online:

Do I recommend using pointers to arrays? No, at least not in general. It confuses way too many developers and leads to ugly casts in order to access plain pointer interfaces. Still, pointers to arrays make sense every now and then and it’s always good to know your options.

This concludes my first installment on pointers. There is more to come. Stay tuned!

________________________________

*) The language designers of C believed that passing an array by value (e. g. as a copy via the stack) would be extremely inefficient and dangerous (think: stack overflow), so there is no direct way to do it. However, they were not so fearful regarding structs (which can also get quite large and overflow the stack), so you could pass an array by value if you wrapped it inside a struct: