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

Commit Message

Dave Thaler Oct. 19, 2022, 6:38 p.m. UTC

From: Dave Thaler <[e-mail]>

Use consistent names for the same field

Signed-off-by: Dave Thaler <[e-mail]>
---
 Documentation/bpf/instruction-set.rst | 107 ++++++++++++++++++--------
 1 file changed, 76 insertions(+), 31 deletions(-)

Comments

Stanislav Fomichev Oct. 19, 2022, 8:57 p.m. UTC | #1

On 10/19, [e-mail] wrote:
> From: Dave Thaler <[e-mail]>

> Use consistent names for the same field

> Signed-off-by: Dave Thaler <[e-mail]>
> ---
>   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

Dave Thaler Oct. 19, 2022, 9:06 p.m. UTC | #2

[e-mail] 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

Stanislav Fomichev Oct. 19, 2022, 11:33 p.m. UTC | #3

On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[e-mail]> wrote:
>
> [e-mail] 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
>

Alexei Starovoitov Oct. 19, 2022, 11:37 p.m. UTC | #4

On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]> wrote:
>
> On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[e-mail]> wrote:
> >
> > [e-mail] 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.

Dave Thaler Oct. 21, 2022, 5:56 p.m. UTC | #5

> On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]>
> wrote:
> > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[e-mail]>
> wrote:
> > >
> > > [e-mail] 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

Stanislav Fomichev Oct. 21, 2022, 6:35 p.m. UTC | #6

On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <[e-mail]> wrote:
>
> > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]>
> > wrote:
> > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[e-mail]>
> > wrote:
> > > >
> > > > [e-mail] 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.

Alexei Starovoitov Oct. 21, 2022, 7:01 p.m. UTC | #7

On Fri, Oct 21, 2022 at 10:56 AM Dave Thaler <[e-mail]> wrote:
>
> > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]>
> > wrote:
> > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler <[e-mail]>
> > wrote:
> > > >
> > > > [e-mail] 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)

Dave Thaler Oct. 21, 2022, 7:24 p.m. UTC | #8

> -----Original Message-----
> From: Alexei Starovoitov <[e-mail]>
> Sent: Friday, October 21, 2022 12:01 PM
> To: Dave Thaler <[e-mail]>
> Cc: Stanislav Fomichev <[e-mail]>; [e-mail];
> [e-mail]
> 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 <[e-mail]> wrote:
> >
> > > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]>
> > > wrote:
> > > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
> > > > <[e-mail]>
> > > wrote:
> > > > >
> > > > > [e-mail] 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

Alexei Starovoitov Oct. 21, 2022, 8:07 p.m. UTC | #9

On Fri, Oct 21, 2022 at 12:24 PM Dave Thaler <[e-mail]> wrote:
>
>
>
> > -----Original Message-----
> > From: Alexei Starovoitov <[e-mail]>
> > Sent: Friday, October 21, 2022 12:01 PM
> > To: Dave Thaler <[e-mail]>
> > Cc: Stanislav Fomichev <[e-mail]>; [e-mail];
> > [e-mail]
> > 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 <[e-mail]> wrote:
> > >
> > > > On Wed, Oct 19, 2022 at 4:35 PM Stanislav Fomichev <[e-mail]>
> > > > wrote:
> > > > > On Wed, Oct 19, 2022 at 2:06 PM Dave Thaler
> > > > > <[e-mail]>
> > > > wrote:
> > > > > >
> > > > > > [e-mail] 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

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