[LLD][BPF] Add bpf support

[yonghong-song]

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

[yonghong-song]

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

[ast]

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

[MaskRay]

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

[yonghong-song]

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

[MaskRay]

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 ↗

(On Diff #344635)

Remove the abstraction: emitFuncDataSections.

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

lld/test/ELF/bpf-basic.s

2 ↗

(On Diff #344635)

Use split-file %s %t

4 ↗

(On Diff #344635)

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

6 ↗

(On Diff #344635)

-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.

[yonghong-song]

• Addressed @MaskRay's comments. Thanks for quick reviewing!

[MaskRay]

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/[e-mail]/

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

1 ↗

(On Diff #345024)

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

[yonghong-song]

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

1 ↗

(On Diff #345024)

will do.

[yonghong-song]

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.

[yonghong-song]

• 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.

[yonghong-song]

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

[MaskRay]

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.

[yonghong-song]

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]

• https://reviews.llvm.org/D102712 made llvm BPF relocations more lld friendly. The patch has landed. Now redo the lld patch with new relocations.
• Per early Fangrui's suggestion, I submitted the following llvm relocation patch https://lore.kernel.org/bpf/[e-mail]/ to linux kernel mailing list and if accepted it will be in kernel bpf docs.

[yonghong-song]

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

[yonghong-song]

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=[e-mail]/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!

[yonghong-song]

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

[alessandrod]

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?

lld/ELF/Arch/BPF.cpp

+//===---- BPF.cpp ---------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InputFiles.h"
+#include "Symbols.h"
+#include "Target.h"
+#include "llvm/Object/ELF.h"
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace lld;
+using namespace lld::elf;
+
+namespace {
+class BPF final : public TargetInfo {
+public:
+  BPF();
+  void relocate(uint8_t *loc, const Relocation &rel,
+                uint64_t val) const override;
+  RelExpr getRelExpr(RelType type, const Symbol &s,
+                     const uint8_t *loc) const override;
+};
+} // namespace
+
+BPF::BPF() {
+  noneRel = R_BPF_NONE;
+}
+
+void BPF::relocate(uint8_t *loc, const Relocation &rel, uint64_t val) const {
+  switch (rel.type) {
+  case R_BPF_NONE:
+    break;
+  case R_BPF_64_64:
+    write64(loc, val);
+    break;
+  case R_BPF_64_32:
+    write32(loc, val);
+    break;
+  default:
+    llvm_unreachable("unknown relocation");
+  }
+}
+
+RelExpr BPF::getRelExpr(RelType type, const Symbol &s,
+               const uint8_t *loc) const {
+  if (type == R_BPF_NONE)
+    return R_NONE;
+  return R_ABS;
+}
+
+TargetInfo *elf::getBPFTargetInfo() {
+  static BPF target;
+  return ⌖
+}

lld/ELF/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(ELFOptionsTableGen)
 
 add_lld_library(lldELF
   AArch64ErrataFix.cpp
   Arch/AArch64.cpp
   Arch/AMDGPU.cpp
   Arch/ARM.cpp
   Arch/AVR.cpp
+  Arch/BPF.cpp
   Arch/Hexagon.cpp
   Arch/Mips.cpp
   Arch/MipsArchTree.cpp
   Arch/MSP430.cpp
   Arch/PPC.cpp
   Arch/PPC64.cpp
   Arch/RISCV.cpp
   Arch/SPARCV9.cpp

lld/ELF/InputFiles.cpp

static uint16_t getBitcodeMachineKind(StringRef path, const Triple &t) {
   case Triple::amdgcn:
   case Triple::r600:
     return EM_AMDGPU;
   case Triple::arm:
   case Triple::thumb:
     return EM_ARM;
   case Triple::avr:
     return EM_AVR;
+  case Triple::bpfel:
+  case Triple::bpfeb:
+    return EM_BPF;
   case Triple::mips:
   case Triple::mipsel:
   case Triple::mips64:
   case Triple::mips64el:
     return EM_MIPS;
   case Triple::msp430:
     return EM_MSP430;
   case Triple::ppc:

lld/ELF/Target.h

protected:
   // Given that, the smallest value that can be used in here is 0x10000.
   uint64_t defaultImageBase = 0x10000;
 };
 
 TargetInfo *getAArch64TargetInfo();
 TargetInfo *getAMDGPUTargetInfo();
 TargetInfo *getARMTargetInfo();
 TargetInfo *getAVRTargetInfo();
+TargetInfo *getBPFTargetInfo();
 TargetInfo *getHexagonTargetInfo();
 TargetInfo *getMSP430TargetInfo();
 TargetInfo *getPPC64TargetInfo();
 TargetInfo *getPPCTargetInfo();
 TargetInfo *getRISCVTargetInfo();
 TargetInfo *getSPARCV9TargetInfo();
 TargetInfo *getX86TargetInfo();
 TargetInfo *getX86_64TargetInfo();

lld/ELF/Target.cpp

TargetInfo *elf::getTarget() {
   case EM_AARCH64:
     return getAArch64TargetInfo();
   case EM_AMDGPU:
     return getAMDGPUTargetInfo();
   case EM_ARM:
     return getARMTargetInfo();
   case EM_AVR:
     return getAVRTargetInfo();
+  case EM_BPF:
+    return getBPFTargetInfo();
   case EM_HEXAGON:
     return getHexagonTargetInfo();
   case EM_MIPS:
     switch (config->ekind) {
     case ELF32LEKind:
       return getMipsTargetInfo<ELF32LE>();
     case ELF32BEKind:
       return getMipsTargetInfo<ELF32BE>();