2 The Dynamic Linker

The dynamic linker is the program that manages shared dynamic libraries on behalf of an executable. It works to load libraries into memory and modify the program at runtime to call the functions in the library.

ELF allows executables to specify an interpreter, which is a program that should be used to run the executable. The compiler and static linker set the interpreter of executables that rely on dynamic libraries to be the dynamic linker.

ianw@lime:~/programs/csbu$ readelf --headers /bin/ls

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x4000000000000040 0x4000000000000040
                 0x0000000000000188 0x0000000000000188  R E    8
  INTERP         0x00000000000001c8 0x40000000000001c8 0x40000000000001c8
                 0x0000000000000018 0x0000000000000018  R      1
      [Requesting program interpreter: /lib/ld-linux-ia64.so.2]
  LOAD           0x0000000000000000 0x4000000000000000 0x4000000000000000
                 0x0000000000022e40 0x0000000000022e40  R E    10000
  LOAD           0x0000000000022e40 0x6000000000002e40 0x6000000000002e40
                 0x0000000000001138 0x00000000000017b8  RW     10000
  DYNAMIC        0x0000000000022f78 0x6000000000002f78 0x6000000000002f78
                 0x0000000000000200 0x0000000000000200  RW     8
  NOTE           0x00000000000001e0 0x40000000000001e0 0x40000000000001e0
                 0x0000000000000020 0x0000000000000020  R      4
  IA_64_UNWIND   0x0000000000022018 0x4000000000022018 0x4000000000022018
                 0x0000000000000e28 0x0000000000000e28  R      8
Example 2.1 Checking the program interpreter

You can see above that the interpreter is set to be /lib/ld-linux-ia64.so.2, which is the dynamic linker. When the kernel loads the binary for execution, it will check if the PT_INTERP field is present, and if so load what it points to into memory and start it.

We mentioned that dynamically linked executables leave behind references that need to be fixed with information that isn't available until runtime, such as the address of a function in a shared library. The references that are left behind are called relocations.

2.1 Relocations

The essential part of the dynamic linker is fixing up addresses at runtime, which is the only time you can know for certain where you are loaded in memory. A relocation can simply be thought of as a note that a particular address will need to be fixed at load time. Before the code is ready to run you will need to go through and read all the relocations and fix the addresses it refers to to point to the right place.

Table 2.1.1 Relocation Example
AddressAction
0x123456Address of symbol "x"
0x564773Function X

There are many types of relocation for each architecture, and each types exact behaviour is documented as part of the ABI for the system. The definition of a relocation is quite straight forward.

typedef struct {
  Elf32_Addr    r_offset;  <--- address to fix
  Elf32_Word    r_info;    <--- symbol table pointer and relocation type
}

typedef struct {
  Elf32_Addr    r_offset;
  Elf32_Word    r_info;
  Elf32_Sword   r_addend;
} Elf32_Rela
Example 2.1.1 Relocation as defined by ELF

The r_offset field refers to the offset in the file that needs to be fixed up. The r_info field specifies the type of relocation which describes what exactly must be done to fix this code up. The simplest relocation usually defined for an architecture is simply the value of the symbol. In this case you simply substitute the address of the symbol at the location specified, and the relocation has been "fixed-up".

The two types, one with an addend and one without specify different ways for the relocation to operate. An addend is simply something that should be added to the fixed up address to find the correct address. For example, if the relocation is for the symbol i because the original code is doing something like i[8] the addend will be set to 8. This means "find the address of i, and go 8 past it".

That addend value needs to be stored somewhere. The two solutions are covered by the two forms. In the REL form the addend is actually store in the program code in the place where the fixed up address should be. This means that to fix up the address properly, you need to first read the memory you are about to fix up to get any addend, store that, find the "real" address, add the addend to it and then write it back (over the addend). The RELA format specifies the addend right there in the relocation.

The trade offs of each approach should be clear. With REL you need to do an extra memory reference to find the addend before the fixup, but you don't waste space in the binary because you use relocation target memory. With RELA you keep the addend with the relocation, but waste that space in the on disk binary. Most modern systems use RELA relocations.

2.1.1 Relocations in action

The example below shows how relocations work. We create two very simple shared libraries and reference one from in the other.

$ cat addendtest.c
extern int i[4];
int *j = i + 2;

$ cat addendtest2.c
int i[4];

$ gcc -nostdlib -shared -fpic -s -o addendtest2.so addendtest2.c
$ gcc -nostdlib -shared -fpic -o addendtest.so addendtest.c ./addendtest2.so

$ readelf -r ./addendtest.so

Relocation section '.rela.dyn' at offset 0x3b8 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
0000000104f8  000f00000027 R_IA64_DIR64LSB   0000000000000000 i + 8
Example 2.1.1.1 Specifying Dynamic Libraries

We thus have one relocation in addendtest.so of type R_IA64_DIR64LSB. If you look this up in the IA64 ABI, the acronym can be broken down to

  1. R_IA64 : all relocations start with this prefix.

  2. DIR64 : a 64 bit direct type relocation

  3. LSB : Since IA64 can operate in big and little endian modes, this relocation is little endian (least significant byte).

The ABI continues to say that that relocation means "the value of the symbol pointed to by the relocation, plus any addend". We can see we have an addend of 8, since sizeof(int) == 4 and we have moved two int's into the array (*j = i + 2). So at runtime, to fix this relocation you need to find the address of symbol i and put its value, plus 8 into 0x104f8.

2.2 Position Independence

In an executable file, the code and data segment is given a specified base address in virtual memory. The executable code is not shared, and each executable gets its own fresh address space. This means that the compiler knows exactly where the data section will be, and can reference it directly.

Libraries have no such guarantee. They can know that their data section will be a specified offset from the base address; but exactly where that base address is can only be known at runtime.

Consequently all libraries must be produced with code that can execute no matter where it is put into memory, known as position independent code (or PIC for short). Note that the data section is still a fixed offset from the code section; but to actually find the address of data the offset needs to be added to the load address.