Skip to contentSkip to conversation

selftests/bpf: Fix zero batch_hash on CPU 0 after batch_gen wraparound

PATCH In review Muhammad Bilal 4 participants 5 messages May 20

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 selftests/bpf: Fix zero batch_hash on CPU 0 after batch_gen wraparound

commit fa747e9f843b ("selftests/bpf: Fix cold_lru producing zero batch_hash in XDP LB benchmark") claims the addition ensures the multiplier input is "always >= 1". This invariant does not hold after wraparound.

batch_gen is __u32. After 2^32 increments it wraps to 0. On CPU 0, bpf_get_smp_processor_id() returns 0:

    batch_gen = 0  (after u32 wraparound)
    batch_hash = (0 + 0) * KNUTH_HASH_MULT = 0
    *saddr ^= 0  ->  no-op, cold_lru miss counter stays 0

Setting bit 0 before multiplying guarantees a non-zero odd result for all possible values of batch_gen and cpu_id, including after wraparound:

(any_value | 1) >= 1 always, since bit 0 is always set

Fixes fa747e9f843b ("selftests/bpf: Fix cold_lru producing zero batch_hash in XDP LB benchmark")
---
 tools/testing/selftests/bpf/progs/xdp_lb_bench.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/xdp_lb_bench.c +1 -1
index 13777b3dcac8..816880c1cd5e 100644
@@ -618,7 +618,7 @@ int xdp_lb_bench(struct xdp_md *xdp)
 		__u32 *saddr = data + saddr_off;
 
 		batch_gen++;
-		batch_hash = (batch_gen + bpf_get_smp_processor_id()) * KNUTH_HASH_MULT;
+		batch_hash = ((batch_gen + bpf_get_smp_processor_id()) | 1) * KNUTH_HASH_MULT;
 		if ((void *)(saddr + 1) <= data_end)
 			*saddr ^= batch_hash;
 	}
Signature · 1 line
2.53.0
#1 lore raw
Quoted 8 lines · Muhammad Bilal

commit fa747e9f843b ("selftests/bpf: Fix cold_lru producing zero batch_hash in XDP LB benchmark") claims the addition ensures the multiplier input is "always >= 1". This invariant does not hold after wraparound.
batch_gen is __u32. After 2^32 increments it wraps to 0. On CPU 0, bpf_get_smp_processor_id() returns 0:

Quoted 8 lines
    batch_gen = 0  (after u32 wraparound)
    batch_hash = (0 + 0) * KNUTH_HASH_MULT = 0
    *saddr ^= 0  ->  no-op, cold_lru miss counter stays 0

Setting bit 0 before multiplying guarantees a non-zero odd result for all possible values of batch_gen and cpu_id, including after wraparound:

(any_value | 1) >= 1 always, since bit 0 is always set

You say - batch_gen is __u32. After 2^32 increments it wraps to 0

A single batch runs for 10ms, and batch_gen is incremented for every batch, so for it to wrap we need to run the benchmark for 1000+ years with a single producer.

and even if we want to benchmark for 1000 years and want to fix this, then doing " | 1 " is not the correct way because:

On CPU 0, consecutive batches with | 1:

  batch_gen=2:  (2 + 0) | 1 = 3,  batch_hash = 3 * KNUTH
  batch_gen=3:  (3 + 0) | 1 = 3,  batch_hash = 3 * KNUTH
  batch_gen=4:  (4 + 0) | 1 = 5,  batch_hash = 5 * KNUTH
  batch_gen=5:  (5 + 0) | 1 = 5,  batch_hash = 5 * KNUTH

Each even/odd pair of batch_gen values collapses to the same batch_hash, so half the batches reuse the previous batch's cold address which is already warm in the LRU.

#2 lore raw
Quoted 3 lines · Puranjay Mohan

A single batch runs for 10ms, and batch_gen is incremented for every batch, so for it to wrap we need to run the benchmark for 1000+ years with a single producer.

You're right, the wraparound argument is not practically relevant here.

Quoted 3 lines

On CPU 0, consecutive batches with | 1:

  batch_gen=2:  (2 + 0) | 1 = 3,  batch_hash = 3 * KNUTH
  batch_gen=3:  (3 + 0) | 1 = 3,  batch_hash = 3 * KNUTH

This is a valid issue. The proposed change introduces unwanted collisions between consecutive batch_gen values on CPU 0, which is worse than the current behavior.

I'll drop this patch.

Thanks for the review.

Muhammad Bilal

#3 lore raw
In reply to Muhammad Bilal
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] Using a bitwise OR with 1 (`| 1`) to calculate `batch_hash` halves the sequence entropy by…

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Using a bitwise OR with 1 (| 1) to calculate batch_hash halves the sequence entropy by producing identical hashes for consecutive executions. --

commit 49a119687bbbdd80daaf459fad5761690fff9da3
Author: Muhammad Bilal <[email protected]>

selftests/bpf: Fix zero batch_hash on CPU 0 after batch_gen wraparound

This commit attempts to fix a rare zero batch_hash case on CPU 0 after batch_gen wraparound by setting bit 0 before multiplying by KNUTH_HASH_MULT. It modifies xdp_lb_bench.c to use a bitwise OR with 1.

tools/testing/selftests/bpf/progs/xdp_lb_bench.c int xdp_lb_bench(struct xdp_md *xdp) · line 621

Quoted 10 lines
tools/testing/selftests/bpf/progs/xdp_lb_bench.c +1 -1
index 13777b3dcac8c..816880c1cd5e0 100644
@@ -618,7 +618,7 @@ int xdp_lb_bench(struct xdp_md *xdp)
 		__u32 *saddr = data + saddr_off;
 
 		batch_gen++;
-		batch_hash = (batch_gen + bpf_get_smp_processor_id()) * KNUTH_HASH_MULT;
+		batch_hash = ((batch_gen + bpf_get_smp_processor_id()) | 1) * KNUTH_HASH_MULT;

[Severity: Medium]
Does applying a bitwise OR with 1 here halve the sequence entropy and produce identical hashes for consecutive executions?

Since batch_gen is incremented sequentially, the sum of batch_gen and the processor ID will alternate between even and odd values on a given CPU. Applying a bitwise OR with 1 maps consecutive pairs to the exact same odd number (for example, 2 | 1 = 3, and 3 | 1 = 3).

In the context of a cold LRU benchmark, reusing the same hash causes the modified source address to perfectly match the previous run, leading to artificial cache hits in half of the runs. This persistent collision rate might degrade the benchmark's accuracy significantly more than the rare wraparound to zero it tries to fix.

Would using a ternary operator like val ?: 1 avoid the zero case without destroying sequence uniqueness?

Quoted 3 lines
tools/testing/selftests/bpf/progs/xdp_lb_bench.c +0 -0
 		if ((void *)(saddr + 1) <= data_end)
 			*saddr ^= batch_hash;
 	}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#4 lore raw
In reply to Muhammad Bilal
Does forcing the LSB to 1 with '| 1' inadvertently destroy the lowest bit of entropy from the batch generator?

tools/testing/selftests/bpf/progs/xdp_lb_bench.c int xdp_lb_bench(struct xdp_md *xdp) · line 621

Quoted 10 lines
tools/testing/selftests/bpf/progs/xdp_lb_bench.c +1 -1
index 13777b3dcac8..816880c1cd5e 100644
@@ -618,7 +618,7 @@ int xdp_lb_bench(struct xdp_md *xdp)
 		__u32 *saddr = data + saddr_off;
 
 		batch_gen++;
-		batch_hash = (batch_gen + bpf_get_smp_processor_id()) * KNUTH_HASH_MULT;
+		batch_hash = ((batch_gen + bpf_get_smp_processor_id()) | 1) * KNUTH_HASH_MULT;
                         ^^^^

Does forcing the LSB to 1 with '| 1' inadvertently destroy the lowest bit of entropy from the batch generator?

Since batch_gen increments sequentially by 1 per batch execution, forcing the least significant bit to 1 maps pairs of adjacent values to the same number.

For example, if the CPU ID evaluates to 0, both batch_gen = 2 and batch_gen = 3 will yield 3 before the multiplication:

    batch_gen = 2, CPU = 0: (2 + 0) | 1 = 3
    batch_gen = 3, CPU = 0: (3 + 0) | 1 = 3

Could this cause 50% of consecutive batches to generate the exact same batch_hash as the previous batch, causing those iterations to hit the warm LRU cache entries that were just populated and defeating the purpose of the cold_lru benchmark?

This concern was raised in Puranjay's v1 patch where he used XOR instead of addition, and he acknowledged the issue and switched to plain addition in v2. This patch reintroduces the same '| 1' approach with addition, but the entropy-loss problem remains.

Referenced discussion:
https://lore.kernel.org/bpf/2afdea40f0c5a11c2337efafe6f460899d85bc28650e04d5e0b9ceb35f3ad9fc@mail.kernel.org/

tools/testing/selftests/bpf/progs/xdp_lb_bench.c int xdp_lb_bench(struct xdp_md *xdp) · line 624

Quoted 3 lines
tools/testing/selftests/bpf/progs/xdp_lb_bench.c +0 -0
 		if ((void *)(saddr + 1) <= data_end)
 			*saddr ^= batch_hash;
 	}

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/26188863722