[linker] linker of choice

 

Reference:
https://lld.llvm.org/#using-lld

$ clang++ -fuse-ld=lld

[C++] key function

Reference:
undefined reference to vtable for X
What is a C++ "Key Function" as described by gold?

Every polymorphic class requires a virtual table or vtable describing the type and its virtual functions. Whenever possible the vtable will only be generated and output in a single object file rather than generating the vtable in every object file which refers to the class (which might be hundreds of objects that include a header but don't actually use the class.)

The cross-platform C++ ABI states that the vtable will be output in the object file that contains the definition of the key function, which is defined as the first non-inline, non-pure, virtual function declared in the class.

If you do not provide a definition for the key function (or fail to link to the file providing the definition) then the linker will not be able to find the class' vtable.

class X {
public:
  virtual ~X() = 0;
  void f();
  virtual void g() { }
  virtual void h(); // defined inline out side of class.
  virtual void i(); // <-- Key fuction.
  virtual void j();
};

inline void X::h() { }

reproduce the error:

#include <iostream>

class Base {
public:
    virtual void foo() = 0; // Pure virtual function
};

class Derived : public Base {
public:
    void foo() override; // Declaring but not defining foo()
};

int main() {
    Derived d; // This will cause a linker error due to missing vtable
    return 0;
}

[elf][note] entry function

ELF executable entry function

_start function facts

• supplied by libc
• written in assembly
• store in a file called crt0.s
• Compilers typically ship with pre-compiled crt0.o object files for each supported architecture.
  https://wiki.osdev.org/Creating_a_C_Library

_start function implements

1. Early low-level initialization, such as
1. Configuring processor registers
2. Initializing external memory
3. Enabling caches
4. Configuring the MMU
2. Stack initialization, making sure that the stack is properly aligned per the ABI requirements
3. Frame pointer initialization
4. Initialization of the C/C++ runtime
   Relocate any relocatable sections (if not handled by the loader or linker)
1. Initializing global and static memory
2. Runtime initializes a subset of uninitialized memory (no = in the declaration) to 0.
   This includes global and static variables, but not stack variables. All uninitialized data that needs to be set to 0 is placed into the .bss section of the compiled program image by the linker. The location of the .bss section is identified during initialization, and the memory is typically set to 0 with memset.
3. C++ global objects must be constructed before calling main. The linker places these constructors into the .init, .init_array, or .ctors section of the image.
   Some compilers also allow C and C++ functions to be marked as a constructor using a compiler attribute (e.g., __attribute__((constuctor))). The constructors are stored in a list by the linker.
   The runtime initialization process iterates through the list and calls each constructor.
4. Prepare the argc and argv variables for invoking main (even if it’s just setting these to 0/NULL)
5. Perform any additional setup steps required by the C/C++ standard library implementation.
   These additional runtime initialization steps are run for many programs (but not all):
1. Heap initialization
2. Initialize stdio (i.e., stdin, stdout, stderr)
3. Initialize exception support (if using C++)
4. Register destructors and other cleanup functions that will run when exiting the program (using atexit and __cxa_atexit)
5. Assembly files commonly found during this portion of the startup process are crtbegin.s, crtend.s, crti.s, and crtn.s.
6. Prepare environment variables
5. Initialization of other scaffolding required by the system
     Program scaffolding setup before main might include:
1. Threading support and thread local storage
2. Buffer overrun detection
3. Stack logging
4. Run-time error checks
5. Locale settings
6. Math error handling
7. Default math library precision
6. Jumping to main
7. Exiting the program with the return code from main

So, how do we get to the _start?

• Baremetal: Reset Vector
• Bootloader Launches Application
• OS Calls an exec function
  Loaders will often perform the following actions:
• Check permissions
• Allocate space for the program’s stack
• Allocate space for the program’s heap
• Initialize registers (e.g., stack pointer)
• Push argc, argv, and envp onto the program stack
• Map virtual address spaces
• Dynamic linking
• Relocations
• Call pre-initialization functions

[split stack] reading notes and references

Reference:
gccgo split stack implementation

1. The stack can start splitting at any point.
2. The stack size is automatically recorded at program startup,
   and each thread startup.
3. The gold linker detects calls from split-stack code to non-split-stack
   code, and rewrites the function header to force a large stack segment to be allocated.
   i.e.
   When not using the gold linker, calls from split-stack code to non-split-stack code will just have whatever is left of the current stack segment, which may not be large enough.
   (look up to "Backward compatibility" section)

In the complex GCC ecosystem the linker is separate from the compiler.
GCC can't assume that gold is available at all.
When building gccgo, configure using
--with-ld=/path/to/gold

The -fuse-ld=gold option is newer than gccgo.
Ian supposes it would be nice if:
* the GCC configure process checks whether -fuse-ld=gold works; if so:
  * -fuse-ld=gold is passed to the libgo configure/build
  * -fuse-ld=gold is used by default by the gccgo driver program



Reference:
Split Stacks in GCC

• Split stacks permits a dis-contiguous stack which is grown automatically as needed. 
• This means that when running multiple threads, each starting with a small stack, and have the stack grow and shrink as required by the program.
• In Golang, each init. GoRoutine sized in 2kB, code reference:
  https://github.com/golang/go/blob/0098f8aeaceb5feec7462ae64f8ce91a473360c1/src/runtime/stack.go#L71

Obvious benefits

• The memory usage of a typical multi-threaded program can decrease significantly, as each thread does not require a worst-case stack size.
• It becomes possible to run millions of threads
  (either full NPTL threads or co-routines) in a 32-bit address space.

Basic explained

Stack will have a guaranteed zone which is always available.
Reference:
[LWN] Preventing stack guard-page hopping


The size of the guard area will be target specific.
It will include enough stack space to actually allocate more stack space.
Each function will have to verify that it has enough space in the current stack to execute.

The basic verification will be a comparison between the stack pointer and the current bottom of the stack plus the guaranteed zone size.
This will have to be the first operation in the function, and will also be target specific.

It must be fast, as it will be executed by each called function.

Two cases to consider.

1. For functions which require a stack frame less than the size of the guaranteed guard area, we can do a simple comparison between the stack pointer and the stack limit.
2. For functions which require a larger stack frame, we must do a comparison including the size of the stack frame.

Design options

1. Reserve a register to hold the bottom of the stack plus the guaranteed size. This will have to be a callee-saved register.
2. Use a TLS(Thread Local Storage) variable. In the general case, in a shared library, this will require calling the __tls_get_addr function.
   Reference:
   How fast is thread local variable access on Linux
   (GOLD elf linker)
   http://gittup.org/cgi-bin/man/man2html?gold+1 
   
   That means that that function will have to work without requiring any additional stack space.
   This is infeasible unless the whole system is compiled with split stacks.
   It would require dlopen's LD_BIND_NOW to be set, so that the __tls_get_addr function is resolved at program startup time.
   Even that is probably insufficient unless we can ensure that the space for the (TLS) variable is fully allocated.
   In general Ian doesn't think they can ensure this, because dlopen can cause a thread to require more space for TLS variables, and that space will be allocated on the first call to __tls_get_addr.
   Reference:
   http://man7.org/linux/man-pages/man8/ld.so.8.html
   LD_BIND_NOW (since glibc 2.1.1)
   If set to a nonempty string, causes the dynamic linker to
   resolve all symbols at program startup instead of deferring
   function call resolution to the point when they are first
   referenced.  This is useful when using a debugger.
3. Have the stack always end at a N-bit boundary.
   E.g., if we always allocate stack segments as a multiple of 4K,
   then align each one so that the stack always ends at a 12-bit boundary.
   Then the amount of space remaining on the stack is SP & 0xfff.
4. Introduce a new function call which handles the comparison of the stack pointer and the stack expansion.
5. Reuse the stack protector support field.
   When using glibc each thread descriptor has a field used by the stack protector.
   Of course it is then not possible to use split stacks in conjunction with stack protector.
6. At least on x86, arrange to allocate a new field in the TCB(thread control block) header accessible via %fs or %gs.
   This is probably the best solution, and it is the one implemented for i386 and x86_64.

Reference:
TCB Thread Control Block in linux kernel:
https://en.wikipedia.org/wiki/Thread_control_block

Expanding the stack

• Expanding the stack requires allocating additional memory.
• This additional memory will have to be allocated using only the stack space slot.
• All of the functions used to allocate additional stack space must be compiled to not use a split stack.
• A new function attribute, no_split_stack will be introduced to mean that the stack should not be split.
• It would also work to ensure that the stack is large enough that they do not need to split the stack during the allocation call.
• After expanding the stack, the function will copy any stack based parameters from the old stack to the new stack.
• Fortunately, all C++ objects which require a copy or move constructor are implicitly passed by reference,so copying the parameters on the stack is OK.
• For varargs functions, this is impossible in general, so we will compile varargs functions differently:
  they will use an argument pointer which is not necessarily based on the frame pointer.
  For functions which return objects on the stack, the objects will be returned on the old stack. (RVO)
  This should normally happen automatically, as the initial hidden parameter will naturally point to the old stack.
• When expanding the stack, the return address of the function will be managed to point to a function which will release the allocated stack block and reset the stack pointer to the caller.
  Reference:
  http://vsdmars.blogspot.com/2017/11/assembly-note.html
• The address of the old stack block, and the old stack pointer, will have been saved somewhere in the new stack block.

Backward compatibility

We want to be able to use split stack programs on systems with pre-built libraries compiled without split stacks.
This means that we need to ensure that there is sufficient stack space before calling any such function.

Each object file compiled in split stack mode will be annotated to indicate that the functions use split stacks.

This should probably be annotated with a note but there is no general support for creating arbitrary notes in GNU as.

Therefore, each object file compiled in split stack mode will have an empty section with a special name: .note.GNU-split-stack

If an object file compiled in split stack mode includes some functions with the no_split_stack attribute, then the object file will also have a .note.GNU-no-split-stack section.

This will tell the linker that some functions may not have the expected split stack prologue.

When the linker links an executable or shared library, it will look for calls from split-stack code to non-split-stack code.

This will include calls to non-split-stack shared libraries
(thus, a program linked against a split-stack shared library may fail if at runtime the dynamic linker finds a non-split-stack shared library;
it might be desirable to use a new segment type to detect this situation).

For calls from split-stack code to non-split-stack code, the linker will change the initial instructions in the split-stack (caller) function.
This means that the linker will have to have special knowledge of the instructions that the compiler emits.
The effect of the changes will be to increase the required frame-size by a number large enough to reasonably work for a non-split-stack.
This will be a target dependent number; the default will be something like 64K.
Note that this large stack will be released when the split-stack function returns.
Note that I'm disregarding the case of split-stack code in a shared library calling non-split-stack code in the main executable; that seems like an unlikely problem.


Function pointers are a tricky case.
In general we don't know whether a function pointer points to split-stack code.
Therefore, all calls through a function pointer will be modified to call (or jump to) a special function __fnptr_morestack.
This will use a target specific function calling sequence, and will be implemented as though it were itself a function call instruction.
That is, all the parameters will be set up, and then the code will jump to __fnptr_morestack.
The __fnptr_morestack function takes two parameters: the function pointer to call, and the number of bytes of arguments pushed on the stack.

[linker] Linker Namespaces (glibc >= 2.3.4)

Reference:
Linker Namespaces design https://sourceware.org/glibc/wiki/LinkerNamespaces
dlmopen source code https://github.com/bminor/glibc/blob/7628a1b05adb1e4c6857b87c6f8b71a1d0b1d72c/dlfcn/dlmopen.c
Unresolved symbol with only dlmopen https://stackoverflow.com/a/33612509/3850881
glibc version list: https://sourceware.org/glibc/wiki/Glibc%20Timeline


API:
dlinfo http://man7.org/linux/man-pages/man3/dlinfo.3.html
dlmopen http://man7.org/linux/man-pages/man3/dlmopen.3.html
rtld-audit http://man7.org/linux/man-pages/man7/rtld-audit.7.html


Books:
John R. Levine's Linkers and Loaders https://www.iecc.com/linker/
Notes from Milan Stevanovic's Advanced C and C++ Compiling http://vsdmars.blogspot.com/2015/09/linking-notes.html

[Go] Execution modes

Reference:

Go Execution Modes - Ian Lance Taylor  https://goo.gl/mrzwCz
https://golang.org/cmd/link/
https://golang.org/cmd/go/#hdr-Build_modes
https://golang.org/cmd/go/#hdr-Compile_packages_and_dependencies
https://github.com/golang/go/issues/18246
https://blog.ksub.org/bytes/2017/02/12/exploring-shared-objects-in-go/

Legacy Go(v1.4.0) support 3 execution modes:

1. A statically linked Go binary.
   Default for program does not import the net or os/user packages and does not use cgo or SWIG.
2. A dynamically linked Go binary.
   Default for program imports the net or os/user packages and does not otherwise use cgo or SWIG
3. A Go binary linked with arbitrary non-Go code.
   Default for program uses cgo or SWIG.
   The interface between Go and non-Go code is a C style API
   (SWIG permits calling between C++ and Go, but this is implemented using a C style API).
   Can be selected with -ldflags -linkmode=external. (obsolete)

API styles

1. Go
2. C, i.e extern "C"

Design in mind

• Go code that is combined into a single executable image must be built with the same version of the Go toolchain.
• We require further that if any Go package appears more than once in the executable image,
  it must be built from the same source code. (Same as C++'s header file)
• This restriction comes from both ways: Golang <-> C

Go runtime:

• All Go code shares a single runtime. 
• All Go code uses the same memory allocator.
• The same goroutine scheduler.
• In general acts as though it were linked into a single Go program.

New execution modes:

• Go code linked into, and called from, a non-Go program. (Go v.1.5.0)
  Go code acts as a library that may be called by a non-Go program.
  A single Go library will be an archive, a .a file on Unix,
  or as a shared library, a .so file on Unix, providing a C style API.
  This mode supports people who must work with large existing programs, especially in C/C++.
  It permits them to extend those existing programs with new packages written in Go.
  i.e the binary code is sheer an ELF format.
• Go code linked into a shared library loaded as a plugin by a program (Go or non-Go) that supports a C style plugin API. (Go v1.6.0)
  i.e dlopen/dlmopen (dlmopen appears in glibc 2.3.4 for linker's namespace)
  https://sourceware.org/glibc/wiki/LinkerNamespaces
  Golang binary code in .so ELF format can be dlopened by C/C++.
• Go code linked into a shared library loaded as a plugin by a Go program that supports a general Go style plugin API.
  A shared library can be dlopened by Golang.
  https://golang.org/pkg/plugin/
• A Go program that uses a plugin interface, either C style or Go style, where plugins are implemented as shared libraries.
  Golang can dlopen any C/C++ .so libraries.
• Building a Go package, or collection of packages, as a shared library that may be linked into a Go program. (Go v1.6.0)
  Single/Multiple Golang packages build into single shared library, which can be linked to other Golang program.
  Updating the Go run-time to a new version requires rebuilding all Go programs that use it.
• A Go program built as a PIE--a Position Independent Executable. (Go v1.6.0)
  Go program is built as usual, but the resulting executable is position-independent, and may be relocated at run time.
  (i.e -fPIC in C/C++)

Go tool flags:

• -buildmode

archive:
Default build mode for a package that is not main.
Builds the package into a .a file.

c-archive: (Go v1.5.0)
Requires a main package, but the main function is ignored (init functions are run as usual).
Build the main package, plus all packages that it imports, into a single C archive file.
The only callable symbols will be those functions marked as exported.

shared: (Go v1.6.0)
Combine all the listed packages into a single shared library that will be used when building with the -linkshared option.

c-shared: (Go v1.6.0)
Requires a main package as for -buildmode=c-archive
Build the main package, plus all packages that it imports, into a single C shared library.
The only callable symbols will be those functions marked as exported.

plugin:
Requires a main package as for -buildmode=c-archive
Build the main package, plus all packages that it imports, into a single shared library that may be loaded as a run-time plugin.

exe:
Default build mode for a package named main.

pie: (Go v1.6.0)
This is like -buildmode=exe , but it builds a Position Independent Executable.

-linkshared:
Directs to Go tool to use link against shared libraries when available.
When no shared library is available for some imported package, the ordinary archive will be used instead.
The -linkshared flag may be used with
-buildmode=shared, exe, pie
As the name suggests, -linkshared is NOT used for -buildmode=archive or c-archive

Hands on:

Build Golang's std library into shared library.
$ go install -buildmode=shared std

Build the shared code:
$ go install -buildmode=shared -linkshared github.com/your/lib/code

Use the shared library:
$ go install -linkshared github.com/your/main/code  // which imports "github.com/your/lib/code"

With a SONAME, and beware to put the compiled binary into the POSIX SONAME location/version.
$ go install \
-ldflags '-extldflags -Wl,-soname,libpikachu.so.0' \
-buildmode=shared \
-linkshared \
github.com/your/lib/code

[LLD 7.0.0] Split stacks.

Ian Lance Taylor [Split Stacks on GCC] https://gcc.gnu.org/wiki/SplitStacks


And thus smells like a usage for goroutine, and tada! :
Ian Lance Taylor [The Go frontend for GCC] https://talks.golang.org/2010/gofrontend-gcc-summit-2010.pdf

Check out the emitted assembly code for further study.


Reference:
https://stackoverflow.com/questions/46313106/how-to-use-fsplit-stack-on-a-large-project

[gcc] link time optimization.

Linker doing link time optimization

[Note] linking notes

Reference:
Weak_symbol

[ABI] Calling conventions.

*Position Independent Code and x86-64 libraries

*Calling Conventions Demystified

*The history of calling conventions, part 1

*The history of calling conventions, part 3

*The history of calling conventions, part 4: ia64

*The history of calling conventions, part 5: amd64

Weak Symbols by Examples

[c][c++] notes , reference for function call, linking process

Introduction to OS X ABI Function Call Guide

gcc : Using Vector Instructions through Built-in Functions

Programming from the Ground Up - Note

linking process note

[ELF][PIC][Note]

References and excerpt from:

http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/

http://eli.thegreenplace.net/2011/11/11/position-independent-code-pic-in-shared-libraries-on-x64/

http://eli.thegreenplace.net/2011/08/25/load-time-relocation-of-shared-libraries/

http://eli.thegreenplace.net/2012/01/03/understanding-the-x64-code-models/

http://eli.thegreenplace.net/2012/08/13/how-statically-linked-programs-run-on-linux/

ecx : Serves as a base pointer to GOT.  e.g : 0x1ff4

a value is taken from [ecx - 0x10], which is a GOT entry, and placed into eax.

The address of myglob : ecx - 0x10 = 0x1fe4 = eax

eax:  address of myglob. eax address : 0x1fe4.

library that uses myglob is pointed to here.

eax type: R_386_GLOB_DAT : put the actual value of the symbol
  (i.e. its address) into that offset".

eax : the value of myglob is placed into eax.

--------
Function:

lazy binding optimization:
When a shared library refers to some function, the real address of that function
  is not known until load time.

Lazy binding scheme is attained by adding yet another level of indirection – the PLT.

Procedure Linkage Table (PLT):
PLT is part of the executable text section, consisting of a set of entries.
(one for each external function the shared library calls)
Each PLT entry is a short chunk of executable code.

Instead of calling the function directly, the code calls an entry in the PLT,
which then takes care to call the actual function.

This arrangement is sometimes called a "trampoline".

Each PLT entry also has a corresponding entry in the GOT which contains the actual
offset to the function, but only when the dynamic loader resolves it.

When the shared library is first loaded, the function calls have not been resolved yet:
PLT[n] => GOT[n] , GOT[n] Has the function's address


PLT[0] is different from other entry. It's a call to a resolver routine,
which is located in the dynamic loader itself.
This routine resolves the actual address of the function.
-------
Flow:

First time call:
Text call function func: -> PLT[n] -> GOT[n] -> back to next address of PLT[n]'s
call to GOT[n], which is to prepare resolver -> PLT[0] , call dynamic loader,
prepare function address and place into GOT[n] -> calls the function.

Next time call:
Text call function func: -> PLT[n] -> GOT[n] ->  calls the function.
------

Lazy symbol resolution performed by the dynamic loader can be configured with
some environment variables:

LD_BIND_NOW : always perform the resolution for all symbols at start-up time.
  With GDB. You’ll see that the GOT entry for ml_util_func contains its real address even before the first call to the function.

LD_BIND_NOT : not to update the GOT entry at all.

More info:
man ld.so

------
The costs of PIC:
1. extra indirection required for all external references to data and code in PIC.
2. increased register usage required to implement PIC.
  it makes sense for the compiler to generate code that keeps its address in a register
  (usually ebx).

------
X64:
RIP-relative addressing:
New "RIP-relative addressing mode",the default for all 64-bit mov instructions that reference memory
(it’s used for other instructions as well, such as lea).
A quote from the "Intel Architecture Manual vol 2a":
A new addressing form, RIP-relative (relative instruction-pointer) addressing, is implemented in 64-bit mode.
An effective address is formed by adding displacement to the 64-bit RIP of the next instruction.

The displacement used in RIP-relative mode is 32 bits in size.
Since it should be useful for both positive and negative offsets,
roughly +/- 2GB is the maximal offset from RIP supported by this addressing mode.

[C++11][NOTE] std::vector performance regression when enabling C++11

std::vector performance regression when enabling C++11

GCC/G++ LinkTimeOptimization

gcc -flto -o f f1.o f2.o

Link-time optimization does not work well with generation of debugging information.
Combining -flto with -g is currently experimental and expected to produce wrong results.

[gcc][NOTE] Linking process

Excerpt from http://eli.thegreenplace.net/

Here’s what the linker does:
The linker maintains a symbol table.
This symbol table does a bunch of things, but among them is keeping two lists:

• A list of symbols exported by all the objects and libraries encountered so far.
• A list of undefined symbols that the encountered objects and libraries requested to import and were not found yet.

When the linker encounters a new object file, it looks at:

• The symbols it exports: these are added to the list of exported symbols mentioned above. 
• If any symbol is in the undefined list, it’s removed from there because it has now been found. 
• If any symbol has already been in the exported list, we get a "multiple definition" error: two different objects export the same symbol and the linker is confused.
• The symbols it imports: these are added to the list of undefined symbols, unless they can be found in the list of exported symbols.

When the linker encounters a new library, things are a bit more interesting.

• The linker goes over all the objects in the library. For each one, it first looks at the symbols it exports.
• If any of the symbols it exports are on the undefined list, the object is added to the link and the next step is executed. Otherwise, the next step is skipped.
• If the object has been added to the link, it’s treated as described above – its undefined and exported symbols get added to the symbol table.
• Finally, if any of the objects in the library has been included in the link, the library is rescanned again – it’s possible that symbols imported by the included object can be found in other objects within the same library.

$ gcc simplemain.o -L. -Wl,--start-group -lbar_dep -lfunc_dep -Wl,--end-group
$ gcc simplemain.o -L. -Wl,--undefined=bar -lbar_dep -lfunc_dep

[ELF] Everything about ELF

• text, data, or bss: A symbol defined in this module. External bit
may or may not be on. Value is the relocatable address in the module
corresponding to the symbol.

• abs: An absolute non-relocatable symbol. (Rare outside of debugger
info.) External bit may or may not be on. Value is the absolute
value of the symbol.
• undefined: A symbol not defined in this module. External bit must
be on. Value is usually zero, but see the ‘‘common block hack’’
below.

These symbol types are adequate for older languages such as C and
Fortran and, just barely, for C++.

ELF header :

char magic[4] = "\177ELF";// magic number
char class; // address size, 1 = 32 bit, 2 = 64 bit
char byteorder; // 1 = little-endian, 2 = big-endian
char hversion; // header version, always 1
char pad[9];
short filetype; // file type: 1 = relocatable, 2 = executable,
// 3 = shared object, 4 = core image
short archtype; // 2 = SPARC, 3 = x86, 4 = 68K, etc.
int fversion; // file version, always 1
int entry; // entry point if executable
int phdrpos; // file position of program header or 0
int shdrpos; // file position of section header or 0
int flags; // architecture specific flags, usually 0
short hdrsize; // size of this ELF header
short phdrent; // size of an entry in program header
short phdrcnt; // number of entries in program header or 0
short shdrent; // size of an entry in section header
short phdrcnt; // number of entries in section header or 0
short strsec; // section number that contains section name strings

Section header :

int sh_name; // name, index into the string table
int sh_type; // section type
int sh_flags; // flag bits, below
int sh_addr; // base memory address, if loadable, or zero
int sh_offset; // file position of beginning of section
int sh_size; // size in bytes
int sh_link; // section number with related info or zero
int sh_info; // more section-specific info
int sh_align; // alignment granularity if section is moved
int sh_entsize; // size of entries if section is an array

Section types include:

• PROGBITS: Program contents including code, data, and
debugger info.
• NOBITS: Like PROGBITS but no space is allocated in the file itself.
Used for BSS data allocated at program load time.
• SYMTAB and DYNSYM: Symbol tables, described in more detail
later. The SYMTAB table contains all symbols and is 
intended for the regular linker, while DYNSYM is just the
symbols for dynamic linking. (The latter table has to be
loaded into memory at runtime,so it’s kept as small
as possible.)
• STRTAB: A string table, analogous to the one in a.out files.
Unlike a.out files, ELF files can and often do contain 
separate string tables for separate purposes, 
e.g. section names, regular symbol names,
and dynamic linker symbol names.
• REL and RELA: Relocation information. REL entries add the
relocation value to the base value stored in the code
or data, while RELA entries include the base value for
relocation in the relocation entries themselves.
(For historical reasons, x86 objects use REL relocation
and 68K objects use RELA.) There are a bunch of relocation
types for each architecture, similar to (and derived from) the
a.out relocation types.
• DYNAMIC and HASH: Dynamic linking information and the runtime
symbol hash table.
There are three flag bits used: ALLOC, which means that
the section occupies memory when the program is
loaded, WRITE which means that the section when loaded
is writable, and EXECINSTR which means that the section
contains executable machine code.

Sections include:

• .text which is type PROGBITS with attributes ALLOC+EXECINSTR.
It’s the equivalent of the a.out text segment.
• .data which is type PROGBITS with attributes ALLOC+
WRITE. It’s the equivalent of the a.out data segment.
• .rodata which is type PROGBITS with attribute ALLOC. It’s
read-only data, hence no WRITE.
• .bss which is type NOBITS with attributes ALLOC+WRITE.
The BSS section takes no space in the file, hence NOBITS, but is
allocated at runtime, hence ALLOC.
• .rel.text, .rel.data, and .rel.rodata, each which is
type REL or RELA. The relocation information for the corresponding
text or data section.
• .init and .fini, each type PROGBITS with attributes ALLOC+
EXECINSTR. These are similar to .text, but are code to
be executed when the program starts up or terminates, respectively.
C and Fortran don’t need these, but they’re essential for C++ which
has global data with executable initializers and finalizers.
• .symtab, and .dynsym types SYMTAB and DYNSYM respectively,
regular and dynamic linker symbol tables. The dynamic
linker symbol table is ALLOC set, since it’s loaded at runtime.
• .strtab, and .dynstr both type STRTAB, a table of name
strings, for a symbol table or the section names for the section
table. The dynstr section, the strings for the dynamic linker
symbol table, has ALLOC set since it’s loaded at runtime.
There are also some specialized sections like .got and .plt, the
Global Offset Table and Procedure Linkage Table used for dynamic
linking (covered in Chapter 10), .debug which contains symbols
for the debugger, .line which contains mappings from
source line numbers to object code locations again for the debugger,
and .comment which contains documentation strings, usually
version control version numbers.

An unusual section type is .interp which contains the name of a program to use as an interpreter. If this section is present, rather than running the program directly, the system runs the interpreter and passes it the ELF file as an argument. Unix has for many years had self-running interpreted text files, using

#! /path/to/interpreter

as the first line of the file. ELF extends this facility to interpreters which run non-text programs. In practice this is used to call the run-time dynamic linker to load the program and link in any required shared libraries. ELF symbol table:

int name; // position of name string in string table
int value; // symbol value, section relative in reloc,
// absolute in executable
int size; // object or function size
char type:4; // data object, function, section, or special case file
char bind:4; // local, global, or weak
char other; // spare
short sect; // section number, ABS, COMMON or UNDEF

If the file is a C++ program, it will probably also contain .init, .fini, .rel.init, and .rel.fini sections as well. Sample relocatable ELF file:

ELF header
.text
.data
.rodata
.bss
.sym
.rel.text
.rel.data
.rel.rodata
.line
.debug
.strtab
(section table, not considered to be a section)

An ELF executable file has the same general format as a relocatable ELF, but the data are arranged so that the file can be mapped into memory and run. The file contains a program header that follows the ELF header in the file. The program header defines the segments to be mapped. ELF program header:

int type; // loadable code or data, dynamic linking info, etc.
int offset; // file offset of segment
int virtaddr; // virtual address to map segment
int physaddr; // physical address, not used
int filesize; // size of segment in file
int memsize; // size of segment in memory (bigger if contains BSS)
int flags; // Read, Write, Execute bits
int align; // required alignment, invariably hardware page size

An executable usually has only a handful of segments, a read-only one for the code and read-only data, and a read-write one for read/write data. All of the loadable sections are packed into the appropriate segments so the system can map the file with one or two operations. ELF files extend the ‘‘header in the address space’’ trick used in QMAGIC a.out files to make the executable files as compact as possible at the cost of some slop in the address space. A segment can start and end at arbitrary file offsets, but the virtual starting address for the segment must have the same low bits modulo the alignment as the starting offset in the file, i.e, must start in the same offset on a page. The system maps in the entire range from the page where the segment starts to the page where the segment ends, even if the segment logically only occupies part of the first and last pages mapped ELF loadable segments:

The mapped text segment consists of the ELF header, program header, and read-only text, since the ELF and program headers are in the same page as the beginning of the text. The read/write but the data segment in the file starts immediately after the text segment. The page from the file is mapped both read-only as the last page of the text segment in memory and copy-on-write as the first page of the data segment. In this example, if a computer has 4K pages, and in an executable file the text ends at 0x80045ff, then the data starts at 0x8005600. The file page is mapped into the last page of the text segment at location 0x8004000 where the first 0x600 bytes contain the text from 0x8004000-0x80045ff, and into the data segment at 0x8005000 where the rest of the page contain the initial contents of data from 0x8005600-0x80056ff. The BSS section again is logically continuous with the end of the read write sections in the data segment, in this case 0x1300 bytes, the difference between the file size and the memory size. The last page of the data segment is mapped in from the file, but as soon as the operating system starts to zero the BSS segment, the copy-on-write system makes a private copy of the page. If the file contains .init or .fini sections, those sections are part of the read only text segment, and the linker inserts code at the entry point to call the .init section code before it calls the main program, and the .fini section code after the main program returns. An ELF shared object contains all the baggage of a relocatable and an executable file. It has the program header table at the beginning, followed by the sections in the loadable segments, including dynamic linking information. Following sections comprising the loadable segments are the relocatable symbol table and other information that the linker needs while creating executable programs that refer to the shared object, with the section table at the end.



Special symbols:
Many systems use a few special symbols defined by the linker itself.
Unix systems all require that the linker define etext, edata,
and end as the end of the text, data, and bss segments, respectively.
The system sbrk() routine uses end as the address of the beginning
of the runtime heap, so it can be allocated contiguously with the existing data and bss.


GOT in addition R_386_GOTPC or its equivalent. The exact
types are architecture-specific, but the x86 is typical:
• R_386_GOT32: The relative location of the slot in the GOT
where the linker has placed a pointer to the given symbol. Used
for indirectly referenced global data.
• R_386_GOTOFF: The distance from the base of the GOT to the
given symbol or address. Used to address static data relative to the
GOT.
• R_386_RELATIVE: Used to mark data addresses in a PIC shared
library that need to be relocated at load time.



In a conventionally linked program, symbols are bound to
addresses and library code is bound to the executable
at link time, so the library the program was linked with
is the one it uses regardless of subsequent changes to
the library.. With static shared libraries, symbols are still
bound to addresses at link time, but library code isn’t bound
to the executable until run time. (With dynamic shared libraries,
they’re both delayed until runtime.)
Structure of typical shared library:

File header, a.out, COFF, or ELF header
(Initialization routine, not always present)
Jump table
Code
Global data
Private data

A UNIX shared library actually consists of two related files,
the shared library itself and a stub library for the linker to
use. A library creation utility takes as input a normal library
in archive format and some files of control information and uses
them to create create the two files. The stub library contains no
code or data at all (other than possibly a tiny bootstrap routine)
but contains symbol definitions for programs linked with the library
to use.

Creating the shared library involves these basic steps,
which we discuss in greater detail below:

• Determine at what address the library’s code and data will

 be loaded.

• Scan through the input library to find all of the exported

 code symbols. (One of the control files may be a list of

 some of symbols not to export, if they’re just used for 

inter-routine communication within the library.)

• Make up the jump table with an entry for each exported

 code symbol.

• If there’s an initialization or loader routine at the 

beginning of the library, compile or assemble that.

• Create the shared library: Run the linker and link 

everything together into one big executable format file.

• Create the stub library: Extract the necessary symbols from

 the newly created shared library, reconcile those symbols

 with the symbols from the input library, create a stub routine

 for each library routine, then compile or assemble the stubs 

and combine them into the stub library.

For static link library:
Linux added a single uselib() system call that took the file
name and address of a library and mapped it into the program
address space. The startup routine bound into the executable
ran down the list of libraries, doing a uselib() on each.


ELF header has a interp section containing the name of
an "interpreter" program to use when running the file.


An ELF shared library:

(Lots of pointer arrows here)
read-only pages:
.hash
.dynsym
.dynstr
.plt
.text
.rodata
read-write pages:
.data
.got
.dynamic
.bss

Ref:

[linking] PIC GOT PLT , Static Link, Dynamic Link

Best explained article:
Position Independent Code (PIC) in shared libraries

Excerpt:
The LD_BIND_NOW env var, when defined, tells the dynamic loader to always perform 
the resolution for all symbols at start-up time, and not lazily.

Conversely, the LD_BIND_NOT env var tells the dynamic loader not to update the 
GOT entry at all. Each call to an external function will then go through the dynamic loader and be resolved anew.

Load-time relocation of shared libraries

How statically linked programs run on Linux

Position Independent Code (PIC) in shared libraries on x64

Understanding the x64 code models

Reference:

http://www.x86-64.org/

Trampoline

[link & loader][NOTE] some useful link and explain

os document:

Solaris : Linker and Libraries Guide

Book:

Linkers and Loaders

Paper:

How to write shared libraries

Wikipedia:

Address space layout randomization(ASLR)

gcc howto:

gcc Howto : Linking

Stackoverflow:

In Linux stubs are used for standard libraries. Why are stubs required?
what is a .sa file for gcc shared library?

My Note about linking:

Something about Link

[Phoebus][Project Docuemt]

General Notes:
Linking Knowledge, ELF , and commands
Android NDK Development Notes:
Android NDK Toolchain & environment setup
Android NDK Build HOWTO
Android.mk
Application.mk
Import Module
Prebuild Library
NDK-Build Command
NDK-GDB Command

Porting:
[Phoebus] Porting to Android / ARM (Cont.)
[Phoebus] Compile psd for OpenWRT / MIPS

OpenWRT install on WRT54GL

AutoTools notes

Eventually this will extend to projects on Android devices. YA!