bpf, docs: Add note about type convention
Subsystems (2)
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
@@ -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
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
@@ -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
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
@@ -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) (dst + 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
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 136 lines · On 10/19, [email protected] wrote:
From: Dave Thaler <[email protected]>
Use consistent names for the same field
Signed-off-by Dave Thaler <[email protected]>--- Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++-------- 1 file changed, 76 insertions(+), 31 deletions(-)Documentation/bpf/instruction-set.rst +0
-0@@ -35,20 +35,59 @@ Instruction encoding eBPF has two instruction encodings: * the basic instruction encoding, which uses 64 bits to encode aninstruction
-* the wide instruction encoding, which appends a second 64-bit immediate valueDocumentation/bpf/instruction-set.rst +1
-1- (imm64) after the basic instruction for a total of 128 bits. +* the wide instruction encoding, which appends a second 64-bit immediate(i.e.,
Documentation/bpf/instruction-set.rst +2
-1+ 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 themost significant
+bits and least significant bits, respectively:============= ======= =============== ====================
============
32 bits (MSB) 16 bits 4 bits 4 bits 8 bits
(LSB)
============= ======= =============== ====================
============Documentation/bpf/instruction-set.rst +1
-1-immediate offset source register destination register opcode +imm offset src dst opcode ============= ======= =============== ================================
Documentation/bpf/instruction-set.rst +17
-0+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-bitimmediate
Documentation/bpf/instruction-set.rst +3
-0+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 tozero,
Documentation/bpf/instruction-set.rst +16
-0+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 ofthe source
Documentation/bpf/instruction-set.rst +2
-0+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) ============== ====== =================Documentation/bpf/instruction-set.rst +5
-8-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 oneof:
Documentation/bpf/instruction-set.rst +8
-1-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) ======== ===============================================================
Documentation/bpf/instruction-set.rst +2
-0+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,
Documentation/bpf/instruction-set.rst the destination register is instead left unchanged. · line 174
Quoted 5 lines
Documentation/bpf/instruction-set.rst +1
-1@@ -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) (dst + src)
IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around? But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
Also, we do keep (u32) ^ (u32) for BPF_XOR below..
Quoted 104 lines
Documentation/bpf/instruction-set.rst +5
-5where '(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 registerand memory.
``BPF_MEM | <size> | BPF_STX`` means::
Documentation/bpf/instruction-set.rst +5
-5- *(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 andexchange
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 thatDocumentation/bpf/instruction-set.rst +1
-1+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 thevalue
Documentation/bpf/instruction-set.rst +6
-6-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 --2.33.4
RE: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 7 lines · [email protected] wrote:
Documentation/bpf/instruction-set.rst the destination register is instead left unchanged. · line 174
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32 bits are 0.
Quoted 2 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Quoted 1 line
Also, we do keep (u32) ^ (u32) for
BPF_XORbelow..
Well for XOR it's equivalent either way so didn't need a change.
Thanks for reviewing,
Dave
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 10 lines · Dave Thaler
Quoted 7 lines · [email protected] wrote:
Documentation/bpf/instruction-set.rst the destination register is instead left unchanged. · line 174
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Quoted 8 lines
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32 bits are 0.
Quoted 2 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Do we mention somewhere above/below that the operands are unsigned? IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
Quoted 7 lines
Quoted 1 line
Also, we do keep (u32) ^ (u32) for
BPF_XORbelow..Well for XOR it's equivalent either way so didn't need a change.
Thanks for reviewing,
Dave
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 19 lines · Stanislav Fomichev
Quoted 17 lines · Dave Thaler
Quoted 7 lines · [email protected] wrote:
Documentation/bpf/instruction-set.rst the destination register is instead left unchanged. · line 174
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32 bits are 0.
Quoted 2 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
Quoted 6 lines
Quoted 1 line
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Do we mention somewhere above/below that the operands are unsigned? IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.
RE: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 24 lines
Quoted 1 line · Stanislav Fomichev
On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[email protected]>
Quoted 7 lines · wrote:
Quoted 7 lines
Quoted 5 lines · [email protected] wrote:
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)Quoted 6 lines
Quoted 6 lines
Quoted 2 lines
IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32
bits are 0.
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Quoted 8 lines
Quoted 4 lines
Do we mention somewhere above/below that the operands are unsigned? IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.
Nothing prevents you from reading the new format as
dst = (u32) ((s32)dst + (s32)src)
because that implementation wouldn't be wrong.
Below is why, please point out any logic errors if you see any.
Mathematically, all of the following have identical results:
dst = (u32) ((s32)dst + (s32)src)
dst = (u32) ((u32)dst + (u32)src)
dst = (u32) ((s32)dst + (u32)src)
dst = (u32) ((u32)dst + (s32)src)u32 and s32, once you allow overflow/underflow to wrap within 32 bits, are mathematical rings (see https://en.wikipedia.org/wiki/Ring_(mathematics) ) meaning they're a circular space where X, X + 2^32, and X - 2^32 are equal. So (s32)src == (u32)src when the most significant bit is clear, and (s32)src == (u32)src - 2^32 when the most significant bit is set.
So the sign of the addition operands does not matter here. What matters is whether you do addition where the result can be more than 32 bits or not, which is what the new line makes unambiguous and the old line did not.
Specifically, nothing prevented mis-interpreting the old line as
u64 temp = (u32)dst;
temp += (u32)src;
dst = temp;
which would give the wrong answer since the upper 32-bits might be non-zero.
u64 temp = (s32)dst;
temp += (s32)src;
dst = (u32)temp;
Would however give the correct answer, same as
u64 temp = (u32)dst;
temp += (u32)src;
dst = (u32)temp;
As such, I maintain the old line was bad and the new line is still good. If you like I can explicitly say
dst = (u32) ((u32)dst + (u32)src)
but as noted above the operand sign is irrelevant once you cast the result.
Let me know if I'm missing anything.
Dave
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 30 lines · Dave Thaler
Quoted 30 lines
Quoted 1 line · Stanislav Fomichev
On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[email protected]>
Quoted 7 lines · wrote:
Quoted 7 lines
Quoted 5 lines · [email protected] wrote:
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)Quoted 6 lines
Quoted 6 lines
Quoted 2 lines
IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32
bits are 0.
Quoted 10 lines
Quoted 5 lines
Quoted 3 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Do we mention somewhere above/below that the operands are unsigned? IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
Quoted 7 lines
Quoted 3 lines
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.Nothing prevents you from reading the new format as
dst = (u32) ((s32)dst + (s32)src)because that implementation wouldn't be wrong.
Assuming the underlying cpu architecture is using 2s complement to represent negative numbers, right? (which is probably a safe one nowadays)
I don't know whether that's something that's spelled out in a generic BPF architecture doc.
Quoted 38 lines
Below is why, please point out any logic errors if you see any.
Mathematically, all of the following have identical results:
dst = (u32) ((s32)dst + (s32)src) dst = (u32) ((u32)dst + (u32)src) dst = (u32) ((s32)dst + (u32)src) dst = (u32) ((u32)dst + (s32)src)u32 and s32, once you allow overflow/underflow to wrap within 32 bits, are mathematical rings (see https://en.wikipedia.org/wiki/Ring_(mathematics) ) meaning they're a circular space where X, X + 2^32, and X - 2^32 are equal. So (s32)src == (u32)src when the most significant bit is clear, and (s32)src == (u32)src - 2^32 when the most significant bit is set.
So the sign of the addition operands does not matter here. What matters is whether you do addition where the result can be more than 32 bits or not, which is what the new line makes unambiguous and the old line did not.
Specifically, nothing prevented mis-interpreting the old line as
u64 temp = (u32)dst;
temp += (u32)src;
dst = temp;which would give the wrong answer since the upper 32-bits might be non-zero.
u64 temp = (s32)dst;
temp += (s32)src;
dst = (u32)temp;Would however give the correct answer, same as
u64 temp = (u32)dst;
temp += (u32)src;
dst = (u32)temp;As such, I maintain the old line was bad and the new line is still good.
[..]
Quoted 3 lines
If you like I can explicitly say
dst = (u32) ((u32)dst + (u32)src)but as noted above the operand sign is irrelevant once you cast the result.
That might be a good compromise. A bit verbose, but solves both "what happens to the overflow" and "what's the operand sign" questions.
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
In reply to Dave ThalerQuoted 57 lines · Dave Thaler
Quoted 25 lines
Quoted 1 line · Stanislav Fomichev
On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[email protected]>
Quoted 7 lines · wrote:
Quoted 7 lines
Quoted 5 lines · [email protected] wrote:
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::Documentation/bpf/instruction-set.rst +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)Quoted 6 lines
Quoted 6 lines
Quoted 2 lines
IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32
bits are 0.
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32 assignment.
Quoted 8 lines
Quoted 4 lines
Do we mention somewhere above/below that the operands are unsigned? IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.Nothing prevents you from reading the new format as
dst = (u32) ((s32)dst + (s32)src)because that implementation wouldn't be wrong.
Below is why, please point out any logic errors if you see any.
Mathematically, all of the following have identical results:
dst = (u32) ((s32)dst + (s32)src) dst = (u32) ((u32)dst + (u32)src) dst = (u32) ((s32)dst + (u32)src) dst = (u32) ((u32)dst + (s32)src)u32 and s32, once you allow overflow/underflow to wrap within 32 bits, are mathematical rings (see https://en.wikipedia.org/wiki/Ring_(mathematics) ) meaning they're a circular space where X, X + 2^32, and X - 2^32 are equal. So (s32)src == (u32)src when the most significant bit is clear, and (s32)src == (u32)src - 2^32 when the most significant bit is set.
So the sign of the addition operands does not matter here. What matters is whether you do addition where the result can be more than 32 bits or not, which is what the new line makes unambiguous and the old line did not.
Quoted 5 lines
Specifically, nothing prevented mis-interpreting the old line as
u64 temp = (u32)dst;
temp += (u32)src;
dst = temp;
Well dst_reg = (u32) dst_reg + (u32) src_reg implies C semantics, so it cannot be misinterpreted that way.
Quoted 6 lines
which would give the wrong answer since the upper 32-bits might be non-zero.
u64 temp = (s32)dst;
temp += (s32)src;
dst = (u32)temp;
Quoted 7 lines
Would however give the correct answer, same as
u64 temp = (u32)dst;
temp += (u32)src;
dst = (u32)temp;As such, I maintain the old line was bad and the new line is still good.
dst_reg = (u32) (dst_reg + src_reg)
implies that the operation is performed in 64-bit and then the result is truncated to 32-bit which is not correct.
If we had traditional carry, sign, overflow flags in bpf ISA the bit-ness of operation would be significant. Thankfully we don't, so it's not a big deal.
but let's do full verbose to avoid describing C semantics:
dst = (u32) ((u32)dst + (u32)src)
RE: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 102 lines
-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Friday, October 21, 2022 12:01 PM
To: Dave Thaler <[email protected]>
Cc: Stanislav Fomichev <[email protected]>; [email protected]; [email protected]
Subject: Re: [PATCH 3/4] bpf, docs: Use consistent names for the same fieldQuoted 20 lines · Dave Thaler
Quoted 20 lines
Quoted 2 lines · Stanislav Fomichev
On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
<[email protected]>Quoted 14 lines · wrote:
Quoted 14 lines
Quoted 7 lines · [email protected] wrote:
Review
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::(quoted diff) +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32
Quoted 6 lines
Quoted 6 lines
bits are 0.
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32
assignment.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Do we mention somewhere above/below that the operands are
unsigned?
Quoted 14 lines
Quoted 7 lines
Quoted 3 lines
IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.Nothing prevents you from reading the new format as
dst = (u32) ((s32)dst + (s32)src)because that implementation wouldn't be wrong.
Below is why, please point out any logic errors if you see any.
Quoted 9 lines
Mathematically, all of the following have identical results:
dst = (u32) ((s32)dst + (s32)src) dst = (u32) ((u32)dst + (u32)src) dst = (u32) ((s32)dst + (u32)src) dst = (u32) ((u32)dst + (s32)src)u32 and s32, once you allow overflow/underflow to wrap within 32 bits, are mathematical rings (see
https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wik
ipedia.org%2Fwiki%2FRing_&data=05%7C01%7Cdthaler%40microsoft.co m%7C44c24e3f67aa4a5c846f08dab396adb0%7C72f988bf86f141af91ab2d7cd01 1db47%7C1%7C0%7C638019756992501432%7CUnknown%7CTWFpbGZsb3d8e yJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D% 7C3000%7C%7C%7C&sdata=1rLsMSKUn0sNiZcN2RjDMH9jWIKCuf%2Fc3qZ d2QOanW8%3D&reserved=0(mathematics) ) meaning they're a circular space where X, X + 2^32, and X - 2^32 are equal.Quoted 8 lines
So (s32)src == (u32)src when the most significant bit is clear, and (s32)src == (u32)src - 2^32 when the most significant bit is set.
So the sign of the addition operands does not matter here. What matters is whether you do addition where the result can be more than 32 bits or not, which is what the new line makes unambiguous and the old line did not.
Quoted 5 lines
Specifically, nothing prevented mis-interpreting the old line as
u64 temp = (u32)dst;
temp += (u32)src;
dst = temp;Well
dst_reg= (u32)dst_reg+ (u32)src_regimplies C semantics, so it cannot be misinterpreted that way.Quoted 1 line
which would give the wrong answer since the upper 32-bits might be non-
zero.
Quoted 11 lines
u64 temp = (s32)dst;
temp += (s32)src;
dst = (u32)temp;Would however give the correct answer, same as
u64 temp = (u32)dst;
temp += (u32)src;
dst = (u32)temp;
Quoted 5 lines
Quoted 1 line
As such, I maintain the old line was bad and the new line is still good.
dst_reg= (u32) (dst_reg+src_reg)
implies that the operation is performed in 64-bit and then the result is truncated to 32-bit which is not correct.
It is mathematically correct as noted in my email above, you always get the correct result if you do the addition in 64-bit and then truncate. You get the same result as if you do the addition in 32-bit and then zero-extend.
Quoted 6 lines
If we had traditional carry, sign, overflow flags in bpf ISA the bit-ness of operation would be significant.
Thankfully we don't, so it's not a big deal.but let's do full verbose to avoid describing C semantics:
dst = (u32) ((u32)dst + (u32)src)
Ok, will do.
Dave
Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
Quoted 103 lines · Dave Thaler
Quoted 103 lines
-----Original Message-----
From: Alexei Starovoitov <[email protected]>
Sent: Friday, October 21, 2022 12:01 PM
To: Dave Thaler <[email protected]>
Cc: Stanislav Fomichev <[email protected]>; [email protected]; [email protected]
Subject: Re: [PATCH 3/4] bpf, docs: Use consistent names for the same fieldQuoted 20 lines · Dave Thaler
Quoted 20 lines
Quoted 2 lines · Stanislav Fomichev
On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
<[email protected]>Quoted 14 lines · wrote:
Quoted 14 lines
Quoted 7 lines · [email protected] wrote:
Review
Quoted 4 lines
``BPF_ADD |
BPF_X| BPF_ALU`` means::(quoted diff) +1
-1- dst_reg = (u32) dst_reg + (u32) src_reg; + dst = (u32) (dst + src)IIUC, by going from (u32) + (u32) to (u32)(), we want to signal that the value will just wrap around?
Right. In particular the old line could be confusing if one misinterpreted it as saying that the addition could overflow into a higher bit. The new line is intended to be unambiguous that the upper 32
Quoted 6 lines
Quoted 6 lines
bits are 0.
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines
But isn't it more confusing now because it's unclear what the sign of the dst/src is (s32 vs u32)?
As stated the upper 32 bits have to be 0, just as any other u32
assignment.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Do we mention somewhere above/below that the operands are
unsigned?
Quoted 14 lines
Quoted 7 lines
Quoted 3 lines
IOW, what prevents me from reading this new format as follows?
dst = (u32) ((s32)dst + (s32)src)
The doc mentions it, but I completely agree with you. The original line was better.
Dave, please undo this part.Nothing prevents you from reading the new format as
dst = (u32) ((s32)dst + (s32)src)because that implementation wouldn't be wrong.
Below is why, please point out any logic errors if you see any.
Quoted 9 lines
Mathematically, all of the following have identical results:
dst = (u32) ((s32)dst + (s32)src) dst = (u32) ((u32)dst + (u32)src) dst = (u32) ((s32)dst + (u32)src) dst = (u32) ((u32)dst + (s32)src)u32 and s32, once you allow overflow/underflow to wrap within 32 bits, are mathematical rings (see
https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wik
ipedia.org%2Fwiki%2FRing_&data=05%7C01%7Cdthaler%40microsoft.co m%7C44c24e3f67aa4a5c846f08dab396adb0%7C72f988bf86f141af91ab2d7cd01 1db47%7C1%7C0%7C638019756992501432%7CUnknown%7CTWFpbGZsb3d8e yJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D% 7C3000%7C%7C%7C&sdata=1rLsMSKUn0sNiZcN2RjDMH9jWIKCuf%2Fc3qZ d2QOanW8%3D&reserved=0(mathematics) ) meaning they're a circular space where X, X + 2^32, and X - 2^32 are equal.Quoted 8 lines
So (s32)src == (u32)src when the most significant bit is clear, and (s32)src == (u32)src - 2^32 when the most significant bit is set.
So the sign of the addition operands does not matter here. What matters is whether you do addition where the result can be more than 32 bits or not, which is what the new line makes unambiguous and the old line did not.
Quoted 5 lines
Specifically, nothing prevented mis-interpreting the old line as
u64 temp = (u32)dst;
temp += (u32)src;
dst = temp;Well
dst_reg= (u32)dst_reg+ (u32)src_regimplies C semantics, so it cannot be misinterpreted that way.Quoted 1 line
which would give the wrong answer since the upper 32-bits might be non-
zero.
Quoted 11 lines
u64 temp = (s32)dst;
temp += (s32)src;
dst = (u32)temp;Would however give the correct answer, same as
u64 temp = (u32)dst;
temp += (u32)src;
dst = (u32)temp;
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
As such, I maintain the old line was bad and the new line is still good.
dst_reg= (u32) (dst_reg+src_reg)
implies that the operation is performed in 64-bit and then the result is truncated to 32-bit which is not correct.It is mathematically correct as noted in my email above, you always get the correct result if you do the addition in 64-bit and then truncate. You get the same result as if you do the addition in 32-bit and then zero-extend.
No. It's not about the result in 32-bits. The flags will be different.
Quoted 10 lines
Quoted 6 lines
If we had traditional carry, sign, overflow flags in bpf ISA the bit-ness of operation would be significant.
Thankfully we don't, so it's not a big deal.but let's do full verbose to avoid describing C semantics:
dst = (u32) ((u32)dst + (u32)src)Ok, will do.
Dave
PATCH 4/4 bpf, docs: Explain helper functions
In reply to [email protected]From: Dave Thaler <[email protected]>
Explain helper functions.
Kernel functions and bpf to bpf calls are covered in a later commit in this set ("Add extended call instructions").
--- Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-)
Documentation/bpf/instruction-set.rst +17 -1
@@ -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
Re: [PATCH 4/4] bpf, docs: Explain helper functions
Quoted 30 lines · On 10/19, [email protected] wrote:
From: Dave Thaler <[email protected]>
Explain helper functions.
Kernel functions and bpf to bpf calls are covered in a later commit in this set ("Add extended call instructions").
Signed-off-by Dave Thaler <[email protected]>--- Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-)Documentation/bpf/instruction-set.rst +1
-1@@ -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 beforedoing a
BPF_EXIT.
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
(the series looks good to me, but I'm assuming Alexei will take a look at these anywey because he did for the previous submissions)
Not really related to the patch, but in general, quoting from the above:
"BPF programs can call ... by the eBPF runtime". I know we do it all the time and use BPF/eBPF interchangeably, but should we try to be consistent at least within the same page?
$ grep -r 'eBPF program' Documentation/bpf/ | wc -l 34 $ grep -r ' BPF program' Documentation/bpf/ | wc -l 97
Quoted 21 lines
Documentation/bpf/instruction-set.rst +4
-0+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 sharedfunction
Documentation/bpf/instruction-set.rst +5
-0+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 5arguments,
+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
===========================
--
2.33.4