Improving the specification of arithmetic for atomics

In a document to the standards committee of last year I had observed a set of unfortunate inconsistencies in C11’s specification of arithmetic operations for atomics. As you perhaps know such operations can be specified with operators a++ (in the language part) or generic functions atomic_fetch_add(&a, 1) (in the library), but unfortunately the two parts had not been redacted to fit well in all places.

My new document Minimal Suggested Corrigendum for Arithmetic on Atomic Objects will hopefully make it as proposed corrigendum into the next “bugfix” version of the standard, and hopefully this new version will see the light and the end of 2017. It will perhaps not be with the exact words as they are presented, but I think that the text already comes close to what the intent of the committee had been, and to what implementors actually do, anyhow.

Demystify undefined behavior

In discussions about C or other standards (e.g POSIX) you may often have come across the term undefined behavior, UB for short. Unfortunately this term is sometimes mystified and even used to scare people unnecessarily, claiming that arbitrary things even outside the scope of your program can happen if a program “encounters undefined behavior”. (And I probably contributed to this at some point.)

First, this is just crappy language. How can something “encounter” behavior?  It can’t. What is simple meant by such slang is that such a program has no defined behavior, or stated yet otherwise, the standard doesn’t define what to do if such a program reaches the state in question. The C standard defines undefined behavior

behavior, upon use of a nonportable or erroneous program construct or of erroneous data,
for which this International Standard imposes no requirements

That’s it.

Simple examples of undefined behavior in C are out-of-bounds access to arrays or overflow of signed integer types. More complicated cases arise when violating aliasing rules or when access to data races between different threads.

Now we often hear statements like “UB may format your hard drive” or “UB may steal all your money from your bank account” implying somehow that a program that is completely unrelated to my disk administration or to my online banking, could by some mysterious force have these evil effects. This is (almost) complete nonsense.

If UB in a simple program of yours formats your hard drive, you shouldn’t blame your program. No simple application run by an unprivileged user should have such devastating consequences, this would be completely inappropriate. If such things happen, it is your system which is at fault, get you another one.

As an analogy from every-day life, take the idea of locking your house at night, which seems to be the rule in some societies. Sure, if you don’t do that, you make it easier for somebody to sneak into your house and shoot you.   But still, that person would be a murderer, to be punished for that by the law, no sane legal system would acquit such a person or see this as mitigating circumstances.

Now things are in fact different when there is a direct relation between the object of your negligence and the ill-effect that it causes. If you leave your purse on the table in the pub when going to the bathroom, you should take a share in responsibility if it is stolen. Or to come back to the programming context, if you are programming a security sensible application (e.g handling passwords or bank credentials) then you should be extremely careful and stay on well-defined grounds.

When programming in C there are different kinds of constructs or data for which the program behavior then is undefined.

• Behavior can be explicitly declared undefined or implicitly left undefined.
• The error can be detectable or undetectable at compile time.
• The error can be detectable or undetectable during execution.
• Behavior of certain constructs can be undefined by a specific standard to allow extensions.

Unfortunately, people often use UB as an excuse to evacuate questions about certain behavior of their code (or compiler). This is just rude behavior by itself, and you usually shouldn’t accept this. An implementation should have reasons and policies how it deals with UB, otherwise it is just bad, and you should switch to something more friendly, if you may.

There is no reason not to be friendly, and there are many to be.

That is, in our context, once a (your!) code detects that it has a problem it must handle it. Possible strategies are

• abort the compilation or the running program
• return an error code
• report the problem
• define and document the behavior in your own terms

For the first you should always have in mind that the program should be debugable, so you really should use #error or static_assert for compile time errors and assert and abort for run time errors. Also, willingly aborting the program is not the same as having the program crash, see below.

Obviously, the second is only possible if the function in question has an established error return convention and if you can expect users of the function to check for that convention. POSIX has many such cases where the documentation says something like “may” return a certain error code. A C (or POSIX) library implementation that detects such a “may” case and doesn’t react accordingly, is of bad quality.

Reporting detected errors is an important alternative and some compiler implementors have chosen this as their default answer to problems. Perhaps you already have seen gcc’s famous “diagnostic” message

dereferencing pointer ‘bla’ does break strict-aliasing rules

This message supposes that you know what aliasing rules are, and that you also know why it came to that. Observe that it says “does” so the compiler claims to have proven that the aliasing rules are violated, and that the behavior is thus undefined. What the message doesn’t tell, and that is bad, is how it resolves the problem.

The last variant, defining your own stuff, should be handled with extreme care. Not only that what you define must be sensible, you also make a commitment in doing so. You promise your clients that you will follow these new rules in the future and that they may suppose that you will take care of the underlying problem. In most cases, you should leave the definition of extensions to the big players, platform designers or other standards. E.g POSIX defines a lot of cases that are UB for C as such.

As a last alternative, when

• the error is undetectable
• the detection of the error would be too expensive

you should simply let the program crash. The best strategy I know of is to always initialize all variables and always treat 0 as a special value. This may, under rare circumstance deal a tiny bit of performance against security, because on some rare occasions your compiler might not be able to optimize an unused initialization. If you do this, most errors that you will see are dereferences of null pointers.

Dereferencing a null pointer has UB. But modern architecture no how to handle this: they raise a  “segmentation fault” error and terminate the program. This is the nicest failure path that you can offer to your clients, failing anytime, anywhere.

Modern C: Level 2 available

I am pleased to announce the feature completion of Level 2 of my book

Modern C

It deals with most principal concepts and features of the C
programming language, such as control structures, data types,
operators and functions. Its knowledge should be sufficient for an
introductory course to Algorithms, with the noticeable particularity
that pointers aren’t fully introduced here, yet.

As before, the current version of the book can be found at my homepage

Click to access File:ModernC.pdf

and also as before, constructive feedback is highly welcome. Many
thanks to those that already gave such valuable feedback for previous
version.

musl 1.1.5 with full C11 library support

Today, Rich Felker has published the next release of musl the lightweight, standard conforming C library. He says:

different times in C: calendar times

Let’s take the occasion of the change back from DST here in Europe, not in the US, yet, to look how times are handled in C.
The C standard proposes a large variety of types for representing times: clock_t, time_t, struct timespec, struct tm, double and textual representations as char[]. It is a bit complicated to find out what the proper type for a particular purpose is, so let me try to explain this.

The first class of “times” can be classified as calendar times, times with a granularity and range as it would typically appear in a human calendar, as for appointments, birthdays and so on. Some of the functions that manipulate these in C99 are a bit dangerous, they operate on global state. Let us have a look how these interact:

Runtime-constraint violations

Somewhat hidden in Annex K, C11 introduces a new term into the C standard, namely runtime-constraint violations. They offer an important change of concept for the functions that are defined in that annex: if such a function is e.g called with invalid parameters, a specific function (called runtime-constraint handler) is called, that could e.g abort the program, or just issue an error message. This is in sharp contrast to the runtime error handling in the rest of the C standard, where the behavior under such errors is mostly undefined (anything may happen then) or sometimes reported to implementation defined behavior (and thus poorly portable and predictable).

Annex K, obscurely coined “Bounds checking interfaces“, introduces some typedef and a series of replacement functions for many C library functions. The function names in this series are usually derived from the name of the function they replace and by adding the suffix _s to the function name, e.g the function qsort gets a “secure” twin interface called qsort_s, as we have seen in an earlier post.

inline functions as good as templates

I recently started to implement parts of the “Bounds checking interfaces” of C11 (Annex K) for P99 and observed a nice property of my implementation of qsort_s. Since for P99 basically all functions are inlined, my compilers (gcc and clang) are able to integrate the comparison functions completely into the sorting code, just as an equivalent implementation in C++ would achieve with template code.

Capture return codes from library functions

C (and POSIX) library functions often communicate error conditions in a two stage procedure: first the return value of the function is set to a special value (such as 0 for malloc) and then the caller can read the particular error condition from the pseudo-variable errno.

This “traditional” error handling has several disadvantages:

• Code that captures all returns from library functions with conditional code quickly becomes unreadable. Optically such code emphasizes on the error handling part, instead of the normal control flow.
• errno is a fragile thing, and in particular after it has been set by a transient error, it must be reset to 0.

P99 now lets you overload functions with appropriate macros for the error check, and that if an error occurs will either abort execution or throw an error via P99’s P99_TROW.

emulating C11 threads through POSIX threads

This month a new version of the C standard, C11, has been published. It brings much less changes to C than C99 and hopefully it will be adopted more easily than that. But it will probably still take some time until the major compilers implement it.

Some of the changes that it brings are minor and can already be simulated within C99 or by extensions that some compilers implement already. Some of them already are emulated by P99. I’ll probably post about them one of these days.

The most important to me seem to be two optional additions to the C library: threads and atomic operations.