How Does C++ Linking Work in Practice

How exactly does linking work?

At this point you have an executable.

No. At this point, you have object files, which are not, in themselves, executable.

But if you actually run that executable what happens?

Something like this:

h2co3-macbook:~ h2co3$ clang -Wall -o quirk.o quirk.c -c
h2co3-macbook:~ h2co3$ chmod +x quirk.o
h2co3-macbook:~ h2co3$ ./quirk.o
-bash: ./quirk.o: Malformed Mach-o file

I told you it was not an executable.

Is the problem that you may have included *.h files, and those only contain function prototypes?

Pretty close, actually. A translation unit (.c file) is (generally) transformed to assembly/machine code that represents what it does. If it calls a function, then there will be a reference to that function in the file, but no definition.

So if you actually call one of the functions from those files, it won't have a definition and your program will crash?

As I've stated, it won't even run. Let me repeat: an object file is not executable.

what exactly does linking do, under the hood? How does it find the .c file associated with the .h that you included [...]

It doesn't. It looks for other object files generated from .c files, and eventually libraries (which are essentially just collections of other object files).

And it finds them because you tell it what to look for. Assuming you have a project which consists of two .c files which call each other's functions, this won't work:

gcc -c file1.c -o file1.o
gcc -c file2.c -o file2.o
gcc -o my_prog file1.o

It will fail with a linker error: the linker won't find the definition of the functions implemented in file2.c (and file2.o). But this will work:

gcc -c file1.c -o file1.o
gcc -c file2.c -o file2.o
gcc -o my_prog file1.o file2.o

[...] and how does it inject that into your machine code?

Object files contain stub references (usually in the form of function entry point addresses or explicit, human-readable names) to the functions they call. Then, the linker looks at each library and object file, finds the references (, throws an error if a function definition couldn't be found), then substitutes the stub references with actual "call this function" machine code instructions. (Yes, this is largely simplified, but without you asking about a specific architecture and a specific compiler/linker, it's hard to tell more precisely...)

Is static when you actually recompile the source of the library for every executable you create?

No. Static linkage means that the machine code of the object files of a library are actually copied/merged into your final executable. Dynamic linkage means that a library is loaded into memory once, then the aforementioned stub function references are resolved by the operating system when your executable is launched. No machine code from the library will be copied into your final executable. (So here, the linker in the toolchain only does part of the job.)

The following may help you to achieve enlightenment: if you statically link an executable, it will be self-contained. It will run anywhere (on a compatible architecture anyway). If you link it dynamically, it will only run on a machine if that particular machine has all the libraries installed that the program references.

So you compile one executable library that is shared by all of your processes that use it? How is that possible, exactly? Wouldn't it be outside of the address space of the processes trying to access it?

The dynamic linker/loader component of the OS takes care all of that.

Also, for dynamic linking, don't you still need to compile the library at some juncture in time?

As I've already mentioned: yes, it is already compiled. Then it is loaded at some point (typically when it's first used) into memory.

When is it compiled?

Some time before it could be used. Typically, a library is compiled, then installed to a location on your system so that the OS and the compiler/linker know about its existence, then you can start compiling (um, linking) programs that use that library. Not earlier.

How does the compilation/linking process work?

The compilation of a C++ program involves three steps:

Preprocessing: the preprocessor takes a C++ source code file and deals with the #includes, #defines and other preprocessor directives. The output of this step is a "pure" C++ file without pre-processor directives.
Compilation: the compiler takes the pre-processor's output and produces an object file from it.
Linking: the linker takes the object files produced by the compiler and produces either a library or an executable file.

Preprocessing

The preprocessor handles the preprocessor directives, like #include and #define. It is agnostic of the syntax of C++, which is why it must be used with care.

It works on one C++ source file at a time by replacing #include directives with the content of the respective files (which is usually just declarations), doing replacement of macros (#define), and selecting different portions of text depending of #if, #ifdef and #ifndef directives.

The preprocessor works on a stream of preprocessing tokens. Macro substitution is defined as replacing tokens with other tokens (the operator ## enables merging two tokens when it makes sense).

After all this, the preprocessor produces a single output that is a stream of tokens resulting from the transformations described above. It also adds some special markers that tell the compiler where each line came from so that it can use those to produce sensible error messages.

Some errors can be produced at this stage with clever use of the #if and #error directives.

Compilation

The compilation step is performed on each output of the preprocessor. The compiler parses the pure C++ source code (now without any preprocessor directives) and converts it into assembly code. Then invokes underlying back-end(assembler in toolchain) that assembles that code into machine code producing actual binary file in some format(ELF, COFF, a.out, ...). This object file contains the compiled code (in binary form) of the symbols defined in the input. Symbols in object files are referred to by name.

Object files can refer to symbols that are not defined. This is the case when you use a declaration, and don't provide a definition for it. The compiler doesn't mind this, and will happily produce the object file as long as the source code is well-formed.

Compilers usually let you stop compilation at this point. This is very useful because with it you can compile each source code file separately. The advantage this provides is that you don't need to recompile everything if you only change a single file.

The produced object files can be put in special archives called static libraries, for easier reusing later on.

It's at this stage that "regular" compiler errors, like syntax errors or failed overload resolution errors, are reported.

Linking

The linker is what produces the final compilation output from the object files the compiler produced. This output can be either a shared (or dynamic) library (and while the name is similar, they haven't got much in common with static libraries mentioned earlier) or an executable.

It links all the object files by replacing the references to undefined symbols with the correct addresses. Each of these symbols can be defined in other object files or in libraries. If they are defined in libraries other than the standard library, you need to tell the linker about them.

At this stage the most common errors are missing definitions or duplicate definitions. The former means that either the definitions don't exist (i.e. they are not written), or that the object files or libraries where they reside were not given to the linker. The latter is obvious: the same symbol was defined in two different object files or libraries.

What do linkers do?

To understand linkers, it helps to first understand what happens "under the hood" when you convert a source file (such as a C or C++ file) into an executable file (an executable file is a file that can be executed on your machine or someone else's machine running the same machine architecture).

Under the hood, when a program is compiled, the compiler converts the source file into object byte code. This byte code (sometimes called object code) is mnemonic instructions that only your computer architecture understands. Traditionally, these files have an .OBJ extension.

After the object file is created, the linker comes into play. More often than not, a real program that does anything useful will need to reference other files. In C, for example, a simple program to print your name to the screen would consist of:

printf("Hello Kristina!\n");

When the compiler compiled your program into an obj file, it simply puts a reference to the printf function. The linker resolves this reference. Most programming languages have a standard library of routines to cover the basic stuff expected from that language. The linker links your OBJ file with this standard library. The linker can also link your OBJ file with other OBJ files. You can create other OBJ files that have functions that can be called by another OBJ file. The linker works almost like a word processor's copy and paste. It "copies" out all the necessary functions that your program references and creates a single executable. Sometimes other libraries that are copied out are dependent on yet other OBJ or library files. Sometimes a linker has to get pretty recursive to do its job.

Note that not all operating systems create a single executable. Windows, for example, uses DLLs that keep all these functions together in a single file. This reduces the size of your executable, but makes your executable dependent on these specific DLLs. DOS used to use things called Overlays (.OVL files). This had many purposes, but one was to keep commonly used functions together in 1 file (another purpose it served, in case you're wondering, was to be able to fit large programs into memory. DOS has a limitation in memory and overlays could be "unloaded" from memory and other overlays could be "loaded" on top of that memory, hence the name, "overlays"). Linux has shared libraries, which is basically the same idea as DLLs (hard core Linux guys I know would tell me there are MANY BIG differences).

Hope this helps you understand!

What every C++ developer should know about linking

There are TONS of resources.

I guess that might be overwhelming for a "beginner" ;)

As far as "Windows", you could do worse than to start here:

Windows Architecture Overview
Beginner's Guide to Linkers

I'd also recommend this:

Programming from the Ground Up

'Hope that helps :)

PS:

As clarification:

You want to know how the bits you've "compiled" (into machine code) all come together by "linking". A totally fair question :)
It also helps to know a bit about how that machine code relates to a "running program"...
... and how a "running program" uses some bits from the (static) .exe, and other bits from the dynamic runtime (.dll's, or "dynamically linked libraries).
All of these details are often completely platform- and OS-specific
Hence the (varied) links.

Again, I hope all that helps with your initial question.

Unclear on linking vs compilation

Preprocessing happens before compilation. The preprocessor takes a one or more source files, and outputs another source file, which is then compiled. The preprocessor is a text-to-text transformer, it has nothing to do with linking.

It is conceptually possible to dump everything in one source file using a preprocessor, and then compile it directly to an executable, skipping the stages of producing object files and linking them together. However this would be extremely inconvenient in practice. Imagine a 100,000,000 lines of code program (this includes all the standard library and all the platform libraries and all the third-party libraries). You need to change one line. Would you be willing to compile all 100,000,000 lines again? and when you make an error in that one line, do it again (and again and again and again and again)?

Some libraries are distributed entirely as header files. They do not need any binary files, and are compiled with your program every time the program is compiled. But not all libraries are like that. Some are too big to be compiled every time. Some are not written in C or C++ (they require bits of assembly language for example, or perhaps Fortran). Some cannot be distributed as source code because the vendors are unwilling to do so for copyright reasons. In all these cases, the solution is to compile the libraries to object files, and then distribute these object files together with headers that contain just interfaces (declarations with no definitions) of functions and variables they expose.

<iostream> that you mention is a mixed bag. In most implementations it contains both function definitions (templates and small inline functions) that you compile every time when your program is compiled, and declarations of external functions, whose definitions are compiled by the vendor and distributed as a precompiled library.

C/C++ How Does Dynamic Linking Work On Different Platforms?

To answer your questions one by one:

Dynamic linking defers part of the linking process to runtime.
It can be used in two ways: implicitly and explicitly.
Implicitly, the static linker will insert information into the
executable which will cause the library to load and resolve the
necessary symbols. Explicitly, you must call LoadLibrary or
dlopen manually, and then GetProcAddress/dlsym for each
symbol you need to use. Implicit loading is used for things
like the system library, where the implementation will depend on
the version of the system, but the interface is guaranteed.
Explicit loading is used for things like plug-ins, where the
library to be loaded will be determined at runtime.
The .lib file is only necessary for implicit loading. It
contains the information that the library actually provides this
symbol, so the linker won't complain that the symbol is
undefined, and it tells the linker in what library the symbols
are located, so it can insert the necessary information to cause
this library to automatically be loaded. All the header files
tell the compiler is that the symbols will exist, somewhere; the
linker needs the .lib to know where.
Under Unix, all of the information is extracted from the
.so. Why Windows requires two separate files, rather than
putting all of the information in one file, I don't know; it's
actually duplicating most of the information, since the
information needed in the .lib is also needed in the .dll.
(Perhaps licensing issues. You can distribute your program with
the .dll, but no one can link against the libraries unless
they have a .lib.)

The main thing to retain is that if you want implicit loading,
you have to provide the linker with the appropriate information,
either with a .lib or a .so file, so that it can insert that
information into the executable. And that if you want explicit
loading, you can't refer to any of the symbols in the library
directly; you have to call GetProcAddress/dlsym to get their
addresses yourself (and do some funny casting to use them).