Skip to contentSkip to conversation

bpf: Support bpf_for_each_map_elem() for BPF_MAP_TYPE_HASH_OF_MAPS maps

PATCH In review David Vernet 2 participants 4 messages Jun 5, 2023

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

PATCH 1/2 bpf: Support bpf_for_each_map_elem() for BPF_MAP_TYPE_HASH_OF_MAPS maps

The bpf_for_each_map_elem() helper can be used to iterate over all of the elements of a map. The helper is not supported for all maps, which currently includes the BPF_MAP_TYPE_HASH_OF_MAPS map type. Other hash map types, such as BPF_MAP_TYPE_HASH, BPF_MAP_TYPE_PERCPU_HASH, etc, do support this helper, so adding support for a hash of maps map type doesn't require much code change.

The current use case for this is sched_ext, where we want to populate a hashmap of cgroup id -> array of integers before a scheduler is attached, so the scheduler can iterate over the map and assign the array of CPUs to each cgroup as a cpumask.

This patch therefore adds support for using bpf_for_each_map_elem() for BPF_MAP_TYPE_HASH_OF_MAPS. A subsequent patch will add selftests which validate its behavior.

---
 include/uapi/linux/bpf.h | 3 ++-
 kernel/bpf/hashtab.c     | 2 ++
 kernel/bpf/verifier.c    | 6 +++++-
 3 files changed, 9 insertions(+), 2 deletions(-)
include/uapi/linux/bpf.h +2 -1
index a7b5e91dd768..fc5f027c4837 100644
@@ -4909,7 +4909,8 @@ union bpf_attr {
  *
  *		BPF_MAP_TYPE_HASH, BPF_MAP_TYPE_PERCPU_HASH,
  *		BPF_MAP_TYPE_LRU_HASH, BPF_MAP_TYPE_LRU_PERCPU_HASH,
- *		BPF_MAP_TYPE_ARRAY, BPF_MAP_TYPE_PERCPU_ARRAY
+ *		BPF_MAP_TYPE_HASH_OF_MAPS, BPF_MAP_TYPE_ARRAY,
+ *		BPF_MAP_TYPE_PERCPU_ARRAY
  *
  *		long (\*callback_fn)(struct bpf_map \*map, const void \*key, void \*value, void \*ctx);
  *
kernel/bpf/hashtab.c +2 -0
index 9901efee4339..fef7b94ed389 100644
@@ -2580,6 +2580,8 @@ const struct bpf_map_ops htab_of_maps_map_ops = {
 	.map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem,
 	.map_gen_lookup = htab_of_map_gen_lookup,
 	.map_check_btf = map_check_no_btf,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_hash_elem,
 	.map_mem_usage = htab_map_mem_usage,
 	BATCH_OPS(htab),
 	.map_btf_id = &htab_map_btf_ids[0],
kernel/bpf/verifier.c +5 -1
index 086b2a14905b..ba74b3b8f181 100644
@@ -8174,10 +8174,14 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 			goto error;
 		break;
 	case BPF_MAP_TYPE_ARRAY_OF_MAPS:
-	case BPF_MAP_TYPE_HASH_OF_MAPS:
 		if (func_id != BPF_FUNC_map_lookup_elem)
 			goto error;
 		break;
+	case BPF_MAP_TYPE_HASH_OF_MAPS:
+		if (func_id != BPF_FUNC_map_lookup_elem &&
+		    func_id != BPF_FUNC_for_each_map_elem)
+			goto error;
+		break;
 	case BPF_MAP_TYPE_SOCKMAP:
 		if (func_id != BPF_FUNC_sk_redirect_map &&
 		    func_id != BPF_FUNC_sock_map_update &&
Signature · 1 line
2.40.1
#1 lore raw

PATCH 2/2 selftests/bpf: Test bpf_for_each_map_elem on BPF_MAP_TYPE_HASH_OF_MAPS

Now that we support using the bpf_for_each_map_elem() on the BPF_MAP_TYPE_HASH_OF_MAPS map type, we should add selftests that verify expected behavior.

This patch addds those selftests. Included in this is a new test_btf_map_in_map_failure.c BPF prog that can be used to verify expected map-in-map failures in the verifier.

---
 .../selftests/bpf/prog_tests/btf_map_in_map.c | 44 +++++++++++
 .../selftests/bpf/progs/test_btf_map_in_map.c | 73 ++++++++++++++++++-
 .../bpf/progs/test_btf_map_in_map_failure.c   | 39 ++++++++++
 3 files changed, 155 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/progs/test_btf_map_in_map_failure.c
tools/testing/selftests/bpf/prog_tests/btf_map_in_map.c +44 -0
index a8b53b8736f0..257b5b5a08ba 100644
@@ -4,6 +4,7 @@
 #include <test_progs.h>
 
 #include "test_btf_map_in_map.skel.h"
+#include "test_btf_map_in_map_failure.skel.h"
 
 static int duration;
 
@@ -154,6 +155,43 @@ static void test_diff_size(void)
 	test_btf_map_in_map__destroy(skel);
 }
 
+static void test_hash_iter(const char *prog_name)
+{
+	struct test_btf_map_in_map *skel;
+	struct bpf_program *prog;
+	struct bpf_link *link = NULL;
+	int err, child_pid, status;
+
+	skel = test_btf_map_in_map__open();
+	if (!ASSERT_OK_PTR(skel, "test_btf_map_in_map__open\n"))
+		return;
+
+	skel->bss->pid = getpid();
+	err = test_btf_map_in_map__load(skel);
+	if (!ASSERT_OK(err, "test_btf_map_in_map__load"))
+		goto cleanup;
+
+	prog = bpf_object__find_program_by_name(skel->obj, prog_name);
+	if (!ASSERT_OK_PTR(prog, "bpf_object__find_program_by_name"))
+		goto cleanup;
+
+	link = bpf_program__attach(prog);
+	if (!ASSERT_OK_PTR(link, "bpf_program__attach"))
+		goto cleanup;
+
+	child_pid = fork();
+	if (!ASSERT_GT(child_pid, -1, "child_pid"))
+		goto cleanup;
+	if (child_pid == 0)
+		_exit(0);
+	waitpid(child_pid, &status, 0);
+	ASSERT_OK(skel->bss->err, "post_wait_err");
+
+cleanup:
+	bpf_link__destroy(link);
+	test_btf_map_in_map__destroy(skel);
+}
+
 void test_btf_map_in_map(void)
 {
 	if (test__start_subtest("lookup_update"))
@@ -161,4 +199,10 @@ void test_btf_map_in_map(void)
 
 	if (test__start_subtest("diff_size"))
 		test_diff_size();
+
+	if (test__start_subtest("hash_iter"))
+		test_hash_iter("test_iter_hash_of_maps");
+
+	RUN_TESTS(test_btf_map_in_map);
+	RUN_TESTS(test_btf_map_in_map_failure);
 }
tools/testing/selftests/bpf/progs/test_btf_map_in_map.c +72 -1

89 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_btf_map_in_map_failure.c new file +39 -0
new file mode 100644
index 000000000000..6b7a94fe15c7
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
+
+#include <linux/types.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include <vmlinux.h>
+
+#include "bpf_misc.h"
+
+struct inner_map {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, int);
+	__type(value, int);
+} inner_map1 SEC(".maps"),
+  inner_map2 SEC(".maps");
+
+struct outer_hash {
+	__uint(type, BPF_MAP_TYPE_HASH_OF_MAPS);
+	__uint(max_entries, 2);
+	__type(key, int);
+	__array(values, struct inner_map);
+} outer_hash SEC(".maps") = {
+	.values = {
+		[0] = &inner_map2,
+		[1] = &inner_map1,
+	},
+};
+
+SEC("tp_btf/task_newtask")
+__failure
+__msg("R2 type=scalar expected=func")
+int BPF_PROG(test_iter_hash_of_maps_null_cb, struct task_struct *task, u64 clone_flags)
+{
+	/* Can't iterate over a NULL callback. */
+	bpf_for_each_map_elem(&outer_hash, NULL, NULL, 0);
+	return 0;
+}
Signature · 1 line
2.40.1
#2 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Test bpf_for_each_map_elem on BPF_MAP_TYPE_HASH_OF_MAPS

tools/testing/selftests/bpf/progs/test_btf_map_in_map.c int handle__sys_enter(void *ctx) · line 177

Quoted 12 lines · David Vernet
tools/testing/selftests/bpf/progs/test_btf_map_in_map.c +11 -0
+
+static __u64 set_invoked(struct bpf_map *map, __u64 *key, __u64 *val, struct callback_ctx *ctx)
+{
+       struct bpf_map *inner_map;
+
+       ctx->invoked = true;
+       inner_map = bpf_map_lookup_elem(map, key);
+       if (!inner_map) {
+               ctx->failed = true;
+               return 1;
+       }

This doesn't look right. 'val' is not 'u64 *'.
It probably should be 'struct bpf_map *',
so lookup shouldn't be necessary.

map_set_for_each_callback_args() just sets it to PTR_TO_MAP_VALUE. It probably should be CONST_PTR_TO_MAP.
Also for normal hash map for_each_elem 'val' is writeable. It shouldn't be in this case.
So to cleanly support iterating hash_of_maps patch 1 needs more work.

#3 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Test bpf_for_each_map_elem on BPF_MAP_TYPE_HASH_OF_MAPS

Quoted 18 lines · Alexei Starovoitov

tools/testing/selftests/bpf/progs/test_btf_map_in_map.c int handle__sys_enter(void *ctx) · line 177

Quoted 12 lines · David Vernet
tools/testing/selftests/bpf/progs/test_btf_map_in_map.c +11 -0
+
+static __u64 set_invoked(struct bpf_map *map, __u64 *key, __u64 *val, struct callback_ctx *ctx)
+{
+       struct bpf_map *inner_map;
+
+       ctx->invoked = true;
+       inner_map = bpf_map_lookup_elem(map, key);
+       if (!inner_map) {
+               ctx->failed = true;
+               return 1;
+       }

This doesn't look right. 'val' is not 'u64 *'.
It probably should be 'struct bpf_map *',
so lookup shouldn't be necessary.

Quoted 5 lines

map_set_for_each_callback_args() just sets it to PTR_TO_MAP_VALUE. It probably should be CONST_PTR_TO_MAP.
Also for normal hash map for_each_elem 'val' is writeable. It shouldn't be in this case.
So to cleanly support iterating hash_of_maps patch 1 needs more work.

Thanks for the review and pointing out these issues. This all makes sense, I'll incorporate it into v2.