prelink.tex

\documentclass[twoside]{article}

\def\docversion{0.7}
% timezone: +01 == CET
\def\timezone{+01}
% Uncomment for draft print.
\def\isdraft{1}

\newif\ifpdf
\ifx\pdfoutput\undefined
  \pdffalse % we are not running PDFLaTeX
\else
  \pdfoutput=1 % we are running PDFLaTeX
  \pdftrue
\fi

\usepackage{linuxtag}
\usepackage{times}
\usepackage{makeidx}
\usepackage{nomencl}
\usepackage[square]{natbib}
\usepackage{marvosym}
\usepackage{longtable}
\renewcommand\bibsection{\chapter{\bibname}}

\ifpdf
  \usepackage[pdftex]{graphics}
  \usepackage{type1cm}
  \usepackage{thumbpdf}
  \pdfcompresslevel9
  \pdfinfo{/CreationDate (D:20030924012900\timezone'00')}
  % The following code to set /ModDate comes from Heiko Oberdiek's paper
  % one PDF & hyperref.  I only added the \timezone stuff.
  \begingroup
    \def\twodigits#1{\ifnum#1<10 0\fi\the#1}%
    \count0=\time \divide\count0 by 60
    \edef\x{\twodigits{\count0}}%
    \multiply\count0 by 60
    \count1=\time \advance\count1 by -\count0
    \edef\x{\x\twodigits{\count1}}%
    \edef\x{/ModDate (D:\the\year \twodigits\month \twodigits\day \x 00\timezone'00')}%
    \expandafter\endgroup
  \expandafter\pdfinfo\expandafter{\x}%
  \input pdfcolor

  %% For a "Draft" mark on the pages uncomment the following:
  \ifx\isdraft\undefined
    \relax
  \else
    \usepackage{eso-pic}
    \usepackage{color}
    \makeatletter
      \AddToShipoutPicture{\rm%
        \setlength{\@tempdimb}{.5\paperwidth}%
        \setlength{\@tempdimc}{.5\paperheight}%
        \setlength{\unitlength}{1pt}%
        \put(\strip@pt\@tempdimb,\strip@pt\@tempdimc){%
          \makebox(0,0){\rotatebox{45}{\textcolor[gray]{0.9}{\fontsize{5cm}{5cm}\selectfont{Draft}}}}
        }
    }
    \makeatother
  \fi
\else
  \usepackage[dvips]{graphics}
\fi

\def\titlecolor{NavyBlue}
\makeatletter
\def\@sect#1#2#3#4#5#6[#7]#8{%
  \ifnum #2>\c@secnumdepth
    \let\@svsec\@empty
  \else
    \refstepcounter{#1}%
    \protected@edef\@svsec{\@seccntformat{#1}\relax}%
  \fi
  \@tempskipa #5\relax
  \ifdim \@tempskipa>\z@
    \begingroup
      \hbox{\expandafter\csname\titlecolor\endcsname#6{%
        \@hangfrom{\hskip #3\relax\@svsec}%
          \interlinepenalty \@M #8\@@par}\Black}%
    \endgroup
    \csname #1mark\endcsname{#7}%
    \addcontentsline{toc}{#1}{%
      \ifnum #2>\c@secnumdepth \else
        \protect\numberline{\csname the#1\endcsname}%
      \fi
      #7}%
  \else
    \def\@svsechd{%
      \hbox{\expandafter\csname\titlecolor\endcsname#6{\hskip #3\relax
      \@svsec #8}%
      \csname #1mark\endcsname{#7}\Black}%
      \addcontentsline{toc}{#1}{%
        \ifnum #2>\c@secnumdepth \else
          \protect\numberline{\csname the#1\endcsname}%
        \fi
        #7}}%
  \fi
  \@xsect{#5}}
\def\@ssect#1#2#3#4#5{%
  \@tempskipa #3\relax
  \ifdim \@tempskipa>\z@
    \begingroup
      \expandafter\csname\titlecolor\endcsname#4{%
        \@hangfrom{\hskip #1}%
          \interlinepenalty \@M #5\@@par}\Black%
    \endgroup
  \else
    \def\@svsechd{\expandafter\csname\titlecolor\endcsname#4{\hskip #1\relax #5}\Black}%
  \fi
  \@xsect{#3}}
\makeatother

\usepackage{fancyheadings}
\pagestyle{fancy}
\rhead{}
\chead{}
\lhead{}
\rfoot[\sl Prelink]{\thepage}
\lfoot[\thepage]{\sl Jakub Jel\'\i nek}
\ifx\isdraft\undefined
\cfoot{Version \docversion}
\else
\cfoot{Draft \docversion}
\fi
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\ifx\isdraft\undefined
\relax
\else
\usepackage[mathlines]{lineno}
\fi

\usepackage{graphicx}
\usepackage{hyperref}
\hypersetup{
  bookmarksnumbered,
  bookmarksopen=true,
  pdfpagemode=UseOutlines,
  pdfkeywords={Prelink, ELF, DSO, Shared Library, Dynamic Linking, Linux}
}
\usepackage{prelinklisting}

\def\tts#1{\texttt{\small #1}}

\setcounter{dbltopnumber}{3}


\makeatletter
\newcommand{\annotate}[2][]{%
  \marginpar{%
    \pdfstringdef\x@title{#1}%
    \edef\r{\string\r}%
    \pdfstringdef\x@contents{#2}%
    \pdfannot
    width 50em%\linewidth
    height .5\baselineskip
    depth 2.5\baselineskip
    {
      /Subtype /Text
      /T (\x@title)
      /Contents (\x@contents)
      }%
    }
  }
\makeatother

\makeglossary
\makeindex

\begin{document}

  \makeatletter
  \newcommand\orgmaketitle{}
  \let\orgmaketitle\maketitle
  \def\maketitle{%
    \hypersetup{
      pdftitle={\@title},
      pdfsubject={Description of prelink tool},
      pdfauthor={\@author}
    }%
    \orgmaketitle
  }
  \makeatother

\title{Prelink}
\author{Jakub Jel\'\i nek\\
Red Hat, Inc.\\
{\small\tt\href{mailto:jakub@redhat.com}{jakub@redhat.com}}}

%\maketitle

%\tableofcontents
%\vfil\break
%\listoftables
%\vfil\break
%\listofprelinklistings
%\vfil\break
%\listoffigures
%\vfil\break

\maketitle

\begin{center}
\begin{abstract}
\vspace*{.5\baselineskip}
\parbox{0.8\textwidth}{%
Prelink is a tool designed to speed up dynamic linking of ELF
programs on various Linux architectures.
It speeds up start up of OpenOffice.org 1.1 by 1.8s from 5.5s on 651MHz Pentium III.}
\end{abstract}
\end{center}

\ifx\isdraft\undefined
  \relax
\else
  \linenumbers
  \linenumbersep4pt
\fi

\section{Preface}

In 1995, Linux changed its binary format from \tts{a.out} to \tts{ELF}.
The \tts{a.out} binary format was very inflexible and shared libraries
were pretty hard to build.  Linux's shared libraries in \tts{a.out} are position
dependent and each had to be given a unique virtual address space slot
at link time.  Maintaining these assignments was pretty hard even when
there were just a few shared libraries, there used to be a central address
registry maintained by humans in form of a text file, but it is certainly
impossible to do these days when there are thousands of different shared libraries
and their size, version and exported symbols are constantly changing.
On the other side, there was just minimum amount of work the dynamic
linker had to do in order to load these shared libraries, as relocation
handling and symbol lookup was only done at link time.  The dynamic linker
used the \tts{uselib} system call which just mapped the named library
into the address space (with no segment or section protection differences,
the whole mapping was writable and executable).

The \href{http://www.caldera.com/developers/devspecs/gabi41.pdf}%
{\tts{ELF}}
\footnote{As described in generic ABI document [1] and various processor
specific ABI supplements [2], [3], [4], [5], [6], [7], [8].}
binary format is one of the most flexible binary formats,
its shared libraries are easy to build and there is no need for a central
assignment of virtual address space slots.  Shared libraries are position
independent and relocation handling and symbol lookup are done partly
at the time the executable is created and partly at runtime.  Symbols in shared
libraries can be overridden at runtime by preloading a new shared
library defining those symbols or without relinking an executable by adding
symbols to a shared library which is searched up earlier during symbol
lookup or by adding new dependent shared libraries to a library used by the
program.  All these improvements have their price, which is a slower
program startup, more non-shareable memory per process and runtime cost
associated with position independent code in shared libraries.

Program startup of \tts{ELF} programs is slower than startup of \tts{a.out}
programs with shared libraries, because the dynamic linker has much more work
to do before calling program's entry point.  The cost of loading libraries
is just slightly bigger, as \tts{ELF} shared libraries have typically
separate read-only and writable segments, so the dynamic linker
has to use different memory protection for each segment.
The main difference is in relocation handling and associated symbol lookup.
In the \tts{a.out} format there was no relocation handling or symbol lookup at runtime.
In \tts{ELF}, this cost is much more important today than it used to be
during \tts{a.out} to \tts{ELF} transition in Linux, as especially GUI
programs keep constantly growing and start to use more and more shared
libraries.  5 years ago programs using more than 10 shared libraries
were very rare, these days most of the GUI programs link against around
40 or more shared and in extreme cases programs use even more than 90
shared libraries.  Every shared library adds its set of dynamic relocations
to the cost and enlarges symbol search scope,
\nomenclature{Symbol Search Scope}{The sequence of \tts{ELF} objects in
which a symbol is being looked up.  When a symbol definition is found,
the searching stops and the found symbol is returned.  Each program
has a global search scope, which starts by the executable, is typically
followed by the immediate dependencies of the executable and then their
dependencies in breadth search order (where only first occurrence
of each shared library is kept).  If \tts{DT\_FILTER}
or \tts{DT\_AUXILIARY} dynamic tags are used the order is slightly
different.  Each shared library loaded with \tts{dlopen} has its
own symbol search scope which contains that shared library and
its dependencies.  \tts{Prelink} operates also with natural
symbol search scope of each shared library, which is the global
symbol search scope the shared library would have if it were started
as the main program}
so in addition to doing more symbol lookups, each symbol
lookup the application has to perform is on average more expensive.
Another factor increasing the cost is the length of symbol names
which have to be compared when finding symbol in the symbol hash table of
a shared library.  C++ libraries tend to have extremely long symbol
names and unfortunately the new \href{http://www.codesourcery.com/cxx-abi/}%
{C++ ABI} puts namespaces and class names first and method names last
in the mangled names, so often symbol names differ only in last
few bytes of very long names.

Every time a relocation is applied the entire memory page
\nomenclature{Page}{Memory block of fixed size which virtual memory
subsystem deals with as a unit.  The size of the page depends on
the addressing hardware of the processor, typically pages are 4K or 8K,
in some cases bigger}
containing the address which is written to must be loaded into memory.
The operating system does a copy-on-write operation which also has the
consequence that the physical memory of the memory page cannot anymore
be shared with other processes.
With \tts{ELF}, typically all of program's Global Offset Table,
\nomenclature{Global Offset Table (\tts{GOT})}{When position independent
code needs to build address which requires dynamic relocation, instead
of building it as constant in registers and applying a dynamic relocation
against the read-only segment (which would mean that any pages of the
read-only segment where relocations are applied cannot be shared between
processes anymore), it loads the address from an offset table
private to each shared library, which is created by the linker.
The table is in writable segment and relocations are applied against it.
Position independent code uses on most architectures a special \tts{PIC}
register which points to the start of the Global Offset Table}
constants and variables containing pointers to objects in shared libraries, etc.
are written into before the dynamic linker passes control over to the program.

On most architectures (with some exceptions like \tts{AMD64} architecture)
position independent code requires that one register needs to be dedicated as
\tts{PIC} register and thus cannot be used in the functions for other purposes.
This especially degrades performance on register-starved
architectures like \tts{IA-32}.  Also, there needs to be some code to
set up the \tts{PIC} register, either invoked as part of function prologues,
or when using function descriptors in the calling sequence.

\tts{Prelink} is a tool which (together with corresponding dynamic linker
and linker changes) attempts to bring back some of the \tts{a.out}
advantages (such as the speed and less COW'd pages) to the \tts{ELF}
binary format while retaining all of its flexibility.  In a limited way
it also attempts to decrease number of non-shareable pages created by
relocations.
\tts{Prelink} works closely with the dynamic linker in the GNU C library,
but probably it wouldn't be too hard to port it to some other \tts{ELF}
using platforms where the dynamic linker can be modified in similar
ways.

\section{Caching of symbol lookup results}

Program startup can be speeded up by caching of symbol lookup
results\footnote{Initially, this has been implemented in the \tts{prelink}
tool and \tts{glibc} dynamic linker, where \tts{prelink} was sorting
relocation sections of existing executables and shared libraries.
When this has been implemented in the linker as well and most executables
and shared libraries are already built with \tts{-z combreloc},
the code from \tts{prelink} has been removed, as it was no longer
needed for most objects and just increasing the tool's complexity.}.
Many shared libraries need more than one lookup of a particular symbol.
This is especially true for C++ shared libraries, where e.g. the same method
is present in multiple virtual tables or {\sl RTTI} data structures.
\nomenclature{RTTI}{C++ runtime type identification}
Traditionally, each \tts{ELF} section which needs dynamic relocations has an
associated \tts{.rela*} or \tts{.rel*} section (depending on whether
the architecture is defined to use \tts{RELA} or \tts{REL} relocations).
\nomenclature{RELA}{Type of relocation structure which includes offset,
relocation type, symbol against which the relocation is and an integer
addend which is added to the symbol.  Memory at offset is not supposed
to be used by the relocation.  Some architectures got this implemented
incorrectly and memory at offset is for some relocation types used
by the relocation, either in addition to addend or addend is not used
at all.  \tts{RELA} relocations are generally better for \tts{prelink},
since when \tts{prelink} stores a pre-computed value into the memory location
at offset, the addend value is not lost}
\nomenclature{REL}{Type of relocation structure which includes just offset,
relocation type and symbol.  Addend is taken from memory location at
offset}
The relocations in those sections are typically sorted by ascending
\tts{r\_offset} values.
Symbol lookups are usually the most expensive operation during program
startup, so caching the symbol lookups has potential to decrease time
spent in the dynamic linker.
One way to decrease the cost of symbol lookups is to create a table with the
size equal to number of entries
in dynamic symbol table (\tts{.dynsym}) in the dynamic linker when resolving
a particular shared library, but that would in some cases need a lot of
memory and some time spent in initializing the table.  Another option
would be to use a hash table with chained lists, but that needs both
extra memory and would also take extra time for computation of the hash value
and walking up the chains when doing new lookups.
Fortunately, neither of this is really necessary if we modify the linker
to sort relocations so that relocations against the same symbol
are adjacent.  This has been done first in the \tts{Sun} linker and dynamic
linker, so the GNU linker and dynamic linker use the same \tts{ELF} extensions
and linker flags.  Particularly, the following new \tts{ELF} dynamic tags have been introduced:

\tts{\#define DT\_RELACOUNT    0x6ffffff9}\\
\tts{\#define DT\_RELCOUNT     0x6ffffffa}

New options \tts{-z combreloc} and \tts{-z nocombreloc} have been
added to the linker.  The latter causes the previous linker behavior,
i.e. each section requiring relocations has a corresponding relocation section,
which is sorted by ascending \tts{r\_offset}.  \tts{-z combreloc}
\footnote{\tts{-z combreloc} is the default in GNU linker versions
2.13 and later.} instructs the linker to create just one relocation
section for dynamic relocations other than symbol jump table (\tts{PLT})
relocations.
\nomenclature{PLT}{Process Linkage Table.  Stubs in \tts{ELF} shared
libraries and executables which allow lazy relocations of function calls.
They initially point to code which will do the symbol lookup.  The
result of this symbol lookup is then stored in the Process Linkage Table
and control transfered to the address symbol lookup returned.  All
following calls to the \tts{PLT} slot just branch to the already looked
up address directly, no further symbol lookup is needed}
This single relocation section (either \tts{.rela.dyn} or \tts{.rel.dyn})
is sorted, so that relative relocations come first (sorted by ascending
\tts{r\_offset}), followed by other relocations, sorted again by ascending
\tts{r\_offset}.  If more relocations are against the same
symbol, they immediately follow the first relocation against that symbol
with lowest \tts{r\_offset}.
\footnote{In fact the sorting needs to take into account also the type of
lookup.  Most of the relocations will resolve to a \tts{PLT} slot in the executable
if there is one for the lookup symbol, because the executable might have a
pointer against that symbol without any dynamic relocations.  But e.g.
relocations used for the \tts{PLT} slots must avoid these.}.
\nomenclature{relative relocation}{Relocation, which doesn't need a symbol
lookup, just adds a shared library load offset to certain memory location
(or locations)}
The number of relative relocations at the beginning of the section
is stored in the \tts{DT\_RELACOUNT} resp. \tts{DT\_RELCOUNT} dynamic tag.

The dynamic linker can use the new dynamic tag for two purposes.
If the shared library is successfully mapped at the same address
as the first \tts{PT\_LOAD} segment's virtual address, the load offset
is zero and the dynamic linker can avoid all the relative relocations which
would just add zero to various memory locations.  Normally shared libraries are
linked with first \tts{PT\_LOAD} segment's virtual address set to zero, so
the load offset is non-zero.  This can be changed through a linker script or by
using a special \tts{prelink} option \tts{--reloc-only} to change
the base address of a shared library.  All prelinked shared libraries
have non-zero base address as well.  If the load offset is non-zero, the
dynamic linker can still make use of this dynamic tag, as relative
relocation handling is typically way simpler than handling other
relocations (since symbol lookup is not necessary) and thus it can
handle all relative relocations in a tight loop in one place and
then handle the remaining relocations with the fully featured
relocation handling routine.  The second and more important point is
that if relocations against the same symbol are adjacent, the dynamic
linker can use a cache with single entry.

The dynamic linker in \tts{glibc}, if it sees \tts{statistics}
as part of the \tts{LD\_DEBUG} environment variable, displays statistics
which can show how useful this optimization is.
Let's look at some big C++ application, e.g. konqueror.
If not using the cache, the statistics looks like this:

\noindent{\small\begin{verbatim}
18000:     runtime linker statistics:
18000:       total startup time in dynamic loader: 270886059 clock cycles
18000:                 time needed for relocation: 266364927 clock cycles (98.3%)
18000:                      number of relocations: 79067
18000:           number of relocations from cache: 0
18000:             number of relative relocations: 31169
18000:                time needed to load objects: 4203631 clock cycles (1.5%)
\end{verbatim}}

This program run is with hot caches, on non-prelinked system, with lazy
binding.
\nomenclature{Lazy Binding}{A way to postpone symbol lookups for calls until
a function is called for the first time in particular shared library.
This decreases number of symbol lookups done during startup and symbols
which are never called don't need to be looked up at all.  Calls requiring
relocations jump into \tts{PLT}, which is initially set up so that a
function in the dynamic linker is called to do symbol lookup.  The looked
up address is then stored either into the \tts{PLT} slot directly
(if \tts{PLT} is writable) or into \tts{GOT} entry corresponding
to the \tts{PLT slot} and any subsequent calls already go directly to that
address.  Lazy binding can be turned off by setting \tts{LD\_BIND\_NOW=1}
in the environment.  Prelinked programs never use lazy binding for the
executable or any shared libraries not loaded using \tts{dlopen}}
The numbers show that the dynamic linker spent most of its time
in relocation handling and especially symbol lookups.  If using symbol
lookup cache, the numbers look different:

\noindent{\small\begin{verbatim}
18013:       total startup time in dynamic loader: 132922001 clock cycles
18013:                 time needed for relocation: 128399659 clock cycles (96.5%)
18013:                      number of relocations: 25473
18013:           number of relocations from cache: 53594
18013:             number of relative relocations: 31169
18013:                time needed to load objects: 4202394 clock cycles (3.1%)
\end{verbatim}}

On average, for one real symbol lookup there were two cache hits and total
time spent in the dynamic linker decreased by 50\%.

\section{Prelink design}

\tts{Prelink} was designed, so that it requires as few \tts{ELF} extensions
as possible.  It should not be tied to a particular architecture, but
should work on all \tts{ELF} architectures.  During program startup it
should avoid all symbol lookups which, as has been shown above, are
very expensive.  It needs to work in an environment where shared
libraries and executables are changing from time to time, whether it is
because of security updates or feature enhancements.  It should avoid big code
duplication between the dynamic linker and the tool.  And prelinked
shared libraries need to be usable even in non-prelinked executables,
or when one of the shared libraries is upgraded and the prelinking of the
executable has not been updated.

To minimize the number of performed relocations during startup,
the shared libraries (and executables) need to be relocated
already as much as possible.  For relative relocations this means the library
needs to be loaded always at the same base address, for other relocations
this means all shared libraries with definitions those relocations resolve
to (often this includes all shared libraries the library or executable depends on)
must always be loaded at the same addresses.  \tts{ELF} executables
(with the exception of {\sl Position Independent Executables})
\nomenclature{Position Independent Executable}{A hybrid between
classical \tts{ELF} executables and \tts{ELF} shared libraries.
It has a form of a \tts{ET\_DYN} object like shared libraries and should
contain position independent code, so that the kernel can load
the executable starting at random address to make certain security attacks
harder.  Unlike shared libraries it contains \tts{DT\_DEBUG} dynamic
tag, must have \tts{PT\_INTERP} segment with dynamic linker's path,
must have meaningful code at its \tts{e\_entry} and can use symbol
lookup assumptions normal executables can make, particularly that
no symbol defined in the executable can be overridden by a shared
library symbol} have their load address fixed already during linking.
For shared libraries, \tts{prelink} needs something similar to \tts{a.out}
registry of virtual address space slots.  Maintaining such registry
across all installations wouldn't scale well, so \tts{prelink} instead
assigns these virtual address space slots on the fly after looking at
all executables it is supposed to speed up and all their dependent shared
libraries.  The next step is to actually relocate shared libraries
to the assigned base address.

When this is done, the actual prelinking of shared libraries can be done.
First, all dependent shared libraries need to be prelinked (\tts{prelink}
doesn't support circular dependencies between shared libraries, will just
warn about them instead of prelinking the libraries in the cycle), then for each
relocation in the shared library \tts{prelink} needs to look up the symbol
in natural symbol search scope of the shared library (the shared library
itself first, then breadth first search of all dependent shared libraries) and
apply the relocation to the symbol's target section.  The symbol lookup code
in the dynamic linker is quite complex and big, so to avoid duplicating all
this, \tts{prelink} has chosen to use dynamic linker to do the symbol lookups.
Dynamic linker is told via a special environment variable it should print
all performed symbol lookups and their type and \tts{prelink} reads this
output through a pipe.  As one of the requirements was that
prelinked shared libraries must be usable even for non-prelinked executables
(duplicating all shared libraries so that there are pristine and prelinked
copies would be very unfriendly to RAM usage), \tts{prelink} has to ensure
that by applying the relocation no information is lost and thus relocation
processing can be cheaply done at startup time of non-prelinked executables.
For \tts{RELA} architectures this is easier, because the content
of the relocation's target memory is not needed when processing the relocation.
\footnote{Relative relocations on certain \tts{RELA} architectures use
relocation target's memory, either alone or together with \tts{r\_addend}
field.}  For \tts{REL} architectures this is not the case.
\tts{prelink} attempts some tricks described
later and if they fail, needs to convert the \tts{REL} relocation section
to \tts{RELA} format where addend is stored in the relocation section
instead of relocation target's memory.

When all shared libraries an executable (directly or indirectly) depends on
are prelinked, relocations in the executable are handled similarly to
relocations in shared libraries.  Unfortunately, not all symbols resolve the
same when looked up in a shared library's natural symbol search scope
(i.e. as it is done at the time the shared library is prelinked) and when
looked up in application's global symbol search scope.  Such symbols are
herein called {\sl conflicts} and the relocations against those symbols
{\sl conflicting relocations}.  Conflicts depend on the executable, all its
shared libraries and their respective order.  They are only computable
for the shared libraries linked to the executable (libraries mentioned in
\tts{DT\_NEEDED} dynamic tags and shared libraries they transitively need).
The set of shared libraries loaded via \tts{dlopen(3)} cannot be predicted
by \tts{prelink}, neither can the order in which this happened, nor the time
when they are unloaded.  When the dynamic linker prints symbol lookups
done in the executable, it also prints conflicts.  \tts{Prelink} then
takes all relocations against those symbols and builds a special
\tts{RELA} section with conflict fixups and stores it into the
prelinked executable.  Also a list of all dependent shared libraries
in the order they appear in the symbol search scope, together
with their checksums and times of prelinking is stored in another special
section.

The dynamic linker first checks if it is itself prelinked.  If yes,
it can avoid its preliminary relocation processing (this one is done
with just the dynamic linker itself in the search scope, so that
all routines in the dynamic linker can be used easily without too many
limitations).  When it is about to start a program, it first looks
at the library list section created by \tts{prelink} (if any) and
checks whether they are present in symbol search scope in the same
order, none have been modified since prelinking and that there aren't any
new shared libraries loaded either.  If all these conditions are
satisfied, prelinking can be used.  In that case the dynamic linker
processes the fixup section and skips all normal relocation handling.
If one or more of the conditions are not met, the dynamic linker continues
with normal relocation processing in the executable and all shared libraries.

\section{Collecting executables and libraries which should be prelinked}

Before the actual work can start the \tts{prelink} tool needs to collect the
filenames of executables and libraries it is supposed to prelink.
It doesn't make any sense to prelink a shared library if no executable is
linked against it because the prelinking information will not be used anyway.
Furthermore, when \tts{prelink} needs to do a \tts{REL} to \tts{RELA}
conversion of relocation sections in the shared library (see later)
or when it needs to convert \tts{SHT\_NOBITS} \tts{PLT} section to
\tts{SHT\_PROGBITS}, a prelinked shared library might grow in size and so
prelinking is only desirable if it will speed up startup of some
program.  The only change which might be useful even for shared libraries
which are never linked against, only loaded using \tts{dlopen}, is
relocating to a unique address.  This is useful if there are many relative
relocations and there are pages in the shared library's writable segment
which are never written into with the exception of those relative
relocations.  Such shared libraries are rare, so \tts{prelink} doesn't
handle these automatically, instead the administrator or developer can
use \tts{prelink --reloc-only={\sl ADDRESS}} to relocate it manually.
Prelinking an executable requires all shared libraries it is linked against
to be prelinked already.

\tts{Prelink} has two main modes in which it collects filenames.
One is {\sl incremental prelinking}, where \tts{prelink} is invoked without
the \tts{-a} option.  In this mode, \tts{prelink} queues for prelinking
all executables and shared libraries given on the command line, all executables
in directory trees specified on the command line, and all shared libraries
those executables and shared libraries are linked against.
For the reasons mentioned earlier a shared library is queued only if a
program is linked with it or the user tells the tool to do it anyway
by explicitly mentioning it on the command line.
The second mode is {\sl full prelinking}, where the \tts{-a} option is
given on the command line.  This in addition to incremental prelinking
queues all executables found in directory trees specified in \tts{prelink.conf}
(which typically includes all or most directories where system executables
are found).  For each directory subtree in the config file the user
can specify whether symbolic links to places outside of the tree are to be followed
or not and whether searching should continue even across filesystem
boundaries.

There is also an option to blacklist some executables or directory trees
so that the executables or anything in the directory trees will not
be prelinked.  This can be specified either on the command line or in
the config file.

\tts{Prelink} will not attempt to change executables which use a non-standard
dynamic linker
\footnote{Standard dynamic linker path is hardcoded in the executable for each
architecture.  It can be overridden from the command line, but only with
one dynamic linker name (normally, multiple standard dynamic linkers are
used when prelinking mixed architecture systems).}
for security reasons, because it actually needs to execute the dynamic
linker for symbol lookup and it needs to avoid executing some random
unknown executable with the permissions with which \tts{prelink} is run
(typically \tts{root}, with the permissions at least for changing all
executables and shared libraries in the system).  The administrator should
ensure that \tts{prelink.conf} doesn't contain world-writable directories
and such directories are not given to the tool on the command line either,
but the tool should be distrustful of the objects nevertheless.

Also, \tts{prelink} will not change shared libraries which are not specified
directly on the command line or located in the directory trees specified on the
command line or in the config file.  This is so that
e.g. \tts{prelink} doesn't try to change shared libraries on shared
networked filesystems, or at least it is possible to configure the tool
so that it doesn't do it.

For each executable and shared library it collects, \tts{prelink} executes
the dynamic linker to list all shared libraries it depends on, checks if
it is already prelinked and whether any of its dependencies changed.
Objects which are already prelinked and have no dependencies which changed
don't have to be prelinked again (with the exception when e.g. virtual
address space layout code finds out it needs to assign new virtual address space slots
for the shared library or one of its dependencies).  Running the dynamic
linker to get the symbol lookup information is a quite costly
operation especially on systems with many executables and shared libraries
installed, so \tts{prelink} offers a faster \tts{-q} mode.  In all modes,
\tts{prelink} stores modification and change times of each shared library
and executable together with all object dependencies and other information
into \tts{prelink.cache} file.  When prelinking in \tts{-q} mode, it
just compares modification and change times of the executables and shared
libraries (and all their dependencies).  Change time is needed because
\tts{prelink} preserves modification time when prelinking (as well as
permissions, owner and group).  If the times match, it assumes the
file has not changed since last prelinking.  Therefore the file can be
skipped if it is already prelinked and none of the dependencies changed.
If any time changed or one of the dependencies changed, it invokes the
dynamic linker the same way as in normal mode to find out real dependencies,
whether it has been prelinked or not etc.  The collecting phase in normal
mode can take a few minutes, while in quick mode usually takes just a few
seconds, as the only operation it does is it calls just lots of \tts{stat}
system calls.

\section{Assigning virtual address space slots}

\tts{Prelink} has to ensure at least that for all successfully prelinked
executables all shared libraries they are (transitively) linked against
have non-overlapping virtual address space slots (furthermore they
cannot overlap with the virtual address space range used by the executable
itself, its \tts{brk} area, typical stack location and \tts{ld.so.cache}
and other files mmaped by the dynamic linker in early stages of dynamic
linking (before all dependencies are mmaped).  If there were any overlaps,
the dynamic linker (which mmaps the shared libraries at the desired location
without \tts{MAP\_FIXED} mmap flag so that it is only soft requirement) would
not manage to mmap them at the assigned locations and the prelinking
information would be invalidated (the dynamic linker would have to do all
normal relocation handling and symbol lookups).  Executables are linked against
very wide variety of shared library combinations and that has to be taken
into account.

The simplest approach is to sort shared libraries by descending
usage count (so that most often used shared libraries like the dynamic
linker, \tts{libc.so} etc. are close to each other) and assign them
consecutive slots starting at some architecture specific base address
(with a page or two in between the shared libraries to allow for a limited
growth of shared libraries without having to reposition them).
\tts{Prelink} has to find out which shared libraries will need
a \tts{REL} to \tts{RELA} conversion of relocation sections
and for those which will need the conversion count with the increased size
of the library's loadable segments.  This is \tts{prelink} behavior without
\tts{-m} and \tts{-R} options.

The architecture specific base address is best located a few megabytes above
the location where \tts{mmap} with \tts{NULL} first argument and without
\tts{MAP\_FIXED} starts allocating memory areas (in Linux this is the value
of \tts{TASK\_UNMAPPED\_BASE} macro).
\footnote{\tts{TASK\_UNMAPPED\_BASE} has been chosen
on each platform so that there is enough virtual memory for both the
\tts{brk} area (between executable's end and this memory address) and \tts{mmap}
area (between this address and bottom of stack).}  The reason for not
starting to assign addresses in \tts{prelink} immediately at
\tts{TASK\_UNMAPPED\_BASE} is that \tts{ld.so.cache} and other mappings by
the dynamic linker will end up in the same range and could overlap with
the shared libraries.  Also, if some application uses \tts{dlopen} to load
a shared library which has been prelinked,
\footnote{Typically this is because some other executable is linked against that
shared library directly.}
those few megabytes above \tts{TASK\_UNMAPPED\_BASE} increase the probability
that the stack slot will be still unused (it can clash with e.g.
non-prelinked shared libraries loaded by \tts{dlopen} earlier
\footnote{If shared libraries have first \tts{PT\_LOAD} segment's virtual
address zero, the kernel typically picks first empty slot above
\tts{TASK\_UNMAPPED\_BASE} big enough for the mapping.} or other kinds
of mmap calls with \tts{NULL} first argument like \tts{malloc} allocating
big chunks of memory, mmaping of locale database, etc.).

This simplest approach is unfortunately problematic on 32-bit (or 31-bit)
architectures where the total virtual address space for a process is
somewhere between 2GB (S/390) and almost 4GB (Linux IA-32 4GB/4GB kernel
split, AMD64 running 32-bit processes, etc.).  Typical installations these
days contain thousands of shared libraries and if each of them is given a
unique address space slot, on average executables will have pretty sparse
mapping of its shared libraries and there will be less contiguous virtual
memory for application's own use
\footnote{Especially databases look these days for every byte of virtual
address space on 32-bit architectures.}.

\tts{Prelink} has a special mode, turned on with \tts{-m} option, in which
it computes what shared libraries are ever loaded together in some executable
(not considering \tts{dlopen}).  If two shared libraries are ever loaded
together, \tts{prelink} assigns them different virtual address space slots,
but if they never appear together, it can give them overlapping addresses.
For example applications using \tts{KDE} toolkit link typically against many
\tts{KDE} shared libraries, programs written using the \tts{Gtk+} toolkit
link typically against many \tts{Gtk+} shared libraries, but there are just
very few programs which link against both \tts{KDE} and \tts{Gtk+} shared
libraries, and even if they do, they link against very small subset of those
shared libraries.  So all \tts{KDE} shared libraries not in that subset can
use overlapping addresses with all \tts{Gtk+} shared libraries but the
few exceptions.  This leads to considerably smaller virtual address space
range used by all prelinked shared libraries, but it has its own
disadvantages too.  It doesn't work too well with incremental prelinking,
because then not all executables are investigated, just those which are given
on \tts{prelink}'s command line.  \tts{Prelink} also considers executables
in \tts{prelink.cache}, but it has no information about executables which have
not been prelinked yet.  If a new executable, which links against some shared
libraries which never appeared together before, is prelinked later,
\tts{prelink} has to assign them new, non-overlapping addresses.
This means that any executables, which linked against the library
that has been moved and re-prelinked, need to be prelinked again.
If this happened during incremental prelinking, \tts{prelink} will
fix up only the executables given on the command line, leaving other
executables untouched.  The untouched executables would not be able to
benefit from prelinking anymore.

Although with the above two layout schemes shared library addresses can
vary slightly between different hosts running the same distribution
(depending on the exact set of installed executables and libraries), especially
the most often used shared libraries will have identical base addresses
on different computers.  This is often not desirable for security reasons,
because it makes it slightly easier for various exploits to jump to routines
they want.  Standard Linux kernels assign always the same addresses to
shared libraries loaded by the application at each run, so with these
kernels \tts{prelink} doesn't make things worse.  But there are kernel
patches, such as Red Hat's \tts{Exec-Shield}, which randomize memory
mappings on each run.  If shared libraries are prelinked, they cannot
be assigned different addresses on each run (prelinking information can
be only used to speed up startup if they are mapped at the base addresses
which was used during prelinking), which
means prelinking might not be desirable on some edge servers.
\tts{Prelink} can assign different addresses on different hosts though,
which is almost the same as assigning random addresses on each run
for long running processes such as daemons.  Furthermore, the administrator
can force full prelinking and assignment of new random addresses every few
days (if he is also willing to restart the services, so that the old
shared libraries and executables don't have to be kept in memory).

To assign random addresses \tts{prelink} has the \tts{-R} option.
This causes a random starting address somewhere in the architecture specific
range in which shared libraries are assigned, and minor random reshuffling
in the queue of shared libraries which need address assignment (normally
it is sorted by descending usage count, with randomization shared libraries
which are not very far away from each other in the sorted list can be
swapped).  The \tts{-R} option should work orthogonally to the \tts{-m}
option.

Some architectures have special further requirements on shared library
address assignment.  On 32-bit PowerPC, if shared libraries are located
close to the executable, so that everything fits into 32MB area, \tts{PLT}
slots resolving to those shared libraries can use the branch relative
instruction instead of more expensive sequences involving memory load
and indirect branch.  If shared libraries are located in the
first 32MB of address space, \tts{PLT} slots resolving to those shared
libraries can use the branch absolute instruction (but already \tts{PLT}
slots in those shared libraries resolving to addresses in the executable
cannot be done cheaply).  This means for optimization \tts{prelink}
should assign addresses from a 24MB region below the executable first, assuming
most of the executables are smaller than those remaining 8MB.
\tts{prelink} assigns these from higher to lower addresses.  When this
region is full, \tts{prelink} starts from address 0x40000
\footnote{To leave some pages unmapped to catch \tts{NULL} pointer
dereferences.} up till the bottom of the first area.  Only when
all these areas are full, \tts{prelink} starts picking addresses high above
the executable, so that sufficient space is left in between to leave room
for \tts{brk}.
When \tts{-R} option is specified, \tts{prelink} needs to honor it, but
in a way which doesn't totally kill this optimization.  So it picks up
a random start base within each of the 3 regions separately, splitting
them into 6 regions.

Another architecture which needs to be handled specially is IA-32
when using \tts{Exec-Shield}.  The IA-32 architecture doesn't have an
bit to disable execution for each page, only for each segment.  All readable
pages are normally executable.  This means the stack is usually executable,
as is memory allocated by \tts{malloc}.  This is undesirable for security reasons,
exploits can then overflow a buffer on the stack to transfer control
to code it creates on the stack.
Only very few programs actually need an executable stack.  For example
programs using GCC trampolines for nested functions need it or when
an application itself creates executable code on the stack and calls it.
\tts{Exec-Shield} works around this IA-32 architecture deficiency
by using a separate code segment, which starts at address 0 and spans
address space until its limit, highest page which needs to
be executable.  This is dynamically changed when some page with higher
address than the limit needs to be executable (either because of \tts{mmap}
with \tts{PROT\_EXEC} bit set, or \tts{mprotect} with \tts{PROT\_EXEC}
of an existing mapping).  This kind of protection is of course only
effective if the limit is as low as possible.  The kernel tries to
put all new mappings with \tts{PROT\_EXEC} set and \tts{NULL} address low.
If possible into {\sl ASCII Shield area} (first 16MB of address space)
\nomenclature{ASCII Shield area}{First 16MB of address space on 32-bit
architectures.  These addresses have zeros in upper 8 bits,
which on little endian architectures are stored as last byte of the address
and on big endian architectures as first byte of the address.
A zero byte terminates string, so it is hard to control the exact
arguments of a function if they are placed on the stack above the
address.  On big endian machines, it is even hard to control the
low 24 bits of the address}, if not, at least below the executable.
If \tts{prelink} detects \tts{Exec-Shield}, it tries to do the same as
kernel when assigning addresses, i.e. prefers to assign addresses in
{\sl ASCII Shield area} and continues with other addresses below
the program.  It needs to leave first 1MB plus 4KB of address space
unallocated though, because that range is often used by programs
using \tts{vm86} system call.

\section{Relocation of libraries}

When a shared library has a base address assigned, it needs to be relocated
so that the base address is equal to the first \tts{PT\_LOAD} segment's
\tts{p\_vaddr}.  The effect of this operation should be bitwise identical
as if the library were linked with that base address originally.
That is, the following scripts should produce identical output:

\noindent{{\small\begin{verbatim}
$ gcc -g -shared -o libfoo.so.1.0.0 -Wl,-h,libfoo.so.1 \
      input1.o input2.o somelib.a
$ prelink --reloc-only=0x54321000 libfoo.so.1.0.0
\end{verbatim}
\prelinklistingcaption{Script to relocate a shared library after linking using \tts{prelink}}}

and:
\noindent{\small\begin{verbatim}
$ gcc -shared -Wl,--verbose 2>&1 > /dev/null \
  | sed -e '/^======/,/^======/!d' \
        -e '/^======/d;s/0\( + SIZEOF_HEADERS\)/0x54321000\1/' \
        > libfoo.so.lds
$ gcc -Wl,-T,libfoo.so.lds -g -shared -o libfoo.so.1.0.0 \
      -Wl,-h,libfoo.so.1 input1.o input2.o somelib.a
\end{verbatim}}
\prelinklistingcaption{Script to link a shared library at non-standard base}}

The first script creates a normal shared library with the default
base address 0 and then uses \tts{prelink}'s special mode when it just
relocates a library to a given address.  The second script first modifies
a built-in GNU linker script for linking of shared libraries, so that
the base address is the one given instead of zero and stores it into a
temporary file.  Then it creates a shared library using that linker script.

The relocation operation involves mostly adding the difference between
old and new base address to all \tts{ELF} fields which contain values
representing virtual addresses of the shared library
(or in the program header table also representing physical addresses).
File offsets need to be unmodified.  Most places where the adjustments
need to be done are clear, \tts{prelink} just has to watch \tts{ELF} spec
to see which fields contain virtual addresses.

One problem is with absolute symbols.  \tts{Prelink} has no way to find
out if an absolute symbol in a shared library is really meant as
absolute and thus not changing during relocation, or if it is an address
of some place in the shared library outside of any section or on their
edge.  For instance symbols created in the GNU linker's script outside
of section directives have all \tts{SHN\_ABS} section, yet they can be
location in the library (e.g. \tts{symbolfoo~=~.}) or they can be absolute
(e.g. \tts{symbolbar~=~0x12345000}).  This distinction is lost at link
time.  But the dynamic linker when looking up symbols doesn't make any
distinction between them, all addresses during dynamic lookup have the
load offset added to it.  \tts{Prelink} chooses to relocate any absolute
symbols with value bigger than zero, that way \tts{prelink --reloc-only}
gets bitwise identical output with linking directly at the different base
in almost all real-world cases.  Thread Local Storage symbols (those with
\tts{STT\_TLS} type) are never relocated, as their values are relative
to start of shared library's thread local area.

When relocating the dynamic section there are no bits which tell if
a particular dynamic tag uses \tts{d\_un.d\_ptr} (which needs to
be adjusted) or \tts{d\_un.d\_val} (which needs to be left as is).
So \tts{prelink} has to hardcode a list of well known architecture
independent dynamic tags which need adjusting and have a hook for
architecture specific dynamic tag adjustment.  Sun came up with
\tts{DT\_ADDRRNGLO} to \tts{DT\_ADDRRNGHI} and \tts{DT\_VALRNGLO}
to \tts{DT\_VALRNGHI} dynamic tag number ranges, so at least as
long as these ranges are used for new dynamic tags \tts{prelink}
can relocate correctly even without listing them all explicitly.

When relocating \tts{.rela.*} or \tts{.rel.*} sections, which is
done in architecture specific code, relative relocations and on \tts{.got.plt}
using architectures also \tts{PLT} relocations typically need an
adjustment.  The adjustment needs to be done in either \tts{r\_addend} field
of the \tts{ElfNN\_Rela} structure, in the memory pointed by \tts{r\_offset},
or in both locations.
On some architectures what needs adjusting is not even the same for all relative relocations.
Relative relocations against some sections need to have \tts{r\_addend}
adjusted while others need to have memory adjusted.
On many architectures, first few words in \tts{GOT} are special and some
of them need adjustment.

The hardest part of the adjustment is handling the debugging sections.
These are non-allocated sections which typically have no corresponding
relocation section associated with them.  \tts{Prelink} has to match the various
debuggers in what fields it adjusts and what are skipped.
As of this writing \tts{prelink} should handle
\href{http://www.eagercon.com/dwarf/dwarf-2.0.0.pdf}%
{\tts{DWARF 2} [15]} standard as corrected (and extended) by
\href{http://reality.sgiweb.org/davea/dwarf3-draft8-011125.pdf}%
{\tts{DWARF 3 draft} [16]},
\href{http://sources.redhat.com/cgi-bin/cvsweb.cgi/src/gdb/doc/stabs.texinfo?cvsroot=src}%
{\tts{Stabs} [17]} with GCC extensions and Alpha or MIPS \tts{Mdebug}.

\tts{DWARF 2} debugging information involves many separate sections,
each of them with a unique format which needs to be relocated differently.
For relocation of the \tts{.debug\_info} section compilation units \tts{prelink} has to
parse the corresponding part of the \tts{.debug\_abbrev} section, adjust all
values of attributes that are using the \tts{DW\_FORM\_addr} form and adjust embedded
location lists.  \tts{.debug\_ranges} and \tts{.debug\_loc} section
portions depend on the exact place in \tts{.debug\_info} section from
which they are referenced, so that \tts{prelink} can keep track of their
base address.  \tts{DWARF} debugging format is very extendable, so
\tts{prelink} needs to be very conservative when it sees unknown extensions.
It needs to fail prelinking instead of silently break debugging information
if it sees an unknown \tts{.debug\_*} section, unknown attribute form
or unknown attribute with one of the \tts{DW\_FORM\_block*} forms, as
they can potentially embed addresses which would need adjustment.

For \tts{stabs} \tts{prelink} tried to match GDB behavior.  For
\tts{N\_FUN}, it needs to differentiate between function start and
function address which are both encoded with this type, the rest of types
either always need relocating or never.  And similarly to \tts{DWARF 2}
handling, it needs to reject unknown types.

The relocation code in \tts{prelink} is a little bit more generic
than what is described above, as it is used also by other parts of
\tts{prelink}, when growing sections in a middle of the shared library
during \tts{REL} to \tts{RELA} conversion.  All adjustment functions
get passed both the offset it should add to virtual addresses and
a start address.  Adjustment is only done if the old virtual address
was bigger or equal than the start address.

\section{REL to RELA conversion}

On architectures which normally use the \tts{REL} format for relocations instead
of \tts{RELA} (IA-32, ARM and MIPS), if certain relocation types use the
memory \tts{r\_offset} points to during relocation, \tts{prelink} has to
either convert them to a different relocation type which doesn't use
the memory value, or the whole \tts{.rel.dyn} section needs to be converted
to \tts{RELA} format.  Let's describe it on an example on IA-32 architecture:

\noindent{{\small\begin{verbatim}
$ cat > test1.c <<EOF
extern int i[4];
int *j = i + 2;
EOF
$ cat > test2.c <<EOF
int i[4];
EOF
$ gcc -nostdlib -shared -fpic -s -o test2.so test2.c
$ gcc -nostdlib -shared -fpic -o test1.so test1.c ./test2.so
$ readelf -l test1.so | grep LOAD | head -1
  LOAD           0x000000 0x00000000 0x00000000 0x002b8 0x002b8 R E 0x1000
$ readelf -l test2.so | grep LOAD | head -1
  LOAD           0x000000 0x00000000 0x00000000 0x00244 0x00244 R E 0x1000
$ readelf -r test1.so

Relocation section '.rel.dyn' at offset 0x2b0 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
000012b8  00000d01 R_386_32          00000000   i
$ objdump -s -j .data test1.so

test1.so:     file format elf32-i386

Contents of section .data:
 12b8 08000000                             ....
$ readelf -s test2.so | grep i\$
    11: 000012a8    16 OBJECT  GLOBAL DEFAULT    8 i
$ prelink -N ./test1.so ./test2.so
$ readelf -l test1.so | grep LOAD | head -1
  LOAD           0x000000 0x04dba000 0x04dba000 0x002bc 0x002bc R E 0x1000
$ readelf -l test2.so | grep LOAD | head -1
  LOAD           0x000000 0x04db6000 0x04db6000 0x00244 0x00244 R E 0x1000
$ readelf -r test1.so

Relocation section '.rel.dyn' at offset 0x2b0 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
04dbb2bc  00000d01 R_386_32          00000000   i + 8
$ objdump -s -j .data test1.so

test1.so:     file format elf32-i386

Contents of section .data:
 4dbb2bc b072db04                             .r..
$ readelf -s test2.so | grep i\$
    11: 04db72a8    16 OBJECT  GLOBAL DEFAULT    8 i
\end{verbatim}}
\prelinklistingcaption{\tts{REL} to \tts{RELA} conversion example}}

This relocation is against {\sl i + 8}, where the addend is stored at the memory
location pointed by \tts{r\_offset}.  \tts{Prelink} assigned base address
0x4dba000 to \tts{test1.so} and 0x4db6000 to \tts{test2.so}.
\tts{Prelink} above converted the \tts{REL} section in \tts{test1.so} to
\tts{RELA}, but let's assume it did not.  All output containing {\sl 2bc}
above would change to {\sl 2b8} (that changed above only because \tts{.rel.dyn}
section grew up by 4 bytes during the conversion to \tts{RELA} format),
the rest would stay unchanged.
When some program linked against \tts{test1.so} was prelinked,
the (only) relocation in \tts{test1.so} would not be used and {\sl j} would
contain the right value, 0x4db72b0 (address of {\sl i + 8}; note that IA-32
is little endian, so the values in .data section are harder to read
for a human).  Now, let's assume one of the shared libraries the executable
is linked against is upgraded.  This means prelink information cannot
be used, as it is out of date.  Let's assume it was a library other
than \tts{test2.so}.  Normal relocation processing for \tts{test1.so}
needs to happen.  Standard \tts{R\_386\_32} calculation is \tts{S~+~A},
in this case 0x4db72a8 + 0x4db72b0 = 0x9b6e558 and {\sl j} contains wrong
value.  Either \tts{test2.so} could change and now the {\sl i} variable would
have different address, or some other shared library linked to the executable
could overload symbol {\sl i}.  Without additional information the dynamic
linker cannot find out the addend is 8.

The original value of a symbol could perhaps be stored in some special
allocated section and the dynamic linker could do some magic to locate it,
but it would mean standard relocation handling code in the dynamic linker
cannot be used for relocation processing of prelinked shared libraries
where prelinking information cannot be used.
So \tts{prelink} in this case converts the whole \tts{.rel.dyn} section
into the \tts{RELA} format, the addend is stored in \tts{r\_addend} field
and when doing relocation processing, it really doesn't matter what
value is at the memory location pointed by \tts{r\_offset}.
The disadvantage of this is that the relocation section
grew by 50\%.  If prelinking information can be used, it shouldn't matter much,
since the section is never loaded at runtime because it is not accessed.
If prelinking cannot be used, whether because it is out of date or
because the shared library has been
loaded by \tts{dlopen}, it will increase memory footprint, but it is read-only
memory which is typically not used after startup and can be discarded
as it is backed out by the file containing the shared library.

At least on IA-32, \tts{REL} to \tts{RELA} conversion is not always
necessary.  If \tts{R\_386\_32} added is originally 0, \tts{prelink}
can instead change its type to \tts{R\_386\_GLOB\_DAT}, which is a
similar dynamic relocation, but calculated as \tts{S} instead of
\tts{S~+~A}.  There is no similar conversion for \tts{R\_386\_PC32}
possible though, on the other side this relocation type should never
appear in position independent shared libraries, only in position
dependent code.  On ARM, the situation is the same, just using
different relocation names (\tts{R\_ARM\_32}, \tts{R\_ARM\_GLOB\_DAT}
and \tts{R\_ARM\_PC24}).

The \tts{.rel.plt} section doesn't have to be converted to \tts{RELA}
format on either of these architectures, if the conversion is needed,
all other \tts{.rel.*} allocated sections, which have to be adjacent
as they are pointed to by \tts{DT\_REL} and \tts{DT\_RELSZ} dynamic tags,
have to be converted together.  The conversion itself is fairly easy,
some architecture specific code just has to fetch the original addend
from memory pointed by the relocation and store it into \tts{r\_addend}
field (or clear \tts{r\_addend} if the particular relocation type
never uses the addend).  The main problem is that when the conversion
happens, the \tts{.rel.dyn} section grows by 50\% and there needs to be
room for that in the read-only loadable segment of the shared library.

In shared libraries it is always possible to grow the first read-only
\tts{PT\_LOAD} segment by adding the additional data at the beginning
of the read-only segment, as the shared library is relocatable.
\tts{Prelink} can relocate the whole shared library to a higher address
than it has assigned for it.  The file offsets of all sections
and the section header table file offset need to be increased,
but the \tts{ELF} header and program headers need to stay at the beginning
of the file.  The relocation section can then be moved to the newly created
space between the end of the program header table and the first section.

Moving the section from the old location to the newly created space
would leave often very big gap in virtual address space as well as in
the file at the old location of the relocation section.  Fortunately the
linker typically puts special \tts{ELF} sections including allocated
relocation section before the code section and other read-only sections
under user's control.  These special sections are intended for dynamic
linking only.  Their addresses are stored just in the \tts{.dynamic} section
and \tts{prelink} can easily adjust them there.  There is no need for
a shared library to store address of one of the special sections
into its code or data sections and existing linkers in fact don't create
such references.  When growing the relocation section, \tts{prelink}
checks whether all sections before the relocation section are
special
\footnote{As special sections \tts{prelink} considers sections with
\tts{SHT\_NOTE}, \tts{SHT\_HASH}, \tts{SHT\_DYNSYM}, \tts{SHT\_STRTAB},
\tts{SHT\_GNU\_verdef}, \tts{SHT\_GNU\_verneed}, \tts{SHT\_GNU\_versym},
\tts{SHT\_REL} or \tts{SHT\_RELA} type or the \tts{.interp} section.}
and if they are, just moves them to lower addresses, so that the
newly created space is right above the relocation section.
The advantage is that instead of moving all sections by the size of
the new relocation section they can be adjusted ideally just by the
difference between old and new relocation section size.

There are two factors which can increase the necessary adjustment of
all higher sections.  The first is required section alignment of any
allocated section above the relocation section.  \tts{Prelink} needs
to find the highest section alignment among those sections and
increase the adjustment from the difference between old and new
relocation section up to the next multiple of that alignment.

The second factor is only relevant to shared libraries where linker
optimized the data segment placement.  Traditionally linker assigned
the end address of the read-only segment plus the architecture's
maximum \tts{ELF} page size as the start address of the read-write
segment.  While this created smallest file sizes of the shared libraries,
it often wasted one page in the read-write segment because of partial
pages.  When linker optimizes such that less space is wasted in partial
pages, the distance between read-only and read-write segments can be
smaller than architecture specific maximum \tts{ELF} page size.
\tts{Prelink} has to take this into account, so that when adjusting
the sections the read-only and read-write segment don't end up on the
same page.  Unfortunately \tts{prelink} cannot increase or decrease
the distance between the read-only and read-write segments, since
it is possible that the shared library has relative addresses of
any allocated code, data or \tts{.bss} sections
stored in its sections without any relocations which would allow
\tts{prelink} to change them.  \tts{Prelink} has to move all sections
starting with the first allocated \tts{SHT\_PROGBITS} section other
than \tts{.interp} up to the last allocated \tts{SHT\_PROGBITS} or
\tts{SHT\_NOBITS} section as a block and thus needs to increase
the adjustment in steps of the highest section alignment as many times
times as needed so that the segments end up in different pages.
Below are 3 examples:

\noindent{{\small\begin{verbatim}
$ cat > test1.c <<EOF
int i[2] __attribute__((aligned (32)));
#define J1(N) int *j##N = &i[1];
#define J2(N) J1(N##0) J1(N##1) J1(N##2) J1(N##3) J1(N##4)
#define J3(N) J2(N##0) J2(N##1) J2(N##2) J2(N##3) J2(N##4)
#define J4(N) J3(N##0) J3(N##1) J3(N##2) J3(N##3) J3(N##4)
J4(0) J4(1) J3(2) J3(3) J1(4)
const int l[256] = { [10] = 1 };
/* Put a zero sized section at the end of read-only segment,
   so that the end address of the segment is printed.  */
asm (".section ro_seg_end, \"a\"; .previous");
EOF
$ gcc -shared -O2 -nostdlib -fpic -o test1.so test1.c
$ readelf -S test1.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            000000b4 0000b4 000930 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          000009e4 0009e4 001430 10   A  3   d  4
  [ 3] .dynstr           STRTAB          00001e14 001e14 000735 00   A  0   0  1
  [ 4] .rel.dyn          REL             0000254c 00254c 000968 08   A  2   0  4
  [ 5] .text             PROGBITS        00002eb4 002eb4 000000 00  AX  0   0  4
  [ 6] .rodata           PROGBITS        00002ec0 002ec0 000400 00   A  0   0 32
  [ 7] ro_seg_end        PROGBITS        000032c0 0032c0 000000 00   A  0   0  1
  [ 8] .data             PROGBITS        000042c0 0032c0 0004b4 00  WA  0   0  4
  [ 9] .dynamic          DYNAMIC         00004774 003774 000070 08  WA  3   0  4
  [10] .got              PROGBITS        000047e4 0037e4 00000c 04  WA  0   0  4
  [11] .bss              NOBITS          00004800 003800 000008 00  WA  0   0 32
  [12] .comment          PROGBITS        00000000 003800 000033 00      0   0  1
  [13] .shstrtab         STRTAB          00000000 003833 000075 00      0   0  1
  [14] .symtab           SYMTAB          00000000 003b28 001470 10     15  11  4
  [15] .strtab           STRTAB          00000000 004f98 000742 00      0   0  1
$ readelf -l test1.so | grep LOAD
  LOAD           0x000000 0x00000000 0x00000000 0x032c0 0x032c0 R E 0x1000
  LOAD           0x0032c0 0x000042c0 0x000042c0 0x00530 0x00548 RW  0x1000
$ prelink -N ./test1.so
$ readelf -l test1.so | grep LOAD
  LOAD           0x000000 0x02000000 0x02000000 0x03780 0x03780 R E 0x1000
  LOAD           0x003780 0x02004780 0x02004780 0x00530 0x00548 RW  0x1000
$ readelf -S test1.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            020000b4 0000b4 000930 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          020009e4 0009e4 001430 10   A  3   d  4
  [ 3] .dynstr           STRTAB          02001e14 001e14 000735 00   A  0   0  1
  [ 4] .rel.dyn          RELA            0200254c 00254c 000e1c 0c   A  2   0  4
  [ 5] .text             PROGBITS        02003374 003374 000000 00  AX  0   0  4
  [ 6] .rodata           PROGBITS        02003380 003380 000400 00   A  0   0 32
  [ 7] ro_seg_end        PROGBITS        02003780 003780 000000 00   A  0   0  1
  [ 8] .data             PROGBITS        02004780 003780 0004b4 00  WA  0   0  4
  [ 9] .dynamic          DYNAMIC         02004c34 003c34 000070 08  WA  3   0  4
  [10] .got              PROGBITS        02004ca4 003ca4 00000c 04  WA  0   0  4
  [11] .bss              NOBITS          02004cc0 003cc0 000008 00  WA  0   0 32
  [12] .comment          PROGBITS        00000000 003cc0 000033 00      0   0  1
  [13] .gnu.liblist      GNU_LIBLIST     00000000 003cf3 000000 14     14   0  4
  [14] .gnu.libstr       STRTAB          00000000 003cf3 000000 00      0   0  1
  [15] .gnu.prelink_undo PROGBITS        00000000 003cf4 00030c 01      0   0  4
  [16] .shstrtab         STRTAB          00000000 004003 0000a0 00      0   0  1
  [17] .symtab           SYMTAB          00000000 0043a0 001470 10     18  11  4
  [18] .strtab           STRTAB          00000000 005810 000742 00      0   0  1
\end{verbatim}}
\prelinklistingcaption{Growing read-only segment with segment distance one page}}

\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{dso1}
\caption{Growing read-only segment with segment distance one page}
\end{figure}

In this example the read-write segment starts at address \tts{0x42c0}, which
is one page above the end of read-only segment.  \tts{Prelink} needs to grow
the read-only \tts{PT\_LOAD} segment by 50\% of \tts{.rel.dyn} size, i.e.
\tts{0x4b4} bytes.  \tts{Prelink} just needs to round that up for the
highest alignment (32 bytes required by \tts{.rodata} or \tts{.bss}
sections) and moves all sections above \tts{.rel.dyn} by \tts{0x4c0} bytes.

\noindent{{\small\begin{verbatim}
$ cat > test2.c <<EOF
int i[2] __attribute__((aligned (32)));
#define J1(N) int *j##N = &i[1];
#define J2(N) J1(N##0) J1(N##1) J1(N##2) J1(N##3) J1(N##4)
#define J3(N) J2(N##0) J2(N##1) J2(N##2) J2(N##3) J2(N##4)
#define J4(N) J3(N##0) J3(N##1) J3(N##2) J3(N##3) J3(N##4)
J4(0) J4(1) J3(2) J3(3) J1(4)
const int l[256] = { [10] = 1 };
int k[670];
asm (".section ro_seg_end, \"a\"; .previous");
EOF
$ gcc -shared -O2 -nostdlib -fpic -o test2.so test2.c
$ readelf -S test2.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            000000b4 0000b4 000934 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          000009e8 0009e8 001440 10   A  3   d  4
  [ 3] .dynstr           STRTAB          00001e28 001e28 000737 00   A  0   0  1
  [ 4] .rel.dyn          REL             00002560 002560 000968 08   A  2   0  4
  [ 5] .text             PROGBITS        00002ec8 002ec8 000000 00  AX  0   0  4
  [ 6] .rodata           PROGBITS        00002ee0 002ee0 000400 00   A  0   0 32
  [ 7] ro_seg_end        PROGBITS        000032e0 0032e0 000000 00   A  0   0  1
  [ 8] .data             PROGBITS        00004000 004000 0004b4 00  WA  0   0  4
  [ 9] .dynamic          DYNAMIC         000044b4 0044b4 000070 08  WA  3   0  4
  [10] .got              PROGBITS        00004524 004524 00000c 04  WA  0   0  4
  [11] .bss              NOBITS          00004540 004540 000a88 00  WA  0   0 32
  [12] .comment          PROGBITS        00000000 004540 000033 00      0   0  1
  [13] .shstrtab         STRTAB          00000000 004573 000075 00      0   0  1
  [14] .symtab           SYMTAB          00000000 004868 001480 10     15  11  4
  [15] .strtab           STRTAB          00000000 005ce8 000744 00      0   0  1
$ readelf -l test2.so | grep LOAD
  LOAD           0x000000 0x00000000 0x00000000 0x032e0 0x032e0 R E 0x1000
  LOAD           0x004000 0x00004000 0x00004000 0x00530 0x00fc8 RW  0x1000
$ prelink -N ./test2.so
$ readelf -l test2.so | grep LOAD
  LOAD           0x000000 0x02000000 0x02000000 0x037a0 0x037a0 R E 0x1000
  LOAD           0x0044c0 0x020044c0 0x020044c0 0x00530 0x00fc8 RW  0x1000
$ readelf -S test2.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            020000b4 0000b4 000934 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          020009e8 0009e8 001440 10   A  3   d  4
  [ 3] .dynstr           STRTAB          02001e28 001e28 000737 00   A  0   0  1
  [ 4] .rel.dyn          RELA            02002560 002560 000e1c 0c   A  2   0  4
  [ 5] .text             PROGBITS        02003388 003388 000000 00  AX  0   0  4
  [ 6] .rodata           PROGBITS        020033a0 0033a0 000400 00   A  0   0 32
  [ 7] ro_seg_end        PROGBITS        020037a0 0037a0 000000 00   A  0   0  1
  [ 8] .data             PROGBITS        020044c0 0044c0 0004b4 00  WA  0   0  4
  [ 9] .dynamic          DYNAMIC         02004974 004974 000070 08  WA  3   0  4
  [10] .got              PROGBITS        020049e4 0049e4 00000c 04  WA  0   0  4
  [11] .bss              NOBITS          02004a00 004a00 000a88 00  WA  0   0 32
  [12] .comment          PROGBITS        00000000 004a00 000033 00      0   0  1
  [13] .gnu.liblist      GNU_LIBLIST     00000000 004a33 000000 14     14   0  4
  [14] .gnu.libstr       STRTAB          00000000 004a33 000000 00      0   0  1
  [15] .gnu.prelink_undo PROGBITS        00000000 004a34 00030c 01      0   0  4
  [16] .shstrtab         STRTAB          00000000 004d43 0000a0 00      0   0  1
  [17] .symtab           SYMTAB          00000000 0050e0 001480 10     18  11  4
  [18] .strtab           STRTAB          00000000 006560 000744 00      0   0  1
\end{verbatim}}
\prelinklistingcaption{Growing read-only segment not requiring additional padding}}

\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{dso2}
\caption{Growing read-only segment not requiring additional padding}
\end{figure}

In the second example \tts{prelink} can grow by just \tts{0x4c0} bytes as
well, eventhough the distance between read-write and read-only segment
is just \tts{0xd20} bytes.  With this distance, hypothetical adjustment
by any size less than \tts{0xd21} bytes (modulo 4096) would need just
rounding up to the next multiple of 32 bytes, while adjustments
from \tts{0xd21} up to \tts{0xfe0} would require adjustments in
multiples of 4096 bytes.

\noindent{{\small\begin{verbatim}
$ cat > test3.c <<EOF
int i[2] __attribute__((aligned (32)));
#define J1(N) int *j##N = &i[1];
#define J2(N) J1(N##0) J1(N##1) J1(N##2) J1(N##3) J1(N##4)
#define J3(N) J2(N##0) J2(N##1) J2(N##2) J2(N##3) J2(N##4)
#define J4(N) J3(N##0) J3(N##1) J3(N##2) J3(N##3) J3(N##4)
J4(0) J4(1) J3(2) J3(3) J1(4)
int k[670];
asm (".section ro_seg_end, \"a\"; .previous");
EOF
$ gcc -shared -O2 -nostdlib -fpic -o test3.so test3.c
$ readelf -S test3.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            000000b4 0000b4 00092c 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          000009e0 0009e0 001420 10   A  3   c  4
  [ 3] .dynstr           STRTAB          00001e00 001e00 000735 00   A  0   0  1
  [ 4] .rel.dyn          REL             00002538 002538 000968 08   A  2   0  4
  [ 5] .text             PROGBITS        00002ea0 002ea0 000000 00  AX  0   0  4
  [ 6] ro_seg_end        PROGBITS        00002ea0 002ea0 000000 00   A  0   0  1
  [ 7] .data             PROGBITS        00003000 003000 0004b4 00  WA  0   0  4
  [ 8] .dynamic          DYNAMIC         000034b4 0034b4 000070 08  WA  3   0  4
  [ 9] .got              PROGBITS        00003524 003524 00000c 04  WA  0   0  4
  [10] .bss              NOBITS          00003540 003540 000a88 00  WA  0   0 32
  [11] .comment          PROGBITS        00000000 003540 000033 00      0   0  1
  [12] .shstrtab         STRTAB          00000000 003573 00006d 00      0   0  1
  [13] .symtab           SYMTAB          00000000 003838 001460 10     14  10  4
  [14] .strtab           STRTAB          00000000 004c98 000742 00      0   0  1
$ readelf -l test3.so | grep LOAD
  LOAD           0x000000 0x00000000 0x00000000 0x02ea0 0x02ea0 R E 0x1000
  LOAD           0x003000 0x00003000 0x00003000 0x00530 0x00fc8 RW  0x1000
$ prelink -N ./test3.so
$ readelf -l test3.so | grep LOAD
  LOAD           0x000000 0x02000000 0x02000000 0x03ea0 0x03ea0 R E 0x1000
  LOAD           0x004000 0x02004000 0x02004000 0x00530 0x00fc8 RW  0x1000
$ readelf -S test3.so | grep '^  \['
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .hash             HASH            020000b4 0000b4 00092c 04   A  2   0  4
  [ 2] .dynsym           DYNSYM          020009e0 0009e0 001420 10   A  3   c  4
  [ 3] .dynstr           STRTAB          02001e00 001e00 000735 00   A  0   0  1
  [ 4] .rel.dyn          RELA            02002538 002538 000e1c 0c   A  2   0  4
  [ 5] .text             PROGBITS        02003ea0 003ea0 000000 00  AX  0   0  4
  [ 6] ro_seg_end        PROGBITS        02003ea0 003ea0 000000 00   A  0   0  1
  [ 7] .data             PROGBITS        02004000 004000 0004b4 00  WA  0   0  4
  [ 8] .dynamic          DYNAMIC         020044b4 0044b4 000070 08  WA  3   0  4
  [ 9] .got              PROGBITS        02004524 004524 00000c 04  WA  0   0  4
  [10] .bss              NOBITS          02004540 004540 000a88 00  WA  0   0 32
  [11] .comment          PROGBITS        00000000 004540 000033 00      0   0  1
  [12] .gnu.liblist      GNU_LIBLIST     00000000 004573 000000 14     13   0  4
  [13] .gnu.libstr       STRTAB          00000000 004573 000000 00      0   0  1
  [14] .gnu.prelink_undo PROGBITS        00000000 004574 0002e4 01      0   0  4
  [15] .shstrtab         STRTAB          00000000 00485b 000098 00      0   0  1
  [16] .symtab           SYMTAB          00000000 004bc8 001460 10     17  10  4
  [17] .strtab           STRTAB          00000000 006028 000742 00      0   0  1
\end{verbatim}}
\prelinklistingcaption{Growing read-only segment if page padding needed}}

\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{dso3}
\caption{Growing read-only segment if page padding needed}
\end{figure}

In the last example the distance between \tts{PT\_LOAD} segments is very
small, just \tts{0x160} bytes and the adjustment had to be done by 4096
bytes.

% Fortunately, shared libraries are position independent, so all absolute
% values in them are either stored in well known \tts{ELF} structures,
% or have corresponding dynamic relocations.  The only problem might be
% with relative relocations, which are resolved at link time.
% The start of read-only \tts{PT\_LOAD} segment of shared libraries is
% typically used by special sections used by the dynamic linker
% (\tts{.hash}, \tts{.dynsym}, \tts{.dynstr}, \tts{.gnu.version*},
% \tts{.rel*}, \tts{.note*}).  It makes no sense for a shared library to
% have relocations against these sections or some addresses inside of them,
% furthermore it is impossible to do it without specially crafted
% linker script.  So \tts{prelink} makes the assumption that it can grow
% freely the shared library after \tts{.rel.dyn} section, as long
% as only sections mentioned above come before \tts{.rel.dyn} (it actually
% checks section types, not names).  \tts{Prelink} certainly can grow the shared library
% size in multiplies of \tts{ELF} architecture specific maximum page size,
% but usually it can do better.  Particularly, \tts{prelink} can grow by the 50\% size
% of \tts{.rel.dyn} section rounded up to the largest section alignment
% in all sections following it, but it has to make sure that two
% different \tts{PT\_LOAD} segments (typically the read-only and read-write)
% will not share the same page, otherwise it needs to grow it more in
% multiplies of the maximum section alignment until they are on different
% pages.  Growing is done by using the shared library relocation code with
% start address set to end of \tts{.rel.dyn} section.  \tts{.rel.plt}
% section is then moved right to the end of \tts{.rel.dyn} section,
% \tts{.dynamic} section needs updating all addresses, type of
% relocation section, segment table needs to be adjusted accordingly
% and file offsets in section header table as well.

\section{Conflicts}

As said earlier, if symbol lookup of some symbol in particular shared
library results in different values when that shared library's natural
search scope is used and when using search scope of the application the
DSO is used in, this is considered a {\sl conflict}.
Here is an example of a conflict on IA-32:

\noindent{{\small\begin{verbatim}
$ cat > test1.c <<EOF
int i;
int *j = &i;
int *foo (void) { return &i; }
EOF
$ cat > test2.c <<EOF
int i;
int *k = &i;
int *bar (void) { return &i; }
EOF
$ cat > test.c <<EOF
#include <stdio.h>
extern int i, *j, *k, *foo (void), bar (void);
int main (void)
{
#ifdef PRINT_I
  printf ("%p\n", &i);
#endif
  printf ("%p %p %p %p\n", j, k, foo (), bar ());
}
EOF
$ gcc -nostdlib -shared -fpic -s -o test1.so test1.c
$ gcc -nostdlib -shared -fpic -o test2.so test2.c ./test1.so
$ gcc -o test test.c ./test2.so ./test1.so
$ ./test
0x16137c 0x16137c 0x16137c 0x16137c
$ readelf -r ./test1.so

Relocation section '.rel.dyn' at offset 0x2bc contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
000012e4  00000d01 R_386_32          00001368   i
00001364  00000d06 R_386_GLOB_DAT    00001368   i
$ prelink -N ./test ./test1.so ./test2.so
$ LD_WARN= LD_TRACE_PRELINKING=1 LD_BIND_NOW=1 /lib/ld-linux.so.2 ./test1.so
        ./test1.so => ./test1.so (0x04db6000, 0x00000000)
$ LD_WARN= LD_TRACE_PRELINKING=1 LD_BIND_NOW=1 /lib/ld-linux.so.2 ./test2.so
        ./test2.so => ./test2.so (0x04dba000, 0x00000000)
        ./test1.so => ./test1.so (0x04db6000, 0x00000000)
$ LD_WARN= LD_TRACE_PRELINKING=1 LD_BIND_NOW=1 /lib/ld-linux.so.2 ./test \
  | sed 's/^[[:space:]]*/  /'
  ./test => ./test (0x08048000, 0x00000000)
  ./test2.so => ./test2.so (0x04dba000, 0x00000000)
  ./test1.so => ./test1.so (0x04db6000, 0x00000000)
  libc.so.6 => /lib/tls/libc.so.6 (0x00b22000, 0x00000000) TLS(0x1, 0x00000028)
  /lib/ld-linux.so.2 => /lib/ld-linux.so.2 (0x00b0a000, 0x00000000)
$ readelf -S ./test1.so | grep '\.data\|\.got'
  [ 6] .data             PROGBITS        04db72e4 0002e4 000004 00  WA  0   0  4
  [ 8] .got              PROGBITS        04db7358 000358 000010 04  WA  0   0  4
$ readelf -r ./test1.so

Relocation section '.rel.dyn' at offset 0x2bc contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
04db72e4  00000d06 R_386_GLOB_DAT    04db7368   i
04db7364  00000d06 R_386_GLOB_DAT    04db7368   i
$ objdump -s -j .got -j .data test1.so

test1.so:     file format elf32-i386

Contents of section .data:
 4db72e4 6873db04                             hs..
Contents of section .got:
 4db7358 e8120000 00000000 00000000 6873db04  ............hs..
$ readelf -r ./test | sed '/\.gnu\.conflict/,$!d'
Relocation section '.gnu.conflict' at offset 0x7ac contains 18 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
04db72e4  00000001 R_386_32                                     04dbb37c
04db7364  00000001 R_386_32                                     04dbb37c
00c56874  00000001 R_386_32                                     fffffff0
00c56878  00000001 R_386_32                                     00000001
00c568bc  00000001 R_386_32                                     fffffff4
00c56900  00000001 R_386_32                                     ffffffec
00c56948  00000001 R_386_32                                     ffffffdc
00c5695c  00000001 R_386_32                                     ffffffe0
00c56980  00000001 R_386_32                                     fffffff8
00c56988  00000001 R_386_32                                     ffffffe4
00c569a4  00000001 R_386_32                                     ffffffd8
00c569c4  00000001 R_386_32                                     ffffffe8
00c569d8  00000001 R_386_32                                     080485b8
00b1f510  00000007 R_386_JUMP_SLOT                              00b91460
00b1f514  00000007 R_386_JUMP_SLOT                              00b91080
00b1f518  00000007 R_386_JUMP_SLOT                              00b91750
00b1f51c  00000007 R_386_JUMP_SLOT                              00b912c0
00b1f520  00000007 R_386_JUMP_SLOT                              00b91200
$ ./test
0x4dbb37c 0x4dbb37c 0x4dbb37c 0x4dbb37c
\end{verbatim}}
\prelinklistingcaption{Conflict example}}

In the example, among some conflicts caused by the dynamic linker and the C library,
\footnote{Particularly in the example, the 5 \tts{R\_386\_JUMP\_SLOT} fixups
are \tts{PLT} slots in the dynamic linker for memory allocator functions
resolving to C library functions instead of dynamic linker's own trivial
implementation.  First 10 \tts{R\_386\_32} fixups at offsets 0xc56874
to 0xc569c4 are Thread Local Storage fixups in the C library and
the fixup at 0xc569d8 is for {\sl \_IO\_stdin\_used} weak undefined symbol
in the C library, resolving to a symbol with the same name in the executable.}
there is a conflict for the symbol {\sl i} in \tts{test1.so} shared library.
\tts{test1.so} has just itself in its natural symbol lookup scope (as proved
by

\tts{LD\_WARN= LD\_TRACE\_PRELINKING=1 LD\_BIND\_NOW=1 /lib/ld-linux.so.2 ./test1.so}

command output), so when looking up symbol {\sl i} in this
scope the definition in \tts{test1.so} is chosen.  \tts{test1.so} has two
relocations against the symbol {\sl i}, one \tts{R\_386\_32} against \tts{.data}
section and one \tts{R\_386\_GLOB\_DAT} against \tts{.got} section.  When
prelinking \tts{test1.so} library, the dynamic linker stores the address of
{\sl i} (0x4db7368) into both locations (at offsets 0x4db72e4 and 0x4db7364).
The global symbol search scope in \tts{test} executable contains the executable
itself, \tts{test2.so} and \tts{test1.so} libraries, \tts{libc.so.6} and
the dynamic linker in the listed order.
When doing symbol lookup for symbol {\sl i}
in \tts{test1.so} when doing relocation processing of the whole executable,
address of {\sl i} in \tts{test2.so} is returned as that symbol comes earlier
in the global search scope.  So, when none of the libraries nor the executable
is prelinked, the program prints 4 identical addresses.  If prelink didn't
create conflict fixups for the two relocations against the symbol {\sl i}
in \tts{test1.so}, prelinked executable (which bypasses normal relocation
processing on startup) would print instead of the desired

\tts{0x4dbb37c 0x4dbb37c 0x4dbb37c 0x4dbb37c}

different addresses,

\tts{0x4db7368 0x4dbb37c 0x4db7368 0x4dbb37c}

That is a functionality change that \tts{prelink} cannot be permitted to
make, so instead it fixes up the two locations by storing the desired
value in there.  In this case \tts{prelink} really cannot avoid that
- \tts{test1.so} shared library could be also used without \tts{test2.so}
in some other executable's symbol search scope.
Or there could be some executable linked with:

\noindent{{\small\begin{verbatim}
$ gcc -o test2 test.c ./test1.so ./test2.so
\end{verbatim}}
\prelinklistingcaption{Conflict example with swapped order of libraries}}

where {\sl i} lookup in \tts{test1.so} and \tts{test2.so} is supposed
to resolve to {\sl i} in \tts{test1.so}.

Now consider what happens if the executable is linked with \tts{-DPRINT\_I}:

\noindent{{\small\begin{verbatim}
$ gcc -DPRINT_I -o test3 test.c ./test2.so ./test1.so
$ ./test3
0x804972c
0x804972c 0x804972c 0x804972c 0x804972c
$ prelink -N ./test3 ./test1.so ./test2.so
$ readelf -S ./test2.so | grep '\.data\|\.got'
  [ 6] .data             PROGBITS        04dbb2f0 0002f0 000004 00  WA  0   0  4
  [ 8] .got              PROGBITS        04dbb36c 00036c 000010 04  WA  0   0  4
$ readelf -r ./test2.so

Relocation section '.rel.dyn' at offset 0x2c8 contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
04dbb2f0  00000d06 R_386_GLOB_DAT    04dbb37c   i
04dbb378  00000d06 R_386_GLOB_DAT    04dbb37c   i
$ objdump -s -j .got -j .data test2.so

test2.so:     file format elf32-i386

Contents of section .data:
 4dbb2f0 7cb3db04                             |...            
Contents of section .got:
 4dbb36c f4120000 00000000 00000000 7cb3db04  ............|...
$ readelf -r ./test3

Relocation section '.rel.dyn' at offset 0x370 contains 4 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
08049720  00000e06 R_386_GLOB_DAT    00000000   __gmon_start__
08049724  00000105 R_386_COPY        08049724   j
08049728  00000305 R_386_COPY        08049728   k
0804972c  00000405 R_386_COPY        0804972c   i

Relocation section '.rel.plt' at offset 0x390 contains 4 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
08049710  00000607 R_386_JUMP_SLOT   080483d8   __libc_start_main
08049714  00000707 R_386_JUMP_SLOT   080483e8   printf
08049718  00000807 R_386_JUMP_SLOT   080483f8   foo
0804971c  00000c07 R_386_JUMP_SLOT   08048408   bar

Relocation section '.gnu.conflict' at offset 0x7f0 contains 20 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
04dbb2f0  00000001 R_386_32                                     0804972c
04dbb378  00000001 R_386_32                                     0804972c
04db72e4  00000001 R_386_32                                     0804972c
04db7364  00000001 R_386_32                                     0804972c
00c56874  00000001 R_386_32                                     fffffff0
00c56878  00000001 R_386_32                                     00000001
00c568bc  00000001 R_386_32                                     fffffff4
00c56900  00000001 R_386_32                                     ffffffec
00c56948  00000001 R_386_32                                     ffffffdc
00c5695c  00000001 R_386_32                                     ffffffe0
00c56980  00000001 R_386_32                                     fffffff8
00c56988  00000001 R_386_32                                     ffffffe4
00c569a4  00000001 R_386_32                                     ffffffd8
00c569c4  00000001 R_386_32                                     ffffffe8
00c569d8  00000001 R_386_32                                     080485f0
00b1f510  00000007 R_386_JUMP_SLOT                              00b91460
00b1f514  00000007 R_386_JUMP_SLOT                              00b91080
00b1f518  00000007 R_386_JUMP_SLOT                              00b91750
00b1f51c  00000007 R_386_JUMP_SLOT                              00b912c0
00b1f520  00000007 R_386_JUMP_SLOT                              00b91200
$ ./test3
0x804972c
0x804972c 0x804972c 0x804972c 0x804972c
\end{verbatim}}
\prelinklistingcaption{Conflict example with COPY relocation for conflicting symbol}}

Because the executable is not compiled as position independent code and
\tts{main} function takes address of {\sl i} variable, the object
file for \tts{test3.c} contains a \tts{R\_386\_32} relocation against
{\sl i}.  The linker cannot make dynamic relocations against read-only
segment in the executable, so the address of {\sl i} must be constant.
This is accomplished by creating a new object {\sl i} in the executable's
\tts{.dynbss} section and creating a dynamic \tts{R\_386\_COPY} relocation
for it.  The relocation ensures that during startup the content of
{\sl i} object earliest in the search scope without the executable
is copied to this {\sl i} object in executable.  Now, unlike \tts{test}
executable, in \tts{test3} executable {\sl i} lookups in both \tts{test1.so}
and \tts{test2.so} libraries result in address of {\sl i} in the executable
(instead of \tts{test2.so}).  This means that two conflict fixups
are needed again for \tts{test1.so} (but storing 0x804972c instead of
0x4dbb37c) and two new fixups are needed for \tts{test2.so}.

If the executable is compiled as position independent code,

\noindent{{\small\begin{verbatim}
$ gcc -fpic -DPRINT_I -o test4 test.c ./test2.so ./test1.so
$ ./test4
0x4dbb37c
0x4dbb37c 0x4dbb37c 0x4dbb37c 0x4dbb37c
\end{verbatim}}
\prelinklistingcaption{Conflict example with position independent code in the executable}}

the address of {\sl i} is stored in executable's \tts{.got} section,
which is writable and thus can have dynamic relocation against it.
So the linker creates a \tts{R\_386\_GLOB\_DAT} relocation against
the \tts{.got} section, the symbol {\sl i} is undefined in the executable
and no copy relocations are needed.  In this case, only \tts{test1.so}
will need 2 fixups, \tts{test2.so} will not need any.

There are various reasons for conflicts:
\begin{itemize}
\item Improperly linked shared libraries.  If a shared library always needs
symbols from some particular shared library, it should be linked against
that library, usually by adding \tts{-lLIBNAME} to \tts{gcc -shared} command
line used during linking of the shared library.  This both reduces conflict
fixups in \tts{prelink} and makes the library easier to load using
\tts{dlopen}, because applications don't have to remember that they have
to load some other library first.  The best place to record the dependency
is in the shared library itself.  Another reason is if the needed library
uses symbol versioning for its symbols.  Not linking against that library
can result in malfunctioning shared library.  \tts{Prelink} issues a warning for
such libraries - \tts{Warning: {\sl library} has undefined non-weak symbols}.
When linking a shared library, the \tts{-Wl,-z,defs} option can be used to
ensure there are no such undefined non-weak symbols.  There are exceptions,
when undefined non-weak symbols in shared libraries are desirable.
One exception is when there are multiple shared libraries providing the
same functionality, and a shared library doesn't care which one is used.
An example can be e.g. \tts{libreadline.so.4}, which needs some terminal
handling functions, which are provided be either \tts{libtermcap.so.2},
or \tts{libncurses.so.5}.  Another exception is with plugins or other
shared libraries which expect some symbols to be resolved to symbols
defined in the executable.
\item A library overriding functionality of some other library.  One example
is e.g. C library and POSIX thread library.  Older versions of the GNU C library
did not provide cancelable entry points required by the standard.  This is
not needed for non-threaded applications.  So only the \tts{libpthread.so.0} shared
library which provides POSIX threading support then overrode the
cancellation entry points required by the standard by wrapper functions
which provided the required functionality.  Although most recent versions
of the GNU C library handle cancellation even in entry points in \tts{libc.so.6}
(this was needed for cases when \tts{libc.so.6} comes earlier before
\tts{libpthread.so.0} in symbol search scope and used to be worked around
by non-standard handling of weak symbols in the dynamic linker), because
of symbol versioning the symbols had to stay in \tts{libpthread.so.0}
as well as in \tts{libc.so.6}.  This means every program using POSIX
threads on Linux will have a couple of conflict fixups because of this.
\item Programs which need copy relocations.  Although \tts{prelink} will
resolve the copy relocations at prelinking time, if any shared library
has relocations against the symbol which needed copy relocation, all such
relocations will need conflict fixups.  Generally, it is better to not
export variables from shared libraries in their APIs, instead provide
accessor functions.
\item Function pointer equality requirement for functions called from
executables.  When address of some global function is taken, at least
C and C++ require that this pointer is the same in the whole program.
Executables typically contain position dependent code, so when code in the
executable takes address of some function not defined in the executable itself,
that address must be link time constant.  Linker accomplishes this by
creating a \tts{PLT} slot for the function unless there was one already
and resolving to the address of \tts{PLT} slot.  The symbol for the function
is created with \tts{st\_value} equal to address of the \tts{PLT} slot,
but \tts{st\_shndx} set to \tts{SHN\_UNDEF}.  Such symbols are treated
specially by the dynamic linker, in that \tts{PLT} relocations
resolve to first symbol in the global search scope after the executable,
while symbol lookups for all other relocation types return the
address of the symbol in the executable.  Unfortunately, GNU linker doesn't
differentiate between taking address of a function in an executable (especially
one for which no dynamic relocation is possible in case it is in read-only
segment) and just calling the function, but never taking its address.
If it cleared the \tts{st\_value} field of the \tts{SHN\_UNDEF} function symbols
in case nothing in the executable takes the function's address, several \tts{prelink}
conflict could disappear (\tts{SHN\_UNDEF} symbols with \tts{st\_value} set
to 0 are treated always as real undefined symbols by the dynamic linker).
\item \tts{COMDAT} code and data in C++.  C++ language has several places where
it may need to emit some code or data without a clear unique
compilation unit owning it.  Examples include taking address of an
\tts{inline} function, local static variable in \tts{inline} functions,
virtual tables for some classes (this depends on \tts{\#pragma interface}
or \tts{\#pragma implementation} presence, presence of non-inline
non-pure-virtual member function in the class, etc.), {\sl RTTI} info for them.
Compilers and linkers handle these using various \tts{COMDAT} schemes,
e.g. GNU linker's \tts{.gnu.linkonce*} special sections or using
\tts{SHT\_GROUP}.  Unfortunately, all these duplicate merging schemes
work only during linking of shared libraries or executables, no duplicate
removal is done across shared libraries.  Shared libraries typically
have relocations against their \tts{COMDAT} code or data objects (otherwise
they wouldn't be at least in most cases emitted at all), so if there are
\tts{COMDAT} duplicates across shared libraries or the executable, they
lead to conflict fixups.  The linker theoretically could try to
merge \tts{COMDAT} duplicates across shared libraries if specifically
requested by the user (if a \tts{COMDAT} symbol is already present in
one of the dependent shared libraries and is \tts{STB\_WEAK}, the linker
could skip it).  Unfortunately, this only works as long as the user has
full control over the dependent shared libraries, because the \tts{COMDAT}
symbol could be exported from them just as a side effect of their
implementation (e.g. they use some class internally).  When such libraries
are rebuilt even with minor changes in their implementation (unfortunately
with C++ shared libraries it is usually not very clear what part is exported
ABI and what is not), some of those \tts{COMDAT} symbols in them could go
away (e.g. because suddenly they use a different class internally and
the previously used class is not referenced anywhere).  When \tts{COMDAT}
objects are not merged across shared libraries, this makes no problems,
as each library which needs the \tts{COMDAT} has its own copy.  But with
\tts{COMDAT} duplicate removal between shared libraries there could suddenly
be unresolved references and the shared libraries would need to be relinked.
The only place where this could work safely is when a single package
includes several C++ shared libraries which depend on each other.  They are
then shipped always together and when one changes, all others need changing
too.
\end{itemize}

\section{Prelink optimizations to reduce number of conflict fixups}

\tts{Prelink} can optimize out some conflict fixups if it can prove that
the changes are not observable by the application at runtime (opening its
executable and reading it doesn't count).  If there is a data object in some
shared library with a symbol that is overridden by a symbol in a different
shared library earlier in global symbol lookup scope or in the executable, then
that data object is likely never referenced and it shouldn't matter what it
contains.  Examine the following example:

\noindent{{\small\begin{verbatim}
$ cat > test1.c <<EOF
int i, j, k;
struct A { int *a; int *b; int *c; } x = { &i, &j, &k };
struct A *y = &x;
EOF
$ cat > test2.c <<EOF
int i, j, k;
struct A { int *a; int *b; int *c; } x = { &i, &j, &k };
struct A *z = &x;
EOF
$ cat > test.c <<EOF
#include <stdio.h>
extern struct A { int *a; int *b; int *c; } *y, *z;
int main (void)
{
  printf ("%p: %p %p %p\n", y, y->a, y->b, y->c);
  printf ("%p: %p %p %p\n", z, z->a, z->b, z->c);
}
EOF
$ gcc -nostdlib -shared -fpic -s -o test1.so test1.c
$ gcc -nostdlib -shared -fpic -o test2.so test2.c ./test1.so
$ gcc -o test test.c ./test2.so ./test1.so
$ ./test
0xaf3314: 0xaf33b0 0xaf33a8 0xaf33ac
0xaf3314: 0xaf33b0 0xaf33a8 0xaf33ac
\end{verbatim}}
\prelinklistingcaption{C example where conflict fixups could be optimized out}}

In this example there are 3 conflict fixups pointing into the 12 byte
long {\sl x} object in \tts{test1.so} shared library (among other
conflicts).  And nothing in the program can poke at {\sl x} content
in \tts{test1.so}, simply because it has to look at it through
{\sl x} symbol which resolves to \tts{test2.so}.  So in this
case \tts{prelink} could skip those 3 conflicts.  Unfortunately
it is not that easy:

\noindent{{\small\begin{verbatim}
$ cat > test3.c <<EOF
int i, j, k;
static struct A { int *a; int *b; int *c; } local = { &i, &j, &k };
extern struct A x;
struct A *y = &x;
struct A *y2 = &local;
extern struct A x __attribute__((alias ("local")));
EOF
$ cat > test4.c <<EOF
#include <stdio.h>
extern struct A { int *a; int *b; int *c; } *y, *y2, *z;
int main (void)
{
  printf ("%p: %p %p %p\n", y, y->a, y->b, y->c);
  printf ("%p: %p %p %p\n", y2, y2->a, y2->b, y2->c);
  printf ("%p: %p %p %p\n", z, z->a, z->b, z->c);
}
EOF
$ gcc -nostdlib -shared -fpic -s -o test3.so test3.c
$ gcc -nostdlib -shared -fpic -o test4.so test2.c ./test3.so
$ gcc -o test4 test4.c ./test4.so ./test3.so
$ ./test4
0x65a314: 0x65a3b0 0x65a3a8 0x65a3ac
0xbd1328: 0x65a3b0 0x65a3a8 0x65a3ac
0x65a314: 0x65a3b0 0x65a3a8 0x65a3ac
\end{verbatim}}
\prelinklistingcaption{Modified C example where conflict fixups cannot be removed}}

In this example, there are again 3 conflict fixups pointing into the
12 byte long {\sl x} object in \tts{test3.so} shared library.
The fact that variable local is located at the same 12 bytes
is totally invisible to prelink, as local is a \tts{STB\_LOCAL}
symbol which doesn't show up in \tts{.dynsym} section.  But if those
3 conflict fixups are removed, then suddenly program's observable
behavior changes (the last 3 addresses on second line would be
different than those on first or third line).

Fortunately, there are at least some objects where \tts{prelink}
can be reasonably sure they will never be referenced through some
local alias.  Those are various compiler generated objects with
well defined meaning which is \tts{prelink} able to identify
in shared libraries.  The most important ones are C++ virtual tables
and {\sl RTTI} data.  They are emitted as COMDAT data by the compiler,
in GCC into \tts{.gnu.linkonce.d.*} sections.  Data or code in these
sections can be accessed only through global symbols, otherwise linker
might create unexpected results when two or more of these sections
are merged together (all but one deleted).  When \tts{prelink} is checking
for such data, it first checks whether the shared library in question
is linked against \tts{libstdc++.so}.  If not, it is not a C++ library
(or incorrectly built one) and thus it makes no sense to search any further.
It looks only in \tts{.data} section, for \tts{STB\_WEAK} \tts{STT\_OBJECT}
symbols whose names start with certain prefixes
\footnote{\tts{\_\_vt\_} for GCC 2.95.x and 2.96-RH virtual tables,
\tts{\_ZTV} for GCC 3.x virtual tables and \tts{\_ZTI} for GCC 3.x {\sl RTTI} data.}
and where no other symbols (in dynamic symbol table) point into the objects.
If these objects are unused because there is a conflict on their symbol,
all conflict fixups pointing into the virtual table or {\sl RTTI} structure
can be discarded.

Another possible optimization is again related to C++ virtual tables.
Function addresses in them are not intended for pointer comparisons.
C++ code only loads them from the virtual tables and calls through
the pointer.  Pointers to member functions are handled differently.
As pointer equivalence is the only reason why all function pointers
resolve to \tts{PLT} slots in the executable even when the executable doesn't
include implementation of the function (i.e. has \tts{SHN\_UNDEF} symbol
with non-zero \tts{st\_value} pointing at the \tts{PLT} slot in the
executable), \tts{prelink} can resolve method addresses in virtual tables
to the actual method implementation.  In many cases this is in the same
library as the virtual table (or in one of libraries in its natural
symbol lookup scope), so a conflict fixup is unnecessary.
This optimization speeds up programs also after control is transfered
to the application and not just the time to start up the application,
although just a few cycles per method call.

The conflict fixup reduction is quite big on some programs.
Below is statistics for \tts{kmail} program on completely unprelinked box:

\noindent{{\small\begin{verbatim}
$ LD_DEBUG=statistics /usr/bin/kmail 2>&1 | sed '2,8!d;s/^ *//'
10621:       total startup time in dynamic loader: 240724867 clock cycles
10621:                 time needed for relocation: 234049636 clock cycles (97.2%)
10621:                      number of relocations: 34854
10621:           number of relocations from cache: 74364
10621:             number of relative relocations: 35351
10621:                time needed to load objects: 6241678 clock cycles (2.5%)
$ ls -l /usr/bin/kmail
-rwxr-xr-x    1 root     root      2149084 Oct  2 12:05 /usr/bin/kmail
$ ( Xvfb :3 & ) >/dev/null 2>&1 </dev/null; sleep 20
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10; killall kmail
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10
$ cat /proc/`/sbin/pidof kmail`/statm
4164 4164 3509 224 33 3907 655
$ killall Xvfb kdeinit kmail
\end{verbatim}}
\prelinklistingcaption{Statistics for unprelinked \tts{kmail}}}

\tts{statm} special file for a process contains its memory statistics.
The numbers in it mean in order total number of used pages (on IA-32
Linux a page is 4KB), number of resident pages (i.e. not swapped out),
number of shared pages, number of text pages, number of library pages,
number of stack and other pages and number of dirty pages used by the
process.  Distinction between text and library pages is very rough,
so those numbers aren't that much useful.  Of interest are mainly
first number, third number and last number.

Statistics for \tts{kmail} on completely prelinked box:

\noindent{{\small\begin{verbatim}
$ LD_DEBUG=statistics /usr/bin/kmail 2>&1 | sed '2,8!d;s/^ *//'
14864:       total startup time in dynamic loader: 8409504 clock cycles
14864:                 time needed for relocation: 3024720 clock cycles (35.9%)
14864:                      number of relocations: 0
14864:           number of relocations from cache: 8961
14864:             number of relative relocations: 0
14864:                time needed to load objects: 4897336 clock cycles (58.2%)
$ ls -l /usr/bin/kmail
-rwxr-xr-x    1 root     root      2269500 Oct  2 12:05 /usr/bin/kmail
$ ( Xvfb :3 & ) >/dev/null 2>&1 </dev/null; sleep 20
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10; killall kmail
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10
$ cat /proc/`/sbin/pidof kmail`/statm
3803 3803 3186 249 33 3521 617
$ killall Xvfb kdeinit kmail
\end{verbatim}}
\prelinklistingcaption{Statistics for prelinked \tts{kmail}}}

Statistics for \tts{kmail} on completely prelinked box with C++ conflict fixup
optimizations turned off:

\noindent{{\small\begin{verbatim}
$ LD_DEBUG=statistics /usr/bin/kmail 2>&1 | sed '2,8!d;s/^ *//'
20645:       total startup time in dynamic loader: 9704168 clock cycles
20645:                 time needed for relocation: 4734715 clock cycles (48.7%)
20645:                      number of relocations: 0
20645:           number of relocations from cache: 59871
20645:             number of relative relocations: 0
20645:                time needed to load objects: 4487971 clock cycles (46.2%)
ls -l /usr/bin/kmail
-rwxr-xr-x    1 root     root      2877360 Oct  2 12:05 /usr/bin/kmail
$ ( Xvfb :3 & ) >/dev/null 2>&1 </dev/null; sleep 20
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10; killall kmail
$ ( DISPLAY=:3 kmail& ) >/dev/null 2>&1 </dev/null; sleep 10
$ cat /proc/`/sbin/pidof kmail`/statm
3957 3957 3329 398 33 3526 628
$ killall Xvfb kdeinit kmail
\end{verbatim}}
\prelinklistingcaption{Statistics for prelinked \tts{kmail} without conflict fixup reduction}}

On this application, C++ conflict fixup optimizations saved 50910 unneeded
conflict fixups, speeded up startup by 13.3\% and decreased number of dirty
pages by 11, which means the application needs 44KB less memory per-process.

\section{Thread Local Storage support}

Thread Local Storage ([12], [13], [14]) support has been recently added to
GCC, GNU binutils and GNU C Library.  \tts{TLS} support is a set of new
relocations which together with dynamic linker and POSIX thread library
additions provide faster and easier to use alternative to traditional
POSIX thread local data API (\tts{pthread\_getspecific},
\tts{pthread\_setspecific}, \tts{pthread\_key\_*}).

\tts{TLS} necessitated several changes to \tts{prelink}.  Thread Local
symbols (with type \tts{STT\_TLS}) must not be relocated, as they are
relative to the start of \tts{PT\_TLS} segment and thus not virtual
addresses.  The dynamic linker had to be enhanced so that it tells
\tts{prelink} at \tts{LD\_TRACE\_PRELINKING} time what \tts{TLS} module
IDs have been assigned and what addresses relative to start of \tts{TLS}
block have been given to \tts{PT\_TLS} segment of each library or executable.
There are 3 classes of new \tts{TLS} dynamic relocations \tts{prelink}
is interested in (with different names on different architectures).

In first class are module ID relocations, which are used for \tts{TLS}
Global Dynamic and Local Dynamic models (for Global Dynamic model
they are supposed to resolve to module ID of the executable or shared library
of particular \tts{STT\_TLS} symbol, for Local Dynamic model this
resolves to module ID of the containing shared library).  These
relocations are hard to prelink in any useful way without moving
\tts{TLS} module ID assignment from the dynamic linker to \tts{prelink}.
Although \tts{prelink} can find out what shared library will contain
particular \tts{STT\_TLS} symbol unless there will be conflicts
for that symbol, it doesn't know how many shared libraries with
\tts{PT\_TLS} segment will precede it or whether executable will or
will not have \tts{PT\_TLS} segment.  Until \tts{TLS} is widely
deployed by many libraries, \tts{prelink} could guess that
only \tts{libc.so} will have \tts{PT\_TLS} and store 1 (first module ID
the dynamic linker assigns), but given that \tts{libc.so} uses just
one such relocation it is not probably worth doing this when soon other
shared libraries besides \tts{libc.so} and \tts{libGL.so} start using
it heavily.  Because of this \tts{prelink} doesn't do anything special
when prelinking shared libraries with these relocations and for each
relocations in this class creates one conflict fixup.

In second class are relocations which resolve to \tts{st\_value}
of some \tts{STT\_TLS} symbol.  These relocations are used in
Global Dynamic \tts{TLS} model (in Local Dynamic they are resolved
at link time already) and from \tts{prelink} point of view they are
much more similar to normal relocations than the other two classes.
When the \tts{STT\_TLS} symbol is looked up successfully in shared library's
natural search scope, \tts{prelink} just stores its \tts{st\_value}
into the relocation.  The chances there will be a conflict are even
smaller than with normal symbol lookups, since overloading \tts{TLS}
symbols means wasted memory in each single thread and thus library
writers will try to avoid it if possible.

The third class includes relocations which resolve to offsets within
program's initial \tts{TLS} block
\footnote{Negative on architectures which have
\tts{TLS} block immediately below thread pointer (e.g. IA-32, AMD64,
SPARC, S/390) and positive on architectures which have \tts{TLS} block
at thread pointer or a few bytes above it (e.g. PowerPC, Alpha, IA-64,
SuperH).}
Relocation in this class are used in Initial Exec \tts{TLS} model
(or in Local Exec model if this model is supported in shared libraries).
These offsets are even harder to predict than module IDs and unlike
module IDs it wouldn't be very helpful if they were assigned by
\tts{prelink} instead of dynamic linker (which would just read them
from some dynamic tag).  That's because \tts{TLS} block needs to be
packed tightly and any assignments in \tts{prelink} couldn't take
into account other shared libraries linked into the same executable
and the executable itself.  Similarly to module ID relocations,
\tts{prelink} doesn't do anything about them when prelinking shared
libraries and for each such relocation creates a conflict fixup.

\section{Prelinking of executables and shared libraries}

Rewriting of executables is harder than for shared libraries, both because
there are more changes necessary and because shared libraries are
relocatable and thus have dynamic relocations for all absolute addresses.

After collecting all information from the dynamic linker and assigning
virtual address space slots to all shared libraries, prelinking of shared
libraries involves following steps:
\begin{itemize}
\item Relocation of the shared library to the assigned base address.
\item \tts{REL} to \tts{RELA} conversion if needed (the only step which
changes sizes of allocated sections in the middle).
\item On architectures which have \tts{SHT\_NOBITS} \tts{.plt} sections,
before relocations are applied the section needs to be converted to
\tts{SHT\_PROGBITS}.  As the section needs to be at the end (or after it)
of file backed part of some \tts{PT\_LOAD} segment, this just means that
the file backed up part needs to be enlarged, the file filled with zeros
and all following section file offsets or program header entry file
offsets adjusted.  All \tts{SHT\_NOBITS} sections in the same \tts{PT\_LOAD}
segment with virtual addresses lower than the \tts{.plt} start address
need to be converted from \tts{SHT\_NOBITS} to \tts{SHT\_PROGBITS} too.
Without making the section \tts{SHT\_PROGBITS}, \tts{prelink} cannot
apply relocations against it as such sections contain only zeros.
Architectures with \tts{SHT\_NOBITS} \tts{.plt} section supported by
\tts{prelink} are PowerPC and PowerPC64.
\item Applying relocations.  For each dynamic relocation in the shared
library, address of relocation's symbol looked up in natural symbol lookup
search scope of the shared library (or 0 if the symbol is not found in
that search scope) is stored in an architecture and relocation type
dependent way to memory pointed by \tts{r\_offset} field of the relocation.
This step uses symbol lookup information provided by dynamic linker.
\item Addition or modification of \tts{DT\_CHECKSUM} and
\tts{DT\_GNU\_PRELINKED} dynamic tags.
\footnote{\tts{Prelink} is not able to grow \tts{.dynamic} section, so it
needs some spare dynamic tags (DT\_NULL) at the end of \tts{.dynamic}
section.  GNU linker versions released after August 2001 leave space by
default.}  The former is set to checksum of allocated sections in the
shared library, the latter to time of prelinking.
\item On architectures which don't use writable \tts{.plt}, but instead use
\tts{.got.plt} (this section is merged during linking into \tts{.got})
section, \tts{prelink} typically stores address into the first PLT slot
in \tts{.plt} section to the reserved second word of \tts{.got} section.
On these architectures, the dynamic linker has to initialize \tts{.plt}
section if lazy binding.  On non-prelinked executables or shared libraries
this typically means adding load offset to the values in \tts{.got.plt}
section,  for prelinked shared libraries or executables if prelinking
information cannot be used it needs to compute the right values in
\tts{.got.plt} section without looking at this section's content
(since it contains prelinking information).  The second word in \tts{.got}
section is used for this computation.
\item Addition of \tts{.gnu\_prelink\_undo} unallocated section if not
present yet.  This section is used by \tts{prelink} internally during
undo operation.
\item Addition of \tts{.gnu\_liblist} and \tts{.gnu\_libstr} unallocated
sections or, if they are already present, their update including possible
growing or shrinking.  These sections are used only by \tts{prelink} to
compare the dependent libraries (and their order) at the time when the
shared library was prelinked against current dependencies.  If a shared
library has no dependencies (e.g. dynamic linker), these sections are not
present.
\end{itemize}

Adding or resizing unallocated section needs just file offsets of following
unallocated sections recomputed (ensuring proper alignment), growing section
header table and \tts{.shstrtab} and adding new section names to that section.

Prelinking of executables involves following steps:
\begin{itemize}
\item \tts{REL} to \tts{RELA} conversion if needed.
\item \tts{SHT\_NOBITS} to \tts{SHT\_PROGBITS} conversion of \tts{.plt} section
if needed.
\item Applying relocations.
\item Addition or resizing of allocated \tts{.gnu.conflict} section containing
list of conflict fixups.
\item Addition or resizing of allocated \tts{.gnu.liblist} section which is used
by the dynamic linker at runtime to see if none of the dependencies changed
or were reordered.  If they were, it continues normal relocation processing,
otherwise they can be skipped and only conflict fixups applied.
\item Growing of allocated \tts{.dynstr} section, where strings referenced from
\tts{.gnu.liblist} section need to be added.
\item If there are any COPY relocations (which \tts{prelink} wants to handle
rather than deferring them as conflict fixups to runtime), they need to be applied.
\item Modifying second word in \tts{.got} section for \tts{.got.plt} using
architectures.
\item Addition or adjusting of dynamic tags which allow the dynamic linker
to find the \tts{.gnu.liblist} and \tts{.gnu.conflict} sections and their
sizes.  \tts{DT\_GNU\_CONFLICT} and \tts{DT\_GNU\_CONFLICTSZ} should be present
if there are any conflict fixups.  It should contain the virtual address of
the \tts{.gnu.conflict} section start resp. its size in bytes. 
\tts{DT\_GNU\_LIBLIST} and \tts{DT\_GNU\_LIBLISTSZ} need to be present in
all prelinked executables and must be equal the to virtual address of
the \tts{.gnu.liblist} section and its size in bytes.
\item Addition of \tts{.gnu\_prelink\_undo} unallocated section if not present.
\end{itemize}

Executables can have absolute relocations already applied (and without a
dynamic relocation) to virtually any allocated \tts{SHT\_PROGBITS} section
\footnote{One exception is \tts{.interp} special section.  It shouldn't have
relocations applied to it, nor any other section should reference it.},
against almost all allocated \tts{SHT\_PROGBITS} and \tts{SHT\_NOBITS}
sections.  This means that when growing, adding or shrinking allocated
sections in executables, all \tts{SHT\_PROGBITS} and \tts{SHT\_NOBITS} section
must keep their original virtual addresses and sizes
\footnote{With a notable exception of splitting one section into two
covering the same virtual address range.}. \tts{Prelink} tries various
places where to put allocated sections which were added or grew:
\begin{itemize}
\item In the unlikely case if there is already some gap between
sections in read-only \tts{PT\_LOAD} segment where the section fits.
\item If the \tts{SHT\_NOBITS} sections are small enough to fit
into a page together with the preceding \tts{SHT\_PROGBITS} section and there
is still some space in the page after the \tts{SHT\_NOBITS} sections.
In this case, \tts{prelink} converts the \tts{SHT\_NOBITS} sections into
\tts{SHT\_PROGBITS} sections, fills them with zeros and adds the new section
after it.  This doesn't increase number of \tts{PT\_LOAD} segments, but
unfortunately those added sections are writable.  This doesn't matter
much for e.g. \tts{.gnu.conflict} section which is only used before control
is transfered to the program, but could matter for \tts{.dynstr} which is
used even during \tts{dlopen}.
\item On IA-32, executables have for historical reasons base address 0x8048000.
The reason for this was that when stack was put immediately below executables,
stack and the executable could coexist in the same second level page table.
Linux puts the stack typically at the end of virtual address space and so
keeping this exact base address is not really necessary.  \tts{Prelink} can
decrease the base address and thus increase size of read-only \tts{PT\_LOAD}
segment while \tts{SHT\_PROGBITS} and \tts{SHT\_NOBITS} section can stay
at their previous addresses.  Just their file offsets need to be increased.
All these segment header adjustments need to be done in multiplies of
\tts{ELF} page sizes, so even if \tts{prelink} chose to do similar things
on architectures other than IA-32 which typically start executables on some address
which is a power of 2, it would be only reasonable if \tts{ELF} page size
on that architecture (which can be much bigger than page size used by the
operating system) is very small.
\item Last possibility is to create a new \tts{PT\_LOAD} segment.
\footnote{Linux kernels before 2.4.10 loaded executables which had middle \tts{PT\_LOAD}
segment with \tts{p\_memsz} bigger than \tts{p\_filesz} incorrectly, so
\tts{prelink} should be only used on systems with 2.4.10 or later kernels.}
Section immediately above program header table (typically \tts{.interp})
has to be moved somewhere else, but if possible close to the beginning
of the executable.  The new \tts{PT\_LOAD} segment is then added after the
last \tts{PT\_LOAD} segment.  The segment has to be writable even when
all the sections in it are read-only, unless it ends exactly on a page
boundary, because \tts{brk} area starts immediately after the end of last
\tts{PT\_LOAD} segment and the executable expects it to be writable.
\end{itemize}

So that verification works properly, if there is \tts{.gnu.prelink\_undo}
section in the executable, \tts{prelink} first reshuffles the sections and
segments for the purpose of finding places for the sections to the original
sequence as recorded in the \tts{.gnu.prelink\_undo} section.
Examples of the above mentioned cases:

\noindent{{\small\begin{verbatim}
$ SEDCMD='s/^.* \.plt.*$/.../;/\[.*\.text/,/\[.*\.got/d'
$ SEDCMD2='/Section to Segment/,$d;/^Key to/,/^Program/d;/^[A-Z]/d;/^ *$/d'
$ cat > test1.c <<EOF
int main (void) { return 0; }
EOF
$ gcc -Wl,--verbose 2>&1 \
  | sed '/^===/,/^===/!d;/^===/d;s/\.rel\.dyn/. += 512; &/' > test1.lds
$ gcc -s -O2 -o test1 test1.c -Wl,-T,test1.lds
$ readelf -Sl ./test1 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08048148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0804816c 00016c 000040 10   A  5   1  4
  [ 5] .dynstr           STRTAB          080481ac 0001ac 000045 00   A  0   0  1
  [ 6] .gnu.version      VERSYM          080481f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080481fc 0001fc 000020 00   A  5   1  4
  [ 8] .rel.dyn          REL             0804841c 00041c 000008 08   A  4   0  4
  [ 9] .rel.plt          REL             08048424 000424 000008 08   A  4   b  4
  [10] .init             PROGBITS        0804842c 00042c 000017 00  AX  0   0  4
...
  [22] .bss              NOBITS          080496f8 0006f8 000004 00  WA  0   0  4
  [23] .comment          PROGBITS        00000000 0006f8 000132 00      0   0  1
  [24] .shstrtab         STRTAB          00000000 00082a 0000be 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x005fc 0x005fc R E 0x1000
  LOAD           0x0005fc 0x080495fc 0x080495fc 0x000fc 0x00100 RW  0x1000
  DYNAMIC        0x000608 0x08049608 0x08049608 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
$ prelink -N ./test1
$ readelf -Sl ./test1 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08048148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0804816c 00016c 000040 10   A  8   1  4
  [ 5] .gnu.liblist      GNU_LIBLIST     080481ac 0001ac 000028 14   A  8   0  4
  [ 6] .gnu.version      VERSYM          080481f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080481fc 0001fc 000020 00   A  8   1  4
  [ 8] .dynstr           STRTAB          0804821c 00021c 000058 00   A  0   0  1
  [ 9] .gnu.conflict     RELA            08048274 000274 0000c0 0c   A  4   0  4
  [10] .rel.dyn          REL             0804841c 00041c 000008 08   A  4   0  4
  [11] .rel.plt          REL             08048424 000424 000008 08   A  4   d  4
  [12] .init             PROGBITS        0804842c 00042c 000017 00  AX  0   0  4
...
  [24] .bss              NOBITS          080496f8 0006f8 000004 00  WA  0   0  4
  [25] .comment          PROGBITS        00000000 0006f8 000132 00      0   0  1
  [26] .gnu.prelink_undo PROGBITS        00000000 00082c 0004d4 01      0   0  4
  [27] .shstrtab         STRTAB          00000000 000d00 0000eb 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x005fc 0x005fc R E 0x1000
  LOAD           0x0005fc 0x080495fc 0x080495fc 0x000fc 0x00100 RW  0x1000
  DYNAMIC        0x000608 0x08049608 0x08049608 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
\end{verbatim}}
\prelinklistingcaption{Reshuffling of an executable with a gap between sections}}

\begin{figure}[!ht]
\centering
\includegraphics[width=\textwidth]{gap}
\caption{Reshuffling of an executable with a gap between sections}
\end{figure}

In the above sample, there was enough space between sections (particularly
between the end of the \tts{.gnu.version\_r} section and the start of \tts{.rel.dyn})
that the new sections could be added there.

\noindent{{\small\begin{verbatim}
$ SEDCMD='s/^.* \.plt.*$/.../;/\[.*\.text/,/\[.*\.got/d'
$ SEDCMD2='/Section to Segment/,$d;/^Key to/,/^Program/d;/^[A-Z]/d;/^ *$/d'
$ cat > test2.c <<EOF
int main (void) { return 0; }
EOF
$ gcc -s -O2 -o test2 test2.c
$ readelf -Sl ./test2 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08048148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0804816c 00016c 000040 10   A  5   1  4
  [ 5] .dynstr           STRTAB          080481ac 0001ac 000045 00   A  0   0  1
  [ 6] .gnu.version      VERSYM          080481f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080481fc 0001fc 000020 00   A  5   1  4
  [ 8] .rel.dyn          REL             0804821c 00021c 000008 08   A  4   0  4
  [ 9] .rel.plt          REL             08048224 000224 000008 08   A  4   b  4
  [10] .init             PROGBITS        0804822c 00022c 000017 00  AX  0   0  4
...
  [22] .bss              NOBITS          080494f8 0004f8 000004 00  WA  0   0  4
  [23] .comment          PROGBITS        00000000 0004f8 000132 00      0   0  1
  [24] .shstrtab         STRTAB          00000000 00062a 0000be 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x003fc 0x003fc R E 0x1000
  LOAD           0x0003fc 0x080493fc 0x080493fc 0x000fc 0x00100 RW  0x1000
  DYNAMIC        0x000408 0x08049408 0x08049408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
$ prelink -N ./test2
$ readelf -Sl ./test2 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08048148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0804816c 00016c 000040 10   A 23   1  4
  [ 5] .gnu.liblist      GNU_LIBLIST     080481ac 0001ac 000028 14   A 23   0  4
  [ 6] .gnu.version      VERSYM          080481f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080481fc 0001fc 000020 00   A 23   1  4
  [ 8] .rel.dyn          REL             0804821c 00021c 000008 08   A  4   0  4
  [ 9] .rel.plt          REL             08048224 000224 000008 08   A  4   b  4
  [10] .init             PROGBITS        0804822c 00022c 000017 00  AX  0   0  4
...
  [22] .bss              PROGBITS        080494f8 0004f8 000004 00  WA  0   0  4
  [23] .dynstr           STRTAB          080494fc 0004fc 000058 00   A  0   0  1
  [24] .gnu.conflict     RELA            08049554 000554 0000c0 0c   A  4   0  4
  [25] .comment          PROGBITS        00000000 000614 000132 00      0   0  1
  [26] .gnu.prelink_undo PROGBITS        00000000 000748 0004d4 01      0   0  4
  [27] .shstrtab         STRTAB          00000000 000c1c 0000eb 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x003fc 0x003fc R E 0x1000
  LOAD           0x0003fc 0x080493fc 0x080493fc 0x00218 0x00218 RW  0x1000
  DYNAMIC        0x000408 0x08049408 0x08049408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
\end{verbatim}}
\prelinklistingcaption{Reshuffling of an executable with small \tts{.bss}}}

\begin{figure}[!ht]
\centering
\includegraphics[width=\textwidth]{bss}
\caption{Reshuffling of an executable with small \tts{.bss}}
\end{figure}

In this case \tts{.bss} section was small enough that \tts{prelink}
converted it to \tts{SHT\_PROGBITS}.

\noindent{{\small\begin{verbatim}
$ SEDCMD='s/^.* \.plt.*$/.../;/\[.*\.text/,/\[.*\.got/d'
$ SEDCMD2='/Section to Segment/,$d;/^Key to/,/^Program/d;/^[A-Z]/d;/^ *$/d'
$ cat > test3.c <<EOF
int foo [4096];
int main (void) { return 0; }
EOF
$ gcc -s -O2 -o test3 test3.c
$ readelf -Sl ./test3 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08048148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0804816c 00016c 000040 10   A  5   1  4
  [ 5] .dynstr           STRTAB          080481ac 0001ac 000045 00   A  0   0  1
  [ 6] .gnu.version      VERSYM          080481f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080481fc 0001fc 000020 00   A  5   1  4
  [ 8] .rel.dyn          REL             0804821c 00021c 000008 08   A  4   0  4
  [ 9] .rel.plt          REL             08048224 000224 000008 08   A  4   b  4
  [10] .init             PROGBITS        0804822c 00022c 000017 00  AX  0   0  4
...
  [22] .bss              NOBITS          08049500 000500 004020 00  WA  0   0 32
  [23] .comment          PROGBITS        00000000 000500 000132 00      0   0  1
  [24] .shstrtab         STRTAB          00000000 000632 0000be 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x003fc 0x003fc R E 0x1000
  LOAD           0x0003fc 0x080493fc 0x080493fc 0x000fc 0x04124 RW  0x1000
  DYNAMIC        0x000408 0x08049408 0x08049408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
$ prelink -N ./test3
$ readelf -Sl ./test3 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08047114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08047128 000128 000020 00   A  0   0  4
  [ 3] .dynstr           STRTAB          08047148 000148 000058 00   A  0   0  1
  [ 4] .gnu.liblist      GNU_LIBLIST     080471a0 0001a0 000028 14   A  3   0  4
  [ 5] .gnu.conflict     RELA            080471c8 0001c8 0000c0 0c   A  7   0  4
  [ 6] .hash             HASH            08048148 001148 000024 04   A  7   0  4
  [ 7] .dynsym           DYNSYM          0804816c 00116c 000040 10   A  3   1  4
  [ 8] .gnu.version      VERSYM          080481f2 0011f2 000008 02   A  7   0  2
  [ 9] .gnu.version_r    VERNEED         080481fc 0011fc 000020 00   A  3   1  4
  [10] .rel.dyn          REL             0804821c 00121c 000008 08   A  7   0  4
  [11] .rel.plt          REL             08048224 001224 000008 08   A  7   d  4
  [12] .init             PROGBITS        0804822c 00122c 000017 00  AX  0   0  4
...
  [24] .bss              NOBITS          08049500 0014f8 004020 00  WA  0   0 32
  [25] .comment          PROGBITS        00000000 0014f8 000132 00      0   0  1
  [26] .gnu.prelink_undo PROGBITS        00000000 00162c 0004d4 01      0   0  4
  [27] .shstrtab         STRTAB          00000000 001b00 0000eb 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08047034 0x08047034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08047114 0x08047114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08047000 0x08047000 0x013fc 0x013fc R E 0x1000
  LOAD           0x0013fc 0x080493fc 0x080493fc 0x000fc 0x04124 RW  0x1000
  DYNAMIC        0x001408 0x08049408 0x08049408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08047128 0x08047128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
\end{verbatim}}
\prelinklistingcaption{Reshuffling of an executable with decreasing of base address}}

\begin{figure}[!ht]
\centering
\includegraphics[width=\textwidth]{basemove}
\caption{Reshuffling of an executable with decreasing of the base address}
\end{figure}

In \tts{test3} the base address of the executable was decreased by one page and
the new sections added there.

\noindent{{\small\begin{verbatim}
$ SEDCMD='s/^.* \.plt.*$/.../;/\[.*\.text/,/\[.*\.got/d'
$ SEDCMD2='/Section to Segment/,$d;/^Key to/,/^Program/d;/^[A-Z]/d;/^ *$/d'
$ cat > test4.c <<EOF
int foo [4096];
int main (void) { return 0; }
EOF
$ gcc -Wl,--verbose 2>&1 \
  | sed '/^===/,/^===/!d;/^===/d;s/0x08048000/0x08000000/' > test4.lds
$ gcc -s -O2 -o test4 test4.c -Wl,-T,test4.lds
$ readelf -Sl ./test4 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08000114 000114 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08000128 000128 000020 00   A  0   0  4
  [ 3] .hash             HASH            08000148 000148 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0800016c 00016c 000040 10   A  5   1  4
  [ 5] .dynstr           STRTAB          080001ac 0001ac 000045 00   A  0   0  1
  [ 6] .gnu.version      VERSYM          080001f2 0001f2 000008 02   A  4   0  2
  [ 7] .gnu.version_r    VERNEED         080001fc 0001fc 000020 00   A  5   1  4
  [ 8] .rel.dyn          REL             0800021c 00021c 000008 08   A  4   0  4
  [ 9] .rel.plt          REL             08000224 000224 000008 08   A  4   b  4
  [10] .init             PROGBITS        0800022c 00022c 000017 00  AX  0   0  4
...
  [22] .bss              NOBITS          08001500 000500 004020 00  WA  0   0 32
  [23] .comment          PROGBITS        00000000 000500 000132 00      0   0  1
  [24] .shstrtab         STRTAB          00000000 000632 0000be 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08000034 0x08000034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08000114 0x08000114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08000000 0x08000000 0x003fc 0x003fc R E 0x1000
  LOAD           0x0003fc 0x080013fc 0x080013fc 0x000fc 0x04124 RW  0x1000
  DYNAMIC        0x000408 0x08001408 0x08001408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08000128 0x08000128 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
$ prelink -N ./test4
$ readelf -Sl ./test4 | sed -e "$SEDCMD" -e "$SEDCMD2"
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08000134 000134 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08000148 000148 000020 00   A  0   0  4
  [ 3] .hash             HASH            08000168 000168 000024 04   A  4   0  4
  [ 4] .dynsym           DYNSYM          0800018c 00018c 000040 10   A 22   1  4
  [ 5] .gnu.version      VERSYM          080001f2 0001f2 000008 02   A  4   0  2
  [ 6] .gnu.version_r    VERNEED         080001fc 0001fc 000020 00   A 22   1  4
  [ 7] .rel.dyn          REL             0800021c 00021c 000008 08   A  4   0  4
  [ 8] .rel.plt          REL             08000224 000224 000008 08   A  4   a  4
  [ 9] .init             PROGBITS        0800022c 00022c 000017 00  AX  0   0  4
...
  [21] .bss              NOBITS          08001500 0004f8 004020 00  WA  0   0 32
  [22] .dynstr           STRTAB          080064f8 0004f8 000058 00   A  0   0  1
  [23] .gnu.liblist      GNU_LIBLIST     08006550 000550 000028 14   A 22   0  4
  [24] .gnu.conflict     RELA            08006578 000578 0000c0 0c   A  4   0  4
  [25] .comment          PROGBITS        00000000 000638 000132 00      0   0  1
  [26] .gnu.prelink_undo PROGBITS        00000000 00076c 0004d4 01      0   0  4
  [27] .shstrtab         STRTAB          00000000 000c40 0000eb 00      0   0  1
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08000034 0x08000034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000134 0x08000134 0x08000134 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08000000 0x08000000 0x003fc 0x003fc R E 0x1000
  LOAD           0x0003fc 0x080013fc 0x080013fc 0x000fc 0x04124 RW  0x1000
  LOAD           0x0004f8 0x080064f8 0x080064f8 0x00140 0x00140 RW  0x1000
  DYNAMIC        0x000408 0x08001408 0x08001408 0x000c8 0x000c8 RW  0x4
  NOTE           0x000148 0x08000148 0x08000148 0x00020 0x00020 R   0x4
  STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
\end{verbatim}}
\prelinklistingcaption{Reshuffling of an executable with addition of a new segment}}

\begin{figure}[!ht]
\centering
\includegraphics[width=\textwidth]{newseg}
\caption{Reshuffling of an executable with addition of a new segment}
\end{figure}

In the last example, base address was not decreased but instead a new
\tts{PT\_LOAD} segment has been added.

\tts{R\_<arch>\_COPY} relocations are typically against first part of the
\tts{SHT\_NOBITS} \tts{.bss} section.  So that \tts{prelink} can apply them,
it needs to first change their section to \tts{SHT\_PROGBITS}, but as \tts{.bss}
section typically occupies much larger part of memory, it is not desirable
to convert \tts{.bss} section into \tts{SHT\_PROGBITS} as whole.  A section
cannot be partly \tts{SHT\_PROGBITS} and partly \tts{SHT\_NOBITS}, so \tts{prelink}
first splits the section into two parts, first \tts{.dynbss} which covers area
from the start of \tts{.bss} section up to highest byte to which some COPY
relocation is applied and then the old \tts{.bss}.  The first is converted
to \tts{SHT\_PROGBITS} and its size is decreased, the latter stays \tts{SHT\_NOBITS}
and its start address and file offset are adjusted as well as its size decreased.
The dynamic linker handles relocations in the executable last, so \tts{prelink}
cannot just copy memory from the shared library where the symbol of the COPY
relocation has been looked up in.  There might be relocations applied by the
dynamic linker in normal relocation processing to the objects, so \tts{prelink}
has to first process the relocations against that memory area.  Relocations
which don't need conflict fixups are already applied, so \tts{prelink} just
needs to apply conflict fixups against the memory area, then copy it
to the newly created \tts{.dynbss} section.

Here is an example which shows various things which COPY relocation handling
in \tts{prelink} needs to deal with:

\noindent{{\small\begin{verbatim}
$ cat > test1.c <<EOF
struct A { char a; struct A *b; int *c; int *d; };
int bar, baz;
struct A foo = { 1, &foo, &bar, &baz };
int *addr (void) { return &baz; }
EOF
$ cat > test.c <<EOF
#include <stdio.h>
struct A { char a; struct A *b; int *c; int *d; };
int bar, *addr (void), big[8192];
extern struct A foo;
int main (void)
{
  printf ("%p: %d %p %p %p %p %p\n", &foo, foo.a, foo.b, foo.c, foo.d,
	  &bar, addr ());
}
EOF
$ gcc -nostdlib -shared -fpic -s -o test1.so test1.c
$ gcc -s -o test test.c ./test1.so
$ ./test
0x80496c0: 1 0x80496c0 0x80516e0 0x4833a4 0x80516e0 0x4833a4
$ readelf -r test | sed '/\.rel\.dyn/,/\.rel\.plt/!d;/^0/!d'
080496ac  00000c06 R_386_GLOB_DAT    00000000   __gmon_start__
080496c0  00000605 R_386_COPY        080496c0   foo
$ readelf -S test | grep bss
  [22] .bss              NOBITS          080496c0 0006c0 008024 00  WA  0   0 32
$ prelink -N ./test ./test1.so
$ readelf -s test | grep foo
     6: 080496c0    16 OBJECT  GLOBAL DEFAULT   25 foo
$ readelf -s test1.so | grep foo
    15: 004a9314    16 OBJECT  GLOBAL DEFAULT    6 foo
$ readelf -r test | sed '/.gnu.conflict/,/\.rel\.dyn/!d;/^0/!d'
004a9318  00000001 R_386_32                                     080496c0
004a931c  00000001 R_386_32                                     080516e0
005f9874  00000001 R_386_32                                     fffffff0
005f9878  00000001 R_386_32                                     00000001
005f98bc  00000001 R_386_32                                     fffffff4
005f9900  00000001 R_386_32                                     ffffffec
005f9948  00000001 R_386_32                                     ffffffdc
005f995c  00000001 R_386_32                                     ffffffe0
005f9980  00000001 R_386_32                                     fffffff8
005f9988  00000001 R_386_32                                     ffffffe4
005f99a4  00000001 R_386_32                                     ffffffd8
005f99c4  00000001 R_386_32                                     ffffffe8
005f99d8  00000001 R_386_32                                     08048584
004c2510  00000007 R_386_JUMP_SLOT                              00534460
004c2514  00000007 R_386_JUMP_SLOT                              00534080
004c2518  00000007 R_386_JUMP_SLOT                              00534750
004c251c  00000007 R_386_JUMP_SLOT                              005342c0
004c2520  00000007 R_386_JUMP_SLOT                              00534200
$ objdump -s -j .dynbss test

test:     file format elf32-i386

Contents of section .dynbss:
 80496c0 01000000 c0960408 e0160508 a4934a00  ..............J.
$ objdump -s -j .data test1.so

test1.so:     file format elf32-i386

Contents of section .data:
 4a9314 01000000 14934a00 a8934a00 a4934a00  ......J...J...J.
$ readelf -S test | grep bss
  [24] .dynbss           PROGBITS        080496c0 0016c0 000010 00  WA  0   0 32
  [25] .bss              NOBITS          080496d0 0016d0 008014 00  WA  0   0 32
$ sed 's/8192/1/' test.c > test2.c
$ gcc -s -o test2 test2.c ./test1.so
$ readelf -S test2 | grep bss
  [22] .bss              NOBITS          080496b0 0006b0 00001c 00  WA  0   0  8
$ prelink -N ./test2 ./test1.so
$ readelf -S test2 | grep bss
  [22] .dynbss           PROGBITS        080496b0 0006b0 000010 00  WA  0   0  8
  [23] .bss              PROGBITS        080496c0 0006c0 00000c 00  WA  0   0  8
\end{verbatim}}
\prelinklistingcaption{Relocation handling of \tts{.dynbss} objects}}

Because \tts{test.c} executable is not compiled as position independent code and
takes address of {\sl foo} variable, a COPY relocation is needed to avoid
dynamic relocation against executable's read-only \tts{PT\_LOAD} segment.
The {\sl foo} object in \tts{test1.so} has one field with no relocations
applied at all, one relocation against the variable itself, one relocation
which needs a conflict fixup (as it is overridden by the variable in the
executable) and one with relocation which doesn't need any fixups.
The first and last field contain already the right values in prelinked
\tts{test1.so}, while second and third one need to be changed for symbol
addresses in the executable (as shown in the \tts{objdump} output).
The conflict fixups against {\sl foo} in \tts{test1.so} need to stay
(unless it is a C++ virtual table or {\sl RTTI} data, i.e. not in this testcase).
In \tts{test}, \tts{prelink} changed \tts{.dynbss} to \tts{SHT\_PROGBITS}
and kept \tts{SHT\_NOBITS} \tts{.bss}, while in slightly modified testcase
(\tts{test2}) the size of \tts{.bss} was small enough that \tts{prelink}
chose to make it \tts{SHT\_PROGBITS} too and grow the read-write
\tts{PT\_LOAD} segment and put \tts{.dynstr} and \tts{.gnu.conflict}
sections after it.

\section{Prelink undo operation}

Prelinking of shared libraries and executables is designed to be reversible,
so that prelink operation followed by undo operation generates bitwise
identical file to the original before prelinking.  For this operation
\tts{prelink} stores the original \tts{ELF} header, all the program and
all section headers into a \tts{.gnu.prelink\_undo} section before it starts prelinking
an unprelinked executable or shared library.  When undoing the modifications,
\tts{prelink} has to convert \tts{RELA} back to \tts{REL} first if \tts{REL}
to \tts{RELA} conversion was done during prelinking and all allocated
sections above it relocated down to adjust for the section shrink.
Relocation types which were changed when trying to avoid \tts{REL} to
\tts{RELA} conversion need to be changed back (e.g. on IA-32, it is
assumed \tts{R\_386\_GLOB\_DAT} relocations should be only those
against \tts{.got} section and \tts{R\_386\_32} relocations in the
remaining places).  On \tts{RELA} architectures, the memory pointed
by \tts{r\_offset} field of the relocations needs to be reinitialized
to the values stored there by the linker originally.
For \tts{prelink} it doesn't matter much what this value is (e.g.
always 0, copy of \tts{r\_addend}, etc.), as long as it is computable
from the information \tts{prelink} has during undo operation
\footnote{Such as relocation type, \tts{r\_addend} value,
type, binding, flags or other attributes of relocation's symbol,
what section the relocation points into or the offset within
section it points to.}.  The GNU linker had to be changed on several
architectures, so that it stores there such a value, as in several places
the value e.g. depended on original addend before final link (which is
not available anywhere after final link time, since \tts{r\_addend}
field could be adjusted during the final link).
If second word of \tts{.got} section has been modified, it needs
to be reverted back to the original value (on most architectures zero).
In executables, sections which were moved during prelinking need to be
put back and segments added while prelinking must be removed.

There are 3 different ways how an undo operation can be performed:
\begin{itemize}
\item Undoing individual executables or shared libraries specified on the
command line in place (i.e. when the undo operation is successful,
the prelinked executable or library is atomically replaced with the
undone object).
\item With \tts{-o} option, only a single executable or shared library
given on the command line is undone and stored to the file specified
as \tts{-o} option's argument.
\item With \tts{-ua} options, \tts{prelink} builds a list of executables
in paths written in its config file (plus directories and executables
or libraries from command line) and all shared libraries these executables
depend on.  All executables and libraries in the list are then unprelinked.
This option is used to unprelink the whole system.  It is not perfect
and needs to be worked on, since e.g. if some executable uses some shared
library which no other executable links against, this executable (and shared
library) is prelinked, then the executable is removed (e.g. uninstalled)
but the shared library is kept, then the shared library is not
unprelinked unless specifically mentioned on the command line.
\end{itemize}

\section{Verification of prelinked files}

As \tts{prelink} needs to modify executables and shared libraries installed
on a system, it complicates system integrity verification (e.g. \tts{rpm -V},
TripWire).  These systems store checksums of installed files into some
database and during verification compute them again and compare to the
values stored in the database.  On a prelinked system most of the executables
and shared libraries would be reported as modified.  \tts{Prelink} offers
a special mode for these systems, in which it verifies that unprelinking
the executable or shared library followed by immediate prelinking (with the
same base address) creates bitwise identical output with the executable
or shared library that's being verified.  Furthermore, depending on
other \tts{prelink} options, it either writes the unprelinked image
to its standard output or computes MD5 or SHA1 digest from this unprelinked
image.  Mere undo operation to a file and checksumming it is not good
enough, since an intruder could have modified e.g. conflict fixups or
memory which relocations point at, changing a behavior of the program
while file after unprelinking would be unmodified.

During verification, both \tts{prelink} executable and the dynamic linker
are used, so a proper system integrity verification first checks whether
\tts{prelink} executable (which is statically linked for this reason) hasn't
been modified, then uses \tts{prelink --verify} to verify the dynamic linker
(when verificating \tts{ld.so} the dynamic linker is not executed)
followed by verification of other executables and libraries.

Verification requires all dependencies of checked object to be unmodified
since last prelinking.  If some dependency has been changed or is missing,
\tts{prelink} will report it and return with non-zero exit status.
This is because prelinking depends on their content and so if they are
modified, the executable or shared library might be different to one after
unprelinking followed by prelinking again.  In the future, perhaps it
would be possible to even verify executables or shared libraries without
unmodified dependencies, under the assumption that in such case the prelink
information will not be used.  It would just need to verify that nothing
else but the information only used when dependencies are up to date
has changed between the executable or library on the filesystem and file
after unprelink followed by prelink cycle.  The prelink operation
would need to be modified in this case, so that no information is
collected from the dynamic linker, the list of dependencies is assumed
to be the one stored in the executable and expect it to have identical
number of conflict fixups.

\section{Measurements}

There are two areas where \tts{prelink} can speed things up noticeably.
The primary is certainly startup time of big GUI applications where the
dynamic linker spends from 100ms up to a few seconds before giving control
to the application.  Another area is when lots of small programs are started
up, but their execution time is rather short, so the startup time which
\tts{prelink} optimizes is a noticeable fraction of the total time.
This is typical for shell scripting.

First numbers are from \tts{lmbench} benchmark, version 3.0-a3.
Most of the benchmarks in \tts{lmbench} suite measure kernel speed,
so it doesn't matter much whether \tts{prelink} is used or not.
Only in \tts{lat\_proc} benchmark \tts{prelink} shows up visibly.
This benchmark measures 3 different things:
\begin{itemize}
\item {\sl fork proc}, which is \tts{fork()} followed by immediate
\tts{exit(1)} in the child and \tts{wait(0)} in the parent.  The results
are (as expected) about the same between unprelinked and prelinked systems.
\item {\sl exec proc}, i.e. \tts{fork()} followed by immediate
\tts{close(1)} and \tts{execve()} of a simple hello world program (this
program is compiled and linked during the benchmark into a temporary
directory and is never prelinked).  The numbers are 160$\mu$s to 200$\mu$s
better on prelinked systems, because there is no relocation processing needed
initially in the dynamic linker and because all relative relocations
in \tts{libc.so.6} can be skipped.
\item {\sl sh proc}, i.e. \tts{fork()} followed by immediate \tts{close(1)}
and \tts{execlp("/bin/sh", "sh", "-c", "/tmp/hello", 0)}.  Although
the hello world program is not prelinked in this case either, the shell is,
so out of the 900$\mu$s to 1000$\mu$s speedup less than 200$\mu$s can be
accounted on the speed up of the hello world program as in {\sl exec proc}
benchmark and the rest to the speedup of shell startup.
\end{itemize}

First 4 rows are from running the benchmark on a fully unprelinked system,
the last 4 rows on the same system, but fully prelinked.

\noindent{{\small\begin{verbatim}
                 L M B E N C H  3 . 0   S U M M A R Y
                 ------------------------------------
		 (Alpha software, do not distribute)

Processor, Processes - times in microseconds - smaller is better
-------------------------------------------------------------------------
Host           OS  Mhz null null      open slct sig  sig  fork exec sh  
                       call  I/O stat clos TCP  inst hndl proc proc proc
---- ------------ ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
pork Linux 2.4.22  651 0.53 0.97 6.20 8.10 41.2 1.44 4.30 276. 1497 5403
pork Linux 2.4.22  651 0.53 0.95 6.14 7.91 37.8 1.43 4.34 274. 1486 5391
pork Linux 2.4.22  651 0.56 0.94 6.18 8.09 43.4 1.41 4.30 251. 1507 5423
pork Linux 2.4.22  651 0.53 0.94 6.12 8.09 41.0 1.43 4.40 256. 1497 5385
pork Linux 2.4.22  651 0.56 0.94 5.79 7.58 39.1 1.41 4.30 271. 1319 4460
pork Linux 2.4.22  651 0.56 0.92 5.76 7.40 38.9 1.41 4.30 253. 1304 4417
pork Linux 2.4.22  651 0.56 0.95 6.20 7.83 37.7 1.41 4.37 248. 1323 4481
pork Linux 2.4.22  651 0.56 1.01 6.04 7.77 37.9 1.43 4.32 256. 1324 4457
\end{verbatim}}
\prelinklistingcaption{\tts{lmbench} results without and with prelinking}}

Below is a sample timing of a 239K long configure shell script from GCC
on both unprelinked and prelinked system.  Preparation step was following:

\noindent{{\small\begin{verbatim}
cd; cvs -d :pserver:anoncvs@subversions.gnu.org:/cvsroot/gcc login
# Empty password
cvs -d :pserver:anoncvs@subversions.gnu.org:/cvsroot/gcc -z3 co -D20031103 gcc
mkdir ~/gcc/obj
cd ~/gcc/obj; ../configure i386-redhat-linux; make configure-gcc
\end{verbatim}}
\prelinklistingcaption{Preparation script for shell script tests}}

On an unprelinked system, the results were:

\noindent{{\small\begin{verbatim}
cd ~/gcc/obj/gcc
for i in 1 2; do ./config.status --recheck > /dev/null 2>&1; done
for i in 1 2 3 4; do time ./config.status --recheck > /dev/null 2>&1; done

real    0m4.436s
user    0m1.730s
sys     0m1.260s

real    0m4.409s
user    0m1.660s
sys     0m1.340s

real    0m4.431s
user    0m1.810s
sys     0m1.300s

real    0m4.432s
user    0m1.670s
sys     0m1.210s
\end{verbatim}}
\prelinklistingcaption{Shell script test results on unprelinked system}}

and on a fully prelinked system:

\noindent{{\small\begin{verbatim}
cd ~/gcc/obj/gcc
for i in 1 2; do ./config.status --recheck > /dev/null 2>&1; done
for i in 1 2 3 4; do time ./config.status --recheck > /dev/null 2>&1; done

real    0m4.126s
user    0m1.590s
sys     0m1.240s

real    0m4.151s
user    0m1.620s
sys     0m1.230s

real    0m4.161s
user    0m1.600s
sys     0m1.190s

real    0m4.122s
user    0m1.570s
sys     0m1.230s
\end{verbatim}}
\prelinklistingcaption{Shell script test results on prelinked system}}

Now timing of a few big GUI programs.  All timings were done without X
server running and with \tts{DISPLAY} environment variable not set
(so that when control is transfered to the application, it very soon
finds out there is no X server it can talk to and bail out).  The
measurements are done by the dynamic linker in ticks on a 651MHz
dual Pentium III machine, i.e. ticks have to be divided by 651000000
to get times in seconds.  Each application has been run 4 times
and the results with smallest total time spent in the dynamic
linker was chosen.  Epiphany WWW browser and Evolution mail client
were chosen as examples of \tts{Gtk+} applications (typically they use
really many shared libraries, but many of them are quite small,
there aren't really many relocations nor conflict fixups and most
of the libraries are written in C) and Konqueror WWW browser and
KWord word processor were chosen as examples of \tts{KDE} applications
(typically they use slightly fewer shared libraries, though
still a lot, most of the shared libraries are written in C++,
have many relocations and cause many conflict fixups, especially
without C++ conflict fixup optimizations in \tts{prelink}).
On non-prelinked system, the timings are done with lazy binding,
i.e. without \tts{LD\_BIND\_NOW=1} set in the environment.
This is because that's how people generally run programs, on the other
side it is not exact apples to apples comparison, since on prelinked
system there is no lazy binding with the exception of shared libraries
loaded through \tts{dlopen}.  So when control is passed to the application,
prelinked programs should be slightly faster for a while since non-prelinked
programs will have to do symbol lookups and processing relocations
(and on various architectures flushing instruction caches) whenever
they call some function they haven't called before in particular shared
library or in the executable.

\noindent{{\small\begin{verbatim}
$ ldd `which epiphany-bin` | wc -l
     64
$ # Unprelinked system
$ LD_DEBUG=statistics epiphany-bin 2>&1 | sed 's/^ *//'
18960:
18960:     runtime linker statistics:
18960:       total startup time in dynamic loader: 67336593 clock cycles
18960:                 time needed for relocation: 58119983 clock cycles (86.3%)
18960:                      number of relocations: 6999
18960:           number of relocations from cache: 4770
18960:             number of relative relocations: 31494
18960:                time needed to load objects: 8696104 clock cycles (12.9%)

(epiphany-bin:18960): Gtk-WARNING **: cannot open display:
18960:
18960:     runtime linker statistics:
18960:                final number of relocations: 7692
18960:     final number of relocations from cache: 4770
$ # Prelinked system
$ LD_DEBUG=statistics epiphany-bin 2>&1 | sed 's/^ *//'
25697:
25697:  runtime linker statistics:
25697:    total startup time in dynamic loader: 7313721 clock cycles
25697:              time needed for relocation: 565680 clock cycles (7.7%)
25697:                   number of relocations: 0
25697:        number of relocations from cache: 1205
25697:          number of relative relocations: 0
25697:             time needed to load objects: 6179467 clock cycles (84.4%)

(epiphany-bin:25697): Gtk-WARNING **: cannot open display:
25697:
25697:  runtime linker statistics:
25697:             final number of relocations: 31
25697:  final number of relocations from cache: 1205

$ ldd `which evolution` | wc -l
     68
$ # Unprelinked system
$ LD_DEBUG=statistics evolution 2>&1 | sed 's/^ *//'
19042:
19042:  runtime linker statistics:
19042:    total startup time in dynamic loader: 54382122 clock cycles
19042:              time needed for relocation: 43403190 clock cycles (79.8%)
19042:                   number of relocations: 3452
19042:        number of relocations from cache: 2885
19042:          number of relative relocations: 34957
19042:             time needed to load objects: 10450142 clock cycles (19.2%)

(evolution:19042): Gtk-WARNING **: cannot open display:
19042:
19042:  runtime linker statistics:
19042:             final number of relocations: 4075
19042:  final number of relocations from cache: 2885
$ # Prelinked system
$ LD_DEBUG=statistics evolution 2>&1 | sed 's/^ *//'
25723:
25723:  runtime linker statistics:
25723:    total startup time in dynamic loader: 9176140 clock cycles
25723:              time needed for relocation: 203783 clock cycles (2.2%)
25723:                   number of relocations: 0
25723:        number of relocations from cache: 525
25723:          number of relative relocations: 0
25723:             time needed to load objects: 8405157 clock cycles (91.5%)

(evolution:25723): Gtk-WARNING **: cannot open display:
25723:
25723:  runtime linker statistics:
25723:             final number of relocations: 31
25723:  final number of relocations from cache: 525

$ ldd `which konqueror` | wc -l
     37
$ # Unprelinked system
$ LD_DEBUG=statistics konqueror 2>&1 | sed 's/^ *//'
18979:
18979:  runtime linker statistics:
18979:    total startup time in dynamic loader: 131985703 clock cycles
18979:              time needed for relocation: 127341077 clock cycles (96.4%)
18979:                   number of relocations: 25473
18979:        number of relocations from cache: 53594
18979:          number of relative relocations: 31171
18979:             time needed to load objects: 4318803 clock cycles (3.2%)
konqueror: cannot connect to X server
18979:
18979:  runtime linker statistics:
18979:             final number of relocations: 25759
18979:  final number of relocations from cache: 53594
$ # Prelinked system
$ LD_DEBUG=statistics konqueror 2>&1 | sed 's/^ *//'
25733:
25733:  runtime linker statistics:
25733:    total startup time in dynamic loader: 5533696 clock cycles
25733:              time needed for relocation: 1941489 clock cycles (35.0%)
25733:                   number of relocations: 0
25733:        number of relocations from cache: 2066
25733:          number of relative relocations: 0
25733:             time needed to load objects: 3217736 clock cycles (58.1%)
konqueror: cannot connect to X server
25733:
25733:  runtime linker statistics:
25733:             final number of relocations: 0
25733:  final number of relocations from cache: 2066

$ ldd `which kword` | wc -l
     40
$ # Unprelinked system
$ LD_DEBUG=statistics kword 2>&1 | sed 's/^ *//'
19065:
19065:  runtime linker statistics:
19065:    total startup time in dynamic loader: 153684591 clock cycles
19065:              time needed for relocation: 148255294 clock cycles (96.4%)
19065:                   number of relocations: 26231
19065:        number of relocations from cache: 55833
19065:          number of relative relocations: 30660
19065:             time needed to load objects: 5068746 clock cycles (3.2%)
kword: cannot connect to X server
19065:
19065:  runtime linker statistics:
19065:             final number of relocations: 26528
19065:  final number of relocations from cache: 55833
$ # Prelinked system
$ LD_DEBUG=statistics kword 2>&1 | sed 's/^ *//'
25749:
25749:  runtime linker statistics:
25749:    total startup time in dynamic loader: 6516635 clock cycles
25749:              time needed for relocation: 2106856 clock cycles (32.3%)
25749:                   number of relocations: 0
25749:        number of relocations from cache: 2130
25749:          number of relative relocations: 0
25749:             time needed to load objects: 4008585 clock cycles (61.5%)
kword: cannot connect to X server
25749:
25749:  runtime linker statistics:
25749:             final number of relocations: 0
25749:  final number of relocations from cache: 2130
\end{verbatim}}
\prelinklistingcaption{Dynamic linker statistics for unprelinked and prelinked GUI programs}}

In the case of above mentioned \tts{Gtk+} applications, the original startup
time spent in the dynamic linker decreased into 11\% to 17\% of the original
times, with \tts{KDE} applications it decreased even into around 4.2\% of original
times.

The startup time reported by the dynamic linker is only part of the total
startup time of a GUI program.  Unfortunately it cannot be measured very
accurately without patching each application separately, so that it would
print current process CPU time at the point when all windows are painted and
the process starts waiting for user input.  The following table contains
values reported by \tts{time(1)} command on each of the 4 GUI programs
running under X, both on unprelinked and fully prelinked system.
As soon as each program painted its windows, it was killed by
application's quit hot key
\footnote{\tts{Ctrl+W} for Epiphany, \tts{Ctrl+Q} for Evolution and
Konqueror and \tts{Enter} in Kword's document type choice dialog.}.
Especially the \tts{real} time values depend also on the speed of
human reactions, so each measurement was repeated 10 times.  All timings
were done with hot caches, after running the applications two times
before measurement.

\noindent{\small\begin{center}
\begin{longtable}{l|llllllllll|ll}
{\bf Type} & \multicolumn{10}{l|}{\bf Values (in seconds)} & {\bf Average} & {\bf Std.Dev.} \\
\hline
\endhead
& \multicolumn{10}{l|}{unprelinked epiphany} && \\
\hline
{real} & {3.053} & {2.84} & {2.996} & {2.901} & {3.019} & {2.929} & {2.883} & {2.975} & {2.922} & {3.026} & {2.954} & {0.0698} \\
{user} & {2.33} & {2.31} & {2.28} & {2.32} & {2.44} & {2.37} & {2.29} & {2.35} & {2.34} & {2.41} & {2.344} & {0.0508} \\
{sys} & {0.2} & {0.23} & {0.23} & {0.19} & {0.19} & {0.12} & {0.25} & {0.16} & {0.14} & {0.14} & {0.185} & {0.0440} \\
\hline
& \multicolumn{10}{l|}{prelinked epiphany} && \\
\hline
{real} & {2.773} & {2.743} & {2.833} & {2.753} & {2.753} & {2.644} & {2.717} & {2.897} & {2.68} & {2.761} & {2.755} & {0.0716} \\
{user} & {2.18} & {2.17} & {2.17} & {2.12} & {2.23} & {2.26} & {2.13} & {2.17} & {2.15} & {2.15} & {2.173} & {0.0430} \\
{sys} & {0.13} & {0.15} & {0.18} & {0.15} & {0.11} & {0.04} & {0.18} & {0.14} & {0.1} & {0.15} & {0.133} & {0.0416} \\
\hline
& \multicolumn{10}{l|}{unprelinked evolution} && \\
\hline
{real} & {2.106} & {1.886} & {1.828} & {2.12} & {1.867} & {1.871} & {2.242} & {1.871} & {1.862} & {2.241} & {1.989} & {0.1679} \\
{user} & {1.12} & {1.09} & {1.15} & {1.19} & {1.17} & {1.23} & {1.15} & {1.11} & {1.17} & {1.14} & {1.152} & {0.0408} \\
{sys} & {0.1} & {0.11} & {0.13} & {0.07} & {0.1} & {0.05} & {0.11} & {0.11} & {0.09} & {0.08} & {0.095} & {0.0232} \\
\hline
& \multicolumn{10}{l|}{prelinked evolution} && \\
\hline
{real} & {1.684} & {1.621} & {1.686} & {1.72} & {1.694} & {1.691} & {1.631} & {1.697} & {1.668} & {1.535} & {1.663} & {0.0541} \\
{user} & {0.92} & {0.87} & {0.92} & {0.95} & {0.79} & {0.86} & {0.94} & {0.87} & {0.89} & {0.86} & {0.887} & {0.0476} \\
{sys} & {0.06} & {0.1} & {0.06} & {0.05} & {0.11} & {0.08} & {0.07} & {0.1} & {0.12} & {0.07} & {0.082} & {0.0239} \\
\hline
& \multicolumn{10}{l|}{unprelinked kword} && \\
\hline
{real} & {2.111} & {1.414} & {1.36} & {1.356} & {1.259} & {1.383} & {1.28} & {1.321} & {1.252} & {1.407} & {1.414} & {0.2517} \\
{user} & {1.04} & {0.9} & {0.93} & {0.88} & {0.89} & {0.89} & {0.87} & {0.89} & {0.9} & {0.8} & {0.899} & {0.0597} \\
{sys} & {0.07} & {0.04} & {0.06} & {0.05} & {0.06} & {0.1} & {0.09} & {0.08} & {0.08} & {0.12} & {0.075} & {0.0242} \\
\hline
& \multicolumn{10}{l|}{prelinked kword} && \\
\hline
{real} & {1.59} & {1.052} & {0.972} & {1.064} & {1.106} & {1.087} & {1.066} & {1.087} & {1.065} & {1.005} & {1.109} & {0.1735} \\
{user} & {0.61} & {0.53} & {0.58} & {0.6} & {0.6} & {0.58} & {0.59} & {0.61} & {0.57} & {0.6} & {0.587} & {0.0241} \\
{sys} & {0.08} & {0.08} & {0.06} & {0.06} & {0.03} & {0.07} & {0.06} & {0.03} & {0.06} & {0.04} & {0.057} & {0.0183} \\
\hline
& \multicolumn{10}{l|}{unprelinked konqueror} && \\
\hline
{real} & {1.306} & {1.386} & {1.27} & {1.243} & {1.227} & {1.286} & {1.262} & {1.322} & {1.345} & {1.332} & {1.298} & {0.0495} \\
{user} & {0.88} & {0.86} & {0.88} & {0.9} & {0.87} & {0.83} & {0.83} & {0.86} & {0.86} & {0.89} & {0.866} & {0.0232} \\
{sys} & {0.07} & {0.11} & {0.12} & {0.1} & {0.12} & {0.08} & {0.13} & {0.12} & {0.09} & {0.08} & {0.102} & {0.0210} \\
\hline
& \multicolumn{10}{l|}{prelinked konqueror} && \\
\hline
{real} & {1.056} & {0.962} & {0.961} & {0.906} & {0.927} & {0.923} & {0.933} & {0.958} & {0.955} & {1.142} & {0.972} & {0.0722} \\
{user} & {0.56} & {0.6} & {0.56} & {0.52} & {0.57} & {0.58} & {0.5} & {0.57} & {0.61} & {0.55} & {0.562} & {0.0334} \\
{sys} & {0.1} & {0.13} & {0.08} & {0.15} & {0.07} & {0.09} & {0.09} & {0.09} & {0.1} & {0.08} & {0.098} & {0.0244} \\
\hline
\multicolumn{13}{l}{} \\
\caption{GUI program start up times without and with prelinking} \\
\end{longtable}
\end{center}}

\tts{OpenOffice.org} is probably the largest program these days in Linux,
mostly written in C++.  In \tts{OpenOffice.org} 1.1, the main executable,
\tts{soffice.bin}, links directly against 34 shared libraries, but typically
during startup it loads using \tts{dlopen} many others.  As has been
mentioned earlier, \tts{prelink} cannot speed up loading shared libraries
using \tts{dlopen}, since it cannot predict in which order and what
shared libraries will be loaded (and thus cannot compute conflict fixups).
The \tts{soffice.bin} is typically started through a wrapper script
and depending on what arguments are passed to it, different
\tts{OpenOffice.org} application is started.  With no options, it starts
just empty window with menu from which the applications can be started,
with say \tts{private:factory/swriter} argument it starts
a word processor, with \tts{private:factory/scalc} it starts a spreadsheet
etc.  When \tts{soffice.bin} is already running, if you start another
copy of it, it just instructs the already running copy to pop up a new
window and exits.

In an experiment, \tts{soffice.bin} has been invoked 7 times against running
X server, with no arguments, \tts{private:factory/swriter},
\tts{private:factory/scalc}, \tts{private:factory/sdraw},
\tts{private:factory/simpress}, \tts{private:factory/smath} arguments
(in all these cases nothing was pressed at all) and last with
the \tts{private:factory/swriter} argument where the menu item \tts{New Presentation}
was selected and the word processor window closed.
In all these cases, \tts{/proc/`pidof soffice.bin`/maps} file was
captured and the application then killed.  This file contains among
other things list of all shared libraries mmapped by the process at
the point where it started waiting for user input after loading up.
These lists were then summarized, to get number of the runs in
which particular shared library was loaded up out of the total 7
runs.  There were 38 shared libraries shipped as part of \tts{OpenOffice.org}
package which have been loaded in all 7 times, another 3 shared
libraries included in \tts{OpenOffice.org} (and also one shared
library shipped in another package, \tts{libdb\_cxx-4.1.so})
which were loaded 6 times.
\footnote{In all runs but when ran without
arguments.  But when the application is started without any
arguments, it cannot do any useful work, so one loads one of the
applications afterward anyway.}  There was one shared library
loaded in 5 runs, but was locale specific and thus not worth
considering.  Inspecting \tts{OpenOffice.org} source, these shared
libraries are never unloaded with \tts{dlclose}, so \tts{soffice.bin}
can be made much more \tts{prelink} friendly and thus save substantial
amount of startup time by linking against all those 76 shared libraries
instead of just 34 shared libraries it is linked against.
In the timings below, \tts{soffice1.bin} is the original \tts{soffice.bin}
as created by the \tts{OpenOffice.org} makefiles and \tts{soffice3.bin} is
the same executable linked dynamically against additional 42 shared libraries.
The ordering of those 42 shared libraries matters for the number of conflict
fixups, unfortunately with large C++ shared libraries there is no obvious rule
for ordering them as sometimes it is more useful when a shared library precedes
its dependency and sometimes vice versa, so a few different orderings were
tried in several steps and always the one with smallest number of conflict
fixups was chosen.  Still, the number of conflict fixups is quite high
and big part of the fixups are storing addresses of \tts{PLT} slots in
the executable into various places in shared libraries
\footnote{This might get better when the linker is modified to handle
calls without ever taking address of the function in executables specially,
but only testing it will actually show it up.}
\tts{soffice2.bin} is another experiment, where the executable itself is empty
source file, all objects which were originally in \tts{soffice.bin}
executable with the exception of start files were recompiled as position independent
code and linked into a new shared library.  This reduced number of conflicts
a lot and speeded up start up times against \tts{soffice3.bin} when caches
are hot.  It is a little bit slower than \tts{soffice3.bin} when running
with cold caches (e.g. for the first time after bootup), as there is one
more shared library to load etc.

In the timings below, numbers for \tts{soffice1.bin} and \tts{soffice2.bin}
resp. \tts{soffice3.bin} cannot be easily compared, as \tts{soffice1.bin}
loads less than half of the needed shared libraries which the remaining
two executables load and the time to load those shared libraries doesn't
show up there.  Still, when it is prelinked it takes just slightly more
than two times longer to load \tts{soffice2.bin} than \tts{soffice1.bin}
and the times are still less than 7\% of how long it takes to load
just the initial 34 shared libraries when not prelinking.

\noindent{{\small\begin{verbatim}
$ S='s/^ *//'
$ ldd /usr/lib/openoffice/program/soffice1.bin | wc -l
     34
$ # Unprelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice1.bin 2>&1 | sed "$S"
19095:
19095:  runtime linker statistics:
19095:    total startup time in dynamic loader: 159833582 clock cycles
19095:              time needed for relocation: 155464174 clock cycles (97.2%)
19095:                   number of relocations: 31136
19095:        number of relocations from cache: 31702
19095:          number of relative relocations: 18284
19095:             time needed to load objects: 3919645 clock cycles (2.4%)
/usr/lib/openoffice/program/soffice1.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
19095:
19095:  runtime linker statistics:
19095:             final number of relocations: 31715
19095:  final number of relocations from cache: 31702
$ # Prelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice1.bin 2>&1 | sed "$S"
25759:
25759:  runtime linker statistics:
25759:    total startup time in dynamic loader: 4252397 clock cycles
25759:              time needed for relocation: 1189840 clock cycles (27.9%)
25759:                   number of relocations: 0
25759:        number of relocations from cache: 2142
25759:          number of relative relocations: 0
25759:             time needed to load objects: 2604486 clock cycles (61.2%)
/usr/lib/openoffice/program/soffice1.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
25759:
25759:  runtime linker statistics:
25759:             final number of relocations: 24
25759:  final number of relocations from cache: 2142
$ ldd /usr/lib/openoffice/program/soffice2.bin | wc -l
     77
$ # Unprelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice2.bin 2>&1 | sed "$S"
19115:
19115:  runtime linker statistics:
19115:    total startup time in dynamic loader: 947793670 clock cycles
19115:              time needed for relocation: 936895741 clock cycles (98.8%)
19115:                   number of relocations: 69164
19115:        number of relocations from cache: 94502
19115:          number of relative relocations: 59374
19115:             time needed to load objects: 10046486 clock cycles (1.0%)
/usr/lib/openoffice/program/soffice2.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
19115:
19115:  runtime linker statistics:
19115:             final number of relocations: 69966
19115:  final number of relocations from cache: 94502
$ # Prelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice2.bin 2>&1 | sed "$S"
25777:
25777:  runtime linker statistics:
25777:    total startup time in dynamic loader: 10952099 clock cycles
25777:              time needed for relocation: 3254518 clock cycles (29.7%)
25777:                   number of relocations: 0
25777:        number of relocations from cache: 5309
25777:          number of relative relocations: 0
25777:             time needed to load objects: 6805013 clock cycles (62.1%)
/usr/lib/openoffice/program/soffice2.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
25777:
25777:  runtime linker statistics:
25777:             final number of relocations: 24
25777:  final number of relocations from cache: 5309
$ ldd /usr/lib/openoffice/program/soffice3.bin | wc -l
     76
$ # Unprelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice3.bin 2>&1 | sed "$S"
19131:
19131:  runtime linker statistics:
19131:    total startup time in dynamic loader: 852275754 clock cycles
19131:              time needed for relocation: 840996859 clock cycles (98.6%)
19131:                   number of relocations: 68362
19131:        number of relocations from cache: 89213
19131:          number of relative relocations: 55831
19131:             time needed to load objects: 10170207 clock cycles (1.1%)
/usr/lib/openoffice/program/soffice3.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
19131:
19131:  runtime linker statistics:
19131:             final number of relocations: 69177
19131:  final number of relocations from cache: 89213
$ # Prelinked system
$ LD_DEBUG=statistics /usr/lib/openoffice/program/soffice3.bin 2>&1 | sed "$S"
25847:
25847:  runtime linker statistics:
25847:    total startup time in dynamic loader: 12277407 clock cycles
25847:              time needed for relocation: 4232915 clock cycles (34.4%)
25847:                   number of relocations: 0
25847:        number of relocations from cache: 8961
25847:          number of relative relocations: 0
25847:             time needed to load objects: 6925023 clock cycles (56.4%)
/usr/lib/openoffice/program/soffice3.bin X11 error: Can't open display:
Set DISPLAY environment variable, use -display option
or check permissions of your X-Server
(See "man X" resp. "man xhost" for details)
25847:
25847:  runtime linker statistics:
25847:             final number of relocations: 24
25847:  final number of relocations from cache: 8961
\end{verbatim}}
\prelinklistingcaption{Dynamic linker statistics for unprelinked and prelinked OpenOffice.org}}

Below are measurement using \tts{time(1)} for each of the \tts{soffice.bin}
variants, prelinked and unprelinked.  \tts{OpenOffice.org} was killed
immediately after painting \tts{Writer}'s window using \tts{Ctrl+Q}.

\noindent{\small\begin{center}
\begin{longtable}{l|llllllllll|ll}
{\bf Type} & \multicolumn{10}{l|}{\bf Values (in seconds)} & {\bf Average} & {\bf Std.Dev.} \\
\hline
\endhead
& \multicolumn{10}{l|}{unprelinked soffice1.bin private:factory/swriter} && \\
\hline
{real} & {5.569} & {5.149} & {5.547} & {5.559} & {5.549} & {5.139} & {5.55} & {5.559} & {5.598} & {5.559} & {5.478} & {0.1765} \\
{user} & {4.65} & {4.57} & {4.62} & {4.64} & {4.57} & {4.55} & {4.65} & {4.49} & {4.52} & {4.46} & {4.572} & {0.0680} \\
{sys} & {0.29} & {0.24} & {0.19} & {0.21} & {0.21} & {0.21} & {0.25} & {0.25} & {0.27} & {0.26} & {0.238} & {0.0319} \\
\hline
& \multicolumn{10}{l|}{prelinked soffice1.bin private:factory/swriter} && \\
\hline
{real} & {4.946} & {4.899} & {5.291} & {4.879} & {4.879} & {4.898} & {5.299} & {4.901} & {4.887} & {4.901} & {4.978} & {0.1681} \\
{user} & {4.23} & {4.27} & {4.18} & {4.24} & {4.17} & {4.22} & {4.15} & {4.25} & {4.26} & {4.31} & {4.228} & {0.0494} \\
{sys} & {0.22} & {0.22} & {0.24} & {0.26} & {0.3} & {0.26} & {0.29} & {0.17} & {0.21} & {0.23} & {0.24} & {0.0389} \\
\hline
& \multicolumn{10}{l|}{unprelinked soffice2.bin private:factory/swriter} && \\
\hline
{real} & {5.575} & {5.166} & {5.592} & {5.149} & {5.571} & {5.559} & {5.159} & {5.157} & {5.569} & {5.149} & {5.365} & {0.2201} \\
{user} & {4.59} & {4.5} & {4.57} & {4.37} & {4.47} & {4.57} & {4.56} & {4.41} & {4.63} & {4.5} & {4.517} & {0.0826} \\
{sys} & {0.24} & {0.24} & {0.21} & {0.34} & {0.27} & {0.19} & {0.19} & {0.27} & {0.19} & {0.29} & {0.243} & {0.0501} \\
\hline
& \multicolumn{10}{l|}{prelinked soffice2.bin private:factory/swriter} && \\
\hline
{real} & {3.69} & {3.66} & {3.658} & {3.661} & {3.639} & {3.638} & {3.649} & {3.659} & {3.65} & {3.659} & {3.656} & {0.0146} \\
{user} & {2.93} & {2.88} & {2.88} & {2.9} & {2.84} & {2.63} & {2.89} & {2.85} & {2.77} & {2.83} & {2.84} & {0.0860} \\
{sys} & {0.22} & {0.18} & {0.23} & {0.2} & {0.18} & {0.29} & {0.22} & {0.23} & {0.24} & {0.22} & {0.221} & {0.0318} \\
\hline
& \multicolumn{10}{l|}{unprelinked soffice3.bin private:factory/swriter} && \\
\hline
{real} & {5.031} & {5.02} & {5.009} & {5.028} & {5.019} & {5.019} & {5.019} & {5.052} & {5.426} & {5.029} & {5.065} & {0.1273} \\
{user} & {4.31} & {4.35} & {4.34} & {4.3} & {4.38} & {4.29} & {4.45} & {4.37} & {4.38} & {4.44} & {4.361} & {0.0547} \\
{sys} & {0.27} & {0.25} & {0.26} & {0.27} & {0.27} & {0.31} & {0.18} & {0.17} & {0.16} & {0.15} & {0.229} & {0.0576} \\
\hline
& \multicolumn{10}{l|}{prelinked soffice3.bin private:factory/swriter} && \\
\hline
{real} & {3.705} & {3.669} & {3.659} & {3.669} & {3.66} & {3.659} & {3.659} & {3.661} & {3.668} & {3.649} & {3.666} & {0.0151} \\
{user} & {2.86} & {2.88} & {2.85} & {2.84} & {2.83} & {2.86} & {2.84} & {2.91} & {2.86} & {2.8} & {2.853} & {0.0295} \\
{sys} & {0.26} & {0.19} & {0.27} & {0.25} & {0.24} & {0.23} & {0.28} & {0.21} & {0.21} & {0.27} & {0.241} & {0.0303} \\
\hline
\multicolumn{13}{l}{} \\
\caption{OpenOffice.org start up times without and with prelinking} \\
\end{longtable}
\end{center}}

\section{Similar tools on other ELF using Operating Systems}

Something similar to \tts{prelink} is available on other \tts{ELF}
platforms.  On Irix there is \tts{QUICKSTART} and on Solaris \tts{crle}.

SGI \tts{QUICKSTART} is much closer to \tts{prelink} from these two.
The \tts{rqs} program relocates libraries to (if possible) unique
virtual address space slot.  The base address is either specified
on the command line with the \tts{-l} option, or \tts{rqs} uses
a \tts{so\_locations} registry with \tts{-c} or \tts{-u} options
and finds a not yet occupied slot.  This is similar to how \tts{prelink}
lays out libraries without the \tts{-m} option.

\tts{QUICKSTART} uses the same data structure for library lists
(\tts{ElfNN\_Lib}) as \tts{prelink}, but uses more fields in it
(\tts{prelink} doesn't use \tts{l\_version} and \tts{l\_flags} fields at
the moment) and uses different dynamic tags and section type for
it.  Another difference is that \tts{QUICKSTART} makes all liblist
section \tts{SHF\_ALLOC}, whether in shared libraries or executables.
\tts{prelink} only needs liblist section in the executable be allocated,
liblist sections in shared libraries are not allocated and used
at \tts{prelink} time only.

The biggest difference between \tts{QUICKSTART} and \tts{prelink}
is in how conflicts are encoded.  SGI stores them in a very compact
format, as array of \tts{.dynsym} section indexes for symbols which
are conflicting.  There is no information publicly available
what exactly SGI dynamic linker does when it is resolving the conflicts,
so this is just a guess.  Given that the conflicts can be stored
in a shared library or executable different to the shared library with the
relocations against the conflicting symbol and different to the shared
library which the symbol was originally resolved to, there doesn't seem
to be an obvious way how to handle the conflicts very cheaply.
The dynamic linker probably collects list of all conflicting symbol
names, for each such symbol computes \tts{ELF} hash and walks hash buckets
for this hash of all shared libraries, looking for the symbol.
Every time it finds the symbol, all relocations against it need to be
redone.  Unlike this, \tts{prelink} stores conflicts as an array of
\tts{ElfNN\_Rela} structures, with one entry for each shared relocation
against conflicting symbol in some shared library.  This guarantees
that there are no symbol lookups during program startup (provided
that shared libraries have not been changed after prelinking), while
with \tts{QUICKSTART} will do some symbol lookups if there are any
conflicts.  \tts{QUICKSTART} puts conflict sections into the executable
and every shared library where \tts{rqs} determines conflicts while
\tts{prelink} stores them in the executable only (but the array is typically
much bigger).  Disk space requirements for prelinked executables are certainly
bigger than for requickstarted executables, but which one has bigger runtime
memory requirements is unclear.  If prelinking can be used, all \tts{.rela*}
and \tts{.rel*} sections in the executable and all shared libraries are skipped,
so they will not need to be paged in during whole program's life (with the
exception of first and last pages in the relocation sections which can be
paged in because of other sections on the same page), but whole
\tts{.gnu.conflict} section needs to be paged in (read-only) and processed.
With \tts{QUICKSTART}, probably all (much smaller) conflict sections need
to be paged in and also likely for each conflict whole relocation sections
of each library which needs the conflict to be applied against.

In \tts{QUICKSTART} documentation, SGI says that conflicts are very costly
and that developers should avoid them.  Unfortunately, this is sometimes quite
hard, especially with C++ shared libraries.  It is unclear whether \tts{rqs}
does any optimizations to trim down the number of conflicts.

Sun took completely different approach.  The dynamic linker provides a
\tts{dldump (const char *ipath, const char *opath, int flags);} function.
{\sl ipath} is supposed to be a path to an \tts{ELF} object loaded already in
the current process.  This function creates a new \tts{ELF} object at
{\sl opath}, which is like the {\sl ipath} object, but relocated to the
base address which it has actually been mapped at in the current process
and with some relocations (specified in {\sl flags} bitmask) applied as
they have been resolved in the current process.  Relocations, which have
been applied, are overwritten in the relocation sections with
\tts{R\_*\_NONE} relocations.  The \tts{crle} executable, in addition to other
functions not related to startup times, with some specific options uses the
\tts{dldump} function to dump all shared libraries a particular executable
uses (and the executable itself) into a new directory, with selected
relocation classes being already applied.  The main disadvantage of this
approach is that such alternate shared libraries are at least for
most relocation classes not shareable across different programs at all
(and for those where they could be shareable a little bit there will
be many relocations left for the dynamic linker, so the speed gains will
be small).  Another disadvantage is that all relocation sections need to
be paged into the memory, just to find out that most of the relocations
are \tts{R\_*\_NONE}.

\section{ELF extensions for prelink}

\tts{Prelink} needs a few \tts{ELF} extensions for its data structures
in \tts{ELF} objects.  For list of dependencies at the time of prelinking,
a new section type \tts{SHT\_GNU\_LIBLIST} is defined:

\noindent{{\small\begin{verbatim}
#define SHT_GNU_LIBLIST   0x6ffffff7  /* Prelink library list */

typedef struct
{
  Elf32_Word l_name;            /* Name (string table index) */
  Elf32_Word l_time_stamp;      /* Timestamp */
  Elf32_Word l_checksum;        /* Checksum */
  Elf32_Word l_version;         /* Unused, should be zero */
  Elf32_Word l_flags;           /* Unused, should be zero */
} Elf32_Lib;

typedef struct
{
  Elf64_Word l_name;            /* Name (string table index) */
  Elf64_Word l_time_stamp;      /* Timestamp */
  Elf64_Word l_checksum;        /* Checksum */
  Elf64_Word l_version;         /* Unused, should be zero */
  Elf64_Word l_flags;           /* Unused, should be zero */
} Elf64_Lib;
\end{verbatim}}
\prelinklistingcaption{New structures and section type constants used by \tts{prelink}}}

Introduces a few new special sections:

\noindent{\begin{center}
\begin{longtable}{l|lc}
{\bf Name} & {\bf Type} & {\bf Attributes} \\
\hline
& {\sl In shared libraries} & \\
{.gnu.liblist} & {SHT\_GNU\_LIBLIST} & {0} \\
{.gnu.libstr} & {SHT\_STRTAB} & {0} \\
{.gnu.prelink\_undo} & {SHT\_PROGBITS} & {0} \\
\hline
& {\sl In executables} & \\
{.gnu.liblist} & {SHT\_GNU\_LIBLIST} & {SHF\_ALLOC} \\
{.gnu.conflict} & {SHT\_RELA} & {SHF\_ALLOC} \\
{.gnu.prelink\_undo} & {SHT\_PROGBITS} & {0} \\
\multicolumn{3}{l}{} \\
\caption{Special sections introduced by \tts{prelink}} \\
\end{longtable}
\end{center}}

\begin{description}
\item[\tts{.gnu.liblist}] This section contains one \tts{ElfNN\_Lib} structure
for each shared library which the object has been prelinked against,
in the order in which they appear in symbol search scope.
Section's \tts{sh\_link} value should contain section index of \tts{.gnu.libstr}
for shared libraries and section index of \tts{.dynsym} for executables.
\tts{l\_name} field contains the dependent library's name as index
into the section pointed by\tts{sh\_link} field.  \tts{l\_time\_stamp}
resp. \tts{l\_checksum} should contain copies of \tts{DT\_GNU\_PRELINKED}
resp. \tts{DT\_CHECKSUM} values of the dependent library.

\item[\tts{.gnu.conflict}] This section contains one \tts{ElfNN\_Rela}
structure for each needed \tts{prelink} conflict fixup.  \tts{r\_offset}
field contains the absolute address at which the fixup needs to be applied,
\tts{r\_addend} the value that needs to be stored at that location.
\tts{ELFNN\_R\_SYM} of \tts{r\_info} field should be zero,
\tts{ELFNN\_R\_TYPE} of \tts{r\_info} field should be architecture
specific relocation type which should be handled the same as
for \tts{.rela.*} sections on the architecture.  For \tts{EM\_ALPHA} machine,
all types with \tts{R\_ALPHA\_JMP\_SLOT} in lowest 8 bits of \tts{ELF64\_R\_TYPE}
should be handled as \tts{R\_ALPHA\_JMP\_SLOT} relocation, the upper
24 bits contains index in original \tts{.rela.plt} section of the
\tts{R\_ALPHA\_JMP\_SLOT} relocation the fixup was created for.

\item[\tts{.gnu.libstr}] This section contains strings for \tts{.gnu.liblist}
section in shared libraries where \tts{.gnu.liblist} section is not
allocated.

\item[\tts{.gnu.prelink\_undo}] This section contains \tts{prelink} private
data used for \tts{prelink --undo} operation.  This data includes the
original \tts{ElfNN\_Ehdr} of the object before prelinking and all its
original \tts{ElfNN\_Phdr} and \tts{ElfNN\_Shdr} headers.
\end{description}

\tts{Prelink} also defines 6 new dynamic tags:

\noindent{{\small\begin{verbatim}
#define DT_GNU_PRELINKED  0x6ffffdf5  /* Prelinking timestamp */
#define DT_GNU_CONFLICTSZ 0x6ffffdf6  /* Size of conflict section */
#define DT_GNU_LIBLISTSZ  0x6ffffdf7  /* Size of library list */
#define DT_CHECKSUM       0x6ffffdf8  /* Library checksum */

#define DT_GNU_CONFLICT   0x6ffffef8  /* Start of conflict section */
#define DT_GNU_LIBLIST    0x6ffffef9  /* Library list */
\end{verbatim}}
\prelinklistingcaption{\tts{Prelink} dynamic tags}}

\tts{DT\_GNU\_PRELINKED} and \tts{DT\_CHECKSUM} dynamic tags must
be present in prelinked shared libraries.  The corresponding
\tts{d\_un.d\_val} fields should contain time when the library
has been prelinked (in seconds since January, 1st, 1970, 00:00 UTC)
resp. \tts{CRC32} checksum of all sections with one of
\tts{SHF\_ALLOC}, \tts{SHF\_WRITE} or \tts{SHF\_EXECINSTR} bit set
whose type is not \tts{SHT\_NOBITS}, in the order they appear in the
shared library's section header table, with \tts{DT\_GNU\_PRELINKED}
and \tts{DT\_CHECKSUM} \tts{d\_un.v\_val} values set to 0 for
the time of checksum computation.

The \tts{DT\_GNU\_LIBLIST} and \tts{DT\_GNU\_LIBLISTSZ} dynamic tags
must be present in all prelinked executables.  The \tts{d\_un.d\_ptr} value of
the \tts{DT\_GNU\_LIBLIST} dynamic tag contains the virtual address
of the \tts{.gnu.liblist} section in the executable and \tts{d\_un.d\_val}
of \tts{DT\_GNU\_LIBLISTSZ} tag contains its size in bytes.

\tts{DT\_GNU\_CONFLICT} and \tts{DT\_GNU\_CONFLICTSZ} dynamic tags
may be present in prelinked executables.  \tts{d\_un.d\_ptr} of
\tts{DT\_GNU\_CONFLICT} dynamic tag contains the virtual address
of \tts{.gnu.conflict} section in the executable (if present)
and \tts{d\_un.d\_val} of \tts{DT\_GNU\_CONFLICTSZ} tag contains
its size in bytes.

\begin{appendix}

\section{Glossary}
\printglossary

\section{References}

\begin{description}
\item[\textrm{[1]}]
\href{http://www.caldera.com/developers/devspecs/gabi41.pdf}%
{\sl System V Application Binary Interface, Edition 4.1}.

\item[\textrm{[2]}]
\href{http://www.caldera.com/developers/devspecs/abi386-4.pdf}%
{\sl System V Application Binary Interface, Intel 386 Architecture Processor
Supplement}.

\item[\textrm{[3]}]
\href{http://www.x86-64.org/cgi-bin/cvsweb.cgi/x86-64-ABI/}%
{\sl System V Application Binary Interface, AMD64 Architecture Processor
Supplement}.

\item[\textrm{[4]}]
\href{http://refspecs.freestandards.org/elf/IA64-SysV-psABI.pdf}%
{{\sl System V Application Binary Interface, Intel Itanium Architecture Processor
Supplement}, Intel Corporation, 2001}.

\item[\textrm{[5]}]
\href{http://refspecs.freestandards.org/elf/elfspec_ppc.pdf}%
{Steve Zucker, Kari Karhi, {\sl System V Application Binary Interface,
PowerPC Architecture Processor Supplement}, SunSoft, IBM, 1995}.

\item[\textrm{[6]}]
\href{ftp://ftp.linuxppc64.org/pub/people/amodra/PPC-elf64abi.txt.gz}%
{\sl System V Application Binary Interface, PowerPC64 Architecture Processor
Supplement}.

\item[\textrm{[7]}]
\href{http://www.arm.com/support/566FHT/$File/ARMELF.pdf}%
{\sl System V Application Binary Interface, ARM Architecture Processor
Supplement}.

\item[\textrm{[8]}]
\href{http://www.sparc.com/standards/SCD.2.4.1.ps.Z}%
{{\sl SPARC Compliance Definition, Version 2.4.1},
SPARC International, Inc., 1999}.

\item[\textrm{[9]}]
\href{http://people.redhat.com/drepper/dsohowto.pdf}%
{Ulrich Drepper, {\sl How To Write Shared Libraries}, Red Hat, Inc., 2003}.

\item[\textrm{[10]}]
\href{http://docs.sun.com/db/doc/816-1386}%
{{\sl Linker And Library Guide}, Sun Microsystems, 2002}.

\item[\textrm{[11]}]
\href{http://www.gzlinux.org/docs/category/dev/c/linkerandloader.pdf}%
{John R. Levine, {\sl Linkers and Loaders}, 1999}.

\item[\textrm{[12]}]
\href{http://people.redhat.com/drepper/tls.pdf}%
{Ulrich Drepper, {\sl ELF Handling For Thread-Local Storage}, Red Hat, Inc.,
2003}.

\item[\textrm{[13]}]
\href{ftp://ftp.linuxppc64.org/pub/people/amodra/ppc32tls.txt.gz}%
{Alan Modra, {\sl PowerPC Specific Thread Local Storage ABI}, 2003}.

\item[\textrm{[14]}]
\href{ftp://ftp.linuxppc64.org/pub/people/amodra/ppc64tls.txt.gz}%
{Alan Modra, {\sl PowerPC64 Specific Thread Local Storage ABI}, 2003}.

\item[\textrm{[15]}]
\href{http://www.eagercon.com/dwarf/dwarf-2.0.0.pdf}%
{\sl DWARF Debugging Information Format Version 2}.

\item[\textrm{[16]}]
\href{http://reality.sgiweb.org/davea/dwarf3-draft8-011125.pdf}%
{{\sl DWARF Debugging Information Format Version 3}, Draft, 2001}.

\item[\textrm{[17]}]
\href{http://sources.redhat.com/cgi-bin/cvsweb.cgi/src/gdb/doc/stabs.texinfo?cvsroot=src}%
{\sl The "stabs" debugging information format}.
\end{description}


\section{Revision History}

\begin{description}
\item[2003-11-03] First draft.


\end{description}

\end{appendix}

\end{document}