Wandering Thoughts archives

An example of optimizing C in the face of undefined behavior

In my entry about my understanding of modern C undefined behavior I alluded to how modern C created a security vulnerability in the Linux kernel because of variable initialization. Today I feel like showing you roughly the code involved and explaining this, rather than alluding to it indirectly.

We'll start with perfectly functional code:

int func(struct foo *arg)
{
    struct bar *p;

    if (arg == NULL)
        return -EINVAL;
    p = arg->f_p;

[.....]

This works right. Then someone comes along and fiddles with the code a bit:

int func(struct foo *arg)
{
    struct bar *p = arg->f_p;

    if (arg == NULL)
        return -EINVAL;

[....]

In the Linux kernel dereferencing a NULL pointer does not immediately segfault so this code is (sort of) okay as written; if arg is NULL we will read some bit of low memory and then return. Then the optimizing compiler shows up.

The compiler knows that no conforming C program can ever dereference a null pointer; to do so is undefined behavior. Since the code dereferences arg without checking for NULL, the compiler is entitled to assume that arg is never NULL. This makes the if's expression into a constant value (it must always be false) and the whole if can then be eliminated as dead code. Now this function will continue on even if arg is NULL and in the process use whatever it fished out of memory as p (this enables the actual exploit).

This is of course bad code (since you should never dereference potentially NULL pointers). But it would not naturally be fatal; it took a C compiler optimizing code to make it that.

(The exact code is used as an example here if you want to read it. It is somewhat more intricate than my version but not much so.)

Regular expression performance and performance folklore

I've spent a certain amount of time looking into the performance of the regular expression engines in both (some version(s) of) Perl and Python and reading things like Russ Cox's series on regular expressions. Like a lot of other people I've also read a certain amount of general wisdom on regular expression performance out on the Internet.

Here is what my direct experience has convinced me: I have no real idea how a regular expression engine is going to perform in some situation unless I measure it. The performance of regexp engines is only vaguely predictable and to do it well you need to know an uncommon amount about the internals of their implementations. Regexp engines that use very similar or identical RE languages can perform very differently on common things you do (the poster child here is the behavior of Perl versus Python on RE alteration, '|').

All of this makes me very wary of airy Internet pronouncements about how to get fast regular expressions in any particular language (it should be clear that a language-independent prediction is either immediately obvious or completely laughable). These bits of advice may be well researched and thus actually correct or they may be what the author thinks should be the case, and it's often hard to tell which is which.

(Even when they're correct, regular expression engines can and do get changed over time. Hopefully the changes improve performance without any regressions, but you never know.)

I came very close to writing such an entry myself until I came to my senses. That's the other thing that this has convinced me of: I cannot possible write anything about this subject without actually measuring it. Per my aside in a recent entry I should also then archive and publish my measuring program.

(By the way, the other minefield for regexp engine performance is whether you are using them on Unicode data or 'plain bytes'. Many tests, mine included, have traditionally been run on plain bytes; these days Unicode performance is much more interesting and relevant, especially as some environments turn all normal strings into Unicode.)