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

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

[dthaler1968]

From: Dave Thaler <dthaler@microsoft.com>

Use consistent names for the same field

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++--------
 1 file changed, 76 insertions(+), 31 deletions(-)

diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index 3a64d4b49..29b599c70 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -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
-- 
2.33.4

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

[sdf]

On 10/19, dthaler1968@googlemail.com wrote:
> From: Dave Thaler <dthaler@microsoft.com>

> Use consistent names for the same field

> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> ---
>   Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++--------
>   1 file changed, 76 insertions(+), 31 deletions(-)

> diff --git a/Documentation/bpf/instruction-set.rst  
> b/Documentation/bpf/instruction-set.rst
> index 3a64d4b49..29b599c70 100644
> --- a/Documentation/bpf/instruction-set.rst
> +++ b/Documentation/bpf/instruction-set.rst
> @@ -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)

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


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

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

[Dave Thaler]

sdf@google.com wrote: 
> >   ``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? 

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.

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

> Also, we do keep (u32) ^ (u32) for BPF_XOR below..

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

[Stanislav Fomichev]

On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <dthaler@microsoft.com> wrote:
>
> sdf@google.com wrote:
> > >   ``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?
>
> 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.
>
> > 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)

> > Also, we do keep (u32) ^ (u32) for BPF_XOR below..
>
> 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

[Alexei Starovoitov]

On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com> wrote:
>
> On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <dthaler@microsoft.com> wrote:
> >
> > sdf@google.com wrote:
> > > >   ``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?
> >
> > 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.
> >
> > > 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)

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

[Dave Thaler]

> On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com>
> wrote:
> > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <dthaler@microsoft.com>
> wrote:
> > >
> > > sdf@google.com wrote:
> > > > >   ``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?
> > >
> > > 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.
> > >
> > > > 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)
> 
> 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

[Stanislav Fomichev]

On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <dthaler@microsoft.com> wrote:
>
> > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com>
> > wrote:
> > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <dthaler@microsoft.com>
> > wrote:
> > > >
> > > > sdf@google.com wrote:
> > > > > >   ``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?
> > > >
> > > > 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.
> > > >
> > > > > 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)
> >
> > 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.

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

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

[Alexei Starovoitov]

On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <dthaler@microsoft.com> wrote:
>
> > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com>
> > wrote:
> > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <dthaler@microsoft.com>
> > wrote:
> > > >
> > > > sdf@google.com wrote:
> > > > > >   ``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?
> > > >
> > > > 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.
> > > >
> > > > > 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)
> >
> > 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;

Well dst_reg = (u32) dst_reg + (u32) src_reg
implies C semantics, so it cannot be misinterpreted that way.

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

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

[Dave Thaler]

> -----Original Message-----
> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Sent: Friday, October 21, 2022 12:01 PM
> To: Dave Thaler <dthaler@microsoft.com>
> Cc: Stanislav Fomichev <sdf@google.com>; dthaler1968@googlemail.com;
> bpf@vger.kernel.org
> Subject: Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
> 
> On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <dthaler@microsoft.com> wrote:
> >
> > > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com>
> > > wrote:
> > > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
> > > > <dthaler@microsoft.com>
> > > wrote:
> > > > >
> > > > > sdf@google.com wrote:
> > > > > > >   ``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?
> > > > >
> > > > > 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.
> > > > >
> > > > > > 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)
> > >
> > > 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://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wik
> ipedia.org%2Fwiki%2FRing_&amp;data=05%7C01%7Cdthaler%40microsoft.co
> m%7C44c24e3f67aa4a5c846f08dab396adb0%7C72f988bf86f141af91ab2d7cd01
> 1db47%7C1%7C0%7C638019756992501432%7CUnknown%7CTWFpbGZsb3d8e
> yJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%
> 7C3000%7C%7C%7C&amp;sdata=1rLsMSKUn0sNiZcN2RjDMH9jWIKCuf%2Fc3qZ
> d2QOanW8%3D&amp;reserved=0(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;
> 
> Well dst_reg = (u32) dst_reg + (u32) src_reg implies C semantics, so it cannot
> be misinterpreted that way.
> 
> > 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.
> 
> 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.

> 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

[Alexei Starovoitov]

On Fri, Oct 21, 2022 at 12:24 PM Dave Thaler <dthaler@microsoft.com> wrote:
>
>
>
> > -----Original Message-----
> > From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> > Sent: Friday, October 21, 2022 12:01 PM
> > To: Dave Thaler <dthaler@microsoft.com>
> > Cc: Stanislav Fomichev <sdf@google.com>; dthaler1968@googlemail.com;
> > bpf@vger.kernel.org
> > Subject: Re: [PATCH 3/4] bpf, docs: Use consistent names for the same field
> >
> > On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <dthaler@microsoft.com> wrote:
> > >
> > > > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <sdf@google.com>
> > > > wrote:
> > > > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
> > > > > <dthaler@microsoft.com>
> > > > wrote:
> > > > > >
> > > > > > sdf@google.com wrote:
> > > > > > > >   ``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?
> > > > > >
> > > > > > 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.
> > > > > >
> > > > > > > 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)
> > > >
> > > > 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://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wik
> > ipedia.org%2Fwiki%2FRing_&amp;data=05%7C01%7Cdthaler%40microsoft.co
> > m%7C44c24e3f67aa4a5c846f08dab396adb0%7C72f988bf86f141af91ab2d7cd01
> > 1db47%7C1%7C0%7C638019756992501432%7CUnknown%7CTWFpbGZsb3d8e
> > yJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%
> > 7C3000%7C%7C%7C&amp;sdata=1rLsMSKUn0sNiZcN2RjDMH9jWIKCuf%2Fc3qZ
> > d2QOanW8%3D&amp;reserved=0(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;
> >
> > Well dst_reg = (u32) dst_reg + (u32) src_reg implies C semantics, so it cannot
> > be misinterpreted that way.
> >
> > > 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.
> >
> > 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.

> > 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 1/4] bpf, docs: Add note about type convention

[dthaler1968]

From: Dave Thaler <dthaler@microsoft.com>

Add note about type convention

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/instruction-set.rst | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index 5d798437d..bed6d33fc 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -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

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

[dthaler1968]

From: Dave Thaler <dthaler@microsoft.com>

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

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/instruction-set.rst | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index bed6d33fc..74dcc13a9 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -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
 ~~~~~~~~~~~~~~~~~~~~~~
-- 
2.33.4

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

[dthaler1968]

From: Dave Thaler <dthaler@microsoft.com>

Use consistent names for the same field

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++--------
 1 file changed, 76 insertions(+), 31 deletions(-)

diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index 74dcc13a9..aa1b37cb5 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -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
-- 
2.33.4

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

[dthaler1968]

From: Dave Thaler <dthaler@microsoft.com>

Explain helper functions

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index aa1b37cb5..40c3293d6 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -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
 ===========================
-- 
2.33.4

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

[sdf]

On 10/27, dthaler1968@googlemail.com wrote:
> From: Dave Thaler <dthaler@microsoft.com>

> Add note about type convention

> Signed-off-by: Dave Thaler <dthaler@microsoft.com>

For the series:
Acked-by: Stanislav Fomichev <sdf@google.com>

Carry-on from my shift last week.

> ---
>   Documentation/bpf/instruction-set.rst | 7 +++++++
>   1 file changed, 7 insertions(+)

> diff --git a/Documentation/bpf/instruction-set.rst  
> b/Documentation/bpf/instruction-set.rst
> index 5d798437d..bed6d33fc 100644
> --- a/Documentation/bpf/instruction-set.rst
> +++ b/Documentation/bpf/instruction-set.rst
> @@ -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

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

[Alexei Starovoitov]

On Thu, Oct 27, 2022 at 7:46 AM <dthaler1968@googlemail.com> wrote:
>
> +
> +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)
?

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

[Alexei Starovoitov]

On Thu, Oct 27, 2022 at 7:46 AM <dthaler1968@googlemail.com> wrote:
>
> From: Dave Thaler <dthaler@microsoft.com>
>
> Explain helper functions
>
> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> ---
>  Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
>  1 file changed, 17 insertions(+), 1 deletion(-)
>
> diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
> index aa1b37cb5..40c3293d6 100644
> --- a/Documentation/bpf/instruction-set.rst
> +++ b/Documentation/bpf/instruction-set.rst
> @@ -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

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

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

[Dave Thaler]

> -----Original Message-----
> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Sent: Wednesday, November 9, 2022 1:51 AM
> To: dthaler1968@googlemail.com
> Cc: bpf <bpf@vger.kernel.org>; Dave Thaler <dthaler@microsoft.com>
> Subject: Re: [PATCH 4/4] bpf, docs: Explain helper functions
> 
> On Thu, Oct 27, 2022 at 7:46 AM <dthaler1968@googlemail.com> wrote:
> >
> > From: Dave Thaler <dthaler@microsoft.com>
> >
> > Explain helper functions
> >
> > Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> > ---
> >  Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
> >  1 file changed, 17 insertions(+), 1 deletion(-)
> >
> > diff --git a/Documentation/bpf/instruction-set.rst
> > b/Documentation/bpf/instruction-set.rst
> > index aa1b37cb5..40c3293d6 100644
> > --- a/Documentation/bpf/instruction-set.rst
> > +++ b/Documentation/bpf/instruction-set.rst
> > @@ -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
> 
> 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

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

[Dave Thaler]

Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: 
> On Thu, Oct 27, 2022 at 7:46 AM <dthaler1968@googlemail.com> wrote:
> >
> > +
> > +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

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

[Alexei Starovoitov]

On Wed, Nov 9, 2022 at 2:30 AM Dave Thaler <dthaler@microsoft.com> wrote:
>
> > -----Original Message-----
> > From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> > Sent: Wednesday, November 9, 2022 1:51 AM
> > To: dthaler1968@googlemail.com
> > Cc: bpf <bpf@vger.kernel.org>; Dave Thaler <dthaler@microsoft.com>
> > Subject: Re: [PATCH 4/4] bpf, docs: Explain helper functions
> >
> > On Thu, Oct 27, 2022 at 7:46 AM <dthaler1968@googlemail.com> wrote:
> > >
> > > From: Dave Thaler <dthaler@microsoft.com>
> > >
> > > Explain helper functions
> > >
> > > Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> > > ---
> > >  Documentation/bpf/instruction-set.rst | 18 +++++++++++++++++-
> > >  1 file changed, 17 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/Documentation/bpf/instruction-set.rst
> > > b/Documentation/bpf/instruction-set.rst
> > > index aa1b37cb5..40c3293d6 100644
> > > --- a/Documentation/bpf/instruction-set.rst
> > > +++ b/Documentation/bpf/instruction-set.rst
> > > @@ -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
> >
> > 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)?

I prefer to use BPF everywhere.