Integer Overflow and An Inverted Spin-Lock

Returning to writing code to aggravate the race condition in my previous entry, I've had a couple interesting developments.

First, I did in fact end up deciding to recompile DTrace with a higher chill() limit. However, I couldn't increase it by much. The limit for how long a chill() can last for is defined in usr/src/uts/common/dtrace/dtrace.c, and is stored as an hrtime_t called dtrace_chill_max:

hrtime_t dtrace_chill_max = 500 * (NANOSEC / MILLISEC); /* 500 ms */

An hrtime_t is a 64-bit time value, so at first thought, it would be easy to make the time limit quite large - if not for the fact that the C preprocessor expands the expression above before compiling, and simplifies it. Why would this cause a problem? Because due to the units in which the time limit is stored, this expression comes out to 500,000,000. Multiplying this value by 4 pushes near the maximum value of a signed 32-bit integer. And guess what types the preprocessor uses to do this multiplication?

I wanted a much wider window than possibly two seconds (which seems wide enough, but somehow it is not). Rather than tangle with the C preprocessor's notion of types, or dig deeper into the DTrace code, I decided to try a somewhat more unorthodox approach. I'm not accustomed to being tasked with writing code to aggravate timing bugs, so I was unsure of how much I could play with the code in the area surrounding the problem and fix before it was considered undesirable for demonstrating the bug. The locator of this bug (and many similar bugs) told me that it was acceptable to change the timing of the code I was playing with, as long as I did not affect the semantics. So I used a combination of nanosleep() calls in my test program, and what is effectively a barrier implemented as a backwards spinlock - one which begins locked - to ensure that the timing of the two threads calling kadmin() was as I wanted it. The first thread to reach it waits, and the next thread unlocks it and both continue on their way.

The code was originally:

    64   kmutex_t ualock;
    ...
    122 int
    123 kadmin(int cmd, int fcn, void *mdep, cred_t *credp)
    124 {
    ...
    155     /*
    156      * Serialize these operations on ualock.  If it is held, just return
    157      * as if successful since the system will soon reset or remount.
    158      */
    159     if (cmd == A_SHUTDOWN || cmd == A_REBOOT || cmd == A_REMOUNT) {
    160         if (!mutex_tryenter(&ualock))
    161             return (0);
    162         locked = 1;
    163     }
    164 
    165     switch (cmd) {
    166     case A_SHUTDOWN:
    167     {
    168         proc_t *p = ttoproc(curthread);
    169 
    170         /*
    171          * Release (almost) all of our own resources if we are called
    172          * from a user context, however if we are calling kadmin() from
    173          * a kernel context then we do not release these resources.
    174          */
    175         if (p != &p0) {
    176             proc_is_exiting(p);
    177             if ((error = exitlwps(0)) != 0) {
    178                 ASSERT(locked);
    179                 mutex_exit(&ualock);
    180                 return (error);
    181             }

    64   kmutex_t ualock;
    ...
    +++ volatile int other = 0;
    122 int
    123 kadmin(int cmd, int fcn, void *mdep, cred_t *credp)
    124 {
    ...
    155     /*
    156      * Serialize these operations on ualock.  If it is held, just return
    157      * as if successful since the system will soon reset or remount.
    158      */
    159     if (cmd == A_SHUTDOWN || cmd == A_REBOOT || cmd == A_REMOUNT) {
    160         if (!mutex_tryenter(&ualock)) {
    +++             other = 1;
    161             return (0);
    +++         }
    162         locked = 1;
    163     }
    164 
    165     switch (cmd) {
    166     case A_SHUTDOWN:
    167     {
    168         proc_t *p = ttoproc(curthread);
    169 
    170         /*
    171          * Release (almost) all of our own resources if we are called
    172          * from a user context, however if we are calling kadmin() from
    173          * a kernel context then we do not release these resources.
    174          */
    175         if (p != &p0) {
    +++             while(!other);
    176             proc_is_exiting(p);
    177             if ((error = exitlwps(0)) != 0) {
    178                 ASSERT(locked);
    179                 mutex_exit(&ualock);
    180                 return (error);
    181             }

This, along with a couple nanosleep() calls in userland, get my three threads lined up nicely, and exercise the race condition.

Interestingly enough, the above block of code was also interesting because I ran into the textbook example of compilers not dealing with multithreaded code. Originally, the variable other which I added was not volatile. So, as is the example given every time an explanation of that C keyword is necessary, the compiler optimized the code for the while loop after line 175, and broke the code. It lifted the load for other out of the loop, and looped over only the instruction testing whether other was 0. So the first time I ran this modified kernel, the first call into this code... never returned. Adding volatile of course fixed this, telling the compiler to actually do the load every time.

Sidenote: Formatting code for the web is not easy. HTML's pre tag takes care of the basics, but it can be hard to adjust to after spending so much time in front of an editor with syntax highlighting on. I used this online formatter for this entry, found after a few minutes on Google, to format the code for this entry. It's actually for C#, but works well enough for C. Still, it's a little lacking, and I'd rather not have to visit a webpage to do this... perhaps I'll do some scripting this weekend... Perhaps I'll also start using fewer ellipses this weekend...