diff mbox series

[bpf-next] bpf, docs: Define signed modulo as using truncated division

Message ID 20231017203020.1500-1-dthaler1968@googlemail.com (mailing list archive)
State Accepted
Commit 0e133a13370389d3894891eafe54fec2c44ad735
Delegated to: BPF
Headers show
Series [bpf-next] bpf, docs: Define signed modulo as using truncated division | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/series_format success Single patches do not need cover letters
netdev/tree_selection success Clearly marked for bpf-next
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 9 this patch: 9
netdev/cc_maintainers warning 14 maintainers not CCed: void@manifault.com ast@kernel.org linux-doc@vger.kernel.org song@kernel.org corbet@lwn.net andrii@kernel.org yonghong.song@linux.dev jolsa@kernel.org kpsingh@kernel.org john.fastabend@gmail.com sdf@google.com daniel@iogearbox.net haoluo@google.com martin.lau@linux.dev
netdev/build_clang success Errors and warnings before: 9 this patch: 9
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 9 this patch: 9
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 14 lines checked
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-0 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-3 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-1 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-5 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-20 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-12 success Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-2 success Logs for build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-6 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-8 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-4 success Logs for build for x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-9 success Logs for test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-18 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-16 success Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 success Logs for test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-27 success Logs for test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-14 success Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for veristat
bpf/vmtest-bpf-next-VM_Test-22 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for test_progs on x86_64 with llvm-16

Commit Message

Dave Thaler Oct. 17, 2023, 8:30 p.m. UTC 
From: Dave Thaler <dthaler@microsoft.com>

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/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@gmail.com/

Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
 Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
 1 file changed, 8 insertions(+)

Comments

David Vernet Oct. 18, 2023, 10:28 p.m. UTC | #1 
On Tue, Oct 17, 2023 at 08:30:20PM +0000, Dave Thaler wrote:
> From: Dave Thaler <dthaler@microsoft.com>
> 
> 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/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@gmail.com/
> 
> Signed-off-by: Dave Thaler <dthaler@microsoft.com>

Acked-by: David Vernet <void@manifault.com>

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

> ---
>  Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
> index c5d53a6e8c7..245b6defc29 100644
> --- a/Documentation/bpf/standardization/instruction-set.rst
> +++ b/Documentation/bpf/standardization/instruction-set.rst
> @@ -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.
> -- 
> 2.33.4
> 
>
Eduard Zingerman Oct. 18, 2023, 10:34 p.m. UTC | #2 
On Tue, 2023-10-17 at 20:30 +0000, Dave Thaler wrote:
> From: Dave Thaler <dthaler@microsoft.com>
> 
> 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/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@gmail.com/
> 
> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> ---
>  Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
> index c5d53a6e8c7..245b6defc29 100644
> --- a/Documentation/bpf/standardization/instruction-set.rst
> +++ b/Documentation/bpf/standardization/instruction-set.rst
> @@ -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.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
patchwork-bot+netdevbpf@kernel.org Oct. 18, 2023, 11:40 p.m. UTC | #3 
Hello:

This patch was applied to bpf/bpf-next.git (master)
by Daniel Borkmann <daniel@iogearbox.net>:

On Tue, 17 Oct 2023 20:30:20 +0000 you wrote:
> From: Dave Thaler <dthaler@microsoft.com>
> 
> 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!
Daniel Borkmann Oct. 18, 2023, 11:40 p.m. UTC | #4 
On 10/19/23 12:34 AM, Eduard Zingerman wrote:
> On Tue, 2023-10-17 at 20:30 +0000, Dave Thaler wrote:
>> From: Dave Thaler <dthaler@microsoft.com>
>>
>> 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/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@gmail.com/
>>
>> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
>> ---
>>   Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
>>   1 file changed, 8 insertions(+)
>>
>> diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
>> index c5d53a6e8c7..245b6defc29 100644
>> --- a/Documentation/bpf/standardization/instruction-set.rst
>> +++ b/Documentation/bpf/standardization/instruction-set.rst
>> @@ -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.
> 
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>

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 Oct. 19, 2023, midnight UTC | #5 
On Thu, 2023-10-19 at 01:40 +0200, Daniel Borkmann wrote:
> On 10/19/23 12:34 AM, Eduard Zingerman wrote:
> > On Tue, 2023-10-17 at 20:30 +0000, Dave Thaler wrote:
> > > From: Dave Thaler <dthaler@microsoft.com>
> > > 
> > > 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/57e6fefadaf3b2995bb259fa8e711c7220ce5290.camel@gmail.com/
> > > 
> > > Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> > > ---
> > >   Documentation/bpf/standardization/instruction-set.rst | 8 ++++++++
> > >   1 file changed, 8 insertions(+)
> > > 
> > > diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
> > > index c5d53a6e8c7..245b6defc29 100644
> > > --- a/Documentation/bpf/standardization/instruction-set.rst
> > > +++ b/Documentation/bpf/standardization/instruction-set.rst
> > > @@ -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.
> > 
> > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> 
> 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.
  >>> -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.
diff mbox series

Patch

diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst
index c5d53a6e8c7..245b6defc29 100644
--- a/Documentation/bpf/standardization/instruction-set.rst
+++ b/Documentation/bpf/standardization/instruction-set.rst
@@ -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.