June, 2006

  • The Old New Thing

    An auto-reset event is just a stupid semaphore

    • 31 Comments

    When you create an event with the CreateEvent function, you get to specify whether you want an auto-reset event or a manual-reset event.

    Manual-reset events are easy to understand: If the event is clear, then a wait on the event is not satisfied. If the event is set, then a wait on the event succeeds. Doesn't matter how many people are waiting for the event; they all behave the same way, and the state of the event is unaffected by how many people are waiting for it.

    Auto-reset events are more confusing. Probably the easiest way to think about them is as if they were semaphores with a maximum token count of one. If the event is clear, then a wait on the event is not satisfied. If the event is set, then one waiter succeeds and the event is reset; the other waiters keep waiting. (And from our discussion of PulseEvent, you already know that it is indeterminate which waiter will be released if there is more than one.)

    The gotcha with auto-reset events is the case where you set an event that is already set. Since an event has only two states (set and reset), setting an event that is already set has no effect. If you are using an event to control a resource producer/consumer model, then the "setting an event that is already set" case will result in you appearing to "lose" a token. Consider the following intended pattern:

    ProducerConsumer
    Wait
    Produce work
    SetEvent
    Wake up and reset event
    Do work
    Produce work
    Wait
    SetEvent
    Wake up and reset event
    Do work
    ... ...

    But what if the timing doesn't quite come out? What if the consumer thread is a little slow to do the work (or the producer thread is a little fast in generating it):

    ProducerConsumer
    Wait
    Produce work
    SetEvent
    Wake up and reset event
    Produce work
    SetEvent
    Do work
    Produce work
    SetEvent (has no effect)
    Wait satisfied immediately
    Reset event
    Do work
    Wait

    Notice that the producer produced three work items, but the consumer performed only two of them. The third SetEvent had no effect since the event was already set. (You have the same problem if you try to increase a semaphore's token count past its maximum.) If you want the number of wakes to match the number of sets, then you need to use a semaphore with a maximum token count as high as the maximum number of outstanding work items you will support.

    Moral of the story: Know your tools, know their limits, and use the right tool for the right job.

  • The Old New Thing

    It's still not a democracy, but at least other people have noticed, too

    • 14 Comments

    I'm glad I'm not the only person to notice that elections for boards of directors are completely rigged so that the nominees always win and there's nothing you can do about it. It appears that the issue was the hot topic in this year's proxy war skirmishes.

    This year, one company actually called me at home asking me to send in my proxy. I guess they didn't have enough votes for the meeting to be held. I explained that not voting was an intentional decision on my part, since it was the only way I could prevent the board of directors from being elected. The caller appeared mollified by that explanation and didn't press the issue further.

  • The Old New Thing

    Psychic debugging: Understanding DDE initiation

    • 11 Comments

    You too can use your psychic powers to debug the following problem:

    We have a problem with opening documents with our application by double-clicking them in Explorer. What's really strange is that if we connect a debugger to Explorer and set a breakpoint on kernel32!CreateProcessW, then wait a moment after CreateProcess returns, then hit 'g', then the document opens fine. But if we don't wait, then the application launches but the document does not open. Instead, you get the error message "Windows cannot find 'abc.lit'. Make sure you typed the name correctly, and then try again." Here is the command we are executing when we run into this problem:

    "F:\Program Files\LitSoft\LitWare\LitWare.exe" /dde
    

    What is wrong?

    If you've been reading carefully and paid attention to the explanation of how document launching via DDE works, then you already know what the problem is.

    Recall that launching documents via DDE is done by first looking for a DDE server and if none is found, launching a server manually and trying again. The command line above was clearly registered as the command associated with a ddeexec. There are two giveaway clues. First is the fact that the document name itself is not present anywhere on the command line. (This couldn't be a direct execution because the program wouldn't know what document it's supposed to be opening!) But the giveaway clue is the phrase /dde on the command line.

    Clearly, something is going wrong when Explorer attempts the second DDE conversation to open the document. The fact that making Explorer wait a few seconds fixes the problem makes the cause obvious: The DDE server is being slow to get itself initialized and listening. Explorer launches the server and tries to talk to it, but the server is not yet ready and therefore doesn't respond to the DDE initiate.

    But how do you fix this?

    The shell assumes that a DDE server is ready to accept connections when it goes input idle. Once WaitForInputIdle on the DDE server returns, Explorer will make its second attempt at initiating a DDE conversation. The fix is for the application to get its DDE server up and running before it starts pumping messages. My guess is that the application moved its DDE server to a background thread to improve startup performance, since the DDE server is not involved in normal program operation. Too bad the program forgot to get the DDE server up and running prior to going input idle when the /dde flag is passed. The one time it's important to have the DDE server running and it misses the boat.

    Moral of the story: If you're going to act as a DDE server, make sure you do so before your primary thread starts pumping messages. Otherwise you have a race condition between your application startup and the shell trying to talk to it.

  • The Old New Thing

    Three-Minute Masterpieces (2006)

    • 1 Comments

    The Seattle Times invited its readers to make three-minute movies, and the best were screened at the Seattle International Film Festival. Or you can watch them online.

  • The Old New Thing

    A single-instance program is its own denial of service

    • 35 Comments

    There are many ways a program can establish itself as a single-instance program; I won't go into them here. But once people head down the path of a single-instance program, they bump into another issue in their security review: Denial of service.

    We are using a named mutex with a fixed name in order to detect whether another copy of the program is running. But that also means an attacker can create the mutex first, thereby preventing our program from running at all! How can I prevent this type of denial of service attack?

    If the attacker is running in the same security context as your program is (or would be) running in, then there is nothing you can do. Whatever "secret handshake" you come up with to determine whether another copy of your program is running, the attacker can mimic it. Since it is running in the correct security context, it can do anything that the "real" program can do.

    But look at the big picture: A single-instance program is its own denial of service! After all, the first instance of the program is preventing the second instance from running. Your program requirements are themselves a security vulnerability. Consequently, you cannot protect against yourself perfectly against a denial of service since a denial of service is what you want in the first place.

    What you can do is to understand and narrow the scope of your vulnerability. Clearly you can't protect yourself from an attacker running at the same security privilege, but you can still protect yourself against unprivileged attackers running at other security privileges. This means using securable objects as part of your handshake. Non-administrative users should not be able to prevent other users from running the program, for example. The worst thing that non-administrative users should be allowed to do is to make their own lives miserable.

  • The Old New Thing

    Announcements on the ferry, one self-explanatory, one not

    • 13 Comments

    While I was riding the ferry last Saturday, there were two announcements made over the public address system.

    "All crew please report to the Second Mate's office."

    What were they all doing in the Second Mate's office? Would the whole crew fit into the office? And while all the crew are in the Second Mate's office, who's steering the ferry?

    The second announcement was self-explanatory:

    "Will the owner of a XYZ please report to the Car Deck to shut off your car alarm? The passenger in the car is becoming increasingly frantic."

    What was I doing on the ferry anyway? I was returning to Seattle from a bike ride with two other friends. (The route is not quite correct, though. Instead of taking Brownsville Highway NE, we took Ogle Rd NE and S Keyport Road NE; also, we took Virginia Loop Road instead of following 308.) The ride includes two stops, one at the Naval Undersea Warfare Museum in Keyport, and a lunch stop in historic downtown Poulsbo.

    This ride began over ten years ago as a "Hey, here's a fun ride, let's try it." On a whim, we added a detour to Chief Seattle's grave, and on the return, coming down Suquamish Way NE, the lead rider "Joe" fell and took an extremely nasty spill. (We concluded later that we must not have been sufficiently respectful at the grave site, and this was Chief Sealth's way of exacting retribution.) As Joe went rolling down the road, I thought to myself, "Well, it's a good thing he's got his helmet on." And then his head struck the ground and the helmet shattered. But he kept going. "Uh oh, now he's got no helmet." Fortunately, he was able to keep his head off the ground and avoid a head injury.

    Now, this was back in the days before mobile phones were a standard personal accessory. Our group consisted of four riders. We sent "John" ahead to call for help. (We knew there was a casino at the bottom of the hill.) "Bob" directed traffic around the accident, while I tended to our fallen friend. John returned sooner than expected; he said that a passing driver offered his car phone (wow, remember car phones?) to call for help. A police officer and an ambulance from the local fire station arrived. While the paramedics tended to Joe's injuries, the police officer took statements and took over traffic direction duties. The officer seemed somewhat disappointed that Joe fell of his own accord. I think he really wanted to nail a driver for hit-and-run.

    As the officer directed traffic, he mentioned to us, "You know, directing traffic is an all-day class." I hadn't thought it about before, but directing traffic is actually quite tricky. You have to be able to convey information to drivers using only nonverbal cues. Things like "Two cars should come forward and stop at this point" or "While I'm directing traffic coming from this direction, cars on the cross street may turn right."

    While we waited for an ambulance from the hospital to arrive, we asked the fire station paramedics, "Why don't you take us to the hospital yourselves?"

    "Consider yourself lucky we aren't. If we took you in our ambulance, that would mean you were on the verge of death."

    Joe, it turned out, suffered a broken shoulder blade. The ambulance driver who took him to the hospital returned later from another run and poked his head into the room.

    "Whatcha got?"

    "Broken shoulder blade."

    The ambulance driver gave him a thumbs-up sign. "Good job!"

    A little ambulance driver humor there.

    Given this auspicious start, we turned the ride into an annual event, naming it "The Joe Memorial Bike Ride". But we never took the Chief Seattle detour ever again. After three or four years, interest in the ride petered out, but I decided this year that it was high time to resurrect it.

  • The Old New Thing

    Why can't you programmatically reorder the items on the Start menu?

    • 47 Comments

    The classic Start menu and the "All Programs" portion of the Windows XP Start menu permit you to customize the order of the shortcuts that appear there. You can use drag/drop to rearrange them, or force them to be sorted by name. But why is there no programmatic interface to these actions?

    Because the power would be used for evil far more than it would be used for good.

    As noted before, the Start menu is highly contentious screen real estate. If a programmatic interface were given to the order of the items on the Start menu, programs would just use it to force their shortcut to the top (and possibly demote their competition). Once you accept that programs will be doing this to the Start menu, the ability for the user to reorder the items would be lost since programs would just override the user's preferences with their own.

  • The Old New Thing

    Understanding what significant digits really mean

    • 40 Comments

    A double-precision floating point number carries fifteen significant digits. What does this really mean?

    I multiplied 0.619207 by 10,000,000 and got 6192069.999999991 instead of 6192070. That's only six significant digits; where's my fifteen?

    Talking about significant digits is really just a shorthand for talking about relative precision. "Fifteen significant digits" means that the representational resolution is one part in 1015. It doesn't mean that the first fifteen digits are correct. (If you spend more time with numerical analysis, you can even see people talking about things like "five and a half significant digits". If the meaning of "significant digits" were literal, how could you have half a digit?)

    The relative error in the above computation is 9 / 6192070000000000 = 1.5 × 10-15, which is consistent with about fifteen significant digits. (And that's assuming the decimal representations are exact, which they aren't.)

    Even if you take a literalist interpretation of significant digits, the values are still good to fifteen digits. Remember that 0.99999... = 1, and therefore the values

    6192069.999999991
    6192069.999999999...

    agree to fifteen significant digits, as promised.

    Now, if you're a hyperliteralist and refuse to accept that 0.99999... = 1, then you are forced to accept that the only possible numbers of significant digits are zero and infinity. Consider a computation whose result is the value 1 exactly, and that the computation is performed to N significant digits (with N > 0). Since you do not accept that 0.9 agrees with 1.0 to even one significant digit, the only values that agree with 1.0 to at least one significant digit must be of the form "one point something". Let's call the result 1 + ε with 0 ≤ ε < 1. Now subtract this result from 2.0, yielding 1 − ε. Again, since you do not accept that 0.9 agrees with 1.0 to even one significant digit, in order for this result to be good to N significant digits (N > 0), the result must be of the form "one point something". Let's call that result 1 + δ with 0 ≤ δ < 1.

    Therefore, we have 1 − ε = 1 + δ and therefore, ε = −δ. Since both δ and ε are greater than or equal to zero, the only way for this equation to be satisfied is to have ε = δ = 0. Consequently, the only number which is equal to 1 to any nonzero number of significant digits (if you subscribe to the hyperliteral definition of significant digits) would be 1 itself. In other words, the only positive number of significant digits is infinity. And I think we all agree that if the only valid numbers of significant digits are zero and infinity, then the whole concept of significant digits would become kind of silly.

    That's why significant digits don't use the hyperliteralist definition.

  • The Old New Thing

    It's a good idea to get somebody who knows the language to be your proofreader

    • 22 Comments

    If you're going to use text from another language, it behooves you to get somebody who knows the language to be your proofreader. Those who fail to heed this advice with respect to Chinese characters may end up featured on Hanzi Smatter 一知半解, which starts with a book titled A Dictionary of Chinese Symbols whose cover depicts the character "book" () upside-down. (Psst, they're called "characters", not "symbols".)

    David Beckham could have done with a good proofreader when he got his wife's name tattooed onto his arm in Hindi, but misspelled it. I get a real chuckle out of the response from Mr. Beckham's poor publicist:

    "You have to understand that there is a difference between Hindi and Hindu. The tattoo has been checked by a Hindu expert."

    When told that Hindi is a language and Hindu a religion, the spokeswoman insisted: "We know the tattoo is spelt correctly."

    The BBC helpfully suggests a way the tattoo can be salvaged.

    My final example of consulting with someone who understands the language you're using comes from a dance rave which used passages from the Koran to decorate its advertising brochure.

    "We had no idea what any of it meant. It looked good on there. It is a beautiful language. And we had desert and a camel in there."

    The kicker is that one of the people involved apologized for the sacrilege with a particularly poor choice of words: "It was an honest-to-God mistake."

  • The Old New Thing

    Window class properties apply to all windows that belong to the class

    • 6 Comments

    Window class properties apply to all windows that belong to the class. That's why they're called class properties. This seems like an obvious thing to say when put in so many words, but I see many "solutions" that lose sight of this simple fact.

    All the properties that you set in the WNDCLASS (or WNDCLASSEX) are window class properties, as are the properties that you can access via Get/SetClassWord/Long/LongPtr. This means that when you change those properties, they affect the entire class. For example, if you write

    SetClassLongPtr(hwnd, GCLP_HCURSOR, (LONG_PTR)hcurNew);
    

    then you aren't just changing the cursor for the window specified by hwnd. You're changing the cursor for all windows of the same class as hwnd. For example, if hwnd is an edit control, then you changed the default cursor for all edit controls.

    But what if you want to change a class property for just one particular window instead of for all windows of a class?

    If you want to change the menu, background, cursor, or icon for a particular window, you can override the class default on a per-window basis:

    PropertyMethod
    Menu SetMenu(hwnd, hmenuNew) + destroy the old menu
    Background Override WM_ERASEBKGND
    Cursor Override WM_SETCURSOR
    Icon SendMessage(hwnd, WM_SETICON, iconSize, (LPARAM)hiconNew)
Page 2 of 4 (34 items) 1234