This is an archive of the discontinued LLVM Phabricator instance.

[LLD][BPF] Add bpf support
Needs ReviewPublic

Authored by yonghong-song on Apr 26 2021, 5:38 PM.

Details

Summary

This patch added BPF support to LLD. BPF
program does not have a defined entry point.
But LLD can still help do linking different
BPF objects into one object.

The simplest way is to link different objects
in a relocatable way.

clang -target bpf -g -O2 -c t1.c t2.c
ld.lld -r t1.o t2.o -o final.o

The drawback is that .BTF section is not deduplicated
as lld just simply merged all .BTF sections and
didn't do deduplication so a post-linker tool
is needed to do deduplication.

But we can build a relocable object file
through LTO. LTO puts all IRs in the same module so
deduplication is automatically done by the compiler.

clang -target bpf -flto -O2 -g -c t1.c -o t1.bc
clang -target bpf -flto -O2 -g -c t2.c -o t2.bc
ld.lld -r t1.bc t2.bc -o final.o

Currently, lld unconditionally emits a section per function/datum
with LTO. The bpf loader library, libbpf, expects only
one .text or .data section. Some other bpf loader tools may
have similar assumptions. To make downstream bpf tools less
complicated, per function/datum sections will not be emited
if LTO is compiled for BPF relocatable object.

The BPF relocation documentation:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/Documentation/bpf/llvm_reloc.rst

Diff Detail

Event Timeline

yonghong-song created this revision.Apr 26 2021, 5:38 PM
yonghong-song requested review of this revision.Apr 26 2021, 5:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 26 2021, 5:38 PM
yonghong-song retitled this revision from [WIP][LLD][BPF] Add bpf support to [LLD][BPF] Add bpf support.
yonghong-song edited the summary of this revision. (Show Details)
yonghong-song added a project: lld.

add tests/docs and target hook emitFuncDataSections(). Removed WIP tag.
@MaskRay Could you take a look? Thanks!

ast accepted this revision.May 11 2021, 2:53 PM

I think addition of emitFuncDataSections is justified.
The rest is bpf specific.

This revision is now accepted and ready to land.May 11 2021, 2:53 PM
MaskRay requested changes to this revision.May 11 2021, 3:23 PM
This revision now requires changes to proceed.May 11 2021, 3:23 PM

I will come to this, but want to make sure this is in a "need review" state.

yonghong-song edited the summary of this revision. (Show Details)

handling static functions (int a different section) properly. static variables should be similar.

MaskRay added inline comments.May 12 2021, 12:54 PM
lld/ELF/Arch/BPF.cpp
50

R_NONE if no dynamic relocation is expected

54

See other Arch/*.cpp: add switch in getRelExpr and add error

lld/ELF/LTO.cpp
87–90

Remove the abstraction: emitFuncDataSections.

Just test config->emachine and config->relocatable.

lld/test/ELF/bpf-basic.s
3

Use split-file %s %t

5

See riscv-*.s how I organize the little-endian and big-endian RUN lines.

7

-relocatable => -r

lld/test/ELF/bpf-lto-basic.s
1 ↗(On Diff #344635)

move to test/ELF/lto

Use .bc for bitcode file extension.

10 ↗(On Diff #344635)

[[#]]

17 ↗(On Diff #344635)

Add a comment what the magic value is.

MaskRay requested changes to this revision.May 12 2021, 12:55 PM
This revision now requires changes to proceed.May 12 2021, 12:55 PM
yonghong-song edited the summary of this revision. (Show Details)
  • Addressed @MaskRay's comments. Thanks for quick reviewing!
MaskRay added a comment.EditedMay 16 2021, 9:52 AM

Does BPF have a Processor Supplement ABI? I think we really should have raised our bar to allow targets which have defined the ABI.
This was also requested in 2018: https://patchwork.ozlabs.org/project/glibc/patch/20180616214515.10737-1-mark@klomp.org/

I don't understand the if (config->emachine != EM_BPF && type != target->noneRel) change as
it feels wrong that "BPF llvm target already wrote the section offset in each relocation instruction"

0000000000000000 <test2>:
       0:       18 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r0 = 0 ll
                0000000000000000:  R_BPF_64_64  sec3
       2:       95 00 00 00 00 00 00 00 exit

If I drop the special case, I will get

0000000000000000 <test2>:
       0:       00 00 00 00 00 00 00 00 <unknown>
                0000000000000000:  R_BPF_64_64  sec3
                ...
       2:       95 00 00 00 00 00 00 00 exit

Why is this <unknown>?

I would suggest that you try figuring out how other REL tests work (by commenting out some !RelTy::IsRela code and seeing what tests would fail).

I am also very concerned with potentially other differently interpreted concepts, e.g. the re-defined STV_INTERNAL (https://lists.llvm.org/pipermail/cfe-dev/2021-May/068134.html).
This would potentially diverge from other implementations and add some symbol resolution complexity to the generic code (say, we would have to check STV_INTERNAL in Symbols.cpp just for BPF)

lld/ELF/Arch/BPF.cpp
57

See other getRelExpr implementations. The allowed relocation types must be listed.

lld/test/ELF/lto/bpf-diff-sec.ll
2

The auxiliary file is only used once. Please use split-file

For this Why is this <unknown>? if you remove if (config->emachine != EM_BPF && type != target->noneRel), this is because I didn't implement BPF target relocate properly. In current llvm BPF backend, BPFAsmBackend.cpp file, we have

void BPFAsmBackend::applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
                               const MCValue &Target,
                               MutableArrayRef<char> Data, uint64_t Value,
                               bool IsResolved,
                               const MCSubtargetInfo *STI) const {
  if (Fixup.getKind() == FK_SecRel_4 || Fixup.getKind() == FK_SecRel_8) {
    // The Value is 0 for global variables, and the in-section offset
    // for static variables. Write to the immediate field of the inst.
    assert(Value <= UINT32_MAX);
    support::endian::write<uint32_t>(&Data[Fixup.getOffset() + 4],
                                     static_cast<uint32_t>(Value),
                                     Endian);
  } else if (Fixup.getKind() == FK_Data_4) {
    support::endian::write<uint32_t>(&Data[Fixup.getOffset()], Value, Endian);
  } else if (Fixup.getKind() == FK_Data_8) {
    support::endian::write<uint64_t>(&Data[Fixup.getOffset()], Value, Endian);
  } else if (Fixup.getKind() == FK_PCRel_4) {
    Value = (uint32_t)((Value - 8) / 8);
    if (Endian == support::little) {
      Data[Fixup.getOffset() + 1] = 0x10;
      support::endian::write32le(&Data[Fixup.getOffset() + 4], Value);
    } else {
      Data[Fixup.getOffset() + 1] = 0x1;
      support::endian::write32be(&Data[Fixup.getOffset() + 4], Value);
    } 
  } else {
    assert(Fixup.getKind() == FK_PCRel_2);
    Value = (uint16_t)((Value - 8) / 8);
    support::endian::write<uint16_t>(&Data[Fixup.getOffset() + 2], Value,
                                     Endian);
  }                                  
}

You can see some relocation data is written at the instruction offset 2 or 4. In my current relocate() function, the start of the insn (which include insn opcode) is written instead of offset 4. That is why you will see "<unknown>" here.

For

I would suggest that you try figuring out how other REL tests work (by commenting out some !RelTy::IsRela code and seeing what tests would fail).

That is a good suggestion, I am certainly not a ldd expert. I will look at the related codes, remove the above hack and resubmit the patch again.

lld/ELF/Arch/BPF.cpp
57

will do.

lld/test/ELF/lto/bpf-diff-sec.ll
2

will do.

For

I am also very concerned with potentially other differently interpreted concepts, e.g. the re-defined STV_INTERNAL (https://lists.llvm.org/pipermail/cfe-dev/2021-May/068134.html).

This would potentially diverge from other implementations and add some symbol resolution complexity to the generic code (say, we would have to check STV_INTERNAL in Symbols.cpp just for BPF)

I agree that BPF interpretation of STV_INTERNAL might be different from the standard. This is not a blocker though so we are fine without it.

  • removed hack in InputSection.cpp to prevent emitting relocations for relocatable BPF.
  • added two new target hooks to differentiate between ALLOC and non-ALLOC as BPF targets need them to take different actions.
  • implement target relocate*() and getImplicitAddend*() properly.

@alessandrod FYI. This is to support BPF in lld. Maybe this may help your rust bpf-linker work?

The REL handling and BPF::relocateAlloc look like hacks to me. Once they are fixed, I think the patch will be in a good state. Thanks!
It looks wrong that relocateAlloc is different from relocate.

Discussed with Alexei, we are going to add more relocations in BPF backend. Here is the patch https://reviews.llvm.org/D102712. You can take a look if you are interested.
Once it or its variant is merged, I will remove getImplicitAddendAlloc() and relocateAlloc(). Then we will have no non-target changes except disabling -ffunction-sections for BPF LTO relocatable mode. Thanks!

yonghong-song edited the summary of this revision. (Show Details)
ormris removed a subscriber: ormris.Jun 3 2021, 10:26 AM

@MaskRay Did you get some time to look at the new revision?

yonghong-song edited the summary of this revision. (Show Details)Jun 23 2021, 9:32 AM

Just updated the summary to include a link to bpf relocation documentation. Later on, once this is integrated into Linus tree (https://github.com/torvalds/linux), and built and placed in kernel/doc bpf relocation information should be very easily searchable (https://www.kernel.org/doc/html/latest/bpf/index.html).

Added Rui Ueyama (@ruiu), Rafael Espindola (@respindola) and George Rimar (@grimar) as reviewers too to get more perspective on how to move forward.

Currently, the patch is stuck as Fangrui (@MaskRay) really wants to rename some of bpf relocations, specifically R_BPF_64_64 and R_BPF_64_32.
See the detailed discussions here:

https://lore.kernel.org/bpf/CAADnVQJa=b=hoMGU213wMxyZzycPEKjAPFArKNatbVe4FvzVUA@mail.gmail.com/T/#t

I completely agree that these names are not really good and not reflect what the underlying relocation is doing. See the above discussion. That is why we added bpf relocations into kernel doc so people can easily check and find out what these relocations are for. BTW, the idea to create a bpf relocation documentation is from
Fangrui.

But relocation names R_BPF_64_64 and R_BPF_64_32 has been in BPF community since Nov 2016 with commit

7ab125dbf344 ([bpf] fix dwarf elf relocs and line numbers)

Before that there is only one relocation called R_BPF_MAP_FD. The renaming happens because bpf is still in its infant stage at that time and not many users.

Now bpf has a large community and R_BPF_64_64/R_BPF_64_32 is in elfutils and glibc_headers and libbpf and possibly other tools. Event the latest ebpf-for-windows mentioning these relocation names. From https://github.com/microsoft/ebpf-for-windows.git,

$ egrep -r R_BPF
docs/tutorial.md:0000000000000000 R_BPF_64_64 .data
docs/tutorial.md:0000000000000040 R_BPF_64_64 map

Changing these names will confuse users as the llvm-objdump -r and llvm-readobj -r output will have different names than the code or *existing* documentation. I think having a ready documentation (https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/Documentation/bpf/llvm_reloc.rst) should be a reasonable step if anybody wants to understand what the relocation intends to do. I think in most cases, for people cares the relocation implementation details, looking at names almost always not enough for any architecture, you need to look at the code or detailed documentations, at least for me.

It would be good if @ruiu, @respindola) and @grimar or any other people interested in discussion can share their perspective. Thanks!

@ruiu @respindola @grimar Pinging. Do you have any comments for this patch?

I'd love to see this merged. I am now involved in a project that maintains a lld fork with this patch, and also maintain bpf-linker for the rust ecosystem. Ideally I'd like to see both disappear. Fwiw, I definitely agree with @yonghong-song that renaming the (admittedly bad) relocation types would cause a lot of unnecessary confusion in the ecosystem as there are now so many projects that use those names.

What needs to happen to move this forward?

Herald added a project: Restricted Project. · View Herald TranscriptJul 13 2022, 3:54 PM