* [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows
@ 2024-07-01 5:59 Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows Shung-Hsi Yu
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: Shung-Hsi Yu @ 2024-07-01 5:59 UTC (permalink / raw)
To: bpf, Alexei Starovoitov, Jiri Olsa
Cc: Daniel Borkmann, John Fastabend, Andrii Nakryiko,
Martin KaFai Lau, Eduard Zingerman, Song Liu, Yonghong Song,
KP Singh, Stanislav Fomichev, Hao Luo, Shung-Hsi Yu
This patch set refactors kernel/bpf/verifier.c to use type-agnostic,
generic overflow-check helpers defined in include/linux/overflow.h to
check for addition and subtraction overflow, and drop the
signed_*_overflows() helpers we currently have in kernel/bpf/verifier.c.
There should be no functional change in how the verifier works.
The main motivation is to make future refactoring[1] easier.
While check_mul_overflow() also exists and could potentially replace what
we have in scalar*_min_max_mul(), it does not help with refactoring and
would either change how the verifier works (e.g. lifting restriction on
umax<=U32_MAX and u32_max<=U16_MAX) or make the code slightly harder to
read, so it is left for future endeavour.
Changes from v1 <https://lore.kernel.org/r/20240623070324.12634-1-shung-hsi.yu@suse.com>:
- use pointers to values in dst_reg directly as the sum/diff pointer and
remove the else branch (Jiri)
- change local variables to be dst_reg pointers instead of src_reg values
- include comparison of generated assembly before & after the change
(Alexei)
1: https://github.com/kernel-patches/bpf/pull/7205/commits
Shung-Hsi Yu (2):
bpf: use check_add_overflow() to check for addition overflows
bpf: use check_sub_overflow() to check for subtraction overflows
kernel/bpf/verifier.c | 151 ++++++++++++------------------------------
1 file changed, 42 insertions(+), 109 deletions(-)
--
2.45.2
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows
2024-07-01 5:59 [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Shung-Hsi Yu
@ 2024-07-01 5:59 ` Shung-Hsi Yu
2024-07-10 2:08 ` Alexei Starovoitov
2024-07-01 5:59 ` [PATCH bpf-next v2 2/2] bpf: use check_sub_overflow() to check for subtraction overflows Shung-Hsi Yu
2024-07-01 9:18 ` [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Jiri Olsa
2 siblings, 1 reply; 7+ messages in thread
From: Shung-Hsi Yu @ 2024-07-01 5:59 UTC (permalink / raw)
To: bpf, Alexei Starovoitov, Jiri Olsa
Cc: Daniel Borkmann, John Fastabend, Andrii Nakryiko,
Martin KaFai Lau, Eduard Zingerman, Song Liu, Yonghong Song,
KP Singh, Stanislav Fomichev, Hao Luo, Shung-Hsi Yu
signed_add*_overflows() was added back when there was no overflow-check
helper. With the introduction of such helpers in commit f0907827a8a91
("compiler.h: enable builtin overflow checkers and add fallback code"), we
can drop signed_add*_overflows() in kernel/bpf/verifier.c and use the
generic check_add_overflow() instead.
This will make future refactoring easier, and takes advantage of
compiler-emitted hardware instructions that efficiently implement these
checks.
After the change GCC 13.3.0 generates cleaner assembly on x86_64:
err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
13625: mov 0x28(%rbx),%r9 /* r9 = src_reg->smin_value */
13629: mov 0x30(%rbx),%rcx /* rcx = src_reg->smax_value */
...
if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
141c1: mov %r9,%rax
141c4: add 0x28(%r12),%rax
141c9: mov %rax,0x28(%r12)
141ce: jo 146e4 <adjust_reg_min_max_vals+0x1294>
check_add_overflow(*dst_smax, src_reg->smax_value, dst_smax)) {
141d4: add 0x30(%r12),%rcx
141d9: mov %rcx,0x30(%r12)
if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
141de: jo 146e4 <adjust_reg_min_max_vals+0x1294>
...
*dst_smin = S64_MIN;
146e4: movabs $0x8000000000000000,%rax
146ee: mov %rax,0x28(%r12)
*dst_smax = S64_MAX;
146f3: sub $0x1,%rax
146f7: mov %rax,0x30(%r12)
Before the change it gives:
s64 smin_val = src_reg->smin_value;
675: mov 0x28(%rsi),%r8
s64 smax_val = src_reg->smax_value;
u64 umin_val = src_reg->umin_value;
u64 umax_val = src_reg->umax_value;
679: mov %rdi,%rax /* rax = dst_reg */
if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
67c: mov 0x28(%rdi),%rdi /* rdi = dst_reg->smin_value */
u64 umin_val = src_reg->umin_value;
680: mov 0x38(%rsi),%rdx
u64 umax_val = src_reg->umax_value;
684: mov 0x40(%rsi),%rcx
s64 res = (s64)((u64)a + (u64)b);
688: lea (%r8,%rdi,1),%r9 /* r9 = dst_reg->smin_value + src_reg->smin_value */
return res < a;
68c: cmp %r9,%rdi
68f: setg %r10b /* r10b = (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value */
if (b < 0)
693: test %r8,%r8
696: js 72b <scalar_min_max_add+0xbb>
signed_add_overflows(dst_reg->smax_value, smax_val)) {
dst_reg->smin_value = S64_MIN;
dst_reg->smax_value = S64_MAX;
69c: movabs $0x7fffffffffffffff,%rdi
s64 smax_val = src_reg->smax_value;
6a6: mov 0x30(%rsi),%r8
dst_reg->smin_value = S64_MIN;
6aa: 00 00 00 movabs $0x8000000000000000,%rsi
if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
6b4: test %r10b,%r10b /* (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value ? goto 6cb */
6b7: jne 6cb <scalar_min_max_add+0x5b>
signed_add_overflows(dst_reg->smax_value, smax_val)) {
6b9: mov 0x30(%rax),%r10 /* r10 = dst_reg->smax_value */
s64 res = (s64)((u64)a + (u64)b);
6bd: lea (%r10,%r8,1),%r11 /* r11 = dst_reg->smax_value + src_reg->smax_value */
if (b < 0)
6c1: test %r8,%r8
6c4: js 71e <scalar_min_max_add+0xae>
if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
6c6: cmp %r11,%r10 /* (dst_reg->smax_value + src_reg->smax_value) <= dst_reg->smax_value ? goto 723 */
6c9: jle 723 <scalar_min_max_add+0xb3>
} else {
dst_reg->smin_value += smin_val;
dst_reg->smax_value += smax_val;
}
6cb: mov %rsi,0x28(%rax)
...
6d5: mov %rdi,0x30(%rax)
...
if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
71e: cmp %r11,%r10
721: jl 6cb <scalar_min_max_add+0x5b>
dst_reg->smin_value += smin_val;
723: mov %r9,%rsi
dst_reg->smax_value += smax_val;
726: mov %r11,%rdi
729: jmp 6cb <scalar_min_max_add+0x5b>
return res > a;
72b: cmp %r9,%rdi
72e: setl %r10b
732: jmp 69c <scalar_min_max_add+0x2c>
737: nopw 0x0(%rax,%rax,1)
Suggested-by: Jiri Olsa <jolsa@kernel.org>
Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
kernel/bpf/verifier.c | 94 +++++++++++++------------------------------
1 file changed, 28 insertions(+), 66 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d3927d819465..26c2b7527942 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12725,26 +12725,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
return 0;
}
-static bool signed_add_overflows(s64 a, s64 b)
-{
- /* Do the add in u64, where overflow is well-defined */
- s64 res = (s64)((u64)a + (u64)b);
-
- if (b < 0)
- return res > a;
- return res < a;
-}
-
-static bool signed_add32_overflows(s32 a, s32 b)
-{
- /* Do the add in u32, where overflow is well-defined */
- s32 res = (s32)((u32)a + (u32)b);
-
- if (b < 0)
- return res > a;
- return res < a;
-}
-
static bool signed_sub_overflows(s64 a, s64 b)
{
/* Do the sub in u64, where overflow is well-defined */
@@ -13246,21 +13226,15 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
* added into the variable offset, and we copy the fixed offset
* from ptr_reg.
*/
- if (signed_add_overflows(smin_ptr, smin_val) ||
- signed_add_overflows(smax_ptr, smax_val)) {
+ if (check_add_overflow(smin_ptr, smin_val, &dst_reg->smin_value) ||
+ check_add_overflow(smax_ptr, smax_val, &dst_reg->smax_value)) {
dst_reg->smin_value = S64_MIN;
dst_reg->smax_value = S64_MAX;
- } else {
- dst_reg->smin_value = smin_ptr + smin_val;
- dst_reg->smax_value = smax_ptr + smax_val;
}
- if (umin_ptr + umin_val < umin_ptr ||
- umax_ptr + umax_val < umax_ptr) {
+ if (check_add_overflow(umin_ptr, umin_val, &dst_reg->umin_value) ||
+ check_add_overflow(umax_ptr, umax_val, &dst_reg->umax_value)) {
dst_reg->umin_value = 0;
dst_reg->umax_value = U64_MAX;
- } else {
- dst_reg->umin_value = umin_ptr + umin_val;
- dst_reg->umax_value = umax_ptr + umax_val;
}
dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
dst_reg->off = ptr_reg->off;
@@ -13363,52 +13337,40 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
static void scalar32_min_max_add(struct bpf_reg_state *dst_reg,
struct bpf_reg_state *src_reg)
{
- s32 smin_val = src_reg->s32_min_value;
- s32 smax_val = src_reg->s32_max_value;
- u32 umin_val = src_reg->u32_min_value;
- u32 umax_val = src_reg->u32_max_value;
+ s32 *dst_smin = &dst_reg->s32_min_value;
+ s32 *dst_smax = &dst_reg->s32_max_value;
+ u32 *dst_umin = &dst_reg->u32_min_value;
+ u32 *dst_umax = &dst_reg->u32_max_value;
- if (signed_add32_overflows(dst_reg->s32_min_value, smin_val) ||
- signed_add32_overflows(dst_reg->s32_max_value, smax_val)) {
- dst_reg->s32_min_value = S32_MIN;
- dst_reg->s32_max_value = S32_MAX;
- } else {
- dst_reg->s32_min_value += smin_val;
- dst_reg->s32_max_value += smax_val;
+ if (check_add_overflow(*dst_smin, src_reg->s32_min_value, dst_smin) ||
+ check_add_overflow(*dst_smax, src_reg->s32_max_value, dst_smax)) {
+ *dst_smin = S32_MIN;
+ *dst_smax = S32_MAX;
}
- if (dst_reg->u32_min_value + umin_val < umin_val ||
- dst_reg->u32_max_value + umax_val < umax_val) {
- dst_reg->u32_min_value = 0;
- dst_reg->u32_max_value = U32_MAX;
- } else {
- dst_reg->u32_min_value += umin_val;
- dst_reg->u32_max_value += umax_val;
+ if (check_add_overflow(*dst_umin, src_reg->u32_min_value, dst_umin) ||
+ check_add_overflow(*dst_umax, src_reg->u32_max_value, dst_umax)) {
+ *dst_umin = 0;
+ *dst_umax = U32_MAX;
}
}
static void scalar_min_max_add(struct bpf_reg_state *dst_reg,
struct bpf_reg_state *src_reg)
{
- s64 smin_val = src_reg->smin_value;
- s64 smax_val = src_reg->smax_value;
- u64 umin_val = src_reg->umin_value;
- u64 umax_val = src_reg->umax_value;
+ s64 *dst_smin = &dst_reg->smin_value;
+ s64 *dst_smax = &dst_reg->smax_value;
+ u64 *dst_umin = &dst_reg->umin_value;
+ u64 *dst_umax = &dst_reg->umax_value;
- if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
- signed_add_overflows(dst_reg->smax_value, smax_val)) {
- dst_reg->smin_value = S64_MIN;
- dst_reg->smax_value = S64_MAX;
- } else {
- dst_reg->smin_value += smin_val;
- dst_reg->smax_value += smax_val;
+ if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
+ check_add_overflow(*dst_smax, src_reg->smax_value, dst_smax)) {
+ *dst_smin = S64_MIN;
+ *dst_smax = S64_MAX;
}
- if (dst_reg->umin_value + umin_val < umin_val ||
- dst_reg->umax_value + umax_val < umax_val) {
- dst_reg->umin_value = 0;
- dst_reg->umax_value = U64_MAX;
- } else {
- dst_reg->umin_value += umin_val;
- dst_reg->umax_value += umax_val;
+ if (check_add_overflow(*dst_umin, src_reg->umin_value, dst_umin) ||
+ check_add_overflow(*dst_umax, src_reg->umax_value, dst_umax)) {
+ *dst_umin = 0;
+ *dst_umax = U64_MAX;
}
}
--
2.45.2
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH bpf-next v2 2/2] bpf: use check_sub_overflow() to check for subtraction overflows
2024-07-01 5:59 [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows Shung-Hsi Yu
@ 2024-07-01 5:59 ` Shung-Hsi Yu
2024-07-01 9:18 ` [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Jiri Olsa
2 siblings, 0 replies; 7+ messages in thread
From: Shung-Hsi Yu @ 2024-07-01 5:59 UTC (permalink / raw)
To: bpf, Alexei Starovoitov, Jiri Olsa
Cc: Daniel Borkmann, John Fastabend, Andrii Nakryiko,
Martin KaFai Lau, Eduard Zingerman, Song Liu, Yonghong Song,
KP Singh, Stanislav Fomichev, Hao Luo, Shung-Hsi Yu
Similar to previous patch that drops signed_add*_overflows() and uses
(compiler) builtin-based check_add_overflow(), do the same for
signed_sub*_overflows() and replace them with the generic
check_sub_overflow() to make future refactoring easier and have the
checks implemented more efficiently.
Unsigned overflow check for subtraction does not use helpers and are
simple enough already, so they're left untouched.
After the change GCC 13.3.0 generates cleaner assembly on x86_64:
if (check_sub_overflow(*dst_smin, src_reg->smax_value, dst_smin) ||
139bf: mov 0x28(%r12),%rax
139c4: mov %edx,0x54(%r12)
139c9: sub %r11,%rax
139cc: mov %rax,0x28(%r12)
139d1: jo 14627 <adjust_reg_min_max_vals+0x1237>
check_sub_overflow(*dst_smax, src_reg->smin_value, dst_smax)) {
139d7: mov 0x30(%r12),%rax
139dc: sub %r9,%rax
139df: mov %rax,0x30(%r12)
if (check_sub_overflow(*dst_smin, src_reg->smax_value, dst_smin) ||
139e4: jo 14627 <adjust_reg_min_max_vals+0x1237>
...
*dst_smin = S64_MIN;
14627: movabs $0x8000000000000000,%rax
14631: mov %rax,0x28(%r12)
*dst_smax = S64_MAX;
14636: sub $0x1,%rax
1463a: mov %rax,0x30(%r12)
Before the change it gives:
if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
13a50: mov 0x28(%r12),%rdi
13a55: mov %edx,0x54(%r12)
dst_reg->smax_value = S64_MAX;
13a5a: movabs $0x7fffffffffffffff,%rdx
13a64: mov %eax,0x50(%r12)
dst_reg->smin_value = S64_MIN;
13a69: movabs $0x8000000000000000,%rax
s64 res = (s64)((u64)a - (u64)b);
13a73: mov %rdi,%rsi
13a76: sub %rcx,%rsi
if (b < 0)
13a79: test %rcx,%rcx
13a7c: js 145ea <adjust_reg_min_max_vals+0x119a>
if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
13a82: cmp %rsi,%rdi
13a85: jl 13ac7 <adjust_reg_min_max_vals+0x677>
signed_sub_overflows(dst_reg->smax_value, smin_val)) {
13a87: mov 0x30(%r12),%r8
s64 res = (s64)((u64)a - (u64)b);
13a8c: mov %r8,%rax
13a8f: sub %r9,%rax
return res > a;
13a92: cmp %rax,%r8
13a95: setl %sil
if (b < 0)
13a99: test %r9,%r9
13a9c: js 147d1 <adjust_reg_min_max_vals+0x1381>
dst_reg->smax_value = S64_MAX;
13aa2: movabs $0x7fffffffffffffff,%rdx
dst_reg->smin_value = S64_MIN;
13aac: movabs $0x8000000000000000,%rax
if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
13ab6: test %sil,%sil
13ab9: jne 13ac7 <adjust_reg_min_max_vals+0x677>
dst_reg->smin_value -= smax_val;
13abb: mov %rdi,%rax
dst_reg->smax_value -= smin_val;
13abe: mov %r8,%rdx
dst_reg->smin_value -= smax_val;
13ac1: sub %rcx,%rax
dst_reg->smax_value -= smin_val;
13ac4: sub %r9,%rdx
13ac7: mov %rax,0x28(%r12)
...
13ad1: mov %rdx,0x30(%r12)
...
if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
145ea: cmp %rsi,%rdi
145ed: jg 13ac7 <adjust_reg_min_max_vals+0x677>
145f3: jmp 13a87 <adjust_reg_min_max_vals+0x637>
Suggested-by: Jiri Olsa <jolsa@kernel.org>
Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
Some bike shedding. For aesthetic symmetry, we can also change unsigned
overflow check for subtraction to
if (check_sub_overflow(*dst_umin, src_reg->umax_value, dst_umin) ||
check_sub_overflow(*dst_umax, src_reg->umin_value, dst_umax)) {
*dst_umin = 0;
*dst_umax = U64_MAX;
}
The 2nd check_sub_overflow(*dst_umax, src_reg->umin_value, dst_umax) is
redundant (though likely don't matter much in terms of performance), but
without that check we technically can't use the value at the dst_umax
pointer. So that, or
*dst_umax -= src_reg->src_reg->umin_value;
/* if dst_umin does not overflow we know that dst_umax won't either */
if (check_sub_overflow(*dst_umin, src_reg->umax_value, dst_umin)) {
*dst_umin = 0;
*dst_umax = U64_MAX;
}
OTOH current unsigned subtraction check already gives pretty clean
assembly right now (see below), so in terms of assembly I don't think
using check_sub_overflow would make much of a difference.
if (dst_reg->umin_value < umax_val) {
139ea: mov 0x38(%r12),%rax
139ef: cmp %r10,%rax
139f2: jb 14247 <adjust_reg_min_max_vals+0xe57>
dst_reg->umax_value -= umin_val;
139f8: mov 0x40(%r12),%rdx
139fd: mov 0x30(%rsp),%rcx
dst_reg->umin_value -= umax_val;
13a02: sub %r10,%rax
dst_reg->umax_value -= umin_val;
13a05: sub %rcx,%rdx
...
13a12: mov %rdx,0x40(%r12)
13a17: mov %rax,0x38(%r12)
...
dst_reg->umax_value = U64_MAX;
14247: mov $0xffffffffffffffff,%rdx
dst_reg->umin_value = 0;
1424e: xor %eax,%eax
---
kernel/bpf/verifier.c | 57 +++++++++++--------------------------------
1 file changed, 14 insertions(+), 43 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 26c2b7527942..8417f6187961 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12725,26 +12725,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
return 0;
}
-static bool signed_sub_overflows(s64 a, s64 b)
-{
- /* Do the sub in u64, where overflow is well-defined */
- s64 res = (s64)((u64)a - (u64)b);
-
- if (b < 0)
- return res < a;
- return res > a;
-}
-
-static bool signed_sub32_overflows(s32 a, s32 b)
-{
- /* Do the sub in u32, where overflow is well-defined */
- s32 res = (s32)((u32)a - (u32)b);
-
- if (b < 0)
- return res < a;
- return res > a;
-}
-
static bool check_reg_sane_offset(struct bpf_verifier_env *env,
const struct bpf_reg_state *reg,
enum bpf_reg_type type)
@@ -13277,14 +13257,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
/* A new variable offset is created. If the subtrahend is known
* nonnegative, then any reg->range we had before is still good.
*/
- if (signed_sub_overflows(smin_ptr, smax_val) ||
- signed_sub_overflows(smax_ptr, smin_val)) {
+ if (check_sub_overflow(smin_ptr, smax_val, &dst_reg->smin_value) ||
+ check_sub_overflow(smax_ptr, smin_val, &dst_reg->smax_value)) {
/* Overflow possible, we know nothing */
dst_reg->smin_value = S64_MIN;
dst_reg->smax_value = S64_MAX;
- } else {
- dst_reg->smin_value = smin_ptr - smax_val;
- dst_reg->smax_value = smax_ptr - smin_val;
}
if (umin_ptr < umax_val) {
/* Overflow possible, we know nothing */
@@ -13377,19 +13354,16 @@ static void scalar_min_max_add(struct bpf_reg_state *dst_reg,
static void scalar32_min_max_sub(struct bpf_reg_state *dst_reg,
struct bpf_reg_state *src_reg)
{
- s32 smin_val = src_reg->s32_min_value;
- s32 smax_val = src_reg->s32_max_value;
+ s32 *dst_smin = &dst_reg->s32_min_value;
+ s32 *dst_smax = &dst_reg->s32_max_value;
u32 umin_val = src_reg->u32_min_value;
u32 umax_val = src_reg->u32_max_value;
- if (signed_sub32_overflows(dst_reg->s32_min_value, smax_val) ||
- signed_sub32_overflows(dst_reg->s32_max_value, smin_val)) {
+ if (check_sub_overflow(*dst_smin, src_reg->s32_max_value, dst_smin) ||
+ check_sub_overflow(*dst_smax, src_reg->s32_min_value, dst_smax)) {
/* Overflow possible, we know nothing */
- dst_reg->s32_min_value = S32_MIN;
- dst_reg->s32_max_value = S32_MAX;
- } else {
- dst_reg->s32_min_value -= smax_val;
- dst_reg->s32_max_value -= smin_val;
+ *dst_smin = S32_MIN;
+ *dst_smax = S32_MAX;
}
if (dst_reg->u32_min_value < umax_val) {
/* Overflow possible, we know nothing */
@@ -13405,19 +13379,16 @@ static void scalar32_min_max_sub(struct bpf_reg_state *dst_reg,
static void scalar_min_max_sub(struct bpf_reg_state *dst_reg,
struct bpf_reg_state *src_reg)
{
- s64 smin_val = src_reg->smin_value;
- s64 smax_val = src_reg->smax_value;
+ s64 *dst_smin = &dst_reg->smin_value;
+ s64 *dst_smax = &dst_reg->smax_value;
u64 umin_val = src_reg->umin_value;
u64 umax_val = src_reg->umax_value;
- if (signed_sub_overflows(dst_reg->smin_value, smax_val) ||
- signed_sub_overflows(dst_reg->smax_value, smin_val)) {
+ if (check_sub_overflow(*dst_smin, src_reg->smax_value, dst_smin) ||
+ check_sub_overflow(*dst_smax, src_reg->smin_value, dst_smax)) {
/* Overflow possible, we know nothing */
- dst_reg->smin_value = S64_MIN;
- dst_reg->smax_value = S64_MAX;
- } else {
- dst_reg->smin_value -= smax_val;
- dst_reg->smax_value -= smin_val;
+ *dst_smin = S64_MIN;
+ *dst_smax = S64_MAX;
}
if (dst_reg->umin_value < umax_val) {
/* Overflow possible, we know nothing */
--
2.45.2
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows
2024-07-01 5:59 [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 2/2] bpf: use check_sub_overflow() to check for subtraction overflows Shung-Hsi Yu
@ 2024-07-01 9:18 ` Jiri Olsa
2024-07-01 9:45 ` Shung-Hsi Yu
2 siblings, 1 reply; 7+ messages in thread
From: Jiri Olsa @ 2024-07-01 9:18 UTC (permalink / raw)
To: Shung-Hsi Yu
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Andrii Nakryiko, Martin KaFai Lau, Eduard Zingerman, Song Liu,
Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo
On Mon, Jul 01, 2024 at 01:59:03PM +0800, Shung-Hsi Yu wrote:
> This patch set refactors kernel/bpf/verifier.c to use type-agnostic,
> generic overflow-check helpers defined in include/linux/overflow.h to
> check for addition and subtraction overflow, and drop the
> signed_*_overflows() helpers we currently have in kernel/bpf/verifier.c.
> There should be no functional change in how the verifier works.
>
> The main motivation is to make future refactoring[1] easier.
>
> While check_mul_overflow() also exists and could potentially replace what
> we have in scalar*_min_max_mul(), it does not help with refactoring and
> would either change how the verifier works (e.g. lifting restriction on
> umax<=U32_MAX and u32_max<=U16_MAX) or make the code slightly harder to
> read, so it is left for future endeavour.
>
> Changes from v1 <https://lore.kernel.org/r/20240623070324.12634-1-shung-hsi.yu@suse.com>:
> - use pointers to values in dst_reg directly as the sum/diff pointer and
> remove the else branch (Jiri)
> - change local variables to be dst_reg pointers instead of src_reg values
> - include comparison of generated assembly before & after the change
> (Alexei)
>
> 1: https://github.com/kernel-patches/bpf/pull/7205/commits
CI failed, but it looks like aws hiccup:
https://github.com/kernel-patches/bpf/actions/runs/9739067425/job/26873810583
lgtm
Acked-by: Jiri Olsa <jolsa@kernel.org>
jirka
>
> Shung-Hsi Yu (2):
> bpf: use check_add_overflow() to check for addition overflows
> bpf: use check_sub_overflow() to check for subtraction overflows
>
> kernel/bpf/verifier.c | 151 ++++++++++++------------------------------
> 1 file changed, 42 insertions(+), 109 deletions(-)
>
> --
> 2.45.2
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows
2024-07-01 9:18 ` [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Jiri Olsa
@ 2024-07-01 9:45 ` Shung-Hsi Yu
0 siblings, 0 replies; 7+ messages in thread
From: Shung-Hsi Yu @ 2024-07-01 9:45 UTC (permalink / raw)
To: Jiri Olsa
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Andrii Nakryiko, Martin KaFai Lau, Eduard Zingerman, Song Liu,
Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo
On Mon, Jul 01, 2024 at 11:18:39AM GMT, Jiri Olsa wrote:
> On Mon, Jul 01, 2024 at 01:59:03PM +0800, Shung-Hsi Yu wrote:
> > This patch set refactors kernel/bpf/verifier.c to use type-agnostic,
> > generic overflow-check helpers defined in include/linux/overflow.h to
> > check for addition and subtraction overflow, and drop the
> > signed_*_overflows() helpers we currently have in kernel/bpf/verifier.c.
> > There should be no functional change in how the verifier works.
> >
> > The main motivation is to make future refactoring[1] easier.
> >
> > While check_mul_overflow() also exists and could potentially replace what
> > we have in scalar*_min_max_mul(), it does not help with refactoring and
> > would either change how the verifier works (e.g. lifting restriction on
> > umax<=U32_MAX and u32_max<=U16_MAX) or make the code slightly harder to
> > read, so it is left for future endeavour.
> >
> > Changes from v1 <https://lore.kernel.org/r/20240623070324.12634-1-shung-hsi.yu@suse.com>:
> > - use pointers to values in dst_reg directly as the sum/diff pointer and
> > remove the else branch (Jiri)
> > - change local variables to be dst_reg pointers instead of src_reg values
> > - include comparison of generated assembly before & after the change
> > (Alexei)
> >
> > 1: https://github.com/kernel-patches/bpf/pull/7205/commits
>
> CI failed, but it looks like aws hiccup:
> https://github.com/kernel-patches/bpf/actions/runs/9739067425/job/26873810583
Should be, before submitting I've checked that it passed in the BPF
CI[1] through manually opened PR#7280.
> lgtm
>
> Acked-by: Jiri Olsa <jolsa@kernel.org>
Thanks!
1: https://github.com/kernel-patches/bpf/actions/runs/9738751746
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows
2024-07-01 5:59 ` [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows Shung-Hsi Yu
@ 2024-07-10 2:08 ` Alexei Starovoitov
2024-07-11 15:06 ` Shung-Hsi Yu
0 siblings, 1 reply; 7+ messages in thread
From: Alexei Starovoitov @ 2024-07-10 2:08 UTC (permalink / raw)
To: Shung-Hsi Yu
Cc: bpf, Alexei Starovoitov, Jiri Olsa, Daniel Borkmann,
John Fastabend, Andrii Nakryiko, Martin KaFai Lau,
Eduard Zingerman, Song Liu, Yonghong Song, KP Singh,
Stanislav Fomichev, Hao Luo
On Sun, Jun 30, 2024 at 10:59 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> signed_add*_overflows() was added back when there was no overflow-check
> helper. With the introduction of such helpers in commit f0907827a8a91
> ("compiler.h: enable builtin overflow checkers and add fallback code"), we
> can drop signed_add*_overflows() in kernel/bpf/verifier.c and use the
> generic check_add_overflow() instead.
>
> This will make future refactoring easier, and takes advantage of
> compiler-emitted hardware instructions that efficiently implement these
> checks.
>
> After the change GCC 13.3.0 generates cleaner assembly on x86_64:
>
> err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
> 13625: mov 0x28(%rbx),%r9 /* r9 = src_reg->smin_value */
> 13629: mov 0x30(%rbx),%rcx /* rcx = src_reg->smax_value */
> ...
> if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
> 141c1: mov %r9,%rax
> 141c4: add 0x28(%r12),%rax
> 141c9: mov %rax,0x28(%r12)
> 141ce: jo 146e4 <adjust_reg_min_max_vals+0x1294>
> check_add_overflow(*dst_smax, src_reg->smax_value, dst_smax)) {
> 141d4: add 0x30(%r12),%rcx
> 141d9: mov %rcx,0x30(%r12)
> if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
> 141de: jo 146e4 <adjust_reg_min_max_vals+0x1294>
> ...
> *dst_smin = S64_MIN;
> 146e4: movabs $0x8000000000000000,%rax
> 146ee: mov %rax,0x28(%r12)
> *dst_smax = S64_MAX;
> 146f3: sub $0x1,%rax
> 146f7: mov %rax,0x30(%r12)
>
> Before the change it gives:
>
> s64 smin_val = src_reg->smin_value;
> 675: mov 0x28(%rsi),%r8
> s64 smax_val = src_reg->smax_value;
> u64 umin_val = src_reg->umin_value;
> u64 umax_val = src_reg->umax_value;
> 679: mov %rdi,%rax /* rax = dst_reg */
> if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> 67c: mov 0x28(%rdi),%rdi /* rdi = dst_reg->smin_value */
> u64 umin_val = src_reg->umin_value;
> 680: mov 0x38(%rsi),%rdx
> u64 umax_val = src_reg->umax_value;
> 684: mov 0x40(%rsi),%rcx
> s64 res = (s64)((u64)a + (u64)b);
> 688: lea (%r8,%rdi,1),%r9 /* r9 = dst_reg->smin_value + src_reg->smin_value */
> return res < a;
> 68c: cmp %r9,%rdi
> 68f: setg %r10b /* r10b = (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value */
> if (b < 0)
> 693: test %r8,%r8
> 696: js 72b <scalar_min_max_add+0xbb>
> signed_add_overflows(dst_reg->smax_value, smax_val)) {
> dst_reg->smin_value = S64_MIN;
> dst_reg->smax_value = S64_MAX;
> 69c: movabs $0x7fffffffffffffff,%rdi
> s64 smax_val = src_reg->smax_value;
> 6a6: mov 0x30(%rsi),%r8
> dst_reg->smin_value = S64_MIN;
> 6aa: 00 00 00 movabs $0x8000000000000000,%rsi
> if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> 6b4: test %r10b,%r10b /* (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value ? goto 6cb */
> 6b7: jne 6cb <scalar_min_max_add+0x5b>
> signed_add_overflows(dst_reg->smax_value, smax_val)) {
> 6b9: mov 0x30(%rax),%r10 /* r10 = dst_reg->smax_value */
> s64 res = (s64)((u64)a + (u64)b);
> 6bd: lea (%r10,%r8,1),%r11 /* r11 = dst_reg->smax_value + src_reg->smax_value */
> if (b < 0)
> 6c1: test %r8,%r8
> 6c4: js 71e <scalar_min_max_add+0xae>
> if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> 6c6: cmp %r11,%r10 /* (dst_reg->smax_value + src_reg->smax_value) <= dst_reg->smax_value ? goto 723 */
> 6c9: jle 723 <scalar_min_max_add+0xb3>
> } else {
> dst_reg->smin_value += smin_val;
> dst_reg->smax_value += smax_val;
> }
> 6cb: mov %rsi,0x28(%rax)
> ...
> 6d5: mov %rdi,0x30(%rax)
> ...
> if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> 71e: cmp %r11,%r10
> 721: jl 6cb <scalar_min_max_add+0x5b>
> dst_reg->smin_value += smin_val;
> 723: mov %r9,%rsi
> dst_reg->smax_value += smax_val;
> 726: mov %r11,%rdi
> 729: jmp 6cb <scalar_min_max_add+0x5b>
> return res > a;
> 72b: cmp %r9,%rdi
> 72e: setl %r10b
> 732: jmp 69c <scalar_min_max_add+0x2c>
> 737: nopw 0x0(%rax,%rax,1)
>
> Suggested-by: Jiri Olsa <jolsa@kernel.org>
> Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> ---
> kernel/bpf/verifier.c | 94 +++++++++++++------------------------------
> 1 file changed, 28 insertions(+), 66 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d3927d819465..26c2b7527942 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12725,26 +12725,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> return 0;
> }
>
> -static bool signed_add_overflows(s64 a, s64 b)
> -{
> - /* Do the add in u64, where overflow is well-defined */
> - s64 res = (s64)((u64)a + (u64)b);
> -
> - if (b < 0)
> - return res > a;
> - return res < a;
> -}
> -
> -static bool signed_add32_overflows(s32 a, s32 b)
> -{
> - /* Do the add in u32, where overflow is well-defined */
> - s32 res = (s32)((u32)a + (u32)b);
> -
> - if (b < 0)
> - return res > a;
> - return res < a;
> -}
Looks good,
unfortunately it gained conflict while sitting in the queue.
signed_add16_overflows() was introduced.
Could you please respin replacing signed_add16_overflows()
with check_add_overflow() ?
pw-bot: cr
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows
2024-07-10 2:08 ` Alexei Starovoitov
@ 2024-07-11 15:06 ` Shung-Hsi Yu
0 siblings, 0 replies; 7+ messages in thread
From: Shung-Hsi Yu @ 2024-07-11 15:06 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: bpf, Alexei Starovoitov, Jiri Olsa, Daniel Borkmann,
John Fastabend, Andrii Nakryiko, Martin KaFai Lau,
Eduard Zingerman, Song Liu, Yonghong Song, KP Singh,
Stanislav Fomichev, Hao Luo
On Tue, Jul 09, 2024 at 07:08:31PM GMT, Alexei Starovoitov wrote:
> On Sun, Jun 30, 2024 at 10:59 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> >
> > signed_add*_overflows() was added back when there was no overflow-check
> > helper. With the introduction of such helpers in commit f0907827a8a91
> > ("compiler.h: enable builtin overflow checkers and add fallback code"), we
> > can drop signed_add*_overflows() in kernel/bpf/verifier.c and use the
> > generic check_add_overflow() instead.
> >
> > This will make future refactoring easier, and takes advantage of
> > compiler-emitted hardware instructions that efficiently implement these
> > checks.
> >
> > After the change GCC 13.3.0 generates cleaner assembly on x86_64:
> >
> > err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
> > 13625: mov 0x28(%rbx),%r9 /* r9 = src_reg->smin_value */
> > 13629: mov 0x30(%rbx),%rcx /* rcx = src_reg->smax_value */
> > ...
> > if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
> > 141c1: mov %r9,%rax
> > 141c4: add 0x28(%r12),%rax
> > 141c9: mov %rax,0x28(%r12)
> > 141ce: jo 146e4 <adjust_reg_min_max_vals+0x1294>
> > check_add_overflow(*dst_smax, src_reg->smax_value, dst_smax)) {
> > 141d4: add 0x30(%r12),%rcx
> > 141d9: mov %rcx,0x30(%r12)
> > if (check_add_overflow(*dst_smin, src_reg->smin_value, dst_smin) ||
> > 141de: jo 146e4 <adjust_reg_min_max_vals+0x1294>
> > ...
> > *dst_smin = S64_MIN;
> > 146e4: movabs $0x8000000000000000,%rax
> > 146ee: mov %rax,0x28(%r12)
> > *dst_smax = S64_MAX;
> > 146f3: sub $0x1,%rax
> > 146f7: mov %rax,0x30(%r12)
> >
> > Before the change it gives:
> >
> > s64 smin_val = src_reg->smin_value;
> > 675: mov 0x28(%rsi),%r8
> > s64 smax_val = src_reg->smax_value;
> > u64 umin_val = src_reg->umin_value;
> > u64 umax_val = src_reg->umax_value;
> > 679: mov %rdi,%rax /* rax = dst_reg */
> > if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> > 67c: mov 0x28(%rdi),%rdi /* rdi = dst_reg->smin_value */
> > u64 umin_val = src_reg->umin_value;
> > 680: mov 0x38(%rsi),%rdx
> > u64 umax_val = src_reg->umax_value;
> > 684: mov 0x40(%rsi),%rcx
> > s64 res = (s64)((u64)a + (u64)b);
> > 688: lea (%r8,%rdi,1),%r9 /* r9 = dst_reg->smin_value + src_reg->smin_value */
> > return res < a;
> > 68c: cmp %r9,%rdi
> > 68f: setg %r10b /* r10b = (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value */
> > if (b < 0)
> > 693: test %r8,%r8
> > 696: js 72b <scalar_min_max_add+0xbb>
> > signed_add_overflows(dst_reg->smax_value, smax_val)) {
> > dst_reg->smin_value = S64_MIN;
> > dst_reg->smax_value = S64_MAX;
> > 69c: movabs $0x7fffffffffffffff,%rdi
> > s64 smax_val = src_reg->smax_value;
> > 6a6: mov 0x30(%rsi),%r8
> > dst_reg->smin_value = S64_MIN;
> > 6aa: 00 00 00 movabs $0x8000000000000000,%rsi
> > if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> > 6b4: test %r10b,%r10b /* (dst_reg->smin_value + src_reg->smin_value) > dst_reg->smin_value ? goto 6cb */
> > 6b7: jne 6cb <scalar_min_max_add+0x5b>
> > signed_add_overflows(dst_reg->smax_value, smax_val)) {
> > 6b9: mov 0x30(%rax),%r10 /* r10 = dst_reg->smax_value */
> > s64 res = (s64)((u64)a + (u64)b);
> > 6bd: lea (%r10,%r8,1),%r11 /* r11 = dst_reg->smax_value + src_reg->smax_value */
> > if (b < 0)
> > 6c1: test %r8,%r8
> > 6c4: js 71e <scalar_min_max_add+0xae>
> > if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> > 6c6: cmp %r11,%r10 /* (dst_reg->smax_value + src_reg->smax_value) <= dst_reg->smax_value ? goto 723 */
> > 6c9: jle 723 <scalar_min_max_add+0xb3>
> > } else {
> > dst_reg->smin_value += smin_val;
> > dst_reg->smax_value += smax_val;
> > }
> > 6cb: mov %rsi,0x28(%rax)
> > ...
> > 6d5: mov %rdi,0x30(%rax)
> > ...
> > if (signed_add_overflows(dst_reg->smin_value, smin_val) ||
> > 71e: cmp %r11,%r10
> > 721: jl 6cb <scalar_min_max_add+0x5b>
> > dst_reg->smin_value += smin_val;
> > 723: mov %r9,%rsi
> > dst_reg->smax_value += smax_val;
> > 726: mov %r11,%rdi
> > 729: jmp 6cb <scalar_min_max_add+0x5b>
> > return res > a;
> > 72b: cmp %r9,%rdi
> > 72e: setl %r10b
> > 732: jmp 69c <scalar_min_max_add+0x2c>
> > 737: nopw 0x0(%rax,%rax,1)
> >
> > Suggested-by: Jiri Olsa <jolsa@kernel.org>
> > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > ---
> > kernel/bpf/verifier.c | 94 +++++++++++++------------------------------
> > 1 file changed, 28 insertions(+), 66 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index d3927d819465..26c2b7527942 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -12725,26 +12725,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> > return 0;
> > }
> >
> > -static bool signed_add_overflows(s64 a, s64 b)
> > -{
> > - /* Do the add in u64, where overflow is well-defined */
> > - s64 res = (s64)((u64)a + (u64)b);
> > -
> > - if (b < 0)
> > - return res > a;
> > - return res < a;
> > -}
> > -
> > -static bool signed_add32_overflows(s32 a, s32 b)
> > -{
> > - /* Do the add in u32, where overflow is well-defined */
> > - s32 res = (s32)((u32)a + (u32)b);
> > -
> > - if (b < 0)
> > - return res > a;
> > - return res < a;
> > -}
>
> Looks good,
> unfortunately it gained conflict while sitting in the queue.
> signed_add16_overflows() was introduced.
> Could you please respin replacing signed_add16_overflows()
> with check_add_overflow() ?
Ack, will send respin a v3 patchset tomorrow.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2024-07-11 15:06 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-07-01 5:59 [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 1/2] bpf: use check_add_overflow() to check for addition overflows Shung-Hsi Yu
2024-07-10 2:08 ` Alexei Starovoitov
2024-07-11 15:06 ` Shung-Hsi Yu
2024-07-01 5:59 ` [PATCH bpf-next v2 2/2] bpf: use check_sub_overflow() to check for subtraction overflows Shung-Hsi Yu
2024-07-01 9:18 ` [PATCH bpf-next v2 0/2] Use overflow.h helpers to check for overflows Jiri Olsa
2024-07-01 9:45 ` Shung-Hsi Yu
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.