The efficiency of ordinal-based imports while still being name-based

Date:July 28, 2006 / year-entry #255
Tags:other
Orig Link:https://blogs.msdn.microsoft.com/oldnewthing/20060728-00/?p=30313
Comments:    10
Summary:Reader Tom brought up the interesting point that ordinal-based imports are slightly faster than name-based, though not by much. But if even that tiny fraction of a percentage bothers you, you can still get the benefits of ordinal-based imports while still being name-based. People are more familiar with the first half of the "rebase and...

Reader Tom brought up the interesting point that ordinal-based imports are slightly faster than name-based, though not by much. But if even that tiny fraction of a percentage bothers you, you can still get the benefits of ordinal-based imports while still being name-based.

People are more familiar with the first half of the "rebase and bind" duo than the second. But it's binding that speeds up import table resolution. When a DLL is "bound" to another DLL, information about the target DLL is cached in the original DLL. Specifically, the timestamp of the target (so that the loader can detect whether the cache is valid), the ordinal corresponding to the name (the "hint"), and the address of the ultimate function. For example, if I had a DLL that linked to kernel32!LocalAlloc the entry in the DLL would go something like this:

"Hello. I would like to link to these functions in kernel32. Oh, and by the way, all the hints I'm about to give you are based on the Aug 04 00:56:36 2004 version of KERNEL32.DLL. As for the function LocalAlloc, I believe that the function resides at address 0x7C8099BD, and that you'll find it in kernel32's named export table in position 247."

When the loader goes to resolve the import, it checks the timestamp of the target file on the computer with the one cached in the DLL. If they match, then it doesn't need to do any look-ups at all; it justs uses the cached value (0x7C8099BD). If they don't match (for example, maybe there was a kernel32 hot-fix), it can still use the look-up hint: Before doing the binary search for LocalAlloc, it looks directly at slot 247 to see if LocalAlloc is there. If so, then the cost of the binary search has been avoided, and the overhead of the look-up over a pure ordinal import is just one string comparison.


Comments (10)
  1. Sebastian Redl says:

    How does it know that slot 247 actually IS LocalAlloc? Does it save the names along with the ordinal? I thought those were two separate tables, one matching names to ordinals and one matching ordinals to addresses.

    [Sorry, I wasn’t clear enough. I’ve updated the entry. It’s slot 247 in the name table (the table that maps names to ordinals). -Raymond]
  2. Ryan says:

    ..and a timestamp comparison.

  3. Tom says:

    Actually, I think it was me what pointed that out.  :) And I’m sorry for the bad link in that post.  It should be http://msdn.microsoft.com/msdnmag/issues/0500/hood/ without the trailing angle bracket. (Whoever wrote the link detection in the blog software should really fix that bug).

    The ‘bind’ utility that performs the DLL binding is part of the Platform SDK.  Some documentation on it is available at http://windowssdk.msdn.microsoft.com/en-us/library/ms726407.aspx

    [Oops, sorry about the attribution. (I don’t think the people who write the blog software read my blog comments.) -Raymond]
  4. BryanK says:

    What happens if the file timestamp matches, but kernel32 (or whatever DLL — this isn’t very likely with kernel32) can’t be loaded at its preferred base address?  The cached address (0x7C8099BD) would be wrong in that case, right?  (If that’s actually a memory address, and not an RVA or something, then it would be.)

    I assume there’s code in the loader to handle this case properly (i.e. fall back to either the ordinal hint or the name)?

    [Obviously. The purpose of this entry was not to provide the algorithm in excruciating detail. -Raymond]
  5. Daniel says:

    BryanK:  That would just require a simple subtraction of the preferred base and addition of the actual base to the cached value.

  6. microbe says:

    : it justs uses the cached value (0x7C8099BD). If they don’t match (for example, maybe there was a kernel32 hot-fix)…

    How does it know they don’t match? I assume this value is just the entry address of the function. What other information could be obtained easily from this address to verify?

    [The “they” that match/don’t match are the cached timestamp and the actual timestamp on the file. -Raymond]
  7. Stu says:

    So what happens if somehow the timestamps match, but the .dlls are different?

    [I think you have a pretty good idea what happens. -Raymond]
  8. Miral says:

    Wouldn’t it be better if the checksum field in the PE header was actually populated by default, and it matched on that rather than the timestamp?  That seems like a more reliable means of detecting a matching DLL.

    [Consider the cost of enforcing the checksum. -Raymond]
  9. Tom says:

    Raymond commented
    >Consider the cost of enforcing the checksum

    If you were using it, you wouldn’t need to recalculate the checksum, it would just be one more 32 bit word you check to see if the DLL matches. It would only be calcuated by the linker when the DLL was built.

    /I once worked on an embedded system which this information to compare module versions.

    uint32 Checksum;   // Just a sum of bytes
    uint16 FileLength;
    uint8  VersionNumber;

    If any of these did not match, a new version would be downloaded. Unfortunately, the checksum was just an arithmetic sum of bytes, not a CRC, and there were some very small files where the order of bytes could change but nothing else. E.g.

    0x01, 0x02, 0x03 has the same sum as
    0x02, 0x01, 0x03

    The one byte version number was added to handle this. When you built new software, you checked for the file contents changing without altering the byte sum, and handled it by bumping the version byte manually.

    There were date and time fields too, but the module comparer had been hacked to ignore them, since otherwise ‘rebuilding from the same label would cause loads of unnecessary downloads’. Sheesh.

    [But who verifies that the checksum is correct? What would prevent a linker from setting all checksums to zero like they do today? -Raymond]
  10. Mike Dimmick says:

    Well, you could refuse to load any DLLs that didn’t have the checksum set, but that would break every DLL ever shipped. The kernel does enforce the checksum for kernel mode – when I first installed Virtual PC on Windows 2000 from an MSDN download, the ISO had (silently) burned incorrectly and the VPC network driver was corrupted, so driver wouldn’t load. This caused Windows 2000 to bugcheck. On Windows XP it merely caused the network stack to stop working.

    At this point I obtained ISOBuster and extracted the contents of the ISO to my hard disk, and installed from there. Much better.

    [As I understand it, the original question was a hypothetical: “What if we required the checksum from day 1…” The first point is that without enforcement you haven’t gained anything. The second point is that enforcement in user-mode means you lose demand-paging. -Raymond]

Comments are closed.


*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:

<-- Back to Old New Thing Archive Index