July, 2006

  • The Old New Thing

    Issues related to forcing a stub to be created for an imported function


    I noted last time that you can concoct situations that force the creation of a stub for an imported function. For example, if you declare a global function pointer variable:

    DWORD (WINAPI *g_pGetVersion)() = GetVersion;

    then the C compiler is forced to generate the stub and assign the address of the stub to the g_pGetVersion variable. That's the best it can do, since the loader will patch up only the imported function address table; it won't patch up anything else in the data segment.

    The C++ compiler, on the other hand, can take advantage of some C++ magic and secretly generate a "pseudo global constructor" (I just made up that term so don't go around using it like it's official or something) that copies the value from the imported function address table to the g_pGetVersion variable at runtime. Note, however, that since this is happening at runtime, mixed in with all the other global constructors, then the variable might not be set properly if you call it from any code that runs during construction of global objects. Consider the following buggy program made up of two files.

    // file1.cpp
    #include <windows.h>
    EXTERN_C DWORD (WINAPI *g_pGetVersion)();
    class Oops {
      public: Oops() { g_pGetVersion(); }
    } g_oops;
    int __cdecl main(int argc, char **argv)
      return 0;
    // file2.cpp
    #include <windows.h>
    EXTERN_C DWORD (WINAPI *g_pGetVersion)() = GetVersion;

    The rules for C++ construction of global objects is that global objects within a single translation unit are constructed in the order they are declared (and destructed in reverse order), but there is no enforced order for global objects from separate translation units. But notice that there is an order-of-construction dependency here. The construction of the g_oops object requires that the g_pGetVersion object be fully constructed, because it's going to call through the pointer when the Oops constructor runs.

    It so happens that the Microsoft linker constructs global objects in the order in which the corresponding OBJ files are listed in the linker's command line. (I don't know whether this is guaranteed behavior or merely an implementation detail, so I wouldn't rely on it.) Consequently, if you tell the linker to link file1.obj + file2.obj, you will crash because the linker will generate a call to the Oops::Oops() constructor before it gets around to constructing g_pGetVersion. On the other hand, if you list them in the order file2.obj + file1.obj, you will run fine.

    Even stranger: If you rename file2.cpp to file2.c, then the program will run fine regardless of what order you give the OBJ files to the linker, because the C compiler will use the stub instead of trying to copy the imported function address at runtime.

    But what happens if you mess up and declare a function as dllimport when it isn't, or vice versa? We'll look at that next time.

  • The Old New Thing

    Raise la lanterne rouge


    Sure, everybody knows that Floyd Landis won this year's Tour de France. But what about the guy who came in last? While the race leader wears the maillot jaune (yellow jersey), the person at the bottom of the pack is saddled with the lanterne rouge (red lantern), after the lamp that hangs on the back of a train. This year's "winner" is Wim Vansevenant, who at least appears to be a good sport about it.

    Lanterne rouge is not a position you go for. It comes for you.

    (It also amuses me that there's even a Tour de France Lanterne Rouge blog which keeps track of who is "pulling up the rear" throughout the race.)

    Now, mind you, at least he finished the race, which is more than can be said for the thirty-some-odd people who dropped out for one reason or another. All of whose water bottles I am not worthy to carry, of course.

  • The Old New Thing

    How a less naive compiler calls an imported function


    If a function is declared with the dllimport declaration specifier, this instructs the Visual Studio C/C++ compiler that the function in question is an imported function rather than a normal function with external linkage. With this additional information, the compiler generates slightly different code when it needs to reference an imported function, since the compiler is aware of the special way imported functions are implemented.

    First, there is no need for the stub function any more, because the compiler can generate the special call [__imp__FunctionName] instruction inline. Furthermore, the compiler knows that the address of an imported function never changes, and consequently it can optimize away multiple loads of the function pointer:

        mov   ebx, [__imp__FunctionName]
        push  1
        call  ebx ; FunctionName(1)
        push  2
        call  ebx ; FunctionName(2)

    (Note to crazy people: This optimization means that you can run into problems if you patch a module's import table once it has started running, because the function pointer may have been optimized into a register before you patched the import. Consider, in the above example. that you patched the __imp__FunctionName table entry after the mov ebx, [__imp__FunctionName] instruction: Your replacement import table entry won't be called since the old function address was cached in the ebx register.)

    Similarly, if your program tries to take the address of an imported function that has been declared with the dllimport declaration specifier, the compiler recognizes this and converts it to a load from the imported function address table.

    As a result of this extra knowledge imparted to the compiler, the stub function is no longer needed; the compiler knows to go straight to the imported function address table.

    Note that there are still occasional circumstances wherein you can induce the stub function to be created. We'll take a look at them (and related dangers) next time.

  • The Old New Thing

    Floyd Landis stuns everybody on stage 17; Raymond less impressive



    I delayed my departure for work Thursday morning until the results were in. And then I was inspired by Floyd's fantastic performance to kick it up a notch on one of the hills on my route, only to find about two thirds of the way up that there's a reason I don't normally go up the hill that fast... (On an unrelated note, a mini-van tried to run me off the road while I was heading up that hill. They pulled up next to me and then started a right turn. Fortunately I was able to escape to the right.)

    Okay, well, attacking that hill wasn't such a great idea now, was it. I decided to continue with an alternate route that takes me up a different hill, and I was able to dispatch it with a decent amount of vigor. (Crossing the street at the top of the hill, another car tried to run me off the road. At the corner was a pedestrian and one other cyclist. A car pulled forward to make a right turn on red and didn't notice the three people waiting to cross the street. Just as the driver decided that the coast was clear, the light turned green, and zoom off he went, right in front of us. A little squealing of bicycle brakes and nobody got hurt, at least not this time. That's one of the skills you pick up as a bicyclist: Detecting which cars are going to try to kill you.)

    Okay, so my attempt to "really show the road who's in charge" wasn't quite the overwhelming success I had hoped. Undaunted, I also picked up the pace on the way home, and at least that effort was successful: I set what I believe to be a personal best time. Go me.

  • The Old New Thing

    I didn't realize that it was International Group B Strep Awareness Month


    I guess they're not doing a particularly good job of creating awareness because it wasn't until I consulted the 2006 National Health Observances calendar that the month of July is International Group B Strep Awareness Month.

    For some reason, July and August are pretty light on the health observances calendar. Maybe because people are on summer vacation.

    Who decides whether a particular health observance merits a day, a week, or a month? You'd think they'd save the months for the really big issues, seeing as there are only twelve of them. And for some reason, ultraviolet radiation gets two months. May is Ultraviolet Awareness Month, and July is UV Safety Month. That's one sixth of the year dedicated to ultraviolet radiation.

    (I'm not belittling the health causes themselves, just the way they get assigned days on the calendar.)

  • The Old New Thing

    Calling an imported function, the naive way


    An import library resolves symbols for imported functions, but it isn't consulted until the link phase. Let's consider a naive implementation where the compiler is blissfully unaware of the existence of imported functions.

    In the 16-bit world, this caused no difficulty at all. The compiler generated a far call instruction and left an external record in the object file indicating that the address of the function should be filled in by the linker. At that time, the linker realizes that the external symbol corresponds to an imported function, so it takes all the call targets, threads them together, and creates an import record in the module's import table. At load time, those call entries are fixed up and everybody is happy.

    Let's look at how a naive 32-bit compiler would deal with the same situation. The compiler would generate a normal call instruction, leaving the linker to resolve the external. The linker then sees that the external is really an imported function, and, uh-oh, the direct call needs to be converted to an indirect call. But the linker can't rewrite the code generated by the compiler. What's a linker to do?

    The solution is to insert another level of indirection. (Warning: The information below is not literally true, but it's "true enough". We'll dig into the finer details later in this series.)

    For each exported function in an import library, two external symbols are generated. The first is for the entry in the imported functions table, which takes the name __imp__FunctionName. Of course, the naive compiler doesn't know about this fancy __imp__ prefix. It merely generates the code for the instruction call FunctionName and expects the linker to produce a resolution.

    That's what the second symbol is for. The second symbol is the longed-for FunctionName, a one-line function that consists merely of a jmp [__imp__FunctionName] instruction. This tiny stub of a function satisfies the external reference and in turn generates an external reference to __imp__FunctionName, which is resolved by the same import library to an entry in the imported function table.

    When the module is loaded, then, the import is resolved to a function pointer and stored in __imp__FunctionName, and when the compiler-generated code calls the FunctionName function, it calls the stub which trampolines (via the indirect call) to the real function entry point in the destination DLL.

    Note that with a naive compiler, if your code tries to take the address of an imported function, it gets the address of the FunctionName stub, since a naive compiler simply asks for the address of the FunctionName symbol, unaware that it's really coming from an import library.

    Next time, we'll look at the dllexport declaration specifier and how a less naive compiler generates code for an imported function.

  • The Old New Thing

    Buy me some peanuts and a set of double-pointed 2's


    It's the second annual Stitch 'n Pitch at Safeco Field. Stitch n' Pitch events for other cities can be found on the Stitch n' Pitch web site. (Channeling Lynne Truss: Ahem, people, the spelling of the middle word is 'n' with an apostrophe fore and aft.) [10am: Fixed sepleling.]

    Seattle Times readers Dave Butner and Mike Wilson took issue with the event (though Mr. Wilson's outrage bordered on satirical). To me, baseball is like soccer: It's a game whose primary draw is not the actual scoring but rather the anticipation that a run might be scored. It's in the tension that builds as scoring opportunities develop (most of which prove fruitless), not in the actual scoring itself. And unlike soccer, where something exciting could happen at almost any time, in baseball, there are long stretches where you can reliably predict that nothing exciting will occur. Like, say, when the pitcher is taking a walk around the mound scratching himself. In other words, baseball is a social event, not a sporting event. And if you're going to attend a social event, why not do it with people whom you share interests with?

    It's not like I don't appreciate baseball. I know when you should perform a double-switch. I know why the catcher sometimes tags the batter with the baseball after a strikeout. I can even explain the infield fly rule. But when I attend a baseball game with friends, we don't talk about baseball the whole time. We enjoy the sunshine, catch up on each other's lives, gossip about friends who aren't present, admire some of the goofball fans in the bleachers. And enjoy a baseball game.

  • The Old New Thing

    Rethinking the way DLL exports are resolved for 32-bit Windows


    Over the past few days we've learned how 16-bit Windows exported and imported functions from DLLs and that the way functions are exported from 32-bit DLLs matches the 16-bit method reasonably well. But the 16-bit way functions are imported simply doesn't work in the 32-bit world.

    Recall that in 16-bit Windows, the fixups for an imported function are threaded through the code segment. This works great in 16-bit Windows since there was a single address space: Code segments were shared globally, and once a segment was loaded, each process could use it. But 32-bit Windows uses separate address spaces. If the fixups were threaded through the code segment, then loading a code page from disk would necessarily entail modifying it to apply the fixups, which prevents the pages from being shared by multiple processes. Even if the fixup table were kept external to the code segment, you would still have to fix up the code pages to establish the jump targets. (With sufficient cleverness, you could manage to share the pages if all the fixups on a page happened to agree exactly with those of another process, but the bookkeeping for this would get rather messy.)

    But beyond just being inefficient, the idea of applying import fixups directly to the code segment is downright impossible. The Alpha AXP has a "call direct" instruction, but it is limited to functions that are at most 128KB away. If you want to call a function that is further away, you have to load the destination address into a temporary register and call through that register. And as we saw earlier, loading a 32-bit value into a register on the Alpha AXP is a two-step operation which depends on whether bit 15 of the value you want to load is set or clear. Since this is an imported function, we have no idea at compile or link time whether the target function's address will have bit 15 set or clear.

    (And the Alpha AXP was hardly the only architecture that restricted the distance to direct calls. The Intel ia64 can make direct calls to functions up to 4MB away, and the AMD x86-64 and Intel EM64T architectures can reach up to 2GB away. This sounds like a lot until you realize that they are 64-bit processors with 16 exabytes of address space. Once again, we see that the x86 architecture is the weirdo.)

    Both of the above concerns made it undesirable (or impossible) for import fixups to modify code. Instead, import fixups have to apply to data. Rather than applying a fixup for each location an imported function was used, a single fixup is applied to a table of function pointers. This means that calls to imported functions are really indirect calls through the function pointer. On an x86, this means that instead of call ImportedFunction the generated code says call [__imp__ImportedFunction], where __imp__ImportedFunction is the name of the variable that holds the function pointer for that imported function.

    This means that resolving imported functions is a simple matter of looking up the target addresses and writing the results into the table of imported function addresses. The code itself doesn't change; it just reads the function address at runtime and calls through it.

    With that simple backgrounder, we are equipped to look at some of the deeper consequences of this design, which we will do next time.

  • The Old New Thing

    The traffic gods are punishing me for bicycling


    It happened again.

    The last time I participated in a bicycle ride that started in Seattle, I got stuck in highway traffic both going out and coming back. The 520 bridge was closed for inspection so everybody was taking the I-90 bridge instead. But traffic at the western terminal of I-90 was backed up because the Alaska Way Viaduct was closed for some sort of fundraiser walk-a-thon. And then, after the ride was over, I got stuck in traffic on the return trip as well because the Mariners baseball game had just let out, and that on top of all the traffic created by the 520 bridge being closed.

    This weekend, heading to the starting point for a light group ride through Seattle (which our group leader nicknamed "Crying over STP" since it coincided with the annual Seattle to Portland bike ride), there was a huge back-up on westbound highway 520 due to a multiple-car accident that closed both main lanes, forcing everybody to squeeze into the car pool lane. And then after the ride was over, I got stuck on the 520 bridge at around 4:10pm. The flashing lights were on, indicating that the drawbridge was open. I turned in to the Department of Transportation highway radio station and learned that the bridge was scheduled to be open from 4pm to 4:30pm for "boat fair traffic". But at least we knew how long we were going to be waiting, so I turned off the car engine, got out, and walked around the bridge. (It's not often that you get to walk on the 520 bridge. It didn't occur to me to ride my bicycle on the bridge.)

    When I got home, I tried to find any information on this scheduled closure, but turned up nothing. I guess you just had to know.

    But at least I won't get stuck in traffic next month when I head to Mercer Island to watch the Blue Angels perform, because I'm going to ride my bicycle there. We'll see whether the hills have returned.

    Postscript 1: And I hadn't known about the Elliot Bay Trail, which runs from the marina, through the trainyards, along the waterfront, to downtown Seattle. Very nice.

    Postscript 2: You can still see the after-effects of that accident on highway 520: The light barriers on the median near Hunts Point have all been scraped off!

    Postscript 3: We stopped for lunch at the Elliott Bay Marina, looking for the the sushi place that we dimly remembered, but it turns out that they no longer exist. (We had lunch at Maggie Bluff's Grill instead.) Sushi is a somewhat unorthodox bicycle food; I amused myself with the image of a support car driving up to a rider and handing over some unagi and maguro...

  • The Old New Thing

    Exported functions that are really forwarders


    Last time, we saw how the way Win32 exports functions is pretty much the same as the way 16-bit Windows exports functions, but with a change in emphasis from ordinal-based exports to name-based exports. This change in emphasis is not expressed anywhere in the file format; both 16-bit and 32-bit DLLs can export either by name or by ordinal (or by both), but the designers of Win32 were biased in spirit in favor of name-only exports.

    But there is a new type of exported function in Win32, known as a forwarder. A forwarder looks just like a regular exported function, except that the entry in the ordinal export table says, "Oh, I'm not really a function in this DLL. I'm really a function in that DLL over there." For example, if you do a link /dump /exports kernel32.dll, you'll see a line like this:

    151   EnterCriticalSection (forwarded to NTDLL.RtlEnterCriticalSection)

    This means that if a program links to KERNEL32.EnterCriticalSection, the loader silently redirects it to NTDLL.RtlEnterCriticalSection. Forwarders are a handy way to accommodate functionality moving from one DLL to another. The old DLL can continue to export the function but forward it to the new DLL.

    The forwarding trick is actually better than just having a stub function in the old DLL that calls the function in the new DLL, because the stub function creates a dependency between the old DLL and the new one. (After all, the old DLL needs to be linked to the new DLL in order to call it!) With a forwarder, however, the new DLL is not loaded unless somebody actually asks for the forwarded function from the old DLL. As a result, you don't pay for the new DLL until somebody actually wants it.

    Okay, we saw that with forwarders, Win32 has diverged from 16-bit Windows, but when it comes to imports, it's a whole new ball game. We'll pick up the story next time.

Page 2 of 4 (39 items) 1234