Re: div_k. Was: [PATCH 07/15] ebpf-docs: Fix modulo zero, division by zero, overflow, and underflow

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: Dave Thaler <dthaler@microsoft.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>,
	"bpf@vger.kernel.org" <bpf@vger.kernel.org>,
	Johan Almbladh <johan.almbladh@anyfinetworks.com>
Subject: Re: div_k. Was: [PATCH 07/15] ebpf-docs: Fix modulo zero, division by zero, overflow, and underflow
Date: Tue, 4 Oct 2022 11:34:49 -0700	[thread overview]
Message-ID: <CAADnVQJ387tWd7WgxqfoB44xMe17bY0RRp_Sng3xMnKsywFpxg@mail.gmail.com> (raw)
In-Reply-To: <DM4PR21MB3440DC0EE41F65013FE15E45A35A9@DM4PR21MB3440.namprd21.prod.outlook.com>

On Tue, Oct 4, 2022 at 11:23 AM Dave Thaler <dthaler@microsoft.com> wrote:
>
> Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> [...]
> > > What is the expected value for the following 64-bit BPF_DIV operation:
> > >     r0 = 0xFFFFFFFFFFFFFFFF
> > >     r0 /= -10
> > > Is it 0x1 or 0x10000000a?  i.e., is the -10 sign extended to
> > > 0xFFFFFFFFFFFFFFF6 or treated as 0xFFFFFFF6 when doing the unsigned
> > > division?
> >
> > x86 and arm64 JITs treat it as imm32 is zero extended.
>
> Alan Jowett just pointed out to me that the question is not limited to DIV.
>
> r0 = 1
> r0 += -1
>
> Is the answer 0 or 0x0000000100000000?
> Assuming the answer is to zero extend imm32, it contains the latter, which
> would be counter-intuitive enough to make it important to point out explicitly.

This is an obvious one. imm32 is _sign_ extended everywhere.

>
> > But looking at the interpreter:
> >         ALU64_DIV_K:
> >                 DST = div64_u64(DST, IMM); it looks like we have a bug there.
> > But we have a bunch of div_k tests in lib/test_bpf.c including negative
> > imm32. Hmm.

Actually I misread the JITs.
/* mov r11, imm32 */
EMIT3_off32(0x49, 0xC7, 0xC3, imm32);

It is sign extending. There is no bug in the interpreter or JIT.

> Yeah.
>
> "ALU64_DIV_K: 0xffffffffffffffff / (-1) = 0x0000000000000001",
> "ALU64_ADD_K: 2147483646 + -2147483647 = -1",
> "ALU64_ADD_K: 0 + (-1) = 0xffffffffffffffff",
> "ALU64_MUL_K: 1 * -2147483647 = -2147483647",
> "ALU64_MUL_K: 1 * (-1) = 0xffffffffffffffff",
> "ALU64_AND_K: 0x0000ffffffff0000 & -1 = 0x0000ffffffff0000",
> "ALU64_AND_K: 0xffffffffffffffff & -1 = 0xffffffffffffffff",
> "ALU64_OR_K: 0x000000000000000 | -1 = 0xffffffffffffffff",
>
> The above assume sign extension not zero extension is the correct behavior
> for these operations, if I understand correctly.
>
> Dave