[RFCv2,bpf-next,15/18] selftests/bpf: Add rbtree map tests

Message ID	20220830172759.4069786-16-davemarchevsky@fb.com (mailing list archive)
State	RFC
Delegated to:	BPF
Headers	show Return-Path: <bpf-owner@kernel.org> From: Dave Marchevsky <davemarchevsky@fb.com> To: <bpf@vger.kernel.org> CC: Alexei Starovoitov <ast@kernel.org>, Daniel Borkmann <daniel@iogearbox.net>, Andrii Nakryiko <andrii@kernel.org>, Kernel Team <kernel-team@fb.com>, Dave Marchevsky <davemarchevsky@fb.com> Subject: [RFCv2 PATCH bpf-next 15/18] selftests/bpf: Add rbtree map tests Date: Tue, 30 Aug 2022 10:27:56 -0700 Message-ID: <20220830172759.4069786-16-davemarchevsky@fb.com> In-Reply-To: <20220830172759.4069786-1-davemarchevsky@fb.com> References: <20220830172759.4069786-1-davemarchevsky@fb.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain Precedence: bulk
Series	bpf: Introduce rbtree map \| expand [RFCv2,bpf-next,00/18] bpf: Introduce rbtree map [RFCv2,bpf-next,01/18] bpf: Add verifier support for custom callback return range [RFCv2,bpf-next,02/18] bpf: Add verifier check for BPF_PTR_POISON retval and arg [RFCv2,bpf-next,03/18] bpf: Add rb_node_off to bpf_map [RFCv2,bpf-next,04/18] bpf: Add rbtree map [RFCv2,bpf-next,05/18] libbpf: Add support for private BSS map section [RFCv2,bpf-next,06/18] bpf: Add bpf_spin_lock member to rbtree [RFCv2,bpf-next,07/18] bpf: Add bpf_rbtree_{lock,unlock} helpers [RFCv2,bpf-next,08/18] bpf: Enforce spinlock hold for bpf_rbtree_{add,remove,find} [RFCv2,bpf-next,09/18] bpf: Support declarative association of lock with rbtree map [RFCv2,bpf-next,10/18] bpf: Verifier tracking of rbtree_spin_lock held [RFCv2,bpf-next,11/18] bpf: Check rbtree lock held during verification [RFCv2,bpf-next,12/18] bpf: Add OBJ_NON_OWNING_REF type flag [RFCv2,bpf-next,13/18] bpf: Add CONDITIONAL_RELEASE type flag [RFCv2,bpf-next,14/18] bpf: Introduce PTR_ITER and PTR_ITER_END type flags [RFCv2,bpf-next,15/18] selftests/bpf: Add rbtree map tests [RFCv2,bpf-next,16/18] selftests/bpf: Declarative lock definition test changes [RFCv2,bpf-next,17/18] selftests/bpf: Lock tracking test changes [RFCv2,bpf-next,18/18] selftests/bpf: Rbtree static lock verification test changes

Context	Check	Description
bpf/vmtest-bpf-next-PR	fail	merge-conflict
netdev/tree_selection	success	Clearly marked for bpf-next, async
netdev/apply	fail	Patch does not apply to bpf-next

diff --git a/tools/testing/selftests/bpf/prog_tests/rbtree_map.c b/tools/testing/selftests/bpf/prog_tests/rbtree_map.c new file mode 100644 index 000000000000..17cadcd05ee4 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/rbtree_map.c @@ -0,0 +1,164 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include <sys/syscall.h> +#include <test_progs.h> +#include "rbtree_map.skel.h" +#include "rbtree_map_fail.skel.h" +#include "rbtree_map_load_fail.skel.h" + +static size_t log_buf_sz = 1048576; /* 1 MB */ +static char obj_log_buf[1048576]; + +static struct { + const char *prog_name; + const char *expected_err_msg; +} rbtree_prog_load_fail_tests[] = { + {"rb_node__field_store", "only read is supported"}, + {"rb_node__alloc_no_add", "Unreleased reference id=2 alloc_insn=3"}, + {"rb_node__two_alloc_one_add", "Unreleased reference id=2 alloc_insn=3"}, + {"rb_node__remove_no_free", "Unreleased reference id=5 alloc_insn=28"}, + {"rb_tree__add_wrong_type", "rbtree: R2 is of type task_struct but node_data is expected"}, + {"rb_tree__conditional_release_helper_usage", + "R2 type=ptr_cond_rel_ expected=ptr_"}, +}; + +void test_rbtree_map_load_fail(void) +{ + struct rbtree_map_load_fail *skel; + + skel = rbtree_map_load_fail__open_and_load(); + if (!ASSERT_ERR_PTR(skel, "rbtree_map_load_fail__open_and_load")) + rbtree_map_load_fail__destroy(skel); +} + +static void verify_fail(const char *prog_name, const char *expected_err_msg) +{ + LIBBPF_OPTS(bpf_object_open_opts, opts); + struct rbtree_map_fail *skel; + struct bpf_program *prog; + int err; + + opts.kernel_log_buf = obj_log_buf; + opts.kernel_log_size = log_buf_sz; + opts.kernel_log_level = 1; + + skel = rbtree_map_fail__open_opts(&opts); + if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open_opts")) + 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; + + bpf_program__set_autoload(prog, true); + err = rbtree_map_fail__load(skel); + if (!ASSERT_ERR(err, "unexpected load success")) + goto cleanup; + + if (!ASSERT_OK_PTR(strstr(obj_log_buf, expected_err_msg), "expected_err_msg")) { + fprintf(stderr, "Expected err_msg: %s\n", expected_err_msg); + fprintf(stderr, "Verifier output: %s\n", obj_log_buf); + } + +cleanup: + rbtree_map_fail__destroy(skel); +} + +void test_rbtree_map_alloc_node__size_too_small(void) +{ + struct rbtree_map_fail *skel; + struct bpf_program *prog; + struct bpf_link *link; + int err; + + skel = rbtree_map_fail__open(); + if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open")) + goto cleanup; + + prog = skel->progs.alloc_node__size_too_small; + bpf_program__set_autoload(prog, true); + + err = rbtree_map_fail__load(skel); + if (!ASSERT_OK(err, "unexpected load fail")) + goto cleanup; + + link = bpf_program__attach(skel->progs.alloc_node__size_too_small); + if (!ASSERT_OK_PTR(link, "link")) + goto cleanup; + + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->size_too_small__alloc_fail, 1, "alloc_fail"); + + bpf_link__destroy(link); +cleanup: + rbtree_map_fail__destroy(skel); +} + +void test_rbtree_map_add_node__no_lock(void) +{ + struct rbtree_map_fail *skel; + struct bpf_program *prog; + struct bpf_link *link; + int err; + + skel = rbtree_map_fail__open(); + if (!ASSERT_OK_PTR(skel, "rbtree_map_fail__open")) + goto cleanup; + + prog = skel->progs.add_node__no_lock; + bpf_program__set_autoload(prog, true); + + err = rbtree_map_fail__load(skel); + if (!ASSERT_OK(err, "unexpected load fail")) + goto cleanup; + + link = bpf_program__attach(skel->progs.add_node__no_lock); + if (!ASSERT_OK_PTR(link, "link")) + goto cleanup; + + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->no_lock_add__fail, 1, "alloc_fail"); + + bpf_link__destroy(link); +cleanup: + rbtree_map_fail__destroy(skel); +} + +void test_rbtree_map_prog_load_fail(void) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(rbtree_prog_load_fail_tests); i++) { + if (!test__start_subtest(rbtree_prog_load_fail_tests[i].prog_name)) + continue; + + verify_fail(rbtree_prog_load_fail_tests[i].prog_name, + rbtree_prog_load_fail_tests[i].expected_err_msg); + } +} + +void test_rbtree_map(void) +{ + struct rbtree_map *skel; + struct bpf_link *link; + + skel = rbtree_map__open_and_load(); + if (!ASSERT_OK_PTR(skel, "rbtree_map__open_and_load")) + goto cleanup; + + link = bpf_program__attach(skel->progs.check_rbtree); + if (!ASSERT_OK_PTR(link, "link")) + goto cleanup; + + for (int i = 0; i < 100; i++) + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->calls, 100, "calls_equal"); + + bpf_link__destroy(link); +cleanup: + rbtree_map__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/rbtree_map.c b/tools/testing/selftests/bpf/progs/rbtree_map.c new file mode 100644 index 000000000000..0cd467838f6e --- /dev/null +++ b/tools/testing/selftests/bpf/progs/rbtree_map.c @@ -0,0 +1,111 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +struct node_data { + struct rb_node node; + __u32 one; + __u32 two; +}; + +struct { + __uint(type, BPF_MAP_TYPE_RBTREE); + __type(value, struct node_data); +} rbtree SEC(".maps"); + +long calls; + +static bool less(struct rb_node *a, const struct rb_node *b) +{ + struct node_data *node_a; + struct node_data *node_b; + + node_a = container_of(a, struct node_data, node); + node_b = container_of(b, struct node_data, node); + + return node_a->one < node_b->one; +} + +// Key = node_datq +static int cmp(const void *key, const struct rb_node *b) +{ + struct node_data *node_a; + struct node_data *node_b; + + node_a = container_of(key, struct node_data, node); + node_b = container_of(b, struct node_data, node); + + return node_b->one - node_a->one; +} + +// Key = just node_data.one +static int cmp2(const void *key, const struct rb_node *b) +{ + __u32 one; + struct node_data *node_b; + + one = *(__u32 *)key; + node_b = container_of(b, struct node_data, node); + + return node_b->one - one; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int check_rbtree(void *ctx) +{ + struct node_data *node, *found, *ret; + struct node_data popped; + struct node_data search; + __u32 search2; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + + node->one = calls; + node->two = 6; + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + ret = (struct node_data *)bpf_rbtree_add(&rbtree, node, less); + if (!ret) { + bpf_rbtree_free_node(&rbtree, node); + goto unlock_ret; + } + + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + search.one = calls; + found = (struct node_data *)bpf_rbtree_find(&rbtree, &search, cmp); + if (!found) + goto unlock_ret; + + int node_ct = 0; + struct node_data *iter = (struct node_data *)bpf_rbtree_first(&rbtree); + + while (iter) { + node_ct++; + iter = (struct node_data *)bpf_rbtree_next(&rbtree, iter); + } + + ret = (struct node_data *)bpf_rbtree_remove(&rbtree, found); + if (!ret) + goto unlock_ret; + + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + + bpf_rbtree_free_node(&rbtree, ret); + + __sync_fetch_and_add(&calls, 1); + return 0; + +unlock_ret: + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +char _license[] SEC("license") = "GPL"; diff --git a/tools/testing/selftests/bpf/progs/rbtree_map_fail.c b/tools/testing/selftests/bpf/progs/rbtree_map_fail.c new file mode 100644 index 000000000000..287c8db080d8 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/rbtree_map_fail.c @@ -0,0 +1,236 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +struct node_data { + struct rb_node node; + __u32 one; + __u32 two; +}; + +struct { + __uint(type, BPF_MAP_TYPE_RBTREE); + __type(value, struct node_data); +} rbtree SEC(".maps"); + +long calls; + +static bool less(struct rb_node *a, const struct rb_node *b) +{ + struct node_data *node_a; + struct node_data *node_b; + + node_a = container_of(a, struct node_data, node); + node_b = container_of(b, struct node_data, node); + + return node_a->one < node_b->one; +} + +// Key = node_datq +static int cmp(const void *key, const struct rb_node *b) +{ + struct node_data *node_a; + struct node_data *node_b; + + node_a = container_of(key, struct node_data, node); + node_b = container_of(b, struct node_data, node); + + return node_b->one - node_a->one; +} + +long size_too_small__alloc_fail; + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int alloc_node__size_too_small(void *ctx) +{ + struct node_data *node, *ret; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(char)); + if (!node) { + size_too_small__alloc_fail++; + return 0; + } + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + /* will never execute, alloc_node should fail */ + node->one = 1; + ret = bpf_rbtree_add(&rbtree, node, less); + if (!ret) { + bpf_rbtree_free_node(&rbtree, node); + goto unlock_ret; + } + +unlock_ret: + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +long no_lock_add__fail; + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int add_node__no_lock(void *ctx) +{ + struct node_data *node, *ret; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + + node->one = 1; + ret = bpf_rbtree_add(&rbtree, node, less); + if (!ret) { + no_lock_add__fail++; + /* will always execute, rbtree_add should fail + * because no lock held + */ + bpf_rbtree_free_node(&rbtree, node); + } + +unlock_ret: + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_node__field_store(void *ctx) +{ + struct node_data *node; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + + /* Only rbtree_map helpers can modify rb_node field */ + node->node.rb_left = NULL; + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_node__alloc_no_add(void *ctx) +{ + struct node_data *node; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + /* The node alloc'd above is never added to the rbtree. It must be + * added or free'd before prog terminates. + */ + + node->one = 42; + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_node__two_alloc_one_add(void *ctx) +{ + struct node_data *node, *ret; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + node->one = 1; + /* The node alloc'd above is never added to the rbtree. It must be + * added or free'd before prog terminates. + */ + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + node->one = 42; + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + ret = bpf_rbtree_add(&rbtree, node, less); + if (!ret) { + bpf_rbtree_free_node(&rbtree, node); + goto unlock_ret; + } + +unlock_ret: + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_node__remove_no_free(void *ctx) +{ + struct node_data *node, *ret; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + node->one = 42; + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + ret = bpf_rbtree_add(&rbtree, node, less); + if (!ret) { + bpf_rbtree_free_node(&rbtree, node); + goto unlock_ret; + } + + ret = bpf_rbtree_remove(&rbtree, ret); + if (!ret) + goto unlock_ret; + /* At this point we've successfully acquired a reference from + * bpf_rbtree_remove. It must be released via rbtree_add or + * rbtree_free_node before prog terminates. + */ + +unlock_ret: + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_tree__add_wrong_type(void *ctx) +{ + /* Can't add a task_struct to rbtree + */ + struct task_struct *task; + struct node_data *ret; + + task = bpf_get_current_task_btf(); + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + ret = bpf_rbtree_add(&rbtree, task, less); + /* Verifier should fail at bpf_rbtree_add, so don't bother handling + * failure. + */ + + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +SEC("?fentry/" SYS_PREFIX "sys_getpgid") +int rb_tree__conditional_release_helper_usage(void *ctx) +{ + struct node_data *node, *ret; + + node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data)); + if (!node) + return 0; + node->one = 42; + + bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree)); + + ret = bpf_rbtree_add(&rbtree, node, less); + /* Verifier should fail when trying to use CONDITIONAL_RELEASE + * type in a helper + */ + bpf_rbtree_free_node(&rbtree, node); + if (!ret) { + bpf_rbtree_free_node(&rbtree, node); + goto unlock_ret; + } + +unlock_ret: + bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree)); + return 0; +} + +char _license[] SEC("license") = "GPL"; diff --git a/tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c b/tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c new file mode 100644 index 000000000000..036558eedd66 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/rbtree_map_load_fail.c @@ -0,0 +1,24 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> + +struct node_data_no_rb_node { + __u64 one; + __u64 two; + __u64 three; + __u64 four; + __u64 five; + __u64 six; + __u64 seven; +}; + +/* Should fail because value struct has no rb_node + */ +struct { + __uint(type, BPF_MAP_TYPE_RBTREE); + __type(value, struct node_data_no_rb_node); +} rbtree_fail_no_rb_node SEC(".maps"); + +char _license[] SEC("license") = "GPL";

[RFCv2,bpf-next,15/18] selftests/bpf: Add rbtree map tests

Checks

Commit Message

Patch