• The Old New Thing

    Undefined behavior can result in time travel (among other things, but time travel is the funkiest)

    • 73 Comments

    The C and C++ languages are notorious for the very large section of the map labeled here be dragons, or more formally, undefined behavior.

    When undefined behavior is invoked, anything is possible. For example, a variable can be both true and false. John Regehr has a list of interesting examples, as well as some winners of the ensuing contest.

    Consider the following function:

    int table[4];
    bool exists_in_table(int v)
    {
        for (int i = 0; i <= 4; i++) {
            if (table[i] == v) return true;
        }
        return false;
    }
    

    What does this have to do with time travel, you ask? Hang on, impatient one.

    First of all, you might notice the off-by-one error in the loop control. The result is that the function reads one past the end of the table array before giving up. A classical compiler wouldn't particularly care. It would just generate the code to read the out-of-bounds array element (despite the fact that doing so is a violation of the language rules), and it would return true if the memory one past the end of the array happened to match.

    A post-classical compiler, on the other hand, might perform the following analysis:

    • The first four times through the loop, the function might return true.
    • When i is 4, the code performs undefined behavior. Since undefined behavior lets me do anything I want, I can totally ignore that case and proceed on the assumption that i is never 4. (If the assumption is violated, then something unpredictable happens, but that's okay, because undefined behavior grants me permission to be unpredictable.)
    • The case where i is 5 never occurs, because in order to get there, I first have to get through the case where i is 4, which I have already assumed cannot happen.
    • Therefore, all legal code paths return true.

    As a result, a post-classical compiler can optimize the function to

    bool exists_in_table(int v)
    {
        return true;
    }
    

    Okay, so that's already kind of weird. A function got optimized to basically nothing due to undefined behavior. Note that even if the value isn't in the table (not even in the illegal-to-access fifth element), the function will still return true.

    Now we can take this post-classical behavior one step further: Since the compiler can assume that undefined behavior never occurs (because if it did, then the compiler is allowed to do anything it wants), the compiler can use undefined behavior to guide optimizations.

    int value_or_fallback(int *p)
    {
     return p ? *p : 42;
    }
    

    The above function accepts a pointer to an integer and either returns the pointed-to value or (if the pointer is null) returns the fallback value 42. So far so good.

    Let's add a line of debugging to the function.

    int value_or_fallback(int *p)
    {
     printf("The value of *p is %d\n", *p);
     return p ? *p : 42;
    }
    

    This new line introduces a bug: It dereferences the pointer p without checking if it is null. This tiny bug actually has wide-ranging consequences. A post-classical compiler will optimize the function to

    int value_or_fallback(int *p)
    {
     printf("The value of *p is %d\n", *p);
     return *p;
    }
    

    because it observes that the null pointer check is no longer needed: If the pointer were null, then the printf already engaged in undefined behavior, so the compiler is allowed to do anything in the case the pointer is null (including acting as if it weren't).

    Okay, so that's not too surprising. That may even be an optimization you expect from a compiler. (For example, if the ternary operator was hidden inside a macro, you would have expected the compiler to remove the test that is provably false.)

    But a post-classical compiler can now use this buggy function to start doing time travel.

    void unwitting(bool door_is_open)
    {
     if (door_is_open) {
      walk_on_in();
     } else {
      ring_bell();
    
      // wait for the door to open using the fallback value
      fallback = value_or_fallback(nullptr);
      wait_for_door_to_open(fallback);
     }
    }
    

    A post-classical compiler can optimize this entire function to

    void unwitting(bool door_is_open)
    {
     walk_on_in();
    }
    

    Huh?

    The compiler observed that the call value_or_fallback(nullptr) invokes undefined behavior on all code paths. Propagating this analysis backward, the compiler then observes that if door_is_open is false, then the else branch invokes undefined behavior on all code paths. Therefore, the entire else branch can be treated as unreachable

    Okay, now here comes the time travel:

    void keep_checking_door()
    {
     for (;;) {
      printf("Is the door open? ");
      fflush(stdout);
      char response;
      if (scanf("%c", &response) != 1) return;
      bool door_is_open = response == 'Y';
      unwitting(door_is_open);
     }
    }
    

    A post-modern compiler may propagate the analysis that "if door_is_open is false, then the behavior is undefined" and rewrite this function to

    void keep_checking_door()
    {
     for (;;) {
      printf("Is the door open? ");
      fflush(stdout);
      char response;
      if (scanf("%c", &response) != 1) return;
      bool door_is_open = response == 'Y';
      if (!door_is_open) abort();
      walk_on_in();
     }
    }
    

    Observe that even though the original code rang the bell before crashing, the rewritten function skips over ringing the bell and just crashes immediately. You might say that the compiler went back in time and unrung the bell.

    This "going back in time" is possible even for objects with external visibility like files, because the standard allows for anything at all to happen when undefined behavior is encountered. And that includes hopping in a time machine and pretending you never called fwrite.

    Even if you claim that the compiler is not allowed to perform time travel,¹ it's still possible to see earlier operations become undone. For example, it's possible that the undefined operation resulted in the file buffers being corrupted, so the data never actually got written. Even if the buffers were flushed, the undefined operation may have resulted in a call to ftruncate to logically remove the data you just wrote. Or it may have resulted in a Delete­File to delete the file you thought you had created.

    All of these behaviors have the same observable effect, namely that the earlier action appears not to have occurred. Whether they actually occurred and were reversed or never occurred at all is moot from a compiler-theoretic point of view.

    The compiler may as well have propagated the effect of the undefined operation backward in time.

    ¹ For the record, the standard explicitly permits time travel in the face of undefined behavior:

    However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

    (Emphasis mine.)

    ² Another way of looking at this transformation is that the compiler saw that the else branch invokes undefined behavior on all code paths, so it rewrote the code as

    void unwitting(bool door_is_open)
    {
     if (door_is_open) {
      walk_on_in();
     } else {
      walk_on_in();
     }
    }
    

    taking advantage of the rule that undefined behavior allows anything to happen, so in this case, it decided that "anything" was "calling walk_on_in by mistake."

    Bonus chatter: Note that there are some categories of undefined behavior which may not be obvious. For example, dereferencing a null pointer is undefined behavior even if you try to counteract the dereference before it does anything dangerous.

    int *p = nullptr;
    int& i = *p;
    foo(&i); // undefined
    

    You might think that the & and the * cancel out and the result is as if you had written foo(p), but the fact that you created a reference to a nonexistent object, even if you never carried through on it, invokes undefined behavior (§8.5.3(1)).

    Related reading: What Every C Programmer Should Know About Undefined Behavior, Part 1, Part 2, Part 3.

    Update: Broke the &* into two lines because it is the lone * that is the problem.

  • The Old New Thing

    For Honor, For Excellence, For Pizza

    • 18 Comments

    Hacker News member citizenlow recalls the time I went over after hours to help out the Money team debug a nasty kernel issue. They were running into mysterious crashes during their stress testing and asked for my help in debugging it.

    I helped out other teams quite a bit, like writing a new version of Dr. Watson for the Windows 98 team or writing a new version of the MSConfig tool based on a sketch on a bar napkin. And for a time, I followed the official policy for moonlighting to make sure everybody understood that I was doing work outside the boundaries of my official job duties.

    When the Money folks asked me for help, I told them that before I could help them, they would have to help me fill out some paperwork.

    • Who will you be working for? Microsoft Corporation.
    • Where will you be doing the work? Office XX/YYYY on Microsoft Redmond Campus.
    • When will the work begin and end? Begin on YYYY/MM/DD at 5pm, ending YYYY/MM/DD at 11pm.
    • How much will you be paid for this work?

    The Money folks were not sure how to answer that last question, since they didn't have any formal budget or procedures for hiring an outside consultant, much less any procedures for hiring one from inside the company.

    I told them, "Just write One slice of pizza."

    Nobody from the Personnel department seemed to notice the odd circumstances of this moonlighting request; they simply rubber-stamped it and put it in my file.

    The crash, it turns out, was in Windows itself. There was a bug in the special compiler the Languages team produced to help build certain components of Windows 95 which resulted in an incorrect address computation under a particularly convoluted boundary condition. The Money folks had merely stumbled across this bug as part of their regular testing. I notified the appropriate people, and the Windows team applied a workaround in their code to tickle the compiler into generating the correct code.

    As I recall, the pizza was just fine. It was just your average delivery pizza, nothing gourmet or anything. Not that it had to be, because I wasn't there for the pizza.

  • The Old New Thing

    Getting past the question to solving the problem, episode 2014.06.25

    • 28 Comments

    Today is another example where the right thing to do is not to answer the customer's question but rather to solve the customer's problem.

    A customer liaison asked, "What do the registry keys X and Y do? We noticed that they are both read from and written to when you open a common file dialog. Just curious."

    I replied, "I'm curious as to your curiousity. I'm afraid that you are curious because your customer is curious, and then the customer will start relying on the keys in a strange and unsupported way." The format of those keys has varied from one version of Windows to another, so there is nothing there applications can rely on. But maybe we can figure out why the customer is snooping there so we can solve the customer's problem.

    The customer liaison was kind enough to explain. "The customer wants to know how to set the default folder shown in the Open and Save As dialogs."

    The algorithm for choosing the default folder shown in the Open and Save As dialogs is spelled out in the documentation of the OPEN­FILE­NAME structure. There is no registry key that can force all dialogs to use a particular folder. But what is the customer's actual problem?

    The customer liaison explained, "The customer wants to change the default save location for Paint and Notepad."

    Okay, now we're getting closer to a solvable problem. Paint defaults to saving in the user's Pictures folder, and Notepad defaults to saving in the user's Documents folder, so you can use folder redirection to point the Pictures and Documents folders to locations of your choosing, noting of course that this will affect all applications which look for those folders.

    It turns out that this was what the customer actually needed. They redirected the user's Pictures and Documents folders to their preferred location via GPO, and everybody was happy.

  • The Old New Thing

    The social interactions in two preschool classes, in graphic form

    • 34 Comments

    Each preschooler at my daughter's school was asked a few simple questions, and the answers were printed in the yearbook. Among other things, the preschoolers were asked to complete the sentence, "I like to play with (person)."

    This is the type of question that leads to tears and hurt feelings.

    Whatever. Their parents are going to be stuck with the therapy bills. (My daughter is not a preschooler at the school, so I avoided a therapy bill. At least not over this.)

    From this data, I created a graph. Each arrow points from a student to the person they said they like to play with.

    1 7 16
    2 8 17
    3 9 14 18
    10 19
    4 11 15 20
    5 12
    6 13

    This class breaks up into four cliques. Two of the cliques consists of a pair of playmates, and one hanger-on. The large clique consists of two focal points (students 9 and 10) who play with each other. The medium-sized clique has a single focal point (student 18) who plays with a best friend (14).

    I think that student 14 is in the best spot. He (or she) is not himself popular, but the popular kid plays with him (or her).

    The second preschool class has a more complex structure.

    21
    22
    23 30
    24 31 35
    25 32 36
    39
    26 33 37
    40
    27 34 38
    28
    29

    The upper left group consists of a core of four students (23, 30, 31, 24) who play with each other, plus some hangers-on.

    The lower left group consists of a pair of friends (27 and 28) and their hangers-on.

    The right-hand group consists of one very popular student (37) who plays with a best friend (36), and their hangers-on.

    The most interesting student is number 26.

    All of the other students gave only one name in response to the prompt. But student 26 gave three names. As a result, that student links together the three cliques in the class.

    Student 26 is bringing people together. I admire that.

  • The Old New Thing

    Finding the "Run as administrator" command, a game of hide-and-seek

    • 46 Comments

    Back in the old days, the "Run as administrator" menu option was placed on the extended menu. To get the extended menu, you hold the shift key when you right-click on the shortcut.

    In Windows 7, the "Run as administrator" option was moved to the primary menu, so you no longer need to hold the shift key to get it.

    Well, except that sometimes you still need to hold the shift key.

    The deal is that there are two "Run as administrator" commands. One of them is for running shortcuts to regular applications as administrator. The other is for running shortcuts to MSI applications as administrator. Shortcuts to MSI applications are weird because they aren't shortcuts to EXEs but rather are shortcuts to an entry in the MSI database.

    When the decision was made to move the "Run as administrator" command from the extended menu to the primary menu, the person who made the change moved only one of the "Run as administrator" commands (the one for regular application) and forgot to move the other one (the one for shortcuts to MSI applications). As a result, you still need to hold the shift key to run MSI applications elevated.

    The problem is fixed on the Windows 8 Start menu. It correctly shows the "Run as administrator" option for both shortcuts to regular applications and shortcuts to MSI applications.

  • The Old New Thing

    Adding a sound to the Alt+Tab window

    • 17 Comments

    Today's Little Program plays a sound when the Alt+Tab window appears and disappears.

    #define STRICT
    #include <windows.h>
    #include <mmsystem.h>
    
    HWND g_hwndAltTab = nullptr;
    
    void CALLBACK WinEventProc(
        HWINEVENTHOOK hWinEventHook,
        DWORD event,
        HWND hwnd,
        LONG idObject,
        LONG idChild,
        DWORD dwEventThread,
        DWORD dwmsEventTime
    )
    {
     PCTSTR pszSound = nullptr;
     switch (event) {
     case EVENT_SYSTEM_SWITCHSTART:
      if (!g_hwndAltTab) {
       g_hwndAltTab = hwnd;
       pszSound = "C:\\Windows\\Media\\Speech on.wav";
      }
      break;
     case EVENT_SYSTEM_SWITCHEND:
      if (g_hwndAltTab) {
       g_hwndAltTab = nullptr;
       pszSound = "C:\\Windows\\Media\\Speech sleep.wav";
      }
      break;
     }
     if (pszSound) {
      PlaySound(pszSound, nullptr, SND_FILENAME | SND_ASYNC);
     }
    }
    
    int WINAPI WinMain(HINSTANCE hinst, HINSTANCE hinstPrev,
                       LPSTR lpCmdLine, int nShowCmd)
    {
     HWINEVENTHOOK hWinEventHook = SetWinEventHook(
         EVENT_SYSTEM_SWITCHSTART, EVENT_SYSTEM_SWITCHEND,
         nullptr, WinEventProc, 0, 0,
         WINEVENT_OUTOFCONTEXT | WINEVENT_SKIPOWNPROCESS);
    
     if (hWinEventHook) {
      MessageBox(nullptr, "Close this window when sufficiently annoyed.",
                 "Hello", MB_OK);
      UnhookWinEvent(hWinEventHook);
     }
     return 0;
    }
    

    The program registers an accessibility event hook for the EVENT_SYSTEM_SWITCH­START and EVENT_SYSTEM_SWITCH­END events. The Start event fires when an Alt+Tab operation begins, and the End event fires when an Alt+Tab operation completes. As noted in the documentation, you can get spurious End events, so we keep track of our current state to avoid any surprises.

    In addition to adding an annoying sound to the Alt+Tab window, let's also add an annoying sound each time you move focus to a new item.

    HWINEVENT g_hWinEventHookFocus = nullptr;
    
    void CALLBACK WinEventProc(
        HWINEVENTHOOK hWinEventHook,
        DWORD event,
        HWND hwnd,
        LONG idObject,
        LONG idChild,
        DWORD dwEventThread,
        DWORD dwmsEventTime
    )
    {
     PCTSTR pszSound = nullptr;
     switch (event) {
     case EVENT_SYSTEM_SWITCHSTART:
      if (!g_hwndAltTab) {
       g_hwndAltTab = hwnd;
       g_hWinEventHookFocus = SetWinEventHook(
         EVENT_OBJECT_FOCUS, EVENT_OBJECT_FOCUS,
         NULL, WinEventProc, 0, 0,
         WINEVENT_OUTOFCONTEXT | WINEVENT_SKIPOWNPROCESS);
       pszSound = "C:\\Windows\\Media\\Speech on.wav";
      }
      break;
     case EVENT_SYSTEM_SWITCHEND:
      if (g_hwndAltTab) {
       g_hwndAltTab = nullptr;
       UnhookWinEvent(g_hWinEventHookFocus);
       g_hWinEventHookFocus = nullptr;
       pszSound = "C:\\Windows\\Media\\Speech sleep.wav";
      }
      break;
     case EVENT_OBJECT_FOCUS:
      if (hwnd == g_hwndAltTab) {
       pszSound = TEXT("C:\\Windows\\Media\\Speech Misrecognition.wav");
      }
      break;
     }
     if (pszSound) {
      PlaySound(pszSound, nullptr, SND_FILENAME | SND_ASYNC);
     }
    }
    
    int WINAPI WinMain(HINSTANCE hinst, HINSTANCE hinstPrev,
                       LPSTR lpCmdLine, int nShowCmd)
    {
     HWINEVENTHOOK hWinEventHook = SetWinEventHook(
         EVENT_SYSTEM_SWITCHSTART, EVENT_SYSTEM_SWITCHEND,
         nullptr, WinEventProc, 0, 0,
         WINEVENT_OUTOFCONTEXT | WINEVENT_SKIPOWNPROCESS);
    
     if (hWinEventHook) {
      MessageBox(nullptr, "Close this window when sufficiently annoyed.",
                 "Hello", MB_OK);
      UnhookWinEvent(hWinEventHook);
      if (g_hWinEventHookFocus) {
       UnhookWinEvent(g_hWinEventHookSelect);
      }
     }
     return 0;
    }
    

    Okay, this was a pretty annoying program, but maybe you can use it for something better.

  • The Old New Thing

    Once you go input-idle, your application is deemed ready to receive DDE messages

    • 11 Comments

    Feel free to stop using DDE.

    There was one customer who confessed that they were still using DDE, and they asked for help debugging a DDE problem. They found that sometimes, when their application was launched for DDE, it never received the WM_DDE_INITIATE message. Instead, the Shell­Execute function returned ERROR_DDE_FAIL. If launched from Explorer, the error message shown to the user was "There was a problem sending the command to the program."

    It took a long time to figure out what was going on, and there were a number of dead ends, but I'll cut to the chase: The problem was that one of the features they added to their program included code that ran during process startup, and that code pumped messages as part of its initialization. Message pumping was not expected there, which is why it took so long to isolate.

    The Wait­For­Input­Idle function was created for DDE. It's how a DDE client determines that the DDE server is ready to accept commands. And as soon as any thread in your process goes input-idle, the entire process is declared to be input-idle, and you end up becoming eligible to receive DDE messages, even if you're not really ready for them.

    In the case of this program, the accidental message pump caused the application to be considered ready to accept DDE commands even though the main DDE server hadn't gotten off the ground yet. The initiation message went to the splash screen, and the splash screen said, "Why are you bothering me with stupid DDE messages? I'm just a splash screen!"

    TL;DR: If your application includes a DDE server, make sure not to pump messages until your DDE server is ready to receive commands.

  • The Old New Thing

    What happened to the Shut Down menu in classic Task Manager?

    • 61 Comments
    The great thing about open comments is that anybody can use them to introduce their favorite gripe as long as it shares at least four letters of the alphabet in common with the putative topic of the base article.

    xpclient "asks" why the Shut Down menu was removed from Task Manager. I put the word "asks" in quotation marks, because it's really a complaint disguised as a question. As in "Why do you guys suck?"

    The first thing to understand is that classic Task Manager went into a state of sustained engineering since Windows 2000. In other words, the component is there, but there is no serious interest in improving it. (That's why it wasn't updated to call Enable­Theme­Dialog­Texture on its pages.) It's not like there's a Task Manager Team of five people permanently dedicated to making Task Manager as awesome as possible for every release of Windows. Rather, the responsibility for maintaining Task Manager is sort of tacked onto somebody whose primary responsibilities are for other parts of the system.

    There are a lot of Windows components in this state of "internal sustained engineering." The infamous "Install font" dialog, for example. The responsibility for maintaining these legacy components is spread out among the product team so that on average, teams are responsible both for cool, exciting things and some not-so-cool, legacy things.

    (On the other hand, according to xpclient, an app must be serving its users really well if it hasn't changed much, so I guess that Install font dialog is the best dialog box in all of Windows at serving its users, seeing as it hasn't changed since 1995.)

    The engineering budget for these components in internal sustained engineering is kept to a minimum, both because there is no intention of adding new features, and also because the components are so old that there is unlikely to be any significant work necessary in the future.

    Every so often, some work becomes necessary, and given that the engineering interest and budget are both very low, the simplest way out when faced with a complicated problem in a rarely-used feature is simply to remove the rarely-used feature.

    And that's what happened to the Shut Down menu. (Note that it's two words "Shut down" since it is being used as a verb, not a noun.) Given the changes to power management in Windows Vista, the algorithm used by Task Manager was no longer accurate. And instead of keeping Task Manager updated with every change, the Shutdown user interface design team agreed to give the Task Manager engineering team a break and say, "Y'know, the Shut Down menu on Task Manager is rarely-used, so we'll let you guys off the hook on this one, so you don't keep getting weekly requests from us to change the way Shut Down works."

    I remember, back in the days of Windows XP, seeing the giant spreadsheet used by the person responsible for overall design of the Shutdown user interface. It tracked the gazillion group policies, user settings, and system configurations which all affect how shutting down is presented to the user. Removing the column for Task Manager from the spreadsheet probably was met with a huge sigh of relief, not just from the Task Manager engineering team, but also from the person responsible for the spreadsheet.

    Remember, engineering is about trade-offs. If you decide to spend more effort making Task Manager awesome, you lose the ability to expend that effort on something else. (And given that you are expending effort in a code base that is relatively old and not fresh in the minds of the people who would be making those changes, you also increase the likelihood that you're going to introduce a bug along the way.)

  • The Old New Thing

    10 is the new 6

    • 35 Comments

    While it may no longer be true that everything at Microsoft is built using various flavors of Visual C++ 5.0, 6.0, and 7.0, there is still a kernel of truth in it: A lot of customers are still using Visual C++ 6.0.

    That's why the unofficial slogan for Visual C++ 2010 was 10 is the new 6. Everybody on the team got a T-shirt with the slogan (because you don't have a product until you have a T-shirt).

  • The Old New Thing

    Who would ever write a multi-threaded GUI program?

    • 37 Comments

    During the development of Windows 95, the user interface team discovered that a component provided by another team didn't work well under multi-threaded conditions. It was documented that the Initialize function had to be the first call made by a thread into the component.

    The user interface team discovered that if one thread called Initialize, and then used the component, then everything worked great. But if a second thread called Initialize, the component crashed whenever the second thread tried to use it.

    The user interface team reported this bug back to the team that provided the component, and some time later, an updated version of the component was delivered.

    Technically, the bug was fixed. When the second thread called Initialize, the function now failed with ERROR_NOT_SUPPORTED.

    The user interface team went back to the team that provided the component. "It's nice that your component detects that it is being used by a multi-threaded client and fails the second thread's attempt to initialize it. But given that design, how can a multi-threaded client use your component?"

    The other team's reply was, "It doesn't matter. Nobody writes multi-threaded GUI programs."

    The user interface team had to politely reply, "Um, we are. The next version of Windows will be built on a multi-threaded shell."

    The other team said, "Oh, um, we weren't really expecting that. Hang on, we'll get back to you."

    The idea that somebody might write a multi-threaded program that used their component caught them by surprise, and they had to come up with a new design of their component that supported multiple threads in a clean way. It was a lot of work, but they came through, and Windows 95 could continue with its multi-threaded shell.

Page 2 of 425 (4,250 items) 12345»