Skip to contentSkip to conversation

bpf, docs: Define signed modulo as using truncated division

PATCH Applied Dave Thaler 5 participants 6 messages Oct 17, 2023 – Oct 19, 2023

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

PATCH 1/1 bpf, docs: Define signed modulo as using truncated division

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/[email protected]/

---
 Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
 1 file changed, 8 insertions(+)
Documentation/bpf/standardization/instruction-set.rst +8 -0
index c5d53a6e8c7..245b6defc29 100644
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
 is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
 interpreted as a 64-bit signed value.
 
+Note that there are varying definitions of the signed modulo operation
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
 The ``BPF_MOVSX`` instruction does a move operation with sign extension.
 ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
 bit operands, and zeroes the remaining upper 32 bits.
Signature · 1 line
2.33.4
reviewer Acked-by on v1 1/1
#1 lore raw
Quoted 9 lines · Dave Thaler

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

Quoted 5 lines

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/[email protected]/

+cc Eduard as well in case he wants to take a look.

Quoted 27 lines
---
 Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
 1 file changed, 8 insertions(+)
Documentation/bpf/standardization/instruction-set.rst +8 -0
index c5d53a6e8c7..245b6defc29 100644
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
 is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
 interpreted as a 64-bit signed value.
 
+Note that there are varying definitions of the signed modulo operation
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
 The ``BPF_MOVSX`` instruction does a move operation with sign extension.
 ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
 bit operands, and zeroes the remaining upper 32 bits.
Signature · 1 line
2.33.4
maintainer Acked-by on v1 1/1
#2 lore raw
In reply to Dave Thaler
Quoted 27 lines · Dave Thaler

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/[email protected]/

---
 Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
 1 file changed, 8 insertions(+)
Documentation/bpf/standardization/instruction-set.rst +1 -0
index c5d53a6e8c7..245b6defc29 100644
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
 is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
 interpreted as a 64-bit signed value.
 
+Note that there are varying definitions of the signed modulo operation

Documentation/bpf/standardization/instruction-set.rst For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``, · line 296

Quoted 10 lines
Documentation/bpf/standardization/instruction-set.rst +7 -0
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
 The ``BPF_MOVSX`` instruction does a move operation with sign extension.
 ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
 bit operands, and zeroes the remaining upper 32 bits.
maintainer
#3 lore raw
Quoted 27 lines · Eduard Zingerman
Quoted 26 lines · Dave Thaler

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/[email protected]/

---
  Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
  1 file changed, 8 insertions(+)
Documentation/bpf/standardization/instruction-set.rst +0 -0
index c5d53a6e8c7..245b6defc29 100644
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
  is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
  interpreted as a 64-bit signed value.
 
Quoted 13 lines

Documentation/bpf/standardization/instruction-set.rst For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``, · line 296

Quoted 11 lines
Documentation/bpf/standardization/instruction-set.rst +8 -0
+Note that there are varying definitions of the signed modulo operation
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
  The ``BPF_MOVSX`` instruction does a move operation with sign extension.
  ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
  bit operands, and zeroes the remaining upper 32 bits.

Eduard, do we have some test cases in BPF CI around this specifically (e.g. via test_verifier)? Might be worth adding if not.

Thanks,
Daniel

maintainer
#4 lore raw
Quoted 42 lines · Daniel Borkmann
Quoted 27 lines · Eduard Zingerman
Quoted 26 lines · Dave Thaler

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

[0]: https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition
[1]: https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/
[2]: https://lore.kernel.org/bpf/[email protected]/

---
  Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
  1 file changed, 8 insertions(+)
Documentation/bpf/standardization/instruction-set.rst +0 -0
index c5d53a6e8c7..245b6defc29 100644
@@ -283,6 +283,14 @@ For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``,
  is first :term:`sign extended<Sign Extend>` from 32 to 64 bits, and then
  interpreted as a 64-bit signed value.
 
Quoted 13 lines

Documentation/bpf/standardization/instruction-set.rst For signed operations (``BPF_SDIV`` and ``BPF_SMOD``), for ``BPF_ALU``, · line 296

Quoted 11 lines
Documentation/bpf/standardization/instruction-set.rst +8 -0
+Note that there are varying definitions of the signed modulo operation
+when the dividend or divisor are negative, where implementations often
+vary by language such that Python, Ruby, etc.  differ from C, Go, Java,
+etc. This specification requires that signed modulo use truncated division
+(where -13 % 3 == -1) as implemented in C, Go, etc.:
+
+   a % n = a - n * trunc(a / n)
+
  The ``BPF_MOVSX`` instruction does a move operation with sign extension.
  ``BPF_ALU | BPF_MOVSX`` :term:`sign extends<Sign Extend>` 8-bit and 16-bit operands into 32
  bit operands, and zeroes the remaining upper 32 bits.
Quoted 2 lines

Eduard, do we have some test cases in BPF CI around this specifically (e.g. via test_verifier)? Might be worth adding if not.

We do, e.g. see tools/testing/selftests/bpf/progs/verifier_sdiv.c:

  SEC("socket")
  __description("SMOD32, non-zero imm divisor, check 1")
  __success __success_unpriv __retval(-1)
  __naked void smod32_non_zero_imm_1(void)
  {
  	asm volatile ("					\
  	w0 = -41;					\
  	w0 s%%= 2;					\
  	exit;						\
  "	::: __clobber_all);
  }

And I'm still surprised that this produces different results in C and in Python :)

  $ python3
  Python 3.11.5 (main, Aug 31 2023, 07:57:41) [GCC] on linux
  Type "help", "copyright", "credits" or "license" for more information.
Quoted 1 line
Quoted 1 line
Quoted 1 line

-41 % 2

1

  $ clang-repl
  clang-repl> #include <stdio.h>
  clang-repl> printf("%d\n", -41 % 2);
  -1

There are several such tests with different combination of signs, both 32-bit and 64-bit.

#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 10 lines · On Tue, 17 Oct 2023 20:30:20 +0000 you wrote:

From: Dave Thaler <[email protected]>

There's different mathematical definitions (truncated, floored, rounded, etc.) and different languages have chosen different definitions [0][1]. E.g., languages/libraries that follow Knuth use a different mathematical definition than C uses. This patch specifies which definition BPF uses, as verified by Eduard [2] and others.

[...]

Here is the summary with links:
- [bpf-next] bpf, docs: Define signed modulo as using truncated division

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

You are awesome, thank you!

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