Skip to contentSkip to conversation

bpf: use div64_u64{,_rem}() in scev.c

PATCH Applied Eduard Zingerman 2 participants 2 messages Oct 10 – Oct 11 BPF

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

PATCH 1/1 bpf: use div64_u64{,_rem}() in scev.c

For whatever reason gcc built-ins implementing 64-bit division are not wired into 32-bit kernel builds:

ld: kernel/bpf/scev.c:2074:(.text+0x4512): undefined reference to `__udivdi3'
ld: kernel/bpf/scev.c:2141:(.text+0x475b): undefined reference to `__udivmoddi4'

Instead, one has to use div64_u64() and div64_u64_rem() explicitly.

---
 kernel/bpf/scev.c | 39 ++++++++++++++++++++-------------------
 1 file changed, 20 insertions(+), 19 deletions(-)
kernel/bpf/scev.c +20 -19
index adad32d8cb12..48500d73105a 100644
@@ -5,6 +5,7 @@
 #include <linux/bpf_verifier.h>
 #include <linux/jhash.h>
 #include <linux/log2.h>
+#include <linux/math64.h>
 #include <linux/min_heap.h>
 #include <linux/bug.h>
 #include <linux/tnum.h>
@@ -2083,7 +2084,7 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 	struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop;
 	struct scev *scev = env->scev;
 	struct scev_value initial_val, step_val, bound_val;
-	u64 step, diff, bound, initial, backedge_taken_count;
+	u64 rem, step, diff, bound, initial, backedge_taken_count;
 	u8 op = latch->op;
 	bool up, down;
 
@@ -2129,26 +2130,26 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		    /* Is the latch condition false on the first iteration? */
 		    initial >= bound ||
 		    /* Count iterations satisfying the strict inequality, including i=0. */
-		    check_add_overflow((diff - 1) / step, 1, &backedge_taken_count) ||
+		    check_add_overflow(div64_u64(diff - 1, step), 1, &backedge_taken_count) ||
 		    /*
 		     * Check if the last iteration overflows the counter:
 		     *   initial + backedge_taken_count * step > U64_MAX
 		     */
-		    backedge_taken_count > (U64_MAX - initial) / step)
+		    backedge_taken_count > div64_u64(U64_MAX - initial, step))
 			return false;
 		break;
 	case BPF_JLE:
 		/* E.g.: 3 + 2*i ≤ 7 ⇔ 2*i ≤ 4 ⇔ i ∈ [0,1,2]. */
 		if (down || initial > bound ||
 		    /* Count iterations satisfying the non-strict inequality. */
-		    check_add_overflow(diff / step, 1, &backedge_taken_count) ||
-		    backedge_taken_count > (U64_MAX - initial) / step)
+		    check_add_overflow(div64_u64(diff, step), 1, &backedge_taken_count) ||
+		    backedge_taken_count > div64_u64(U64_MAX - initial, step))
 			return false;
 		break;
 	case BPF_JGT:
 		/* E.g.: 7 - 2*i > 3 ⇔ 2*i < 4 ⇔ i ∈ [0,1]. */
 		if (up || initial <= bound ||
-		    check_add_overflow((-diff - 1) / -step, 1, &backedge_taken_count) ||
+		    check_add_overflow(div64_u64(-diff - 1, -step), 1, &backedge_taken_count) ||
 		    /*
 		     * The last iteration underflows the counter if:
 		     *   initial + backedge_taken_count * step < 0 ⇔
@@ -2156,35 +2157,35 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		     *                    backedge_taken_count > initial / -step
 		     * (direction flips because step < 0)
 		     */
-		    backedge_taken_count > initial / -step)
+		    backedge_taken_count > div64_u64(initial, -step))
 			return false;
 		break;
 	case BPF_JGE:
 		/* E.g.: 7 - 2*i ≥ 3 ⇔ 2*i ≤ 4 ⇔ i ∈ [0,1,2]. */
 		if (up || initial < bound ||
-		    check_add_overflow(-diff / -step, 1, &backedge_taken_count) ||
-		    backedge_taken_count > initial / -step)
+		    check_add_overflow(div64_u64(-diff, -step), 1, &backedge_taken_count) ||
+		    backedge_taken_count > div64_u64(initial, -step))
 			return false;
 		break;
 	case BPF_JSLT:
 		if (down || (s64)initial >= (s64)bound ||
-		    check_add_overflow((diff - 1) / step, 1, &backedge_taken_count) ||
+		    check_add_overflow(div64_u64(diff - 1, step), 1, &backedge_taken_count) ||
 		    /*
 		     * Check if the last iteration overflows the signed counter:
 		     *   (s64)initial + backedge_taken_count * step > S64_MAX
 		     */
-		    backedge_taken_count > ((u64)S64_MAX - initial) / step)
+		    backedge_taken_count > div64_u64((u64)S64_MAX - initial, step))
 			return false;
 		break;
 	case BPF_JSLE:
 		if (down || (s64)initial > (s64)bound ||
-		    check_add_overflow(diff / step, 1, &backedge_taken_count) ||
-		    backedge_taken_count > ((u64)S64_MAX - initial) / step)
+		    check_add_overflow(div64_u64(diff, step), 1, &backedge_taken_count) ||
+		    backedge_taken_count > div64_u64((u64)S64_MAX - initial, step))
 			return false;
 		break;
 	case BPF_JSGT:
 		if (up || (s64)initial <= (s64)bound ||
-		    check_add_overflow((-diff - 1) / -step, 1, &backedge_taken_count) ||
+		    check_add_overflow(div64_u64(-diff - 1, -step), 1, &backedge_taken_count) ||
 		    /*
 		     * The last iteration underflows the signed counter if:
 		     *   (s64)initial + backedge_taken_count * step < S64_MIN ⇔
@@ -2192,13 +2193,13 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		     *                         backedge_taken_count > initial - (u64)S64_MIN / -step
 		     *	 (direction flips because step < 0)
 		     */
-		    backedge_taken_count > (initial - (u64)S64_MIN) / -step)
+		    backedge_taken_count > div64_u64(initial - (u64)S64_MIN, -step))
 			return false;
 		break;
 	case BPF_JSGE:
 		if (up || (s64)initial < (s64)bound ||
-		    check_add_overflow(-diff / -step, 1, &backedge_taken_count) ||
-		    backedge_taken_count > (initial - (u64)S64_MIN) / -step)
+		    check_add_overflow(div64_u64(-diff, -step), 1, &backedge_taken_count) ||
+		    backedge_taken_count > div64_u64(initial - (u64)S64_MIN, -step))
 			return false;
 		break;
 	case BPF_JNE:
@@ -2208,9 +2209,9 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		 */
 		diff = down ? -diff : diff;
 		step = down ? -step : step;
-		if (diff == 0 || diff % step)
+		backedge_taken_count = div64_u64_rem(diff, step, &rem);
+		if (diff == 0 || rem != 0)
 			return false;
-		backedge_taken_count = diff / step;
 		break;
 	default:
 		return false;
Signature · 1 line
2.53.0
#1 lore raw
This patch was applied to bpf/bpf-next.git (master) by Kumar Kartikeya Dwivedi <[email protected]>:

Hello:

This patch was applied to bpf/bpf-next.git (master) by Kumar Kartikeya Dwivedi <[email protected]>:

Quoted 9 lines · On Sat, 10 Oct 2026 13:58:26 -0700 you wrote:

For whatever reason gcc built-ins implementing 64-bit division are not wired into 32-bit kernel builds:

   ld: kernel/bpf/scev.c:2074:(.text+0x4512): undefined reference to `__udivdi3'
   ld: kernel/bpf/scev.c:2141:(.text+0x475b): undefined reference to `__udivmoddi4'

Instead, one has to use div64_u64() and div64_u64_rem() explicitly.

[...]

Here is the summary with links:
- bpf: use div64_u64{,_rem}() in scev.c

    https://git.kernel.org/bpf/bpf-next/c/4cce28612bf7

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html