selftests/bpf: Fix zero batch_hash on CPU 0 after batch_gen wraparound
Subsystems (4)
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 0Setting 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
--- 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
@@ -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
Quoted 8 lines · Muhammad Bilal
commit
fa747e9f843b("selftests/bpf: Fixcold_lruproducing zerobatch_hashin XDP LB benchmark") claims the addition ensures the multiplier input is "always >= 1". This invariant does not hold after wraparound.batch_genis__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 0Setting bit 0 before multiplying guarantees a non-zero odd result for all possible values of
batch_genandcpu_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.
Quoted 3 lines · Puranjay Mohan
A single batch runs for 10ms, and
batch_genis 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
[email protected]
AI reviewThank 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@@ -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
-0if ((void *)(saddr +1 ) <= data_end) *saddr ^= batch_hash; }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
[email protected]
AI reviewDoes 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@@ -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 = 3Could 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
-0if ((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