Skip to contentSkip to conversation

bpf, docs: Add note about type convention

PATCH In review [email protected] 4 participants 10 messages Oct 27, 2022 – Nov 9, 2022

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/4 bpf, docs: Add note about type convention

From: Dave Thaler <[email protected]>

Add note about type convention

---
 Documentation/bpf/instruction-set.rst | 7 +++++++
 1 file changed, 7 insertions(+)
Documentation/bpf/instruction-set.rst +7 -0
index 5d798437d..bed6d33fc 100644
@@ -7,6 +7,11 @@ eBPF Instruction Set Specification, v1.0
 
 This document specifies version 1.0 of the eBPF instruction set.
 
+Documentation conventions
+=========================
+
+For brevity, this document uses the type notion "u64", "u32", etc.
+to mean an unsigned integer whose width is the specified number of bits.
 
 Registers and calling convention
 ================================
@@ -116,6 +121,8 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = (u32) dst_reg + (u32) src_reg;
 
+where '(u32)' indicates truncation to 32 bits.
+
 ``BPF_ADD | BPF_X | BPF_ALU64`` means::
 
   dst_reg = dst_reg + src_reg
Signature · 1 line
2.33.4
#1 lore raw

PATCH 2/4 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow

From: Dave Thaler <[email protected]>

Fix modulo zero, division by zero, overflow, and underflow. Also clarify how a negative immediate value is ued in unsigned division

---
 Documentation/bpf/instruction-set.rst | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +13 -2
index bed6d33fc..74dcc13a9 100644
@@ -104,19 +104,26 @@ code      value  description
 BPF_ADD   0x00   dst += src
 BPF_SUB   0x10   dst -= src
 BPF_MUL   0x20   dst \*= src
-BPF_DIV   0x30   dst /= src
+BPF_DIV   0x30   dst = (src != 0) ? (dst / src) : 0
 BPF_OR    0x40   dst \|= src
 BPF_AND   0x50   dst &= src
 BPF_LSH   0x60   dst <<= src
 BPF_RSH   0x70   dst >>= src
 BPF_NEG   0x80   dst = ~src
-BPF_MOD   0x90   dst %= src
+BPF_MOD   0x90   dst = (src != 0) ? (dst % src) : dst
 BPF_XOR   0xa0   dst ^= src
 BPF_MOV   0xb0   dst = src
 BPF_ARSH  0xc0   sign extending shift right
 BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 ========  =====  ==========================================================
 
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap.  If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead left unchanged.
+
 ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
   dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -135,6 +142,10 @@ where '(u32)' indicates truncation to 32 bits.
 
   src_reg = src_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned,
+where 'imm' is first sign extended to 64 bits and then converted
+to an unsigned 64-bit value.  There are no instructions for
+signed division or modulo.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
#2 lore raw

PATCH 3/4 bpf, docs: Use consistent names for the same field

In reply to [email protected]

From: Dave Thaler <[email protected]>

Use consistent names for the same field

---
 Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++--------
 1 file changed, 76 insertions(+), 31 deletions(-)
Documentation/bpf/instruction-set.rst +76 -31
index 74dcc13a9..aa1b37cb5 100644
@@ -35,20 +35,59 @@ Instruction encoding
 eBPF has two instruction encodings:
 
 * the basic instruction encoding, which uses 64 bits to encode an instruction
-* the wide instruction encoding, which appends a second 64-bit immediate value
-  (imm64) after the basic instruction for a total of 128 bits.
+* the wide instruction encoding, which appends a second 64-bit immediate (i.e.,
+  constant) value after the basic instruction for a total of 128 bits.
 
-The basic instruction encoding looks as follows:
+The basic instruction encoding is as follows, where MSB and LSB mean the most significant
+bits and least significant bits, respectively:
 
 =============  =======  ===============  ====================  ============
 32 bits (MSB)  16 bits  4 bits           4 bits                8 bits (LSB)
 =============  =======  ===============  ====================  ============
-immediate      offset   source register  destination register  opcode
+imm            offset   src              dst                   opcode
 =============  =======  ===============  ====================  ============
 
+imm
+  signed integer immediate value
+
+offset
+  signed integer offset used with pointer arithmetic
+
+src
+  the source register number (0-10), except where otherwise specified
+  (`64-bit immediate instructions`_ reuse this field for other purposes)
+
+dst
+  destination register number (0-10)
+
+opcode
+  operation to perform
+
 Note that most instructions do not use all of the fields.
 Unused fields shall be cleared to zero.
 
+As discussed below in `64-bit immediate instructions`_, a 64-bit immediate
+instruction uses a 64-bit immediate value that is constructed as follows.
+The 64 bits following the basic instruction contain a pseudo instruction
+using the same format but with opcode, dst, src, and offset all set to zero,
+and imm containing the high 32 bits of the immediate value.
+
+=================  ==================
+64 bits (MSB)      64 bits (LSB)
+=================  ==================
+basic instruction  pseudo instruction
+=================  ==================
+
+Thus the 64-bit immediate value is constructed as follows:
+
+  imm64 = imm + (next_imm << 32)
+
+where 'next_imm' refers to the imm value of the pseudo instruction
+following the basic instruction.
+
+In the remainder of this document 'src' and 'dst' refer to the values of the source
+and destination registers, respectively, rather than the register number.
+
 Instruction classes
 -------------------
 
@@ -76,20 +115,24 @@ For arithmetic and jump instructions (``BPF_ALU``, ``BPF_ALU64``, ``BPF_JMP`` an
 ==============  ======  =================
 4 bits (MSB)    1 bit   3 bits (LSB)
 ==============  ======  =================
-operation code  source  instruction class
+code            source  instruction class
 ==============  ======  =================
 
-The 4th bit encodes the source operand:
+code
+  the operation code, whose meaning varies by instruction class
 
-  ======  =====  ========================================
-  source  value  description
-  ======  =====  ========================================
-  BPF_K   0x00   use 32-bit immediate as source operand
-  BPF_X   0x08   use 'src_reg' register as source operand
-  ======  =====  ========================================
+source
+  the source operand location, which unless otherwise specified is one of:
 
-The four MSB bits store the operation code.
+  ======  =====  ==========================================
+  source  value  description
+  ======  =====  ==========================================
+  BPF_K   0x00   use 32-bit 'imm' value as source operand
+  BPF_X   0x08   use 'src' register value as source operand
+  ======  =====  ==========================================
 
+instruction class
+  the instruction class (see `Instruction classes`_)
 
 Arithmetic instructions
 -----------------------
@@ -117,6 +160,8 @@ BPF_ARSH  0xc0   sign extending shift right
 BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 ========  =====  ==========================================================
 
+where 'src' is the source operand value.
+
 Underflow and overflow are allowed during arithmetic operations,
 meaning the 64-bit or 32-bit value will wrap.  If
 eBPF program execution would result in division by zero,
@@ -126,21 +171,21 @@ the destination register is instead left unchanged.
 
 ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
-  dst_reg = (u32) dst_reg + (u32) src_reg;
+  dst = (u32) ((u32) dst + (u32) src)
 
 where '(u32)' indicates truncation to 32 bits.
 
 ``BPF_ADD | BPF_X | BPF_ALU64`` means::
 
-  dst_reg = dst_reg + src_reg
+  dst = dst + src
 
 ``BPF_XOR | BPF_K | BPF_ALU`` means::
 
-  src_reg = (u32) src_reg ^ (u32) imm32
+  src = (u32) src ^ (u32) imm
 
 ``BPF_XOR | BPF_K | BPF_ALU64`` means::
 
-  src_reg = src_reg ^ imm32
+  src = src ^ imm
 
 Also note that the division and modulo operations are unsigned,
 where 'imm' is first sign extended to 64 bits and then converted
@@ -173,11 +218,11 @@ Examples:
 
 ``BPF_ALU | BPF_TO_LE | BPF_END`` with imm = 16 means::
 
-  dst_reg = htole16(dst_reg)
+  dst = htole16(dst)
 
 ``BPF_ALU | BPF_TO_BE | BPF_END`` with imm = 64 means::
 
-  dst_reg = htobe64(dst_reg)
+  dst = htobe64(dst)
 
 Jump instructions
 -----------------
@@ -252,15 +297,15 @@ instructions that transfer data between a register and memory.
 
 ``BPF_MEM | <size> | BPF_STX`` means::
 
-  *(size *) (dst_reg + off) = src_reg
+  *(size *) (dst + offset) = src_reg
 
 ``BPF_MEM | <size> | BPF_ST`` means::
 
-  *(size *) (dst_reg + off) = imm32
+  *(size *) (dst + offset) = imm32
 
 ``BPF_MEM | <size> | BPF_LDX`` means::
 
-  dst_reg = *(size *) (src_reg + off)
+  dst = *(size *) (src + offset)
 
 Where size is one of: ``BPF_B``, ``BPF_H``, ``BPF_W``, or ``BPF_DW``.
 
@@ -294,11 +339,11 @@ BPF_XOR   0xa0   atomic xor
 
 ``BPF_ATOMIC | BPF_W  | BPF_STX`` with 'imm' = BPF_ADD means::
 
-  *(u32 *)(dst_reg + off16) += src_reg
+  *(u32 *)(dst + offset) += src
 
 ``BPF_ATOMIC | BPF_DW | BPF_STX`` with 'imm' = BPF ADD means::
 
-  *(u64 *)(dst_reg + off16) += src_reg
+  *(u64 *)(dst + offset) += src
 
 In addition to the simple atomic operations, there also is a modifier and
 two complex atomic operations:
@@ -313,16 +358,16 @@ BPF_CMPXCHG  0xf0 | BPF_FETCH  atomic compare and exchange
 
 The ``BPF_FETCH`` modifier is optional for simple atomic operations, and
 always set for the complex atomic operations.  If the ``BPF_FETCH`` flag
-is set, then the operation also overwrites ``src_reg`` with the value that
+is set, then the operation also overwrites ``src`` with the value that
 was in memory before it was modified.
 
-The ``BPF_XCHG`` operation atomically exchanges ``src_reg`` with the value
-addressed by ``dst_reg + off``.
+The ``BPF_XCHG`` operation atomically exchanges ``src`` with the value
+addressed by ``dst + offset``.
 
 The ``BPF_CMPXCHG`` operation atomically compares the value addressed by
-``dst_reg + off`` with ``R0``. If they match, the value addressed by
-``dst_reg + off`` is replaced with ``src_reg``. In either case, the
-value that was at ``dst_reg + off`` before the operation is zero-extended
+``dst + offset`` with ``R0``. If they match, the value addressed by
+``dst + offset`` is replaced with ``src``. In either case, the
+value that was at ``dst + offset`` before the operation is zero-extended
 and loaded back to ``R0``.
 
 64-bit immediate instructions
@@ -335,7 +380,7 @@ There is currently only one such instruction.
 
 ``BPF_LD | BPF_DW | BPF_IMM`` means::
 
-  dst_reg = imm64
+  dst = imm64
 
 
 Legacy BPF Packet access instructions
Signature · 1 line
2.33.4
#3 lore raw

Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field

Documentation/bpf/instruction-set.rst Instruction encoding · line 83

Quoted 5 lines · On Thu, Oct 27, 2022 at 7:46 AM <[email protected]> wrote:
Documentation/bpf/instruction-set.rst +4 -0
+
+Thus the 64-bit immediate value is constructed as follows:
+
+  imm64 = imm + (next_imm << 32)

Are you sure this is correct considering that 'imm' was defined earlier in the doc as sign extended? Maybe use:
imm64 = (u32)imm | ((u64)(u32)next_imm) << 32) ?

#4 lore raw

RE: [PATCH 3/4] bpf, docs: Use consistent names for the same field

Quoted 11 lines · Alexei Starovoitov

Documentation/bpf/instruction-set.rst Instruction encoding · line 83

Quoted 5 lines · On Thu, Oct 27, 2022 at 7:46 AM <[email protected]> wrote:
Documentation/bpf/instruction-set.rst +4 -0
+
+Thus the 64-bit immediate value is constructed as follows:
+
+  imm64 = imm + (next_imm << 32)

Are you sure this is correct considering that 'imm' was defined earlier in the doc as sign extended? Maybe use:
imm64 = (u32)imm | ((u64)(u32)next_imm) << 32) ?

I agree that would be clearer, will update.

Dave

#5 lore raw

PATCH 4/4 bpf, docs: Explain helper functions

In reply to [email protected]

From: Dave Thaler <[email protected]>

Explain helper functions

---
 Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
Documentation/bpf/instruction-set.rst +17 -1
index aa1b37cb5..40c3293d6 100644
@@ -242,7 +242,7 @@ BPF_JSET  0x40   PC += off if dst & src
 BPF_JNE   0x50   PC += off if dst != src
 BPF_JSGT  0x60   PC += off if dst > src     signed
 BPF_JSGE  0x70   PC += off if dst >= src    signed
-BPF_CALL  0x80   function call
+BPF_CALL  0x80   function call              see `Helper functions`_
 BPF_EXIT  0x90   function / program return  BPF_JMP only
 BPF_JLT   0xa0   PC += off if dst < src     unsigned
 BPF_JLE   0xb0   PC += off if dst <= src    unsigned
@@ -253,6 +253,22 @@ BPF_JSLE  0xd0   PC += off if dst <= src    signed
 The eBPF program needs to store the return value into register R0 before doing a
 BPF_EXIT.
 
+Helper functions
+~~~~~~~~~~~~~~~~
+Helper functions are a concept whereby BPF programs can call into a
+set of function calls exposed by the eBPF runtime.  Each helper
+function is identified by an integer used in a ``BPF_CALL`` instruction.
+The available helper functions may differ for each eBPF program type.
+
+Conceptually, each helper function is implemented with a commonly shared function
+signature defined as:
+
+  u64 function(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+
+In actuality, each helper function is defined as taking between 0 and 5 arguments,
+with the remaining registers being ignored.  The definition of a helper function
+is responsible for specifying the type (e.g., integer, pointer, etc.) of the value returned,
+the number of arguments, and the type of each argument.
 
 Load and store instructions
 ===========================
Signature · 1 line
2.33.4
#6 lore raw

Re: [PATCH 4/4] bpf, docs: Explain helper functions

Quoted 24 lines · On Thu, Oct 27, 2022 at 7:46 AM <[email protected]> wrote:

From: Dave Thaler <[email protected]>

Explain helper functions

---
 Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
Documentation/bpf/instruction-set.rst +1 -1
index aa1b37cb5..40c3293d6 100644
@@ -242,7 +242,7 @@ BPF_JSET  0x40   PC += off if dst & src
 BPF_JNE   0x50   PC += off if dst != src
 BPF_JSGT  0x60   PC += off if dst > src     signed
 BPF_JSGE  0x70   PC += off if dst >= src    signed
-BPF_CALL  0x80   function call
+BPF_CALL  0x80   function call              see `Helper functions`_
 BPF_EXIT  0x90   function / program return  BPF_JMP only
 BPF_JLT   0xa0   PC += off if dst < src     unsigned
 BPF_JLE   0xb0   PC += off if dst <= src    unsigned

Documentation/bpf/instruction-set.rst BPF_JSLE 0xd0 PC += off if dst <= src signed · line 259

Quoted 7 lines
Documentation/bpf/instruction-set.rst +4 -0
@@ -253,6 +253,22 @@ BPF_JSLE  0xd0   PC += off if dst <= src    signed
 The eBPF program needs to store the return value into register R0 before doing a
 BPF_EXIT.
 
+Helper functions
+~~~~~~~~~~~~~~~~
+Helper functions are a concept whereby BPF programs can call into a
+set of function calls exposed by the eBPF runtime.  Each helper

eBPF right next to BPF looks odd. Let's stick to BPF everywhere?

#7 lore raw

RE: [PATCH 4/4] bpf, docs: Explain helper functions

Quoted 36 lines

-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Wednesday, November 9, 2022 1:51 AM
To: [email protected]
Cc: bpf <[email protected]>; Dave Thaler <[email protected]>
Subject: Re: [PATCH 4/4] bpf, docs: Explain helper functions

Quoted 28 lines · On Thu, Oct 27, 2022 at 7:46 AM <[email protected]> wrote:

From: Dave Thaler <[email protected]>

Explain helper functions

---
 Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
Documentation/bpf/instruction-set.rst +1 -1
index aa1b37cb5..40c3293d6 100644
@@ -242,7 +242,7 @@ BPF_JSET  0x40   PC += off if dst & src
 BPF_JNE   0x50   PC += off if dst != src
 BPF_JSGT  0x60   PC += off if dst > src     signed
 BPF_JSGE  0x70   PC += off if dst >= src    signed
-BPF_CALL  0x80   function call
+BPF_CALL  0x80   function call              see `Helper functions`_
 BPF_EXIT  0x90   function / program return  BPF_JMP only
 BPF_JLT   0xa0   PC += off if dst < src     unsigned
 BPF_JLE   0xb0   PC += off if dst <= src    unsigned
@@ -253,6 +253,22 @@ BPF_JSLE  0xd0   PC += off if dst <= src    signed
 The eBPF program needs to store the return value into register R0

before doing a BPF_EXIT.

Quoted 6 lines

Documentation/bpf/instruction-set.rst BPF_JSLE 0xd0 PC += off if dst <= src signed · line 259

Quoted 4 lines
Documentation/bpf/instruction-set.rst +4 -0
+Helper functions
+~~~~~~~~~~~~~~~~
+Helper functions are a concept whereby BPF programs can call into a
+set of function calls exposed by the eBPF runtime.  Each helper

eBPF right next to BPF looks odd. Let's stick to BPF everywhere?

Since the brand is eBPF, could we stick to eBPF everywhere except the actual defines (BPF_CALL, etc. have to be literal)?

Dave

#8 lore raw

Re: [PATCH 4/4] bpf, docs: Explain helper functions

Quoted 44 lines · Dave Thaler
Quoted 37 lines

-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Wednesday, November 9, 2022 1:51 AM
To: [email protected]
Cc: bpf <[email protected]>; Dave Thaler <[email protected]>
Subject: Re: [PATCH 4/4] bpf, docs: Explain helper functions

Quoted 28 lines · On Thu, Oct 27, 2022 at 7:46 AM <[email protected]> wrote:

From: Dave Thaler <[email protected]>

Explain helper functions

---
 Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
Documentation/bpf/instruction-set.rst +1 -1
index aa1b37cb5..40c3293d6 100644
@@ -242,7 +242,7 @@ BPF_JSET  0x40   PC += off if dst & src
 BPF_JNE   0x50   PC += off if dst != src
 BPF_JSGT  0x60   PC += off if dst > src     signed
 BPF_JSGE  0x70   PC += off if dst >= src    signed
-BPF_CALL  0x80   function call
+BPF_CALL  0x80   function call              see `Helper functions`_
 BPF_EXIT  0x90   function / program return  BPF_JMP only
 BPF_JLT   0xa0   PC += off if dst < src     unsigned
 BPF_JLE   0xb0   PC += off if dst <= src    unsigned
@@ -253,6 +253,22 @@ BPF_JSLE  0xd0   PC += off if dst <= src    signed
 The eBPF program needs to store the return value into register R0

before doing a BPF_EXIT.

Quoted 6 lines

Documentation/bpf/instruction-set.rst BPF_JSLE 0xd0 PC += off if dst <= src signed · line 259

Quoted 4 lines
Documentation/bpf/instruction-set.rst +4 -0
+Helper functions
+~~~~~~~~~~~~~~~~
+Helper functions are a concept whereby BPF programs can call into a
+set of function calls exposed by the eBPF runtime.  Each helper

eBPF right next to BPF looks odd. Let's stick to BPF everywhere?

Quoted 2 lines

Since the brand is eBPF, could we stick to eBPF everywhere except the actual defines (BPF_CALL, etc. have to be literal)?

I prefer to use BPF everywhere.

Acked-by on v1 1/4
#9 lore raw
In reply to [email protected]
Quoted 5 lines · On 10/27, [email protected] wrote:

From: Dave Thaler <[email protected]>

Add note about type convention

For the series:

Carry-on from my shift last week.

Quoted 32 lines
---
  Documentation/bpf/instruction-set.rst | 7 +++++++
  1 file changed, 7 insertions(+)
Documentation/bpf/instruction-set.rst +7 -0
index 5d798437d..bed6d33fc 100644
@@ -7,6 +7,11 @@ eBPF Instruction Set Specification, v1.0
 
  This document specifies version 1.0 of the eBPF instruction set.
 
+Documentation conventions
+=========================
+
+For brevity, this document uses the type notion "u64", "u32", etc.
+to mean an unsigned integer whose width is the specified number of bits.
 
  Registers and calling convention
  ================================
@@ -116,6 +121,8 @@ BPF_END   0xd0   byte swap operations (see `Byte swap  
 instructions`_ below)
 
    dst_reg = (u32) dst_reg + (u32) src_reg;
 
+where '(u32)' indicates truncation to 32 bits.
+
  ``BPF_ADD | BPF_X | BPF_ALU64`` means::
 

dst_reg = dst_reg + src_reg
--
2.33.4