Linkers and Loaders

Discussing how compilers, links and loaders work and the benefits of shared libraries.

Linking is the process of combining various pieces of code and data together to form a single executable that can be loaded in memory. Linking can be done at compile time, at load time (by loaders) and also at run time (by application programs). The process of linking dates back to late 1940s, when it was done manually. Now, we have linkers that support complex features, such as dynamically linked shared libraries. This article is a succinct discussion of all aspects of linking, ranging from relocation and symbol resolution to supporting position-independent shared libraries. To keep things simple and understandable, I target all my discussions to ELF (executable and linking format) executables on the x86 architecture (Linux) and use the GNU compiler (GCC) and linker (ld). However, the basic concepts of linking remain the same, regardless of the operating system, processor architecture or object file format being used.

Compiler, Linker and Loader in Action: the Basics

Consider two program files, a.c and b.c. As we invoke the GCC on a.c b.c at the shell prompt, the following actions take place:

gcc a.c b.c
  • Run preprocessor on a.c and store the result in intermediate preprocessed file.

    cpp other-command-line options a.c /tmp/a.i
    

  • Run compiler proper on a.i and generate the assembler code in a.s

    cc1 other-command-line options /tmp/a.i  -o /tmp/a.s
    

  • Run assembler on a.s and generate the object file a.o

    as other-command-line options /tmp/a.s  -o /tmp/a.o
    

cpp, cc1 and as are the GNU's preprocessor, compiler proper and assembler, respectively. They are a part of the standard GCC distribution.

Repeat the above steps for file b.c. Now we have another object file, b.o. The linker's job is to take these input object files (a.o and b.o) and generate the final executable:

   ld other-command-line-options /tmp/a.o /tmp/b.o -o a.out

The final executable (a.out) then is ready to be loaded. To run the executable, we type its name at the shell prompt:

./a.out

The shell invokes the loader function, which copies the code and data in the executable file a.out into memory, and then transfers control to the beginning of the program. The loader is a program called execve, which loads the code and data of the executable object file into memory and then runs the program by jumping to the first instruction.

a.out was first coined as the Assembler OUTput in a.out object files. Since then, object formats have changed variedly, but the name continues to be used.

Linkers vs. Loaders

Linkers and loaders perform various related but conceptually different tasks:

  • Program Loading. This refers to copying a program image from hard disk to the main memory in order to put the program in a ready-to-run state. In some cases, program loading also might involve allocating storage space or mapping virtual addresses to disk pages.

  • Relocation. Compilers and assemblers generate the object code for each input module with a starting address of zero. Relocation is the process of assigning load addresses to different parts of the program by merging all sections of the same type into one section. The code and data section also are adjusted so they point to the correct runtime addresses.

  • Symbol Resolution. A program is made up of multiple subprograms; reference of one subprogram to another is made through symbols. A linker's job is to resolve the reference by noting the symbol's location and patching the caller's object code.

So a considerable overlap exists between the functions of linkers and loaders. One way to think of them is: the loader does the program loading; the linker does the symbol resolution; and either of them can do the relocation.

Object Files

Object files comes in three forms:

  • Relocatable object file, which contains binary code and data in a form that can be combined with other relocatable object files at compile time to create an executable object file.

  • Executable object file, which contains binary code and data in a form that can be directly loaded into memory and executed.

  • Shared object file, which is a special type of relocatable object file that can be loaded into memory and linked dynamically, either at load time or at run time.

Compilers and assemblers generate relocatable object files (also shared object files). Linkers combine these object files together to generate executable object files.

Object files vary from system to system. The first UNIX system used the a.out format. Early versions of System V used the COFF (common object file format). Windows NT uses a variant of COFF called PE (portable executable) format; IBM uses its own IBM 360 format. Modern UNIX systems, such as Linux and Solaris use the UNIX ELF (executable and linking format). This article concentrates mainly on ELF.

ELF Header

.text

.rodata

.data

.bss

.symtab

.rel.text

.rel.data

.debug

.line

.strtab

The above figure shows the format of a typical ELF relocatable object file. The ELF header starts with a 4-byte magic string, \177ELF. The various sections in the ELF relocatable object file are:

  • .text, the machine code of the compiled program.

  • .rodata, read-only data, such as the format strings in printf statements.

  • .data, initialized global variables.

  • .bss, uninitialized global variables. BSS stands for block storage start, and this section actually occupies no space in the object file; it is merely a placer holder.

  • .symtab, a symbol table with information about functions and global variables defined and referenced in the program. This table does not contain any entries for local variables; those are maintained on the stack.

  • .rel.text, a list of locations in the .text section that need to be modified when the linker combines this object file with other object files.

  • .rel.data, relocation information for global variables referenced but not defined in the current module.

  • .debug, a debugging symbol table with entries for local and global variables. This section is present only if the compiler is invoked with a -g option.

  • .line, a mapping between line numbers in the original C source program and machine code instructions in the .text section. This information is required by debugger programs.

  • .strtab, a string table for the symbol tables in the .symtab and .debug sections.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

www.onlinejobs-sales.com

Anonymous's picture

Very good article and nice explanation of linkers and loaders ...
www.onlinejobs-sales.com

I want to know that how to differentiate between library file and object file. If we have given input to linker as mixture of library file and object/relocatable files as an input , how linker will determine whether given file is library file or object file.

www.eastereggshunt.com

google ions's picture

good interpretation of linker and loader http://www.eastereggshunt.com/

discussion is incomplete

jithu's picture

Hi sandeep,

You article is pretty good, but i think it is incomplete in one sense ...

When talking about the loader, you should talk about new address space/virtual memory/process creation. That will make this discussion complete.

Explanation of Relocation.

Anshul 's picture

Sir,
This a excellent online article.
Good job! Really a nice one.
Can you give a basic example where reloaction occurs. or explain with a small program how it(program) is mapped from program's memory space address to main memory address space.
address name(or number) with add to advantage.

Linker Script

Baheerathan's picture

wat is the effect on x86 CS and DS registers when we input addresses on .SECTIONS command in linker script file ?

Fixing address of data in linker

Blitzkreig's picture

This is a very well written paper! Lucid language and a smooth flow.

I have a question regarding the relocation capabilities of the linker:

The paper mentions the linker merges the .code, .data, etc. sections and gives all symbols a run-time address. Is this assignment some default OR can the user have some control on it?...(eg: If I want the .data section to start at address 0x00000000 and fololw it up with the .code section, instead of the default way...Can I do it? If so, how?)

Thanks!

Fixing address of data in linker

Vikram Singh's picture

yep , you can do it. you will need to work on the linker script. There u can specify the desired addresses for any of the section.
for example to define a variable __executable_start if you want the linker to place your startup code at 0x92070800

PROVIDE (__executable_start = /*TEXT_ADDR*/ 0x97020800); . = /*TEXT_ADDR*/ 0x97020800;

Very good work Sandeep

Vishwanatha K's picture

Very good work...
I've never come across such a document on Linkers and Loaders online.

keep it up...

--
Regards,
Vish

Re: Linkers and Loaders

Anonymous's picture

Very good. Thanks for it.

Let me ask a question:
You wrote:

Shared libraries can be loaded from applications even in the middle of their executions. An application can request a dynamic linker to load and link shared libraries, even without linking those shared libraries to the executable.
--------------------

What do you mean by "Link shared libraries, even without
linking those shared libraries to the executable"?

Is there a kind of linking "shared libraries", which does not
link them to the executable?

Moon Jung
Korea

Re: Linkers and Loaders

Anonymous's picture

Hi, Moon Jung..

I'm a Korean, too.

There are two kinds of dynamic linking method...Explicit Linking & Implicit Linking...
Maybe, there are a little difference between shared libraries for explicit and implicit linking...

The shared libraries that you asked is the second case...
Those libraries can be loaded by LoadLibrary() and then we can call some functions parsed from GetProcAddress().

I hope this is helpful to you...

Kim, Hyoung Yuk
Korea

Re: Linkers and Loaders

Anonymous's picture

If my code (say, main()) calls "foobar();", and "void foobar(void)" is defined in library libhjk.so, then I must include "-lhjk" on the linker (ld) command line; then, the run-time linker will resolve the dynamic reference when my program is loaded. That's "implicit" linking.

If my code declares a function pointer "void (*foo_ptr)(void);", and then calls 'dlopen( "libhjk.so" ); foo_ptr = dlsym( "foobar" );' (or something like that), then my code can call foobar via foo_ptr ("(*foo_ptr)();"). In this case, since my code only contains the strings "libhjk.so" and "foobar", rather than a call to "foobar", I _don't_ need to add "-lhjk.so" to the ld command line -- but my program needs to do extra work to find the routine I want to call. That's "explicit" linking.

Explicit linking is harder to code, but it means you can add new code to your program without rerunning the static linker "ld". Apache, for example, uses explicit linking to find add-on modules, without requiring the site administrator to re-run ld on Apache; instead, a reference to the module is added to Apache's text configuration file (httpd.conf), Apache reads the file, and calls dlopen() and dlsym() to find the (standardized) entrypoint names in the new module; then it can call them when an HTTP request uses a feature handled by the new module.

Re: Linkers and Loaders

Anonymous's picture

I have to develop a relocateable loader as a part of an assignment please help
atul atulkush@yahoo.com

Re: Linkers and Loaders

Anonymous's picture

I apologize who can explain more clearly what is S, A and P, why it is S+A-P or S+A?

Thanks!

Re: Linkers and Loaders

Anonymous's picture

For ease, treat S+A as the final run-time-address of called

function, and P as the address of the next instruction

to be executed after the current one...

In PC32 type, the calls are made by adding the offset

from the instruction to the program counter, so we need

to subtract P from S + A, since that will automatically

be taken care by the architecture.

Re: Linkers and Loaders

Anonymous's picture

Two questions:

1. When the linker imports the object code to resolve a symbol does it import the entire contents of the object file or just the code bit referenced by the symbol?

2. How does the dynamic linker know where the .so files are on the file system?

Re: Linkers and Loaders

Anonymous's picture

1) The entire object module. If the module is part of an
archive, only the module containing the symbol definition
is imported (of course, that module may have unresolved
symbols requiring other modules in the archive, or
elsewhere, to resolve).
2) Environment variable : LD_LIBRARY_PATH.

Re: Linkers and Loaders

Anonymous's picture

1. As it is said in Setion "Linking with Static Libraries", the linker scans object files and achives for the definition of the symbol. So, it is not entire code.

2. File /etc/ld.so.conf contains the searching paths of .so files. Remember to run command ldconfig after edit the file.

Difference between library file and object file.

Anonymous's picture

My query is how to distinguis between library file and object file. Suppose we have given mix of library file and object/relocatable file as an input to linker. So how linker will know given file is library file or object file.

Re: Linkers and Loaders

Anonymous's picture

linux is very slow in runtime linking... konqueror needs

some seconds to start on a relative new machine

why is this the case?

Re: Linkers and Loaders

Anonymous's picture

The paper mentioned in the previous post states:

"This paper is based on gcc 2.95, many of the issues described here have been fixed in gcc 3.1."

Indeed, KDE is faster if built with gcc 3.2, but it is still a CPU hog. It would be useful to know which issues remain with gcc3.2, and how to either fix or design around these problems.

Re: Linkers and Loaders

Anonymous's picture

I believe this is a QT problem, most of the time consumed in KDE is at the dynamic linker.

This doc explains it -

Making C++ ready for the desktop

Re: Linkers and Loaders

Anonymous's picture

Actually the latest versions of HP-UX for the IA-64 platform use ELF objects and name the shared objects with the .so extension.

Older versions of HP-UX for the PA platform use the .sl extension for shared object files.

Re: Linkers and Loaders

Anonymous's picture

I think this is a fine introduction to the subject matter. As a programmer coming from the Windoze world, I couldn't imagine how easy it is to create a dynamic library in Linux.

More articles like these, please!

MG

Solaris .so loading problem

Subrata's picture

Hi I am Subrata from India. I have a very strange prob with Solaris. I have a 3rd party shared object file say A.so. From my module I generate another shared object file say B.so which call A.so. I have saparate executable from which I load my B.so which will in turn load A.so. My program compiles fine.I link my B.so with A.so at compile time. But when I start my prog it crashes after loding my B.so saying segmentation fault.This problem was solved when I link my executable(main exe) with A.so. If anyone have any solution mail me at subrata1in@yahoo.co.in .Pls help me ...............

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix