April, 2011

  • The Old New Thing

    Windows is not a .NET Framework delivery channel either

    • 52 Comments

    We learned a while ago that Windows is not an MFC delivery channel. And, since you asked, it's not a .NET Framework delivery channel either.

    If you're developing a program that uses the .NET Framework, you have to have a backup plan if the version of the .NET Framework you need is not installed on the computer. This might mean including a copy of the installer on your CD. It might mean redirecting the user to an appropriate download site. It might just mean telling the user, "This program requires version XYZ of the .NET Framework." Whatever you do, you need to do something.

    Windows XP didn't come with any version of the .NET Framework. Windows Vista came with version 2, and Windows 7 came with version 3.5, but these were provided as optional components which were installed by default. You can go into the Programs and Features control panel to remove them.

    As I recall, the application compatibility folks have a list of programs that treated Windows as a .NET Framework delivery channel; if you install any of them, and the version of the .NET Framework they depend on isn't installed, the application compatibility layer will display the informational message that the application neglected to.

    Bonus chatter: These programs which treated Windows as a .NET Framework delivery channel may have been misled by charts like this one or lists like this one which give the impression that Windows is a .NET Framework delivery channel.

  • The Old New Thing

    No, you can't ask whether your notification icon is visible or not

    • 43 Comments

    A customer asked what started out as a simple question, but by now you know that this sort of simple question only raises new questions:

    Is there a way that we can detect that the user has hidden our notification icon?

    No, there is no way to ask whether your notification icon is hidden or visible. Users decide which icons they want to see, and you don't get to snoop in on the users' decisions.

    Questions like this scare me, because it sounds like this customer's program is going to respond to the user's choice to hide their icon by doing something even more annoying. This is another demonstration of Le Chatelier's Principle as interpreted by John Gall: Every system resists its proper functioning. In this case, a design to make programs less annoying and intrusive merely drives those programs to even more annoying and intrusive behavior.

    The customer's response confirmed this suspicion.

    We have a long-running process with multiple stages. It starts with a dialog box and a progress bar, and after the dialog finishes, a long operation takes place in the background. In some cases during this background operation, we need to ask the user to take an action or make a decision. Our previous version of the program displayed a dialog box under these circumstances, but we switched to a notification balloon to make the experience less annoying. But if the user has hidden our notification, then we want to go back to showing the dialog. (Ideally, we would make the long background operation part of the initial dialog box, but we do not control the initial dialog box.)

    If you use a notification icon, then you have to accept that the user can hide notification icons. If you still want a notification icon, you can start by displaying a dialog box with a progress bar, and give it a button that says "Hide this dialog and display a notification when attention is required." With this design, converting the dialog box to a notification icon is an active step the user must take, and if the user hides the notification icon, it's their own fault.

    Or abandon the notification icon entirely. According to the notification area design guidance, you shouldn't use notification icons if immediate action is required.

    Is the status critical? Is immediate action required? If so, display the information in a way that demands attention and cannot be easily ignored, such as a dialog box.

    Windows 7 lets you communicate the progress of the background operation unobtrusively by displaying the progress bar as part of the taskbar icon.

  • The Old New Thing

    How do I pin a program directly to the Start menu rather than a shortcut?

    • 34 Comments

    Anonymous bemoans the fact that pinning programs to the Start menu (in Windows XP) actually pins the shortcut rather than the program itself. This means that if you right-click on a shortcut to pin it, then delete the shortcut, the pinned item stops working. How do you pin the program directly?

    You pin the program directly by right-clicking on the program directly. If you right-click on a shortcut and select Pin to Start menu, then you're pinning the shortcut. This is sort of obvious, because after all, that's what you right-clicked on. If you want to pin the raw program, then dive into the Program Files folder and right-click the EXE and select Pin to Start menu. Now you pinned the program executable rather than a shortcut.

    The Windows XP Start menu behaves this way instead of tunnelling through the shortcut to the executable because the shortcut itself contains valuable information such as name, command line parameters, hotkey, working directory, and icon. If you have a shortcut called "Development command prompt" that has custom console colors and runs CMD.EXE with a working directory set to your development tree and with a special startup batch file (via the /K command line switch) to set up your environment variables, and you right-click on that shortcut and selected Pin to Start menu, then you would probably be upset if the thing that actually got pinned to your Start menu was a boring CMD.EXE command prompt with no options and no customization.

    "It would be nice if Windows were a bit more intuitive about this."

    Anonymous didn't provide any specific suggestion as to what would be more intuitive. Pinning the executable and throwing away the shortcut properties is definitely not intuitive.

    The Windows 7 folks thought about this and came up with something that hopefully meets the a bit more intuitive criterion: When you pin a shortcut to the taskbar or the Start menu, they make a copy of the shortcut and pin the copy.

  • The Old New Thing

    Lock-free algorithms: Choosing a unique value (warm-up)

    • 34 Comments

    Here's a snippet of code whose job is to generate a unique number within the process. Here's some reference reading to get yourself in the mood. Caution: It may or may not be useful.

    dwUniqueId = InterlockedCompareExchange(&g_dwUniqueId, 
                                            g_dwUniqueId+1, 
                                            g_dwUniqueId);
    

    Criticize this code fragment.

  • The Old New Thing

    The funniest joke I've ever told (to a three-year-old)

    • 33 Comments

    I've tested this joke on several children ages three and four, and it never fails.

    There were two kittens walking down the street, and one of them fell on its butt!

    I developed this joke for one of my honorary nieces. She had just started to learn about joke-telling and asked me to tell her a joke. One of the keys to joke-telling is to know your audience: A three-year-old won't have the attention span for a longer joke, and subtlety and observational humor won't work either. It's got to be short and direct. She thought kittens were cute, and falling on one's butt was funny, so I figured, hey, let me combine the two.

    When I told this joke, she fell on the floor in uncontrollable laughter. I had a winner.

  • The Old New Thing

    There's only so much you can do to stop running code from simulating UI actions

    • 33 Comments

    Commenter KiwiBlue asks whether Captcha-style tests were considered to prevent unsigned drivers from programmatically clicking the 'Install anyway' button.

    I'm sure somebody considered it, but Captcha has its own problems.

    "Type the (distorted) letters below"-type Captcha cannot be used by people with visual impairments, people who are dyslexic, or people who simply are not familiar with the Latin alphabet. (Believe it or not, the vast majority of people on the planet have a native language which does not use the Latin alphabet.) Using an audio captcha runs into the problem of different accents, letters whose readings vary (zee/zed anyone?), and computers without a sound card (like most servers).

    And yes, there are other types of Captchas (dog/cat, for example), but the strongest argument against Captcha is probably that it's just adding more locks to the front door while leaving the service entrance wide open. Once you make it computationally infeasible to programmatically solve the Captcha, unscrupulous driver vendors would simply inject a DLL into the "Install this unsigned driver?" process and patch the call to Did­User­Answer­Captcha­Correctly so it always returns TRUE.

    Or even easier, just programmatically set the Driver Signing Options to Install the software anyway.

    If somebody is running code with administrative privileges, then they already own your machine. Any roadblocks you put up they can find a way to drive over. The goal is not so much putting up stronger and stronger roadblocks (because eventually people will simply drive around them) but rather making it clear to the developer that what they're doing is driving around a roadblock.

  • The Old New Thing

    Lock-free algorithms: The try/commit/(try again) pattern

    • 31 Comments

    The singleton constructor pattern and the Interlocked­Multiply example we saw some time ago are really special cases of the more general pattern which I'll call try/commit/(try again). I don't know if this pattern has a real name, but that's what I'm calling it for today.

    The general form of this pattern goes like this:

    for (;;) {
     // capture the initial value of a shared variable we want to update
     originalValue = sharedVariable;
    
     ... capture other values we need to perform the operation ...
     ... these values must be indepedent of sharedVariable ...
    
     newValue = ... calculate the desired new result
                    based on originalValue and other captured values ...
    
     // Xxx can be Acquire, Release, or null
     if (InterlockedCompareExchangeXxx(
                &sharedVariable,
                newValue, oldValue) == oldValue) {
      break; // update was successful
     }
    
     ... clean up newValue ...
    
    } // loop back and try again
    

    We calculate the desired new value based on the initial value, combining it with other values that vary depending on the operation you want to perform, and then use an Interlocked­Compare­Exchange to update the shared value, provided the variable hasn't changed from its initial value. If the value did change, then that means another thread raced against us and updated the value before we could; in that case, we go back and try it again. Maybe the next time through we won't collide against somebody.

    Note that the try/commit/try again pattern is unfair. There's no assurance that the thread that has been trying to update the value for the longest time will win the next race. (This is a property common to most lock-free algorithms.)

    The Interlocked­Multiply function follows this pattern very closely: The other value required to perform the operation is simply the multiplier, which is a parameter to the function and therefore is independent of the shared variable. The new value is simply the product, and if we are unable to update the shared value (because somebody else modified it), we just start over.

    A variation of try/commit/try again is try/commit/abandon. In this pattern, there is no loop. If the exchange fails, you just give up and return a failure code. The function Try­Enter­Critical­Section uses the try/commit/abandon pattern. (It also uses the Acquire version of Interlocked­Compare­Exchange for reasons which should be obvious.)

    Our singleton pattern is another special case of try/commit/try again where the "try again" is optimized out because we know what the result of "try again" is going to be, so we don't actually have to do it. In the singleton pattern case, the Interlocked­Compare­Exchange is a Release because the new value depends on other memory locations.

    Normally, the shared variable is an integer rather than a pointer, because a pointer is subject to the ABA problem if you incorporate the pointed-to data into your calculations. We get away with it in the singleton pattern case because the value change is unidirectional: It goes from NULL to something, and once it's something it never changes again. If the value of the shared variable can change in more general ways, then you have to be more careful if you use a pointer as the shared variable. (The most common solution is to make the shared variable not just a pointer but a pointer plus a counter which increments at each operation.)

    Here's another use of the try/commit/try again pattern, using a change counter as the shared variable. First, two helper functions:

    LONG InterlockedReadAcquire(__in LONG *pl, __in LONG lUnlikely)
    {
      return InterlockedCompareExchangeAcquire(pl, lUnlikely, lUnlikely);
    }
    
    LONG InterlockedReadRelease(__in LONG *pl, __in LONG lUnlikely)
    {
      return InterlockedCompareExchangeRelease(pl, lUnlikely, lUnlikely);
    }
    

    Although direct reads and writes of properly aligned LONGs are atomic, the operations are not synchronized and impose no memory ordering semantics. To read a value with specific semantics, I pull a sneaky trick: I perform an Interlocked­Compare­Exchange with the desired memory ordering semantics, passing the same value as the comparand and the exchange; therefore, the operation, even if successful, has no computational effect.

    if (*pl == lUnlikely) *pl = lUnlikely;
    

    To avoid dirtying the cache line, I use an unlikely value as the comparand/exchange, so most of the time, the comparison fails and no memory is written. (This trick doesn't help on all architectures, but it doesn't hurt.)

    Okay, back to the change counter example:

    LONG g_lColorChange;
    
    ...
    case WM_SYSCOLORCHANGE:
     InterlockedIncrement(&g_lColorChange);
     ...
    
    int CalculateSomethingAboutSystemColors()
    {
     LONG lColorChangeStart;
     do {
      lColorChangeStart = InterlockedReadAcquire(&g_lColorChange, -1);
      COLORREF clrWindow = GetSysColor(COLOR_WINDOW);
      COLORREF clrHighlight = GetSysColor(COLOR_HIGHLIGHT);
      ... other computations involving GetSysColor(...)
     } while (InterlockedReadRelease(
                           &g_lColorChange, -1) != lColorChangeStart);
     return iResult;
    }
    

    We capture the color change counter and then begin doing our calculations. We capture the value with acquire semantics so that we get the value before we start reading the system colors. When we're done, we compare the value of the change counter against the value we captured. If it's different, then that means that the colors changed while we were doing our calculations, so our calculations are all messed up. In that case, we go back and try it again.

    This technique does assume that you won't get into a situation where one thread manages to increment the change counter 4 billion times before the other thread manages to run. This is not a problem in practice. For example, in this case, it's reasonable to assume that nobody is going to change their system colors 4 billion times within a single thread quantum.

    Next time, I'll show a different variation on try/commit/abandon which might be suitable for simple caches.

    Exercise: Criticize the following: "I noticed that there is no interlocked read operation, but there is Interlocked­Or, so my plan is to perform an interlocked read by or'ing with zero."

  • The Old New Thing

    Lock-free algorithms: The singleton constructor

    • 25 Comments

    The first half may be familiar to many (most?) readers, but there's an interesting exercise at the bottom.

    A very useful pattern for the Interlocked* functions is lock-free lazy initialization via Interlocked­Compare­Exchange­Pointer­Release. Yes, that's a really long function name, but it turns out every part of it important.

    Widget *g_pwidCached;
    
    Widget *GetSingletonWidget()
    {
     Widget *pwid = g_pwidCached;
     if (!pwid) {
      pwid = new(nothrow) Widget();
      if (pwid) {
       Widget *pwidOld = reinterpret_cast<Widget*>
           (InterlockedCompareExchangePointerRelease(
              &reinterpret_cast<PVOID&>(g_pwidCached),
              pwid, NULL));
       if (pwidOld) {
        delete pwid; // lost the race - destroy the redundant copy
        pwid = pwidOld; // use the old one
       }
      }
     }
     return pwid;
    }
    

    This is a double-check lock, but without the locking. Instead of taking lock when doing the initial construction, we just let it be a free-for-all over who gets to create the object. If five threads all reach this code at the same time, sure, let's create five objects. After everybody creates what they think is the winning object, they called Interlocked­Compare­Exchange­Pointer­Release to attempt to update the global pointer.

    The parts of the name of the Interlocked­Compare­Exchange­Pointer­Release function work like this:

    • Interlocked: The operation is atomic. This is important to avoid two threads successfully updating the value of g_pwidCached.
    • Compare: The value in g_pwidCached is compared against NULL.
    • Exchange: If the values are equal, then g_pwidCached is set to pwid. This, combined with the comparison, ensures that only one thread gets to set the value of g_pwidCached.
    • Pointer: The operations are on pointer-sized data.
    • Release: The operation takes place with release semantics. This is important to ensure that the pwid we created is fully-constructed before we publish its pointer to other processors.

    This technique is suitable when it's okay to let multiple threads try to create the singleton (and have all the losers destroy their copy). If creating the singleton is expensive or has unwanted side-effects, then you don't want to use the free-for-all algorithm.

    Bonus reading:

    • One-Time Initialization helper functions save you from having to write all this code yourself. They deal with all the synchronization and memory barrier issues, and support both the one-person-gets-to-initialize and the free-for-all-initialization models.
    • A lazy initialization primitive for .NET provides a C# version of the same.

    Okay, now here's the interesting exercise. This is an actual problem I helped out with, although details have been changed for expository purposes.

    We have a data structure which manages a bunch of singleton objects, let's say that they are instances of a structure called ITEMCONTROLLER and they are keyed by a 32-bit ID. We're looking for design suggestions on making it thread-safe. The existing code goes like this (pseudocode):

    struct ITEMCONTROLLER;
    struct SINGLETONINFO {
     DWORD dwId;
     ITEMCONTROLLER *(*pfnCreateController)();
    };
    
    class SingletonManager {
    public:
     // rgsi is an array that describes how to create the objects.
     // It's a static array, with csi in the range 20 to 50.
     SingletonManager(const SINGLETONINFO *rgsi, UINT csi)
                   : m_rgsi(rgsi), m_csi(csi),
                     m_rgcs(NULL), m_ccs(0), m_ccsAlloc(0) { }
     ~SingletonManager() { ... }
     ITEMCONTROLLER *Lookup(DWORD dwId);
    
    private:
     struct CREATEDSINGLETON {
      DWORD dwId;
      ITEMCONTROLLER *pic;
     };
    
    private:
     const SINGLETONINFO *m_rgsi;
     int m_csi;
    
     // Array that describes objects we've created
     CREATEDSINGLETON *m_rgcs;
     int m_ccs;
    };
    
    ITEMCONTROLLER *SingletonManager::Lookup(DWORD dwId)
    {
     int i;
    
     // See if we already created one
     for (i = 0; i < m_ccs; i++) {
      if (m_rgcs[i].dwId == dwId)
       return m_rgcs[i].pic;
     }
    
     // Not yet created - time to create one
     ITEMCONTROLLER *pic;
     for (i = 0; i < m_rgsi; i++) {
      if (m_rgsi[i].dwId == dwId) {
       pic = m_rgsi[i].pfnCreateController();
       break;
      }
     }
     if (pic == NULL) return;
    
     ... if m_rgcs == NULL then allocate it and update m_ccsAlloc
     ... else realloc it bigger and update m_ccsAlloc
    
     // append to our array so we can find it next time
     m_rgcs[m_ccs].dwId = dwId;
     m_rgcs[m_ccs].pic  = pic;
     m_ccs++;
    
     return pic;
    }
    

    In words, the SingletonManager takes an array of SINGLETONINFO structures, each of which contains an ID and a function to call to create the object with that ID. To look up an entry, we first check if we already created one; if so, then we just return the existing one. Otherwise, we create the object (using pfnCreateController) and add it to our array of created objects.

    Our initial inclination is to put a critical section around the entire Lookup function, but maybe there's something more clever we can do here. Maybe a slim reader-writer lock?

    Bonus chatter: Although it's the case on Windows that the plain versions of the interlocked functions impose both acquire and release semantics, other platforms may not follow Windows' lead. In particular, on the XBOX360 platform, the plain versions of the interlocked functions impose neither acquire nor release semantics. I don't know what the rules are for Windows CE.

    Erratum: I once knew but subsequently forgot that the singleton pattern described in this article (with the InterlockedCompareExchangePointer) is not safe on some CPU architectures. An additional MemoryBarrier() needs to be inserted after the fetch of the single pointer to ensure that indirections through it will retrieve the new values and not any cached old values:

    Widget *GetSingletonWidget()
    {
     Widget *pwid = g_pwidCached;
     if (!pwid) {
      ...
     } else {
      // Ensure that dereferences of pwid access new values and not old
      // cached values.
      MemoryBarrier();
     }
     return pwid;
    }
    

    The discussion of lock-free algorithms continues (with probably more errors!) next time.

  • The Old New Thing

    Back from Las Vegas, and now my clothes smell like cigarette smoke

    • 23 Comments

    I actually came back Thursday night, but I've been too lazy to jot down some reactions until now.

    There are signs on the street directing you to a tram connecting the Monte Carlo hotel with the Bellagio. but once you follow the first sign (that takes you into the casino), there are no more signs telling you how to get to the tram. The tram is a lie.

    Actually, the tram does exist, but it's not marked. You have to walk through the entire Monte Carlo casino to the Street of Dreams shops, and then past them and up a flight of stairs to the tram station. When you reach the Bellagio, you then have to do the reverse, walking through the Bellagio to get your way back to the street. I'm not sure if it's actually faster than just walking the regular way.

    Note to people who choose swag for conferences: if people are flying into your conference, a toy gun is probably not a good choice for a giveaway.

    A word of warning to Japanese tourists: The people in costumes standing around enticing you to pose with them for a picture? After you take your picture, they're going to ask you for money. And apparently, the practice has spread to helpful "volunteer" photographers who will just shrug and walk away if they break your camera.

    The Marquee bills itself as a "Nightclub and Dayclub." Doesn't that just make it a "Club"?

    I didn't win a Niney, but I did get to meet Lady Gaga (or a least a Lady Gaga impersonator). As a courtesy, I called her "Your Grace." I knew it wasn't the correct honorific, but she seemed okay with it.

    Man, that Niney award is heavy. And Scott won two of them! If he packs them both in the same suitcase, he's going to get a hernia.

    At the urinal is a small shelf, presumably a place to put your drink while you make room for your next drink.

    Let me get this straight. If you visit the Paris Hotel and take a picture of the fake Eiffel Tower, you'll also capture in the frame a U.S. flag. I guess that's sort of like the fake streets mapmakers add so they can detect copyright violations.

    One of the figures atop the Paris Hotel is a statue with the simple label Suger. Once again proving that if you know Swedish, the world is funnier. In Swedish, suger means sucks.

    When airline pilots come onto the speaker to tell you the weather at your destination, why do they all assume they're talking to other pilots? "The winds are out of the south-southwest, and the cloud ceiling is 10,000 feet, with visibility of five miles and air pressure of 30.05 inches." The only way this could be made more useless would be if a passenger shouted out, "But what's the dew point?" One of my friends suggested that airline pilots are simply frustrated that they couldn't make it as a weatherman.

    My clothes smell like cigarette smoke, so I guess what happens in Vegas doesn't always stay in Vegas.

  • The Old New Thing

    Microspeak: Hipo

    • 23 Comments

    A friend of mind was asked out of the blue, "What does hypo mean?"

    She started to flash back to high school English class and Greek word roots.

    "I've started to hear it everywhere. Like Everyone in that meeting is a hypo or We need to reach out to hypos."

    My friend realized that she had mis-heard the question. It was not about the Greek root hypo but rather the bizarro Microspeak word hipo, shorthand for high-potential employee.

    As I researched this term (which I had never encountered before), I found that it fell into that special category of Microspeak known as if you have to ask, I'm not going to tell you. Identifying and developing high-potential employees is one of the charter activities of the ExPo project. And if you look through the ExPo Web site, you'll find that nowhere do they tell you what HiPo and ExPo stand for. "If you have to ask, I'm not going to tell you."

    My friend suggested that "ExPos are people who have a lot of potential and enjoy showing it off to others."

Page 1 of 3 (28 items) 123