The hash and array batch validators mark visited entries by output
position, making the subsequent completeness checks always succeed.
Duplicate keys with matching values can therefore hide missing entries.

Check that returned keys fall within the populated range and index
the visited array by key. This detects missing entries while preserving
unordered results and existing per-CPU value validation.

Controlled inputs confirm that the old validators accept duplicates
and out-of-range keys with matching values, while the updated checks
reject them. Ordered, reversed and shuffled valid keys still pass,
and scalar and per-CPU value corruption is still rejected. The full
test_maps suite passes with no skips on the matching kernel.

Fixes: 30ff3c59137d ("selftests/bpf: Add batch ops testing for htab and htab_percpu map")
Fixes: f0fac2cec286 ("selftests/bpf: Add batch ops testing to array bpf map")
Assisted-by: LLM
Signed-off-by: Tianyi Chen <hi@tychen.cc>
---
 tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c | 5 ++++-
 tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c  | 4 +++-
 2 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c b/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
index b595556315b..76d3800a82a 100644
--- a/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
+++ b/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
@@ -45,6 +45,9 @@ static void map_batch_verify(int *visited, __u32 max_entries, int *keys,
 
 	memset(visited, 0, max_entries * sizeof(*visited));
 	for (i = 0; i < max_entries; i++) {
+		CHECK(keys[i] < 0 || keys[i] >= max_entries, "key checking",
+		      "error: i %d key %d out of range\n", i, keys[i]);
+
 		if (is_pcpu) {
 			cpu_offset = i * nr_cpus;
 			for (j = 0; j < nr_cpus; j++) {
@@ -59,7 +62,7 @@ static void map_batch_verify(int *visited, __u32 max_entries, int *keys,
 			      "error: i %d key %d value %lld\n", i, keys[i],
 			      values[i]);
 		}
-		visited[i] = 1;
+		visited[keys[i]] = 1;
 	}
 	for (i = 0; i < max_entries; i++) {
 		CHECK(visited[i] != 1, "visited checking",
diff --git a/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c b/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
index 5da493b94ae..430949f9691 100644
--- a/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
+++ b/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
@@ -50,6 +50,8 @@ static void map_batch_verify(int *visited, __u32 max_entries,
 
 	memset(visited, 0, max_entries * sizeof(*visited));
 	for (i = 0; i < max_entries; i++) {
+		CHECK(keys[i] < 1 || keys[i] > max_entries, "key checking",
+		      "error: i %d key %d out of range\n", i, keys[i]);
 
 		if (is_pcpu) {
 			for (j = 0; j < bpf_num_possible_cpus(); j++) {
@@ -65,7 +67,7 @@ static void map_batch_verify(int *visited, __u32 max_entries,
 			      ((int *)values)[i]);
 		}
 
-		visited[i] = 1;
+		visited[keys[i] - 1] = 1;
 
 	}
 	for (i = 0; i < max_entries; i++) {
-- 
2.55.0

> diff --git a/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c b/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
> index b595556315bc..76d3800a82af 100644
> --- a/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
> +++ b/tools/testing/selftests/bpf/map_tests/array_map_batch_ops.c
> @@ -45,6 +45,9 @@ static void map_batch_verify(int *visited, __u32 max_entries, int *keys,
>
>  	memset(visited, 0, max_entries * sizeof(*visited));
>  	for (i = 0; i < max_entries; i++) {
> +		CHECK(keys[i] < 0 || keys[i] >= max_entries, "key checking",
> +		      "error: i %d key %d out of range\n", i, keys[i]);
> +
>  		if (is_pcpu) {
>  			cpu_offset = i * nr_cpus;
>  			for (j = 0; j < nr_cpus; j++) {
> @@ -59,7 +62,7 @@ static void map_batch_verify(int *visited, __u32 max_entries, int *keys,
>  			      "error: i %d key %d value %lld\n", i, keys[i],
>  			      values[i]);
>  		}
> -		visited[i] = 1;
> +		visited[keys[i]] = 1;
>  	}
>  	for (i = 0; i < max_entries; i++) {
>  		CHECK(visited[i] != 1, "visited checking",
> diff --git a/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c b/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
> index 5da493b94ae2..430949f9691d 100644
> --- a/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
> +++ b/tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c
> @@ -50,6 +50,8 @@ static void map_batch_verify(int *visited, __u32 max_entries,
>
>  	memset(visited, 0, max_entries * sizeof(*visited));
>  	for (i = 0; i < max_entries; i++) {
> +		CHECK(keys[i] < 1 || keys[i] > max_entries, "key checking",
> +		      "error: i %d key %d out of range\n", i, keys[i]);
>
>  		if (is_pcpu) {
>  			for (j = 0; j < bpf_num_possible_cpus(); j++) {
> @@ -65,7 +67,7 @@ static void map_batch_verify(int *visited, __u32 max_entries,
>  			      ((int *)values)[i]);
>  		}
>
> -		visited[i] = 1;
> +		visited[keys[i] - 1] = 1;
>
>  	}
>  	for (i = 0; i < max_entries; i++) {

This isn't a bug, but map_tests/ has three near-identical batch
validators, and lpm_trie_map_batch_ops.c still has the same
position-indexed visited[i] = 1 marking that this patch replaces in the
array and htab copies. The changelog scopes itself to 'the hash and
array batch validators', and the LPM key is a struct so it cannot index
visited directly, but would it be worth covering the third validator in
the same series (perhaps keyed off the parsed last octet), or is the
struct key a reason to leave it alone?

The first half of the changelog states the problem and the fix clearly.

> The hash and array batch validators mark visited entries by output
> position, making the subsequent completeness checks always succeed.
> Duplicate keys with matching values can therefore hide missing entries.
>
> Check that returned keys fall within the populated range and index
> the visited array by key. This detects missing entries while preserving
> unordered results and existing per-CPU value validation.
>
> Controlled inputs confirm that the old validators accept duplicates
> and out-of-range keys with matching values, while the updated checks
> reject them. Ordered, reversed and shuffled valid keys still pass,
> and scalar and per-CPU value corruption is still rejected. The full
> test_maps suite passes with no skips on the matching kernel.

This isn't a bug, but the last five lines describe an ad hoc validation
harness that is not part of the patch and cannot be reproduced from it.
Would this validation narrative read better below the --- line, leaving
the changelog to the problem and the fix?


---
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/34040182269

Thanks for pointing out the third validator.

I have included the LPM trie case in v2. The struct key is not a reason
to leave it out: the updated check validates the /32 prefix and complete
192.168.1.x address, then checks the host octet against the inserted key
range before using it to index visited.

I also moved the validation notes below the --- separator, leaving the
commit message focused on the problem and the fix.

The revised full test_maps suite passes with no skips on the matching
kernel, including array, per-CPU array, hash, per-CPU hash and LPM batch
tests. The revised patch is here:

https://lore.kernel.org/bpf/178870889323.880246.16480713814270899611.bpf-batch-v2@tychen.cc/

Thanks,
Tianyi