Sections, Symbols, and Relocations in an ELF Object File

A compiler that emitted only machine code would leave the linker with an impossible job. The code contains holes: a call to a function defined in another file, an address of a global variable, a reference to a string constant whose final location is not yet known. Nothing in a flat byte stream tells the linker where those holes are, how wide they are, or what should eventually be written into them. Nor does a flat stream say which bytes are code and which are read-only data, so the operating system could not give the two different page permissions.

The ELF object format exists to carry exactly that missing information. It is a container with four interlocking parts: a section header table that describes byte ranges, a symbol table that names things, a string table that holds the names, and relocation entries that mark the holes. Everything a static linker does follows from reading those four structures.

A file is described by offsets, not by contents

The ELF header is 64 bytes on a 64-bit target and holds, among other fields, the file’s class, its byte order, the address of the section header table, the number of entries in that table, and the index of the entry holding section names. The section header table itself is an array of 64-byte entries, one per section. Each entry records a type, a set of flags, a virtual address, a file offset, a size, an alignment, and two indices named sh_link and sh_info whose meaning depends on the section type.

The important structural point is that sections do not contain each other and are not necessarily in any particular order in the file. They are byte ranges identified by offset and length, and the linker treats them as such. A section’s type says how to interpret it: SHT_PROGBITS is arbitrary bytes with program-defined meaning, SHT_NOBITS occupies memory but no file space (this is how .bss costs nothing on disk), SHT_SYMTAB is an array of symbol records, SHT_STRTAB is a string table, SHT_RELA is an array of relocation records with explicit addends.

Two of those types carry cross-references. A symbol table’s sh_link is the section index of the string table holding its names, and its sh_info is the index of the first non-local symbol. A relocation section’s sh_link is the symbol table it refers to, and its sh_info is the section being patched. Those links are the reason a linker can process an object file without guessing: every structure announces what it depends on.

sh_info on the symbol table deserves attention because it encodes an ordering requirement. All local symbols must come before all global and weak ones, so that the boundary is a single integer rather than a scan. This lets a linker renumber symbols when it combines several objects without touching the local ones, whose indices are private to their own file.

What a symbol record actually stores

A 64-bit symbol entry is 24 bytes: a 32-bit offset into the string table, an 8-bit binding, an 8-bit type, an 8-bit visibility, a 16-bit section index, an 8-byte value, and an 8-byte size. The name is not in the record; the record holds an offset into the string table, and the name is the NUL-terminated bytes starting there. Keeping names out of the fixed-size records means symbols with long names cost nothing extra per entry, and identical names can be shared by pointing at the same offset.

The binding field separates STB_LOCAL from STB_GLOBAL and STB_WEAK. Local symbols are visible only inside their own object and are not candidates for resolution against other objects; they exist mainly for debuggers and for relocation entries that need to name a section rather than a global entity. Global symbols are the ones that participate in the link-wide namespace, and weak symbols are the ones that may be overridden without a duplicate-definition error.

The type field distinguishes objects from functions and from a few specialised kinds. STT_OBJECT is a data object, STT_FUNC is executable code, STT_TLS is thread-local storage, and STT_SECTION is a synthetic symbol representing a whole section, used when a relocation must refer to a section plus an offset. The distinction matters for the dynamic linker, which treats function symbols and object symbols differently when resolving and when building address ranges.

The st_value field means different things depending on the file’s type. In a relocatable object (ET_REL, the output of a compiler) it is an offset from the start of the section named by st_shndx. In a linked executable or shared object it is a virtual address, because by then the section layout is fixed. A linker converting one into the other is doing the central act of linking: turning section-relative offsets into process-wide addresses.

Relocation entries mark the holes

A relocation record says: at offset r_offset within the target section, apply relocation type r_type to the value of symbol r_sym, and the result should equal S + A under the arithmetic that type defines, where S is the symbol’s final address and A is an addend. The addend is the part the compiler already knows, such as the offset of a field inside a struct.

ELF has two encodings. SHT_REL entries store no addend, and the addend is whatever value currently sits at the patch site; this was workable on machines with simple instruction encodings but is awkward when the field to be patched is not contiguous with the instruction. SHT_RELA entries carry a 64-bit addend in the record, making the patch site pure output. x86-64 uses RELA exclusively, and a RELA entry is 24 bytes: offset, symbol-and-type packed into one 64-bit word, and addend.

Packing the symbol index and the type into one word is a space optimisation with a real consequence: the symbol index gets the high 32 bits and the type the low 32, so a section can refer to at most about four billion symbols and there are effectively no limits on type numbers. Readers extract them with a shift and a mask rather than two loads.

#include <elf.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
    if (argc != 2) return 1;
    FILE *f = fopen(argv[1], "rb");
    if (!f) return 1;

    Elf64_Ehdr eh;
    if (fread(&eh, sizeof eh, 1, f) != 1) return 1;
    if (memcmp(eh.e_ident, ELFMAG, SELFMAG) != 0) return 1;

    Elf64_Shdr *sh = malloc(eh.e_shnum * sizeof *sh);
    fseek(f, (long)eh.e_shoff, SEEK_SET);
    fread(sh, sizeof *sh, eh.e_shnum, f);

    /* Section names live in the section named by e_shstrndx. */
    Elf64_Shdr *strsh = &sh[eh.e_shstrndx];
    char *names = malloc(strsh->sh_size);
    fseek(f, (long)strsh->sh_offset, SEEK_SET);
    fread(names, 1, strsh->sh_size, f);

    for (int i = 0; i < eh.e_shnum; i++)
        printf("%-20s type=%u off=%llu size=%llu\n",
               names + sh[i].sh_name, sh[i].sh_type,
               (unsigned long long)sh[i].sh_offset,
               (unsigned long long)sh[i].sh_size);

    free(names); free(sh); fclose(f);
    return 0;
}

The listing this produces is the whole map of the file: which bytes are instructions, which are read-only constants, which are writable data, which are symbol records, which are relocations. A linker’s first act on any input is to build exactly this map, plus an index from section index to output section.

Where the naive format breaks

Several details in the format are responses to failures of simpler designs.

Names must live in a string table rather than inline because the linker rewrites symbol tables when it combines objects, and fixed-size records make that rewrite a simple array operation. Section names are indirected the same way, through a dedicated string table named by e_shstrndx, so every entry in the section header table is a fixed-size record holding an offset rather than a variable-length name. Nothing in the load path depends on that table: the kernel reads the program header table, so an executable whose section headers have been removed still runs.

SHT_NOBITS exists because zero-filled data is the common case for large arrays, and storing megabytes of zeros in every object file would be wasteful. The linker allocates address space for it and the loader maps anonymous zero pages; no file bytes are involved. The cost is that .bss cannot be initialised with anything but zero, and a compiler that wants a non-zero initial value must place the object in .data instead.

Common symbols, marked with the special section index SHN_COMMON, are a legacy of pre-standard C: a tentative definition such as int x; at file scope could be emitted as common, and the linker would allocate storage for the largest declaration and merge all references. Modern compilers default to -fno-common, emitting such definitions into .bss as ordinary globals, which turns a silent merge into a duplicate-symbol error. The trade is deliberate: an error at link time is easier to diagnose than storage silently sized by the wrong declaration.

Alignment is per-section and can be large. A section whose sh_addralign is 64 must start at a 64-byte boundary in the output, and the linker must insert padding between sections to satisfy it. Since sections also need distinct page permissions, the linker groups them by permission and rounds each group up to a page boundary, which is why the file layout of an executable has visible gaps between text and data.

What the linker needs that a single object cannot supply

One object file is self-contained but incomplete. Its symbol table lists definitions and undefined references; the undefined ones carry section index SHN_UNDEF and a zero value, and only the link-wide symbol resolution described in Static Archives and Link Order can fill them in. Its relocation entries point at those symbols, and their arithmetic — the different formulas for absolute and program-counter-relative patches — is the subject of Relocation Arithmetic.

The format also deliberately does not say how big the final address space is. That is decided at link time for an executable, or at load time for a shared object, and the same relocation record must work in both cases. That requirement is what forces the distinction between absolute and position-independent addressing, taken up in Position-Independent Code and the Global Offset Table.