BPF relocations

BPF relocations

[David Miller]

I haven't done more work on bintuils BPF support because we
need to figure out exactly what to do with relocations.  So
I've been trying to spend time thinking about this.

As far as I can tell the 64-bit BPF relocation llvm uses
is used in two situations:

1) 64-bit relocations against data

2) 64-bit relocations against ldimm64 instructions

If this is true it's a very bad decision that has ramifications for us
right now.

One must always explicitly define relocations as being against data or
instruction fields.  You cannot use the same relocation for both kinds
of transformations, somehow trying to figure out what to do
"contextually".  That doesn't work.

Right now in binutils I gave this relocation with value "1" the name
R_BPF_DATA_64.  But it's not correct as explained above.

I'm using it as a data relocation so that dwarf2 information emitted
by llvm gets handled correctly by binutils.

The only real dependency upon relocation "1" being used against
instructions is the ELF parser that records the relocations against
MAP sections which get applied to ldimm64 instructions.

So I propose:

1) We define the set of relocations as follows:

  RELOC_NUMBER (R_BPF_NONE, 0)
  RELOC_NUMBER (R_BPF_OLD_64, 1)
  RELOC_NUMBER (R_BPF_INSN_64, 2)
  RELOC_NUMBER (R_BPF_INSN_32, 3)
  RELOC_NUMBER (R_BPF_INSN_16, 4)
  RELOC_NUMBER (R_BPF_WDISP16, 5)
  RELOC_NUMBER (R_BPF_DATA_8,  8)
  RELOC_NUMBER (R_BPF_DATA_16, 9)
  RELOC_NUMBER (R_BPF_DATA_32, 10)
  RELOC_NUMBER (R_BPF_DATA_64, 11)

2) LLVM is changed to have relocations:

	#define R_BPF_OLD_64_64	1  /* deprecated, do not use */
	#define R_BPF_INSN_64	2  /* 64-bit instruction relocation */
	#define R_BPF_64_32	10 /* 32-bit data relocation */
	#define R_BPF_DATA_64	11 /* 64-bit data relocation */

   and emit 64-bit relocations against instructions and data using
   R_BPF_INSN_64 and R_BPF_DATA_64, respectively.  Keep the llvm code
   around for interpreting R_BPF_OLD_64_64 so that interaction with
   older binaries keeps working.

3) The existing loaders should continue to function properly, and with
   suitable changes alongside the list in #1 to binutils it will still
   properly read dwarf2 information in both old and new binaries.

4) Add explicit relocation number checks to the ELF loaders, they
   should accept both "1" and "2" for MAP relocations against ldimm64

Comments?

Re: BPF relocations

[Alexei Starovoitov]

On 5/11/17 12:31 PM, David Miller wrote:
>
> I haven't done more work on bintuils BPF support because we
> need to figure out exactly what to do with relocations.  So
> I've been trying to spend time thinking about this.
>
> As far as I can tell the 64-bit BPF relocation llvm uses
> is used in two situations:
>
> 1) 64-bit relocations against data
>
> 2) 64-bit relocations against ldimm64 instructions
>
> If this is true it's a very bad decision that has ramifications for us
> right now.
>
> One must always explicitly define relocations as being against data or
> instruction fields.  You cannot use the same relocation for both kinds
> of transformations, somehow trying to figure out what to do
> "contextually".  That doesn't work.

why it doesn't work?
as far as i can see x86 doesn't care where the relo applies.
afaik relocations are divided into absolute, pc relative and pic 
relative and it doesn't matter whether they're against .text,
.eh_frame or .debug_* sections.

We have just two so far: absolute 32-bit and absolute 64-bit relocation.
I don't see what we would use pc-relative relo for.

If I remember correctly, the x64 and other cpus use pc-relative for
'call foo' insns since this is how those instructions work.
We don't have such calls yet.

Re: BPF relocations

[David Miller]

From: Alexei Starovoitov <ast@fb.com>
Date: Thu, 11 May 2017 16:10:35 -0700

> I don't see what we would use pc-relative relo for.

We must have them at least for banches.

Internally, we have to emit some kind of relocation as GAS makes it's
first pass over the instructions.

Afterwards, it walks the relocations and resolves all that can be done
at assembly time, and preserves as relocations in the object file for
those which it cannot.

Thinking further down the line many other kinds of PC relative
relocations are possible, even if you don't allow calls.  For example:

	ldimm64	R1, 24 + (. - external_label)

This would be a 64-bit PC relative reloc, with the value 24 in the
addend.

And eventually we want full linking.

The example above may seem silly, but every other full CPU ELF
specification handles these things completely and we should seek to be
complete as well.

Re: BPF relocations

[Alexei Starovoitov]

On 5/11/17 6:19 PM, David Miller wrote:
> From: Alexei Starovoitov <ast@fb.com>
> Date: Thu, 11 May 2017 16:10:35 -0700
>
>> I don't see what we would use pc-relative relo for.
>
> We must have them at least for banches.
>
> Internally, we have to emit some kind of relocation as GAS makes it's
> first pass over the instructions.
>
> Afterwards, it walks the relocations and resolves all that can be done
> at assembly time, and preserves as relocations in the object file for
> those which it cannot.

got it. yes.
llvm has this thing as well. It calls it FK_PCRel_2
(FK stands for Fixup Kind) which is 16-bit pc relative relo
into 'off' bits of insn.
Fortunately for LLVM this fixup is never converted to actual relo
and it is applied before final .o is emitted.

So, indeed, defining 16-bit pc-relative relo for branches is
definitely useful.
I can imagine someone combining two .o files with 'goto's
crossing two functions or something.
Let's pick a code for it.

> Thinking further down the line many other kinds of PC relative
> relocations are possible, even if you don't allow calls.  For example:
>
> 	ldimm64	R1, 24 + (. - external_label)
>
> This would be a 64-bit PC relative reloc, with the value 24 in the
> addend.

yes. that would be useful as well.
I don't mind defining it for our semi-official bpf relo spec :)

> And eventually we want full linking.
>
> The example above may seem silly, but every other full CPU ELF
> specification handles these things completely and we should seek to be
> complete as well.

I agree that the further we go the more complete it will become.
My concern that if we define too many things because other archs
have them we may end up not using them when time comes, since we
didn't think of some minor detail.
So today I would only add 16-bit pc-relative and 64-bit pc-relative.
The former is clearly useful for branches and the latter for calls
and jmp tables.
Right now we don't have simple 'switch()'. llvm has to convert it
into a sequence of branches. It's ok-ish. Ideally we need jmp-table
like normal cpus do and ldimm64 + relo should work for such purpose.

Re: BPF relocations

[Maciej W. Rozycki]

On Fri, 12 May 2017, David Miller wrote:

> Internally, we have to emit some kind of relocation as GAS makes it's
> first pass over the instructions.

 Not really, you can defer that until the relaxation pass, e.g. to avoid 
figuring out what to do about forward local symbol references, especially 
in complex expressions that may eventually resolve to assembly constants.

 This is how MIPS16 assembly works for example, due to its dual regular vs 
extended instruction encoding, so that no artificial relocations had to be 
invented in GAS for the regular instructions, which never get relocations 
recorded against in an object file.  Any instruction that ends up needing 
a relocation, if supported (not all encodings do), gets converted to the 
extended form in the relaxation pass and only then a suitable fixup is 
attached to it.

 Of course that may not matter for your specific case, but I think it's 
worth noting so as to avoid people getting misled about how GAS works.

 FWIW,

  Maciej