• The Old New Thing

    The geeky thrill of discovering that two things are really the same thing, just with different labels


    Today's post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between forests and matched parentheses is simply to consider each { as an XML open-tag and each } as an XML end-tag.

    One thing to take away from the enumeration of objects controlled by Catalan numbers is that when you see multiplication in a recurrence relation, that typically corresponds to a nested loop. (We saw this ourselves when we studied Stirling numbers of the second kind.)

    The correspondence between binary trees and arbitrary forests is done by simply renaming variables: left­Child and right­Child turn into first­Child and next­Sibling.

    Renaming variables also reveals an interesting equivalence between the two algorithms for reversing a linked list. One technique is to do link rewriting:

    Node *Reverse(Node *head)
     Node *prev = nullptr;
     while (head) {
      // The node we are rewriting
      Node *current = head;
      // Advance to next node before
      // we overwrite the outbound pointer
      head = current->next;
      // Repoint to previous node
      current->next = prev;
      // Advance the trailing pointer
      prev = current;
     return prev;

    Another technique is to pop nodes off one list while pushing them onto another.

    Node *Reverse(Node *head)
     Node *result = nullptr;
     while (head) {
      // Pop
      Node *current = head;
      head = current->next;
      // Push
      current->next = result;
      result = current;
     return result;

    But if you look more closely at the two versions, you'll see that they are not really two algorithms. They are the same algorithm, just with different comments and variable names!

    One of my colleagues used this as an interview question and guided candidates through both algorithms, only to discover later that they were actually the same algorithm, merely viewed through different-colored glasses.

  • The Old New Thing

    Why does the access violation error message put the operation in quotation marks? Is is some sort of euphemism?


    When an application crashes with an access violation, the error message says something like

    The instruction at "XX" referenced memory at "YY". The memory could not be "read".

    Why is the operation in quotation marks? Is this some sort of euphemism?

    The odd phrasing is a consequence of globalization. The operation name is a verb in the infinitive ("read", "write"), but depending on how the containing message is localized, it may need to take a different form. Since the kernel doesn't understand grammar, it just puts the words in quotation marks to avoid having to learn every language on the planet. Imagine if it tried:

    The memory could not be readed.

    The kernel tried to form the passive, which is normally done in English by adding "–ed" to the end of the verb. Too bad "read" and "write" are irregular verbs!

    The more conventional solution for this type of problem is to create a separate error message for each variant so that the text can be translated independently. rather than building sentences at runtime,

    The access violation error message is in a pickle, though, because the underlying status code is STATUS_ACCESS_VIOLATION, and that message contains three insertions, one for the instruction address, one for the address being accessed, and one for the operation. If there were three different status codes, like STATUS_ACCESS_VIOLATION_READ, STATUS_ACCESS_VIOLATION_WRITE, and STATUS_ACCESS_VIOLATION_EXECUTE, then a separate string could be created for each. But that's not how the status codes folks decided to do things, and the translation team was stuck having to use the ugly quotation marks.

  • The Old New Thing

    It rather involved being on the other side of this airtight hatchway: Invalid parameters from one security level crashing code at the same security level (again)


    A few years after I posted this story, the security team received something very similar.

    If have found that if you call the XYZ function (whose last parameter is supposed to be a pointer to a DWORD) and instead of passing a value pointer to a DWORD, you pass NULL, then you can trigger an access violation in the XYZ function. The XYZ function does not check whether the input parameter is NULL. This is a denial of service attack against the system.

    Okay, first of all, even if the XYZ function checked that the final parameter is non-NULL, that wouldn't prevent a caller from passing an invalid non-NULL pointer, so adding a NULL check doesn't accomplish much from a security-theoretical standpoint.

    The problem with this vulnerability report is that there is no elevation. The attack code and the code that crashes are on the same side of the airtight hatchway. If your goal was to make the process crash, then instead of passing invalid parameters to the XYZ function, you can just trigger the crash yourself.

    int __cdecl main(int, char**)
        return *(DWORD*)NULL = 0;

    In other words, in order to trigger an access violation in the XYZ function, you must already have had enough privilege to run code, which means that you already have enough privilege to trigger an access violation without even needing the help of the XYZ function.

    This dubious vulnerability falls into the category Code execution results in code execution.

  • The Old New Thing

    Buggy milk cartons, beeping computers, and other silliness


    Some time ago, there was a performance-related bug that went something like this:

    mm/dd/yy Created by bob
    The attached file contains a dataset that takes a very long time to process.

    The engineer who fixed the problem decided to take the cryptic approach:

    mm/dd/yy Resolved as fixed by alice
    It got better.

    It was a common practice during highly stressful periods to file humorous bugs in the defect tracking system, and once the initial bug was filed, it turned into a sort of collaborative performance effort.

    For some reason, milk is often a trigger.

    Many years ago, the vendor who supplies milk to Microsoft changed the design of their milk cartons, and the new cartons were significantly harder to open than the old cartons. (Apparently they bought a new machine, and the glue level needed to be tuned.) This naturally inspired people to do what they usually do when they see something amiss: File a bug.

    More than one person was inspired to file a milk carton bug, but probably the most famous one is the one reprinted by Korby Parnell back in 2003.

    Kraig Brockschmidt describes an earlier milk carton bug:

    A friend of mine who worked as a tester on Microsoft Excel once logged a bug against the cartons of milk in the free drink coolers. He noticed that the chocolate milk failed to list the ingredient "cocoa" whereas the plain 2% milk did. An intense discussion in raid [the defect tracking system] over the relative merits of these "features" continued for three or four weeks and involved as many as a fifteen different engineers. I think it set some kind of record. Anyway, someone finally went so far as to notify the dairy itself and the bug was closed as "won't fix—assigned to vendor."

    (In the years since the original story occurred, our defect tracking system gained a new resolution class, and today it would be resolved as "external—assigned to vendor.")

    Over in the languages group, there was a bug that went roughly "IDE fails to beep when build is finished." Nobody can find a copy of the bug any more, it having been archived away ages ago, but one of my colleagues recalls that it went something like this:

    • Start a build.
    • Leave office to get a beverage from the kitchen.
    • Return to office.
    • Observe that build has finished, but no beep was heard.

    One person resolved the bug "Not Repro" because they stood just outside the office and clearly heard the beep, but that led to a debate over how far from the office you needed to be in order to reproduce the bug. Things got sillier and sillier until someone finally closed the bug after claiming to have taken their computer out to the forest behind the building and started the compilation. When they returned 30 minutes later, they found that a tree had fallen on the machine.

    I admire the philosophical resolution to that one.

    Bonus content: Mark Lambert posted the text of the "IDE fails to beep" bug.

  • The Old New Thing

    Geeky t-shirt alert: Windows 7's so-called God Mode


    Back in 2010, the so-called God Mode was the hit discovery of the Internet, at least until the next cute cat video made the rounds. If you had stopped by the Microsoft Visitor Center during that meme's brief moment in the sun, and wandered into the gift shop, you could have picked up a t-shirt that said {ED7BA470-8E54-465E-825C-99712043E01C} on the front.

    Of course, if you actually wore that shirt, you would also get stuffed into a locker and have your lunch money stolen from you.

  • The Old New Thing

    I think this person's monitor is broken: It doesn't know how to render text in capital letters


    Some time ago, somebody asked a question about why, when they do 1 and 2, they get extra thing 3.

    "The extra 3 is there because of the 456 feature. BUT DO NOT DISABLE THE 456 FEATURE JUST BECAUSE YOU DON'T LIKE 3. The 456 feature is important, because it ensures that 2 runs to completion. Otherwise, you risk data loss."

    The person wrote back, "I disabled the 456 feature, and that fixed it. Thanks!"

    It appears that that person's monitor is broken: It doesn't know how to render text in capital letters.

  • The Old New Thing

    Why do I have to hit an arrow key before a keyboard-initiated Move operation will follow the mouse?


    TehShrike wonders why you have to hit an arrow key before a keyboard-initiated Move operation will follow the mouse.

    I don't know, but I think it's just a bug. Mind you, it's a bug with extraordinary seniority (probably going as far back as Windows 1.0).

    The Move and Size commands from the system menu are operated by the same common function, and the keyboard-initiated Size command requires you to hit an arrow in order to specify which edge you are trying to resize. The Move command doesn't need to let you pick a side (since moving is independent of sides), but the common helper function waits for the arrow key regardless of the underlying operation.

  • The Old New Thing

    Operations jargon: Internet egress


    As I've noted before, the operations team has their own jargon which superficially resembles English. Some time ago, they sent out a message with the subject A New Internet Egress Path Is Coming.

    Translation: We're changing the way computers access the Internet.

    Bonus jargon: traffic on the edge. This does not refer to traffic that is on the verge of a nervous breakdown. It merely refers to traffic that crosses the boundary between intranet and Internet.

  • The Old New Thing

    Microspeak: Party, in various forms


    Remember, Microspeak includes words and phrases in general use, as long as they are employed at Microsoft at a higher rate than in the general population, or in specific situations that may not be obvious to the uninitiated. They are the words and phrases you need to use in order to fit in.

    Today's word is party, in various forms, and usually paired with the preposition on. In general, it means to use, change, or modify with few or no constraints. These aren't genteel tea parties; they're more like wild college parties, the kind that end with the police being called.

    LockBits returns a pointer to the pixel buffer, and the caller can party on the memory inside the rectangle until it calls UnlockBits.

    When used with permission verbs like can and may, the usage indicates that the component has permission to read from and write to the memory, subject to the given constraints.

    The code partied on our data structures because it used a pointer after freeing it.

    It is often used in a negative sense to indicate that the component wrote to memory that it should not have. Sort of an unauthorized party. (Compare fandango on core.)

    The Contoso notifier injects a DLL into Explorer so it can party on the internal data that keeps track of icons in the notification area and thereby disable the icons of its competitors.

    These sorts of unauthorized parties can be malicious and willful as well as merely accidental.

    The exp branch is a party branch. You can commit your changes there so we can test it before pulling it into the release branch.

    The word party can be used to describe an environment in which the normal rules and constraints are reduced or removed entirely. Here, the party branch is presumably a branch of the project in which the usual procedures for code changes don't apply, or at least apply less strictly than normal. You can put any experimental changes in the exp branch, and then when a new build comes out the next day, you can run your tests against it to see if they solve the problem. If so, then you can start filling out the necessary paperwork to pull the changes into the release branch.

    Many release branches have an experimental offshoot.¹ The idea is that people developing fixes to the product can commit their changes to the experimental branch to see how they work out. If the changes look good, they are pulled into the release branch. If the changes doesn't pass muster, they are rolled back. The developers who use the experimental branch are on their honor to keep the branch in good condition.

    Note that this sense of party is relative. The experimental branch is a big party compared to the staid and formal release branch, but it's still not a crazy free-for-all. You still need to be judicious about what you put into the party branch so you don't ruin the party for everybody else.

    The Q1 branch is locked down for the beta, but you can party your post-beta fixes into the Q2 branch.

    The above example further highlights the relative nature of the term party. Even though the Q2 branch is open to post-beta fixes, you still have to go through the usual test and review processes for fixing bugs. It's just that Q2 will accept any approved bug fix, whereas Q1 will accept only fixes for bugs marked beta-blocking.

    (That's a little extra Microspeak for you: blocking. In Microspeak, a beta blocker is not a pharmacological agent. Rather, it's something that prevents the beta from being released.)

    ¹ In Windows, the experimental branch associated with a release branch is typically called cbt. This officially stands for Central Build Team, but some people who live in my house like to joke that it stands for Can't Be Trusted.

  • The Old New Thing

    Racing email against a snail


    The Windows team double-dogfoods Windows Server and Exchange Server, and while this is good for both products, it can be quite frustrating when something goes wrong.

    I remember back in the early days of the Windows 95 project, the mail servers once got so messed up that some email messages were not delivered for several days. After a colleague told me that he had just received an email message that I had sent several days earlier, I went to the library to look up the typical speed of a garden snail. (This was back in the days when you had to use an actual library to look up facts, and cat videos were available only once a week. The Internet looked like this and a few years later, this.)

    Conclusion: A garden snail would have delivered the message faster than our email system.

    More recently, a wrinkle in the space-time continuum resulted in one of our automated systems sending out warning messages four months after the anomalous situation was detected. (The anomalous situation was repaired almost immediately, so the warning was not only late, it was spurious.)

    One of my colleagues remarked,

    I have a story I read to my grandkids where Frog writes Toad a letter and gives it to a passing snail, who delivers it to Toad's house four days later.

    Can we hire that snail?

    Today is Thank a Mailman Day.

Page 3 of 93 (927 items) 12345»