Linkers and Loaders

John R. Levine

Mentioned 12

Whatever your programming language, whatever your platform, you probably tap into linker and loader functions all the time. But do you know how to use them to their greatest possible advantage? Only now, with the publication of Linkers & Loaders, is there an authoritative book devoted entirely to these deep-seated compile-time and run-time processes. The book begins with a detailed and comparative account of linking and loading that illustrates the differences among various compilers and operating systems. On top of this foundation, the author presents clear practical advice to help you create faster, cleaner code. You'll learn to avoid the pitfalls associated with Windows DLLs, take advantage of the space-saving, performance-improving techniques supported by many modern linkers, make the best use of the UNIX ELF library scheme, and much more. If you're serious about programming, you'll devour this unique guide to one of the field's least understood topics. Linkers & Loaders is also an ideal supplementary text for compiler and operating systems courses. *Includes a linker construction project written in Perl, with project files available for download. *Covers dynamic linking in Windows, UNIX, Linux, BeOS, and other operating systems. *Explains the Java linking model and how it figures in network applets and extensible Java code. *Helps you write more elegant and effective code, and build applications that compile, load, and run more efficiently.

More on Amazon.com

Mentioned in questions and answers.

I'm trying to figure out how to execute machine code stored in memory.

I have the following code:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    FILE* f = fopen(argv[1], "rb");

    fseek(f, 0, SEEK_END);
    unsigned int len = ftell(f);
    fseek(f, 0, SEEK_SET);

    char* bin = (char*)malloc(len);
    fread(bin, 1, len, f);

    fclose(f);

    return ((int (*)(int, char *)) bin)(argc-1, argv[1]);
}

The code above compiles fine in GCC, but when I try and execute the program from the command line like this:

./my_prog /bin/echo hello

The program segfaults. I've figured out the problem is on the last line, as commenting it out stops the segfault.

I don't think I'm doing it quite right, as I'm still getting my head around function pointers.

Is the problem a faulty cast, or something else?

What you are trying to do is something akin to what interpreters do. Except that an interpreter reads a program written in an interpreted language like Python, compiles that code on the fly, puts executable code in memory and then executes it.

You may want to read more about just-in-time compilation too:

Just in time compilation
Java HotSpot JIT runtime

There are libraries available for JIT code generation such as the GNU lightning and libJIT, if you are interested. You'd have to do a lot more than just reading from file and trying to execute code, though. An example usage scenario will be:

  1. Read a program written in a scripting-language (maybe your own).
  2. Parse and compile the source into an intermediate language understood by the JIT library.
  3. Use the JIT library to generate code for this intermediate representation, for your target platform's CPU.
  4. Execute the JIT generated code.

And for executing the code you'd have to use techniques such as using mmap() to map the executable code into the process's address space, marking that page executable and jumping to that piece of memory. It's more complicated than this, but its a good start in order to understand what's going on beneath all those interpreters of scripting languages such as Python, Ruby etc.

The online version of the book "Linkers and Loaders" will give you more information about object file formats, what goes on behind the scenes when you execute a program, the roles of the linkers and loaders and so on. It's a very good read.

I'm interested in writing an x86 assembler for a hobby project.

At first it seemed fairly straight forward to me but the more I read into it, the more unanswered questions I find myself having. I'm not totally inexperienced: I've used MIPs assembly a fair amount and I've written a toy compiler for a subset of C in school.

My goal is to write a simple, but functional x86 assembler. I'm not looking to make a commercially viable assembler, but simply a hobby project to strengthen my knowledge in certain areas. So I don't mind if I don't implement every available feature and operation.

I have many questions such as: Should I use a one-pass or two-pass method? Should I use ad-hoc parsing or define formal grammars and use a parser-generator for my instructions? At what stage, and how do I resolve the addresses of my symbols?

Given my requirements, can anyone suggest some general guidelines for the methods I should be using in my pet-project assembler?

You may find the dragon book to be helpful.

The actual title is Compilers: Principles, Techniques, and Tools (amazon.com).

Check out the Intel Architectures Software Developer's Manuals for the complete documentation of the IA-32 and IA-64 instruction sets.

AMD's architecture technical documents are available on its website as well.

Linkers and Loaders (amazon.com) is a good introduction to object formats and linking issues. (The unedited original manuscript is also available online.)

A quick question about elf file headers, I can't seem to find anything useful on how to add/change fields in the elf header. I'd like to be able to change the magic numbers and to add a build date to the header, and probably a few other things.

As I understand it the linker creates the header information, but I don't see anything in the LD script that refers to it (though i'm new to ld scripts).

I'm using gcc and building for ARM.

thanks!

Updates:

  • ok maybe my first question should be: is it possible to create/edit the header file at link time?

I didn't finish the book but iirc Linkers and Loaders by John Levine had the gory details that you would need to be able to do this.

Assume library A has a() and b(). If I link my program B with A and call a(), does b() get included in the binary? Does the compiler see if any function in the program call b() (perhaps a() calls b() or another lib calls b())? If so, how does the compiler get this information? If not, isn't this a big waste of final compile size if I'm linking to a big library but only using a minor feature?

Take a look at link-time optimization. This is necessarily vendor dependent. It will also depend how you build your binaries. MS compilers (2005 onwards at least) provide something called Function Level Linking -- which is another way of stripping symbols you don't need. This post explains how the same can be achieved with GCC (this is old, GCC must've moved on but the content is relevant to your question).

Also take a look at the LLVM implementation (and the examples section).

I suggest you also take a look at Linkers and Loaders by John Levine -- an excellent read.

There is a lot of information out there about designing and implementing a compiler, but i can't find anything about linkers.

I'm very interested in these subjects but I can't find any information about linkers. Does anyone know a tutorial, book, etc. about linker design and implementation?

The classic book on linkers: Linkers and Loaders. A draft of it is available online.

Ian Lance Taylor recently implemented a new ELF linker (gold). He wrote a series of blog posts explaining a lot of details. Start here.

I am curious about the things happend before main() is called , such like load the executable into memory , dynamic load of shared library. Do you have any suggestions how to understand these things by a hand-on exercise?

The tools amd things I know of ,and using now, includes:

  • strace
  • disassemble
  • readelf
  • /proc/pid/map

NOTES: I know the great book linkers and loaders, but hands-on exercise may teach me better than reading the book.

  • The ld.so man page documents several environment variables that may be set to either tweak the dynamic linking process or provide additional details.

e.g.

LD_DEBUG=all cat </dev/null
  • You can easily obtain the source code for each and every piece involved - Linux kernel, dynamic linker, C library, startup code (crt0.o or similar). You could start by studying the code and making experimental modifications.

I want to write a little function's tracer. I use ptrace.

When I see a CALL instruction, I want to show the function name equivalent to the address call.

My tracer work with symbols with absolute address (symbol define in the main binary). But I don't know how I can get the absolute address in virtual memory of the function of the shared library. Detect the call to libc's functions for example.

I notice that the address of the function in the shared library is relative to the file.

Does the following equation is good?

Absolute address of symbol = address of the shared library in virtual memory +
                             relative address of the symbol.

How can I get the absolute address of a symbol from a shared library?

The book 'Linkers and Loaders' contains answers to such questions, as well as the background explanations. It might be worth a read. What applies to ELF doesn't apply on Windows, but the book covers both - and some other systems too.

I'm using C language on windows. This question was previously part of What happens to identifiers in a program? . I broke it to reduce no. of questions. This is a standalone query (doesn't depend on the previous question)

If there is nothing to link (i.e.. I'm not using any libraries. I know it wont be of any use.) will the linker change the object code output of assembler? If so what does it change?

I heard that LINKER also does the operation of some memory mapping. I don't understand how. The program is not running, its just in the manufacturing stage. How could linker map to memory? How would it look like? What all are the functions of LINKER?

When people refer to "relocation" , "address binding". I don't really get what they mean. What is it & what is its purpose?

Some debuggers show info like : call stack: 0xfffef32 , 0xf3234fe etc.. Its at the run time right? or is the the memory addresses of so called "memory mapping" of linker?

when people refer to something like symbols or symbol table. Do they mean identifiers(variable names, constant names, function names)?

I searched info on internet but couldn't find anything useful. May be I'm not sure what to search for. I don't want to read big books on this. But if there are any articles, tutorials which clear concepts. That would also be helpful.

I'm a novice programmer. So, it would be great you can explain in simple but technical terms.

Not an answer, just a suggestion: buy "Linkers and Loaders", read it a few times. It's amazingly helpful.

Please suggest some website or some book that deals with these topics in really good detail.

I need to have a better understanding of these concepts (in reference to C++):

  1. stack and heaps
  2. symbol tables
  3. implementation of scope rules
  4. implementation of function calls

Try online version of the "Linkers &Loaders" book. Chapter 11 may help you with these concepts w.r.t C++. A very good book to get your fundamentals right. Try Gustavo's excellent blog to understand concepts of memory management (stack, heap and a lot more).

I have some question regarding shared libraries

  1. Who will load shared libraries when I run binary depends on shared libraries(.so)?

  2. Where shared libraries loaded?

  3. If shared libraries were already loaded and I run binary depends on loaded libraries, in this case shared libraries will going to be loaded or binary will use loaded libraries?

The answer to your questions 1 and 2 is: it depends (on the OS you are using). On most UNIX OSes, the runtime loader (usually ld.so or ld-linux.so) will load shared libraries, wherever it pleases to do so.

For question 3, usually shared libraries are shared between processes, so yes: a newly-loaded executable will re-use shared libraries that are already loaded by some other process. Note: only code (and read-only data) segment is shared; each process gets its own copy of writable data segment.

Looking for an answer drawing from credible and/or official sources.

For Linux, this guide details the process of shared library loading (likely with more details than you care about).

Also, this book has an early draft available on-line.

Please suggest some good resource to understand the function load_elf_binary...I have tried googlin on the topic but was unable to find anything helpful.

"Linkers and Loaders" by John Levine.

I have created 2 C programs in Ubuntu(Linux 2.6) as below

1.c
----
main()
{
}

2.c
----
#include<stdio.h>
main()
{
int a[500];
float f[1000];
double d[100000];
int i = 0;
for(i = 0;i < 10000;i++);  // Intentional ;
for(i = 0;i < 10000;i++);  // Intentional ;
for(i = 0;i < 10000;i++);  // Intentional ;
for(i = 0;i < 10000;i++);  // Intentional ;
if(1)
{
}
else
{
}
switch(1)
{
}
while(1);
}

After separately compiled and created executable files,I checked the size of both the executables.To my surprise the size of both the executables were same(7099 bytes).

However the size of object file differs.

Someone please explain me why the executable size was same for program 1.c and 2.c.Program 2.c should have used more space and executable size should have got increased right? How linker links C keywords(like int,float,while,if..) and creates executable file?

Thanks a lot

I believe that's related to optimizer. But, for linker I suggest reading the points below since you showed curiosity about linkers. Reading these would help any C & C++ programmer. Knowing what linking actually means is an important knowledge.

For more info:

Note: This may not be what you were looking for but researching and learning what you're looking for by yourself will make what you learned last longer.