Skip to contentSkip to conversation

bpf, docs: Fix modulo zero, division by zero, overflow, and underflow

PATCH In review [email protected] 5 participants 10 messages Jan 17, 2023 – Jan 24, 2023

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

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

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed 32-bit comments from Daniel and Stanislav.

---
 Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +14 -2
index e672d5ec6cc..fcd4db45717 100644
@@ -99,19 +99,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;
@@ -128,6 +135,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first converted to an unsigned
+32-bit value, whereas for `BPF_ALU64`, 'imm' is first sign extended
+to 64 bits and then converted to an unsigned 64-bit value.  There
+are no instructions for signed division or modulo.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
#1 lore raw

Documentation/bpf/instruction-set.rst BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below) · line 142

Quoted 6 lines
Documentation/bpf/instruction-set.rst +5 -0
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first converted to an unsigned
+32-bit value, whereas for `BPF_ALU64`, '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.

English is not my native language, but I think "converted" may be too generic for this paragraph: are the same bits reinterpreted as unsigned? Or an actual conversion like absolute value is performed?

Wouldn't it be better to say "interpreted as" instead of "converted to" in this case?

Something like this:

"Also note that the division and modulo operations are unsigned.
Thus, for BPF_ALU, 'imm' is interpreted as an unsigned 32-bit value, whereas 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."

#2 lore raw

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

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed conversion comment from Jose.

---
 Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +14 -2
index e672d5ec6cc..f79dae527ad 100644
@@ -99,19 +99,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;
@@ -128,6 +135,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first interpreted as an unsigned
+32-bit value, whereas 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.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
maintainer
#3 lore raw
Quoted 32 lines · On 1/18/23 4:23 PM, [email protected] wrote:

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed conversion comment from Jose.

---
  Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
  1 file changed, 14 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +2 -2
index e672d5ec6cc..f79dae527ad 100644
@@ -99,19 +99,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

Documentation/bpf/instruction-set.rst code value description · line 120

Quoted 10 lines
Documentation/bpf/instruction-set.rst +6 -0
  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.

Looks good to go with one small nit for the previous sentence which could be misinterpreted. The rewrites from verifier for modulo op are:

      mod32:                            mod64:

      (16) if w0 == 0x0 goto pc+2       (15) if r0 == 0x0 goto pc+1
      (9c) w1 %= w0                     (9f) r1 %= r0
      (05) goto pc+1
      (bc) w1 = w1

So for BPF_ALU as 32-bit op, it is expected that the result is 32-bit value, too. So for 32-bit op the destination register is truncated to 32-bit value. (Related commit 9b00f1b78809 ("bpf: Fix truncation handling for mod32 dst reg wrt zero")).

Quoted 16 lines
Documentation/bpf/instruction-set.rst +5 -0
  ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
    dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +135,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
    dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first interpreted as an unsigned
+32-bit value, whereas 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.
 
  Byte swap instructions
  ~~~~~~~~~~~~~~~~~~~~~~
#4 lore raw

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

In reply to [email protected]

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed comments from Daniel.

---
 Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +16 -2
index e672d5ec6cc..dd37cc5c0bf 100644
@@ -99,19 +99,28 @@ 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 set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the value is truncated to 32 bits.
+
 ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
   dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +137,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas 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.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
#5 lore raw
Quoted 2 lines · On Thu, Jan 19, 2023 at 2:25 PM <[email protected]> wrote:
Documentation/bpf/instruction-set.rst +1 -1
-BPF_MOD   0x90   dst %= src
+BPF_MOD   0x90   dst = (src != 0) ? (dst % src) : dst

...

Documentation/bpf/instruction-set.rst code value description · line 122

Quoted 4 lines
Documentation/bpf/instruction-set.rst +4 -0
+If execution would result in modulo by zero,
+the destination register is instead set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the value is truncated to 32 bits.

These two don't match.
Probably should say that for ALU64 dst doesn't change and for alu32 it's upper 32-bits are zeroed.

#6 lore raw

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

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed comments from Alexei.

---
 Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +16 -2
index e672d5ec6cc..2546630fcbd 100644
@@ -99,19 +99,28 @@ 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 set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the upper 32 bits are zeroed.
+
 ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
   dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +137,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas 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.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
maintainer
#7 lore raw

On 1/20/23 9:16 PM, [email protected] wrote:
[...]

Quoted 2 lines
Documentation/bpf/instruction-set.rst +1 -1
-BPF_MOD   0x90   dst %= src
+BPF_MOD   0x90   dst = (src != 0) ? (dst % src) : dst   

[...]

Documentation/bpf/instruction-set.rst code value description · line 122

Quoted 4 lines
Documentation/bpf/instruction-set.rst +4 -0
+If execution would result in modulo by zero,
+the destination register is instead set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the upper 32 bits are zeroed.

I think the "the destination register is instead set to the source register as ``BPF_MOV`` would do" is a bit ambiguous. Could we just simplify it to the following:

If execution would result in modulo by zero, for ``BPF_ALU64`` the value of the destination register is unchanged whereas for ``BPF_ALU`` the upper 32 bits of the destination register are zeroed.

#8 lore raw

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

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed comments from Daniel.

---
 Documentation/bpf/instruction-set.rst | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +15 -2
index e672d5ec6cc..a7f4574562c 100644
@@ -99,19 +99,27 @@ 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, for ``BPF_ALU64``
+the value of the destination register is unchanged whereas for
+``BPF_ALU`` the upper 32 bits of the destination register are zeroed.
+
 ``BPF_ADD | BPF_X | BPF_ALU`` means::
 
   dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +136,11 @@ BPF_END   0xd0   byte swap operations (see `Byte swap instructions`_ below)
 
   dst_reg = dst_reg ^ imm32
 
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas 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.
 
 Byte swap instructions
 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
#9 lore raw
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 8 lines · On Tue, 24 Jan 2023 00:12:18 +0000 you wrote:

From: Dave Thaler <[email protected]>

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

Changes from last submission: addressed comments from Daniel.

[...]

Here is the summary with links:
- bpf, docs: Fix modulo zero, division by zero, overflow, and underflow

    https://git.kernel.org/bpf/bpf-next/c/0eb9d19e2201

You are awesome, thank you!

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