bpf, docs: Define signed modulo as using truncated division
Subsystems (3)
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
@@ -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
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]/Signed-off-by Dave Thaler <[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@@ -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
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]/Signed-off-by Dave Thaler <[email protected]>--- Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++ 1 file changed, 8 insertions(+)Documentation/bpf/standardization/instruction-set.rst +1
-0@@ -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.
Daniel Borkmann
maintainerQuoted 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]/Signed-off-by Dave Thaler <[email protected]>--- Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++ 1 file changed, 8 insertions(+)Documentation/bpf/standardization/instruction-set.rst +0
-0@@ -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.Acked-by Eduard Zingerman <[email protected]>
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
Eduard Zingerman
maintainerQuoted 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]/Signed-off-by Dave Thaler <[email protected]>--- Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++ 1 file changed, 8 insertions(+)Documentation/bpf/standardization/instruction-set.rst +0
-0@@ -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.Acked-by Eduard Zingerman <[email protected]>
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);
-1There are several such tests with different combination of signs, both 32-bit and 64-bit.
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