bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
Subsystems (2)
PATCH 1/1 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
From: Dave Thaler <[email protected]>
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.
--- Documentation/bpf/instruction-set.rst | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +14 -2
@@ -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 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
Documentation/bpf/instruction-set.rst BPF_END 0xd0 byte swap operations (see `Byte swap instructions`_ below) · line 142
Quoted 6 lines
Documentation/bpf/instruction-set.rst +5
-0+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."
PATCH 1/1 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
From: Dave Thaler <[email protected]>
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.
--- Documentation/bpf/instruction-set.rst | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +14 -2
@@ -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 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
Daniel Borkmann
maintainerQuoted 32 lines · On 1/18/23 4:23 PM, [email protected] wrote:
From: Dave Thaler <[email protected]>
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 <[email protected]>--- Documentation/bpf/instruction-set.rst | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)Documentation/bpf/instruction-set.rst +2
-2@@ -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
Documentation/bpf/instruction-set.rst code value description · line 120
Quoted 10 lines
Documentation/bpf/instruction-set.rst +6
-0BPF_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 = w1So 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")).
Quoted 16 lines
Documentation/bpf/instruction-set.rst +5
-0``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 ~~~~~~~~~~~~~~~~~~~~~~
PATCH 1/1 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
In reply to [email protected]From: Dave Thaler <[email protected]>
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.
--- Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +16 -2
@@ -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 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
Quoted 2 lines · On Thu, Jan 19, 2023 at 2:25 PM <[email protected]> wrote:
Documentation/bpf/instruction-set.rst +1
-1-BPF_MOD 0x90 dst %= src +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
...
Documentation/bpf/instruction-set.rst code value description · line 122
Quoted 4 lines
Documentation/bpf/instruction-set.rst +4
-0+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.
PATCH 1/1 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
From: Dave Thaler <[email protected]>
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.
--- Documentation/bpf/instruction-set.rst | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +16 -2
@@ -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 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
Daniel Borkmann
maintainerOn 1/20/23 9:16 PM, [email protected] wrote:
[...]
Quoted 2 lines
Documentation/bpf/instruction-set.rst +1
-1-BPF_MOD 0x90 dst %= src +BPF_MOD 0x90 dst = (src != 0) ? (dst % src) : dst
[...]
Documentation/bpf/instruction-set.rst code value description · line 122
Quoted 4 lines
Documentation/bpf/instruction-set.rst +4
-0+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.
PATCH 1/1 bpf, docs: Fix modulo zero, division by zero, overflow, and underflow
From: Dave Thaler <[email protected]>
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.
--- Documentation/bpf/instruction-set.rst | 17 +++++++++++++++-- 1 file changed, 15 insertions(+), 2 deletions(-)
Documentation/bpf/instruction-set.rst +15 -2
@@ -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 ~~~~~~~~~~~~~~~~~~~~~~
Signature · 1 line
2.33.4
This patch was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:
Quoted 8 lines · On Tue, 24 Jan 2023 00:12:18 +0000 you wrote:
From: Dave Thaler <[email protected]>
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!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html