June, 2008

  • The Old New Thing

    If you say that you don't care about something, you shouldn't be upset that it contains garbage

    • 32 Comments

    There are many situations where you pass a structure to a function, and the function fills in the structure with information you request. In some cases, the function always fills in the entire structure (example: GlobalMemoryStatus). In other cases, you tell the function which bits of information you care about, to save the function the effort of computing something you weren't interested in anyway (example: TreeView_GetItem).

    In the latter case, if you say that you aren't interested in certain parts of the structure, and then you change your mind and start paying attention to them, don't be surprised if you find that there's nothing interesting there. After all, you said you didn't care.

    For example, if you call TreeView_GetItem and set the mask to TVIF_IMAGE | TVIF_PARAM, this means that you want the function to set the iImage and lParam members of the TVITEM structure and that you don't care about the rest. After the call returns, the values of those two members are defined, since you said that's what you wanted, and the remainder of the output fields are undefined. They might contain useful information, they might contain garbage, you're not supposed to care since you said that you didn't.

    Why might fields you said you didn't care about still contain information (correct or incorrect)? It might be that the value is so easy to compute that checking whether the value should be set takes more work than actually setting it! In such a case, the function might choose to set the value even if you didn't say that you needed it.

    On the other hand, the value might be an artifact of a translation layer: You pass a structure saying, "I'm interested in two out of the four members." The function in turn calls a lower lever function with a different structure, saying, "I'm interested in two out of the five members of this different structure." After the call returns, the middle-man function converts the lower-level structure to the higher-level structure. Sure, it may also "convert" stuff that was never asked for, but you said you weren't interested, so they just get garbage. In other words, the function you're calling might be defined like this:

    // The pinfo parameter points to this structure
    struct FOOINFO {
     DWORD dwInUse;
     DWORD dwAvailable;
     DWORD dwRequested;
     DWORD dwDenied;
    };
    
    // The dwMask parameter can be a combination of these values
    #define FOOINFO_INUSE     0x0001
    #define FOOINFO_AVAILABLE 0x0002
    #define FOOINFO_REQUESTED 0x0004
    #define FOOINFO_DENIED    0x0008
    
    BOOL GetFooInfo(FOOINFO *pinfo, DWORD dwMask);
    

    Now, the GetFooInfo function might just be a middle man that talks to another component to do the real work.

    // lowlevel.h
    
    struct LOWLEVELSTATS {
     DWORD dwUnitSize;
     DWORD dwUnitsInUse;
     DWORD dwUnitsAvailable;
     DWORD dwUnitsRequested;
     DWORD dwUnitsGranted;
     DWORD dwTotalRequests;
    };
    
    // The dwMask parameter can be a combination of these values
    #define LLSTATS_UNITSIZE  0x0001
    #define LLSTATS_INUSE     0x0002
    #define LLSTATS_AVAILABLE 0x0004
    #define LLSTATS_REQUESTED 0x0008
    #define LLSTATS_GRANTED   0x0020
    #define LLSTATS_REQUESTS  0x0040
    
    BOOL GetLowLevelStatistics(LOWLEVELSTATS *pstats, DWORD dwMask);
    

    The resulting GetFooInfo function merely translates the call from the application into a call to the GetLowLevelStatistics function:

    BOOL GetFooInfo(FOOINFO *pinfo, DWORD dwMask)
    {
     LOWLEVELSTATS stats;
     DWORD dwLowLevelMask = LLINFO_UNITSIZE;
    
     if (dwMask & FOOINFO_INUSE)
      dwLowLevelMask |= LLSTATS_INUSE;
     if (dwMask & FOOINFO_AVAILABLE)
      dwLowLevelMask |= LLSTATS_AVAILABLE;
     if (dwMask & FOOINFO_REQUESTED)
      dwLowLevelMask |= LLSTATS_REQUESTED;
     if (dwMask & FOOINFO_DENIED)
      dwLowLevelMask |= LLSTATS_REQUESTED | LLSTATS_GRANTED;
    
     if (!GetLowLevelStats(&info;stats, dwLowLevelMask))
      return FALSE;
    
     // Convert the LOWLEVELSTATS into a FOOINFO
     pinfo->dwInUse = stats.dwUnitSize * stats.dwUnitsInUse;
     pinfo->dwAvailable = stats.dwUnitSize * stats.dwUnitsAvailable;
     pinfo->dwRequested = stats.dwUnitSize * stats.dwUnitsRequested;
     pinfo->dwDenied = stats.dwUnitSize *
                       (stats.dwUnitsRequested - stats.dwUnitsGranted);
    
     return TRUE;
    }
    

    Notice that if you ask for just FOOINFO_DENIED, you still get the dwRequested as a side effect, since computing the number of requests that were denied entails obtaining the total number of requests. On the other hand, you also get garbage for dwInUse since the call to GetLowLevelStats didn't ask for LLSTATS_INUSE, but the code that converts the LOWLEVELSTATS to a FOOINFO doesn't know that and converts the uninitialized garbage. But since you said that you didn't care about the dwInUse member, you shouldn't be upset that it contains garbage.

    You now know enough to answer this person's question.

    (Note of course that I'm assuming we are not returning uninitialized garbage across a security boundary.)

  • The Old New Thing

    GUIDs are globally unique, but substrings of GUIDs aren't

    • 40 Comments

    A customer needed to generate an 8-byte unique value, and their initial idea was to generate a GUID and throw away the second half, keeping the first eight bytes. They wanted to know if this was a good idea.

    No, it's not a good idea.

    The GUID generation algorithm relies on the fact that it has all 16 bytes to use to establish uniqueness, and if you throw away half of it, you lose the uniqueness. There are multiple GUID generation algorithms, but I'll pick one of them for concreteness, specifically the version described in this Internet draft.

    The first 60 bits of the GUID encode a timestamp, the precise format of which is not important.

    The next four bits are always 0001, which identify that this GUID was generated by "algorithm 1". The version field is necessary to ensure that two GUID generation algorithms do not accidentally generate the same GUID. The algorithms are designed so that a particular algorithm doesn't generate the same GUID twice, but without a version field, there would be no way to ensure that some other algorithm wouldn't generate the same GUID by some systematic collision.

    The next 14 bits are "emergency uniquifier bits"; we'll look at them later, because they are the ones that fine tune the overall algorithm.

    The next two bits are reserved and fixed at 01.

    The last 48 bits are the unique address of the computer's network card. If the computer does not have a network card, set the top bit and use a random number generator for the other 47. No valid network card will have the top bit set in its address, so there is no possibility that a GUID generated from a computer without a network card will accidentally collide with a GUID generated from a computer with a network card.

    Once you take it apart, the bits of the GUID break down like this:

    • 60 bits of timestamp,
    • 48 bits of computer identifier,
    • 14 bits of uniquifier, and
    • six bits are fixed,

    for a total of 128 bits.

    The goal of this algorithm is to use the combination of time and location ("space-time coordinates" for the relativity geeks out there) as the uniqueness key. However, timekeeping is not perfect, so there's a possibility that, for example, two GUIDs are generated in rapid succession from the same machine, so close to each other in time that the timestamp would be the same. That's where the uniquifier comes in. When time appears to have stood still (if two requests for a GUID are made in rapid succession) or gone backward (if the system clock is set to a new time earlier than what it was), the uniquifier is incremented so that GUIDs generated from the "second time it was five o'clock" don't collide with those generated "the first time it was five o'clock".

    Once you see how it all works, it's clear that you can't just throw away part of the GUID since all the parts (well, except for the fixed parts) work together to establish the uniqueness. If you take any of the three parts away, the algorithm falls apart. In particular, keeping just the first eight bytes (64 bits) gives you the timestamp and four constant bits; in other words, all you have is a timestamp, not a GUID.

    Since it's just a timestamp, you can have collisions. If two computers generate one of these "truncated GUIDs" at the same time, they will generate the same result. Or if the system clock goes backward in time due to a clock reset, you'll start regenerating GUIDs that you had generated the first time it was that time.

    Upon further investigation, the customer really didn't need global uniqueness. The value merely had to be unique among a cluster of a half dozen computers. Once you understand why the GUID generation algorithm works, you can reimplement it on a smaller scale:

    • Four bits to encode the computer number,
    • 56 bits for the timestamp, and
    • four bits as a uniquifier.

    We can reduce the number of bits to make the computer unique since the number of computers in the cluster is bounded, and we can reduce the number of bits in the timestamp by assuming that the program won't be in service 200 years from now, or that if it is, the items that were using these unique values are no longer relevant. At 100 nanoseconds per tick, 2^56 ticks will take 228 years to elapse. (Extending the range beyond 228 years is left as an exercise, but it's wasted effort, because you're going to hit the 16-computer limit first!)

    You can get away with a four-bit uniquifier by assuming that the clock won't drift more than an hour out of skew (say) and that the clock won't reset more than sixteen times per hour. Since you're running under a controlled environment, you can make this one of the rules for running your computing cluster.

  • The Old New Thing

    Why has my clipboard stopped working?

    • 25 Comments

    You may be minding your own business and discover that your clipboard has stopped working. You try to copy something to the clipboard, and it's not there. You try to paste something from the clipboard, and nothing comes out. What's going on?

    The clipboard is a shared resource. (More specifically, shared among programs that run on the same desktop.) The window manager automatically closes the clipboard if a process terminates while it has ownership of the clipboard, but if a program opens the clipboard and simply forgets to close it for whatever reason, the clipboard will remain unavailable to other programs until that program exits.

    If you find yourself in this situation, and you want your clipboard back, you'll have to start exiting programs until you find the one that has been holding the clipboard locked. The Terminal Services Team discussed one case where the rdpclip program can become the "bad guy" that locks up the clipboard. (There's a second part to the story for those who can't get enough.) Or it might be a Virtual PC Virtual Machine Addition.

  • The Old New Thing

    Just because you're using a smart pointer class doesn't mean you can abdicate understanding what it does

    • 38 Comments

    It's great when you have a tool to make programming easier, but you still must understand what it does or you're just replacing one set of problems with another set of more subtle problems. For example, we discussed earlier the importance of knowing when your destructor runs. Here's another example, courtesy of my colleague Chris Ashton. This was posted as a Suggestion Box entry, but it's pretty much a complete article on its own.

    I came across an interesting bug this weekend that I've never seen described anywhere else, I thought it might be good fodder for your blog.

    What do you suppose the following code does?

    CComBSTR bstr;
    bstr = ::SysAllocStringLen(NULL, 100);
    
    1. Allocates a BSTR 100 characters long.
    2. Leaks memory and, if you're really lucky, opens the door for an insidious memory corruption.

    Obviously I'm writing here, so the answer cannot be A. It is, in fact, B.

    The key is that CComBSTR is involved here, so operator= is being invoked. And operator=, as you might recall, does a deep copy of the entire string, not just a shallow copy of the BSTR pointer. But how long does operator= think the string is? Well, since BSTR and LPCOLESTR are equivalent (at least as far as the C++ compiler is concerned), the argument to operator= is an LPCOLESTR – so operator= naturally tries to use the wcslen length of the string, not the SysStringLen length. And in this case, since the string is uninitialized, wcslen often returns a much smaller value than SysStringLen would. As a result, the original 100-character string is leaked, and you get back a buffer that can only hold, say, 25 characters.

    The code you really want here is:

    CComBSTR bstr;
    bstr.Attach(::SysAllocStringLen(NULL, 100));
    

    Or:

    CComBSTR bstr(100);
    

    I'm still a big fan of smart pointers (surely the hours spent finding this bug would have been spent finding memory leaks caused by other incautious programmers), but this example gives pause – CComBSTR and some OLE calls just don't mix.

    All I can add to this story is an exercise: Chris writes, "Since the string is uninitialized, wcslen often returns a much smaller value than SysStringLen would." Can it possibly return a larger value? Is there a potential read overflow here?

  • The Old New Thing

    Food products that are offenses against nature: Bisquick Shake 'n Pour

    • 58 Comments

    Yes, it's another entry in the extremely sporadic series of food products that are offenses against nature. Today it's the incorrectly-punctuated Bisquick Shake 'n Pour.

    For people for whom adding a half cup of milk and one egg to two cups of Bisquick powder is too complicated, now they've even dehydrated the milk and egg and pre-measured the mix, so all you need to do is add a measured amount of water. Because you know, cracking an egg is so time-consuming.

    My colleague who tips me off to all the foods that are offenses against nature let me know by email that even she, mother to a three-week-old baby, was able to somehow pull it together and measure out the milk and crack the egg. "Oh wait," she corrected herself. "I made the pancakes from scratch."

  • The Old New Thing

    Why is there a menu show delay, anyway?

    • 55 Comments

    One of the reactions to my note on how the window manager uses the double-click time as a way to tell how good your reflexes are is bemusement, well okay, not so much bemusement as outrage, over why we need a menu show delay in the first place.

    Imagine, you're navigating a deeply-nested menu hierarchy and then you want to move to one of the items in the most recent fly-out, but instead of moving the mouse directly to the right then down, you move it ever so slightly diagonally down. Boom, the entire menu collapses and you have to start over. There's a place for maddeningly fiendish mouse dexterity games, but trying to create a pivot table is not it.

    I run into this problem all the time on the Web. Web site designers forget to incorporate a menu show delay, resulting in frustration when trying to navigate around them. For example, let's look at the navigation bar on the home page of The Discovery Channel. Hover over TV Shows, and the menu appears. Suppose you want to go to Koppel on Discovery, but instead of moving the mouse straight downward, the way you hold your arm on the desk moves the mouse in an arc that happens to swing to the right before it arcs downward. You touch TV Schedules and your navigation is screwed up. You have to start over and make sure to move the mouse exactly straight down.

    This phenomenon is even worse for sites that position their submenus as a horizontal bar below the main navigation bar, such as EVA Air or NBC. On the NBC site, for example, hover over Schedule and a band appears below the navigation bar with more options. But you can't move the mouse diagonally to, say, Pacific; if you do, you'll accidentally touch News & Sports and the Schedule submenu will be disappear. If you just move and click in one motion, then boom, congratulations, you just clicked on Access Hollywood. You have to carefully move your mouse straight down (being careful not to touch anything else that might open a different menu or cause the existing menu to auto-dismiss), and then straight sideways (being careful not to accidentally move it upward three pixels, causing the secondary navigation bar to be replaced with a different submenu). It's like its own miniature mouse dexterity game. But one you didn't elect to play.

    The folks over at TechNet Magazine did take the menu show delay into account, though it's still not as long as I'd like. Hover over the word TechCenters in the navigation bar, and a submenu appears. If you move toward Script Center and happen to touch TechNet Magazine ever so briefly (like one Planck time), the TechCenters menu stays up. On the other hand, the menu animation is abysmally slow if you use Firefox, so one step forward, one step back.

  • The Old New Thing

    Don't be helpless: You can find information, too, if you try

    • 29 Comments

    Here's a question that floated past my view:

    Anybody know if there exists a library for computing MD5 hashes from unmanaged code? MSDN has information about .NET classes, but nothing about the unmanaged side.

    Hm, let's see.

    C:\Windows SDK\Include> grep MD5 *.h
    wincrypt.h:#define ALG_SID_MD5                     3
    wincrypt.h:#define ALG_SID_SSL3SHAMD5              8
    wincrypt.h:#define CALG_MD5                (ALG_CLASS_HASH | ALG_TYPE_ANY | ALG_SID_MD5)
    wincrypt.h:#define CALG_HUGHES_MD5         (ALG_CLASS_KEY_EXCHANGE|ALG_TYPE_ANY|ALG_SID_MD5)
    wincrypt.h:#define CALG_SSL3_SHAMD5        (ALG_CLASS_HASH | ALG_TYPE_ANY | ALG_SID_SSL3SHAMD5)
    wincrypt.h:#define KP_PRECOMP_MD5          24
    wincrypt.h:#define szOID_RSA_MD5RSA        "1.2.840.113549.1.1.4"
    wincrypt.h:#define szOID_RSA_MD5           "1.2.840.113549.2.5"
    

    Wow, those hits sure look promising. Perhaps a search on Windows Live or Google¹ will turn up something. Oh hey, how about that, sample code.

    Exercise: Use this exact same technique to answer this commenter's question on how the C# ++ operator works. Hint: Since this is a question about the C# language, the C# language specification would be a good starting point.

    Exercise: Use this technique to answer this commenter's question on how to connect to a process as a debugger.

    Footnotes

    ¹ OH MY GOD I LINKED TO GOOGLE.

  • The Old New Thing

    Blinding bank robbers with kindness

    • 10 Comments

    Despite the friendliness of people in the Pacific Northwest (or perhaps because of it), bank robberies in the area are above the national average. But in the Seattle area they went down by nearly half in the beginning of 2007. The reason isn't known for certain, but one factor may be a new approach to thwarting bank robbers by employing "aggressive friendliness" and rattling the nerves of a would-be robber.

    Scott Taffera sensed something was wrong when a man walked into the Ballard bank branch he manages wearing garden gloves, a hat and sunglasses.

    But instead of following the nonconfrontational strategy used by most banks with suspicious people, Taffera approached the man with a hearty greeting and an offer to help. He invited him to remove his hat and sunglasses, and guided him to an equally bubbly teller.

    In the end, the oddly dressed man requested a roll of quarters before slinking out the door.

    By the end of 2007, bank robberies in the state hit a 20-year low, dropping the state from fourth most robbed in the nation to eleventh.

  • The Old New Thing

    Why does OpenProcess succeed even when I add three to the process ID?

    • 42 Comments

    A customer noticed that if you add three to a process ID and pass it to the OpenProcess function, it still succeeds. Why is that?

    Well, first of all, I need to say up front that the behavior you're seeing is an artifact of the implementation and is not part of the contract. You're passing intentionally invalid parameters, what did you expect? The context of this question is "We're seeing this behavior and we can't explain it," not "We're using this trick and want confirmation that it's okay."

    Now, you actually know the answer to this already.

    As we saw earlier, for convenience, the Windows NT kernel uses the handle manager to parcel out process and thread IDs, and the handle manager ignores the bottom two bits of handles. Therefore, adding three has no effect on the process-id-to-object mapping.

    This mechanism is peculiar to kernels based on Windows NT. Versions of Windows derived from the Windows 95 kernel have a different mechanism for mapping process IDs to processes, and that mechanism is unflinchingly rigid. If you add three, the OpenProcess function will reject your process ID as invalid. And I don't know how Windows CE handles it.

    Again, I wish to emphasize that the behavior you see in Windows NT-based kernels is just an implementation artifact which can change at any time. Who knows, maybe once they read this entry, the kernel folks will go in and change OpenProcess to be even more strict.

    Pre-emptive Yuhong Bao comment: "Process IDs on Windows 95 are a pointer to an internal data structure XORed with a constant to obfuscate them."

  • The Old New Thing

    There are only twelve function keys, and who says there's somebody there to push them?

    • 39 Comments

    One of the proposals for adding hidden features to Windows Setup is to have a bunch of hidden function keys, one for each hidden option. Well, first of all, there are only twelve function keys and there are way more than twelve possible Setup features. (Yes, there may be a few function keys still active during Setup, but they exist only for compatibility purposes. No new Setup features involve function keys as far as I'm aware. And yes, there are keyboard layouts with more than twelve function keys, but think about what you're saying in context: "Yes, Setup should use function keys that are not available on most keyboards.")

    Furthermore, there's no guarantee that there's somebody sitting in front of the computer when it's running Setup. Indeed, 90% of the time, there is nobody there at all; Setup is running on a factory floor somewhere churning out computers day and night.

    Adding a command line option to Setup also runs you into problems: The command line gradually gets bloated with a bajillion options. After taking your several dozen customizations and cramming them onto the command line, you'll find yourself having to type 500 characters onto the command line to get what you want, and woe unto you if you typo one of those 500 characters. Can you imagine if somebody said, "To set up Windows the way I like, I simply type the following command," followed by a command that goes on for six lines? "This is total crap. I'm expected to type this monstrosity?"

    Windows Setup for quite a long time has supported so-called unattended installation. You build a so-called unattend file and pass it to the setup program as a single command line parameter, something like setup /unattend:unattendfile. (I forget the command line exactly; you can go look it up yourself.) Now somebody can post their favorite settings onto their Web site, and you can download it and pass it to Setup.

    For many years, this unattend file took the form of an INI file, with [Sections] and Key=Value entries. In Windows Vista, the Setup folks threw away the old parser and switched to XML. Because XML is the wave of the future, right? (I can imagine Steve Ballmer jumping up and down shouting "XML! XML! XML!") I don't know whether they've actually done it, but in principle, the switch to XML means that they can write a schema for the unattend file, and then all the standard XML validation tools become available.

Page 1 of 4 (32 items) 1234