Skip to contentSkip to conversation

bpf: Lift hashtab key_size limit

PATCH Superseded Florian Lehner 2 participants 3 messages Oct 24, 2020 – Oct 27, 2020

Subsystems (5)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 bpf: Lift hashtab key_size limit

Currently key_size of hashtab is limited to MAX_BPF_STACK. As the key of hashtab can also be a value from a per cpu map it can be larger than MAX_BPF_STACK.

The use-case for this patch originates to implement allow/disallow lists for files and file paths. The maximum length of file paths is defined by PATH_MAX with 4096 chars including nul.
This limit exceeds MAX_BPF_STACK.

Changelog:

v3:
- Rebase

v2:
- Add a test for bpf side

---
 kernel/bpf/hashtab.c                          | 16 +++----
 .../selftests/bpf/prog_tests/hash_large_key.c | 28 ++++++++++++
 .../selftests/bpf/progs/test_hash_large_key.c | 45 +++++++++++++++++++
 tools/testing/selftests/bpf/test_maps.c       |  2 +-
 4 files changed, 79 insertions(+), 12 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/hash_large_key.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_hash_large_key.c
kernel/bpf/hashtab.c +5 -11
index 1815e97d4c9c..10097d6bcc35 100644
@@ -390,17 +390,11 @@ static int htab_map_alloc_check(union bpf_attr *attr)
 	    attr->value_size == 0)
 		return -EINVAL;
 
-	if (attr->key_size > MAX_BPF_STACK)
-		/* eBPF programs initialize keys on stack, so they cannot be
-		 * larger than max stack size
-		 */
-		return -E2BIG;
-
-	if (attr->value_size >= KMALLOC_MAX_SIZE -
-	    MAX_BPF_STACK - sizeof(struct htab_elem))
-		/* if value_size is bigger, the user space won't be able to
-		 * access the elements via bpf syscall. This check also makes
-		 * sure that the elem_size doesn't overflow and it's
+	if ((attr->key_size + attr->value_size) >= KMALLOC_MAX_SIZE -
+	    sizeof(struct htab_elem))
+		/* if key_size + value_size is bigger, the user space won't be
+		 * able to access the elements via bpf syscall. This check
+		 * also makes sure that the elem_size doesn't overflow and it's
 		 * kmalloc-able later in htab_map_update_elem()
 		 */
 		return -E2BIG;
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +28 -0
new file mode 100644
index 000000000000..962f56060b76
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2020 Florian Lehner
+
+#include <test_progs.h>
+
+void test_hash_large_key(void)
+{
+	const char *file = "./test_hash_large_key.o";
+	int prog_fd, map_fd[2];
+	struct bpf_object *obj = NULL;
+	int err = 0;
+
+	err = bpf_prog_load(file, BPF_PROG_TYPE_CGROUP_SKB, &obj, &prog_fd);
+	if (CHECK_FAIL(err)) {
+		printf("test_hash_large_key: bpf_prog_load errno %d", errno);
+		goto close_prog;
+	}
+
+	map_fd[0] = bpf_find_map(__func__, obj, "hash_map");
+	if (CHECK_FAIL(map_fd[0] < 0))
+		goto close_prog;
+	map_fd[1] = bpf_find_map(__func__, obj, "key_map");
+	if (CHECK_FAIL(map_fd[1] < 0))
+		goto close_prog;
+
+close_prog:
+	bpf_object__close(obj);
+}
tools/testing/selftests/bpf/progs/test_hash_large_key.c new file +45 -0

45 lines not on this page · raw message

tools/testing/selftests/bpf/test_maps.c +1 -1
index 0d92ebcb335d..17fe19a2114d 100644
@@ -1225,7 +1225,7 @@ static void test_map_large(void)
 {
 	struct bigkey {
 		int a;
-		char b[116];
+		char b[4096];
 		long long c;
 	} key;
 	int fd, i, value;
Signature · 1 line
2.26.2
#1 lore raw
Quoted 12 lines · Florian Lehner

Currently key_size of hashtab is limited to MAX_BPF_STACK. As the key of hashtab can also be a value from a per cpu map it can be larger than MAX_BPF_STACK.

The use-case for this patch originates to implement allow/disallow lists for files and file paths. The maximum length of file paths is defined by PATH_MAX with 4096 chars including nul.
This limit exceeds MAX_BPF_STACK.

Changelog:

Quoted 8 lines

v3:
- Rebase

v2:
- Add a test for bpf side

---

You dropped the ack from John, btw.

Quoted 18 lines
 kernel/bpf/hashtab.c                          | 16 +++----
 .../selftests/bpf/prog_tests/hash_large_key.c | 28 ++++++++++++
 .../selftests/bpf/progs/test_hash_large_key.c | 45 +++++++++++++++++++
 tools/testing/selftests/bpf/test_maps.c       |  2 +-
 4 files changed, 79 insertions(+), 12 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/hash_large_key.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_hash_large_key.c
kernel/bpf/hashtab.c +0 -2
index 1815e97d4c9c..10097d6bcc35 100644
@@ -390,17 +390,11 @@ static int htab_map_alloc_check(union bpf_attr *attr)
            attr->value_size == 0)
                return -EINVAL;
 
-       if (attr->key_size > MAX_BPF_STACK)
-               /* eBPF programs initialize keys on stack, so they cannot be

kernel/bpf/hashtab.c static int htab_map_alloc_check(union bpf_attr *attr) · line 393

Quoted 10 lines
kernel/bpf/hashtab.c +1 -9
-                * larger than max stack size
-                */
-               return -E2BIG;
-
-       if (attr->value_size >= KMALLOC_MAX_SIZE -
-           MAX_BPF_STACK - sizeof(struct htab_elem))
-               /* if value_size is bigger, the user space won't be able to
-                * access the elements via bpf syscall. This check also makes
-                * sure that the elem_size doesn't overflow and it's
+       if ((attr->key_size + attr->value_size) >= KMALLOC_MAX_SIZE -

key_size+value_size can overflow, can't it? So probably want to cast to (size_t) or __u64?

Quoted 16 lines
kernel/bpf/hashtab.c +4 -0
+           sizeof(struct htab_elem))
+               /* if key_size + value_size is bigger, the user space won't be
+                * able to access the elements via bpf syscall. This check
+                * also makes sure that the elem_size doesn't overflow and it's
                 * kmalloc-able later in htab_map_update_elem()
                 */
                return -E2BIG;
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +3 -0
new file mode 100644
index 000000000000..962f56060b76
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2020 Florian Lehner
+

tools/testing/selftests/bpf/prog_tests/hash_large_key.c line 13

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +10 -0
+#include <test_progs.h>
+
+void test_hash_large_key(void)
+{
+       const char *file = "./test_hash_large_key.o";
+       int prog_fd, map_fd[2];
+       struct bpf_object *obj = NULL;
+       int err = 0;
+
+       err = bpf_prog_load(file, BPF_PROG_TYPE_CGROUP_SKB, &obj, &prog_fd);

Please utilize the BPF skeleton in the new tests.

tools/testing/selftests/bpf/prog_tests/hash_large_key.c line 24

Quoted 11 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +11 -0
+       if (CHECK_FAIL(err)) {
+               printf("test_hash_large_key: bpf_prog_load errno %d", errno);
+               goto close_prog;
+       }
+
+       map_fd[0] = bpf_find_map(__func__, obj, "hash_map");
+       if (CHECK_FAIL(map_fd[0] < 0))
+               goto close_prog;
+       map_fd[1] = bpf_find_map(__func__, obj, "key_map");
+       if (CHECK_FAIL(map_fd[1] < 0))
+               goto close_prog;

You are not really checking much here.

Why don't you check that the value was set to 42 here? Consider also using big global variables as your key and value. You can specify them from user-space with BPF skeleton easily to any custom value (not just zeroes).

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +4 -0
+
+close_prog:
+       bpf_object__close(obj);
+}

[...]

#2 lore raw
Quoted 5 lines · Andrii Nakryiko
Quoted 3 lines

---

You dropped the ack from John, btw.

I was not sure if it is ok to keep the ACK for an updated patch. So I did not include it.

Quoted 16 lines
Quoted 16 lines
 kernel/bpf/hashtab.c                          | 16 +++----
 .../selftests/bpf/prog_tests/hash_large_key.c | 28 ++++++++++++
 .../selftests/bpf/progs/test_hash_large_key.c | 45 +++++++++++++++++++
 tools/testing/selftests/bpf/test_maps.c       |  2 +-
 4 files changed, 79 insertions(+), 12 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/hash_large_key.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_hash_large_key.c
kernel/bpf/hashtab.c +0 -0
index 1815e97d4c9c..10097d6bcc35 100644
@@ -390,17 +390,11 @@ static int htab_map_alloc_check(union bpf_attr *attr)
            attr->value_size == 0)
                return -EINVAL;
 
Quoted 16 lines

kernel/bpf/hashtab.c static int htab_map_alloc_check(union bpf_attr *attr) · line 393

Quoted 12 lines
kernel/bpf/hashtab.c +1 -11
-       if (attr->key_size > MAX_BPF_STACK)
-               /* eBPF programs initialize keys on stack, so they cannot be
-                * larger than max stack size
-                */
-               return -E2BIG;
-
-       if (attr->value_size >= KMALLOC_MAX_SIZE -
-           MAX_BPF_STACK - sizeof(struct htab_elem))
-               /* if value_size is bigger, the user space won't be able to
-                * access the elements via bpf syscall. This check also makes
-                * sure that the elem_size doesn't overflow and it's
+       if ((attr->key_size + attr->value_size) >= KMALLOC_MAX_SIZE -

key_size+value_size can overflow, can't it? So probably want to cast to (size_t) or __u64?

I will add this cast to u64.

Quoted 20 lines
Quoted 20 lines
kernel/bpf/hashtab.c +4 -0
+           sizeof(struct htab_elem))
+               /* if key_size + value_size is bigger, the user space won't be
+                * able to access the elements via bpf syscall. This check
+                * also makes sure that the elem_size doesn't overflow and it's
                 * kmalloc-able later in htab_map_update_elem()
                 */
                return -E2BIG;
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +7 -0
new file mode 100644
index 000000000000..962f56060b76
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2020 Florian Lehner
+
+#include <test_progs.h>
+
+void test_hash_large_key(void)
+{
Quoted 9 lines

tools/testing/selftests/bpf/prog_tests/hash_large_key.c line 13

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +6 -0
+       const char *file = "./test_hash_large_key.o";
+       int prog_fd, map_fd[2];
+       struct bpf_object *obj = NULL;
+       int err = 0;
+
+       err = bpf_prog_load(file, BPF_PROG_TYPE_CGROUP_SKB, &obj, &prog_fd);

Please utilize the BPF skeleton in the new tests.

I will update the test and utilize the BPF skeleton.

Quoted 26 lines

tools/testing/selftests/bpf/prog_tests/hash_large_key.c line 24

Quoted 11 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +11 -0
+       if (CHECK_FAIL(err)) {
+               printf("test_hash_large_key: bpf_prog_load errno %d", errno);
+               goto close_prog;
+       }
+
+       map_fd[0] = bpf_find_map(__func__, obj, "hash_map");
+       if (CHECK_FAIL(map_fd[0] < 0))
+               goto close_prog;
+       map_fd[1] = bpf_find_map(__func__, obj, "key_map");
+       if (CHECK_FAIL(map_fd[1] < 0))
+               goto close_prog;

You are not really checking much here.

Why don't you check that the value was set to 42 here? Consider also using big global variables as your key and value. You can specify them from user-space with BPF skeleton easily to any custom value (not just zeroes).

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/hash_large_key.c new file +4 -0
+
+close_prog:
+       bpf_object__close(obj);
+}

[...]