Skip to contentSkip to conversation

Allow struct_ops maps with a large number of programs

PATCH Applied Kui-Feng Lee 3 participants 6 messages Feb 24, 2024 – Mar 4, 2024

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

v4 cover Allow struct_ops maps with a large number of programs

The BPF struct_ops previously only allowed for one page to be used for the trampolines of all links in a map. However, we have recently run out of space due to the large number of BPF program links. By allocating additional pages when we exhaust an existing page, we can accommodate more links in a single map.

The variable st_map->image has been changed to st_map->image_pages, and its type has been changed to an array of pointers to buffers of PAGE_SIZE. Additional pages are allocated when all existing pages are exhausted.

The test case loads a struct_ops maps having 40 programs. Their trampolines takes about 6.6k+ bytes over 1.5 pages on x86.

---
Major differences from v3:

- Refactor buffer allocations to bpf_struct_ops_tramp_buf_alloc() and bpf_struct_ops_tramp_buf_free().

Major differences from v2:

- Move image buffer allocation to bpf_struct_ops_prepare_trampoline().

Major differences from v1:

- Always free pages if failing to update.

- Allocate 8 pages at most.

v3: https://lore.kernel.org/all/[email protected]/
v2: https://lore.kernel.org/all/[email protected]/
v1: https://lore.kernel.org/all/[email protected]/

Kui-Feng Lee (3):
bpf, net: validate struct_ops when updating value.
bpf: struct_ops supports more than one page for trampolines. selftests/bpf: Test struct_ops maps with a large number of program
links.

 include/linux/bpf.h                           |   4 +-
 kernel/bpf/bpf_struct_ops.c                   | 139 ++++++++++++------
 net/bpf/bpf_dummy_struct_ops.c                |  12 +-
 net/ipv4/tcp_cong.c                           |   6 +-
 .../selftests/bpf/bpf_testmod/bpf_testmod.h   |  44 ++++++
 .../prog_tests/test_struct_ops_multi_pages.c  |  30 ++++
 .../bpf/progs/struct_ops_multi_pages.c        | 102 +++++++++++++
 7 files changed, 280 insertions(+), 57 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/test_struct_ops_multi_pages.c
 create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_multi_pages.c
Signature · 1 line
2.34.1
#1 lore raw

PATCH v4 1/3 bpf, net: validate struct_ops when updating value.

Perform all validations when updating values of struct_ops maps. Doing validation in st_ops->reg() and st_ops->update() is not necessary anymore. However, tcp_register_congestion_control() has been called in various places. It still needs to do validations.

---
 kernel/bpf/bpf_struct_ops.c | 11 ++++++-----
 net/ipv4/tcp_cong.c         |  6 +-----
 2 files changed, 7 insertions(+), 10 deletions(-)
kernel/bpf/bpf_struct_ops.c +6 -5
index a6019087b467..07e554c191d1 100644
@@ -672,13 +672,14 @@ static long bpf_struct_ops_map_update_elem(struct bpf_map *map, void *key,
 		*(unsigned long *)(udata + moff) = prog->aux->id;
 	}
 
+	if (st_ops->validate) {
+		err = st_ops->validate(kdata);
+		if (err)
+			goto reset_unlock;
+	}
+
 	if (st_map->map.map_flags & BPF_F_LINK) {
 		err = 0;
-		if (st_ops->validate) {
-			err = st_ops->validate(kdata);
-			if (err)
-				goto reset_unlock;
-		}
 		arch_protect_bpf_trampoline(st_map->image, PAGE_SIZE);
 		/* Let bpf_link handle registration & unregistration.
 		 *
net/ipv4/tcp_cong.c +1 -5
index 1b34050a7538..28ffcfbeef14 100644
@@ -146,11 +146,7 @@ EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control);
 int tcp_update_congestion_control(struct tcp_congestion_ops *ca, struct tcp_congestion_ops *old_ca)
 {
 	struct tcp_congestion_ops *existing;
-	int ret;
-
-	ret = tcp_validate_congestion_control(ca);
-	if (ret)
-		return ret;
+	int ret = 0;
 
 	ca->key = jhash(ca->name, sizeof(ca->name), strlen(ca->name));
 
Signature · 1 line
2.34.1
#2 lore raw

PATCH v4 2/3 bpf: struct_ops supports more than one page for trampolines.

In reply to Kui-Feng Lee

The BPF struct_ops previously only allowed for one page to be used for the trampolines of all links in a map. However, we have recently run out of space due to the large number of BPF program links. By allocating additional pages when we exhaust an existing page, we can accommodate more links in a single map.

The variable st_map->image has been changed to st_map->image_pages, and its type has been changed to an array of pointers to buffers of PAGE_SIZE. Every struct_ops map can have MAX_IMAGE_PAGES (8) pages for trampolines at most.

---
 include/linux/bpf.h            |   4 +-
 kernel/bpf/bpf_struct_ops.c    | 128 +++++++++++++++++++++++----------
 net/bpf/bpf_dummy_struct_ops.c |  12 ++--
 3 files changed, 97 insertions(+), 47 deletions(-)
include/linux/bpf.h +3 -1
index 814dc913a968..f8d9ff56057c 100644
@@ -1763,7 +1763,9 @@ int bpf_struct_ops_prepare_trampoline(struct bpf_tramp_links *tlinks,
 				      struct bpf_tramp_link *link,
 				      const struct btf_func_model *model,
 				      void *stub_func,
-				      void *image, void *image_end);
+				      void **image, u32 *image_off,
+				      bool allow_alloc);
+void bpf_struct_ops_tramp_buf_free(void *image);
 static inline bool bpf_try_module_get(const void *data, struct module *owner)
 {
 	if (owner == BPF_MODULE_OWNER)
kernel/bpf/bpf_struct_ops.c +90 -38

239 lines not on this page · raw message

net/bpf/bpf_dummy_struct_ops.c +4 -8
index 02de71719aed..da73905eff4a 100644
@@ -91,6 +91,7 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
 	struct bpf_tramp_link *link = NULL;
 	void *image = NULL;
 	unsigned int op_idx;
+	u32 image_off = 0;
 	int prog_ret;
 	s32 type_id;
 	int err;
@@ -114,12 +115,6 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
 		goto out;
 	}
 
-	image = arch_alloc_bpf_trampoline(PAGE_SIZE);
-	if (!image) {
-		err = -ENOMEM;
-		goto out;
-	}
-
 	link = kzalloc(sizeof(*link), GFP_USER);
 	if (!link) {
 		err = -ENOMEM;
@@ -133,7 +128,8 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
 	err = bpf_struct_ops_prepare_trampoline(tlinks, link,
 						&st_ops->func_models[op_idx],
 						&dummy_ops_test_ret_function,
-						image, image + PAGE_SIZE);
+						&image, &image_off,
+						true);
 	if (err < 0)
 		goto out;
 
@@ -147,7 +143,7 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
 		err = -EFAULT;
 out:
 	kfree(args);
-	arch_free_bpf_trampoline(image, PAGE_SIZE);
+	bpf_struct_ops_tramp_buf_free(image);
 	if (link)
 		bpf_link_put(&link->link);
 	kfree(tlinks);
Signature · 1 line
2.34.1
#4 lore raw

PATCH v4 3/3 selftests/bpf: Test struct_ops maps with a large number of program links.

In reply to Kui-Feng Lee

Create and load a struct_ops map with a large number of programs to generate trampolines taking a size over multiple pages. The map includes 40 programs. Their trampolines takes 6.6k+, more than 1.5 pages, on x86.

---
 .../selftests/bpf/bpf_testmod/bpf_testmod.h   |  44 ++++++++
 .../prog_tests/test_struct_ops_multi_pages.c  |  30 ++++++
 .../bpf/progs/struct_ops_multi_pages.c        | 102 ++++++++++++++++++
 3 files changed, 176 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/test_struct_ops_multi_pages.c
 create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_multi_pages.c
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.h +44 -0
index c3b0cf788f9f..3e6481b2a50a 100644
@@ -35,6 +35,50 @@ struct bpf_testmod_ops {
 	void (*test_2)(int a, int b);
 	/* Used to test nullable arguments. */
 	int (*test_maybe_null)(int dummy, struct task_struct *task);
+
+	/* The following pointers are used to test the maps having multiple
+	 * pages of trampolines.
+	 */
+	int (*tramp_1)(int value);
+	int (*tramp_2)(int value);
+	int (*tramp_3)(int value);
+	int (*tramp_4)(int value);
+	int (*tramp_5)(int value);
+	int (*tramp_6)(int value);
+	int (*tramp_7)(int value);
+	int (*tramp_8)(int value);
+	int (*tramp_9)(int value);
+	int (*tramp_10)(int value);
+	int (*tramp_11)(int value);
+	int (*tramp_12)(int value);
+	int (*tramp_13)(int value);
+	int (*tramp_14)(int value);
+	int (*tramp_15)(int value);
+	int (*tramp_16)(int value);
+	int (*tramp_17)(int value);
+	int (*tramp_18)(int value);
+	int (*tramp_19)(int value);
+	int (*tramp_20)(int value);
+	int (*tramp_21)(int value);
+	int (*tramp_22)(int value);
+	int (*tramp_23)(int value);
+	int (*tramp_24)(int value);
+	int (*tramp_25)(int value);
+	int (*tramp_26)(int value);
+	int (*tramp_27)(int value);
+	int (*tramp_28)(int value);
+	int (*tramp_29)(int value);
+	int (*tramp_30)(int value);
+	int (*tramp_31)(int value);
+	int (*tramp_32)(int value);
+	int (*tramp_33)(int value);
+	int (*tramp_34)(int value);
+	int (*tramp_35)(int value);
+	int (*tramp_36)(int value);
+	int (*tramp_37)(int value);
+	int (*tramp_38)(int value);
+	int (*tramp_39)(int value);
+	int (*tramp_40)(int value);
 };
 
 #endif /* _BPF_TESTMOD_H */
tools/testing/selftests/bpf/prog_tests/test_struct_ops_multi_pages.c new file +30 -0
new file mode 100644
index 000000000000..645d32b5160c
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
+#include <test_progs.h>
+
+#include "struct_ops_multi_pages.skel.h"
+
+static void do_struct_ops_multi_pages(void)
+{
+	struct struct_ops_multi_pages *skel;
+	struct bpf_link *link;
+
+	/* The size of all trampolines of skel->maps.multi_pages should be
+	 * over 1 page (at least for x86).
+	 */
+	skel = struct_ops_multi_pages__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "struct_ops_multi_pages_open_and_load"))
+		return;
+
+	link = bpf_map__attach_struct_ops(skel->maps.multi_pages);
+	ASSERT_OK_PTR(link, "attach_multi_pages");
+
+	bpf_link__destroy(link);
+	struct_ops_multi_pages__destroy(skel);
+}
+
+void test_struct_ops_multi_pages(void)
+{
+	if (test__start_subtest("multi_pages"))
+		do_struct_ops_multi_pages();
+}
tools/testing/selftests/bpf/progs/struct_ops_multi_pages.c new file +102 -0

102 lines not on this page · raw message

Signature · 1 line
2.34.1
#5 lore raw
In reply to Kui-Feng Lee
This series was applied to bpf/bpf-next.git (master) by Martin KaFai Lau <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Martin KaFai Lau <[email protected]>:

Quoted 6 lines · On Sat, 24 Feb 2024 14:34:15 -0800 you wrote:

The BPF struct_ops previously only allowed for one page to be used for the trampolines of all links in a map. However, we have recently run out of space due to the large number of BPF program links. By allocating additional pages when we exhaust an existing page, we can accommodate more links in a single map.

Quoted 6 lines

The variable st_map->image has been changed to st_map->image_pages, and its type has been changed to an array of pointers to buffers of PAGE_SIZE. Additional pages are allocated when all existing pages are exhausted.

[...]

Here is the summary with links:
- [bpf-next,v4,1/3] bpf, net: validate struct_ops when updating value.

    https://git.kernel.org/bpf/bpf-next/c/73e4f9e615d7
  - [bpf-next,v4,2/3] bpf: struct_ops supports more than one page for trampolines.
    https://git.kernel.org/bpf/bpf-next/c/187e2af05abe
  - [bpf-next,v4,3/3] selftests/bpf: Test struct_ops maps with a large number of program links.
    https://git.kernel.org/bpf/bpf-next/c/93bc28d859e5

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
reviewer Applied
#3 lore raw

Re: [PATCH bpf-next v4 2/3] bpf: struct_ops supports more than one page for trampolines.

In reply to Kui-Feng Lee

kernel/bpf/bpf_struct_ops.c static bool is_valid_value_type(struct btf *btf, s32 value_id, · line 140

Quoted 4 lines · Kui-Feng Lee
kernel/bpf/bpf_struct_ops.c +4 -0
+void bpf_struct_ops_tramp_buf_free(void *image)
+{
+	arch_free_bpf_trampoline(image, PAGE_SIZE);
+	if (image)

Moved the "arch_free_bpf_trampoline(image, PAGE_SIZE);" after the image NULL test. I think it was an overlook at the bpf_dummy_struct_ops.c. The exisiting __bpf_struct_ops_map_free(image, PAGE_SIZE) had been testing NULL before free also.

Quoted 65 lines
kernel/bpf/bpf_struct_ops.c +33 -5
+		bpf_jit_uncharge_modmem(PAGE_SIZE);
+}
+
  #define MAYBE_NULL_SUFFIX "__nullable"
  #define MAX_STUB_NAME 128
@@ -461,6 +486,15 @@ static void bpf_struct_ops_map_put_progs(struct bpf_struct_ops_map *st_map)
  	}
  }
 
+static void bpf_struct_ops_map_free_image(struct bpf_struct_ops_map *st_map)
+{
+	int i;
+
+	for (i = 0; i < st_map->image_pages_cnt; i++)
+		bpf_struct_ops_tramp_buf_free(st_map->image_pages[i]);
+	st_map->image_pages_cnt = 0;
+}
+
  static int check_zero_holes(const struct btf *btf, const struct btf_type *t, void *data)
  {
  	const struct btf_member *member;
@@ -503,12 +537,21 @@ const struct bpf_link_ops bpf_struct_ops_link_lops = {
  	.dealloc = bpf_struct_ops_link_dealloc,
  };
 
+/* *image should be NULL and allow_alloc should be true if a caller wants
+ * this function to allocate a image buffer for it. Otherwise, this
+ * function allocate a new image buffer only if allow_alloc is true and the
+ * size of the trampoline is larger than the space left in the current
+ * image buffer.
+ */
  int bpf_struct_ops_prepare_trampoline(struct bpf_tramp_links *tlinks,
  				      struct bpf_tramp_link *link,
  				      const struct btf_func_model *model,
-				      void *stub_func, void *image, void *image_end)
+				      void *stub_func,
+				      void **_image, u32 *image_off,
+				      bool allow_alloc)
  {
  	u32 flags = BPF_TRAMP_F_INDIRECT;
+	void *image = *_image;
  	int size;
 
  	tlinks[BPF_TRAMP_FENTRY].links[0] = link;
@@ -518,14 +561,30 @@ int bpf_struct_ops_prepare_trampoline(struct bpf_tramp_links *tlinks,
  		flags |= BPF_TRAMP_F_RET_FENTRY_RET;
 
  	size = arch_bpf_trampoline_size(model, flags, tlinks, NULL);
-	if (size < 0)
+	if (size <= 0)
  		return size;
-	if (size > (unsigned long)image_end - (unsigned long)image)
-		return -E2BIG;
-	return arch_prepare_bpf_trampoline(NULL, image, image_end,
+
+	/* Allocate image buffer if necessary */
+	if (!image || size > PAGE_SIZE - *image_off) {
+		if (!allow_alloc)
+			return -E2BIG;
+
+		image = bpf_struct_ops_tramp_buf_alloc();
+		if (IS_ERR(image))
+			return PTR_ERR(image);
+		*_image = image;

kernel/bpf/bpf_struct_ops.c int bpf_struct_ops_prepare_trampoline(struct bpf_tramp_links *tlinks, · line 584

Quoted 10 lines
kernel/bpf/bpf_struct_ops.c +8 -1
+		*image_off = 0;
+	}
+
+	size = arch_prepare_bpf_trampoline(NULL, image + *image_off,
+					   image + PAGE_SIZE,
  					   model, flags, tlinks, stub_func);
-}
+	if (size > 0)
+		*image_off += size;
+	/* The caller should free the allocated memory even if size < 0 */

I massage the logic a little such that the caller does not need to free the new unused page when this function errored out. I kept both the "*_image" and "*image_off" param unchanged on the error case.

Applied. Thanks.

[ ... ]

Quoted 12 lines
kernel/bpf/bpf_struct_ops.c +1 -4
@@ -781,10 +850,7 @@ static void __bpf_struct_ops_map_free(struct bpf_map *map)
  	if (st_map->links)
  		bpf_struct_ops_map_put_progs(st_map);
  	bpf_map_area_free(st_map->links);
-	if (st_map->image) {
-		arch_free_bpf_trampoline(st_map->image, PAGE_SIZE);
-		bpf_jit_uncharge_modmem(PAGE_SIZE);
-	}
+	bpf_struct_ops_map_free_image(st_map);
  	bpf_map_area_free(st_map->uvalue);
  	bpf_map_area_free(st_map);
  }

[ ... ]

Quoted 44 lines
net/bpf/bpf_dummy_struct_ops.c +4 -8
index 02de71719aed..da73905eff4a 100644
@@ -91,6 +91,7 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
  	struct bpf_tramp_link *link = NULL;
  	void *image = NULL;
  	unsigned int op_idx;
+	u32 image_off = 0;
  	int prog_ret;
  	s32 type_id;
  	int err;
@@ -114,12 +115,6 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
  		goto out;
  	}
 
-	image = arch_alloc_bpf_trampoline(PAGE_SIZE);
-	if (!image) {
-		err = -ENOMEM;
-		goto out;
-	}
-
  	link = kzalloc(sizeof(*link), GFP_USER);
  	if (!link) {
  		err = -ENOMEM;
@@ -133,7 +128,8 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
  	err = bpf_struct_ops_prepare_trampoline(tlinks, link,
  						&st_ops->func_models[op_idx],
  						&dummy_ops_test_ret_function,
-						image, image + PAGE_SIZE);
+						&image, &image_off,
+						true);
  	if (err < 0)
  		goto out;
 
@@ -147,7 +143,7 @@ int bpf_struct_ops_test_run(struct bpf_prog *prog, const union bpf_attr *kattr,
  		err = -EFAULT;
  out:
  	kfree(args);
-	arch_free_bpf_trampoline(image, PAGE_SIZE);
+	bpf_struct_ops_tramp_buf_free(image);
  	if (link)
  		bpf_link_put(&link->link);
  	kfree(tlinks);