* [PATCH linux-6.12.y 1/2] selftests/bpf: Add a test for arena range tree algorithm
@ 2025-07-15 22:27 Yifei Liu
0 siblings, 0 replies; 3+ messages in thread
From: Yifei Liu @ 2025-07-15 22:27 UTC (permalink / raw)
To: yonghong.song, ast; +Cc: yifei.l.liu, bpf, stable
From: Alexei Starovoitov <ast@kernel.org>
Add a test that verifies specific behavior of arena range tree
algorithm and adjust existing big_alloc1 test due to use
of global data in arena.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Link: https://lore.kernel.org/bpf/20241108025616.17625-3-alexei.starovoitov@gmail.com
(cherry picked from commit e58358afa84e8e271a296459d35d1715c7572013)
[Yifei: This commit fixes the failure of verifier_arena_large test over 64k page size kernels.
This commit also introduce some new tests targeting the new feature, arena range tree algorithm,
which is not in linux-6.12.y, I just comment out the test headers so that it would not be run here.
If this feature is introduced later, we can just uncomment those two lines.]
Signed-off-by: Yifei Liu <yifei.l.liu@oracle.com>
---
.../bpf/progs/verifier_arena_large.c | 110 +++++++++++++++++-
1 file changed, 108 insertions(+), 2 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/verifier_arena_large.c b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
index 6065f862d964..f318675814c6 100644
--- a/tools/testing/selftests/bpf/progs/verifier_arena_large.c
+++ b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
@@ -29,12 +29,12 @@ int big_alloc1(void *ctx)
if (!page1)
return 1;
*page1 = 1;
- page2 = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE,
+ page2 = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE * 2,
1, NUMA_NO_NODE, 0);
if (!page2)
return 2;
*page2 = 2;
- no_page = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE,
+ no_page = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE,
1, NUMA_NO_NODE, 0);
if (no_page)
return 3;
@@ -66,4 +66,110 @@ int big_alloc1(void *ctx)
#endif
return 0;
}
+
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
+#define PAGE_CNT 100
+__u8 __arena * __arena page[PAGE_CNT]; /* occupies the first page */
+__u8 __arena *base;
+
+/*
+ * Check that arena's range_tree algorithm allocates pages sequentially
+ * on the first pass and then fills in all gaps on the second pass.
+ */
+__noinline int alloc_pages(int page_cnt, int pages_atonce, bool first_pass,
+ int max_idx, int step)
+{
+ __u8 __arena *pg;
+ int i, pg_idx;
+
+ for (i = 0; i < page_cnt; i++) {
+ pg = bpf_arena_alloc_pages(&arena, NULL, pages_atonce,
+ NUMA_NO_NODE, 0);
+ if (!pg)
+ return step;
+ pg_idx = (pg - base) / PAGE_SIZE;
+ if (first_pass) {
+ /* Pages must be allocated sequentially */
+ if (pg_idx != i)
+ return step + 100;
+ } else {
+ /* Allocator must fill into gaps */
+ if (pg_idx >= max_idx || (pg_idx & 1))
+ return step + 200;
+ }
+ *pg = pg_idx;
+ page[pg_idx] = pg;
+ cond_break;
+ }
+ return 0;
+}
+
+//SEC("syscall")
+//__success __retval(0)
+int big_alloc2(void *ctx)
+{
+ __u8 __arena *pg;
+ int i, err;
+
+ base = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
+ if (!base)
+ return 1;
+ bpf_arena_free_pages(&arena, (void __arena *)base, 1);
+
+ err = alloc_pages(PAGE_CNT, 1, true, PAGE_CNT, 2);
+ if (err)
+ return err;
+
+ /* Clear all even pages */
+ for (i = 0; i < PAGE_CNT; i += 2) {
+ pg = page[i];
+ if (*pg != i)
+ return 3;
+ bpf_arena_free_pages(&arena, (void __arena *)pg, 1);
+ page[i] = NULL;
+ cond_break;
+ }
+
+ /* Allocate into freed gaps */
+ err = alloc_pages(PAGE_CNT / 2, 1, false, PAGE_CNT, 4);
+ if (err)
+ return err;
+
+ /* Free pairs of pages */
+ for (i = 0; i < PAGE_CNT; i += 4) {
+ pg = page[i];
+ if (*pg != i)
+ return 5;
+ bpf_arena_free_pages(&arena, (void __arena *)pg, 2);
+ page[i] = NULL;
+ page[i + 1] = NULL;
+ cond_break;
+ }
+
+ /* Allocate 2 pages at a time into freed gaps */
+ err = alloc_pages(PAGE_CNT / 4, 2, false, PAGE_CNT, 6);
+ if (err)
+ return err;
+
+ /* Check pages without freeing */
+ for (i = 0; i < PAGE_CNT; i += 2) {
+ pg = page[i];
+ if (*pg != i)
+ return 7;
+ cond_break;
+ }
+
+ pg = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
+
+ if (!pg)
+ return 8;
+ /*
+ * The first PAGE_CNT pages are occupied. The new page
+ * must be above.
+ */
+ if ((pg - base) / PAGE_SIZE < PAGE_CNT)
+ return 9;
+ return 0;
+}
+#endif
char _license[] SEC("license") = "GPL";
--
2.46.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH linux-6.12.y 1/2] selftests/bpf: Add a test for arena range tree algorithm
@ 2025-08-08 23:19 Yifei Liu
2025-08-08 23:19 ` [PATCH linux-6.12.y 2/2] selftests/bpf: Fix build error with llvm 19 Yifei Liu
0 siblings, 1 reply; 3+ messages in thread
From: Yifei Liu @ 2025-08-08 23:19 UTC (permalink / raw)
To: stable, ast; +Cc: yifei.l.liu, bpf
From: Alexei Starovoitov <ast@kernel.org>
[ Upstream commit e58358afa84e8e271a296459d35d1715c7572013 ]
Add a test that verifies specific behavior of arena range tree
algorithm and adjust existing big_alloc1 test due to use
of global data in arena.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Link: https://lore.kernel.org/bpf/20241108025616.17625-3-alexei.starovoitov@gmail.com
[Yifei: This commit fixes the failure of verifier_arena_large test over 64k page size kernels.
This commit also introduce some new tests targeting the new feature, arena range tree algorithm,
which is not in linux-6.12.y, I just comment out the test headers so that it would not be run here.
If this feature is introduced later, we can just uncomment those two lines.]
Signed-off-by: Yifei Liu <yifei.l.liu@oracle.com>
---
.../bpf/progs/verifier_arena_large.c | 110 +++++++++++++++++-
1 file changed, 108 insertions(+), 2 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/verifier_arena_large.c b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
index 6065f862d964..f318675814c6 100644
--- a/tools/testing/selftests/bpf/progs/verifier_arena_large.c
+++ b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
@@ -29,12 +29,12 @@ int big_alloc1(void *ctx)
if (!page1)
return 1;
*page1 = 1;
- page2 = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE,
+ page2 = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE * 2,
1, NUMA_NO_NODE, 0);
if (!page2)
return 2;
*page2 = 2;
- no_page = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE,
+ no_page = bpf_arena_alloc_pages(&arena, base + ARENA_SIZE - PAGE_SIZE,
1, NUMA_NO_NODE, 0);
if (no_page)
return 3;
@@ -66,4 +66,110 @@ int big_alloc1(void *ctx)
#endif
return 0;
}
+
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
+#define PAGE_CNT 100
+__u8 __arena * __arena page[PAGE_CNT]; /* occupies the first page */
+__u8 __arena *base;
+
+/*
+ * Check that arena's range_tree algorithm allocates pages sequentially
+ * on the first pass and then fills in all gaps on the second pass.
+ */
+__noinline int alloc_pages(int page_cnt, int pages_atonce, bool first_pass,
+ int max_idx, int step)
+{
+ __u8 __arena *pg;
+ int i, pg_idx;
+
+ for (i = 0; i < page_cnt; i++) {
+ pg = bpf_arena_alloc_pages(&arena, NULL, pages_atonce,
+ NUMA_NO_NODE, 0);
+ if (!pg)
+ return step;
+ pg_idx = (pg - base) / PAGE_SIZE;
+ if (first_pass) {
+ /* Pages must be allocated sequentially */
+ if (pg_idx != i)
+ return step + 100;
+ } else {
+ /* Allocator must fill into gaps */
+ if (pg_idx >= max_idx || (pg_idx & 1))
+ return step + 200;
+ }
+ *pg = pg_idx;
+ page[pg_idx] = pg;
+ cond_break;
+ }
+ return 0;
+}
+
+//SEC("syscall")
+//__success __retval(0)
+int big_alloc2(void *ctx)
+{
+ __u8 __arena *pg;
+ int i, err;
+
+ base = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
+ if (!base)
+ return 1;
+ bpf_arena_free_pages(&arena, (void __arena *)base, 1);
+
+ err = alloc_pages(PAGE_CNT, 1, true, PAGE_CNT, 2);
+ if (err)
+ return err;
+
+ /* Clear all even pages */
+ for (i = 0; i < PAGE_CNT; i += 2) {
+ pg = page[i];
+ if (*pg != i)
+ return 3;
+ bpf_arena_free_pages(&arena, (void __arena *)pg, 1);
+ page[i] = NULL;
+ cond_break;
+ }
+
+ /* Allocate into freed gaps */
+ err = alloc_pages(PAGE_CNT / 2, 1, false, PAGE_CNT, 4);
+ if (err)
+ return err;
+
+ /* Free pairs of pages */
+ for (i = 0; i < PAGE_CNT; i += 4) {
+ pg = page[i];
+ if (*pg != i)
+ return 5;
+ bpf_arena_free_pages(&arena, (void __arena *)pg, 2);
+ page[i] = NULL;
+ page[i + 1] = NULL;
+ cond_break;
+ }
+
+ /* Allocate 2 pages at a time into freed gaps */
+ err = alloc_pages(PAGE_CNT / 4, 2, false, PAGE_CNT, 6);
+ if (err)
+ return err;
+
+ /* Check pages without freeing */
+ for (i = 0; i < PAGE_CNT; i += 2) {
+ pg = page[i];
+ if (*pg != i)
+ return 7;
+ cond_break;
+ }
+
+ pg = bpf_arena_alloc_pages(&arena, NULL, 1, NUMA_NO_NODE, 0);
+
+ if (!pg)
+ return 8;
+ /*
+ * The first PAGE_CNT pages are occupied. The new page
+ * must be above.
+ */
+ if ((pg - base) / PAGE_SIZE < PAGE_CNT)
+ return 9;
+ return 0;
+}
+#endif
char _license[] SEC("license") = "GPL";
--
2.46.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH linux-6.12.y 2/2] selftests/bpf: Fix build error with llvm 19
2025-08-08 23:19 [PATCH linux-6.12.y 1/2] selftests/bpf: Add a test for arena range tree algorithm Yifei Liu
@ 2025-08-08 23:19 ` Yifei Liu
0 siblings, 0 replies; 3+ messages in thread
From: Yifei Liu @ 2025-08-08 23:19 UTC (permalink / raw)
To: stable, ast; +Cc: yifei.l.liu, bpf
From: Alexei Starovoitov <ast@kernel.org>
[ Upstream commit 608e99f7869e3a6e028c7cba14a896c7797e8746 ]
llvm 19 fails to compile arena self test:
CLNG-BPF [test_progs] verifier_arena_large.bpf.o
progs/verifier_arena_large.c:90:24: error: unsupported signed division, please convert to unsigned div/mod.
90 | pg_idx = (pg - base) / PAGE_SIZE;
Though llvm <= 18 and llvm >= 20 don't have this issue,
fix the test to avoid the build error.
Reported-by: Jiri Olsa <olsajiri@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
[Yifei: This fix is necessary to make the selfttest build with llvm19 if
commit e58358afa84e ("selftests/bpf: Add a test for arena range tree algorithm") is backported]
Signed-off-by: Yifei Liu <yifei.l.liu@oracle.com>
---
tools/testing/selftests/bpf/progs/verifier_arena_large.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/tools/testing/selftests/bpf/progs/verifier_arena_large.c b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
index f318675814c6..758b09a5eb88 100644
--- a/tools/testing/selftests/bpf/progs/verifier_arena_large.c
+++ b/tools/testing/selftests/bpf/progs/verifier_arena_large.c
@@ -87,7 +87,7 @@ __noinline int alloc_pages(int page_cnt, int pages_atonce, bool first_pass,
NUMA_NO_NODE, 0);
if (!pg)
return step;
- pg_idx = (pg - base) / PAGE_SIZE;
+ pg_idx = (unsigned long) (pg - base) / PAGE_SIZE;
if (first_pass) {
/* Pages must be allocated sequentially */
if (pg_idx != i)
--
2.46.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2025-08-08 23:20 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-08-08 23:19 [PATCH linux-6.12.y 1/2] selftests/bpf: Add a test for arena range tree algorithm Yifei Liu
2025-08-08 23:19 ` [PATCH linux-6.12.y 2/2] selftests/bpf: Fix build error with llvm 19 Yifei Liu
-- strict thread matches above, loose matches on Subject: below --
2025-07-15 22:27 [PATCH linux-6.12.y 1/2] selftests/bpf: Add a test for arena range tree algorithm Yifei Liu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).