Two Different “Linkers”

On ELF, the dynamic linker resolves symbols like this:

1. Look at the executable’s dynamic symbol table.
2. If it finds a strong symbol malloc there, that wins.
3. It patches every shared library’s GOT entry for malloc to point to that address in our executable.

But first, it helps to separate two distinct phases:

GOT and PLT: Indirection for Unknown Runtime Addresses

Shared libraries are position-independent and can be mapped at unpredictable addresses. Therefore, the compiler and link editor cannot hardcode absolute call targets for imported symbols.

ELF solves this via two cooperating structures:

Lazy Binding (Step-by-Step)

As we pointed out, shared libraries are position-independent and can be mapped at unpredictable addresses. This means the compiler cannot predict the run-time address of the function defined in the shared module, because it could be loaded anywhere at run time. Rather than fixing all of them before running the program, GNU compilation systems defer binding the address of each function up until the first time it is called. This is called - surprise surprise - ‘lazy binding’.

The reason is that an arbitrary program won’t probably call ALL of the functions that the shared library exposes, which can be pretty large in numbers, hundreds or thousands. By defering the resolution, linker avoids all those unnecessary relocations at load time. At link time, linker only ensures that there is a library that is able to provide the symbols(s) i.e. exports the symbol(s).

Let’s mimick the flow for a call to an imported malloc from within a shared library. If our malloc would be dynamically linked, it would have a PLT entry along those lines:

		GOT:
		GOT[0]: addr. of .dynamic
		GOT[1]: addr. of relocation entries
		GOT[2]: addr. of dynamic linker
		# ... -> after this point on, each of the remaining entries (addresses of called functions) must be resolved at runtime, they each have a PLT entry. At first, each entry points to the 2. instruction in it's PLT entry
	---	GOT[4]: 0x4005c6 # this is the entry for our malloc
	|
	|	PLT:
	|	PLT[0]: call dynamic linker
	|	# ...
	|	PLT[2]:
	|	4005c0: 	jump *GOT[4] 		
	-->	4005c6:		push relocation_index 
		4005cb:		jump PLT[0]

1. Caller executes bl malloc@plt (or call malloc@plt on x86-64).
2. The malloc@plt stub jumps through the GOT slot for malloc.

• Since the address of the dynamically linked procedure is not resolved, it retrieves the address of the PLT entry of malloc which is PLT[2] and jumps there (0x4005c0)

1. Initially, that GOT slot points back into the PLT resolver stub.

• Call [got[malloc]] executes the first instruction in PLT entry which is to jump to the address in GOT[4] (0x4005c6), the second instruction in PLT[2].

1. The PLT resolver calls into the dynamic loader.
   • It pushes the ID of malloc into the stack and jumps to PLT[0] which is a call to dynamic loader.

The dynamic loader:

• uses its stack entries (one of which is the malloc’s ID) to
  • determine the runtime location of malloc
  • overwrite GOT[4] with the found runtime address of malloc so that during the next call, it does not jumps back to PLT but the where malloc is
  • pass control to malloc

Subsequent calls:

• PLT jumps through GOT
• GOT already contains the resolved function pointer
• no loader involvement
• This makes the “extra work” happen only once per imported function.

Why Shared Libraries Resolve to the Executable’s malloc

The crucial ELF rule for this project is:

When resolving a symbol, the dynamic loader chooses a strong global symbol in the main executable over the same symbol name in a shared library.

So if the executable defines a strong malloc, and a shared library calls malloc, the loader may resolve that reference to the executable’s definition even if it had previously its own.

This is how allocator interposition happens on Linux without needing LD_PRELOAD.

In our case:

• the test executable contains malloc in its .text
• the process loads shared libraries that import malloc
• those shared libraries’ GOT entries are patched to point at our malloc

As a result, allocator calls from within shared libraries flow into our allocator.

Why Return Addresses Still Point to the Caller

Even though PLT/GOT is used to reach the resolved function, the return address recorded at the callee is still the caller’s next instruction.

For example on AArch64:

• the caller executes bl malloc@plt
• bl sets lr to the next instruction in the caller’s .text
• the PLT/GOT machinery determines the destination, but does not change lr

So __builtin_return_address(0) reports the caller location inside:

• the main executable for internal calls
• a shared library for external calls

This matches what was observed in callsite tracing and in gdb.

Practical Debug Hooks

Let’s remember what we were doing first:

In our container:

• we build libmalloc.a (or just object files).
• we link it statically into the final executable test_malloc.
• that executable is dynamically linked to:
  • libc.so.6
  • libstdc++.so.6
  • ld-linux-aarch64.so.1

At runtime:

• main test executable contains our malloc implementation in its .text.
• shared libraries (DSOs): libstdc++, libc, … each with their own PLT/GOT machinery that expects to call a malloc somewhere.

A few tools that are useful when validating this in practice:

# within the container after building the binary 

# Confirming malloc lies in .text
root@a8a15ed4fdce:/app# readelf -WS build/tests/test_malloc | awk '$2 == ".text" {print}'
  [12] .text             PROGBITS        0000000000007a40 007a40 00e7e4 00  AX  0   0 64

# So the text starts at address 0000000000007a40 and it's size is 00e7e4
# With a quick mental arithmetic... we have to validate in another way ... 

# Confirming the symbol exists in the executable
root@a8a15ed4fdce:/app# nm -n build/tests/test_malloc | grep ' malloc$'
0000000000015100 T malloc

# our malloc has the address 0000000000015100 within the .text or does it?
root@a8a15ed4fdce:/app# gdb build/tests/test_malloc 
... # we don't need to see the output..

(gdb) info address malloc
Symbol "malloc" is a function at address 0x15100.

# Ok, gdb seems to approve of the above claim
(gdb) info files
Symbols from "/app/build/tests/test_malloc".
Local exec file:
        `/app/build/tests/test_malloc', file type elf64-littleaarch64.
        Entry point: 0x7a40
        ...
        0x00000000000076e0 - 0x0000000000007a30 is .plt
        0x0000000000007a40 - 0x0000000000016224 is .text 	# <-----  cropping to relieve our brittle minds; 0x007a40 <  0x015100 < 0x016224 voila
        0x0000000000016224 - 0x000000000001623c is .fini
        0x0000000000016240 - 0x0000000000017d03 is .rodata
        ...
        0x000000000002fd48 - 0x000000000002ff48 is .dynamic
        0x000000000002ff48 - 0x000000000002ffe8 is .got
        0x000000000002ffe8 - 0x0000000000030198 is .got.plt
        0x0000000000030198 - 0x0000000000034978 is .data
        0x0000000000034978 - 0x0000000000038cc8 is .bss

Summary

On ELF/Linux:

• shared libraries call imported functions through PLT stubs
• PLT stubs consult GOT slots
• the dynamic loader resolves symbols and patches GOT slots
• a strong symbol in the executable can override the same symbol name in libraries

This is why statically linking an allocator implementation into the test executable caused much of the process—including shared libraries—to use that allocator.

Next, Mach-O & dyld Interposition explains why macOS does not behave like this by default.