5 ms·

A ToC of the 20-part linker essay (2008)

64 points by _qc3o 12y ago

rayiner 12y ago
See also: http://www.iecc.com/linkers/ http://www.iecc.com/linkers/
userbinator 12y ago
As someone who has worked far more with dynamic linking in Windows the ELF system has always seemed needlessly complex; the extra indirections of the GOT/PLT mechanism and PIC are avoided by simply linking DLLs with different load addresses (so they don't always need to be relocated, but can be if necessary), and the only thing that needs to be associated with a symbol is an address. Makes it especially convenient when writing things like in-memory executable compression and shared data between processes. The ability to "import X from Y" easily is also nice. Anyone with experience from the other side (working with ELFs and then moving into Windows) want to share their views?
- cordite 12y ago
  I just happen to know that at work where I do VB6, the loaders are inefficient if it is to probe for a load address, so it is best to give one that doesn't collide with other dll/ocx's that are loaded.
- yew 12y ago
  I don't have much experience with the Windows model, but if I'm understanding you correctly . . . ELF does support load-time relocation, as appears to be done under Windows if two base addresses conflict. That just isn't the standard way of doing things, for several reasons. First, load-time relocation imposes a cost at startup (whereas PIC imposes a smaller cost throughout the lifetime of the process). I'm given to understand that, back in the day, the startup delay for programs using large shared libraries could be quite noticeable. Second, load-time relocation reduces in-memory text section sharing in the case where relocation is performed. If your goal in using shared libraries is saving RAM, this is a problem. Third, it's a matter of inertia. Originally, UNIX shared libraries (a.out format) were built with a static, non-relocatable base address. Library authors had to coordinate via a central authority to ensure compatibility. PIC seemed like a good way to get as far away from that problem as possible - or so I understand. Indirection through the GOT/PLT also serves another purpose, even in load-time relocation code - it enables replacing a symbol in one shared library with a symbol from another (eg via LD_PRELOAD). Though that's more of a side benefit than a justification.
  - deleted 12y ago
    [deleted]
  - quotemstr 12y ago
    Keep in mind that you don't need text relocations for code sequences that are naturally PC-relative, like jumps on x86, or pretty much anything on ARM and amd64. Windows DLLs don't need text relocations for references to other modules: the IAT (Import Address Table) does pretty much the same thing as the GOT and in pretty much the same way.
    - yew 12y ago
      Sure. Much of what I wrote is very x86 specific! Though I believe that a degree of indirection is preserved on AMD64 to enable symbol interposition?
      - quotemstr 12y ago
        > Though I believe that a degree of indirection is preserved on AMD64 to enable symbol interposition? You really don't want symbol interdiction. You don't use it most of the time, and the rest of the time, you're just changing a call that looks like: foo(1, 2); to (*g_foo)(1, 2); Which do you think is faster? There's a reason everything on Android compiles with -Bsymbolic (which kills interdiction for calls between functions in the same module). You really should be compiling all your code with -Bsymbolic -fvisibility=hidden; explicitly export the symbols you want other modules to call.
        yew 12y ago
        The first is faster, of course. Whether or not I want the second depends entirely on what I'm doing :) It certainly shouldn't be the default - it isn't very useful during normal work - but I've been glad to have it before. I wouldn't recommend -Bsymbolic by default unless you know it's safe for your environment, though. There is software that uses symbol interposition to 'productive' ends in production (not much of it, thank heavens). Mobile platforms are something of a special case.
- quotemstr 12y ago
  I've worked extensively with both ELF and PE systems --- I was on the Windows Perf team and the Windows Phone core team, and now I do low-level Android goo at Facebook. I vastly prefer the Windows shared library model. In addition to the advantages you mention, the Windows per-DLL symbol namesystem system is much better than ELF's hazardous model: in ELF, accidental interposition is a big hazard, so you have to very carefully namespace the symbols exported from a shared object. In Windows (and in OS X), symbol name collisions are simply not a problem: there's no global namespace in which symbols can collide. Yes, you still have DLL _name_ collisions, but SxS addresses that problem nicely. As a result, hosting unrelated bits of code in the same process is very common in the Windows world and uncommon in the ELF world. RTLD_LOCAL and RTLD_DEEPBIND are completely unnecessary. Another advantage Windows has in practice is default symbol visibility. Windows DLLs export only the symbols you explicitly instruct your compiler and linker to export --- through export files or compiler annotations. The default in ELF systems is to export everything that's not file-static. This configuration is particularly fun when combined with the namespace problem. While Unixish compilers can be configured to work like Windows and export only needed symbols, I've found that very few people do. These people then go on to wonder why shared libraries are slow and the binaries so large. (-Bsymbolic helps, of course.) If I were benevolent POSIX dictator for life, one of my edicts (although not my first one) would be to require an OS-X-style two-level namespace and hidden symbol visibility by default. Yes, LD_PRELOAD interposition gets harder. Just deal with it and modify functions directly. The ELF dynamic linking mechanism is designed to emulate static linking. That's like designing cars to neigh and occasionally kick people to death with robot legs that exist only for this purpose. Also, it's a minor thing, but LoadLibrary in Windows returns a pointer to the PE header. dlopen is nowhere near that simple, nor is the in-memory representation of a shared object as useful. (It'd also be nice if dladdr1 got some documentation. Also, it'd be nice if Bionic weren't even more awful than glibc in this respect.)
  - brigade 12y ago
    > The ELF dynamic linking mechanism is designed to emulate static linking. That's like designing cars to neigh and occasionally kick people to death with robot legs that exist only for this purpose. So I'm only passingly familiar with the state of OS's back before I was born, but between "your code works unchanged between static and dynamic linking, you just have to change your build system which is already OS dependent" and "how you export and import symbols in the source code varies depending on how you're linking and also which OS you're building on and which compiler you're using", the former seems less insane.
- pjc50 12y ago
  Related question: is any of the Windows shared library system covered by software patents?
  - pjmlp 12y ago
    Not sure, but AIX used to have a similar shared library model.
  - dbrower 12y ago
    Shared libraries and DLL's came into being before the software patent flood opened, probably by 10 years or so.
- weinzierl 12y ago
  One disadvantage of the Windows system is, as far as I understand it, that, once relocation happens the libraries can't be shared in memory anymore. This defeats the purpose of a shared object somewhat. After the loader patched in the new addresses the pages making up the library contain different data for multiple copies of your library, and differ from the data in the PE file. So the PE file can't simply be mmaped and the same pages can't be used by different processes. I'm not saying this is a big issue, but I think it's a difference worth mentioning.
bookface 12y ago
If anybody prefers a .mobi: http://www.filedropper.com/linkers-ianlancetaylor http://www.filedropper.com/linkers-ianlancetaylor (If anyone has a suggestion for a good place to upload that, let me know. I don't know whether the site I found on Google is sketchy.)

64 points by _qc3o 12y ago

See also: http://www.iecc.com/linkers/ http://www.iecc.com/linkers/

As someone who has worked far more with dynamic linking in Windows the ELF system has always seemed needlessly complex; the extra indirections of the GOT/PLT mechanism and PIC are avoided by simply linking DLLs with different load addresses (so they don't always need to be relocated, but can be if necessary), and the only thing that needs to be associated with a symbol is an address. Makes it especially convenient when writing things like in-memory executable compression and shared data between processes. The ability to "import X from Y" easily is also nice. Anyone with experience from the other side (working with ELFs and then moving into Windows) want to share their views?

cordite 12y ago
I just happen to know that at work where I do VB6, the loaders are inefficient if it is to probe for a load address, so it is best to give one that doesn't collide with other dll/ocx's that are loaded.
yew 12y ago
I don't have much experience with the Windows model, but if I'm understanding you correctly . . . ELF does support load-time relocation, as appears to be done under Windows if two base addresses conflict. That just isn't the standard way of doing things, for several reasons. First, load-time relocation imposes a cost at startup (whereas PIC imposes a smaller cost throughout the lifetime of the process). I'm given to understand that, back in the day, the startup delay for programs using large shared libraries could be quite noticeable. Second, load-time relocation reduces in-memory text section sharing in the case where relocation is performed. If your goal in using shared libraries is saving RAM, this is a problem. Third, it's a matter of inertia. Originally, UNIX shared libraries (a.out format) were built with a static, non-relocatable base address. Library authors had to coordinate via a central authority to ensure compatibility. PIC seemed like a good way to get as far away from that problem as possible - or so I understand. Indirection through the GOT/PLT also serves another purpose, even in load-time relocation code - it enables replacing a symbol in one shared library with a symbol from another (eg via LD_PRELOAD). Though that's more of a side benefit than a justification.
- deleted 12y ago
  [deleted]
- quotemstr 12y ago
  Keep in mind that you don't need text relocations for code sequences that are naturally PC-relative, like jumps on x86, or pretty much anything on ARM and amd64. Windows DLLs don't need text relocations for references to other modules: the IAT (Import Address Table) does pretty much the same thing as the GOT and in pretty much the same way.
  - yew 12y ago
    Sure. Much of what I wrote is very x86 specific! Though I believe that a degree of indirection is preserved on AMD64 to enable symbol interposition?
    - quotemstr 12y ago
      > Though I believe that a degree of indirection is preserved on AMD64 to enable symbol interposition? You really don't want symbol interdiction. You don't use it most of the time, and the rest of the time, you're just changing a call that looks like: foo(1, 2); to (*g_foo)(1, 2); Which do you think is faster? There's a reason everything on Android compiles with -Bsymbolic (which kills interdiction for calls between functions in the same module). You really should be compiling all your code with -Bsymbolic -fvisibility=hidden; explicitly export the symbols you want other modules to call.
      - yew 12y ago
        The first is faster, of course. Whether or not I want the second depends entirely on what I'm doing :) It certainly shouldn't be the default - it isn't very useful during normal work - but I've been glad to have it before. I wouldn't recommend -Bsymbolic by default unless you know it's safe for your environment, though. There is software that uses symbol interposition to 'productive' ends in production (not much of it, thank heavens). Mobile platforms are something of a special case.
quotemstr 12y ago
I've worked extensively with both ELF and PE systems --- I was on the Windows Perf team and the Windows Phone core team, and now I do low-level Android goo at Facebook. I vastly prefer the Windows shared library model. In addition to the advantages you mention, the Windows per-DLL symbol namesystem system is much better than ELF's hazardous model: in ELF, accidental interposition is a big hazard, so you have to very carefully namespace the symbols exported from a shared object. In Windows (and in OS X), symbol name collisions are simply not a problem: there's no global namespace in which symbols can collide. Yes, you still have DLL _name_ collisions, but SxS addresses that problem nicely. As a result, hosting unrelated bits of code in the same process is very common in the Windows world and uncommon in the ELF world. RTLD_LOCAL and RTLD_DEEPBIND are completely unnecessary. Another advantage Windows has in practice is default symbol visibility. Windows DLLs export only the symbols you explicitly instruct your compiler and linker to export --- through export files or compiler annotations. The default in ELF systems is to export everything that's not file-static. This configuration is particularly fun when combined with the namespace problem. While Unixish compilers can be configured to work like Windows and export only needed symbols, I've found that very few people do. These people then go on to wonder why shared libraries are slow and the binaries so large. (-Bsymbolic helps, of course.) If I were benevolent POSIX dictator for life, one of my edicts (although not my first one) would be to require an OS-X-style two-level namespace and hidden symbol visibility by default. Yes, LD_PRELOAD interposition gets harder. Just deal with it and modify functions directly. The ELF dynamic linking mechanism is designed to emulate static linking. That's like designing cars to neigh and occasionally kick people to death with robot legs that exist only for this purpose. Also, it's a minor thing, but LoadLibrary in Windows returns a pointer to the PE header. dlopen is nowhere near that simple, nor is the in-memory representation of a shared object as useful. (It'd also be nice if dladdr1 got some documentation. Also, it'd be nice if Bionic weren't even more awful than glibc in this respect.)
- brigade 12y ago
  > The ELF dynamic linking mechanism is designed to emulate static linking. That's like designing cars to neigh and occasionally kick people to death with robot legs that exist only for this purpose. So I'm only passingly familiar with the state of OS's back before I was born, but between "your code works unchanged between static and dynamic linking, you just have to change your build system which is already OS dependent" and "how you export and import symbols in the source code varies depending on how you're linking and also which OS you're building on and which compiler you're using", the former seems less insane.
pjc50 12y ago
Related question: is any of the Windows shared library system covered by software patents?
- pjmlp 12y ago
  Not sure, but AIX used to have a similar shared library model.
- dbrower 12y ago
  Shared libraries and DLL's came into being before the software patent flood opened, probably by 10 years or so.
weinzierl 12y ago
One disadvantage of the Windows system is, as far as I understand it, that, once relocation happens the libraries can't be shared in memory anymore. This defeats the purpose of a shared object somewhat. After the loader patched in the new addresses the pages making up the library contain different data for multiple copies of your library, and differ from the data in the PE file. So the PE file can't simply be mmaped and the same pages can't be used by different processes. I'm not saying this is a big issue, but I think it's a difference worth mentioning.

bookface 12y ago

If anybody prefers a .mobi: http://www.filedropper.com/linkers-ianlancetaylor http://www.filedropper.com/linkers-ianlancetaylor (If anyone has a suggestion for a good place to upload that, let me know. I don't know whether the site I found on Google is sketchy.)