[lld] Unsorted loadable program headers with `-Ttext=` argument

[pskrgag]

ELF spec say that program headers must be sorted by p_vaddr

Loadable segment entries in the program header table appear in ascending order,
sorted on the p_vaddr member

However it does not work if -Ttext argument is used.

Consider following example:

int main(void)
{
        while (1);
}

~/Documents/compiler_ws/lld
paskripkin > ~/Documents/git/llvm-project/build/bin/ld.lld -e main -Ttext=0x80000 test.o -o a.out

~/Documents/compiler_ws/lld
paskripkin > llvm-readelf -l a.out

Elf file type is EXEC (Executable file)
Entry point 0x800000
There are 5 program headers, starting at offset 64

Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  PHDR           0x000040 0x0000000000200040 0x0000000000200040 0x000118 0x000118 R   0x8
  LOAD           0x000000 0x0000000000200000 0x0000000000200000 0x000158 0x000158 R   0x1000
  LOAD           0x001000 0x0000000000080000 0x0000000000080000 0x000016 0x000016 R E 0x1000
  LOAD           0x001018 0x0000000000081018 0x0000000000081018 0x00003c 0x00003c R   0x1000
  GNU_STACK      0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW  0x0

 Section to Segment mapping:
  Segment Sections...
   00
   01
   02     .text
   03     .eh_frame
   04
   None   .comment .symtab .shstrtab .strtab

Note that first loadable segment has a p_vaddr less than the second one. (still reproduces on current master c50cba6).

Sort of analysis

The first loadable segment is the one that contains ELF header and program headers. It's added in Writer<ELFT>::createPhdrs.

    // Add the headers. We will remove them if they don't fit.
    // In the other partitions the headers are ordinary sections, so they don't
    // need to be added here.
    if (isMain) {
      load = addHdr(PT_LOAD, flags);
      load->add(ctx.out.elfHeader.get());
      load->add(ctx.out.programHeaders.get());
    }

In normal case it gets merged into some of other segments because of the following code

    bool sameLMARegion =
        load && !sec->lmaExpr && sec->lmaRegion == load->firstSec->lmaRegion;
    if (load && sec != relroEnd &&
        sec->memRegion == load->firstSec->memRegion &&
        (sameLMARegion || load->lastSec == ctx.out.programHeaders.get()) &&
        (ctx.script->hasSectionsCommand || sec->type == SHT_NOBITS ||
         load->lastSec->type != SHT_NOBITS)) {
      load->p_flags |= newFlags;
    } else {
      load = addHdr(PT_LOAD, newFlags);
      flags = newFlags;
    }

However if -Ttext is specified, predicate above may fail and new segment will be inserted. Then during LinkerScript::assignAddresses, first PT_LOAD segment gets assigned to ctx.target->getImageBase(), which may be far from the base of text (IIUC lld starts calculating p_vaddrs from the base passed in -T).

Note

This is not a synthetic example. It was observed in real life with very strict elf loader.

[pskrgag]

CC @MaskRay I guess?

[llvmbot]

@llvm/issue-subscribers-bug

Author: Pavel Skripkin (pskrgag)

ELF spec say that program headers must be sorted by `p_vaddr`

> Loadable segment entries in the program header table appear in ascending order,
> sorted on the p_vaddr member

However it does not work if -Ttext argument is used.

Consider following example:

int main(void)
{
        while (1);
}

~/Documents/compiler_ws/lld
paskripkin > ~/Documents/git/llvm-project/build/bin/ld.lld -e main -Ttext=0x800000 test.o -o a.out

~/Documents/compiler_ws/lld
paskripkin > llvm-readelf -l a.out

Elf file type is EXEC (Executable file)
Entry point 0x800000
There are 5 program headers, starting at offset 64

Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  PHDR           0x000040 0x0000000000200040 0x0000000000200040 0x000118 0x000118 R   0x8
  LOAD           0x000000 0x0000000000200000 0x0000000000200000 0x000158 0x000158 R   0x1000
  LOAD           0x001000 0x0000000000800000 0x0000000000800000 0x00000d 0x00000d R E 0x1000
  LOAD           0x001010 0x0000000000801010 0x0000000000801010 0x00003c 0x00003c R   0x1000
  GNU_STACK      0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW  0x0

 Section to Segment mapping:
  Segment Sections...
   00
   01
   02     .text
   03     .eh_frame
   04
   None   .comment .symtab .shstrtab .strtab

Note that first loadable segment has a p_vaddr less than the second one. (still reproduces on current master c50cba6).

Sort of analysis

The first loadable segment is the one that contains ELF header and program headers. It's added in Writer<ELFT>::createPhdrs.

    // Add the headers. We will remove them if they don't fit.
    // In the other partitions the headers are ordinary sections, so they don't
    // need to be added here.
    if (isMain) {
      load = addHdr(PT_LOAD, flags);
      load->add(ctx.out.elfHeader.get());
      load->add(ctx.out.programHeaders.get());
    }

In normal case it gets merged into some of other segments because of the following code

    bool sameLMARegion =
        load && !sec->lmaExpr && sec->lmaRegion == load->firstSec->lmaRegion;
    if (load && sec != relroEnd &&
        sec->memRegion == load->firstSec->memRegion &&
        (sameLMARegion || load->lastSec == ctx.out.programHeaders.get()) &&
        (ctx.script->hasSectionsCommand || sec->type == SHT_NOBITS ||
         load->lastSec->type != SHT_NOBITS)) {
      load->p_flags |= newFlags;
    } else {
      load = addHdr(PT_LOAD, newFlags);
      flags = newFlags;
    }

However if -Ttext is specified, predicate above may fail and new segment will be inserted. Then during LinkerScript::assignAddresses, first PT_LOAD segment gets assigned to ctx.target->getImageBase(), which may be far from the base of text (IIUC lld starts calculating p_vaddrs from the base passed in -T).

Note

This is not a synthetic example. It was observed in real life with very strict elf loader.

[rui314]

It looks like all PT_LOAD segments are sorted by p_vaddr in your example. The program has three loadable segments, and in ascending order their virtual addresses are the following.

0x200000
0x800000
0x801010

Am I missing something?

If you are talking about PT_PHDR, it's not a bug that the segment's p_vaddr is smaller than the first PT_LOAD entry. In fact, the ELF specification requires that the PT_PHDR precede any PT_LOAD entry in the program header. The spec states that all loadable segments (i.e., all PT_LOAD segments) must be sorted by p_vaddr, and nothing more.

[pskrgag]

@rui314 Sorry, I've added extra 0 while writing this bug report. It should be -Ttext=0x80000, i.e text should be lower than default base for !pie case (0x200000).

I will update it in moment

[pskrgag]

I guess #140126 may help. Not sure, since I am not lld expert at all

[MaskRay]

Thanks for the detailed report (PT_LOAD not sorted p_vaddr), analysis, and a patch with tests.

I think this use ld.lld -e main -Ttext=0x80000 test.o -o a.out is probably invalid as you specify a -Ttext address smaller than the default x86-64 image base 0x200000.
There is a read-only PT_LOAD segment covering the ELF and program headers but not any sections.

I've created #140187 to add a warning.

Note: Our section layout is quite different from GNU ld and we intentionally make different choices on some aspects.
ld.bfd -Ttext= behavior can be used as a reference, but we would only follow its behavior when it makes sense.