mkogg.py: Fix 'self.get_mp4_metadata(self, source)'

[blog.git] / posts / Linking.mdwn

This example shows the details of linking a simple program from three
source files.  There are three ways to link: directly from object
files, statically from static libraries, or dynamically from shared
libraries.  If you're following along in my [[example
source|linking.tar.gz]], you can compile the three flavors of the
`hello_world` program with:

    $ make

And then run them with:

    $ make run

Compiling and linking
=====================

Here's the general compilation process:

1. Write code in a human-readable language (C, C++, …).
2. Compile the code to [object files][object-files] (`*.o`) using a
   compiler (`gcc`, `g++`, …).
3. Link the code into executables or libraries using a [linker][]
   (`ld`, `gcc`, `g++`, …).

Object files are binary files containing [machine code][machine-code]
versions of the human-readable code, along with some bookkeeping
information for the linker (relocation information, stack unwinding
information, program symbols, …).  The machine code is specific to a
particular processor architecture (e.g. [x86-64][]).

Linking files resolves references to symbols defined in translation
units, because a single object file will rarely (never?) contain
definitions for all the symbols it requires.  It's easy to get
confused about the difference between compiling and linking, because
you often use the same program (e.g. `gcc`) for both steps.  In
reality, `gcc` is performing the compilation on its own, but is
using external utilities like `ld` for the linking.  To see this in
action, add the `-v` (verbose) option to your `gcc` (or `g++`)
calls.  You can do this for all the rules in the `Makefile` with:

    make CC="gcc -v" CXX="g++ -v"

On my system, that shows `g++` using `/lib64/ld-linux-x86-64.so.2`
for dynamic linking.  On my system, C++ seems to require at least some
dynamic linkning, but a simple C program like `simple.c` can be
linked statically.  For static linking, `gcc` uses `collect2`.

Symbols in object files
=======================

Sometimes you'll want to take a look at the symbols exported and
imported by your code, since there can be [subtle bugs][bugs] if you
link two sets of code that use the same symbol for different purposes.
You can use `nm` to inspect the intermediate object files.  I've saved
the command line in the `Makefile`:

    $ make inspect-object-files
    nm -Pg hello_world.o print_hello_world.o hello_world_string.o
    hello_world.o:
    _Z17print_hello_worldv U         
    main T 0000000000000000 0000000000000010
    print_hello_world.o:
    _Z17print_hello_worldv T 0000000000000000 0000000000000027
    _ZNSolsEPFRSoS_E U         
    _ZNSt8ios_base4InitC1Ev U         
    _ZNSt8ios_base4InitD1Ev U         
    _ZSt4cout U         
    _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ U         
    _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc U         
    __cxa_atexit U         
    __dso_handle U         
    hello_world_string U         
    hello_world_string.o:
    hello_world_string R 0000000000000010 0000000000000008

The output format for `nm` is described in its man page.  With the
`-g` option, output is restricted to globally visible symbols.  With
the `-P` option, each symbol line is:

    <symbol> <type> <offset-in-hex> <size-in-hex>

For example, we see that `hello_world.o` defines a global text
symbol `main` with at position 0 with a size of 0x10.  This is where
the loader will start execution.

We also see that `hello_world.o` needs (i.e. “has an undefineed symbol
for”) `_Z17print_hello_worldv`.  This means that, in order to run,
`hello_world.o` must be linked against something else which provides
that symbol.  The symbol is for our `print_hello_world` function.  The
`_Z17` prefix and `v` postfix are a result of [name
mangling][mangling], and depend on the compiler used and function
signature.  Moving on, we see that `print_hello_world.o` defines the
`_Z17print_hello_worldv` at position 0 with a size of 0x27.  So
linking `print_hello_world.o` with `hello_world.o` would resolve the
symbols needed by `hello_world.o`.

`print hello_world.o` has undefined symbols of its own, so we can't
stop yet.  It needs `hello_world_string` (provided by
`hello_world_string.o`), `_ZSt4cout` (provided by `libcstd++`),
….

The process of linking involves bundling up enough of these partial
code chunks so that each of them has access to the symbols it needs.

There are a number of other tools that will let you poke into the
innards of object files.  If `nm` doesn't scratch your itch, you may
want to look at the more general `objdump`.

Storage classes
===============

In the previous section I mentioned “globally visible symbols”.  When
you declare or define a symbol (variable, function, …), you can use
[storage classes][storage-classes] to tell the compiler about your
symbols' *linkage* and *storage duration*.

For more details, you can read through *§6.2.2 Linkages of
identifiers*, *§6.2.4 Storage durations of objects*, and *§6.7.1
Storage-class specifiers* in [WG14/N1570][N1570], the last public
version of [ISO/IEC 9899:2011][9899] (i.e. the C11 standard).

Since we're just worried about linking, I'll leave the discussion of
storage duration to others.  With linkage, you're basically deciding
which of the symbols you define in your translation unit should be
visible from other translation units.  For example, in
`print_hello_world.h`, we declare that there is a function
`print_hello_world` (with a particular signature).  The `extern`
means that may be defined in another translation unit.  For
block-level symbols (i.e. things defined in the root level of your
source file, not inside functions and the like), this is the default;
writing `extern` just makes it explicit.  When we define the
function in `print_hello_world.cpp`, we also label it as `extern`
(again, this is the default).  This means that the defined symbol
should be exported for use by other translation units.

By way of comparison, the string `secret_string` defined in
`hello_world_string.cpp` is declared `static`.  This means that
the symbol should be restricted to that translation unit.  In other
words, you won't be able to access the value of `secret_string` from
`print_hello_world.cpp`.

When you're writing a library, it is best to make any functions that
you don't *need* to export `static` and to [avoid global variables
altogether][global].

Static libraries
================

You never want to code *everything* required by a program on your own.
Because of this, people package related groups of functions into
libraries.  Programs can then take use functions from the library, and
avoid coding that functionality themselves.  For example, you could
consider `print_hello_world.o` and `hello_world_string.o` to be
little libraries used by `hello_world.o`.  Because the two object
files are so tightly linked, it would be convenient to bundle them
together in a single file.  This is what static libraries are, bundles
of object files.  You can create them using `ar` (from “archive”;
`ar` is the ancestor of `tar`, from “tape archive”).

You can use `nm` to list the symbols for static libraries exactly as
you would for object files:

    $ make inspect-static-library
    nm -Pg libhello_world.a
    libhello_world.a[print_hello_world.o]:
    _Z17print_hello_worldv T 0000000000000000 0000000000000027
    _ZNSolsEPFRSoS_E U         
    _ZNSt8ios_base4InitC1Ev U         
    _ZNSt8ios_base4InitD1Ev U         
    _ZSt4cout U         
    _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ U         
    _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc U         
    __cxa_atexit U         
    __dso_handle U         
    hello_world_string U         
    libhello_world.a[hello_world_string.o]:
    hello_world_string R 0000000000000010 0000000000000008

Notice that nothing has changed from the object file output, except
that object file names like `print_hello_world.o` have been replaced
by `libhello_world.a[print_hello_world.o]`.

Shared libraries
================

Library code from static libraries (and object files) is built into
your executable at link time.  This means that when the library is
updated in the future (bug fixes, extended functionality, …), you'll
have to relink your program to take advantage of the new features.
Because no body wants to recompile an entire system when someone makes
`cout` a bit more efficient, people developed shared libraries.  The
code from shared libraries is never built into your executable.
Instead, instructions on how to find the dynamic libraries are built
in.  When you run your executable, a loader finds all the shared
libraries your program needs and copies the parts you need from the
libraries into your program's memory.  This means that when a system
programmer improves `cout`, your program will use the new version
automatically.  This is a Good Thing™.

You can use `ldd` to list the shared libraries your program needs:

    $ make list-executable-shared-libraries
    ldd hello_world
            linux-vdso.so.1 =>  (0x00007fff76fbb000)
            libstdc++.so.6 => /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/libstdc++.so.6 (0x00007ff7467d8000)
            libm.so.6 => /lib64/libm.so.6 (0x00007ff746555000)
            libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007ff74633e000)
            libc.so.6 => /lib64/libc.so.6 (0x00007ff745fb2000)
            /lib64/ld-linux-x86-64.so.2 (0x00007ff746ae7000)

The format is:

    soname => path (load address)

You can also use `nm` to list symbols for shared libraries:

    $ make inspect-shared-libary | head
    nm -Pg --dynamic libhello_world.so
    _Jv_RegisterClasses w         
    _Z17print_hello_worldv T 000000000000098c 0000000000000034
    _ZNSolsEPFRSoS_E U         
    _ZNSt8ios_base4InitC1Ev U         
    _ZNSt8ios_base4InitD1Ev U         
    _ZSt4cout U         
    _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ U         
    _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc U         
    __bss_start A 0000000000201030 
    __cxa_atexit U         
    __cxa_finalize w         
    __gmon_start__ w         
    _edata A 0000000000201030 
    _end A 0000000000201048 
    _fini T 0000000000000a58 
    _init T 0000000000000810 
    hello_world_string D 0000000000200dc8 0000000000000008

You can see our `hello_world_string` and `_Z17print_hello_worldv`,
along with the undefined symbols like `_ZSt4cout` that our code
needs.  There are also a number of symbols to help with the shared
library mechanics (e.g. `_init`).

To illustrate the “link time” vs. “load time” distinction, run:

    $ make run
    ./hello_world
    Hello, World!
    ./hello_world-static
    Hello, World!
    LD_LIBRARY_PATH=. ./hello_world-dynamic
    Hello, World!

Then switch to the `Goodbye` definition in
`hello_world_string.cpp`:

    //extern const char * const hello_world_string = "Hello, World!";
    extern const char * const hello_world_string = "Goodbye!";

Recompile the libraries (but not the executables) and run again:

    $ make libs
    …
    $ make run
    ./hello_world
    Hello, World!
    ./hello_world-static
    Hello, World!
    LD_LIBRARY_PATH=. ./hello_world-dynamic
    Goodbye!

Finally, relink the executables and run again:

    $ make
    …
    $ make run
    ./hello_world
    Goodbye!
    ./hello_world-static
    Goodbye!
    LD_LIBRARY_PATH=. ./hello_world-dynamic
    Goodbye!

When you have many packages depending on the same low-level libraries,
the savings on avoided rebuilding is large.  However, shared libraries
have another benefit over static libraries: shared memory.

Much of the machine code in shared libraries is static (i.e. it
doesn't change as a program is run).  Because of this, several
programs may share the same in-memory version of a library without
stepping on each others toes.  With statically linked code, each
program has its own in-memory version:

<table class="center" style="border-spacing: 40px 0px">
        <thead>
                <tr><th>Static</th><th>Shared</th></tr>
        </thead>
        <tbody>
                <tr><td>Program A → Library B</td><td>Program A → Library B</td></tr>
                <tr><td>Program C → Library B</td><td>Program C ⎯⎯⎯⎯⬏</td></tr>
        </tbody>
</table>

<!--
        Unicode characters used in above figure:
        U2192 RIGHTWARDS ARROW
        U23AF HORIZONTAL LINE EXTENSION
        U2B0F RIGHTWARDS ARROW WITH TIP UPWARDS
        -->

Further reading
===============

If you're curious about the details on loading and shared libraries,
[Eli Bendersky][EB] has a nice series of articles on [load time
relocation][relocation], [PIC on x86][PIC-x86], and [PIC on
x86-64][PIC-x86-64].

[object-files]: http://en.wikipedia.org/wiki/Object_file
[linker]: http://en.wikipedia.org/wiki/Linker_%28computing%29
[machine-code]: http://en.wikipedia.org/wiki/Instruction_set_architecture
[x86-64]: http://en.wikipedia.org/wiki/X86-64
[collect2]: http://gcc.gnu.org/onlinedocs/gccint/Collect2.html
[bugs]:
  http://blog.flameeyes.eu/2008/02/09/flex-and-linking-conflicts-or-a-possible-reason-why-php-and-recode-are-so-crashy
[mangling]: http://en.wikipedia.org/wiki/Name_mangling
[storage-classes]:
  http://ee.hawaii.edu/~tep/EE160/Book/chap14/section2.1.1.html
[N1570]: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
[9899]: http://www.open-std.org/jtc1/sc22/wg14/
[global]: http://c2.com/cgi/wiki?GlobalVariablesAreBad
<!--
        Wulf and Shaw, Global variable considered harmful
        http://dx.doi.org/10.1145%2F953353.953355
        -->
[EB]: http://eli.thegreenplace.net/
[relocation]:
  http://eli.thegreenplace.net/2011/08/25/load-time-relocation-of-shared-libraries/
[PIC-x86]:
  http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/
[PIC-x86-64]:
  http://eli.thegreenplace.net/2011/11/11/position-independent-code-pic-in-shared-libraries-on-x64/

[[!tag tags/C]]
[[!tag tags/linux]]