• The Old New Thing

    Enumerating all the ways of making change


    Today's Little Program enumerates all the ways of making change for a particular amount given a set of available denominations.

    The algorithm is straightforward. To make change for a specific amount from a set of available denominations, you can take one denomination and decide how many of those you want to use. Then use the remaining denominations to make change for the remainder.

    For example, if the available coins have values [1, 5, 10, 25] and you want to make change for 60 cents, you first decide how many 25-cent pieces you want to use. If you use none, then you need to make change for 60 cents using just [1, 5, 10]. If you use one, then you need to make change for 35 cents using just [1, 5, 10]. And if you use two, then you need to make change for 10 cents using just [1, 5, 10].

    (We use the largest coin first to reduce the number of dead ends, like asking "Please make change for 83 cents using only 10-cent coins.")

    function MakeChange(coins, total, f) {
     if (total == 0) { f([]); return; }
     if (coins.length == 0) return;
     var coin = coins[coins.length - 1];
     var remaining = coins.slice(0, -1);
     var used = [];
     for (var target = total; target >= 0; target -= coin) {
      MakeChange(remaining, target, function(s) {
    MakeChange([1, 5, 10, 25], 60, console.log.bind(console));

    First, we take care of some base cases. To make change for zero cents, we simply use zero coins. And it's not possible to make change for a nonzero amount with no coins.

    Otherwise, we take the highest denomination coin and try using zero of them, then one of them, and so on, until we exceed the total amount necessary.

    There are related problems, such as determining whether a particular amount of change can even be made, given a collection of denominations and calculating the number of ways change can be made rather than enumerating them. But I like enumeration problems.

  • The Old New Thing

    What did Windows 3.1 do when you hit Ctrl+Alt+Del?


    This is the end of Ctrl+Alt+Del week, a week that sort of happened around me and I had to catch up with.

    The Windows 3.1 virtual machine manager had a clever solution for avoiding deadlocks: There was only one synchronization object in the entire kernel. It was called "the critical section", with the definite article because there was only one. The nice thing about a system where the only available synchronization object is a single critical section is that deadlocks are impossible: The thread with the critical section will always be able to make progress because the only thing that could cause it to stop would be blocking on a synchronization object. But there is only one synchronization object (the critical section), and it already owns that.

    When you hit Ctrl+Alt+Del in Windows 3.1, a bunch of crazy stuff happened. All this work was in a separate driver, known as the virtual reboot device. By convention, all drivers in Windows 3.1 were called the virtual something device because their main job was to virtualize some hardware or other functionality. That's where the funny name VxD came from. It was short for virtual x device.

    First, the virtual reboot device driver checked which virtual machine had focus. If you were using an MS-DOS program, then it told all the device drivers to clean up whatever they were doing for that virtual machine, and then it terminated the virtual machine. This was the easy case.

    Otherwise, the focus was on a Windows application. Now things got messy.

    When the 16-bit Windows kernel started up, it gave the virtual reboot device the addresses of a few magic things. One of those magic things was a special byte that was set to 1 every time the 16-bit Windows scheduler regained control. When you hit Ctrl+Alt+Del, the virtual reboot device set the byte to 0, and it also registered a callback with the virtual machine manager to say "Call me back once the critical section becomes available." The callback didn't do anything aside from remember the fact that it was called at all. And then the code waited for ¾ seconds. (Why ¾ seconds? I have no idea.)

    After ¾ seconds, the virtual reboot device looked to see what the state of the machine was.

    If the "call me back once the critical section becomes available" callback was never called, then the problem is that a device driver is stuck in the critical section. Maybe the device driver put an Abort, Retry, Ignore message on the screen that the user needs to respond to. The user saw this message:


    This background non-Windows application is not responding.

    *  Press any key to activate the non-Windows application.
    *  Press CTRL+ALT+DEL again to restart your computer. You will
       lose any unsaved information.

      Press any key to continue _

    After the user presses a key, focus was placed on the virtual machine that holds the critical section so the user can address the problem. A user who is still stuck can hit Ctrl+Alt+Del again to restart the whole process, and this time, execution will go into the "If you were using an MS-DOS program" paragraph, and the code will shut down the stuck virtual machine.

    If the critical section was not the problem, then the virtual reboot device checked if the 16-bit kernel scheduler had set the byte to 1 in the meantime. If so, then it means that no applications were hung, and you got the message


    Although you can use CTRL+ALT+DEL to quit an application that has stopped responding to the system, there is no application in this state.

    To quit an application, use the application's quit or exit command, or choose the Close command from the Control menu.

    *  Press any key to return to Windows.
    *  Press CTRL+ALT+DEL again to restart your computer. You will
       lose any unsaved information in all applications.

      Press any key to continue _

    (Anachronism alert: The System menu was called the Control menu back then.)

    Otherwise, the special byte was still 0, which means that the 16-bit scheduler never got control, which meant that a 16-bit Windows application was not releasing control back to the kernel. The virtual reboot device then waited for the virtual machine to finish processing any pending virtual interrupts. (This allowed any pending MS-DOS emulation or 16-bit MS-DOS device drivers to finish up their work.) If things did not return to this sane state within 3¼ seconds, then you got this screen:


    The system is either busy or has become unstable. You can wait and see if the system becomes available again and continue working or you can restart your computer.

    *  Press any key to return to Windows and wait.
    *  Press CTRL+ALT+DEL again to restart your computer. You will
       lose any unsaved information in all applications.

      Press any key to continue _

    Otherwise, we are in the case where the system returned to a state where there are no active virtual interrupts. The kernel single-stepped the processor if necessary until the instruction pointer was no longer in the kernel, or until it had single-stepped for 5000 instructions and the instruction pointer was not in the heap manager. (The heap manager was allowed to run for more than 5000 instructions.)

    At this point, you got the screen that Steve Ballmer wrote.

    Contoso Deluxe Music Composer

      This Windows application has stopped responding to the system.

      *  Press ESC to cancel and return to Windows.
      *  Press ENTER to close this application that is not responding.
         You will lose any unsaved information in this application.
      *  Press CTRL+ALT+DEL again to restart your computer. You will
         lose any unsaved information in all applications.

    If you hit Enter, then the 16-bit kernel terminated the application by doing mov ax, 4c00h followed by int 21h, which was the system call that applications used to exit normally. This time, the kernel is making the exit call on behalf of the stuck application. Everything looks like the application simply decided to exit normally.

    The stuck application exits, the kernel regains control, and hopefully, things return to normal.

    I should point out that I didn't write any of this code. "It was like that when I got here."

    Bonus chatter: There were various configuration settings to tweak all of the above behavior. For example, you could say that Ctrl+Alt+Del always restarted the computer rather than terminating the current application. Or you could skip the check whether the 16-bit kernel scheduler had set the byte to 1 so that you could use Ctrl+Alt+Del to terminate an application even if it wasn't hung.¹ There was also a setting to restart the computer upon receipt of an NMI, the intention being that the signal would be triggered either by a dedicated add-on switch or by poking a ball-point pen in just the right spot. (This is safer than just pushing the reset button because the restart would flush disk caches and shut down devices in an orderly manner.)

    ¹ This setting was intended for developers to assist in debugging their programs because if you went for this option, the program that got terminated is whichever one happened to have control of the CPU at the time you hit Ctrl+Alt+Del. This was, in theory, random, but in practice it often guessed right. That's because the problem was usually that a program got wedged into an infinite message loop, so most of the CPU was being run in the stuck application anyway.

  • The Old New Thing

    A lie repeated often enough becomes the truth: The continuing saga of the Windows 3.1 blue screen of death (which, by the way, was never called that)


    HN has been the only major site to report the history of the Windows 3.1 Ctrl+Alt+Del dialog correctly. But it may have lost that title due to this comment thread.

    I read here that Steve Ballmer wrote part of [the blue screen of death] too.

    The comment linked to one of may articles that erroneously reported that Steve wrote the blue screen of death.

    Somebody replied,


    linking back to my article where I set the record straight.

    Undeterred, the original commenter wrote,

    LOL! so far only MSDN has been refuting the claim.

    and linked to two technology sites which reported the story incorrectly.

    Just goes to show that a lie repeated often enough becomes the truth.

    Oh, and by the way, the phrase "blue screen of death" did not really apply to the blue screen messages in Windows 3.1 or Windows 95. As we saw earlier, the Windows 3.1 fatal error message was a black screen of death, and in Windows 95, the blue screen message was more a screen of profound injury rather than death. (Windows 95 was sort of like the Black Knight, trying very hard to continue the fight despite having lost all of its limbs.)

    The phrase "blue screen of death" was generally attributed to the blue screen fatal error message of Windows NT. In Windows 95, we just called them "blue screen messages", without the "of death".

    I didn't expect this to become "blue screen week", though that's sort of what it turned into.

  • The Old New Thing

    The history of Win32 critical sections so far


    The CRITICAL_SECTION structure has gone through a lot of changes since its introduction back oh so many decades ago. The amazing thing is that as long as you stick to the documented API, your code is completely unaffected.

    Initially, the critical section object had an owner field to keep track of which thread entered the critical section, if any. It also had a lock count to keep track of how many times the owner thread entered the critical section, so that the critical section would be released when the matching number of Leave­Critical­Section calls was made. And there was an auto-reset event used to manage contention. We'll look more at that event later. (It's actually more complicated than this, but the details aren't important.)

    If you've ever looked at the innards of a critical section (for entertainment purposes only), you may have noticed that the lock count was off by one: The lock count was the number of active calls to Enter­Critical­Section minus one. The bias was needed because the original version of the interlocked increment and decrement operations returned only the sign of the result, not the revised value. Biasing the result by 1 means that all three states could be detected: Unlocked (negative), locked exactly once (zero), reentrant lock (positive). (It's actually more complicated than this, but the details aren't important.)

    If a thread tries to enter a critical section but can't because the critical section is owned by another thread, then it sits and waits on the contention event. When the owning thread releases all its claims on the critical section, it signals the event to say, "Okay, the door is unlocked. The next guy can come in."

    The contention event is allocated only when contention occurs. (This is what older versions of MSDN meant when they said that the event is "allocated on demand.") Which leads to a nasty problem: What if contention occurs, but the attempt to create the contention event fails? Originally, the answer was "The kernel raises an out-of-memory exception."

    Now you'd think that a clever program could catch this exception and try to recover from it, say, by unwinding everything that led up to the exception. Unfortunately, the weakest link in the chain is the critical section object itself: In the original version of the code, the out-of-memory exception was raised while the critical section was in an unstable state. Even if you managed to catch the exception and unwind everything you could, the critical section was itself irretrievably corrupted.

    Another problem with the original design became apparent on multiprocessor systems: If a critical section was typically held for a very brief time, then by the time you called into kernel to wait on the contention event, the critical section was already freed!

    void SetGuid(REFGUID guid)
     g_theGuid = guid;
    void GetGuid(GUID *pguid)
     *pguid = g_theGuid;

    This imaginary code uses a critical section to protect accesses to a GUID. The actual protected region is just nine instructions long. Setting up to wait on a kernel object is way, way more than nine instructions. If the second thread immediately waited on the critical section contention event, it would find that by the time the kernel got around to entering the wait state, the event would say, "Dude, what took you so long? I was signaleded, like, a bazillion cycles ago!"

    Windows 2000 added the Initialize­Critical­Section­And­Spin­Count function, which lets you avoid the problem where waiting for a critical section costs more than the code the critical section was protecting. If you initialize with a spin count, then when a thread tries to enter the critical section and can't, it goes into a loop trying to enter it over and over again, in the hopes that it will be released.

    "Are we there yet? How about now? How about now? How about now? How about now? How about now? How about now? How about now? How about now? How about now? How about now? How about now?"

    If the critical section is not released after the requested number of iterations, then the old slow wait code is executed.

    Note that spinning on a critical section is helpful only on multiprocessor systems, and only in the case where you know that all the protected code segments are very short in duration. If the critical section is held for a long time, then spinning is wasteful since the odds that the critical section will become free during the spin cycle are very low, and you wasted a bunch of CPU.

    Another feature added in Windows 2000 is the ability to preallocate the contention event. This avoids the dreaded "out of memory" exception in Enter­Critical­Section, but at a cost of a kernel event for every critical section, whether actual contention occurs or not.

    Windows XP solved the problem of the dreaded "out of memory" exception by using a fallback algorithm that could be used if the contention event could not be allocated. The fallback algorithm is not as efficient, but at least it avoids the "out of memory" situation. (Which is a good thing, because nobody really expects Enter­Critical­Section to fail.) This also means that requests for the contention event to be preallocated are now ignored, since the reason for preallocating (avoiding the "out of memory" exception) no longer exists.

    (And while they were there, the kernel folks also fixed Initialize­Critical­Section so that a failed initialization left the critical section object in a stable state so you could safely try again later.)

    In Windows Vista, the internals of the critical section object were rejiggered once again, this time to add convoy resistance. The internal bookkeeping completely changed; the lock count is no longer a 1-biased count of the number of Enter­Critical­Section calls which are pending. As a special concession to backward compatibility with people who violated the API contract and looked directly at the internal data structures, the new algorithm goes to some extra effort to ensure that if a program breaks the rules and looks at a specific offset inside the critical section object, the value stored there is −1 if and only if the critical section is unlocked.

    Often, people will remark that "your compatibility problems would go away if you just open-sourced the operating system." I think there is some confusion over what "go away" means. If you release the source code to the operating system, it makes it even easier for people to take undocumented dependencies on it, because they no longer have the barrier of "Well, I can't find any documentation, so maybe it's not documented." They can just read the source code and say, "Oh, I see that if the critical section is unlocked, the Lock­Count variable has the value −1." Boom, instant undocumented dependency. Compatibility is screwed. (Unless what people are saying "your compatibility problems would go away if you just open-sourced all applications, so that these problems can be identified and fixed as soon as they are discovered.")

    Exercise: Why isn't it important that the fallback algorithm be highly efficient?

  • The Old New Thing

    I wrote the original blue screen of death, sort of


    We pick up the story with Windows 95. As I noted, the blue Ctrl+Alt+Del dialog was introduced in Windows 3.1, and in Windows 95; it was already gone. In Windows 95, hitting Ctrl+Alt+Del called up a dialog box that looked something like this:

    Close Program × 
    Contoso Deluxe Composer [not responding]
    Fabrikam Chart 2.0
    LitWare Chess Challenger
    WARNING: Pressing CTRL+ALT+DEL again will restart your computer. You will lose unsaved information in all programs that are running.
    End Task
    Shut Down

    (We learned about Systray some time ago.)

    Whereas Windows 3.1 responded to fatal errors by crashing out to a black screen, Windows 95 switched to showing severe errors in blue. And I'm the one who wrote it. Or at least modified it last.

    I was responsible for the code that displayed blue screen messages: Asking the kernel-mode video driver to switch into text mode, filling the screen with a blue background, drawing white text, waiting for the user to press a key, restoring the screen to its original contents, and reporting the user's response back to the component that asked to display the message.¹

    When a device driver crashed, Windows 95 tried its best to limp along despite a catastrophic failure in a kernel-mode component. It wasn't a blue screen of death so much as a blue screen of lameness. For those fortunate never to have seen one, it looked like this:


    An exception 0D has occurred at 0028:80014812. This was called from 0028:80014C34. It may be possible to continue normally.

    * Press any key to attempt to continue.
    * Press CTRL+ALT+DEL to restart your computer. You will
      lose any unsaved information in all applications.

    Note the optimistic message "It may be possible to continue normally." Everybody forgets that after Windows 95 showed you a blue screen error, it tried its best to ignore the error and keep running anyway. I mean, sure your scanner driver crashed, so scanning doesn't work any more, but the rest of the system seems to be okay.

    (Imagine if you did that today. "Press any key to ignore this kernel panic.")

    Technically, what happened was that the virtual machine manager abandoned the event currently in progress and returned to the event dispatcher. It's the kernel-mode equivalent to swallowing exceptions in window procedures and returning to the message loop. If there was no event in progress, then the current application was terminated.

    Sometimes the problem was global, and abandoning the current event or terminating the application did nothing to solve the problem; all that happened was that the next event or application to run encountered the same problem, and you got another blue screen message a few milliseconds later. After about a half dozen of these messages, you most likely gave up hope and hit Ctrl+Alt+Del.

    Now, that's what the message looked like originally, but that message had a problem: Since the addresses at which device drivers were loaded into the kernel were not predictable, having the raw address didn't really tell you much. If you were someone who was told, "This senior executive got this crash message, can you figure out what happened?", all you had to work with was a bunch of mostly useless numbers.

    That someone might have been me.

    To help with this problem, I tweaked the message to include the name of the driver, the section number, and the offset within the section.


    An exception 0D has occurred at 0028:80014812 in VxD CONTOSO(03) + 00000152. This was called from 0028:80014C34 in VxD CONTOSO(03) + 00000574. It may be possible to continue normally.

    * Press any key to attempt to continue.
    * Press CTRL+ALT+DEL to restart your computer. You will
      lose any unsaved information in all applications.

    Now you had the name of the driver that crashed, which might give you a clue of where the problem is, even if you knew nothing else. And somebody with access to a MAP file for the driver could now look up the address and identify which line crashed. Not great, but better than nothing, and before I made this change, nothing is what you had.

    So you could say that I wrote the Windows 95 blue screen of death lameness to make my own life easier.

    Bonus chatter: Later, someone (I forget whether it was me, so let's say it was one of my colleagues) added some more code to inspect the crashing address, and if it was inside the kernel heap manager, the message changed slightly:


    A 32-bit device driver has corrupted critical system memory, resulting in an exception 0D at 0028:80001812 in VxD VMM(01) + 00001812. This was called from 0028:80014C34 in VxD CONTOSO(03) + 00000575.

    * Press any key to attempt to continue.
    * Press CTRL+ALT+DEL to restart your computer. You will
      lose any unsaved information in all applications.

    In this case, the sentence "It may be possible to continue normally" disappeared. Because we knew that, odds are, it won't be.

    Bonus chatter: Nice job, Slashdot. You considered posting a correction, but your correction was also wrong. At least you realized your mistake.

    ¹ Since this code ran in the kernel, it didn't have access to keyboard layout information. It doesn't know that if you are using the Chinese-Bopomofo keyboard layout, then the way to type "OK" is to press C, followed by L, followed by 3. Not that it would help, because there is no IME in the kernel anyway. As much as possible, the responses were mapped to language-independent keys like Enter and ESC.

  • The Old New Thing

    Steve Ballmer did not write the text for the blue screen of death


    Somehow, it ended up widely reported that Steve Ballmer wrote the blue screen of death. And all of those articles cited my article titled "Who wrote the text for the Ctrl+Alt+Del dialog in Windows 3.1?" Somehow, everybody decided to ignore that I wrote "Ctrl+Alt+Del dialog" and replace it with what they wanted to hear: "blue screen of death".¹

    Note also that people are somehow blaming the person who wrote the text of the error message for the fact that the message appears in the first place. It's like blaming Pat Fleet for AT&T's crappy service. It must suck being the person whose job it is to write error messages.

    Anyway, the Ctrl+Alt+Del dialog was not the blue screen of death. I mean, it had a Cancel option, for goodness's sake. What message of death comes with a Cancel option?

    Grim Reaper: I am here to claim your soul.

    You: No thanks.

    Grim Reaper: Oh, well, in that case, sorry to have bothered you.

    Also, blue screen error messages were not new to Windows 3.1. They existed in Windows 3.0, too. What was new in Windows 3.1 was a special handler for Ctrl+Alt+Del which tried to identify the program that was not responding and give you the opportunity to terminate it. Windows itself was fine; it was just the program that was in trouble.

    Recall that Windows in Enhanced mode ran three operating systems simultaneously, A copy of Standard mode Windows ran inside one of the virtual machines, and all your MS-DOS applications ran in the other virtual machines. These blue screen messages came from the virtual machine manager.

    If you had a single-floppy system, the two logical drives A: and B: were shared by the single physical floppy drive. When a program switched from accessing drive A: to drive B:, or vice versa, Windows prompted you to insert the disk for the new drive:


      Please Insert Diskette for drive B:

      Press any key to continue _

    Another job of the virtual machine manager is to arbitrate access to physical hardware. As long as two virtual machines didn't try to access the same resource simultaneously, the arbitration could be resolved invisibly. But if two virtual machines tried to access, say, the serial port at the same time, Windows alerted you to the conflict and asked you which virtual machines should be granted access and which should be blocked. It looked like this:

     Device Conflict 

    'XyWrite' is attempting to use the COM1 device, which 'Procomm' is currently using. Do you want 'XyWrite' to take control of the device?

    Press Y for Yes or N for No: _

    Windows 3.1 didn't have a blue screen of death. If an MS-DOS application crashed, you got a blue screen message saying that the application crashed, but Windows kept running. If it was a device driver that crashed, then Windows 3.1 shut down the virtual machine that the device driver was running in. But if the device driver crashed the Windows virtual machine, then the entire virtual machine manager shut itself down, sometimes (but not always) printed a brief text message, and handed control back to MS-DOS. So you might say that it was a black screen of death.

    Could not continue running Windows because of paging error.


    The window of opportunity for seeing the blue Ctrl+Alt+Del dialog was quite small: You basically had to be running Windows 3.1 or Windows 3.11.

    Next time, we'll see who actually wrote Windows 95 blue screen of death. Spoiler alert: It was me.

    ¹ I like how The Register wrote "Microsoft has revealed" and "Redmond's Old new thing blog", once again turning me into an official company spokesperson. (They also chose not to identify me by name, which may be a good thing.)

    DailyTech identified me as a Microsoft executive. I'm still waiting for that promotion letter. (And, more important, the promotion pay raise.)

    First honorable mention goes to Engadget for illustrating the article with the Windows 95 dialog that Steve Ballmer didn't write. I mean, I had a copy of the screen in my article, and they decided to show some other screen instead. I gues nobody bothered to verify that the dialogs matched.

    Second honorable mention goes jointly to Gizmodo and lifehacker for illustrating the article with the Windows NT blue screen of death. Not only was it the wrong dialog, it was the wrong operating system. Nice one, guys.

    And special mention goes to BGR, who entirely fabricated a scenario and posited it as real: "What longtime Windows user can forget the panic that set in the first time their entire screen went blue for no explicable reason and was informed that 'This Windows application has stopped responding to the system.'" Yeah, that never happened. The Ctrl+Alt+Del dialog did not appear spontaneously; you had to press Ctrl+Alt+Del to get it. The answer to their question "Who remembers this?" is "Nobody." BGR also titled their article "It turns out Steve Ballmer was directly responsible for developing Windows most hated feature." He didn't develop the feature. He just wrote the text. I also wonder why giving the user the opportunity to terminate a runaway program is the most-hated feature of Windows. Sorry for giving you some control over your computer. I guess they would prefer things the way Windows 3.0 did it: A runaway program forces you to reboot.

  • The Old New Thing

    The wisdom of seventh graders: The emergency survival kit


    As a precursor to reading a story about survival, seventh grade students were asked to come up with a list of things they would want to have in their emergency survival kit. Students were specifically instructed to limit themselves to things that were readily available (so no Apache helicopters), and the complete kit had to be something you could comfortably carry in a student backpack.

    As always, there are students who chose a very sensible collection of things to put in their emergency survival kit: water purification tablets, a flashlight (with batteries), a first-aid kit. Those students are not the subject of today's story.

    Here are some of the more unusual items some students chose to put in their emergency survival kit:

    September is National Preparedness Month.

  • The Old New Thing

    Piping to notepad


    In honor of NotepadConf's new KickStarter video, today's Little Program takes its stdin and puts it in a Notepad window.

    using System;
    using System.Diagnostics;
    using System.Windows.Automation;
    using System.Runtime.InteropServices;
    class Program
      static void Main(string[] args)
        // Slurp stdin into a string.
        var everything = Console.In.ReadToEnd();
        // Fire up a brand new Notepad.
        var process = new Process();
        process.StartInfo.UseShellExecute = false;
        process.StartInfo.FileName = @"C:\Windows\System32\notepad.exe";
        // Find the Notepad edit control.
        var edit = AutomationElement.FromHandle(process.MainWindowHandle)
                       new PropertyCondition(
        // Shove the text into that window.
        var nativeHandle = new IntPtr((int)edit.GetCurrentPropertyValue(
        SendMessage(nativeHandle, WM_SETTEXT, IntPtr.Zero, everything);
      [DllImport("user32.dll", EntryPoint="SendMessage", CharSet=CharSet.Unicode)]
      static extern IntPtr SendMessage(
        IntPtr windowHandle, int message, IntPtr wParam, string text);
      const int WM_SETTEXT = 0x000C;

    The comments pretty much lay out the steps. The part that may not be obvious is the part that deals with UI Automation: We take the main Notepad window, then ask UI Automation to find Document element inside it.

    From that element, we extract the window handle, then drop to Win32 and send a WM_SET­TEXT message to jam the text into the Notepad window.

    If you save this program under the name 2np, then you can do

    dir | 2np

    and it will open a Notepad window with a directory listing inside it.

    Change one line of code, and this program will launch Wordpad instead.

  • The Old New Thing

    You can use a file as a synchronization object, too


    A customer was looking for a synchronization object that had the following properties:

    • Can be placed in a memory-mapped file.
    • Can be used by multiple processes simultaneously. Bonus if it can even be used by different machines simultaneously.
    • Does not leak resources if the file is deleted.

    It turns out there is already a synchronization object for this, and you've been staring at it the whole time: The file.

    File locking is a very old feature that most people consider old and busted because it's just one of those dorky things designed for those clunky database systems that use tape drives like they have in the movies. While that may be true, it's still useful.

    The idea behind file locking is that every byte of a file can be a synchronization object. The intended pattern is that a database program indicates its intention to access a section of a file by locking it, and this prevents other processes from accessing that same section of the file. This allows the database program to update the file without race conditions. When the database program is finished with that section of the file, it unlocks it.

    One interesting bit of trivia about file locking is that you can lock bytes that don't even exist. It is legal to lock bytes beyond the end of the file. This is handy in the database case if you want to extend the file. You can lock the bytes you intend to add, so that nobody else can extend the file at the same time.

    The usage pattern for byte-granular file locks maps very well to the customer's requirements. The synchronization object is... the file itself. And you put it in the file by simply choosing a byte to use as the lock target. (And the byte can even be imaginary.) And if you delete the file, the lock disappears with it.

    Note that the byte you choose as your lock target need not be dedicated for use as a lock target. You can completely ignore the contents of the file and simply agree to use byte zero as the lock target. You just have to understand that when the byte is locked, only the owner of the lock can access it via the Read­File and Write­File family of functions. (Reading or writing a byte that is locked by somebody else will fail with ERROR_LOCK_VIOLATION. Note that access via memory-mapping is not subject to file locking, which neatly lines up with the customer's first requirement.)

    To avoid the problem with locking an actual byte, you can choose imaginary bytes at ridiculously huge offsets purely for locking. Since those bytes don't exist, you won't interfere with other code that tries to read and write them. For example, you might agree to lock byte 0xFFFFFFFF`FFFFFFFF, on the assumption that the file will never become four exabytes in size.

    File locking supports the reader/writer lock model: You can claim a lock for shared access (read) or for exclusive access (write).

    The basic Lock­File function is a subset of the more general Lock­File­Ex function, so let's look at the general function.

    To lock a portion of a file, you call Lock­File­Ex with the range you want to lock, the style of lock (shared or exclusive), and how you want failed locks to be handled. To release the lock, you pass the same range to Unlock­File­Ex. Note that ranges cannot be chopped up or recombined. If you lock bytes 0–10 and 11–19 with separate calls, then you must unlock them with separate matching calls; you can't make a single bulk call to unlock bytes 0–19, nor can you do a partial unlock of bytes 0–5.

    Most of the mechanics of locking are straightforward, except for the "how you want failed locks to be handled" part. If you specify LOCKFILE_FAIL_IMMEDIATELY and the lock attempt fails, then the call simply fails with ERROR_LOCK_VIOLATION and that's the end of it. It's up to you to retry the operation if that's what you want.

    On the other hand, if you do not specify LOCKFILE_FAIL_IMMEDIATELY, and the lock attempt fails, then the behavior depends on whether the handle is synchronous or asynchronous. If synchronous, then the call blocks until the lock is acquired. If asynchronous, then the call returns immediately with ERROR_IO_PENDING, and the I/O completes when the lock is acquired.

    The documentation in MSDN on how lock failures are handled is a bit confusing, thanks to tortured sentence structure like "X behaves like Y if Z unless Q." Here is the behavior of lock failures in table form:

    If Lock­File­Ex fails Handle type
    Asynchronous Synchronous
    LOCKFILE_FAIL_IMMEDIATELY specified Returns FALSE immediately.
    Error code is ERROR_LOCK_VIOLATION.
    LOCKFILE_FAIL_IMMEDIATELY not specified Returns FALSE immediately.
    Error code is ERROR_IO_PENDING.
    I/O completes when lock is acquired.
    Blocks until lock is acquired, returns TRUE.

    Here's a little test app that exercises all the options. Run the program with two command line options. The first is the name of the file you want to lock, and the second is a string describing what kind of lock you want. Pass zero or more of the following letters:

    • "o" to open an overlapped (asynchronous) handle; otherwise, it will be opened non-overlapped (synchronous).
    • "e" to lock exclusively; otherwise, it will be locked shared
    • "f" to fail immediately; otherwise, it will wait

    For example, you would pass "ef" to open a synchronous handle and request an exclusive lock that fails immediately if it cannot be acquired. If you want all the defaults, then pass "" as the options.

    #include <windows.h>
    #include <stdio.h>
    #include <tchar.h>
    int __cdecl _tmain(int argc, TCHAR **argv)
     // Ensure correct number of command line arguments
     if (argc < 3) return 0;
     // Get the options
     DWORD dwFileFlags = 0;
     DWORD dwLockFlags = 0;
     for (PTSTR p = argv[2]; *p; p++) {
      if (*p == L'o') dwFileFlags |= FILE_FLAG_OVERLAPPED;
      if (*p == L'e') dwLockFlags |= LOCKFILE_EXCLUSIVE_LOCK;
      if (*p == L'f') dwLockFlags |= LOCKFILE_FAIL_IMMEDIATELY;
     // Open the file
     _tprintf(TEXT("Opening the file '%s' as %s\n"), argv[1],
              (dwFileFlags & FILE_FLAG_OVERLAPPED) ?
              TEXT("asynchronous") : TEXT("synchronous"));
     HANDLE h = CreateFile(argv[1], GENERIC_READ,
                    FILE_SHARE_READ | FILE_SHARE_WRITE,
                    NULL, OPEN_EXISTING,
                    FILE_ATTRIBUTE_NORMAL | dwFileFlags, NULL);
     if (h == INVALID_HANDLE_VALUE) {
      _tprintf(TEXT("Open failed, error = %d\n"), GetLastError());
      return 0;
     // Set the starting position in the OVERLAPPED structure
     OVERLAPPED o = { 0 };
     o.Offset = 0; // we lock on byte zero
     // Say what kind of lock we want
     if (dwLockFlags & LOCKFILE_EXCLUSIVE_LOCK) {
      _tprintf(TEXT("Requesting exclusive lock\n"));
     } else {
      _tprintf(TEXT("Requesting shared lock\n"));
     // Say whether we're going to wait to acquire
     if (dwLockFlags & LOCKFILE_FAIL_IMMEDIATELY) {
      _tprintf(TEXT("Requesting immediate failure\n"));
     } else if (dwFileFlags & FILE_FLAG_OVERLAPPED) {
      _tprintf(TEXT("Requesting notification on lock acquisition\n"));
      // The event that will be signaled when the lock is acquired
      // error checking deleted for expository purposes
      o.hEvent = CreateEvent(NULL, TRUE, FALSE, NULL);
     } else {
      _tprintf(TEXT("Call will block until lock is acquired\n"));
     // Okay, here we go.
     _tprintf(TEXT("Attempting lock\n"));
     BOOL fRc = LockFileEx(h, dwLockFlags, 0, 1, 0, &o);
     // If the lock failed, remember why.
     DWORD dwError = fRc ? ERROR_SUCCESS : GetLastError();
     _tprintf(TEXT("Wait %s, error code %d\n"),
              fRc ? TEXT("succeeded") : TEXT("failed"), dwError);
     if (fRc) {
      _tprintf(TEXT("Lock acquired immediately\n"));
     } else if (dwError == ERROR_IO_PENDING) {
      _tprintf(TEXT("Waiting for lock\n"));
      WaitForSingleObject(o.hEvent, INFINITE);
      fRc = TRUE; // lock has been acquired
     // If we got the lock, then hold the lock until the
     // user releases it.
     if (fRc) {
      _tprintf(TEXT("Hit Enter to unlock\n"));
      UnlockFileEx(h, 0, 1, 0, &o);
     // Clean up
     if (o.hEvent) CloseHandle(o.hEvent);
     return 0;

    When you run this program, it will try to acquire the lock in the manner requested, and if the lock is successfully acquired, it will wait for you press Enter, then it will release the lock.

    You naturally need to run multiple copies of this program to see how the flags interact. (If you run only one copy, then it will always succeed.)

    Exercise: What changes would you make if you wanted to wait at most 5 seconds to acquire the lock? (Hint.)

  • The Old New Thing

    Aha, I have found a flaw in the logic to detect whether my program is running on 64-bit Windows


    Some time ago, I described how to detect programmatically whether you are running on 64-bit Windows, and one of the steps of the algorithm was "If you are a 64-bit program, then you are running on 64-bit Windows, because 32-bit Windows cannot run 64-bit programs."

    Every so often, somebody will claim that they found a flaw in this logic: "This algorithm may work today, but it assumes that the only version of Windows that can run 64-bit applications is 64-bit Windows. What if a future non-64-bit version of version of Windows runs 64-bit applications? Then your algorithm will incorrectly say that it is running on 64-bit Windows!"

    Yeah, but so what?

    Suppose you detect that the program is running on this hypothetical version of Windows that is not natively 64-bit but still runs 64-bit applications. What will your program do differently? How can you reason about the feature set and compatibility requirements of something that hasn't been invented yet?

    This is another case of If you don't know what you're going to do with the answer to a question, then there's not much point in asking it.

    In this specific case, you should just continue about your normal business and let the emulation layer of the hypothetical future version of Windows do its job of giving you a 64-bit sky with 64-bit birds in the 64-bit trees.

Page 4 of 434 (4,335 items) «23456»