diff options
| author | Dave Thaler <dthaler@microsoft.com> | 2023-10-17 23:30:20 +0300 |
|---|---|---|
| committer | Daniel Borkmann <daniel@iogearbox.net> | 2023-10-19 02:36:12 +0300 |
| commit | 0e133a13370389d3894891eafe54fec2c44ad735 (patch) | |
| tree | 54f3b6815025572d7a5bcf028caf6a37bce626c3 | |
| parent | bb6a88885fde24835afdaa1c5bb976a1bf5c5d71 (diff) | |
| download | linux-0e133a13370389d3894891eafe54fec2c44ad735.tar.xz | |
bpf, docs: Define signed modulo as using truncated division
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>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: David Vernet <void@manifault.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/bpf/20231017203020.1500-1-dthaler1968@googlemail.com
| -rw-r--r-- | Documentation/bpf/standardization/instruction-set.rst | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/Documentation/bpf/standardization/instruction-set.rst b/Documentation/bpf/standardization/instruction-set.rst index c5d53a6e8c79..245b6defc298 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. |