* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
@ 2023-01-05 16:32 dthaler1968
2023-01-05 19:01 ` sdf
0 siblings, 1 reply; 15+ messages in thread
From: dthaler1968 @ 2023-01-05 16:32 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 15 +++++++++++++--
1 file changed, 13 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..2ba7c618f33 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,26 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead left unchanged.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +135,10 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned,
+where 'imm' is first sign extended to 64 bits and then converted
+to an unsigned 64-bit value. There are no instructions for
+signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-05 16:32 [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow dthaler1968
@ 2023-01-05 19:01 ` sdf
2023-01-06 16:27 ` Daniel Borkmann
0 siblings, 1 reply; 15+ messages in thread
From: sdf @ 2023-01-05 19:01 UTC (permalink / raw)
To: dthaler1968; +Cc: bpf, Dave Thaler
On 01/05, dthaler1968@googlemail.com wrote:
> From: Dave Thaler <dthaler@microsoft.com>
> Fix modulo zero, division by zero, overflow, and underflow.
> Also clarify how a negative immediate value is used in unsigned division
> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
Acked-by: Stanislav Fomichev <sdf@google.com>
With a small note below.
> ---
> Documentation/bpf/instruction-set.rst | 15 +++++++++++++--
> 1 file changed, 13 insertions(+), 2 deletions(-)
> diff --git a/Documentation/bpf/instruction-set.rst
> b/Documentation/bpf/instruction-set.rst
> index e672d5ec6cc..2ba7c618f33 100644
> --- a/Documentation/bpf/instruction-set.rst
> +++ b/Documentation/bpf/instruction-set.rst
> @@ -99,19 +99,26 @@ code value description
> BPF_ADD 0x00 dst += src
> BPF_SUB 0x10 dst -= src
> BPF_MUL 0x20 dst \*= src
> -BPF_DIV 0x30 dst /= src
> +BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
> BPF_OR 0x40 dst \|= src
> BPF_AND 0x50 dst &= src
> BPF_LSH 0x60 dst <<= src
> BPF_RSH 0x70 dst >>= src
> BPF_NEG 0x80 dst = ~src
> -BPF_MOD 0x90 dst %= src
> +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
> BPF_XOR 0xa0 dst ^= src
> BPF_MOV 0xb0 dst = src
> BPF_ARSH 0xc0 sign extending shift right
> BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_
> below)
> ======== =====
> ==========================================================
> +Underflow and overflow are allowed during arithmetic operations,
> +meaning the 64-bit or 32-bit value will wrap. If
> +eBPF program execution would result in division by zero,
> +the destination register is instead set to zero.
> +If execution would result in modulo by zero,
> +the destination register is instead left unchanged.
> +
> ``BPF_ADD | BPF_X | BPF_ALU`` means::
> dst_reg = (u32) dst_reg + (u32) src_reg;
> @@ -128,6 +135,10 @@ BPF_END 0xd0 byte swap operations (see `Byte
> swap instructions`_ below)
> dst_reg = dst_reg ^ imm32
[..]
> +Also note that the division and modulo operations are unsigned,
> +where 'imm' is first sign extended to 64 bits and then converted
> +to an unsigned 64-bit value. There are no instructions for
> +signed division or modulo.
Less sure about this part, but it looks to be true at least by looking at
the interpreter which does:
DST = DST / IMM
where:
DST === (u64) regs[insn->dst_reg]
IMM === (s32) insn->imm
(and s32 is sign-expanded to u64 according to C rules)
> Byte swap instructions
> ~~~~~~~~~~~~~~~~~~~~~~
> --
> 2.33.4
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-05 19:01 ` sdf
@ 2023-01-06 16:27 ` Daniel Borkmann
2023-01-06 18:11 ` Dave Thaler
0 siblings, 1 reply; 15+ messages in thread
From: Daniel Borkmann @ 2023-01-06 16:27 UTC (permalink / raw)
To: sdf, dthaler1968; +Cc: bpf, Dave Thaler
On 1/5/23 8:01 PM, sdf@google.com wrote:
> On 01/05, dthaler1968@googlemail.com wrote:
>> From: Dave Thaler <dthaler@microsoft.com>
>
>> Fix modulo zero, division by zero, overflow, and underflow.
>> Also clarify how a negative immediate value is used in unsigned division
>
>> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
>
> Acked-by: Stanislav Fomichev <sdf@google.com>
>
> With a small note below.
>
>> ---
>> Documentation/bpf/instruction-set.rst | 15 +++++++++++++--
>> 1 file changed, 13 insertions(+), 2 deletions(-)
>
>> diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
>> index e672d5ec6cc..2ba7c618f33 100644
>> --- a/Documentation/bpf/instruction-set.rst
>> +++ b/Documentation/bpf/instruction-set.rst
>> @@ -99,19 +99,26 @@ code value description
>> BPF_ADD 0x00 dst += src
>> BPF_SUB 0x10 dst -= src
>> BPF_MUL 0x20 dst \*= src
>> -BPF_DIV 0x30 dst /= src
>> +BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
>> BPF_OR 0x40 dst \|= src
>> BPF_AND 0x50 dst &= src
>> BPF_LSH 0x60 dst <<= src
>> BPF_RSH 0x70 dst >>= src
>> BPF_NEG 0x80 dst = ~src
>> -BPF_MOD 0x90 dst %= src
>> +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
>> BPF_XOR 0xa0 dst ^= src
>> BPF_MOV 0xb0 dst = src
>> BPF_ARSH 0xc0 sign extending shift right
>> BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
>> ======== ===== ==========================================================
>
>> +Underflow and overflow are allowed during arithmetic operations,
>> +meaning the 64-bit or 32-bit value will wrap. If
>> +eBPF program execution would result in division by zero,
>> +the destination register is instead set to zero.
>> +If execution would result in modulo by zero,
>> +the destination register is instead left unchanged.
>> +
>> ``BPF_ADD | BPF_X | BPF_ALU`` means::
>
>> dst_reg = (u32) dst_reg + (u32) src_reg;
>> @@ -128,6 +135,10 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
>
>> dst_reg = dst_reg ^ imm32
>
>
> [..]
>
>> +Also note that the division and modulo operations are unsigned,
>> +where 'imm' is first sign extended to 64 bits and then converted
>> +to an unsigned 64-bit value. There are no instructions for
>> +signed division or modulo.
>
> Less sure about this part, but it looks to be true at least by looking at
> the interpreter which does:
>
> DST = DST / IMM
>
> where:
>
> DST === (u64) regs[insn->dst_reg]
> IMM === (s32) insn->imm
>
> (and s32 is sign-expanded to u64 according to C rules)
Yeap, the actual operation is in the target width, so for 32 bit it's casted
to u32, e.g. for modulo (note that the verifier rewrites it into `(src != 0) ?
(dst % src) : dst` form, so here is just the extract of the plain mod insn and
it's similar for div):
ALU64_MOD_X:
div64_u64_rem(DST, SRC, &AX);
DST = AX;
CONT;
ALU_MOD_X:
AX = (u32) DST;
DST = do_div(AX, (u32) SRC);
CONT;
ALU64_MOD_K:
div64_u64_rem(DST, IMM, &AX);
DST = AX;
CONT;
ALU_MOD_K:
AX = (u32) DST;
DST = do_div(AX, (u32) IMM);
CONT;
So in above phrasing the middle part needs to be adapted or just removed.
Thanks,
Daniel
^ permalink raw reply [flat|nested] 15+ messages in thread
* RE: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-06 16:27 ` Daniel Borkmann
@ 2023-01-06 18:11 ` Dave Thaler
2023-01-06 21:08 ` [Bpf] " Daniel Borkmann
0 siblings, 1 reply; 15+ messages in thread
From: Dave Thaler @ 2023-01-06 18:11 UTC (permalink / raw)
To: Daniel Borkmann, sdf, dthaler1968; +Cc: bpf, bpf
Daniel Borkmann wrote:
[...]
> >> +Also note that the division and modulo operations are unsigned,
> >> +where 'imm' is first sign extended to 64 bits and then converted to
> >> +an unsigned 64-bit value. There are no instructions for signed
> >> +division or modulo.
> >
> > Less sure about this part, but it looks to be true at least by looking
> > at the interpreter which does:
> >
> > DST = DST / IMM
> >
> > where:
> >
> > DST === (u64) regs[insn->dst_reg]
> > IMM === (s32) insn->imm
> >
> > (and s32 is sign-expanded to u64 according to C rules)
>
> Yeap, the actual operation is in the target width, so for 32 bit it's casted to
> u32, e.g. for modulo (note that the verifier rewrites it into `(src != 0) ?
> (dst % src) : dst` form, so here is just the extract of the plain mod insn and it's
> similar for div):
>
> ALU64_MOD_X:
> div64_u64_rem(DST, SRC, &AX);
> DST = AX;
> CONT;
> ALU_MOD_X:
> AX = (u32) DST;
> DST = do_div(AX, (u32) SRC);
> CONT;
> ALU64_MOD_K:
> div64_u64_rem(DST, IMM, &AX);
> DST = AX;
> CONT;
> ALU_MOD_K:
> AX = (u32) DST;
> DST = do_div(AX, (u32) IMM);
> CONT;
>
> So in above phrasing the middle part needs to be adapted or just removed.
The phrasing was based on the earlier discussion on this list (see
https://lore.kernel.org/bpf/CAADnVQJ387tWd7WgxqfoB44xMe17bY0RRp_Sng3xMnKsywFpxg@mail.gmail.com/) where
Alexei wrote "imm32 is _sign_ extended everywhere",
and I cited the div_k tests in lib/test_bpf.c that assume sign extension
not zero extension.
So I don't know how to reconcile your comments with that thread.
If you do, please educate me :)
Dave
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [Bpf] [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-06 18:11 ` Dave Thaler
@ 2023-01-06 21:08 ` Daniel Borkmann
0 siblings, 0 replies; 15+ messages in thread
From: Daniel Borkmann @ 2023-01-06 21:08 UTC (permalink / raw)
To: Dave Thaler, sdf, dthaler1968; +Cc: bpf, bpf
On 1/6/23 7:11 PM, Dave Thaler wrote:
> Daniel Borkmann wrote:
> [...]
>>>> +Also note that the division and modulo operations are unsigned,
>>>> +where 'imm' is first sign extended to 64 bits and then converted to
>>>> +an unsigned 64-bit value. There are no instructions for signed
>>>> +division or modulo.
>>>
>>> Less sure about this part, but it looks to be true at least by looking
>>> at the interpreter which does:
>>>
>>> DST = DST / IMM
>>>
>>> where:
>>>
>>> DST === (u64) regs[insn->dst_reg]
>>> IMM === (s32) insn->imm
>>>
>>> (and s32 is sign-expanded to u64 according to C rules)
>>
>> Yeap, the actual operation is in the target width, so for 32 bit it's casted to
>> u32, e.g. for modulo (note that the verifier rewrites it into `(src != 0) ?
>> (dst % src) : dst` form, so here is just the extract of the plain mod insn and it's
>> similar for div):
>>
>> ALU64_MOD_X:
>> div64_u64_rem(DST, SRC, &AX);
>> DST = AX;
>> CONT;
>> ALU_MOD_X:
>> AX = (u32) DST;
>> DST = do_div(AX, (u32) SRC);
>> CONT;
>> ALU64_MOD_K:
>> div64_u64_rem(DST, IMM, &AX);
>> DST = AX;
>> CONT;
>> ALU_MOD_K:
>> AX = (u32) DST;
>> DST = do_div(AX, (u32) IMM);
>> CONT;
>>
>> So in above phrasing the middle part needs to be adapted or just removed.
>
> The phrasing was based on the earlier discussion on this list (see
> https://lore.kernel.org/bpf/CAADnVQJ387tWd7WgxqfoB44xMe17bY0RRp_Sng3xMnKsywFpxg@mail.gmail.com/) where
> Alexei wrote "imm32 is _sign_ extended everywhere",
> and I cited the div_k tests in lib/test_bpf.c that assume sign extension
> not zero extension.
`Where 'imm' is first sign extended to 64 bits and then converted to an unsigned
64-bit value` is true for the 64 bit operation, for the 32-bit it's just converted
to an unsigned 32-bit value, see the (u32)IMM which is (u32)(s32) insn->imm. From
the phrasing, it was a bit less clear perhaps.
Thanks,
Daniel
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-24 0:12 ` dthaler1968
@ 2023-01-24 15:50 ` patchwork-bot+netdevbpf
0 siblings, 0 replies; 15+ messages in thread
From: patchwork-bot+netdevbpf @ 2023-01-24 15:50 UTC (permalink / raw)
To: None; +Cc: bpf, dthaler
Hello:
This patch was applied to bpf/bpf-next.git (master)
by Daniel Borkmann <daniel@iogearbox.net>:
On Tue, 24 Jan 2023 00:12:18 +0000 you wrote:
> From: Dave Thaler <dthaler@microsoft.com>
>
> Fix modulo zero, division by zero, overflow, and underflow.
> Also clarify how a negative immediate value is used in unsigned division
>
> Changes from last submission: addressed comments from Daniel.
>
> [...]
Here is the summary with links:
- bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
https://git.kernel.org/bpf/bpf-next/c/0eb9d19e2201
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-23 21:45 ` Daniel Borkmann
@ 2023-01-24 0:12 ` dthaler1968
2023-01-24 15:50 ` patchwork-bot+netdevbpf
0 siblings, 1 reply; 15+ messages in thread
From: dthaler1968 @ 2023-01-24 0:12 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Changes from last submission: addressed comments from Daniel.
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 17 +++++++++++++++--
1 file changed, 15 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..a7f4574562c 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,27 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero, for ``BPF_ALU64``
+the value of the destination register is unchanged whereas for
+``BPF_ALU`` the upper 32 bits of the destination register are zeroed.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +136,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas for ``BPF_ALU64``, 'imm' is first sign extended
+to 64 bits and the result interpreted as an unsigned 64-bit value.
+There are no instructions for signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-20 20:16 ` dthaler1968
@ 2023-01-23 21:45 ` Daniel Borkmann
2023-01-24 0:12 ` dthaler1968
0 siblings, 1 reply; 15+ messages in thread
From: Daniel Borkmann @ 2023-01-23 21:45 UTC (permalink / raw)
To: dthaler1968, bpf; +Cc: Dave Thaler
On 1/20/23 9:16 PM, dthaler1968@googlemail.com wrote:
[...]
> -BPF_MOD 0x90 dst %= src
> +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
[...]
> +If execution would result in modulo by zero,
> +the destination register is instead set to the source register
> +as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
> +is unchanged whereas for ``BPF_ALU`` the upper 32 bits are zeroed.
I think the "the destination register is instead set to the source register
as ``BPF_MOV`` would do" is a bit ambiguous. Could we just simplify it to the
following:
If execution would result in modulo by zero, for ``BPF_ALU64`` the value of
the destination register is unchanged whereas for ``BPF_ALU`` the upper 32 bits
of the destination register are zeroed.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-20 1:01 ` Alexei Starovoitov
@ 2023-01-20 20:16 ` dthaler1968
2023-01-23 21:45 ` Daniel Borkmann
0 siblings, 1 reply; 15+ messages in thread
From: dthaler1968 @ 2023-01-20 20:16 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Changes from last submission: addressed comments from Alexei.
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++--
1 file changed, 16 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..2546630fcbd 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,28 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the upper 32 bits are zeroed.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +137,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas for ``BPF_ALU64``, 'imm' is first sign extended
+to 64 bits and the result interpreted as an unsigned 64-bit value.
+There are no instructions for signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-19 22:04 ` dthaler1968
@ 2023-01-20 1:01 ` Alexei Starovoitov
2023-01-20 20:16 ` dthaler1968
0 siblings, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2023-01-20 1:01 UTC (permalink / raw)
To: dthaler1968; +Cc: bpf, Dave Thaler
On Thu, Jan 19, 2023 at 2:25 PM <dthaler1968@googlemail.com> wrote:
> -BPF_MOD 0x90 dst %= src
> +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
...
> +If execution would result in modulo by zero,
> +the destination register is instead set to the source register
> +as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
> +is unchanged whereas for ``BPF_ALU`` the value is truncated to 32 bits.
These two don't match.
Probably should say that for ALU64 dst doesn't change
and for alu32 it's upper 32-bits are zeroed.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-18 15:23 ` dthaler1968
2023-01-18 16:20 ` Daniel Borkmann
@ 2023-01-19 22:04 ` dthaler1968
2023-01-20 1:01 ` Alexei Starovoitov
1 sibling, 1 reply; 15+ messages in thread
From: dthaler1968 @ 2023-01-19 22:04 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Changes from last submission: addressed comments from Daniel.
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++--
1 file changed, 16 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..dd37cc5c0bf 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,28 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead set to the source register
+as ``BPF_MOV`` would do, meaning that for ``BPF_ALU64`` the value
+is unchanged whereas for ``BPF_ALU`` the value is truncated to 32 bits.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +137,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned.
+Thus, for ``BPF_ALU``, 'imm' is first interpreted as an unsigned
+32-bit value, whereas for ``BPF_ALU64``, 'imm' is first sign extended
+to 64 bits and the result interpreted as an unsigned 64-bit value.
+There are no instructions for signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-18 15:23 ` dthaler1968
@ 2023-01-18 16:20 ` Daniel Borkmann
2023-01-19 22:04 ` dthaler1968
1 sibling, 0 replies; 15+ messages in thread
From: Daniel Borkmann @ 2023-01-18 16:20 UTC (permalink / raw)
To: dthaler1968, bpf; +Cc: Dave Thaler
On 1/18/23 4:23 PM, dthaler1968@googlemail.com wrote:
> From: Dave Thaler <dthaler@microsoft.com>
>
> Fix modulo zero, division by zero, overflow, and underflow.
> Also clarify how a negative immediate value is used in unsigned division
>
> Changes from last submission: addressed conversion comment from
> Jose.
>
> Signed-off-by: Dave Thaler <dthaler@microsoft.com>
> ---
> Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
> 1 file changed, 14 insertions(+), 2 deletions(-)
>
> diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
> index e672d5ec6cc..f79dae527ad 100644
> --- a/Documentation/bpf/instruction-set.rst
> +++ b/Documentation/bpf/instruction-set.rst
> @@ -99,19 +99,26 @@ code value description
> BPF_ADD 0x00 dst += src
> BPF_SUB 0x10 dst -= src
> BPF_MUL 0x20 dst \*= src
> -BPF_DIV 0x30 dst /= src
> +BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
> BPF_OR 0x40 dst \|= src
> BPF_AND 0x50 dst &= src
> BPF_LSH 0x60 dst <<= src
> BPF_RSH 0x70 dst >>= src
> BPF_NEG 0x80 dst = ~src
> -BPF_MOD 0x90 dst %= src
> +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
> BPF_XOR 0xa0 dst ^= src
> BPF_MOV 0xb0 dst = src
> BPF_ARSH 0xc0 sign extending shift right
> BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
> ======== ===== ==========================================================
>
> +Underflow and overflow are allowed during arithmetic operations,
> +meaning the 64-bit or 32-bit value will wrap. If
> +eBPF program execution would result in division by zero,
> +the destination register is instead set to zero.
> +If execution would result in modulo by zero,
> +the destination register is instead left unchanged.
Looks good to go with one small nit for the previous sentence which could be
misinterpreted. The rewrites from verifier for modulo op are:
mod32: mod64:
(16) if w0 == 0x0 goto pc+2 (15) if r0 == 0x0 goto pc+1
(9c) w1 %= w0 (9f) r1 %= r0
(05) goto pc+1
(bc) w1 = w1
So for BPF_ALU as 32-bit op, it is expected that the result is 32-bit
value, too. So for 32-bit op the destination register is truncated to
32-bit value. (Related commit 9b00f1b78809 ("bpf: Fix truncation handling
for mod32 dst reg wrt zero")).
> ``BPF_ADD | BPF_X | BPF_ALU`` means::
>
> dst_reg = (u32) dst_reg + (u32) src_reg;
> @@ -128,6 +135,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
>
> dst_reg = dst_reg ^ imm32
>
> +Also note that the division and modulo operations are unsigned.
> +Thus, for `BPF_ALU`, 'imm' is first interpreted as an unsigned
> +32-bit value, whereas for `BPF_ALU64`, 'imm' is first sign extended
> +to 64 bits and the result interpreted as an unsigned 64-bit value.
> +There are no instructions for signed division or modulo.
>
> Byte swap instructions
> ~~~~~~~~~~~~~~~~~~~~~~
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-18 9:43 ` Jose E. Marchesi
@ 2023-01-18 15:23 ` dthaler1968
2023-01-18 16:20 ` Daniel Borkmann
2023-01-19 22:04 ` dthaler1968
0 siblings, 2 replies; 15+ messages in thread
From: dthaler1968 @ 2023-01-18 15:23 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Changes from last submission: addressed conversion comment from
Jose.
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
1 file changed, 14 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..f79dae527ad 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,26 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead left unchanged.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +135,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first interpreted as an unsigned
+32-bit value, whereas for `BPF_ALU64`, 'imm' is first sign extended
+to 64 bits and the result interpreted as an unsigned 64-bit value.
+There are no instructions for signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
2023-01-17 22:49 dthaler1968
@ 2023-01-18 9:43 ` Jose E. Marchesi
2023-01-18 15:23 ` dthaler1968
0 siblings, 1 reply; 15+ messages in thread
From: Jose E. Marchesi @ 2023-01-18 9:43 UTC (permalink / raw)
To: dthaler1968; +Cc: bpf, Dave Thaler
> +Also note that the division and modulo operations are unsigned.
> +Thus, for `BPF_ALU`, 'imm' is first converted to an unsigned
> +32-bit value, whereas for `BPF_ALU64`, 'imm' is first sign extended
> +to 64 bits and then converted to an unsigned 64-bit value. There
> +are no instructions for signed division or modulo.
English is not my native language, but I think "converted" may be too
generic for this paragraph: are the same bits reinterpreted as unsigned?
Or an actual conversion like absolute value is performed?
Wouldn't it be better to say "interpreted as" instead of "converted to"
in this case?
Something like this:
"Also note that the division and modulo operations are unsigned.
Thus, for `BPF_ALU`, 'imm' is interpreted as an unsigned 32-bit
value, whereas for `BPF_ALU64`, 'imm' is first sign extended to 64
bits and the result interpreted as an unsigned 64-bit value. There
are no instructions for signed division or modulo."
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
@ 2023-01-17 22:49 dthaler1968
2023-01-18 9:43 ` Jose E. Marchesi
0 siblings, 1 reply; 15+ messages in thread
From: dthaler1968 @ 2023-01-17 22:49 UTC (permalink / raw)
To: bpf; +Cc: Dave Thaler
From: Dave Thaler <dthaler@microsoft.com>
Fix modulo zero, division by zero, overflow, and underflow.
Also clarify how a negative immediate value is used in unsigned division
Changes from last submission: addressed 32-bit comments from
Daniel and Stanislav.
Signed-off-by: Dave Thaler <dthaler@microsoft.com>
---
Documentation/bpf/instruction-set.rst | 16 ++++++++++++++--
1 file changed, 14 insertions(+), 2 deletions(-)
diff --git a/Documentation/bpf/instruction-set.rst b/Documentation/bpf/instruction-set.rst
index e672d5ec6cc..fcd4db45717 100644
--- a/Documentation/bpf/instruction-set.rst
+++ b/Documentation/bpf/instruction-set.rst
@@ -99,19 +99,26 @@ code value description
BPF_ADD 0x00 dst += src
BPF_SUB 0x10 dst -= src
BPF_MUL 0x20 dst \*= src
-BPF_DIV 0x30 dst /= src
+BPF_DIV 0x30 dst = (src != 0) ? (dst / src) : 0
BPF_OR 0x40 dst \|= src
BPF_AND 0x50 dst &= src
BPF_LSH 0x60 dst <<= src
BPF_RSH 0x70 dst >>= src
BPF_NEG 0x80 dst = ~src
-BPF_MOD 0x90 dst %= src
+BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
BPF_XOR 0xa0 dst ^= src
BPF_MOV 0xb0 dst = src
BPF_ARSH 0xc0 sign extending shift right
BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
======== ===== ==========================================================
+Underflow and overflow are allowed during arithmetic operations,
+meaning the 64-bit or 32-bit value will wrap. If
+eBPF program execution would result in division by zero,
+the destination register is instead set to zero.
+If execution would result in modulo by zero,
+the destination register is instead left unchanged.
+
``BPF_ADD | BPF_X | BPF_ALU`` means::
dst_reg = (u32) dst_reg + (u32) src_reg;
@@ -128,6 +135,11 @@ BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below)
dst_reg = dst_reg ^ imm32
+Also note that the division and modulo operations are unsigned.
+Thus, for `BPF_ALU`, 'imm' is first converted to an unsigned
+32-bit value, whereas for `BPF_ALU64`, 'imm' is first sign extended
+to 64 bits and then converted to an unsigned 64-bit value. There
+are no instructions for signed division or modulo.
Byte swap instructions
~~~~~~~~~~~~~~~~~~~~~~
--
2.33.4
^ permalink raw reply related [flat|nested] 15+ messages in thread
end of thread, other threads:[~2023-01-24 15:50 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-01-05 16:32 [PATCH] bpf, docs: Fix modulo zero, division by zero, overflow, and underflow dthaler1968
2023-01-05 19:01 ` sdf
2023-01-06 16:27 ` Daniel Borkmann
2023-01-06 18:11 ` Dave Thaler
2023-01-06 21:08 ` [Bpf] " Daniel Borkmann
2023-01-17 22:49 dthaler1968
2023-01-18 9:43 ` Jose E. Marchesi
2023-01-18 15:23 ` dthaler1968
2023-01-18 16:20 ` Daniel Borkmann
2023-01-19 22:04 ` dthaler1968
2023-01-20 1:01 ` Alexei Starovoitov
2023-01-20 20:16 ` dthaler1968
2023-01-23 21:45 ` Daniel Borkmann
2023-01-24 0:12 ` dthaler1968
2023-01-24 15:50 ` patchwork-bot+netdevbpf
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).