[linker] linker of choice

 

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

$ clang++ -fuse-ld=lld

[C++][cpponsea] Keep C++ Binaries Small - summary

Reference:
https://youtu.be/7QNtiH5wTAs?si=c8I_prA9k9Hasfdr

Problem

• Devices with limited storage
• Devices with limited bandwith
• Env impact

Parts of an executable

• Header
• Text
• Data (init. vs uninit)
• Read-only data
• symbol table
• Relocation info
• (ref https://eli.thegreenplace.net/2013/07/09/library-order-in-static-linking)
• Import table / Procedure linkage table
• Export table
• Exception handling info
• Debugging info

Consider

• cross platform?
• linking/symbol resolution handling
• PIC
• Endianness
• Architecture / extensibility

Tools

https://github.com/google/bloaty

Coding part

• Object init.
• Member ordering
  padding http://www.catb.org/esr/structure-packing/
  alignment https://vsdmars.blogspot.com/2022/03/c-memory-allignment-wrap-up.html
• Special member functions
• virtual functions
• templates
• passing functions around
• constexpr functions

Object init.

0(.zerofill) vs. other thing else; decrease size

Member ordering

Usually won't reduce the binary size due to compiler is able to optimize.

Special member functions

• inline default special functions
• inline empty special functions
• following the rule of zero(RoZ)
• with either virtual or non-virtual destructor

Follow the Rule-Of-Zero

https://en.cppreference.com/w/cpp/language/rule_of_three

templates

• minimal template code section; same as marco
• Exact/promote to the upper level, which the code is not generated
  for every new type instance.

Compiler options

• -Os
• -flto
• -fdata-sections / -ffunction-sections -Wl, --gc-sections
• The Traditional Way (Still Valid) If you are linking against a traditional static library (.a file), the linker still operates on an object-file level. If a static library is built with strlen.o, strcpy.o, and printf.o as separate files inside the archive, and your code only references strlen, the linker will strictly pull in strlen.o. The other object files are completely ignored, keeping your binary small. Many embedded and legacy C libraries are still structured exactly this way.
• The Modern Way: Section Garbage Collection Today, instead of splitting source code into a million files, we let the compiler and linker do the heavy lifting using function-level sections. When compiling modern C code (using GCC or Clang), you can pass specific flags: -ffunction-sections and -fdata-sections: This tells the compiler to put every single function and data item into its own distinct section inside a single object file, rather than bundling them all into one giant .text section. --gc-sections (Linker flag): This tells the linker to perform "garbage collection" and throw away any unused sections during the final build. Why this matters: You can have a single string.c file containing 50 functions. With these flags, the linker will still grab only strlen and discard the other 49, achieving the exact same tiny binary size without the architectural headache.
• Link-Time Optimization (LTO) The ultimate evolution of this is LTO (compiled with -flto). With LTO enabled, the compiler doesn't just emit machine code into object files; it emits its internal intermediate representation. At the linking stage, the compiler looks at the entire program holistically. It can inline strlen directly into your code, eliminate dead code with extreme precision, and completely optimize away unused functions, regardless of how the source files or libraries were structured.
• -Wl, --icf=all or -Wl, --icf==safe
• -Wl, -s and -Wl, --strip-all
• -Wl, --as-needed
• -mllvm -inline-threshold=<n>
• -fstack-protector
  https://clang.llvm.org/docs/ClangCommandLineReference.html#cmdoption-clang-fstack-protector
• -finline-limit=n
  https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#index-finline-limit
• Identical Code Folding (ICF)
  https://research.google/pubs/safe-icf-pointer-safe-and-unwinding-aware-identical-code-folding-in-gold

[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;
}

[Linkage] COMDAT

Reference:
https://maskray.me/blog/2021-07-25-comdat-and-section-group

COMDAT gives indication to the linker to deduplicate the inline/weak reference/external linkage symbols.

https://github.com/llvm/llvm-project/blob/2e603c6/clang/lib/AST/ItaniumMangle.cpp#L1458-L1472

inline vs. non-inline name mangling with extra letter 'L'.

e.g.

_ZSt8in_place vs. _ZStL8in_place

[stack guard-page] Preventing stack guard-page hopping reading notes

Reference:
Preventing stack guard-page hopping

The stack area in a running process is, on most architectures,
placed at a relatively high virtual address; it grows downward as the process's stack needs increase.

A virtual-memory region that automatically grows as a result of page faults brings some inherent risks; in particular, it must be prevented from growing into another memory region placed below it.

In a single-threaded process, the address space reserved for the stack can be large and difficult to overflow.

Multi-threaded processes contain multiple stacks; those stacks are smaller and are likely to be placed between other virtual-memory areas of interest.

An accidental overflow could corrupt the area located below a stack; a deliberate overflow, if it can be arranged, could be used to compromise the system.

The kernel has long placed a guard page — a page that is inaccessible to the owning process — below each stack area.

A process that wanders off the bottom of a stack into the guard page will be rewarded with a segmentation-fault signal, which is likely to bring about the process's untimely end.

The world has generally assumed that the guard page is sufficient to protect against stack overflows but, it seems, the world was mistaken.

The fundamental problem with the guard page is that it is too small.
There are a number of ways in which the stack can be expanded by more than one page at a time.

• make large alloca() calls
• with large variable-length arrays or other large on-stack data structures.

It turns out to be relatively easy for an attacker to cause a program to generate stack addresses that hop over the guard page, stomping on whatever memory is placed below the stack.

Partial solution: extend the guard page size: 4KB -> 1MB
Configurable at boot time:
stack_guard_gap

[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

[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

[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

[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.

[c++14][NOTE] pointer to function do have linkage in C++14

excerpt from Scott Meyers' New C++ Closures as Function Pointers: Capture‐less closures implicitly convert to function pointers:

 
int (*fp)(int) = [](int x) { return x * x; };

Such closures can be treated like functions.
 No need for std::function to refer to them.
 No captures ⇒ no stored pointers or references ⇒ no dangling.
 Often useful for callbacks with C‐like APIs:

 
int atexit(void (*f)()) noexcept; // from <cstdlib>
std::atexit([]{ logMsg("Shutting down..."); });

In C++11, function pointer linkage not specified ⇒ possible linkage problems.
 C++14 specifies C++ linkage.
noexcept akin to throw(), but enables more optimizations.
 Violated noexcept ⇒ terminate.
 Exception specifications now deprecated.

[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