Skip to contentSkip to conversation

Shift operations are defined to use a mask

PATCH Applied Dave Thaler 4 participants 6 messages May 9, 2023 – May 17, 2023

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

PATCH 1/1 Shift operations are defined to use a mask

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like negative) is undefined.

---
 Documentation/bpf/instruction-set.rst | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
Documentation/bpf/instruction-set.rst +6 -3
index 492980ece1a..6644842cd3e 100644
@@ -163,13 +163,13 @@ BPF_MUL   0x20   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_LSH   0x60   dst <<= (src & mask)
+BPF_RSH   0x70   dst >>= (src & mask)
 BPF_NEG   0x80   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_ARSH  0xc0   sign extending dst >>= (src & mask)
 BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 ========  =====  ==========================================================
 
@@ -204,6 +204,9 @@ for ``BPF_ALU64``, 'imm' is first sign extended to 64 bits and the result
 interpreted as an unsigned 64-bit value. There are no instructions for
 signed division or modulo.
 
+Shift operations use a mask of 0x3F (63) for 64-bit operations and 0x1F (31)
+for 32-bit operations.
+
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
 
Signature · 1 line
2.33.4
Acked-by on v1 1/1
#1 lore raw
Quoted 7 lines · Dave Thaler

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like negative) is undefined.

LGTM with a few nit below.

Quoted 12 lines
---
  Documentation/bpf/instruction-set.rst | 9 ++++++---
  1 file changed, 6 insertions(+), 3 deletions(-)
Documentation/bpf/instruction-set.rst +0 -0
index 492980ece1a..6644842cd3e 100644
@@ -163,13 +163,13 @@ BPF_MUL   0x20   dst \*= src
  BPF_DIV   0x30   dst = (src != 0) ? (dst / src) : 0
  BPF_OR    0x40   dst \|= src
  BPF_AND   0x50   dst &= src

Documentation/bpf/instruction-set.rst BPF_MUL 0x20 dst \*= src · line 172

Quoted 10 lines
Documentation/bpf/instruction-set.rst +3 -3
-BPF_LSH   0x60   dst <<= src
-BPF_RSH   0x70   dst >>= src
+BPF_LSH   0x60   dst <<= (src & mask)
+BPF_RSH   0x70   dst >>= (src & mask)
  BPF_NEG   0x80   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_ARSH  0xc0   sign extending dst >>= (src & mask)
		    dst s>>= (src & mask)

?

Quoted 13 lines
Documentation/bpf/instruction-set.rst +3 -0
  BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
  ========  =====  ==========================================================
 
@@ -204,6 +204,9 @@ for ``BPF_ALU64``, 'imm' is first sign extended to 64 bits and the result
  interpreted as an unsigned 64-bit value. There are no instructions for
  signed division or modulo.
 
+Shift operations use a mask of 0x3F (63) for 64-bit operations and 0x1F (31)
+for 32-bit operations.
+
  Byte swap instructions
  ~~~~~~~~~~~~~~~~~~~~~~
 
#2 lore raw
Quoted 12 lines · Yonghong Song
Quoted 7 lines · Dave Thaler

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like negative) is undefined.

LGTM with a few nit below.

[...]

Quoted 5 lines

Documentation/bpf/instruction-set.rst BPF_MUL 0x20 dst \*= src · line 172

Quoted 2 lines
Documentation/bpf/instruction-set.rst +1 -1
-BPF_ARSH  0xc0   sign extending shift right
+BPF_ARSH  0xc0   sign extending dst >>= (src & mask)
		    dst s>>= (src & mask)

?

I had thought about that, but based on Jose's LSF/MM/BPF presentation yesterday there are multiple such syntaxes.

">>=" vs "s>>=" is only one of several. There's ">>" vs ">>>",
there's assembly-like, etc. So I thought that it would take
more text to define "s>>" as meaning signing extending right shift, than just saying sign extending ">>=" here. And I didn't want to just assume the reader knows what "s>>" means without defining it since neither the C standard nor gcc use "s>>".

Thanks for the Ack.

Dave

#3 lore raw
Quoted 23 lines · Dave Thaler
Quoted 12 lines · Yonghong Song
Quoted 7 lines · Dave Thaler

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like negative) is undefined.

LGTM with a few nit below.

[...]

Quoted 5 lines

Documentation/bpf/instruction-set.rst BPF_MUL 0x20 dst \*= src · line 172

Quoted 2 lines
Documentation/bpf/instruction-set.rst +1 -1
-BPF_ARSH  0xc0   sign extending shift right
+BPF_ARSH  0xc0   sign extending dst >>= (src & mask)
		    dst s>>= (src & mask)

?

I had thought about that, but based on Jose's LSF/MM/BPF presentation yesterday there are multiple such syntaxes.

Quoted 7 lines

">>=" vs "s>>=" is only one of several. There's ">>" vs ">>>",
there's assembly-like, etc. So I thought that it would take
more text to define "s>>" as meaning signing extending right shift, than just saying sign extending ">>=" here. And I didn't want to just assume the reader knows what "s>>" means without defining it since neither the C standard nor gcc use "s>>".

gcc will implement clang asm syntax as well. So for the consistency of verifier log, bpftool xlated dump, and llvm-objdump result. I think using "s>>=" syntax is the best.

The following table is the alu opcode in kernel/bpf/disasm.c (used by both kernel verifier and bpftool xlated dump):

const char *const bpf_alu_string[16] = {
        [BPF_ADD >> 4]  = "+=",
        [BPF_SUB >> 4]  = "-=",
        [BPF_MUL >> 4]  = "*=",
        [BPF_DIV >> 4]  = "/=",
        [BPF_OR  >> 4]  = "|=",
        [BPF_AND >> 4]  = "&=",
        [BPF_LSH >> 4]  = "<<=",
        [BPF_RSH >> 4]  = ">>=",
        [BPF_NEG >> 4]  = "neg",
        [BPF_MOD >> 4]  = "%=",
        [BPF_XOR >> 4]  = "^=",
        [BPF_MOV >> 4]  = "=",
        [BPF_ARSH >> 4] = "s>>=",
        [BPF_END >> 4]  = "endian",
};

Also, in Documentation/bpf/instruction-set.rst:

========  =====  ==========================================================
code      value  description
========  =====  ==========================================================
BPF_ADD   0x00   dst += src
BPF_SUB   0x10   dst -= src
BPF_MUL   0x20   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 != 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)
========  =====  ==========================================================

In the above, the BPF_NEG is specified as
'dst = ~src`, which is not correct, it should be
'dst = -dst'.

See kernel/bpf/core.c:

        ALU_NEG:
                DST = (u32) -DST;
                CONT;
        ALU64_NEG:
                DST = -DST;
                CONT;

Could you help fix it?

Quoted 5 lines

Thanks for the Ack.

Dave

#4 lore raw
Quoted 32 lines · Yonghong Song
Quoted 24 lines · Dave Thaler
Quoted 13 lines · Yonghong Song
Quoted 8 lines · Dave Thaler

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like
negative) is undefined.

LGTM with a few nit below.

[...]

Quoted 5 lines

Documentation/bpf/instruction-set.rst BPF_MUL 0x20 dst \*= src · line 172

Quoted 2 lines
Documentation/bpf/instruction-set.rst +1 -1
-BPF_ARSH  0xc0   sign extending shift right
+BPF_ARSH  0xc0   sign extending dst >>= (src & mask)
		    dst s>>= (src & mask)

?

I had thought about that, but based on Jose's LSF/MM/BPF presentation yesterday there are multiple such syntaxes.

Quoted 6 lines

">>=" vs "s>>=" is only one of several. There's ">>" vs ">>>",
there's assembly-like, etc. So I thought that it would take
more text to define "s>>" as meaning signing extending right shift, than just saying sign extending ">>=" here. And I didn't want to just assume the reader knows what "s>>" means without defining it since neither the C standard nor gcc use "s>>".

Quoted 3 lines

gcc will implement clang asm syntax as well. So for the consistency of verifier log, bpftool xlated dump, and llvm-objdump result.
I think using "s>>=" syntax is the best.

Just posting to the list what we discussed in person today.
I will do this in a subsequent submission since that comment also affects the comparison operators, so treating it as separate from this patch.

Quoted 48 lines

The following table is the alu opcode in kernel/bpf/disasm.c (used by both kernel verifier and bpftool xlated dump):

const char *const bpf_alu_string[16] = {
         [BPF_ADD >> 4]  = "+=",
         [BPF_SUB >> 4]  = "-=",
         [BPF_MUL >> 4]  = "*=",
         [BPF_DIV >> 4]  = "/=",
         [BPF_OR  >> 4]  = "|=",
         [BPF_AND >> 4]  = "&=",
         [BPF_LSH >> 4]  = "<<=",
         [BPF_RSH >> 4]  = ">>=",
         [BPF_NEG >> 4]  = "neg",
         [BPF_MOD >> 4]  = "%=",
         [BPF_XOR >> 4]  = "^=",
         [BPF_MOV >> 4]  = "=",
         [BPF_ARSH >> 4] = "s>>=",
         [BPF_END >> 4]  = "endian",
};

Also, in Documentation/bpf/instruction-set.rst:

======== =====
==========================================================
code value description
======== =====
==========================================================

BPF_ADD   0x00   dst += src
BPF_SUB   0x10   dst -= src
BPF_MUL   0x20   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 != 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)
========  =====

==========================================================

In the above, the BPF_NEG is specified as 'dst = ~src`, which is not correct, it should be 'dst = -dst'.

See kernel/bpf/core.c:

Quoted 8 lines
         ALU_NEG:
                 DST = (u32) -DST;
                 CONT;
         ALU64_NEG:
                 DST = -DST;
                 CONT;

Could you help fix it?

Yes I can put it into the same patch as the other change discussed above.

Would like to see the current one merged so I can base the next one on top of this one.

Thanks,
Dave

#5 lore raw
In reply to Dave Thaler
This patch was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Hello:

This patch was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Quoted 9 lines · On Tue, 9 May 2023 18:08:45 +0000 you wrote:

From: Dave Thaler <[email protected]>

Update the documentation regarding shift operations to explain the use of a mask, since otherwise shifting by a value out of range (like negative) is undefined.

[...]

Here is the summary with links:
- [bpf-next] Shift operations are defined to use a mask

    https://git.kernel.org/bpf/bpf-next/c/8819495a754e

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html