Re: [PATCH] Resend: Add a new chapter on the dynamic linker

[Florian Weimer <fw at deneb dot enyo dot de>]

* Ben Woodard:

> +@node Dynamic Linking, Program Basics, Signal Handling, Top
> +@c %MENU% Loading libraries, finding functions, and other symbols
> +@chapter Dynamic Linker
> +
> +On every operating system currently supported by @theglibc{}, the
> +operating system provides a facility for run time dynamic
> +linking. This facility is implemented by @theglibc{}'s dynamic linker.

Two spaces after the end of a sentence (this applies throughout).

Dynamic linking support in glibc is in fact optional, and can be
disabled at build time.

I think it makes to mention here that glibc strives to implement the
ELF specification for dynamic linking.

> +Because run time linking is so intimately involved with the lauching
> +of almost every program, it exists at the interface between the
> +operating system kernel and the system libraries. Thus configuration
> +and administration of the run time dynamic linker is operating system
> +specific. Individuals who are interested in this topic are encouraged
> +to look at the operating system documentation.
> +@c which is often found in
> +@c the @cite{ld.so(8)} and the @cite{ldconfig(8)} man pages.
> +@c pindex ld.so
> +@c pindex ldconfig

The above is a bit weird.  I'm not sure what the intent of this
paragraph is.  Do you want to say that there are manual pages for
ld.so and ldconfig (provided by glibc) which live outside of the glibc
project and provide additional information?

> +The run time dynamic linker also provides several mechanisms which
> +allow the system administrator or user to modify its operation when
> +running an application. Many of the tools to modify glibc's run time

“to modify the operation of @theglibc{} run time linker”

> +linker's operation are environmental variables. However, if more
> +sophisticated manipulation of the process of run time linking and
> +symbol resolution is needed, the dynamic has a kind of plugin
> +called an audit library.

“The dynamic linker offers a plugin facility called the audit
subsystem.”

> +@node Concepts of Dynamic Linking
> +@section Concepts of Dynamic linking

Should probably be “Concepts of Static and Dynamic Linking”.

I think you could explain here that linking has to parts: symbol
binding and relocation, and that there are three and half different
ELF object types—ET_REL, ET_DYN, ET_EXEC and PIE ET_EXEC (currently
ET_DYN as well).

> +When you compile a file and are left with an object file that is
> +called a compilation unit. At the time that it is compiled, the
> +compiler can see all the variables and functions that are within the
> +file and it can fill in references to those function and
> +variables. Many times there are functions or variables that exist
> +outside of a particular compilation unit. If you link object files
> +then the linker is able to find the location of referenced symbols or
> +functions in other compilation unit's object files, insert them into
> +the resulting executable, and bind the references to them.
> +
> +Libraries are a special kind object file which include the partially
> +linked aggregation of many compilation unit's object files. You can
> +link with a library one of two ways. Linking with a library statically
> +is the old original way of linking. This is no different than linking
> +with any other object file. Linking statically is not recommended in
> +almost all cases. The second way of linking is dynamically linking
> +with the library.

Can you reword it so that it's clear that there two different types of
libraries?

> In this case, the linker makes sure that all the
> +functions and symbols referred to by your program can be found in the
> +libraries that you are linking with but instead of copying the
> +function or variable over into the resulting executable, it stores a
> +reference to the library in the executable's header and replaces the
> +references to the function with calls to stub functions that will make
> +sure that the needed library is loaded into memory and then will
> +ultimately call the required function. Variables that exist in
> +libraries are handled similarly through a level of indirection.

That's not actually true in all cases.  It depends on the binding and
relocation type (see the noplt function attribute and copy relocations
for variables).

I think it's reasonable to gloss over the implementation details at
this stage.

> +@menu
> +* Finding a Library:: The process of resolving the location of a library
> +* Finding a Symbol:: The process of resolving symbols within libraries
> +* Binding a Variable:: How the GOT is used to bind a variable in a library
> +* Binding a Function:: How the PLT is used to bind functions from libraries
> +* Linkage Tables:: Using non-global linking to avoid potential symbol conflicts
> +@end menu

(line too long)

Maybe this should start with the kernel loading the program
interpreter and the main executable, for completeness.  Something like
this.

@node Loading The Program Interpreter

When the kernel replaces the current process image with a new
executable during the @code{execve} call, it parses the ELF program
header of the executable and performs the file mappings
(readable/writable/executable) indicated there.

@smallexample
$ readelf -l /bin/ls

Elf file type is DYN (Shared object file)
Entry point 0x5430
There are 9 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x0000000000000040 0x0000000000000040
                 0x00000000000001f8 0x00000000000001f8  R E    0x8
  INTERP         0x0000000000000238 0x0000000000000238 0x0000000000000238
                 0x000000000000001c 0x000000000000001c  R      0x1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD           0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x000000000001e184 0x000000000001e184  R E    0x200000
  LOAD           0x000000000001e388 0x000000000021e388 0x000000000021e388
                 0x0000000000001260 0x0000000000002440  RW     0x200000
  DYNAMIC        0x000000000001edb8 0x000000000021edb8 0x000000000021edb8
                 0x00000000000001f0 0x00000000000001f0  RW     0x8
  NOTE           0x0000000000000254 0x0000000000000254 0x0000000000000254
                 0x0000000000000044 0x0000000000000044  R      0x4
  GNU_EH_FRAME   0x000000000001ab74 0x000000000001ab74 0x000000000001ab74
                 0x000000000000082c 0x000000000000082c  R      0x4
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     0x10
  GNU_RELRO      0x000000000001e388 0x000000000021e388 0x000000000021e388
                 0x0000000000000c78 0x0000000000000c78  R      0x1
@end smallexample

The kernel also extracts the program interpreter path (see
@code{INTERP} in the example), and loads it as well.  It then transfer
control to the program interpreter (in userspace).  The program
interpreter first relocates itself (during a bootstrapping step) and
then proceeds to load the shared objects needed by the main executable
(and their dependencies), and finally relocates all the objects and
the main program.

Unlike many other operating systems, dynamic linking, as implemented
by @theglibc{}, is a process which completely resides within
userspace.  The kernel is only used for initial bootstrapping.


> +
> +@node Finding a Library
> +@subsection Finding a Library
> +@cindex Finding a Library, Dynamic Linking
> +Binaries that are not linked statically require the dynamic linker to
> +load the libraries into the process's address space before beginning
> +to run the executable. The shared libraries needed by am executable or
> +a library are stored in dynamic section of the ELF header. The list of
> +the libraries needed can be quickly enumerated with the
> +@command{readelf} command.
> +@pindex readelf
> +
> +@cindex NEEDED, dynamic linking
> +@cindex DT_NEEDED
> +@example
> +$ readelf -d /usr/bin/ls | grep NEEDED

Please use /bin/ls, the portable path.

> +@pindex ldd
> +To make the association between between the library listed as needed
> +in the ELF dynamic section and where they are located as shown by the
> +@command{ldd} command, the run time linker has to look in several
> +places. This process is known as object search. A library can audit or
> +interpose itself into this process of locating a library by
> +implementing the the @code{la_objsearch()} function.
> +@findex la_objsearch

The audit interface should be covered in a separate section, IMHO.

> +If a library listed as NEEDED includes a slash in its name, then it is
> +assumed to be either an absolute or relative pathname as is often the
> +case when a library is specified on the command line. When a pathname
> +is found as the target of the NEEDED section it is resolved as such.

I think this needs some polishing, and I'm not actually sure how the
dynamic linker behaves.  Will any slash in DT_NEEDED inhibit searches
along the library path?

> +the system. Thus extensive use of @env{LD_LIBRARY_PATH} could have
> +substantial negative performance implications.

NB: Only affects load time, not run time.

> +@cindex RUNPATH
> +@cindex DT_RUNPATH
> +After processing @env{LD_LIBRARY_PATH}, an ELF directive similar to RPATH
> +called RUNPATH is searched. This ELF directive is what libtool and
> +other compile time linkers insert when linking with libraries in
> +unusual directories specified on the link command line. Any RUNPATHs
> +found in an ELF executable or library can be listed by printing the
> +dynamic section of the ELF header.

Some distros strip DT_RUNPATH or patch libtool not to add it.

> +Very occasionally RPATH and RUNPATH may include some macros that will
> +be expanded before objects search is performed in the directories
> +specified. Users are encouraged to look at the linux ld.so man page
> +for more details.

That's actualy quite widely used because OpenJDK relies on it.

> +@node Finding a Symbol
> +@subsection Finding a Symbol
> +When two objects are linked dynamically, the location of symbols which
> +are referenced in one object file which exist an an other object file
> +cannot be resolved until run time. This is because the location within
> +a process's address space where a library will be loaded is
> +intentionally slightly non-deterministic to make hacking more
> +difficult and because different applications can load the same object
> +file in different locations.

The relative locations are currently totally predictable, so this is
misleading.  The main point is that implementations can change and
shared objects can change sizes (or the length of functions), which
makes these offsets non-constant over time and require computation of
these offsets at run time.

> This is why libraries must be compiled as
> +position independent code.

Technically, this is a non sequitur.  Position-independent code
changes the relocation types used within an object, it does not
necessarily affect symbol binding directly.

>                             These unresolved symbols are known as
> +relocations. You can use the @command{readelf} command to list the
> +relocations needing to be satisfied within an object file.

You could refer back to the discussion of relocations vs symbol
binding earlier (or expand on the distinction here).

Not all relocations have associated symbols.  Undefined symbols will
be used by at least one relocation (I think, but perhaps there is a
counterexample).  Defined symbols may not have any associated
relocations at all.

> +The dynamic linker's job is to find the required symbol in the shared
> +libraries. The symbols available within an object file can be
> +enumerated with the @command{readelf --dyn-sym} command.

@samp{readelf --dyn-sym -W}, I think.

> +All of the relocations needed by the executable and all its libraries
> +will be satisfied by the objects loaded. For example two of the
> +symbols needed by the @command{ls} can be found in the
> +@file{/usr/lib64/libc.so.6} library.
> +
> +@example
> +$ readelf --relocs /usr/bin/ls | egrep stdout\|opendir
> +00000061af90  000f00000006 R_X86_64_GLOB_DAT 0000000000000000 stdout + 0
> +00000061b0e0  001e00000007 R_X86_64_JUMP_SLO 0000000000000000 opendir + 0
> +$ readelf --dyn-syms /usr/lib64/libc.so.6 | egrep " stdout| opendir"
> +  1036: 00000000003b88e8     8 OBJECT  GLOBAL DEFAULT   32 stdout@@GLIBC_2.2.5

stdout is a bit of a bad example because the executable has a
definition of the object as well, and there is a copy relocation for
it.

> +  1270: 00000000000c0350    13 FUNC    WEAK   DEFAULT   12 opendir@@GLIBC_2.2.5
> +@end example
> +
> +After the symbol is found in the object file, the reference to the
> +symbol must be patched so that the code can referring to it can make
> +use of it. This is known as binding a symbol.
> +
> +@node Binding a Variable
> +@subsection Binding a Variable
> +Binding a variable is the process of patching the location of a symbol
> +in the processes current address space into the code which refers to
> +it. There might be hundreds if not thousands of uses of a particular
> +variabletherefore patching in the location into every one of those
           ^ missing “, ”

> +uses would increase the amount of time spent in the dynamic linker
> +before main was started. Also patching the actual destination memory

“before the @code{main} function was started.”

> +address into the code of the object that refers to it would change the
> +in memory version of that object so that it could no longer be shared
> +with all the other processes using that object. The solution to these

Technically, glibc does in fact support text relocations.

> +two problems is to have indirect references to the external variables
> +and to place tables of these indirect references in a region of memory
> +not shared by users of that object. This indirection can be easily
> +seen when looking at the assembly code for a simple function. In this
> +case x86_64 is used but a similar mechanism is used for most
> +architectures.

Actually, x86-64 is way simpler than most architectures.

> +@example
> +$ cat test.c
> +extern int foo;
> +
> +int function(void) @{
> +    return foo;
> +@}
> +$ gcc -shared -fPIC -g -o libtest.so test.c
> +$ gdb libtest.so -q -ex "disassemble function" -ex quit
> +Reading symbols from libtest.so...done.
> +Dump of assembler code for function function:
> +   0x00000000000006d0 <+0>:	push   %rbp
> +   0x00000000000006d1 <+1>:	mov    %rsp,%rbp
> +   0x00000000000006d4 <+4>:	mov    0x200905(%rip),%rax        # 0x200fe0
> +   0x00000000000006db <+11>:	mov    (%rax),%eax
> +   0x00000000000006dd <+13>:	pop    %rbp
> +   0x00000000000006de <+14>:	retq
> +End of assembler dump.
> +$ readelf --relocs libtest.so | egrep dyn\|Type\|foo
> +Relocation section '.rela.dyn' at offset 0x470 contains 9 entries:
> +  Offset          Info           Type           Sym. Value    Sym. Name + Addend
> +000000200fe0  000400000006 R_X86_64_GLOB_DAT 0000000000000000 foo + 0
> +$ readelf --sections libtest.so | egrep -A1 Nr\|20\]\|Key\|order
> +  [Nr] Name              Type             Address           Offset
> +       Size              EntSize          Flags  Link  Info  Align
> +--
> +  [20] .got              PROGBITS         0000000000200fd0  00000fd0
> +       0000000000000030  0000000000000008  WA       0     0     8
> +--
> +Key to Flags:
> +  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
> +  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
> +  O (extra OS processing required) o (OS specific), p (processor specific)
> +@end example
> +
> +The address of the variable foo is located at the address 0x200905
> +past the current instruction pointer. GDB nicely computes this for you
> +to be 0x200fe0. This matches the address of the location in the
> +relocation section. When you find that address in the list of sections
> +within the ELF file you find that it is in a section called the
> +``GOT'' which stands for the global offset table. We can see from the
> +flags that this region is both wriable and dynamically allocated. At
                                  ^ “writable”
                                  
> +run time it is allocated and then then the dynamic linker inserts the
> +location of foo into 0x200fe0. This is the process known as binding a
> +symbol.

“writes the location of @code{foo} to the address 0x200fe0”

Arguably, this is relocation. 8-)  Binding the symbol is the lookups to
find the DSO that defines it and figuring out what kind of location
operation has to be used.

> +
> +@node Binding a Function
> +@subsection Binding a Function
> +
> +@cindex procedure linkage table
> +@cindex PLT
> +Binding a function is very similar to binding a variable except there
> +are a couple of other features and requirements that add a little bit
> +of additional complexity. Some of the additional complexity is due to
> +the need to make function calls between position independent code
> +which needs to be in read only memory. A couple of other important
> +features are lazy binding and the ability to audit function calls
> +between objects.

Note that many distributions have essentially removed the ability to
audit system libraries, so that tools like latrace stop working:

  https://bugzilla.redhat.com/show_bug.cgi?id=1483591

> +Like variable relocations, the requirement to have references in read
> +only memory so executable sections can be shared necessitates the use
> +of indirection. A simple approach would be to put the address to the
> +function in the GOT. However, another layer of indirection is needed
> +to support lazy binding of functions.
> +
> +The way this is accomplished is through another section of read-only
> +executable code called the Procedure Linkage Table, or PLT. The
> +executing code calls a tiny bit of stub code in the PLT. This stub
> +code jumps to the location of an associated entry in the GOT. This is
> +not a call, this is a jump and so returning the function's return
> +value and call stack is not disturbed.

There is considerable variance how PLT-like constructs are
implemented, and modern distributions do not have PLTs anymore in most
binaries on x86-64.

I am not sure if it makes sense to explain lazy binding in such detail
because it is increasingly of historical interest only.

> +After a function is bound, the entry in the GOT pointed to by the PLT
> +stub code will contain the address of the function in the process's
> +address space. Before the function is bound, usually at the time when
> +the object is loaded, the dynamic later inserts value in the GOT that
                                           ^ “stores”

Inserting implies shifting the other values around.

> +@node Linkage Tables
> +@subsection Linkage Tables
> +@findex dlopen
> +@findex dlmopen
> +Linkage tables are lists of the objects that the dynamic linker has
> +loaded into the process's address space. They are defined in
> +@file{<link.h>} and made up of the @code{link_map} structure. The
> +executable, the libraries that it needs to run, and any object files
> +that it opens with @code{dlopen} will be linked together in a doubly
> +linked list in a base link map. However, a process which opens objects
> +using @code{dlmopen} will have other link maps as well.

Isn't there a struct link_map object for each loaded object, not just
for each namespace?

I'm not sure if it is advisable to discuss these internals in such
detail.  These exports look more or less accidental or historical to
me.  Access is not thread safe, so different interfaces should be used
in general (such as dladdr, dlinfo, or __dl_iterate_phdr).

> +These @code{link_map} structures should be considered read only and
> +should not be modified. In addition to the the @code{l_next} and
> +@code{l_prev} pointers connecting the list, each @code{link_map}
> +structure has the @code{l_name} which is the name of the object
> +represented by this structure. In most cases, this value is filled in,
> +however the name of the executable object being run is not set because
> +it is loaded before the dynamic linker object @code{ld_linux} is
> +loaded.

“not set”?  Do you mean it is set as the empty string?

I think this is just the convention used to identify the main
executable.

> +@node Dynamic Linker API Functions
> +@section Dynamic Linker API Functions
> +@cindex Dynamic Linker API Functions
> +@Theglibc in conjunction with the underlying operating system provides
> +several functions which can be called from applications to load
> +linkable objects, most frequently libraries and plugins, and find the
> +addresses of symbols within them so that they can subsequently be
> +called through a function pointer. These functions are well documented
> +in their associated man pages.

See above.  Maybe we can somehow bridge the licensing gap and include
that text here for completeness.

> +These functions are all defined in @file{<dlfcn.h>} and exist in the
> +@file{libdl} library.

“Objects using these functions need to link with @code{-ldl}.”  (The
name of the dynamic linker library is implementation-defined.)

> +@section Audit Interface
> +@cindex rtld-audit
> +@cindex Audit, dynamic linking
> +
> +The dynamic linker provides an interface to monitor and intercept its
> +functioning. Since this interface was modeled after the Solaris's
> +audit interface, a good reference to it's operation is the Oracle
> +@cite{Solaris Linker and Libraries Guide}.
> +@c The linux man page for
> +@c rtld-audit(7) has a brief summary of the interface.
> +
> +@vindex LD_AUDIT
> +To run a program with an audit library, set the @env{LD_AUDIT}
> +environment variable to a colon separated list of shared libraries

(shared objects)

> +which implement any subset of the functions listed above containing

Listed below?

> +@code{la_version()} which is required to be present in all audit libraries.
> +@findex la_version
> +
> +The current implementation of the run time linker audit interface
> +currently includes the following functions.

Drop one current.

> +
> +@menu
> +* la_version:: Negotiate the version of the audit interface.
> +* la_objsearch:: Called when searching for a library.
> +* la_activity::  Called the link map is updated.
> +* la_objopen:: Called when an object file is opened.
> +* la_objclose:: Called just before the object file is unloaded.
> +* la_preinit:: Called after libraries are loaded but before main is called.
> +* la_symbind:: Called when a symbol is bound.
> +* la_pltenter:: Called when entering the PLT.
> +* la_pltexit:: Called when exiting the PLT.
> +@end menu
> +
> +@node la_version
> +@subsection la_version
> +@deftypefun unsigned int la_version(unsigned int @var{version})
> +@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{}}
> +@findex la_version
> +
> +This is the only function guaranteed to be implemented by the every
> +version of the audit interface. It is also the only function required
> +to be defined in every audit library.
> +
> +The parameter passed in, is the highest version of the audit interface
> +that the run time linker implements. An audit library should check
> +this version to make sure that the run time linker implements a
> +version of the audit interface that is compatible and sufficient for
> +its needs. The audit library should return the version of the
> +interface that it intends to use to use. While this is likely to be

s/ to use_to use/to use/

> +the same as the version passed in as a parameter, it can also be an
> +older version. This allows an older audit library to still work with a
> +newer version of the audit interface. Currently, the run time linker
> +supports all previous versions of the audit interface and it is
> +expected that it will continue to provide backward compatibility with
> +these older versions of the interface for the foreseeable future. It
> +is unlikely that this guarantee of backward compatibility will be
> +broken during the lifetime of the ELF, Executable and Linkable File,
> +file format, but if the run time linker cannot support the version of
> +the audit interface returned by the auditing library's la_version()
> +function then that audit library will be ignored. One example where
> +this might be the case is if an audit library was compiled against a
> +newer version of glibc which implemented a newer version of the

@theglibc{}

> +interface and it required those new capabilities to run properly. The
> +audit library can also choose to return zero and the run time linker
> +will then ignore that audit library.
> +
> +The current version of the audit interface implemented by the run time
> +linker is defined as LAV_CURRENT in @file{link.h}. Thus a suggested

@code{LAV_CURRENT}.

> +implementation of @code{la_version()} without the capability to run against
> +version one of the audit interface would be:

GNU style does not use () after function names, so pleae use
@code{la_version} throughout.

> +Within a run time linker audit library @code{la_obsearch()} is
> +invoked each time the run time dynamic linker is going to search for
> +an object. This function may be called multiple times during the
> +process of resolving the location of a library. Initially, the run
> +time linker passes in the name of the object found from DT_NEEDED

@code{DT_NEEDED}.  All constants need similar markup.

Sorry, have to stop here for now.