Dynamic Linking and Shared Libraries

The Problem with Static Linking

Let's imagine a world where all the programs on your computer are statically linked. What would that look like…?

$ ls -lh /bin/cat /bin/find /bin/grep /bin/ls /bin/python3
-rwxr-xr-x 1 root root 843K Apr  5  2024 /bin/cat
-rwxr-xr-x 1 root root 1.5M Apr  8  2024 /bin/find
-rwxr-xr-x 1 root root 1.7M Apr  8  2024 /bin/grep
-rwxr-xr-x 1 root root 1.3M Apr  5  2024 /bin/ls
-rwxr-xr-x 1 root root 9.4M Sep 11 07:17 /bin/python3
-rwxr-xr-x 1 root root 879K Apr  8  2024 /bin/xargs

If we run a command pipeline like

$ find . -name "*.c" | grep TODO | xargs cat

we're running four programs (find, grep, xargs, and cat). The combined code for all of them is 1.5 MB + 1.7 MB + 879 KB + 843 KB = 4.75 MB, all for something quite simple! The bulk of that space is four separate copies of the C library code!

A First Try: Link with Absolute Addresses

The problem with fixing the addresses of library functions in the program is that if the library changes, the addresses will change, too. So we'd have to recompile every program that uses the library every time the library changes. That's not very practical!

A Second Try: Load-Time Relocation

The big problem with running the linker every time we load a program is that it would slow things down. We'd have to read in the program, read in the libraries, patch the code in memory to fix up the addresses, and only then start running the program. Full-blown linking is often quite a complex process, and we'd be doing it every time we load a program.

There's also the question of sharing code between multiple instances of the same program. With our prelinked programs, the program code was read-only and could be read into memory directly from the executable file. But if we're going to be patching the code every time we load it, the code might not be so easy to share. We also can't demand-page the code out of the executable file; we'd have to swap the writeable pages to swap space if we didn't want those pages in memory.

What We Want…

Let's pause to review what we want from a shared-library system:

• Memory Efficiency: We want to share library code between programs to save memory.
• Speed: We don't want to slow down program startup (too much).
• Flexibility: We want to be able to update libraries without recompiling all programs.
• Security: We want to be able to move libraries around in memory (ASLR), rather than always having them at the same address.
• Read-Only Code: We want to share program code between processes and not patch it in memory.

A Better Way: Indirect Calls

Instead of modifying our code to call library functions directly, what if we

1. Made a table of function addresses.
2. Have the code call through the table.
3. Only fix up the table entries when we load the program.

That table is called the Global Offset Table (GOT). To use this approach, our compiler needs to transform our hello program to use the GOT. Here's pseudocode for what the compiler would turn our hello program into:

#include <unistd.h>

struct got_entry {
        void *address;
        char *symbol_name;
};

__attribute__((section(".data.got")))
struct got_entry got[] = {
        { 0, "write" },
        { 0, "printf" },
        { 0, "exit" },
        { 0, NULL }
};

typedef ssize_t (*write_func)(int, const void *, size_t);
typedef int (*printf_func)(const char *, ...);
typedef void (*exit_func)(int);

int 
main()
{
        ((write_func)got[0].address)(1, "Hello World!\n", 13);
        ((printf_func)got[1].address)("... and hello to dynamic linking!\n");
        ((exit_func)got[2].address)(0);
        return 0;
}


/* Below is some magic code to actually fill in the GOT. You don't need
 * to worry too much about it, only that it's run when the program is
 * loaded.  We'll imagine that the dynamic linker does this for us. */

#include <dlfcn.h>

#ifndef RTLD_DEFAULT
    #define RTLD_DEFAULT 0
#endif

// Magic constructor function to fill in the GOT, using dlsym and GCC magic attributes
void __attribute__((constructor)) 
initialize_got()
{
        for (int i = 0; got[i].symbol_name != NULL; i++) {
                got[i].address = dlsym(RTLD_DEFAULT, got[i].symbol_name);
        }
}

Thus, main compiles to

main:
        endbr64
        subq    $8, %rsp
        movl    $13, %edx
        movl    $.LC0, %esi
        movl    $1, %edi
        call    *got(%rip)      # Call write
        movl    $.LC1, %edi
        xorl    %eax, %eax
        call    *got+16(%rip)   # Call printf
        xorl    %edi, %edi
        call    *got+32(%rip)   # Call exit
        xorl    %eax, %eax
        addq    $8, %rsp
        ret

• Try this code in OnlineGDB

So long as we know where got is (which we do, since it's inside the executable), we can find the addresses of the library functions. And because the global offset table is just data, we can write to it when we load the program.

And so:

• The code can be read-only and shared.
• We only need to write to data pages (the GOT).
• Each process has its own GOT with the right addresses.
• Linking is relatively fast (just update the GOT by looking up all the symbols we need).

Lazy Binding: Why Fix Everything at Once?

There's another way we could do things, at least for functions. Instead of a table of data, we could have a table of code (called function stubs). After the dynamic linker has run, it's as if we'd written

.text.plt:
write_jump:
        jmp     write
printf_jump:
        jmp     printf
exit_jump:
        jmp     exit

But initially, the table would look like

.text.plt:
write_jump:
        jmp     0
printf_jump:
        jmp     0
exit_jump:
        jmp     0

We'd expect the linker to patch up the table entries when we load the program.

The Trick

What we actually make the table entries look like initially is

.text.plt:
write_jump:
        call    dyld_fixup
printf_jump:
        call    dyld_fixup
exit_jump:
        call    dyld_fixup

.rodata.symnames:
S1:     .asciz  "write"
S2:     .asciz  "printf"
S3:     .asciz  "exit"

.rodata.symlist:
        .quad   S1
        .quad   S2
        .quad   S3
        .quad   0

The trick is that dyld_fixup looks up the symbol name in the symbol list, finds the address of the function, and then patches the code, replacing the call to dyld_fixup with a jump to the actual function in the library. With this approach, we don't have to look up the address of the function until we actually need it.

This approach is either called lazy binding (on macOS) or the Procedure Linkage Table (PLT) (on Linux). It's a way to avoid looking up the addresses of library functions until we actually need them.

In Practice…

Let's compile this program and see what it looks like!

#include <unistd.h>
#include <stdio.h>

int 
main()
{
        write(1, "Hello World!\n", 13);
        printf("... and hello to dynamic linking!\n");
        exit(0);
}

The code for main looks like

main:
        endbr64
        subq    $8, %rsp
        movl    $13, %edx
        leaq    .LC0(%rip), %rax
        movq    %rax, %rsi
        movl    $1, %edi
        call    write@PLT
        leaq    .LC1(%rip), %rax
        movq    %rax, %rdi
        movl    $0, %eax
        call    printf@PLT
        movl    $0, %edi
        call    exit@PLT

So you can see here that it's calling little stub functions like we suggested (except that they're called write@PLT, printf@PLT, and exit@PLT rather than write_jump, printf_jump, and exit_jump), and then those functions will call the real functions, figuring out where the functions really are on the first call.

$ objdump -j .plt.sec -D -r  hello-dyn2
Disassembly of section .plt.sec:

0000000000001070 <write@plt>:
    1070:       f3 0f 1e fa             endbr64
    1074:       ff 25 46 2f 00 00       jmp    *0x2f46(%rip)        # 3fc0 <write@GLIBC_2.2.5>
    107a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

0000000000001080 <printf@plt>:
    1080:       f3 0f 1e fa             endbr64
    1084:       ff 25 3e 2f 00 00       jmp    *0x2f3e(%rip)        # 3fc8 <printf@GLIBC_2.2.5>
    108a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

0000000000001090 <exit@plt>:
    1090:       f3 0f 1e fa             endbr64
    1094:       ff 25 36 2f 00 00       jmp    *0x2f36(%rip)        # 3fd0 <exit@GLIBC_2.2.5>
    109a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

$ objdump -j .plt -D -r  hello-dyn2

Disassembly of section .plt:

0000000000001020 <.plt>:
    1020:   ff 35 8a 2f 00 00       push   0x2f8a(%rip)        # 3fb0 <_GLOBAL_OFFSET_TABLE_+0x8>
    1026:   ff 25 8c 2f 00 00       jmp    *0x2f8c(%rip)        # 3fb8 <_GLOBAL_OFFSET_TABLE_+0x10>
    102c:   0f 1f 40 00             nopl   0x0(%rax)
  write@plt_helper:
    1030:   f3 0f 1e fa             endbr64
    1034:   68 00 00 00 00          push   $0x0
    1039:   e9 e2 ff ff ff          jmp    1020 <_init+0x20>
    103e:   66 90                   xchg   %ax,%ax
  printf@plt_helper:
    1040:   f3 0f 1e fa             endbr64
    1044:   68 01 00 00 00          push   $0x1
    1049:   e9 d2 ff ff ff          jmp    1020 <_init+0x20>
    104e:   66 90                   xchg   %ax,%ax
  exit@plt_helper:
    1050:   f3 0f 1e fa             endbr64
    1054:   68 02 00 00 00          push   $0x2
    1059:   e9 c2 ff ff ff          jmp    1020 <_init+0x20>
    105e:   66 90                   xchg   %ax,%ax

Back to Memory Usage

Remember the sizes of those executables from before? Let's look at the savings; or, to put it another way, how much worse static linking is compared to dynamic linking:

You can see that, especially for small programs, the dynamic-linking approach saves a lot of space. And even for larger programs, the savings are significant.

So now, if we run a command like

$ find . -name "*.c" | grep TODO | xargs cat

It's only going to require 38.5 KB + 182.4 KB + 62.4 KB + 139.0 KB = 422.3 KB, rather than 4.75 MB! A tenfold reduction in memory usage!

(When logged in, completion status appears here.)