Support additional 64bit immediate instruction modes

[Alan-Jowett]

https://www.ietf.org/archive/id/draft-ietf-bpf-isa-04.html#name-platform-variables

The BPF ISA at the IETF defines various 64bit immediate loads:

5.4.  64-bit immediate instructions

   Instructions with the IMM 'mode' modifier use the wide instruction
   encoding defined in Instruction encoding (Section 3), and use the
   'src_reg' field of the basic instruction to hold an opcode subtype.

   The following table defines a set of {IMM, DW, LD} instructions with
   opcode subtypes in the 'src_reg' field, using new terms such as "map"
   defined further below:

    +=========+================================+==========+==========+
    | src_reg | pseudocode                     | imm type | dst type |
    +=========+================================+==========+==========+
    | 0x0     | dst = (next_imm << 32) | imm   | integer  | integer  |
    +---------+--------------------------------+----------+----------+
    | 0x1     | dst = map_by_fd(imm)           | map fd   | map      |
    +---------+--------------------------------+----------+----------+
    | 0x2     | dst = map_val(map_by_fd(imm))  | map fd   | data     |
    |         | + next_imm                     |          | address  |
    +---------+--------------------------------+----------+----------+
    | 0x3     | dst = var_addr(imm)            | variable | data     |
    |         |                                | id       | address  |
    +---------+--------------------------------+----------+----------+
    | 0x4     | dst = code_addr(imm)           | integer  | code     |
    |         |                                |          | address  |
    +---------+--------------------------------+----------+----------+
    | 0x5     | dst = map_by_idx(imm)          | map      | map      |
    |         |                                | index    |          |
    +---------+--------------------------------+----------+----------+
    | 0x6     | dst = map_val(map_by_idx(imm)) | map      | data     |
    |         | + next_imm                     | index    | address  |
    +---------+--------------------------------+----------+----------+

                 Table 12: 64-bit immediate instructions




Thaler                  Expires 27 December 2024               [Page 21]

Internet-Draft                   BPF ISA                       June 2024


   where

   *  map_by_fd(imm) means to convert a 32-bit file descriptor into an
      address of a map (see Maps (Section 5.4.1))

   *  map_by_idx(imm) means to convert a 32-bit index into an address of
      a map

   *  map_val(map) gets the address of the first value in a given map

   *  var_addr(imm) gets the address of a platform variable (see
      Platform Variables (Section 5.4.2)) with a given id

   *  code_addr(imm) gets the address of the instruction at a specified
      relative offset in number of (64-bit) instructions

   *  the 'imm type' can be used by disassemblers for display

   *  the 'dst type' can be used for verification and JIT compilation
      purposes

Currently the verifier only supports type 0 and type 1 loads.

Type 1 loads are supported here:
https://github.com/vbpf/ebpf-verifier/blob/16e06cf98c36848c0da804d71310041e4243642b/src/asm_files.cpp#L431C1-L435C22

To support type 3, the code should handle the case where the relocation is to a .rodata section (aka platform variables).

Behavior would be:

1. Allocate a pseudo fd for the region, treat it as if it were an array map of size == relocation region.
2. Set source = 3 and immediate == assigned fd.
3. When handling this instruction, treat it the same as a bpf_map_lookup_elem (i.e. return pointer shared memory + size info).

At that point, the rest of the code should operate correctly.

[a-hamza-r]

This documentation has helped me understand relocations: https://docs.kernel.org/bpf/llvm_reloc.html

[a-hamza-r]

I have spent some time on the relocation issue. Consider the following simple example:

> cat relocation_example.c 
static volatile int l1 __attribute__((section("sec")));
static volatile int l2 __attribute__((section("sec")));
int test(int a, int b) {
  return l1 + l2;
}

Its disassembly looks like this:

> llvm-objdump-14 -dr relocation_example.o

relocation_example.o:	file format elf64-bpf

Disassembly of section .text:

0000000000000000 <test>:
       0:	18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00	r1 = 0 ll
		0000000000000000:  R_BPF_64_64	sec
       2:	61 11 00 00 00 00 00 00	r1 = *(u32 *)(r1 + 0)
       3:	18 02 00 00 04 00 00 00 00 00 00 00 00 00 00 00	r2 = 4 ll
		0000000000000018:  R_BPF_64_64	sec
       5:	61 20 00 00 00 00 00 00	r0 = *(u32 *)(r2 + 0)
       6:	0f 10 00 00 00 00 00 00	r0 += r1
       7:	95 00 00 00 00 00 00 00	exit

The relocations are at instructions 0 and 3, shown as relocation to section sec (not as relocations to actual symbols l1 and l2). This is the behavior for static variables. The next instruction for each relocation is a memory load, which loads their values. The relocation table:

> llvm-readelf-14 -r relocation_example.o

Relocation section '.rel.text' at offset 0x678 contains 2 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name
0000000000000000  0000000500000001 R_BPF_64_64            0000000000000000 sec
0000000000000018  0000000500000001 R_BPF_64_64            0000000000000000 sec

The symbol table:

llvm-readelf-14 -s relocation_example.o

Symbol table '.symtab' contains 15 entries:
   Num:    Value          Size Type    Bind   Vis       Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT   UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT   ABS relocation_example.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT     2 .text
     3: 0000000000000000     4 OBJECT  LOCAL  DEFAULT     4 l1
     4: 0000000000000004     4 OBJECT  LOCAL  DEFAULT     4 l2
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT     4 sec
     ...

The type for each relocation (relocation table) has the first 4 bytes as 00000005 stating that the relocation symbol is at index 5 in the symbol table. To get the addresses of relocations l1 and l2, we would have to look at the actual instructions r1 = 0 ll and r2 = 4 ll (resp.), where 0 and 4 (resp.) are the addends. We compute the address of l1 as 0000000000000000 (sec symbol's value) + 0 (addend for l1) = 0, stating that inside section sec, l1 is at location 0. We compute the address of l2 as 0000000000000000 + 4 = 4, stating l2 is at location 4 into section sec. Conceptually, r1 stores address(sec) + 0 and r2 stores address(sec) + 4.

[a-hamza-r]

@Alan-Jowett, based on the algorithm you suggested above, should we keep each relocation in a separate region of its own (i.e., one region for l1 and l2 each)? Each region will only store the value of the single relocation variable. Then, the load operation on that region will load the value. The other possibility is to keep one region for section sec (potentially multiple regions for multiple sections). Then, when replacing the relocation instruction, we should include the offset information to know which specific address we are loading inside the region.

I apologize if this seems confusing. I have limited knowledge about relocations and how the verifier already implements map relocations, and there is a possibility I am way off with the above description.

[Alan-Jowett]

@a-hamza-r this is what Linux / libbpf is doing:

// Copyright (c) Prevail Verifier contributors.
// SPDX-License-Identifier: MIT

#include "bpf.h"

static volatile uint32_t global_var = 0;
static volatile uint32_t global_var_2 = 0;


int func(void* ctx) {
    global_var ++;
    global_var_2 += 2;
    return 0;
}

The xlated assembly is then:

int func(void * ctx):
; global_var ++;
   0: (18) r1 = map[id:43][0]+0
   2: (61) r2 = *(u32 *)(r1 +0)
   3: (07) r2 += 1
   4: (63) *(u32 *)(r1 +0) = r2
; global_var_2 += 2;
   5: (18) r1 = map[id:43][0]+4
   7: (61) r2 = *(u32 *)(r1 +0)
   8: (07) r2 += 2
   9: (63) *(u32 *)(r1 +0) = r2
; return 0;
  10: (b7) r0 = 0
  11: (95) exit

The ELF file contains 1 .bss section with two relocations point to it and the xlated BPF byte code shows 1 array map of size == size of bss section.

I think if verifier followed the same example, it would be a good thing.

From reading the libbpf code, it names the section map as follows:
First 7 characters from the ELF file name + section name.

So, assuming the program was called "global_variables.o" the map would be called:
"global_.bss"

Given that the verifier's loader is already updating lddw instructions to set the source = 1 for map relocations, it may make sense to have it do the same for this type of relocation.