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

[Daniel Borkmann <daniel@iogearbox.net>]

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