GNU ld's output section layout is determined by a linker script,which can be either internal (default) or external (specified with-T or -dT). Within the linker script,SECTIONS commands define how input sections are mapped intooutput sections.

Input sections not explicitly placed by SECTIONScommands are termed "orphansections".

Orphan sections are sections present in the input files which are notexplicitly placed into the output file by the linker script. The linkerwill still copy these sections into the output file by either finding,or creating a suitable output section in which to place the orphanedinput section.

GNU ld's default behavior is to create output sections to hold theseorphan sections and insert these output sections into appropriateplaces.

Orphan section placement is crucial because GNU ld's built-in linkerscripts, while understanding common sections like.text/.rodata/.data, are unawareof custom sections. These custom sections should still be included inthe final output file.

• Grouping: Orphan input sections are grouped into orphan outputsections that share the same name.
• Placement: These grouped orphan output sections are then insertedinto the output sections defined in the linker script. They are placednear similar sections to minimize the number of PT_LOADsegments needed.

GNU ld's algorithm

GNU ld's orphan section placement algorithm is primarily specifiedwithin ld/ldlang.c:lang_place_orphans andld/ldelf.c:ldelf_place_orphan.lang_place_orphans is a linker pass that is betweenINSERT processing and SHF_MERGE sectionmerging.

The algorithm utilizes a structure (orphan_save) toassociate desired BFD flags (e.g., SEC_ALLOC, SEC_LOAD)with specific section names (e.g., .text, .rodata) and areference to the last associated output section.

For each output section that holds orphan sections:

• GNU ld identifies the matching orphan_save elementbased on the section's flags.
• If an associated output section exists related theorphan_save element, the orphan section is placed after it.The associated output section is initialized to the specific sectionnames (e.g., .text, .rodata), if present.
• Otherwise, heuristics are applied to place the orphan section aftera similar existing section. For example:
  • .rodata-like sections follow .text-like sections.
  • .tdata-like sections follow .data-like sections.
  • .sdata-like sections follow .data-like sections.
  • .data-like sections can follow .rodata-like sections.
• The associated output section is replaced with the new outputsection. The next orphan output section of similar flags will be placedafter the current output section.

For example, custom code section mytext (withSHF_ALLOC | SHF_EXECINSTR) would typically be placed after.text, and custom data section mydata (withSHF_ALLOC | SHF_WRITE) after .data.

1
2
3
4
5
6
7
8
9
10
11

static struct orphan_save hold[] = {
    { ".text", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_READONLY | SEC_CODE, 0, 0, 0, 0 },
    { ".rodata", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_READONLY | SEC_DATA, 0, 0, 0, 0 },
    { ".tdata", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_DATA | SEC_THREAD_LOCAL, 0, 0, 0, 0 },
    { ".data", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_DATA, 0, 0, 0, 0 },
    { ".bss", SEC_ALLOC, 0, 0, 0, 0 },
    { 0, SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_READONLY | SEC_DATA, 0, 0, 0, 0 },
    { ".interp", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_READONLY | SEC_DATA, 0, 0, 0, 0 },
    { ".sdata", SEC_HAS_CONTENTS | SEC_ALLOC | SEC_LOAD | SEC_DATA | SEC_SMALL_DATA, 0, 0, 0, 0 },
    { ".comment", SEC_HAS_CONTENTS, 0, 0, 0, 0 },
};

For each orphan section, GNU ld maps it to the output section andfinds the orphan_save element with matching flags. If theassociated output section is not null, the orphan section will be placedafter that output section. Otherwise, the orphan section will be after asimilar section using a few heuristics, e.g.

• .rodata-like sections can be placed after .text-like sections.
• .tdata-like sections can be placed after .data-like sections.
• .sdata-like sections can be placed after .data-like sections
• .data-like sections can be placed after .rodata-like sections

Noteworthy details:

.interp and .rodata have the same BFDflags, but they are anchors for different sections.SHT_NOTE sections go after .interp, whileother read-only sections go after .rodata.

lld's algorithm

The LLVM linker lld implements a large subset of the GNU ld linkerscript. However, due to the lack of an official specification and thecomplexity of GNU ld, there can be subtle differences in behavior.

While lld strives to provide a similar linker script behavior, itoccasionally makes informed decisions to deviate where deemedbeneficial. We balance compatibility with practicality andinterpretability.

Users should be aware of these potential discrepancies whentransitioning from GNU ld to lld, especially when dealing with intricatelinker script features.

Rank-based sorting

lld assigns a rank to each output section, calculated using variousflags like RF_NOT_ALLOC, RF_EXEC, RF_RODATA, etc. Orphanoutput sections are then sorted by these ranks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

enum RankFlags {
  RF_NOT_ADDR_SET = 1 << 27,
  RF_NOT_ALLOC = 1 << 26,
  RF_PARTITION = 1 << 18, // Partition number (8 bits)
  RF_LARGE_ALT = 1 << 15,
  RF_WRITE = 1 << 14,
  RF_EXEC_WRITE = 1 << 13,
  RF_EXEC = 1 << 12,
  RF_RODATA = 1 << 11,
  RF_LARGE = 1 << 10,
  RF_NOT_RELRO = 1 << 9,
  RF_NOT_TLS = 1 << 8,
  RF_BSS = 1 << 7,
};

Finding the most similar section

For each orphan section, lld identifies the output section with themost similar rank. The similarity is determined by counting the numberof leading zeros in the XOR of the two ranks.

1
2
3
4
5
6
7
8
9
10

// We want to find how similar two ranks are.
// The more branches in getSectionRank that match, the more similar they are.
// Since each branch corresponds to a bit flag, we can just use
// countLeadingZeros.
static int getRankProximity(OutputSection *a, SectionCommand *b) {
  auto *osd = dyn_cast<OutputDesc>(b);
  return (osd && osd->osec.hasInputSections)
             ? llvm::countl_zero(a->sortRank ^ osd->osec.sortRank)
             : -1;
}

Placement decision

The orphan section is placed either before or after the most similarsection, based on a complex rule involving:

• The relative ranks of the orphan and similar section.
• The presence of PHDRS or MEMORY commands in the linker script.
• Scanning backward or forward through the script for suitableinsertion points.

In essence:

• If the orphan section's rank is lower than the similar section'srank, and no PHDRS/MEMORYcommands exist, it's placed before the similar section.
• Otherwise, it's placed after the similar section,potentially skipping symbol assignments or output sections without inputsections in the process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

auto isOutputSecWithInputSections = [](SectionCommand *cmd) {
  auto *osd = dyn_cast<OutputDesc>(cmd);
  return osd && osd->osec.hasInputSections;
};

// If i's rank is larger, the orphan section can be placed before i.
//
// However, don't do this if custom program headers are defined. Otherwise,
// adding the orphan to a previous segment can change its flags, for example,
// making a read-only segment writable. If memory regions are defined, an
// orphan section should continue the same region as the found section to
// better resemble the behavior of GNU ld.
bool mustAfter = script->hasPhdrsCommands() || !script->memoryRegions.empty();
if (cast<OutputDesc>(*i)->osec.sortRank <= sec->sortRank || mustAfter) {
  for (auto j = ++i; j != e; ++j) {
    if (!isOutputSecWithInputSections(*j))
      continue;
    if (getRankProximity(sec, *j) != proximity)
      break;
    i = j + 1;
  }
} else {
  for (; i != b; --i)
    if (isOutputSecWithInputSections(i[-1]))
      break;
}

// As a special case, if the orphan section is the last section, put
// it at the very end, past any other commands.
// This matches bfd's behavior and is convenient when the linker script fully
// specifies the start of the file, but doesn't care about the end (the non
// alloc sections for example).
if (std::find_if(i, e, isOutputSecWithInputSections) == e)
  return e;

while (i != e && shouldSkip(*i))
  ++i;
return i;

Special case: last section

If the orphan section happens to be the last one, it's placed at thevery end of the output, mimicking GNU ld's behavior for cases where thelinker script fully specifies the beginning but not the end of thefile.

Special case: skipping symbol assignments

It is common to surround an output section description withencapsulation symbols. lld has a special case to not place orphansbetween foo and a following symbol assignment.

Backward scan example:

1
2
3
4
5

begin_previous = .;
previous : { *(previous) } // Found output section with a backward scan
end_previous = .;          // We should place the orphan after instead of before this symbol assignment

similar : { *(similar) }   // The most similar section found by the first step

Forward scan example:

1
2
3
4

similar0 : { *(similar0) }
begin_similar1 = .;
similar1 : { *(similar1) } // The most similar section found by the first step
end_similar1 = .;          // We should place the orphan after instead of before this symbol assignment

However, an assignment to the location counter can serve as a barrierto stop the forward scan.

1
2
3
4
5
6
7

begin_previous = .;
previous : { *(previous) } // Found output section with a backward scan
end_previous = .;          // We should place the orphan after instead of before this symbol assignment
symbol = .;                // We conservatively assume any symbol as a probable "end" symbol.
. = ALIGN(CONSTANT(MAXPAGESIZE)); // Barrier

similar : { *(similar) }   // The most similar section found by the first step

Special case: initial location counter

In addition, if there is a location counter assignment before thefirst output section, orphan sections cannot be inserted before theinitial location counter assignment. This is to recognize the commonpattern that the initial location counter assignments specifies the loadaddress.

1
2
3

sym0 = .;
. = initial_location; // Initial assignment to DOT. Orphan sections cannot be inserted before here.
.text : {}            // First output section

Analysis

By employing this rank-based approach, lld provides an elegantimplementation that does not hard code specific section names (e.g.,.text/.rodata/.data). In GNU ld,if you rename special section names.text/.rodata/.data in the linkerscript, the output could become subtle different.

Portability

To maximize portability of linker scripts across different linkers,it's essential to establish clear boundaries for PT_LOAD segments. Thiscan be achieved by:

• Explicit alignment: Utilizing MAXPAGESIZE alignment todistinctly separate sections within the linker script.
• Anchoring sections: Ensuring that the first section in eachPT_LOAD segment includes at least one input section,preventing ambiguous placement decisions by the linker.

By adhering to these guidelines, you can reduce reliance onlinker-specific orphan section placement algorithms, promotingconsistency across GNU ld and lld.

Disabling orphan sections

For projects that require absolute control over section placement,GNU ld version 2.26 and later provides--orphan-handling=[place|warn|error|discard]. This allowsyou to choose how orphan sections are handled:

• place (default): The linker places orphan sections according to itsinternal algorithm.
• warn: The linker places orphan sections but also issues warnings foreach instance.
• error: The linker treats orphan sections as errors, preventing thelinking process from completing.
• discard: The linker discards orphan sections entirely.