CSCI 2021: ELF Files, Linking, and Loading

Chris Kauffman

Last Updated:
Mon May 1 11:26:10 AM CDT 2023

1
Logistics
Reading Bryant/O’Hallaron
Date Event
▶ Ch 9: Virtual Mem Mon 24-Apr Virtmem Wrap
▶ Ch 7: ELF / Linking Obj Code/Linking
Tue 25-Apr Lab/HW 13 Due

Goals Wed 26-Apr Obj Code/Linking

▶ Finish Virtmem Lab 14: P4 + Feedback
Fri 28-Apr Obj Code/Linking
▶ ELF Files Mon 01-May Last Lecture, Review
▶ Linking/Loading SRTs due by 1:25pm
P4 Due
Unified OH
P4 - Lind 316 8am-1:30pm
- Lind 326 1:30pm-5pm
▶ Due Mon 01-May
▶ Unified OH: 01-May Fri 05-May 10:30a-12:30pm Final Exam
for 1:25pm Lec 001
▶ Lab 14: Help on P4
▶ Video later today Sat 06-May 10:30a-12:30pm Final Exam
(maybe) for 3:35pm Lec 010
2
Course Feedback

Course Exit Survey on Canvas

▶ Opens on Canvas Wed 24-Apr, Due Tue 02-May
▶ 1 Engagement Point for Completing it

Official Student Rating of Teaching (SRTs)

▶ Official UMN Evals are done online this semester
▶ Available here: [Link]
▶ EVALUATE YOUR LECTURE SECTION: 001 or 010
Optionally evaluate lab section
▶ Due Mon 01-May by 1:25pm
▶ Response Rate ≥ 80% in both sections → One Final Exam
Question Revealed

3
Final Exam Logistics

▶ Final Exam in person, normal lecture location

▶ ~1.5 pages F/B Virtual Memory / Linking / Object Files / P5
▶ ~1.5 page F/B Comprehensive Review
(F/B = Front/Back)
▶ 2 hours to take Final Exam in person
▶ Review during last lecture

4
Overview

▶ Review building programs

▶ Executable and Linkable Format (ELF) Files
▶ Linker: Merging ELF files
▶ Loading: Creating running Problems
▶ Relocation
▶ Static vs Dynamic Linking
▶ Static/Dynamic Libraries
May not have time to cover all these topics and whatever we don’t
get to won’t appear on any exams.

5
The Immense Journey (apologies to Loren Eisley)
From C source file to running process involves a variety of tools,
formats, software and hardware, summarized for Linux below
1. Compilation: gcc preprocesses prog.c file, converts to internal
representation, optimizes, produces assembly code (stop at this
stage with -S)
2. Assembly: gas invoked by gcc to turn a prog.s file to a prog.o
ELF file, may be other .o files involved for multiple .c files
3. Linking: ld invoked by gcc to link multiple .o files to single
executable or library, copy in any statically linked library code,
indicates if executable has dynamic library dependencies
4. Stored Program: Now have an executable program in ELF format
stored on disk waiting to be run; call it [Link]
5. Loading: [Link] invoked by shell to load [Link] into
memory, sets up virtual memory map for .data / .text / heap /
stack, initializes .bss sections to 0, resolves any dynamic library
links required at load time, sets %rip to first program instruction
6. Running: OS handles remaining behavior of executing program
(process), running, sleeping, exiting, killing on segfaults
6
Exercise: Separate Compilation

# COMPILATION 1
> gcc -c func_01.c
> gcc -c main_func.c
> gcc -o main_func main_func.o func_01.o

# COMPILATION 2
> gcc -o main_func main_func.c func_01.c
▶ Describe differences between compilations above
▶ What is the result in each case?
▶ How are they different: any artifacts created in one but not
the other?
▶ Any advantages/disadvantages to them?

7
Answers: Separate Compilation
# COMPILATION 1
> gcc -c func_01.c
> gcc -c main_func.c
> gcc -o main_func main_func.o func_01.o

# COMPILATION 2
> gcc -o main_func main_func.c func_01.c

Compilation 1: Separate Compilation

▶ Separately compile func_01.c and main_func.c to binary
▶ Results in 2 .o object files
▶ Final step is to link two objects together to create an executable

Compilation 2: “Together” Compilation

▶ Compile all the C files at once to produce an executable
▶ Still likely to internally do separate compilation BUT no .o files will be
produced, only executable
Advantages of Separate Compilation described at the end of this presentation,
primarily efficiency: changing 1 file means recompiling 1 file and re-linking, NOT
recompiling all files

8
Object Files and ELF

▶ Binary files can’t be random so will

usually adhere to some standard
▶ Executable and Linkable Format
(ELF) is standard for the results of
compilation on Unix systems
▶ Stores program data in a variety of
sections in binary
▶ Explicitly designed to allow binary
objects to be
▶ Executed (programs)
▶ Merged with other objects
(linked)
Historically, ELF was preceded by a
dated format called [Link]: still default
name of gcc output programs
9
Brief Tour of ELF Sections
▶ ELF defines sections that are used in specific circumstances
▶ Always ELF Header at the beginning
▶ Always Program (Segment) Header Table for executable
▶ Always Section Header Table for linkable objects
▶ Some sections like .debug are common but don’t appear in ELF
specification (have their own DWARF spec)
Section Brief Description
ELF Header Global Info (32- or 64-bit, Execuable?, Byte ordering, etc.)
Program Header Table For executable programs, virtual address space info
Section Header Table Descriptions of sections and positions in file
.text Opcodes (binary assembly) that can be executed
.rodata Read Only data like string constants
.data Initialized global variables, space for values
.bss Un-initialized global variables, no space for values
.symtab Table of publicly available symbols for funcs/vars
.strtab Null-terminated strings, names of things in .symtab
.shstrab Null-terminated strings, names in section headers
.debug Debug info from gcc -g in DWARF format
.[Link] Relocation information for .text section
.[Link] Relocation information for .data section 10
ELF is a Binary Format
▶ ELF is a binary format so it is NOT easy on the eyes
▶ Make use of utilities like readelf to examine sections
▶ Can view bytes yourself but it is not usually intelligible

Linux for Embedded Systems (Lecture Slides), Ahmed El Arabawy, Cairo Univ. 11
Linking: Merging Binary Files to One
Linking: merge multiple .o into one .o OR executable file
▶ Merge .text section with instructions
▶ Merge .data section with global variables
▶ Merge .symtab modifying positions of where things exist, etc.
Symbol Resolution
▶ Multiple object files define a symbol, must resolve which
definition to use
▶ Some tricky bugs can arise in resolution

Relocation
▶ Adjust offsets of things in symbol table
▶ Change any instructions which use locations that have
changed
Linkers must deal with a lot of details; we will only touch on a few
important principles and how they relate C/Assembly programs
12
Linker: Multiple .o to Single/Executable
▶ A linker converts multiple # Demo merging two .o files with ld

.o files to… > nm func_01.o # names in .o file

0000000000000000 T func_01
▶ An executable (default) U puts
▶ Single .o file (-r option)
> nm func_02.o # names in .o file
▶ gcc automatically invokes 0000000000000000 T func_02
U puts
the linker when creating
# manually link to create combined .o
executables > ld -r func_01.o func_02.o \
▶ Can also manually play with -o funcs_12.o

linker: command 'ld' > nm funcs_12.o # names in .o file

0000000000000000 T func_01
▶ SO: Why is the Unix 0000000000000013 T func_02
linker called ’ld’? U puts

▶ Rarely use ld by hand: # can't create executable with

# undefined symbols and no main()
difficult to generate > ld func_01.o func_02.o \
-o executable.o
executables properly ld: warning: cannot find
entry symbol _start;
▶ gcc invokes ld with many defaulting to 00000000004000e8
func_01.o: In function 'func_01':
additional options / libraries func_01.c:(.text+0xc): 'puts' undefined
to create executables func_02.o: In function 'func_02':
func_02.c:(.text+0xc): 'puts' undefined
13
Symbol Resolution by the Linker
▶ Linker must resolve symbols when merging relocatable
objects (.o files)
▶ Only global stuff qualify as symbols: functions, global
variables. These can be seen / used from outside a C file
▶ Local variables inside functions will NOT have symbols
associated
▶ A few rules apply during symbol resolution
1. .o files can have undefined symbols but executables cannot
(for the most part) cannot
2. Symbols are classified as strong and weak; can only have one
strong definition but many weak definitions
3. Strong definitions are mostly named functions and global
variables with initial values
4. Weak definitions are mostly uninitialized global variables and
extern declarations for global variables, function prototypes

14
Exercise: Linking Trouble
Consider these two C files
// FILE: x_int.c // FILE: x_long.c
int x=0; // global vars long x; // global var
int y=0; // strongly defined // weakly defined
void x_to_neg8(){
void x_to_neg8(); // in different .o x = -8; // set global var
}
#include <stdio.h>
int main(){
x_to_neg8(); // set x only
printf("x: %d\n",x);
printf("y: %d\n",y);
return 0;
}

Compile + Run
> gcc -fcommon x_int.c x_long.c
/usr/bin/ld: Warning: ...
> ./[Link]
x: -8
y: -1 # WTF^M??
Why is this output unexpected?
What might be the cause? 15
Answers: Linking Trouble
▶ Two files define the sizes of global variable x differently
// FILE: x_long.c
long x; // uninitialized, weak symbol
// FILE: x_int.c
int x = 0; // initialized, strong symbol, prevails
int y = 0;
▶ Linker warns of this during compilation (see below)
> gcc -fcommon x_int.c x_long.c
/usr/bin/ld: Warning: alignment 4 of symbol 'x'
in /tmp/ccs1zLtj.o is smaller than 8 in /tmp/ccc7ZX9Q.o
▶ Variable y in x_int.c, adjacent to 4-byte x in memory
▶ Function void x_to_neg8() is in x_long.c
▶ Writes 8 bytes to location x clobbering y
INITIAL MEMORY
| GLOBALS | #2044 | y | 0 | 0x00000000 |
| | #2040 | x | 0 | 0x00000000 |

movq $-8, 2040 # 8-byte write for a long

| GLOBALS | #2044 | y | -1 | 0xFFFFFFFF
| | #2040 | x | -8 | 0xFFFFFFF8
▶ Message: Global variables are dangerous in linking (and for
code design in general) [but you knew that already]
16
Version Note
GCC Version 10 (Rel May 7, 2020) prevents global variable linking
problems better by NOT mapping uninitialized C vars to
“Common” (weak) symbols.
GCC now defaults to -fno-common. As a result, global variable
accesses are more efficient on various targets. In C, global vari-
ables with multiple tentative definitions now result in linker
errors. With -fcommon such definitions are silently merged dur-
ing linking.
– GCC 10 Release Series, Changes, New Features, and Fixes
> gcc --version
gcc (GCC) 10.2.0
vvvvvvvv
> gcc x_long.c x_int.c > gcc -fcommon x_long.c x_int.c
/usr/bin/ld: /tmp/ccbEBDOn.o: /usr/bin/ld: warning:
multiple definition of 'x'; size of symbol 'x' changed from 8
collect2: error: ld returned in /tmp/ccSWBZ.o to 4 in /tmp/ccENzS.o
1 exit status

> file [Link] > file [Link]

[Link]: cannot open '[Link]' [Link]: ELF 64-bit LSB pie executable
(No such file or directory)
17
The Value of Headers and extern declarations
▶ Headers (.h) declare global ▶ Proper use of headers allow
symbols for all C files that compiler to warn of
will use them conflicting definitions
// FILE: x_main.c
▶ May declare external #include "x_to_neg8.h"
variables which are defined int x = 0; // !!!
...
in another file
// FILE: x_to_neg8.h > gcc -c x_main_bad.c
extern long x; x_main_bad.c:4:5: error:
void x_to_neg8(); conflicting types for 'x'
------------------------- int x = 0; // !!!
// FILE: x_to_neg8.c ^
#include "x_to_neg8.h" x_to_neg8.h:7:13: note:
long x; // actual global var previous declaration of
void x_to_neg8(){ 'x' was here
x = -8; extern long x;
} ^
-------------------------
// FILE: x_main.c ▶ Without using .h header
#include "x_to_neg8.h"
// there will be an x var
files, compiler can’t help as
// and x_to_neg8() func much
...
18
Loading ELF: Stored Program becomes Running Process
▶ Loader maps ELF file Text/Globals into virtual memory
▶ Loader maps Stack/Heap into virtual memory
Virtual Memory of Process

Memory
Map

19
Linker and Loader
Traditional: Static Linking Modern: Dynamic Linking
▶ Linker merges .o files to ▶ Linker merges .o files to
create executable create executable
▶ All global symbols must be ▶ Global symbols from
resolved: copy text for Dynamic Libraries are left
functions into the executable Undefined (U)
from libraries ▶ Loader copies executable
▶ Loader copies executable into memory, sets %rip but..
into memory, sets %rip to ▶ Creates a virtual memory
first instruction address, map to definitions for library
notifies OS to schedule it for functions dynamically
execution linking to definitions
▶ All code/data for running ▶ Code for running program is
program is in its own spread across its memory
memory image image and shared libraries
20
gcc: Statically vs Dynamically Linked Executables
▶ By default gcc produces ’mixed’ executables
▶ Use as many dynamic libraries (.so) as possible
▶ Use a static version (.a) of library ONLY if no dynamic version
is available
▶ With the -static option, use all static libraries
▶ Note the differences reported by the file command below
> cat hello.c
#include <stdio.h>
int main(int argc, char *argv[]){
printf("Hello world! I'm a program\n");
return 0;
}

# compile static dynamically linked vs statically linked

> gcc -o hello_dynamic hello.c
> gcc -o hello_static hello.c -static

# examine file types

> file hello_dynamic
hello_dynamic: ELF 64-bit LSB shared object, x86-64, dynamically linked,
interpreter /lib64/[Link].2

> file hello_static

hello_static: ELF 64-bit LSB executable, x86-64, statically linked
21
Exercise: Static/Dynamic Program Sizes

▶ Examine file sizes of two programs below reported by du

▶ Which program is bigger on disk in number of bytes?
▶ Why is there a size difference?
# compile static dynamically linked vs statically linked
> cat hello.c
#include <stdio.h>
int main(int argc, char *argv[]){
printf("Hello world! I'm a program\n");
return 0;
}

> gcc -o hello_dynamic hello.c

> gcc -o hello_static hello.c -static

# examine size of executables in bytes

> du -b hello_*
9664 hello_dynamic
721424 hello_static

22
Answers: Static/Dynamic Program Sizes

# examine size of executables in bytes # examine symbols/functions

> du -b hello_* # in static/dynamic executables
9664 hello_dynamic # 9,664 bytes
721424 hello_static # 721,424 bytes > nm hello_static
...
▶ All libc.a functions needed 00000000004009dd T main
# T: defined "strong" symbol
(printf/puts/malloc/etc.) ...
copied into statically linked 0000000000408460 W puts
# W: defined "weak" symbol
version ...
▶ Dynamically linked version > nm hello_dynamic
has undefined references to ...
000000000000064a T main
functions like puts() which # T: defined "strong" symbol
will be resolved at load/run ...
U puts@@GLIBC_2.2.5
time # U: undefined
# Thank you Mario, but your function
# is in a different file

23
Libraries Required at Load/Runtime

▶ Most executables know ahead of time which dynamic libraries

will be needed at run time
▶ Can examine this with the ldd command: print shared object
dependencies
> gcc -o hello_dynamic hello.c
> gcc -o hello_static hello.c -static

# examine which libraries will be dynamically linked

# compile static dynamically linked vs statically linked

> ldd hello_static

not a dynamic executable

> ldd hello_dynamic

[Link].1 (0x00007ffe9b0fb000)
[Link].6 => /usr/lib/[Link].6 (0x00007f6a8c295000) #printf!
/lib64/[Link].2 =>
/usr/lib64/[Link].2 (0x00007f6a8c84e000)

24
Linking Against Standard Libraries
▶ At link time, linker must know about library dependencies
▶ gcc option -l will link against a library
> gcc do_math.c -lm # link to math library
> gcc do_pthreads.c -lpthread # link to threads library
▶ Default Convention: -lmystuff tries linking files
▶ [Link] (dynamic lib) THEN
▶ libmystuff.a (static lib)
▶ Force use of ONLY static libraries with -static option
▶ GCC always links libc (unless using -nostdlib)
▶ Compiler/Linker searches known directories for headers and
libraries
> gcc -v do_math.c -lm # -v: verbose output
...
#include <...> search starts here:
/usr/lib/gcc/x86_64-pc-linux-gnu/7.2.1/include
/usr/local/include
/usr/lib/gcc/x86_64-pc-linux-gnu/7.2.1/include-fixed
/usr/include
...
LIBRARY_PATH=/lib/:/usr/lib/:...
25
Creating/Linking Statically Linked Libraries
▶ Statically Linked Libraries
are archives with .a > gcc -g -Wall -c tree.c
> gcc -g -Wall -c array.c
extension > gcc -g -Wall -c list.c
▶ Traditional form of program > gcc -g -Wall -c util.c
libraries, comprised of a # create archive with ar
bunch of .o files > ar rcs libds_search.a \
tree.o array.o list.o util.o
▶ Utility ar allows creation,
modification, inspection of > file libds_search.a
.a files libds_search.a: current ar archive

▶ Most systems include # show .o files in archive

/lib/libc.a to allow > ar t libds_search.a
tree.o array.o list.o util.o
creation statically linked
programs > ar t /lib/libc.a | grep printf.o
vfprintf.o vprintf.o reg-printf.o
▶ System .a archives are fprintf.o printf.o snprintf.o
identical in structure to ...
user-created libraries
26
Linking Against User Libraries
▶ When header files and libraries are NOT in a “standard”
location, linker/loader will not find them by default
> ls ds_search_static/
libds_search.a
ds_search.h

# PROBLEM 1
> gcc do_search.c -lds_search
do_search.c:8:10: fatal error:
ds_search.h: No such file or directory # can't find header
#include "ds_search.h"
^~~~~~~~~~~~~
compilation terminated.

# PROBLEM 2
> gcc do_search.c -lds_search ...
/usr/bin/ld: cannot find -lds_search # can't find library
collect2: error: ld returned 1 exit status
▶ Compilers have options to resolve these two problems

27
Directing Compiler to non-standard Locations

> ls ds_search_static/
libds_search.a
ds_search.h

# PROBLEM 1
# Use -I to give "includes" directory with header
> gcc do_search.c -lds_search \
-I ds_search_static/ # header directory for ds_search.h
/usr/bin/ld: cannot find -lds_search
collect2: error: ld returned 1 exit status

# PROBLEM 2
# Use -L to add a directory to search for libraries
> gcc do_search.c -lds_search \
-I ds_search_static/ # header directory for ds_search.h
-L ds_search_static/ # library directory with libds_search.a
> file [Link]

[Link]: ELF 64-bit LSB shared object, x86-64

28
— END SPRING 2023 CONTENT —

The remaining slides are informative but optional. Their content

will not be part of the SPRING 2022 final exam.

29
Creating Dynamic Libaries

▶ Dynamically Libraries are > gcc -g -Wall -fpic -c tree.c

> gcc -g -Wall -fpic -c array.c
shared objects with .so > gcc -g -Wall -fpic -c list.c
> gcc -g -Wall -fpic -c util.c
extension (or .dll if you are
a Windows user) # create shared object with gcc
> gcc -shared -o libds_search.so \
▶ Created by invoking tree.o array.o list.o util.o
compiler linker with
appropriate options > file libds_search.so
libds_search.so: ELF 64-bit LSB
▶ Compile option fPIC for shared object, x86-64, ...
position independent
# show dependencies
code > ldd libds_search.so
▶ Link option -shared for a [Link].1 (0x00007ffce291e000)
shared object [Link].6 => /usr/lib/[Link].6 (0x00
/usr/lib64/[Link].2 (0x00
▶ Dynamic libraries may
depend on other dynamic
libraries
30
Exercise: A Dynamic Hitch
Consider the below hitch which hinders the convenience of
dynamic libraries
> gcc do_search.c -lds_search \
-I ds_search_dynamic/ \
-L ds_search_dynamic/

> ./[Link]
[Link]: error while loading shared libraries:
libds_search.so: cannot open shared object file:
No such file or directory

> ldd [Link]

[Link].1
libds_search.so => not found !!!!
[Link].6 => /usr/lib/[Link].6
/lib64/[Link].2 => /usr/lib64/[Link].2

▶ What went wrong?

▶ Thoughts on how to resolve?
▶ Why didn’t this happen in the statically linked case?
31
Answers: A Dynamic Hitch
▶ Compiler informed that libds_search.so was in a
non-standard directory
▶ Loader NOT informed of this
▶ Loader searched /lib/ and other places, didn’t find
libds_search.so gave up on loading the program
▶ Must inform loader of non-standard directories for libraries
with LD_LIBRARY_PATH
▶ An environment variable honored by loader, directories to
search aside from standard locations
▶ Environment variables can be set in most shells and are looked
for by programs to modify their behaviour
▶ Default command shell on many Unixes is bash with env’t var
syntax export VAR=some_value
▶ Often set vars in initialization files like .bashrc or
.bash_init in your home directory
export PAGER=less # a better 'more'
export EDITOR=emacs # major improvement
export BROWSER=google-chrome # hog my RAM!
32
Answers: A Dynamic Hitch
Below is a complete session which fixes the loading problem
> ./[Link]
[Link]: error while loading shared libraries:
libds_search.so: cannot open shared object file:
No such file or directory

> export LD_LIBRARY_PATH="ds_search_dynamic"

> ldd [Link]

[Link].1
libds_search.so => ds_search_dynamic/libds_search.so :-)
[Link].6 => /usr/lib/[Link].6
/lib64/[Link].2 => /usr/lib64/[Link].2

> ./[Link]
Searching 2048 elem array, 10 repeats: 1.6470e-01 seconds
If distributing a .so, either
▶ Install it in a standard location like /usr/lib/ (admin access)
▶ Notify users of library to adjust LD_LIBRARY_PATH

33
Exercise: Dynamic Loading Tricks

Consider the following strange sesssion

> gcc hello.c
> ./[Link]
Hello World!
My favorite int is 32 and float is 1.234000

> gcc -shared -fPIC -Wl,-soname -Wl,libsamy_printf.so \

-o libsamy_printf.so samy_printf.c -ldl
> export LD_PRELOAD=$PWD/libsamy_printf.so

> ./[Link]
Hello World!
... but most of all, Samy is my hero.
My favorite int is 32 and float is 1.234000
... but most of all, Samy is my hero.
Why would compiling another piece of code change the behavior of
an already compiled program?

34
Answers: Dynamic Loading Tricks
▶ One can interpose library calls: ask dynamic loader to link a
function to a different definition
▶ Only possible with dynamic linking but a powerful technique
▶ In this case, re-define printf(), similar tricks by valgrind
for malloc() / free()
> gcc hello.c
> [Link]
> ldd [Link]
[Link].1
[Link].6 => /usr/lib/[Link].6
/lib64/[Link].2 => /usr/lib64/[Link].2

> export LD_PRELOAD=$PWD/libsamy_printf.so

> ldd [Link]
[Link].1 (0x00007fff591d6000)
./libsamy/libsamy_printf.so !!!!
[Link].6 => /usr/lib/[Link].6
[Link].2 => /usr/lib/[Link].2
/lib64/[Link].2 => /usr/lib64/[Link].2

35
Valgrind and Your own Malloc

▶ Valgrind replaces normal malloc() / free() with its own

version which is slower but allows error checking
▶ Uses dynamic loading tricks for this so you don’t need to
recompile your program
▶ If you complete el_malloc.c, you could extend it to a full
allocator (would need realloc(), use of sbrk() for heap
management, define malloc() / free())
▶ Use library interposition with LD_PRELOAD dynamically link
in your own programs
▶ Brief Instructions in the GNU libc manual on how to do this

36
Recall: Globals in Assembly

▶ A long time ago in an assembly project far, far away…

▶ Used a weird syntax to access global variables in assembly
movl SOME_GLOBAL_VAR(%rip), %edi
▶ Load is based on an offset from the Instruction Pointer rip
▶ Similarly, will often see in decompiled code the following
> objdump -d clock_update.o
2f2: e8 00 00 00 00 callq 2f7 <set_tod_from_secs>
...
31c: e8 00 00 00 00 callq 321 <set_display_from_tod>
▶ Why are both call instructions e8 00 00 ...?
▶ Both these deserve some explanation

37
Relocation and PC-Relative Address
▶ Linker merges global symbols from multiple .o files into single
output sections
▶ Functions into single .text
▶ Global vars into .data / .bss sections
▶ Historically, linker would just assign a virtual memory address
to each symbol / section (simple, easy to implement)
▶ Problem: forces program to be loaded at a fixed virtual
memory address, decreases options available to
loader/dynamic linker
▶ gcc now generates relocatable code by default: all
instructions must be independent of exact memory position
where program is loaded (trickier but flexible/safer)
▶ Loader guarantees: distance between sections is constant
▶ .text might be loaded at 0x9000 or at 0x9100 by OS
▶ .text and .data always 0x1000 bytes apart
▶ .text loaded contiguously at some start address
▶ Addressing relative to PC allows flexibility in code placement,
requires extra linker work
38
Relocation Entries
▶ ELF files contain relocation entries, spots with unknown
address that must be “filled in” at link time
▶ Relocation entries are created for function calls and global
variable use in ELF sections
▶ .[Link]: Relocation info for .text section
▶ .[Link]: Relocation info for .data section
▶ Compiler notes byte locations that require insertion of info at
link time
▶ Position where the fix is needed (“fill this in”)
▶ What symbol is needed
▶ Extra arithmetic stuff
▶ Interested in two types of relocation entries
▶ R_X86_64_PC32: insert address of something relative to rip;
used for global vars, functions in same C file
▶ R_X86_64_PLT32: insert address of a procedure linkage
table entry; used for functions not in same C file
▶ Linker inserts addresses at positions indicated by relocation
entries
39
Example of Relocation Entries
ORIGINAL SOURCE CODE RELOCATION ENTRIES
// file: glob.c > readelf -r glob.o
int glob_arr[128]; Off Type Sym + Addend
void glob_func1(int scale){ ... } 66 R_X86_64_PC32 glob_func1 - 4
83 R_X86_64_PC32 glob_arr - 4
void glob_func2(int scale, inty[]) e0 R_X86_64_PLT32 printf - 4
{
glob_func1(scale); // 66 Above byte positions must have
for(int i=0; i<128; i++){ addresses inserted by the linker
glob_arr[i] += y[i]; // 83 at link time. Currently those
printf("%d\n",glob_arr[i]); // e0 position have 00's as placeholders
} until the linker fills them in.
}

RELEVANT DISASSEMBLED CODE

> objdump -dx glob.o
0000000000000051 <glob_func2>:
65: e8 00 00 00 00 callq 6a # call function
^^ 66: R_X86_64_PC32 glob_func1-0x4 # in same file

80: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # use global var

^^ 83: R_X86_64_PC32 glob_arr-0x4 # in same file

df: e8 00 00 00 00 callq e4 # call function

^^ e0: R_X86_64_PLT32 printf-0x4 # in another file
40
End Result: Relocatable Code
▶ Most ELF programs have no load time constant addresses
▶ All functions and variables (locals/globals) are referenced
relative to the rip (program counter)
▶ ELF image can be loaded at an starting Virtual Memory
Address and run successfully
▶ Will notice memory address of functions/variables change
from run to run but the difference between locations is
constant
> gcc -o glob_main glob_main.c glob.c
> ./glob_main > ./glob_main
ADDRESSES ADDRESSES
0x5637e3bc6060: glob_arr variable 0x5642d3feb060: glob_arr variable
0x5637e3bc3159: main func 0x5642d3fe8159: main func
0x5637e3bc32aa: glob_func1 0x5642d3fe82aa: glob_func1
0x5637e3bc32fa: glob_func2 0x5642d3fe82fa: glob_func2

ADDRESS DIFFERENCES ADDRESS DIFFERENCES

2f07: glob_arr - main 2f07: glob_arr - main
2db6: glob_arr - glob_func1 2db6: glob_arr - glob_func1
151: glob_func1 - main 151: glob_func1 - main
50: glob_func2 - glob_func1 50: glob_func2 - glob_func1
41
Wait, what about that PLT thing?
void main(){
▶ Minor performance hit for ...
dynamically linked libraries, printf(...); // compiled to call_printf()
use of program linkage ...
}
table (PLT) and global
offset table (GOT) void *GOT[]; // has addresses of funcs

▶ First call to printf() is void call_printf(...){

expensive when it is int (*func_ptr) = GOT[3]; // get func ptr
func_ptr(...); // call func
dynamically linked }
▶ Dynamic linker delays void link_printf(...){ // 1st call only
determining address of void *printf_addr = // use linker to
printf() until it is called dlsym("printf"); // find printf
GOT[3] = printf_addr; // save ptr later
▶ Pseudo-code representing printf_addr(...); // call printf
}
gcc / Linux approach to
the right: clever use of 1 void *GOT[] = { // global table
level of indirection and GOT ...
&link_printf, // for first printf call
table of function pointers ..
}
42
Exercise: Separate Compilation Time

▶ Mack is building a large application

▶ Has a main_func.c and func_01.c, func_02.c ... that
define application, up to func_20.c
▶ During build process notices that it takes about 10s for to
compile each C file and 20s to link the C files
▶ After editing files to add features, Mack usually compiles to
project like this
> gcc -o main_func *.c
▶ Estimate his typical build time in seconds
▶ Suggest a way that he might reduce his build time if he has
edited only a small number of files

43
Answers: Separate Compilation Time

Total Build Time gcc -o main_func *.c

Item Example Build Tot
Library C files func_01.c 20 x 10s 200s
Main C file main_func.c 1 x 10s 10s
Linking all .o files 1 x 20s 20s
Total Time ~ 4min 22 steps 230s

▶ Explicitly recompiling all C files to object code despite many

not changing
▶ Spends valuable human time waiting to redo the same task as
has been done many before

44
Answers: Separate Compilation Time
Exploit Separate Compilation
▶ Assume already compiled all files, have func_01.o,
func_02.o
▶ Edit func_08.c to add a new feature
▶ Don’t recompile C files that haven’t changed
▶ Compile like this
> gcc -c func_08.c
> gcc -o main_func *.o

Item Example Build Time

Library .o files func_01.o 19 x 0s 0s
Main .o file main_func.o 1 x 0s 0s
Changed .c files func_08.c 1 x 10s 10s
Linking all .o files 1 x 20s 20s
Total Time ~ 30 seconds 2 steps 30s

45
Build Systems Exploit Separate Compilation
▶ Build Systems like make / Makefile exploit separate
compilation
▶ Build system establishes a dependency structure
▶ Targets are usually files to create
▶ Dependencies are other files/targets that must be up to date
to create a given target
▶ Only rebuild a target if a dependency changes
# Typical Makefile gives targets, dependencies,
# commands to create target using dependencies
# TARGET : DEPENDENCIES
# COMMANDS / ACTIONS

main_func : main_func.o func_01.o func_02.o

gcc -o main_funcs main_func.o func_01.o func_02.o

main_func.o : main_func.c
gcc -c main_funcs.c

func_01.o : func_01.c
gcc -c funcs_01.c
46
Example Builds from big-compile/
> make clean
rm -f *.o main_func

# first compiles, no object files built, build everything

> make main_func
gcc -c main_func.c
gcc -c func_01.c
gcc -c func_02.c
...
gcc -c func_20.c
gcc -o main_func main_func.o func_01.o func_02.o...

# edit func_08.c

# 1 file changed, recompile it and re-link

> make main_func
gcc -c func_08.c # ONLY NEED TO RECOMPILE THIS
gcc -o main_func main_func.o func_01.o func_02.o...

# no edits, no need to rebuild

> make main_func
make: Nothing to be done for 'main_func'.
47
Exercise: Initialized vs Uninitialized Data Matters
Some interesting engineering tricks are baked into the ELF file
format. Observe:
// FILE: big_data.c // FILE: big_bss.c
long arr[20000] = {1,2,3}; long arr[20000] = {};
int main(){ int main(){
for(int i=0; i<1024; i++){ for(int i=0; i<1024; i++){
arr[i] = i; arr[i] = i;
} }
return 0; return 0;
} }
> gcc -c big_data.c # compile to object
> du -b big_data.o # print number of bytes
161384 big_data.o

> gcc -c big_bss.c # compile to object

> du -b big_bss.o # print number of bytes
1384 big_bss.o

▶ What is the difference between the two files above?

▶ Why is there such a size difference in the object files

48
Answers: Initialized vs Uninitialized Data Matters
▶ ELF .data section tracks global variables that is initialized
with non-zero values
▶ Must record every value in global variable so it can be
properly set when loaded to run
▶ big_data.o will have a large .data section as the line
long arr[20000] = {1,2,3};
initializes the first few array values, rest will be 0
> readelf -S big_data.o
There are 12 section headers, starting at offset 0x27368:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
...
[ 3] .data PROGBITS 0000000000000000 00000080 <--
----> 0000000000027100 0000000000000000 WA 0 0 32
[ 4] .bss NOBITS 0000000000000000 00027180 <--
0000000000000000 0000000000000000 WA 0 0 1
...
▶ 0x27100 = 160000 bytes: entire arr array stored in file
49
Answers: Initialized vs Uninitialized Data Matters
▶ ELF .bss section tracks global variables that are not
initialized or initialized to all 0’s
▶ No specific values need be recorded, just instructions on how
much space to allocate on starting the program
▶ big_bss.o will have a miniscule .data section as the line
long arr[20000] = {};
initializes to all 0’s so .bss section
> readelf -S big_bss.o
There are 12 section headers, starting at offset 0x268:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
...
[ 3] .data PROGBITS 0000000000000000 0000007f
0000000000000000 0000000000000000 WA 0 0 1
[ 4] .bss NOBITS 0000000000000000 00000080 <--
----> 0000000000027100 0000000000000000 WA 0 0 32
[ 5] .comment PROGBITS 0000000000000000 00000080 <--
0000000000000012 0000000000000001 MS 0 0 1
...
▶ arr array NOT stored in file, significantly smaller .o file
50