Shared library writeup: Part 3

I ended last time by talking about how the dynamic linker had to run before an ELF file could run. Currently, in other words, the dynamic linker has been loaded into the memory space of the process that we want to run, and we're going to run the linker before we can run our actual application.

We cannot run the linker quite yet, however. The linker has to know where it should transfer control to after it has completed whatever it is supposed to do. This is accomplished by the kernel - it puts an auxiliary vector on top of the process' stack. This vector is a name-value array (or in Python terms, a dictionary), and it already contains the values I talked about last time - the PT_INTERP value which is contained in the p_offset field of the ELF program header. In addition to these, a number of other values are added to the auxiliary vector. The values that can be added like this are defined in the elf.h header file, and have the prefix AT_. After this vector has been set up, control is finally transferred to the dynamic linker. The linker's entry point is defined in the ELF header of the linker, in the e_entry field.

Trusting the linker

At this point the (dynamic) linker is supposed to do its magic. It has three tasks:

• Determine and load dependencies
• Relocate the application and all dependencies
• Initialize the application and dependencies in the correct order

The paper doesn't go into detail on the first and last point - I suppose the author considers them trivial - but the key to speeding up these two points is having fewer dependencies: the time needed to sort through all dependencies and load them in order usually scales worse than linearly with the number of dependencies. However, the relocation process is usually the most expensive part of the linker's tasks, scaling at least as $O(R+nr)$, where $R$ is the number of relative relocations, $r$ is the number of absolute relocations, and $n$ is the total number of DSOs in the application. Also, there could be additional overhead associated with the symbols in the process, depending on which ELF extensions are being used and so on. In such cases, the cost can be $O(R+nrlog\; s)$, where $s$ is the number of symbols.